THE EXPECTED NUMBER OF REAL ROOTS OF A MULTIHOMOGENEOUS SYSTEM OF POLYNOMIAL EQUATIONS

Andrew McLennan

Abstract. The methods of Shub and Smale [SS93] are extended to the class of multihomogeneous systems of polynomial equations, yielding Theorem 1, which is a formula expressing the mean (with respect to a particular distribution on the space of coefficient vectors) number of real roots as a multiple of the mean absolute value of the determinant of a random matrix. Theorem 2 derives closed form expressions for the mean in special cases that include: (a) Shub and Smale’s result that the expected number of real roots of the general homogeneous system is the square root of the generic number of complex roots given by Bezout’s theorem; (b) Rojas’ [Roj96] characterization of the mean number of real roots of an “unmixed” multihomogeneous system. Theorem 3 gives upper and lower bounds for the mean number of roots, where the lower bound is the square root of the generic number of complex roots, as determined by Bernstein’s

[Ber75] theorem. These bounds are derived by induction from recursive inequalities given in Theorem 4.

Research at MSRI is supported in part by NSF grant DMS-9701755. I have benefited from numerous discussions with Maurice Rojas, and I am grateful for comments by seminar participants at the University of Minnesota, the AMS Meeting at Temple University in April 1998, and the conference on polynomial system solving at the Mathematical Sciences Research Institute in September 1998.

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

1. Introduction

The study of the distribution of real roots of a polynomial with random coefficients, which traces back at least to [BP32], has recently been developed in the direction of multivariate systems. (This literature is ably surveyed, and extended, by Edelman and Kostlan [EK95].) Kostlan [Kos93] shows that, for a homogeneous polynomial equation of degree d in n + 1 variables, a particular inner product on the space of coefficient vectors is distinguished by invariance under the natural action of O(n + 1) and orthogonality of monomials. He goes on to show that, for the system of n such equations, when the coefficient vectors for the various equations are independent random variables, with each one distributed according to the central normal distribution associated with this inner product, the mean number of projective roots in n-dimensional real projective space is d^{n/2}, which is the square root of the generic number of complex roots given by Bezout’s theorem. Shub and Smale [SS93] extend this result to the general homogeneous system of n homogeneous polynomial equations of degrees d_{1}, …, d_{n}, showing that the mean is \sqrt{∏_{i} d_{i}}, which is again the square root of the Bezout number. Rojas [Roj96] studies unmixed^{(1)} systems of multihomogeneous equations, arriving at a closed form formula for the mean number of roots in the cartesian product of projective spaces that is the natural root space for such systems.

This paper studies the more general case of mixed multihomogeneous systems. Theorem 1 is a formula expressing the mean number of real roots of a random multihomogeneous system as the product of the mean absolute value of the determinant of a random matrix times an expression composed of evaluations of Euler’s function Γ at multiples of 1/2. Theorem 2, which is a corollary, gives a closed form formula for this mean, for a smaller class of systems that includes both the general homogeneous system and the unmixed systems as special cases, so that the results of [SS93] and [Roj96] described above are corollaries. Theorem 3 generalizes the “square root of the Bezout number” result by giving upper and lower bounds on the mean

(1) Sparse systems of polynomial equations are described in Section 2. Roughly, such a system is unmixed if all polynomials have the same collection of monomials with nonzero coefficients, and otherwise it is mixed. number of roots, where the lower bound is the square root of the maximal number of roots for the associated “demultihomogenized” system, as given by Bernshtein’s [Ber75] extension of Bezout’s theorem to sparse systems of polynomial equations. These bounds follow from recursive inequalities given in Theorem 4.

The author’s interest in this topic is motivated in part by concepts of noncooperative game theory^{(2)}. The concept of a totally mixed Nash equilibrium for a normal form game amounts to a root, all of whose components must be positive, of particular sort of multihomogeneous system. McLennan and McKelvey [MM97] give a method for constructing normal form games that have as many regular (real) totally mixed Nash equilibria as are permitted by Bernshtein’s theorem. The conceptual import of this result is that the maximal number of Nash equilibria is large, at least compared to most game theorists’ prior intuition. Games that have the maximal number of equilibria are thought to be very atypical, and there arises the question of whether the set of equilibria is not only potentially large, but also large on average. McLennan [McL97] investigates the application, to this problem, of the results developed here, using Theorem 3 to show that the mean number of Nash equilibria can grow exponentially with various measures of the size of the game. Among other things, this analysis involves the extension of our work here to systems consisting of a multihomogeneous system of the sort studied here to which additional multihomogeneous polynomial inequalities have been appended, with the generalized formula being the one given here times a factor that may be regarded as the “probability” that a root of the system of equations also satisfies the inequalities.

In connection with speculation concerning whether analogues of Theorem 3 might hold for more general classes of sparse systems than the multihomogeneous ones, we recommend [Roj], which gives an extension to general sparse systems of the model of a random system studied here, and which presents results and conjectures along these lines. It is interesting to note that multihomogeneous systems are potentially special insofar as they can have as many real regular roots as are permitted by Bernshtein’s theorem. (This is proved in [McL98] by pointing out that the argument

(2) This is not the place to give a general introduction to noncooperative game theory; Fudenberg and Tirole (1991) is a standard text. For the internal logic of this paper the description of quasiequilibrium (Section 2) is sufficient. For the connection between this notion and the standard concepts of Nash equilibrium and totally mixed Nash equilibrium see [MM97, McL97]. in [MM97], which establishes this claim for the systems arising in game theory, is actually valid for any multihomogeneous system.)

The proof of Theorem 1 parallels the analysis in [SS93] and [BCS98] rather closely, and is thus a descendant of the methods of [Kac43]. The incidence variety is the set of coefficient vector-root pairs. It is a submanifold of the cartesian product of the space of coefficient vectors and the root space, and the projection of it onto the root space is a fibration. The roots of the system at a particular coefficient vector are the preimages of the projection of the incidence variety onto the space of coefficient vectors, and an integral formula [SS93, p. 273; BCS98, p. 240] is used to reexpress the mean number of roots as a double integral, where the outer integral is over the root space and the inner integral is over the fibre of the projection onto the roots space at the root in question. Invariance is used to show that the inner integral does not depend on this root, so that the double integral is the volume of the root space times the inner integral, evaluated at a point in the root space which may be chosen at whim. For a particular choice it is possible to simplify the inner integral by transforming variables in a way that eliminates variables that do not enter the integrand, and from this Theorem 1 emerges.

The algorithms used by [MM97] to compute maximal numbers of Nash equilibria are based on recursive formulas for the Bernshtein number that extend directly to general multihomogeneous systems. Below (see also [McL98]) we describe how these formulas can be seen as the consequence of expressing the Bernshtein number for such a system as the permanent (e.g. [Ego96]) of a matrix, after which the recursions are obtained by expanding along a row or column. In investigating whether the mean number of real roots is greater than the square root of the Bernshtein number, as asserted by Theorem 3, it is natural to guess that the squares of the mean numbers of real roots obey the corresponding recursive inequalities, which is the assertion of Theorem 4, since then Theorem 3 follows from induction. Using Theorem 1, Proposition 7.1 restates these inequalities as recursive inequalities for the mean absoute values of the determinants of certain random matrices. The proof of Proposition 7.1 is, perhaps, rather surprising insofar as it depends on properties of normal random variables that seem quite distant from the geometric starting point of these investigations.

The remainder has the following organization. Section 2 describes multihomogeneous systems as a certain type of sparse system. Section 3 specifies an inner product on the space of coefficient vectors of a multihomogeneous equation that is uniquely characterized by invariance and orthogonality of monomials. The central normal distribution with respect to this inner product is our model of a random equation, and our random systems have the coefficient vectors of the various equations distributed independently according to these distributions. Section 4 states Theorem 1, and in Section 5 we discuss those systems for which it is possible to reduce the formula in Theorem 1 either to closed form or to an expression involving the formula applied to smaller systems. Section 6 defines mixed volume, states Bernshtein’s theorem precisely, and shows how the generic number of complex roots of a multihomogeneous system may be computed recursively. Section 7 proves Theorems 3 and 4, and presents a result giving upper and lower bounds for the mean absolute value of the determinant of a random matrix. Sections 8–11 present the proof of Theorem 1.

