Existential–universal real sentences in the counting hierarchy

The explanation

Here is a question about real numbers. Is there a number x such that, for every number y, the value y² − 2xy + 1 stays above zero? Try x = 0. The value becomes y² + 1, which never drops below 1. So the answer is yes. Now try x = 2 and y = 2. The value is 4 − 8 + 1 = −3, which fails. In general, the smallest value over all y is 1 − x², reached at y = x. So exactly the numbers x strictly between −1 and 1 work.

This is an existential–universal sentence over the reals. “Existential” means “there is”, and “universal” means “for every”. The paper studies the general version. Each block may hold many variables. The conditions test whether polynomials equal zero or are positive. These tests may be joined with AND, OR and NOT. The task is to decide, by an exact algorithm, whether a given sentence is true.

The polynomials arrive as arithmetic circuits. A circuit is a short recipe of additions, subtractions and multiplications, where each step may reuse earlier results. Short recipes can describe huge numbers. Start with 2 and square it ten times. Ten multiplications give 2 to the power 1024, a number with 309 digits. Fifty squarings give a number with about 3.4 × 10¹⁴ digits. So an algorithm cannot simply expand everything and compute.

Computer scientists sort problems by the resources they need. PSPACE holds the problems solvable with memory that grows at most like a fixed power of the input length. That kind of growth is called polynomial. PP holds problems solved in polynomial time with fair coin flips. There, the answer is yes exactly when more than half of the coin outcomes accept. The counting hierarchy, introduced by Wagner in 1986, stacks PP on itself. Its first level is PP. Each higher level is PP with free access to the level below, used as an oracle. An oracle is a black box that answers questions instantly.

Tarski proved that such sentences can always be decided by some algorithm. In 1988 Canny put the purely existential case in PSPACE. Renegar's bounds give polynomial space for each fixed number of quantifier blocks, that is, runs of “there is” or “for every” variables. Every fixed level of the counting hierarchy already lies inside PSPACE. In 2009, Allender, Bürgisser, Kjeldgaard-Pedersen and Miltersen placed a related problem, PosSLP, in the counting hierarchy. PosSLP asks whether a circuit with no division outputs a positive integer. Their counting tools are the ones this paper builds on.

The paper claims to prove that all two-block sentences of this kind are decided at one fixed level of the counting hierarchySource 1. The level does not grow with the number of variables, the degrees, or the size of the coefficientsSource 2. For sentences with only the “there is” block, it claims the explicit level 26Source 3. That also covers every problem that can be translated efficiently into that existential case.

The hard part is the witness. For a true sentence, the algorithm wants a short description of a good x. But a good x may be an irrational root of a polynomial with enormous degree. Writing its digits is hopeless. Checking whether one given x works also gives no finite description of a good xSource 4. The paper names a chosen root by the signs of the polynomial's derivatives thereSource 5. That list of signs can be too long, so the paper compresses it into one weighted sumSource 6,Source 7. It then shows that some good point always has coordinates among such labelled roots. Counting machines can check these labels without building the giant numbers.

The two-block claim names no specific levelSource 8. It says only that some fixed whole number works. The explicit level 26 is for the existential case aloneSource 3. The result also stops at two blocks. It says nothing direct about sentences that switch between “there is” and “for every” more often.

How sure is this? No Lean formalization is listed for this result in the openai/math release. So no computer proof checker has checked the claim. The argument rests on the paper alone, and no specialist review has been published.

What it doesn't show. This does not cover real sentences that switch between “there is” and “for every” more than once.