Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 40 (1999), No. 2, 343-350.

The Maximum Number of Real Roots of a Multihomogeneous System of Polynomial Equations

Andrew McLennan*

Department of Economics, University of Minnesota 271 19th Avenue South, Minneapolis, MN 55455 e-mail: mclennan@atlas.socsci.umn.edu

Abstract. A multihomogeneous system of polynomial equations, with as many equations as degrees of freedom, has instances for which there are as many regular real roots, in the relevant product of projective spaces, as are allowed, for the corresponding dehomogenized system, by Bernshtein’s [1] theorem. One may, in addition, require that all roots lie in a prescribed open subset of the solution space. The maximal number of roots is characterized as a multiple (by the inverse of a product of factorials) of the permanent of a certain matrix, and recursive formulas are given for this number.

344 A. McLennan:The maximum number of real roots of a …

This note characterizes the maximal number of regular real roots of a system of polynomial equations that is multihomogeneous, in the sense that the variables of the system are partitioned into groups, with each equation being homogeneous separately in the variables of each group. (In this note a root is a vector of nonzero numbers that satisfy the equations.) The main result is that, for systems in this class, there are open sets of coefficient vectors on which the number of real regular roots is the generic (in the space of complex coefficient vectors) number of complex roots, as given by Bernshtein’s [1] theorem. To see that this will not be the case for general sparse systems one may consider that the univariate example a_{0} + a_{3}x^{3} has (for a_{0}, a_{3} ≠ 0) one real root and two other complex roots ^{1}. It is easy to find systems outside the multihomogeneous class that can have as many regular real roots as Bernshtein’s theorem allows, e.g., ax + by^{2} = 0 = cx + dy, but we have little else to say about the class of systems with this property. Our method is constructive, and it does allow the result to be sharpened in one respect: for any nonempty open set U in the solution space we can find an open set of coefficient vectors on which U contains the maximal number of roots.

* I have benefited from comments by participants in seminars at the University of Minnesota and meetings of the AMS at Temple University. Conversations with Jesus DeLoera have been very helpful, and an anonymous referee provided several useful suggestions.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1999 Heldermann Verlag

We also express the maximal number of roots in terms of the permanent of a certain matrix, and provide a recursive formula that serves as the basis of efficient algorithms for computing the number.

Examples of multihomogeneous equations include the (singly) homogeneous equations considered in Bezout’s theorem, multilinear functions, and the equations characterizing totally mixed Nash equilibrium of a normal form game. The systems occurring in the definition of totally mixed Nash equilibrium are studied by McKelvey and McLennan [8]; the results and proofs here are straightforward generalizations of that work. The mean (with respect to a natural distribution on coefficient vectors) number of totally mixed Nash equilibria is studied in [9], and that analysis is extended to general multihomogeneous systems in [10].

The general form of a sparse system of n polynomial equations in n variables is

f(x) = (f_{1}(x), …, f_{n}(x)) = 0,  (1)

where x = (x_{1}, …, x_{n}) and, for each i = 1, …, n, there is a nonempty finite A_{i} ⊂ N^{n} such that f_{i}(x) = ∑_{a∈A_{i}} f_{ia}x^{a} for some coefficients f_{ia}. (Here x^{a} = x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}}.) We will be most interested in real coefficients f_{ia}, but for several points in the argument we consider the space of vectors of complex coefficients. Let H^{ℝ} (H^{ℂ}) be the set of f with real (complex) coefficients in which no f_{i} vanishes identically. Let ℝ^{∗} = ℝ\{0} and ℂ^{∗} = ℂ\{0}. Consider (f, x) ∈ H^{ℝ} × (ℝ^{∗})^{n} (H^{ℂ} × (ℂ^{∗})^{n}). Since x has only nonzero components, no monomial x^{a} vanishes. Since the coefficients of each f_{i} can be varied freely near f_{i} without leaving H^{ℝ} (H^{ℂ}), it follows that (f, x) is a regular point of the map (f, x) ↦ f(x). The regular value theorem implies that

