TheoremStatement: 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.

BLR rejection is proportional to distance from linearity

Statement

For every $n \geq 0$ and every $f : F_{2}^{n} \to F_{2}$ , let $α (f)$ be the BLR acceptance probability and $ε (f) = 1 - α (f)$ the BLR rejection probability of The BLR linearity test over F_2, and let $dist (f, Λ) : = \min_{a \in F_{2}^{n}} dist (f, ℓ_{a}), Λ = {ℓ_{a} : x \mapsto a \cdot x}$ be the relative Hamming distance from $f$ to the nearest linear function, the minimum being over the nonempty finite set of $2^{n}$ linear functions. Then $ε (f) \geq dist (f, Λ) .$ Equivalently, the fraction of violated constraints of the Hadamard linearity constraint system ${Lin}_{n} (f)$ of Hadamard linearity constraint system is at least the distance of $f$ from $Λ$ . There is no restriction on the acceptance probability: the bound holds in the low-acceptance regime $α \leq 1 / 2$ as well, and it holds in dimension $n = 0$ .

Facts & Assumptions

Given: an integer $n \geq 0$ and a fixed table $f : F_{2}^{n} \to F_{2}$ , with $h (x) : = (- 1)^{f (x)}$ and $\hat{h} (a) = E_{x} h (x) χ_{a} (x)$ .

[F1]

The BLR test chooses independent uniform $x, y \in F_{2}^{n}$ and accepts exactly when $f (x) + f (y) = f (x + y)$ ; its acceptance probability is denoted $α$ and $ε = 1 - α$ is its rejection probability. The linear functions are $ℓ_{a} (x) = a \cdot x$ with $a \in F_{2}^{n}$ , the normalized distance is $dist (f, g) = 2^{- n} # {x : f (x) \neq g (x)}$ , and for $n = 0$ the cube has one point and the sole linear function is $ℓ_{0} = 0$ (The BLR linearity test over F_2).

[F2]

With $h = (- 1)^{f}$ one has $2 α - 1 = E_{x, y} h (x) h (y) h (x + y) = \sum_{a} \hat{h} (a)^{3}$ , the sum being over the $2^{n}$ indices $a$ (The cubic Fourier identity for BLR).

[F3]

The characters are orthonormal and Parseval holds: $\sum_{a} \hat{h} (a)^{2} = E_{x} h (x)^{2} = 1$ , with $\hat{h} (a) = E_{x} h (x) χ_{a} (x)$ and $χ_{a} (x) = (- 1)^{a \cdot x}$ (Character orthogonality, inversion and Parseval).

[F4]

The Hadamard linearity constraint system ${Lin}_{n} (f)$ lists one ternary constraint for each ordered pair $(x, y)$ with tuple $(x, y, x + y)$ and relation $a + b = c$ , has $4^{n}$ constraints, and the fraction of its constraints violated by $f$ equals the BLR rejection probability $ε$ ; every linear table satisfies all its constraints (Hadamard linearity constraint system).

Proof

technique · direct calculation

1.1

The index set $F_{2}^{n}$ is finite and nonempty for every $n \geq 0$ , so $M : = \max_{a} \hat{h} (a)$ exists; it is a signed maximum, attained at some index, and no absolute value is taken.

F3givenalgebra

2.1

By [F2] and [F3], $2 α - 1 = \sum_{a} \hat{h} (a)^{3} \leq \sum_{a} M \hat{h} (a)^{2} = M \sum_{a} \hat{h} (a)^{2} = M$ , because $\hat{h} (a) \leq M$ and $\hat{h} (a)^{2} \geq 0$ for every index $a$ ; the sum has $2^{n} \geq 1$ terms, and the inequality is preserved by the finite sum.

F2F3step 1.1algebra

2.2

