betaFeedback

WorksComputer Science

An edge comparison with constant 3/2 and the coefficient 6/sqrt(2 pi) for the average sensitivity of polynomial threshold functions

Abstract

For every real polynomial threshold function f of degree at most d on the uniform cube {-1,1}^n we prove AS(f) <= min{n, 6 d b_n (n+d)/(n+2d)} <= (6/sqrt(2 pi)) d sqrt(n) < 2.394 d sqrt(n), where b_n = E|B_n - n/2| for B_n ~ Bin(n,1/2). The previous coefficient was 8/sqrt(2 pi) = 3.1915... The new ingredient is an edge comparison with constant 3/2 in place of 2 in OpenAI's weighted-grading argument: for every positive weight and every sign function h, the number of ordered equal-sign edges of h is at most (3/2)||MH+HM||_HS^2. The proof rests on the exact identity (Z_i M Z_i - M)^2 = I - A_i^2, where A_i is the grade-diagonal part of the multiplication by x_i. Combined with OpenAI's original coupling estimate alone, the lemma already gives AS(f) <= 6 d sqrt(n).

Result

For f:{−1,1}n→{−1,1}f:\{-1,1\}^{n}\to\{-1,1\} let AS⁡(f)=∑i=1nPr⁡{f(X)≠f(X⊕i)}\operatorname{AS}(f)=\sum_{i=1}^{n}\Pr\{f(X)\ne f(X^{\oplus i})\}, with XX uniform and X⊕iX^{\oplus i} obtained by reversing coordinate ii. OpenAI [1] proved AS⁡(sgn⁡p)≤8dn\operatorname{AS}(\operatorname{sgn}p)\le8d\sqrt{n} for every real polynomial pp of degree at most dd (with sgn⁡0=1\operatorname{sgn}0=1), uniformly in 1≤d≤n1\le d\le n. The probability step of that argument was then sharpened by Lagdive, Aglave and Damre to 3.833.83 [2] and to 8/2π8/\sqrt{2\pi} [3]; Anchen gave a Lean proof of the coefficient 3.7623.762 [4], and Q. Chen gave a self-contained reconstruction of the 8/2π8/\sqrt{2\pi} bound with the rational witness 399/125399/125 [5]. All these results keep OpenAI’s edge comparison [1 §4], which carries a factor 22. We replace it by 3/23/2.

Theorem 1. Let n,d≥1n,d\ge1, let pp be a real polynomial of degree at most dd, and let f=sgn⁡pf=\operatorname{sgn}p on {−1,1}n\{-1,1\}^{n}, with sgn⁡0=1\operatorname{sgn}0=1. Then

AS⁡(f)≤min⁡{n,6dbnn+dn+2d}≤62πdn<1197500dn.\operatorname{AS}(f)\le\min\left\{n,6d b_n\frac{n+d}{n+2d}\right\}\le\frac{6}{\sqrt{2\pi}}d\sqrt{n}<\frac{1197}{500}d\sqrt{n}.

Corollary 2. With OpenAI’s coupling estimate [1 §2] in place of the compensated one, Lemma 3 gives AS⁡(f)≤6dn\operatorname{AS}(f)\le6d\sqrt{n}.

The weighted grading

We use the notation of [1 §3]. Put Ω={−1,1}n\Omega=\{-1,1\}^{n}, N=2nN=2^n, and work in RΩ\mathbb{R}^{\Omega} with the counting inner product, so that the point masses δx\delta_x form an orthonormal basis; ∥B∥HS2=∑x,yBxy2\|B\|_{\mathrm{HS}}^2=\sum_{x,y}B_{xy}^2. Let VkV_k be the span of the characters χS\chi_S with ∣S∣≤k|S|\le k. Fix w:Ω→(0,∞)w:\Omega\to(0,\infty), let DD be the multiplication by w\sqrt{w}, and let Πk\Pi_k be the orthogonal projection onto Ek=DVk∩(DVk−1)⊥E_k=DV_k\cap(DV_{k-1})^\perp. Then dim⁡Ek=(nk)\dim E_k=\binom{n}{k}, the EkE_k are mutually orthogonal and span RΩ\mathbb{R}^{\Omega}, and

M=∑k=0n(k−n2)Πk,∥M∥HS2=nN4.M=\sum_{k=0}^{n}\left(k-\frac{n}{2}\right)\Pi_k,\qquad\|M\|_{\mathrm{HS}}^2=\frac{nN}{4}.

