OctoInformBeta

OpenAI preprint, September 2026 · §4. Recovering edges from the anticommutator

Lemma 3: |ℰh|≤2∥MH+HM∥HS2|\mathcal{E}_h|\le 2\|MH+HM\|_{\mathrm{HS}}^2 for a matrix MM on Ω\Omega under three conditions on its entries, and commutator bounds for centered gradings

Bounding the edges where hh is constant by the 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

The Boolean cube Ω={−1,1}n\Omega=\{-1,1\}^n of dimension nn is the set of the N=2nN=2^n points that assign a sign ±1\pm1 to each index ii between 11 and nn✦; the coordinate xix_i of a point xx is its sign at ii, the real number 11 or −1-1.✦ Points xx and yy are neighbors when their Hamming distance ρ(x,y)\rho(x,y), the number of indices at which they differ, is 11, and the ordered edges of Ω\Omega are the ordered pairs of neighbors.✦ The set ℰh\mathcal{E}_h of constant edges of a real function hh on Ω\Omega is the set of ordered edges along which hh is constant: ℰh={(x,y)∈Ω×Ω:ρ(x,y)=1,h(x)=h(y)}.\mathcal{E}_h=\{(x,y)\in\Omega\times\Omega:\ \rho(x,y)=1,\ h(x)=h(y)\}.(1)✦

In the proof of Theorem 1 of the source paper on the average sensitivity of polynomial threshold functions, f=sgn(p)f=\mathrm{sgn}(p) is a polynomial threshold function, with pp a real multilinear polynomial, and h=χfh=\chi f, with χ\chi the parity of all nn coordinates. Then ℰh\mathcal{E}_h is the set of ordered edges along which ff changes sign, and |ℰh|=NI(f)|\mathcal{E}_h|=N\,I(f) for the average sensitivity I(f)I(f).

The weight there is w=|p|w=|p|, and the centered grading built from ww is M=L−n2IdM=L-\tfrac{n}{2}\mathrm{Id}, where L=∑k=0nkΠkL=\sum_{k=0}^{n}k\Pi_k and Πk\Pi_k is the orthogonal projection onto Ek=Kk∩Kk−1⟂E_k=K_k\cap K_{k-1}^{\perp}, with Kk=DVkK_k=DV_k, K−1={0}K_{-1}=\{0\}, DD multiplication by w\sqrt{w} and VkV_k the span of the characters χS\chi_S with |S|≤k|S|\le k. With HH multiplication by hh, Lemma 3 bounds |ℰh||\mathcal{E}_h| through the Hilbert-Schmidt norm of the anticommutator T=MH+HMT=MH+HM.

The library states this bound for any complex matrix MM on Ω\Omega under three conditions on its entries. Two of them come from bounds on the commutators of MM with the multiplications by the coordinates xix_i, and the library bounds such commutators for the centered grading of a general family of orthogonal projections. The last part of the lemma is a counting inequality for nonnegative weights.

Matrices and Shells

A matrix on a finite set JJ is a complex matrix A=(Axy)x,y∈JA=(A_{xy})_{x,y\in J} with rows and columns indexed by JJ; on Ω\Omega these are the operators on ℂΩ\mathbb{C}^{\Omega} in the point basis. The commutator of two matrices AA and BB on JJ is [A,B]=AB−BA[A,B]=AB-BA. The squared Hilbert-Schmidt norm of a complex matrix AA with rows and columns indexed by finite sets is the sum of the squared moduli of its entries, ∥A∥HS2=∑x,y|Axy|2.\|A\|_{\mathrm{HS}}^2=\sum_{x,y}|A_{xy}|^2 .(2)✦

The multiplication matrix of a real function gg on Ω\Omega is the diagonal matrix on Ω\Omega with diagonal entries g(x)g(x).✦ For ii between 11 and nn, the matrix ZiZ_i is the multiplication matrix of the coordinate x↦xix\mapsto x_i.✦

The shell at kk of a function dd from a finite set AA to ℕ\mathbb{N} is the set Ak={a∈A:d(a)=k}A_k=\{a\in A: d(a)=k\}.✦ For the Hamming distance ρ\rho on A=Ω×ΩA=\Omega\times\Omega, the shell at 11 is the set of ordered edges and the shell at 00 is the diagonal.

Projection Families and Gradings

A finite family (Pk)(P_k) of matrices on JJ is an orthogonal projection family if it decomposes the identity into Hermitian projections: each PkP_k is self-adjoint and idempotent, Pk*=Pk=Pk2P_k^{*}=P_k=P_k^{2}; distinct members are orthogonal, PrPs=0P_rP_s=0 for r≠sr\ne s; and ∑kPk=Id\sum_k P_k=\mathrm{Id}.✦

