Kung–Traub conjecture proved, Lean check with ChatGPT 6
Awaiting review
Importance: major (4 of 5)Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 2 November 2026
Your AI and this story
- GPT-6 Astra143 days after its cutoff
- Claude Opus 5.582 days after its cutoff
- Gemini 4 Argon173 days after its cutoff
- Grok 4.7112 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 82 days before it.
Key facts
- Claim: a deterministic stationary root-finding method without memory, using at most n real scalar function or derivative evaluations per iteration, cannot have local order greater than 2^(n−1) on every real analytic function with a simple zero; for n ≥ 2 the bound is attained by Kung–Traub methods (abstract)
- Conjecture source: Kung and Traub, ‘Optimal order of one-point and multipoint iteration’ (J. ACM, 1974), Conjecture 8.1
- Method: a localisation property of polynomial Wronskians gives a lower bound at each fixed scale; a diagonal construction yields one entire function for which every larger order fails; also a complex-evaluation version
- AI declaration (verbatim): ‘The formal Lean verification was carried out with assistance from ChatGPT 6. The resulting Lean proof and its problem formulation were thoroughly checked by the author and with the Lean 4 Comparator … ChatGPT 5.6 and 6 were also used as interactive aids in discussing and checking some of the arguments in the paper.’
- Verification status: preprint plus author-reported Lean verification (Lean 4 Comparator, no new axioms); no independent expert review seen as of 2 Nov 2026
- Timing: arXiv lists submission on 20 Sep 2026 but the paper appeared only in the 2 Nov 2026 announcement (id 2610.40660)
What happened
Matthew Colbrook posted “Adversarial Wronskians: A proof of the Kung–Traub conjecture” on arXiv (2610.40660). The 1974 conjecture bounds how fast any root-finding iteration without memory can converge given a fixed number of function or derivative evaluations per step; Newton’s method (two evaluations, order 2) and the Kung–Traub multipoint methods meet the bound. The paper proves the bound holds for all such methods, with adaptive choice of evaluation points allowed, and states that the results are verified in Lean.
The AI declaration says the Lean verification “was carried out with assistance from ChatGPT 6”, checked by the author with the Lean 4 Comparator, and that ChatGPT 5.6 and 6 “were also used as interactive aids in discussing and checking some of the arguments”. The author thanks Gonzalo Cao-Labora and George Stepaniants for advice on the setup.
Why it matters
The Kung–Traub conjecture is a standard open question in numerical analysis textbooks for half a century. This is a human proof with a machine-checked formalization produced with an LLM, a workflow that has become common in 2026. We found no independent review or public reaction yet (HN search unavailable during this run).
What is disputed or not yet verified
| Verification | Preprint; Lean formalization checked with Lean 4 Comparator (author’s statement) |
|---|
Sources
2 sources from 2 sites. Numbers match the chips in the text.
2 sources: 2 primary
Primary
Changes
- Filed from the 2 Nov sweep (arXiv AI-disclosure list)