Quantum Signal Processing

Repeated use of [F1] and [F2] factors $H$ over $\mathbb{C}$ into linear factors with multiplicity. For a root $\zeta$ of multiplicity $m$, write $H=(x-\zeta {)}^{m}G$ with $G(\zeta )\mathrm{\ne }0$. Conjugating coefficients gives $H=(x-\bar{\zeta }{)}^m\bar{G}$ and $\bar{G}(\bar{\zeta })=\overline{G(\zeta )}\mathrm{\ne }0$, so the conjugate has exactly the same multiplicity. Thus, consistently with [F3], nonreal factors pair as $(x-(a+ib))(x-(a-ib))=(x-a{)}^2+b^2$, which is strictly positive for real $x$ when $b\mathrm{\ne }0$. The remaining factors are real linear factors $x-r$ for the real roots $r$.

On an open interval containing no real root, each real factor $x-r$ is either strictly positive throughout or strictly negative throughout by [F5]; every paired nonreal factor is positive throughout, and the real leading coefficient has fixed sign. Thus $H$ has one constant sign on that interval.

Each root value is zero, and the endpoints are checked separately. Step 2.1 shows each exact sample determines the sign on its entire root-free component, so the finite checks imply $H\ge 0$ on all of $[-1,1]$. If $H\ge 0$ everywhere, every sample and endpoint check plainly passes.

Each nonzero remainder has degree smaller than its divisor by [F1], so the chain terminates. The Euclidean algorithm preserves the common divisors of $f$ and $f^{\mathrm{\prime }}$, and their gcd is $1$ by the square-free hypothesis; hence the last nonzero member is a nonzero constant. A nonzero polynomial has only finitely many real roots: repeatedly divide by $t-c$ at each distinct root $c$ in $\mathbb{R}[t]$; each division lowers degree, so there can be no more roots than the original degree.

For each intermediate index $0<j<m$, the division identity is $f_{j-1}=q_j{f}_j-f_{j+1}$. If $f_j(c)=0$, then $f_{j-1}(c)=-f_{j+1}(c)$. No two consecutive members can vanish at one point: the identity would propagate a common zero to the final nonzero constant. Thus both neighbors are nonzero and have opposite signs at $c$.

A polynomial $h$ with $h(c)\mathrm{\ne }0$ keeps its sign in some interval about $c$: division by $t-c$ gives $h(t)=h(c)+(t-c)k(t)$, and the finite polynomial $k$ is bounded on $[c-1,c+1]$ by the sum of the absolute values of its coefficients times the corresponding powers of $\mathrm{\mid }c\mathrm{\mid }+1$. Taking $\mathrm{\mid }t-c\mathrm{\mid }$ small enough makes $\mathrm{\mid }(t-c)k(t)\mathrm{\mid }<\mathrm{\mid }h(c)\mathrm{\mid }$. Therefore, near a zero $c$ of an intermediate $f_j$, its two neighboring members keep their opposite signs; whether $f_j$ is positive, negative, or zero, those three entries contribute exactly one sign change. Intermediate zeros do not change $V$, including at an endpoint where $f_0$ is nonzero.

If $c$ is a root of $f_0=f$, then $f_1(c)=f^{\mathrm{\prime }}(c)\mathrm{\ne }0$: otherwise the Euclidean algorithm and [F1] give polynomials $u,v\in K[t]$ with $uf+v{f}^{\mathrm{\prime }}=1$, and evaluating at $c$ would give $0=1$. Division in $\mathbb{R}[t]$ gives $f(t)=(t-c)h(t)$ by [F6]. Expanding $h$ in powers of $t-c$, the coefficient of $(t-c)$ in $f$ is $h(c)$; the formal derivative formula [F2] says this coefficient is $f^{\mathrm{\prime }}(c)$. By step 3.1, $h$ keeps the sign of $f^{\mathrm{\prime }}(c)$ near $c$, so $f$ changes sign exactly once there, from the opposite sign to the same sign as $f^{\mathrm{\prime }}(c)$. The first pair $(f_0,f_1)$ therefore loses exactly one sign change as $t$ passes left to right through $c$.

The chain has finitely many roots by step 1.1. Every chain member is a real polynomial and so is continuous by [F4]; if its sign changed between two consecutive zeros, [F5] would give an additional zero. Thus between the finitely many chain-root locations all signs are fixed by [F6]. At every intermediate-member zero the variation is unchanged by step 3.1, and at every root of $f$ it decreases by one by step 4.1. Since $f(a)f(b)\mathrm{\ne }0$, neither endpoint is a root of $f$; summing the changes from $a$ to $b$ gives $V(a)-V(b)$ equal to the number of distinct roots of $f$ in $(a,b)$.

