--- id: "2026-07-14-gpt-5-6-zeroth-order-convex-lower-bound" url: "https://postcutoff.com/e/2026-07-14-gpt-5-6-zeroth-order-convex-lower-bound/" as_of: "2026-11-22T13:32:00+01:00" date: "2026-07-14" date_precision: day category: science importance: 3 confidence: medium status: [Awaiting review] verification: Preprint only sources: 7 editor: human editor human_review: null version: "2026-10-19" --- As of: 2026-11-22 13:32 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-07-14-gpt-5-6-zeroth-order-convex-lower-bound/ # 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) ## 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. ## What is disputed or not yet verified - Verification: Partial Lean: the core deterministic lower bound is formally verified in Lean 4 (public repo); the upper-bound and transfer results are not formalized; unrefereed single-author preprint ## Your AI and this story - GPT-6.2 Astra (training cutoff May 2026): 44 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 14 days after its cutoff - Gemini 4 Hydrogen (training cutoff March 2026): 105 days after its cutoff - Grok 4.7 (training cutoff May 2026): 44 days after its cutoff ## Sources 1. [arXiv 2607.13335: Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization](https://arxiv.org/abs/2607.13335) (arxiv.org, paper) 2. [GitHub: PhillipKerger/zero-order-bounds-lean-verification (Lean 4 companion)](https://github.com/PhillipKerger/zero-order-bounds-lean-verification) (github.com, code) 3. [Phillip Kerger (Medium): An AI-assisted breakthrough in convex optimization](https://medium.com/@kerger.p/an-ai-assisted-breakthrough-in-convex-optimization-an-optimization-problem-dating-back-30-years-a-db5c631119de) (medium.com, official) 4. [arXiv 2607.16558: Near-optimal lower bounds for randomized algorithms (follow-up)](https://arxiv.org/abs/2607.16558) (arxiv.org, paper) 5. [temperature2: GPT-5.6 closes a second 30-year math gap without OpenAI](https://temperature2.com/p/2026-07-19-gpt-5-6-second-math-proof-outside-openai/) (temperature2.com, press) 6. [AI Weekly: GPT-5.6 Sol Pro closes 30-year gap in zeroth-order convex optimization, Lean-verified](https://aiweekly.co/node/6956) (aiweekly.co, press) 7. [Hacker News discussion (601 points)](https://news.ycombinator.com/item?id=48957779) (news.ycombinator.com, discussion) ## Changes - 2026-10-19: Status confirmed → pending (only part of the paper is Lean-verified; the preprint is unrefereed) - 2026-10-02 (filed): Created (r/math / HN item) ## Related - 2026-09-30: [Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help](https://postcutoff.com/e/2026-09-30-ai-assisted-conjecture-wave-summer-2026/index.md) - 2026-07-17: [GPT-5.6 Sol Ultra proves the 50-year-old cycle double cover conjecture](https://postcutoff.com/e/2026-07-17-cycle-double-cover-conjecture-proved/index.md) - 2026-07-09: [OpenAI broadly releases GPT-5.6 after government-gated preview](https://postcutoff.com/e/2026-07-09-gpt-5-6-sol-terra-luna/index.md)