---
id: "2026-10-06-openai-matrix-multiplication-omega-9-4"
url: "https://postcutoff.com/e/2026-10-06-openai-matrix-multiplication-omega-9-4/"
as_of: "2026-10-30T13:42:00+01:00"
date: "2026-10-06"
date_precision: day
category: science
importance: 5
confidence: medium
status: [Result confirmed]
verification: Lean-verified
sources: 13
editor: human editor
human_review: null
version: "2026-10-29"
---

As of: 2026-10-30 13:42 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-10-06-openai-matrix-multiplication-omega-9-4/

# OpenAI proves ω ≤ 9/4 for matrix multiplication

Full title: OpenAI's release lowers the matrix multiplication exponent to ω ≤ 9/4, from about 2.371, with a Lean proof; experts have since re-proved the bound over every field and made it constructive

"An Upper Bound of 9/4 for the Matrix Multiplication Exponent" (OpenAI, dated 2 Oct 2026, released 6 Oct, family 107) proves that for every ε > 0, n × n complex matrices can be multiplied using O_ε(n^(9/4+ε)) arithmetic operations, so ω ≤ 2.25. The previous record from the laser-method line was ω < 2.371177. The proof works with Strassen's asymptotic spectrum and inequalities for polynomial-multiplication tensors, gives no explicit algorithm, and is formalized in Lean (statement checked by community comparator runs). Independent expositions and proofs followed: Amanov, van den Berg and Zuiddam (arXiv 2610.30054) re-prove it over every field, and Rafael Pass (arXiv 2610.28627) gives a constructive, elementary proof.

