Digesting ω ≤ 9/4

On October 6th, 2026, OpenAI released a repository containing 722 manuscripts that made progress on 373 open problems in mathematics, providing Lean proofs for many of them. The event, affectionately called the “slop drop” or “mathpocalypse”, has naturally caused quite the uproar in the mathematics community, but this post is not meant to delve into this controversy. This is just my attempt at digesting one of the results. I give some of my personal thoughts in the afterword.

In the repository, one proof shows that the matrix multiplication exponent over the complex numbers ωC\omega_\mathbb{C} is at most 9/49/4 [1], and several preprints and Lean proofs that were posted soon after generalize the result to all fields [2][3][4][5]. This is a drastic improvement over the previous bound ω≤2.371177\omega \leq 2.371177 due to Dupont et al. [6]. This marks the largest single improvement to the upper bound of ω\omega since Schönhage in 1981 [7]. The methodology of this paper is also substantially different from that of the last 40 years of literature on the problem. In 1987, Strassen introduced the laser method for bounding ω\omega [8], and until now, all of the improvements since then have been refinements of this method. The OpenAI proof instead leverages another idea Strassen introduced in 1988 called the asymptotic spectrum of tensors [9]. Remarkably, this proof gives a completely non-constructive bound on ω\omega. It proves the existence of an O(n9/4+ε)O\left(n^{9/4 + \varepsilon}\right) matrix multiplication algorithm without describing one.1

None of the writing in this post was generated by LLMs, but they were used extensively to generate visuals, understand the proof, and simplify it to work over arbitrary fields. While prior knowledge of Strassen’s algorithm might be helpful, the technical parts of this post do not assume any familiarity with the theory of matrix multiplication, just basic field theory and tensors.

Matrix Multiplication as a Tensor Problem

Let FF be a field.

Since the field is arbitrary and fixed, we use ω\omega to mean ωF\omega_F. We know ω≥2\omega \geq 2 because any algorithm must read its input, and the naive matrix multiplication algorithm gives ω≤3\omega \leq 3. It is widely believed that ω=2\omega = 2, but mathematicians have struggled to prove it for the better part of a century.

The first improvement on the naive bound was in 1969 due to Strassen [10]. He showed how to multiply two 2×22 \times 2 matrices using only 7 multiplications instead of the naive algorithm’s 8. This generalizes to arbitrary matrices by treating this as a base case and recursively splitting the matrices into quadrants and multiplying them, only requiring 7 recursive calls. This algorithm proves ω≤log⁡27≈2.807\omega \leq \log_2{7} \approx 2.807. More generally, if we can show that multiplying two n×nn \times n matrices requires no more than pp multiplications, then ω≤log⁡np\omega \leq \log_{n}{p} by a similar recursive algorithm. The following setup formalizes this idea of counting the number of multiplications.

Given two n×nn \times n matrices A,B∈Fn×nA, B \in F^{n \times n}, their product C=ABC = AB satisfies

Cik=∑jAijBjk.C_{ik} = \sum_{j} A_{ij}B_{jk}.

Let cij∈Fn×nc_{ij} \in F^{n \times n} be the matrix with a 1 in entry jiji and 0 everywhere else (the indices switching is convenient for symmetry but otherwise unimportant). We are then trying to compute

C=∑i,j,kAijBjkcki.C = \sum_{i, j, k} A_{ij}B_{jk}c_{ki}.

For example, when n=2n = 2,

C=A11B11(1000)+A11B12(0100)+A12B21(1000)+A12B22(0100)+A21B11(0010)+A21B12(0001)+A22B21(0010)+A22B22(0001)=(A11B11+A12B21A11B12+A12B22A21B11+A22B21A21B12+A22B22).\begin{align*} C &= A_{11}B_{11}\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} + A_{11}B_{12}\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} + A_{12}B_{21}\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} + A_{12}B_{22}\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \\ &\quad + A_{21}B_{11}\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} + A_{21}B_{12}\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} + A_{22}B_{21}\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} + A_{22}B_{22}\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \\ &= \begin{pmatrix} A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\ A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22} \end{pmatrix}. \end{align*}

Each of the 8 terms in this summation corresponds to one multiplication performed in the naive algorithm. However, Strassen’s algorithm gives a way to rewrite CC with only 7 terms:

C=(A11+A22)(B11+B22)(1001)+(A21+A22)B11(001−1)+A11(B12−B22)(0101)+A22(B21−B11)(1010)+(A11+A12)B22(−1100)+(A21−A11)(B11+B12)(0001)+(A12−A22)(B21+B22)(1000).\begin{align*} C &= (A_{11} + A_{22})(B_{11} + B_{22})\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \\ &\quad + (A_{21} + A_{22})B_{11}\begin{pmatrix} 0 & 0 \\ 1 & -1 \end{pmatrix} \\ &\quad + A_{11}(B_{12} - B_{22})\begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix} \\ &\quad + A_{22}(B_{21} - B_{11})\begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} \\ &\quad + (A_{11} + A_{12})B_{22}\begin{pmatrix} -1 & 1 \\ 0 & 0 \end{pmatrix} \\ &\quad + (A_{21} - A_{11})(B_{11} + B_{12})\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \\ &\quad + (A_{12} - A_{22})(B_{21} + B_{22})\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}. \end{align*}

To be precise, each term represents one multiplication because it is the product of linear forms on the entries of AA, the entries of BB, and the matrices cijc_{ij}. Let aij,bij∈(Fn×n)∗a_{ij}, b_{ij} \in \left(F^{n \times n}\right)^* both be the map A↦AijA \mapsto A_{ij}. We can write matrix multiplication as the bilinear map φn ⁣:Fn×n×Fn×n→Fn×n\varphi_n\colon F^{n \times n} \times F^{n \times n} \to F^{n \times n} where

AB=φn(A,B)=∑i,j,kaij(A)bjk(B)cki.AB = \varphi_n(A, B) = \sum_{i, j, k} a_{ij}(A) b_{jk}(B) c_{ki}.

So the minimum number of multiplications pp required to multiply two n×nn \times n matrices is also the minimum value of pp such that

φn(A,B)=∑i=1pui(A)vi(B)wi\varphi_n(A, B) = \sum_{i=1}^p u_i(A) v_i(B) w_i

where ui,vi∈(Fn×n)∗u_i, v_i \in \left(F^{n \times n}\right)^* and wi∈Fn×nw_i \in F^{n \times n}. For vector spaces U,V,WU, V, W, we can associate a bilinear map f ⁣:U×V→Wf\colon U \times V \to W with an order 3 tensor t∈U∗⊗V∗⊗Wt \in U^* \otimes V^* \otimes W via the canonical isomorphism that sends the simple tensor u⊗v⊗wu \otimes v \otimes w to the map (A,B)↦u(A)v(B)w(A, B) \mapsto u(A)v(B)w. Under this isomorphism, φn\varphi_n is associated with

⟨n,n,n⟩=∑i,j,kaij⊗bjk⊗cki.\langle n, n, n \rangle = \sum_{i, j, k} a_{ij} \otimes b_{jk} \otimes c_{ki}.

We call ⟨n,n,n⟩\langle n, n, n \rangle the n×nn \times n matrix multiplication tensor. More generally, ⟨m,n,p⟩\langle m, n, p \rangle is the tensor representing the multiplication of an m×nm \times n matrix by an n×pn \times p matrix. We call the three blocks of variables the legs of the tensor.

For example, we know R(⟨2,2,2⟩)≤7R(\langle 2, 2, 2 \rangle) \leq 7 by Strassen’s algorithm:

⟨2,2,2⟩= (a11+a22)⊗(b11+b22)⊗(c11+c22)+(a21+a22)⊗b11⊗(c12−c22)+a11⊗(b12−b22)⊗(c21+c22)+a22⊗(b21−b11)⊗(c11+c12)+(a11+a12)⊗b22⊗(c21−c11)+(a21−a11)⊗(b11+b12)⊗c22+(a12−a22)⊗(b21+b22)⊗c11.\begin{align*} \langle 2, 2, 2 \rangle = &\ (a_{11} + a_{22}) \otimes (b_{11} + b_{22}) \otimes (c_{11} + c_{22}) \\ &+ (a_{21} + a_{22}) \otimes b_{11} \otimes (c_{12} - c_{22}) \\ &+ a_{11} \otimes (b_{12} - b_{22}) \otimes (c_{21} + c_{22}) \\ &+ a_{22} \otimes (b_{21} - b_{11}) \otimes (c_{11} + c_{12}) \\ &+ (a_{11} + a_{12}) \otimes b_{22} \otimes (c_{21} - c_{11}) \\ &+ (a_{21} - a_{11}) \otimes (b_{11} + b_{12}) \otimes c_{22} \\ &+ (a_{12} - a_{22}) \otimes (b_{21} + b_{22}) \otimes c_{11}. \end{align*}

In fact, Winograd proved that R(⟨2,2,2⟩)=7R(\langle 2, 2, 2 \rangle) = 7 [11]. Now we can state more concisely that the minimum number of multiplications required to multiply two n×nn \times n matrices is R(⟨n,n,n⟩)R(\langle n, n, n \rangle).

This follows by using the rank decomposition of ⟨n,n,n⟩\langle n, n, n \rangle as the base case for a recursive algorithm à la Strassen. It actually holds that ω=ν\omega = \nu, but the other direction has a more involved proof and is not necessary for our purposes.

There are two primary operations of interest when working with tensors: the direct sum and the tensor product. If we picture a tensor in U⊗V⊗WU \otimes V \otimes W as a cuboid of elements of FF where each axis corresponds to a basis of UU, VV, or WW, then these operations have nice visualizations.

Two 3×3×3 tensors: t₁, drawn as colored cubes, and t₂, drawn as cubes labeled with symbols. Their direct sum t₁ ⊕ t₂ places them diagonally in a 6×6×6 cuboid; their tensor product t₁ ⊗ t₂ contains one copy of t₂ for each entry of t₁, colored like that entry.

