Research · Papers · Adders, counters and the heap law · MF-182
Unification of Additive Line Multiplicative Complexity via Greedy Column-Heap Recursion
Heap recursion d_0=k+c0, d_{i+1}=k+⌈(d_i-1)/2⌉ with cost Σ⌈(d_i-1)/2⌉ matches all exact MC values for multi-operand addition and H_n.
Published 2026-09-04
For everyone
Plain summary
Adding binary numbers is fundamental to cryptography and zero-knowledge proof systems. In these systems, XOR additions are free, while AND multiplications determine the circuit cost. Minimizing the total number of AND operations—multiplicative complexity—is essential for performance.
Previously, exact AND counts for different addition layouts appeared as isolated empirical numbers with irregular offsets. A single greedy column-heap recursion—matching classical carry-save or Dadda dot reduction—reproduces every known exact multiplicative-complexity value across multi-operand addition lines without exception. While carry-save dot reduction is standard in hardware arithmetic, showing that its operation counts match all known minimum-AND circuit complexities is new.
Result
Let a column of d dots of weight 1 be reduced to a single sum dot using full adders and half adders. The reduction requires h(d) = ⌈(d−1)/2⌉ AND gates and emits h(d) carry dots to the next column.
For k words with c0 carry-in dots, the column heap depth evolves as: d_0 = k + c0 d_{i+1} = k + h(d_i)
The total multiplicative complexity is: Cost = Σ h(d_i) summed over all bit columns whose carries are needed. The highest required column is free, and kept top digits cost one half adder per resolved pair.
This recursion reproduces all known exact multiplicative complexities and boundary constants:
- Multi-word addition over 32-bit words:
- Specific standard multi-operand additions:
T(k,32) = (k−1)·32 − c_k where c_k = (k−1) + Σ ((k−1) − h(d_i)) gives the ramp deficits. The recursion yields c_k = 1, 3, 4, 7, 10 for k = 2, 3, 4, 5, 7, exactly matching benchmark certificates, and predicts c_6 = 8, yielding T(6,32) = 152.
- Add32 = 31
- Add32x3 = 61
- Add32x3Canon33 = 62
- Structured multi-operand families:
- J_m = 2m − 2 (exact for m ≤ 4)
- K_m = 2m + 1 (for all m)
- Single-column addition:
- Boyar–Peralta symmetric counting functions: MC(H_n) = n − HW(n) for n = 4..15, where HW(n) denotes the Hamming weight of n.
Setting and definitions
Circuits are evaluated over GF(2) under the standard XOR-and-inverter-free (XAG) metric MC(f), where XOR and NOT gates cost zero and AND gates cost one.
In a k-word addition, bit column i receives k primary operand bits alongside carry dots from column i−1. A carry-save step reduces d dots at column i using full adders (3 dots in, 1 sum dot and 1 carry dot out, cost 1 AND) and half adders (2 dots in, 1 sum dot and 1 carry dot out, cost 1 AND). Reducing d dots to 1 requires h(d) = ⌈(d−1)/2⌉ adders and produces h(d) carries.
The ramp deficit of column i with incoming depth d_i is (k−1) − h(d_i), measuring the difference between the steady-state carry rate (k−1) and the actual carry count during transient columns.
Method
The heap recurrence was verified programmatically against the known exact multiplicative-complexity corpus:
- The exact circuit catalog in ZKGOLF-EXACT-ATLAS.
- The dynamic programming dot-price table in fivecent_dotprice.py.
- The synthesis scripts and verification tables in SYNTHESIS-2026-09-03.md §1 (with duplicate box copy in zkgolf-decomp/SYNTHESIS-2026-09-03.md).
For each target function, the step-by-step carry generation profile and terminal half-adder resolution costs were checked against verified minimum-AND certificates.
Discussion
The column-heap reduction formula matches classical Dadda and carry-save dot reduction from digital hardware. Its exact agreement with every verified multiplicative-complexity value across multi-operand addition families—including boundary constants and transient ramp deficits—unifies the additive line under a single structural recurrence.
This result does not prove that greedy dot reduction achieves global optimality for arbitrary word lengths or operand counts k; global optimality across all XAG topologies remains an open conjecture (MF-183).
For everyone — the takeaway
What this means
Circuit designers working on zero-knowledge arithmetic previously had to benchmark multi-word additions individually to find their minimum multiplication counts, dealing with bespoke boundary corrections for each configuration.
All known minimum AND counts for addition chains follow one simple carry-save rule. Engineers can compute exact circuit costs directly with a basic formula rather than running brute-force searches.
Attribution and prior art
Prior art: While the recursion is based on standard carry-save and Dadda dot reduction, the observation that it matches every exact XAG value, including the boundary constants, appears to be new.
Register references
- Register Entry: MF-182
- Related Entries: MF-181 (derivation of K_m = 2m+1), MF-183 (optimality conjectures of greedy heap reduction)
- Verification Receipt: SYNTHESIS-2026-09-03.md §1 (and box copy zkgolf-decomp/SYNTHESIS-2026-09-03.md)
- Software and Catalogs: ZKGOLF-EXACT-ATLAS, fivecent_dotprice.py
- Prior Art: Boyar–Peralta exact bounds for MC(H_n) = n − HW(n) (n = 4..15); classical Dadda / carry-save dot-reduction techniques
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 (9 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.