Research · Papers · Adders, counters and the heap law · MF-002
An upper bound on the multiplicative complexity of a three-column interior adder tile
MC(g) ≤ 9
Published 2026-08-29
For everyone
Plain summary
MF-002 verifies an explicit boolean circuit for a three-column interior adder tile. The construction uses nine nonlinear products (multiplications of two binary terms) to implement the tile interface. In comparison, the 2026 STACS MDFA adder generator produces a circuit with twelve nonlinear gates for the same interface. Because nonlinear multiplications dominate cost in zero-knowledge proofs and secure multi-party computation, cutting three products is a practical gain.
This is an upper bound: nine products work, but fewer might too. Comparing against its twelve gates evaluates that specific tool, not the general state of the art. The nine-product circuit remains verified, with the MDFA generator as its explicit baseline.
Result
Let g denote the three-column interior adder tile with its stated interface. The register establishes an explicit realization with nine nonlinear products:
MC(g) ≤ 9.
For the same interface, the 2026 STACS MDFA generator evaluated via cirbo outputs twelve nonlinear gates. The result provides an upper bound and a direct comparison against MDFA; it contains no optimality claim MC(g) = 9 and no lower-bound certificate ruling out an eight-product realization.
Setting and definitions
The tile interface specifies fixed binary inputs and outputs. An r-product realization is an XOR-AND circuit over GF(2) with r nonlinear AND gates and affine output reconstructions. The quantity MC(g) denotes multiplicative complexity; the present entry supplies only an upper bound.
The twelve-gate figure is the reported nonlinear gate count produced by the cited 2026 STACS MDFA generator for this interface, serving strictly as a comparison benchmark.
Method
The nine-product circuit was verified for functional equivalence against the tile specification using cirbo. Its nonlinear gate count was compared directly to the twelve-gate circuit synthesized by the 2026 STACS MDFA generator for the same interface.
The register records a verified construction and comparison. It records no SAT-based lower-bound search, no UNSAT refutation at eight products, and no claim of exact multiplicative complexity.
Discussion
The audit in MF-077 leaves the upper bound MC(g) ≤ 9 intact, as MF-002 asserted only constructive existence.
MF-077 clarified the external baseline. The Cirbo/STACS-2026 MDFA generator minimizes total binary gate count rather than nonlinear depth or product count. Standard carry-save adder arrays match the three-product-per-column density across arbitrary widths. Consequently, the nine-product circuit improves upon that specific MDFA synthesis output, but does not advance the general multiplicative complexity frontier for multi-operand addition.
The result holds strictly for the verified three-column interior tile interface. Status remains CAVEAT: the comparison applies solely to the 2026 STACS MDFA/cirbo artifact without asserting broader prior-art superiority or circuit minimality.
For everyone — the takeaway
What this means
We know nine binary multiplications are enough to build this specific adder tile. That offers an immediately usable building block for zero-knowledge proofs and secure computing, where multiplications drive performance costs.
Nine is just an upper ceiling; an eight-product circuit might still exist. The comparison is also specific: twelve gates is what a particular tool produced because it was trying to minimize all logic gates, not just multiplications. The result delivers a verified, cheaper circuit while staying clear about its exact baseline.
Attribution and prior art
Prior art: While the 2026 STACS MDFA/cirbo generator is used as the comparison point at twelve reported nonlinear gates, entry MF-077 clarifies that it does not represent the state-of-the-art baseline for AND count.
Register references
- MF-002; receipt: HANDOFF §2.6.
- MF-077; receipt:
zkgolf-transfer-studies/04-andcount-optimization/REPORT.md§1–3. - Prior art/comparison: the cited 2026 STACS MDFA/cirbo generator, reported at twelve nonlinear gates for the same interface.
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 0 of 0 receipt files bundled (1 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-27The nine-product tile construction in MF-002 remains valid and unaffected by the audit in MF-094, since optimality was never claimed. Its external comparison was separately corrected in MF-077.
- 2026-08-29Published on this site.