If \(j \in S\), translating by the unit vector \(e_j\) permutes the cube and negates \(\chi _S\), so \(\sum _x \chi _S(x) = -\sum _x \chi _S(x) = 0\). Orthonormality then follows from \(\chi _S \chi _T = \chi _{S \triangle T}\), since \(S \triangle T = \emptyset \) iff \(S = T\).

Substituting \(\widehat{f}(S) = 2^{-n} \sum _y f(y) \chi _S(y)\) and \(\chi _S(y)\chi _S(x) = \chi _S(x + y)\) gives \(\sum _S \widehat{f}(S)\chi _S(x) = 2^{-n} \sum _y f(y) \sum _S \chi _S(x + y)\), and \(\sum _S \chi _S(z)\) is \(2^n\) at \(z = 0\) and \(0\) elsewhere. Uniqueness comes from taking inner products with each \(\chi _T\). Two functions with the same coefficients have the same expansion.

The parities are orthonormal and span, so they form an orthonormal basis, and Plancherel is Parseval’s identity for that basis. For Boolean-valued \(f\), \(\langle f, f \rangle = \mathbb {E}[f^2] = 1\).

Take \(\chi _\emptyset = 1\) in the definition of \(\widehat{f}(\emptyset )\), then apply Plancherel and split off the empty set. For Boolean-valued functions, \(f^2 = 1\) pointwise, and \(f(x) g(x)\) is \(1\) where \(f\) and \(g\) agree and \(-1\) where they differ.

The variance is a sum of squared Fourier coefficients. For Boolean-valued \(f\), let \(p = \Pr [f = 1]\) and \(q = \Pr [f = -1]\). Then \(p + q = 1\) and \(\mathbb {E}[f] = p - q\), so \(\mathrm{Var}[f] = 1 - (p - q)^2 = 4pq\). Also \(\mathrm{dist}(f, 1) = q\) and \(\mathrm{dist}(f, -1) = p\), and \(2\min (p,q) \le 4pq \le 4\min (p,q)\).

Substitute \(x = y + z\) and use \(\chi _S(y + z) = \chi _S(y)\chi _S(z)\). The density claims follow by exchanging the two averages in \(\mathbb {E}[\varphi * \psi ]\) and by computing \(\mathbb {E}[1_A] = |A|/2^n\).

Regroup the Fourier expansion and Parseval’s sum by \(|S|\). The projection \(f^{=k}\) keeps exactly the coefficients with \(|S| = k\).

A multiplicative \(\pm 1\)-valued function is a character of \(\mathbb {F}_2^n\). Take \(S = \{ i : f(e_i) = -1\} \) and write each \(x\) as a sum of unit vectors.

The acceptance probability is \(\frac{1}{2} + \frac{1}{2} \langle f, f * f \rangle \). Then apply the convolution theorem.

Bound \(\sum _S \widehat{f}(S)^3 \le \max _S \widehat{f}(S)\) using Parseval, and convert the largest coefficient to a distance with \(\langle f, \chi _S \rangle = 1 - 2\, \mathrm{dist}(f, \chi _S)\).

\(y\) and \(x + y\) are each uniform. Apply a union bound to the two events where \(f\) disagrees with \(\chi _S\).

Read off coefficients using orthonormality, then apply Plancherel. The identities for \(T_1\) and \(T_0\) compare Fourier coefficients.

Term-by-term comparison of the spectral sums.

Compute \(\mathbb {E}_{y \sim N_\rho (x)}[\chi _S(y)] = \rho ^{|S|}\chi _S(x)\) and extend by linearity. The first step is to define the product distribution \(N_\rho (x)\) as a finite weighted average.

Exchange the sums over \(i\) and \(S\), and bound \(|S|\) by \(n\) or \(d\).

The flip is measure-preserving and negates exactly the parities containing \(i\). Then apply Parseval, and compare Fourier coefficients for \(L_i f = \chi _{\{ i\} } \cdot D_i f\).

For Boolean-valued \(f\), \((L_i f)^2\) is the indicator that \(i\) is pivotal at \(x\).

Every nonempty \(S\) has \(|S| \ge 1\).

Use \(1 - \rho ^k \le (1 - \rho ) k\) term by term.

The singletons are exactly the sets of size \(1\). Each inequality drops nonnegative terms from a spectral sum.

\(\widehat{f}(\{ i\} ) = \mathbb {E}[f(x)\chi (x_i)]\). By monotonicity this equals the probability that \(i\) is pivotal. For the second claim, apply Cauchy–Schwarz to \(\sum _i \widehat{f}(\{ i\} )\) and use \(W^1[f] \le 1\).

Differentiate the multilinear polynomial \(p \mapsto \mu _p(f = 1)\) one coordinate at a time. The first step is a \(p\)-biased expectation, which the library does not yet have (it has only the uniform measure).

Expand. The slack is \(8b^4/9 \ge 0\).

Induct on \(n\). Write \(f = g + x_n h\), where \(g\) and \(h\) do not depend on \(x_n\). Apply the base case pointwise, then the induction hypothesis to \(g\) and \(h\), with Cauchy–Schwarz. The noise operator factors as a product of one-bit operators, so a coordinate-restriction API for \(T_\rho \) is needed first.

Apply the theorem to \(T_{\sqrt{3}} f\), whose coefficients are at most \(\sqrt{3}^{\, k}\) times those of \(f\).

\(T_{1/\sqrt{3}}\) is self-adjoint, and \(4/3\) and \(4\) are Hölder conjugates.

Let \(\ell = f^{=1}\). Bound \(W^1[f] = \langle f, \ell \rangle \) by splitting on whether \(|\ell |\) exceeds a threshold. The tail is controlled by hypercontractive concentration of the linear form \(\ell \).

\(\ell = f^{=1}\) has \(\ell ^2\) close to \(1\) in \(L^2\). The Bonami lemma applied to the degree-2 polynomial \(\ell ^2 - 1\) forces one coefficient of \(\ell \) to dominate.

Apply the \((4/3, 2)\) bound to each \(D_i f\). For Boolean-valued \(f\), \(\lVert D_i f \rVert _{4/3}^{4/3} = \mathrm{Inf}_i[f]\), which gives \(\sum _i \mathrm{Stab}_{1/3}[D_i f] \le \sum _i \mathrm{Inf}_i[f]^{3/2}\). Compare with the low-degree part of \(\mathbf{I}[f]\).

Let \(J\) be the coordinates with influence above \(2^{-O(\mathbf{I}[f]/\varepsilon )}\). Hypercontractivity bounds the Fourier weight outside \(J\) and above degree \(O(\mathbf{I}[f]/\varepsilon )\). Round the restriction of \(f\) to \(J\) to \(\pm 1\). The junta predicate has to be defined first.

\(F\) is a sum over leaves of the leaf label times the indicator of the path. The indicator of a depth-\(t\) path is a product of \(t\) functions \((1 \pm \chi (x_i))/2\).

Relate \(W^{{\gt}k}[F]\) to the expected high-degree weight of a random restriction of \(F\). The restriction formula is \(\widehat{F_{J \mid z}}(S) = \sum _{T \subseteq \bar J} \widehat{F}(S \cup T)\chi _T(z)\). By the switching lemma, the restricted circuit is a shallow decision tree with high probability. A Fourier-side restriction API on the cube is needed first.

The real-valued view of parity is \(\chi _{[n]}\), whose entire Fourier weight sits at degree \(n\).