In a 148 minutes session using a prompt modeled after OpenAI's Cycle Double Cover proof, GPT-5.6 Sol Pro produced a proof closing a complexity gap in convex optimization dating to 1996. The result establishes a near-quadratic lower bound for deterministic zeroth-order convex optimization, resolving whether gradients fundamentally help. Previously, only an Ω(d) lower bound existed, inherited from first-order models, while Protasov's 1996 algorithm gave an O(d²) upper bound — leaving a linear gap in dimension d.

The problem concerns minimizing convex, 1-Lipschitz functions on a Euclidean unit ball using only exact function values. Phillip Kerger, a PhD in applied mathematics and teaching professor at UC Berkeley, had worked on this sporadically for a year without success, including attempts with earlier GPT versions. After adapting OpenAI's CDC prompting methodology into a ten-page prompt, GPT-5.6 Sol Pro returned a construction using maxes of affine functions and an adversarial oracle strategy.

Kerger verified the proof in Lean, confirming formal correctness. He notes the techniques aren't fundamentally new — the breakthrough lies in finding the right construction, which AI can now achieve for problems solvable with existing methods. This suggests researchers will shift toward problems requiring genuinely novel approaches rather than low- or medium-hanging fruit.