Results on Fourier coefficients, asymptotically normal scores, reports and amplification, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Fourier expansion on the cube — Lemma 1.1. Characters are orthonormal; every function on the cube equals its Fourier expansion, with Parseval's identity; degree is subadditive under products.
• Linear bound (Nisan-Szegedy) — Proposition 2.1. For Boolean f, the sum of the |f^({i})| is at most the total influence, which is at most deg f.
• Calculus of observations — Lemma 3.1. Functions of observations with cell degree bounds have bounded degree; scores add over disjoint blocks; sign(T_F) has linear correlation E|T_F|.
• Fourth moments of averages — Lemma 1.2. E Z_M^4 = E T^4/(M v^2) + 3(M-1)/M for normalized sums of bounded centred variables.
• Restricted moments — Lemma 2.1. If Z_n is asymptotically standard normal with mean 0 and variance 1, then E[1_J(Z_n) Z_n^a] tends to its Gaussian value for finite unions of intervals J and a <= 2.
• Product portmanteau — Lemma 3.1. For independent copies and a Borel set with Gaussian-null boundary, probabilities and restricted sums converge to their Gaussian values.
• Perturbations of asymptotic normality — Lemma 4.1. Perturbations small in L^2 and scalings tending to one preserve asymptotic standard normality.
• Amplification criterion — Proposition 1.2. A rule on r inputs with coordinate cost d retaining variance at least d + eta for asymptotically normal inputs gives arbitrarily large ratios v(F)/D.
• Cost of the refined report — Lemma 2.1. The indicator of the tagged event is a combination of functions of m inputs, so the refined report has coordinate cost m.
• Retained variance of the refined report — Lemma 2.2. Var(E[L | W]) >= m + E[1_A (1 - (L - b)^2)] for every real b.
• Gaussian design — Lemma 3.1. Intervals and a selector for which the Gaussian deficit d_A exceeds (3/4) p_*.
• Unbounded violations of the square-root degree bound (OpenAI) — Theorem 4.3. For every C > 0 there is a nonconstant Boolean f with sum of f^({i}) > C sqrt(deg f).
• Coarse report — Proposition 5.1. The report with single marks on both exceptional events also satisfies the amplification criterion.
• Refinement — Lemma 1.1. An event of cost q-1 on which the sum has conditional variance below one extends to a costed partition with V > c = q - p_A.
• Amplification from a mean cost advantage — Theorem 2.2. A costed partition with Gaussian-null cell boundaries and V > c gives arbitrarily large ratios v(F)/D.
• Weighted mixture — Lemma 3.1. For large R the weighted-mixture event has positive probability and conditional variance of the sum below one.
• Coarse report with small width — Proposition 3.2. The coarse report retains m + Q H_w(U); H_w(G) tends to 1, and the small-width schedule satisfies the amplification criterion.

Reading order

Read the lessons in order; each uses the notation and results of the previous ones.