Research · Papers · Adders, counters and the heap law · MF-101
The universal one-gate bracket for three-operand addition
2n−4 ≤ MC(A_{3,n}) ≤ 2n−3; the upper is exact at n = 2,3,4,5 and for prefix-causal circuits
Published 2026-08-29
For everyone
Plain summary
Adding three n-bit numbers requires a certain number of non-linear logic gates (multiplications or AND gates). In hardware and zero-knowledge proofs, linear operations like XOR are essentially free, so multiplicative operations set the total cost. For any bit width n ≥ 2, adding three n-bit numbers takes at least 2n-4 non-linear gates and never more than 2n-3.
The upper bound of 2n-3 is exact for small widths (n = 2, 3, 4, and 5) and for all circuits that process bits strictly right-to-left (prefix-causal circuits). Whether unrestricted circuits can reach the lower floor of 2n-4 at larger widths remains open. This entry makes no priority or novelty claims, and no fresh prior-art sweep was run on this composite result.
Result
For modular addition of three n-bit operands, denoted A_{3,n}, the multiplicative complexity MC(A_{3,n}) over GF(2) satisfies:
2n-4 ≤ MC(A_{3,n}) ≤ 2n-3 for all n ≥ 2.
The upper bound 2n-3 is exact for widths n ∈ {2, 3, 4, 5}, and holds tightly across all n ≥ 2 for prefix-causal circuits. Unrestricted all-width equality MC(A_{3,n}) = 2n-3 remains unproven and open.
Setting and definitions
The target function is truncated three-operand addition A_{3,n}: ({0,1}^n)^3 → {0,1}^n, mapping (x, y, z) to (x + y + z) mod 2^n. The complexity measure MC(f) is the multiplicative complexity over GF(2): the minimum number of two-input AND gates needed to evaluate f in a straight-line XOR-AND graph (XAG) with unrestricted fan-out and free linear gates (XOR and NOT).
A circuit is prefix-causal if every output bit at index i depends only on intermediate multiplicative outputs evaluated at or below index i.
Method
The lower bound 2n-4 is derived symbolically by eliminating linear gate combinations and tracking dependency rank under non-linear dimension reductions.
The upper bound 2n-3 is constructed directly using standard adder networks.
For n ∈ {2, 3, 4, 5}, exact lower and upper equality is verified by exhaustive search and complete certificate replay over the state space of minimal XAGs. The certificates rule out any unrestricted circuit of cost 2n-4 at these widths.
The verification corpus includes:
- SYNTH-H-LOWERBOUND.md
- PROVER-A-Q1.md
- PROVER-D-ELIM.md
- zkgolf-decomp/reports/SYNTH-H-LOWERBOUND.md
- zkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.md
- zkgolf-decomp/prover-b-scratch/extremal_game.receipt.txt (SHA-256 450a39bd1ba1f39d41b131832474c43f676c180499d53096bcffa567484897a2)
- zkgolf-decomp/prover-b-scratch/measure_profiles.receipt.txt (SHA-256 06383d485de07a30698ed720943303bbc174789a9c7b9bf6205afbed778a8c1f)
- zkgolf-decomp/prover-e-scratch/k3n4-exact-receipt.json (SHA-256 582f152bd9bde2dc2b0dc5b2418dd5528f665b15752aaca380d8e620f35c6709)
- synth-n-scratch/recompute_capstone.receipt.json
Discussion
The register record establishes a one-gate bracket separating the general lower floor 2n-4 from the upper construction 2n-3.
Four conditions bound this record:
- Exactness at n = 2, 3, 4, 5 does not constitute an inductive proof for all n.
- Prefix-causal exactness at 2n-3 does not automatically transfer to unrestricted circuits, where non-causal feedback or lookahead might save an AND gate at larger widths.
- The lower bound 2n-4 is the sharpest confirmed all-width lower boundary for three-operand modular addition in the register.
- No claims of external priority or novelty are asserted; a composite prior-art sweep has not been run.
For everyone — the takeaway
What this means
Adding three numbers is a standard building block in arithmetic circuits and zero-knowledge proofs. This result traps the expensive non-linear cost within a single gate for every bit width.
For 2, 3, 4, and 5 bits, the exact minimum is settled at 2n-3 gates. For larger inputs, the true cost lies strictly between 2n-4 and 2n-3. Unless a circuit uses non-causal lookahead, it requires exactly 2n-3 gates.
Register references
- Register Entry: MF-101
- zkgolf-decomp/reports/SYNTH-H-LOWERBOUND.md
- zkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.md
- SYNTH-H-LOWERBOUND.md
- PROVER-A-Q1.md
- PROVER-D-ELIM.md
- zkgolf-decomp/prover-b-scratch/extremal_game.receipt.txt (SHA-256 450a39bd1ba1f39d41b131832474c43f676c180499d53096bcffa567484897a2)
- zkgolf-decomp/prover-b-scratch/measure_profiles.receipt.txt (SHA-256 06383d485de07a30698ed720943303bbc174789a9c7b9bf6205afbed778a8c1f)
- zkgolf-decomp/prover-e-scratch/k3n4-exact-receipt.json (SHA-256 582f152bd9bde2dc2b0dc5b2418dd5528f665b15752aaca380d8e620f35c6709)
- synth-n-scratch/recompute_capstone.receipt.json
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 5 receipt files bundled (18 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.