The following figure shows the recursive splitting of 4×44 \times 4 matrices into quadrants to get ⟨2,2,2⟩⊗⟨2,2,2⟩=⟨4,4,4⟩\langle 2, 2, 2 \rangle \otimes \langle 2, 2, 2 \rangle = \langle 4, 4, 4 \rangle. Each colored cube represents a coefficient of 1.

The matrix multiplication tensor ⟨2, 2, 2⟩ and its tensor square ⟨2, 2, 2⟩ ⊗ ⟨2, 2, 2⟩, drawn as cuboids with one cube per nonzero entry. Each nonzero entry of ⟨2, 2, 2⟩ becomes a block of ⟨2, 2, 2⟩ ⊗ ⟨2, 2, 2⟩ holding a copy of ⟨2, 2, 2⟩.

Let t1∈U⊗V⊗Wt_1 \in U \otimes V \otimes W and t2∈U′⊗V′⊗W′t_2 \in U' \otimes V' \otimes W' be tensors.

We omit the proof because it is boring. Inconveniently, tensor rank is neither additive under direct sums nor multiplicative under tensor products. Strassen conjectured in 1973 that tensor rank was additive and it was not until 2019 that Shitov provided a counterexample [12]. The next section defines tools to get around this inconvenience.

The Asymptotic Spectrum of Tensors

First, we define a way to compare two tensors.

The simplest example of a restriction is t≥⟨0⟩t \geq \langle 0 \rangle for all tensors tt. Here, ⟨0⟩\langle 0 \rangle is the zero tensor. Another example is that every nonzero tensor restricts to every simple tensor.

For an integer m>0m > 0, let ⟨m⟩∈Fm⊗Fm⊗Fm\langle m \rangle \in F^m \otimes F^m \otimes F^m be the unit tensor. If ei∈Fme_i \in F^m is the vector with a 1 in its ii-th entry and 0 everywhere else, then

⟨m⟩=∑i=1mei⊗ei⊗ei.\langle m \rangle = \sum_{i=1}^m e_i \otimes e_i \otimes e_i.

We can also define the rank of a tensor in terms of restrictions.

This is true because picking mm simple tensors ui⊗vi⊗wiu_i \otimes v_i \otimes w_i that sum to tt is equivalent to picking three linear maps rU,rV,rWr_U, r_V, r_W under the correspondence

rU(ei)=ui,rV(ei)=vi,rW(ei)=wi.r_U(e_i) = u_i, \quad r_V(e_i) = v_i, \quad r_W(e_i) = w_i.

The following proposition is another useful fact about restrictions.

This holds because we get a rank decomposition of t2t_2 by applying rU⊗rV⊗rWr_U \otimes r_V \otimes r_W to each term in a rank decomposition of t1t_1.

Write t1∼t2t_1 \sim t_2 if t1t_1 and t2t_2 are restrictions of each other (i.e., t1≥t2t_1 \geq t_2 and t2≥t1t_2 \geq t_1). Note that ∼\sim is an equivalence relation. Let SS be the commutative semiring (a ring that does not require additive inverses) of all three-legged tensors modulo ∼\sim under direct sum and tensor product. In this post, we use == on tensors to mean equality in SS. We are now ready to define the object central to the main proof of the paper.

Instead of calling them tensor characters, Strassen used the name spectral points when he introduced them [9]. Like the tensor rank, a tensor character is a measure of the complexity of a tensor but with the benefit of being additive and multiplicative. The core idea of OpenAI’s proof is to make general statements about the entire asymptotic spectrum, not a particular character, and combine these statements with existing results connecting the asymptotic spectrum to the tensor rank. We begin to explore this relation with the following proposition.

The proof is short. Let m=R(t)m = R(t). By Proposition 6, ⟨m⟩≥t\langle m \rangle \geq t. Since ξ\xi is monotone with respect to restriction,

ξ(⟨m⟩)≥ξ(t).(1)\htmlId{lambda1}{ \xi(\langle m \rangle) \geq \xi(t). }\tag{1}

But if we write ⟨m⟩=⟨1⟩⊕⋯⊕⟨1⟩\langle m \rangle = \langle 1 \rangle \oplus \cdots \oplus \langle 1 \rangle, the additivity and unitality of ξ\xi imply

ξ(⟨m⟩)=m=R(t).(2)\htmlId{lambda2}{ \xi(\langle m \rangle) = m = R(t). }\tag{2}

Combining (1) and (2) gives the desired result.

As we learn more about tensor characters, it helps to have a concrete example in mind. The simplest example is called the flattening rank. To compute it, take a tensor in Fm⊗Fn⊗FpF^m \otimes F^n \otimes F^p, flatten it into a matrix Fm×npF^{m \times np}, and take its rank. This can be done along any of the three legs.

The matrix multiplication tensor ⟨2, 2, 2⟩ and its flattening. Each of the four slices of ⟨2, 2, 2⟩ along the b axis is laid side by side, giving a 4×16 matrix with rows indexed by c and columns by pairs of a and b. The matrix is written out in full below the drawing, with R of it equal to 4: each row has two nonzero entries and no two rows share a column.

Next we study the value of tensor characters on matrix multiplication tensors. A useful fact is that

⟨m,n,p⟩⊗⟨m′,n′,p′⟩=⟨mm′,nn′,pp′⟩.\langle m, n, p \rangle \otimes \langle m', n', p' \rangle = \langle mm', nn', pp' \rangle.

In particular, we can write

⟨n,n,n⟩=⟨n,1,1⟩⊗⟨1,n,1⟩⊗⟨1,1,n⟩.\langle n, n, n \rangle = \langle n, 1, 1 \rangle \otimes \langle 1, n, 1 \rangle \otimes \langle 1, 1, n \rangle.

We call these three factors the dot product tensors. The rank of these tensors is exactly nn. The upper bound follows immediately from the naive matrix multiplication algorithm, and the lower bound can be shown using the flattening rank and Proposition 9. It happens that tensor characters are very well-behaved on dot product tensors.

We prove the claim for ℓ1(ξ)\ell_1(\xi) and the other two follow similarly. For concision, write ℓ1=ℓ1(ξ)\ell_1 = \ell_1(\xi). First, we show an incorrect proof and then how to correct it. Set

ℓ1=log⁡2ξ(⟨2,1,1⟩).\ell_1 = \log_2 \xi(\langle 2, 1, 1 \rangle).

Then

nℓ1log⁡n2=2ℓ1=ξ(⟨2,1,1⟩)=ξ(⟨nlog⁡n2,1,1⟩).(3)\htmlId{wrong1}{ n^{\ell_1\log_n{2}} = 2^{\ell_1} = \xi(\langle 2, 1, 1 \rangle) = \xi\left(\langle n^{\log_n{2}}, 1, 1 \rangle\right). }\tag{3}

If we erroneously allow arbitrary positive real tensor powers instead of just integers, then

ξ(⟨nlog⁡n2,1,1⟩)=ξ(⟨n,1,1⟩⊗log⁡n2)=ξ(⟨n,1,1⟩)log⁡n2.(4)\htmlId{wrong2}{ \xi\left(\langle n^{\log_n{2}}, 1, 1 \rangle\right) = \xi\left(\langle n, 1, 1 \rangle^{\otimes \log_n{2}}\right) = \xi(\langle n, 1, 1 \rangle)^{\log_n{2}}. }\tag{4}

Taking the (log⁡n2)(\log_n{2})-th root of (3) and (4) would finish the proof. To fix this argument, we rely on a common technique in the study of matrix multiplication: taking the limit of a large tensor power. We then combine this trick with the squeeze theorem. For p≥1p \geq 1, let s=⌊plog⁡2n⌋s = \lfloor p\log_2{n} \rfloor:

2s≤np≤2s+1ξ(⟨2,1,1⟩)s≤ξ(⟨n,1,1⟩)p≤ξ(⟨2,1,1⟩)s+1slog⁡2ξ(⟨2,1,1⟩)≤plog⁡2ξ(⟨n,1,1⟩)≤(s+1)log⁡2ξ(⟨2,1,1⟩)sℓ1p≤log⁡2ξ(⟨n,1,1⟩)≤(s+1)ℓ1plim⁡p→∞sℓ1p≤lim⁡p→∞log⁡2ξ(⟨n,1,1⟩)≤lim⁡p→∞(s+1)ℓ1pℓ1log⁡2n≤log⁡2ξ(⟨n,1,1⟩)≤ℓ1log⁡2n.\def\arraystretch{1.5} \begin{array}{rcccl} 2^s & \leq & n^p & \leq & 2^{s + 1} \\ \xi(\langle 2, 1, 1 \rangle)^{s} & \leq & \xi(\langle n, 1, 1 \rangle)^p & \leq & \xi(\langle 2, 1, 1 \rangle)^{s + 1} \\ s\log_2{\xi(\langle 2, 1, 1 \rangle)} & \leq & p\log_2{\xi(\langle n, 1, 1 \rangle)} & \leq & (s+1)\log_2{\xi(\langle 2, 1, 1 \rangle)} \\ \dfrac{s\ell_1}{p} & \leq & \log_2{\xi(\langle n, 1, 1 \rangle)} & \leq & \dfrac{(s+1)\ell_1}{p} \\ \lim_{p \to \infty}\dfrac{s\ell_1}{p} & \leq & \lim_{p \to \infty}\log_2{\xi(\langle n, 1, 1 \rangle)} & \leq & \lim_{p \to \infty}\dfrac{(s+1)\ell_1}{p} \\ \ell_1\log_2{n} & \leq & \log_2{\xi(\langle n, 1, 1 \rangle)} & \leq & \ell_1\log_2{n}. \end{array}

Finally, we get

ℓ1=log⁡nξ(⟨n,1,1⟩).\ell_1 = \log_n{\xi(\langle n, 1, 1 \rangle)}.