2. Multihomogeneous Systems

In stating Bernshtein’s theorem we will need to consider general sparse systems, so we describe multihomogeneous systems as a specialization of this concept. A sparse system of n polynomial equations in ℓ variables is

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

where x = (x_{1}, …, x_{ℓ}) and, for each i = 1, …, n, there is a nonempty finite A_{i} ⊂ N^{ℓ} such that f_{i}(x) = ∑_{a∈A_{i}} f_{ia}x^{a} for some system of coefficients f_{ia}. (Here x^{a} denotes the monomial x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{ℓ}^{a_{ℓ}}.) The general approach of the theory of sparse systems is to hold the n-tuple of supports (A_{1}, …, A_{n}) fixed while treating the coefficients f_{ia} as variables, for instance in the sense of studying properties that are generic in the space of vectors of coefficients. Such a system is said to be unmixed if A_{1} = … = A_{n}; otherwise it is mixed. Identifying a polynomial with its vector of coefficients, we regard H_{i} := IR^{A_{i}} \ {0} as the space of polynomials with real coefficients whose supports are nonempty subsets of A_{i}. Let

H := H_{1} × … × H_{n}.

The system is multihomogeneous if the variables in x are divided into k groups, so that x = (y_{1}, …, y_{k}) where y_{j} = (y_{j0}, y_{j1}, …, y_{jn_{j}}), and each equation is homogeneous of degree δ_{ij} as a function of y_{j}, for any given values of the other variables (y_{1}, …, y_{j−1}, y_{j+1}, …, y_{k}). More precisely, we require that there are nonnegative integers δ_{ij} (i = 1, …, n, j = 1, …, k) such that

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

When f_{i} is multihomogeneous, the truth value of the proposition ‘f_{i}(x) = 0’ is unaffected if each block of variables is multiplied by a nonzero scalar, so that, in effect, there are ℓ − k degrees of freedom. We work only with systems that are, in this sense, exactly determined: ℓ = n + k, so that n_{1} + … + n_{k} = n. An instance of the type of system studied here is specified by the vector n and the n × k matrix δ := (δ_{ij}).

Four particular types of multihomogeneous system figure in our discussion:

(a) When k = 1 we have the general homogeneous system, for which the problem studied here was analyzed in [SS93]. In inductive constructions it will be convenient to allow the numbers of variables in some blocks to be zero, and we will use the phrase ‘general homogeneous system’ to describe any multihomogeneous system with n_{j} = n for some j, in which case we must have n_{h} = 0 for all h ≠ j.

(b) The unmixed multihomogeneous systems studied in [Roj96] are described by the condition that all equations have the same support: there are integers e_{1}, …, e_{k} such that

δ_{1j} = … = δ_{nj} = e_{j} (j = 1, …, k).

(c) Generalizing (a) and (b) are the systems for which there are numbers d_{1}, …, d_{n} and e_{1}, …, e_{k} such that δ_{ij} = d_{i}e_{j} for all i and j.

(d) The systems arising, in game theory, from the concept of quasiequilibrium ([MM97]) of a finite normal form game, have, for each j = 1, …, k, n_{j} equations that are homogeneous of degree one in y_{h} for all h ≠ j, and are homogeneous of degree zero in y_{j}. Formally these systems can be characterized as follows:

δ_{ij} = \{ \begin{matrix}0 & if q(i) = j, \\ 1 & otherwise, \end{matrix}  (1)

where q : {1, …, n} → {1, …, k} is the function defined implicitly by the inequality

n_{1} + … + n_{q(i)−1} < i ≤ n_{1} + … + n_{q(i)}.

3. An Invariant Inner Product

Fix a pair (n, δ). Since n_{1}+…+n_{k} = n, we may index the components of an exponent vector a ∈ N^{n+k} by the pairs (j, h) for j = 1, …, k and h = 0, …, n_{j}. For such an a let

\begin{aligned}η & (a) := \frac{a_{10}! · . . . · a_{1n_{1}}!}{(a_{10} + … + a_{1n_{1}})!} · . . . · \frac{a_{k0}! · . . . · a_{kn_{k}}!}{(a_{k0} + … + a_{kn_{k}})!} \\ & = \binom{a_{10} + … + a_{1n_{1}}}{a_{10}, …, a_{1n_{1}}}^{−1} · . . . · \binom{a_{k0} + … + a_{kn_{k}}}{a_{k0}, …, a_{kn_{k}}}^{−1} . \end{aligned}

We endow each H_{i} with the inner product

⟨f_{i}, f′_{i}⟩_{i} := ∑_{a∈A_{i}} η(a)f_{ia}f′_{ia}.

Let ∥ · ∥_{i} be the norm derived from ⟨·, ·⟩_{i}.

Consider the product group

G := O(n_{1} + 1) × … × O(n_{k} + 1).

There is the obvious component-wise action of G on IR^{n_{1}+1} × … × IR^{n_{k}+1}, and for f_{i} ∈ H_{i} and O ∈ G, f_{i} ∘ O^{−1} is easily seen to be a polynomial function that is multihomogeneous for the same numbers δ_{ij}, so f_{i} ∘ O^{−1} is an element of H_{i}. Thus the formula Of_{i} := f_{i} ∘ O^{−1} defines an action from the left of G on H_{i}. The following generalizes [Kos93, Th. 4.2], which is the case k = 1.

Lemma 3.1: The inner product (4) is the unique (up to multiplication by a scalar) inner product on H_{i} that is invariant under the action of G and with respect to which the monomials are pairwise orthogonal.

Proof: Let ⟨f_{i}, f′_{i}⟩_{i}^{∗} = ∑_{a∈A_{i}} η^{∗}(a)f_{ia}f′_{ia} be an invariant inner product with all monomials orthogonal. We wish to show that η^{∗}(a)/η^{∗}(a′) = η(a)/η(a′) for all a, a′ ∈ A_{i}. Fixing arbitrary a ∈ A_{i} and j = 1, …, k, it suffices to establish that this formula holds for those a′ ∈ A_{i} with a_{ℓh} = a′_{ℓh} whenever ℓ ≠ j, and this follows from [Kos93, Th. 4.2] applied to the subspace of H_{i} spanned by such a′.

To see that ⟨·, ·⟩_{i} is invariant under the action of G observe that, by [Kos93, Th. 4.2], it is invariant under the action of any group element g with only one component g_{j} different from the identity in O(n_{j} + 1), and that such group elements generate G.

Following [Kos93, EK95, Roj96], in our model of a random multihomogeneous system the coefficient vectors of the various equations are statistically independent, with the coefficient vector of the i^{th} equation centrally normally distributed in H_{i} relative to ⟨·, ·⟩_{i}. Concretely this means that the coefficients f̃_{ia} are independent Gaussian random variables with mean 0 and variance η(a)^{−1}. In the setting of arbitrary sparse systems [Roj96] presents a definition and motivation of these variances that is geometric and general, in the sense that it pertains to any sparse system. Let μ_{i} be the probability measure on H_{i} that is the distribution of f̃_{i}, and let

μ := μ_{1} × … × μ_{n}

be the distribution of f̃:= (f̃_{1}, …, f̃_{n}).

In the calculations used to prove Theorem 1 we also consider the model in which the coefficient vectors f_{1}, …, f_{n} are statistically independent, with each f_{i} uniformly distributed in the unit sphere (relative to ∥ · ∥_{i}) of H_{i}. The distribution of roots depends only on the distribution of the normalized coefficient vectors f_{i}/∥f_{i}∥_{i}, so standard facts concerning the multivariate normal distribution imply that, from our point of view, the two models are equivalent.

4. The Central Formula

We count roots in the k-fold product of projective spaces

P := P_{1} × … × P_{k}

where, for j = 1, …, k, P_{j} := P^{n_{j}}(IR) is n_{j}-dimensional real projective space. In the usual way, the equation f_{i}(ζ) = 0 is meaningful for f_{i} ∈ H_{i} and ζ ∈ P even though f_{i} is not a function defined on P. Our central concern is the expected number of roots

E(n, δ) := E(#({ ζ ∈ P : f̃(ζ) = 0 })),

but in fact we completely characterize the distribution of roots.

Let Z̃ be a random n × n matrix with rows indexed by the integers i = 1, …, n, columns indexed by the pairs jh for j = 1, …, k and h = 1, …, n_{j}, and entries z̃_{i}^{jh} that are independently distributed normal random variables with mean zero and variance δ_{ij}. Let Γ(s) := ∫_{0}^{∞} exp(−t)t^{s−1} dt be Euler’s function.

Theorem 1:

(a)

E(n, δ) = 2^{−n/2} · (∏_{j=1}^{k} \frac{Γ(\frac{1}{2})}{Γ(\frac{n_{j}+1}{2})}) · E(| det Z̃|).  (2)

(b) The induced distribution of roots is uniform: for any open W ⊂ P,

E(#(\{ ζ ∈ W : f̃(ζ) = 0 \})) = \frac{vol(W)}{vol(P)}E(n, δ).

This will be proved in Sections 8–11. The next three sections describe the consequences of this result.

5. Reduction to Closed Form

In certain circumstances the RHS of (2) can be reexpressed in closed form or in terms of the expressions derived from application of this formula to systems that are, in certain senses, smaller. Insofar as Γ(\frac{1}{2}) = \sqrt{π}, Γ(1) = 1, and Γ(s + 1) = sΓ(s) for all s > 0, the evaluations of Γ in (2) will be regarded as being in closed form already, so the problem is to reduce the term E(| det Z̃|).

We begin by considering systems in which there is a subset of the variables that are determined by equations involving only those variables. Specifically, suppose there is some integer k′ between 1 and k such that δ_{ij} = 0 for all i, j such that q(i) ≤ k′ and k′ < j, where q(·) is the function defined at the end of Section 2. Set n′ := n_{1} + … + n_{k′}. Then

δ = [ \begin{matrix}δ^{11} & 0 \\ δ^{21} & δ^{22} \end{matrix} ] .

where δ^{11}, δ^{21}, and δ^{22} have dimensions n′ ×k′, (n−n′)×k′, and (n−n′)× (k − k′) respectively. Then (with probability one) Z̃ has an n′ × (n − n′) block of zeros in its upper right corner, so its determinant is the product of the determinants of the n′ × n′ submatrix in the upper left and the (n − n′) × (n − n′) submatrix in the lower right. In particular, E(| det Z̃|) does not depend on δ^{21}. Consequently (2) implies that E(n, δ) is also independent of δ^{21}. When we set δ^{21} = 0 we have a cartesian product of two independent systems, and our assumed distribution of coefficients for the combined system is the product measure of the assumed distributions for the subsystems. For any particular coefficient vector for the combined system, the number of roots is the product of the numbers of roots of the subsystems, so the following is a consequence of the fact that the mean of a product of independent random variables is the product of their means. Computationally, it follows immediately from the fact that the determinant of Z̃ is the product of the determinants of the submatrices.

Corollary 1: Suppose there is some 1 ≤ k′ < k such that δ_{ij} = 0 whenever q(i) ≤ k′ < j, and let δ^{11} and δ^{22} be as above. Then

E(n, δ) = E((n_{1}, …, n_{k′}), δ^{11}) · E((n_{k′+1}, …, n_{k}), δ^{22}).

A second general principle results from the effect on the determinant of multiplying a row or a column by a scalar.

Corollary 2: If there are nonnegative integers d_{1}, …, d_{n} and e_{1}, …, e_{k} such that δ′_{ij} = d_{i} · e_{j} · δ_{ij}, then

E(n, δ′) = \sqrt{∏_{i=1}^{n} d_{i}} · \sqrt{∏_{j=1}^{k} e_{j}^{n_{j}}} · E(n, δ).

Consider now the particular case of k = 1 and δ_{11} = … = δ_{n1} = 1. This corresponds to a system of n linear functionals in n+1 variables, and there is exactly one projective root for almost all coefficient vectors. In view of (2) we must have:

Proposition 5.1: The mean absolute value of the determinant of a random n × n matrix whose entries are independently distributed normal random variables with mean zero and unit variance is

2^{n/2} · \frac{Γ(\frac{n+1}{2})}{Γ(\frac{1}{2})}.

Combining the last two results with Theorem 1 yields Theorem 2: If there are nonnegative integers d_{1}, …, d_{n} and e_{1}, …, e_{k} such that δ_{ij} = d_{i} · e_{j}, then

E(n, δ) = \frac{Γ(\frac{n+1}{2})}{Γ(\frac{1}{2})} · (∏_{j=1}^{k} \frac{Γ(\frac{1}{2})}{Γ(\frac{n_{j}+1}{2})}) · \sqrt{∏_{i=1}^{n} d_{i}} · \sqrt{∏_{j=1}^{k} e_{j}^{n_{j}}}.

The Shub-Smale formula is the special case k = 1, and Rojas’ formula for unmixed systems is obtained when d_{1} = … = d_{n} = 1.

There is a class of systems for which E(n, δ) can be computed exactly by combining Corollaries 1 and 2 with Proposition 5.1. I know of no case outside this class in which the expectation E(| det Z̃|) evaluates to a closed form expression. For the systems arising from normal form games we are able to evaluate in closed form only when k = 2, which corresponds to a game with two players. Applying ideas similar to those underlying Corollary 1 yields:

Corollary 3: In the case of the game equilibrium system given by (1), if k = 2 then

E(n, δ) = \{ \begin{matrix}1 & if n_{1} = n_{2}, \\ 0 & otherwise. \end{matrix}

6. The BKK Bound for Multihomogeneous Systems

This section explains the consequences of Bernshtein’s [Ber75] theorem for multihomogeneous systems. Let f(z) = (f_{1}(z), …, f_{n}(z)) be a general sparse system of n equations in the n variables z_{1}, …, z_{n}, where f_{i} has support A_{i} ⊂ N^{n}. The Newton polytope of f_{i} is the convex polytope Q_{i} = con(A_{i}). The mixed volume of Q_{1}, …, Q_{n}, which was first defined and studied by Minkowski, and which we denote by MV(Q_{1}, …, Q_{n}), may be defined to be the coefficient of the monomial λ_{1} · . . . · λ_{n} in the polynomial^{(3)} vol(Q_{λ}) where

Q_{λ} = λ_{1}Q_{1} + … + λ_{n}Q_{n}.

Theorem: ([Ber75]) Let C^{∗} := C \ {0}. Let H^{C} = H_{1}^{C} × … × H_{n}^{C} where H_{i}^{C} = C^{A_{i}} is the space of complex polynomials with support A_{i}.

(3) See [Ewa96] for a proof that vol(Q_{λ}) is, in fact, a polynomial function of λ.

For systems f in the complement, in H^{C}, of an algebraic set of positive (complex) codimension, there are MV(Q_{1}, …, Q_{n}) roots in (C^{∗})^{n}.

The maximal number MV(Q_{1}, …, Q_{n}) of roots is often referred to as the “BKK bound” of the system in recognition of closely related work [Kus76, Kov78].

We apply this result to the “demultihomogenized” system obtained, from the given multihomogeneous system, by setting y_{10} = … = y_{k0} = 1. In comparing the roots of the latter system, in (C^{∗})^{n}, with the roots, in P, of the given multihomogeneous system, there is the possibility of roots in one of the coordinate subspaces (in the projective sense) along which one of the variables vanishes, but invariance under the action of G quickly implies that generic systems do not have such roots, or roots at projective infinity. Thus, generically, there is a one-to-one correspondence between the roots of the given multihomogeneous system and of the demultihomogenized system. The Newton polytope of the i^{th} demultihomogenized equation is Q_{i} = ∏_{j:n_{j}>0} δ_{ij}Δ(n_{j}), where

Δ(n_{j}) := { (z_{j1}, …, z_{jn_{j}}) ∈ IR_{≥0}^{n_{j}} : z_{j1} + … + z_{jn_{j}} ≤ 1 },

and the generic number of complex roots of the system is

BKK(n, δ) := MV( ∏_{j:n_{j}>0} δ_{1j}Δ(n_{j}), …, ∏_{j:n_{j}>0} δ_{nj}Δ(n_{j})).

Our analysis of this quantity employs the following concept. The permanent (e.g., [Ego96]) of an m × n matrix D with entries d_{ij} is

per D := ∑_{σ∈S_{m,n}} (∏_{i=1}^{n} d_{iσ(i)})

where S_{m,n} is the set of one to one functions from {1, …, m} to {1, …, n}. Since there are no such functions when m > n, in which case per D is automatically zero. Note that multiplying any row of D by a scalar has the effect of multiplying the permanent by that scalar, and that we may expand by minors along any row: for each i = 1, …, m

per D = ∑_{j=1}^{n} d_{ij} · per D^{ij}

where D^{ij} is the (m − 1) × (n − 1) matrix obtained from D by eliminating the i^{th} row and the j^{th} column. When m = n the permanent of D agrees with the permanent of its transpose, and these comments hold with rows and columns reversed.

Let Δ(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 computation

vol(∑_{i=1}^{n} λ_{i}( ∏_{j:n_{j}>0} δ_{ij}Δ(n_{j}))) = vol( ∏_{j:n_{j}>0} ( ∑_{i=1}^{n} λ_{i}δ_{ij})Δ(n_{j}))

= \frac{∏_{j:n_{j}>0} ( ∑_{i=1}^{n} λ_{i}δ_{ij})^{n_{j}}}{n_{1}! · . . . · n_{k}!}

has the following immediate implication:

Proposition 6.1: ([McL98])

BKK(n, δ) = \frac{per Δ(n, δ)}{n_{1}! · . . . · n_{k}!}.

The next result enumerates consequences of the elementary properties of the permanent, applied to this result. For i = 1, …, n let δ^{−i} be the (n−1)×k matrix obtained by eliminating the i^{th} row of δ. For j = 1, …, k let e_{j} be the j^{th} standard unit basis vector of IR^{k}. In the recursive formulas below we are adopting the convention that

BKK((0, …, 0), δ_{0}) = E((0, …, 0), δ_{0}) = 1,

where δ_{0} is the 0 × k matrix. This means that the “null system” with no variables and no equations has one root.

Proposition 6.2: ([McL98])

(a) For all i = 1, …, n,

BKK(n, δ) = ∑_{j:n_{j}>0} δ_{ij} · BKK(n − e_{j}, δ^{−i}).

(b) For all j = 1, …, k such that n_{j} > 0,

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

(c) Suppose there is some 1 ≤ k′ < k such that δ_{ij} = 0 whenever q(i) ≤ k′ < j, and let δ^{11}, δ^{21}, and δ^{22} be as in Section 4. Then

BKK(n, δ) = BKK((n_{1}, …, n_{k′}), δ^{11}) · BKK((n_{k′+1}, …, n_{k}), δ^{22}).

(d) If there are nonnegative integers d_{1}, …, d_{n} and e_{1}, …, e_{k} such that δ′_{ij} = d_{i} · e_{j} · δ_{ij}, then

BKK(n, δ′) = ( ∏_{i=1}^{n} d_{i}) · ( ∏_{j:n_{j}>0} e_{j}^{n_{j}}) · BKK(n, δ).

The recursive formulas (a) and (b) give obvious algorithms for computing BKK(n, δ) that have computed values of BKK on the order of 10^{21}. (Cf. [MM97].)

In preparation for Theorem 3, we ask when BKK(n, δ) can be computed by repeated applications of (a) in which the RHS has only one nonzero term. We say that the pair (n, δ) is simply reducible if the following inductive definition is satisfied: there is some i for which there is at most one j with n_{j} > 0, δ_{ij} > 0, and BKK(n − e_{j}, δ^{−i}) > 0, and if n > 1 we require that for this j, (n − e_{j}, δ^{−i}) is also simply reducible. This will clearly be the case when repeated applications of (c) reduces BKK(n, δ) to a product of instances of the general homogeneous system. In fact this is the only way that (n, δ) can be simply reducible, as we shall see in the next section.

We will need the following technical result. Let A be an m × n matrix of 0’s and 1’s. We say that an m × n matrix D = (d_{i}j) is A-sparse if d_{ij} = 0 whenever a_{ij} = 0.

Lemma 6.3: The following conditions are equivalent:

(i) there is an integer 1 ≤ k < m such that, after relabelling of rows and columns, A has a k × (n + 1 − k) block of 0’s.

(ii) per A = 0;

(iii) all A-sparse matrices have row rank less than m.

Proof: Clearly (i) implies (ii). The meaning of (ii) is that for each oneto-one σ : {1, …, m} → {1, …, n} there is some i such that a_{iσ(i)} = 0, which implies that all A-sparse matrices have no m × m submatrices of full rank, so (ii) implies (iii). Assuming that (iii) holds, we may assume without loss of the generality that the first k rows of A are minimally linearly independent: for a generic A-sparse matrix D their span agrees with the span of any (k − 1)-element subset. Reordering columns, we may assume that, for generic D, the projection of the span of the first k rows onto the space of the first k − 1 columns has full rank. Now the upper right hand k × (n − (k − 1)) block of A must vanish, since otherwise it is straightforward to construct an A-sparse matrix D whose first k rows are linearly independent.

7. The Mean Exceeds the Square Root of the Maximum

Let Δ_{\frac{1}{2}}(n, δ) be the n × n matrix whose (i, jh)-entry is \sqrt{δ_{ij}}. This section establishes the following generalization of the Shub–Smale formula.

Theorem 3:

\frac{per Δ_{\frac{1}{2}}(n, δ)}{n_{1}! · . . . · n_{k}!} ≥ E(n, δ) ≥ \sqrt{BKK(n, δ)} = \sqrt{\frac{per Δ(n, δ)}{n_{1}! · . . . · n_{k}!}}.

These inequalities hold with equality when (n, δ) is simply reducible and not otherwise.

Theorem 3 will follow by induction from the following stronger result.

Theorem 4: For all i = 1, …, n,

∑_{j:n_{j}>0} \sqrt{δ_{ij}} · E(n − e_{j}, δ^{−i}) ≥ E(n, δ) ≥ \sqrt{∑_{j:n_{j}>0} δ_{ij} · E(n − e_{j}, δ^{−i})^{2}},

These inequalities hold with equality if and only if there is at most one j with δ_{ij} > 0 and E(n − e_{j}, δ^{−i}) > 0.

Proof of Theorem 3: The asserted inequalities follow from an induction on n that begins with the convention that E(n, δ) = BKK(n, δ) = 1 when n_{1} = … = n_{k} = 0. The induction step is a matter of comparing (a) of Proposition 6.2 and the analogous formula for per Δ_{\frac{1}{2}} (n, δ) with the inequalities in Theorem 4. Moreover, Theorem 4 implies that either of the inequalities in Theorem 3 holds with equality if and only if there is at most one j with E(n − e_{j}, δ^{−i}) > 0, and E(n − e_{j}, δ^{−i}) also satisfies the inequality with equality. In particular, it follows from induction that E(n, δ) > 0 if and only if BKK(n, δ) > 0, so either of the inequalities in Theorem 3 holds with equality if and only if (n, δ) is simply reducible.

Remark: We can now give a direct characterization of simple reducibility. Applying Theorem 3 to the situation laid out in Corollary 1 and (c) of Proposition 6.2 shows that (n, δ) is simply reducible if and only if both ((n_{1}, …, n_{k′}), δ^{11}) and ((n_{k′+1}, …, n_{k}), δ^{22}) are simply reducible. Thus it suffices to characterize simple reducibility when the hypotheses of (c) of Proposition 6.2 are not satisfied: there is no 1 ≤ k′ < k such that (after any reordering of rows and columns) δ_{ij} = 0 whenever q(i) ≤ k′ < j. The inequality of Theorem 3 cannot hold with equality unless all instances of the inequality in Theorem 4 hold with equality, so we see that if (n, δ) is simply reducible, then for any i = 1, …, n there is at most one j with n_{j} > 0, δ_{ij} > 0, and BKK(n − e_{j}, δ^{−i}) > 0, with (n − e_{j}, δ^{−i}) simply reducible if n > 1. If there is some i for which there exist distinct j, j′ with n_{j} > 0, n_{j′} > 0, δ_{ij} > 0, and δ_{ij′} > 0, then either BKK(n − e_{j}, δ^{−i}) = 0 or BKK(n − e_{j′}, δ^{−i}) = 0, in which case Proposition 6.1 and Lemma 6.3 imply that Δ(n−e_{j}, δ^{−i}) or Δ(n−e_{j′}, δ^{−i}) has a block of zeros, as per (iii) of Lemma 6.3, and this implies that the hypotheses of (c) of Proposition 6.2 are satisfied by (n, δ), contrary to assumption. For each i there is consequently at most one j with n_{j} > 0 and δ_{ij} > 0. If there is more than one j with n_{j} > 0 it is again easy to show that the hypotheses of (c) of Proposition 6.2 are satisfied by (n, δ), so n_{j} = n for some j. That is, we have the general homogeneous case.

It remains to prove Theorem 4. For the random matrix Z̃ of Theorem 1, let Z̃_{jh}^{i} be the determinant of the (n − 1) × (n − 1) minor obtained by eliminating row i and column jh. Observe that, by Theorem 1,

E(|Z̃_{jh}^{i}|) = 2^{\frac{n−1}{2}} \frac{Γ(\frac{n_{j}}{2} )}{Γ(\frac{n_{j}+1}{2})}(∏_{p=1}^{k} \frac{Γ(\frac{n_{p}+1}{2})}{Γ(\frac{1}{2})})E(n − e_{j}, δ^{−i}),

so, applying Theorem 1 again to express E(n, δ) in terms of E(| det Z̃|), we quickly find that the assertion of Theorem 4 is equivalent to:

Proposition 7.1: For all i = 1, …, n,

∑_{j:n_{j}>0} \sqrt{δ_{ij}} \frac{Γ(\frac{n_{j}+1}{2})}{Γ(\frac{n_{j}}{2} )}E(|Z̃_{j1}^{i}|) ≥ \frac{E(| det Z̃|)}{\sqrt{2}} ≥ \sqrt{∑_{j:n_{j}>0} δ_{ij}(\frac{Γ(\frac{n_{j}+1}{2})}{Γ(\frac{n_{j}}{2} )})^{2}E(|Z̃_{j1}^{i}|)^{2}}.

These inequalities hold with equality if and only if δ_{ij}E(|Z̃_{j1}^{i}|) > 0 for at most one j.

The proof of this will be our goal for the remainder of the section. The next result describes the source of the inaccuracy of the approximation.

Lemma 7.2: If x̃ is a IR_{≥0}^{m}–valued random variable for which E(x̃) is defined, then

∑_{h=1}^{m} E(|x̃_{h}|) ≥ E(∥x̃∥) ≥ ∥E(x̃)∥.

The first inequality holds with equality if and only if the support of the distribution of x̃ is contained in the union of the coordinate axes. The second inequality holds with equality if and only if the support of the distribution of x̃ is contained in a single ray emanating from the origin.

Proof: Since ∑_{h} E(|x̃_{h}|) = E( ∑_{h} |x̃_{h}|), the first inequality follows from ∑_{h=1}^{m} |x̃_{h}| ≥ ∥x̃∥, and it holds with equality if and only if, with probability one, ∑_{h=1}^{m} |x̃_{h}| = ∥x̃∥. The second inequality follows from Jensen’s inequality, and it holds with equality if and only if ∥(1 − α)x_{0} + αx_{1}∥ = (1 − α)∥x_{0}∥ + α∥x_{1}∥ for any x_{0}, x_{1} in the support of the distribution of x̃ and any 0 ≤ α ≤ 1.

We will need the following technical fact.

Lemma 7.3: Let ϵ̃ = (ϵ̃_{1}, …, ϵ̃_{m}) where ϵ̃_{1}, …, ϵ̃_{m} are independent identically distributed normal random variables with mean zero and unit variance. Then

E(∥ϵ̃∥) = \frac{\sqrt{2} · Γ(\frac{m+1}{2})}{Γ(\frac{m}{2})}.  (3)

Proof: We compute that

E(∥ϵ̃∥) = ∫_{−∞}^{∞} … ∫_{−∞}^{∞} ∥x∥ · (\frac{1}{\sqrt{2π}} e^{−x_{1}^{2}/2} dx_{1}) · . . . · (\frac{1}{\sqrt{2π}} e^{−x_{m}^{2}/2} dx_{m})
= (2π)^{−m/2} ∫_{IR^{m}} ∥x∥ · e^{−∥x∥^{2}/2} dx
= (2π)^{−m/2} ∫_{0}^{∞}(re^{−r^{2}/2}) · vol(S^{m−1}) · r^{m−1} dr.

The asserted formula is now obtained from the formula (e.g., [Fed69, p. 251])

vol(S^{m−1}) = 2\frac{Γ(\frac{1}{2})^{m}}{Γ(\frac{m}{2})} (m ≥ 1)  (4)

the change of variables t := r^{2}/2, the fact that Γ(\frac{1}{2}) = \sqrt{π}, and the definition of Γ(·).

The next result expresses the central idea of the method, which exploits a special property of random normal variables, in its simplest form. Random matrices have been studied extensively [Gir90, Meh91, Mui82] but there seems to be little prior work on mean absolute values of random determinants.

Proposition 7.4: Let Ẽ be an n × n matrix whose entries ϵ̃_{ab} are independently distributed normal random variables with mean zero and variance σ_{ab}^{2}. For 1 ≤ a, b ≤ n let Ẽ^{ab} be the determinant of the (n − 1) × (n − 1) minor of Ẽ obtained by eliminating row a and column b. Then for any a = 1, …, n:

\sqrt{2/π} · ∑_{b=1}^{n} σ_{ab} · E(|Ẽ^{ab}|) ≥ E(| det Ẽ|) ≥ \sqrt{2/π} · (∑_{b=1}^{n} σ_{ab}^{2} · E(|Ẽ^{ab}|)^{2})^{1/2} .

Proof: The expansion of the determinant by minors along row a is

det Ẽ = ∑_{b=1}^{n}(−1)^{a+b}ϵ̃_{ab}Ẽ^{ab}.

For any numbers E^{a1}, …, E^{an}, elementary properties of Gaussian random variables imply that ∑_{b=1}^{n}(−1)^{a+b}ϵ̃_{ab}E^{ab} is a normally distributed random variable with mean 0 and variance ∑_{b=1}^{n} σ_{ab}^{2}(Ẽ^{ab})^{2}. Since (ϵ̃_{a1}, …, ϵ̃_{an}) and (Ẽ^{a1}, …, Ẽ^{an}) are statistically independent, Fubini’s theorem and (3) in the case m = 1 yield

E(| det Ẽ|) = \frac{\sqrt{2}}{Γ(\frac{1}{2})}E(\sqrt{∑_{b=1}^{n} σ_{ab}^{2}(Ẽ^{ab})^{2}} ).

Recalling that Γ(\frac{1}{2}) = \sqrt{π}, the claim follows from Lemma 7.2.

Let Σ_{1} be the n × n matrix with entries σ_{ab}, and let Σ_{2} be the n × n matrix with entries σ_{ab}^{2}. By an induction on n we now have:

Corollary:

(2/π)^{n/2} · per Σ_{1} ≥ E(| det Ẽ|) ≥ (2/π)^{n/2} · \sqrt{per Σ_{2}}.

The upper and lower bounds in Lemma 7.2 correspond to the extreme cases in which the distribution of x̃ is concentrated on the coordinate axes or on the ray through E(x̃). When the distribution of x̃ is known to be invariant under the action of a group, it can be possible to show that it is far from these extremes. In the specific case we have in mind the group

H = SO(IR^{n_{1}}) × … × SO(IR^{n_{k}})

acts on the space of n × n matrices Z by simultaneously acting on each row of Z, where each row is viewed as an element of IR^{n_{1}} × … × IR^{n_{k}}. Then, because the determinant of a linear transformation between inner product spaces is invariant under composition with orientation preserving orthogonal transformations of the domain or range, we have det(ηZ) = det Z for all η ∈ H and all n × n matrices Z.

Let Z_{jh}^{i} denote the determinant of the (n−1)×(n−1) minor obtained from Z by eliminating row i and column jh. Define the function c_{i} from the space of n × n matrices to IR^{n} by letting c_{i}(Z) be the vector with components c_{i}^{jh}(Z) = (−1)^{i+n_{1}+...+n_{j−1}+h}Z_{jh}^{i}. (Of course c_{i}(Z) is independent of the i^{th} row of Z, and is called the cross product (cf. [Spi65], pp. 84-5) of the remaining n − 1 rows.)

Lemma 7.5: c_{i} is equivariant: c_{i}(ηZ) = ηc_{i}(Z) for all n × n matrices Z and all η ∈ H.

Proof: Let Z_{i} denote the i^{th} row of Z. Then for any η ∈ H we have

Z_{i} · c_{i}(Z) = det Z = det(ηZ) = ηZ_{i} · c_{i}(ηZ).

Since c_{i}(Z) and c_{i}(ηZ) are independent of Z_{i}, and this holds for all Z_{i}, it must be the case that c_{i}(ηZ) = ηc_{i}(Z) for all n × n matrices Z and all η ∈ H.

Proof of 7.1: As in the last proof, we write det(Z̃) = Z̃_{i} · c_{i}(Z̃). As in the proof of Proposition 7.4, elementary properties of normal random variables and Fubini’s theorem imply that

E(| det Z̃|) = \frac{\sqrt{2} · Γ(1)}{Γ(\frac{1}{2})}E(\sqrt{∑_{j=1}^{k} ∑_{h=1}^{n_{j}} δ_{ij} · (Z̃_{jh}^{i})^{2}} )

= \frac{\sqrt{2} · Γ(1)}{Γ(\frac{1}{2})}E(\sqrt{∑_{j=1}^{k} δ_{ij} · ∥ξ̃_{ij}∥^{2}} ).

Combining this with Lemma 7.2 yields

\frac{\sqrt{2} · Γ(1)}{Γ(\frac{1}{2})} ∑_{j=1}^{k} \sqrt{δ_{ij}}E(∥ξ̃_{ij}∥) ≥ E(| det Z̃|) ≥ \frac{\sqrt{2} · Γ(1)}{Γ(\frac{1}{2})}\sqrt{∑_{j=1}^{k} δ_{ij}E(∥ξ̃_{ij}∥)^{2}}. (5)

For j = 1, …, k let Π_{j} : IR^{n} → IR^{n_{j}} be the projection
Π_{j}(z^{11}, …, z^{1n_{1}}, …, z^{k1}, …, z^{kn_{k}}) = (z^{j1}, …, z^{jn_{j}}).

Clearly Π_{j} is equivariant: Π_{j}(ηz) = η_{j}(Π_{j}(z)) for all z ∈ IR^{n} and η = (η_{1}, …, η_{k}) ∈ H. Therefore Π_{j} ∘ c_{i} is equivariant. By virtue of elementary properties of the multivariate normal, the distribution of the random matrix Z̃ on the space of n × n matrices is invariant under the action of H, so the distribution of ξ̃_{ij} = Π_{j}(c_{i}(Z̃)) is invariant under the action of SO(IR^{n_{j}}).

If x̃ is any IR^{n_{j}}–valued random variable whose distribution is invariant under the action of O(IR^{n_{j}}), the ratio E(|x̃_{h}|)/E(∥x̃∥) must agree with the mean absolute value of the first component of a random vector that is uniformly distributed on the unit sphere in IR^{n_{j}}. In particular, by Lemma 7.3 we have

\frac{E(∥ξ̃_{ij}∥)}{E(∥Z̃_{i}^{j1}∥)} = \frac{E(∥ϵ̃∥)}{E(|ϵ̃_{1}|)} = \frac{Γ(\frac{n_{j}+1}{2})/Γ(\frac{n_{j}}{2} )}{Γ(1)/Γ(\frac{1}{2})}

when ϵ̃ = (ϵ̃_{1}, …, ϵ̃_{n_{j}}) and ϵ̃_{1}, …, ϵ̃_{n_{j}} are i.i.d. normal random variables with mean zero. The asserted inequality follows from substituing this into (5).

With respect to conditions under which the inequalities hold strictly, if the vector (∥ξ̃_{i1}∥, …, ∥ξ̃_{ik}∥) has two components that are nonzero with positive probability, then both inequalities in (5) hold strictly, by Lemma 7.2, and otherwise they do not.

8. A Reformulation

This and the following three sections constitute the proof of Theorem 1. We now reformulate the problem in a framework that is more amenable to calculation, and which allows the application of the methods of [SS93] and [BCS98]. Let M_{i} ⊂ H_{i} be the unit sphere defined by ⟨·, ·⟩_{i}, and let

M := M_{1} × … × M_{n}.

As a submanifold of H, M inherits a measure corresponding to the intuitive notion of volume which we denote by vol(·) or (when no confusion is possible) M. The uniform distribution on M is U_{M}(·) := vol(·)/vol(M). The analogous notation will occur in connection with other manifolds as well. The roots of f ∈ H depend only on (f_{1}/∥f_{1}∥, …, f_{n}/∥f_{n}∥), and the random system (f̃_{1}/∥f̃_{1}∥, …, f̃_{n}/∥f̃_{n}∥) is uniformly distributed in M, by virtue of standard facts concerning the multivariate normal distribution.

We regard P_{j} as the space of unordered pairs [ζ_{j}] = {ζ_{j}, −ζ_{j}} of antipodal points in N_{j}, where N_{j} is the unit sphere in IR^{n_{j}+1}. Let

N := N_{1} × … × N_{k}.

For each root [ζ] ∈ P of f ∈ H there are 2^{k} corresponding roots in N.

For each i let θ_{i} : N → H_{i} be the function with components θ_{ia}(ζ) := η(a)^{−1}ζ^{a}. Let F : M × N → IR^{n} be the evaluation map with components

F_{i}(f, ζ) := f_{i}(ζ) = ⟨f_{i}, θ_{i}(ζ)⟩_{i}.

The incidence variety is V = F^{−1}(0). Let π_{1} and π_{2} be the projections from V to M and N respectively. We now have

E(n, δ) = 2^{−k} ∫_{M} #(π_{1}^{−1}(f)) dU_{M}.  (6)

In preparation for the result of the next section we discuss some technical matters.

Lemma 8.1: Each θ_{i} is equivariant with respect to the actions of G on N and H_{i}: θ_{i}(Oζ) = Oθ_{i}(ζ) for all ζ ∈ N and O ∈ G. The image of θ_{i} is contained in the unit sphere of H_{i}.

Proof: We have

⟨Of_{i}, Oθ_{i}(ζ)⟩_{i} = ⟨f_{i}, θ_{i}(ζ)⟩_{i} = f_{i}(ζ) = f_{i}(O^{−1}(Oζ)) = ⟨Of_{i}, θ_{i}(Oζ)⟩_{i}.

Here the first equality is the invariance established in Lemma 3.1, and the other three equalities are essentially matters of definition. For given ζ this holds for all f_{i}, so θ_{i}(Oζ) = Oθ_{i}(ζ). Consequently ∥θ_{i}(Oζ)∥ = ∥θ_{i}(ζ)∥ for all ζ and O. Clearly θ_{i}(ζ) is a standard basis vector of H_{i} if ζ_{1}, …, ζ_{k} are all standard basis vectors in IR^{n_{1}+1}, …, IR^{n_{k}+1} respectively, so the second claim follows from the fact that the action of G on N is transitive.

The equation f_{i}(ζ) = 0 means precisely that f_{i} and θ_{i}(ζ) are orthogonal, so for (f, ζ) ∈ V we may construe θ_{i}(ζ) as a tangent vector in T_{f_{i}}M_{i}, and clearly

\frac{∂F_{i}}{∂f} (f, ζ)(0, …, θ_{i′}(ζ), …, 0)

is nonzero according to whether i′ = i. Thus (f, ζ) is a regular point of F, and 0 is a regular value of F, so the regular value theorem (e.g., [GP65]) implies:

Lemma 8.2: V is a C^{∞} submanifold of M × N with dim V = dim M.

Abusing notation, we let V_{ζ} denote both of the “fibers”

π_{2}^{−1}(ζ) ⊂ V ⊂ M × N and { f ∈ M : (f, ζ) ∈ π_{2}^{−1}(ζ) }

over a point ζ ∈ N, with the appropriate interpretation to be inferred from context. For each i let V_{ζ,i} be the set of f_{i} ∈ M_{i} with f_{i}(ζ) = 0. As the intersection of M_{i} with a hyperplane, this set is a subsphere of M_{i} of codimension one. Thus V_{ζ} = V_{ζ,1} × … × V_{ζ,n} has a simple topology that is independent of ζ, and, as one might expect:

Lemma 8.3: π_{2} : V → N is a C^{∞} fibration.

As usual, to argue this point in detail would be a longwinded and mundane affair, and we shall not do so. It is, perhaps, worth mentioning that the “group” of the fibration may be taken to be the group G introduced in Section 3, and that a suitable atlas of coordinate functions^{(4)} is given by the following maps: given ζ_{0} ∈ N, a neighborhood W ⊂ N of ζ_{0}, and a C^{∞} map h : W → G satisfying h(ζ)ζ_{0} = ζ for all ζ ∈ W, let ϕ : V_{ζ_{0}} × W → π_{2}^{−1}(W) be given by ϕ(f, ζ) := (h(ζ)f, ζ).

(4) This terminology, and the definition of “fibration” we are appealing to, are from [Ste51, §2].

9. An Integral Formula

Sard’s theorem implies that almost all points of M are regular values of π_{1}, so we need only consider such points in computing the average number of roots. Consider a regular point (f, ζ) of π_{1}. Since T_{(f,ζ)}V is mapped surjectively onto T_{f}M by Dπ_{1}(f, ζ), the restriction of DF (f, ζ) to T_{ζ}N ⊂ T_{(f,ζ)}(M × N) must be nonsingular, else (f, ζ) would not be a regular point of F. The implicit function theorem implies that there is a neighborhood U ⊂ M of f for which there is a smooth G : U → N with G(f) = ζ whose graph is contained in V. The condition matrix at (f, ζ) is the matrix of DG(f) which, by the implicit function theorem, is

C(f, ζ) := −(\frac{∂F}{∂ζ} (f, ζ))^{−1} \frac{∂F}{∂f} (f, ζ) : T_{f}M → T_{ζ}N.

This linear transformation gives a description of the way polynomial systems f are associated with roots near (f, ζ). Let C^{∗}(f, ζ) : T_{ζ}N → T_{f}M be the adjoint of C(f, ζ).

Proposition 9.1: ([BCS98, p. 240]) For any open U ⊂ V,

∫_{M} #(π_{1}^{−1}(f) ∩ U) dM = ∫_{N} ∫_{V_{y}∩U} det(C(f, ζ)C^{∗}(f, ζ))^{−1/2}dV_{ζ}dN.

Lemma 9.2: If (f, ζ) ∈ V is a regular point of π_{1}, then

det (C(f, ζ)C^{∗}(f, ζ))^{−1/2} = | det Df(ζ)|.

Proof: For v ∈ T_{0}IR^{n} and ϕ ∈ T_{f}M = T_{f_{1}}M_{1} × … × T_{f_{n}}M_{n} we compute that

\begin{aligned}⟨\frac{∂F}{∂f} (f, ζ)ϕ, v⟩ & = ⟨(⟨ϕ_{1}, θ_{1}(ζ)⟩_{1}, …, ⟨ϕ_{n}, θ_{n}(ζ)⟩_{n}), v⟩ \\ & = ∑_{i=1}^{n}⟨ϕ_{i}, v_{i}θ_{i}(ζ)⟩_{i} = ⟨ϕ, (v_{1}θ_{1}(ζ), …, v_{n}θ_{n}(ζ))⟩. \end{aligned}

This means precisely that the map v ↦ (v_{1}θ_{1}(ζ), …, v_{n}θ_{n}(ζ)) is the adjoint \frac{∂F}{∂f} (f, ζ)^{∗} of \frac{∂F}{∂f} (f, ζ), and in particular \frac{∂F}{∂f} (f, ζ)\frac{∂F}{∂f} (f, ζ)^{∗} is the identity on T_{0}IR^{n}. Since the matrix of the adjoint of a linear transformation is the transpose of the transformation’s matrix, substituting the definition of the condition matrix leads to

det (C(f, ζ)C^{∗}(f,ζ))^{−1/2} = (det(\frac{∂F}{∂ζ} (f, ζ)^{−1}(\frac{∂F}{∂ζ} (f, ζ)^{−1})^{∗}))^{−1/2}

= |det \frac{∂F}{∂ζ} (f, ζ)| = | det Df(ζ)|.

Combining the last two results, for any open U ⊂ V we have

∫_{f∈π_{1}(U)} #(π_{1}^{−1}(f)) dM = ∫_{N} ∫_{V_{ζ}∩U} | det Df(ζ)| dV_{ζ}dN.  (7)

10. Invariance

Combining the actions of G on the various H_{i} (recall Section 3) we obtain an action of G on H given by

Of := (f_{1} ∘ O^{−1}, …, f_{n} ∘ O^{−1}).

We will exploit this symmetry to further simplify the RHS of the formula above.

Each M_{i} is invariant under the action of G on H_{i}, of course, so M is an invariant of the action of G on H, and the restriction of this action to M is an action of G on M. Of course N is invariant under the usual action of G on ∏_{j=1}^{k} IR^{n_{j}+1}. Combining these actions, we derive an action of G on M × N given by O(f, ζ) := (Of, Oζ). For any O ∈ G, f ∈ M, and ζ ∈ N we have Of(Oζ) = f ∘ O^{−1}(Oζ) = f(ζ), so:

Lemma 10.1: V is an invariant of the action of G on M × N: OV = V for all O ∈ G. Consequently (for either interpretation of the symbol V_{ζ}) O(V_{ζ}) = V_{Oζ} for all ζ and O.

Proposition 10.2: The quantity ∫_{V_{ζ}} | det Df(ζ)| dV_{ζ} is independent of ζ.

Proof: Observe that

D(Of)(Oζ) = D(f ∘ O^{−1})(Oζ) = Df(ζ) ∘ O^{−1}

so that | det D(Of)(Oζ)| = | det Df(ζ)|. We now have the calculation that

∫_{V_{Oζ}} | det Df(Oζ)| dV_{Oζ} = ∫_{V_{ζ}} | det D(Of)(Oζ)| dV_{ζ} = ∫_{V_{ζ}} | det Df(ζ)| dV_{ζ}.

Here the first equality is an application of the change of variables formula with the change of variables function an isometry, so that the Jacobean is identically one. The claim now follows from the fact that the action of G on N is transitive.

Applying this to (7), for any open W ⊂ N and any ζ ∈ N we have

∫_{M} #(π_{1}^{−1}(f) ∩ π_{2}^{−1}(W)) dM = vol(W) · ∫_{V_{ζ}} | det Df(ζ)| dV_{ζ}.  (8)

Clearly (b) of Theorem 1 follows directly from this. The remaining task is to prove (a) of that result.

11. The Final Calculations

Fixing ζ ∈ N, let f̃_{ζ} = (f̃_{ζ,1}, …, f̃_{ζ,n}) be the orthogonal projection of f̃ onto the subspace of polynomial systems for which ζ is a root. For each i, ∥f̃_{ζ,i}∥ and f̃_{ζ,i}/∥f̃_{ζ,i}∥ are statistically independent, and the normalized vector is uniformly distributed in V_{ζ,i}, so

∫_{H} | det Df̃_{ζ}(ζ)| dμ = ∫_{H} ( ∏_{i=1}^{n} ∥f̃_{ζ,i}∥) · | det D(\frac{f̃_{ζ,1}}{∥f̃_{ζ,1}∥}, …, \frac{f̃_{ζ,n}}{∥f̃_{ζ,n}∥})(ζ)| dμ

= ( ∏_{i=1}^{n} E(∥f̃_{ζ,i}∥)) ∫_{V_{ζ}} | det Df(ζ)| dU_{V_{ζ}}.

Combining this with (6) and (8), we now obtain

E(n, δ) = 2^{−k} \frac{vol(N) · vol(V_{ζ})}{vol(M) · ∏_{i=1}^{n} E(∥f̃_{ζ,i}∥)} ∫_{H} | det Df̃_{ζ}(ζ)| dμ.

The formula (4) for sphere volume gives

vol(N_{j}) = 2\frac{Γ(\frac{1}{2})^{n_{j}+1}}{Γ(\frac{n_{j}+1}{2})} , vol(M_{i}) = 2\frac{Γ(\frac{1}{2})^{dim H_{i}}}{Γ(\frac{dim H_{i}}{2} )} , vol(V_{ζ,i}) = 2\frac{Γ(\frac{1}{2})^{dim H_{i}−1}}{Γ(\frac{dim H_{i}−1}{2})} ,

and Lemma 7.3 yields

E(∥f̃_{ζ,i}∥) = \frac{\sqrt{2} · Γ(\frac{dim H_{i}}{2} )}{Γ(\frac{dim H_{i}−1}{2})}.

Since vol(M) = vol(M_{1}) × … × vol(M_{n}), and similarly for N and V_{ζ}, we now have

E(n, δ) = 2^{−n/2} · (∏_{j=1}^{k} \frac{Γ(\frac{1}{2})}{Γ(\frac{n_{j}+1}{2})}) · ∫_{H} | det Df̃_{ζ}(ζ)| dμ.  (9)

In the further evaluation of this quantity we are free to let ζ be any convenient point in N. We will compute at ζ_{0} = (e_{10}, …, e_{k0}) ∈ N where, for 1 ≤ j ≤ k, e_{j0}, e_{j1}, …, e_{jn_{j}} are the standard unit basis vectors of IR^{n_{j}+1}. For each i and j let a_{ij}^{0} = (δ_{ij}, 0, …, 0) ∈ A_{ij}, and for each i let a_{i}^{0} = (a_{i1}^{0}, …, a_{ik}^{0}) ∈ A_{i}. Since ζ_{0}^{a} = 0 for all a ∈ A_{i} other than a_{i}^{0}, and ζ_{0}^{a_{i}^{0}} = 1, for each i V_{ζ_{0},i} := { f_{i} ∈ M_{i} : f_{ia_{i}^{0}} = 0 }. For i and j such that δ_{ij} > 0 and each h = 1, …, n_{j}, let a_{i}^{jh} be a_{i}^{0} with a_{ij}^{0} replaced by (δ_{ij} − 1, 0, …, 0, 1, 0, …, 0) (the ‘1’ is component h). Then T_{ζ_{0}}N is spanned by the n vectors

b_{jh} := (0, …, e_{jh}, …, 0) (1 ≤ j ≤ k, 1 ≤ h ≤ n_{j}),

and elementary calculus yields

Df̃_{ζ_{0},i}(ζ_{0})b_{jh} = \{ \begin{matrix}f̃_{ia_{i}^{jh}} & if δ_{ij} > 0, \\ 0 & if δ_{ij} = 0. \end{matrix}

In this way we obtain a description of Df̃_{ζ_{0}}(ζ_{0}) as an n × n matrix with rows indexed by f_{1}, …, f_{n}, columns indexed by the pairs (j, h), and this (i, jh)–entry. Recalling from Section 3 that the variance of f̃_{ia_{i}^{jh}} is δ_{ij}, we

see that the matrix of Df̃_{ζ_{0}}(ζ_{0}) has the same distribution as Z̃. In view of (9) this observation completes the proof of Theorem 1.

References

[Ber75] D. N. Bernshtein, The number of roots of a system of equations, Functional Analysis and its Applications 9 (1975), 183–185.

[BCS93] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer-Verlag, New York, (1998).

[BP32] A. Bloch and G. Pólya, On the roots of a certain algebraic equation, Proc. London Math. Soc. 33 (1932), 102–114.

[EK95] A. Edelman and E. Kostlan, How many zeros of a random polynomial are real?, Bulletin of the American Mathematical Society 32 (1995), 1–37.

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

[Ewa96] G. Ewald, Combinatorial Convexity and Algebraic Geometry, Springer, New York, (1996).

[Fed69] H. Federer, Geometric Measure Theory, Springer, New York, (1969).

[FT91] D. Fudenberg and J. Tirole, Game Theory, MIT Press, Cambridge, (1991).

[Gir90] V.L. Girko, The Theory of Random Determinants, Kluwer, Boston, (1990).

[GP65] V. Guillemin and A. Pollack, DifferentialTopology, Prentice-Hall, Englewood Cliffs, (1965).

[Kac43] M. Kac, On the average number of real roots of a random algebraic equation, Bulletin of the American Mathematical Society 49 (1943), 314–320 and 938.

[Kho78] A. G. Khovanskii, Newton polyhedra and the genus of complete intersections, Functional Analysis and its Applications 12 (1978), 51–61.

[Kos93] E. Kostlan, On the distribution of roots of random polynomials, From Topology to Computation: Proceedings of the Smalefest, Hirsch, M., Marsden, J., and Shub, M. (eds) (1993).

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

[MM97] R. D. McKelvey and A. McLennan, The maximal number of regular totally mixed Nash equilibria, Journal of Economic Theory 72 (1997), 411–425.

[McL97] A. McLennan, On the Expected Number of Nash Equilibria of a Normal Form Game, mimeo, University of Minnesota, (1997).

[McL98] A. McLennan, The maximal number of real roots of a multihomogeneous system of polynomial equations, forthcoming in Beiträge zur Algebra und Geometrie, (1998).

[Meh91] M.L. Mehta, Random Matrices, Academic Press, New York (1991).

[Mui82] R.J. Muirhead, Aspects of Multivariate Statistical Theory, Wiley, New York (1982).

[Roj96] J. M. Rojas, On the average number of real roots of certain random sparse polynomial systems, Lectures on Applied Mathematics Series, ed. by J. Renegar, M. Shub, and S. Smale, American Mathematical Society, (1996).

[SS93] M. Shub and S. Smale, Complexity of Bezout’s theorem II: volumes and probabilities, Computational Algebraic Geometry (F. Eyssette and A. Galligo, eds.), Progr. Math., vol. 109 (1993), Birkhauser, Boston, 267–285.

[Spi65] M. Spivak, Calculus on Manifolds : a Modern Approach to Classical Theorems of Advanced Calculus, Benjamin, New York, (1965).

[Ste51] N. Steenrod, The Topology of Fibre Bundles, Princeton University Press, Princeton (1951).

Andrew McLennan Department of Economics University of Minnesota 271 19th Ave. S. Minneapolis, MN 55455, USA

mclennan@atlas.socsci.umn.edu
http://www.econ.umn.edu/~mclennan