VibeMathedMath problems solved with AI
Sign in

Homogeneous depth-five lower bounds for iterated matrix multiplication with unrestricted bottom fan-in (Bera-Chakrabarti question, balanced regime)

Let IMMw,d\mathrm{IMM}_{w,d} be the (1,1)(1,1) entry of a product of dd generic w×ww\times w matrices. Nisan and Wigderson (1995) asked for superpolynomial lower bounds for homogeneous ΣΠΣΠΣ\Sigma\Pi\Sigma\Pi\Sigma circuits, and Kayal and Saha asked for depth-five bounds for IMM. Bera and Chakrabarti (CCC 2015) proved that homogeneous ΣΠΣΠΣ\Sigma\Pi\Sigma\Pi\Sigma circuits computing IMMnq,n\mathrm{IMM}_{n^q,n} in NN variables need NΩ(n)N^{\Omega(\sqrt n)} gates, but only when every bottom linear form has fan-in at most NμN^{\mu} with μ<1/2\mu<1/2. They called it the most immediate and natural open question whether the bound survives bottom fan-in up to N1−Θ(1)N^{1-\Theta(1)} or NN, the general case. Does the n\sqrt n-exponent lower bound for homogeneous depth-five circuits computing IMM hold with unrestricted bottom fan-in?

Result
Proved(see note)
Status
Variant only
AI contribution
AI-discovered
Method
Argument
Field
Algebraic complexity; arithmetic circuit lower bounds
Posed by
Suman K. Bera and Amit Chakrabarti, A Depth-Five Lower Bound for Iterated Matrix Multiplication (CCC 2015), closing open question; background question of Nisan and Wigderson (1995)
Year posed
2015
Years open
11y
Solved
2026-09-25
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
15 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Claims that over every field of characteristic zero every syntactically homogeneous ΣΠΣΠΣ\Sigma\Pi\Sigma\Pi\Sigma circuit computing IMMn,n\mathrm{IMM}_{n,n} has at least nn/400n^{\sqrt n/400} gates for large nn, with gate sharing, arbitrary fan-in and bottom linear forms of arbitrary support allowed, and a block construction gives nn+4n^{\sqrt n+4} over every field, so the gate complexity is nΘ(n)n^{\Theta(\sqrt n)}. The measure is the rank of a partial-derivative-times-multiplication operator. It does NOT treat the Bera-Chakrabarti regime IMMnq,n\mathrm{IMM}_{n^q,n} directly, positive characteristic, non-homogeneous circuits, or depths beyond five.

What the AI did

The release README says all results were produced by an unreleased internal OpenAI model, the vast majority by one fixed procedure using on average about three hours of ChatGPT Pro thinking compute per result. Its named exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region, whose write-up was human edited for readability) do not concern this family. The manuscript is credited to OpenAI with no human author named. The lower and upper bounds have a Lean comparator challenge in the release.

Verification

No independent mathematician has checked this yet. Theorem 1.1 and its corollaries were read against the Bera-Chakrabarti question. The Lean challenge lean/ComparatorChallenges/DepthFive.json (solution module OAI.Algebra.DepthFive.Bounds, present at the pinned commit) is not in the formalization catalogue; it was found through lean/docs/135.md. Its statement OAI.Problem335.main was read here: for circuits with five layers, formal-degree homogeneity at every sum gate and arbitrary bottom linear forms, computing IMM of n matrices of size n x n needs at least nn/400n^{\sqrt n/400} gates (leaves counted) for all large n, over the complex numbers and over every characteristic-zero field with one threshold; and over every field there are such circuits with at most nn+4n^{\sqrt n+4} gates. This is the headline. Not rebuilt here.

Sources

Changelog1 change

Discussion