We know ⟨n,n,n⟩≥⟨n⟩\langle n, n, n \rangle \geq \langle n \rangle by setting all the off-diagonal entries to 0, so ξ(⟨n,n,n⟩)≥n\xi(\langle n, n, n \rangle) \geq n. This tells us L(ξ)≥1L(\xi) \geq 1.

Approximate Algorithms

In 1980, Bini proved a key result that unlocked all of the improvements to ω\omega that followed. Informally, it states that if there exists an efficient algorithm that approximates the product of two matrices, then there exists an exact algorithm whose asymptotic runtime is arbitrarily close to that of the approximate algorithm [13]. We now formalize what is meant by an approximate algorithm.

Let ∣∣⋅∣∣|| \cdot || be a norm on U′⊗V′⊗W′U' \otimes V' \otimes W'. We would like to say that t1t_1 approximately restricts to t2t_2 if for all ε>0\varepsilon > 0, there exists a tensor ee with ∣∣e∣∣<ε||e|| < \varepsilon such that t1≥t2+et_1 \geq t_2 + e. Here, ee represents some small error term. However, this sort of analytic definition does not generalize well to arbitrary fields where only the trivial metric might exist. Instead, we opt for a more algebraic definition.

So instead of adding a “small” tensor to t2t_2, we use a function of some indeterminate ε\varepsilon. For convenience, this function is a polynomial. And while this is never explicitly performed, we can imagine scaling by ε−h\varepsilon^{-h} and taking the limit as ε→0\varepsilon \to 0 to get t2t_2. In this way, degeneration is the more general form of approximate restriction that we were looking for. Trivially, if t1≥t2t_1 \geq t_2, then t1⊵t2t_1 \trianglerighteq t_2.

If allowing for a leading εh\varepsilon^h seems strange, note that the definition collapses to restriction if we require (dU⊗dV⊗dW)(t1)=t2+εe(d_U \otimes d_V \otimes d_W)(t_1) = t_2 + \varepsilon e. This alternative equation can be satisfied for an equivalent definition if we also adjoin ε−1\varepsilon^{-1} to the codomains of dU,dV,dWd_U, d_V, d_W, but this makes it more tedious to define the degree of degeneration.

In the style of Proposition 6, we define an approximate form of tensor rank in two ways.

Note that R‾(t)≤R(t)\underline{R}(t) \leq R(t) for all tensors tt. Border rank behaves similarly to the regular tensor rank as in Proposition 4 and Proposition 7 with similarly routine proofs.

Now we can state the theorem that connects the border rank to exact algorithms.

This is exactly the statement from Proposition 3 but with the border rank instead of the regular tensor rank. The original theorem is slightly more general, considering rectangular matrix multiplication tensors instead of only square ones, but this is unimportant for our purposes. In fact, we do not need this theorem at all for the main proof. However, it is still valuable to show its proof because we will employ similar techniques later on.

We start with a lemma that tells us how to get from a degeneration to a restriction. Let t⊕kt^{\oplus k} and t⊗kt^{\otimes k} denote repeated direct sums and tensor products respectively.

Write

dU=∑i=0hdU(i)εi,dV=∑i=0hdV(i)εi,dW=∑i=0hdW(i)εid_U = \sum_{i=0}^h d_U^{(i)} \varepsilon^i, \quad d_V = \sum_{i=0}^h d_V^{(i)} \varepsilon^i, \quad d_W = \sum_{i=0}^h d_W^{(i)} \varepsilon^i

where

dU(i) ⁣:U→U′,dV(i) ⁣:V→V′,dW(i) ⁣:W→W′.d_U^{(i)}\colon U \to U', \quad d_V^{(i)}\colon V \to V', \quad d_W^{(i)}\colon W \to W'.

Then t2t_2 is the sum of the coefficients of terms with degree hh:

t2=∑i+j+k=h(dU(i)⊗dV(j)⊗dW(k))(t1).t_2 = \sum_{i+j+k=h} \left(d_U^{(i)} \otimes d_V^{(j)} \otimes d_W^{(k)}\right)(t_1).

The number of triples (i,j,k)∈Z≥03(i, j, k) \in \mathbb{Z}_{\geq 0}^3 with i+j+k=hi + j + k = h is exactly Nh=(h+22)N_h = \binom{h + 2}{2}.2

If we imagine each map in the sum being applied to a different copy of t1t_1, we can rewrite the above equation as a function of t1⊕Nht_1^{\oplus N_h}. We index the components of this direct sum using triples (i,j,k)(i, j, k). Let πU(i,j,k) ⁣:U⊕Nh→U\pi_U^{(i, j, k)}\colon U^{\oplus N_h} \to U be the projection onto the (i,j,k)(i, j, k)-th component, and similarly define πV(i,j,k)\pi_V^{(i, j, k)} and πW(i,j,k)\pi_W^{(i, j, k)}. Let

fU(i,j,k)=dU(i)∘πU(i,j,k),fV(i,j,k)=dV(j)∘πV(i,j,k),fW(i,j,k)=dW(k)∘πW(i,j,k).f_U^{(i, j, k)} = d_U^{(i)} \circ \pi_U^{(i, j, k)}, \quad f_V^{(i, j, k)} = d_V^{(j)} \circ \pi_V^{(i, j, k)}, \quad f_W^{(i, j, k)} = d_W^{(k)} \circ \pi_W^{(i, j, k)}.

Then

t2=(∑i+j+k=hfU(i,j,k)⊗fV(i,j,k)⊗fW(i,j,k))(t1⊕Nh).(6)\htmlId{t2}{ t_2 = \left(\sum_{i+j+k=h} f_U^{(i, j, k)} \otimes f_V^{(i, j, k)} \otimes f_W^{(i, j, k)}\right)\left(t_1^{\oplus N_h}\right). }\tag{6}

The last step is to express this as a restriction map, meaning we need the tensor product of three homomorphisms, not the sum of many such tensor products. Luckily, we can take advantage of the fact that t1⊕Nht_1^{\oplus N_h}, when embedded in U⊕Nh⊗V⊕Nh⊗W⊕NhU^{\oplus N_h} \otimes V^{\oplus N_h} \otimes W^{\oplus N_h}, is only nonzero along the diagonal components U(i,j,k)⊗V(i,j,k)⊗W(i,j,k)U_{(i,j,k)} \otimes V_{(i,j,k)} \otimes W_{(i,j,k)}. So

t2=((∑i+j+k=hfU(i,j,k))⊗(∑i+j+k=hfV(i,j,k))⊗(∑i+j+k=hfW(i,j,k)))(t1⊕Nh).(7)\htmlId{t2restrict}{ t_2 = \left(\left(\sum_{i+j+k=h} f_U^{(i, j, k)}\right) \otimes \left(\sum_{i+j+k=h} f_V^{(i, j, k)}\right) \otimes \left(\sum_{i+j+k=h} f_W^{(i, j, k)}\right)\right) \left(t_1^{\oplus N_h}\right). }\tag{7}

It is not the case that the maps in (6) and (7) are the same. In general, sums and tensor products do not commute like this and (7) has many more terms than (6). But all of the new terms are only nonzero outside of the diagonal that t1⊕Nht_1^{\oplus N_h} occupies, so they evaluate to 0. This proves the lemma.

Now we prove Theorem 15. Suppose R‾(⟨n,n,n⟩)=m\underline{R}(\langle n, n, n \rangle) = m. By the definition of border rank, ⟨m⟩⊵⟨n,n,n⟩\langle m \rangle \trianglerighteq \langle n, n, n \rangle. Let hh be the degree of degeneration. We again rely on analyzing a large tensor power, this time of ⟨n,n,n⟩\langle n, n, n \rangle. Observe that ⟨mp⟩⊵⟨n,n,n⟩⊗p\left\langle m^p \right\rangle \trianglerighteq \langle n, n, n \rangle^{\otimes p} with degree phph. By Lemma 16,

⟨mp⟩⊕Nph=⟨mpNph⟩≥⟨n,n,n⟩⊗p.\left\langle m^p \right\rangle ^{\oplus N_{ph}} = \left\langle m^pN_{ph} \right\rangle \geq \langle n, n, n \rangle ^{\otimes p}.

Then by Proposition 6,

mpNph≥R(⟨n,n,n⟩⊗p).m^pN_{ph} \geq R\left(\langle n, n, n \rangle^{\otimes p}\right).

We know ⟨n,n,n⟩⊗p=⟨np,np,np⟩\langle n, n, n \rangle^{\otimes p} = \left\langle n^p, n^p, n^p \right\rangle. Combining this with Proposition 3 gives

ω≤log⁡nR(⟨n,n,n⟩⊗p)1/p≤log⁡n(mpNph)1/p=log⁡nm+ln⁡(Nph)ln⁡(np).(8)\htmlId{asymptoticrank}{ \omega \leq \log_n {R\left(\langle n, n, n \rangle^{\otimes p}\right)}^{1/p} \leq \log_n \left(m^pN_{ph}\right)^{1/p} = \log_n{m} + \frac{\ln(N_{ph})}{\ln(n^p)}. }\tag{8}

Since this holds for all pp, we can take the limit as p→∞p \to \infty. The rightmost term above goes to 0 because NphN_{ph} is a polynomial in pp and grows slower than npn^p, so

ω≤log⁡nm=log⁡nR‾(⟨n,n,n⟩).\omega \leq \log_n{m} = \log_n{\underline{R}(\langle n, n, n \rangle)}.

This holds for all nn, so reapplying the infimum finishes the proof.

We end the section by giving a name to the quantity that allowed us to prove the previous theorem.

Using the submultiplicativity of the tensor rank, we can apply Fekete’s lemma, a classical result from real analysis, to write

R~(t)=lim⁡p→∞R(t⊗p)1/p.\widetilde{R}(t) = \lim_{p \to \infty} R\left(t^{\otimes p}\right)^{1/p}.

To recap, we now have three variations on the idea of tensor rank that relate to each other as follows:

R~(t)≤R‾(t)≤R(t).\widetilde{R}(t) \leq \underline{R}(t) \leq R(t).

