LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passaudited 2026-09-30

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.

Tensor consistency rejects a wrong decoded tensor

Statement

Let $N \geq 0$ , $u \in F_{2}^{N}$ , and $V \in F_{2}^{N \times N}$ with $V \neq u \otimes u$ , using row-major tensor coordinates. Put $F_{u} = {WH}_{N} (u)$ and $G_{V} = {WH}_{N^{2}} (vec (V))$ . The ideal test samples independent uniform $r, s \in F_{2}^{N}$ and rejects exactly when $G_{V} (r \otimes s) \neq F_{u} (r) F_{u} (s)$ . Its rejection probability is at least $1 / 4$ .

Now let fixed tables $f : F_{2}^{N} \to F_{2}$ and $g : F_{2}^{N \times N} \to F_{2}$ have relative distances $δ_{f} = 2^{- N} ∣ {x : f (x) \neq F_{u} (x)} ∣, δ_{g} = 2^{- N^{2}} ∣ {Z : g (Z) \neq G_{V} (Z)} ∣ .$ The six-query self-corrected test samples independent uniform $r, s, y, y^{'} \in F_{2}^{N}$ and $Y \in F_{2}^{N \times N}$ , forms ${\hat{f}}_{r} = f (y) + f (r + y), {\hat{f}}_{s} = f (y^{'}) + f (s + y^{'}), {\hat{g}}_{r \otimes s} = g (Y) + g (Y + r \otimes s),$ and rejects exactly when ${\hat{g}}_{r \otimes s} \neq {\hat{f}}_{r} {\hat{f}}_{s}$ . It makes six nonadaptive table queries, allowing repeated locations, and rejects with probability at least $\frac{1}{4} - 4 δ_{f} - 2 δ_{g}$ . When $N = 0$ the condition $V \neq u \otimes u$ is impossible.

Facts & Assumptions

Given: A dimension $N$ , a vector $u$ , a matrix $V \neq u \otimes u$ , and fixed tables $f, g$ at the stated distances from the corresponding linear Walsh–Hadamard tables.

[F1]

Walsh–Hadamard tables are truth tables of linear forms, so ${WH}_{n} (w) (x) = w \cdot x$ . (Walsh–Hadamard encoding and relative Hamming distance)

[F2]

The ideal tensor test compares $g (r \otimes s)$ with $f (r) f (s)$ for independent uniform $r, s$ . (Quadratic tensor consistency test)

[F3]

Tensor coordinates are $(r \otimes s)_{i j} = r_{i} s_{j}$ in fixed row-major order. (Quadratic tensor consistency test)

[F4]

For every nonzero binary vector $d$ and uniform $z$ , $\Pr [z \cdot d = 1] = 1 / 2$ . (Random binary subsums detect every nonzero discrepancy)

[F5]

The two-query corrector for a fixed oracle $h$ at request $q$ returns $h (a) + h (q + a)$ for uniform $a$ . (Two-query linear self-correction)

[F6]

The self-corrected tensor test independently samples its auxiliary points and uses two table queries for each of its three decoded values. (Quadratic tensor consistency test)

Proof

1.1F1F2F3F4givenconstructalgebra

Let $D = V + u \otimes u \neq 0$ over $F_{2}$ , choose the first nonzero column $j$ of $D$ , and view $r$ as a row vector. By [F4], $r D \neq 0$ with probability at least $\Pr [r \cdot D_{*, j} = 1] = 1 / 2$ . For each such $r$ , $r D$ is a nonzero vector, so [F4] gives $\Pr_{s} [r D s = 1] = 1 / 2$ . Since $G_{V} (r \otimes s) + F_{u} (r) F_{u} (s) = r D s$ by [F1] and [F3], the rejection probability of the ideal test in [F2] is at least $1 / 4$ .

1.2F1F5givenalgebra

For any fixed requested point $q$ and any fixed table $h$ at relative distance $η$ from a linear form $L$ , the points $a$ and $q + a$ are both uniform when $a$ is uniform. Unless either lies in the error set, [F5] returns $h (a) + h (q + a) = L (a) + L (q + a) = L (q)$ . The union bound therefore gives corrector error at most $2 η$ , uniformly in $q$ , including $q = 0$ .

2.1F2F6step 1.1step 1.2algebra

Apply step 1.2 to the two requests $r, s$ for $f$ and to request $r \otimes s$ for $g$ . The probability that any of the three corrected values is wrong is at most $2 δ_{f} + 2 δ_{f} + 2 δ_{g} = 4 δ_{f} + 2 δ_{g}$ . Outside that union, the self-corrected predicate in [F6] equals the ideal predicate in [F2]. Hence its rejection probability is at least the ideal rejection probability from step 1.1 minus $4 δ_{f} + 2 δ_{g}$ , which is the claimed bound; no independence of the correction errors is used.

3.1F5F6step 2.1constructdischarge-construct∎

The test samples $r, s, y, y^{'}$ using $4 N$ unbiased bits and $Y$ using $N^{2}$ more, computes all six query locations before receiving any table value, and makes exactly six queries as stated in [F6]. Repeated locations are permitted by [F5]; for $N = 0$ , all domains are singletons and the hypothesis is impossible.

Depends on

Used by

Dependency tree · two levels

8 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 proof of Theorem 18.21 Step 2, printed pp. 366–367 (standard reference, not scraped)