Pith.

Computational Complexity · arXiv:2610.28627 v2 · submitted 20 Oct 2026

Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of ω ≤ 9/4

Rafael Pass

The paper says

“We give a self-contained constructive proof that the matrix multiplication exponent satisfies ω ≤ 9/4. In a recent breakthrough, OpenAI i̧teoriginal established this bound in the model of exact scalar arithmetic over the complex numbers, using non-constructive arguments in Strassen's asymptotic spectral framework.”

more of the abstract

We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. For every γ > 0, the resulting algorithm multiplies two n × n integer matrices using O(n9/4 + γ) integer arithmetic operations. As an independent contribution, we develop a framework of polynomial packings—methods for reducing many polynomial multiplications to fewer ones using linear operations. We isolate and generalize a construction of OpenAI i̧teoriginal to obtain a simple packing, and show how packings can be composed to amplify their “compression rate", which finally yields Strassen-like identities.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 21 Oct 2026 · of version 1 of the paper; version 2 is newer · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up, with conditions. First genuinely constructive route to ω ≤ 9/4 with a novel gadget architecture, stalled by a false floor inequality in Section 4.1 that a ceiling repairs while preserving the bound. This line is wrong

This review says the paper's mathematics is wrong. Pith did not check that against the paper's source.

2 major objections · 4 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the references say.

The paper says, at Section 4.1

The review did not quote this passage.

Pith says: Objection 1 of 2 · major

