Research · Papers · Adders, counters and the heap law · MF-082
Multiplicative complexity of modular addition of up to eight operands
MC(x+y mod 2ⁿ) = n−1 (n ≥ 2); MC(x₁+⋯+x_K mod 2ⁿ) ≤ {2n−3, 3n−4, 4n−7, 5n−8, 6n−10, 7n−11} for K = 3, 4, 5, 6, 7, 8
Published 2026-08-29
For everyone
Plain summary
When adding binary numbers and keeping only the lowest n bits, overflow is discarded. In circuit design, counting AND gates while treating XOR gates as free is standard. A carry-save construction reduces columns of bits before the final addition. This paper gives concrete AND counts for adding two through eight n-bit numbers: n−1 for two operands, rising to 7n−11 for eight. At n = 1, the lowest bit is just an XOR sum, requiring zero ANDs. The formulas are verified symbolically, certified, and checked by exhaustive simulation on small cases. The two-operand count matches a classical exact result. For three or more operands, the formulas set upper-bound benchmarks rather than proved minimums. These K ≥ 3 thresholds were preregistered targets, and the entry makes no novelty claim.
Result
Let x₁, …, x_K be n-bit operands and consider the low n bits of x₁ + ⋯ + x_K mod 2ⁿ. For n ≥ 2, the carry-save construction uses the following number of ANDs:
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, every listed K uses zero ANDs because the low bit is a pure XOR. For K = 2, the construction achieves the exact multiplicative complexity MC(x+y mod 2ⁿ) = n−1. For K ≥ 3, the result provides upper bounds via explicit carry-save circuits.
Setting and definitions
The target is modular addition of K binary words of width n, discarding the carry out of column n−1. Cost is measured in multiplicative complexity (MC), the number of AND gates in a Boolean circuit over {AND, XOR, NOT} where XOR and NOT are free. Carry-save reduction compresses operand bits column by column before final summation.
Method
The script modular_baseline.py generated symbolic formulas for the carry-save tree and output modular_baseline_certificate.json. The register records both receipt artifacts under zkgolf-transfer-studies/08-multiop-addition-audit/.
The formulas were evaluated and validated across K ∈ {2, …, 8} at n ∈ {1,2,3,4,5,6,8,16,32}. Full exhaustive simulation verified (K,n) ∈ {(3,2),(3,3),(4,2),(4,3),(5,2)} with zero failures. The test harness also checked two boundary cases: the classical K = 2 exact count n−1 (Boyar–Peralta–Pochuev) and the full-precision n = 1 sum K − HW(K) (Boyar–Peralta, from MF-076).
Discussion
This entry provides constructive upper bounds for modular multi-operand addition. For K ≥ 3, no matching lower bounds or optimality proofs are asserted. The counts serve as baselines for evaluating alternative designs, such as CCZ-based multi-operand adders.
The K = 2 row matches the exact bound MC(x+y mod 2ⁿ) = n−1. The zero-AND cost at n = 1 applies strictly to the modular low bit; it differs from the full-precision n = 1 expression K − HW(K) validated from MF-076.
For K = 3 and K = 4, the expressions 2n−3 and 3n−4 match the target thresholds listed without constructions in 06_ACTIVE_FRONTIERS Frontier 4. MF-082 supplies concrete carry-save implementations for both and extends the family through K = 8. As noted in the curation record, K = 2 recovers known theory, the K ≥ 3 cases address preregistered targets, and no novelty is claimed. Exhaustive replay certifies the small-parameter instances without establishing multiplicative complexity lower bounds at arbitrary n.
For everyone — the takeaway
What this means
This entry sets the reference AND-gate cost for adding two to eight binary numbers when overflow is dropped. In this cost model, XOR gates are free. Three numbers take 2n−3 ANDs, four take 3n−4, and eight take 7n−11. Two numbers take n−1, which is proven optimal. For three or more numbers, these counts are construction baselines: any new circuit must beat them to show an improvement, though cheaper circuits might exist. If the words are only one bit wide, modular addition needs zero AND gates.
Attribution and prior art
Prior art: The K=2 case reproduces the known classical exact value, while the K>=3 thresholds were preregistered targets. No novelty is claimed for these results.
Register references
Entry: MF-082.
Receipt artifacts: zkgolf-transfer-studies/08-multiop-addition-audit/modular_baseline.py (SHA-256 6e79afb0…8bba); modular_baseline_certificate.json (SHA-256 edd29f8f…babd).
Named prior art: Boyar–Peralta–Pochuev, for the classical exact value MC(x+y mod 2ⁿ) = n−1; Boyar–Peralta, for the full-precision n = 1 value K − HW(K). The register does not record titles for these works.
Named compendium: 06_ACTIVE_FRONTIERS Frontier 4.
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 2 of 2 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-29Published on this site.
- 2026-08-30Superseded (2026-08-30): The filed circuits remain valid upper bounds, but their unrestricted optimality claim is withdrawn. Entries MF-102 and MF-122 state the surviving construction and class theorems, while unrestricted MC=T remains OPEN.