And when applied to ⟨n,n,n⟩\langle n, n, n \rangle, they bound ω\omega as in (8):

ω≤log⁡nR~(⟨n,n,n⟩)≤log⁡nR‾(⟨n,n,n⟩)≤log⁡nR(⟨n,n,n⟩).\omega \leq \log_n{\widetilde{R}(\langle n, n, n \rangle)} \leq \log_n{\underline{R}(\langle n, n, n \rangle)} \leq \log_n{R(\langle n, n, n \rangle)}.

The leftmost inequality above is actually an equality, meaning R~(⟨n,n,n⟩)=nω\widetilde{R}(\langle n, n, n \rangle) = n^\omega, but we omit the proof because we do not need it.

Putting it Together

We state an extension of Lemma 16 that combines ideas from the previous two sections, particularly the proof of Theorem 15.

As usual, let hh be the degree of degeneration. For all pp, we have t1⊗p⊵t2⊗pt_1^{\otimes p} \trianglerighteq t_2^{\otimes p} with degree phph. By Lemma 16,

(t1⊗p)⊕Nph≥t2⊗p.\left(t_1^{\otimes p}\right)^{\oplus N_{ph}} \geq t_2^{\otimes p}.

Take some ξ∈Δ(S)\xi \in \Delta(S). We apply the monotonicity with respect to restriction, additivity, and multiplicativity of tensor characters in that order:

ξ((t1⊗p)⊕Nph)≥ξ(t2⊗p)Nphξ(t1⊗p)≥ξ(t2⊗p)Nphξ(t1)p≥ξ(t2)pNph1/pξ(t1)≥ξ(t2).\begin{align*} \xi\left(\left(t_1^{\otimes p}\right)^{\oplus N_{ph}}\right) &\geq \xi\left(t_2^{\otimes p}\right) \\ N_{ph}\xi\left(t_1^{\otimes p}\right) &\geq \xi\left(t_2^{\otimes p}\right) \\ N_{ph}\xi(t_1)^p &\geq \xi(t_2)^p \\ N_{ph}^{1/p}\xi(t_1) &\geq \xi(t_2). \end{align*}

Taking the limit as p→∞p \to \infty gives the desired result because NphN_{ph} is a polynomial in pp, meaning Nph1/pN_{ph}^{1/p} goes to 1.

Using this, we also get an analogue to Proposition 9 for the border rank whose proof is identical except that it substitutes degenerations for restrictions and border rank for the regular tensor rank.

The following is a foundational result in the study of asymptotic spectra due to Strassen [9]. This theorem is essential to the main argument of this post, but the proof is long so we refer the reader to the excellent exposition by Wigderson and Zuiddam, particularly Theorem 3.25 [14].

Polynomial Multiplication Tensors

Instead of directly analyzing matrix multiplication tensors, we study a closely related family of tensors: those representing polynomial multiplication. Let PdP_d be the vector space of polynomials with coefficients in FF of degree at most d−1d-1 with variable uu. Let f∈Paf \in P_a and g∈Pbg \in P_b be written as

f=∑i=0a−1αiui,g=∑j=0b−1βjuj.f = \sum_{i=0}^{a-1} \alpha_iu^i, \quad g = \sum_{j=0}^{b-1} \beta_ju^j.

Then their product is

fg=∑i=0a−1∑j=0b−1αiβjui+j.fg = \sum_{i=0}^{a-1}\sum_{j=0}^{b-1} \alpha_i\beta_ju^{i+j}.

Analogously to matrix multiplication, we can interpret polynomial multiplication between PaP_a and PbP_b as a bilinear map and associate it with a tensor C(a,b)∈Pa∗⊗Pb∗⊗Pa+b−1C(a, b) \in P_a^* \otimes P_b^* \otimes P_{a + b - 1} where

C(a,b)=∑i=0a−1∑j=0b−1xi⊗yj⊗zi+j.C(a, b) = \sum_{i=0}^{a-1}\sum_{j=0}^{b-1} x_i \otimes y_j \otimes z_{i+j}.

Here, xi(f)=αix_i(f) = \alpha_i, yj(g)=βjy_j(g) = \beta_j, and zk=ukz_k = u^k. Observe that C(a,1)=⟨a,1,1⟩C(a, 1) = \langle a, 1, 1 \rangle and C(1,a)=⟨1,1,a⟩C(1, a) = \langle 1, 1, a \rangle. This is the connection that allows us to derive statements about matrix multiplication from polynomial multiplication.

The reason it is helpful to study these tensors is that we know a lot more about them than matrix multiplication tensors.

This equality actually holds for the regular tensor rank when FF has at least a+b−2a + b - 2 elements, but we do not need that.

≥\geq: By Corollary 19, the border rank is bounded from below by any tensor character, so we use the flattening rank on the third leg. This evaluates to a+b−1a + b - 1, and is illustrated below for C(3,4)C(3, 4).

The polynomial multiplication tensor C(3, 4) and its flattening. Its twelve nonzero entries x_i ⊗ y_j ⊗ z_{i+j} form a staircase in a 3×4×6 cuboid. Each of the four slices along the y axis is laid side by side, giving a 6×12 matrix with rows indexed by z and columns by pairs of x and y. The matrix is written out in full below the drawing, with R of it equal to 6: each column has exactly one nonzero entry and every row has at least one.

≤\leq: Take f∈Paf \in P_a and g∈Pbg \in P_b. Lagrange interpolation tells us that the product fgfg is entirely determined by its value at a+b−1a + b - 1 distinct points. However, FF might not have that many elements, so consider the field F(ε)F(\varepsilon). Importantly, this field is infinite even when FF is finite. Interpret ff and gg as elements of the polynomial ring F(ε)[u]F(\varepsilon)[u]. Apply Lagrange interpolation with inputs ε1,…,εa+b−1\varepsilon^1, \ldots, \varepsilon^{a+b-1} to write

fg=∑i=1a+b−1(fg)(εi)Li=∑i=1a+b−1f(εi)g(εi)Li(9)\htmlId{lagrange}{ fg = \sum_{i=1}^{a+b-1} (fg)(\varepsilon^i)L_i = \sum_{i=1}^{a+b-1} f(\varepsilon^i)g(\varepsilon^i)L_i }\tag{9}

where

Li=∏j≠iu−εjεi−εj∈F(ε)[u].L_i = \prod_{j \neq i} \frac{u - \varepsilon^j}{\varepsilon^i - \varepsilon^j} \in F(\varepsilon)[u].

Recall that F(ε)F(\varepsilon) is the field of fractions of F[ε]F[\varepsilon]. Let D∈F[ε]D \in F[\varepsilon] be the product of all the denominators of the LiL_i and let cc be the coefficient of the lowest degree term of DD. So we have c−1DLi∈F[ε][u]c^{-1}DL_i \in F[\varepsilon][u]. The maps x^i ⁣:f↦f(εi)\hat{x}_i\colon f \mapsto f(\varepsilon^i) and y^i ⁣:g↦g(εi)\hat{y}_i\colon g \mapsto g(\varepsilon^i) are linear forms over F[ε]F[\varepsilon]. Thus,

c−1DC(a,b)=∑i=1a+b−1x^i⊗y^i⊗c−1DLi.c^{-1}D C(a, b) = \sum_{i = 1}^{a+b-1} \hat{x}_i \otimes \hat{y}_i \otimes c^{-1}DL_i.

Since the lowest degree term of c−1Dc^{-1}D has coefficient 1, the left-hand side becomes εhC(a,b)+εh+1e\varepsilon^h C(a,b) + \varepsilon^{h+1}e for some e∈(Pa∗⊗Pb∗⊗Pa+b−1)[ε]e \in (P_a^* \otimes P_b^* \otimes P_{a + b -1})[\varepsilon], precisely the definition of the border rank.

One minor inconvenience of the vocabulary we have built up so far is that it is sensitive to the order of the tensor legs. While U⊗V⊗WU \otimes V \otimes W is trivially isomorphic to V⊗W⊗UV \otimes W \otimes U, our notions of restriction, degeneration, and tensor characters do not recognize this. Define an action of the symmetric group S3S_3 on the set of all three-legged tensors where σ∈S3\sigma \in S_3 permutes the legs of the tensor it acts on. For example, if t∈U⊗V⊗Wt \in U \otimes V \otimes W, then (3  2  1)t∈V⊗W⊗U(3\; 2\; 1)t \in V \otimes W \otimes U. It will be convenient to have a function that behaves like a tensor character on polynomial multiplication tensors but is invariant under this action. For some ξ∈Δ(S)\xi \in \Delta(S), define Ξ ⁣:S→R≥0\Xi\colon S \to \mathbb{R}_{\geq 0} such that

Ξ(t)=(∏σ∈S3ξ(σt))1/(2L(ξ))\Xi(t) = \left( \prod_{\sigma \in S_3} \xi(\sigma t) \right)^{1/(2L(\xi))}

where L(ξ)L(\xi) is defined as in Corollary 11. This function is monotone with respect to restriction and degeneration, multiplicative under tensor products, and interestingly superadditive under direct sums (more on that later). For concision, let γ(a,b)=Ξ(C(a,b))\gamma(a, b) = \Xi(C(a, b)). In addition to being symmetric with γ(a,b)=γ(b,a)\gamma(a, b) = \gamma(b, a), this function was selected to have the convenient property that γ(1,b)=b\gamma(1, b) = b, which follows from Proposition 10. By Corollary 19 and Proposition 21, ξ(C(a,b))≤a+b−1\xi(C(a, b)) \leq a + b - 1, so

γ(a,b)≤(a+b−1)3/L(ξ).(10)\htmlId{lambdaup}{ \gamma(a, b) \leq (a + b - 1)^{3/L(\xi)}. }\tag{10}

Main Theorem

We work backwards from the result.

It turns out that this theorem follows quickly from a lower bound on the diagonal of γ\gamma.

This lemma combined with (10) gives

