Research · Papers · Direct sums, wedges and the p14 frontier · MF-086
Multiplicative complexity of independent copies of 2×2 matrix multiplication over GF(2)
rank_CP/bilinear(M₂^⊕s) = 7s, MC_formal-quadratic(M₂^⊕s) = 7s over GF(2)
Published 2026-08-29
For everyone
Plain summary
MF-086 proves that computing s independent copies of 2×2 matrix multiplication over GF(2) takes exactly seven multiplications per copy in two structured settings. Under bilinear rank and formal-quadratic multiplicative complexity, the total cost is 7s. Combining separate copies yields zero savings in these models.
This bound has a precise boundary. General Boolean circuits built from XOR and AND gates (XAGs) can generate higher-degree expressions, cancel them later, and apply idempotence (where squaring a bit leaves it unchanged). The 7s argument does not cover those unrestricted circuits. Alder–Strassen and Strassen established the structured 7s baseline; whether unrestricted Boolean circuits can beat seven products per copy remains open.
Result
For s independent copies of M₂ over GF(2):
\[ \operatorname{rank}_{\mathrm{CP/bilinear}}(M_2^{\oplus s}) = 7s, \qquad \operatorname{MC}_{\mathrm{formal\text{-}quadratic}}(M_2^{\oplus s}) = 7s. \]
Six affine-factor gates cannot compute a single copy. The result holds strictly for the bilinear and formal-quadratic models and makes no equality claim for unrestricted sequential Boolean XAG multiplicative complexity.
Setting and definitions
Let M₂ denote the 2×2 matrix multiplication map over GF(2), and M₂^{⊕s} its s-fold direct sum. The CP/bilinear rank counts product terms in the bilinear model; formal-quadratic multiplicative complexity counts product gates in the formal-quadratic model. An affine-factor gate takes inputs strictly from the affine forms permitted by the model. An unrestricted sequential Boolean XAG combines XOR and AND gates, allowing higher-degree intermediates that may cancel downstream.
The structured models restrict intermediate representations to bilinear or formal-quadratic forms. Unrestricted sequential Boolean circuits admit intermediate algebraic simplifications via field and Boolean equivalences. Consequently, equality in the structured measures does not imply equality for Boolean multiplicative complexity.
Method
The 7s value matches the Alder–Strassen lower bound with Strassen’s upper bound across the bilinear and formal-quadratic models. The one-copy six-affine-factor obstruction establishes the base case. Full derivations, scope boundaries, and supporting search artifacts appear in this paper's downloadable evidence pack.
These Boolean search implementations chart the model boundary. The register contains no six-gate impossibility certificate for the unrestricted sequential Boolean model.
Discussion
MF-086 proves direct-sum additivity at 7s exclusively for CP/bilinear and formal-quadratic models. Bilinear circuits embed into quadratic circuits, which embed into unrestricted XOR–AND circuits (Boyar–Find). Because M₂ produces four outputs (eight for two copies), no quadratic normalisation exists for this vector-output setting. Unrestricted XAGs can exploit intermediate degree growth and Boolean idempotence (x² = x), preventing a direct transfer of the Alder–Strassen and Strassen bound. The unrestricted Boolean status remains open, and no correction is recorded for MF-086.
Two subsequent tests are planned. First, refuting an unrestricted six-gate sequential circuit for M₂ would close the single-copy gap and establish MC(M₂) = 7 against Strassen's upper bound. Second, a 13-gate search on two copies would test functional direct-sum additivity, a problem distinct from tensor rank additivity. Neither the single-copy Boolean lower bound nor direct-sum additivity is settled by MF-086.
For everyone — the takeaway
What this means
This result fixes the exact multiplication cost for 2×2 matrices in two standard algebraic models. Doing the calculation s times takes exactly 7s products. Batching separate copies brings no savings in these settings.
Standard computer logic is more flexible. A general program built from XOR and AND gates can generate temporary higher-degree expressions and cancel them out later. The proof here doesn't rule out those shortcuts. The structured problem is solved, but the unrestricted Boolean problem stays open. Future tests will check whether one copy can run in six gates and whether two copies can run in 13.
Attribution and prior art
Prior art: The 7s value is credited to Alder-Strassen and Strassen under bilinear and formal-quadratic models, but this result has not been established for unrestricted Boolean settings.
Register references
- Entry: MF-086.
- Receipt artifacts:
02-direct-sum-tensor/REPORT.md§§7–9;mm2_boolean_mc.py;boolean-mm-sat/;LITERATURE-NOTES.md. - Prior-art works: Alder–Strassen; Strassen.
- Other named work: Boyar–Find.
- Unrestricted Boolean equality: the register does not record this.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 3 of 3 receipt files bundled (20 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.