False statementConstruction: AI-adaptedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 2026-09-27

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

False: IP = PSPACE needs no degree reduction in this arithmetization

Statement

False assertion. If the multilinearization operators $R_{x}$ are omitted from the quantified arithmetization and the resulting protocol uses only the quantifier operators $A_{x}$ and $E_{x}$ in inner-to-outer order, then the prover messages still have degree polynomial in the input length: for every closed prenex quantified Boolean formula of size $m$ , the polynomial carried at every operator node of the naive sequence has degree at most a polynomial in $m$ , so no degree reduction is needed for this proof route.

Facts & Assumptions

Given: The naive inner-to-outer quantified arithmetization without multilinearization operators, and the family of formulas defined below.

[A1]

The ordered arithmetization replaces NOT, AND and OR by $1 - a$ , $a b$ and $a + b - a b$ , applies $A_{X} P = (P ∣_{X = 0}) (P ∣_{X = 1})$ to a universally quantified variable and $E_{X} P = 1 - (1 - P ∣_{X = 0}) (1 - P ∣_{X = 1})$ to an existentially quantified variable, and processes inner quantifiers first (Field arithmetization of QBF quantifiers).

[A2]

The multilinearized ordered arithmetization inserts, before each quantifier operation, the reductions $R_{X_{i}} P = (1 - X_{i}) (P ∣_{X_{i} = 0}) + X_{i} (P ∣_{X_{i} = 1})$ ; the variant considered here omits exactly these reductions and keeps the same quantifier operations and the same inner-to-outer order (Multilinearization in one variable).

[A3]

A closed prenex quantified Boolean formula is $Q_{1} x_{1} \dots Q_{k} x_{k} ψ$ with quantifier-free matrix $ψ$ , and its truth value is defined by the usual Boolean semantics of the quantifiers over ${0, 1}$ (Quantified Boolean formulas and the language TQBF).

[A4]

Arithmetization maps a variable leaf $x_{i}$ to $X_{i}$ and a matrix built from these leaves by the gate rules of [A1] (Arithmetization of Boolean formulas).

Refutation

1.1

For every $k \geq 1$ let $Φ_{k} : = \exists y \forall x_{1} \dots \forall x_{k} (y)$ ; its matrix is the variable $y$ , and its prefix has $k + 1$ quantifiers. Fix the standard effective encoding with binary variable indices and fixed punctuation, so the encoded size of this family is $m_{k} = O (k \log (k + 1))$ . By [A4] the arithmetization of the matrix is $b = Y$ .

A3A4construct

1.2

In the naive inner-to-outer sequence the universal quantifiers are processed first, starting with the innermost $x_{k}$ and ending with $x_{1}$ , and the outer existential quantifier in $y$ is processed last, by the ordering rule of [A1]; the omitted operations are precisely the reductions $R_{X_{i}}$ of [A2].

A1A2

2.1

We claim that after the first $j$ universal quantifiers the carried polynomial is $Y^{2^{j}}$ , by induction on $j$ . For $j = 0$ this is $b = Y$ ; for the step, $Y^{2^{j}}$ does not involve the next variable $X_{i}$ , so both of its specializations at $X_{i} = 0$ and $X_{i} = 1$ equal $Y^{2^{j}}$ , and $A_{X_{i}}$ gives the product $Y^{2^{j}} \cdot Y^{2^{j}} = Y^{2^{j + 1}}$ .

A1step 1.1algebra

3.1

Taking $j = k$ in step 2.1, the polynomial carried at the input of the outer quantifier node $E_{y}$ is $Y^{2^{k}}$ , whose degree as a polynomial in the active variable $y$ is $2^{k}$ ; the message that the protocol requires at that node is the restriction of this polynomial in the active variable, so it also has degree $2^{k}$ .

step 1.2step 2.1algebra

4.1

Since $m_{k} = O (k \log (k + 1))$ for the encoding fixed in step 1.1, every polynomial $q (m_{k})$ is bounded above by a polynomial in $k \log (k + 1)$ and is eventually smaller than $2^{k}$ . Hence the asserted polynomial degree bound fails for the family $Φ_{k}$ under this allowed encoding, which refutes the false assertion. The count of syntax nodes alone would not give this encoded-length bound under an arbitrary effective encoding.

step 1.1step 3.1algebra

5.1

The failure is one of degree and not of Boolean semantics: for every $k$ the formula $Φ_{k}$ is true, because $\forall x_{1} \dots \forall x_{k} (y)$ holds exactly when $y = 1$ and then $\exists y$ is satisfied; so the refuted degree bound is not rescued by any appeal to the truth of the instances.

A3step 3.1algebra∎

Depends on

Used by

Exponential degree without multilinearization Counterexample

Dependency tree · two levels

6 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Arora and Barak, Computational Complexity: A Modern Approach, §8.5.3 (degree growth warning) and Remark 8.19, author-hosted draft (standard reference, not scraped)
A. Shen, IP = PSPACE: Simplified Proof, JACM 39(4) 1992, pp. 878–880 (standard reference, not scraped)