Research · Papers · Adders, counters and the heap law · MF-109
Is the projected-heap upper bound always exact?
CONJECTURE: MC(A_{k,n}) = T(k,n); the first sharp stable fork is A_{9,3} ∈ {9,10}
Published 2026-08-29
For everyone
Plain summary
Multiplicative complexity counts the AND gates needed to compute a function when XOR gates are free. When adding multiple binary numbers and truncating the result to a fixed width, a circuit design called a projected heap gives an upper bound on the multiplications required, written T(k,n) for k inputs of n bits.
Whether this upper bound is always exact remains an open conjecture: MC(A_{k,n}) = T(k,n). The smallest test case that could disprove it is finding a six-multiplication circuit for A_(6,3). The first stable open choice is deciding whether A_(9,3) needs 9 or 10 multiplications.
This entry reframes the problem from the broader carry-save focus in ML-048 directly to the projected heap. No priority or novelty claim is made, and no formal prior-art sweep has run.
Result
CONJECTURE: MC(A_{k,n}) = T(k,n)
The cheapest candidate falsifier seeks six products for A_(6,3). The first sharp stable fork asks whether A_{9,3} ∈ {9,10}.
Status: OPEN. Unrestricted projected-heap equality remains undecided. Evidence tier is OPEN, with full reproduction (FR) established only for the upper-bound construction side.
Setting and definitions
Cost model: GF(2) XAG (XOR-free multiplicative complexity).
- A_{k,n}: truncated addition of k operands of n bits each over GF(2).
- MC(f): multiplicative complexity of a Boolean function f over GF(2).
- T(k,n): multiplicative complexity upper bound achieved by the projected-heap construction.
- N/E: non-evidence resulting from incomplete searches or solver timeouts.
Method
Upper bounds are certified by explicit constructions, including receipt AX162 in zkgolf-decomp/prover-trunc-scratch/replay-all.json (SHA-256 8954064fee25c5585ec53f190d73b9bfd9a72ab4e76ef40d8eeabc30a8573aec).
Lower bounds were evaluated via SAT:
- A restricted fixed-seed subclass evaluated in prover-trunc-scratch/seeded-core-k6-p6.result.json and prover-trunc-scratch/seeded-core-early-q-k6-p6.result.json returned UNSAT for six products on A_(6,3).
- Unrestricted search spaces timed out or terminated incompletely (N/E). Because no quotient-promotion theorem lifts fixed-seed UNSAT certificates to the unrestricted domain, unrestricted lower bounds remain unproven.
Discussion
This entry replaces the broad carry-save optimality framing in ML-048, targeting the projected heap rather than superseded fold families.
Evidence tier remains OPEN, with FR limited to the upper-bound constructions. No priority or novelty claim is asserted; a formal prior-art sweep has not run.
The fixed-seed UNSAT certificate proves only that no six-product implementation exists within that specific template. It does not establish MC(A_{6,3}) ≥ 7 unrestricted. Resolving unrestricted A_(6,3) and determining whether MC(A_{9,3}) is 9 or 10 remain the concrete targets for deciding the conjecture.
For everyone — the takeaway
What this means
Adding several numbers and keeping only the low bits is a standard operation in cryptography and digital arithmetic. Current circuit designs set a clear ceiling on how many multiplications this takes, but we do not know if those designs are the absolute best possible.
This conjecture sets the exact boundary. If someone finds a six-multiplication circuit for adding six 3-bit numbers, or a nine-multiplication circuit for adding nine 3-bit numbers, the ceiling drops and the conjecture fails. If no such circuits exist, the projected heap is optimal.
Register references
- Entry: MF-109
- Supersedes framing in: ML-048
- Reports:
- zkgolf-decomp/reports/SYNTH-L-TRUNCADD.md
- zkgolf-decomp/reports/STATE-OF-PROGRAM.md
- zkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.md
- EXACT-ATLAS.md
- PROVER-TRUNC-SHARE.md
- Receipt artifacts:
- prover-trunc-scratch/seeded-core-k6-p6.result.json
- prover-trunc-scratch/seeded-core-early-q-k6-p6.result.json
- zkgolf-decomp/prover-trunc-scratch/replay-all.json (SHA-256 8954064fee25c5585ec53f190d73b9bfd9a72ab4e76ef40d8eeabc30a8573aec)
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 3 of 4 receipt files bundled (32 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.