%%%%%%%%%%%%%%%% Macros specific to this document %%%%%%%%%%%%%%%%%%% \def\label#1{\global\edef#1{\the\sectnumber.\the\thenumber}} \newcount\myequno \myequno=0 \def\myeqno{\global\advance\myequno by 1 \eqno(\the\myequno)} \def\eqlabel#1{\global\edef#1{\the\myequno}} \def\MMProp#1{\Prop{\sl #1}} \def\MMLemma#1{\Lemma{\sl #1}} \font\BIGA=cmbx10 scaled \magstep1 \font\BIGB=cmbx10 scaled \magstep2 \font\BIGC=cmbx10 scaled \magstep3 \def\cA{{\cal A}} \def\hcA{{\hat \cA}} \def\cH{{\cal H}} \def\cI{{\cal I}} \def\cHR{\cH^{\Re}} \def\cHC{\cH^{\bf C}} \def\cM{{\cal M}} \def\cP{{\cal P}} \def\cT{{\cal T}} \def\cU{{\cal U}} \def\cV{{\cal V}} \def\cUR{\cU^{\Re}} \def\cUC{\cU^{\bf C}} \def\bb{{\bf b}} \def\be{{\bf e}} \def\bn{{\bf n}} \def\bt{{\bf t}} \def\bx{{\bf x}} \def\by{{\bf y}} \def\bz{{\bf z}} \def\bT{{\bf T}} \def\bU{{\bf U}} \def\ha{{\hat a}} \def\hbx{{\hat \bx}} \def\hby{{\hat \by}} \def\hf{{\hat f}} \def\hU{{\hat U}} \def\hlambda{{\hat \lambda}} \def\hLambda{{\hat \Lambda}} \def\tf{{\tilde f}} \def\tell{{\tilde \ell}} \def\tm{{\tilde m}} \def\tx{{\tilde x}} \def\ty{{\tilde y}} \def\tz{{\tilde z}} \def\tE{{\tilde E}} \def\tM{{\tilde M}} \def\tN{{\tilde N}} \def\tQ{{\tilde Q}} \def\tZ{{\tilde Z}} \def\tepsilon{{\tilde \epsilon}} \def\tzeta{{\tilde \zeta}} \def\tpi{{\tilde \pi}} \def\txi{{\tilde \xi}} \def\tcM{{\tilde{\cal M}}} \def\tcV{{\tilde{\cal V}}} \def\Cstar{{\bf C}^*} \def\prodRorig{P^{d^1}(\Re) \times \ldots \times P^{d^s}(\Re)} \def\prodR{{\cal P}^{\Re}} \def\prodRstarorig{P^{d^1}(\Re^*) \times \ldots \times P^{d^s}(\Re^*)} \def\prodRstar{{\cal P}^{\Re^*}} \def\prodCstar{{\cal P}^{{\bf C}^*}} \def\prodCorig{P^{d^1}({\bf C}) \times \ldots \times P^{d^s}({\bf C})} \def\prodC{{\cal P}^{\bf C}} \def\halpha{{\hat \alpha}} \def\hbeta{{\hat \beta}} \def\hvarepsilon{{\hat \varepsilon}} \def\hmu{{\hat \mu}} \def\cA{{\cal A}} \def\MV{{\cal MV}} \def\Delj{\Delta(n_j)} \def\vol{{\rm vol}} \def\per{{\rm per}} \def\Expect#1#2{{\bf E}_{#1}\big(#2\big)} \def\BigExpect#1#2{{\bf E}_{#1}\Big(#2\Big)} \def\Goal{\Expect{M}{\#(\pi_1^{-1}(\cdot))}} \def\IndexGoal{E(\bn, \delta)} \def\AbsDetDeriv#1#2{{\cal D}(#1,#2)} \def\BKK{B\!K\!K} \def\norevbel{ \bigskip [NO REVISIONS BELOW] \bigskip} \def\Gbig{\Big} \def\Gbigl{\Bigl} \def\Gbigr{\Bigr} \font\elevenbf=cmbx10 scaled \magstephalf % boldface for titles \font\twelvebf=cmbx10 scaled 1315 % large boldface for large titles \def\Re{I\!\!R} \def\bull{\vrule height 1.5ex width 1.0ex depth -.1ex} \newcount\sectnumber \newcount\subsectnumber \newcount\eqnnumber \newcount\notenumber \newcount\thenumber \newcount\teoremnumber \def\eqnno#1{\global\advance\eqnnumber by 1 $$#1\eqno(\the\eqnnumber)$$} \def\acknowledge#1#2{\footnote{#1}{#2}} \def\note#1{\global\advance\notenumber by 1 \footnote{$^{(\the\notenumber)}$}{#1}} \def\Ass{\noindent \global\advance\thenumber by 1 {\bf Assumption $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\endass{\bigskip} \def\Not{\noindent \global\advance\thenumber by 1 {\bf Notation $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\endnot{\bigskip} \def\Def{\noindent \global\advance\thenumber by 1 {\bf Definition $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\enddef{\bigskip} \def\Rem{\noindent \global\advance\thenumber by 1 {\bf Remark $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\endrem{\bigskip\rm} \def\Th{\noindent \global\advance\teoremnumber by 1 {\bf Theorem $\bf \the\teoremnumber$:}\enspace} \teoremnumber = 0 \def\endth{\bigskip\rm} \def\Cor{\noindent \global\advance\thenumber by 1 {\bf Corollary $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\endcor{\bigskip\rm} \def\Ex{\noindent \global\advance\thenumber by 1 {\bf Example $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\endex{\bigskip} \def\Prop{\noindent \global\advance\thenumber by 1 {\bf Proposition $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\AppBProp{\noindent \global\advance\thenumber by 1 {\bf Proposition B.$\bf \the\thenumber$:}\enspace} \def\endprop{\bigskip\rm} \def\Claim{\noindent \global\advance\thenumber by 1 {\bf Claim $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\endclaim{\bigskip\rm} \def\Lemma{\noindent\global\advance\thenumber by 1 {\bf Lemma $\bf \the\sectnumber$.$\bf \the\thenumber$:}\enspace} \def\AppALemma{\noindent\global\advance\thenumber by 1 {\bf Lemma A.$\bf \the\thenumber$:}\enspace} \def\endlemma{\bigskip\rm} \def\Proof{\noindent{\bf Proof of:}} \def\endproof{\enspace\bull\bigskip} \def\Pf{\noindent{\bf Proof:\enspace}} \def\endpf{\enspace\bull\bigskip} % The following were added by AM, in response to a desire for % macros that did not constrain theorem and lemma numbers unduly \def\myLem#1#2{\noindent {\bf Lemma {#1}:} {\it #2}} %%%%%%%%% \def\Section#1{\bigskip \eqnnumber=0 \thenumber=0 \subsectnumber=0 \global\advance\sectnumber by 1 {\noindent{\elevenbf$\bf \the\sectnumber$.\enspace#1}} \nobreak} \def\Subsection#1{\medskip \global\advance\subsectnumber by 1 {\noindent $\quad$\it$\bf \the\sectnumber$.$\bf \the\subsectnumber$.\enspace#1} \smallskip} %%%%%%%%%%%%%%%%%% Start of MSRI Form %%%%%%%%%%%%%%%%%%%%%%%%% \magnification=1200 \vsize=8truein \hsize=6truein \hoffset=18truept \voffset=24truept \font\smc=cmcsc10 \font\smallsmc=cmcsc8 \font\smallrm=cmcsc8 \headline={\ifodd\pageno \ifnum\pageno>1 \smallrm \hfil EXPECTED NUMBER OF REAL ROOTS % running head for right-hand page is title in caps \hfil\folio \else\hfill\fi \else \smallrm \folio \hfill ANDREW MCLENNAN % running head for left-hand page is authors in caps \hfill\fi} \footline={\hss} % footline is blank \vglue .5in \centerline{\bf THE EXPECTED NUMBER OF REAL ROOTS} \centerline{ \bf OF A MULTIHOMOGENEOUS SYSTEM } \centerline{\bf OF POLYNOMIAL EQUATIONS %use capital letters for title } \vglue .5in \centerline{\smc %cap and lowercase for author Andrew McLennan } \vglue .5in \narrower{\noindent {\smc 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. } \vglue .5in \footnote{}{\hskip-\parindent 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. } \vfill \eject \centerline{\twelvebf The Expected Number of Real Roots of a} \centerline{\twelvebf Multihomogeneous System of Polynomial Equations} \bigskip \vskip .1cm \Section{Introduction} \medskip 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, \ldots, d_n$, showing that the mean is $\sqrt{\prod_i d_i}$, which is again the square root of the Bezout number. Rojas [Roj96] studies unmixed\note{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.} 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 $\Gamma$ 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 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\note{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 {\it quasiequilibrium\/} (Section 2) is sufficient. For the connection between this notion and the standard concepts of {\it Nash equilibrium\/} and {\it totally mixed Nash equilibrium\/} see [MM97, McL97].}. 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 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 {\it 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. \vskip .1cm \medskip \Section{Multihomogeneous Systems} \medskip 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 {\it sparse system\/} of $n$ polynomial equations in $\ell$ variables is $$f(\bx) = (f_1(\bx), \ldots, f_n(\bx)) = 0, $$ where $\bx\,=\,(x_1,\ldots,x_{\ell})\,$ and, for each $i = 1, \ldots, n$, there is a nonempty finite $\cA_i \subset {\bf N}^{\ell}$ such that $f_i (\bx) = \sum_{a \in \cA_i}f_{ia} \bx^a$ for some system of coefficients $f_{ia}$. (Here $\bx^a$ denotes the monomial $x_1^{a_1}x_2^{a_2}\cdots x_{\ell}^{a_{\ell}}$.) The general approach of the theory of sparse systems is to hold the $n$-tuple of {\it supports\/} $(\cA_1, \ldots, \cA_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 {\it unmixed\/} if $\cA_1 = \ldots = \cA_n$; otherwise it is {\it mixed}. Identifying a polynomial with its vector of coefficients, we regard $\cH_i := \Re^{\cA_i} \setminus \{0\}$ as the space of polynomials with real coefficients whose supports are nonempty subsets of $\cA_i$. Let $$\cH := \cH_1 \times \ldots \times \cH_n.$$ The system is {\it multihomogeneous\/} if the variables in $\bx$ are divided into $k$ groups, so that $\bx = (\by_1, \ldots, \by_k)$ where $\by_j = (y_{j0},y_{j1}, \ldots, y_{jn_j})$, and each equation is homogeneous of degree $\delta_{ij}$ as a function of $\by_j$, for any given values of the other variables $(\by_1, \ldots, \by_{j-1}, \by_{j+1}, \ldots, \by_k)$. More precisely, we require that there are nonnegative integers $\delta_{ij}$ ($i = 1, \ldots, n$, $j = 1, \ldots, k$) such that $$\cA_i = \cA_{i1} \times \ldots \times \cA_{ik}, \quad \hbox{where} \quad \cA_{ij} = \{\, \alpha \in {\bf N}^{n_j+1} : \alpha_0 + \alpha_1 + \ldots + \alpha_{n_j} = \delta_{ij} \,\}.$$ When $f_i$ is multihomogeneous, the truth value of the proposition `$f_i(\bx) = 0$' is unaffected if each block of variables is multiplied by a nonzero scalar, so that, in effect, there are $\ell - k$ degrees of freedom. We work only with systems that are, in this sense, exactly determined: $\ell = n + k$, so that $n_1 + \ldots + n_k = n.$ An instance of the type of system studied here is specified by the vector $\bn$ and the $n \times k$ matrix $\delta := (\delta_{ij})$. Four particular types of multihomogeneous system figure in our discussion: \smallskip \item{(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 \ne j$. \item{(b)} The {\it unmixed\/} multihomogeneous systems studied in [Roj96] are described by the condition that all equations have the same support: there are integers $e_1, \ldots, e_k$ such that $$\delta_{1j} = \ldots = \delta_{nj} = e_j \quad (j = 1, \ldots, k).$$ \item{(c)} Generalizing (a) and (b) are the systems for which there are numbers $d_1, \ldots, d_n$ and $e_1, \ldots, e_k$ such that $\delta_{ij} = d_ie_j$ for all $i$ and $j$. \item{(d)} The systems arising, in game theory, from the concept of quasiequilibrium ([MM97]) of a finite normal form game, have, for each $j = 1, \ldots,k$, $n_j$ equations that are homogeneous of degree one in $\by_h$ for all $h \ne j$, and are homogeneous of degree zero in $\by_j$. Formally these systems can be characterized as follows: $$\delta_{ij} = \cases{ 0 & if $q(i) = j$, \cr \noalign{\smallskip} 1 & otherwise, \cr }\myeqno \eqlabel{\NashEquilibrium} $$ where $q : \{1, \ldots, n\} \to \{1, \ldots, k\}$ is the function defined implicitly by the inequality $$n_1 + \ldots + n_{q(i)-1} < i \le n_1 + \ldots + n_{q(i)}.$$ \vskip .1cm \goodbreak \medskip \vfill \eject \Section{An Invariant Inner Product} \nobreak \medskip Fix a pair $(\bn,\delta)$. Since $n_1 + \ldots + n_k = n$, we may index the components of an exponent vector $a \in {\bf N}^{n+k}$ by the pairs $(j,h)$ for $j = 1, \ldots, k$ and $h = 0, \ldots, n_j$. For such an $a$ let $$\eqalign{ \eta & (a) := { a_{10}! \cdot \ldots \cdot a_{1n_1}! \over (a_{10} + \ldots + a_{1n_1})!} \cdot \ldots \cdot { a_{k0}! \cdot \ldots \cdot a_{kn_k}! \over (a_{k0} + \ldots + a_{kn_k})!} \cr & \strut \cr & = \left( { a_{10} + \ldots + a_{1n_1} \atop a_{10}, \ldots, a_{1n_1} } \right)^{-1} \cdot \ldots \cdot \left( { a_{k0} + \ldots + a_{kn_k} \atop a_{k0}, \ldots, a_{kn_k} } \right)^{-1}. \cr }$$ We endow each $\cH_i$ with the inner product $$\langle f_i, f'_i \rangle_i := \sum_{a \in \cA_i} \eta(a) f_{ia}f'_{ia}.$$ Let $\|\cdot\|_i$ be the norm derived from $\langle \cdot, \cdot \rangle_i$. Consider the product group $$G := O(n_1 + 1) \times \ldots \times O(n_k + 1).$$ There is the obvious component-wise action of $G$ on $\Re^{n_1+1} \times \ldots \times \Re^{n_k+1}$, and for $f_i \in \cH_i$ and $O \in G$, $f_i \circ O^{-1}$ is easily seen to be a polynomial function that is multihomogeneous for the same numbers $\delta_{ij}$, so $f_i \circ O^{-1}$ is an element of $\cH_i$. Thus the formula $Of_i := f_i \circ O^{-1}$ defines an action from the left of $G$ on $\cH_i$. The following generalizes [Kos93, Th.~4.2], which is the case $k = 1$. \medskip \MMLemma{ \label{\UniqueInvariance} The inner product (4) is the unique (up to multiplication by a scalar) inner product on $\cH_i$ that is invariant under the action of $G$ and with respect to which the monomials are pairwise orthogonal. } \endlemma \medskip \noindent{\bf Proof:} Let $\langle f_i, f'_i \rangle_i^* = \sum_{a \in \cA_i} \eta^*(a) f_{ia}f'_{ia}$ be an invariant inner product with all monomials orthogonal. We wish to show that $\eta^*(a)/\eta^*(a') = \eta(a)/\eta(a')$ for all $a, a' \in \cA_i$. Fixing arbitrary $a \in \cA_i$ and $j = 1, \ldots, k$, it suffices to establish that this formula holds for those $a' \in \cA_i$ with $a_{\ell h} = a'_{\ell h}$ whenever $\ell \ne j$, and this follows from [Kos93, Th.~4.2] applied to the subspace of $\cH_i$ spanned by such $a'$. To see that $\langle \cdot , \cdot \rangle_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$. \endproof 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^{\rm th}$ equation centrally normally distributed in $\cH_i$ relative to $\langle \cdot, \cdot \rangle_i$. Concretely this means that the coefficients $\tf_{ia}$ are independent Gaussian random variables with mean 0 and variance $\eta(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 $\mu_i$ be the probability measure on $\cH_i$ that is the distribution of $\tf_i$, and let $$\mu := \mu_1 \times \ldots \times \mu_n$$ be the distribution of $\tf := (\tf_1, \ldots, \tf_n)$. In the calculations used to prove Theorem 1 we also consider the model in which the coefficient vectors $f_1, \ldots, f_n$ are statistically independent, with each $f_i$ uniformly distributed in the unit sphere (relative to $\|\cdot\|_i$) of $\cH_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. \vskip .1cm \goodbreak \medskip \Section{The Central Formula} \medskip We count roots in the $k$-fold product of projective spaces $$P := P_1 \times\ldots \times P_k$$ where, for $j = 1, \ldots, k$, $P_j := {\bf P}^{n_j}(\Re)$ is $n_j$-dimensional real projective space. In the usual way, the equation $f_i(\zeta) = 0$ is meaningful for $f_i \in \cH_i$ and $\zeta \in P$ even though $f_i$ is not a function defined on $P$. Our central concern is the expected number of roots $$\IndexGoal := \Expect{}{ \#(\{\, \zeta \in P : \tf(\zeta) = 0 \,\})},$$ but in fact we completely characterize the distribution of roots. Let $\tZ$ be a random $n \times n$ matrix with rows indexed by the integers $i = 1, \ldots, n$, columns indexed by the pairs $jh$ for $j = 1, \ldots, k$ and $h = 1, \ldots, n_j$, and entries $\tz_i^{jh}$ that are independently distributed normal random variables with mean zero and variance $\delta_{ij}$. Let $\Gamma(s) := \int_0^{\infty} {\rm exp}(-t)t^{s-1}\, dt$ be Euler's function. \medskip \noindent{\bf Theorem 1:} {\sl \itemitem{(a)} $$\IndexGoal = 2^{-n/2} \cdot \Gbigl( \prod_{j = 1}^k { \Gamma({1 \over 2}) \over \Gamma({n_j + 1 \over 2}) } \Gbigr) \cdot \Expect{}{ | \det \tZ | }. \myeqno \eqlabel{\MainResult} $$ \itemitem{(b)} The induced distribution of roots is uniform: for any open $W \subset P$, $$\Expect{}{ \#(\{\, \zeta \in W : \tf(\zeta) = 0 \,\})} = {\vol(W) \over \vol(P)}\IndexGoal.$$ } \medskip \noindent This will be proved in Sections 8--11. The next three sections describe the consequences of this result. \vskip .1cm \goodbreak \medskip \Section{Reduction to Closed Form} \medskip In certain circumstances the RHS of (\MainResult) 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 $\Gamma({1 \over 2}) = \sqrt{\pi}$, $\Gamma(1) = 1$, and $\Gamma(s + 1) = s\Gamma(s)$ for all $s > 0$, the evaluations of $\Gamma$ in (\MainResult) will be regarded as being in closed form already, so the problem is to reduce the term $\Expect{}{ | \det \tZ | }$. 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 $\delta_{ij} = 0$ for all $i,j$ such that $q(i) \le k'$ and $k' < j$, where $q(\cdot)$ is the function defined at the end of Section 2. Set $n' := n_1 + \ldots + n_{k'}$. Then $$\delta = \left[ \matrix{ \delta^{11} & 0 \cr \delta^{21} & \delta^{22} \cr } \right].$$ where $\delta^{11}$, $\delta^{21}$, and $\delta^{22}$ have dimensions $n' \times k'$, $(n - n') \times k'$, and $(n - n') \times (k - k')$ respectively. Then (with probability one) $\tZ$ has an $n' \times (n - n')$ block of zeros in its upper right corner, so its determinant is the product of the determinants of the $n' \times n'$ submatrix in the upper left and the $(n - n') \times (n - n')$ submatrix in the lower right. In particular, $\Expect{}{|\det \tZ|}$ does not depend on $\delta^{21}$. Consequently (\MainResult) implies that $\IndexGoal$ is also independent of $\delta^{21}$. When we set $\delta^{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 $\tZ$ is the product of the determinants of the submatrices. \medskip \noindent {\bf Corollary 1:} {\sl Suppose there is some $1 \le k' < k$ such that $\delta_{ij} = 0$ whenever $q(i) \le k' < j$, and let $\delta^{11}$ and $\delta^{22}$ be as above. Then $$E(\bn, \delta) = E((n_1,\ldots,n_{k'}), \delta^{11}) \cdot E((n_{k' + 1},\ldots,n_{k}), \delta^{22}).$$ } \medskip A second general principle results from the effect on the determinant of multiplying a row or a column by a scalar. \medskip \noindent{\bf Corollary 2:} {\sl If there are nonnegative integers $d_1, \ldots, d_n$ and $e_1, \ldots, e_k$ such that $\delta'_{ij} = d_i \cdot e_j \cdot \delta_{ij}$, then $$E(\bn, \delta') = \sqrt{\prod_{i = 1}^n d_i} \cdot \sqrt{\prod_{j=1}^k e_j^{n_j}} \cdot \IndexGoal.$$ } \medskip Consider now the particular case of $k = 1$ and $\delta_{11} = \ldots = \delta_{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 (\MainResult) we must have: \medskip \MMProp{ \label{\MeanAbsoluteDeterminant} The mean absolute value of the determinant of a random $n \times n$ matrix whose entries are independently distributed normal random variables with mean zero and unit variance is $$2^{n/2} \cdot {\Gamma({n+1 \over 2}) \over \Gamma({1 \over 2})}.$$ } Combining the last two results with Theorem 1 yields \medskip \noindent {\bf Theorem 2:} {\sl If there are nonnegative integers $d_1, \ldots, d_n$ and $e_1, \ldots, e_k$ such that $\delta_{ij} = d_i \cdot e_j$, then $$E(\bn, \delta) = { \Gamma({n+1 \over 2}) \over \Gamma({1 \over 2})} \cdot \Gbigl( \prod_{j = 1}^k { \Gamma({1 \over 2}) \over \Gamma({n_j + 1 \over 2}) } \Gbigr) \cdot \sqrt{\prod_{i = 1}^n d_i} \cdot \sqrt{\prod_{j=1}^k e_j^{n_j}}.$$ } \medskip \noindent The Shub-Smale formula is the special case $k = 1$, and Rojas' formula for unmixed systems is obtained when $d_1 = \ldots = d_n = 1$. There is a class of systems for which $\IndexGoal$ can be computed exactly by combining Corollaries 1 and 2 with Proposition \MeanAbsoluteDeterminant. I know of no case outside this class in which the expectation $\Expect{}{ | \det \tZ | }$ 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: \medskip \noindent{\bf Corollary 3:} {\sl In the case of the game equilibrium system given by (\NashEquilibrium), if $k = 2$ then $$E(\bn, \delta) = \cases{ 1 & if $n_1 = n_2$, \cr \noalign{\smallskip} 0 & otherwise. \cr }$$ } \vskip .1cm \goodbreak \medskip \Section{The BKK Bound for Multihomogeneous Systems} \medskip This section explains the consequences of Bernshtein's [Ber75] theorem for multihomogeneous systems. Let $f(\bz) = (f_1(\bz), \ldots, f_n(\bz))$ be a general sparse system of $n$ equations in the $n$ variables $z_1, \ldots, z_n$, where $f_i$ has support $\cA_i \subset {\bf N}^{n}$. The {\it Newton polytope\/} of $f_i$ is the convex polytope $Q_i = {\rm con}(\cA_i)$. The {\it mixed volume\/} of $Q_1, \ldots, Q_n$, which was first defined and studied by Minkowski, and which we denote by ${\cal MV}( Q_1, \ldots, Q_n)$, may be defined to be the coefficient of the monomial $\lambda_1 \cdot \ldots \cdot \lambda_n$ in the polynomial\note{See [Ewa96] for a proof that $\vol(Q_{\lambda})$ is, in fact, a polynomial function of $\lambda$.} $\vol(Q_{\lambda})$ where $$Q_{\lambda} = \lambda_1Q_1 + \ldots + \lambda_nQ_n.$$ \medskip\noindent {\bf Theorem:} ([Ber75]) {\sl Let $\Cstar := {\bf C} \setminus \{0\}$. Let $\cH^{\bf C} = \cH^{\bf C}_1 \times \ldots \times \cH^{\bf C}_n$ where $\cH^{\bf C}_i = {\bf C}^{\cA_i}$ is the space of complex polynomials with support $\cA_i$. For systems $f$ in the complement, in $\cH^{\bf C}$, of an algebraic set of positive (complex) codimension, there are ${\cal MV}( Q_1, \ldots, Q_n)$ roots in $(\Cstar)^n$. } \medskip \noindent The maximal number ${\cal MV}( Q_1, \ldots, 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} = \ldots = y_{k0} = 1$. In comparing the roots of the latter system, in $(\Cstar)^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^{\rm th}$ demultihomogenized equation is $Q_i = \prod_{j:n_j>0} \delta_{ij}\Delj$, where $$\Delj := \{\, (z_{j1}, \ldots , z_{jn_j}) \in \Re^{n_j}_{\ge0} : z_{j1} + \ldots + z_{jn_j} \le 1 \,\},$$ and the generic number of complex roots of the system is $$\BKK (\bn, \delta) := {\cal MV}\Big(\prod_{j:n_j>0} \delta_{1j}\Delj, \ldots, \prod_{j:n_j>0} \delta_{nj}\Delj\Big).$$ Our analysis of this quantity employs the following concept. The {\it permanent\/} (e.g., [Ego96]) of an $m \times n$ matrix $D$ with entries $d_{ij}$ is $${\rm per} \, D := \sum_{\sigma \in S_{m,n}} \left(\prod_{i=1}^n d_{i\sigma(i)}\right)$$ where $S_{m,n}$ is the set of one to one functions from $\{1,\ldots,m\}$ to $\{1,\ldots,n\}$. Since there are no such functions when $m > n$, in which case ${\rm 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, \ldots,m$ $${\rm per} \, D = \sum_{j=1}^n d_{ij} \cdot {\rm per} \, D^{ij}$$ where $D^{ij}$ is the $(m - 1) \times (n - 1)$ matrix obtained from $D$ by eliminating the $i^{\rm th}$ row and the $j^{\rm 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 $\Delta(\bn,\delta)$ be the $n \times n$ matrix whose first $n_1$ columns are the first column of $\delta$, whose next $n_2$ columns are the second column of $\delta$, and so forth. The computation $$\vol\Gbigl( \sum_{i=1}^n \lambda_i \Big(\prod_{j:n_j > 0} \delta_{ij} \Delta(n_j) \Big)\Gbigr) = \vol\Gbigl(\prod_{j:n_j > 0} \Big(\sum_{i=1}^n \lambda_i \delta_{ij} \Big)\Delta(n_j) \Gbigr)$$ $$= {\prod_{j:n_j > 0} \Big(\sum_{i=1}^n \lambda_i \delta_{ij} \Big)^{n_j} \over n_1! \cdot \ldots \cdot n_k!}$$ has the following immediate implication: \medskip \MMProp{ \label{\RecursiveMaximum} {\rm ([McL98])} $$\BKK (\bn,\delta) = {{\rm per} \, \Delta(\bn,\delta) \over n_1!\cdot\ldots\cdot n_k!}.$$ } \medskip The next result enumerates consequences of the elementary properties of the permanent, applied to this result. For $i = 1, \ldots, n$ let $\delta^{-i}$ be the $(n - 1)\times k$ matrix obtained by eliminating the $i^{\rm th}$ row of $\delta$. For $j = 1, \ldots, k$ let $\be_j$ be the $j^{\rm th}$ standard unit basis vector of $\Re^k$. In the recursive formulas below we are adopting the convention that $$\BKK ((0,\ldots,0),\delta_0) = E((0,\ldots,0),\delta_0) = 1,$$ where $\delta_0$ is the $0 \times k$ matrix. This means that the ``null system'' with no variables and no equations has one root. \medskip \MMProp{ \label{\RecursiveMaximumCorollaries} {\rm ([McL98])} \itemitem{(a)} For all $i = 1, \ldots, n$, $$\BKK (\bn,\delta) = \sum_{j : n_j > 0} \delta_{ij} \cdot \BKK (\bn - \be_j, \delta^{-i}). $$ \itemitem{(b)} For all $j = 1, \ldots, k$ such that $n_j > 0$, $$\BKK (\bn,\delta) = {1 \over n_j}\sum_{i = 1}^n \delta_{ij} \cdot \BKK(\bn - \be_j, \delta^{-i}).$$ \itemitem{(c)}Suppose there is some $1 \le k' < k$ such that $\delta_{ij} = 0$ whenever $q(i) \le k' < j$, and let $\delta^{11}$, $\delta^{21}$, and $\delta^{22}$ be as in Section 4. Then $$\BKK (\bn, \delta) = \BKK ((n_1,\ldots,n_{k'}), \delta^{11}) \cdot \BKK ((n_{k' + 1},\ldots,n_{k}), \delta^{22}).$$ \itemitem{(d)} If there are nonnegative integers $d_1, \ldots, d_n$ and $e_1, \ldots, e_k$ such that $\delta'_{ij} = d_i \cdot e_j \cdot \delta_{ij}$, then $$\BKK (\bn, \delta') = \Big( \prod_{i = 1}^n d_i \Big) \cdot \Big( \prod_{j:n_j>0} e_j^{n_j} \Big) \cdot \BKK (\bn,\delta).$$ } \medskip The recursive formulas (a) and (b) give obvious algorithms for computing $\BKK (\bn, \delta)$ that have computed values of $\BKK $ on the order of $10^{21}$. (Cf.~[MM97].) In preparation for Theorem 3, we ask when $\BKK(\bn,\delta)$ can be computed by repeated applications of (a) in which the RHS has only one nonzero term. We say that the pair $(\bn,\delta)$ is {\it 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$, $\delta_{ij} > 0$, and $\BKK(\bn - \be_j, \delta^{-i}) > 0$, and if $n > 1$ we require that for this $j$, $(\bn - \be_j, \delta^{-i})$ is also simply reducible. This will clearly be the case when repeated applications of (c) reduces $\BKK(\bn,\delta)$ to a product of instances of the general homogeneous system. In fact this is the only way that $(\bn,\delta)$ can be simply reducible, as we shall see in the next section. We will need the following technical result. Let $A$ be an $m \times n$ matrix of 0's and 1's. We say that an $m \times n$ matrix $D = (d_ij)$ is $A$-{\it sparse\/} if $d_{ij} = 0$ whenever $a_{ij} = 0$. \medskip \MMLemma {\label{\RankCondition} The following conditions are equivalent: \itemitem{(i)} there is an integer $1 \le k < m$ such that, after relabelling of rows and columns, $A$ has a $k \times (n + 1 - k)$ block of 0's. \itemitem{(ii)} ${\rm per}\, A = 0$; \itemitem{(iii)} all $A$-sparse matrices have row rank less than $m$. } \medskip \noindent {\bf Proof:} Clearly (i) implies (ii). The meaning of (ii) is that for each one-to-one $\sigma : \{1,\ldots,m\} \to \{1,\ldots,n\}$ there is some $i$ such that $a_{i\sigma(i)} = 0$, which implies that all $A$-sparse matrices have no $m \times 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 \times (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. \endproof \vskip .1cm \goodbreak \medskip \Section{The Mean Exceeds the Square Root of the Maximum} \medskip Let $\Delta_{1 \over 2}\!(\bn, \delta)$ be the $n \times n$ matrix whose $(i,jh)$-entry is $\sqrt{\delta_{ij}}$. This section establishes the following generalization of the Shub--Smale formula. \medskip \noindent {\bf Theorem 3:} {\sl $${\per \, \Delta_{1 \over 2}\!(\bn,\delta) \over n_1! \cdot \ldots \cdot n_k!} \ge E(\bn,\delta) \ge \sqrt{\BKK (\bn,\delta)} = \sqrt{{\per \, \Delta(\bn,\delta) \over n_1! \cdot \ldots \cdot n_k!}}.$$ These inequalities hold with equality when $(\bn,\delta)$ is simply reducible and not otherwise. } \medskip Theorem 3 will follow by induction from the following stronger result. \medskip \noindent {\bf Theorem 4:} {\sl For all $i = 1, \ldots, n$, $$\sum_{j : n_j > 0} \sqrt{\delta_{ij}} \cdot E(\bn - \be_j, \delta^{-i}) \ge E(\bn,\delta) \ge \sqrt{\sum_{j : n_j > 0} \delta_{ij} \cdot E(\bn - \be_j, \delta^{-i})^2}, $$ These inequalities hold with equality if and only if there is at most one $j$ with $\delta_{ij} > 0$ and $E(\bn - \be_j, \delta^{-i}) > 0$. } \medskip \noindent {\bf Proof of Theorem 3:} The asserted inequalities follow from an induction on $n$ that begins with the convention that $E(\bn,\delta) = \BKK (\bn,\delta) = 1$ when $n_1 = \ldots = n_k = 0$. The induction step is a matter of comparing (a) of Proposition \RecursiveMaximumCorollaries\ and the analogous formula for $\per \, \Delta_{1 \over 2}(\bn,\delta)$ 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(\bn - \be_j, \delta^{-i}) > 0$, and $E(\bn - \be_j, \delta^{-i})$ also satisfies the inequality with equality. In particular, it follows from induction that $ E(\bn,\delta) > 0$ if and only if $\BKK (\bn,\delta) > 0$, so either of the inequalities in Theorem 3 holds with equality if and only if $(\bn,\delta)$ is simply reducible. \endproof \medskip \noindent {\bf 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 \RecursiveMaximumCorollaries\ shows that $(\bn,\delta)$ is simply reducible if and only if both $((n_1,\ldots,n_{k'}), \delta^{11})$ and $((n_{k' + 1},\ldots,n_{k}), \delta^{22})$ are simply reducible. Thus it suffices to characterize simple reducibility when the hypotheses of (c) of Proposition \RecursiveMaximumCorollaries\ are not satisfied: there is no $1 \le k' < k$ such that (after any reordering of rows and columns) $\delta_{ij} = 0$ whenever $q(i) \le 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 $(\bn,\delta)$ is simply reducible, then for {\it any\/} $i = 1, \ldots, n$ there is at most one $j$ with $n_j > 0$, $\delta_{ij} > 0$, and $\BKK(\bn - \be_j, \delta^{-i}) > 0$, with $(\bn - \be_j, \delta^{-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$, $\delta_{ij} > 0$, and $\delta_{ij'} > 0$, then either $\BKK(\bn - \be_j,\delta^{-i}) = 0$ or $\BKK(\bn - \be_{j'},\delta^{-i}) = 0$, in which case Proposition \RecursiveMaximum\ and Lemma \RankCondition\ imply that $\Delta(\bn - \be_j,\delta^{-i})$ or $\Delta(\bn - \be_{j'},\delta^{-i})$ has a block of zeros, as per (iii) of Lemma \RankCondition, and this implies that the hypotheses of (c) of Proposition \RecursiveMaximumCorollaries\ are satisfied by $(\bn,\delta)$, contrary to assumption. For each $i$ there is consequently at most one $j$ with $n_j > 0$ and $\delta_{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 \RecursiveMaximumCorollaries\ are satisfied by $(\bn,\delta)$, so $n_j = n$ for some $j$. That is, we have the general homogeneous case. \medskip It remains to prove Theorem 4. For the random matrix $\tZ$ of Theorem 1, let $\tZ^i_{jh}$ be the determinant of the $(n-1) \times (n-1)$ minor obtained by eliminating row $i$ and column $jh$. Observe that, by Theorem 1, $$\Expect{}{|\tZ^i_{jh}|} = 2^{n-1 \over 2}{ \Gamma({n_j \over 2}) \over \Gamma({n_j + 1 \over 2}) } \Gbigl( \prod_{p = 1}^k { \Gamma({n_p + 1 \over 2}) \over \Gamma({1 \over 2}) } \Gbigr)E(\bn - \be_j,\delta^{-i}),$$ so, applying Theorem 1 again to express $E(\bn,\delta)$ in terms of $\Expect{}{|\det \tZ|}$, we quickly find that the assertion of Theorem 4 is equivalent to: \medskip \MMProp{ \label{\InTermsOfZ} For all $i = 1, \ldots, n$, $$\sum_{j : n_j > 0} \sqrt{\delta_{ij}} { \Gamma({n_j +1 \over 2}) \over \Gamma({n_j \over 2})} \Expect{}{|\tZ^i_{j1}|} \ge { \Expect{}{|\det \tZ|} \over \sqrt{2} } \ge \sqrt{\sum_{j : n_j > 0} \delta_{ij} \Gbig( { \Gamma({n_j +1 \over 2}) \over \Gamma({n_j \over 2})} \Gbig)^2\Expect{}{|\tZ^i_{j1}|}^2}.$$ These inequalities hold with equality if and only if $\delta_{ij}\Expect{}{|\tZ^i_{j1}|} > 0$ for at most one $j$. } \medskip 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. \medskip \MMLemma{ \label{\UpperLowerExpectedNormBounds} If $\tx$ is a $\Re^m_{\ge 0}$--valued random variable for which $\Expect{}{\tx}$ is defined, then $$\sum_{h = 1}^m \Expect{}{|\tx_h|} \ge \Expect{}{\|\tx\|} \ge \big\|\Expect{}{\tx}\big\|.$$ The first inequality holds with equality if and only if the support of the distribution of $\tx$ 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 $\tx$ is contained in a single ray emanating from the origin. } \medskip \noindent {\bf Proof:} Since $\sum_h \Expect{}{|\tx_h|} = \Expect{}{ \sum_h |\tx_h|}$, the first inequality follows from $\sum_{h = 1}^m |\tx_h| \ge \|\tx\|$, and it holds with equality if and only if, with probability one, $\sum_{h = 1}^m |\tx_h| = \|\tx\|$. The second inequality follows from Jensen's inequality, and it holds with equality if and only if $\|(1 - \alpha)x_0 + \alpha x_1\| = (1 - \alpha)\|x_0\| + \alpha\|x_1\|$ for any $x_0, x_1$ in the support of the distribution of $\tx$ and any $0 \le \alpha \le 1$.\endproof \medskip We will need the following technical fact. \medskip \MMLemma{ \label{\MeanNormLemma} Let $\tepsilon = (\tepsilon_1, \ldots, \tepsilon_m)$ where $\tepsilon_1, \ldots, \tepsilon_m$ are independent identically distributed normal random variables with mean zero and unit variance. Then $$\Expect{}{\|\tepsilon\|} = {\sqrt{2} \cdot \Gamma({m+1 \over 2})\over \Gamma({m \over 2}) }. \myeqno \eqlabel{\MeanNorm} $$ } \medskip \noindent {\bf Proof:} We compute that $$\eqalign{ \Expect{}{\|\tepsilon\|} & = \int_{-\infty}^{\infty} \ldots \int_{-\infty}^{\infty} \|x\| \cdot ({1 \over \sqrt{2\pi}} e^{-x_1^2/2} \, dx_1) \cdot \ldots \cdot ({1 \over \sqrt{2\pi}} e^{-x_m^2/2} \, dx_m) \cr & = (2\pi)^{-m/2} \int_{\Re^m} \|x\| \cdot e^{-\|x\|^2/2} \, dx \cr & = (2\pi)^{-m/2} \int_0^{\infty} (re^{-r^2/2}) \cdot \vol(S^{m-1}) \cdot r^{m-1} \, dr. \cr }$$ The asserted formula is now obtained from the formula (e.g.,~[Fed69, p.~251]) $$\vol(S^{m-1}) = 2 { \Gamma({1 \over 2})^m \over \Gamma({m \over 2}) } \quad (m \ge 1) \myeqno \eqlabel{\SphereVolume}$$ the change of variables $t := r^2/2$, the fact that $\Gamma({1 \over 2} ) = \sqrt{\pi}$, and the definition of $\Gamma(\cdot)$. \endproof \medskip 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. \medskip \MMProp{ \label{\ExpansionByMinors} Let $\tE$ be an $n \times n$ matrix whose entries $\tepsilon_{ab}$ are independently distributed normal random variables with mean zero and variance $\sigma_{ab}^2$. For $1 \le a,b \le n$ let $\tE^{ab}$ be the determinant of the $(n-1) \times (n-1)$ minor of $\tE$ obtained by eliminating row $a$ and column $b$. Then for any $a = 1, \ldots, n$: $$ \sqrt{2/\pi} \cdot \sum_{b=1}^n \sigma_{ab} \cdot \Expect{}{|\tE^{ab}|} \, \ge \, \Expect{}{|\det \tE|} \, \ge \, \sqrt{2/\pi} \cdot \left( \sum_{b=1}^n \sigma_{ab}^2 \cdot \Expect{}{|\tE^{ab}|}^2 \right)^{1/2} .$$ } \medskip \noindent {\bf Proof:} The expansion of the determinant by minors along row $a$ is $$\det \tE = \sum_{b=1}^n (-1)^{a+b} \tepsilon_{ab}\tE^{ab}.$$ For any numbers $E^{a1},\ldots,E^{an}$, elementary properties of Gaussian random variables imply that $\sum_{b=1}^n (-1)^{a+b} \tepsilon_{ab}E^{ab}$ is a normally distributed random variable with mean 0 and variance $\sum_{b=1}^n \sigma_{ab}^2 (\tE^{ab})^2.$ Since $(\tepsilon_{a1},\ldots,\tepsilon_{an})$ and $(\tE^{a1},\ldots,\tE^{an})$ are statistically independent, Fubini's theorem and (\MeanNorm) in the case $m = 1$ yield $$\Expect{}{|\det \tE|} = { \sqrt{2} \over \Gamma({1 \over 2}) } {\bf E}\Bigg(\sqrt{ \sum_{b=1}^n \sigma_{ab}^2 (\tE^{ab})^2 } \,\,\Bigg).$$ Recalling that $\Gamma({1 \over 2}) = \sqrt{\pi}$, the claim follows from Lemma \UpperLowerExpectedNormBounds. \endproof Let $\Sigma_1$ be the $n \times n$ matrix with entries $\sigma_{ab}$, and let $\Sigma_2$ be the $n \times n$ matrix with entries $\sigma^2_{ab}$. By an induction on $n$ we now have: \medskip \noindent {\bf Corollary:} {\sl $$ (2/\pi)^{n/2} \cdot \per \, \Sigma_1 \ge \Expect{}{ | \det \tE | } \ge (2/\pi)^{n/2} \cdot \sqrt{\per \, \Sigma_2 } .$$ } The upper and lower bounds in Lemma \UpperLowerExpectedNormBounds\ correspond to the extreme cases in which the distribution of $\tx$ is concentrated on the coordinate axes or on the ray through $\Expect{}{\tx}$. When the distribution of $\tx$ 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(\Re^{n_1}) \times \ldots \times SO(\Re^{n_k})$$ acts on the space of $n \times n$ matrices $Z$ by simultaneously acting on each row of $Z$, where each row is viewed as an element of $\Re^{n_1} \times \ldots \times \Re^{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(\eta Z) = \det Z$ for all $\eta \in H$ and all $n \times n$ matrices $Z$. Let $Z^i_{jh}$ denote the determinant of the $(n-1) \times (n-1)$ minor obtained from $Z$ by eliminating row $i$ and column $jh$. Define the function $c_i$ from the space of $n \times n$ matrices to $\Re^n$ by letting $c_i(Z)$ be the vector with components $c_i^{jh}(Z) = (-1)^{i + n_1 + \ldots + n_{j-1} + h}Z^i_{jh}$. (Of course $c_i(Z)$ is independent of the $i^{\rm th}$ row of $Z$, and is called the {\it cross product\/} (cf.~[Spi65], pp. 84-5) of the remaining $n-1$ rows.) \medskip \MMLemma{$c_i$ is equivariant: $c_i(\eta Z) = \eta c_i(Z)$ for all $n \times n$ matrices $Z$ and all $\eta \in H$.} \medskip \noindent {\bf Proof:} Let $Z_i$ denote the $i^{\rm th}$ row of $Z$. Then for any $\eta \in H$ we have $$Z_i \cdot c_i(Z) = \det Z = \det(\eta Z) = \eta Z_i \cdot c_i(\eta Z).$$ Since $c_i(Z)$ and $c_i(\eta Z)$ are independent of $Z_i$, and this holds for all $Z_i$, it must be the case that $c_i(\eta Z) = \eta c_i(Z)$ for all $n \times n$ matrices $Z$ and all $\eta \in H$. \endproof \medskip \noindent {\bf Proof of \InTermsOfZ:} As in the last proof, we write $\det(\tZ) = \tZ_i \cdot c_i(\tZ)$. As in the proof of Proposition \ExpansionByMinors, elementary properties of normal random variables and Fubini's theorem imply that $$\eqalign{ \Expect{}{|\det \tZ|} & = {\sqrt{2} \cdot \Gamma(1) \over \Gamma({1 \over 2})} {\bf E}\Bigg(\sqrt{\sum_{j=1}^k\sum_{h=1}^{n_j} \delta_{ij} \cdot (\tZ_{jh}^i)^2}\,\,\Bigg) \cr }$$ $$= {\sqrt{2} \cdot \Gamma(1) \over \Gamma({1 \over 2})} {\bf E}\Bigg(\sqrt{\sum_{j=1}^k \delta_{ij} \cdot \|\txi_{ij}\|^2}\,\,\Bigg).$$ Combining this with Lemma \UpperLowerExpectedNormBounds\ yields $$ {\sqrt{2} \cdot \Gamma(1) \over \Gamma({1 \over 2}) }\sum_{j=1}^k \sqrt{\delta_{ij}} \Expect{}{\|\txi_{ij}\|} \, \ge \, \Expect{}{|\det \tZ|} \, \ge \, {\sqrt{2} \cdot \Gamma(1) \over \Gamma({1 \over 2}) }\sqrt{\sum_{j=1}^k \delta_{ij} \Expect{}{\|\txi_{ij}\|}^2}. \myeqno \eqlabel{\BigInequality}$$ For $j = 1, \ldots, k$ let $\Pi_j : \Re^n \to \Re^{n_j}$ be the projection $$\Pi_j(z^{11}, \ldots, z^{1n_1}, \,\, \ldots \,\, ,z^{k1}, \ldots, z^{kn_k}) = (z^{j1}, \ldots, z^{jn_j}).$$ Clearly $\Pi_j$ is equivariant: $\Pi_j(\eta z) = \eta_j(\Pi_j(z))$ for all $z \in \Re^n$ and $\eta = (\eta_1, \ldots, \eta_k) \in H$. Therefore $\Pi_j \circ c_i$ is equivariant. By virtue of elementary properties of the multivariate normal, the distribution of the random matrix $\tZ$ on the space of $n \times n$ matrices is invariant under the action of $H$, so the distribution of $\txi_{ij} = \Pi_j(c_i(\tZ))$ is invariant under the action of $SO(\Re^{n_j})$. If $\tx$ is any $\Re^{n_j}$--valued random variable whose distribution is invariant under the action of $O(\Re^{n_j})$, the ratio $\Expect{}{|\tx_h|}/\Expect{}{\|\tx\|}$ must agree with the mean absolute value of the first component of a random vector that is uniformly distributed on the unit sphere in $\Re^{n_j}$. In particular, by Lemma \MeanNormLemma\ we have $${\Expect{}{\|\txi_{ij}\|} \over \Expect{}{\|\tZ_i^{j1}\|}} = {\Expect{}{\|\tepsilon\|} \over \Expect{}{|\tepsilon_1|}} = {\Gamma({n_j+1 \over 2}) / \Gamma({n_j \over 2}) \over \Gamma(1) / \Gamma({1 \over 2})}$$ when $\tepsilon = (\tepsilon_1, \ldots, \tepsilon_{n_j})$ and $\tepsilon_1, \ldots, \tepsilon_{n_j}$ are i.i.d.~normal random variables with mean zero. The asserted inequality follows from substituing this into (\BigInequality). With respect to conditions under which the inequalities hold strictly, if the vector $(\|\txi_{i1}\|,\ldots, \|\txi_{ik}\|)$ has two components that are nonzero with positive probability, then both inequalities in (\BigInequality) hold strictly, by Lemma \UpperLowerExpectedNormBounds, and otherwise they do not. \endproof \vskip .1cm \goodbreak \medskip \Section{A Reformulation} \medskip 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 \subset \cH_i$ be the unit sphere defined by $\langle \cdot, \cdot \rangle_i$, and let $$M := M_1 \times \ldots \times M_n.$$ As a submanifold of $\cH$, $M$ inherits a measure corresponding to the intuitive notion of volume which we denote by $\vol(\cdot)$ or (when no confusion is possible) $M$. The {\it uniform distribution\/} on $M$ is $\bU_M(\cdot) := \vol(\cdot)/\vol(M)$. The analogous notation will occur in connection with other manifolds as well. The roots of $f \in \cH$ depend only on $(f_1 / \|f_1\|, \ldots, f_n / \|f_n\|),$ and the random system $(\tf_1 / \|\tf_1\|, \ldots,\tf_n / \|\tf_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 $[\zeta_j] = \{\zeta_j,-\zeta_j\}$ of antipodal points in $N_j$, where $N_j$ is the unit sphere in $\Re^{n_j + 1}$. Let $$N := N_1 \times \ldots \times N_k.$$ For each root $[\zeta] \in P$ of $f \in \cH$ there are $2^k$ corresponding roots in $N$. For each $i$ let $\theta_i : N \to \cH_i$ be the function with components $\theta_{ia}(\zeta) := \eta(a)^{-1}\zeta^a$. Let $F : M \times N \to \Re^n$ be the evaluation map with components $$F_i(f,\zeta) := f_i(\zeta) = \langle f_i, \theta_i(\zeta) \rangle_i.$$ The {\it incidence variety\/} is $V = F^{-1}(0)$. Let $\pi_1$ and $\pi_2$ be the projections from $V$ to $M$ and $N$ respectively. We now have $$\IndexGoal = 2^{-k} \int_M \#(\pi_1^{-1}(f)) \, d\bU_M. \myeqno \eqlabel{\TwoTok} $$ In preparation for the result of the next section we discuss some technical matters. \medskip \MMLemma{ Each $\theta_i$ is equivariant with respect to the actions of $G$ on $N$ and $\cH_i$: $\theta_i(O\zeta) = O\theta_i(\zeta)$ for all $\zeta \in N$ and $O \in G$. The image of $\theta_i$ is contained in the unit sphere of $\cH_i$.} \medskip \noindent {\bf Proof:} We have $$\langle Of_i, O\theta_i(\zeta) \rangle_i = \langle f_i, \theta_i(\zeta) \rangle_i = f_i(\zeta) = f_i(O^{-1}(O\zeta)) = \langle Of_i, \theta_i(O\zeta) \rangle_i.$$ Here the first equality is the invariance established in Lemma \UniqueInvariance, and the other three equalities are essentially matters of definition. For given $\zeta$ this holds for all $f_i$, so $\theta_i(O\zeta) = O\theta_i(\zeta)$. Consequently $\|\theta_i(O\zeta)\| = \|\theta_i(\zeta)\|$ for all $\zeta$ and $O$. Clearly $\theta_i(\zeta)$ is a standard basis vector of $\cH_i$ if $\zeta_1,\ldots,\zeta_k$ are all standard basis vectors in $\Re^{n_1 + 1}, \ldots, \Re^{n_k + 1}$ respectively, so the second claim follows from the fact that the action of $G$ on $N$ is transitive. \endproof \medskip The equation $f_i(\zeta) = 0$ means precisely that $f_i$ and $\theta_i(\zeta)$ are orthogonal, so for $(f,\zeta) \in V$ we may construe $\theta_i(\zeta)$ as a tangent vector in $T_{f_i}M_i$, and clearly $${\partial F_{i} \over \partial f}(f,\zeta)(0,\ldots,\theta_{i'}(\zeta), \ldots, 0)$$ is nonzero according to whether $i' = i$. Thus $(f,\zeta)$ is a regular point of $F$, and $0$ is a regular value of $F$, so the regular value theorem (e.g., [GP65]) implies: \medskip \MMLemma{ $V$ is a $C^{\infty}$ submanifold of $M \times N$ with $\dim V = \dim M$. } \medskip \def\hV{{V}} Abusing notation, we let $V_{\zeta}$ denote both of the ``fibers'' $$\pi_2^{-1}(\zeta) \subset V \subset M \times N \quad \hbox{and } \quad \{\, f \in M : (f,\zeta) \in \pi_2^{-1}(\zeta) \,\}$$ over a point $\zeta \in N$, with the appropriate interpretation to be inferred from context. For each $i$ let $\hV_{\zeta,i}$ be the set of $f_i \in M_i$ with $f_i(\zeta) = 0$. As the intersection of $M_i$ with a hyperplane, this set is a subsphere of $M_i$ of codimension one. Thus $\hV_{\zeta} = \hV_{\zeta,1} \times \ldots \times \hV_{\zeta,n}$ has a simple topology that is independent of $\zeta$, and, as one might expect: \medskip \MMLemma{ $\pi_2 : V \to N$ is a $C^{\infty}$ fibration. } \medskip 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\note{This terminology, and the definition of ``fibration'' we are appealing to, are from [Ste51, \S2].} is given by the following maps: given $\zeta_0 \in N$, a neighborhood $W \subset N$ of $\zeta_0$, and a $C^{\infty}$ map $h : W \to G$ satisfying $h(\zeta)\zeta_0 = \zeta$ for all $\zeta \in W$, let $\phi: \hV_{\zeta_0} \times W \to \pi_2^{-1} (W)$ be given by $\phi \big ( f, \zeta \big ) := \big (h (\zeta) f, \zeta \big )$. \vskip .1cm \goodbreak \medskip \Section{An Integral Formula} \medskip Sard's theorem implies that almost all points of $M$ are regular values of $\pi_1$, so we need only consider such points in computing the average number of roots. Consider a regular point $(f,\zeta) $ of $\pi_1$. Since $T_{(f,\zeta)}V$ is mapped surjectively onto $T_fM$ by $D\pi_1(f,\zeta)$, the restriction of $DF(f,\zeta)$ to $T_{\zeta}N \subset T_{(f,\zeta)}(M \times N)$ must be nonsingular, else $(f,\zeta)$ would not be a regular point of $F$. The implicit function theorem implies that there is a neighborhood $U \subset M$ of $f$ for which there is a smooth $G : U \to N$ with $G(f) = \zeta$ whose graph is contained in $V$. The {\it condition matrix\/} at $(f,\zeta)$ is the matrix of $DG(f)$ which, by the implicit function theorem, is $$C(f,\zeta) := - \Bigl( { \partial F \over \partial \zeta}(f,\zeta) \Bigr)^{-1}{\partial F \over \partial f}(f,\zeta) : T_fM \to T_{\zeta}N.$$ This linear transformation gives a description of the way polynomial systems $f$ are associated with roots near $(f,\zeta)$. Let $C^*(f,\zeta) : T_{\zeta}N \to T_fM$ be the adjoint of $C(f,\zeta)$. \medskip \noindent \MMProp {{\rm ([BCS98, p.~240])} \sl For any open $U \subset V$, $$\int_M \#(\pi_1^{-1}(f) \cap U)\,dM = \int_N \int_{V_y \cap U} \det\bigl(C(f,\zeta) C^*(f,\zeta)\bigr)^{-1/2} dV_{\zeta}dN.$$} \medskip \MMLemma{ If $(f,\zeta) \in V$ is a regular point of $\pi_1$, then $$\det\big(C(f,\zeta)C^*(f,\zeta)\big)^{-1/2} = |\det Df(\zeta)|. $$ } \medskip \noindent {\bf Proof:} For $v \in T_0\Re^n$ and $\phi \in T_fM = T_{f_1}M_1 \times \ldots \times T_{f_n}M_n$ we compute that $$\eqalign{ \Bigl\langle {\partial F \over \partial f} (f,\zeta)\phi, v \Bigr\rangle & = \Bigl\langle \bigl(\langle \phi_1, \theta_1(\zeta) \rangle_1,\ldots, \langle \phi_n, \theta_n(\zeta) \rangle_n\bigr), v \Bigr\rangle \cr & = \sum_{i=1}^n \langle \phi_i, v_i\theta_i(\zeta) \rangle_i = \Bigl\langle \phi, \bigl(v_1\theta_1(\zeta),\ldots,v_n\theta_n(\zeta)\bigr) \Bigr\rangle. \cr }$$ This means precisely that the map $v \mapsto (v_1\theta_1(\zeta),\ldots,v_n\theta_n(\zeta))$ is the adjoint ${\partial F \over \partial f}(f,\zeta)^*$ of ${\partial F \over \partial f}(f,\zeta)$, and in particular ${\partial F \over \partial f}(f,\zeta) {\partial F \over \partial f}(f,\zeta)^*$ is the identity on $T_0\Re^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 $$\eqalign{ \det\big(C(f,\zeta)C^*(f, & \zeta)\big)^{-1/2} = \Biggl(\det\Bigl( { \partial F \over \partial \zeta}(f,\zeta)^{-1} \bigl( { \partial F \over \partial \zeta}(f,\zeta) ^{-1} \bigr)^* \Bigr) \Biggr)^{-1/2}\cr & = \bigl|\det { \partial F \over \partial \zeta}(f,\zeta)\bigr| = |\det Df(\zeta)|. \enspace \bull \cr }$$ \medskip Combining the last two results, for any open $U \subset V$ we have $$\int_{f \in \pi_1(U)} \#(\pi_1^{-1}(f)) \, dM= \int_N \int_{V_{\zeta} \cap U} |\det Df(\zeta)| \,\,dV_{\zeta}dN. \myeqno \eqlabel{\ToDf}$$ \vskip .1cm \goodbreak \medskip \Section{Invariance} \medskip Combining the actions of $G$ on the various $\cH_i$ (recall Section 3) we obtain an action of $G$ on $\cH$ given by $$Of := (f_1 \circ O^{-1}, \ldots, f_n \circ 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 $\cH_i$, of course, so $M$ is an invariant of the action of $G$ on $\cH$, 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 $\prod_{j=1}^k \Re^{n_j+1}$. Combining these actions, we derive an action of $G$ on $M \times N$ given by $O(f,\zeta) := (Of,O\zeta)$. For any $O \in G$, $f \in M$, and $\zeta \in N$ we have $Of(O\zeta) = f \circ O^{-1}(O\zeta) = f(\zeta)$, so: \medskip \MMLemma{ $V$ is an invariant of the action of $G$ on $M \times N$: $OV = V$ for all $O \in G$. Consequently (for either interpretation of the symbol $V_{\zeta}$) $O(V_{\zeta}) = V_{O\zeta}$ for all $\zeta$ and $O$. } \medskip \noindent \MMProp{ The quantity $\int_{\hV_{\zeta}} |\det Df(\zeta)| \, dV_{\zeta}$ is independent of $\zeta$. } \medskip \noindent {\bf Proof:} Observe that $$D(Of)(O\zeta) = D(f \circ O^{-1})(O\zeta) = Df(\zeta) \circ O^{-1}$$ so that $ |\det D(Of)(O\zeta)| = |\det Df(\zeta)|.$ We now have the calculation that $$\int_{\hV_{O\zeta}} |\det Df(O\zeta)| \, d\hV_{O\zeta} = \int_{\hV_{\zeta}} |\det D(Of)(O\zeta)| \, d\hV_{\zeta} = \int_{\hV_{\zeta}} |\det Df(\zeta)| \, d\hV_{\zeta}.$$ 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. \endproof Applying this to (\ToDf), for any open $W \subset N$ and any $\zeta \in N$ we have $$\int_{M}\#(\pi_1^{-1}(f) \cap \pi_2^{-1}(W)) \, dM = \vol(W) \cdot \int_{\hV_{\zeta}} |\det Df(\zeta)| \, d\hV_{\zeta}. \myeqno \eqlabel{\AfterInvariance}$$ Clearly (b) of Theorem 1 follows directly from this. The remaining task is to prove (a) of that result. %\medskip %\MMProp{ \label{\AfterInvariance} % For any open $W \subset N$ and any $\zeta \in N$, %$$\int_{M}\#(\pi_1^{-1}(f) \cap \pi_2^{-1}(W)) \, dM = \vol(W) %\cdot \int_{\hV_{\zeta}} |\det Df(\zeta)| \, d\hV_{\zeta}.$$ %} %\medskip %Clearly (b) of Theorem 1 follows directly from this. The remaining %task is to prove (a) of that result. %\endprop \vskip .1cm \goodbreak \medskip \Section{The Final Calculations} \medskip Fixing $\zeta \in N$, let $\tf_{\zeta} = (\tf_{\zeta,1}, \ldots, \tf_{\zeta,n})$ be the orthogonal projection of $\tf$ onto the subspace of polynomial systems for which $\zeta$ is a root. For each $i$, $\|\tf_{\zeta,i}\|$ and $\tf_{\zeta,i}/\|\tf_{\zeta,i}\|$ are statistically independent, and the normalized vector is uniformly distributed in $V_{\zeta,i}$, so $$\eqalign{ \int_{\cH} |\det D\tf_{\zeta}(\zeta)| \, d\mu & = \int_{\cH} \Gbig(\prod_{i=1}^n \|\tf_{\zeta,i}\|\Gbig) \cdot \Big|\det D\Big({ \tf_{\zeta,1} \over \|\tf_{\zeta,1}\| }, \ldots, { \tf_{\zeta,n} \over \|\tf_{\zeta,n}\| }\Big) (\zeta)\Big| \, d\mu \cr & = \Gbig( \prod_{i=1}^n \Expect{}{\|\tf_{\zeta,i}\|} \Gbig) \int_{\hV_{\zeta}} |\det Df(\zeta)| \, d\bU_{\hV_{\zeta}}. \cr }$$ Combining this with (\TwoTok) and (\AfterInvariance), we now obtain $$E(\bn,\delta) = 2^{-k}{ \vol(N) \cdot \vol(V_{\zeta}) \over \vol(M) \cdot \prod_{i=1}^n \Expect{}{\|\tf_{\zeta,i}\|} } \int_{\cH} |\det D\tf_{\zeta}(\zeta)| \, d\mu.$$ The formula (\SphereVolume) for sphere volume gives $$\vol(N_j) = 2{ \Gamma({1 \over 2})^{n_j + 1} \over \Gamma({n_j +1 \over 2}) }, \quad \vol(M_i) = 2{ \Gamma({1 \over 2})^{\dim \cH_i} \over \Gamma({\dim \cH_i \over 2}) }, \quad \vol(V_{\zeta,i}) = 2{ \Gamma({1 \over 2})^{\dim \cH_i - 1} \over \Gamma({\dim \cH_i - 1 \over 2}) },$$ and Lemma \MeanNormLemma\ yields $$\Expect{}{\|\tf_{\zeta,i}\|} = { \sqrt{2} \cdot \Gamma({\dim \cH_i \over 2}) \over \Gamma({\dim \cH_i - 1 \over 2}) }.$$ Since $\vol(M) = \vol(M_1) \times \ldots \times \vol(M_n)$, and similarly for $N$ and $V_{\zeta}$, we now have $$\IndexGoal = 2^{-n/2} \cdot \Gbigl( \prod_{j = 1}^k { \Gamma({1 \over 2}) \over \Gamma({n_j + 1 \over 2}) } \Gbigr) \cdot \int_{\cH} |\det D\tf_{\zeta}(\zeta)| \, d\mu. \myeqno \eqlabel{\NextToLast}$$ In the further evaluation of this quantity we are free to let $\zeta$ be any convenient point in $N$. We will compute at $\zeta_0 = (\be_{10}, \ldots, \be_{k0}) \in N$ where, for $1 \le j \le k$, $\be_{j0}, \be_{j1}, \ldots, \be_{jn_j}$ are the standard unit basis vectors of $\Re^{n_j + 1}$. For each $i$ and $j$ let $a^0_{ij} = (\delta_{ij},0,\ldots,0) \in \cA_{ij}$, and for each $i$ let $a_i^0 = (a^0_{i1}, \ldots, a^0_{ik}) \in \cA_i$. Since $\zeta_0^a = 0$ for all $a \in \cA_i$ other than $a^0_i$, and $\zeta_0^{a^0_i} = 1$, for each $i$ $ \hV_{\zeta_0,i} := \{\, f_i \in M_i : f_{ia_i^0} = 0 \,\}.$ For $i$ and $j$ such that $\delta_{ij} > 0$ and each $h = 1, \ldots, n_j$, let $a^{jh}_i$ be $a^0_i$ with $a^0_{ij}$ replaced by $(\delta_{ij} - 1, 0,\ldots,0,1,0,\ldots,0)$ (the `1' is component $h$). Then $T_{\zeta_0}N$ is spanned by the $n$ vectors $${\bf b}_{jh} := (0, \ldots, \be_{jh}, \ldots,0) \qquad (1 \le j \le k, 1 \le h \le n_j),$$ and elementary calculus yields $$D\tf_{\zeta_0,i}(\zeta_0){\bf b}_{jh} = \cases{ \tf_{ia_i^{jh}} & if $\delta_{ij} > 0$, \cr 0 & if $\delta_{ij} = 0$. \cr}$$ In this way we obtain a description of $D\tf_{\zeta_0}(\zeta_0)$ as an $n \times n$ matrix with rows indexed by $f_1,\ldots, f_n$, columns indexed by the pairs $(j,h)$, and this $(i,jh)$--entry. Recalling from Section 3 that the variance of $ \tf_{ia_i^{jh}}$ is $\delta_{ij}$, we see that the matrix of $D\tf_{\zeta_0}(\zeta_0)$ has the same distribution as $\tZ$. In view of (\NextToLast) this observation completes the proof of Theorem 1. \bigskip \vfill \eject \goodbreak % \vfill \eject % \newcount\bibnumber % \def\bibitem{\global\advance\bibnumber by 1 % \hangindent=36pt \the\bibnumber. } % \def\bibitem{\global\advance\bibnumber by 1 % \itemitem{\the\bibnumber.}} \newcount\bibnumber \def\bibitem#1#2{\smallskip \hangindent=36pt $\hbox to 1.4cm{#1 \hfil}$#2} \bibnumber = 0 \parindent=0pt \centerline{\bf References} \medskip \bibitem{[Ber75]} {D.~N.~Bernshtein, The number of roots of a system of equations, {\it Functional Analysis and its Applications} {\bf 9} (1975), 183--185.} \bibitem{[BCS93]} { L.~Blum, F.~Cucker, M.~Shub, and S.~Smale, {\it Complexity and Real Computation\/}, Springer-Verlag, New York, (1998).} \bibitem{[BP32]} {A.~Bloch and G.~P\'olya, On the roots of a certain algebraic equation, {\it Proc.~London Math.~Soc\/}.~ {\bf 33} (1932), 102--114.} %\bibitem{[CS61]} {R.~D.~Carmichael and E.~R.~Smith, {\it Mathematical %Tables and Formulas\/}, Dover, New York, (1961).} %\bibitem{[CE95]} {J.~F.~Canny and I.~Emiris, Efficient Incremental %Algorithms for the Sparse Resultant and the Mixed Volume, %{\it Journal of Symbolic Computation\/} {\bf 20} (1995), 117--149.} %\bibitem{[Dre]} {M.~Dresher, Probability of a pure equilibrium %point in $n$-person games, {\it Journal of Combinatorial Theory\/} %{\bf 8} (1970), 134--145.} \bibitem{[EK95]} {A.~Edelman and E.~Kostlan, How many zeros of a random polynomial are real?, {\it Bulletin of the American Mathematical Society\/} {\bf 32} (1995), 1--37.} \bibitem{[Ego96]} {G.~P.~Egorychev, Van der Waerden conjecture and applications, {\it Handbook of Algebra\/}, Vol.~I, Elsevier, Amsterdam (1996), 3--26.} \bibitem{[Ewa96]} {G.~Ewald, {\it Combinatorial Convexity and Algebraic Geometry\/}, \break Springer, New York, (1996).} \bibitem{[Fed69]} {H.~Federer, {\it Geometric Measure Theory\/}, Springer, New York, (1969).} \bibitem{[FT91]} {D.~Fudenberg and J.~Tirole, {\it Game Theory\/}, MIT Press, Cambridge, (1991).} \bibitem{[Gir90]} {V.L.~Girko, {\it The Theory of Random Determinants\/}, Kluwer, \break Boston, (1990).} \bibitem{[GP65]} {V.~Guillemin and A.~Pollack, {\it Differential$\!$ Topology\/}, Prentice-Hall, Englewood Cliffs, (1965).} % \bibitem{[GPS]}{F.~Gul, D.~Pearce, and E.~Stachetti, A % bound on the proportion of pure strategy equilibria in generic % games, {\it Mathematics of Operations Research\/} {\bf 18} (1993), 548-- % 552.} %\bibitem J.~C.~Harsanyi, Oddness of the number %of equilibrium points: a new proof, {\it Int.~J.~Game Theory}, {\bf %2} (1973), 235--250. \bibitem{[Kac43]} {M.~Kac, On the average number of real roots of a random algebraic equation, {\it Bulletin of the American Mathematical Society\/} {\bf 49} (1943), 314--320 and 938.} %\bibitem H.~Keiding, On the maximal number of Nash equilibria %in a bimatrix game. Forthcoming in {\it Games and Economic %Behavior}. \bibitem{[Kho78]} {A.~G.~Khovanskii, Newton polyhedra and the genus of complete intersections, {\it Functional Analysis and its Applications} {\bf 12} (1978), 51--61.} %\bibitem E.~Kohlberg and J.-F.~Mertens, On the strategic %stability of equilibria, {\it Econometrica\/} {\bf 54} (1986), %1003--1038. \bibitem{[Kos93]} E.~Kostlan, On the distribution of roots of random polynomials, {\it From Topology to Computation: Proceedings of the Smalefest\/}, Hirsch, M., Marsden, J., and Shub, M. (eds) (1993). %\bibitem H.~Kuhn, et.~al., The work of John Nash in game %theory: Nobel seminar, December 8, 1994, {\it Journal of Economic %Theory\/} {\bf 69} (1996), 153--185. \bibitem{[Kus75]} {A.~G.~Kushnirenko, The Newton polyhedron and the number of solution of a system of $k$ equations in $k$ unknowns, {\it Upsekhi Mat. Nauk.} {\bf 30} (1975), 266--267.} \bibitem{[MM97]} {R.~D.~McKelvey and A.~McLennan, The maximal number of regular totally mixed Nash equilibria, {\it Journal of Economic Theory} {\bf 72} (1997), 411--425.} %\bibitem A.~McLennan, The %maximal generic number of pure Nash equilibria, {\it Journal of %Economic Theory} {\bf 72} (1997a), 408--410.} \bibitem{[McL97]} {A.~McLennan, On the Expected Number of Nash Equilibria of a Normal Form Game, mimeo, University of Minnesota, (1997).} \bibitem{[McL98]} {A.~McLennan, The maximal number of real roots of a multihomogeneous system of polynomial equations, forthcoming in {\it Beitr\"age zur Algebra und Geometrie\/}, (1998).} %\bibitem A.~McLennan and I.-U.~Park, Generic 4x4 games have at %most 15 Nash equilibria, Discussion Paper 300, Center for Economic %Research, University of Minnesota, (1997). \bibitem{[Meh91]} M.L.~Mehta, {\it Random Matrices}, Academic Press, New York \break (1991). \bibitem{[Mui82]} R.J.~Muirhead, {\it Aspects $\!$of$\!$ Multivariate Statistical Theory}, Wiley, New York (1982). % \bibitem F.~Morgan, {\it Geometric Measure Theory: a Beginner's % Guide}, Academic Press, New York (1988). %\bibitem J.~Nash, ``Non-cooperative games,'' %Ph.D.~Thesis, Mathematics Department, Princeton University, (1950). %\bibitem J.~Nash, Non-cooperative games, %{\it Annals of Mathematics\/} {\bf 54} (1951), 286--295. %\bibitem M.~Okuno-Fujiwara and A.~Postlewaite, Social Norms %and Random Matching Games, {\it Games and Economic Behavior\/} {\bf 9} %(1995), 79--109. %\bibitem I.~Powers, Limiting distributions of the number of %pure strategy Nash equilibria, {\it International Journal of Game %Theory\/} {\bf 19} (1990), 277--286. %\bibitem T.~Quint and M.~Shubik, A theorem on the number of %Nash equilibria in a bimatrix game, {\it International Journal of Game %Theory\/} {\bf 26} (1997), 353--360. \bibitem{[Roj96]} {J.~M.~Rojas, On the average number of real roots of certain random sparse polynomial systems, {\it Lectures on Applied Mathematics Series\/}, ed. by J.~Renegar, M.~Shub, and S.~Smale, American Mathematical Society, (1996).} \bibitem{[SS93]} {M.~Shub and S.~Smale, Complexity of Bezout's theorem II: volumes and probabilities, {\it Computational Algebraic Geometry\/} (F. Eyssette and A.~Galligo, eds.), Progr.~Math., vol.~109 (1993), Birkhauser, Boston, 267--285.} \bibitem{[Spi65]} {M.~Spivak, {\it Calculus on Manifolds : a Modern Approach to Classical Theorems of Advanced Calculus\/}, Benjamin, New York, (1965). } %\bibitem M.~Spivak, {\it A Comprehensive Introduction to %Differential Geometry. Volume 1.\/}, 2nd ed., Publish or Perish, %(1979). %\bibitem W.~Stanford, The Poisson distribution and %probability of $k$ pure equilibria in matrix games, mimeo, Department of %Economics, University of Illinois at Chicago, (1993). % \bibitem W.~Stanford, The limit distribution of the % number of pure equilibria in symmetric bimatrix games, mimeo, % Department of Economics, University of Illinois at Chicago, (1994). \bibitem{[Ste51]} {N.~Steenrod, {\it The Topology of Fibre Bundles\/}, Princeton University Press, Princeton (1951).} \bigskip \baselineskip10pt \bigskip \noindent {\smallsmc Andrew McLennan \hfill \break \noindent Department of Economics \hfill\break \noindent University of Minnesota\hfill\break \noindent 271 19th Ave. S.\hfill\break \noindent Minneapolis, MN 55455, USA\hfill \break \noindent \par} \noindent {\tt mclennan@atlas.socsci.umn.edu} \hfill \break \noindent {\tt http://www.econ.umn.edu/{\char'176}mclennan} \end