Results on threshold functions, the weighted grading and the Gotsman–Linial bound, 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.

• Symmetric threshold functions — Proposition 2.1. The sign of prod_(j in J) (t(x) - j - 1/2), t the number of +1 coordinates, has average sensitivity n 2^(1-n) sum_(j in J) binom(n-1, j).
• Sharpness of the order d sqrt(n) — Proposition 2.2. For n >= 17 and 1 <= d <= 1 + sqrt(n-1)/3, a symmetric threshold function of degree d has average sensitivity at least d sqrt(n)/6.
• One-sided coupling (OpenAI) — Lemma 3.1. Equally distributed U, V with variance sigma^2 and V - U <= a satisfy E(U - V)^2 <= 8 a sigma.
• Hilbert-Schmidt and block norms — Lemma 1.1. The Hilbert-Schmidt norm is basis independent and splits over the blocks of an orthogonal decomposition; entries are bounded by the operator norm.
• The weighted grading — Lemma 2.1. The weighted degree increments have dimensions binom(n, k), the centred grading has squared Hilbert-Schmidt norm nN/4, and coordinate multiplications connect only equal or adjacent grades.
• Edges from the anticommutator (OpenAI) — Lemma 3.1. For every positive weight and sign function h, the number of ordered edges on which h is constant is at most 2 ||MH + HM||_HS^2.
• The asymptotic Gotsman-Linial conjecture (OpenAI) — Theorem 1.1. A polynomial threshold function of degree at most d on {-1,1}^n has average sensitivity at most 8 d sqrt(n).
• Noise sensitivity in Fourier terms — Lemma 2.1. NS_eta(f) = (1/2) sum_S (1 - (1 - 2 eta)^|S|) fhat(S)^2, nondecreasing in eta on [0, 1/2].
• Noise sensitivity of threshold functions (OpenAI) — Corollary 2.2. A polynomial threshold function of degree at most d has noise sensitivity at most 8 sqrt(2) d sqrt(eta).

Reading order

Read the lessons in order. The first sets up threshold functions and proves the coupling inequality. The second builds the weighted grading and counts edges with it. The third proves the theorem and the noise sensitivity bound. The course on sensitivity and block sensitivity is a companion, not a prerequisite.