V^{ℝ} := { (f, x) ∈ H^{ℝ} × (ℝ^{∗})^{n} : f(x) = 0 } and V^{ℂ} := { (f, x) ∈ H^{ℂ} × (ℂ^{∗})^{n} : f(x) = 0 }

are smooth manifolds of the same dimensions as H^{ℝ} and H^{ℂ} respectively.

Let π^{ℝ} : V^{ℝ} → H^{ℝ} and π^{ℂ} : V^{ℂ} → H^{ℂ} be the restrictions of the natural projections. Evidently (f, x) is a regular point of π^{ℝ} (π^{ℂ}) if and only if there are no vectors in T_{(f,x)}V^{ℝ} (T_{(f,x)}V^{ℂ}) that are parallel to (ℝ^{∗})^{n} ((ℂ^{∗})^{n}), which is precisely the condition that x is a regular point of f. Let U^{ℝ} and U^{ℂ} be the sets of f in H^{ℝ} and H^{ℂ} having only regular roots. Applications of Sard’s theorem to π^{ℝ} and π^{ℂ} show that U^{ℝ} and U^{ℂ} are dense.

1 Observing that the support of this polynomial, namely the set of monomials {1, x^{3}} is not “convex” in the sense that it does not also contain x or x^{2}, one might wonder whether convexity of the supports was sufficient for there to exist coefficient vectors with the number of regular real roots allowed by Bernshtein’s theorem. The system ax + by^{2} = 0 = cx^{2} + dy shows that this is not the case.

The convex hull of A_{i} is denoted by Q_{i}, and is called the Newton polytope of f_{i}. Generalizing a result of Kushnirenko [6], Bernshtein [1] shows that, for the general system (1), every f in a dense subset of U^{ℂ} has MV(Q_{1}, …, Q_{n}) roots in (ℂ^{∗})^{n}, where MV(Q_{1}, …, Q_{n}) is the mixed volume of the n-tuple of Newton polytopes. (The concept of mixed volume is due to Minkowski; Betke [2] is a recent treatment.)

Let ρ(A_{1}, …, A_{n}) be the maximal number of real regular roots of f ∈ U^{ℝ}. Other work studying ρ(A_{1}, …, A_{n}) includes the theory of fewnomials of Khovanski [5], in which arguments are based on the number |A_{i}| of monomials in each equation, and Sturmfels [12] and Itenberg and Roy [4], who use the methods of the theory of sparse systems of polynomials to derive bounds on ρ(A_{1}, …, A_{n}). (This line of research is very clearly described in [13].) Supports A_{1}, …, A_{n} for which ρ(A_{1}, …, A_{n}) = MV(Q_{1}, …, Q_{n}), as in our main result, are interesting from the point of view of the conjectures presented by Itenberg and Roy (for which a counterexample has been developed by Li and Wang [7]) since the assertions of these conjectures can hold only in quite particular ways.

Some of these authors also consider the maximal number of roots in the various orthants of ℝ^{n}. Let ρ_{+}(A_{1}, …, A_{n}) be the maximal number of regular roots in the (strictly) positive orthant of ℝ^{n}. We will say that a set A ⊂ N^{n} is comprehensive if a ∈ A whenever a, b ∈ N^{n} with a ≤ b ∈ A. The next result shows that ρ_{+}(A_{1}, …, A_{n}) = ρ(A_{1}, …, A_{n}) when A_{1}, …, A_{n} are comprehensive, as is the case for the class of systems studied here.

Lemma 1. If A_{1}, …, A_{n} are comprehensive, then, for any C ∈ ℝ, it is possible to find f ∈ U^{ℝ} for which there are ρ(A_{1}, …, A_{n}) regular roots in (C, ∞)^{n}.

