Research · Papers · Adders, counters and the heap law · MF-107
Counterexamples to four former addition laws
FullAdd (K−1)n, greedy truncated equality, U(k,n) tightness, and CS-base for k ≥ 9 are refuted
Published 2026-08-29
For everyone
Plain summary
When measuring circuit efficiency, multiplicative complexity counts how many AND gates a calculation needs, treating XOR gates as free. Earlier working notes in this project proposed four general formulas to describe the exact cost of adding multiple numbers and reducing bit-heaps. This entry refutes all four formulas by providing concrete circuit designs that beat the proposed costs or break the hypothesized equalities. Specifically, the universal (K-1)n FullAdd formula, the greedy truncated-heap equality, the tightness of the U(k,n) family, and the CS-base claim for every k ≥ 9 are all false. The older designs still serve as valid upper bounds on cost, but they are not exact minimums or universal laws. This entry serves as an internal correction ledger; no external priority is claimed.
Result
Concrete counterexamples refute four conjectures regarding addition and bit-heap multiplicative complexity:
- Universal FullAdd rule: The exact cost of multi-operand addition does not obey MC = (K-1)n for all input configurations.
- Greedy truncated-heap equality: Truncated addition heaps do not strictly satisfy the equality predicted by greedy column reduction.
- Tightness of U(k,n): The parameterized upper-bound family U(k,n) is not a tight complexity frontier for multi-operand addition.
- CS-base rule for k ≥ 9: The carry-save base reduction claim fails for every k ≥ 9.
The previously asserted circuit constructions remain valid upper bounds on MC, but all associated claims of exact equality, tightness, or minimality are false.
Setting and definitions
Synthesis operates over the standard Boolean basis (AND, XOR, NOT) under the XOR-free multiplicative complexity metric over GF(2), denoted MC(f). Circuit structures evaluated include:
- Multi-operand addition circuits reducing K operands of bit-width n.
- Truncated bit-heaps omitting high- or low-order bits according to fixed masks.
- The parameterized candidate upper-bound family U(k,n).
- Carry-save base reduction strategies (CS-base) across column depths k.
Method
Counterexamples were synthesized using exact SAT encodings and validated via automated replay runners.
Refutations and verification artifacts are logged across several project records:
- The universal FullAdd rule (K-1)n and U(k,n) tightness refutations are documented in STATE-OF-PROGRAM.md section 2 and SYNTH-I-FAMILIES.md, with replayed circuits in prover-afr-scratch/focal-replay-final.json.
- The greedy truncated-heap equality refutation is documented in SYNTH-L-TRUNCADD.md, with verified instances in prover-trunc-scratch/replay-all.json.
- The CS-base rule refutation for k ≥ 9 is documented in PROVER-ICC-DIRECTSUM.md and SD-RESEARCH-UPDATE-REPORT.md. The counterexample circuit receipt is stored in prover-icc-scratch/bitheap-k9-base-refutation.json (SHA-256 hash 6388f5b09a444868373e9afb3fa7e79d6bebd3096903a91cbae3893ad70ef9db) and confirmed by independent replay in prover-icc-scratch/bitheap-k9-independent-replay.json (SHA-256 hash 9b29f01f3f8c9047ddb43a84bc2c8239009f8e75ace541c8fa21bcf7c32da9ff).
Evidence tier: FC + FR (finite-checked and focal replay).
Discussion
These counterexamples show that greedy column reductions and naive carry-save baselines fail to capture minimal multiplicative complexity in multi-operand addition. Non-greedy bit-heap reduction patterns exploit cross-column linear dependencies in GF(2) to bypass single-column AND-count barriers.
Scope and caveats:
- Constructions from the original heuristics remain valid upper bounds on MC.
- Claims asserting these bounds as exact lower bounds, tight frontiers, or universal equalities are formally withdrawn.
- This entry acts purely as an internal ledger correction; no external novelty or priority is asserted.
For everyone — the takeaway
What this means
Simple formulas often try to predict the minimum number of multiplication steps needed to add several numbers together. This entry shows that four previous formulas overestimated those minimums. By building specific, working circuits that beat the old predictions, we show that multi-number addition can be done with fewer steps than previously thought. The old circuit designs still work, but they do not set the absolute limit on efficiency.
Register references
- Entry: MF-107
- Reports:
- STATE-OF-PROGRAM.md (Section 2)
- SYNTH-I-FAMILIES.md
- SYNTH-L-TRUNCADD.md
- PROVER-ICC-DIRECTSUM.md
- SD-RESEARCH-UPDATE-REPORT.md
- Receipt artifacts:
- prover-afr-scratch/focal-replay-final.json
- prover-trunc-scratch/replay-all.json
- prover-icc-scratch/bitheap-k9-base-refutation.json (SHA-256 6388f5b09a444868373e9afb3fa7e79d6bebd3096903a91cbae3893ad70ef9db)
- prover-icc-scratch/bitheap-k9-independent-replay.json (SHA-256 9b29f01f3f8c9047ddb43a84bc2c8239009f8e75ace541c8fa21bcf7c32da9ff)
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 5 of 7 receipt files bundled (48 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.