On the Number of Real Zeros of Random Fewnomials

Peter Bürgisser, Alperen Ali Ergür, Josué Tonelli-CuetoSIAM J. Appl. Algebra Geom 2019 · DOI

TL;DR

This paper tackles the problem of bounding the number of positive real solutions to systems of random polynomial equations. The authors prove that for a system of $n$ random polynomials, each with $t$ terms, the expected number of positive real solutions is bounded by $2 \cdot (\frac{1}{2^{n-1}})^t$. This result offers a probabilistic answer to a long-standing question in fewnomial theory and shows that for sparse random systems, the number of solutions tends to zero exponentially with the number of variables.

What Problem Does This Paper Address?

The paper investigates the number of real solutions to systems of polynomial equations, a fundamental problem in algebraic geometry with applications in various scientific fields. Specifically, it focuses on "fewnomials," which are polynomials with a limited number of terms. A key question in this area, known as Question 1.1, asks whether the number of non-degenerate positive solutions to a system of $n$ polynomial equations in $n$ variables, each with at most $t$ terms, can be bounded by a polynomial in $t$ (for a fixed $n$). This is a challenging deterministic problem, and current bounds are exponential in $t$.

The authors propose to tackle this question by considering random sparse polynomial systems. They aim to provide a probabilistic analogue of this question, asking about the expected number of solutions. This approach is motivated by prior work on probabilistic versions of Bézout's theorem and the desire to understand the behavior of solutions in a random setting, which can sometimes offer insights into the deterministic case.

Methods

The core of the paper's methodology lies in connecting the expected number of zeros to an integral over a manifold. They leverage a result from integral geometry (Proposition 2.1) and a specific integral formula for the expected number of zeros of random smooth functions (Theorem 2.2). This formula expresses the expectation as an integral of the square root of the determinant of a matrix involving the derivatives of a normalized version of the polynomial system.

The authors then specialize this formula to random sparse polynomial systems. A crucial step involves using the Cauchy-Binet formula to decompose the determinant under the integral into a sum of squares of determinants of smaller matrices. This decomposition, combined with a clever application of a deterministic result on the number of roots of a specific type of random polynomial (Proposition 3.1), allows them to derive the bound. Proposition 3.1 itself relies on Descartes' rule of signs for univariate polynomials and a lemma (Lemma 3.2) that bounds the number of non-degenerate positive solutions of a system involving square roots.

Datasets

Not discussed in the paper. The paper deals with theoretical results on random polynomial systems, not empirical evaluation on datasets.

Key Insights and Ideas

  • Probabilistic Approach to a Deterministic Problem: The paper demonstrates that by considering random systems, one can obtain strong bounds on the expected number of solutions, offering a new perspective on the challenging fewnomial problem.
  • Exponential Decay of Solutions: The main result shows that for random sparse systems, the expected number of positive real solutions decreases exponentially with the number of variables ($n$). This suggests that random sparse systems are "unlikely" to have many solutions.
  • Connection to Integral Geometry: The proof elegantly uses tools from integral geometry, specifically relating the expected number of zeros to the volume of a manifold and an integral over it.
  • Decomposition via Cauchy-Binet: The use of the Cauchy-Binet formula to break down the determinant under the integral is a key technical innovation that enables the application of simpler probabilistic results.
  • Special Case for Univariate Polynomials: The paper also presents a tighter bound for the univariate case ($n=1$), showing that the expected number of zeros is bounded by $\sqrt{t} \log t$, which is an improvement over the general bound for $n=1$.

Key Results

The main quantitative result is Theorem 1.2: For a system of $n$ random polynomials, each with a common support $A \subseteq \mathbb{Z}^n$ of cardinality $t$, the expected number of non-degenerate positive real zeros is bounded by:

$E N(A, \sigma) < \frac{1}{2^{n-1}} \left(\frac{1}{2^{n-1}}\right)^t$

where $\sigma$ represents the variances of the Gaussian coefficients.

For the univariate case ($n=1$), Theorem 1.5 provides a tighter bound:

$E N(A, 1) \leq \sqrt{t} \log t$

Limitations and Future Work

  • Specific Randomness Model: The results are derived for a specific model of random polynomials: coefficients are independent Gaussian random variables with prescribed variances. The authors mention that their proof only requires the image of the coefficients to be uniformly distributed on the unit sphere, which is a generalization.
  • Common Support: The main result assumes that all polynomials in the system share the same set of exponent vectors (support $A$). A natural extension would be to consider systems where each polynomial can have a different support.
  • Positive Orthant: The bounds are for solutions in the positive orthant ($\mathbb{R}_+^n$). Extending this to other regions or to all real solutions would be a valuable direction.
  • Deterministic vs. Probabilistic: While the probabilistic result is strong, it doesn't directly solve the deterministic Question 1.1. However, the authors suggest that the combinatorial flavor of their proof might inspire new deterministic approaches.

Summary updated

BibTeX
@article{burgisser2019number,
  author = {Peter Bürgisser and Alperen Ali Ergür and Josué Tonelli-Cueto},
  title = {{On the Number of Real Zeros of Random Fewnomials}},
  journal = {SIAM J. Appl. Algebra Geom.},
  year = {2019},
  doi = {10.1137/18m1228682},
}
Figure