Proof. Choose f′ ∈ U^{ℝ} with ρ(A_{1}, …, A_{n}) regular roots in ℝ^{∗}. Let D be a number such that all roots are in (D, ∞)^{n}, let \underline{x} = (D − C, …, D − C) ∈ ℝ^{n}, and let f(x) = f′(x + \underline{x}). Since each A_{i} is comprehensive, each f_{i} has no monomials with nonzero coefficients that are not in A_{i}. The roots of f are the roots of f′ translated by \underline{x}, so all of them are in (C, ∞)^{n}. In addition f ∈ U^{ℝ}, since if it had irregular roots, so would f′, contrary to the requirement that f′ ∈ U^{ℝ}. □

This note focuses on the specialization of the general framework in which the variables in x are divided into k groups, so that x = (y^{1}, …, y^{k}) where y^{j} = (y_{1}^{j}, …, y_{n_{j}}^{j}), and there are nonnegative integers δ_{ij} (i = 1, …, n, j = 1, …, k) such that

A_{i} = A_{i1} × … × A_{ik}, where A_{ij} = { a ∈ N^{n_{j}} : a_{1} + … + a_{n_{j}} ≤ δ_{ij} }.  (2)

To see the significance of this we construct the associated “multihomogenized” system of equations. A new collection of variables is given by x̂ = (ŷ^{1}, …, ŷ^{k}) where ŷ^{j} = (y_{0}^{j}, y_{1}^{j}, …, y_{n_{j}}^{j}). Let

Â_{i} = Â_{i1} × … × Â_{ik}, where Â_{ij} = { â ∈ N^{n_{j}+1} : â_{0} + â_{1} + … + â_{n_{j}} = δ_{ij} }.

There are bijections β_{ij} : Â_{ij} → A_{ij} and β_{i} : Â_{i} → A_{i} given by β_{ij}(â_{0}, â_{1}, …, â_{n_{j}}) = (â_{1}, …, â_{n_{j}}) and β_{i}(â^{1}, …, â^{k}) = (β_{i1}(â^{1}), …, β_{ik}(â^{k})). For each instance of (1) there is an associated multihomogeneous system of equations

f̂(x̂) = (f̂_{1}(x̂), …, f̂_{n}(x̂)) = 0 ∈ ℝ^{n} where f̂_{i}(x̂) = ∑_{â∈Â_{i}} f_{iβ_{i}(â)}x̂â.  (3)

Remark 1. The case k = 1 recovers the general homogeneous system considered by Bezout’s theorem. If δ_{ij} = 1 for all i and j, then each f_{i} is a multilinear functional. The definition of a totally mixed Nash equilibrium of a normal form game gives rise to a multihomogeneous system in which, for each j = 1, …, k, there are n_{j} indices i for which δ_{i}^{j} = 0 and δ_{ij′} = 1 for all j′ ≠ j.

The natural spaces in which to look for, and count, solutions of (3), are the products of projective spaces P^{K} = P^{n_{1}}(K) × … × P^{n_{k}}(K), for K = ℝ^{∗}, ℝ, ℂ^{∗}, ℂ. In the obvious way we regard these spaces as nested: P^{ℝ^{∗}} ⊂ P^{ℝ} ⊂ P^{ℂ} and P^{ℝ^{∗}} ⊂ P^{ℂ^{∗}} ⊂ P^{ℂ}. For

x̂ = (ŷ^{1}, …, ŷ^{k}) ∈ (ℂ^{n_{1}+1}\{0}) × … × (ℂ^{n_{k}+1}\{0})

let [x̂] = ([ŷ^{1}], …, [ŷ^{k}]) denote the corresponding element of P^{ℂ}. If x = (y^{1}, …, y^{k}) is a solution of (1), where y^{j} = (y_{1}^{j}, …, y_{n_{j}}^{j}), then an associated solution x̂ of (3) is derived by setting ŷ^{j} = (1, y_{1}^{j}, …, y_{n_{j}}^{j}) and [x̂] = ([ŷ^{1}], …, [ŷ^{k}]). Although Theorem 1 below is most naturally understood as pertaining to (3), for several reasons it will be more convenient to argue in terms of system (1).

