Average sensitivity of polynomial threshold functions

What OpenAI claims

Proves that a degree-at-most-d polynomial threshold function on the uniform n-dimensional Boolean cube has average sensitivity at most 8d√n, uniformly for 1 ≤ d ≤ n. Average sensitivity counts expected output changes under single-bit flips. This establishes the asymptotic Gotsman–Linial conjecture, allowing polynomial zeros with sign (0)=1. (Lean)

Paper

1. Average sensitivity of polynomial threshold functions

   25 September 2026 · Preprint, not peer reviewed · PDF

   For every n ≥ 1 and 1 ≤ d ≤ n, we prove that a polynomial threshold function of degree at most d on the uniform Boolean cube has average sensitivity at most 8d√n. This proves the asymptotic form of the Gotsman–Linial conjecture. The bound is uniform in both parameters and uses the convention sgn (0)=1.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.