Three Classes of Polynomial Systems

The classification in Table 1 is inspired by [44]. The dense class is closest to the common algebraic description, whereas the determinantal systems arise in enumerative geometry.

 

Table 1: Key words of the three classes of polynomial systems.

system	model	theory	space
dense	highest degrees	Bézout	${\Bbb P}^n$	projective
sparse	Newton polytopes	Bernshtein	$({\Bbb C}^*)^n$	toric
determinantal	localization posets	Schubert	Gmr	Grassmannian

 

For the vector of unknowns ${\bf x} = (x_1,x_2,\ldots,x_n)$and exponents ${\bf a} = (a_1,a_2,\ldots,a_n) \in {\Bbb N}^n$, denote ${\bf x}^{\bf a} = x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$. A polynomial system $P({\bf x}) = {\bf0}$ is given by $P = (p_1,p_2,\ldots,p_n)$, a tuple of polynomials $p_i \in {\Bbb C}[{\bf x}]$, $i = 1,2,\ldots,n$.

The complexity of a dense polynomial p is measured by its degree d:

$$p({\bf x}) = \sum_{0 \leq a_1+a_2+\cdots+a_n \leq d} c_{\bf a} {\bf x}^{\bf a}, \quad \quad d = \deg(p),$$ (1)

where at least one monomial of degree d should have a nonzero coefficient. The total degree D of a dense system P is $D = \prod_{i=1}^n \deg(p_i)$.

Theorem 2.1 (Bézout [15])   The system $P({\bf x}) = {\bf0}$ has no more than D isolated solutions, counted with multiplicities.

Consider for example

$$P(x_1,x_2) = \left\{ \begin{array}{r} x_1^4 + x_1 x_2 + ... ...y} \right. \quad {\rm with~total~degree}~D = 4 \times 4 = 16.$$ (2)

Although D = 16, this system has only eight solutions because of its sparse structure.

The support A of a sparse polynomial p collects all exponents of those monomials whose coefficients are nonzero. Since we allow negative exponents ( ${\bf a} \in {\Bbb Z}^n$), we restrict ${\bf x} \in ({\Bbb C}^*)^n$, ${\Bbb C}^* = {\Bbb C}\setminus \{ 0 \}$.

$$p({\bf x}) = \sum_{{\bf a} \in A} c_{\bf a} {\bf x}^{\bf a}, ... ...not= 0, \quad A \subset {\Bbb Z}^n, \quad \char93 A < \infty.$$ (3)

The Newton polytope Q of p is the convex hull of the support Aof p. We model the structure of a sparse system P by a tuple of Newton polytopes ${\cal Q} = (Q_1,Q_2,\ldots,Q_n)$, spanned by ${\cal A} = (A_1,A_2,\ldots,A_n)$, the so-called supports of P.

The volume of a positive linear combination of polytopes is a homogeneous polynomial in the multiplication factors. The coefficients are mixed volumes. For instance, for (Q₁,Q₂), we write:

$$2!{\rm vol}_2(\lambda_1 Q_1 + \lambda_2 Q_2) = V_2(Q_1,Q_1... ... V_2(Q_1,Q_2) \lambda_1 \lambda_2 + V_2(Q_2,Q_2) \lambda_2^2,$$ (4)

normalizing $V_2(Q,Q) = 2! {\rm vol}_2(Q)$. For the Newton polytopes of the system (2): $2! {\rm vol}_2(\lambda_1 Q_1 + \lambda_2 Q_2) = 4 \lambda_1^2 + 2 \cdot 8 \lambda_1 \lambda_2 + 5 \lambda_2^2$. To interpret this we look at Figure 1 and see that multiplying P₁ and P₂ respectively by $\lambda_1$ and $\lambda_2$ changes their areas respectively with $\lambda_1^2$ and $\lambda_2^2$. The cells in the subdivision of Q₁ + Q₂ whose area is scaled by $\lambda_1 \lambda_2$ contribute to the mixed volume. So, for the example in (2), the root count is eight.

  

Figure 1: Newton polytopes Q₁, Q₂, a mixed subdivision of Q₁ + Q₂ with volumes.

Theorem 2.2 (Bernshtein [7])   A system $P({\bf x}) = {\bf0}$ with Newton polytopes ${\cal Q}$ has no more than $V_n({\cal Q})$ isolated solutions in $({\Bbb C}^*)^n$, counted with multiplicities.

The mixed volume was nicknamed [13] as the BKK bound to honor Bernshtein [7], Kushnirenko [51], and Khovanskii [49].

For the third class of polynomial systems we consider a matrix [C | X]where $C \in {\Bbb C}^{(m+r) \times m}$ and $X \in {\Bbb C}^{(m+r) \times r}$respectively collect the coefficients and indeterminates. Laplace expansion of the maximal minors of [C | X] in m-by-m and r-by-r minors yields a determinantal polynomial

$$p({\bf x}) = \sum_{\scriptsize\begin{array}{c} I \cup J = U... ...} } {\rm sign}(I,J) C[I] X[J], \quad U = \{ 1,2,\ldots,m+r\},$$ (5)

where the summation runs over all distinct choices I of m elements of U. The partition $\{ I, J \}$ of U defines the permutation $U \mapsto (I,J)$with ${\rm sign}(I,J)$ its sign. The symbols C[I] and X[I] respectively represent coefficient minors and minors of indeterminates. Note that for more general intersection conditions, the matrices [C | X] are not necessarily square.

The vanishing of a polynomial as in (5) expresses the condition that the r-plane X meets a given m-plane nontrivially. The counting and finding of all figures that satisfy certain geometric conditions is the central theme of enumerative geometry. For example, consider the following.

Theorem 2.3 (Schubert [91])   Let $m,r \geq 2$. In  ${\Bbb C}^{m+r}$ there are

$$d_{m,r} \quad = \quad \frac{1! \, 2! \, 3! \cdots (r\!- \!... ...\! + \! 1)! \, (m \! + \! 2)! \cdots(m \! + \! r \! - \! 1)!}$$ (6)

r-planes that nontrivially meet mr given m-planes in general position.

This root count d_m,r is sharp compared to other root counts, see [98] and [114] for examples.

We can picture the simplest case, using the fact that 2-planes in ${\Bbb C}^4$represent lines in ${\Bbb P}^3$. In Figure 2 the positive real projective 3-space corresponds to the interior of the tetrahedron.

$\parbox{5cm}{ \par \centerline{\psfig{figure=psfgrass.ps,width=5cm}} \par ~~~~~Figure~2: $m = 2 = r$ . \par \addtocounter{figure}{1} \par }$ $\parbox{10cm}{ \par \smallskip \par In Figure~2, we see two thick l... ...specialization of the solution $r$ -plane when the input is specialized. \par }$

Algorithmic proofs for the above theorems consist in two steps. First we show how to construct a generic start system that has exactly as many regular solutions as the root count. Then we set up a homotopy for which all isolated solutions of any particular target system lie at the end of some solution path originating at some solution of the constructed start system.