a4/3≤γ(a,a)≤(2a−1)3/L(ξ).a^{4/3} \leq \gamma(a, a) \leq (2a - 1)^{3/L(\xi)}.

If we take the limit as a→∞a \to \infty, we see that 4/3≤3/L(ξ)4/3 \leq 3/L(\xi), or that L(ξ)≤9/4L(\xi) \leq 9/4. By Theorem 20,

nω≤R~(⟨n,n,n⟩)=max⁡ξ∈Δ(S)ξ(⟨n,n,n⟩)=max⁡ξ∈Δ(S)nL(ξ)≤n9/4.n^\omega \leq \widetilde{R}(\langle n, n, n \rangle) = \max_{\xi \in \Delta(S)} \xi(\langle n, n, n \rangle) = \max_{\xi \in \Delta(S)} n^{L(\xi)} \leq n^{9/4}.

So now we need to prove Lemma 23, which we will do using two more lemmas whose proofs we defer to the following sections.

For a visual aid, note that f(x,y)=xyf(x, y) = xy also satisfies both lemmas.

The proof of Lemma 23 does not rely on anything related to tensor characters and only uses the two lemmas above. Intuitively, Lemma 25 gives us a lower bound on the growth of γ\gamma between (a,b)(a, b) and (a,3b+a−1)(a, 3b + a - 1), but Lemma 24 tells us that γ\gamma grows more slowly as its coordinates increase, meaning most of that growth is happening near (a,b)(a, b). We apply this to the case a=ba = b to lower bound the diagonal of γ\gamma. Let

δ(a,b)=γ(a,b+1)−γ(a,b).\delta(a, b) = \gamma(a, b + 1) - \gamma(a, b).

By Lemma 24, δ\delta is nonincreasing in bb. Use this and Lemma 25 to write

2γ(a,a)≤γ(a,4a−1)−γ(a,a)=∑i=a4a−2δ(a,i)≤(3a−1)δ(a,a).2\gamma(a, a) \leq \gamma(a, 4a - 1) - \gamma(a, a) = \sum_{i=a}^{4a-2} \delta(a, i) \leq (3a - 1)\delta(a, a).

Dividing by 3a−13a - 1 gives

δ(a,a)≥2γ(a,a)3a−1.(11)\htmlId{deltadiag}{ \delta(a, a) \geq \frac{2\gamma(a, a)}{3a - 1}. }\tag{11}

Next we bound the diagonal increment of γ\gamma using its symmetry and concavity for all a≥2a \geq 2:

γ(a,a)−γ(a−1,a−1)=δ(a−1,a−1)+δ(a,a−1)≥δ(a−1,a−1)+δ(a,a).(12)\htmlId{lambdadiff}{ \begin{align*} \gamma(a, a) - \gamma(a - 1, a - 1) &= \delta(a - 1, a - 1) + \delta(a, a - 1) \\ &\geq \delta(a - 1, a - 1) + \delta(a, a). \end{align*}}\tag{12}

Combining (11) and (12) yields

γ(a,a)−γ(a−1,a−1)≥2γ(a−1,a−1)3a−4+2γ(a,a)3a−1,\gamma(a, a) - \gamma(a - 1, a - 1) \geq \frac{2\gamma(a - 1, a - 1)}{3a - 4} + \frac{2\gamma(a, a)}{3a - 1},

which rearranges to

γ(a,a)≥(1+23a−4)(1+23a−3)γ(a−1,a−1).\gamma(a, a) \geq \left(1 + \frac{2}{3a - 4}\right)\left(1 + \frac{2}{3a - 3}\right) \gamma(a - 1, a - 1).

Inductively, this expands to

γ(a,a)≥∏i=2a(1+23i−4)(1+23i−3)=∏i=1a−1(1+23i−1)(1+23i)≥∏i=1a−1(1+23i)2.\begin{align*} \gamma(a, a) \geq \prod_{i = 2}^a \left(1 + \frac{2}{3i - 4}\right)\left(1 + \frac{2}{3i - 3}\right) &= \prod_{i = 1}^{a-1} \left(1 + \frac{2}{3i - 1}\right)\left(1 + \frac{2}{3i}\right) \\ &\geq \prod_{i = 1}^{a-1} \left(1 + \frac{2}{3i}\right)^2. \end{align*}

Recall Bernoulli’s inequality, which states that for all x>0x > 0 and 0≤y≤10 \leq y \leq 1,

1+xy≥(1+x)y.1 + xy \geq (1 + x)^y.

This gives

∏i=1a−1(1+23i)2≥∏i=1a−1(1+1i)4/3=∏i=1a−1(i+1i)4/3.\prod_{i = 1}^{a-1} \left(1 + \frac{2}{3i}\right)^2 \geq \prod_{i = 1}^{a-1} \left(1 + \frac{1}{i}\right)^{4/3} = \prod_{i = 1}^{a-1} \left(\frac{i + 1}{i}\right)^{4/3}.

This is a telescoping product that evaluates to a4/3a^{4/3}, proving the lemma.

Shared-Leg Sums

This section is where this post diverges from the original proof. The OpenAI preprint relies on the existence of roots of unity to prove its Proposition 3.1, but their use is superficial and the proof is simpler without them. We demonstrate this in Proposition 27, generalizing the argument to work over all fields. Then their Corollary 3.2 has an unnecessarily convoluted statement of which we give an alternative in Lemma 28 that is easier to describe.3

Dot product tensors are a key ingredient in the main proof, so it is helpful to study tensor products of the form t⊗⟨1,1,n⟩t \otimes \langle 1, 1, n \rangle. Recall

⟨1,1,n⟩=C(1,n)=∑i=1nx⊗yi⊗zi.\langle 1, 1, n \rangle = C(1, n) = \sum_{i=1}^n x \otimes y_i \otimes z_i.

So the first leg of t⊗⟨1,1,n⟩t \otimes \langle 1, 1, n \rangle is the same as the first leg of tt, and the second and third legs are nn disjoint copies of the second and third legs tt. More generally, we can define this operation of taking a direct sum where the first leg is shared.

Using this notation, we can write more concisely

t⊗⟨1,1,n⟩=t⊞n.t \otimes \langle 1, 1, n \rangle = t^{\boxplus n}. Three tensors t₁, t₂ and t₃, each drawn as a single box. Their direct sum t₁ ⊕ t₂ ⊕ t₃ places them diagonally in a 3×3×3 grid. Their shared-leg sum t₁ ⊞ t₂ ⊞ t₃ identifies the three copies of the first leg U, which runs into the page, so the boxes lie on the diagonal of a 3×3 grid that is one box deep.

While this operation arises naturally when working with polynomial multiplication tensors, it does not keep the nice properties that direct sums have. In particular, tensor characters are not additive under shared-leg sums. Trivially, t1⊕t2≥t1⊞t2t_1 \oplus t_2 \geq t_1 \mathop{\boxplus} t_2, so

ξ(t1⊞t2)≤ξ(t1⊕t2)=ξ(t1)+ξ(t2),\xi(t_1 \mathop{\boxplus} t_2) \leq \xi(t_1 \oplus t_2) = \xi(t_1) + \xi(t_2),

giving us only subadditivity. The following proposition is the key degeneration that allows us to also compute lower bounds on the tensor characters of shared-leg sums, transforming shared-leg sums into direct sums.

The degeneration comprises three maps

dU ⁣:(Pa∗⊗U)→(P1∗⊗Ua)[ε],dV ⁣:(Pa∗⊗(V1⊕⋯⊕Va))→(Pa∗⊗(V1⊕⋯⊕Va))[ε],dW ⁣:(P2a−1⊗(W1⊕⋯⊕Wa))→(Pa⊗(W1⊕⋯⊕Wa))[ε].\begin{align*} d_U&\colon (P_a^* \otimes U) \to (P_1^* \otimes U^a)[\varepsilon], \\ d_V&\colon (P_a^* \otimes (V_1 \oplus \cdots \oplus V_a)) \to (P_a^* \otimes (V_1 \oplus \cdots \oplus V_a))[\varepsilon], \\ d_W&\colon (P_{2a-1} \otimes (W_1 \oplus \cdots \oplus W_a)) \to (P_a \otimes (W_1 \oplus \cdots \oplus W_a))[\varepsilon]. \end{align*}

Every term in C(a,a)⊗(t0⊞⋯⊞ta−1)C(a, a) \otimes (t_0 \boxplus \cdots \boxplus t_{a-1}) is of the form

ck,i′,j′,k′(xi⊗ui′)⊗(yj⊗vj′(k))⊗(zi+j⊗wk′(k))c_{k,i',j',k'}(x_i \otimes u_{i'}) \otimes (y_j \otimes v^{(k)}_{j'}) \otimes (z_{i+j} \otimes w^{(k)}_{k'})

where ui′,vj′(k),wk′(k)u_{i'}, v^{(k)}_{j'}, w^{(k)}_{k'} are basis elements of U,Vk,WkU, V_k, W_k respectively. Consider the terms with i=ki=k. If we associate each xk⊗ui′x_k \otimes u_{i'} with a basis element x0⊗ui′(k)∈P1∗⊗Uax_0 \otimes u_{i'}^{(k)} \in P_1^* \otimes U^a, then these terms look like

ck,i′,j′,k′(x0⊗ui′(k))⊗(yj⊗vj′(k))⊗(zk+j⊗wk′(k)).c_{k,i',j',k'}(x_0 \otimes u_{i'}^{(k)}) \otimes (y_j \otimes v^{(k)}_{j'}) \otimes (z_{k+j} \otimes w^{(k)}_{k'}).

Up to reindexing the zz variables, these are exactly the terms of C(1,a)⊗(t0⊕⋯⊕ta−1)C(1, a) \otimes (t_0 \oplus \cdots \oplus t_{a-1}). So we need to define the degeneration to eliminate all terms with i≠ki \neq k. Intuitively, we are giving up the first input of C(a,a)C(a, a) in exchange for separating the first legs of all the tit_i. Define

