Research · Papers · Adders, counters and the heap law · MF-138
Exact multiplicative complexity of the two-column C7 carry transducer
MC(T) = 6 for the 11-input, 5-output two-column C7 carry transducer
Published 2026-09-04
For everyone
Plain summary
In digital hardware design, addition circuits combine several numbers at once using blocks called compressors. In cryptographic hardware, zero-knowledge proofs, and private computing, linear XOR gates cost almost nothing, while non-linear AND gates drive the computational cost. Multiplicative complexity measures the absolute minimum number of AND gates needed to evaluate a given function.
This paper determines the exact multiplicative complexity of the two-column C7 carry transducer, an 11-input, 5-output circuit built by chaining two four-operand compressor stages across a three-wire carry state. The minimum cost is exactly six AND gates. An explicit six-gate circuit proves that six suffice. Mathematical analysis combined with automated SAT solvers proves that five gates are impossible: solvers split the five-gate search space into 61 separate cases and verified that none contain a working circuit.
Result
Let T : GF(2)^11 -> GF(2)^5 denote the two-column C7 carry transducer map formed by cascading two four-operand C7 compressor stages sharing a three-wire redundant carry state. The multiplicative complexity of T over GF(2) under the standard XOR-free cost model is:
MC(T) = 6
Setting and definitions
Computation is evaluated in the standard XOR-AND graph (XAG) model over GF(2), where linear operations (XOR, XNOR) carry zero cost and complexity is the number of two-input AND gates (products).
The map T takes 11 Boolean inputs and produces 5 Boolean outputs. It computes the chained composition of two three-product C7 compressor instances across two adjacent columns of four operands, communicating through a three-wire redundant carry state.
Multiplicative complexity MC(T) is the minimum number of AND gates p required in an XAG to evaluate all component functions of T simultaneously.
Method
The value MC(T) = 6 is settled by matching bounds:
- Upper bound (MC(T) <= 6):
Constructed via an explicit replayed six-gate circuit.
- Lower bound (MC(T) >= 6):
The algebraic lower bound follows from MF-137, which establishes dim V = 4 and mu = 3 for the underlying linear and affine structure.
- Automated solver verification (p = 5 refutation):
Refutation of p = 5 was established via the cube-and-conquer SAT pipeline documented in RECORD-WINOGRAD-P5.md:
- The p = 5 search space was partitioned into 61 cubes.
- The cubes are pairwise disjoint and satisfy an exact Kraft sum of 1.
- All 61 subproblems were solved UNSAT across 31 CaDiCal legs and 30 Kissat legs.
- Verification tier: P+FC+FR (Proof, Full Certificate, Full Replay).
Discussion
The result closes the multiplicative complexity of the two-column C7 carry transducer at MC(T) = 6, leaving no gap between the constructive upper bound and the verified lower bound.
Key properties:
- The proof combines the structural algebraic invariant from MF-137 (dim V = 4, mu = 3) with an exhaustive, certified SAT search at p = 5.
- A Kraft sum of 1 across the 61 disjoint cubes certifies full coverage of the search space without gaps or double-counting.
- The result is restricted to the two-column chained C7 configuration on a three-wire redundant carry state; the register records no extensions to wider cascades or alternative carry encodings.
- No prior-art claims or index corrections are recorded for this entry.
For everyone — the takeaway
What this means
This establishes an exact lower bound and optimal circuit for multi-operand addition networks. Designers building compressor trees for secure hardware, zero-knowledge proofs, or fully homomorphic encryption can implement this two-column transducer with six AND gates, confident that no five-gate alternative exists.
Register references
- MF-138
- MF-137
- RECORD-WINOGRAD-P5.md
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 0 of 1 receipt files bundled (1 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.