Research · Papers · Adders, counters and the heap law · MF-110
Correcting two truncated-addition cells
MC(A_{5,3}) = 5; MC(A_{4,4}) ∈ [6,8], not exact 8 on retained evidence
Published 2026-08-29
For everyone
Plain summary
This audit corrects the recorded costs of two basic arithmetic operations used in zero-knowledge proof circuits. Truncated addition sums binary numbers and drops any overflow carries past a target bit-width. The cost metric is multiplicative complexity: the smallest number of multiplication gates needed to build the circuit when additions are free.
For adding four 4-bit numbers, earlier reports claimed an exact cost of 8 multiplications. An inspection showed no proof certificate in custody for that lower bound. The cost for adding four 4-bit numbers is corrected to an open range of 6 to 8 multiplications, and the exact-8 claim is retracted until a full certificate is produced.
Result
For truncated addition over GF(2) under standard XOR-free multiplicative complexity MC:
- MC(A_(5,3)) = 5, verified by full certificate and replay verification (tier FC + FR).
- MC(A_(4,4)) ∈ [6, 8], verified by an explicit upper bound and proved floor (tier VUB + PF).
The equality MC(A_(4,4)) = 8 is unproven on retained evidence. This finding supersedes the 7-versus-8 gap in ML-048 and removes unsupported exact-8 assertions from the active catalog.
Setting and definitions
Let A_(k,w): (GF(2)^w)^k -> GF(2)^w denote multi-operand truncated addition mapping k operands of bit-width w to their integer sum modulo 2^w. The multiplicative complexity MC(f) of a multi-output Boolean function f over GF(2) is the minimum number of binary AND gates in an XOR-AND graph (XAG) computing f.
Evidence tiers:
- FC + FR: Full certificate of unsatisfiability at target cost p - 1 together with an explicit witness replay at cost p.
- VUB + PF: Verified upper bound via an explicit circuit witness replay alongside an algebraic or structural proved floor.
Method
MC(A_(5,3)) = 5 combines:
- A decisive p = 4 unsatisfiability certificate recorded by SHA-256 digest 1816e37e911e3ee363e0b6eb5fc2ae60b655d4298d1c4db3d587d923c88d560f in PROVER-ICC-DIRECTSUM.md.
- A 5-gate witness replay executed across factory/runs/mc53-witness-bank/RESULT.json and witness-replay.json, accompanied by flow bank receipt prover-e-scratch/flow-bank-receipt.json (SHA-256 7e52026341cb319fd75a18ee1138d22a5babd38b753d4bee32ce5103417d1e72).
For A_(4,4), degree-product constraints in prover-c-scratch/degree_product_bound.out set a lower floor of 6, while an 8-gate synthesis witness provides the replayed upper bound p = 8. No archived certificate rules out cost 6 or cost 7.
Discussion
This finding serves strictly as an internal evidence audit and consistency correction, making no external priority or mathematical novelty claims.
Two custody and reporting points arise:
- For A_(5,3), the p = 4 unsatisfiability hash 1816e37e911e3ee363e0b6eb5fc2ae60b655d4298d1c4db3d587d923c88d560f is verified, but PROVER-ICC-DIRECTSUM.md omits the filesystem path to the raw certificate file. The result is retained with this custody caveat documented.
- Older synthesis reports labeled MC(A_(4,4)) as exactly 8 without deposited certificates ruling out 6 and 7. Those labels recorded informal synthesis ceilings rather than proved minima. MF-110 supersedes ML-048 and restricts the catalog entry for A_(4,4) to the conservative bracket [6, 8].
For everyone — the takeaway
What this means
Circuit optimization benchmarks require concrete proof records. When a system asserts that a circuit cannot run with fewer multiplication gates, it must keep the mathematical proof on file. It also demotes four-operand 4-bit addition from an unproven cost of 8 down to an open range of 6 to 8.
Register references
- Register Entry: MF-110
- Prior Art / Superseded Records: ML-048
- Reports:
- zkgolf-decomp/reports/STATE-OF-PROGRAM.md
- zkgolf-decomp/reports/PROVER-ICC-DIRECTSUM.md
- zkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.md
- EXACT-ATLAS.md
- Receipts and Artifacts:
- factory/runs/mc53-witness-bank/RESULT.json
- factory/runs/mc53-witness-bank/units/witness-replay.json
- zkgolf-decomp/prover-e-scratch/flow-bank-receipt.json (SHA-256 7e52026341cb319fd75a18ee1138d22a5babd38b753d4bee32ce5103417d1e72)
- prover-c-scratch/degree_product_bound.out
- Decisive p = 4 certificate digest: SHA-256 1816e37e911e3ee363e0b6eb5fc2ae60b655d4298d1c4db3d587d923c88d560f (unprinted receipt pathname in PROVER-ICC-DIRECTSUM.md)
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 4 of 6 receipt files bundled (28 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.