Polynomial arithmetic cost for rounded-input bounded-grid root isolation

For $d\ge 1$ interpolate $p$ at $x_j=-1+2j\mathrm{/}d$, $j=0,\dots ,d$. The Lagrange basis is $L_j(x)={\prod }_{k\mathrm{\ne }j}(x-x_k)\mathrm{/}{\prod }_{k\mathrm{\ne }j}(x_j-x_k)$. The numerator's sum of absolute coefficients is at most ${\prod }_{k\mathrm{\ne }j}(1+\mathrm{\mid }{x}_k\mathrm{\mid })\le 2^d$; the absolute denominator is $(2\mathrm{/}d{)}^{d}j!(d-j)!\ge (2\mathrm{/}d{)}^d$. Therefore each coefficient of $L_j$ has absolute value at most $d^d$, and, since $\mathrm{\mid }p(x_j)\mathrm{\mid }\le 1$, every coefficient of $p$ has absolute value at most $A=(d+1)d^d$. This interpolation identity follows because subtracting the interpolant leaves a polynomial of degree at most $d$ with $d+1$ distinct zeros. For $d=0$ use $A=1$. Hence ${\log }_2(\max (2,A))=O(d\log (d+1)+1)$, independently of any encoding of the original coefficients.

We give explicit coarse separation estimates sufficient for counting subdivisions. For a primitive integer polynomial $U$ of degree $m$ and coefficient magnitude at most $2^J$, every root has $\mathrm{\mid }z\mathrm{\mid }\le C=1+2^J$ by the Cauchy argument: outside that radius the leading monomial strictly dominates the geometric sum of the others. Every primitive integer divisor $V$ of $U$ has leading coefficient dividing that of $U$ and all its roots among those of $U$. Its coefficients, by expanding its linear factors, thus have magnitude at most $2^J{2}^m\max (1,C{)}^m$. The assertion that primitive integer divisors may be used here follows from Gauss's lemma: products of primitive polynomials are primitive, since reduction modulo any prime gives a product of two nonzero polynomials over a field; clearing denominators of a rational factorization and comparing contents then gives the integral factorization. Consequently the primitive square-free part, and every gcd with another integer polynomial, has coefficient height $O(m(J+1))$. This is an output coefficient-growth bound; it does not bound the internal Euclidean fractions.

For the root-isolation input $P$, if $n=\mathrm{deg}P=0$, the constant branch in [F1] returns the empty list, which is correct and takes constant work; assume $n\ge 1$ below. Put $q$ equal to the square-free part of $P$ and $F(x,y)=\mathrm{Im}q(x+iy)$. This is a nonzero real bivariate polynomial of total degree at most $n$: if $\mathrm{Im}q$ vanished everywhere, its $x$ derivative and its $y$ derivative would force $q^{\mathrm{\prime }}=0$ by the coefficient expansion, contrary to nonconstancy. A nonzero bivariate polynomial of total degree $\le n$ vanishes at at most $nN$ points of a product of two $N$-point sets. Indeed, if its leading nonzero coefficient as a polynomial in $y$ has $x$-degree $s$, at most $s$ $x$-values annihilate that coefficient; at every remaining $x$ there are at most $n-s$ $y$-zeros, giving at most $sN+(N-s)(n-s)\le nN$. Each fixed old edge restriction of $F$ is nonzero by admissibility, so it has at most $n$ forbidden new vertex coordinates. There are at most $n$ root real coordinates and $n$ root imaginary coordinates, and at most $n$ coordinates making $F$ vanish identically along a vertical or horizontal line: such a coordinate must annihilate any chosen nonzero coefficient polynomial. The new center-vertex condition excludes at most $nN$ pairs. Old-edge vertex, root-line, and identically-zero-edge restrictions together exclude fewer than $20(n+1)N$ pairs. The analogous four outer-corner polynomials $F(\pm X,\pm Y)$ are nonzero and obey the same bound. Therefore $N=100(n+1)$ gives an admissible pair both outside and inside, so INTERNAL_ERROR is unreachable. At most $N^2$ candidate pairs are tested at each node. A univariate nonzero polynomial similarly excludes at most $n$ candidates, proving the one-dimensional bounded search.

