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} let AS(f)=∑i=1nPr{f(X)=f(X⊕i)}, with X uniform and X⊕i obtained by reversing coordinate i. OpenAI [1] proved AS(sgnp)≤8dn for every real polynomial p of degree at most d (with sgn0=1), uniformly in 1≤d≤n. The probability step of that argument was then sharpened by Lagdive, Aglave and Damre to 3.83[2] and to 8/2π[3]; Anchen gave a Lean proof of the coefficient 3.762[4], and Q. Chen gave a self-contained reconstruction of the 8/2π bound with the rational witness 399/125[5]. All these results keep OpenAI’s edge comparison [1 §4], which carries a factor 2. We replace it by 3/2.
Theorem 1. Let n,d≥1, let p be a real polynomial of degree at most d, and let f=sgnp on {−1,1}n, with sgn0=1. Then
AS(f)≤min{n,6dbnn+2dn+d}≤2π6dn<5001197dn.
Corollary 2. With OpenAI’s coupling estimate [1 §2] in place of the compensated one, Lemma 3 gives AS(f)≤6dn.
The weighted grading
We use the notation of [1 §3]. Put Ω={−1,1}n, N=2n, and work in RΩ with the counting inner product, so that the point masses δx form an orthonormal basis; ∥B∥HS2=∑x,yBxy2. Let Vk be the span of the characters χS with ∣S∣≤k. Fix w:Ω→(0,∞), let D be the multiplication by w, and let Πk be the orthogonal projection onto Ek=DVk∩(DVk−1)⊥. Then dimEk=(kn), the Ek are mutually orthogonal and span RΩ, and
M=k=0∑n(k−2n)Πk,∥M∥HS2=4nN.
Let Zi be the multiplication by xi. It is a self-adjoint unitary commuting with D, and ΠsZiΠr=0 for ∣s−r∣>1[1 §3]. For an operator X and an integer t put X(t)=∑kΠk+tXΠk; then X=∑tX(t), (XY)(t)=∑r+s=tX(s)Y(r), and X=0 if and only if every X(t)=0. Write ρ(x,y) for Hamming distance, xi for x with coordinate i reversed, and
A0=x∑Mxx2,F=ρ(x,y)≥2∑Mxy2.
all sums being over ordered pairs.
The edge comparison
Lemma 3. Let w>0 and h:Ω→{−1,1}, let H be the multiplication by h, and let Eh be the set of ordered pairs (x,y) with ρ(x,y)=1 and h(x)=h(y). Then
∣Eh∣≤23∥MH+HM∥HS2.
More precisely, ∣Eh∣≤∥MH+HM∥HS2+4∑Mxy2, the sum running over the ordered pairs with ρ(x,y)≥3 and h(x)=h(y).
Proof.Step 1: an exact identity. Put Ai=Zi(0) and Bi=Zi(1), so that Zi=Ai+Bi+Bi∗ and Ai is self-adjoint. The parts of Zi2=I of shift 2 and 0 give Bi2=0 and Ai2+BiBi∗+Bi∗Bi=I. Since [M,Πk+1ZiΠk]=Πk+1ZiΠk, we have Ci:=[M,Zi]=Bi−Bi∗, hence
Ci∗Ci=BiBi∗+Bi∗Bi−Bi2−(Bi∗)2=I−Ai2.
Put Gi=ZiCi=ZiMZi−M. It is self-adjoint, and Gi2=Gi∗Gi=Ci∗Ci. Therefore
Summing (2) over x and i, and using ∑x,i(41−Mxxi2)=4nN−∑ρ=1Mxy2=A0+F,
A0=41i∑∥Ai∥HS2+ρ(x,y)≥2∑(ρ(x,y)−1)Mxy2.(3)
Step 3: counting. Call (x,i) an equal slot if h(x)=h(xi); there are ∣Eh∣ of them. Put Ah=∑(x,y)∈EhMxy2, and, for ρ(x,y)≥2, ν(x,y)=#{i:xi=yi,h(xi)=h(x)}. Writing 41=Mxxi2+(41−Mxxi2) on each equal slot and using (2), then ai≥0 and (3),
the sum running over unordered pairs. A pair with h(x)=h(y) contributes at most 0. Let h(x)=h(y) and ρ(x,y)=2, with x,y differing in i,j. The edges counted by c(x,y) are {x,xi}, {x,xj}, {y,yi}={y,xj} and {y,yj}={y,xi}, the four edges of the square spanned by x and y. Each of the edge-disjoint paths x,xi,y and x,xj,y contains an edge on which h changes, so c(x,y)≥2 and the contribution is at most 0. A pair with h(x)=h(y) and ρ≥3 contributes at most 2Mxy2. This proves the second assertion.
Step 4. By (3), 2∑ρ≥3Mxy2≤∑ρ≥2(ρ−1)Mxy2≤A0≤41∥T∥HS2. Therefore ∣Eh∣≤∥T∥HS2+2A0≤23∥T∥HS2.
Remark 4. The edge comparison of [1 §4] states ∣Eh∣≤2∥MH+HM∥HS2. Identity (3) refines its inequality F≤A0, and (2) identifies each edge deficit exactly.
Proof of Theorem 1
The reduction is OpenAI’s [1 §5]. After a harmless perturbation p has no zero on Ω; put w=∣p∣, h=χ[n]f. Then AS(f)=∣Eh∣/N, and the random grades (R,S) with Pr{R=r,S=s}=N−1∥ΠsHΠr∥HS2 have both marginals Bin(n,1/2), satisfy R+S≥n−d, and N−1∥T∥HS2=E(R+S−n)2. With U=S, V=n−R (same law, values in [0,n], V−U≤d), Lemma 3 gives
AS(f)≤23E(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 L, with V−U≤a and b=E∣U−EU∣, satisfy E(U−V)2≤4abL+2aL+a. With L=n, a=d, b=bn this gives AS(f)≤6dbn(n+d)/(n+2d); also AS(f)≤n trivially. The estimate bn(n+d)/(n+2d)≤n/(2π) for all n,d≥1 is proved in [5 §6] from the Wallis inequalities; it gives the bound 2π6dn.
For the rational witness: arctan21+arctan31=4π and arctanx>x−3x3+5x5−7x7 for 0<x≤1 give π>4898881538665[5 (20)]. Hence
the last inequality being 8817984⋅250000=2204496000000<2204613059985=1432809⋅1538665.
Verification
The ancillary script VERIF_AS_EDGE.py (Python and numpy only) checks, for random weights and random sign functions with 3≤n≤7, 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≤2000, 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]OpenAI, Average sensitivity of polynomial threshold functions, OpenAI Math Release preprint, September 25, 2026, https://github.com/openai/math.
[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]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]Anchen, Average sensitivity: a Lean proof with coefficient 3.762, https://github.com/Anchen-AI4Math/average-sensitivity-lean, October 2026.
[5]Q. Chen, A uniform average-sensitivity bound, October 17, 2026, https://github.com/canghaimeng/openai-math-improvement (problems/bound-127).