Exact multiplicative complexity of carry-calculus and threshold functions

Result

Let MC(f) denote the multiplicative complexity of a Boolean function f over GF(2). Let Th(K, n, t) denote the threshold function taking K operands of bit-width n with threshold t, evaluating to 1 if and only if the sum of the integer values of the K operands meets or exceeds t.

1. Exact values of MC(f) are computed for 59 distinct threshold, truncated-threshold, and carry functions with multi-bit operands (n >= 2), with 39 further multi-bit cells bracketed between tight lower and upper bounds.
2. For K = 5, n = 2, the relation MC(Th(5, 2, t)) = 9 - v_2(t) holds for 14 out of 15 values of t in 1..15 \ {8}, where v_2(t) is the 2-adic valuation of t. This pattern fails at K = 4, n = 2 and does not generalize across all K.
3. For the Hamming-weight bridge defect function D(m) over m inputs with bit-width b = floor(log2 m) + 1:

D(m) = floor(log2 m) - 1 for m != 2^b - 1 D(m) = floor(log2 m) for m = 2^b - 1 Equality holds exactly for 2 <= m <= 15. The lower bound D(m) >= floor(log2 m) - 1 holds for all m >= 2: every don't-care code in the bridge specification sets bit b - 1, ensuring that the degree-(b - 1) algebraic normal form (ANF) coefficient is invariant under any completion, which forces MC >= b - 2.

4. The exact multiplicative complexity of all 504 symmetric Boolean functions on m variables is confirmed for m = 2..7, satisfying MCmax(S_m) = m - 1 for m = 1..7.

Setting and definitions

Let B = {0, 1}. A Boolean function f: B^N -> B is represented in algebraic normal form (ANF) over GF(2). The multiplicative complexity MC(f) is the minimum number of two-input AND gates required to evaluate f in an XOR-AND graph (XAG) with zero-cost XOR and NOT gates.

Let S_m denote the class of symmetric Boolean functions on m inputs, whose outputs depend solely on the Hamming weight |x| of the input vector x in B^m. Define MCmax(S_m) = max { MC(f) : f in S_m }.

For threshold functions, Th(K, n, t) maps K integers x_1, ..., x_K in {0, ..., 2^n - 1} to B by testing whether the sum of x_i for i = 1..K is at least t. When n = 1, these reduce to symmetric threshold functions on K variables. When n >= 2, inputs are multi-bit binary words.

The Hamming-weight bridge maps m input bits to their base-2 Hamming weight in b = floor(log2 m) + 1 bits, using don't-care states for unreachable integer weights. The defect D(m) measures the gate overhead that this bridge encoding introduces relative to direct ANF degree lower bounds.

Method

Upper bounds derive from explicit gate lists synthesized and verified by exhaustive replay across the full 2^N input domain using mc_engine.py, solver.py, carry/threshold_final.py, symmetric_exact.py, and bridge_full.py.

Lower bounds combine algebraic derivations and SAT refutations:

1. Exact ANF degree and affine restriction arguments.
2. Walsh spectral analysis and restriction-to-4-variables lower bound certificates.
3. Complete SAT refutations of smaller candidate circuits via solver.py.
4. General algebraic proof for the bridge defect law: because all don't-care assignments in the bridge retain top bit b - 1, the degree-(b - 1) monomial coefficient in the ANF is invariant across all completions. Standard degree bounds therefore force MC >= b - 2 = floor(log2 m) - 1 for all m.

Verification artifacts are recorded in out/thresholds_final.json, out/weight_bridge.json, and out/symmetric_exact.json.

Discussion

The 59 exact multi-bit carry and threshold cells (n >= 2) provide the first cataloged complexity values beyond the single-bit case n = 1.

The symmetric function values on m = 2..7 inputs and the bound MCmax(S_m) = m - 1 for m = 1..7 confirm results by BCSTP, who proved MCmax(S_n) = n - 1 for all n <= 21 and n = 23. Lemma 13 of Boyar and Peralta (2008) yielded only MC <= 8 at m = 7.

The 2-adic valuation regularity MC(Th(5, 2, t)) = 9 - v_2(t) holds for 14 of 15 non-trivial thresholds at K = 5, n = 2. It fails at K = 4, n = 2, confirming it is not a general carry-calculus law.

The closed-form bridge formula D(m) = floor(log2 m) - [m != 2^b - 1] proves the lower bound for all m and matches exact values for m = 2..15. BCSTP Sections 4.1–4.2 previously tabulated empirical slack under three encodings without a closed form. This defect bound constrains the bridge construction itself rather than target functions directly, as the Hamming-weight bridge is lossy (for example, at m = 4).

Attribution and prior art

Prior art: The symmetric cases and maximum MC bound are from BCSTP, correcting an earlier attribution to Boyar–Peralta (2008). The multi-bit carry cells and closed D(m) bridge formula are new to this work.

Register references

• Entry ID: MF-171
• Receipt artifacts: carry/threshold_final.py, out/thresholds_final.json, mc_engine.py, solver.py, weight_bridge.py, out/weight_bridge.json, symmetric_exact.py, bridge_full.py, out/symmetric_exact.json
• Prior-art references: BCSTP (§4.1–4.2); Boyar–Peralta (2008, Lemma 13)

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 9 of 9 receipt files bundled (26 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.

Download evidence.zip

Related in this programme

• MF-169
  Exact multiplicative complexity of 7-variable majority
• MF-179
  Exact Multiplicative Complexity of Parallel Counters and Multi-Operand Compressors
• MF-181
  Exact multiplicative complexity of the resolved-carry family K_m
• MF-182
  Unification of Additive Line Multiplicative Complexity via Greedy Column-Heap Recursion