Research · Papers · Adders, counters and the heap law · MF-136
Exact multiplicative complexity of 5-by-3 addition and six addition floors
MC(Add(5,3)) = 5, with Add(5,4) >= 8, Add(5,5) >= 10, Add(6,3) >= 6, Add(6,4) >= 9, Add(7,3) >= 7, Add(7,4) >= 11
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the minimum number of nonlinear operations (AND gates) needed to compute a Boolean function when linear operations (XOR gates) are free. AND gates dominate the cost of privacy-preserving cryptographic protocols and hardware implementations.
This entry resolves the exact multiplicative complexity of adding an unsigned 5-bit integer to an unsigned 3-bit integer. An exhaustive spectral evaluation of the addition function proves that 5-by-3 addition requires at least 5 AND gates. This matches an existing 5-gate construction, fixing the exact value at 5.
The same evaluation method yields new lower bounds for six larger addition tasks: adding 5-bit numbers to 4-bit and 5-bit numbers, 6-bit numbers to 3-bit and 4-bit numbers, and 7-bit numbers to 3-bit and 4-bit numbers.
Result
Under the standard GF(2) XOR-AND graph cost model:
MC(Add(5,3)) = 5
Direct spectral evaluation also establishes six addition lower bounds:
- MC(Add(5,4)) ≥ 8
- MC(Add(5,5)) ≥ 10
- MC(Add(6,3)) ≥ 6
- MC(Add(6,4)) ≥ 9
- MC(Add(7,3)) ≥ 7
- MC(Add(7,4)) ≥ 11
Setting and definitions
Computation is modeled by the GF(2) XOR-AND Graph (XAG), where XOR, XNOR, and NOT gates have zero cost and 2-input AND gates have unit cost. The multiplicative complexity MC(f) of a multi-output Boolean function f is the minimum number of AND gates required to compute f over GF(2).
The function Add(n, m): GF(2)ⁿ × GF(2)ᵐ → GF(2)^(max(n,m)+1) computes the binary integer sum of an n-bit operand and an m-bit operand.
Floor B lower bounds determine multiplicative complexity thresholds directly from Walsh spectral invariants of the component functions, specifically the maximum normalized l1 norm and the maximum spectral support across non-trivial linear combinations.
Method
Complete-domain Walsh spectral evaluation of Add(5,3) yields:
- Maximum normalized l1 norm: 16
- Maximum spectral support: 352
Applying the lower-bound formulation of MF-135 floor (ii) to these invariants produces a Floor B lower bound of 5 AND gates. Replaying an existing 5-gate circuit construction matches the lower bound, establishing MC(Add(5,3)) = 5.
Evaluating the larger parameter sets under the same MF-135 floor (ii) framework produces the six lower bounds:
- Add(5,4) ≥ 8
- Add(5,5) ≥ 10
- Add(6,3) ≥ 6
- Add(6,4) ≥ 9
- Add(7,3) ≥ 7
- Add(7,4) ≥ 11
The bounding scripts, spectral checks, and verification procedures are certified at evidence tier P+FR in COUNCIL3-VERIFY-FLOORS.md.
Discussion
Exact equality is proved only for Add(5,3). For Add(5,4), Add(5,5), Add(6,3), Add(6,4), Add(7,3), and Add(7,4), the spectral floors establish valid lower bounds, but matching upper-bound constructions are not certified here.
The register records no prior-art position, no index corrections, and no scope addenda.
For everyone — the takeaway
What this means
Computing a 5-bit plus 3-bit addition requires 5 AND gates; 4 gates are mathematically impossible, and 5 gates are achievable. For the six larger additions, these new floors rule out smaller designs and set the baseline targets for circuit synthesizers.
Register references
- Entry: MF-136
- Baseline bounding method: MF-135 floor (ii)
- Verification receipt: COUNCIL3-VERIFY-FLOORS.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.