Set $f=1-p^2$ and $n=\mathrm{deg}f\le 2d$ when $f\mathrm{\ne }0$. The zero polynomial accepts; a nonzero constant accepts exactly when positive. Otherwise evaluate $f(-1),f(1)$ and reject a negative endpoint. Normalize $F=f\mathrm{/}\mathrm{lc}(f)$ to monic. Put $H_0=F$ and $H_j=\mathrm{monicgcd}(H_{j-1},F^{(j)})$ for $j=1,\dots ,n$, so $H_n=1$. For a complex root of $F$ of multiplicity $m$, its multiplicity in $H_j$ is $\max (m-j,0)$: while $j\le m$, [F3] gives derivative multiplicity exactly $m-j$, and once the root has left $H_{j-1}$ it cannot reappear in the gcd. Characteristic zero follows from $K\subseteq \mathbb{R}$.

Define $G_j=H_{j-1}\mathrm{/}{H}_j$ for $1\le j\le n$ and $G_{n+1}=1$. Each $G_j$ is monic squarefree with roots exactly the roots of $F$ of multiplicity at least $j$. Hence $S_j=G_j\mathrm{/}{G}_{j+1}$ is an exact polynomial quotient, with precisely the roots of original multiplicity $j$, each once. This follows over $\mathbb{C}$ by the multiplicity formula and factorization in [F2], and division in $K[x]$ has zero remainder because its scalar extension does. The product $V={\prod }_{j\text{ odd}}{S}_j$ is monic squarefree with exactly the odd-multiplicity roots of $f$; the empty product is $1$. These are gcd, derivative, exact division and multiplication operations over $K$, with no individual roots computed.

Remove $x-1$ and $x+1$ from $V$ whenever the corresponding endpoint is a root, each at most once, obtaining $W$. If $W$ is nonconstant, its endpoints are nonzero, and [F1] counts its distinct real roots in $(-1,1)$; for constant $W$ the count is zero. A positive count rejects: near an interior odd-multiplicity root $r$, write $f(x)=(x-r{)}^{m}g(x)$ with $g(r)\mathrm{\ne }0$. Continuity gives a strict fixed sign for $g$ near $r$, so the odd power gives opposite signs for $f$ on the two sides, both inside the interval.

If the count is zero, all interior real roots of $f$ have even multiplicity. Between successive roots its sign is constant by [F4], and crossing an even root preserves that sign by the factorization from step 3.1. Thus all nonroot points of $(-1,1)$ have one strict sign. Among the $n+1$ fixed rational points $t_j=-1+2j\mathrm{/}(n+2)$, $j=1,\dots ,n+1$, at least one is not a root by [F4]. Find the first by exact Horner evaluation and accept exactly when its value is positive. All interior values are then positive or zero, and the checked endpoint values are nonnegative. Conversely nonnegative $f$ passes all checks. Since $f\ge 0$ is equivalent to $\mathrm{\mid }p\mathrm{\mid }\le 1$, this is the required exact decision, including invalid inputs.

All polynomial degrees are at most $n$. Schoolbook long division costs $O((n+1{)}^2)$ field operations. A gcd or signed Sturm chain has at most $n+1$ degree decreases, costing $O((n+1{)}^3)$ operations/tests including leading-zero detection. There are $n$ gcd computations; derivatives, exact quotients and products cost $O((n+1{)}^3)$ in total, and endpoint/sample evaluation costs $O((n+1{)}^2)$. Hence the total is $O((n+1{)}^4)=O((d+1{)}^4)$. Every normalization divides only a verified nonzero leading coefficient. Exact divisibility and polynomial identities follow from steps 1.1–2.1 and may also be verified by multiplication within this budget. No refinement loop, coordinate sign oracle or implementation bit-time bound is used.

The Euclidean gcd in [F1] terminates because each nonzero remainder has smaller degree by [F3]. By induction on degree, [F5] and [F3] factor $p$ over the field $\mathbb{C}$ [F10]: take a root, divide by its linear factor, and repeat on the lower-degree quotient. At a root of multiplicity $m$, write $p(z)=(z-\zeta {)}^{m}h(z)$ with $h(\zeta )\mathrm{\ne }0$. Differentiation by [F4] gives $p^{(j)}(\zeta )=0$ for $j<m$ and $p^{(m)}(\zeta )=m!h(\zeta )\mathrm{\ne }0$. Also $p^{\mathrm{\prime }}$ has multiplicity exactly $m-1$ at $\zeta$, so $p\mathrm{/}\gcd (p,p^{\mathrm{\prime }})$ contains that root once. Thus square-free reduction preserves exactly the distinct roots, and the least derivative order with no common root at $\zeta$ is its original multiplicity. It remains to verify the membership implementation.