For systems satisfying (2), a root [x̂] ∈ P^{ℂ} of f̂ is said to be regular if x̂ is a regular point of f̂. It is easy to show that if x̂ = (ŷ^{1}, …, ŷ^{k}) is a regular point of f̂, then so is (α^{1}ŷ^{1}, …, α^{k}ŷ^{k}) for any α^{1}, …, α^{k} ∈ ℂ^{∗}, so this definition is meaningful. Our main result is that, when (2) holds, there exists a real coefficient vector for which there are as many regular real roots as are allowed by Bernshtein’s theorem.

Theorem 1. When (2) holds, for any open Û ⊂ P^{ℝ} there is an f ∈ U^{ℝ} for which the corresponding f̂ has MV(Q_{1}, …, Q_{n}) regular roots in Û.

Remark 2. Theorem 1 suggests that multihomogeneous systems are well behaved in the sense of sharing properties of the general homogeneous system. Additional evidence for this point of view is given by Sturmfels and Zelevinsky [11], who give Sylvester type (that is, determinantal) formulas for the resultant of the unmixed (A_{0} = A_{1} = … = A_{n}) multihomogeneous system in which the number of equations exceeds the number of degrees of freedom by one.

Theorem 1 follows from Lemmas 2–4 below.

Lemma 2. If (2) holds, there is an f ∈ U^{ℝ} for which the corresponding f̂ has no roots in P^{ℂ} \ P^{ℝ^{∗}}.

Proof. For each i let

f_{i}(x) = ∏_{j=1}^{k} ∏_{ℓ=1}^{δ_{ij}} μ_{i}^{jℓ}(y^{j})

for some choice of affine functionals μ_{i}^{jℓ} : ℝ^{n_{j}} → ℝ. It is easy to see that

f̂_{i}(x̂) = ∏_{j=1}^{k} ∏_{ℓ=1}^{δ_{ij}} μ̂_{i}^{jℓ}(ŷ^{j}),

where, for each i, j, ℓ, μ̂_{i}^{jℓ} is the linear functional on ℝ^{n_{j}+1} that reduces to μ_{i}^{jℓ} under the specialization y_{0}^{j} = 1.

For each j let

E^{j} = { μ_{i}^{jℓ} : 1 ≤ i ≤ n, 1 ≤ ℓ ≤ δ_{ij} }.

We may choose the affine functionals μ_{i}^{jℓ} in general position in the sense that, for any subset E ⊂ E^{j}, the intersection of the kernels of the elements of E is an affine subspace of ℝ^{n_{j}} of dimension n_{j} − #E. We may also insist that the intersection of the kernels has an intersection with each coordinate subspace of the expected dimension, so that when #E = n_{j}, the unique common root has nonvanishing coordinates, and there are no roots when #E > n_{j}

Let [x̂] = ([ŷ^{1}], …, [ŷ^{k}]) be a projective root of (3). For each i there must be some (j_{i}, ℓ_{i}) such that μ̂_{i}^{j_{i}ℓ_{i}}(ŷ^{j_{i}}) = 0. The general position assumption implies that for each j there are at most n_{j} indices i with j_{i} = j, and since the total number of indices i is n = n_{1}+…+n_{k}, for each j there must be exactly n_{j} such i. Therefore each ŷ^{j} is a solution of a system of n_{j} linear equations in n_{j} + 1 variables that has exactly one projective root, which is real, namely [(1, y_{1}^{j}, …, y_{n_{j}}^{j})] where y^{j} = (y_{1}^{j}, …, y_{n_{j}}^{j}) is the unique root of the associated system of n_{j} affine functionals μ_{i}^{jℓ}. This shows that all roots of (3) are in P^{ℝ^{∗}}.

Suppose j_{i} = j. By varying y^{j} in the intersection of the kernels of the other μ_{i′}^{j_{i′} ℓ_{i′}} with j_{i′} = j, we may vary f_{i} without changing the value of any other f_{i′}. Thus the image of Df(x) spans the standard basis of ℝ^{n}, so x is a regular root. This shows that all roots are regular, so that f ∈ U^{ℝ}. □

