# Threshold functions and a one-sided coupling *Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).* On the cube \(\Omega=\{-1,1\}^n\), the *average sensitivity* (or *total influence*) of \(f\colon\Omega\to\{-1,1\}\) is \[ I(f)=\sum_{i=1}^n\mathbb P\bigl(f(X)\neq f(X^{\oplus i})\bigr), \] where \(X\) is uniform on \(\Omega\) and \(x^{\oplus i}\) is \(x\) with the \(i\)-th coordinate reversed. It is the average over \(x\) of the sensitivity \(s(f,x)\) of [Sensitivity, block sensitivity and composition](course:sensitivity-and-block-sensitivity/sensitivity-block-sensitivity-and-composition), written for the values \(\pm1\) instead of \(0,1\). A *polynomial threshold function of degree at most \(d\)* is \(f=\operatorname{sgn}p\) for a real polynomial \(p\) of degree at most \(d\), with \(\operatorname{sgn}t=1\) for \(t\ge0\) and \(-1\) for \(t<0\). Gotsman and Linial proposed in 1994 that a certain symmetric function maximizes \(I(f)\) among such functions; this exact form is false, as shown by Chapman [Chapman] and independently by Kim, Maldonado and Wellens [KMW]. The asymptotic form, \(I(f)=O(d\sqrt n)\), remained open: Harsha, Klivans and Meka proved \(I(f)\le2^{O(d)}n^{1-1/(4d+6)}\), Diakonikolas, Raghavendra, Servedio and Tan independently proved \(I(f)\le2^{O(d)}(\log n)\,n^{1-1/(4d+2)}\) [DRST], and Kane proved \(\sqrt n(\log n)^{O(d\log d)}2^{O(d^2\log d)}\) [Kane]. OpenAI proved it in September 2026 with an absolute constant [OpenAI-G]: **Theorem** (OpenAI). If \(n\ge1\), \(1\le d\le n\), and \(p\) is a real polynomial of degree at most \(d\) in \(n\) variables, then \(f=\operatorname{sgn}p\) on \(\{-1,1\}^n\) satisfies \(I(f)\le8d\sqrt n\). This course proves it. The present lesson sets up the cube and shows that the order \(d\sqrt n\) is attained by symmetric examples (Proposition 2.2), and proves a probability estimate, the *one-sided coupling* (Lemma 3.1): random variables with the same law whose difference is bounded in one direction only are close in mean square. The lessons [A weighted grading of the cube](a-weighted-grading-of-the-cube.md) and [The Gotsman–Linial bound](the-gotsman-linial-bound.md) build an operator on functions on the cube, weighted by \(|p|\), whose matrix entries count the sensitive edges of \(f\), and turn the degree bound into a one-sided constraint on a pair of binomial random variables. ## 1. The cube For \(S\subseteq[n]=\{1,\dots,n\}\), the *character* \(\chi_S(x)=\prod_{i\in S}x_i\) is a function \(\Omega\to\{-1,1\}\), with \(\chi_\varnothing=1\), \(\chi_S\chi_T=\chi_{S\triangle T}\) and \(\sum_{x\in\Omega}\chi_S(x)=0\) for \(S\neq\varnothing\) (pair \(x\) with \(x^{\oplus i}\) for some \(i\in S\)). Hence the \(2^n\) characters are orthogonal for \(\langle a,b\rangle=\sum_x\overline{a(x)}b(x)\), with \(\langle\chi_S,\chi_T\rangle=2^n\mathbf 1_{S=T}\), and form a basis of the functions on \(\Omega\). Since \(x_i^2=1\) on \(\Omega\), every monomial agrees on \(\Omega\) with a character of no larger degree; so a real polynomial of degree at most \(d\) agrees on \(\Omega\) with a combination of characters \(\chi_S\), \(|S|\le d\). We say that a function on \(\Omega\) has *Fourier degree at most \(d\)* if it is such a combination. Call \(x,y\in\Omega\) *adjacent* if they differ in exactly one coordinate, and let \(\mathcal P_f\) be the set of ordered pairs \((x,y)\) of adjacent points with \(f(x)\neq f(y)\). Counting the pairs \((x,x^{\oplus i})\) gives the identity (1.1): \[ I(f)=\frac{|\mathcal P_f|}{2^n}=\frac1{2^n}\sum_{x\in\Omega}s(f,x). \] In particular \(I(f)\le n\). ## 2. Symmetric examples Let \(t(x)=\frac12(n+x_1+\dots+x_n)\), the number of coordinates equal to \(1\). **Proposition 2.1.** Let \(J\subseteq\{0,\dots,n-1\}\) and \(p_J(x)=\prod_{j\in J}\bigl(t(x)-j-\frac12\bigr)\), a polynomial of degree \(|J|\). Then \[ I(\operatorname{sgn}p_J)=\frac n{2^{n-1}}\sum_{j\in J}\binom{n-1}j. \] **Proof.** \(p_J\) never vanishes on \(\Omega\), and its sign changes between adjacent \(x,y\) exactly when \(\{t(x),t(y)\}=\{j,j+1\}\) for some \(j\in J\). There are \((n-j)\binom nj=n\binom{n-1}j\) unordered adjacent pairs with weights \(j\) and \(j+1\), hence twice as many ordered pairs; divide by \(2^n\) as in (1.1). \(\square\) **Proposition 2.2** (sharpness). Let \(n\ge17\), \(m=n-1\), \(c=\lceil m/2\rceil\), and \(1\le d\le1+\sqrt m/3\). For \(J=\{c,c+1,\dots,c+d-1\}\), \[ I(\operatorname{sgn}p_J)\ge\tfrac16\,d\sqrt n. \] **Proof.** *The central coefficient.* Put \(a_k=\binom{2k}k4^{-k}\). Then \(a_1=\frac12\) and \(a_{k+1}=a_k\frac{2k+1}{2k+2}\), and by induction \(a_k^2\ge\frac1{4k}\): indeed \((2k+1)^2(k+1)\ge k(2k+2)^2\) reduces to \(k+1\ge0\). So \(\binom{2k}k\ge4^k/(2\sqrt k)\). If \(m=2k\), this is \(\binom mc\ge2^m/\sqrt{2m}\); if \(m=2k+1\), then \(c=k+1\) and \(\binom m{k+1}=\binom{2k}k\frac{2k+1}{k+1}\), which is at least \(4^k/(2\sqrt k)\ge2^m/(2\sqrt{2m})\). In both cases \(\binom mc\ge2^m/(3\sqrt m)\). *Nearby coefficients.* For \(j=c+u\) with \(u\ge0\), \(\binom m{j+1}/\binom mj=\frac{m-j}{j+1}\), which is at least \(\frac{(m-1)/2-u}{(m+3)/2+u}\ge1-\frac{4u+4}m\). For \(0\le T\le\sqrt m/3\), using \(\prod(1-\epsilon_u)\ge1-\sum\epsilon_u\) for \(\epsilon_u\in[0,1]\), \[ \begin{aligned} &\binom m{c+T}\ge\binom mc\Bigl(1-\sum_{u=0}^{T-1}\frac{4u+4}m\Bigr)\\ &\quad =\binom mc\Bigl(1-\frac{2T^2+2T}m\Bigr)\ge\frac12\binom mc, \end{aligned} \] because \(2T^2\le\frac29m\) and \(2T\le\frac23\sqrt m\le\frac16m\) for \(m\ge16\). The numbers \(\epsilon_u=(4u+4)/m\) lie in \([0,1]\), since \(u\le T-1\) gives \(4u+4\le\frac43\sqrt m\le m\). *Conclusion.* Each \(j\in J\) is \(c+T\) with \(0\le T\le d-1\le\sqrt m/3\), and \(c+d-1\le\frac{m+1}2+\frac{\sqrt m}3\le m\), so each \(\binom mj\ge2^m/(6\sqrt m)\), and by Proposition 2.1 \[ \begin{aligned} &I(\operatorname{sgn}p_J)\ge\frac n{2^m}\cdot d\cdot\frac{2^m}{6\sqrt m}\\ &\quad =\frac{nd}{6\sqrt{n-1}}\ge\frac{d\sqrt n}6. \end{aligned} \] \(\square\) So the bound \(8d\sqrt n\) of the theorem is attained up to a constant factor for \(d\) up to about \(\sqrt n/3\). For \(d\ge\sqrt n/8\) the theorem gives nothing beyond \(I(f)\le n\). ## 3. A one-sided coupling **Lemma 3.1** (one-sided coupling; OpenAI). Let \(U,V\) be real random variables taking finitely many values, with the same distribution, mean \(\mu\) and variance \(\sigma^2\). If \(V-U\le a\) always, where \(a\ge0\), then \[ \mathbb E(U-V)^2\le8a\sigma. \] **Proof.** Let \(g(t)=\int_\mu^t|z-\mu|\,dz=\frac12(t-\mu)|t-\mu|\), a strictly increasing function. For \(u0\) exactly when \(V>U\). On that event \(0U}Y\bigr]\\ &\quad \le a\,\mathbb E\bigl(|U-\mu|+|V-\mu|\bigr)\le2a\sigma, \end{aligned} \] using \(\mathbb E|U-\mu|\le(\mathbb E(U-\mu)^2)^{1/2}=\sigma\). By the lower bound in (3.1), \((U-V)^2\le4|g(U)-g(V)|=4|Y|\) always. Taking expectations, \(\mathbb E(U-V)^2\le8a\sigma\). \(\square\) Nothing is assumed about the joint distribution of \(U\) and \(V\), and \(V-U\) may be very negative on rare events. Equality of the marginals is what balances the two directions, through the cancellation \(\mathbb E[g(V)-g(U)]=0\). Exercise 4.4 shows that the bound has the right order. ## 4. Exercises **Exercise 4.1** (easy). Compute \(I(f)\) for \(f(x)=x_1\), for \(f=\chi_{[n]}\), and for the majority function \(\operatorname{sgn}(x_1+\dots+x_n)\) with \(n\) odd. **Exercise 4.2** (easy). Show that \(I(f)=\sum_{S}|S|\,\widehat f(S)^2\), where \(\widehat f(S)=2^{-n}\langle\chi_S,f\rangle\). *Hint:* \(\mathbb P(f(X)\neq f(X^{\oplus i}))\) equals \(\frac14\mathbb E(f(X)-f(X^{\oplus i}))^2\). **Exercise 4.3** (medium). Show that the conclusion of Lemma 3.1 fails if \(U\) and \(V\) are not assumed to have the same distribution. **Exercise 4.4** (medium). Let \(U\) be uniform on \(\{0,1,\dots,L\}\) and \(V=U+1\) if \(U