Research · Papers · Adders, counters and the heap law · MF-181
Exact multiplicative complexity of the resolved-carry family K_m
MC(K_m) = 2m+1 for every m ≥ 1
Published 2026-09-04
For everyone
Plain summary
When digital circuits add numbers, exclusive-OR operations (addition modulo 2) are essentially free, while AND gates carry high computational costs in zero-knowledge proofs and secure cryptographic protocols. Multiplicative complexity measures the absolute minimum number of AND gates needed to evaluate a function.
This paper establishes the exact multiplicative complexity for an infinite family of four-operand additions, denoted K_m. The operation takes a single carry bit and three m-bit binary words, producing the m lowest sum bits alongside both resolved top carry bits. We prove that computing K_m requires exactly 2m+1 AND gates for any word length m ≥ 1. The result matches an explicit circuit construction against a lower bound derived from algebraic polynomial degrees. While prior work by Boyar and Peralta analyzed redundant carry representations, this exact determination for the fully resolved carry family is new.
Result
For every integer m ≥ 1, the multiplicative complexity of the resolved-carry function K_m over GF(2) is:
MC(K_m) = 2m+1
The function K_m accepts one carry bit t and three m-bit binary words X = (x_0, ..., x_{m-1}), Y = (y_0, ..., y_{m-1}), and Z = (z_0, ..., z_{m-1}). It outputs the m low sum bits of the integer sum V = t + X + Y + Z together with both resolved high carry bits ρ_m (bit m of V) and ν_m (bit m+1 of V).
Setting and definitions
Let GF(2) denote the two-element field with addition (XOR, denoted +) and multiplication (AND, denoted · or juxtaposition). The multiplicative complexity MC(f) of a multi-output Boolean function f is the minimum number of 2-input AND gates in any straight-line program over the basis (XOR, AND, NOT) over GF(2) computing f, with XOR and NOT gates free.
An XOR-AND graph over GF(2) is denoted XAG. By the standard 2-XAG degree theorem, an XAG with p multiplicative gates computes functions whose algebraic normal form (ANF) polynomial degree is at most p+1.
Let V be the integer sum:
V = t + ∑_{j=0}^{m-1} (x_j + y_j + z_j) 2^j
The output of K_m is the vector of m+2 bits (s_0, s_1, ..., s_{m-1}, ρ_m, ν_m) representing V in binary:
V = ∑_{j=0}^{m-1} s_j 2^j + ρ_m 2^m + ν_m 2^{m+1}
The related family J_m outputs only the m low sum bits (s_0, ..., s_{m-1}), while J_{m+1} corresponds to (J_m, ρ_m) up to affine readout. The resolution tax is τ_m := MC(K_m) − MC(J_{m+1}).
Method
The equality MC(K_m) = 2m+1 holds uniformly in m by matching upper and lower bounds:
- Upper bound (MC(K_m) ≤ 2m+1):
A column-heap construction of full adders (FA) and half adders (HA), each costing one AND gate, realizes K_m with gate count:
2 + 2(m−2) + 2 + 1 = 2m+1 AND gates
Column 0 uses two initial adders (2 ANDs). Columns 1 through m−2 process intermediate carries using 2 ANDs each. The final boundary stages consume 2 and 1 ANDs. Truth-table replay verified the construction on all 2^{3m+1} input rows for m ∈ {1, 2, 3, 4, 5} with zero mismatches, evaluated by council4/k_family_cleanroom.py against the output of council4/k_family_heap.py.
- Lower bound (MC(K_m) ≥ 2m+1):
Consider the monomial:
M = t · x_0 · y_0 · z_0 · ∏_{j=1}^{m-1} (x_j · y_j)
The degree of M is 1 + 3 + 2(m−1) = 2m+2. On the subcube where variables outside the support of M are set to 0, V attains its maximum value 1 + 3 + 2(m−1) = 2m+2. Across this subcube, V ≤ 2^{m+1}, with V = 2^{m+1} holding if and only if all variables in the support of M equal 1. Thus the top carry bit ν_m equals 1 on this subcube precisely at the all-ones point, making the ANF coefficient of M in ν_m equal to 1.
By the 2-XAG degree theorem, computing any Boolean function containing a monomial of degree 2m+2 requires at least (2m+2) − 1 = 2m+1 AND gates, so MC(K_m) ≥ 2m+1. Explicit Möbius inversion confirmed the non-zero ANF coefficient of M for m = 1, 2, 3, 4, 5.
Discussion
Matching bounds settle MC(K_m) = 2m+1 for all m ≥ 1. This result bears several structural consequences:
- Resolution Tax and the Flagship Family J_m:
The tax τ_m := MC(K_m) − MC(J_{m+1}) lies in {1, 2}. The conjecture MC(J_m) = 2m−2 is equivalent to τ_m = 1 for all m. For small dimensions, τ_1 = τ_2 = τ_3 = 1 are exact (resolving J_2, J_3, and J_4), while τ_4 ∈ {1, 2} corresponds to the open bracket MC(J_5) ∈ {7, 8}.
- Degree Tightness:
The degree lower bound is tight on the resolved object K_m, but falls one short on the redundant carry object J_{m+1}. The missing gate in the lower bound for J_m therefore cannot be detected by degree constraints alone; the obstruction resides in non-degree algebra, consistent with the scalar two-corrections lemma (SCALAR-FLAGSHIP-NOTES-2026-09-02).
- Exact Synthesis Degree Filtering:
The uniform degree bound serves as a pre-solver filter: any exact synthesis instance whose specification contains an output of degree ≥ p+2 is provably UNSAT at budget p without solver encoding. For instance, testing K_3 at p=6 returned UNSAT in zero solver seconds.
Prior art notes: Boyar and Peralta studied gate counts for redundant carry representations. Exact multiplicative complexity for the fully resolved family K_m as a closed-form family theorem is not present in prior literature and is categorized as APPARENTLY-NEW.
For everyone — the takeaway
What this means
Adding several binary numbers creates carry bits that ripple into higher columns. In cryptography and circuit synthesis, knowing the minimum number of nonlinear operations required to resolve these carries removes empirical guesswork.
Because the resolved-carry family K_m requires exactly 2m+1 multiplications for any word size m, standard full-adder heap designs are provably optimal: no circuit shortcut can eliminate a single AND gate when every carry bit is fully unpacked. The proof also shows why degree-based bounds work directly on fully unpacked outputs, but require deeper algebraic techniques when carries remain combined.
Attribution and prior art
Prior art: This result appears to be new as a general family statement: while Boyar–Peralta counted the redundant object, the exact count for the resolved object is not found in the known literature.
Register references
- Register Entry: MF-181
- Proof note: zkgolf-sha256/K-FAMILY-NOTE-2026-09-03.md
- Supporting note: SCALAR-FLAGSHIP-NOTES-2026-09-02
- Heap implementation: council4/k_family_heap.py
- Clean-room verification: council4/k_family_cleanroom.py
- Artifact box: record-scratch/council4_fivecent/K{1..5}_heap.json
- Execution log: RECORD-COUNCIL4-FIVECENT.log (entries "K_m HEAP REPLAY" and "CLEAN-ROOM PASS")
- Prior art reference: Boyar–Peralta (redundant object counting)
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 (7 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.