MathCheck

Overview

MathCheck is a system which combines functionality from Boolean satisfiability (SAT) solvers and computer algebra systems (CAS) to verify conjectures in mathematics up to a finite bound and to search for counterexamples.

The SAT+CAS approach is particularly effective for combinatorial conjectures, as many conjectures in combinatorics reduce to a huge combinatorial search for which there are no known efficient algorithms. Using a SAT solver can make such searches tractable for many combinatorial conjectures, though relying on these solvers alone is not sufficient because they are not able to exploit combinatorial relationships known to mathematicians. On the other hand, computer algebra systems contain a storehouse of mathematical knowledge but typically lack the sophisticated combinatorial search engine of SAT solvers.

List of mathematical conjectures resolved

The aim of the MathCheck project is to develop a SAT+CAS system which combines the best of both worlds to find counterexamples or finitely verify conjectures in mathematics. To date the MathCheck project has achieved the following successes:

  • Verified the Ruskey–Savage conjecture up to order 5 for the first time
  • Verified the Norine conjecture up to order 6 for the first time
  • Verified that 35 is the smallest counterexample of the Williamson conjecture for the first time
  • Enumerated all Williamson matrices in orders divisible by 2 or 3 up to order 70 for the first time (with results available online)
  • Found over 100,000 new Williamson matrices in even orders
  • Found one previously undiscovered set of Williamson matrices in order 63
  • Found 8-Williamson matrices in all odd orders up to and including 35 for the first time (especially interesting since regular Williamson matrices don't exist in order 35)
  • Enumerated all complex Golay pairs up to length 25 (with publicly available results for the first time)
  • Verified the Craigen–Holzmann–Kharaghani conjecture that complex Golay pairs of length 23 do not exist

Additionally, a component of the MathCheck project is designing custom-tailored SAT solvers using the programmatic SAT paradigm, currently specializing in combinatorial matrix problems defined via periodic and aperiodic correlation. Both MathCheck and MathCheck2 are open source and released under the MIT licence.