Paperlane

no. 16 · Tuesday 17 November 2026

The multiplicative complexity of the three-bit low-half multiplier

Bshara Alhodali and Gregory Morse

math.CO · v2 · □ lean · 21 pp

Abstract

We prove that the multiplicative complexity of the three-bit low-half multiplier is six, giving a structural, enumeration-free lower-bound proof valid against unrestricted nonlinear reuse in Boolean XOR-AND circuits. The value was first established by SAT searches of the first author and independently confirmed by the second author. An explicit six-AND circuit supplies the upper bound. The lower bound combines derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal. Independent finite checks accompany the arguments. $\mathrm{MC}(M_3)=6$ is fully formalized in Lean 4, using only Lean's three standard axioms (propositional extensionality, choice and quotient soundness).

comments
21 pages, 1 table. The Lean 4 formalization and verification artifacts are linked in the paper (Appendix A)
fields
Combinatorics
pdf ↗ page arXiv:2611.15992 ↗