An edge comparison with constant 3/2 and the coefficient 6/sqrt(2 pi) for the average sensitivity of polynomial threshold functions
Version 1 / Nov 15, 2026 / CC BY 4.0
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).
Provenance statement
Tools used
- Anthropic
- Claude Opus
References
- OpenAI, Average sensitivity of polynomial threshold functions , OpenAI Math Release preprint, September 25, 2026, https://github.com/openai/math.link
- 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.DOI
- 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.
- Anchen, Average sensitivity: a Lean proof with coefficient 3.762 , https://github.com/Anchen-AI4Math/average-sensitivity-lean, October 2026.link
- Q. Chen, A uniform average-sensitivity bound , October 17, 2026, https://github.com/canghaimeng/openai-math-improvement (problems/bound-127).link
Version history
- v1 · 4 pagesSubmitted by David Niedbala GiraudinInitial depositCurrentNov 13, 2026