History and significance

Tarski proved decidability of the first-order theory of real closed fields (Tarski 1951). Collins’s cylindrical algebraic decomposition gave a geometric method for eliminating quantifiers (Collins 1975), and Canny established the polynomial-space upper bound for the existential fragment (Canny 1988). For each fixed number of real quantifier blocks, Renegar’s decision bounds yield a polynomial-space algorithm (Renegar 1992, Theorem 1.1). This applies to the circuit encoding above: the quartic reduction in Lemma 22 preserves the two quantifier blocks. Our theorem places this two-block language in a fixed level of the counting hierarchy. Real quantifier hierarchies distinguish the number and order of blocks; Schaefer and Štefankovič develop their finite-encoding formulation (Schaefer and Štefankovič 2024). The existential class already captures many geometric realization and continuous feasibility problems; Schaefer, Cardinal, and Miltzow survey these connections (Schaefer et al. 2026).

The counting hierarchy gives a way to decide some exact algebraic questions without constructing their enormous intermediate integers. Allender, Bürgisser, Kjeldgaard-Pedersen, and Miltersen proved that \(\mathsf{PosSLP}\)—positivity of the integer output of a division-free straight-line program—belongs to \(\mathsf{CH}\) (Allender et al. 2009). Their modular-product and approximate Chinese-remainder techniques are the counting tools behind our treatment of implicit polynomial families. Every fixed counting level lies in \(\mathsf{PSPACE}\): a depth-first simulation enumerates random choices and answers the fixed-depth oracle queries using polynomial space.

Recent counting-hierarchy bounds address other polynomial feasibility problems. Andrews, Garg, and Schost place Hilbert’s Nullstellensatz over \(\mathbb Q\) and several other fields in \(\mathsf{CH}\) (Andrews et al. 2026); the common zeros there lie in an algebraic closure. Balaji, Shirmohammadi, Tavenas, and Worrell prove counting-hierarchy bounds for approximate polynomial satisfiability over \(\mathbb Q\) and finite fields (Balaji et al. 2026), where the question is membership of zero in the Zariski closure of a polynomial image over the algebraic closure. Exact real quantification must also control the reality of solutions, their attainment, and the dependence of a quantified fiber on its parameters. These are the issues addressed by the argument here.

Our algebraic tools belong to the critical-point and deformation methods of real algebraic geometry (Basu et al. 2006). Multiplication determinants are evaluated through the classical relation between residues and traces (Scheja and Storch 1975; Cattani et al. 1996). We prove the needed identities and computational rules directly, including their behavior under parameter specialization. These computational rules apply to implicitly represented families that need not have short coefficient lists or arithmetic circuits.

From quantified fibers to short algebraic witnesses

Fix the existential tuple \(x\). Introducing gate and auxiliary variables turns failure of \(\Phi(x,y)\) into a real zero of a nonnegative quartic \(F(x,z)\), where \(z\) includes \(y\) and the auxiliaries. Thus we seek an \(x\) for which the fiber \(F(x,\cdot)\) has no real zero. Call such an \(x\) good. Merely testing fibers does not provide a finite description of a good parameter. The main geometric argument produces such descriptions.

For \(u\ge0\), consider the minimum \[m_x(u)=\min_{z\in\mathbb R^n}\left(\sum_{i=1}^n z_i^6+6uF(x,z)\right).\] The sixth powers keep bounded sublevel sets compact. It follows that \(m_x(u)\) remains bounded as \(u\to\infty\) precisely when the fiber has a zero. At a minimizing point the critical equations have pure fifth powers as their leading terms. Their quotient algebra has dimension \(D=5^n\), and multiplication by the minimized polynomial has a monic characteristic polynomial \(Q(x,u,Y)\) satisfying \(Q(x,u,m_x(u))=0\).

This identity supplies a uniform growth test: \(x\) is good precisely when \(m_x(v^{D+1})>v\) for all sufficiently large \(v\). Form \[E(x,v)=Q(x,v^{D+1},v).\] The coefficient of \(v^D\) is always \(1\), so \(E(x,\cdot)\) is never zero. Partition parameter space into the sets on which \(E(x,\cdot)\) has each possible degree. On each such degree piece, polynomial root bounds give a locally uniform threshold beyond which \(E\) does not vanish. Continuity of the minimum then makes goodness locally constant on that piece. Introducing the reciprocal of its leading coefficient realizes the piece as a closed algebraic set. Both the good and nongood parts of this lift are closed.

A second minimization argument now extracts candidate coordinates. Choose a compact sublevel set of a coercive polynomial with a good point in its interior. Within this set, the good and nongood parts of the lift are separated. Minimize the coercive polynomial plus a growing nonnegative polynomial penalty that vanishes exactly on the lift, restricting to a compact neighborhood that avoids the nongood part. A subsequence of minimizers converges to a good point and is eventually interior to the neighborhood, so these minimizers satisfy the unconstrained critical equations. The highest parameter coefficients of their coordinate characteristic polynomials therefore vanish at the limit coordinates. This produces finitely indexed univariate polynomial families whose roots contain the coordinates of a suitable witness, without computing the good part or its connected components. Section 6 proves this geometric construction and completes the main theorem.

Two computational ingredients make these candidate coordinates usable. First, all polynomials just described have degree and logarithmic coefficient bounds with polynomial-length binary encodings, and their finite-field evaluations lie at fixed counting levels. We call such families controlled. Sections 2 and 3 establish their closure rules and the evaluation of multiplication determinants without constructing the matrices.