Let ZiZ_i be the multiplication by xix_i. It is a self-adjoint unitary commuting with DD, and ΠsZiΠr=0\Pi_sZ_i\Pi_r=0 for ∣s−r∣>1|s-r|>1 [1 §3]. For an operator XX and an integer tt put X(t)=∑kΠk+tXΠkX^{(t)}=\sum_k\Pi_{k+t}X\Pi_k; then X=∑tX(t)X=\sum_tX^{(t)}, (XY)(t)=∑r+s=tX(s)Y(r)(XY)^{(t)}=\sum_{r+s=t}X^{(s)}Y^{(r)}, and X=0X=0 if and only if every X(t)=0X^{(t)}=0. Write ρ(x,y)\rho(x,y) for Hamming distance, xix^i for xx with coordinate ii reversed, and

A0=∑xMxx2,F=∑ρ(x,y)≥2Mxy2.A_0=\sum_x M_{xx}^2,\qquad F=\sum_{\rho(x,y)\geq2}M_{xy}^2.

all sums being over ordered pairs.

The edge comparison

Lemma 3. Let w>0w>0 and h:Ω→{−1,1}h:\Omega\to\{-1,1\}, let HH be the multiplication by hh, and let EhE_h be the set of ordered pairs (x,y)(x,y) with ρ(x,y)=1\rho(x,y)=1 and h(x)=h(y)h(x)=h(y). Then

∣Eh∣≤32∥MH+HM∥HS2.|E_h|\leq\frac{3}{2}\lVert MH+HM\rVert_{\mathrm{HS}}^2.

More precisely, ∣Eh∣≤∥MH+HM∥HS2+4∑Mxy2|E_h|\leq\lVert MH+HM\rVert_{\mathrm{HS}}^2+4\sum M_{xy}^2, the sum running over the ordered pairs with ρ(x,y)≥3\rho(x,y)\geq3 and h(x)≠h(y)h(x)\ne h(y).

Proof. Step 1: an exact identity. Put Ai=Zi(0)A_i=Z_i^{(0)} and Bi=Zi(1)B_i=Z_i^{(1)}, so that Zi=Ai+Bi+Bi∗Z_i=A_i+B_i+B_i^* and AiA_i is self-adjoint. The parts of Zi2=IZ_i^2=I of shift 2 and 0 give Bi2=0B_i^2=0 and Ai2+BiBi∗+Bi∗Bi=IA_i^2+B_iB_i^*+B_i^*B_i=I. Since [M,Πk+1ZiΠk]=Πk+1ZiΠk[M,\Pi_{k+1}Z_i\Pi_k]=\Pi_{k+1}Z_i\Pi_k, we have Ci:=[M,Zi]=Bi−Bi∗C_i:=[M,Z_i]=B_i-B_i^*, hence

Ci∗Ci=BiBi∗+Bi∗Bi−Bi2−(Bi∗)2=I−Ai2.C_i^*C_i=B_iB_i^*+B_i^*B_i-B_i^2-(B_i^*)^2=I-A_i^2.

Put Gi=ZiCi=ZiMZi−MG_i=Z_iC_i=Z_iMZ_i-M. It is self-adjoint, and Gi2=Gi∗Gi=Ci∗CiG_i^2=G_i^*G_i=C_i^*C_i. Therefore

Gi2=I−Ai2,(Gi)xy=(xiyi−1)Mxy=−21{xi≠yi}Mxy.(1)G_i^2=I-A_i^2,\qquad(G_i)_{xy}=(x_iy_i-1)M_{xy}=-2\mathbf{1}_{\{x_i\ne y_i\}}M_{xy}. \tag*{(1)}

Step 2: edge deficits. The diagonal entry of (1) at xx reads 4∑y:xi≠yiMxy2=1−(Ai2)xx4\sum_{y:x_i\ne y_i}M_{xy}^2=1-(A_i^2)_{xx}. Separating the neighbour y=xiy=x^i,

14−Mxxi2=14ai(x)+∑y:xi≠yiρ(x,y)≥2Mxy2,ai(x):=(Ai2)xx=∥Aiδx∥2≥0.(2)\frac{1}{4}-M_{xx^i}^2=\frac{1}{4}a_i(x)+\sum_{\substack{y:x_i\ne y_i\\\rho(x,y)\geq2}}M_{xy}^2,\qquad a_i(x):=(A_i^2)_{xx}=\lVert A_i\delta_x\rVert^2\geq0. \tag*{(2)}

Summing (2) over xx and ii, and using ∑x,i(14−Mxxi2)=nN4−∑ρ=1Mxy2=A0+F\sum_{x,i}(\frac{1}{4}-M_{xx^i}^2)=\frac{nN}{4}-\sum_{\rho=1}M_{xy}^2=A_0+F,

A0=14∑i∥Ai∥HS2+∑ρ(x,y)≥2(ρ(x,y)−1)Mxy2.(3)A_0=\frac{1}{4}\sum_i\lVert A_i\rVert_{\mathrm{HS}}^2+\sum_{\rho(x,y)\geq2}(\rho(x,y)-1)M_{xy}^2. \tag*{(3)}

