Research · Papers · Adders, counters and the heap law · ML-048
Bounds on the multiplicative complexity of multi-operand addition
MC(x₁+…+x_K) ≤ (K−1)·n with equality for every n ≥ 1 when K is a power of two
Published 2026-08-29
For everyone
Plain summary
Multiplicative complexity (MC) counts the nonlinear operations (AND gates) in a circuit when XOR gates are free. Full precision means keeping every carry bit.
Adding K unsigned n-bit integers with a standard carry-save tree uses (K−1)·n AND gates, matching the exact cost whenever K is a power of two. For K ≥ 3, no lower bound matches this count, leaving (K−1)·n as a conjecture. At n = 1, Boyar–Peralta established the exact cost as K − HW(K), where HW(K) is the Hamming weight of K. For four full-precision operands, the proven range is n+1 ≤ MC ≤ 3n. This differs from modular addition: for four 4-bit operands modulo 16, the gap is specifically 7 versus 8 products.
Result
Let x₁,…,x_K be unsigned n-bit integers. In the XOR-free/AND-charged model, carry-save addition achieves
MC(x₁+…+x_K) ≤ (K−1)·n
asymptotically, holding with equality for every n ≥ 1 when K is a power of two. The bound is constructively verified for K ∈ {2,3,4,5,6,7,8,16} and n ∈ {1,2,4,8,16,32}. For n = 1, the exact cost is K − HW(K).
No matching lower bound exists for general K ≥ 3. For K = 4, the full-precision complexity satisfies
n+1 ≤ MC ≤ 3n.
For modular addition returning the low n bits (n ≥ 2), carry-save reduction gives:
K | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| ANDs | n−1 | 2n−3 | 3n−4 | 4n−7 | 5n−8 | 6n−10 | 7n−11 |
At n = 1, modular addition requires 0 ANDs. For K = 4 at n = 4, the modular baseline is 3·4−4 = 8 ANDs, leaving a concrete discriminator gap of 7 versus 8 products.
Setting and definitions
Full-precision addition outputs the complete sum of x₁+…+x_K, preserving all carry bits. Modular addition computes the sum modulo 2ⁿ, discarding the carry out of column n−1. MC denotes multiplicative complexity over GF(2). HW(K) denotes the Hamming weight of K.
The carry-save construction applies full adders greedily to each column until two operand rows remain, then completes the sum with a ripple-carry adder. Each full adder consumes one AND via
MAJ(a,b,c)=((a⊕c)(b⊕c))⊕c.
Method
- Full precision was evaluated across
K ∈ {2,3,4,5,6,7,8,16}andn ∈ {1,2,4,8,16,32}via symbolic counting and exhaustive replay forK = 4,n ≤ 3with zero discrepancies, reproducing the Boyar–Peralta formula atn = 1. - Modular baselines were computed by truncating top carries across
n ∈ {1,2,3,4,5,6,8,16,32}, replaying(K,n) ∈ {(3,2),(3,3),(4,2),(4,3),(5,2)}with zero failures, and recoveringMC(x+y mod 2ⁿ)=n−1atK = 2.
Lower bounds rely on affine-rank and forced-value arguments, which yield only n + ⌈log₂K⌉ − 1 (giving n+1 ≤ MC ≤ 3n at K = 4). The rank-plus-degree bound provides no improvement because the minimum degree across nonzero output components is 2. Counting total full and half adders implies an architectural floor of (K−1)n − ⌈log₂K⌉, but this structural count is not a valid circuit lower bound and fails at n = 1.
Discussion
The problem remains OPEN because carry-save networks furnish only an upper bound; their optimality for K ≥ 3 is unproved. Known exact baselines—Boyar–Peralta at n = 1 and Boyar–Peralta–Pochuev for modular K = 2—confirm the accounting but do not close the multi-operand gap.
The full-precision gap for K = 4 spans n+1 ≤ MC ≤ 3n. By contrast, the 7-versus-8 product comparison applies strictly to modular addition at width n = 4 (3·4−4 = 8).
The smallest unresolved test of the full-precision conjecture is exact SAT synthesis for K = 4, n = 2 at p = 5 (where carry-save uses 6 products). Resolving that case would test the smallest non-trivial instance without settling the general asymptotic bound.
For everyone — the takeaway
What this means
K is the count of numbers being added, and n is their bit width. Carry-save addition merges columns of bits in parallel before running one final addition step.
This construction guarantees that adding K integers takes at most (K−1)·n nonlinear steps. For single-bit inputs, the exact formula is settled. For wider numbers with K ≥ 3, no one has proved that a clever circuit cannot beat carry-save addition. For four 4-bit numbers added modulo 16, testing whether a circuit needs 7 or 8 products is the most immediate open benchmark.
Attribution and prior art
Prior art: The exact value for n=1 was established by Boyar-Peralta. General optimality for K>=3 remains an open conjecture, and this record provides no new lower-bound techniques.
Register references
- ML-048
- MF-076
zkgolf-transfer-studies/08-multiop-addition-audit/multiop_addition_audit.py(SHA-256bc4f4305…143d)multiop_addition_audit_certificate.json(SHA-25626fabd01…59b6)AUDIT.md, §Consequences- MF-082
zkgolf-transfer-studies/08-multiop-addition-audit/modular_baseline.py(SHA-2566e79afb0…8bba)modular_baseline_certificate.json(SHA-256edd29f8f…babd)- Boyar–Peralta
- Boyar–Peralta–Pochuev
- General
K ≥ 3optimality prior art: 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 1 of 1 receipt files bundled (4 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-30
- 2026-08-27While ML-048 established `n+1 ≤ MC ≤ 3n` for four-operand full-precision addition, the modular bound is tighter at `3n−4` (MF-082). Against the competing `2w−1` hypothesis, the remaining open question narrows to a difference of just one product at `w = 4` (7 vs 8).
- 2026-08-29Published on this site.
- 2026-08-30Updated 2026-08-30 (correcting ML-048): the former A_{4,4} 7-versus-8 framing and broad carry-save optimality claims are withdrawn. We retain 6 ≤ MC(A_{4,4}) ≤ 8, exact MC(A_{5,3}) = 5, and the projected-heap upper bound, while unrestricted MC = T remains open.