The multiplicative complexity of the three-bit low-half multiplier
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "The multiplicative complexity of the three-bit low-half multiplier".
Jane: Here's the gist of the paper. 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 previously established by SAT searches of the second author An explicit six-AND circuit supplies the upper bound Circuit Complexity and Bounds The paper establishes that the three-bit low-half multiplier has an unrestricted multiplicative complexity MC(M3) = 6 This exact value distinguishes an optimal implementation from a merely small one The lower bound combines derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal An explicit six-AND circuit supplies the upper bound.
Tom: Formal Proof Structure The lower bound follows from a short list of algebraic lemmas about quadratic Boolean functions and exterior forms (Sections 6–10) proved against unrestricted nonlinear reuse A Lean 4 proof of the same theorem uses the case reductions described in Appendix B.
Jane: The kernel-checked proof uses only the axioms propext, Classical.choice and Quot.sound.
Tom: Key Algebraic Tools Several lemmas are introduced to manage the algebraic structure of Boolean functions Lemma 3 provides a normalization technique that preserves the number of linear gates unless the replaced gate is nonlinear, in which case it increases that number by one.
Title and authors: Jane: We've been looking at the paper now, "The multiplicative complexity of the three-bit low-half multiplier," and it starts by introducing what they're trying to measure.
Tom: They immediately state that they are proving the multiplicative complexity of this specific function is six >
Lu: This paper sets up a framework where they study the vectorial Boolean function M3, which is defined by inputs a and b as three-bit integers >
Jane: The actual output for this function is specified by z0 plus two times z1 plus four times z2 equals the integer product of a and b modulo eight >
Tom: It’s about counting the number of two-input AND gates you need, allowing arbitrary affine combinations of inputs and previously computed gates at no cost >
Meng: So it’s not just counting simple ANDs; it accounts for how we can combine things linearly too, which adds a layer of complexity >
Jane: Exactly. The definition says the factors of an AND gate may contain earlier AND outputs, which is what makes this multiplicative complexity interesting >
Tom: That's what they were focusing on—the unrestricted model where linear processing is free when we count the gates themselves >
Lu: They use the unrestricted model of Morse to set up their study on this function because it allows them to see the full scope of nonlinearity in action >
Meng: I wonder if that unrestricted model is realistic for a real chip, or if we have constraints like that in practice >
Jane: That's a good question. The paper says they are using the unrestricted model because it gives them the most general picture of what’s possible mathematically >
Tom: And they found that this specific structure yields exactly six nonlinear operations for this three-bit low-half multiplier >
Lu: It shows that even when you have linear processing for free, there's a fixed number of nonlinear operations required to compute the full output vector >
The paper's summary: Jane: Now, let’s look at what the paper actually says in terms of what they found about this complexity.
Tom: They find that the three-bit low-half multiplier has unrestricted multiplicative complexity MC M3 equals six >
Lu: This exact value is important because it distinguishes an optimal implementation from a merely small one >
Jane: It measures the number of nonlinear operations required even when linear processing is free, and gives us a concrete benchmark for circuit synthesis and lower bound methods >
Meng: So this means if you're designing something, you have to aim for six, not just maybe five or four gates >
Tom: They found this value by combining derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal to establish the lower bound >
Jane: That combination of mathematical tools is what allows them to prove that no smaller circuit can compute this function under these unrestricted reuse conditions >
Lu: And they also made sure the kernel-checked proof uses only the axioms propext, Classical choice, and Quot sound axioms >
Meng: That formalization sounds like they are building a very solid mathematical foundation for this result, which is good for trusting the number six >
Jane: It shows that this isn't just some lucky guess; it’s derived from careful algebraic structure analysis >
The paper's improvements: Tom: They suggest using these algebraic tools to move away from simple enumeration and toward a structural, enumeration-free lower bound proof >
Lu: That means they are aiming for a proof that doesn't have to test every possible circuit structure, which is much more powerful >
Jane: It suggests that the improvements involve using these lemmas about quadratic Boolean functions and exterior forms to manage the algebraic structure of the problem >
Meng: So it’s about getting a method that works regardless of how complex the function gets, as long as we can describe its parts algebraically >
Tom: They want to rule out smaller circuit sizes using obstruction arguments that show no five-AND circuit with five linear gates can compute those outputs z0, z1, and z2 >
Lu: That's a specific way they rule out sizes by showing how the structure of the wires restricts what can be computed in certain gate counts >
Jane: They are essentially using these obstruction arguments to show that smaller circuit sizes simply don't have enough structure to capture the full function >
Conclusion: Tom: So, we’re wrapping up this discussion on "The multiplicative complexity of the three-bit low-half multiplier." The main point is that six is the exact number >
Jane: This result gives us a structural, enumeration-free lower bound proof against unrestricted nonlinear reuse in Boolean XOR and AND circuits >
Lu: It’s fully formalized in Lean four which means we have computational verification of this value now > <ref:2611.15992#pg1,fully formalized in Lean 4>
Meng: For deployment at scale, the explicit six-AND circuit they provide is the upper bound we need to check our hardware against >
Tom: So, to summarize, the multiplicative complexity of M3 is six and it’s a result derived from derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal >
Jane: It really means that we have a structural way to prove this number without having to test every possible circuit structure >
Faculty of Informatics, Eötvös Loránd University · Department of Programming Languages and Compilers, Faculty of Informatics, Eötvös Loránd University
cs.CC, cs.LO, math.CO
Submitted: 2026-11-11
Updated: 2026-11-16
Comments: 21 pages, 1 table. Lean formalization and verification artifacts: https://github.com/bishara74/lowhalf-mul3
Code: https://github.com/bishara74/lowhalf-mul3
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 79/100
The gist: 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…
Key concepts
- Multiplicative Complexity (MC)
- This measures the minimum number of AND gates required to compute a Boolean function. A higher MC means a more complex circuit is needed. The paper establishes that for the three-bit low-half multiplier, this minimum number is exactly six.
- Structural Lower Bound Proof
- This type of proof establishes a lower limit on circuit size based on the algebraic structure of the function itself, rather than searching through possible circuits. It combines advanced algebraic techniques like derivatives and quadratic products to show that any smaller circuit cannot compute the function.
- Obstruction Arguments
- These are logical arguments used to prove that a certain circuit size is impossible. The paper uses these arguments—such as proving no five-AND gate circuit can compute specific outputs—to systematically rule out smaller possible implementations of the multiplier.
Terminology
Summary
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 previously established by SAT searches of the second author An explicit six-AND circuit supplies the upper bound
Circuit Complexity and Bounds
The paper establishes that the three-bit low-half multiplier has an unrestricted multiplicative complexity MC(M3) = 6 This exact value distinguishes an optimal implementation from a merely small one The lower bound combines derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal An explicit six-AND circuit supplies the upper bound. p. 0 The value was previously established by SAT searches
of the second author. An explicit six-AND circuit supplies the upper bound.Where the paper says it
Formal Proof Structure
The lower bound follows from a short list of algebraic lemmas about quadratic Boolean functions and exterior forms (Sections 6–10) proved against unrestricted nonlinear reuse A Lean 4 proof of the same theorem uses the case reductions described in Appendix B. The kernel-checked proof uses only the axioms propext, Classical. p. 0 MC(M3) = 6
is fully formalized in Lean 4. The kernel-checked proof uses only the axioms propext,
Classical. MC(M3) = 6
is fully formalized in Lean 4. The kernel-checked proof uses only the axioms propext,
Classical. The kernel-checked proof uses only the axioms propext,
Classical. choice and Quot. The kernel-checked proof uses only the axioms propext,
Classical. choice and Quot.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Key Algebraic Tools
Several lemmas are introduced to manage the algebraic structure of Boolean functions Lemma 3 provides a normalization technique that preserves the number of linear gates unless the replaced gate is nonlinear, in which case it increases that number by one. Lemma 4 relates the affine factors and quadratic parts of a function to a space Q. p. 2 For any space Q of 2-forms, put
V (Q) = {f : deg f ≤ 2, π2(f) ∈ Q}. If the first j gates have affine factors and their quadratic parts span Q, then
Vj = V (Q). Lean checks the two target splittings by finite computation in lemma3_finite_Z1
and lemma3_finite_Z1P0. Cross-part kernel The kernel of Φ is Λ
2
(U), since Φ records exactly the coefficients involving
a2 or b2.Where the paper says it
Where the paper says it
Exclusion Arguments
The proof utilizes various obstruction arguments to rule out smaller circuit sizes Theorem 8 proves no five-AND circuit with five linear gates computes (z0, z1, z2). The three-linear-gate case is shown to exclude both z2 and z2 + z1 from V4 The final extension forces z1 ∈ V4, and z1 ∈/ V3 now gives g3 ∈ z1 + V3 and V4 ⊆ W.
Computational Verification
The manuscript includes computational verification tests that check local Boolean identities and finite parameter choices used in the written proofs The independent Python checks accompany this revision test the local Boolean identities and finite parameter choices used in the written proofs. The earlier exhaustive searches, independent certificates, and Lean formalization are supporting evidence. p. 1 Morse [1]
supplies the unrestricted multiplication framework, while Soeken [5] develops SAT methods
for determining exact multiplicative complexity. The second author’s earlier SAT searches
established MC(M3) = 6 by ruling out five AND gates.Where the paper says it
References
[1] Gregory Morse. Unrestricted Boolean multiplicative complexity of four-term binary polynomial multiplication: Rational places, Hasse jets, and the failure of nonlinear feedback
[2] Joan Boyar, René Peralta, and Denis Pochuev. On the multiplicative complexity of Boolean functions over the basis (∧, ⊕, 1). p. 1 The carry in z2 makes this
a vectorial problem with a quartic output; the degree bound alone does not yield the exact
answer. Boyar, Peralta, and Pochuev [2] study multiplicative complexity over the Boolean basis
(∧, ⊕, 1), and Boyar and Find [3] treat vector-valued Boolean functions.Where the paper says it
[3] Joan Boyar and Magnus Gausdal Find. p. 1 The carry in z2 makes this
a vectorial problem with a quartic output; the degree bound alone does not yield the exact
answer. Boyar, Peralta, and Pochuev [2] study multiplicative complexity over the Boolean basis
(∧, ⊕, 1), and Boyar and Find [3] treat vector-valued Boolean functions. The carry in z2 makes this
a vectorial problem with a quartic output; the degree bound alone does not yield the exact
answer. Boyar, Peralta, and Pochuev [2] study multiplicative complexity over the Boolean basis
(∧, ⊕, 1), and Boyar and Find [3] treat vector-valued Boolean functions. ORCID: 0000-0002-0231-6557. 1
arXiv:2611.Where the paper says it
Where the paper says it
Where the paper says it
[4] R. Mirwald and C. p. 1 Boyar, Peralta, and Pochuev [2] study multiplicative complexity over the Boolean basis
(∧, ⊕, 1), and Boyar and Find [3] treat vector-valued Boolean functions. Mirwald and Schnorr [4]
show that the multiplicative complexity of a quadratic Boolean form is half the rank of the
alternating matrix obtained by adding its coefficient matrix to its transpose over F2.Where the paper says it
[5] Mathias Soeken. Determining the multiplicative complexity of Boolean functions using SAT, 2020. p. 1 Mirwald and Schnorr [4]
show that the multiplicative complexity of a quadratic Boolean form is half the rank of the
alternating matrix obtained by adding its coefficient matrix to its transpose over F2. Morse [1]
supplies the unrestricted multiplication framework, while Soeken [5] develops SAT methods
for determining exact multiplicative complexity. ORCID: 0000-0002-0231-6557. 1
arXiv:2611.Where the paper says it
Where the paper says it
[6] Accompanying release. Replay files for the low-half multiplier LRAT certificate. p. 0 The multiplicative complexity of the three-bit low-half multiplier
Bshara Alhodali∗ Gregory Morse†
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 previously established by SAT searches
of the second author. ORCID: 0000-0002-0231-6557. 1
arXiv:2611.Where the paper says it
Where the paper says it
[7] Çağdaş Çalık, Meltem Sönmez Turan, and René Peralta. p. 1 Theorem 1 answers Question 2 affirmatively: the lower bound follows from a short list of
algebraic lemmas about quadratic Boolean functions and exterior forms (Sections 6–10), proved
against unrestricted nonlinear reuse, and a Lean 4 proof of the same theorem uses the case
reductions described in Appendix B. Çalık, Turan, and Peralta [7] determine multiplicative
complexity for small Boolean functions. The carry in z2 makes this
a vectorial problem with a quartic output; the degree bound alone does not yield the exact
answer. Boyar, Peralta, and Pochuev [2] study multiplicative complexity over the Boolean basis
(∧, ⊕, 1), and Boyar and Find [3] treat vector-valued Boolean functions.Where the paper says it
Where the paper says it
[8] Palomar Registry. PALOMAR-2026-11-09-000020. p. 0 15992v1 [cs. CC] 11 Nov 2026 15992v1 [cs. CC] 11 Nov 2026Where the paper says it
Where the paper says it
[9] The paper is 2611. p. 0 ORCID: 0000-0002-0231-6557. 1
arXiv:2611. ORCID: 0000-0002-0231-6557. 1
arXiv:2611.Where the paper says it
Where the paper says it
[10] The paper is 2611.15992>
[33] One signal. For f, h ∈ V (Q) and g = fh, put W = V (S) + ⟨g⟩. p. 2 The
number of linear gates increases by one if the replaced gate was nonlinear, and is preserved
otherwise. For any space Q of 2-forms, put
V (Q) = {f : deg f ≤ 2, π2(f) ∈ Q}.Where the paper says it
[34] No normalized five-AND circuit with exactly one linear gate computes (z0, z1, z2)
[35] Cubic first-gate normal form. Every product g1 of two factors in V1, at least one of them nonaffine, has a representative g1 ≡ (P0 + A)B (mod V1), with A, B homogeneous linear functions
[36] Quadratic first gate. If deg g1 ≤ 2 and g1 + (P0 + l)b ∈ V1 for homogeneous l, b, then V1 + ⟨g1⟩ ⊆ V (⟨P0, l ∧ b⟩)
[37] The first nonlinear gate places no remaining output. For every g1 = fh, f, h ∈ V1, none of z1, z2, z1 + z2 belongs to V2 = V1 + ⟨g1⟩
[38] Early feedback. Let c = (P0 + l)b with b /∈ ⟨a0, b0⟩. p. 1 1 Introduction
Let a = a0 + 2a1 + 4a2 and b = b0 + 2b1 + 4b2 be three-bit integers. We study the vectorial
Boolean function M3(a, b) = (z0, z1, z2) specified by ab mod 8 = z0 + 2z1 + 4z2.Where the paper says it
[39] Early z1 forces a core cubic signal. Suppose g1 is cubic and z1 ∈ V2 + ⟨fh⟩ for f, h ∈ V2, then g1 is core supported
[40] Noncore intermediate-space obstruction. Let c = (P0 + l)b be noncore with l, b homogeneous and b /∈ ⟨a0, b0⟩. p. 3 When a 2-form occurs in a Boolean expression, it denotes its homogeneous quadratic ANF
representative. Likewise the carry function a0a1b0b1 is occasionally denoted by Ω in Boolean
identities; exterior products use the corresponding 4-form. On B = j, write βj (X, Y ) =
P
u:B(u)=j X(u)Y (u) and put yi = xi + ziZ1. These functions belong to the restriction of
T = Aff(U) + ⟨P0⟩. The
number of linear gates increases by one if the replaced gate was nonlinear, and is preserved
otherwise. For any space Q of 2-forms, put
V (Q) = {f : deg f ≤ 2, π2(f) ∈ Q}.Where the paper says it
Where the paper says it
Where the paper says it
[41] The paper is 2611.15992>
[48] The relaxed four-gate circuit computes (z1, q2) on the 48 points a0b0 = 0
[49] The paper is 2611.15992>
[50] The paper is 2611.15992>
[53] The paper is 2611.15992>
Conclusion
The multiplicative complexity of the three-bit low-half multiplier is six This result provides a structural, enumeration-free lower-bound proof valid against unrestricted nonlinear reuse in Boolean XOR–AND circuits The authors prove MC(M3) = 6 is fully formalized in Lean 4. This value is established by a lower bound combining derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal. p. 0 An explicit six-AND circuit supplies the upper bound. The lower
bound combines derivatives, quadratic products, complementary minors, and extraction
modulo a Boolean ideal. The value was previously established by SAT searches
of the second author. An explicit six-AND circuit supplies the upper bound.Where the paper says it
Where the paper says it
Pruning redundant reasoning tokens
The paper proves that the three-bit low-half multiplier has unrestricted multiplicative complexity MC(M3) = 6 This exact value distinguishes an optimal implementation from a merely small one The lower bound combines derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal. An explicit six-AND circuit supplies the upper bound.
How the training signal is built
The lower bound follows from a short list of algebraic lemmas about quadratic Boolean functions and exterior forms (Sections 6–10) proved against unrestricted nonlinear reuse A Lean 4 proof of the same theorem uses the case reductions described in Appendix B. The kernel-checked proof uses only the axioms propext, Classical.choice and Quot.sound.
Where the gains come from
The proof utilizes various obstruction arguments to rule out smaller circuit sizes Theorem 8 proves no five-AND circuit with five linear gates computes (z0, z1, z2). The three-linear-gate case is shown to exclude both z2 and z2 + z1 from V4 The final extension forces z1 ∈ V4, and z1 ∈/ V3 now gives g3 ∈ z1 + V3 and V4 ⊆ W. This excludes the final placement of z2. p. 4 Degree excludes λ = 5. For λ = 4 a good external direction excludes the final product.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Structural Lower Bound Proofs: Implement a system that can derive structural, enumeration-free lower-bound proofs for multiplicative complexity by combining derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal as described in Section 4.
-
Formal Verification of Complexity Bounds: Develop a Lean 4 proof engine capable of verifying the exact multiplicative complexity of functions like M3(a, b) against an explicit upper bound circuit using only axioms propext, Classical choice and Quot sound, as formalized in Section B.
-
Circuit Synthesis Benchmarking: Create a synthesis tool that can generate an explicit six-AND circuit to establish the upper bound for MC(M3), allowing direct comparison with proposed implementations and lower-bound methods.
-
Automated Search Space Reduction: Build an automated search mechanism that utilizes coset obstruction, multiplier rigidity, and extraction modulo the low-bit ideal to rule out smaller circuit sizes (e.g., five AND gates) without relying on brute-force SAT solving, as motivated by Question 2 in Section 1.
-
Vectorial Function Analysis: Enhance the system to analyze vector-valued Boolean functions by tracking their algebraic normal forms over F2[x]/(x 2i - xi), allowing for the classification of functions based on their degree and rank-two generation properties, as detailed in Preliminaries and Lemma 4.
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 previously established by SAT searches of 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. MC(M 3)=6 is fully formalized in Lean 4. The kernel-checked proof uses only the axioms propext, Classical.choice and Quot.sound.
Sources
- Multiplicative Complexity of Vector Valued Boolean Functions
- Determining the Multiplicative Complexity of Boolean Functions using SAT
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?