Second, a chosen real root needs a short description even when its polynomial has exponential degree. Derivative signs distinguish real roots, as in Thom encodings (Basu et al. 2006), but the full sign string can be too long. Section 4 compresses that string to a weighted integer sum with weights computed modulo a short prime, and realizes the resulting label by a polynomial positivity test. Every desired real root can be isolated, including a root of a polynomial with multiplicities. The sign approximation uses geometric products of the type studied by Beigel, Reingold, and Spielman (Beigel et al. 1995). This arbitrary-root labeling rule and the coordinate construction are reusable ingredients of the proof.

Finally, Section 5 proves an existential decision procedure for controlled families. For a guessed coordinate description, we use it twice: the described parameter set must be nonempty, and it must contain no parameter with a zero of \(F\). A suitable choice of root labels singles out the good point constructed above. All choices have polynomial total bit length, and all family constructions have fixed depth. Counting over these choices therefore gives one fixed level of the hierarchy.

Uniformity and counting

Recall that \(\mathsf C_{0}\mathsf P=\mathsf P\) and \(\mathsf C_{a+1}\mathsf P=\bigcup_{A\in\mathsf C_{a}\mathsf P}\mathsf{PP}^A\). Put \[\mathsf F_{a}=\bigcup_{A\in\mathsf C_{a}\mathsf P}\mathsf{FP}^A.\] A function in \(\mathsf F_{a}\) has polynomially bounded output length and is computed in polynomial bit time with one fixed oracle in \(\mathsf C_{a}\mathsf P\). We call a function available if it belongs to \(\mathsf F_{a}\) for some fixed \(a\). A decision made by such a function belongs to \(\mathsf C_{a+1}\mathsf P\): a probabilistic oracle machine can perform the same computation and ignore its random bits.

The levels \(\mathsf C_{a}\mathsf P\) are increasing and are closed under finite tagged unions. For the second assertion, induct on \(a\), select the machine indicated by the tag, and replace its oracle by the tagged union of the finitely many lower-level oracles. Padding with unused random bits gives one polynomial random-bit bound. Consequently, polynomial-time computation using any fixed finite collection of available functions again gives an available function. This observation permits adaptive calls; it makes no assertion that adaptive access to \(\mathsf{PP}\) collapses to \(\mathsf{PP}\).

An integer or index is called short if its binary encoding has length bounded by a fixed polynomial in the relevant input length. For a tuple, this means its total encoding length. A short integer may have exponentially large value. Every index range below has a fixed polynomial encoding bound, and every machine is fixed independently of the input. All algorithms are total: length and range checks prevent invalid accesses, and undefined arithmetic operations receive fixed defaults. Their asserted algebraic guarantees apply on the specified domains.

A sum over a tuple of indices uses one application of Lemma 2, as long as the tuple has polynomial total length. In particular, the number of counting levels does not grow with the number of coordinates in a grid.

If a function receives \(p\) as an additional input, its polynomial bounds may use \(|w|+\operatorname{bitlength}(p)\). An application on a smaller input, however, must supply \(p\) with length polynomial in that smaller input. We will distinguish such evaluation inputs from the data that describe the underlying polynomial family.

Polynomial families accessible by evaluation

Counting and finite-field products allow algebraic constructions without writing their coefficients. We now specify exactly what is retained about a polynomial, and prove that coefficient extraction and differentiation are compatible with this information. For an integer polynomial \(V\), write \(\left\lVert V\right\rVert_1\) for the sum of the absolute values of all its coefficients, in all its indeterminates.

The word \(w\) may include discrete choices and short indices. When members \(V_{w,i}\) are summed or multiplied over an index set, the total length of \(i\) is bounded by a fixed polynomial in \(|w|\), evaluation is uniform in \(i\), and we use bounds uniform over the allowed indices. For example, if \(|i|\le q(|w|)\) and each of \(d,b,\lambda\) has at most \(r(|w|+|i|)\) bits, for fixed increasing polynomials \(q,r\), then \(2^{r(|w|+q(|w|))}\) bounds all three uniformly. This enlarged bound is computable from \(w\) alone, without enumerating the indices or testing which members will be used. All families in the argument arise from fixed constructions; no machine describing a family is supplied as part of the input.

Ordinarily encoded short integers are controlled constant families. The same holds for much larger constants such as \(2^e\) with a short nonnegative exponent \(e\): its logarithmic norm bound is \(e\), and its residue is obtained by modular powering. Such a constant is used through its residues and bounds, not through its full binary expansion.

Recovering an integer sign

The closure rules give modular evaluations and magnitude bounds for integer families, including integers too large to write down. It remains to recover their signs. A collection of prime residues mathematically determines such an integer, but constructing its full Chinese-remainder representative may require exponentially many bits. We instead approximate the integer divided by a sufficiently large prime product, modulo one. Successive doublings bring a nonzero quotient far enough from zero to reveal its sign.

We can now manipulate polynomials through short bounds and modular evaluation procedures. The next step is to show that a characteristic polynomial of multiplication in a finite polynomial quotient admits exactly this description, even when the quotient has exponentially large rank.

A basis and a coefficient functional

