51 Additions per Recursive Step for Rank-23 3×33\times 3 Matrix Multiplication, Machine-Checked over Arbitrary Rings

Get email updates

Greg Sidebottom

Sidebottom gives a rank-23 scheme for 3×33\times 3 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.

What was already known

Nielsen’s scheme uses 52 additions in this model. Stapleton and Perminov first reached 51 with a different scheme.

AI involvement AI-centered

Sidebottom directed the work and credits Claude with implementing the search and exact minimizers that found the scheme, together with the Lean development.

Importance Notable

The new scheme matches the earlier count with a separate construction and a Lean proof that preserves multiplication order, so it applies to noncommuting blocks.

Technical verification Formal (Lean 4 and exact computation)

Appendix A reports a Lean check of the complete emitted scheme over arbitrary rings. The repository pipeline also compares all nine outputs with the matrix product over a word ring and counts the operations.

Formal checking

Appendix A reports a Lean check of the complete emitted scheme over arbitrary rings. The repository pipeline also compares all nine outputs with the matrix product over a word ring and counts the operations.

Checker
Lean 4 and Sidebottom’s exact word-ring check
Scope
Checked all nine outputs with the factor order preserved, as well as the recorded operation count.
Basis
Reported by the linked checker

Human understanding Few

The paper describes the basis sweep and signed realization but does not separately attribute an explanation of the search’s central argument to Sidebottom.

Correction and publication history

2026-11-14 · correction

Records the October paper as historical backfill and distinguishes its 11 conversion additions from the earlier scheme’s five.

Read this published revision