Exact interval boundedness by multiplicity strata and Sturm counts

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.