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\).

Restricted monomials span by triangular elimination on subset cardinality. Complementing coordinates handles the upper half of the cube.

Reinterpolate a block when a variable reaches its middle level; use \(h_i^2=h_i\). Iterate over each monomial in the polynomial’s support.

On \(E=\{ p=H\} \), eliminate a majority factor from a block with \(|A_i|+d\le m\), using induction on weight. Counting retained generators gives \(2|E|\le 2^{k\ell }+(2N_{m,d})^k\). Apply the same bound to \(p+1\).

Bound \(N_{m,d}\le d\binom \ell m\) and \(\binom \ell m\le 2^\ell /\sqrt\ell \). The latter follows from the elementary inductive inequality \((3m+1)\binom {2m}{m}^2\le 16^m\).

Split the coordinates into \(R\) and its complement and factor the finite expectations. Each projected pattern has the same number of completions.

If a value vanishes, concentrate a normalized weight there. Otherwise, the reciprocal density gives an attaining weight; completing the square proves the matching lower bound for every admissible weight.

Use the variational minimum for concavity. For coordinate inclusion, induct on dimension using the arithmetic and harmonic means of the two slices, their monotonicity, and concavity. The endpoints follow directly from the definition.

Prove the one-bit inequality by a square, then induct on dimension. If the first coordinate is absent, average its two slices; if it is present, take the harmonic mean of their transforms. Apply concavity and the one-bit inequality before the induction hypotheses.

Since \(f\le B\), the mean of \(\sqrt f\) is at least \(B^{-1/2}\). Apply the harmonic mean inequality and bound \(\sqrt{\breve f}\) by one on the good event and by \((2\sqrt B)^{-1}\) outside it.

The positive harmonic mean forces every entry to be positive. Bound the indicator of \(f_R(z)\le b\) by \(b/f_R(z)\) and average.

The union of independent masks of rates \(p,q\) has rate \(p+q-pq\). Iterating \(h\) rate-\(r\) masks gives union rate \(1-(1-r)^h\le hr\); downward closure bounds its membership probability by \(\Pr _r(A)^h\). For \(r{\gt}0\), take \(h=\lfloor 1/(4r)\rfloor \), so \(hr\le 1/4\) and \(1/h\le 5r\), and use monotonicity in the sampling rate. At \(r=0\), the sampled set is empty and belongs to \(A\).

Split the cube into selected and complementary coordinates and factor the finite sums. The number of completions is \(2^{n-|R|}\).

Transfer the downward-closed family of good projections from rate \(1/4\) to rate \(r\), then apply Markov’s inequality to the reciprocal marginal density. The failure probability is at most \(5r(k/2+1)\le 1/64\). Convert the fraction of light normalized-density patterns into the stated count using the mass-to-density marginal bridge.

Completing and restricting patterns give the fiber bijection. The deficit and mass bounds follow by exponentiating the defining logarithm.

Group points by their restriction outside \(S\). The finite log-sum inequality lower-bounds the average log fiber size by \(\log |X|-|I\setminus S|\log 2\). Subtract from \(|S|\) and convert to base two.

Apply Markov’s inequality to the nonnegative fiber deficit.

Split the cube into selected and complementary coordinates. Normalize the uniform mass and exponentiate its entropy deficit.

Check the two Boolean coordinates and induct on dimension, then transport by an equivalence of finite coordinate types. Factor out unused coordinates to obtain the subtype formulation.

Condition on \(S=P\cup Q\). The entropy lemma bounds the fiber deficit by \(64k\) with probability \(63/64\). Lemma 10 with parameter \(64k\) bounds light projected patterns, again with probability \(63/64\). The conditional rate is at most \((32768k)^{-1}\). A projected density multiplied by \(2^{-D_\infty (X_{x,S})}\) equals the completion density. Outside the light patterns this is at least \(2^{-192k-2}\ge 2^{-194k}\). Their fraction is at most \(2^{-64k}\le 2^{-k-6}\). Combine the two good events.

Sample a uniform \(x\in X\) and a rate-\(p\) mask. On fibers of \(Y\) of density at least \(2^{-k}\), sample uniformly from their intersection with \(Y\); otherwise sample from the whole fiber. This variant of Korten’s guiding sets has density at most \(2^k\) relative to uniform fiber sampling. Its output belongs to \(Y\) with probability at least \(3/4\), and the completion estimate bounds its subsequent failure probability by \(1/16\). A Markov argument leaves mass at least \(1/4\) on the points in \(Y\) that are \((q,194k)\)-limits of \(X\). The output mass of any set \(A\) is at most \(2^k|A|/|X|\), proving \(|Y'|\ge 2^{|I|-2k-2}\).

Use \(x_i^a=x_i^{a\bmod 2}\) on the sign cube. Reducing an exponent modulo two cannot increase it. Apply these facts termwise to the polynomial’s support.

Multilinearize, apply OpenAI’s weighted-grading and edge-recovery theorem, and transport the Boolean sign encoding through the coordinate equivalence that respects flips and uniform expectation. The combinatorial average sensitivity equals the canonical total influence.

Noise sensitivity is bounded by \((1-\rho )I[f]/2\). Every Fourier coefficient above degree \(m\) contributes at least \(m+1\) times its weight to \(I[f]\).

Average the pointwise margin inequality, distribute the finite sum, and apply the triangle inequality and the per-feature correlation bounds.

Singleton sensitive coordinates are disjoint sensitive blocks. At a tree node, at most one block contains the queried coordinate; the other blocks remain sensitive for the selected subtree. Induct on the tree. For the upper bound, query all coordinates and output the function’s value.

OpenAI’s construction iterates nested Hamming-ball predicates using a regular tournament with a suitable edge labeling. The four sensitivity profiles give the quantitative ratio. Block composition of a seed with ratio greater than one yields the fixed-power family.

Apply the block-sensitivity bound to every exact tree. The lower bound at the all-zero input also transfers the divergence of block sensitivity.