Berkeley's Phillip Kerger uses GPT-5.6 Sol and a 10-page prompt to close a 30-year gap in derivative-free convex optimization
In July 2026 UC Berkeley IEOR teaching professor Phillip Kerger posted a proof that deterministic optimization of a convex Lipschitz function over a d-dimensional ball with only exact function values needs Ω(d²/log(d+1)) queries. This nearly matches Protasov's 1996 ~d² algorithm and closes a gap that had stood since 1996 (the previous lower bound was ~d). Kerger says GPT-5.6 Sol produced the proof in one ~2.5-hour session from a 10-page prompt modelled on OpenAI's cycle-double-cover method. He verified the core lower bound in Lean. It was the first widely noticed outside replication of that "long prompt" method.
Key facts
- Paper: arXiv 2607.13335, 'Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values' (Phillip Kerger, submitted July 14, 2026, 36 pages); it also gives Õ(d²·2ⁿ) results for mixed-integer problems
- Result: Ω(d²/log(d+1)) deterministic exact-value query lower bound vs O(d² log² d) upper bound from Protasov's 1996 method; the previously applicable lower bound was Ω(d)
- AI role (Kerger's Medium post, as reported by temperature2 and AI Weekly): a ~10-page prompt with background, techniques and direction; the model produced a complete proof in ~2.5 hours without intervention. Kerger had worked on the gap for about a year. AI Weekly names the model 'GPT-5.6 Sol Pro'
- Lean 4/mathlib companion repo (PhillipKerger/zero-order-bounds-lean-verification, created July 14) fully verifies the paper's deterministic d^(-1/2)-accuracy lower bound, including Brunn–Minkowski and Urysohn machinery; the upper-bound and transfer results are outside the formalization
- The arXiv abstract itself does not mention AI. The AI-assistance claim rests on the author's own blog post
- Attention: r/math post 'After OpenAI's CDC proof announcement, GPT-5.6 used a prompt to close a 30-year gap in convex optimization' reached the Hacker News front page (601 points, July 18)
- Follow-up: Zhang, Zhang, Qi and Lin (arXiv 2607.16558, July 18) proved near-optimal lower bounds for randomized algorithms in the same exact-value setting (no AI mentioned)
Science result
- Field
- mathematics / optimization / oracle complexity
- Problem
- Query complexity of derivative-free (zeroth-order, exact-value) convex Lipschitz optimization: gap between Protasov's ~d² upper bound and the ~d lower bound (open since 1996)
- Result
- Deterministic lower bound Ω(d²/log(d+1)), matching Protasov's 1996 upper bound up to polylogarithmic factors.
- AI system
- GPT-5.6 Sol
- Human role
- AI-assisted: the researcher wrote a 10-page guiding prompt after a year on the problem; the model produced the proof; the human wrote the paper and checked it in Lean
- Verification
- Core deterministic lower bound formally verified in Lean 4 (public repo); paper is a preprint, not yet peer-reviewed
- Status
- confirmed
- Why surprising
- A single researcher replicated OpenAI's lab-scale proof recipe on a problem of his own choosing within days.
What happened
A few days after OpenAI's cycle double cover proof, Kerger applied the same kind of long, structured prompt to a problem he had worked on for a year. The question is how many function evaluations a deterministic method needs to minimize a convex function when it sees only exact values and no gradients. Protasov's 1996 method needs about d² evaluations, but the best lower bound was only about d. The model's argument establishes a near-quadratic lower bound. Kerger then had the core result machine-checked in Lean and published the paper, the Lean code and (reportedly) the prompt and chat logs.
Why it matters
Most of the summer's AI-math headlines came from the labs themselves. This was an outside, single-author result with a formal proof, on a well-defined classical gap, and it suggested the recipe transfers to other areas of mathematics. Caveat: the Medium post with the step-by-step AI account could not be read directly here, because of a Cloudflare block. Details of the AI's role come from secondary summaries of it.
Changelog
- 2026-10-02: created (from leads queue; r/math / HN item)
Related events
- GPT-5.6 Sol Ultra proves the 50-year-old cycle double cover conjecture ★★★★★
- OpenAI broadly releases GPT-5.6 (Sol, Terra, Luna) after government-gated preview ★★★★
- Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
Sources (7)
- paperarXiv 2607.13335: Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization
- codeGitHub: PhillipKerger/zero-order-bounds-lean-verification (Lean 4 companion)
- officialPhillip Kerger (Medium): An AI-assisted breakthrough in convex optimization
- presstemperature2: GPT-5.6 closes a second 30-year math gap without OpenAI
- pressAI Weekly: GPT-5.6 Sol Pro closes 30-year gap in zeroth-order convex optimization, Lean-verified
- discussionHacker News discussion (601 points)
- paperarXiv 2607.16558: Near-optimal lower bounds for randomized algorithms (follow-up)
id: 2026-07-14-gpt-5-6-zeroth-order-convex-lower-bound · updated 2026-10-02 · open in the interactive timeline