The proof sets t = floor((3L-1)/(c-1)) and asserts that the packing preconditions ct >= a+2b-1 hold at (a,b)=(L,L) and at (L',L) because (c-1)t >= 3L-1. This inequality is false for a floor: (c-1)t <= 3L-1, with equality only when c-1 divides 3L-1.

more of objection 1

For example, c=4 and L=1 gives t=0 and ct=0 < 2, so even the first application of Theorem 2.9 is invalid; for c=4 and L=3, the second application demands ct >= 3L-1+t = 10 while ct=8. Since the one-round reduction is the mechanism that grows the length parameter and shrinks the matrix side, the iteration producing Theorem 4.1 does not follow as written. Replacing the floor by a ceiling restores (c-1)t >= 3L-1 and hence both packing preconditions, so the defect is repairable, but it is load-bearing.

This review says the paper's mathematics is wrong. Pith did not check that against the paper's source.

The paper says, at Section 4.1

The review did not quote this passage.

Pith says: Objection 2 of 2 · major

The displayed length bound L' <= rho L + 1 is not justified by the displayed parameter choices. With t = floor((3L-1)/(c-1)) and rho = 1 + 3/c, the example c=4, L=10 gives t=9 and L'=19, while (1+3/c)L+1 = 18.5.

more of objection 2

The bound that is actually needed, and that does hold, is L' <= (1 + 3/(c-1))L + 1, obtained with t = ceil((3L-1)/(c-1)). With these corrected choices the subsequent exponent calculation log(64 rho^{6d})/log R = 9/4 + O(1/c) is unchanged, so the issue is local; but the authors need to state the corrected pair explicitly and re-verify the iteration.

4 minor objections

The paper says, at Section 1.1

Pith says: minor objection 1 of 4

The word 'nexy' should be 'next'.

The paper says, at Section 4.1

Pith says: minor objection 2 of 4

The expression for rho is typeset ambiguously; it should be stated explicitly as rho = 1 + 3/(c-1) once the ceiling repair is made.

show 2 more

The paper says, at Equation (5)

Pith says: minor objection 3 of 4

With d = c^3, the error term in log(w/u) is actually O(log c), not O(c); this is harmless for the stated asymptotic conclusion but should be corrected.

The paper says, at Lemma 3.3

Pith says: minor objection 4 of 4

The claim that polynomial multiplication of length L can be computed with O(L) scalar products via evaluation and interpolation is correct for exact rational arithmetic, but the evaluation points may require large representation; a sentence clarifying that the complexity count is algebraic would improve readability.

What would settle it

Instantiate the one round of Section 4.1 at c=4, L=3 exactly as written with t=floor(8/3)=2 and L'=5, and check whether the second packing precondition ct≥L'+2L-1 holds (8≥10 fails), confirming the concern. Then rerun with t=ceil(8/3)=3 and ρ=1+3/(c-1): all packing preconditions hold, L+t≤ρL+1 becomes 6≤6, and log(64ρ^{6d})/log R remains 9/4+O(1/c), showing the repair is sufficient.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 21 Oct 2026

  1. Reader holds up, with conditions confidence moderate
  2. Skeptic agrees 1 min 53 s · 18,313 tokens read, 19,161 written
  3. Editor wrote the verdict above 38 s · 19,372 tokens read, 6,466 written
  4. Referee major revision: 2 major objections, 4 minor 2 min 0 s · 18,874 tokens read, 20,349 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

Read this one. It is the first genuinely constructive shot at ω ≤ 9/4: an explicit rational identity plus integer-arithmetic recursion, standing on ordinary algebra rather than the OpenAI asymptotic-spectrum machinery. The multivariate packing amplification across 2d variables and the interpolation-based left-input separation (Lemma 2.8) are new, and the proof is self-contained — the three-for-one gadget is reproved as the c=1 case, and composition, transposition, and Bini conversion are proved in the text, not cited away. I checked the exponent count: d=c3 gives log(w/u)=4c2+O(c), so the per-round growth log(64ρ6d)/log R lands at 9/4+O(1/c). There is no fitting anywhere; the 9/4 falls out of the algebra. The galactic-constant caveat is stated honestly, and the AI-use disclosure is unusually candid, including a footnote attributing the separation encoding idea to Codex.

The soft spot is real, and it is exactly where the reader put it. In the proof of Theorem 4.1, t is set to floor((3L−1)/(c−1)) and the text claims (c−1)t ≥ 3L−1. A floor gives the opposite inequality, with equality only when c−1 divides 3L−1. Example: c=4, L=3 gives t=2, and the second packing application needs ct ≥ L′+2L−1 = 3L−1+t = 10, but ct=8. So the precondition of Theorem 2.9 fails at (L′,L), and the round, as written, is broken. This is load-bearing — Theorem 4.1's identity comes from iterating this round. The stress-test's repair is right: replace the floor with a ceiling; then (c−1)t ≥ 3L−1 holds and L′ ≤ (1+3/(c−1))L + O(1) preserves the same asymptotics. It is a one-line fix, and the architecture is intact.

The length-bound complaint is secondary. The rho in the text is garbled: if it means 1+3/(c−1), the floor version of L′ ≤ ρL+1 is fine; if it means 1+3/c, it fails. Either way, the floor inequality is the issue that matters.

Minor caveat: no code, no machine-checked proof, and the identity is shown computable rather than exhibited. Acceptable for this genre, but it means the argument rests on human-checkable algebra.

Who it is for: the matrix multiplication crowd, and anyone tracking the OpenAI 9/4 claim who wants a constructive witness. It deserves a serious referee; the claim is major and the defect is localized. My recommendation: send it to review with a specific request to check Section 4.1 recurrences, and expect a conditional accept with the ceiling fix. I would bring it to reading group.

The strongest objection

The finite identity in Theorem 4.1 is obtained by iterating the one-round reduction in Section 4.1, so that reduction is load-bearing. The paper sets t=floor((3L-1)/(c-1)), L'=L+t, and claims the packing preconditions hold both at (a,b)=(L,L) and at (L',L), since (c-1)t≥3L-1. For the second application, Lemma 2.4 and Theorem 2.9 with a=L', b=L require ct ≥ a+2b-1 = (L+t)+2L-1 = 3L-1+t, which is exactly (c-1)t ≥ 3L-1. A floor cannot give this: (c-1)floor(K/(c-1)) ≤ K, with strict inequality unless c-1 divides K. For c=4, L=3, t=2 and ct=8, while the second precondition demands 3L-1+t=10; for c=4, L=2, even the first precondition ct≥5 fails because ct=4. The claimed length bound L'≤(1+3/c)L+1 is also false in general: c=4, L=10 gives t=9, L'=19 > 18.5. The defect is confined to this recurrence; the packing lemmas and Bini conversion are not implicated. Using t=ceil((3L-1)/(c-1)) and ρ=1+3/(c-1) restores (c-1)t≥3L-1 and L'≤ρL+1, and the exponent bound remains 9/4+O(1/c), so the flaw is repairable. But as written, Theorem 4.1 does not follow.

