LemmaStatement: Literature-sourcedProof: 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.

Quadratic tensor test rejects an inconsistent tensor

Statement

Let $n \geq 0$ , let $u \in F_{2}^{n}$ and let $w \in F_{2}^{n \times n}$ be read as a matrix, with $W$ the matrix of entries $w_{i j}$ and $u \otimes u$ the matrix of entries $u_{i} u_{j}$ . Suppose $W \neq u \otimes u$ . Then:

(Ideal test.) The ideal tensor test of Quadratic tensor consistency test applied to the linear tables $f = ℓ_{u}$ and $g = ℓ_{w}$ , where $ℓ_{w} (z) = w ⊙ z$ , rejects with probability at least $1 / 4$ : $ε_{t e n} (ℓ_{u}, ℓ_{w}) \geq \frac{1}{4} .$
(Self-corrected test.) If instead $f$ and $g$ are arbitrary tables at distances $δ_{f}, δ_{g} < 1 / 4$ from $ℓ_{u}$ and $ℓ_{w}$ respectively, then with auxiliary points drawn independently as in the self-corrected tensor test, $\Pr [self-corrected test rejects] \geq \frac{1}{4} - 4 δ_{f} - 2 δ_{g} .$ In particular, whenever $4 δ_{f} + 2 δ_{g} < 1 / 4$ the self-corrected test rejects with probability bounded below by the positive constant $1 / 4 - 4 δ_{f} - 2 δ_{g}$ , and for $δ_{f}, δ_{g} \leq δ$ this is at least $1 / 4 - 6 δ$ . More generally, if an ideal test using $c$ values from tables each within distance $δ < 1 / 4$ of a specified linear table rejects with probability at least $π$ , then replacing those values by self-corrections makes it reject with probability at least $π - 2 c δ$ .

Facts & Assumptions

Given: an integer $n \geq 0$ , vectors $u \in F_{2}^{n}$ , $w \in F_{2}^{n \times n}$ with $W \neq u \otimes u$ , independent uniform $r, s \in F_{2}^{n}$ , and the ideal and self-corrected tensor tests of Quadratic tensor consistency test.

[F1]

The ideal tensor test accepts exactly when $g (r \otimes s) = f (r) f (s)$ , with $r, s$ independent uniform; for linear tables $f = ℓ_{u}$ , $g = ℓ_{w}$ the two sides are $(u \cdot r) (u \cdot s)$ and $w ⊙ (r \otimes s)$ (Quadratic tensor consistency test).

[F2]

For linear tables, $(u \otimes u) ⊙ (r \otimes s) = \sum_{i, j} u_{i} u_{j} r_{i} s_{j} = (u \cdot r) (u \cdot s)$ , and $w ⊙ (r \otimes s) = \sum_{i, j} w_{i j} r_{i} s_{j}$ , the matrix $W$ having entries $w_{i j}$ (Quadratic tensor consistency test).

[F3]

For every nonzero vector $c \in F_{2}^{m}$ the linear function $x \mapsto c \cdot x$ takes the value $1$ on exactly half of the cube $F_{2}^{m}$ ; equivalently, two distinct linear Boolean functions disagree on exactly half the cube (Character orthogonality, inversion and Parseval).

[F4]

If a table $h$ has distance $δ < 1 / 4$ from a linear function $ℓ$ , then $ℓ$ is the unique linear function at distance less than $1 / 4$ , and at every fixed requested point the two-query self-corrector returns $ℓ$ at that point with probability at least $1 - 2 δ$ (Pointwise correctness under less than quarter noise, Two-query linear self-correction).

[F5]

The self-corrected tensor test replaces each of the three queried values by a two-query self-correction with independent auxiliary points and accepts exactly when the corrected values satisfy the tensor equation (Quadratic tensor consistency test).

Proof

technique · direct

1.1

The difference $D : = W - u \otimes u$ is a nonzero matrix over $F_{2}$ , so some column of $D$ is nonzero; fix such a column $j$ and let $c$ be that column, a nonzero vector with $(r D)_{j} = c \cdot r$ for every row vector $r$ .

F2givenchoose

2.1

By [F3] applied to the nonzero $c$ of step 1.1 the functional $r \mapsto (r D)_{j}$ equals $1$ on exactly half of the cube, so the set of $r$ with $r D \neq 0$ has probability at least $1 / 2$ , because $(r D)_{j} = 1$ makes the row vector $r D$ nonzero.

