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

arXiv:2611.15992 · cs.CC, cs.LO, math.CO · Submitted 2026-11-11 · Read on arXiv

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

Where the paper says it

The value was previously established by SAT searches of the second author. An explicit six-AND circuit supplies the upper bound.

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

Where the paper says it

MC(M3) = 6 is fully formalized in Lean 4. The kernel-checked proof uses only the axioms propext, Classical.

p. 0
Where the paper says it

MC(M3) = 6 is fully formalized in Lean 4. The kernel-checked proof uses only the axioms propext, Classical.

choice and Quot. p. 0
Where the paper says it

The kernel-checked proof uses only the axioms propext, Classical. choice and Quot.

p. 0
Where the paper says it

The kernel-checked proof uses only the axioms propext, Classical. choice and Quot.

sound.

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

Where the paper says it

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).

The cross-part kernel analysis shows that the kernel of Φ is Λ2(U), since Φ records exactly the coefficients involving a2 or b2. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

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

Where the paper says it

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.

Theoretical Computer Science, 235(1):43–57, 2000. DOI.

[3] Joan Boyar and Magnus Gausdal Find. p. 1

Where the paper says it

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.

Multiplicative complexity of vector valued Boolean functions. p. 1
Where the paper says it

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.

Theoretical Computer Science, 720:36–46, 2018. DOI. Preprint: arXiv:1407. p. 0
Where the paper says it

ORCID: 0000-0002-0231-6557. 1 arXiv:2611.

6169>

[4] R. Mirwald and C. p. 1

Where the paper says it

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.

P. Schnorr. The multiplicative complexity of quadratic Boolean forms

[5] Mathias Soeken. Determining the multiplicative complexity of Boolean functions using SAT, 2020. p. 1

Where the paper says it

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.

arXiv:2005. p. 0
Where the paper says it

ORCID: 0000-0002-0231-6557. 1 arXiv:2611.

01778v1>

[6] Accompanying release. Replay files for the low-half multiplier LRAT certificate. p. 0

Where the paper says it

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.

GitHub, tag lowhalf-arxiv-v2, 2026. p. 0
Where the paper says it

ORCID: 0000-0002-0231-6557. 1 arXiv:2611.

Commit 3770baefb67b5afe1715e22283aa9aed606d096b.

[7] Çağdaş Çalık, Meltem Sönmez Turan, and René Peralta. p. 1

Where the paper says it

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 multiplicative complexity of 6-variable Boolean functions. p. 1
Where the paper says it

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.

Cryptography and Communications, 11(1):93–107, 2019. Published online in 2018. DOI.

[8] Palomar Registry. PALOMAR-2026-11-09-000020. p. 0

Where the paper says it

15992v1 [cs. CC] 11 Nov 2026

Registration v1, 2026. p. 0
Where the paper says it

15992v1 [cs. CC] 11 Nov 2026

Verified commit b6c00ef8d94ff578585b428270df1af271a96bd6.

[9] The paper is 2611. p. 0

Where the paper says it

ORCID: 0000-0002-0231-6557. 1 arXiv:2611.

p. 0
Where the paper says it

ORCID: 0000-0002-0231-6557. 1 arXiv:2611.

15992>

[10] The paper is 2611.15992>

[33] One signal. For f, h ∈ V (Q) and g = fh, put W = V (S) + ⟨g⟩. p. 2

Where the paper says it

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}.

Then z2 ∈/ W, and no product of two elements of W belongs to z2 + W

[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

Where the paper says it

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.

For k, F ∈ V1, one has k(c + F) + z1 ∈/ V1

[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

Where the paper says it

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.

Put B = Aff + ⟨P0, c⟩, A = B + ⟨Z1⟩, and g = fh a product with f, h ∈ B. p. 9
Where the paper says it

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⟩.

Put W = A + ⟨g⟩. p. 2
Where the paper says it

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}.

Then z2 ∈/ W, and F H + z2 ∈/ W for all F, H ∈ W

[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

Where the paper says it

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 explicit upper bound is provided by an explicit six-AND circuit. p. 0
Where the paper says it

The value was previously established by SAT searches of the second author. An explicit six-AND circuit supplies the upper bound.

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

Where the paper says it

Degree excludes λ = 5. For λ = 4 a good external direction excludes the final product.

The paper is 2611.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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

Related papers