The reader and I isolate the same weak point: Section 4.1's one-round argument. The paper's central theorem cannot be accepted on the written proof because every recursive round passes through the false inequality (c-1)t≥3L-1, and the counterexamples are small and explicit. I do not see a separate obstruction in the polynomial-packing lemmas or in Bini's exactification; the paper gives enough proof detail there to make the main claim plausible pending repair. The suggested correction is natural and preserves the advertised 9/4, which supports a conditional rather than a reject verdict. Since the reader already assigned CONDITIONAL and identified this same assumption, my stress-test pass does not change the verdict. The reader's illustrative numbers for c=4, L=4 contain a small arithmetic slip (the floor is 3, not 1), but the structural point and the proposed ceiling repair are correct.

The referee's report

Assuming the construction is correct, the result is significant: it would give an explicit identity and a recursive algorithm for omega <= 9/4, a bound previously claimed only through non-constructive asymptotic spectral arguments. The paper is unusually self-contained: it proves the closure properties it uses, and it reproves (as the c=1 case) the OpenAI gadget rather than relying on it. The exponent 9/4 is not fitted; it emerges from asymptotic parameter choices. However, the one-round recurrence in Section 4.1 contains a false inequality on which the entire identity construction depends. The error is localized and has an obvious repair, but until the recurrence is corrected and the proof re-verified, the central theorem is not established.

Pith's reading of the paper (a machine's summary, not the authors')

The paper claims a proof that the matrix multiplication exponent satisfies $\omega \le 9/4$, by explicit construction rather than by the non-constructive spectral argument of a recent preprint claiming the same bound. The core object is a 'polynomial packing': a telescoping gadget that recovers $c+2$ polynomial products of matrix coefficients from only $c$ source products, whose saving is amplified across many variables, converted to independent left inputs, and turned into a fixed identity $AB = \sum_\nu \ell_\nu(A)m_\nu(B)W_\nu$ with $\log_v r$ arbitrarily close to $9/4$. Ordinary block recursion on that identity then gives the claimed recursive integer algorithm with $O(n^{9/4+\gamma})$ operations for every $\gamma>0$. The construction is self-contained and runs on integer arithmetic. The critical one-round length-growth inequality in Section 4.1, however, appears to rely on a false bound, so the $9/4$ asymptotics likely survive a corrected round but not the proof exactly as written.

What carries the argument. The central device is the polynomial packing (PP; same-left SL-PP), a list of linear encoders, source polynomial products, and linear decoders whose composed map matches the target modulo a formal parameter $\varepsilon$. The load-bearing identity is the telescoping sum $W = \sum_j z^{t(j-1)} A E_j = AP_1 - z^{ct}AP_{c+1} + \varepsilon z^b A Q$, in which all intermediate products cancel, the endpoints occupy disjoint coefficient ranges, and the shifted $\varepsilon AQ$ fills the empty gap to yield a 'middle product', giving $c+2$ outputs from $c$ sources. Amplification comes from running primal packings in the first $d$ variables and dual packings in the last $d$ of $2d$ variables, gaining a multiplicative factor $((c+2)/c)^{2d}$, from separating left inputs via polynomial interpolation, and from a three-role exchange that reduces rows, inner dimension, and columns simultaneously. Bini's approximate-to-exact lemma converts the $\varepsilon$-packing into the exact identity (6).

Core claim. On its own terms, the paper proves Theorem 1.1: for every $\gamma>0$, an explicit recursive algorithm multiplies two $n\times n$ integer matrices in $O(n^{9/4+\gamma})$ integer arithmetic operations, so $\omega \le 9/4$. The route is elementary: a $(c+2)$-for-$c$ 'polynomial packing' modulo $\varepsilon$ recovers $c+1$ full products and one middle product from $c$ source products via the telescoping sum $W = \sum_j z^{t(j-1)}AE_j = AP_1 + \varepsilon z^b AQ - z^{ct}AP_{c+1}$, where intermediate terms cancel and the shifted $\varepsilon$-block fills an empty coefficient gap. Primal and dual packings are combined across $2d$ variables to amplify the output count by $((c+2)/c)^{2d}$, left inputs are separated by interpolation, all three matrix dimensions are reduced at once, and after finitely many rounds Bini's approximate-to-exact conversion yields an exact rational identity $AB = \sum_\nu \ell_\nu(A)m_\nu(B)W_\nu$ with $\log_v r$ arbitrarily close to $9/4$; ordinary block recursion on this identity finishes the proof.