Lemma 3. If, for some f ∈ U^{ℝ}, the corresponding f̂ has no roots in P^{ℂ} \ P^{ℝ^{∗}}, then

ρ(A_{1}, …, A_{n}) = MV(Q_{1}, …, Q_{n}).

Proof. Consider a root [x̂] of f̂. If x̂ = (ŷ^{1}, …, ŷ^{k}) where ŷ^{j} = (y_{0}^{j}, y_{1}^{j}, …, y_{n_{j}}^{j}), we set x = (y^{1}, …, y^{k}) where y^{j} = (y_{1}^{j}/y_{0}^{j}, …, y_{n_{j}}^{j}/y_{0}^{j}). Applying the (complex) implicit function theorem at x, then multihomogenizing, we see that there exist neighborhoods U_{[x̂]} ⊂ H^{ℂ} of f and W_{[x̂]} ⊂ P^{ℂ} of [x̂] for which

{ (f′, [x̂′]) ∈ U_{[x̂]} × W_{[x̂]} : [x̂′] is a root of f̂′ }

is the graph of a C^{∞} function r_{[x̂]} : U_{[x̂]} → W_{[x̂]}. At this point we have not used the hypothesis that f̂ has no roots outside of P^{ℝ^{∗}}, and by applying the argument to this point to some f̂ with the maximal number of real regular roots, we may conclude that

ρ(A_{1}, …, A_{n}) ≤ MV(Q_{1}, …, Q_{n}).

If every neighborhood of f in H^{ℂ} contained an f′ for which the associated f̂′ had a root in P^{ℂ} \ ⋃_{[x̂]} W_{[x̂]}, then, since this set is compact, it would contain a root of f̂, which is impossible. Consequently it must be possible to choose a neighborhood U of f small enough that, for every f′ ∈ U, the only roots of the associated f̂′ in P^{ℂ} are the various r_{[x̂]}(f′). Since U is open in H^{ℂ}, generic f′ ∈ U must have MV(Q_{1}, …, Q_{n}) roots, so we see that this number is also a lower bound on ρ(A_{1}, …, A_{n}). □

Lemma 4. Suppose that (2) holds, and f ∈ U^{ℝ}. If the corresponding f̂ has no roots in P^{ℂ} \ P^{ℝ^{∗}}, then for any open Û ⊂ P^{ℝ} there is an f′ ∈ U^{ℝ} for which the corresponding f̂′ has as many roots as f, with all of them lying in Û.

Proof. By Lemma 1, for arbitrary C ∈ ℝ we can find f′′ ∈ U^{ℝ} with as many regular real roots as f, and with all roots in (C, ∞)^{n}. If a neighborhood of

([(0, 1, …, 1)], …, [(0, 1, …, 1)]) ∈ P^{ℝ}

is given, then, by choosing C large, we can force the corresponding f̂′′ to have all its projective roots in this neighborhood. The action of the product group G = O(n_{1} + 1) × …×O(n_{k} +1) on ℝ^{n_{1}+1}×…×ℝ^{n_{k}+1} induces an action on the space of multilinear systems (3) with real coefficients. Under such a transformation, the roots of the transformed system are related to the roots of the given system by the corresponding action of G on P^{ℝ} = P^{n_{1}}(ℝ) × … × P^{n_{k}}(ℝ). By choosing an appropriate element of G we can move ([(0, 1, …, 1)], …, [(0, 1, …, 1)]) to any other point in P^{ℝ}, and under the induced action f̂′′ is transformed to a system f̂′ having all its roots in the corresponding neighborhood of the chosen point. With C sufficiently large, and the point in P^{ℝ} chosen suitably, this results in f̂′ having all its roots in Û. Finally, it is easy to check that the transformations considered in this argument preserve the regularity of all roots, so that f′ ∈ H^{ℝ}. □

