Research · Papers · The quadratic hull and its defects · MF-144
The packing filtration lower bound and master identity for multiplicative complexity
MC(F) = dim V + max_j (m_{j+1}(V) - j - 1) and MC(F) ≥ dim V' - j + m_{j+1}(V') - 1 for all V' ≤ V
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity counts the minimum number of AND gates needed to compute a logical function when XOR gates are free. Finding this exact count for cryptographic operations like S-boxes is usually very difficult. This work establishes an exact formula and lower bounds that compute multiplicative complexity by tracking how gate outputs overlap with target output directions across dimensions.
Checking these overlaps across each subspace dimension yields a sequence of bounds that peaks at the true complexity. Restricting the calculation to smaller subspaces often gives higher bounds than checking the whole output space at once. Earlier rank and gate-span techniques were developed by Schnorr (1989), Boyar, Peralta, and Pochuev (2000), and Boyar and Find (2018); expressing multiplicative complexity as a filtration identity over dimension indices is new here.
Result
Let F be a multi-output Boolean function over GF(2) under the XOR-free XAG cost model. Let V be the nonlinear output span modulo affine components, and let m_j(V) denote the minimum number of multiplication gate classes whose span meets V in a j-dimensional subspace.
For every subspace V' <= V and every index 0 <= j < dim V', the packing filtration lower bound satisfies:
MC(F) >= dim V' - j + m_{j+1}(V') - 1
Evaluating over the full space V yields the master identity:
MC(F) = dim V + max_j (m_{j+1}(V) - j - 1)
Theorem D shows that a lower bound on any single value m_{j+1}(V) establishes a global circuit lower bound.
Corollary D1: If m_{D-2}(V_c) >= 3c - 2, then MC(F_c) >= 3c for every circuit.
Setting and definitions
Let F: GF(2)^n -> GF(2)^m. In the GF(2) XOR-and-inverter graph (XAG) model, XOR gates and constant additions are cost-free, and complexity is measured by multiplicative complexity MC(F), the minimum number of AND gates.
Let V <= GF(2)^m / Affine denote the linear span of the nonlinear coordinates of F modulo affine functions. For any subspace V' <= V, the subspace packing number m_j(V') is the minimum number k of intermediate AND gate output classes g_1, ..., g_k such that dim(span(g_1, ..., g_k) ∩ V') >= j.
The parameter j indexes a filtration over the dimensions of gate-span intersections with V', where 0 <= j < dim V'. Setting j = 0 and V' = V recovers the MF-137 lower bound.
Method
- Symbolic proof: Derived via dimensional filtration of gate spans intersecting V and restricted subspaces V'. Theorem D and Corollary D1 trace dimension deficiencies across gate class allocations.
- Computational sweep: Executed via
sweep.pyandgeometry/restricted.pyacross an 89-unit test suite. Outputs compiled insweep_results.jsonandSWEEP-TABLE.mdconfirmed zero exceedances against the master identity and filtration bounds. - Analysis details and proofs appear in
geometry/REPORT.md§§3–4, 6.
Discussion
The packing filtration links circuit complexity directly to subspace intersection numbers. Prior gate-span and rank methods in multiplicative complexity stem from Schnorr (1989), Boyar, Peralta, and Pochuev (2000), and Boyar and Find (2018); formulating the relation as a tight master identity across the full filtration over j is novel to this entry.
Restricting to proper subspaces V' < V is structurally necessary. For the 2-by-2 matrix multiplication tensor M_2, evaluating the bound on the full output space gives 5, whereas evaluating on an optimal 2-plane yields 6 (MF-149).
Corollary D1 resolves the missing half of the bound in MF-139, predicting that the two-column C7 transducer output space V contains a class of degree >= 3. The truth-table verification on AX162 required to confirm this degree property has not yet been run.
For everyone — the takeaway
What this means
This result provides an exact formula connecting the number of AND gates in an optimal circuit to geometric packing properties of its outputs. Rather than searching through vast spaces of circuit wirings, one can compute how output functions intersect smaller linear subspaces. Because the bound can be tested on individual subspaces, it often captures tighter complexity values than whole-system checks. This closes a gap in circuit lower bounds and supplies a concrete target for analyzing specific cryptographic components.
Attribution and prior art
Prior art: The gate-span and rank arguments are credited to Schnorr (1989), Boyar–Peralta–Pochuev (2000), and Boyar–Find (2018). However, the filtration over j was not located as an explicit identity in prior literature.
Register references
- MF-137
- MF-139
- MF-144
- MF-149
- Schnorr (1989)
- Boyar, Peralta, and Pochuev (2000)
- Boyar and Find (2018)
geometry/REPORT.md§§3–4, 6geometry/restricted.pysweep.pysweep_results.jsonSWEEP-TABLE.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 5 of 5 receipt files bundled (15 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.