The Simultaneous Rectangle for Systems, without Homotopy: All the Solutions of a Polynomial System, Each in a Certified Ball, with a Proof That None Is Missing
Version 1 / Nov 18, 2026 / CC BY 4.0
Abstract
This note carries the simultaneous rectangle of one polynomial (version G8) to a system of polynomial equations in unknowns, and removes the homotopy on which the previous version S1 relied. The points start on the solutions of a start system and are swept on itself with a rectangle step of order three, each point deflated of its nearest neighbours; nothing is tracked. What the sweeps do not find is obtained in three ways: the images of the solutions found by the symmetries read on the system; runs of the step of one point from random points; and the law of the residues: by the formula of Euler and Jacobi the solutions found determine the moments of the missing ones, which are then the generalised eigenvalues of small matrices. Every point passes one certificate (a contraction of a ball in interval arithmetic, and a box by Rouché's theorem for a double solution), and the output is complete when as many disjoint balls are certified as a bound of the number of solutions. For sparse systems that bound is the mixed volume, computed by mixed cells; we show that one lifting, whatever it is, gives the mixed volume as soon as an exact check meets no tie, so that the count is a proof and not a probability. With the Rust crate pandsysroots 0.21.0, on 40,000 systems of twenty-seven families the output is as expected on all of them and proved complete on 39,998; on eighteen classical or large systems, up to 6561 solutions and 64 unknowns, completeness is proved on every one, and the program is faster than a reference homotopy solver with certification on fourteen of them, level on two and slower on two (one machine, default settings). The algebra of the step, the certificate, the laws used by the residues and the argument of the lifting are checked in Lean 4 (64 theorems). The note states which results are formal proofs, written proofs, quoted theorems and numerical observations, and its limits: no theorem of convergence, no certificate for a multiplicity above two, no proof of completeness for a system with a curve of solutions.
Provenance statement
References
- O. Aberth. Iteration methods for finding all zeros of a polynomial simultaneously. Math. Comp. 27 (1973), 339--344.
- L. A. Aĭzenberg, A. P. Yuzhakov. Integral Representations and Residues in Multidimensional Complex Analysis . Amer. Math. Soc., 1983.
- W. Auzinger, H. J. Stetter. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Numerical Mathematics, Singapore 1988 , Birkhäuser, 1988, 11--30.
- J. Backelin. Square multiples give infinitely many cyclic -roots. Reports, Matematiska Institutionen, Stockholms Universitet, 1989.
- D. N. Bernstein. The number of roots of a system of equations. Funct. Anal. Appl. 9 (1975), 183--185.
- I. Besevic. Geometric Root Calculators , version V29, 2026.
- I. Besevic. Complex Geometric Root Calculators , version C5, 2026.
- I. Besevic. The simultaneous rectangle , version G8, revision 9, 2026. https://doi.org/10.5281/zenodo.24257672.DOI
- I. Besevic. The simultaneous rectangle for systems , version S1, 2026.
- I. Besevic. pandsysroots , version 0.21.0, 2026. https://crates.io/crates/pandsysroots.link
Show all 31 referencesShow fewer references
- G. Björck, R. Fröberg. A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic -roots. J. Symbolic Comput. 12 (1991), 329--336.
- P. Breiding, S. Timme. HomotopyContinuation.jl: a package for homotopy continuation in Julia. In Mathematical Software -- ICMS 2018 , Springer, 2018, 458--465.
- P. Breiding, K. Rose, S. Timme. Certifying zeros of polynomial systems using interval arithmetic. ACM Trans. Math. Software 49 (2023), no. 1.
- K. M. Brown, W. B. Gearhart. Deflation techniques for the calculation of further solutions of a nonlinear system. Numer. Math. 16 (1971), 334--342.
- F. J. Drexler. Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen. Numer. Math. 29 (1977), 45--58.
- L. W. Ehrlich. A modified Newton method for polynomials. Comm. ACM 10 (1967), 107--108.
- P. E. Farrell, Á. Birkisson, S. W. Funke. Deflation techniques for finding distinct solutions of nonlinear partial differential equations. SIAM J. Sci. Comput. 37 (2015), A2026--A2045.
- T. Gao, T. Y. Li, M. Wu. Algorithm 846: MixedVol: a software package for mixed-volume computation. ACM Trans. Math. Software 31 (2005), 555--560.
- C. B. Garcia, W. I. Zangwill. Finding all solutions to polynomial systems and other systems of equations. Math. Programming 16 (1979), 159--176.
- B. Huber, B. Sturmfels. A polyhedral method for solving sparse polynomial systems. Math. Comp. 64 (1995), 1541--1555.
- C. G. J. Jacobi. Theoremata nova algebraica circa systema duarum aequationum inter duas variabiles propositarum. J. Reine Angew. Math. 14 (1835), 281--288.
- A. G. Khovanskii. Newton polyhedra and the Euler--Jacobi formula. Russian Math. Surveys 33 (1978), no. 6, 237--238.
- R. Krawczyk. Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken. Computing 4 (1969), 187--201.
- T. Y. Li, X. Wang. The BKK root count in . Math. Comp. 65 (1996), 1477--1484.
- A. P. Morgan, A. J. Sommese. Computing all solutions to polynomial systems using homotopy continuation. Appl. Math. Comput. 24 (1987), 115--138.
- A. P. Morgan, A. J. Sommese. A homotopy for solving general polynomial systems that respects -homogeneous structures. Appl. Math. Comput. 24 (1987), 101--113.
- V. W. Noonburg. A neural network modeled by an adaptive Lotka--Volterra system. SIAM J. Appl. Math. 49 (1989), 1779--1792.
- S. M. Rump. Verification methods: rigorous results using floating-point arithmetic. Acta Numer. 19 (2010), 287--449.
- S. Smale. Newton's method estimates from data at one point. In The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics , Springer, 1986, 185--196.
- A. J. Sommese, C. W. Wampler. The Numerical Solution of Systems of Polynomials Arising in Engineering and Science . World Scientific, 2005.
- J. Verschelde. Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Software 25 (1999), 251--276.
Version history
- v1 · 14 pagesSubmitted by Ivan BESEVICVersion S2, 17 November 2026. Also deposited on Zenodo with the Lean files, the programs of the figures and the measurements: https://doi.org/10.5281/zenodo.24314654. Software: https://crates.io/crates/pandsysroots (version 0.21.0). Companion for systems of The Simultaneous Rectangle (G8), https://doi.org/10.5281/zenodo.24257672.CurrentNov 17, 2026