The premise it rests on. The one-round reduction in Section 4.1 assumes that $t = \lfloor (3L-1)/(c-1)\rfloor$ satisfies $(c-1)t \ge 3L-1$ and that $L+t \le (1+3/c)L+1$; the floor gives $(c-1)t \le 3L-1$, and for large $L$ the length bound fails (for $c=4$, $L=9$, $L'=17 > 16.75 = (1+3/4)\cdot 9+1$), so the written proof rests on a false inequality, although a ceiling and $\rho = 1+3/(c-1)$ would restore the asymptotic $9/4$.

If the paper is right (Pith's inferences, not the authors')

For every $\gamma>0$ the construction yields an explicit recursive algorithm computing $n\times n$ integer matrix products in $O(n^{9/4+\gamma})$ operations, so $\omega \le 9/4$.

The bound is certified by a concrete finite identity $AB = \sum_\nu \ell_\nu(A)m_\nu(B)W_\nu$ with $\log_v r < 9/4 + \gamma$, making the exponent checkable by direct verification of the identity rather than by a spectral existence argument.

The algorithm runs on integer arithmetic with bit cost $O(n^{9/4+\gamma}M(B + \log n))$, unlike the non-constructive complex-scalar statement it answers.

Because the constants are 'galactic' (enormous, as the authors state), the result is a structural bound, not a practical algorithm.

My reading of Section 4.1 is that the false length bound is a repairable gap: replacing the floor by a ceiling and $\rho = 1+3/c$ by $1+3/(c-1)$ preserves the asymptotic $9/4$, so the plausible outcome is a corrected proof rather than a dead claim, and a careful reader should demand the corrected round before trusting the conclusion.

If the packing chain is sound, tuning $c$, $d$, and the terminal evaluation bound may push the constant toward or below $9/4$ or yield rectangular multiplication bounds, since the $(c+2)/c$ gain and the $d+1$ shape-selection loss are the only free parameters.

The exactness of the final identity rests on the terminal bound $O(L^{6d})$ matrix products and on the degree $D$ in Bini's conversion; computing these constants for small $c,d$ would give a cheap empirical test of the whole construction.

A natural testable extension is to run the $(c+2)$-for-$c$ packing with the packing precondition $ct \ge a+2b-1$ enforced exactly (using a ceiling), and measure the resulting exponent for small $d$ to see how close to $9/4$ the finite identity actually lands.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

We give a self-contained constructive proof that the matrix multiplication exponent satisfies ω ≤ 9/4. In a recent breakthrough, OpenAI i̧teoriginal established this bound in the model of exact scalar arithmetic over the complex numbers, using non-constructive arguments in Strassen's asymptotic spectral framework. We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. For every γ > 0, the resulting algorithm multiplies two n × n integer matrices using O(n9/4 + γ) integer arithmetic operations. As an independent contribution, we develop a framework of polynomial packings—methods for reducing many polynomial multiplications to fewer ones using linear operations. We isolate and generalize a construction of OpenAI i̧teoriginal to obtain a simple packing, and show how packings can be composed to amplify their “compression rate", which finally yields Strassen-like identities.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-10-21

The authors' main claim, as the classifier picked it out 1.00

“We give a self-contained constructive proof that the matrix multiplication exponent satisfies $\omega\le9/4$.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.37 · human participants 0.01 · controlled comparison 0.06 · randomized assignment 0.01 · states quantitative result 0.99 · compares with prior results 0.96 · mentions code or data availability 0.03

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
We give a self-contained constructive proof that the matrix multiplication exponent satisfies $\omega\le9/4$. result 0.53 0.97 0.97 asserted 1.00
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. background 0.97 0.03 0.03 asserted 0.99
We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. method 0.87 0.96 0.15 asserted 1.00
For every $\gamma>0$, the resulting algorithm multiplies two $n\times n$ integer matrices using $O(n^{9/4+\gamma})$ integer arithmetic operations. result 0.99 0.93 0.24 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-21: 1 request, 3,610 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (2)
Figure 1 of the paper
Figure 1. The telescoping sum before and after adding
Figure 2 of the paper
Figure 2. The bivariate construction for c = 4. Each original column contains five Full inputs and one Mid input in x; each original row contains five Mid inputs and one Full input in y. After encoding, compute the sixteen products AVr,s, Full in x and Mid in y, at the longer source lengths. Decode in y and then in x to recover all thirty-six requested outputs modulo ε. computing all x-coefficients and the y-coefficients at exponents a − 1, . . . , a + b − 1. Apply the dual decoder in y, then the primal decoder in x. Encoding in x and then in y, computing the source products, and decoding in…

Figures are the authors', reproduced from the paper.

Cited by 5 Pith papers

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment