OctoInformBeta

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

The block coupling and the anticommutator bound: When projections Πk\Pi_k of trace (nk)\binom nk sum to the identity, a unitary HH with ΠsHΠr=0\Pi_sH\Pi_r=0 for r+s<n−dr+s<n-d has ∥MH+HM∥HS2≤4dn2n\|MH+HM\|_{\mathrm{HS}}^2\le4d\sqrt n\,2^n

A binomial coupling bounds the centered anticommutator.

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

In the proof of Theorem 1 of the paper on the average sensitivity of polynomial threshold functions, take a polynomial threshold function f=sgn⁡(p)f=\operatorname{sgn}(p) of degree at most dd on the cube Ω={−1,1}n\Omega=\{-1,1\}^n, with w=|p|w=|p| and h=χfh=\chi f, where χ\chi is the full parity, the character of all nn coordinates. With DD the multiplication by w\sqrt w and VkV_k the span of the characters χS\chi_S with |S|≤k|S|\le k, put Kk=DVkK_k=DV_k, K−1={0}K_{-1}=\{0\} and Ek=Kk∩Kk−1⟂E_k=K_k\cap K_{k-1}^\perp; the space ℂΩ\mathbb{C}^\Omega is the orthogonal sum of E0,…,EnE_0,\dots,E_n, and the projections Π0,…,Πn\Pi_0,\dots,\Pi_n onto these pieces give the grading L=∑kkΠkL=\sum_k k\Pi_k and the centered grading M=L−n2IdM=L-\tfrac n2\,\mathrm{Id}. The operator HH of multiplication by hh is unitary, and the quantity to bound is ∥T∥HS2\|T\|_{\mathrm{HS}}^2 for the anticommutator T=MH+HMT=MH+HM.

An operator BB on ℂΩ\mathbb{C}^\Omega splits into the blocks ΠsBΠr\Pi_sB\Pi_r, one for each pair (r,s)(r,s) in {0,…,n}2\{0,\dots,n\}^2, the block ΠsBΠr\Pi_sB\Pi_r carrying ErE_r into EsE_s. The item is about these blocks: how anticommuting with MM acts on them, and how the masses ∥ΠsHΠr∥HS2\|\Pi_sH\Pi_r\|_{\mathrm{HS}}^2 of the blocks of a unitary HH spread over the pairs (r,s)(r,s).

The library states the item for complex matrices with rows and columns indexed by a finite set ι\iota, the operators on ℂι\mathbb{C}^\iota, with any family of mutually orthogonal projections Π0,…,Πn\Pi_0,\dots,\Pi_n summing to the identity in place of the projections onto the EkE_k, and any matrix HH in place of multiplication by hh.

Projection Families and Block Masses

Fix a finite set ι\iota. The squared Hilbert-Schmidt norm of a complex matrix AA with rows indexed by ι\iota and columns indexed by a finite set κ\kappa is ∥A∥HS2=∑i∈ι∑j∈κ|Aij|2\|A\|_{\mathrm{HS}}^2=\sum_{i\in\iota}\sum_{j\in\kappa}|A_{ij}|^2.✦

A family of matrices Πk\Pi_k on ℂι\mathbb{C}^\iota, one for each kk in a finite index set, is an orthogonal projection family if each Πk\Pi_k is self-adjoint and idempotent, Πk*=Πk=Πk2\Pi_k^*=\Pi_k=\Pi_k^2, if ΠrΠs=0\Pi_r\Pi_s=0 for r≠sr\neq s, and if ∑kΠk=Id\sum_k\Pi_k=\mathrm{Id}.✦

The grading of a family of matrices Πk\Pi_k on ℂι\mathbb{C}^\iota with real weights λk\lambda_k is the matrix ∑kλkΠk\sum_k\lambda_k\Pi_k.✦ The centered grading MM of a family Π0,…,Πn\Pi_0,\dots,\Pi_n of matrices on ℂι\mathbb{C}^\iota is the matrix obtained from the grading by taking the weights λk=k−n2\lambda_k=k-\tfrac n2: M=∑k=0n(k−n2)Πk.M=\sum_{k=0}^{n}\Bigl(k-\frac n2\Bigr)\Pi_k.(1)✦

The binomial weights of order nn are the probabilities βn(k)=(nk)2−n\beta_n(k)=\binom nk2^{-n}, k=0,…,nk=0,\dots,n, of the binomial law Bin(n,12)\mathrm{Bin}(n,\tfrac12).✦

The block coupling weight of a family Π0,…,Πn\Pi_0,\dots,\Pi_n and a matrix HH on ℂι\mathbb{C}^\iota is the function γ\gamma on {0,…,n}2\{0,\dots,n\}^2 given by γ(r,s)=∥ΠsHΠr∥HS22n.\gamma(r,s)=\frac{\|\Pi_sH\Pi_r\|_{\mathrm{HS}}^2}{2^n}.(2)✦

