Skip to content
Preprint

Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of $\omega\le9/4$

Oct 2026 · 0 citations · 13 references
Computer Science

Abstract

We give a self-contained constructive proof that the matrix multiplication exponent satisfies $\omega\le9/4$. This bound was recently claimed by OpenAI~\cite{original} through non-constructive arguments in Strassen's asymptotic spectral framework, counting exact scalar arithmetic operations over the complex numbers. We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. For every $\gamma>0$, the resulting algorithm multiplies two $n\times n$ integer matrices using $O(n^{9/4+\gamma})$ integer arithmetic operations.

View source

Similar papers

Preprint Sep 2026

A Quadratic Lower Bound on Determinantal Complexity

We prove an $\Omega(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over the field of complex numbers. A similar result was claimed in a recent paper of Sheshadri (arXiv:2606.13628), via an AI-assisted and AI-written proof. Assuming its correctness, this was the first...

Mrinal Kumar, Ben Lee Volk · 2 citations
Preprint Oct 2026

Certified Fourier rounding for the real Grothendieck inequality

We give a computer-assisted proof that the real Grothendieck constant is strictly smaller than $1.77987164$. The proof provides a complete interval-arithmetic realization of Ren's five-variable construction. A finite Fourier calculation encloses every scalar coefficient through degree $403$; a fourth-derivative estimat...

Bo Peng · 0 citations
Preprint Sep 2026

Prime Plus a Non-Square-Free Integer: An Elementary Approach

Lee and O'Clarey recently conjectured that every integer $n>24$ can be written as the sum of a prime and a positive integer that is not square-free. They proved this for odd $n$, and for all $n>24$ assuming the generalised Riemann hypothesis for Dirichlet $L$-functions. We prove their conjecture unconditionally for eve...

Peter J. Campbell · 0 citations
Preprint Oct 2026

An explicit elementary proof of no Landau--Siegel zeros

We give an elementary proof of the absence of Landau--Siegel zeros with the explicit constant $c=1/100$. For every primitive quadratic Dirichlet character $\chi$ of conductor $q\ge3$, each real zero $\beta\in(0,1)$ of $L(s,\chi)$ satisfies $(1-\beta)\log q>c$. The proof combines integer coefficient counting, polynomial...

V. Z. Guo · 0 citations
Preprint Oct 2026

Polynomial parametrization of $\text{SL}_2$ over global function field rings

We combine the universal polynomial matrix identities of Larsen--Nguyen with Trost's arithmetic lemmas to obtain polynomial parametrizations of $\text{SL}_2(\mathcal{O}_{K,S})$ for every global function field $K$ and every nonempty finite set of places $S$. The additional ingredient is a function-field cancellation lem...

D. Q. Nguyen · 0 citations
Preprint Sep 2026

Vector Balancing in Polynomial Time

We present a spectral signing algorithm solving the Koml\'os problem with a constant discrepancy in polynomial time. Given a matrix $A\in\mathbb{R}^{m\times n}$ whose columns have Euclidean norm at most $1$, the algorithm finds a vector $\varepsilon\in\{-1,1\}^n$ satisfying $\|A\varepsilon\|_\infty\le C$, where $C$ is...

Sheng Guo, Ethan X. Fang, Jun-Wei Lu · 3 citations · ⚡2

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.