Research · Papers · Further results · MF-137
The packing lemma lower bound for multiplicative complexity
MC(F) ≥ dim(V) + μ(V) - 1, where V is nonlinear output span mod affine and μ(V) is min gate cost of any nonzero scalar class in V
Published 2026-09-04
For everyone
Plain summary
Multiplicative complexity measures the fewest multiplication steps (AND gates) needed to compute a set of Boolean functions using addition and multiplication over GF(2). Finding this exact minimum usually requires long SAT solver runs.
This paper proves a general lower bound called the packing lemma that requires no search. The bound combines two properties: the dimension of the function's nonlinear output space modulo affine functions, and the minimum multiplication cost among all nonzero scalar components in that space. The dimension comes from standard linear algebra, and component costs follow from degree and quadratic polar bounds, so the bound evaluates instantly.
One caveat: on the benchmark case where the true optimal complexity is known to be 6, the packing lemma gives 5. The bound undershoots by one in calibrated testing and should not be assumed to be tight.
Result
Let F be a multi-output Boolean function. Let V be the nonlinear output span of F modulo affine functions, and let mu(V) be the minimum gate cost of any nonzero scalar class in V. Then:
MC(F) >= dim(V) + mu(V) - 1
Setting and definitions
Let F: GF(2)ⁿ -> GF(2)ᵐ be a Boolean function. The multiplicative complexity MC(F) is the minimum number of AND gates in an XOR-AND graph (XAG) computing F over GF(2).
Let V denote the linear span of the coordinate functions of F modulo the space of affine functions. For any scalar class g in V, let MC(g) denote the multiplicative complexity of g modulo affine functions. The quantity mu(V) is defined as:
mu(V) = min { MC(g) : g in V, g != 0 }
Method
Let an optimal XAG compute F with r = MC(F) multiplicative gates, and let g1, g2, ..., gr represent the gate output classes modulo affine functions.
- Linear independence modulo affine functions: The set {g1, ..., gr} is linearly independent modulo affine functions. If an affine dependence existed across g1, ..., gk with k <= r, gate gk could be expressed as an affine combination of earlier gates g1, ..., g(k-1) and circuit inputs, eliminating gk and contradicting the minimality of r.
- Disjoint spans: Let W = span(g1, ..., g(mu(V)-1)). By definition of mu(V), any nonzero element in V requires at least mu(V) multiplicative gates. Therefore, no nonzero element of V lies in W, which implies V ∩ W = {0}.
- Dimension bound: All nonlinear outputs of F reside in span(g1, ..., gr). Because V is a subspace of span(g1, ..., gr) that intersects the (mu(V) - 1)-dimensional subspace W only at zero, the total gate count r must satisfy r >= dim(V) + (mu(V) - 1).
The bound requires no SAT solver to evaluate. The quantity dim(V) is computed directly by linear rank reduction of the coordinate functions, and mu(V) is bounded below via the exact quadratic polar bound and the degree bound.
The result is catalogued under evidence tier P in zkgolf-decomp/RECORD-WINOGRAD-P5.md.
Discussion
The packing lemma provides a lower bound on multiplicative complexity directly from linear algebra and degree considerations.
Calibration and tightness: On the single benchmark cell where exact multiplicative complexity is known, the true complexity is 6, whereas the packing lemma evaluates to 5. The lemma runs one low in this test case and cannot be treated as tight.
Scope: The bound applies to any multi-output Boolean function F over GF(2). Its primary utility is ruling out small circuit sizes without invoking SAT solvers or constraint satisfaction routines.
For everyone — the takeaway
What this means
Determining the exact number of multiplications in a circuit typically requires heavy automated solver runs that scale poorly. The packing lemma provides a fast, solver-free floor on the number of AND gates required. While calibration shows it can undershoot the exact minimum by one gate, it gives circuit designers an immediate, proven lower bound using only matrix rank and algebraic degree.
Register references
- Register ID: MF-137
- Source receipt: zkgolf-decomp/RECORD-WINOGRAD-P5.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 0 of 1 receipt files bundled (1 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.