Let \(S\) be a commutative ring with identity, let \(n\ge1\) and \(\ell\ge2\), and suppose that \(r_1,\ldots,r_n\in S[x_1,\ldots,x_n]\) satisfy \(\deg_x r_i<\ell\). Set \[ f_i=x_i^\ell-r_i,\qquad \mathcal A=S[x_1,\ldots,x_n]/(f_1,\ldots,f_n),\qquad D=\ell^n,\qquad \tau=(\ell-1,\ldots,\ell-1). \tag{9}\] For a multi-index \(a\), write \(|a|=\sum_i a_i\) and \(x^a=\prod_i x_i^{a_i}\). We will show that the \(D\) monomials \(x^a\) with \(0\le a_i<\ell\) form an \(S\)-basis of \(\mathcal A\).

We use formal Laurent sums whose total degrees are bounded above and whose support in each total degree is finite. Addition and multiplication are well defined: for any prescribed total degree, only finitely many pairs of degrees and finitely many terms can contribute. Since \(r_i x_i^{-\ell}\) has total degree at most \(-1\), its geometric series is such a Laurent sum. Define the \(S\)-linear functional \[ \mathcal L(v)= [x_1^{-1}\cdots x_n^{-1}] v(x)\prod_{i=1}^n \left(x_i^{-\ell}\sum_{j\ge0} (r_i(x)x_i^{-\ell})^j\right). \tag{10}\] This is a formal coefficient extraction, requiring neither convergence nor division in \(S\). It is a concrete residue formula of the type studied in (Cattani et al. 1996); we prove the facts needed here directly over \(S\).

A trace formula and its spectral consequences

Let \(M_v\) denote the matrix of multiplication by the class of \(v\in S[x]\) in this basis, and put \[ J(x)=\det\bigl(\partial_j f_i(x)\bigr)_{1\le i,j\le n}. \tag{14}\] The following classical trace–residue identity is associated with Scheja and Storch (Scheja and Storch 1975); see also (Cattani et al. 1996, Author version, Equation (4.7)). Its proof uses the dual-basis property of a Bezoutian, a construction developed further in (Elkadi and Mourrain 2005, sec. 3.3). The explicit proof matters here because we need arbitrary coefficient rings and specialization at multiple zeros.

Both the basis and the trace formula commute with every change of coefficient ring. In particular, parameters may be specialized and coefficients reduced modulo a prime without assuming that the common zeros are distinct. The following elementary fact explains how the characteristic polynomials will encode real critical values.

Characteristic coefficients from finite-field evaluations

We now turn the trace formula into a uniform computation. All the large sums below are indexed by tuples of polynomial bit length. Each entire tuple is a single counting index; the number of its coordinates does not increase the number of counting levels. We state the evaluation bound separately, so that later applications with elementary evaluators can retain their sharper level count.

The determinant rule for controlled families

The preceding computation provides residues. To obtain a controlled family, we also need degree and coefficient-norm bounds before specialization. The decreasing degree in the reduction relations supplies these bounds directly.

The rule applies equally to characteristic polynomials of coordinate multiplication and of a polynomial objective. In both cases it replaces an exponentially large matrix by finite-field evaluations with a fixed number of counting stages. Its coefficient polynomials are controlled by Proposition 6, so the rule may be used again at later, fixed stages of the construction.

Values and derivative signs at algebraic roots

The value bound must allow nonmonic polynomials and multiple roots. The product argument below treats both without taking a squarefree part. Throughout this section, the norm of a polynomial is the sum of the absolute values of its coefficients.

We shall use this lemma for \(b_0\) and for \(b_j=P^{(j)}\), \(1\le j\le d\). If \(P\) and \(b_0\) both have norm at most \(2^b\), these tests have norm at most \(2^{b+d^2}\): a derivative multiplies each coefficient by a falling factorial bounded by \(d^d\le2^{d^2}\). Zero derivatives cause no difficulty.

The next fact is the uniqueness underlying Thom encodings; see (Basu et al. 2006, Proposition 2.28). Its short proof also explains why repeated roots are allowed.

Compressing derivative-sign strings

Fix a nonzero polynomial \(P\) of degree at most \(d\), with \(d\ge2\), and write \(b_j=P^{(j)}\) for \(1\le j\le d\). The derivative signs distinguish its roots by Lemma 16, but we cannot record all \(d\) signs. Instead we encode them by a weighted integer sum.

A label is a triple \(a=(\mu,\gamma,S_*)\) in the range \[ \begin{gathered} W_*=2\max(16,d^3)^4,\\ 3\le\mu\le W_*,\qquad 0\le\gamma<\mu,\qquad |S_*|\le dW_*. \end{gathered} \tag{26}\] For every such label define integer weights \[w_j=\gamma^j\bmod\mu,\qquad 0\le w_j<\mu.\] At a real root \(\alpha\) of a nonzero \(P\), the associated weighted sum is \[S(\alpha)=\sum_{j=1}^d w_j\mathop{\mathrm{sgn}}b_j(\alpha).\] This sum is an integer in \([-dW_*,dW_*]\). The construction below accepts precisely those roots for which \(S(\alpha)=S_*\) and \(b_0(\alpha)>0\).

We claim that some choices of \(\mu,\gamma\) make \(S\) injective on the distinct real roots of \(P\). We use polynomial evaluation to distinguish the strings, the fingerprinting idea underlying (Schwartz 1980). The elementary prime-count estimate in the proof of Proposition 7, with \(Z=\max(16,d^3)\), supplies a prime \(\mu\) with \(d^3<\mu\le W_*\). For two distinct derivative-sign strings \(\sigma,\tau\in\{-1,0,1\}^d\), the polynomial \[\sum_{j=1}^d(\sigma_j-\tau_j)X^j\] is nonzero over \(\mathbb F_\mu\): some coefficient belongs to \(\{-2,-1,1,2\}\) and \(\mu>2\). It has at most \(d\) zeros in that field. There are at most \(d\) distinct real roots, so fewer than \(d^3\) values of \(\gamma\) are forbidden by all pairs together. Choose a remaining \(\gamma\in\mathbb F_\mu\). The sums at distinct roots are then distinct modulo \(\mu\), hence distinct as integers. For a prescribed root \(\alpha\), taking \(S_*=S(\alpha)\) selects it uniquely. Only three short integers are recorded; the derivative-sign string is never stored.

