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: the verifier can trust the final field value

Statement

False assertion. The Shamir protocol remains sound if its terminal step is modified so that the verifier accepts whenever the current claim equals a field value $v$ announced by the prover, instead of evaluating the arithmetized matrix $b$ at the current point: on every false closed prenex quantified Boolean formula the modified verifier would still accept with probability at most $1 / 3$ against every prover.

Facts & Assumptions

Given: The modified protocol, in which the round checks of the Shamir protocol are kept unchanged and the terminal comparison $c = b (σ)$ is replaced by the comparison $c = v$ for a value $v$ announced by the prover.

[A1]

The rounds run for $t = T, \dots, 1$ , the initial claim is $c = 1$ , a round with node $M$ checks $c = s (0) s (1)$ for a universal node, $c = s (0) + s (1) - s (0) s (1)$ for an existential node, and $c = (1 - a) s (0) + a s (1)$ with $a = σ (i)$ for a reduction, and then sets $c = s (r_{t})$ at the fresh challenge; the unmodified terminal step accepts exactly when $c = b (σ)$ , and this evaluation is the only place where the matrix arithmetization is used (The Shamir interactive protocol for TQBF).

[A2]

Soundness $s$ of a protocol means that for every input outside the language and every prover strategy the acceptance probability is at most $s$ , so soundness at most $1 / 3$ fails as soon as one false instance is accepted with probability exceeding $1 / 3$ (Completeness and soundness of an interactive protocol).

[A3]

A closed prenex quantified Boolean formula $\exists x φ (x)$ is true exactly when $φ$ holds for $x = 0$ or for $x = 1$ (Quantified Boolean formulas and the language TQBF).

[A4]

Arithmetization sends the leaf $x$ to $X$ and forms $X (1 - X)$ for $x \land \neg x$ , and it agrees with the Boolean value of the matrix at Boolean inputs (Arithmetization of Boolean formulas).

[L1]

The unmodified protocol has soundness at most $1 / 3$ on false inputs, achieved through the terminal evaluation against $b$ (Total TQBF soundness by the first repaired claim).

Refutation

1.1

Let $Φ : = \exists x (x \land \neg x)$ . By [A3] the formula is false: $φ (x) = x \land \neg x$ holds neither at $x = 0$ nor at $x = 1$ , so the existential quantification is false. Its matrix arithmetization is $b = X (1 - X)$ .

A3A4construct

1.2

Consider the prover strategy that sends, in every round, the constant coefficient list $s \equiv 1$ , and announces $v = 1$ at the modified terminal step; this is a legal message in every round, since the constant polynomial has degree $0 \leq D$ .

A1construct

2.1

We verify that every round test passes and that the claim remains $1$ . The claim starts at $c = 1$ . For a universal node the test is $c = s (0) s (1) = 1 \cdot 1 = 1$ ; for an existential node it is $c = s (0) + s (1) - s (0) s (1) = 1 + 1 - 1 = 1$ ; for a reduction with current value $a$ it is $c = (1 - a) s (0) + a s (1) = (1 - a) + a = 1$ . In every case the test passes, and the update $c : = s (r_{t})$ leaves $c = 1$ for every challenge $r_{t}$ .

A1step 1.2algebra

3.1

Consequently, after all rounds the claim is $c = 1$ ; the modified verifier then compares it with the announced value $v = 1$ and accepts. This holds for every random tape, because the strategy $s \equiv 1$ and the announcement $v = 1$ do not depend on the challenges.

step 2.1A1given

4.1

The modified verifier therefore accepts the false input $Φ$ with probability $1$ , which is greater than $1 / 3$ ; by [A2] the quality that fails here is exactly soundness, so the false assertion is refuted. This also shows why the terminal evaluation $c = b (σ)$ cannot be delegated to the prover: it is what forces the final claim to agree with a value computed from the input.

step 3.1A2L1given∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

16 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

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