Certified and exact algorithms for solving polynomial systems need lower bounds on how close two distinct isolated roots can be (root separation). Emiris, Mourrain, and Tsigaridas (J. Symbolic Comput. 101, 2020) established worst-case aggregate separation bounds — the multivariate Davenport–Mahler–Mignotte bound DMM_n — exploiting the sparsity of the system through Newton polytopes, mixed volume, and sparse resultant heights, and extended them to positive-dimensional systems via the toric generalized characteristic polynomial (TGCP). The paper itself states two open directions: (1) an average-case, i.e., probabilistic or distributional, version of DMM_n reflecting the fact that typical systems have few and well-separated roots, of which only the univariate case is understood; and (2) positive-dimensional separation and coordinate-magnitude bounds explicitly parametrized by the dimension of the excess (positive-dimensional) components. Both directions remain open: existing beyond-worst-case results cover univariate root isolation, and the closest positive-dimensional work bounds the reach of a variety, a different quantity that does not involve excess-component dimension.

Background

A polynomial system is a finite set of polynomial equations f1=⋯=fn=0f_1=\cdots=f_n=0 in nn variables; its roots are the points of its variety. Algorithms that solve or certify the roots exactly or numerically — subdivision-based real-root isolation, elimination solvers, algorithms for algebraic quantities such as eigenvalues — must be able to decide when two candidate roots are distinct, so they depend on a separation bound: a lower bound on the minimum Euclidean distance sep\mathrm{sep} between any two distinct isolated roots. For univariate polynomials, the classical Davenport–Mahler–Mignotte (DMM) theory gives aggregate bounds, i.e., amortized lower bounds on products of root-to-nearest-root distances Δj\Delta_j (rather than on sep\mathrm{sep} alone), obtained from discriminant-type quantities. Emiris, Mourrain, and Tsigaridas extended this to square systems (as many equations as variables) whose variety is zero-dimensional, i.e., consists of finitely many isolated points (Main Theorem 5, the bound they call DMM_n). Their bound exploits sparsity: the Newton polytope of a polynomial is the convex hull of the exponent vectors of its support, and the mixed volume of the Newton polytopes — the coefficient of λ1⋯λn\lambda_1\cdots\lambda_n in the Euclidean volume of the Minkowski sum λ1P1+⋯+λnPn\lambda_1 P_1+\cdots+\lambda_n P_n, which by Bernstein's theorem bounds the number of roots in the algebraic torus (C∗)n(\mathbb{C}^*)^n, i.e., in (C∖{0})n(\mathbb{C}\setminus\{0\})^n — replaces the total degree, while the coefficients enter through the (logarithmic) height, i.e., the logarithm of the largest coefficient magnitude, of the sparse (toric) resultant, a polynomial in the coefficients that vanishes exactly when the system has a root in the torus. A univariate elimination polynomial (a specialized uu-resultant, the resultant of the system augmented by a generic linear form) then reduces the multivariate question to the univariate DMM bound. This improves the classical gap theorem of Canny by a factor O(d n−1)O(d^{\,n-1}) in the maximum degree dd and yields, among other applications, bitsize bounds for eigenvalues of integer matrices and for the minimum of a positive polynomial over the standard simplex, as well as worst-case step bounds for subdivision-based root isolation. When the variety has positive-dimensional components (called excess components, because they make the naive resultant vanish identically), Canny's generalized characteristic polynomial (GCP) trick — perturbing the system by a parameter ss and taking the lowest nonzero coefficient in ss of the resultant — recovers information about the isolated roots; Emiris–Mourrain–Tsigaridas give its sparse version, the toric GCP (TGCP), and prove (Theorem 14) separation and coordinate-magnitude bounds for the isolated roots and their limit points, in terms of the mixed volume M0M_0, the root count, and resultant-height quantities. These bounds, however, do not involve the dimension of the excess components. The 2020 paper closes its introduction with two explicit open directions: 'it is challenging to derive an average-case DMM_n', since practical systems have few real roots and all roots are well separated on average, and 'another open question is to express the positive-dimensional bound with respect to the dimension of the excess component'.

Problem Statement

The problem consists of the two open directions stated by Emiris–Mourrain–Tsigaridas in 'Separation bounds for polynomial systems' (2020), which together extend the aggregate separation-bound framework beyond its current worst-case, zero-dimensional-strength limits:

(a) Average-case DMM_n. Construct a rigorous average-case (probabilistic or distributional) version of the multivariate aggregate separation bound DMM_n. This requires specifying a random model for polynomial systems that reflects their typical sparsity structure (supports / Newton polytopes, hence mixed volume) and a concrete coefficient distribution (for example integer coefficients of bounded bitsize, or a Gaussian model), and proving aggregate separation bounds for the isolated roots in (C∗)n(\mathbb{C}^*)^n — in expectation, or with explicit high-probability tail bounds — that quantitatively improve on the worst-case DMM_n and capture the empirical phenomenon that typical systems have few, well-separated roots. The model must be representative of typical inputs rather than reverse-engineered to make the bound hold trivially (for example, a degenerate ensemble concentrated on a single explicit well-separated system family does not qualify). The univariate case (an average-case DMM_1) is known; the multivariate case n≥2n\ge 2 is the open target.