## Key facts
- Theorem 1.1 (verbatim): 'For every ε > 0, two n × n complex matrices can be multiplied using Oε(n^{9/4+ε}) arithmetic operations. In particular, ω ≤ 9/4.' The paper adds that its proof 'does not specify a competitive finite matrix size'. 13 pages, dated 2 Oct 2026
- Companions in the family: 'Complex Matrix Multiplication Below 2.258 and Rectangular Bounds' (83 pp., 24 Sep; ω < 2.258, dual exponent α > 0.465, ω(1, 0.709, 1) < 2.092 in characteristic zero) and 'Staggered extraction for exact matrix multiplication over every field' (35 pp., 24 Sep; ω < 2.371054886006746 over every fixed field, including positive characteristic)
- Method (paper): 'The present proof combines explicit tensor degenerations with the spectral viewpoint.' A separation construction turns blocks that share one tensor leg into independent blocks; two inequalities for polynomial-multiplication tensors force a growth rate a^{4/3}, which gives 3t ≤ 9/4 for every spectral character
- Previous records (as listed by Pass): ω < 2.371339 (Alman et al., 2025) and ω < 2.371177 (Dupont et al., August 2026, found with AlphaEvolve; see [2026-08-17-alphaevolve-matrix-multiplication-exponent](https://postcutoff.com/e/2026-08-17-alphaevolve-matrix-multiplication-exponent/index.md))
- Lean: comparator challenge MatrixMultiplication.lean defines straight-line programs with constant, input, add, subtract and multiply gates, counts the arithmetic gates, and defines ω as the infimum of exponents τ admitting correct programs of cost C·n^(τ+ε) for every n; theorem complex_omega_le_nine_quarters (plus α > 93/200 and the rectangular bound). The oai-math-revised comparator run (25–26 Oct) accepted it
- Amanov, van den Berg and Zuiddam (arXiv 2610.30054, 21 Oct, verbatim): 'We give an exposition of OpenAI’s recent proof that the exponent ωC of matrix multiplication over the complex numbers satisfies ωC ≤ 9/4. Our version of the proof gives ωF ≤ 9/4 over every field F.' They prove an 'operational barrier' showing the current analysis cannot be pushed further with the same ingredients, and note that Sela Navot, Kunal Marwaha and they themselves each released Lean proofs of ω_F ≤ 9/4 for every field on 7 Oct
- Rafael Pass (arXiv 2610.28627, 20 Oct, verbatim): 'We give a self-contained constructive proof that the matrix multiplication exponent satisfies ω ≤ 9/4 … We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion.' His AI statement says Codex (Astra) was used extensively, while 'The main ideas behind the construction, analysis, and abstractions are my own'
- Other follow-ups: Przemysław Uznański (arXiv 2610.10494) extends the analysis to rectangular products, ω(1, 1/2, 1) = 2, and all-pairs shortest paths in directed unweighted graphs in O(n^2.5); Houxi Lü (arXiv 2610.18914) replaces a Fourier step by polynomial interpolation to get ω ≤ 9/4 in every characteristic
- Reactions: Steven Strogatz: 'This leap in progress is like Bob Beamon's long jump'; Abbas Mehrabian (X, 8 Oct): 'a groundbreaking algorithm to multiply matrices, showing ω⩽2.25. Our team had the best bound before OpenAI's result'; Virginia Vassilevska Williams (Scientific American): 'In a maybe diabolical sense, the advance on matrix multiplication can be seen as an attempt by the LLMs to speed themselves up'; Yuval Filmus (X, 17 Oct): the proof is 'outlandish, using Strassen's theory of asymptotic spectra'
- Practicality: Sergey Gusev (X, 20 Oct) says the explicit algorithms built so far are 'galactic'; a first AI-written construction needed matrices with about 10^(2.3×10^11) rows even at exponent 2.67, later reduced to about 10^4,650 rows

## What happened

The exponent ω measures how fast matrices can be multiplied: the schoolbook method costs n³ operations, Strassen showed in 1969 that
fewer suffice, and a long line of tensor-based "laser method" refinements brought the bound to about 2.371 by 2025–2026, each step
gaining a few thousandths. OpenAI's 6 Oct release includes a 13-page manuscript, dated 2 Oct, that proves ω ≤ 9/4 = 2.25 over the
complex numbers. Two companion papers from late September give the intermediate bound 2.258, rectangular bounds, and a small
improvement over every field.

The proof does not exhibit an algorithm. It works in Strassen's spectral framework: it bounds every "character" of the matrix
multiplication tensor by comparing it with polynomial multiplication, using a new way of separating tensor blocks that share one
leg. OpenAI formalized the main bound in Lean, with a statement that defines arithmetic programs and their cost from scratch; the
community comparator run accepted it.

## Why it matters

ω is one of the central constants of algebraic complexity theory, and a jump from 2.371 to 2.25 is far larger than anything achieved
since the 1980s. Practical matrix multiplication is unaffected: the constructions behave like "galactic" algorithms whose advantage
appears only at sizes far beyond any computer.

## Independent checks

Within three weeks the result had been re-derived by others. Alimzhan Amanov, Maxim van den Berg and Jeroen Zuiddam wrote an
exposition in the language of degenerations and asymptotic spectra, extended it to every field and to rectangular shapes, and showed
that this analysis cannot give a better exponent with the same ingredients. Rafael Pass gave an explicit Strassen-style identity that
reaches 9/4 by ordinary recursion. Both papers used AI assistance. Several people also released Lean proofs for arbitrary fields.

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 159 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 98 days after its cutoff
- Gemini 4 Argon (training cutoff March 2026): 189 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 128 days after its cutoff

## Sources

1. [OpenAI: An Upper Bound of 9/4 for the Matrix Multiplication Exponent (2 Oct)](https://github.com/openai/math/blob/main/preprints/Matrix-Multiplication-Nine-Fourths-October-2-2026/paper.pdf) (github.com, paper)
2. [OpenAI: Complex Matrix Multiplication Below 2.258 and Rectangular Bounds](https://github.com/openai/math/blob/main/preprints/Complex-Matrix-Multiplication-Below-2.258-and-Rectangular-Bounds-September-24-2026/Complex-Matrix-Multiplication-Below-2.258-and-Rectangular-Bounds-September-24-2026.pdf) (github.com, paper)
3. [Lean scope note for family 107](https://github.com/openai/math/blob/main/lean/docs/107.md) (github.com, code)
4. [Lean comparator challenge: MatrixMultiplication.lean](https://github.com/openai/math/blob/main/lean/ComparatorChallenges/MatrixMultiplication.lean) (github.com, code)
5. [arXiv 2610.30054: Amanov, van den Berg, Zuiddam, Multiplying matrices via polynomials: exposition and barriers](https://arxiv.org/abs/2610.30054) (arxiv.org, paper)
6. [arXiv 2610.28627: Rafael Pass, A Constructive and Elementary Proof of ω ≤ 9/4](https://arxiv.org/abs/2610.28627) (arxiv.org, paper)
7. [arXiv 2610.10494: Przemysław Uznański, Rectangular matrix multiplication from polynomial products](https://arxiv.org/abs/2610.10494) (arxiv.org, paper)
8. [arXiv 2610.18914: Houxi Lü, matrix multiplication in arbitrary characteristic](https://arxiv.org/abs/2610.18914) (arxiv.org, paper)
9. [oai-math-revised: comparator run on all challenges (LEAN_CHECKS.md)](https://github.com/mathcommunity/oai-math-revised/blob/main/docs/LEAN_CHECKS.md) (github.com, code)
10. [Scientific American: The most exciting claims from OpenAI's heap of new proofs (Vassilevska Williams on 107)](https://www.scientificamerican.com/article/the-most-exciting-claims-from-openais-heap-of-new-proofs/) (scientificamerican.com, press)
11. [Abbas Mehrabian on X (8 Oct)](https://x.com/abbas_mehrabian/status/2108002041742393818) (x.com, discussion)
12. [Yuval Filmus on X (17 Oct)](https://x.com/YFilmus/status/2111319639208910889) (x.com, discussion)
13. [Sergey Gusev on X: explicit 9/4-type algorithms are galactic (20 Oct)](https://x.com/13SergeyGusev/status/2112373928802799741) (x.com, discussion)

## Changes

- 2026-10-29 (filed): Created (families 001–125; manuscript, Lean statement, comparator results and the follow-up arXiv papers read)

## Related

- 2026-10-07: [Outside researchers using AI crowdsource a tighter exponent in OpenAI's integer-multiplication result #109, from 2^-182 to about 2^-8.4 (conditional)](https://postcutoff.com/e/2026-10-07-colkitt-codex-integer-multiplication-exponent/index.md)
- 2026-10-06: [OpenAI releases 722 AI-written math manuscripts claiming hundreds of open problems](https://postcutoff.com/e/2026-10-06-openai-math-release-722-manuscripts/index.md)
- 2026-08-17: [AlphaEvolve helps lower the matrix multiplication exponent ω to below 2.371177](https://postcutoff.com/e/2026-08-17-alphaevolve-matrix-multiplication-exponent/index.md)
- People: [Virginia Vassilevska Williams](https://postcutoff.com/person/virginia-vassilevska-williams/), [Steven Strogatz](https://postcutoff.com/person/steven-strogatz/)
- Archived: 3 posts, listed in https://postcutoff.com/e/2026-10-06-openai-matrix-multiplication-omega-9-4/index.json