Put $M={\max }_{j<n}\mathrm{\mid }{a}_j\mathrm{/}{a}_n\mathrm{\mid }$ for a degree-$n$ polynomial. If $\mathrm{\mid }z\mathrm{\mid }>1+M$, then $\mathrm{\mid }z\mathrm{\mid }>1$ and ${\sum }_{j<n}\mathrm{\mid }{a}_j{z}^j\mathrm{\mid }\le \mathrm{\mid }{a}_n\mathrm{\mid }M{\sum }_{j<n}\mathrm{\mid }z{\mathrm{\mid }}^j=\mathrm{\mid }{a}_n\mathrm{\mid }M\frac{\mathrm{\mid }z{\mathrm{\mid }}^n-1}{\mathrm{\mid }z\mathrm{\mid }-1}<\mathrm{\mid }{a}_n\mathrm{\mid }\mathrm{\mid }z{\mathrm{\mid }}^n\mathrm{.}$ Hence $p(z)\mathrm{\ne }0$. The exact comparisons and increasing rational enumeration in [F1] therefore find a strict rational bound; any rectangle whose two half-widths exceed that bound contains every root in its interior.

For nonconstant square-free $q$, each root has finite real and imaginary coordinates, so only finitely many vertical or horizontal offsets pass through a root. Only finitely many horizontal offsets can make $\mathrm{Im}q(t+iy)$ identically zero as a polynomial in $t$: otherwise every coefficient polynomial in $y$ would vanish identically, which would force $\mathrm{Im}q(x+iy)$ to be the zero bivariate polynomial; writing $q$ first on the real axis and then differentiating its coefficient expansion in $y$ shows this is impossible for nonconstant $q$. The vertical case is identical. Each vertex condition $\mathrm{Im}q(\pm X\pm iY)=0$ is the zero set of a nonzero polynomial in $(X,Y)$. A nonzero bivariate polynomial cannot vanish on an open rectangle: fixing one coordinate on an interval makes each coefficient polynomial in the other coordinate vanish on an interval and hence identically. The finitely many forbidden coordinate lines and vertex zero sets thus cannot fill the open rational search region $X,Y>B$. Rational pairs are dense there, so the outer-bound enumeration in [F1] finds an admissible rectangle.

On each edge, simultaneous vanishing of $R$ and $I$ is equivalent to a root of their gcd. The vertex test excludes endpoint roots, so [F2] decides whether such a root lies in the edge interior. At each zero of $I$, boundary-root-freeness implies $R\mathrm{\ne }0$; the sign of this exact nonzero algebraic value is decidable by refinement, and the square-free Sturm sequence isolates every zero of $I$. Thus every crossing and its direction in [F1] is finitely and exactly determined.

REALROOTS is correct at each subdivision by [F2]: its square-free polynomial first records any roots at $-1$ and $1$, divides out those endpoint linear factors using [F3], and applies Sturm to the residual, whose endpoints are root-free. The selected interior cut is not a root, so the two open children partition the residual roots. The polynomial has finitely many distinct roots by repeated division and degree decrease [F3]. If there are at least two, the minimum separation of its finite root set is positive in the real order [F11]; repeated bisection eventually makes every positive-count interval narrower than both that separation and the requested width. Each level has finitely many intervals, so the recursion terminates and outputs disjoint isolators for all real roots in $(-1,1)$, together with the endpoint roots tested separately.

In a parent rectangle already satisfying the admissibility tests, the same finite-exclusion argument gives an admissible cut pair in the product of the two middle-third intervals. Cut coordinates that pass through roots are finite in number; offsets making an edge imaginary restriction identically zero are finite; vertex-zero conditions along an old side are nonzero univariate polynomials because that side's imaginary restriction is not identically zero; and conditions at a new cut intersection are nonzero bivariate polynomials by the argument in step 1.3. Their finite union has empty interior. The exhaustive dyadic enumeration therefore finds cuts for which all four child boundaries satisfy the exact tests.

Let $\gamma (t)=q(z(t))$ traverse an admissible rectangle counterclockwise. Each edge restriction is polynomial, avoids zero, has nonzero imaginary-part polynomial, and has no endpoint with zero imaginary part. It therefore meets the positive real ray only at the finitely many interior zeros isolated in step 1.4. For $w\mathrm{\notin }[0,\mathrm{\infty })$, define ${\mathrm{Arg}}_{+}(w)$ as the unique $\theta \in (0,2\pi )$ in its polar representation; existence follows by applying [F8] to $-w$ and adding $\pi$. This branch is continuous: on each open semicircle avoiding the cut, the unit-circle parametrization is one-to-one, and the chord identity $\mathrm{\mid }{e}^{i\theta }-e^{i{\theta }_0}\mathrm{\mid }=2\mathrm{\mid }\sin ((\theta -{\theta }_0)\mathrm{/}2)\mathrm{\mid }$ shows that nearby circle points have nearby angles. Thus on every subarc between positive-ray intersections, ${\mathrm{Arg}}_{+}(\gamma (t))$ is continuous. At an upward crossing its one-sided values approach $2\pi$ and $0$, so adding $2\pi$ to the subsequent branch continues the lift and increases its integer offset by one. A downward crossing decreases the offset by one, and a non-crossing contact leaves it unchanged. The curve is closed and its starting vertex is off the ray, so the lifted argument's total increment divided by $2\pi$ is exactly the signed crossing sum in [F1].