(b) Excess-dimension-parametrized positive-dimensional bounds. The existing bounds for systems whose variety has positive-dimensional (excess) components — obtained through the toric generalized characteristic polynomial and controlling the isolated solutions and their limit points — are stated in terms of the mixed volume, the number of isolated roots, and sparse-resultant height quantities, but do not involve the dimension of the excess components. Derive separation and coordinate-magnitude bounds for the isolated roots of positive-dimensional systems that are explicitly parametrized by the dimension of the excess components (so the bounds quantitatively reflect how much of the ambient dimension is carried by the excess components).

Each of (a) and (b) is also a coherent standalone contribution. The common objective they serve is a separation-bound theory for polynomial-system solving that is as tight in the positive-dimensional setting as the zero-dimensional DMM_n is in the worst case, and realistic rather than pessimistic for typical inputs.

References

  1. Ioannis Emiris, Bernard Mourrain, Elias Tsigaridas. Separation bounds for polynomial systems. Journal of Symbolic Computation 101:128–151, 2020. DOI 10.1016/j.jsc.2019.07.001, https://doi.org/10.1016/j.jsc.2019.07.001
  2. Ioannis Z. Emiris, Bernard Mourrain, Elias P. Tsigaridas. The DMM bound: multivariate (aggregate) separation bounds. Proc. ISSAC 2010, pp. 243–250. DOI 10.1145/1837934.1837981, arXiv:1005.5610, https://arxiv.org/abs/1005.5610
  3. Ioannis Z. Emiris, André Galligo, Elias Tsigaridas. Random polynomials and expected complexity of bisection methods for real solving. Proc. ISSAC 2010, pp. 235–242. DOI 10.1145/1837934.1837980, arXiv:1005.2001, https://arxiv.org/abs/1005.2001
  4. Alperen A. Ergür, Josué Tonelli-Cueto, Elias Tsigaridas. Beyond Worst-Case Analysis for Root Isolation Algorithms. Proc. ISSAC 2022, pp. 139–148. DOI 10.1145/3476446.3535475, arXiv:2202.06428, https://arxiv.org/abs/2202.06428
  5. Alperen A. Ergür, Josué Tonelli-Cueto, Elias Tsigaridas. Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms. arXiv:2506.04436 (2025), https://arxiv.org/abs/2506.04436
  6. Chris La Valle, Josué Tonelli-Cueto. Some Lower Bounds on the Reach of an Algebraic Variety. Proc. ISSAC 2024, pp. 217–225. DOI 10.1145/3666000.3669693, arXiv:2402.15649, https://arxiv.org/abs/2402.15649
  7. Vikram Sharma. Generalizing The Davenport-Mahler-Mignotte Bound — The Weighted Case. Proc. ISSAC 2020, pp. 410–417. DOI 10.1145/3373207.3404016, arXiv:2005.07843, https://arxiv.org/abs/2005.07843
  8. Pierre Lairez. Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems. Journal of the American Mathematical Society 33:487–526, 2020. DOI 10.1090/jams/938, https://doi.org/10.1090/jams/938
  9. Peter Bürgisser, Felipe Cucker, Pierre Lairez. Rigid continuation paths II. Structured polynomial systems. Forum of Mathematics, Pi 11, 2023. DOI 10.1017/fmp.2023.7, arXiv:2010.10997, https://arxiv.org/abs/2010.10997
  10. Teresa Krick. Effective bounds for polynomial systems defined over the rationals. arXiv:2506.18144 (2025), https://arxiv.org/abs/2506.18144
  11. Boulos El Hilany, Elias Tsigaridas. Bounds on the infimum of polynomials over a generic semi-algebraic set using asymptotic critical values. arXiv:2407.17093 (2024), https://arxiv.org/abs/2407.17093
  12. Ioannis Z. Emiris, Angelos Mantzaflaris, Elias P. Tsigaridas. Multilinear polynomial systems: Root isolation and bit complexity. Journal of Symbolic Computation 105:145–164, 2021. DOI 10.1016/J.JSC.2020.06.005, https://doi.org/10.1016/J.JSC.2020.06.005
  13. John Canny. Generalised characteristic polynomials. Journal of Symbolic Computation 9:241–250, 1990. DOI 10.1016/S0747-7171(08)80012-0, https://doi.org/10.1016/S0747-7171(08)80012-0
  14. W. Dale Brownawell, Chee K. Yap. Lower bounds for zero-dimensional projections. Proc. ISSAC 2009, pp. 79–86. DOI 10.1145/1576702.1576716, https://doi.org/10.1145/1576702.1576716