For each $a$ , since $h = (- 1)^{f}$ takes the value $+ 1$ exactly where $f = ℓ_{a}$ and $- 1$ exactly where $f \neq ℓ_{a}$ , $\hat{h} (a) = E_{x} h (x) χ_{a} (x) = \Pr [f (x) = ℓ_{a} (x)] - \Pr [f (x) \neq ℓ_{a} (x)] = 1 - 2 dist (f, ℓ_{a}),$ so $dist (f, ℓ_{a}) = (1 - \hat{h} (a)) / 2$ and therefore $dist (f, Λ) = \min_{a} (1 - \hat{h} (a)) / 2 = (1 - M) / 2$ , the minimum of the distances corresponding to the maximum of the coefficients.

F1F3step 1.1algebra

3.1

Combining steps 2.1 and 2.2, $ε = 1 - α = (1 - (2 α - 1)) / 2 \geq (1 - M) / 2 = dist (f, Λ)$ . This is the claimed inequality, with no hypothesis on $α$ ; in particular it is available when $α \leq 1 / 2$ , where the acceptance-based form of BLR soundness imposes no restriction on $f$ .

step 2.1step 2.2algebra

4.1

By [F4] the fraction of constraints of ${Lin}_{n} (f)$ violated by the table $f$ equals $ε$ , so step 3.1 says exactly that this violated fraction is at least $dist (f, Λ)$ ; the system has $4^{n}$ constraints of arity $3$ over $F_{2}$ , and the statement of the theorem is the conjunction of the two formulations.

F4step 3.1

5.1

Degenerate and extremal cases. For $n = 0$ we have $M = \hat{h} (0) = h (0) = (- 1)^{f (0)}$ , so $2 α - 1 = M$ and $dist (f, ℓ_{0}) = (1 - M) / 2$ : if $f (0) = 0$ then $ε = 0 = dist$ and the single constraint $(0, 0, 0)$ of the system is satisfied, while if $f (0) = 1$ then $ε = 1 = dist$ , matching the constraint $f (0) + f (0) = f (0)$ being violated. For a linear table $f = ℓ_{u}$ every constraint is satisfied by [F4], so $ε = 0 = dist (f, Λ)$ . The inequality is not in general an equality: for $n \geq 1$ and $f = ℓ_{u} + 1$ one has $f (x) + f (y) = ℓ_{u} (x + y)$ and $f (x + y) = ℓ_{u} (x + y) + 1$ for all $x, y$ , so every constraint is violated and $ε = 1$ , while $dist (f, ℓ_{u}) = 1$ and $dist (f, ℓ_{b}) = 1 / 2$ for $b \neq u$ give $dist (f, Λ) = 1 / 2 < 1$ .

F1F4step 3.1algebra∎

Remarks

What the bound does and does not say. The inequality $ε \geq dist (f, Λ)$ is one-sided: it converts a large distance into a large rejection probability and says nothing about the converse, and the example $f = ℓ_{u} + 1$ shows the two quantities can differ by a factor two. Read backwards it recovers the classical form of BLR acceptance implies agreement with a linear function, which concludes agreement with a linear function from acceptance above one half; the present statement covers all acceptance probabilities, including the ones for which that conclusion is vacuous.
Why the signed Fourier maximum is the right object. Step 2.2 identifies $dist (f, Λ)$ with $(1 - M) / 2$ where $M = \max_{a} \hat{h} (a)$ is the largest coefficient, and step 2.1 bounds $2 α - 1$ by the same $M$ ; both the geometry of the nearest linear table and the acceptance probability are controlled by that single signed maximum. A maximum of $∣ \hat{h} (a) ∣$ would not do: the constant table $f \equiv 1$ has $\hat{h} (0) = - 1$ and is at distance $1$ from the only linear table of dimension zero, while $ε = 1$ .
Use in the tester. The proportional form is what the exponential-base tester of An exponential-size constant-query base assignment tester needs for its first rejection family: a table that is not close to any linear function is rejected with probability bounded below by the constant distance threshold, and the Hadamard system of Hadamard linearity constraint system materializes the tests as explicit constraints.

Depends on

Used by

Dependency tree · two levels

7 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.1 Theorem 18.23 and §19.3 Theorem 19.9, printed pp. 364 and 390-391. (standard reference, not scraped)
Irit Dinur, The PCP theorem by gap amplification, §5 (distance of a table from linearity), printed pp. 17-18. (standard reference, not scraped)