The weighted grading of a finite family (Pk)(P_k) of matrices on JJ with real weights λ(k)\lambda(k) is the matrix ∑kλ(k)Pk\sum_k\lambda(k)P_k on JJ.✦ The centered grading of a family (Pk)k=0n(P_k)_{k=0}^{n} of matrices on JJ is its weighted grading with weights k−n2k-\tfrac{n}{2}, M=∑k=0n(k−n2)Pk.M=\sum_{k=0}^{n}\Bigl(k-\frac{n}{2}\Bigr)P_k .(3)✦

A matrix ZZ on JJ is block tridiagonal with respect to a family (Pk)k=0n(P_k)_{k=0}^{n} of matrices on JJ if PsZPr=0P_sZP_r=0 whenever |r−s|≥2|r-s|\ge 2.✦

The Claim

Theorem 1. (a) Let MM be a matrix on Ω\Omega, and let hh be a real function on Ω\Omega with values in {−1,1}\{-1,1\} and multiplication matrix HH. Suppose that ∥M∥HS2=nN/4\|M\|_{\mathrm{HS}}^2=nN/4, that ∑x,y∈Ωρ(x,y)|Mxy|2≤∥M∥HS2\sum_{x,y\in\Omega}\rho(x,y)\,|M_{xy}|^2\le\|M\|_{\mathrm{HS}}^2, and that |Mxy|2≤14|M_{xy}|^2\le\tfrac14 whenever x≠yx\ne y. Then |ℰh|≤2∥MH+HM∥HS2.|\mathcal{E}_h|\le 2\,\|MH+HM\|_{\mathrm{HS}}^2 .(4)✦

(b) Let (Pk)k=0n(P_k)_{k=0}^{n} be an orthogonal projection family of matrices on a finite set JJ with centered grading MM, and let ZZ be a unitary matrix on JJ that is block tridiagonal with respect to the family. Then, for all x,y∈Jx,y\in J, |[M,Z]xy|2≤1,|[M,Z]_{xy}|^2\le 1 ,(5)✦ and ∥[M,Z]∥HS2≤|J|.\|[M,Z]\|_{\mathrm{HS}}^2\le |J| .(6)✦

(c) Let MM be a matrix on Ω\Omega with |[M,Zi]xy|2≤1|[M,Z_i]_{xy}|^2\le 1 for every ii and all x,y∈Ωx,y\in\Omega. Then, for all distinct x,y∈Ωx,y\in\Omega, |Mxy|2≤14.|M_{xy}|^2\le\tfrac14 .(7)✦

(d) Let MM be a matrix on Ω\Omega with ∥[M,Zi]∥HS2≤N\|[M,Z_i]\|_{\mathrm{HS}}^2\le N for every ii. Then ∑x,y∈Ωρ(x,y)|Mxy|2≤nN4.\sum_{x,y\in\Omega}\rho(x,y)\,|M_{xy}|^2\le\frac{nN}{4} .(8)✦

(e) Let dd be a function from a finite set AA to ℕ\mathbb{N} with shells AkA_k, and let uu be a function from AA to [0,∞)[0,\infty) with ∑a∈Au(a)=|A1|/4\sum_{a\in A}u(a)=|A_1|/4 and ∑a∈Ad(a)u(a)≤∑a∈Au(a)\sum_{a\in A}d(a)\,u(a)\le\sum_{a\in A}u(a). Then ∑a∈A1(14−u(a))≤2∑a∈A0u(a).\sum_{a\in A_1}\Bigl(\tfrac14-u(a)\Bigr)\le 2\sum_{a\in A_0}u(a) .(9)✦

In the paper, the result reads: for n≥1n\ge1, a weight w:Ω→(0,∞)w:\Omega\to(0,\infty) with the centered grading MM built from it, and a function h:Ω→{−1,1}h:\Omega\to\{-1,1\} with HH multiplication by hh, |ℰh|≤2∥MH+HM∥HS2|\mathcal{E}_h|\le 2\|MH+HM\|_{\mathrm{HS}}^2.

What Is Checked

The claim is stated over the cube Ω\Omega with its coordinates xix_i, its Hamming distance and its ordered edges, complex matrices on finite sets with their squared Hilbert-Schmidt norm, the multiplication matrices HH and ZiZ_i, the set ℰh\mathcal{E}_h of constant edges, orthogonal projection families with their centered gradings, unitary matrices block tridiagonal with respect to such a family, and the shells of a function with values in ℕ\mathbb{N}. About these constructions the library also gives that the weighted grading of an orthogonal projection family acts as λ(k)\lambda(k) on the range of each PkP_k, and that a centered grading equals L−n2IdL-\tfrac{n}{2}\mathrm{Id}, with L=∑kkPkL=\sum_k kP_k, when its family sums to the identity.