Research · Papers · Adders, counters and the heap law · MF-100
The exact width-two law for truncated multi-operand addition
MC(A_{k,2}) = ⌊k/2⌋ for every k ≥ 2
Published 2026-08-29
For everyone
Plain summary
When digital circuits add several numbers together in settings like privacy-preserving cryptography, nonlinear multiplications (AND gates) dominate the computational cost. Linear operations like addition modulo 2 (XOR gates) are treated as free. This work determines the exact cost of adding k separate two-bit numbers when discarding everything except the lowest two bits of the sum.
For every integer k at least 2, computing these two lowest bits requires exactly floor(k/2) nonlinear multiplications. This closed form holds only when higher carry bits are discarded; keeping the full sum or exposing intermediate carries changes the function and requires more multiplications. This result independently rediscovers a theorem published by Joan Boyar and René Peralta in 2008, who proved the identical bound for symmetric polynomials.
Result
For every integer k ≥ 2, let A_{k,2}: GF(2)^(2k) → GF(2)^2 denote truncated multi-operand addition taking k independent 2-bit words and returning the low 2 bits of their integer sum. The multiplicative complexity of A_{k,2} over GF(2) satisfies:
MC(A_{k,2}) = ⌊k/2⌋
Setting and definitions
The map A_{k,2} takes inputs (x_{i,1}, x_{i,0}) for i ∈ {1, ..., k} to (y_1, y_0) ∈ GF(2)^2:
y_0 = ∑_{i=1}^k x_{i,0} mod 2 y_1 = (⌊(∑_{i=1}^k (2*x_{i,1} + x_{i,0})) / 2⌋) mod 2
The metric MC(f) measures the minimum number of two-input AND gates required to compute f in a straight-line XOR-AND graph over GF(2), with affine operations and constants provided at zero cost.
The output coordinates decompose over GF(2) into an affine bit y_0 and a quadratic bit y_1:
y_1 = Σ₂ᵏ(x_{1,0}, ..., x_{k,0}) ⊕ ⨁_{i=1}^k x_{i,1}
where Σ₂ᵏ is the degree-2 elementary symmetric Boolean polynomial on k variables, representing the carry generated by the low-order column.
Method
The tight bound MC(A_{k,2}) = ⌊k/2⌋ follows from matching lower and upper bounds:
- Lower bound: A symbolic polar-rank certificate establishes that no straight-line program over GF(2) with fewer than ⌊k/2⌋ AND gates can generate the quadratic form Σ₂ᵏ embedded in y_1.
- Upper bound: A uniform construction partitions the k low-column inputs into pairs, evaluating the quadratic interactions with ⌊k/2⌋ disjoint AND gates and an affine recombining network.
- Verification: Symbolic derivations are documented in
SYNTH-H-LOWERBOUND.md,PROVER-C-CARRYSAVE.md,PROVER-G-WIDTH.md, andSD-RESEARCH-UPDATE-REPORT.md. Concrete rank evaluations and test suites were audited viaprover-c-scratch/width2_rank.out,prover-trunc-scratch/replay-all.json, andprover-g-scratch/bank-checks.json(SHA-256190be83317622915eb6f5f1aacb73d44c40913b6939b8d6d607e0b6bda729e70).
Discussion
The identity MC(A_{k,2}) = ⌊k/2⌋ applies exclusively to modular addition truncated to two output bits. Multi-operand addition retaining the full sum (FullAdd), carry-save representations, and circuits exposing intermediate carry flags (AddCarry) strictly exceed this bound.
Attribution and prior art: As cataloged on 2026-08-30 in PRIOR-ART-S1.md and PRIOR-ART-S7.md, this formula is an exact rediscovery of Theorem 9 (p. 234) in Joan Boyar and René Peralta, "Tight bounds for the multiplicative complexity of symmetric functions," Theoretical Computer Science 396 (2008), 223–246. Boyar and Peralta established MC(Σ₂ᵏ) = ⌊k/2⌋. Because y_0 and the column-one contribution to y_1 are affine over GF(2), A_{k,2} is affine-equivalent to Σ₂ᵏ. While original priority belongs to Boyar and Peralta, the polar-rank derivation and uniform construction provide independent verification.
For everyone — the takeaway
What this means
Adding any number of two-bit numbers requires only one nonlinear multiplication for every two operands, provided we keep only the two lowest bits of the answer. All remaining arithmetic runs through free linear XOR gates.
This settles the exact multiplicative cost for truncated two-bit addition and confirms that the core mathematics aligns with Boyar and Peralta's 2008 symmetric-function bound. Circuit designers targeting secure computation can safely use floor(k/2) multiplications whenever higher overflow bits can be discarded.
Register references
- Entry ID: MF-100
- Curation and Audit Reports:
zkgolf-decomp/reports/SYNTH-H-LOWERBOUND.mdzkgolf-decomp/reports/PROVER-C-CARRYSAVE.mdzkgolf-decomp/reports/PROVER-G-WIDTH.mdzkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.mdzkgolf-decomp/reports/PRIOR-ART-S1.mdzkgolf-decomp/reports/PRIOR-ART-S7.md- Receipt Artifacts:
zkgolf-decomp/prover-g-scratch/bank-checks.json(SHA-256190be83317622915eb6f5f1aacb73d44c40913b6939b8d6d607e0b6bda729e70)prover-c-scratch/width2_rank.outprover-trunc-scratch/replay-all.json- Prior Art:
- Joan Boyar and René Peralta, "Tight bounds for the multiplicative complexity of symmetric functions," Theoretical Computer Science 396 (2008), 223–246.
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 4 of 7 receipt files bundled (35 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-30
- 2026-08-29Published on this site.
- 2026-08-30On 2026-08-30, MF-100 was reattributed as a rediscovery of Theorem 9 from Boyar and Peralta, “Tight bounds for the multiplicative complexity of symmetric functions,” Theoretical Computer Science (2008). The equality MC(A_{k,2})=⌊k/2⌋ and its independent proof remain valid corroboration.