What was already known
The classical bound uses polynomial degree. Hayman’s sparse bound is linear in the number of nonzero terms; the question was whether a square-root bound in that number could hold.
AI involvement
An internal OpenAI model supplied the sparse polynomial construction and proof. Alexeev, Putterman, Sawhney, Sellke and Valiant say they verified and explained it.
The paper attributes this proof to the internal model; it does not document enough prompt detail for autonomy.
Importance
The construction settles a specific sparse-discrepancy question and shows why the proposed sharpening fails.
Limitations
The result rules out the proposed square-root bound; it does not disprove Hayman’s linear sparse bound. No separate machine certificate is documented.
Technical verification
The authors explicitly report verifying each model solution, including this counterexample. The illustrative N=2 numerical values do not constitute a separate machine certificate.
Independent checking
human verification of the model proof; §1 AI comment; §5 Theorem 5.1, Lemma 5.4 and Proposition 5.6
- Checker
- Alexeev, Putterman, Sawhney, Sellke and Valiant
- Scope
- Problem 990 failure of the sqrt(nu log M) bound
- Basis
- Reported by the linked checker
Human understanding
The authors explain how interpolation creates multiplicity N+1 while keeping the coefficient parameter bounded.
Correction and publication history
The construction settles a specific sparse-discrepancy question and shows why the proposed sharpening fails.
Read this published revision