Research · Papers · The quadratic hull and its defects · MF-145
Packing floors on quadratic multiplicative complexity for linear spaces of quadratics
qMC(W) ≥ ceil(sum_{w ≠ 0} mc(w) / 2^{d-1}) for d-dim space W; d=2 yields qMC(W) ≥ ceil((mc(q1)+mc(q2)+mc(q3))/2)
Published 2026-09-04
For everyone
Plain summary
When computing several quadratic formulas together, circuits save operations by sharing intermediate multiplication gates. Multiplicative complexity measures the minimum number of multiplications required to evaluate Boolean functions over binary inputs. In the quadratic model, every multiplication gate multiplies two linear functions of the input bits.
This work establishes a lower bound on the quadratic multiplications needed to evaluate an entire linear space of quadratic equations. Viewed as a geometric code, each multiplication gate contributes to at most half of the non-zero equations in any linear slice. Summing the individual costs across the space yields a packing floor. For two-dimensional spaces, this floor matches the exact complexity across all eleven tested targets. While the bound holds for unrestricted circuits on two-dimensional spaces, on spaces of dimension three and higher it holds only in the quadratic model.
Result
Let W be a d-dimensional linear space of quadratic forms over GF(2). Let qMC(W) denote the quadratic multiplicative complexity of W, and let mc(w) denote the multiplicative complexity of an individual form w ∈ W.
LEMMA B₃ (General Packing Floor): qMC(W) ≥ ceil( sum_{w ≠ 0} mc(w) / 2^(d-1) )
LEMMA B (Plane Parity Floor, d = 2): For a two-dimensional space W = span{q1, q2} with non-zero elements q1, q2, and q3 = q1 + q2: qMC(W) ≥ ceil( (mc(q1) + mc(q2) + mc(q3)) / 2 )
Model Transfer:
- For d ≤ 2, Mirwald–Schnorr normal forms transfer the bound to unrestricted multiplicative complexity MC(W), giving m_2(V) ≥ ceil((mc(q1)+mc(q2)+mc(q3))/2) in every circuit model and making THEOREM A′ unrestricted at j = 1.
- For d ≥ 3, the inequality bounds qMC(W) strictly. The corresponding inequality for unrestricted multiplicative complexity MC(W) fails in general (MF-174 ii).
The plane parity floor matches exact complexity qMC(W) on all 11 all-quadratic target spaces evaluated.
Setting and definitions
Let GF(2) be the field of two elements. A quadratic form is a homogeneous polynomial of degree 2 in GF(2)[x1, ..., xn]. The multiplicative complexity mc(f) of a Boolean function f is the minimum number of AND gates (GF(2) multiplications) in an XOR-AND graph computing f from inputs x1, ..., xn and constants.
The quadratic multiplicative complexity qMC(W) of a linear space W of quadratic forms is the minimum number r of rank-1 forms p_k = L_k * R_k (with affine L_k, R_k) whose linear span contains W.
For an affine subspace V of Boolean mappings, m_2(V) denotes the multiplicative complexity floor on two-dimensional projections. The coordinate code of W relative to a minimal decomposable basis {p_1, ..., p_r} is the linear evaluation map from W into GF(2)^r sending w to the binary vector (c_1, ..., c_r) satisfying w = sum_{k=1}^r c_k * p_k.
Method
The bound follows from coordinate weight-counting on the realization's dual code.
- Coordinate code construction: Let {p_1, ..., p_r} be a minimal quadratic basis for W, where r = qMC(W). Each w ∈ W expands as w = sum_{k=1}^r c_k(w) * p_k. Because W has dimension d, the map w ↦ (c_1(w), ..., c_r(w)) defines an injective linear code of dimension d and length r over GF(2).
- Weight counting: For each active coordinate k ∈ {1, ..., r}, the functional c_k : W → GF(2) is non-zero. Its kernel has dimension d - 1, so c_k(w) = 1 for exactly 2^(d-1) non-zero elements w ∈ W.
- Summation: Summing Hamming weight across all non-zero codewords gives:
sum_{w ≠ 0} wt(c(w)) = sum_{k=1}^r sum_{w ≠ 0} c_k(w) = r * 2^(d-1)
- Complexity floor: Because w decomposes into wt(c(w)) rank-1 forms, mc(w) ≤ wt(c(w)). Summing over all 2^d - 1 non-zero elements yields:
sum_{w ≠ 0} mc(w) ≤ sum_{w ≠ 0} wt(c(w)) = qMC(W) * 2^(d-1) Dividing by 2^(d-1) and taking the ceiling establishes LEMMA B₃.
Verification and benchmark receipts:
geometry/REPORT.md§4geometry/exact_m2.pyexact_m2_result.jsonwave1-ms3/u3_fano_floor.pywave1-ms3/REPORT.md§2 U3
Discussion
The packing floor links the isolated complexity of individual forms to the joint complexity of their linear span.
Model boundaries:
- For d = 2, Mirwald–Schnorr normal forms ensure that optimal unrestricted circuits normalize to quadratic form without adding multiplication gates, making the floor universal.
- For d ≥ 3, normal forms do not guarantee this reduction. MF-174 ii provides counterexamples where higher-degree intermediate products in unrestricted circuits beat the packing floor, restricting the bound to qMC(W).
Prior art context: Prior art is assessed as PARTIAL. The counting argument applies standard Griesmer- or simplex-style linear code weight distributions to decomposable coordinate bases. LEMMA B (d = 2) follows directly from Mirwald–Schnorr quadratic form classifications.
Empirical tightness: Exhaustive evaluation across 11 target quadratic spaces confirms LEMMA B is tight for every tested two-dimensional plane.
For everyone — the takeaway
What this means
This result sets a hard floor on the multiplication cost of evaluating sets of quadratic formulas. When bundling quadratic expressions in hardware or cryptography, sharing multiplication gates between outputs cannot bypass geometric packing constraints: any two-dimensional plane of formulas requires at least half the sum of their individual costs, rounded up.
Attribution and prior art
Prior art: This is a partial result. Griesmer- and simplex-style counting methods apply to the decomposable-coordinate code, while Mirwald–Schnorr's normal form plausibly resolves the `d = 2` case.
Register references
- Entry: MF-145
- Related entries: MF-174 ii
- Artifacts:
geometry/REPORT.md§4geometry/exact_m2.pyexact_m2_result.jsonwave1-ms3/u3_fano_floor.pywave1-ms3/REPORT.md§2 U3- Prior art: Mirwald–Schnorr normal form; Griesmer / simplex-style coordinate code weight counting.
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 4 of 4 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.