\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Uwe Schauz}
%
%
\medskip
\noindent
%
%
{\bf Algebraically Solvable Problems: Describing Polynomials as Equivalent to Explicit Solutions}
%
%
\vskip 5mm
\noindent
%
%
%
%
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|_{\hbox{\font\fraktur=cmfrak8 {\fraktur X}}_1\times\cdots\times
\hbox{\font\fraktur=cmfrak8 {\fraktur X}}_n}$ when only incomplete information
about the polynomial $P(X_1,\dots,X_n)$ is given.

In a very general working frame, the grid points
$x\in\hbox{\font\fraktur=cmfrak10 {\fraktur X}}_1\times\cdots\times
\hbox{\font\fraktur=cmfrak10 {\fraktur X}}_n$ which do not vanish under an
algebraic solution -- a certain describing polynomial
$P(X_1,\dots,X_n)$ -- 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 ${\cal S}$, which may be called
the {\em set of solutions}; and a subset ${\cal S}_{\rm
triv}\subseteq{\cal S}$, the {\em set of trivial solutions}.

We give several examples of how to find algebraic solutions, and 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.

\smallskip

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.

\bye