The label has \(O(\log d)\) bits, even though the derivative-sign string can have length \(d\). We next express the condition \(S(\alpha)=S_*\), together with \(b_0(\alpha)>0\), by one polynomial positivity test.

Approximating the sign function

The algebraic values in Lemma 15 can be extremely small, but their binary exponents have short descriptions. A product over these exponents gives a rational function that recognizes their signs with a uniform error. This sign approximation and the subsequent clearing of positive denominators are closely related to the method of Beigel, Reingold, and Spielman (Beigel et al. 1995); we give the needed construction explicitly.

Constructing and verifying the labels

A minimum that detects a zero

Choose an odd integer \(\ell\ge3\) larger than the degree bound for \(F\). It has a polynomial-length binary encoding and is computable in polynomial time. For \(1\le i\le n\), put \(a_i=(4\ell)^i\) and define \[ \begin{split} G(x)&=\sum_{i=1}^n \bigl(x_i^{\ell+1}-(\ell+1)a_i^\ell x_i +(\ell+1)a_i^{\ell+1}\bigr),\\ h_u(x)&=G(x)+(\ell+1)uF(x),\\ r_i(x,u)&=a_i^\ell-u\,\partial_iF(x),\qquad f_i(x,u)=x_i^\ell-r_i(x,u). \end{split} \tag{30}\] Coercive perturbations and critical-point equations are classical tools in real algebraic geometry; see, for example, Basu et al. (2006). Here the separated constants \(a_i\) serve an additional purpose: the critical values at \(u=0\) will all be distinct.

All polynomials in Equation (30), including \(u\) as an indeterminate, are controlled. Indeed, the \(a_i\) themselves have polynomial bit length, and their displayed powers are allowed by Proposition 6. Moreover, \(\deg_x r_i<\ell\). Apply Proposition 13 to the relations \(f_1,\ldots,f_n\) and to multiplication by \(h_u\), obtaining \[ Q(u,y)=\det(yI-M_{h_u})\in\mathbb Z[u,y], \qquad D=\ell^n. \tag{31}\] This is a controlled polynomial, monic of degree \(D\) in \(y\).

Each summand of \(G\) has derivative \((\ell+1)(x_i^\ell-a_i^\ell)\). Since \(\ell\) is odd, its unique real minimum occurs at \(x_i=a_i\) and equals \(a_i^{\ell+1}\). The even leading power makes \(G\) coercive: \(G(x)\to+\infty\) as \(\lVert x\rVert\to\infty\). In particular, \[ h_u(x)\ge G(x)\ge\sum_{i=1}^n a_i^{\ell+1}>0 \qquad(u\ge0). \tag{32}\]

Replacing the limit by one specialization

The boundedness criterion is not yet a finite test. We will choose a value cutoff \(R\) and a parameter \(U\) so that a bounded minimum lies below \(R\), whereas a divergent minimum exceeds \(R\) by parameter \(U\). A finite limit of \(m(u)\) must be a root of the leading coefficient of \(Q\) as a polynomial in \(u\), itself a polynomial in \(y\), so a coefficient bound supplies \(R\). Once \(R\) is chosen, taking \(U\) larger than every positive real root of the nonzero polynomial \(Q(u,R)\) prevents the minimum from crossing \(R\) after \(U\). We also take \(U\) beyond every parameter where \(Q(u,y)\) has a repeated root: Lemma 11 will then realize every real root of \(Q(U,y)\) as a value at a real critical point. We first bound those exceptional parameters.

Recall the elementary root bound: a nonzero integer polynomial of coefficient norm at most \(2^b\) has all its complex roots in \(|z|\le1+2^b\). For \(|z|>1+2^b\), its leading coefficient has modulus at least \(1\) and the geometric-series estimate makes its leading term strictly larger than the sum of the lower terms.

Choose a polynomial-time computable short bound \(H\) with \(\left\lVert Q\right\rVert_1\le2^H\), as supplied by Proposition 13, and let \(V\) be a short bound on \(\deg_uQ\). Define \[ \begin{aligned} \rho&=H+4,& R&=2^\rho,\\ \sigma&=H_\Delta+H+D\rho+4,& U&=2^\sigma,\\ K&=H+\sigma V. \end{aligned} \tag{36}\] The exponents and bounds in this display are short integers. The integers \(R\) and \(U\) are used as controlled constant families; their binary expansions need not have polynomial length.

One root label and one determinant sign

Proposition 21 has reduced feasibility to the existence of a real root of the controlled polynomial \(q\) below \(R\). Apply Proposition 14 to \(q\) with \(b_0(y)=R-y\). It supplies a family of integer polynomials \(L\), indexed by short labels, with the following properties at real roots \(\alpha\) of \(q\):

• \(L(\alpha)\ge\tfrac12\) or \(L(\alpha)\le-\tfrac12\);

• \(L(\alpha)>0\) implies \(\alpha<R\);

• each real root \(\alpha<R\) has a label whose polynomial is positive at that root and negative at every other real root.

