math.NA — Numerical Analysis
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
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.