Research · Papers · Adders, counters and the heap law · MF-099
The exact digit-sum law for full K-operand addition
MC(FullAdd(K,n)) = Kn − s₂(K(2ⁿ−1)); FullAdd(5,2) = 6 ≠ 8
Published 2026-08-29
For everyone
Plain summary
Full addition keeps every nonconstant bit of an ordinary integer sum, including all final carries. When XOR gates and constants are free and binary AND gates cost one, adding K unsigned n-bit words takes exactly Kn−s₂(K(2ⁿ−1)) AND gates. Here s₂ counts the 1 bits in an integer. An algebraic degree argument proves the lower bound, and a weighted bit-heap construction meets it. A clean-room checker verified the width-two endpoint products. For five two-bit inputs, the exact cost is 6 ANDs, verified across all 1,024 inputs. This disproves the earlier universal conjecture (K−1)n, which predicted 8. The old formula remains a valid upper bound and is exact in its proper digit-sum regime. No priority or novelty claim is made, and no prior-art sweep has run on this theorem.
Result
For all integers K,n ≥ 1, let
M=K(2ⁿ−1).
Then
MC(FullAdd(K,n))=Kn−s₂(M)=Kn−s₂(K(2ⁿ−1)).
Here FullAdd(K,n) outputs every nonconstant bit of the integer sum of K independent n-bit words. In particular,
MC(FullAdd(5,2))=6,
whereas (K−1)n predicts 8. At width one, the law specializes to MC(FullAdd(K,1))=K−s₂(K).
The certificate lower bound and matching bit-heap construction are general symbolic proofs; finite checks confirm decisive instances.
Setting and definitions
The circuit model is the acyclic 2-XAG over GF(2) with free affine operations and unit-cost two-input AND gates. Let y_j denote the output bit of weight 2^j in the sum. The function s₂(t) is the binary digit sum of the nonnegative integer t.
The maximum sum is M=K(2ⁿ−1). Let h=s₂(M), and select the output positions where the binary expansion of M has a 1.
The bit-heap construction groups wires into columns by binary weight. If column j receives q_j wires, one-AND half and full adders reduce them to parity bit b_j and g_j=floor(q_j/2) carries passed to column j+1.
Method
The lower bound evaluates the product of the h selected output bits. This product evaluates to 1 if and only if the sum equals its maximum value M, which requires all Kn inputs to be 1:
product_(j:M_j=1) y_j = product_(a=1)^K product_(b=0)^(n−1) x_(a,b).
The right side has algebraic degree Kn. A FullAdd circuit with p AND gates can compute the product of its h selected outputs using h−1 additional ANDs. Because a scalar function built with p+h−1 ANDs has algebraic degree at most p+h,
p ≥ Kn−h=Kn−s₂(M).
The weighted bit heap attains this bound. In column j, with a_j=K for source columns and zero elsewhere, the wire recurrence is
q_j=a_j+g_(j−1)=b_j+2g_j.
By construction, b_j is the j-th binary digit of M. Summing across all columns yields
sum_j g_j=Kn−sum_j b_j=Kn−s₂(M).
Because each carry reduction counted by g_j costs one AND, the construction meets the lower bound.
Independent clean-room checks confirm the degree-8 product for FullAdd(4,2) and degree-10 product for FullAdd(5,2). The six-gate heap for FullAdd(5,2) is recorded in prover-afr-scratch/fulladd-5-2-bitheap.json and verified on all 1,024 inputs in prover-afr-scratch/focal-replay-final.json with zero mismatches.
Discussion
MF-099 combines the endpoint-product lower bound from PROVER-AFP-CARRY.md with the bit-heap upper bound from PROVER-AFR-CONSTRUCT.md. The bounds match for all K,n ≥ 1, settling the exact multiplicative complexity of full addition without requiring optimal circuits to preserve bit-column structure.
The theorem refutes the universal claim MC=(K−1)n. That formula remains a valid upper bound and is exact whenever s₂(K(2ⁿ−1))=n, including all cases with K≤2ⁿ. For some cells beyond that regime, the bit heap shares work across columns. The instance FullAdd(5,2)=6 is the minimal counterexample: the old formula predicts 8, but both the lower bound and the replayed circuit yield 6.
Full addition is distinct from truncated addition. Truncating high bits removes the maximum-sum endpoint product and invalidates this degree argument. Consequently, this result does not prove the projected-heap conjecture for truncated sums or justify porting plain adders into fixed-constant, carry-in, residue, or ordered identity-C record blocks.
No priority, novelty, or world-first claim is made. A prior-art sweep has not run on this composed theorem.
For everyone — the takeaway
What this means
The exact cost depends on the binary representation of the maximum possible sum, not just input count and word length. Every 1 bit in that endpoint saves one nonlinear gate in the bit heap. Because the same endpoint provides the degree lower bound, no circuit in this model can do better. For five two-bit words, this drops the true cost from the predicted 8 to 6, verified across all 1,024 inputs. This formula applies only to full addition; truncated sums and specialized adder blocks require separate proofs.
Register references
- MF-099.
SYNTH-I-FAMILIES.md.PROVER-AFP-CARRY.md.PROVER-AFR-CONSTRUCT.md.prover-afr-scratch/fulladd-5-2-bitheap.json.prover-afr-scratch/focal-replay-final.json.synth-n-scratch/recompute_capstone.receipt.json.- Prior-art position: no priority sweep has run on this theorem, and no priority claim is made.
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 5 receipt files bundled (20 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.