Let $\tau =\min (\delta ,8)$ and $t=2^{-L}$. The least-$L$ rule gives $t\le \tau \mathrm{/}[64(d+1)]$ and, unless $L=0$, $t>\tau \mathrm{/}[128(d+1)]$. Since $0<\tau \le 8$, the shrink factor $1-\tau \mathrm{/}16$ lies in $[1\mathrm{/}2,1)$. For each scaled coefficient, binary search over the integer mesh indices in $[-M,M]$, where $M=(A+2)2^L$, finds the lower mesh point and exact comparison with its midpoint resolves the rounding tie. Since the interpolation bound gives $\mathrm{\mid }((1-\tau \mathrm{/}16)p{)}_j\mathrm{\mid }\le A$, this search interval contains the needed cell and takes $O(\log (A+1)+L)$ exact comparisons and rational arithmetic operations, including each integer midpoint division by two. Rounding error per coefficient is at most $t\mathrm{/}2\le \tau \mathrm{/}[64(d+1)]$, so $\mathrm{\parallel }h-(1-\tau \mathrm{/}16)p{\mathrm{\parallel }}_{\mathrm{\infty }}\le \tau \mathrm{/}64$. Thus $\mathrm{\parallel }h-p{\mathrm{\parallel }}_{\mathrm{\infty }}\le 5\tau \mathrm{/}64<\tau \mathrm{/}8$ and $\mathrm{\parallel }h{\mathrm{\parallel }}_{\mathrm{\infty }}\le 1-3\tau \mathrm{/}64$. Parity is preserved because forbidden coefficients remain exactly zero. The integers $2^L{h}_j$ have length $O(L+\log (A+1))$, and the convolution coefficients of $2^{2L}(1-h^2)$ have length $O(L+\log (A+1)+\log (d+1))$. Minimality of $L$ gives $L=O(\log (d+1)+{\log }_{+}(1\mathrm{/}\tau )+1)$, proving the claimed height and rounding cost, also when $\delta \ge 1$. Zero leading rounded coefficients only lower the actual degree.

Let $V(z)=a{z}^r+{\sum }_{j<r}{v}_j{z}^j$ be the primitive square-free integer part of $U$, of degree $r\ge 2$. Define $W(t)=a^{r-1}V(t\mathrm{/}a)$. Its leading coefficient is one, and its $j$-th coefficient for $j<r$ is $v_j{a}^{r-1-j}$, an integer. Its distinct roots are ${\beta }_i=a{\zeta }_i$, with $\mathrm{\mid }{\beta }_i\mathrm{\mid }\le \mathrm{\mid }a\mathrm{\mid }C$. By [F4], $\mathrm{Disc}(W)$ is a nonzero integer and $\mathrm{\mid }\mathrm{Disc}(W)\mathrm{\mid }={\prod }_{i<j}\mathrm{\mid }{\beta }_i-{\beta }_j{\mathrm{\mid }}^2\ge 1$. If ${\mathrm{\Delta }}_{\beta }$ is the least separation of its roots, all other pairwise distances are at most $2\mathrm{\mid }a\mathrm{\mid }C$, so $1\le {\mathrm{\Delta }}_{\beta }^2(2\mathrm{\mid }a\mathrm{\mid }C{)}^{r(r-1)-2}$. Therefore the separation of the roots of $V$ obeys ${\mathrm{\Delta }}_{\zeta }={\mathrm{\Delta }}_{\beta }\mathrm{/}\mathrm{\mid }a\mathrm{\mid }\ge \mathrm{\mid }a{\mathrm{\mid }}^{-1}(2\mathrm{\mid }a\mathrm{\mid }C{)}^{-(r(r-1)-2)\mathrm{/}2}$. Step 1.2 bounds ${\log }_2\mathrm{\mid }a\mathrm{\mid }$ by $O(m(J+1))$ and ${\log }_{2}C$ by $O(J+1)$, so ${\log }_2(1\mathrm{/}{\mathrm{\Delta }}_{\zeta })=O(m^3(J+1))$. Constants and degree-one polynomials need no separation estimate. This argument uses only the two actual local discriminant suppliers in [F4], with no resultant multiplicativity premise.

Every child side length lies between one third and two thirds of its parent side length. The initial side lengths have logarithm $O(H+1)$, by the original Cauchy bound. By step 2.2, after $D=\mathrm{poly}(n,H,b)$ levels every rectangle has diameter less than both $2^{-b}$ and the least distinct-root separation, and hence has count at most one. At every level at most $n$ positive-count rectangles exist, because their disjoint interiors each contain a root by [F2]. Each is replaced by at most four children, so there are $O(n(D+1))$ tested tree nodes, not $4^D$. A side at level $k$ has length at least its initial length times $3^{-k}$. The least dyadic denominator containing $N+1$ middle-third points therefore has exponent $O(H+k+\log (n+1))$; all coordinates have numerator and denominator length $T=O(H+D+\log (n+1))$. Even if the interval already contains many integers, only its first $N$ grid points are tested. This last restriction is essential: unrestricted lexicographic enumeration of all pairs in a very wide interval has no polynomial bound merely from a finite forbidden-coordinate count.

