\documentclass[10pt,a4paper]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern} \usepackage[a4paper,margin=23mm,top=24mm,bottom=24mm]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{booktabs,enumitem,microtype,fancyhdr,float,graphicx,xcolor} \usepackage[font=small,labelfont=bf,skip=5pt]{caption} \usepackage[hidelinks]{hyperref} \pagestyle{fancy}\fancyhf{} \fancyhead[L]{\small Geometric root calculators: the simultaneous rectangle for systems, without homotopy} \fancyhead[R]{\small S2 / Research preprint} \fancyfoot[C]{\small\thepage} \renewcommand{\headrulewidth}{0.3pt} \setlength{\parindent}{0pt}\setlength{\parskip}{5pt} \setlist{itemsep=1pt,topsep=2pt} \setlength{\emergencystretch}{2em} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\ip}[2]{\langle #1,#2\rangle} \newcommand{\nrm}[1]{\lVert #1\rVert} \newcommand{\cperp}{c_{\perp}} \newcommand{\MV}{\operatorname{MV}} \definecolor{ink}{HTML}{1B2333} \begin{document} {\small\scshape Constructive geometry \,/\, root iterations \,/\, systems of polynomial equations} \vspace{6pt} {\LARGE\bfseries The simultaneous rectangle for systems,\\[2pt] without homotopy\par} \vspace{3pt} {\large All the solutions of a polynomial system, each in a certified ball, with a proof that none is missing: sweeps of the rectangle step, the solutions computed from one another by the law of the residues, and a count by mixed cells that one lifting proves\par} \vspace{8pt} Ivan Besevic\footnote{Computational assistance: AI (Claude, Anthropic) was used for derivations, proofs, numerical experiments, the Lean formalisation, the programs and manuscript preparation. The author is responsible for the claims and their attribution. Section~\ref{sec:evidence} states which results are formal proofs, written proofs and numerical observations.} \quad$\cdot$\quad Independent research\\ Version S2, revised for the version 0.21.0 of the program (it replaces the version S1; companion of \emph{The simultaneous rectangle}, G8 revision~9) \quad$\cdot$\quad 17 November 2026 \vspace{6pt}\hrule\vspace{8pt} \textbf{Abstract.} The note~\cite{s1} carried the simultaneous rectangle of~\cite{g8} from one polynomial to a system of $n$ polynomial equations in $n$ unknowns, and concluded that the step and the certificate transpose while the global work had to be left to a homotopy. This note removes the homotopy. The points start on the solutions of a start system and are swept on $F$ itself with the 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 that have no counterpart in a path method: (1)~the images of the solutions found by the symmetries read on the system; (2)~runs of the step of one point from random points, by batches; (3)~\emph{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 common eigenvalues of small matrices (Proposition~\ref{prop:moments}). Every point, wherever it comes from, passes one certificate, 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 \emph{one} lifting, whatever it is, gives the mixed volume as soon as an exact check meets no tie (Theorem~\ref{thm:lifting}), so that the count is a proof and not a probability. On 40\,000 systems of twenty-seven families the implementation returns what is expected on all of them and proves completeness on 39\,998. On eighteen classical or large systems, up to 6561 solutions and 64 unknowns, it proves completeness on every one, and is faster than a reference homotopy solver with certification on fourteen of them, by a factor of 2 to 25, level on two and slower on two, by a factor of 1.5 (Figure~\ref{fig:versus}). 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, no \texttt{sorry} (Section~\ref{sec:evidence}). \vspace{4pt}\hrule \begin{figure}[!htbp]\centering \includegraphics[width=\textwidth]{fig_gallery.pdf} \caption{All the solutions of four systems, each certified and the list proved complete: the first coordinate of every solution in the complex plane (the colour is the argument of the second coordinate; a ring marks a solution proved real). The first three take 0.12~s, 0.02~s and 0.10~s on ten threads.}\label{fig:gallery} \end{figure} \section{Purpose} $F=(F_1,\dots,F_n):\C^n\to\C^n$ is a polynomial map, $F_i$ of degree $d_i\ge1$, $d=\max_id_i$, and we look for all the solutions of $F(x)=0$, each in a ball that provably contains exactly one, together with a proof that the list is complete. The note~\cite{s1} ended on this sentence: \emph{for systems, the deformation does the global work, and it is not a rectangle construction}. The deformation was the total-degree homotopy~\cite{gz,drexler,ms,sw}. The present note keeps the statements of~\cite{s1} on the step and on the certificate, which it recalls in Sections~\ref{sec:step} and~\ref{sec:cert}, and replaces the rest: \begin{itemize} \item Section~\ref{sec:search}: the search without homotopy, and the three sources of the solutions that the sweeps do not find. \item Section~\ref{sec:res}: the law of the residues, which computes the missing solutions from the others. \item Section~\ref{sec:count}: the count. Completeness is proved when the number of certified balls reaches a bound; for a sparse system the bound that is reached is the mixed volume, and its computation must itself be a proof. \item Section~\ref{sec:cert}: the certificate, with two additions: a box for a double solution, and the value $F(z)$ computed with more bits inside the certificate in doubles. \item Sections~\ref{sec:algo} and~\ref{sec:meas}: the algorithm, the measurements, and a comparison with a homotopy solver. \end{itemize} The measurements are those of a compiled implementation, the Rust crate \texttt{pandsysroots}, version 0.21.0~\cite{crate}. Vectors of $\C^n$ are columns, $\ip uv=\sum_i\overline{u_i}v_i$, $\nrm\cdot$ is the Euclidean norm and $\nrm\cdot_\infty$ the maximum norm with its matrix norm. \emph{Complete} always means: proved complete. \section{The step and the deflation}\label{sec:step} This section recalls~\cite{s1}, where the proofs are. \textbf{The step.} A support is a function $q$ of a cursor $t$ with $q(1)=1$. The three means of degree $p$ of~\cite{v29} are $q_M(t)=\mu(1+t)+\gamma\sqrt t-\nu\sqrt{t+\delta(t-1)^2}$, with $2\mu+\gamma-\nu=1$. Let $f:\C^n\to\C^n$ be analytic, $x$ a point where $f(x)\ne0$ and $f'(x)$ is invertible, and $D=-f'(x)^{-1}f(x)$ Newton's displacement. On the line $x+sD$ the scalar function $\varphi(s)=\ip{f(x)}{f(x+sD)}/\nrm{f(x)}^2$ has $\varphi(0)=1$, $\varphi'(0)=-1$ and \[ \varphi''(0)=L:=\frac{\ip{f(x)}{f''(x)(D,D)}}{\nrm{f(x)}^2},\qquad t=1-\frac p{p-1}\,L,\qquad s=\frac{p}{1+(p-1)\,q(t)} . \] The line does not see all of the second-order term: $f''(x)(D,D)=L\,f(x)+R_\perp$ with $R_\perp\perp f(x)$, and $\cperp=f'(x)^{-1}R_\perp$. \begin{definition}[Rectangle step of a system]\label{def:step} $x^+=x+s\,D-\frac12\,\cperp$, with $p=d$ and the three means as support. \end{definition} For $n=1$ this is the step of~\cite{g8}. For every support with $q'(1)=\frac12$ it agrees with Chebyshev's step up to a term of third order, and the iteration has order three near a simple solution~\cite[Proposition~2.2]{s1}. The cost is one factorisation of $f'(x)$ and one second derivative along one direction. No other iteration is used anywhere in what follows: the sweeps, the runs from random points, the improvement of a candidate and the refinement with more bits are all this step. \textbf{Evaluation.} A step needs $F$, $F'$ and $F''(D,D)$ at the point, and on a large dense system this is most of its cost. The terms of each $F_i$ are kept as a tree of factors: a term is the list of its factors $x_v^{e}$, and the terms that begin with the same factors share them. With $S(w)$ the sum of the terms below a node $w$, without the factors that lead to $w$, and $L(u)$ the product of the factors from the root to $u$, \[ S(u)=c(u)+\sum_{w\text{ child of }u}x_{v(w)}^{e(w)}\,S(w),\qquad F_i=S(\text{root}),\qquad \frac{\partial F_i}{\partial x_v}=\sum_{u}L(u)\sum_{\substack{w\text{ child of }u\\ v(w)=v}}e(w)\,x_v^{e(w)-1}\,S(w), \] since a term has at most one factor of each unknown. $F''(D,D)$ is twice the coefficient of $s^2$ of $S(\text{root})$ when each factor is replaced by its expansion along $D$ to the second order. This is about two products per node. A dense polynomial of degree 16 in three unknowns has 969 terms, 2907 factors and 1140 nodes, and the evaluation of one step on three such equations takes 27 microseconds instead of 63 term by term. Far from the origin the values exceed $10^{154}$ and their squares overflow: $F$ and $F''(D,D)$ are divided by one power of two before $L$ is computed, which leaves it unchanged. \textbf{The deflation.} Let $z_1,\dots,z_m$ be the points. For the point $z_k$ and each equation $i$, let $V_i(k)$ be the $d_i-1$ points nearest to $z_k$ among the others. The map deflated for the point $k$ is $G_k=(F_i/g_i)_i$, where $g_i$ is the product over $j\in V_i(k)$ of the linear forms $\ip{z_k-z_j}{x-z_j}/\nrm{z_k-z_j}^2$, equal to one at $z_k$ and to zero on the hyperplane through $z_j$ orthogonal to $z_k-z_j$. The step of Definition~\ref{def:step} is applied to $G_k$; it needs $F$, $F'$ and $F''(D,D)$ at $z_k$ and sums over the neighbours. For $n=1$ the neighbours are all the other points and the deflated Newton step is that of Ehrlich and Aberth~\cite{ehrlich,aberth}. The number $d_i-1$ comes from the law of the weights~\cite[Proposition~3.3]{s1}: with all the other points as neighbours the points are sent to infinity, with small equal weights they meet, and with $d-1$ neighbours of weight one a point that is far comes back in one step and two points cannot settle on one solution. \begin{figure}[!htbp]\centering \includegraphics[width=\textwidth]{fig_sweeps.pdf} \caption{Two cubics with complex Gaussian coefficients, nine points swept on $F$ from the binomial start, all together. Left and centre: the two coordinates of each point after each sweep, from the start to the nine solutions (large dots). Right: the size of the Newton displacement of each point. Eight points settle in five to eight sweeps; the ninth one wanders until the nineteenth sweep before it finds the solution that is left. One example.}\label{fig:sweeps} \end{figure} \begin{figure}[!htbp]\centering \includegraphics[width=\textwidth]{fig_basins.png} \caption{The step of one point alone, without neighbours, on $x^3-x+0.3\,y=0$, $y^3-y+0.3\,x=0$, from each point of a grid of $900\times900$ real starting points: the colour is the solution reached (the nine solutions are real, white dots), darker when more steps were needed, black when no solution is reached in sixty steps. Left: the rectangle step of Definition~\ref{def:step}, 5.4 steps on average; 0.4\,\% of the starts reach no solution. Right: the support $AK$ without the term $\cperp$, which is Newton's iteration, 7.2 steps on average; every start reaches a solution. The step of order three is faster and its basins are more intricate; in the method the starts that fail cost one run among thousands.}\label{fig:basins} \end{figure} \section{The search, without homotopy}\label{sec:search} \textbf{Start.} The points start on the solutions of a start system; only its solutions are used, the system itself is never deformed. By default it is the binomial system $x_i^{d_i}=r^{d_i}$, whose $N=d_1\cdots d_n$ solutions are the points $(r\omega_1,\dots,r\omega_n)$, $\omega_i^{d_i}=1$, each coordinate being a root extraction of~\cite{v29,c5}; $r$ is the geometric mean over $i$ of $(|F_i(0)|/c_i)^{1/d_i}$, $c_i$ the largest modulus of a coefficient of degree $d_i$ of $F_i$. When a partition of the unknowns gives a smaller multihomogeneous B\'ezout number (Section~\ref{sec:count}), the start is a product of linear forms that follows the partition, with as many solutions as that number. When the mixed volume is smaller still and is known before the search, as many points as the mixed volume are drawn among those of the start: a point in excess can only leave for infinity, and costs as much as a point that finds a solution. When the system has symmetries beyond the conjugation (below), a solution found gives its images, and the search does not need a point per solution: with $g\le8$ the size of the orbit of a point in general position, counted up to eight, it starts from $2/g$ of the count: 1637 points for the 6545 solutions of noon-8, 231 for the 924 of cyclic-7. \textbf{Sweeps.} All the points are moved together by the step of Section~\ref{sec:step} on $F$, each one deflated of its nearest neighbours (Figure~\ref{fig:sweeps}). A point whose Newton displacement is at the level of the rounding has settled: it no longer moves and stays a neighbour of the others, so that a sweep costs only the points still looking for a solution. A point that leaves the range of the start by a factor $10^8$ is at infinity. The sweeps stop when every point has settled or left, or after a number of sweeps without progress. Nothing guarantees that the sweeps find every solution, and in general they do not: on the large systems of Section~\ref{sec:meas} they bring 4\,\% to 88\,\% of the solutions (Table~\ref{tab:stages}). In~\cite{s1} this was the reason for the homotopy. Here the rest comes from three sources. \textbf{(1) Symmetries.} Three symmetries are read on the terms of the system: the conjugation when the coefficients are real; a permutation of the unknowns that sends the set of the equations onto itself up to constants; the multiplication of every unknown by a root of unity of order $g$ when the degrees of the terms of each equation are congruent modulo $g$. The image of a solution is a solution; it is treated as a candidate and certified like any other point, each image once. For cyclic-7 the sweeps of 231 points find 39 solutions, their images are 759 others, and the 126 that are left come from the runs below and from their images. \textbf{(2) Runs from random points.} The step of one point alone, from a point drawn at random at the scale of the solutions found, ends on a solution drawn more or less at random (Figure~\ref{fig:basins}); it is cheap, and a batch of several thousand runs is spread over the threads. While many solutions are missing a good part of the runs find a new one. The batches go on as long as they bring something. \textbf{(3) The law of the residues}, Section~\ref{sec:res}: the solutions found give the missing ones by linear algebra. Its cost grows as the cube of the number of missing solutions and that of a batch as their number, so, at degree eight at most, the batches come first, while more than two hundred solutions are missing and a batch finds one in sixteen of them, and the residues close the count. Last, and only when solutions are still missing: restarts of the step deflated of every solution found, from points near the solutions and at several scales; and a second search from another start. A search for solutions that the count announces and that do not exist (a system with a curve of solutions) is given up after two batches and three hundred restarts without result; the output is then not complete, and says so. \begin{table}[!htbp]\centering\footnotesize\setlength{\tabcolsep}{5pt} \begin{tabular}{@{}lrrrrrrr@{}}\toprule system & unknowns & solutions & points & sweeps & symmetries & random runs & residues \\\midrule cyclic-7 & 7 & 924 & 231 & 39 & 759 & 126 & \\ noon-7 & 7 & 2173 & 544 & 344 & 1829 & & \\ noon-8 & 8 & 6545 & 1637 & 872 & 5673 & & \\ Katsura-12 & 12 & 4096 & 4096 & 3259 & 474 & 178 & 185 \\ two unknowns, degree 40 & 2 & 1600 & 1600 & 1049 & & & 551 \\ three unknowns, degree 16 & 3 & 4096 & 4096 & 3607 & & & 489 \\ 8 cubics & 8 & 6561 & 6561 & 5343 & & 1018 & 200 \\ 12 quadrics & 12 & 4096 & 4096 & 3184 & & 803 & 109 \\ bilinear $7+7$ & 14 & 3432 & 3432 & 1676 & & 1563 & 193 \\ eigenvalues, order 64 & 64 & 64 & 64 & 33 & 10 & & 21 \\ sparse, four unknowns & 4 & 185 & 185 & 121 & & & 64 \\ \bottomrule\end{tabular} \caption{Where the solutions come from, on eleven systems of Section~\ref{sec:meas}: the number of points swept, the solutions certified at the end of the sweeps, and those added by each of the three sources (the runs from random points with their images; the last column includes the few partners of close pairs found by the step of a cluster of two). Every system is complete.}\label{tab:stages} \end{table} \section{The law of the residues}\label{sec:res} \begin{theorem}[Euler, Jacobi~\cite{jacobi}]\label{thm:ej} Let $F$ have $N=d_1\cdots d_n$ solutions in $\C^n$, all simple. For every polynomial $g$ of degree at most $E=d_1+\dots+d_n-n-1$, \[ \sum_{F(\xi)=0}\frac{g(\xi)}{\det F'(\xi)}=0 . \] \end{theorem} In one unknown this is $\sum_\xi\xi^k/f'(\xi)=0$ for $k\le d-2$. The theorem says that the solutions are not independent: a few of them are determined by the others. Let $\xi_1,\dots,\xi_K$ be the solutions found and $\zeta_1,\dots,\zeta_r$ the missing ones, $K+r=N$, and $\omega_j=1/\det F'(\zeta_j)\ne0$. For an exponent $c$ with $|c|\le E$ the \emph{moment} \begin{equation}\label{eq:moment} m(c):=-\sum_{k=1}^K\frac{\xi_k^{\,c}}{\det F'(\xi_k)}=\sum_{j=1}^r\omega_j\,\zeta_j^{\,c} \end{equation} is computed from the solutions found, and is the moment of a measure with one atom per missing solution. Let $B$ be a set of exponents and $\ell(x)=\sum_c\ell_cx_c$ a linear form, such that $|a|+|b|+1\le E$ for all $a,b\in B$, and \[ M_0=\bigl(m(a+b)\bigr)_{a,b\in B},\qquad M_\ell=\Bigl(\sum_c\ell_c\,m(a+b+e_c)\Bigr)_{a,b\in B}. \] \begin{proposition}\label{prop:moments} Let $V$ be the $r\times|B|$ matrix $(\zeta_j^{\,a})$, $W=\operatorname{diag}(\omega_j)$ and $\Lambda=\operatorname{diag}(\ell(\zeta_j))$. Then $M_0=V^TWV$ and $M_\ell=V^TW\Lambda V$. If $V$ has rank $r$ and $v$ is a vector with $Vv=e_j$, then \[ M_\ell\,v=\ell(\zeta_j)\,M_0\,v,\qquad M_0\,v=\omega_j\,\bigl(\zeta_j^{\,a}\bigr)_{a\in B} . \] So the numbers $\ell(\zeta_j)$ are the generalised eigenvalues of the pair $(M_\ell,M_0)$, and for an eigenvector $v$ the vector $u=M_0v$ lists the monomials at the missing solution up to a factor: if $a$ and $a+e_c$ are in $B$, the coordinate $c$ of $\zeta_j$ is $u_{a+e_c}/u_a$. \end{proposition} \begin{proof} By~\eqref{eq:moment}, $m(a+b)=\sum_j\zeta_j^{\,a}\,\omega_j\,\zeta_j^{\,b}$ and $\sum_c\ell_cm(a+b+e_c)=\sum_j\zeta_j^{\,a}\,\omega_j\,\ell(\zeta_j)\,\zeta_j^{\,b}$. With $Vv=e_j$: $M_0v=V^TWe_j=\omega_j$ times the row $j$ of $V$, and $M_\ell v=V^TW\Lambda e_j=\ell(\zeta_j)\,M_0v$. \end{proof} The matrices are those of the multiplication by $\ell$ in the quotient algebra, read on the missing solutions alone; that the solutions of a system are eigenvalues of such matrices is the method of~\cite{as}. What is specific here is where the matrices come from: no Gr\"obner basis and no resultant, only the values of monomials and of $\det F'$ at the solutions already certified. The size of the matrices is the number of \emph{missing} solutions, not $N$. \textbf{In practice.} $B$ is taken a quarter larger than $r$, so that the elimination can choose well-conditioned monomials, and the rank $r$ of $M_0$ is read during the elimination. One random form $\ell$ separates the eigenvalues; they are computed by a Hessenberg reduction and the shifted $QR$ iteration, the eigenvectors by inverse iteration, and the coordinates as the quotients of the proposition. The law needs $2\max_{a\in B}|a|+1\le E$: for two equations of degree 40, $E=77$, the monomials of degree at most 38 are 780, and the 551 missing solutions of Table~\ref{tab:stages} are computed from the 1049 others. \begin{figure}[!htbp]\centering \includegraphics[width=0.93\textwidth]{fig_residues.pdf} \caption{Two equations of degree 12 with complex Gaussian coefficients, 144 solutions. The sweeps alone find 134 of them (grey). The ten others (rings) are computed from the 134 by Proposition~\ref{prop:moments} (crosses): before any step of improvement the candidates are within $4\cdot10^{-15}$ to $10^{-12}$ of the solutions (right). One example.}\label{fig:residues} \end{figure} \textbf{Three forms of the law.} Theorem~\ref{thm:ej} asks for as many solutions as B\'ezout's number. Two extensions are used, each tied to a count of Section~\ref{sec:count}. \emph{(a)~Groups of unknowns.} If the system has as many simple solutions as the multihomogeneous B\'ezout number of a partition of the unknowns into groups of sizes $k_1,\dots,k_s$, the sum vanishes for every $g$ whose degree in the unknowns of the group $j$ is at most $E_j=\sum_id_{ij}-k_j-1$, $d_{ij}$ being the degree of $F_i$ in that group. This covers the bilinear systems and the eigenvalue problems, where B\'ezout's number is far above the number of solutions. \emph{(b)~Newton polytopes.} If the system has as many simple solutions as the mixed volume of its Newton polytopes, the sum of $\xi^{\,c}/\det F'(\xi)$ vanishes for every exponent $c$ such that $c+(1,\dots,1)$ is in the interior of the sum of the polytopes (Khovanskii~\cite{khov}). Whether an exponent is inside the sum is decided by a linear program. \textbf{What rests on the law.} Nothing. A candidate computed by the law is improved by the step of Definition~\ref{def:step} and must pass the certificate of Section~\ref{sec:cert}; if the hypotheses of the law fail (a solution that is not simple, a count that is not reached), the candidates are close to nothing and are refused. The law is a way to find points, not an argument of the proof. \section{The count}\label{sec:count} The output is complete when the number of disjoint certified balls is a bound of the number of isolated solutions in $\C^n$, counted with multiplicity. The bounds used, the smallest being kept: \begin{itemize} \item B\'ezout's number $N=d_1\cdots d_n$; \item the multihomogeneous B\'ezout number of a partition of the unknowns into groups of sizes $k_1,\dots,k_s$: the coefficient of $a_1^{k_1}\cdots a_s^{k_s}$ in $\prod_i(d_{i1}a_1+\dots+d_{is}a_s)$ (Morgan and Sommese~\cite{ms2}); all the partitions up to nine unknowns, searched once per system; \item the mixed volume $\MV(P_1,\dots,P_n)$ of the Newton polytopes $P_i$ of the supports $A_i$ with the origin added (Bernstein~\cite{bernstein} in the torus; Li and Wang~\cite{lw} for $\C^n$). \end{itemize} \begin{remark}\label{rem:full} When every $P_i$ is the whole product of simplices $\prod_jd_{ij}\Delta_{k_j}$ of a partition, the mixed volume is the multihomogeneous B\'ezout number of the partition, and nothing has to be computed; it is enough to look for the vertices of the product in the support. This is the case of the dense and of the bilinear systems. \end{remark} \textbf{Mixed cells.} Up to three unknowns the mixed volume is computed from the volumes of the sums of the polytopes, exactly, in integers. Beyond, by the mixed cells of Huber and Sturmfels~\cite{hs2}. Give each point $a$ of each support $A_i$ an integer $w_i(a)$, the \emph{lifting}. For $g\in\R^n$ the lifted function of the support $i$ is $a\mapsto\ip ag+w_i(a)$. \begin{definition}\label{def:cell} A \emph{choice of edges} is a pair $\{p_i,q_i\}\subset A_i$ for each $i$, with $\Delta=\det(p_1-q_1,\dots,p_n-q_n)\ne0$; its vector $g$ is the solution of the $n$ equations $\ip{p_i-q_i}g=w_i(q_i)-w_i(p_i)$. It is a \emph{mixed cell} of $w$ if, for every $i$, the lifted function of $A_i$ at $g$ is smallest at $p_i$ and $q_i$ and nowhere else. It is a \emph{tie} of $w$ if it is smallest at $p_i$ and $q_i$ for every $i$, and also at a third point for some $i$. \end{definition} \begin{theorem}[Huber, Sturmfels~\cite{hs2}]\label{thm:hs} For a lifting in general position, $\MV(P_1,\dots,P_n)=\sum|\Delta|$ over the mixed cells. \end{theorem} The liftings that are not in general position are contained in a finite union of hyperplanes of the space of liftings (the walls of the regular subdivisions of the Cayley configuration of the supports). A lifting drawn at random among real numbers is in general position with probability one; a lifting drawn among the integers below $2^{36}$ is so with a probability that is close to one and is not one. A count that proves completeness cannot rest on it. Computing the cells with two liftings and comparing is evidence; the next statement is a proof. \begin{figure}[!htbp]\centering \includegraphics[width=0.93\textwidth]{fig_cells.pdf} \caption{Two supports in the plane (left, centre) and the subdivision of $A_1+A_2$ that a lifting induces (right). The mixed cells (green) are the sums of an edge of $A_1$ and an edge of $A_2$; the number in each is $|\Delta|$, and their sum, 11, is the mixed volume: two equations with these supports have at most 11 isolated solutions. The other cells are the sum of a triangle of one support and a point of the other.}\label{fig:cells} \end{figure} \begin{theorem}[One lifting]\label{thm:lifting} Let $w$ be any lifting. If $w$ has no tie, then $\MV(P_1,\dots,P_n)=\sum|\Delta|$ over the mixed cells of $w$. \end{theorem} \begin{proof} Let $\eta$ be a direction of the space of liftings contained in none of the hyperplanes of the paragraph above. Then $w_\varepsilon=w+\varepsilon\eta$ is in general position for every small $\varepsilon>0$: a hyperplane that contains $w$ does not contain $w_\varepsilon$, and the others are at a positive distance from $w$. Fix a choice of edges. Its vector for $w_\varepsilon$ is $g_\varepsilon=g+\varepsilon h$, an affine function of $\varepsilon$, since the matrix of the $n$ equations does not depend on the lifting. Each condition ``the lifted function is not smaller at $a$ than at $p_i$'' therefore reads $A+\varepsilon B\le0$, with $A$ its value for $w$. \emph{A mixed cell of $w$ is a mixed cell of $w_\varepsilon$ for small $\varepsilon$:} its conditions hold strictly at $\varepsilon=0$, that is $A<0$, hence $A+\varepsilon B<0$ for small $\varepsilon$. \emph{A choice of edges that is a mixed cell of $w_\varepsilon$ for arbitrarily small $\varepsilon>0$ is a mixed cell of $w$:} every condition satisfies $A+\varepsilon B\le0$ for arbitrarily small $\varepsilon>0$, hence $A\le0$; the lifted functions are smallest at $p_i$ and $q_i$ for $w$, and since $w$ has no tie, nowhere else. The choices of edges are finitely many, so for $\varepsilon$ small enough $w$ and $w_\varepsilon$ have the same mixed cells, with the same $\Delta$, and Theorem~\ref{thm:hs} applies to $w_\varepsilon$. \end{proof} \textbf{The search of the cells} enumerates the choices of edges support by support. A partial choice puts linear conditions on $g$: equalities for the edges, inequalities for the other points. It is given up when these conditions have no solution, which is decided by the simplex method in doubles on the dual program: weights $y\ge0$ on the conditions, of sum one, whose combination of the rows vanishes, and that make the same combination of the right sides smallest. A new edge adds columns to this program, so the basis of the parent choice is still a basis and a few pivots are enough. A negative value comes with the $n+1$ conditions of the basis, and the doubles are \emph{never trusted}: the choice is given up only if an exact elimination on these $n+1$ conditions, in integers, produces a combination with a zero left side and a negative right side. At the last support the $n-1$ edges chosen leave a line of vectors $g$, computed once in integers, and every edge of the last support is tested on it by signs of products of integers; a condition met with equality by a choice whose other conditions hold is a tie, and the lifting is then drawn again. So for the lifting that is kept, every mixed cell is found and counted exactly, no tie exists, and Theorem~\ref{thm:lifting} applies. A float error can only make the search longer. The mixed volume of cyclic-7 (924) takes 0.05~s, that of cyclic-9 (11\,016) 1.7~s, that of noon-9 (19\,665) 0.7~s. It is computed before the search when the other counts would start a hundred points or more. \section{The certificate}\label{sec:cert} Let $z\in\C^n$ and let $A$ be any matrix, in practice an approximate inverse of $F'(z)$. Write $F(z+h)=\sum_\alpha c_\alpha h^\alpha$ and $\eta=\nrm{AF(z)}_\infty$, $\delta=\nrm{I-AF'(z)}_\infty$, $T_k=\max_i\sum_{|\alpha|=k}|(Ac_\alpha)_i|$. \begin{theorem}[Certificate~{\cite[Theorem~6.1]{s1}}]\label{thm:cert} If $\eta+\delta\rho+\sum_{k\ge2}T_k\rho^k\le\rho$ and $\delta+\sum_{k\ge2}kT_k\rho^{k-1}<1$, the closed ball $B(z,\rho)$ of the maximum norm contains exactly one solution of $F=0$, and it is simple. \end{theorem} The proof is a contraction of the ball by $x\mapsto x-AF(x)$. If $M$ certified balls are pairwise disjoint, $F$ has at least $M$ solutions; if $M$ is a bound of Section~\ref{sec:count}, it has no other isolated solution. For a real system with a complete output, a solution whose mirror ball meets no other ball is real~\cite[Proposition~6.3]{s1}. \textbf{A cheaper bound.} The sums $T_k$ need all the Taylor coefficients at $z$, which is most of the cost at high degree. Let $|F_i|$ be the polynomial with the moduli of the coefficients of $F_i$, and $H_i(\rho)$ the sum of all its second derivatives at the point $(|z_1|+\rho,\dots,|z_n|+\rho)$. \begin{proposition}\label{prop:cheap} Let $S(\rho)=\max_i\sum_j|A_{ij}|\,H_j(\rho)$. In Theorem~\ref{thm:cert}, $\sum_{k\ge2}T_k\rho^k$ may be replaced by $\frac12\rho^2S(\rho)$ and $\sum_{k\ge2}kT_k\rho^{k-1}$ by $\rho\,S(\rho)$. In particular, with $\rho=2\eta$, the ball is certified as soon as $2\delta+\rho\,S(\rho)\le1$ and $\delta+\rho\,S(\rho)<1$. \end{proposition} \begin{proof} For $\nrm h_\infty\le\rho$ and $0\le\theta\le1$, each second derivative of $F_i$ at $z+\theta h$ is bounded in modulus by the same derivative of $|F_i|$ at $(|z_c|+\rho)_c$, a polynomial with nonnegative coefficients. Taylor's formula bounds the terms of order two and more of $F_i(z+h)$ by $\frac12\rho^2H_i(\rho)$ and their derivative along a direction of norm one by $\rho\,H_i(\rho)$; these are the two quantities that the proof of Theorem~\ref{thm:cert} uses. \end{proof} One evaluation instead of the whole expansion; the sums $T_k$ are computed only when this test does not conclude. \textbf{The value with more bits.} The radius of the ball is $2\eta$, and $\eta$ is computed from an enclosure of $F(z)$. At high degree the value of $F(z)$ in interval arithmetic of doubles is an interval far wider than the number: the ball is certified, and wide, though the point is as good as a double can be. On two equations of degree 40, this happened at 743 of the 1600 solutions. Refining the point with 128 bits does not address the cause. Instead, $F(z)$ alone is computed with fixed-point balls of 128 bits and rounded outward to doubles, and the certificate in doubles is run again with this enclosure; $A$, $\delta$ and $S$ are unchanged. Then, if the ball is still wide, the point is moved by the step computed from that value, while the radius decreases: where the square of the displacement is below the last bit of the point, the terms of order two of Definition~\ref{def:step} are below the rounding and the step is its first term. \textbf{Beyond doubles.} A point that doubles do not certify is improved by the step of Definition~\ref{def:step} on centres of 128, 256, \dots\ bits and certified at that precision; the ball returned around the centre rounded to doubles is certified with the slack of that rounding. A second entry returns centres and radii at any precision asked for. \textbf{Double solutions.} Theorem~\ref{thm:cert} proves simplicity, and cannot hold at a solution of multiplicity two, nor in doubles at two solutions closer than the rounding allows to separate. At a point $c$ where $F'(c)$ is nearly singular, with $v$ and $u$ its right and left vectors of smallest singular value, take coordinates $x=c+Th$ whose first axis is $v$ and a matrix $M$ whose first row is $u^*$, such that $G(h)=MF(c+Th)$ is close to $P(h)=(a\,h_1^2,h_2,\dots,h_n)$. \begin{proposition}[Double box]\label{prop:double} If $|G_1-a\,h_1^2|<|a|\,r_1^2$ and $|G_i-h_i|