LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-07

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.

Character orthogonality, inversion and Parseval

Statement

For $n \geq 0$ , real functions $h, k$ on $F_{2}^{n}$ and the normalized characters and coefficients, $E_{x} χ_{a} (x) χ_{b} (x) = {\begin{cases} 1 & a = b, \\ 0 & a \neq b, \end{cases} h (x) = \sum_{a} \hat{h} (a) χ_{a} (x),$ $E_{x} h (x) k (x) = \sum_{a} \hat{h} (a) \hat{k} (a), E_{x} h (x)^{2} = \sum_{a} \hat{h} (a)^{2} .$ Any two distinct linear Boolean functions $ℓ_{a}, ℓ_{b}$ disagree on exactly half the cube.

Facts & Assumptions

Given: The objects and hypotheses in the statement above.

[F1]

Characters are real signs (-1)^(a dot x), and coefficients are their normalized finite inner products with h (Characters and normalized Fourier coefficients).

Proof

1.1F1algebra

From the definitions, $χ_{a} χ_{b} = χ_{a + b}$ and $χ_{a} (x + y) = χ_{a} (x) χ_{a} (y)$ . If $a = b$ , their product is one everywhere. If $a \neq b$ , some coordinate $j$ of $a + b$ equals one. Pair $x$ with $x + e_{j}$ : the pairing is a fixed-point-free involution and reverses the sign of $χ_{a + b}$ . Its sum is zero. This proves orthogonality.

2.1F1step 1.1algebra

For fixed $x, y$ , sum $χ_{a} (x) χ_{a} (y) = χ_{a} (x + y)$ over $a$ . If $x = y$ , this sum is $2^{n}$ . Otherwise pair $a$ with $a + e_{j}$ at a nonzero coordinate of $x + y$ to get zero. Thus $\sum_{a} χ_{a} (x) χ_{a} (y) = 2^{n} 1_{x = y}$ . Substituting the coefficient definition gives $\sum_{a} \hat{h} (a) χ_{a} (x) = 2^{- n} \sum_{y} h (y) \sum_{a} χ_{a} (y) χ_{a} (x) = h (x)$ .

3.1step 1.1step 2.1algebra

Expand both $h$ and $k$ by the preceding identity and average their product. All sums are finite, so rearrangement gives $E h k = \sum_{a, b} \hat{h} (a) \hat{k} (b) E χ_{a} χ_{b} = \sum_{a} \hat{h} (a) \hat{k} (a)$ . Taking $k = h$ proves Parseval, also when either function is zero.

4.1step 1.1step 2.1step 3.1algebra∎

For $a \neq b$ , the character $χ_{a + b}$ is one where $ℓ_{a} = ℓ_{b}$ and minus one where they differ. Its zero mean therefore forces equal counts of agreement and disagreement. For $n = 0$ , there are no distinct indices; the sole character is one and every displayed Fourier identity is an equality of one-term sums. For $n = 1$ , the pairing interchanges the two cube points.

Depends on

Characters and normalized Fourier coefficients

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, January 2007 web draft, §19.3.1 and Lemma 19.7 pp.388–389; §18.4.1 p.363 (standard reference, not scraped)