Research · Papers · Adders, counters and the heap law · MF-095
Exact multiplicative complexity of small modular additions
For modular addition of K n-bit operands in acyclic-XAG, MC(2,3)=2, MC(2,4)=3, MC(2,5)=4, MC(3,3)=3, MC(4,2)=2
Published 2026-08-29
For everyone
Plain summary
MF-095 establishes exact product counts for five small modular additions. Multiplicative complexity measures the number of AND-like multiplication steps needed when XOR gates and linear output combinations are free. We evaluated two operands of 3, 4, and 5 bits, three 3-bit operands, and four 2-bit operands in feed-forward circuits. The exact counts are 2, 3, 4, 3, and 2. Each value matches the standard carry-save baseline. An automated search produced working circuits at these counts, proved no smaller circuit exists, and verified every working circuit across all possible inputs. The two-operand counts match the classical Boyar–Peralta–Pochuev theorem, confirming the search harness. The three- and four-operand counts provide the first exact values in this register for K ≥ 3. These five data points support the carry-save optimality conjecture without resolving it or its asymptotic behavior.
Result
Consider modular addition of K n-bit operands in the acyclic-XAG model used by the register: each product is the product of two affine factors over {1, inputs, earlier products}, and each output is an affine readout. The exact multiplicative complexities are:
| K | n | baseline (MF-082) | exact MC | certificate |
|---|---|---|---|---|
| 2 | 3 | n−1 = 2 | 2 | p=2 SAT, p=1 UNSAT |
| 2 | 4 | n−1 = 3 | 3 | p=3 SAT, p=2 UNSAT |
| 2 | 5 | n−1 = 4 | 4 | p=4 SAT by construction, p=3 UNSAT |
| 3 | 3 | 2n−3 = 3 | 3 | p=3 SAT, p=2 UNSAT |
| 4 | 2 | 3n−4 = 2 | 2 | p=2 SAT, p=1 UNSAT |
Here p is the candidate product count. In every row, the recorded MC equals the listed carry-save baseline.
Setting and definitions
Let K be the operand count and n the bit width. Multiplicative complexity (MC) is the minimum number of non-linear products in an acyclic XAG over GF(2). An affine factor is a linear combination over {1, inputs, earlier products}. Each primary output is an affine readout over all available signals. SAT denotes synthesis of a valid circuit at product budget p; UNSAT denotes an unsatisfiability certificate proving no circuit exists at p.
Method
Circuits were synthesized via exact CEGIS over acyclic XAGs with full-domain truth-table evaluation. Because the encoder omitted symmetry breaking, UNSAT certificates on constrained sub-tables remain sound over the complete domain, avoiding the MF-018 caveat. Every SAT assignment underwent full-domain replay verification. The K=2, n=5 upper bound is certified by explicit construction rather than SAT search.
The implementation and execution logs are available in this paper's downloadable evidence pack.
Discussion
The three K=2 cases rederive the Boyar–Peralta–Pochuev theorem MC(x+y mod 2ⁿ) = n−1, serving as harness validation. The K=3 and K=4 cases provide the register's first exact values for multi-operand addition (K ≥ 3). No evaluated instance beats the carry-save baseline.
These five instances provide limited empirical support for the ML-048 conjecture that carry-save multiplication counts are optimal. They do not prove the conjecture, nor do they constrain asymptotic behavior. No corrections are registered for MF-095.
For everyone — the takeaway
What this means
We know the exact number of multiplications needed to add these five small groups of numbers without feedback loops. In every case, standard carry-save addition turns out to be unbeatable. The two-operand tests prove our search tools work on known math. The three- and four-operand tests give new exact baselines where we previously only had upper bounds. These checks cover only small bit widths; whether carry-save remains optimal for larger additions is still unknown.
Attribution and prior art
Prior art: The K=2 values rederive the classical result by Boyar, Peralta, and Pochuev. For K=3 and K=4, these are the first exact values calculated within this project, with no broader novelty claim.
Register references
- MF-095
- Receipt directory: zkgolf-transfer-studies/08-multiop-addition-audit/
- Receipt artifacts: exact_mc_cegis.py, sweep_results.json, sweep2_results.json, sweep.log, sweep2.log
- Prior art: Boyar–Peralta–Pochuev, MC(x+y mod 2ⁿ) = n−1. The register does not record a full bibliographic citation.
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 5 of 5 receipt files bundled (5 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-30Corrected on 2026-08-30: while the five finite exact cells stand, they do not establish general carry-save tightness. MC(A_{5,3})=5 is recorded at MF-110, MC(A_{4,4}) remains [6,8], the projected heap remains a valid upper bound, and unrestricted equality remains open.