dU(xi⊗ui′)=εi2(x0⊗ui′(i)),dV(yj⊗vj′(k))=εk2+2jk(yj⊗vj′(k)),dW(zℓ⊗wk′(k))=ε4a2−2kℓ(zℓ−k⊗wk′(k)).\begin{align*} d_U(x_i \otimes u_{i'}) &=\varepsilon^{i^2} (x_0 \otimes u_{i'}^{(i)}), \\ d_V(y_j \otimes v^{(k)}_{j'}) &= \varepsilon^{k^2 + 2jk} (y_j \otimes v^{(k)}_{j'}), \\ d_W(z_{\ell} \otimes w^{(k)}_{k'}) &= \varepsilon^{4a^2-2k\ell} (z_{\ell - k} \otimes w^{(k)}_{k'}). \end{align*}

Since ℓ=i+j\ell = i + j, the power of ε\varepsilon in every term is

i2+k2+2jk+4a2−2kℓ=(i−k)2+4a2.i^2 + k^2 + 2jk + 4a^2 - 2k\ell = (i - k)^2 + 4a^2.

This expression is minimized when i=ki=k, so we keep only the desired terms. Note that the 4a24a^2 term is only there to keep the exponent of ε\varepsilon in dWd_W positive.

Using this degeneration, we can prove a very useful property about Ξ\Xi.

The proof borrows techniques from the laser method introduced by Strassen [8]. Let t=(t0⊞t1)⊗pt = (t_0 \mathop{\boxplus} t_1)^{\otimes p} be a large tensor power, which is an element of U⊗p⊗(V0⊕V1)⊗p⊗(W0⊕W1)⊗pU^{\otimes p} \otimes (V_0 \oplus V_1)^{\otimes p} \otimes (W_0 \oplus W_1)^{\otimes p}. Our goal is to degenerate tt to a direct sum instead of a shared-leg sum in order to take advantage of the additivity of tensor characters. Every basis element in the second leg lives in VB1⊗⋯⊗VBpV_{B_1} \otimes \cdots \otimes V_{B_p} for some binary string B∈{0,1}pB \in \{0, 1\}^p, and similarly every basis element in the third leg lives in some WB1⊗⋯⊗WBpW_{B_1} \otimes \cdots \otimes W_{B_p}. Write these spaces as VBV_B and WBW_B for short. Tensor products distribute over shared-leg sums, so we can also write

t=⊞⁡B∈{0,1}p(tB1⊗⋯⊗tBp)=⊞⁡B∈{0,1}ptB.t = \bigboxplus_{B \in \{0, 1\}^p} \left(t_{B_1} \otimes \cdots \otimes t_{B_p}\right) = \bigboxplus_{B \in \{0,1\}^p} t_B.

For an integer k0≥0k_0 \geq 0, let KK be the set of all binary strings with exactly k0k_0 zeros. We restrict tt by zeroing every basis element in the second and third legs that is not in VBV_B or WBW_B for some B∈KB \in K. What we are left with is

t≥⊞⁡B∈KtB.t \geq \bigboxplus_{B \in K} t_B.

Call the shared-leg sum on the right-hand side above ss. When considered individually, each term of ss is equal to t0⊗k0⊗t1⊗(p−k0)t_0^{\otimes k_0} \otimes t_1^{\otimes (p - k_0)}. It is tempting to say s=⟨1,1,∣K∣⟩⊗t0⊗k0⊗t1⊗(p−k0)s = \langle 1, 1, |K| \rangle \otimes t_0^{\otimes k_0} \otimes t_1^{\otimes (p - k_0)}, but this is incorrect, and this statement still would not be true if the equality were replaced by a restriction in either direction (finding explicit counterexamples is somewhat involved). The first legs of the summands interact with each other, so we need to apply Proposition 27 to obtain a direct sum:

C(∣K∣,∣K∣)⊗s⊵C(1,∣K∣)⊗(⨁B∈KtB)=C(1,∣K∣)⊗(⟨∣K∣⟩⊗t0⊗k0⊗t1⊗(p−k0)).C(|K|, |K|) \otimes s \trianglerighteq C(1, |K|) \otimes \left(\bigoplus_{B \in K} t_B\right) = C(1, |K|) \otimes \left(\langle |K| \rangle \otimes t_0^{\otimes k_0} \otimes t_1^{\otimes(p-k_0)}\right).

Applying Ξ\Xi to both sides of this degeneration gives

γ(∣K∣,∣K∣)⋅Ξ(s)≥γ(1,∣K∣)⋅(Ξ(⟨∣K∣⟩)⋅Ξ(t0)k0⋅Ξ(t1)p−k0).\gamma(|K|, |K|) \cdot \Xi(s) \geq \gamma(1, |K|) \cdot \left(\Xi(\langle |K| \rangle) \cdot \Xi(t_0)^{k_0} \cdot \Xi(t_1)^{p - k_0}\right).

Recall that γ(∣K∣,∣K∣)≤(2∣K∣−1)3/L(ξ)\gamma(|K|, |K|) \leq (2|K| - 1)^{3/L(\xi)} by (10), that γ(1,∣K∣)=∣K∣\gamma(1, |K|) = |K|, and that ξ(⟨∣K∣⟩)=∣K∣\xi(\langle |K| \rangle) = |K|. So

(2∣K∣−1)3/L(ξ)⋅Ξ(s)≥∣K∣1+3/L(ξ)⋅Ξ(t0)k0⋅Ξ(t1)p−k0Ξ(s)≥∣K∣23/L(ξ)⋅Ξ(t0)k0⋅Ξ(t1)p−k0.\begin{align*} (2|K| - 1)^{3/L(\xi)} \cdot \Xi(s) &\geq |K|^{1 + 3/L(\xi)} \cdot \Xi(t_0)^{k_0} \cdot \Xi(t_1)^{p - k_0} \\ \Xi(s) &\geq \frac{|K|}{2^{3/L(\xi)}} \cdot \Xi(t_0)^{k_0} \cdot \Xi(t_1)^{p - k_0}. \end{align*}

Using the facts that t≥st \geq s and ∣K∣=(pk0)|K| = \binom{p}{k_0}, we can write

Ξ(t0⊞t1)≥(123/L(ξ)⋅(pk0)⋅Ξ(t0)k0⋅Ξ(t1)p−k0)1/p.\Xi(t_0 \boxplus t_1) \geq \left(\frac{1}{2^{3/L(\xi)}} \cdot \binom{p}{k_0} \cdot \Xi(t_0)^{k_0} \cdot \Xi(t_1)^{p - k_0}\right)^{1/p}.

The binomial theorem and pigeonhole principle tell us we can pick k0k_0 such that

(pk0)⋅Ξ(t0)k0⋅Ξ(t1)p−k0≥(Ξ(t0)+Ξ(t1))pp+1.\binom{p}{k_0} \cdot \Xi(t_0)^{k_0} \cdot \Xi(t_1)^{p - k_0} \geq \frac{(\Xi(t_0) + \Xi(t_1))^p}{p + 1}.

Put this all together:

Ξ(t0⊞t1)≥Ξ(t0)+Ξ(t1)(23/L(ξ)(p+1))1/p.\Xi(t_0 \boxplus t_1) \geq \frac{\Xi(t_0) + \Xi(t_1)}{\left(2^{3/L(\xi)}(p + 1)\right)^{1/p}}.

As p→∞p \to \infty, the denominator approaches 1, finishing the proof.

Concavity

This section is dedicated to proving Lemma 24. The original preprint rushed through this proof and provided little motivation, so it took me by far the longest to comprehend. I want to highlight that this and the following sections follow the same pattern as the proof of the superadditivity of Ξ\Xi: Come up with a clever degeneration that looks similar to the inequality you are trying to prove, and then apply Ξ\Xi to both sides and use its monotonicity. First, we construct the degeneration in the following proposition.

Recall C(1,2)=⟨1,1,2⟩C(1, 2) = \langle 1, 1, 2 \rangle, so the presence of the shared-leg sum should not be surprising. And the statement of this proposition bears a striking resemblance to the statement of Lemma 24 when rearranged:

2γ(a,b)≥γ(a,b−1)+γ(a,b+1).(13)\htmlId{rearrange}{ 2\gamma(a, b) \geq \gamma(a, b-1) + \gamma(a, b+1). }\tag{13}

Under the canonical isomorphism introduced in the beginning of the post, the tensor C(a,b)⊗C(1,2)C(a, b) \otimes C(1, 2) corresponds to a bilinear map

μ ⁣:Pa×(Pb⊗P2)→(Pa+b−1⊗P2)\mu\colon P_a \times (P_b \otimes P_2) \to (P_{a + b - 1} \otimes P_2)

that maps (f,g)↦fg(f, g) \mapsto fg. Say P2P_2 has variable vv and all the other spaces have variable uu, so here gg is a polynomial in uu and vv whose degree in uu is at most b−1b - 1 and whose degree in vv is at most 1. Alternatively, think of gg as a vector of length two with entries in PbP_b. We know there exists an isomorphism φd ⁣:Pd⊗P2→Pd−1⊕Pd+1\varphi_d\colon P_d \otimes P_2 \to P_{d - 1} \oplus P_{d + 1} since they are both 2d2d-dimensional vector spaces over FF. Let θ ⁣:Pa×(Pb−1⊕Pb+1)→Pa+b−2⊕Pa+b\theta\colon P_a \times (P_{b-1} \oplus P_{b+1}) \to P_{a + b - 2} \oplus P_{a+b} be the bilinear map associated with the shared-leg sum C(a,b−1)⊞C(a,b+1)C(a, b - 1) \mathop{\boxplus} C(a, b + 1), the target of our degeneration. It maps (f,(g,h))↦(fg,fh)(f, (g, h)) \mapsto (fg, fh). This gives us a square:

Pa×(Pb⊗P2)→μPa+b−1⊗P2idPa×φb↓↓φa+b−1Pa×(Pb−1⊕Pb+1)→θPa+b−2⊕Pa+b\begin{CD} {P_a \times (P_b \otimes P_2)} @>{\mu}>> {P_{a + b - 1} \otimes P_2} \\ @V{\mathrm{id}_{P_a} \times \varphi_b}VV @VV{\varphi_{a+b-1}}V \\ {P_a \times (P_{b-1} \oplus P_{b+1})} @>{\theta}>> {P_{a + b - 2} \oplus P_{a+b}} \end{CD}

If this diagram were commutative, then the proof would be finished. In fact, we would have proved the stronger statement that the two tensors of interest are equal because their associated maps μ\mu and θ\theta would be the same up to isomorphisms on their outputs and second inputs. However, this is not generally the case. Instead, we will define φd\varphi_d in such a way that the diagram almost commutes, and use a degeneration to handle the error terms.

We construct φd\varphi_d by defining a basis BdB_d of Pd⊗P2P_d \otimes P_2 composed of two disjoint sets Bd−B_d^- and Bd+B_d^+ such that φd\varphi_d isomorphically maps Bd−B_d^- onto Pd−1⊕0P_{d-1} \oplus 0 and Bd+B_d^+ onto 0⊕Pd+10 \oplus P_{d+1}. Let

Bd−={ui(u−v)∣0≤i<d−1},Bd+={uiv∣0≤i<d}∪{1}.B_d^- = \{u^i(u-v) \mid 0 \leq i < d - 1\}, \quad B_d^+ = \{u^iv \mid 0 \leq i < d\} \cup \{1\}.

Indeed, these sets are disjoint, ∣Bd−∣=d−1|B_d^-| = d - 1, and ∣Bd+∣=d+1|B_d^+| = d + 1, so the dimensions are correct. They also span Pd⊗P2P_d \otimes P_2 because Bd+B_d^+ contains 1 and every uivu^iv, and the identity ui+1=ui(u−v)+uivu^{i+1} = u^i(u - v) + u^iv recovers the remaining monomials. Now that we have a basis, let

φd(ui(u−v))=(ui,0),φd(uiv)=(0,ui+1),φd(1)=(0,1).\varphi_d(u^i(u - v)) = (u^i, 0), \quad \varphi_d(u^iv) = (0, u^{i+1}), \quad \varphi_d(1) = (0, 1).

Take an arbitrary f∈Paf \in P_a and write f=∑j=0a−1αjujf = \sum_{j=0}^{a-1} \alpha_j u^j. Observe how on the second component, φd\varphi_d substitutes v↦uv \mapsto u, an operation that commutes with multiplication by ff. But on the first component, φd\varphi_d drops constant terms and divides by u−vu - v. This does not commute with multiplication by ff as we are about to see. We compute the values of φa+b−1∘μ\varphi_{a + b - 1} \circ \mu when ff is paired with each element of BbB_b:

Pa×(Pb⊗P2)→μPa+b−1⊗P2→φa+b−1Pa+b−2⊕Pa+bBb−{ui(f,ui(u−v))↦fui(u−v)↦(fui,0)Bb+{ui∑(f,uiv)↦fuiv↦(0,fui+1)(f,1)↦f↦(∑j=1a−1αjuj−1,f)(14)\htmlId{maps}{ \begin{array}{rccccc} & P_a \times (P_b \otimes P_2) & \xrightarrow{\mu} & P_{a+b-1} \otimes P_2 & \xrightarrow{\varphi_{a+b-1}} & P_{a+b-2} \oplus P_{a+b} \\[0.75em] B_b^- \left\{\vphantom{u^i}\right. & (f, u^i(u - v)) & \mapsto & fu^i(u - v) & \mapsto & (fu^i, 0) \\[0.25em] \smash{\raisebox{-1.05em}{$B_b^+ \left\{\vphantom{\begin{matrix} u^i \\[0.5em] \sum \end{matrix}}\right.$}} & (f, u^iv) & \mapsto & fu^iv & \mapsto & (0, fu^{i+1}) \\[0.25em] & (f, 1) & \mapsto & f & \mapsto & \left(\sum_{j=1}^{a-1} \alpha_ju^{j-1}, f \right) \end{array} }\tag{14}

And we do the same for θ∘(idPa×φb)\theta \circ (\mathrm{id}_{P_a} \times \varphi_b):

Pa×(Pb⊗P2)→idPa×φbPa×(Pb−1⊕Pb+1)→θPa+b−2⊕Pa+bBb−{ui(f,ui(u−v))↦(f,(ui,0))↦(fui,0)Bb+{uiui(f,uiv)↦(f,(0,ui+1))↦(0,fui+1)(f,1)↦(f,(0,1))↦(0,f)\begin{array}{rccccc} & P_a \times (P_b \otimes P_2) & \xrightarrow{\mathrm{id}_{P_a} \times \varphi_b} & P_a \times (P_{b-1} \oplus P_{b+1}) & \xrightarrow{\theta} & P_{a+b-2} \oplus P_{a+b} \\[0.75em] B_b^- \left\{\vphantom{u^i}\right. & (f, u^i(u - v)) & \mapsto & (f, (u^i, 0)) & \mapsto & (fu^i, 0) \\[0.25em] \smash{\raisebox{-0.85em}{$B_b^+ \left\{\vphantom{\begin{matrix} u^i \\[0.25em] u^i \end{matrix}}\right.$}} & (f, u^iv) & \mapsto & (f, (0, u^{i+1})) & \mapsto & (0, fu^{i+1}) \\[0.25em] & (f, 1) & \mapsto & (f, (0, 1)) & \mapsto & (0, f) \end{array}

In the first and second lines of each table, φa+b−1∘μ\varphi_{a + b - 1} \circ \mu behaves identically to θ∘(idPa×φb)\theta \circ (\mathrm{id}_{P_a} \times \varphi_b). It is only on the third lines when the second input is 1 that they differ because φa+b−1\varphi_{a+b-1} picks up some unwanted terms in the first component of the output. This is the noncommutativity of dropping constants mentioned above. We can get rid of that ∑j=1a−1αjuj−1\sum_{j=1}^{a-1} \alpha_ju^{j-1} by using a degeneration to multiply it by a power of ε\varepsilon. First, we use (14) to see which components of the output are nonzero in the image of φa+b−1∘μ\varphi_{a + b - 1} \circ \mu when the second input is restricted to Bb−B_b^- or Bb+B_b^+:

Pa+b−2outputPa+b−2Pa+b−2Pa+bsecond inputBb−✓×Bb+✓✓\begin{array}{rc|cc} & & \hphantom{P_{a+b-2}} \mathrlap{\hspace{5pt} \mathclap{\text{output}}} & \hphantom{P_{a+b-2}} \\ & & P_{a+b-2} & P_{a+b} \\ \hline \smash{\raisebox{-0.6em}{\text{second input}}} & B_b^- & \checkmark & \times \\ & B_b^+ & \checkmark & \checkmark \end{array}

The unwanted terms all live in the bottom-left entry, so if we imagine multiplying the second row and the first column each by ε\varepsilon, then the unwanted terms get multiplied by ε2\varepsilon^2 while the diagonal terms only get multiplied by ε\varepsilon (the top-right entry is empty so we ignore it). To formalize this, the degeneration needs three homomorphisms

dU ⁣:Pa∗→Pa∗[ε],dV ⁣:(Pb⊗P2)∗→(Pb−1⊕Pb+1)∗[ε],dW ⁣:(Pa+b−1⊗P2)→(Pa+b−2⊕Pa+b)[ε].\begin{align*} d_U&\colon P_a^* \to P_a^*[\varepsilon], \\ d_V&\colon (P_b \otimes P_2)^* \to (P_{b-1} \oplus P_{b+1})^*[\varepsilon], \\ d_W&\colon (P_{a+b-1} \otimes P_2) \to (P_{a+b-2} \oplus P_{a+b})[\varepsilon]. \end{align*}

Let dUd_U be the identity. Multiplying the second row by ε\varepsilon means letting dVd_V multiply the duals of elements of Bb+B_b^+ by ε\varepsilon and then applying (φb−1)∗(\varphi_b^{-1})^*. Similarly, multiplying the first column by ε\varepsilon means letting dWd_W multiply elements of Ba+b−1−B_{a+b-1}^- by ε\varepsilon and then applying φa+b−1\varphi_{a+b-1}. Let ρ\rho be the bilinear map associated with (dU⊗dV⊗dW)(C(a,b)⊗C(1,2))(d_U \otimes d_V \otimes d_W)(C(a, b) \otimes C(1, 2)). So

Bb−{uiρ(f,φb(ui(u−v)))=(εfui,0)=εθ(f,φb(ui(u−v)))Bb+{ui∑ρ(f,φb(uiv))=(0,εfui+1)=εθ(f,φb(uiv))ρ(f,φb(1))=(ε2∑j=1a−1αjuj−1,εf)=εθ(f,φb(1))+ε2e.\begin{array}{rccccc} B_b^- \left\{\vphantom{u^i}\right. & \rho(f, \varphi_b(u^i(u - v))) & = & \left(\varepsilon fu^i, 0\right) & = & \varepsilon \theta(f, \varphi_b(u^i(u - v))) \\[0.25em] \smash{\raisebox{-1.05em}{$B_b^+ \left\{\vphantom{\begin{matrix} u^i \\[0.5em] \sum \end{matrix}}\right.$}} & \rho(f, \varphi_b(u^iv)) & = & \left(0, \varepsilon fu^{i+1}\right) & = & \varepsilon \theta(f, \varphi_b(u^iv)) \\[0.25em] & \rho(f, \varphi_b(1)) & = & \left(\varepsilon^2 \sum_{j=1}^{a-1}\alpha_ju^{j-1}, \varepsilon f\right) & = & \varepsilon \theta(f, \varphi_b(1)) + \varepsilon^2 e. \end{array}

We have thus constructed a degeneration of degree one, finishing the proof.

Lemma 24 follows quickly from this degeneration. Multiplicativity tells us

2γ(a,b)=γ(a,b)γ(1,2)=Ξ(C(a,b)⊗C(1,2)).(15)\htmlId{concavity1}{ 2\gamma(a, b) = \gamma(a,b)\gamma(1,2) = \Xi(C(a, b) \otimes C(1, 2)). }\tag{15}

We can write

Ξ(C(a,b)⊗C(1,2))≥Ξ(C(a,b−1)⊞C(a,b+1))≥γ(a,b−1)+γ(a,b+1),(16)\htmlId{concavity2}{ \begin{align*} \Xi(C(a, b) \otimes C(1, 2)) &\geq \Xi(C(a, b - 1) \mathop{\boxplus} C(a, b + 1)) \\ &\geq \gamma(a, b - 1) + \gamma(a, b + 1), \end{align*} }\tag{16}

where the first inequality is given by Proposition 29 and monotonicity, and the second inequality is given by superadditivity. Combining (15) and (16) proves the lemma as rearranged in (13).

Shifted Tripling

We are barreling down the home stretch and all that stands in our way is the following degeneration that enables us to prove Lemma 25.

Partition each of the second and third legs of C(a,3b+a−1)C(a, 3b + a - 1) into three parts as follows:

y0,…,yb−1⏞Y1yb,…,y2b+a−2⏞Y2y2b+a−1,…,y3b+a−2⏞Y3z0,…,za+b−2⏟Z1za+b−1,…,z2b+a−2⏟Z2z2b+a−1,…,z3b+2a−3⏟Z3\begin{array}{c|c|c} \overbrace{y_0, \ldots, y_{b-1}}^{\textstyle Y_1} & \overbrace{y_b, \ldots, y_{2b+a-2}}^{\textstyle Y_2} & \overbrace{y_{2b+a-1}, \ldots, y_{3b+a-2}}^{\textstyle Y_3} \rule[-0.75em]{0pt}{0.75em} \\ \hline \underbrace{z_0, \ldots, z_{a+b-2}}_{\textstyle Z_1} & \underbrace{z_{a+b-1}, \ldots, z_{2b+a-2}}_{\textstyle Z_2} & \underbrace{z_{2b+a-1}, \ldots, z_{3b+2a-3}}_{\textstyle Z_3} \rule{0pt}{1em} \end{array}

Consider only the terms in C(a,3b+a−1)C(a, 3b + a - 1) whose variables in the second and third legs are from YiY_i and ZiZ_i respectively. When ii is 1 or 3, we get a copy of C(a,b)C(a, b). When i=2i = 2, we get a copy of C(a,b)C(a, b) with the second and third legs swapped. The proofs of these equivalences are formal and involve a lot of tedious reindexing, so we omit them.

Our goal is to eliminate all terms with variables from YiY_i and ZjZ_j with i≠ji \neq j. Since every term is of the form xi⊗yj⊗zi+jx_i \otimes y_j \otimes z_{i+j} and i<ai < a, there are already no terms from the following pairs of blocks: (Y1,Z2),(Y1,Z3),(Y3,Z1),(Y3,Z2)(Y_1, Z_2), (Y_1, Z_3), (Y_3, Z_1), (Y_3, Z_2). So we only need to worry about Y2Y_2 mixing with Z1Z_1 and Z3Z_3. Let the degeneration maps multiply variables in Y2Y_2, Z1Z_1, and Z3Z_3 by ε\varepsilon. This multiplies all the unwanted terms by ε2\varepsilon^2 while all the other nonzero terms only get multiplied by ε\varepsilon, giving us the desired result. The following figure shows this degeneration with a=4a = 4 and b=3b = 3.

The polynomial multiplication tensor C(4, 12), drawn with y across and z up. Both legs are cut into three parts; cubes in the blocks Y₁×Z₁, Y₂×Z₂ and Y₃×Z₃ are colored and outlined, and the gray cubes are the entries from Y₂ that land in Z₁ or Z₃.

Lemma 25 follows immediately by applying Ξ\Xi and its superadditivity to both sides of this degeneration.

Afterword

As I was working on this post, especially toward the end, I kept questioning myself: “Why am I writing this?” What is the purpose of repackaging AI-generated math? The reason I had when I started was simple. I wanted to create a learning resource accessible to math and computer science undergraduates that consolidated into one place everything you needed to understand the newest developments in the theory of matrix multiplication. I started learning about this subject almost two years ago, before LLMs took math by storm, because I read in Yufei Zhao’s excellent Graph Theory and Additive Combinatorics that the existence of large sets with no three-term arithmetic progressions given by Behrend’s construction was an integral part of Coppersmith and Winograd’s matrix multiplication algorithm [15][16]. Put simply, a clever construction in combinatorics somehow enabled progress to be made on the upper bound of ω\omega. This was such a surprising connection to me and I desperately wanted to understand it. I found myself bouncing between many learning resources, the most helpful of which was probably Williams’ lecture notes, until I eventually wrapped my head around the proof. I then started working on a video for my YouTube channel explaining the main ideas of the argument, but the project quickly grew in scope and I had to put it on the back burner.

Cut to October 6th when I found out OpenAI released a proof that ω≤9/4\omega \leq 9/4. I opened the preprint and was shocked at how short it was: only 13 pages with citations. Then I started reading it and was shocked again at how graspable many of the ideas were. Then I continued reading it and was not shocked at all when I realized many of the proofs were poorly written and that I was totally lost. So I set myself the goal to fully understand the paper and to write a post about it. I wanted to give the reader all the context they would need and to write the proofs in a simpler, more accessible way. It felt like I could produce something “useful”.

Now it is today, I am procrastinating on writing the last few proofs, staring at this blog post that has slowly ballooned into a textbook chapter, and I have had plenty of time to ruminate. What I have come to realize is that I have a second, more personal reason for writing this: This post is a certificate of my understanding. Sure, maybe I can save someone a few tokens who wants to learn about matrix multiplication, or maybe I can even introduce someone to the field (and I really hope I do!), but these hopes are tied to the vicissitudes of AI and how people spend their time. All that I can be truly certain of is that I, at this very moment, understand a proof that ω≤9/4\omega \leq 9/4. I am shouting into the void, “I get it!” That is inalienable.

Before finally signing off, I want to emphasize that this post was a lot of fun to write. I truly believe that this is one of the most exciting times to be a recreational mathematician. The barrier to engage with research mathematics has never felt lower, and I hope we continue to take advantage of that.

Footnotes

  1. The reason ε\varepsilon needs to be in the time complexity is that ω\omega is actually a limit point. Coppersmith and Winograd proved the surprising result that given an algorithm for multiplying matrices, there exists a faster one [17]. ↩

  2. See stars and bars. ↩

  3. It feels strange to criticize the source material in this way, but I think this will become a more common practice in the brave new world. If exposition is going to play such an important part in the act of the doing mathematics, then highlighting the expository choices made should be an expected part of mathematical writing. On the other hand, I cannot help but worry that this sentiment might be a reflection of the current transitory state where LLMs are better provers but worse explainers and theory builders than humans. Maybe all that we will have left is the interpersonal: teacher empathizing with student, or colleague sharing with colleague. ↩

References

  1. OpenAI. An Upper Bound of 9/49/4 for the Matrix Multiplication Exponent. OpenAI Math Release preprint https://github.com/openai/math/blob/main/preprints/Matrix-Multiplication-Nine-Fourths-October-2-2026/paper.pdf; 2026.
  2. Lü H. Polynomial Separation of a Shared Tensor Leg and Matrix Multiplication in Arbitrary Characteristic. arXiv preprint arXiv:261018914. 2026;
  3. Amanov A, Berg M van den, Zuiddam J. Multiplying matrices via polynomials: exposition and barriers. arXiv preprint arXiv:261030054. 2026;
  4. Navot S. The Matrix Multiplication Bound ω≤9/4\omega \le 9/4 over Arbitrary Fields [Internet]. Manuscript, GitHub repository selanavot/matrix-multiplication-all-fields; 2026. Available from: https://github.com/selanavot/matrix-multiplication-all-fields/blob/main/paper/paper.pdf
  5. Zuiddam J. omega-nine-quarters-all-fields: Lean proof that the matrix multiplication exponent is at most 9/49/4 over every field [Internet]. GitHub repository; 2026. Available from: https://github.com/jzuiddam/omega-nine-quarters-all-fields
  6. Dupont E, Eisenberger M, Kozlovskii B, Mehrabian A, Ruiz FJ, See A, et al. Improving the matrix multiplication exponent with modern optimization and AlphaEvolve. arXiv preprint arXiv:260816884. 2026;
  7. Schönhage A. Partial and total matrix multiplication. SIAM Journal on Computing. 1981;10(3):434–55.
  8. Strassen V. Relative bilinear complexity and matrix multiplication. 1987;
  9. Strassen V. The asymptotic spectrum of tensors. 1988;
  10. Strassen V. Gaussian elimination is not optimal. Numerische Mathematik. 1969;13(4):354–6.
  11. Winograd S. On multiplication of 2×22 \times 2 matrices. Linear algebra and its applications. 1971;
  12. Shitov Y. Counterexamples to Strassen’s direct sum conjecture. 2019;
  13. Bini D. Relations between exact and approximate bilinear algorithms. Applications. Calcolo. 1980;17(1):87–97.
  14. Wigderson A, Zuiddam J. Asymptotic spectra: Theory, applications and extensions. Manuscript dated October. 2023;24.
  15. Zhao Y. Graph theory and additive combinatorics: exploring structure and randomness. Cambridge University Press; 2023.
  16. Coppersmith D, Winograd S. Matrix multiplication via arithmetic progressions. In: Proceedings of the nineteenth annual ACM symposium on Theory of computing. 1987. p. 1–6.
  17. Coppersmith D, Winograd S. On the asymptotic complexity of matrix multiplication. SIAM Journal on Computing. 1982;11(3):472–92.