The Claim

Theorem 1. Let ι\iota be a finite set, nn and dd natural numbers, Π0,…,Πn\Pi_0,\dots,\Pi_n and HH matrices on ℂι\mathbb{C}^\iota, MM the centered grading (1) of the Πk\Pi_k, and γ\gamma the block coupling weight (2) of the Πk\Pi_k and HH.

  1. If the Πk\Pi_k form an orthogonal projection family, then every matrix BB on ℂι\mathbb{C}^\iota satisfies, for all r,s∈{0,…,n}r,s\in\{0,\dots,n\}, Πs(MB+BM)Πr=(s+r−n)ΠsBΠr,\Pi_s(MB+BM)\Pi_r=(s+r-n)\,\Pi_sB\Pi_r,(3)✦ and ∥MB+BM∥HS2=∑r=0n∑s=0n(s+r−n)2∥ΠsBΠr∥HS2.\|MB+BM\|_{\mathrm{HS}}^2=\sum_{r=0}^{n}\sum_{s=0}^{n}(s+r-n)^2\,\|\Pi_sB\Pi_r\|_{\mathrm{HS}}^2.(4)✦

  2. Suppose the Πk\Pi_k form an orthogonal projection family with ∥Πk∥HS2=(nk)\|\Pi_k\|_{\mathrm{HS}}^2=\binom nk for every kk. If H*H=IdH^*H=\mathrm{Id}, then for every r∈{0,…,n}r\in\{0,\dots,n\} ∑s=0nγ(r,s)=βn(r),\sum_{s=0}^{n}\gamma(r,s)=\beta_n(r),(5)✦ and if HH*=IdHH^*=\mathrm{Id}, then for every s∈{0,…,n}s\in\{0,\dots,n\} ∑r=0nγ(r,s)=βn(s).\sum_{r=0}^{n}\gamma(r,s)=\beta_n(s).(6)✦

  3. If ΠsHΠr=0\Pi_sH\Pi_r=0 whenever r+s<n−dr+s<n-d, then supp⁡γ⊆{(r,s):r+s≥n−d}.\operatorname{supp}\gamma\subseteq\{(r,s):r+s\ge n-d\}.(7)✦

  4. If (ars)r,s=0n(a_{rs})_{r,s=0}^{n} is an array of nonnegative reals with row sums ∑sars=(nr)\sum_s a_{rs}=\binom nr for every rr and column sums ∑rars=(ns)\sum_r a_{rs}=\binom ns for every ss, and with ars=0a_{rs}=0 whenever r+s<n−dr+s<n-d, then ∑r=0n∑s=0n(s+r−n)2ars≤4dn2n.\sum_{r=0}^{n}\sum_{s=0}^{n}(s+r-n)^2\,a_{rs}\le 4d\sqrt n\,2^n.(8)✦

  5. If the Πk\Pi_k form an orthogonal projection family with tr⁡Πk=(nk)\operatorname{tr}\Pi_k=\binom nk for every kk, HH is unitary, and ΠsHΠr=0\Pi_sH\Pi_r=0 whenever r+s<n−dr+s<n-d, then ∥MH+HM∥HS2≤4dn2n.\|MH+HM\|_{\mathrm{HS}}^2\le 4d\sqrt n\,2^n.(9)✦

In the paper, the result reads: for T=MH+HMT=MH+HM and N=2nN=2^n, ΠsTΠr=(s+r−n)ΠsHΠr\Pi_sT\Pi_r=(s+r-n)\Pi_sH\Pi_r; the weights ∥ΠsHΠr∥HS2/N\|\Pi_sH\Pi_r\|_{\mathrm{HS}}^2/N form the law of a pair (R,S)(R,S) with Bin(n,12)\mathrm{Bin}(n,\tfrac12) marginals supported on R+S≥n−dR+S\ge n-d; and Lemma 2 with U=SU=S, V=n−RV=n-R, a=da=d and σ=n/2\sigma=\sqrt n/2 gives ∥T∥HS2/N≤4dn\|T\|_{\mathrm{HS}}^2/N\le 4d\sqrt n.

What Is Checked

The claim is stated over families Π0,…,Πn\Pi_0,\dots,\Pi_n and matrices HH on ℂι\mathbb{C}^\iota for a finite set ι\iota, orthogonal projection families, the centered grading MM, the squared Hilbert-Schmidt norm, the binomial weights βn\beta_n and the block coupling weight γ\gamma, and in part (d) over arrays of nonnegative reals indexed by {0,…,n}2\{0,\dots,n\}^2.