Let n := (n_{1}, …, n_{k}), let δ be the n × k matrix with entries δ_{ij}, and let B(n, δ) be the Bernstein bound for the system given by (2). Let J be the set of n-tuples (j_{1}, …, j_{n}) such that, for each 1 ≤ j ≤ k, there are n_{j} indices i with j_{i} = j. For the coefficient vector constructed in the proof of Lemma 2, the roots are evidently in one-to-one correspondence with the set of n-tuples ((j_{1}, ℓ_{1}), …, (j_{n}, ℓ_{n})) such that (j_{1}, …, j_{n}) ∈ J and 1 ≤ ℓ_{i} ≤ δ_{ij_{i}} for all i. Thus

B(n, δ) = ∑_{(j_{1},...,j_{n})∈J} (∏_{i=1}^{n} δ_{ij_{i}}) .

Recall that the permanent (e.g., [3]) of an n × n matrix M with entries m_{ij} is

per(M) := ∑_{σ∈S_{n}} (∏_{i=1}^{n} m_{iσ(i)}) .

(Here S_{n} is the symmetric group.) Let M(n, δ) be the n×n matrix whose first n_{1} columns are the first column of δ, whose next n_{2} columns are the second column of δ, and so forth. The next result follows from the formula above because, for any (j_{1}, …, j_{n}) ∈ J, there are n_{1}! · . . . · n_{k}! permutations σ ∈ S_{n} such that, for each i, column σ(i) of M(n, δ) is column j_{i} of δ.

Theorem 2. B(n, δ) = \frac{per(M(n,δ))}{n_{1}!·...·n_{k}!}.

Let δ^{−i} be the (n − 1) × k matrix obtained by eliminating the i^{th} row of δ. Expansion of the permanent by minors yields the following recursive formulas:

Corollary 1. For all i = 1, …, n,

B(n, δ) = ∑_{j:n_{j}>0} δ_{ij} · B((n_{1}, …, n_{j} − 1, …, n_{k}), δ^{−i}).

Corollary 2. For all j = 1, …, k such that n_{j} > 0,

B(n, δ) = \frac{1}{n_{j}} ∑_{i=1}^{n} δ_{ij} · B((n_{1}, …, n_{j} − 1, …, n_{k}), δ^{−i}).

References

[1] Bernshtein, D. N.: The number of roots of a system of equations. Funct. Anal. Appl. 9 (1975), 183–185.

[2] Betke, U.: Mixed volumes of polytopes. Arch. Math. 58 (1992), 388–391.

[3] Egorychev, G. P.: Van der Waerden conjecture and applications. Handbook of Algebra, Vol. I, Elsevier, Amsterdam (1996), 3–26.

[4] Itenberg, I.; Roy, M.-F.: Multivariate Descartes’ rule. Beitr. Algebra Geom. 37 (1996), 337–346.

[5] Khovanski, A. G.: Fewnomials. Amer. Math. Soc., Translations of Math. Monographs, Vol. 88 (1991).

[6] Kushnirenko, A. G.: The Newton polyhedron and the number of solutions of a system of k equations in k unknowns. Uspsekhi Mat. Nauk. 30 (1975), 266–267.

[7] Li, T. Y.; Wang, X.: On multivariate Descartes’ rule – a counterexample. Preprint, Michigan State University (1997).

[8] McKelvey, R. D.; McLennan, A.: The maximal number of regular totally mixed Nash equilibria. J. Econ. Theory 72 (1997), 411–425.

[9] McLennan, A.: On the expected number of equilibria of a normal form game. Preprint, University of Minnesota (1997).

[10] McLennan, A.: The expected number of real roots of a multihomogeneous system of polynomial equations. Preprint, University of Minnesota (1998).

[11] Sturmfels, B.; Zelevinsky, A.: Multigraded resultants of Sylvester type. J. Algebra 163 (1994), 115–127.

[12] Sturmfels, B.: On the number of real roots of a sparse polynomial system. Hamiltonian and gradient flows, algorithms, and control. A. Block, ed., Amer. Math. Soc., Providence (1994), 137–143.

[13] Sturmfels, B.: Polynomial equations and convex polytopes. Draft for a chapter in: New Direction in Mathematics, Cambridge University Press, undated.

Received May 22, 1997