On the Number of Real Zeros of Random Sparse Polynomial Systems

Alperen A. Ergür, Máté L. Telek, Josué Tonelli-CuetoarXiv 2023 · DOI · arXiv

Abstract

Consider a random system $\mathfrak{f}_1(x)=0,\ldots,\mathfrak{f}_n(x)=0$ of $n$ random real polynomials in $n$ variables, where each $\mathfrak{f}_k$ has a prescribed set of exponent vectors in a set $A_k\subseteq \mathbb{Z}^n$ of size $t_k$. Assuming that the coefficients of the $\mathfrak{f}_k$ are independent Gaussian of any variance, we prove that the expected number of zeros of the random system in the positive orthant is bounded from above by $4^{-n} \prod_{k=1}^n t_k(t_k-1)$. This result is a probabilistic version of Kushnirenko's conjecture; it provides a bound that only depends on the number of terms and is independent of their degree.

Introduction

In computational mathematics and its diverse applications—ranging from robotics and computer vision to chemical reaction networks—solving systems of polynomial equations is a fundamental task. While the number of complex solutions to such systems is well-understood through the Bernstein-Khovanskii-Kushnirenko (BKK) bound, determining the number of real solutions remains a significant challenge in the field of real algebraic geometry.

A particularly intriguing subset of this problem involves "sparse" polynomial systems, often referred to as "fewnomials." These are systems where each polynomial consists of a relatively small number of terms (monomials), even if the degrees of those terms are extremely high. In 1977, Kushnirenko conjectured that the number of positive real zeros for such systems should be bounded by a function of the number of terms alone, independent of the degree. This deterministic conjecture has remained one of the most elusive problems in the field. This paper addresses the "average case" of this problem, providing a breakthrough upper bound on the expected number of real zeros for random sparse systems.

Methodology

The authors derive their results by integrating techniques from random field theory and discrete geometry. The proof strategy relies on four primary pillars:

  1. The Rice Formula: A cornerstone of random field theory, the Rice formula allows the authors to express the expected number of zeros as an integral over the domain. This integral involves the density of the random variables and the expected value of the absolute determinant of the system's Jacobian matrix.
  2. Cauchy-Binet Formula: To manage the complexity of the Jacobian determinant within the Rice formula, the authors apply the Cauchy-Binet formula. This decomposes the determinant into a sum of determinants of simpler $n \times n$ matrices, facilitating a more tractable analysis.
  3. Regular Mixed Subdivisions: The authors utilize the logarithms of the coefficient variances to induce a polyhedral subdivision of the space. This geometric approach allows them to partition $\mathbb{R}^n$ into cells where the behavior of the polynomial system is dominated by a specific subset of monomials.
  4. Reduction to Binomial Systems: By analyzing these cells, the problem of bounding a general random system is reduced to bounding "binomial" systems—systems where each equation consists of only two terms. This reduction is critical for establishing a bound that is independent of the specific exponents.

Notably, this methodology does not require the variances of the coefficients to be identical or follow a specific distribution (such as the Kostlan distribution), ensuring the results are highly generalizable across different Gaussian models.

Key Insights

Degree Independence

The most striking insight of this research is that the expected number of zeros is entirely independent of the exponents (the degrees) of the monomials. Whether the system involves $x^2$ or $x^{1,000,000}$, the average number of real zeros remains constant as long as the number of terms ($t_k$) is fixed. This provides a powerful probabilistic confirmation of the intuition behind Kushnirenko’s conjecture.

The Power of Sparsity

The derived bound, $4^{-n} \prod_{k=1}^n t_k(t_k-1)$, demonstrates that sparsity significantly restricts the expected number of real solutions. In contrast to "dense" systems where the number of solutions grows rapidly with the degree, sparse systems are constrained by their combinatorial structure.

The paper establishes a deep connection between the probability of a zero's existence and the geometry of mixed subdivisions. The expected number of zeros is intimately linked to the number of vertices in a specific Minkowski sum of polytopes, bridging the gap between algebraic geometry and discrete geometry.

Vanishing Zeros in Unmixed Systems

For "unmixed" systems—where every equation shares the same set of monomials—the authors show that if the number of terms $t$ is small relative to the number of variables $n$ (specifically $n+\ell$ terms), the probability of finding any positive real zero actually vanishes as $n$ increases.

Main Results

The paper establishes several key bounds for the expected number of positive real zeros:

  • General Sparse Systems: For a system of $n$ random polynomials in $n$ variables where the $k$-th polynomial has $t_k$ terms, the expected number of positive real zeros $E[N]$ satisfies: $$E[N] \le 4^{-n} \prod_{k=1}^n t_k(t_k-1)$$
  • Unmixed Systems: If all polynomials share the same $t$ terms, the bound is refined to: $$E[N] \le \frac{n+1}{4^n} \binom{t}{n+1}$$
  • Projective Varieties: The results extend to projective space, providing bounds on the average volume of random sparse varieties that remain independent of the degree.
  • Descartes' Rule of Signs: In the univariate case ($n=1$), the bound simplifies to $(t-1)/2$. This aligns perfectly with the average value suggested by the classical Descartes' Rule of Signs, providing a satisfying consistency with historical results.

Conclusion and Future Work

This work represents a major step forward in understanding the real roots of random polynomials. By proving a degree-independent bound, the authors provide a probabilistic solution to a long-standing open problem.

However, several avenues for future research remain. First, the current results provide upper bounds on the expectation; determining the exact average or the variance of the number of zeros remains an open question. Second, while the Gaussian assumption is flexible regarding variance, exploring non-Gaussian distributions (such as sparse or heavy-tailed coefficients) would further generalize the theory. Finally, the deterministic version of Kushnirenko’s conjecture remains one of the "holy grails" of real algebraic geometry, and it is yet to be seen if these probabilistic techniques can be adapted to solve the deterministic case.

Summary updated

Abstract

Consider a random system $\mathfrak{f}_1(x)=0,\ldots,\mathfrak{f}_n(x)=0$ of $n$ random real polynomials in $n$ variables, where each $\mathfrak{f}_k$ has a prescribed set of exponent vectors in a set $A_k\subseteq \mathbb{Z}^n$ of size $t_k$. Assuming that the coefficients of the $\mathfrak{f}_k$ are independent Gaussian of any variance, we prove that the expected number of zeros of the random system in the positive orthant is bounded from above by $4^{-n} \prod_{k=1}^n t_k(t_k-1)$. This result is a probabilisitc version of Kushnirenko's conjecture; it provides a bound that only depends on the number of terms and is independent of their degree.
BibTeX
@misc{ergur2023number,
  author = {Alperen A. Ergür and Máté L. Telek and Josué Tonelli-Cueto},
  title = {{On the Number of Real Zeros of Random Sparse Polynomial Systems}},
  year = {2023},
  eprint = {2306.06784},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.06784},
}

Loading related content...

Figure