Research · Papers · Direct sums, wedges and the p14 frontier · ML-077
Exact Multiplicative Complexity of x1x2x3 ⊕ y1y2y3y4
MC(x1x2x3 ⊕ y1y2y3y4) = 5
Published 2026-09-04
For everyone
Plain summary
The multiplicative complexity of a Boolean function is the minimum number of AND gates needed to compute it when XOR gates are free. This note determines the exact multiplicative complexity of the direct-sum function x1x2x3 ⊕ y1y2y3y4, which combines a 3-variable AND product and a 4-variable AND product on separate inputs.
The exact complexity is 5. Ruling out all candidate 4-AND circuits establishes that 4 multiplications cannot compute the function. Symmetries of the component monomials compress the 2,667 possible first-gate configurations into six representative cases. For each case, the CaDiCaL SAT solver produced an unsatisfiability proof certificate in DRAT format. The drat-trim checker independently verified every certificate, certifying the lower bound without gaps.
Result
For the direct-sum Boolean function f(x, y) = x1x2x3 ⊕ y1y2y3y4 on 7 variables over GF(2):
MC(x1x2x3 ⊕ y1y2y3y4) = 5
Six exhaustive first-gate symmetry orbit refutations verified via non-binary DRAT proofs certify the lower bound MC(x1x2x3 ⊕ y1y2y3y4) ≥ 5.
Setting and definitions
Let f: F_2^7 → F_2 be defined by f(x1, x2, x3, y1, y2, y3, y4) = x1x2x3 ⊕ y1y2y3y4. The multiplicative complexity MC(f) is the smallest integer k such that f can be computed by a straight-line program over (AND, XOR, NOT) containing k AND gates.
Under factor normalisation condition S1 (REPORT.md §2), affine constant terms in the linear inputs to the first multiplication gate are set to zero without loss of generality. The first AND gate computes M_1 N_1 for linear forms M_1, N_1 in F_2^7. The isomorphism class cls(M_1 N_1) is uniquely characterized by the 2-dimensional subspace span(M_1, N_1) in F_2^7.
The symmetry group preserving the component monomials mod Aff is G = GL(3,2) × GL(4,2), with order |G| = 168 × 20,160 = 3,386,880. The group acts block-diagonally on F_2^7 by phi(x, y) = (Ax, Dy) for A ∈ GL(3,2) and D ∈ GL(4,2).
Method
Determining MC(x1x2x3 ⊕ y1y2y3y4) = 5 combines symmetry reduction, Grassmannian orbit partitioning, and machine-checked SAT refutations:
- Symmetry invariance:
The block-diagonal action phi(x, y) = (Ax, Dy) preserves x1x2x3 mod Aff and y1y2y3y4 mod Aff. Verification across all 18 generators of G using t14_recall.py confirms that phi maps any valid k-AND circuit for x1x2x3 ⊕ y1y2y3y4 to another valid k-AND circuit for the same function.
- Cover partition:
The Grassmannian Gr(2, F_2^7) contains (2^7 - 1)(2^7 - 2) / 6 = 2,667 distinct two-dimensional subspaces. The script t02_orbits.py partitioned these 2,667 subspaces under the G-action into six orbits:
- Orbit [1,2,3]: size 7
- Orbit [1,8,9]: size 105
- Orbit [1,10,11]: size 315
- Orbit [8,16,24]: size 35
- Orbit [8,17,25]: size 735
- Orbit [9,18,27]: size 1,470
The orbit sizes sum to 7 + 105 + 315 + 35 + 735 + 1,470 = 2,667. The complete partition receipt is logged in out/t02_orbits.json and verified with cover_ok: true in out/t14_cover.json.
- DRAT proof generation and verification:
For each orbit representative, 4-AND circuit synthesis was encoded as a propositional satisfiability problem and solved with CaDiCaL 1.9.5 (--binary=false) on an AX162 host. Each run produced a non-binary DRAT refutation trace checked by drat-trim:
- orbit_1_2_3.drat: s VERIFIED (940,479 core lemmas, 27.9M resolution steps, 81.4s)
- orbit_1_8_9.drat: s VERIFIED
- orbit_1_10_11.drat: s VERIFIED
- orbit_8_16_24.drat: s VERIFIED
- orbit_8_17_25.drat: s VERIFIED
- orbit_9_18_27.drat: s VERIFIED
Verified unsatisfiability across all six orbits rules out all 4-AND circuits under factor normalisation S1, establishing MC(x1x2x3 ⊕ y1y2y3y4) ≥ 5. Combined with the achievable upper bound of 5, the exact complexity is 5.
Discussion
This entry closes MF-164 (ii) at tier FC(drat-verified). The audit row records a CONFIRMED verdict under the cost model AGL(n, 2) Orbits / Encodings.
The lower bound rests on the complete 2,667-subspace partition under the block-diagonal symmetry group GL(3,2) × GL(4,2) and the independent DRAT verification of refutations for all six orbit representatives.
For everyone — the takeaway
What this means
Evaluating independent sub-functions together does not automatically require the sum of their individual multiplication counts without proof. Computing x1x2x3 takes 2 multiplications and y1y2y3y4 takes 3 multiplications on their own, but proving that x1x2x3 ⊕ y1y2y3y4 cannot share operations across parts requires ruling out every potential shortcut.
This result proves that computing x1x2x3 ⊕ y1y2y3y4 strictly requires 5 multiplications. Symmetry reduces thousands of candidate circuit configurations to six cases, and automated SAT solvers provide independently checked proofs that no 4-multiplication circuit exists.
Register references
- Entry: ML-077 (MF-164 (ii))
- Scripts and receipts: wave1-directsum2/t02_orbits.py, out/t02_orbits.json, t14_recall.py, out/t14_cover.json, wave1-directsum2/run_5.sh, REPORT.md §2
- DRAT artifacts: /tmp/ds2_k4_cubes/*.drat.log, orbit_1_2_3.drat, orbit_1_8_9.drat, orbit_1_10_11.drat, orbit_8_16_24.drat, orbit_8_17_25.drat, orbit_9_18_27.drat via drat-trim
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 6 of 13 receipt files bundled (17 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.