Research · Papers · Further results · MF-153
Solver-Free Multiplicative Complexity Lower Bounds from Degree and Walsh Floors
MC(3×3) ≥ 6, MC(4×4) ≥ 9, MC(clmul_4) ≥ 8, MC(clmul_5) ≥ 11, MC(Add(4,5)) ≥ 8 via degree and Walsh floor methods
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the minimum number of logical AND gates needed to evaluate a Boolean function using only AND and XOR operations. Proving that a circuit cannot be built with fewer AND gates typically requires running SAT solvers, which slow down or fail entirely on larger circuits. This work derives rigorous lower bounds analytically using algebraic degree floors and Walsh spectral floors, bypassing automated solvers completely. Across an atlas of 33 addition circuits, the combined floors match exact counts in 23 cases and miss by a single gate in 9 cases. Degree floors give tighter bounds on narrower inputs, while Walsh spectral floors dominate as inputs widen.
Result
Analytical degree and Walsh spectral floors establish solver-free lower bounds for integer multiplication, carryless multiplication, schedule tiles, and multi-operand addition:
- Integer multiplication:
- MC(3×3) >= 6
- MC(4×4) >= 9
- MC(5×5) >= 12
- Carryless and finite field multiplication:
- MC(clmul_4) >= 8 (known upper bound 9; quadratic-model value 9 via MF-167)
- MC(clmul_5) >= 11 (known upper bound 13)
- MC(clmul(3,4)) >= 7 (known upper bound 8)
- MC(GF(8) mult) >= 5 (exact value 6)
- MC(clmul_2) = MC(GF(4) mult) = 3 (exact; upper bound replayed)
- Schedule tile and multi-operand addition circuits:
- MC(MF-096 schedule tile) >= 5 (recorded construction 6)
- MC(Add(4,5)) >= 8
- MC(Add(8,3)) >= 8
- MC(Add(3,n)) >= 2n - 4 (re-derived independently of MF-101)
- MC(A_{4,4}) >= 6
- Solver-free lower-bound re-derivations of banked exact cells:
- chi_3 = 3, chi_4 = 4, chi_5 = 5
- A_{3,3} = 3
- A_{4,2} = 2
- A_{3,2} = 1
- A_{2,n} = n - 1
- A_{k,2} = floor(k/2) for k = 5..8 (MF-100)
Across an empirical combined-floor slack atlas of 33 addition cells, the bounds never exceed exact values: 23 cells have slack 0 (exact), 9 have slack 1, and 1 has slack 4 (FullAdd(4,4)). The degree floor dominates for K <= 3, while the Walsh floor dominates for K >= 4.
Setting and definitions
Let f: GF(2)^n -> GF(2)^m be a multi-output Boolean function. The multiplicative complexity MC(f) is the minimum number of two-input AND gates required to compute f over the basis (AND, XOR, NOT).
The algebraic degree floor, denoted Floor A (Schnorr), bounds MC(f) from below using the algebraic degrees of the coordinate functions of f and their linear combinations.
The Walsh spectral floor, denoted Floor B or Walsh floor MF-135(ii), bounds MC(f) from below via the non-linearities and spectral properties derived from the Walsh transform of f.
Add(K,n) and A_{K,n} denote the addition of K operands of bit-width n. The term clmul_n denotes carryless multiplication of two n-bit polynomials over GF(2), and clmul(n,m) denotes carryless multiplication of an n-bit polynomial and an m-bit polynomial.
Method
Lower bounds follow analytically from closed-form degree bounds (Schnorr) and Walsh spectral floor formulas (MF-135(ii)) without SAT solver execution or search encodings.
Calculations are implemented in carry/walsh_atlas.py and degree_atlas.py. Evaluation artifacts covering addition grids, polynomial multiplication, and mixed integer families are logged in:
- floors/out_family.json
- floors/out_family2.json
- floors/out_mixed.json
- floors/out_grid_add.json
- out/walsh_atlas.json
Evidence tier: P floors (proved lower bounds), FC atlas (fully checked empirical slack distribution).
Discussion
The bounds provide rigorous lower bounds without automated search, though gaps remain against known upper bounds:
- For clmul_4, the floor guarantees MC(clmul_4) >= 8, against a known upper bound of 9 (and quadratic-model value 9 via MF-167).
- For clmul_5, the floor yields MC(clmul_5) >= 11 against a known upper bound of 13.
- For clmul(3,4), the floor yields MC(clmul(3,4)) >= 7 against a known upper bound of 8.
- For GF(8) multiplication, the floor yields >= 5 against an exact value of 6.
- For the MF-096 schedule tile, the floor yields >= 5 against a recorded construction of 6.
- For FullAdd(4,4), the combined floor is four gates below exact.
Upper bounds are not replayed in this register entry except for clmul_2, clmul_3, and mult_2x2.
Dominance splits cleanly along operand count: degree floors govern K <= 3, whereas Walsh spectral floors become strictly stronger for K >= 4. Add(4,5) and Add(8,3) populate floor cells absent from the MF-136 catalogue.
For everyone — the takeaway
What this means
Proving lower bounds on circuit sizes usually requires automated search tools that time out as inputs grow. By computing bounds directly from algebraic degrees and Walsh spectra, these formulas produce provable lower bounds on paper. While the analytical floors miss exact gate counts on dense or wide functions, they match exact values on most addition circuits tested and provide a dependable baseline for integer and polynomial arithmetic.
Attribution and prior art
Prior art: These bounds are previously established: the degree floor is credited to Schnorr, and the Walsh floor is documented under entry MF-135.
Register references
- Register Entry: MF-153
- Prior Art: Schnorr (algebraic degree floor); MF-135 (Walsh spectral floor MF-135(ii))
- Related Entries: MF-096, MF-100, MF-101, MF-136, MF-167
- Receipt Artifacts:
- floors/out_family.json
- floors/out_family2.json
- floors/out_mixed.json
- floors/out_grid_add.json
- carry/walsh_atlas.py
- degree_atlas.py
- out/walsh_atlas.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 7 of 7 receipt files bundled (9 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.