For nonzero real $h$, REALROOTS returns all roots in $[-1,1]$ by step 1.5, and the additional isolator refinement terminates: the finite distinct interior roots have positive distances from each other and from $-1,1$, and each refined interval contracts by at least $2\mathrm{/}3$. Thus their closures eventually separate strictly. Every component between consecutive actual roots contains the rational sample in the gap between their isolators; the two outer components are treated the same way. By [F9] this sample determines the sign on that whole component, including the portions inside isolators up to their roots; the root values themselves are zero and the endpoints are tested separately. Thus the routine accepts exactly when $h\ge 0$ on the whole interval. The $h=0$ branch accepts directly.

Step 1.1 factors $q(z)=c{\prod }_j(z-{\zeta }_j)$ over its distinct roots. Continuous argument lifts add under multiplication, so the winding increment of $q$ is the sum of the increments of these linear factors. Fix one root $\zeta$ not on the rectangle boundary. Enumerate rational directions $(r,s)$ with $(r,s)\mathrm{\ne }(0,0)$ by increasing positive denominator and then numerator pair, and take the first whose line is not parallel to a rectangle side and whose line through $\zeta$ contains no rectangle vertex. Only finitely many directions are forbidden, while rational directions are dense, so this search terminates. Normalize the chosen vector to a unit scalar $u$; its norm is nonzero. Rotating the curve $z-\zeta$ by the constant unit scalar $\bar{u}$ does not change its total argument increment, and makes the chosen direction the positive real ray. If $\zeta$ is inside the convex rectangle, the ray leaves it exactly once; counterclockwise orientation puts the interior on the left, so this outward crossing is upward and contributes $+1$. If $\zeta$ is outside, the ray either misses the rectangle or enters and exits it, contributing a downward crossing and an upward crossing whose signs cancel. Thus the winding increment of $z-\zeta$ divided by $2\pi$ is $1$ exactly for an interior root and $0$ otherwise. Summing over the distinct roots shows that the signed crossing count of $q$ in step 2.2 is exactly the number of roots inside the rectangle. Since $q$ is square-free, this is the number of distinct roots.

For a retained rectangle containing the unique root $\zeta$ of $q$, let $h=\gcd (q,p^{(m)})$, $1\le m\le n$. This gcd is nonzero. A constant $h$ has zero roots; otherwise $h$ divides square-free $q$, so it is square-free and has no boundary root. At a vertex $v$, $\mathrm{Im}((1+it)h(v))=\mathrm{Im}h(v)+t\mathrm{Re}h(v)$ vanishes for at most one real $t$, since $h(v)\mathrm{\ne }0$. On an edge write $h=R+iI$. The polynomial $I+tR$ can be identically zero for at most one $t$: two such values would force $R=I=0$, contradicting boundary-root-freeness. Thus the four vertices and four edges exclude at most eight scalars, and one of $0,\dots ,8$ passes all exact tests. The nonzero scalar $1+it$ preserves roots and square-freeness. Steps 1.4, 2.2 and 3.1 therefore count its roots on the unchanged rectangle, giving one exactly when $h(\zeta )=0$. Each derivative test terminates, and step 1.1 gives the least zero-count order as the original multiplicity, by $m=n$. For REALROOTS, root-free interval endpoints also remain root-free for gcd divisors; [F2] decides interior membership, constants have zero count, and endpoint singletons use direct derivative evaluation.

A cut line contains no root by step 2.1, and each parent boundary is root-free by admissibility. The four child interiors therefore partition the parent's roots without omission or duplication; their exact counts are correct by step 3.1. Discarding count-zero children and continuing preserves exactly the roots inside the initial rectangle, which contains all roots by step 1.2.

Each subdivision cut lies strictly inside the corresponding middle third, so each child's side lengths are at most $2\mathrm{/}3$ of its parent's. The finite set of distinct roots has a positive minimum pairwise distance when it has at least two elements. After finitely many levels, every rectangle has diameter below that separation and below $2^{-b}$; hence it cannot contain two roots. If there is one root, only the precision condition is needed. The finite four-child tree then terminates. Every retained rectangle contains exactly one root, their open interiors are pairwise disjoint, and step 4.1 supplies the correct multiplicity.

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.