Adders, counters and the heap law

What this programme is about

Arithmetic circuits in zero-knowledge cryptography and secure computation treat addition and XOR operations as free, while non-linear multiplications—AND gates—drive the cost in proof size and execution time. This programme asks the minimal number of AND gates needed to add multiple binary words, run parallel counters, and resolve carry bits over GF(2).

Outside circuit complexity, a result here buys concrete lower bounds and optimal blueprints for cryptographic hardware and proof systems. Hash functions like SHA-256 and BLAKE3 spend most of their algebraic budgets on multi-operand addition and carry propagation. Knowing the exact multiplicative complexity of an adder or compressor slice tells protocol engineers when an implementation hits the mathematical floor of the model. That prevents wasted engineering cycles on impossible circuit optimizations and secures verifiable computations against overhead bloat.

What has been settled

For full-precision addition, MF-099 settles the exact digit-sum law MC(FullAdd(K,n)) = Kn − s₂(K(2ⁿ−1)), disproving the former universal (K−1)n conjecture with an explicit six-product circuit for FullAdd(5,2); a prior-art sweep hasn't run. Truncated addition of k two-bit words costs exactly MC(A_{k,2}) = ⌊k/2⌋ MF-100. For four operands, MF-077 and ML-047 prove a three-product cell achieves 3n ANDs, matching the standard carry-save baseline MF-076; an earlier 25% improvement claim was corrected because the cited Cirbo/STACS generator targeted total gate count. MF-107 retracted four earlier addition rules when explicit replayed circuits refuted universal FullAdd costs, greedy truncated equality, U(k,n) tightness, and carry-save baselines for k ≥ 9. Greedy column-heap recursion unifies these additive lines, matching every verified exact value MF-182.

For carry chains, MF-181 proves the resolved-carry family has exact complexity MC(K_m) = 2m+1, an apparently new family result compared to Boyar–Peralta's redundant counter. The injected-carry family J_m has exact values MC(J_2)=2, MC(J_3)=4, and MC(J_4)=6 MF-111. MF-103 reduces three-operand addition's one-gate gap to injected carry via MC(J_m) = MC(A_{3,m+1}) − 1. Two length-L ripple chains sharing an operand cost exactly 2L MF-023. The two-column C7 carry transducer costs exactly 6 ANDs MF-138.

Parallel counters and compressors hit exact bounds over F_2, including MC(3->2)=1, MC(4->3)=3, MC(5:2)=3, and MC(6:2)=4 MF-179, while cascaded compressor slices satisfy MC(k:2) = k - 2 ML-087. MF-169 closes Boyar–Peralta's bracket for seven-variable majority at 4 ANDs. Restriction of Boolean functions preserves complexity through MC(f) - MC(f|_R) = k_R + e_R under a 1-Lipschitz potential [MF-114, ML-056]. Constant addition exhibits shear symmetry MC(F_{n,K}) = MC(F_{n,K+2^{n-2}}) MF-118, though MF-140 notes this small-width freeness fails to lift to 32-bit words.

What is still open

Several core complexity cells remain open within verified brackets. For three operands, MF-101 leaves all-width equality between 2n-4 and 2n-3 open, with the flagship instance J₃₂ pinned at {61,62} MF-103. The injected-carry cell J_5 sits within [7,8] against a synthesis solver wall ML-054, leaving the resolution tax τ_4 in {1,2} ML-089. Truncated four-operand addition at width 4 sits in [6,8] MF-110, while SAT solvers verified an 8-product witness and leave p=7 open ML-049. Strict width-nine cost E_9 remains bracketed between 18 and 36 [MF-117, ML-059]. Across broader families, MF-109 conjectures exactness for the projected-heap bound MC(A_{k,n}) = T(k,n), where the first stable fork A_{9,3} ∈ {9,10} and the candidate falsifier A_{6,3} remain unresolved, and MF-183 leaves the discard-tax principle as an unproved conjecture.

How to read the evidence

This programme relies on receipted circuit artifacts and exhaustive checks, backed by paper proofs and certified machine reductions. Settled upper bounds carry explicit circuit witnesses replayed over all input combinations, making them reproducible and verifiable. Lower bounds depend on algebraic rank arguments and certified restriction proofs. When an entry lacks a retained certificate or relies on an unverified baseline. Treat settled upper bounds as verified code and lower bounds as audited mathematics.