Step 3: counting. Call (x,i)(x,i) an equal slot if h(x)=h(xi)h(x)=h(x^i); there are ∣Eh∣|E_h| of them. Put Ah=∑(x,y)∈EhMxy2A_h=\sum_{(x,y)\in E_h}M_{xy}^2, and, for ρ(x,y)≥2\rho(x,y)\geq2, ν(x,y)=#{i:xi≠yi, h(xi)≠h(x)}\nu(x,y)=\#\{i:x_i\ne y_i,\ h(x^i)\ne h(x)\}. Writing 14=Mxxi2+(14−Mxxi2)\frac{1}{4}=M_{xx^i}^2+(\frac{1}{4}-M_{xx^i}^2) on each equal slot and using (2), then ai≥0a_i\geq0 and (3),

∣Eh∣4=Ah+14∑equal slotsai(x)+∑ρ(x,y)≥2Mxy2(ρ(x,y)−ν(x,y))≤Ah+A0+∑ρ(x,y)≥2Mxy2(1−ν(x,y)).\begin{aligned} \frac{|E_h|}{4}=A_h+\frac{1}{4}\sum_{\text{equal slots}}a_i(x)+\sum_{\rho(x,y)\geq2}M_{xy}^2\bigl(\rho(x,y)-\nu(x,y)\bigr) \\ &\leq A_h+A_0+\sum_{\rho(x,y)\geq2}M_{xy}^2\bigl(1-\nu(x,y)\bigr). \end{aligned}

On the other hand T=MH+HMT=MH+HM has entries (h(x)+h(y))Mxy(h(x)+h(y))M_{xy}, so 14∥T∥HS2=A0+Ah+Fh\frac{1}{4}\lVert T\rVert_{\mathrm{HS}}^2=A_0+A_h+F_h with Fh=∑ρ≥2, h(x)=h(y)Mxy2F_h=\sum_{\rho\geq2,\ h(x)=h(y)}M_{xy}^2. Hence

∣Eh∣−∥T∥HS24≤∑{x,y}:ρ≥2Mxy2(2−c(x,y)−2⋅1{h(x)=h(y)}),c(x,y)=ν(x,y)+ν(y,x),\frac{|E_h|-\lVert T\rVert_{\mathrm{HS}}^2}{4}\leq\sum_{\{x,y\}:\rho\geq2}M_{xy}^2\bigl(2-c(x,y)-2\cdot\mathbf{1}_{\{h(x)=h(y)\}}\bigr),\qquad c(x,y)=\nu(x,y)+\nu(y,x),

the sum running over unordered pairs. A pair with h(x)=h(y)h(x)=h(y) contributes at most 0. Let h(x)≠h(y)h(x)\ne h(y) and ρ(x,y)=2\rho(x,y)=2, with x,yx,y differing in i,ji,j. The edges counted by c(x,y)c(x,y) are {x,xi}\{x,x^i\}, {x,xj}\{x,x^j\}, {y,yi}={y,xj}\{y,y^i\}=\{y,x^j\} and {y,yj}={y,xi}\{y,y^j\}=\{y,x^i\}, the four edges of the square spanned by xx and yy. Each of the edge-disjoint paths x,xi,yx,x^i,y and x,xj,yx,x^j,y contains an edge on which hh changes, so c(x,y)≥2c(x,y)\ge2 and the contribution is at most 0. A pair with h(x)≠h(y)h(x)\ne h(y) and ρ≥3\rho\ge3 contributes at most 2Mxy22M_{xy}^2. This proves the second assertion.

Step 4. By (3), 2∑ρ≥3Mxy2≤∑ρ≥2(ρ−1)Mxy2≤A0≤14∥T∥HS22\sum_{\rho\ge3}M_{xy}^2\le\sum_{\rho\ge2}(\rho-1)M_{xy}^2\le A_0\le\frac{1}{4}\lVert T\rVert_{\mathrm{HS}}^2. Therefore ∣Eh∣≤∥T∥HS2+2A0≤32∥T∥HS2\lvert\mathcal{E}_h\rvert\le\lVert T\rVert_{\mathrm{HS}}^2+2A_0\le\frac{3}{2}\lVert T\rVert_{\mathrm{HS}}^2.

Remark 4. The edge comparison of [1 §4] states ∣Eh∣≤2∥MH+HM∥HS2\lvert\mathcal{E}_h\rvert\le2\lVert MH+HM\rVert_{\mathrm{HS}}^2. Identity (3) refines its inequality F≤A0F\le A_0, and (2) identifies each edge deficit exactly.

Proof of Theorem 1

