OctoInformBeta

OpenAI preprint, September 2026 · §5. Parity and the binomial coupling (proof of Theorem 1)

Assembly of the proof: For ff with values ±1\pm1 and projections P0,…,PnP_0,\dots,P_n with tr⁡Pk=(nk)\operatorname{tr}P_k=\binom{n}{k}, each ZiZ_i block tridiagonal and PsHPr=0P_sHP_r=0 for r+s<n−dr+s<n-d

Average sensitivity at most 8dn8d\sqrt{n} from graded projections.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The cube Ω={−1,1}n\Omega=\{-1,1\}^n is the set of points x=(x1,…,xn)x=(x_1,\dots,x_n) whose coordinates xix_i are the real numbers ±1\pm1; it has N=2nN=2^n points.✦ Take a real multilinear polynomial pp of degree at most dd on Ω\Omega and the polynomial threshold function f=sgn⁡(p)f=\operatorname{sgn}(p), where sgn⁡(t)=1\operatorname{sgn}(t)=1 for t≥0t\ge0 and sgn⁡(t)=−1\operatorname{sgn}(t)=-1 for t<0t<0. The question is how large its average sensitivity I(f)I(f), defined below, can be in terms of dd and nn. Theorem 1 of the paper behind the library, Average sensitivity of polynomial threshold functions, answers it, and the last step of its proof turns statements about operators on ℂΩ\mathbb{C}^\Omega into a bound on I(f)I(f).

In that proof the weight is w=|p|w=|p|, and DD is the diagonal matrix on ℂΩ\mathbb{C}^\Omega that multiplies each value at a point xx by w(x)\sqrt{w(x)}. For k=0,…,nk=0,\dots,n, Πk\Pi_k is the orthogonal projection onto Ek=Kk∩Kk−1⟂E_k=K_k\cap K_{k-1}^{\perp}, where Kk=DVkK_k=DV_k is the image under DD of the span VkV_k of the characters χS(x)=∏j∈Sxj\chi_S(x)=\prod_{j\in S}x_j with |S|≤k|S|\le k, and K−1={0}K_{-1}=\{0\}. The centered grading MM of the projections Π0,…,Πn\Pi_0,\dots,\Pi_n is the matrix M=∑k=0nkΠk−n2IdM=\sum_{k=0}^n k\,\Pi_k-\frac n2\,\mathrm{Id} on ℂΩ\mathbb{C}^\Omega.

The full parity χ\chi is the character of all nn coordinates, χ(x)=x1x2⋯xn\chi(x)=x_1x_2\cdots x_n.✦ With h=χfh=\chi f and HH multiplication by hh, put T=MH+HMT=MH+HM. The set ℰh\mathcal{E}_h consists of the ordered pairs (x,y)(x,y) of points of Ω\Omega at Hamming distance ρ(x,y)=1\rho(x,y)=1 with h(x)=h(y)h(x)=h(y).

The library states the last step in two forms: one in which a family of orthogonal projections P0,…,PnP_0,\dots,P_n on ℂΩ\mathbb{C}^\Omega takes the place of Π0,…,Πn\Pi_0,\dots,\Pi_n, and one that involves only I(f)I(f) and two real numbers.

Average Sensitivity

For a point xx of Ω\Omega and a coordinate ii, the flip x⊕ix^{\oplus i} is the point of Ω\Omega obtained from xx by reversing its ii-th coordinate.✦ A sensitive vertex of a real function ff on Ω\Omega in direction ii is a point xx of Ω\Omega with f(x⊕i)≠f(x)f(x^{\oplus i})\neq f(x).✦ The average sensitivity I(f)I(f) of a real function ff on Ω\Omega is the number of its sensitive vertices, counted over the nn directions and divided by NN; for XX uniform on Ω\Omega, I(f)=1N∑i=1n|{x∈Ω:f(x⊕i)≠f(x)}|=∑i=1n𝑷{f(X)≠f(X⊕i)}.I(f)=\frac1N\sum_{i=1}^n\bigl|\{x\in\Omega : f(x^{\oplus i})\neq f(x)\}\bigr| =\sum_{i=1}^n\mathbf{P}\{f(X)\neq f(X^{\oplus i})\}.(1)✦

Multiplication Matrices and Projection Families

The multiplication matrix of a real function gg on Ω\Omega is the diagonal complex matrix indexed by Ω\Omega with entry g(x)g(x) at each point xx.✦ For i=1,…,ni=1,\dots,n, the coordinate matrix ZiZ_i is the multiplication matrix of the coordinate function x↦xix\mapsto x_i.✦

A family of complex square matrices PkP_k, one for each kk in a finite index set and all indexed by the same finite set, is an orthogonal projection family if it decomposes the identity into mutually orthogonal self-adjoint projections: Pk*=Pk,Pk2=Pk,PrPs=0(r≠s),∑kPk=Id.P_k^{*}=P_k,\qquad P_k^2=P_k,\qquad P_rP_s=0\quad(r\neq s),\qquad \sum_k P_k=\mathrm{Id}.(2)✦

A complex square matrix ZZ is block tridiagonal with respect to a family P0,…,PnP_0,\dots,P_n of complex square matrices indexed by the same finite set as ZZ if ZZ couples the index rr only to the indices r−1r-1, rr and r+1r+1: PsZPr=0whenever |r−s|>1.P_sZP_r=0\qquad\text{whenever } |r-s|>1.(3)✦

The Claim

Theorem 1. Let dd be a nonnegative integer and ff a real function on the cube Ω={−1,1}n\Omega=\{-1,1\}^n.

  1. Suppose that ff takes only the values ±1\pm1, and let HH be multiplication by h=χfh=\chi f. Let P0,…,PnP_0,\dots,P_n be an orthogonal projection family (2) of complex square matrices indexed by Ω\Omega such that tr⁡Pk=(nk)\operatorname{tr}P_k=\binom{n}{k} for every kk, every coordinate matrix ZiZ_i is block tridiagonal (3) with respect to P0,…,PnP_0,\dots,P_n, and PsHPr=0P_sHP_r=0 whenever r+s<n−dr+s<n-d. Then I(f)≤8dn.I(f)\le 8d\sqrt n.(4)✦

  2. Suppose that CC and QQ are real numbers with I(f)=C/NI(f)=C/N, C≤2QC\le 2Q and Q≤4dnNQ\le 4d\sqrt n\,N. Then I(f)≤8dn.I(f)\le 8d\sqrt n.(5)✦

In the paper, the result reads I(f)=|ℰh|/N≤(2/N)∥T∥HS2≤8dnI(f)=|\mathcal{E}_h|/N\le(2/N)\|T\|_{\mathrm{HS}}^2\le 8d\sqrt n, with |ℰh||\mathcal{E}_h| in the place of CC and ∥T∥HS2\|T\|_{\mathrm{HS}}^2 in that of QQ.

What Is Checked

The claims (4) and (5) are stated over the cube Ω\Omega with its coordinates xix_i and flips x⊕ix^{\oplus i}, and over the average sensitivity (1) built from sensitive vertices; (4) is stated also over the full parity χ\chi, the multiplication matrices ZiZ_i and HH, orthogonal projection families and block tridiagonal matrices.