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

Primarily AI-generated textHuman understanding: no partscs.CC — Computational Complexitymath.CO — Combinatorics

Contributed by David Niedbala Giraudin ↗

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

The research and the writing were carried out by the author with Claude (Anthropic). The identities and the main inequality were checked numerically by the ancillary script, and the cited estimates were checked against their sources. No professional mathematician has reviewed the note yet.

Tools used

Anthropic
Claude Opus

References

  1. OpenAI, Average sensitivity of polynomial threshold functions , OpenAI Math Release preprint, September 25, 2026, https://github.com/openai/math.link
  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.DOI
  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.
  4. Anchen, Average sensitivity: a Lean proof with coefficient 3.762 , https://github.com/Anchen-AI4Math/average-sensitivity-lean, October 2026.link
  5. Q. Chen, A uniform average-sensitivity bound , October 17, 2026, https://github.com/canghaimeng/openai-math-improvement (problems/bound-127).link

Version history

  1. v1 · 4 pagesSubmitted by David Niedbala GiraudinInitial depositCurrentNov 13, 2026