The reduction is OpenAI’s [1 §5]. After a harmless perturbation pp has no zero on Ω\Omega; put w=∣p∣w=\lvert p\rvert, h=χ[n]fh=\chi_{[n]}f. Then AS⁡(f)=∣Eh∣/N\operatorname{AS}(f)=\lvert\mathcal{E}_h\rvert/N, and the random grades (R,S)(R,S) with Pr⁡{R=r,S=s}=N−1∥ΠsHΠr∥HS2\Pr\{R=r,S=s\}=N^{-1}\lVert\Pi_sH\Pi_r\rVert_{\mathrm{HS}}^2 have both marginals Bin⁡(n,1/2)\operatorname{Bin}(n,1/2), satisfy R+S≥n−dR+S\ge n-d, and N−1∥T∥HS2=E(R+S−n)2N^{-1}\lVert T\rVert_{\mathrm{HS}}^2=\mathbb{E}(R+S-n)^2. With U=SU=S, V=n−RV=n-R (same law, values in [0,n][0,n], V−U≤dV-U\le d), Lemma 3 gives

AS⁡(f)≤32E(U−V)2.\operatorname{AS}(f)\le\frac{3}{2}\mathbb{E}(U-V)^2.

The compensated coupling estimate of Lagdive, Aglave and Damre [3] (see also [5 Lemma 2]) states that equal-law variables in an interval of length LL, with V−U≤aV-U\le a and b=E∣U−EU∣b=\mathbb{E}\lvert U-\mathbb{E}U\rvert, satisfy E(U−V)2≤4abL+aL+2a\mathbb{E}(U-V)^2\le4ab\frac{L+a}{L+2a}. With L=nL=n, a=da=d, b=bnb=b_n this gives AS⁡(f)≤6dbn(n+d)/(n+2d)\operatorname{AS}(f)\le6db_n(n+d)/(n+2d); also AS⁡(f)≤n\operatorname{AS}(f)\le n trivially. The estimate bn(n+d)/(n+2d)≤n/(2π)b_n(n+d)/(n+2d)\le\sqrt{n/(2\pi)} for all n,d≥1n,d\ge1 is proved in [5 §6] from the Wallis inequalities; it gives the bound 62πdn\frac{6}{\sqrt{2\pi}}d\sqrt n.

For the rational witness: arctan⁡12+arctan⁡13=π4\arctan\frac{1}{2}+\arctan\frac{1}{3}=\frac{\pi}{4} and arctan⁡x>x−x33+x55−x77\arctan x>x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7} for 0<x≤10<x\le1 give π>1538665489888\pi>\frac{1538665}{489888} [5 (20)]. Hence

362π=18π<18⋅4898881538665=88179841538665<1432809250000=(1197500)2.\frac{36}{2\pi}=\frac{18}{\pi}<\frac{18\cdot489888}{1538665}=\frac{8817984}{1538665}<\frac{1432809}{250000}=\left(\frac{1197}{500}\right)^2.

the last inequality being 8817984⋅250000=2204496000000<2204613059985=1432809⋅15386658817984\cdot250000=2204496000000<2204613059985=1432809\cdot1538665.

Verification

The ancillary script VERIF_AS_EDGE.py (Python and numpy only) checks, for random weights and random sign functions with 3≤n≤73\le n\le7, the identities (1), (2) and (3), the exact form of Step 3 and the inequality of Lemma 3; it checks Theorem 1 on random polynomial threshold functions, the binomial estimate in exact arithmetic for 1≤n≤20001\le n\le2000, and the rational witness in integer arithmetic. These checks are verifications of the statements above, not part of their proofs.

Acknowledgements

Acknowledgements. The construction is OpenAI’s [1]; the compensated coupling and the binomial estimate are due to Lagdive, Aglave and Damre [3] and to Q. Chen [5]. This note was prepared with the assistance of Claude (Anthropic).

Meaux, France

References

  1. [1]OpenAI, Average sensitivity of polynomial threshold functions, OpenAI Math Release preprint, September 25, 2026, https://github.com/openai/math.
  2. [2]P. Lagdive, V. Aglave, S. Damre, An elementary improvement of the average sensitivity bound for polynomial threshold functions, Zenodo, https://doi.org/10.5281/zenodo.23269472.
  3. [3]P. Lagdive, V. Aglave, S. Damre, A compensated coupling bound for the average sensitivity of polynomial threshold functions, Research Square preprint rs-11323154, October 13, 2026.DOI
  4. [4]Anchen, Average sensitivity: a Lean proof with coefficient 3.762, https://github.com/Anchen-AI4Math/average-sensitivity-lean, October 2026.
  5. [5]Q. Chen, A uniform average-sensitivity bound, October 17, 2026, https://github.com/canghaimeng/openai-math-improvement (problems/bound-127).

Paper details

vlnc:W_3vg3xz6y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Anthropic Claude Opus

View statement
Looking for related papers…
Contents