no. 16 · Tuesday 17 November 2026
The multiplicative complexity of the three-bit low-half multiplier
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