Research · Papers · Adders, counters and the heap law · MF-152
Sharpness of the 5/8 law and multiplicative complexity of n-bit addition
delta = (5/8)^p attained at MC = p for disjoint ANDs, mod 2^n addition (MC = n - 1), and full addition (MC = n); Floor A <= 1.4747 m
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity counts the minimum number of nonlinear operations, like AND gates, needed to evaluate a logic function when linear steps like XOR are free. A key lower-bound technique, Floor A, tracks how function energy decays by at most 5/8 per multiplication. This work proves that the 5/8 decay factor cannot be tightened.
Three explicit circuit families achieve this bound with exact equality: chains of independent AND gates, modular addition of two n-bit integers (which takes exactly n - 1 multiplications), and full n-bit addition with an output carry (taking n multiplications). Because the decay factor matches these circuits exactly, the circuit cost of n-bit addition follows by direct algebra without running automated SAT or SMT solvers. Boyar, Peralta, and Pochuev (2000) originally established the n - 1 count; proving that the 5/8 rate is unconditionally sharp across these families is new.
Result
The energy decay factor 5/8 in the Floor A lower bound is unconditionally sharp. For any circuit with p multiplication gates, the spectral decay parameter delta reaches its theoretical minimum:
delta = (5/8)^p
Equality delta = (5/8)^p occurs at multiplicative complexity MC = p for three families:
- Direct sums of p independent two-input AND gates: MC = p with delta = (5/8)^p.
- Two-operand modular addition A_{2,n}(x, y) = x + y mod 2^n: MC = n - 1 with delta = (5/8)^(n - 1), verified for n = 1 through 32 and proved for all n.
- Full-precision two-operand addition with carry out: MC = n with delta = (5/8)^n.
Geometric condition: delta = (5/8)^p holds if and only if the transcript Fourier-Walsh spectrum intersects each affine coset of the gate input subspace span{a, b} in at most one point. Neither bijectivity nor bentness forces a decay factor below 5/8: the Toffoli gate has MC = 1 with delta = 5/8, and the bent function x1 x2 gives delta = 5/8.
The associated complexity estimators satisfy:
- Floor A <= log_{8/5}(2^m) <= 1.4747 m for m output bits (closed form of the shelf's "about 2,360" at m = 1600).
- Floor A <= 1 for single-output Boolean functions (m = 1).
- Floor B <= ceil(n / 2) for any n-input function.
Setting and definitions
The model is XOR-free multiplicative complexity over GF(2), equivalent to straight-line programs in XOR-AND graphs (XAGs) where linear GF(2) operations (XOR, XNOR) carry zero cost. The multiplicative complexity MC(f) is the minimum number of GF(2) AND gates required to compute f: GF(2)^n -> GF(2)^m.
In the spectral framework, Floor A assigns an affine subspace span{a, b} to the inputs of each multiplication gate. The parameter delta tracks the residual Fourier-Walsh spectral weight surviving projection under gate evaluations. The universal lower bound enforces delta >= (5/8)^(MC(f)).
Floor B denotes the linear-algebraic dimension-halving lower bound determined by the rank of component derivatives.
Method
Results were established with exact rational arithmetic and transfer-matrix induction in Python:
- Exact rational evaluation: Scripts
floors/energy58.py,transfer_energy.py, andtransfer_full.pyevaluate spectral decay sequences over GF(2) using exact rational arithmetic to avoid floating-point error. - Transfer-matrix induction: Addition A_{2,n} was modeled as a Markov state-transfer process. Verification artifact
out_transfer_k2.jsonconfirmed delta = (5/8)^(n - 1) for all widths n = 1 through 32. State uniformity across bit positions supplies inductive closure for all n >= 1 without SAT/SMT search. - Carry and scaling verification: Full-precision adder dynamics and direct sums were evaluated via
scaling_probe.pyand logged inout_scaling.json.
Discussion
Boyar, Peralta, and Pochuev (2000, abstract-only) first proved MC(x + y mod 2^n) = n - 1. The present derivation recovers this count analytically as an immediate consequence of the sharpness of the 5/8 factor.
Structural limits established by the analysis:
- The 5/8 constant is tight against both bent functions and reversible permutations like the Toffoli gate.
- Floor A is additive under direct sums: Floor A(f +++ g) = Floor A(f) + Floor A(g). Floor B is not additive under direct sums.
- Neither bound dominates universally. Floor A is strictly tighter on two-operand addition, the Keccak chi permutation, and integer multiplication. Floor B is strictly tighter on multi-operand addition with k >= 4 summands.
- State uniformity fails for addition with K >= 3 input operands; the sharpness proof for A_{2,n} does not extend directly to K >= 3.
For everyone — the takeaway
What this means
Proving how many logic gates a computation requires means ruling out every possible shortcut. The 5/8 decay rate measures how much progress a single multiplication can make in the Floor A framework. Proving that standard binary addition hits this 5/8 limit at every bit shows that the mathematical constant cannot be improved, and that binary addition uses the minimum multiplication gates theoretically possible under this measure.
Attribution and prior art
Prior art: While the value n - 1 was previously reported in BPP (2000, abstract only), the sharpness of this internal constant appears to be new.
Register references
- Register entry: MF-152
- Boyar, Peralta, and Pochuev (2000) [BPP 2000, ABSTRACT-ONLY]
- Source artifacts:
floors/energy58.py,transfer_energy.py,out_transfer_k2.json,transfer_full.py,scaling_probe.py,out_scaling.json
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 6 of 6 receipt files bundled (10 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.