Algebraically Solvable Problems: Describing Polynomials as Equivalent to Explicit Solutions

Abstract

The main result of this paper is a coefficient formula that sharpens and generalizes Alon and Tarsi's Combinatorial Nullstellensatz. On its own, it is a result about polynomials, providing some information about the polynomial map $P|_X$ when only incomplete information about the polynomial $P$ is given.

In a very general working frame, the grid points $x\in X:=X_1\times\dots\times X_n$ which do not vanish under an algebraic solution - a certain describing polynomial $P$ - correspond to the explicit solutions of a problem. As a consequence of the coefficient formula, we prove that the existence of an algebraic solution is equivalent to the existence of a nontrivial solution to a problem. By a problem, we mean everything that "owns" both, a set $S$, which may be called the set of solutions; and a subset $S_t\subset S$, the set of trivial solutions.

We give several examples on how to find algebraic solutions, and on how to apply our coefficient formula. These examples are mainly from graph theory and combinatorial number theory, but we also prove several versions of Chevalley and Warning's Theorem, including a generalization of Olson's Theorem, as examples and useful corollaries.

We obtain a permanent formula by applying our coefficient formula to the matrix polynomial, which is a generalization of the graph polynomial. This formula is an integrative generalization and sharpening of:

1. Ryser's permanent formula.

2. Alon's Permanent Lemma.

3. Alon and Tarsi's Theorem about orientations and colorings of graphs.

Furthermore, in combination with the Vigneron-Ellingham-Goddyn property of planar n-regular graphs, the formula contains as very special cases:

4. Scheim's formula for the number of edge n-colorings of such graphs.

5. Ellingham and Goddyn's partial answer to the list coloring conjecture.

In a further application of our coefficient formula, we prove a sharpening of Warning's classical result about the number of simultaneous zeros of systems of polynomial equations over finite fields.

We discuss the numerical aspects of using algebraic solutions to find explicit solutions, and present two polynomial-time algorithms that find nonzeros of polynomials. One of these algorithms is derived as a winning strategy of a new coloration game for polynomials (and graphs). It also satisfies a request by Alon and Tarsi for a purely combinatorial proof of their theorem about orientations and colorings of graphs (point 3 above).

Die direkteste und beste Art, ein Existenzproblem zu lösen, besteht darin, eine explizite Lösung anzugeben. Ist dies nicht möglich, so kann man sich nach einer algebraischen Lösung, also einem beschreibenden Polynom mit gewissen Eigenschaften wie z.B. niedrigem Totalgrad, umsehen. Wir zeigen, dass die Existenz einer algebraischen Lösung äquivalent ist zur Existenz einer expliziten Lösung des Problems. Wobei wir unter einem "Problem" alles verstehen, was eine Menge $S$ und eine Teilmenge $S_t\subset S$ "besitzt", deren Elemente man "Lösungen" bzw. "triviale Lösungen" nennt.

Diese Äquivalenz basiert auf Alon und Tarsis kombinatorischem Nullstellensatz, für den wir eine verschärfte und verallgemeinerte Fassung (eine Koeffizientenformel) und einige nützliche Korollare, einschließlich einer Verallgemeinerung von Olsons Theorem, vorstellen. Die Verschärfung erlaubt auch (gewichtet) quantitative Rückschlüsse über die Lösungen eines Problems. Sie ist ursprünglich ein Resultat über Polynome und liefert Informationen über die polynomiale Abbildung $P|_X$, wenn nur unvollständige Informationen über das Polynom $P$ gegeben sind. All das hat zu tun mit Interpolationspolynomen auf endlichen "Rastern" $X:=X_1\times\dots\times X_n\subseteq R^n$ über kommutativen Ringen $R$.

Wir geben verschiedene Beispiele, wie man algebraische Lösungen finden und die Koeffizientenformel (kombinatorischer Nullstellensatz) anwenden kann. Diese Beispiele stammen hauptsächlich aus der Graphentheorie und der kombinatorischen Zahlentheorie. Der Chevalley-Warning Satz ist eine weitere Anwendung.

Wir wenden unsere Koeffizientenformel auf das Matrizenpolynom, eine Verallgemeinerung des Graphenpolynoms, an und erhalten eine Permanentenformel. Diese Formel ist eine vereinheitlichende Verallgemeinerung und Verschärfung von:

1. Rysers Permanentenformel.

2. Alons Permanentenlemma.

3. Alon und Tarsis Theorem über Orientierungen und Färbungen von Graphen.

In Kombination mit der Vigneron-Ellingham-Goddyn Eigenschaft planarer n-regulärer Graphen enthält sie außerdem, als kleine Spezialfälle:

4. Scheims Formel für die Anzahl der Kantenfärbungen derartiger Graphen mit n Farben.

5. Ellingham und Goddyns teilweise Bestätigung der Listenfärbungsvermutung.

In einer weiteren Anwendung verschärfen wir Warnings klassisches Resultat über die Anzahl simultaner Nullstellen von Systemen von Polynomen über endlichen Körpern.

Wir diskutieren die numerischen Aspekte und präsentieren zwei Algorithmen mit polynomialer Laufzeit, die Nichtnullstellen von Polynomen finden. Einen dieser Algorithmen erhalten wir als Gewinnstrategie zu einem neuen Färbungsspiel für Polynome (und Graphen). Dies führt auch zu einem rein kombinatorischen Beweis des Satzes von Alon und Tarsi (Punkt 3 oben).