The family is controlled uniformly in the label. Multiplying \(L\) by \(-4D\) gives a sign margin large enough that a small integer shift preserves all real-root signs. We use that shift to avoid zero factors at nonreal roots. For a short choice \(e\in\{0,\ldots,D\}\), define \[ g(y)=-4DL(y)+e, \qquad X=\det M_{g(h_U)}. \tag{39}\] The multiplication matrices here use the relations specialized at \(u=U\). They respect polynomial composition, and hence \[ X=\det g(M_{h_U}) =\prod_{q(\alpha)=0}g(\alpha)\in\mathbb Z. \tag{40}\] The product runs over all complex roots of \(q\).

At a real root, the label margin gives \[L(\alpha)>0\ \Longrightarrow\ g(\alpha)\le-D<0, \qquad L(\alpha)<0\ \Longrightarrow\ g(\alpha)\ge2D>0.\] Since \(g\) has real coefficients, a conjugate nonreal pair contributes \(g(\alpha)g(\overline\alpha)=|g(\alpha)|^2\ge0\) to Equation (40). Consequently \(X<0\) implies that some real root has \(g(\alpha)<0\), and such a root lies below \(R\).

Conversely, if \(q\) has a real root below \(R\), choose a label positive at exactly that real root. Since \(q\) is squarefree, every \(e\in\{0,\ldots,D\}\) then gives exactly one negative real factor and all other real factors positive. At any fixed nonreal root, \(g(\alpha)=0\) excludes at most one value of \(e\). Since there are at most \(D\) such roots and \(D+1\) available choices, some \(e\) leaves every nonreal factor nonzero. Each conjugate pair now contributes a positive factor, so \(X<0\). We have proved \[ F\text{ has a real zero} \quad\Longleftrightarrow\quad X<0\text{ for some short label and some }0\le e\le D. \tag{41}\]

Empty fibers and a growing minimum

First encode failure of the universal condition by a single polynomial. The encoding must work for every fixed \(x\), because \(x\) remains a parameter throughout the construction.

Call \(x\) good if \(F(x,\cdot)\) has no real zero. By Lemma 22, our task is to decide whether a good parameter exists. Introduce a nonnegative real parameter \(u\) and set \[ h(x,u,z)=\sum_{i=1}^n z_i^6+6uF(x,z), \qquad m_x(u)=\min_{z\in\mathbb R^n}h(x,u,z). \tag{43}\] The coercive term prevents minimizers from escaping whenever their values remain bounded. In particular, the minimum exists and is nonnegative. For fixed \(x\) it is nondecreasing in \(u\).

The function \((x,u)\mapsto m_x(u)\) is continuous on \(\mathbb R^r\times[0,\infty)\). Indeed, on a compact parameter neighborhood, comparison with \(z=0\) gives a uniform upper bound on the minimum. Since \(h(x,u,z)\ge\sum_i z_i^6\), all minimizers lie in one compact set. Uniform continuity of \(h\) on that set and the parameter neighborhood then implies continuity of its minimum. Moreover, \[ x\text{ is good} \quad\Longleftrightarrow\quad m_x(u)\longrightarrow+\infty\quad(u\longrightarrow+\infty). \tag{44}\] A zero of \(F(x,\cdot)\) supplies a uniform upper bound. Conversely, if the nondecreasing minimum stays bounded, take minimizers along \(u\to+\infty\). They stay in a compact set, and \(6uF(x,z)\le h(x,u,z)\) forces \(F(x,z)\to0\) along them. A limit point is a zero of the fiber polynomial.

At each minimizer the critical equations are \[f_i=z_i^5+u\frac{\partial F}{\partial z_i}=0 \qquad(1\le i\le n).\] Their lower-degree terms have \(z\)-degree at most \(3\). Proposition 13, with \(x,u\) as parameters, therefore constructs a controlled polynomial \[ Q(x,u,T)=\det(TI-M_h),\qquad D=5^n. \tag{45}\] It is monic of degree \(D\) in \(T\), and evaluation at a critical point gives \[ Q(x,u,m_x(u))=0. \tag{46}\] We next use this one polynomial to separate the parameters with bounded minima from those with divergent minima.

Degree pieces and a closed lift

The rate of divergence in (44) can be detected by a fixed power substitution. For each fixed \(x\), \[ \begin{cases} m_x(v^{D+1})>v\text{ for all sufficiently large }v,&x\text{ good},\\ m_x(v^{D+1})<v\text{ for all sufficiently large }v,&x\text{ not good}. \end{cases} \tag{47}\] The second assertion follows from boundedness. For the first, write the specialization of \(Q\) at \(x\) as \[Q(x,u,T)=\sum_{j=0}^a q_j(T)u^j,\qquad q_a\ne0, \qquad\deg q_j\le D.\] If a sequence \(v\to+\infty\) satisfied \(m_x(v^{D+1})\le v\), put \(t_v=m_x(v^{D+1})\). Then \(t_v\to+\infty\), whereas (46), divided by \(v^{a(D+1)}\), gives \[q_a(t_v)=-\sum_{j<a}q_j(t_v)v^{-(a-j)(D+1)}\longrightarrow0.\] Here \(0\le t_v\le v\) makes each term on the right \(O(v^{-1})\). A nonzero polynomial cannot tend to zero along a sequence tending to \(+\infty\), giving the contradiction.