F3step 1.1algebra

3.1

Conditioned on any fixed $r$ with $r D \neq 0$ the map $s \mapsto r D s = (r D) \cdot s$ is a nonzero linear functional of $s$ , so by [F3] it equals $1$ for exactly half of the $s$ ; since $s$ is independent of $r$ , this conditional probability is $1 / 2$ for every such $r$ . For linear tables the ideal test rejects exactly when $w ⊙ (r \otimes s) \neq (u \cdot r) (u \cdot s)$ , and by [F2] the two sides differ by $w ⊙ (r \otimes s) - (u \otimes u) ⊙ (r \otimes s) = r (W - u \otimes u) s = r D s$ , a bit; hence rejection is the event $r D s = 1$ and its probability is at least $\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$ , which proves the first clause. For $n = 0$ the hypothesis $W \neq u \otimes u$ is empty, the one-point cube having $u \otimes u$ as its only element.

F1F2F3step 2.1algebra

4.1

For the second clause let $E$ be the event that all three self-corrections return the true linear values, namely ${Corr}_{f} (r) = ℓ_{u} (r)$ , ${Corr}_{f} (s) = ℓ_{u} (s)$ and ${Corr}_{g} (r \otimes s) = ℓ_{w} (r \otimes s)$ ; by [F4] and the union bound $\Pr [E^{c}] \leq 2 δ_{f} + 2 δ_{f} + 2 δ_{g} = 4 δ_{f} + 2 δ_{g}$ , since each failure bound holds uniformly at every requested point. On $E$ the self-corrected test of [F5] reads exactly the values the ideal test reads at the same pair $(r, s)$ , so its outcome coincides with the ideal outcome. With $π \geq 1 / 4$ the ideal rejection probability of step 3.1, the union bound, without an independence assumption between $E$ and $(r, s)$ , gives $\Pr [self-corrected rejects] \geq \Pr [{r D s = 1} \cap E] \geq π - \Pr [E^{c}] \geq \frac{1}{4} - 4 δ_{f} - 2 δ_{g} .$

F4F5step 3.1algebra

5.1

Steps 3.1 and 4.1 are the two clauses of the statement. If $δ_{f}, δ_{g} \leq δ$ the second bound is at least $1 / 4 - 6 δ$ . For the general clause, let $I$ be the event that the specified ideal test rejects, so $\Pr [I] \geq π$ , and let $E_{c}$ be the event that all $c$ corrections return their specified linear values. The uniform bound of [F4] and the union bound give $\Pr [E_{c}^{c}] \leq 2 c δ$ even when requested points depend on the test randomness. On $I \cap E_{c}$ the corrected test rejects, so $\Pr [corrected test rejects] \geq \Pr [I] - \Pr [E_{c}^{c}] \geq π - 2 c δ$ . ∎

F4step 3.1step 4.1givenalgebra

Remarks

Where each factor of $1 / 2$ comes from. The proof needs two independent half-cube events: a nonzero row functional in $r$ , then a nonzero functional in $s$ . This is the random subsum principle in its two-variable form, cited from the character lemma rather than reproved, and it is the only probabilistic input to the ideal analysis; the value $1 / 4$ is exactly the product of the two halves and is therefore not improvable by this argument.
Dependence of the corrected values. The auxiliary points $y, y^{'}, Y$ are drawn independently, while the two query points within each correction are linked by the requested point. The union bound uses only the separate failure estimates, which hold for each requested point; it requires no independence between the correction event and the ideal rejection event.
Why this suffices for the tester. The constant-query tester of An exponential-size constant-query base assignment tester tests tables that are promised to pass a $0.99$ -linearity test, so their distances from linear are at most $0.01$ ; with $δ_{f}, δ_{g} \leq 0.01$ the bound of the second clause is at least $1 / 4 - 0.06 > 0.19$ , a positive constant independent of $n$ and of the tables. This is the sense in which the tensor test has soundness error bounded away from zero, and it is what the composition step later consumes.

Depends on

Used by

Dependency tree · two levels

10 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, §18.4.2 Step 2 (rejection probability 1/4), printed pp. 382-383. (standard reference, not scraped)
Irit Dinur, The PCP theorem by gap amplification, §5 (consistency test), printed pp. 17-18. (standard reference, not scraped)