Explicit depth-three circuit lower bounds beyond the square-root exponent

For a Boolean function $f$ on $\{0,1\}^n$ , let $S_3(f)$ be the least number of gates in an unbounded fan-in OR-AND-OR (depth-three) circuit computing $f$ . Hastad's switching lemma gives $S_3(\text{parity})=2^{\Theta(\sqrt n)}$ , and Paturi-Pudlak-Zane's bound $\Omega(n^{1/4}2^{\sqrt n})$ is tight for parity; all lower bounds for explicit functions remained of the form $2^{c\sqrt n}$ for a constant $c$ . Hastad, Jukna and Pudlak asked for an explicit function needing $2^{n^{1/2+\varepsilon}}$ gates, and Gurumukhani-Paturi-Pudlak-Saks-Talebanfard discuss as open the weaker goal of a superconstant multiple of $\sqrt n$ in the exponent. Is there an explicit function, for instance a language in polynomial time, with $S_3(f_n)\ge 2^{\omega(\sqrt n)}$ ?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Circuit complexity; depth-three Boolean circuits
Posed by: Discussed as open by Gurumukhani, Paturi, Pudlak, Saks and Talebanfard (CCC 2024); Hastad, Jukna and Pudlak (1995) posed the stronger 2^(n^(1/2+eps)) problem
Year posed: 2024
Years open: 2y
Solved: 2026-09-23
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 48 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: there is a language $L$ decidable by a deterministic Turing machine in time $C(n+1)^a$ whose $n$ -bit membership functions satisfy $\log_2 S_3(f_n)/\sqrt n\to\infty$ , counting all gates of OR-AND-OR circuits with no fan-in restriction. The language and machine are fixed before the constant $A$ . It does not give a fixed exponent $n^{1/2+\varepsilon}$ (Hastad-Jukna-Pudlak's problem stays open), says nothing about AND-OR-AND circuits beyond what duality gives for the complement, and nothing about depth above three or Valiant's $2^{\omega(n/\log\log n)}$ threshold.

What the AI did

The release README says the vast majority of results, this one included, were produced with one fixed procedure using an unreleased internal OpenAI model, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region, whose write-up was human-edited). The manuscript is authored 'OpenAI' and names no human author.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the question as the manuscript and its cited sources pose it. The proof was not refereed. lean/formalization.yaml lists a main result for this manuscript (comparator DepthThree, declaration OAI.DepthThreeLowerBound.exists_polynomial_time_language_depth_three_lower_bound). The statement ComparatorChallenges/DepthThree.lean was read: there are a language $L$ , a finite multitape Turing machine deciding it within $C(n+1)^a$ steps on every input, and for every real $A>0$ an $N$ such that every OR-AND-OR circuit (literal and constant inputs, arbitrary fan-in and sharing, all gates counted) computing $L$ on $n\ge N$ bits has more than $2^{A\sqrt n}$ gates. This states the headline claim. Permitted axioms: propext, Quot.sound, Classical.choice. Not rebuilt here.

Explicit depth-three circuit lower bounds beyond the square-root exponent

What was actually shown

What the AI did

Verification

Sources

Discussion