Addition counts for rank-23 matrix multiplication
A rank-23 scheme multiplies two matrices with 23 products of linear forms. How many additions and subtractions does it need at each recursive step when changes into and out of alternative bases can be shared across steps?
Why it matters and what counts as progress
Why it matters: The multiplication count gives only one part of the cost. A low addition count makes a recursive scheme cheaper, particularly when each entry is itself a matrix block.
What counts as progress: Give a correct scheme with fewer additions under the same accounting or prove a lower bound with a precise scope. State whether the scheme works over arbitrary rings and count basis conversion separately.
How the problem developed
- 26 Sept 2026 · Earlier 51-addition scheme [3]
Joshua Stapleton and Andrew Perminov Gave a rank-23 alternative-basis kernel with 51 additions and five more for conversion.
Greg Sidebottom with Claude Reported another 51-addition recursive kernel with a Lean proof over arbitrary rings.
AI contribution
51 Additions per Recursive Step for Rank-23 Matrix Multiplication, Machine-Checked over Arbitrary Rings
Sidebottom gives a rank-23 scheme for matrix multiplication over arbitrary rings. It uses 51 additions or subtractions per recursive step in the alternative-basis model, with 11 further additions for conversion in a one-shot computation.
Sources
Publication history
Daily emails by default, only when there’s an update.