VibeMathedMath problems solved with AI
Sign in

The matrix multiplication exponent: is omega at most 9/4?

The exponent ω\omega of matrix multiplication over C\mathbb C is the infimum of the τ\tau such that, for every ε>0\varepsilon>0, two n×nn\times n matrices can be multiplied with Oε(nτ+ε)O_\varepsilon(n^{\tau+\varepsilon}) arithmetic operations. Strassen's 1969 algorithm gave ω≤log⁡27<2.81\omega\le\log_2 7<2.81, and the laser method of Strassen, Coppersmith-Winograd and their successors (Stothers, Vassilevska Williams, Le Gall, Alman-Vassilevska Williams, Duan-Wu-Zhou and others) brought the bound down to ω<2.371177\omega<2.371177 (Dupont et al., 2026). The trivial lower bound is ω≥2\omega\ge2, and whether ω=2\omega=2 is a central open question of algebraic complexity. The related dual exponent α\alpha, the largest kk for which n×nkn\times n^k by nk×nn^k\times n products take n2+o(1)n^{2+o(1)} operations, was known to satisfy α≥0.321334\alpha\ge0.321334. How small can the upper bound on ω\omega be made?

Result
Proved(see note)
Status
Partial result
AI contribution
AI-discovered
Method
Argument
Field
Algebraic complexity, bilinear and tensor methods
Posed by
Volker Strassen, Gaussian elimination is not optimal (Numerische Mathematik, 1969), which introduced subcubic matrix multiplication and the exponent question
Year posed
1969
Years open
57y
Solved
2026-10-02
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
55 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for every ε>0\varepsilon>0 two complex n×nn\times n matrices can be multiplied with Oε(n9/4+ε)O_\varepsilon(n^{9/4+\varepsilon}) arithmetic operations, so ω≤9/4\omega\le9/4 over C\mathbb C. The companions prove α>0.465\alpha>0.465 over every field of characteristic zero, ω(1,0.709,1)<2.092\omega(1,0.709,1)<2.092, ω<2.258\omega<2.258 over all fields outside one uncomputed finite set of positive characteristics, and ω<2.371054886006746\omega<2.371054886006746 over every field. Not shown: anything about ω=2\omega=2, bit complexity, or a practical crossover size; the 9/4 proof gives no competitive finite matrix size and its transfer to positive characteristic is not claimed.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this family is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscripts are authored as OpenAI with no human author named. The README also cautions that unformalized results could have issues. The 9/4 bound is the October 2 manuscript; two September 24 companions in the same family give the weaker square bound omega < 2.258 with alpha > 0.465 and a rectangular bound (with Python certificate checks), and omega < 2.371054886006746 over every field including positive characteristic. All three main bounds have Lean formalizations in the release.

Verification

No independent mathematician has checked this yet. Checked here: the abstract, introduction and Theorem 1.1 of 'An Upper Bound of 9/4 for the Matrix Multiplication Exponent', read against the exponent as usually defined (arithmetic operations over C, epsilon slack). The proof (a separation inequality for tensors sharing one leg, polynomial-multiplication inequalities and Strassen's asymptotic spectrum) was not refereed. Lean: formalization.yaml lists OAI.MatrixMultiplication.complex_omega_le_nine_quarters (lean/OAI/LinearAlgebra/MatrixMultiplication/Main.lean, comparator ComparatorChallenges/MatrixMultiplication.lean). Its statement was read: omega(C) <= 9/4, where omega is the infimum of exponents tau such that for every eps > 0 some constant C bounds the cost of correct division-free straight-line programs (add, sub, mul, constants) for n x n products by C n^(tau+eps) at every n. That is the headline claim. The same file states alpha > 93/200 and omega(1, 0.709, 1) < 523/250; OAI.MatrixAllFields...omega_lt_source_constant states omega(F) < 2.371054886006746 for every field F. Permitted axioms are propext, Quot.sound and Classical.choice. Not rebuilt here. The lean/docs page for this family names only the two September 24 companions, while formalization.yaml lists the 9/4 paper as a source.

Sources

Changelog1 change

Discussion