Existential–Universal Real Sentences Fall Within a Fixed Counting Level

A sentence of the form (\exists x,\forall y:\Phi(x,y)) asks for one real tuple (x) that makes a condition true for every real tuple (y). The choice cannot adapt to the challenge. In the simple example (y^2+x>0), setting (y=0) forces (x>0); any such (x) then works for every (y).

The manuscript studies this pattern when (\Phi) is a Boolean combination of polynomial equalities and inequalities. Its central claim is that deciding these existential–universal sentences takes place at some fixed level of the counting hierarchy. The level is fixed across input sizes; it does not mean the problem has a practical or fast algorithm.

At the base, PP accepts when strictly more than half of a computation’s equally likely paths accept. Higher levels can make queries to the preceding level. The result therefore places the decision problem within a bounded depth of counting, though the manuscript’s stated two-block theorem does not give a specific numerical level.

The input matters. Polynomials are represented by arithmetic circuits using addition, subtraction and multiplication, with signed binary integers and shared wires. The circuits have no division or exponentiation gates. The theorem allows arbitrarily many variables in both quantified blocks. The appendix gives an explicit level-26 upper bound only for the existential-only fragment; that is not the bound stated for the two-block problem.

The proof begins by fixing (x) and asking whether it has a counterexample: some (y) for which (\Phi(x,y)) fails. The manuscript encodes the circuit’s intermediate values and the Boolean choices with additional variables. After splitting products into equations, the required equations have degree at most two. Summing their squares produces a non-negative polynomial (F(x,z)), of degree at most four, such that for each fixed (x), a counterexample exists exactly when (F(x,z)=0) for some (z).

Thus (x) is “good” precisely when its fiber contains no real zero of (F).

The distinction between having no zero and merely having a positive minimum is essential. Consider [ F(s,t)=s^2+(st-1)^2. ] A zero would require both (s=0) and (st=1), which is impossible. Yet along (s=1/t), the value is (1/t^2), approaching zero as (t) grows. The infimum is zero without being attained: approximate solutions escape to infinity.

To prevent that escape, the proof studies a different minimum: [ m_x(u)=\min_z\left(\sum_i z_i^6+6uF(x,z)\right),\qquad u\ge 0. ] The sixth powers grow as the coordinates grow, so the minimum is attained. Since (F\ge0), increasing (u) cannot lower it.

If the fiber has a zero (z_0), evaluating the expression there removes the penalty term, giving (m_x(u)\le\sum_i(z_0)_i^6) for every (u). One zero supplies a uniform bound for all (u).

Conversely, if the minima stay below some fixed (B), their minimizers have (\sum_i z_i^6\le B), so their coordinates remain bounded. Along a convergent subsequence as (u) grows, the penalty bound gives (0\le F(x,z(u))\le B/(6u)), which tends to zero. By continuity, the limit is a real zero. Therefore the minima stay bounded exactly when the fiber has a zero; for a good (x), they tend to infinity.

Showing that (m_x(u)) eventually grows is not yet a finite decision procedure. At a minimizer, the derivative equations have leading terms (z_i^5). The resulting quotient algebra has dimension (5^n), where (n) is the number of fiber variables. The manuscript constructs a characteristic polynomial (Q) whose roots include the minimum value, but avoids building the enormous matrix directly. Instead it uses degree and coefficient-size bounds, with evaluations modulo primes, to control the relevant polynomial families.

A power substitution turns divergence into an eventual comparison with a variable (v). Substituting into (Q) yields a polynomial (E) whose coefficient of (v^D) is always one, so it cannot vanish identically. On regions where its degree is fixed, the proof establishes that goodness is locally constant.

The remaining construction turns the existence of a good point into finite algebraic choices. A reciprocal of the leading coefficient makes a fixed-degree region closed. A further compact-minimization argument produces univariate polynomials whose roots include the coordinates of some good point, if one exists. Derivative signs distinguish real roots, including repeated ones. The proof then compresses each sign string into a weighted sum computed modulo a short prime. A label records the prime, a weight parameter and a target sum, allowing a selected root to be specified by a polynomial positivity test.

A displayed example uses (t^3-t), whose roots have distinct derivative-sign strings and can be distinguished by such a label. It illustrates the mechanism; it is not itself the general compression proof.

For guessed coordinate polynomials and root labels, the construction defines a parameter set (S). It asks two questions: is (S) nonempty, and is there no point in (S) whose fiber contains a zero of (F)? If both tests pass, every selected parameter supplies a good (x). The guess need not isolate a single point: nonemptiness and the absence of any bad fiber are enough for soundness.

For completeness, the geometric construction and root labels ensure that whenever a good point exists, some choices select one. The manuscript’s construction uses polynomially many bits for the discrete choices and has fixed nesting depth. It uses existential tests for the resulting controlled polynomial families to connect the real quantifiers to a fixed counting level.

The manuscript develops the boundedness argument in detail and gives a roadmap for the later constructions. Together, those steps connect “one real choice survives every challenge” to bounded-depth counting, without asserting that the decision can be carried out efficiently in practice.