For root analysis with $n\ge 1$ (the constant case is settled in step 1.3), integer parts and grid generation are charged operations rather than free primitives. For a rational operand of numerator/denominator length at most $S$, find its bounding signed powers of two by doubling, then find its floor by binary search through the bounded integer interval, using $O(S+1)$ rational comparisons and additions; compare exactly with the resulting integer to obtain the ceiling and strict open-interval endpoints. Before denominator clearing, normalize the input $P$ by its nonzero leading coefficient in $O(n+1)$ rational field operations. If $U$ is its primitive integer representative with height $H$, each resulting monic coefficient ratio is $U_j\mathrm{/}{U}_n$, whose reduced numerator and denominator lengths are $O(H)$, independently of an arbitrarily large common rational scalar in the original $P$. The product of these at most $n+1$ denominators has length $O((n+1)H)$; using that product as common denominator gives integer coefficients of length $O((n+1)H)$. Their content is found by integer Euclidean gcds. Each division quotient is obtained by the bounded binary search just described, with polynomial-length integer operands. Integer remainders decrease in magnitude; after at most two nonterminal divisions the larger nonzero operand has at least halved (if the first remainder exceeds half the previous divisor, the next is smaller than its complement). Thus the number of divisions per gcd is linear in the initial operand length. Content removal and denominator clearing therefore cost $\mathrm{poly}(n,H)$ rational arithmetic and comparisons. The resulting primitive integer representative has height at most $H$ and is the input used in step 1.2 and step 2.2 and step 1.3 and step 3.1. In particular the outer $B$ is obtained in $\mathrm{poly}(H)$ operations from the original coefficient ratios. To generate a grid, begin with denominator one and double it, recomputing the strict lower/upper admissible integer numerators by this binary search, until their difference gives at least $N+1$ points. Step 3.1 bounds the number of doublings by $O(H+D+\log (n+1))$; every rational tested has polynomial numerator/denominator height in $n,H,b$, because it is a parent coordinate or width times such a dyadic denominator. Each integer-part search therefore costs $\mathrm{poly}(n,H,b)$ operations. Writing the first $N$ consecutive grid numerators costs $O(N)$ further additions. This bound also applies to any one-dimensional bounded grid once its coordinate-height and denominator-doubling bounds are established. The least $L$ in rounding is likewise found by sequential denominator doubling and exact comparison with $\tau \mathrm{/}[64(d+1)]$, with $O(\log (d+1)+{\log }_{+}(1\mathrm{/}\tau )+1)$ iterations; mesh-cell integer selection is the bounded binary search already charged in step 2.1. No floor, ceiling, or denominator selection is treated as unit-cost.

Each rational edge substitution $z=u+vt$ into $q$ has degree at most $n$. Clearing the rational denominators after binomial expansion gives real and imaginary integer polynomials with coefficient height $J_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}=\mathrm{poly}(n,H,T)$: each term uses at most $n$ coordinate factors of length $T$ and one $q$ coefficient of height $O(n(H+1))$, and there are at most $n+1$ terms per coefficient. This also applies to all proposed edges, since they use the same bounded-coordinate grids. Products of two such edge polynomials have polynomial degree and height. Their primitive square-free parts and gcds have polynomial output height by step 1.2, and their distinct roots have separation $2^{-\mathrm{poly}(n,H,T)}$ by step 2.2. The same facts apply to the gcds used for multiplicity tests, since the $m$-th derivative has coefficient height $O(H+n\log (n+1))$ and its gcd is a divisor of $q$.

Polynomial division of degree-at-most-$n$ rational polynomials takes $O(n^2)$ field operations, and Euclidean and negative-remainder chains have at most $n$ nonzero stages. A Sturm evaluation at rational endpoints thus takes $\mathrm{poly}(n)$ field operations and comparisons, regardless of the rational operand sizes. Square-free reduction and every boundary gcd test have the same polynomial arithmetic bound. Isolate each edge's $I$-roots on $[0,1]$ with the bounded one-dimensional search, first handling endpoint factors. The separation estimate for the square-free product $RI$ proves that $\mathrm{poly}(n,H,T)$ levels suffice to separate distinct $I$-roots and distinguish each $I$-root from all noncommon $R$-roots. A root $\alpha$ of $I$ on the edge is not a root of $R$ by the certified boundary test. Refinement therefore eventually puts $\alpha$ in an interval containing no $R$-root; [F3] certifies this last fact by zero $R$-root count, and a rational sample gives the nonzero sign of $R$ there. The sign change of $I$ is its two endpoint signs. At every level at most $n$ positive $I$-root intervals are retained (at most $2n$ when isolating the product). For a depth-$K$ interval in $[0,1]$, its length is at least $3^{-K}$ and its endpoints have dyadic height $O(K+\log (n+1))$; the grid denominator therefore requires $O(K+\log (n+1))$ doublings. The grid integer parts, ceilings, and written candidate coordinates are consequently charged by step 4.1 within the same polynomial operation bound. Endpoint handling, bounded-grid cuts, all root counts, and all refinements therefore take $\mathrm{poly}(n,H,T)$ rational arithmetic operations. A nonzero constant $I$ has no crossings; an identically zero $I$ was already excluded by the grid.

Combining $O(n(D+1))$ nodes, $N^2$ candidates per node, polynomial edge costs from step 5.1, and at most $n$ derivative/gcd multiplicity tests per retained root proves $\mathrm{poly}(n,H,b)$ rational arithmetic cost. All accepted boundaries satisfy exactly the conditions in [F2], so its winding, partition, and multiplicity arguments prove correctness unchanged. Substituting $n\le 2d$ and $H=O(d\log (d+1)+{\log }_{+}(1\mathrm{/}\delta )+1)$ from step 2.1 gives the claimed rounded-input root cost. The proof counts field operations; it never bounds Euclidean intermediate operand lengths or the precision required by later algebraic phase calculations, so it makes none of those additional assertions.