The asymptotic Gotsman-Linial conjecture on average sensitivity of polynomial threshold functions

A degree- $d$ polynomial threshold function on $\{-1,1\}^n$ is $f(x)=\mathrm{sgn}(p(x))$ for a real polynomial $p$ of degree at most $d$ . Its average sensitivity (total influence) is $I(f)=\sum_{i=1}^n\Pr[f(X)\ne f(X^{\oplus i})]$ for uniform $X$ . Gotsman and Linial proposed that the maximum of $I(f)$ over degree- $d$ PTFs is attained by a symmetric function of $x_1+\dots+x_n$ , which would give $I(f)=O(d\sqrt n)$ ; Chapman disproved the exact extremal form and separated it from the asymptotic bound. The best bounds were sublinear for fixed $d$ (Harsha-Klivans-Meka, Diakonikolas-Raghavendra-Servedio-Tan) and $\sqrt n(\log n)^{O(d\log d)}2^{O(d^2\log d)}$ (Kane). Is $I(f)=O(d\sqrt n)$ for every degree- $d$ polynomial threshold function, with an absolute constant?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Analysis of Boolean functions; polynomial threshold functions
Posed by: Craig Gotsman and Nathan Linial (exact extremal form); asymptotic form stated by Chapman
Year posed: 1994
Years open: 32y
Solved: 2026-09-25
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 42 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: for $n\ge1$ , $1\le d\le n$ and a real multilinear polynomial $p$ of degree at most $d$ , $f=\mathrm{sgn}(p)$ with $\mathrm{sgn}(0)=1$ has $I(f)\le8d\sqrt n$ ; the constant is absolute and $d$ may grow with $n$ . Symmetric examples show the order $d\sqrt n$ is sharp for $d\le\sqrt n$ . It removes the polylogarithmic loss in Kane's bound. It makes no claim about the exact extremizers of the original Gotsman-Linial proposal (already refuted by Chapman and by Kim-Maldonado-Wellens) and does not address non-uniform distributions.

What the AI did

The release README says the vast majority of results, this one included, were produced with one fixed procedure using an unreleased internal OpenAI model, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human-edited). The manuscript is authored 'OpenAI' and names no human author.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the asymptotic conjecture. The proof was not refereed. lean/formalization.yaml lists OAI.LeanBlast.GotsmanLinial.gotsmanLinialStatement (comparator GotsmanLinial). Its statement was read: for all $1\le d\le n$ and every real multilinear polynomial of total degree at most $d$ , the threshold function with sign(0)=1 has average sensitivity (sum over coordinates of the fraction of cube points where flipping that coordinate changes the value) at most $8d\sqrt n$ . Multilinearity loses nothing on the cube. This states the headline claim. Not rebuilt here.

The asymptotic Gotsman-Linial conjecture on average sensitivity of polynomial threshold functions

What was actually shown

What the AI did

Verification

Sources

Discussion