To control the growth test locally as \(x\) varies, we track possible zeros of \(m_x(v^{D+1})-v\). By (46), each such zero forces \(Q(x,v^{D+1},v)=0\). Define the controlled polynomial \[ E(x,v)=Q(x,v^{D+1},v)=\sum_{j=0}^{d_E}E_j(x)v^j, \tag{48}\] where \(d_E\) is a short, polynomial-time computable degree bound. Coefficient extraction makes the \(E_j\) a uniformly controlled family. Crucially, \[ E_D(x)=1\qquad\text{for every }x. \tag{49}\] Indeed, the term \(T^D\) in \(Q\) gives \(v^D\). Every other term has \(T\)-degree at most \(D-1\), so after substitution its \(v\)-exponent has the form \(a(D+1)+b\) with \(a\ge0\) and \(0\le b<D\); none equals \(D\). Thus \(E(x,\cdot)\) is never the zero polynomial. Fixing its actual degree keeps its leading coefficient locally away from zero, and hence gives a locally uniform bound on its roots.

The sets \(A_d\) need not be closed in the ambient space. To make the separation in Proposition 23 usable in a compact minimization argument, introduce one real variable \(t\) and define \[ W_d(x,t)=(E_d(x)t-1)^2+\sum_{j=d+1}^{d_E}E_j(x)^2, \qquad Z_d=\{(x,t)\in\mathbb R^{r+1}:W_d(x,t)=0\}. \tag{50}\] The \(W_d\) are nonnegative controlled polynomials, uniformly in the short index \(d\). The set \(Z_d\) is closed, and projection onto \(x\) is a homeomorphism from \(Z_d\) onto \(A_d\), with inverse \(x\mapsto(x,1/E_d(x))\). Thus the good part of \(Z_d\) and its complement in \(Z_d\) are both closed in the ambient Euclidean space. We have separated the two behaviors without needing a description of the connected components of a degree piece.

Algebraic coordinates in a selected closed part

We now show that a nonnegative polynomial \(W\) supplies coordinate polynomials whose roots include the coordinates of a point in every nonempty part of \(\{W=0\}\) that is both open and closed within that zero set. Their construction is independent of which part is selected and requires no equations describing that part. The use of a deformation and limiting characteristic-polynomial roots is related to the sampling methods in Basu, Pollack, and Roy (Basu et al. 2006, secs. 12.5–12.6). The argument below proves the precise form needed here directly.

Apply Proposition 24 to \(W=W_d\) and to the good part of \(Z_d\). We use \(c=(x,t)\in\mathbb R^{r+1}\) and choose \(\ell\) from a uniform short degree bound on \(W_d\). Whenever this good part is nonempty, it contains a point whose coordinates are roots of the nonzero coefficient polynomials \(P_{i,j_i}\). These polynomials are controlled uniformly in \(d,i,j_i\).

The final decision

We can now use root labels to replace the real choice of \(x\) by short discrete data. Choose an integer \(0\le d\le d_E\) and, for each \(1\le i\le r+1\), an index \(j_i\) within a uniform short bound on the \(w\)-degree of \(P_i\). For each \(P_{i,j_i}\) choose root-label data as in Proposition 14, with the auxiliary positivity test equal to \(1\), and write \(L_i\) for the resulting controlled polynomial. Let \(\mathcal S(c)\) denote the conjunction \[ W_d(c)=0,\qquad P_{i,j_i}(c_i)=0,\qquad L_i(c_i)>0 \quad(1\le i\le r+1). \tag{55}\] For these choices, accept exactly when both statements hold: \[\begin{align*} &\exists c\in\mathbb R^{r+1}\;\mathcal S(c), \tag{56}\\ &\neg\exists(c,z)\in\mathbb R^{r+1+n}\; \bigl(\mathcal S(c)\ \wedge\ F(x,z)=0\bigr). \tag{57}\end{align*}\] Each existential statement is an instance of Theorem 18. Their conjunction, with negation as displayed, is therefore an available decision.

We verify the two directions separately; they use the labels in different ways. If the test accepts, choose \(c=(x,t)\) from (56). Statement (57) implies that \(F(x,\cdot)\) has no real zero. Thus \(x\) is good. This implication holds for every choice of the indices and labels, even if a selected coefficient polynomial is zero or the conjunction selects more than one point.

Conversely, suppose a good \(x\) exists. Let \(d\) be the actual degree of \(E(x,\cdot)\). Then the good part of \(Z_d\) is nonempty. Proposition 24 supplies a point \(c^*=(x^*,t^*)\) in that part and highest nonzero coefficient indices \(j_i\) for which \(P_{i,j_i}(c_i^*)=0\). By Proposition 14, labels can be chosen to single out each \(c_i^*\) among the real roots of its coefficient polynomial. For these choices, (55) has exactly the one solution \(c^*\). It satisfies (56), and goodness of \(x^*\) gives (57). Some discrete choices therefore accept. Notice that the decision procedure does not need to verify that an index is highest or a coefficient polynomial nonzero: those properties provide complete choices, whereas the two tests ensure soundness for all choices.

Finally, all discrete choices together have polynomial encoding length. There are only \(r+1\) coefficient indices and labels; each degree bound, index bound, and label bound is short. The real variables and the number of equations and positivity tests in (56)–(57) are polynomially bounded. The controlled-polynomial rules are used in a fixed order: construct \(Q\) and \(E\), extract their coefficients and form \(W_d\), construct the coordinate polynomials, form the labels, and apply the two existential tests. Each stage is uniform in its short indices; none introduces a separate oracle or one counting level per index. The existential quantification over the entire discrete choice tuple thus preserves availability. The resulting decision function belongs to a fixed level of the counting hierarchy, independent of the input. Malformed inputs were rejected in polynomial time, so this proves Theorem 1.

