Research · Papers · The quadratic hull and its defects · MF-146
Deficit law lower bound for all-quadratic spaces
MC(F) ≥ dim V - 2 + ⌈3μ/2⌉ for all-quadratic V with every nonzero class of cost μ
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the fewest nonlinear multiplications needed to evaluate a system of equations in a logic circuit. For quadratic systems—where every equation has degree at most two—lower bounds prove that a cryptographic block or algebraic routine cannot run with fewer multiplications.
This result gives the deficit law for all-quadratic spaces. If a space of quadratic functions has dimension dim V and every nonzero class in that space costs mu multiplications on its own, evaluating the full system takes at least dim V - 2 + ceil(3mu/2) multiplications. This beats the earlier baseline bound (MF-137) by ceil(mu/2) - 1.
The bound applies only to all-quadratic targets. It says nothing about cubic or higher-degree systems such as chi², arithmetic adders, or cryptographic transducers. Because it combines MF-144 and MF-145, it is classified as partial prior art.
Result
Let V be an all-quadratic space over GF(2), where every nonzero class has cost mu under the bilinear cost model. The multiplicative complexity MC(F) of the system F associated with V satisfies:
MC(F) ≥ dim V - 2 + ⌈3μ/2⌉
This bound strictly improves the baseline bound from MF-137 by ⌈μ/2⌉ - 1.
Setting and definitions
Let V be a finite-dimensional vector space of quadratic Boolean functions over GF(2) containing no cubic or higher-degree components.
- dim V denotes the linear dimension of V over GF(2).
- mu (or μ) denotes the uniform multiplicative cost of every nonzero class in V.
- MC(F) denotes the multiplicative complexity of the target map F corresponding to V, evaluated under standard bilinear/tensor rank complexity.
- The deficit law quantifies the structural deficit between the baseline dimension-dependent lower bound and the aggregate cost induced by component cost mu.
Method
The theoretical bound (Corollary C) is an analytic deduction combining structural bounds MF-144 and MF-145 (evidence tier P, proved).
Computational verification (evidence tier FC) covers an 89-unit sweep of test instances. The bound is implemented in Target.bound_corC within geometry/mcgeom.py, with empirical data logged in sweep_results.json.
Discussion
The deficit law tightens the multiplicative complexity lower bound for all-quadratic spaces whenever mu ≥ 3, widening the baseline margin over MF-137 by ceil(mu/2) - 1.
Scope and caveats:
- Scope: Restricted to all-quadratic spaces V where every nonzero class has uniform cost mu.
- Higher degrees: Silent on cubic and higher-degree targets; it yields no bounds for chi², adders, or sequential transducers.
- Prior art: Classified as partial prior art because it directly composites MF-144 and MF-145.
For everyone — the takeaway
What this means
In circuit design and cryptography, finding the minimum number of multiplications stops engineers from hunting for circuits that cannot exist. The deficit law sets a hard floor for quadratic systems using their dimension and component costs.
It doesn't cover cubic formulas or adders, but it sharpens the limits for quadratic maps: when individual components cost more, the whole circuit's required multiplication count rises with them.
Attribution and prior art
Prior art: PARTIAL (composite of MF-144/MF-145).
Register references
- Register entry: MF-146
- Related register entries: MF-137, MF-144, MF-145
- Artifact receipts: geometry/mcgeom.py (Target.bound_corC), sweep_results.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 2 of 2 receipt files bundled (4 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.