LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 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.

Random binary subsums detect every nonzero discrepancy

Statement

For every nonzero $d \in F_{2}^{m}$ and uniform $z \in F_{2}^{m}$ , $\Pr [z \cdot d = 1] = \frac{1}{2} .$ The same conclusion applies whenever $d$ is a nonzero vector of violated quadratic equations or the difference of two distinct decoded prefixes.

Facts & Assumptions

Given: A nonzero binary vector $d \in F_{2}^{m}$ and the uniform distribution on the finite cube.

[F1]

Distinct Walsh–Hadamard messages in dimension $m \geq 1$ have tables that disagree on exactly half the coordinates. (Distinct Walsh–Hadamard words differ on half the cube)

Proof

1.1givenconstructalgebra

Since $d \neq 0$ , choose the least index $j$ with $d_{j} = 1$ , and let $e_{j}$ be its unit vector. The map $z \mapsto z + e_{j}$ is a fixed-point-free involution of the cube and $(z + e_{j}) \cdot d = z \cdot d + 1$ , so it pairs each outcome with one whose dot product has the opposite bit.

2.1F1step 1.1algebradischarge-construct∎

Each pair from step 1.1 has exactly one vector with $z \cdot d = 1$ , hence exactly $2^{m - 1}$ of the $2^{m}$ vectors satisfy the event and its uniform probability is $1 / 2$ . Equivalently these are precisely the coordinates where ${WH}_{m} (0)$ and ${WH}_{m} (d)$ disagree, consistent with the half-distance lemma in [F1]. Thus every nonzero violated-equation vector and every difference of distinct prefixes has the same detection probability; the number and correlations of its coordinates are irrelevant.

Depends on

Distinct Walsh–Hadamard words differ on half the cube

Used by

Dependency tree · two levels

2 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 random subsum principle and its applications, printed pp. 366–367 (standard reference, not scraped)