Selecting some root with few derivative conditions

The distinction between selecting some root and selecting a prescribed root is elementary but useful. Derivative signs distinguish all real roots by Lemma 16. If only one root from a nonempty set is needed, repeatedly keeping a smallest nonempty sign class gives a much shorter description.

For an \(\mathsf{ETR}\) instance \(\exists y\,\Theta(y)\), apply Lemma 22 with no free parameters and with \(\Phi=\neg\Theta\). Renaming the full variable tuple gives an explicitly listed nonnegative polynomial \(F\in\mathbb Z[x_1,\ldots,x_n]\) with \(n\ge1\) and degree at most four, whose real zeros encode truth of the instance. Use Proposition 21 with \(\ell=5\). In its notation, \(D=5^n\), \(U=2^\sigma\), \(R=2^\rho\), and \[q(y)=\det(yI-M_{h_U})\in\mathbb Z[y]\] is monic and squarefree of degree \(D\). The original sentence is true if and only if \(q\) has a real root below \(R\). Take \(K=\max(1,H+\sigma V)\) from that proposition, so \(\left\lVert q\right\rVert_1\le2^K\) and \(K\) is short and polynomial-time computable. Although \(U\), \(R\), and the coefficients of \(q\) may have long binary expansions, their bound exponents are short.

Put \(T=2+3n\). A test list consists of \(t\) pairs \((b_i,v_i)\), where \[1\le t\le T,\qquad b_1(y)=R-y,\qquad v_1=1,\] and each subsequent \(b_i\) is \(q^{(j_i)}\) for some \(1\le j_i\le D\), with \(v_i\in\{-1,0,1\}\). A root matches the list when \(\mathop{\mathrm{sgn}}b_i(\alpha)=v_i\) for every \(i\). If a real root below \(R\) exists, Lemma 26 applied to all such roots gives a list matching exactly one real root. Indeed, at most \(\lceil\log_2D\rceil\le3n\) derivative conditions suffice. Every list has polynomial encoding length, since both \(T\) and \(\log D\) are polynomially bounded.

A polynomial detecting the list

We next turn these conditions into a polynomial that is negative exactly at matching real roots. The construction is the rational sign approximation of Lemma 17, now applied to only polynomially many tests.

First we need a common range for their nonzero values. Every complex root \(\alpha\) of \(q\) satisfies \(|\alpha|\le2^{K+1}\), and every test polynomial satisfies \[\deg b_i\le D, \qquad \left\lVert b_i\right\rVert_1\le2^{K+D^2+\rho+2}.\] For derivatives, the coefficient increase is bounded by \(D^D\le2^{D^2}\); the same displayed estimate covers \(R-y\). Set \[ B_0=K+D^2+\rho+2+D(K+1),\qquad B=DB_0+2. \tag{58}\] Then \(|b_i(\alpha)|\le2^{B_0}\). For the lower bound, the eigenvalues of the integer matrix \(b_i(M_{h_U})\) are these values at the \(D\) roots of \(q\). The product of its nonzero eigenvalues, up to sign, is a nonzero coefficient of its monic integer characteristic polynomial, and so has absolute value at least one. Bounding the other factors by \(2^{B_0}\) gives \[ b_i(\alpha)\ne0 \quad\Longrightarrow\quad 2^{-B}\le |b_i(\alpha)|\le2^B. \tag{59}\] This argument permits some test values to vanish.

Let \(s=T+10\) and define \[ P(z)=\prod_{j=-B}^{B} \left(2^{\max(0,j)}+2^{\max(0,-j)}z\right)^{2s}, \qquad A(z)=\frac{P(z)-P(-z)}{P(z)+P(-z)}. \tag{60}\] By Lemma 17, the denominator is at least one on the real line, \(A(0)=0\), and Equation (59) implies \[|A(b_i(\alpha))-\mathop{\mathrm{sgn}}b_i(\alpha)| \le2\cdot3^{-2s}\le\frac1{8T} \qquad(q(\alpha)=0,\ \alpha\in\mathbb R).\] Consequently \[\Psi(y)=4\sum_{i=1}^{t}(A(b_i(y))-v_i)^2-1\] is at most \(-1+1/(16T)\) at a matching real root. At any other real root one difference in the sum has absolute value at least \(1-1/(8T)\ge7/8\), and therefore \(\Psi\ge33/16\).

Clear the positive squared denominators by setting \[\begin{align*} D_i(y)&=P(b_i(y))+P(-b_i(y)),\\ N_i(y)&=P(b_i(y))-P(-b_i(y)),\\ g_*(y)&=4\sum_{i=1}^{t}(N_i(y)-v_iD_i(y))^2 \prod_{j\ne i}D_j(y)^2 -\prod_{j=1}^{t}D_j(y)^2. \end{align*}\] This is an integer polynomial, equal on the real line to \(\Psi\prod_iD_i^2\). As every \(D_i\ge1\), it satisfies \[ \begin{cases} g_*(\alpha)\le-\tfrac12,&\text{if $\alpha$ matches the list},\\ g_*(\alpha)\ge\tfrac12,&\text{otherwise}, \end{cases} \qquad(q(\alpha)=0,\ \alpha\in\mathbb R). \tag{61}\] For one additional choice \(e\in\{0,\ldots,D\}\) put \[ g(y)=4Dg_*(y)+e, \qquad X=\det M_{g(h_U)} =\prod_{q(\alpha)=0}g(\alpha)\in\mathbb Z. \tag{62}\] The determinant identity is Lemma 11. The sign argument of Section 5, applied to \(L=-g_*\), gives \[ q\text{ has a real root below }R \quad\Longleftrightarrow\quad X<0\text{ for some test list and some }e. \tag{63}\] Indeed, every \(e\) preserves the real-root signs. A list matching exactly one real root gives exactly one negative real factor; some \(e\) avoids every nonreal zero, since each of at most \(D\) nonreal roots forbids at most one of the \(D+1\) choices. The conjugate pairs then contribute positive factors. Conversely, a negative product has a negative real factor, whose root matches the list and hence lies below \(R\).

