Research · Papers · Exact answers in open problems · ML-093
Proof-system mismatch for the circulant weighing matrix cell CW(112,36)
DRAT resolution and RoundingSat cutting planes fail on CW(112,36) and known-nonexistent CW(n,36) for n ∈ {40, 44, 50, 56}.
Published 2026-09-06
For everyone
Plain summary
A circulant weighing matrix is a square grid of 0s, 1s, and -1s where each row cyclically shifts the row above it and distinct rows are orthogonal. The smallest undecided case in Strassler's classification is CW(112,36). We tested whether standard automated reasoning tools—DRAT-logging SAT solvers and pseudo-Boolean cutting-planes solvers—could decide if this matrix exists.
The solvers timed out on CW(112,36). They also failed on smaller test cases with known answers: they could not disprove four impossible instances (CW(40,36), CW(44,36), CW(50,36), and CW(56,36)) and could not construct the known solution CW(104,36). The failure is not raw problem size. The Boolean translation strips out algebraic properties that resolution and cutting-planes logic cannot reconstruct. Continuing search with this encoding is a dead end.
Result
Standard Boolean resolution and pseudo-Boolean cutting planes cannot decide the circulant weighing family CW(n,36). While CW(112,36) remains open mathematically, the direct CNF and pseudo-Boolean search pipeline is proved dead.
Benchmark results establish the proof-system mismatch:
- CW(112,36) resolution: DRAT runs timed out across monolithic searches (two runs at 5400 s) and quotient-ring contraction cubes (12 runs at 1200 s), stalling at 270-300 conflicts per second with zero search-space collapse.
- Negative resolution controls: The pipeline failed to refute known-nonexistent instances CW(n,36) for n ∈ {40, 44, 50, 56} within 300 s each.
- Negative pseudo-Boolean control: RoundingSat failed to refute known-nonexistent CW(40,36) within 240 s.
- Positive resolution control: The pipeline failed to find a satisfying assignment for known-existing CW(104,36) within 1800 s.
Setting and definitions
A circulant weighing matrix CW(n,k) is an n × n matrix W with entries in {0, 1, -1} satisfying W W^(T) = k I_n, where each row is the cyclic right-shift of the preceding row. The cell CW(112,36) is the smallest open case in Strassler's table.
The pipeline encodes circulant autocorrelation constraints over n ternary variables into CNF for CDCL/DRAT solvers and linear pseudo-Boolean constraints for RoundingSat. Contraction cubes partition the search space via projections onto quotient rings.
Method
Pipeline viability was evaluated by benchmarking against control instances of known status:
- Monolithic resolution: Two independent DRAT runs on full CW(112,36) at 5400 s each.
- Cubed resolution: Twelve sound contraction sub-cubes for CW(112,36) at 1200 s each, sustaining 270-300 conflicts per second with no clause-learning acceleration.
- Negative controls: DRAT refutation attempts on known-nonexistent CW(40,36), CW(44,36), CW(50,36), and CW(56,36) (300 s timeout each; zero refutations derived).
- Cutting-planes control: RoundingSat on known-nonexistent CW(40,36) (240 s timeout; no contradiction derived).
- Positive control: DRAT model search on known-existing CW(104,36) (1800 s timeout; no model found).
Run logs and ladder files reside in frontier/cwm/ (PROGRESS.box.log, status/*.json, invent_k*) and lane receipts WALL.md, invent/.
Discussion
CW(112,36) remains open, but allocating further compute to direct resolution or cutting-planes encodings is futile. Because the pipeline fails on small instances (n = 40, 44, 50, 56, 104), the bottleneck is an intrinsic proof-system mismatch rather than instance scale.
The viable path forward is an algebraic mod-16 / mod-28 contraction tower. Orbit censuses computed under MF-193 eliminate two of four mod-28 orbits through a 2-adic obstruction that Boolean encodings cannot detect.
For everyone — the takeaway
What this means
When a logic solver stalls on a hard math problem, adding compute rarely helps if the solver cannot express the problem's underlying structure. Our controls showed the solver could not resolve small test cases whose answers are already proven. The Boolean formulation discards algebraic rules the solver cannot rebuild. Settling CW(112,36) requires algebraic techniques, like modular contraction towers, rather than brute-force SAT resolution.
Attribution and prior art
Sources: Arasu, Gordon, Zhang 2021 · Tan 2026
Register references
- ML-093
- Box receipt:
frontier/cwm/(PROGRESS.box.log,status/*.json, ladder JSONs underinvent_k*) - Lane receipts:
WALL.md,invent/ - Related entry: MF-193
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 2 of 2 receipt files bundled (4 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.
- 2026-09-06The previously reported solver speedups applied only to these refuted cells and failed on live cases, including CW(40,36) and CW(56,36).
- 2026-09-06Independent verification certified the eight ruled-out cubes in MF-196 (4 live / 8 dead) and confirmed Gordon's CW(48,36) witness in one of 2,898 cubes. A calibration check on CW(56,36) proved 11 of 24 cubes UNSAT in <= 1 s, while 4 timed out at 1,800 s.
- 2026-09-06Correction (2026-09-06) to the ML-093 addendum: for the CW(56,36) twin, seven cubes timed out at 1,800 s instead of four (cubes 01, 02, 04, 07, 09, 10, 12), with 12 of 19 decided cubes verified in <= 1 s. The verification gate remains closed.