Research · Papers · Direct sums, wedges and the p14 frontier · MF-164
Exact multiplicative complexity of direct sums of monomial Boolean functions
MC(x1x2x3 ⊕ y1y2y3y4) = 5, MC(x1x2x3 ⊕ y1y2y3) = 4, and additivity holds across all tested direct-sum cells
Published 2026-09-04
For everyone
Plain summary
In digital circuits and cryptography, multiplicative complexity counts the minimum number of logical AND gates needed to evaluate a Boolean function when XOR operations are free. Because AND gates drive the computational cost in secure multi-party computation and zero-knowledge proofs, finding exact gate bounds is essential. A core question in circuit complexity is whether evaluating two separate functions on independent variable sets (their direct sum) ever lets a circuit share intermediate work to beat the sum of their individual costs.
This work proves exact gate counts for several benchmark direct-sum functions. In particular, computing the direct sum of a 3-variable monomial and a 4-variable monomial requires exactly 5 AND gates, matching the sum of their separate complexities (2 + 3 = 5). These resolved cases extend beyond prior 6-variable classifications.
Result
Multiplicative complexity is strictly additive across all evaluated direct-sum benchmarks:
- MC(x1x2x3 ⊕ y1y2y3y4) = 5 on n = 7 variables.
- MC(x1x2x3 ⊕ y1y2y3) = 4 on n = 6 variables.
- MC(x1x2x3 ⊕ (y1y2 + y3y4)) = 4 on n = 7 variables.
- MC((x1x2 + x3x4) ⊕ (y1y2 + y3y4)) = 4 on n = 8 variables.
- MC(x1x2 ⊕ y1y2y3y4) = 4 on n = 6 variables.
In every case, MC(f(x) ⊕ g(y)) = MC(f(x)) + MC(g(y)), showing zero defect against the additive baseline.
Setting and definitions
For a Boolean function f: GF(2)^n -> GF(2), the multiplicative complexity MC(f) is the minimum number of two-input AND gates needed to evaluate f over the basis {AND, XOR, NOT} with unrestricted fan-out and free affine operations over GF(2).
Given functions f: GF(2)^p -> GF(2) and g: GF(2)^q -> GF(2) on disjoint inputs x = (x1, ..., xp) and y = (y1, ..., yq), their direct sum is (f ⊕ g)(x, y) = f(x) ⊕ g(y) on n = p + q variables. The additivity conjecture asks whether MC(f ⊕ g) = MC(f) + MC(g) holds unconditionally.
Two standard normalisation rules reduce the space of valid circuit topologies without loss of generality:
- (S1) Both linear inputs to each AND gate have a zero constant term.
- (S2) Both selection vectors specifying the linear inputs at each gate are non-zero.
These reductions permit exact decision via per-point Tseitin encodings.
Method
Bounds were established via exact SAT encodings, symmetry-reduced universe partitioning, and certified proof traces.
For MC(x1x2x3 ⊕ y1y2y3y4) = 5:
- Upper bound: The 5-AND circuit g1 = x1x2, g2 = g1x3, g3 = y1y2, g4 = y3y4, g5 = g3g4, with output out = g2 + g5, was verified across all 128/128 truth-table entries by two independent evaluators. CaDiCaL also identified an alternative 5-AND realization.
- Lower bound: Proving MC > 4 required establishing unsatisfiability at k = 4. The first-gate universe of (2^7 - 1)(2^7 - 2) / 6 = 2,667 affine equivalence classes was partitioned into six orbit cubes under the lifted GL(3,2) × GL(4,2) group action. The orbit sizes are 7, 105, 315, 35, 735, and 1470 (summing to 2,667), forming a verified complete cover.
- Proof verification: CaDiCaL 1.9.5 solved all six orbit cubes at k = 4 in 902 CPU seconds (~15 minutes wall-clock) and emitted non-binary DRAT traces. drat-trim checked and verified every trace on host AX162 (receipt ML-077). Uncubed k = 3 unsatisfiability was checked separately.
- Controls: Nine recall controls, including two planted 4-AND circuits matching size and budget constraints, were successfully recovered.
For the remaining direct-sum cells:
- Full enumeration over the first-gate universe of (2^n - 1)(2^n - 2) / 6 classes (651 classes at n = 6, 2,667 at n = 7, and 10,795 at n = 8) established unsatisfiability at k = 3.
- The 4-AND circuits for MC(x1x2x3 ⊕ y1y2y3) = 4 and MC(x1x2 ⊕ y1y2y3y4) = 4 were independently confirmed using a second SAT solver that verified k = 3 UNSAT and k = 4 SAT with replayed circuits.
Discussion
The instance MC(x1x2x3 ⊕ y1y2y3y4) is the smallest open direct-sum corridor where both component functions have multiplicative complexity strictly exceeding their algebraic degree minus one (both blocks have excess >= 1, with MC(y1y2y3y4) = 3). This setup yields an additive baseline of 5 and a potential defect of at most 1. The result proves that cross-block gate sharing cannot reduce the total count.
The SAT encodings use the formulation introduced by Calik, Turan, and Peralta (ePrint 2015/848, 2018/002; arXiv 2005.01778). The direct-sum cells resolved here lie outside the complete n <= 6 Boolean function census. While every tested benchmark is strictly additive, the general direct-sum conjecture for multiplicative complexity remains open.
For everyone — the takeaway
What this means
AND gates dominate the runtime and memory overhead of zero-knowledge proofs and secure multi-party computation. Knowing whether independent subroutines can secretly share non-linear gates is critical for building optimal cryptographic circuits.
These results show that independent monomial blocks cannot share AND gates to lower their combined cost. The symmetry-reduced SAT pipeline and certified proof traces demonstrate that exact complexity bounds can be verified past the limits of full truth-table classification.
Attribution and prior art
Prior art: Using standard methods from Calik–Turan–Peralta (ePrint 2015/848, 2018/002; arXiv 2005.01778), these specific direct-sum cells fall outside the n <= 6 census and appear to be new. The additivity conjecture remains open after three searches.
Register references
- Register Entry: MF-164
- Receipt artifacts: directsum/REPORT.md §5; wave1-directsum2/out/t12_upper.json, t10_main_k5.json, t11_orbit_*_k4.json, t14_cover.json, t10_cc3_k{3,4}.json, t10_a1_k{3,4}.json, satlib.py
- DRAT verification receipt: ML-077
- Prior art: Calik–Turan–Peralta (ePrint 2015/848, 2018/002; arXiv 2005.01778)
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 6 receipt files bundled (14 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.