For the subsequent computations we record explicit short bounds. Writing \(m_*=2s(2B+1)\) for the degree of \(P\), set \[ \begin{split} d_g&=2Tm_*D,\\ l_*&=m_*(2B+1),\\ E_*&=2T(l_*+2)+16(D+T+2),\\ m_X&=DE_*+1. \end{split} \tag{64}\] Then \(\deg g\le d_g\) and \(|X|\le2^{m_X}\). For the first bound, every term in \(g_*\) has \(t\) squared factors, each of degree at most \(m_*D\). For the second, at every complex root \(\alpha\) each base in \(P(\pm b_i(\alpha))\) has modulus at most \(2^{2B+1}\). Hence \[|P(\pm b_i(\alpha))|\le2^{l_*},\qquad |D_i(\alpha)|,|N_i(\alpha)|\le2^{l_*+1},\qquad |N_i(\alpha)-v_iD_i(\alpha)|\le2^{l_*+2}.\] Therefore \[|g(\alpha)|\le D(16T+5)\,2^{2T(l_*+2)}\le2^{E_*},\] which gives the asserted product bound. All displayed bound parameters use a fixed number of sums and products of short integers, so are themselves short and polynomial-time computable.

Accounting for the oracle levels

The two multiplication-determinant computations now have an explicit cost. Set \[\Omega=6(1+d_g),\qquad L_0=D\Omega+4n,\qquad \lambda=5L_0+4n+D^2+10.\] For every prime \(p>\lambda\), Proposition 12 applies both to \(h_U\), of degree at most six, and to \(g(h_U)\), of degree at most \(6d_g\). The larger cutoff is used for both applications. To recover \(\mathop{\mathrm{sgn}}X\) we need only \(p\le Y=2\max(16,m_X,\lambda)^4\), as in Proposition 7. In particular every queried prime has polynomial bit length.

For the first application, the relations \(f_i(\cdot,U)\) and the objective \(h_U\) have direct polynomial-bit-time evaluations modulo \(p\). Indeed, \(\ell=5\) gives \(a_i=20^i\), with polynomial bit length. The quartic \(F\) and its first and second derivatives have polynomial-size monomial lists. The constants \(U\bmod p\) and \(R\bmod p\) are computed by powering with the short exponents \(\sigma\) and \(\rho\). The Jacobian is an \(n\times n\) determinant of directly evaluable entries. Thus Proposition 12, with \(a=0\), computes the indexed coefficients \(q_k\bmod p\) of \(q(y)=\sum_{k=0}^{D}q_ky^k\) in \(\mathsf F_{8}\).

For \(1\le j\le D\), \[q^{(j)}(y)=\sum_{k=j}^{D}q_k \left(\prod_{r=0}^{j-1}(k-r)\right)y^{k-j}.\] The falling factorial is in \(\mathsf F_{4}\) by Lemma [lem:product]; the outer sum therefore gives derivative evaluations in \(\mathsf F_{9}\) by Lemma 2. This includes every test \(b_i\), since \(R-y\) is directly evaluable. Each factor of \(P(b_i(y))\) in Equation (60) is consequently in \(\mathsf F_{9}\). The product lemma puts \(P(\pm b_i(y))\) in \(\mathsf F_{13}\). Since the list contains only polynomially many tests, the formulas for \(D_i,N_i,g_*\), and \(g\) need only polynomially many such calls and short arithmetic operations. Thus \(g(y)\), and then \(g(h_U(x))\), are evaluable in \(\mathsf F_{13}\). These expressions use only integer additions and multiplications; their field evaluations never invert a test denominator.

The second application of Proposition 12, with \(a=13\) and \(v=g(h_U)\), computes \[X\bmod p=(-1)^D[y^0]\det(yI-M_{g(h_U)})\bmod p\] in \(\mathsf F_{21}\). The first application uses only the original quartic and its critical equations; the second calls the first through the evaluations of \(g\). This is a fixed sequence of two applications, independent of \(n\) and \(D\).

By Proposition 7 and Equation (64), the sign of \(X\) is in \(\mathsf F_{24}\). Lemma 2 then puts existence of a test list and an \(e\) with \(X<0\) in \(\mathsf F_{25}\). Equation (63) therefore gives a decision function for \(\mathsf{ETR}\) at that level, and a language in \(\mathsf C_{26}\mathsf P\). Polynomial-time many-one precomputation preserves this level, proving the second assertion of Theorem 25.

The shortness of all indices is independent of these level counts. The bounds \(D,K,\rho,\sigma,B,d_g,m_X,\lambda,Y\) are computed in polynomial bit time, test lists have at most \(T\) entries, and every field element and product index has a polynomial-length encoding. Thus no long integer is passed as an explicit oracle query, and Table 1 describes fixed uniform machines.