Research · Papers · Direct sums, wedges and the p14 frontier · ML-088
Search scale barrier for unrestricted 6-AND XAG decision of M_2(F_2)
Deciding 6-AND unrestricted XAG for M_2(F_2) requires refuting a CNF with 155,669 clauses and 33,345 variables; open at k=6.
Published 2026-09-04
For everyone
Plain summary
Multiplying two 2-by-2 matrices of zeros and ones is a classic problem in computer science. In digital logic, this calculation uses two types of components: XOR gates for addition and AND gates for multiplication. Seven AND gates are known to be enough, but whether six can do the job remains an open mathematical question.
To check if a 6-AND circuit exists, researchers convert the problem into a Boolean satisfiability (SAT) instance for automated solvers. This yields a constraint system with 155,669 clauses and 33,345 true-or-false variables. Standard solvers stall on this instance, unable to find a working circuit or prove that none exists. The problem remains open and serves as a concrete benchmark for automated reasoning tools.
Result
The existence of an unrestricted 6-AND XOR-AND graph (XAG) circuit computing 2x2 matrix multiplication over F_2, denoted M_2(F_2), is open at k=6. Deciding existence or non-existence requires resolving a CNF formula with 155,669 clauses and 33,345 variables across 256 truth-table evaluation points. The subfield F_4 invariant 2-plane filtration bounds the multiplicative complexity qMC(M_2) to [6, 7], but the exact value at k=6 remains undecided.
Setting and definitions
The target function is the bilinear map for matrix multiplication in M_2(F_2), mapping 8 input variables (two 2x2 matrices over GF(2)) to 4 output variables.
An unrestricted XAG circuit for this map consists of 6 sequential 2-input AND gates fed by arbitrary linear (XOR/XNOR) combinations of primary inputs and intermediate gate outputs, terminated by 4 affine output combinators. The multiplicative complexity qMC(M_2) is the minimum number of AND gates required to evaluate M_2(F_2) over all 256 binary input vectors. The decision problem is formulated as a propositional CNF formula with 33,345 Boolean variables and 155,669 clauses.
Method
The CNF formula encoding the synthesis constraints was generated with programs/corridor-sweep-20260901/wave2-m2-closure/multi_satlib.py, producing the instance file programs/corridor-sweep-20260901/wave2-m2-closure/m2_k6.cnf.
The encoding constrains 6 sequential AND gates driven by linear combinations of 8 inputs and earlier gate outputs, requiring their affine combinations to match M_2(F_2) on all 256 truth-table assignments. Standard CDCL solver heuristics exhibit heavy-tailed runtimes on this formula. Complete resolution requires GL(2, F_2) x GL(2, F_2) symmetry cubing or distributed DRAT-certified proof generation on remote compute infrastructure such as AX162.
Discussion
The register records the status of this problem as BENCHMARK CERTIFIED / OPEN AT k=6.
Although the subfield F_4 invariant 2-plane filtration bounds qMC(M_2) to [6, 7], SAT solvers have generated neither a satisfying circuit assignment nor a certified refutation across the 2^{33,345} state space. Complete refutation remains open, requiring dedicated proof-logging pipelines or symmetry reduction to circumvent the CDCL search barrier.
For everyone — the takeaway
What this means
Finding the minimum number of basic multiplication steps for 2-by-2 binary matrices is a foundational benchmark in logic synthesis. We know seven AND gates work, but determining whether six are sufficient requires searching an enormous logical space. Because standard automated solvers stall on this 33,345-variable formula, it provides a certified test case for advanced SAT solvers, symmetry-breaking methods, and distributed proof systems.
Register references
- ML-088
- programs/corridor-sweep-20260901/wave2-m2-closure/multi_satlib.py
- programs/corridor-sweep-20260901/wave2-m2-closure/m2_k6.cnf
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 1 of 2 receipt files bundled (2 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.