MATHCHECK: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers

Edward Zulkoski, Vijay Ganesh, Krzysztof Czarnecki

Introduction

In the field of automated reasoning, researchers often face a trade-off between search efficiency and mathematical expressiveness. SAT and SMT solvers are world-class at navigating massive, complex logic spaces to find solutions or proofs, yet they struggle to "understand" high-level mathematical concepts. For instance, encoding a property like "is this graph Hamiltonian?" into raw Boolean logic is notoriously difficult and computationally inefficient.

Conversely, Computer Algebra Systems (CAS) like Maple or Sage possess deep knowledge of mathematical structures and can perform complex symbolic computations with ease. However, they lack the robust search capabilities required to find counterexamples to open conjectures in large state spaces. MATHCHECK is a hybrid "SAT+CAS" system designed to bridge this gap by embedding the domain-specific power of a CAS directly into the search loop of a SAT solver.

The MATHCHECK Architecture

The MATHCHECK system functions similarly to a "DPLL(T)" SMT solver, but where the "Theory" (T) is an entire CAS. This allows mathematicians to use the CAS to define complex predicates while the SAT solver handles the heavy lifting of the search.

The MATHCHECK architecture showing the interaction between the SAT solver and the CAS interface.

As illustrated in the architecture diagram, the process follows a specific workflow:

  1. Input: A mathematical conjecture is expressed as a combination of SAT predicates (simple logic) and CAS predicates (code written in Python/Sage).
  2. The Inner Loop: As the SAT solver (Glucose) searches for a counterexample, it periodically queries the CAS (SAGE) with partial assignments.
  3. Learning: If the CAS determines that a partial assignment violates a mathematical property, it generates "learned clauses"—mathematical lemmas—that are fed back into the SAT solver to prune large sections of the search tree.

Case Study: Hypercube Conjectures

The authors evaluated MATHCHECK on a specific challenge in graph theory: verifying Conjecture 1 (Ruskey and Savage). This conjecture posits that any matching in a $d$-dimensional hypercube ($Q_d$) can be extended to a Hamiltonian cycle.

A 3-dimensional hypercube ($Q_3$) illustrating the complex vertex and edge relationships MATHCHECK must analyze.

Testing the system on dimensions $d=3, 4,$ and $5$ demonstrated the power of the hybrid approach. While a pure SAT encoding of Hamiltonian cycles would require a massive, complex set of constraints, writing a predicate to check for a Hamiltonian cycle in SAGE takes only a few lines of Python code.

Key Results and Insights

MATHCHECK successfully verified the Ruskey and Savage conjecture for the 5-dimensional hypercube ($Q_5$), a feat previously out of reach for standard solvers. Previous known results had only reached $d=4$.

Key performance factors included:

  • Efficiency: For $Q_5$, the system completed the verification in just under 8 hours on a standard laptop, performing approximately 348,150 CAS predicate checks. For lower dimensions ($d \leq 4$), the system finished in under 20 seconds.
  • Search Space Reduction: The authors utilized mathematical insights, such as focusing only on "maximal forbidden matchings," to reduce the number of cases the SAT solver had to check.
  • Symmetry Breaking: By exploiting the inherent symmetry of hypercubes, the system could fix certain variables (e.g., ensuring a specific vertex remains unmatched) to further speed up the search without losing generality.

Limitations and Future Work

Despite the success with $Q_5$, the authors note that $Q_6$ and higher dimensions remain likely out of reach without discovering further mathematical lemmas to prune the search space more aggressively.

Future development for MATHCHECK involves integrating it with proof-producing solvers (like VeriT) to generate independently verifiable "certificates" of results. Additionally, the authors intend to extend the system to other domains, such as number theory and topology, where CAS systems already possess robust built-in libraries.

Summary updated

Abstract

We present a method and an associated system, called MathCheck, that embeds the functionality of a computer algebra system (CAS) within the inner loop of a conflict-driven clause-learning SAT solver. SAT+CAS systems, a la MathCheck, can be used as an assistant by mathematicians to either counterexample or finitely verify open universal conjectures on any mathematical topic (e.g., graph and number theory, algebra, geometry, etc.) supported by the underlying CAS system. Such a SAT+CAS system combines the efficient search routines of modern SAT solvers, with the expressive power of CAS, thus complementing both. The key insight behind the power of the SAT+CAS combination is that the CAS system can help cut down the search-space of the SAT solver, by providing learned clauses that encode theory-specific lemmas, as it searches for a counterexample to the input conjecture (just like the T in DPLL(T)). In addition, the combination enables a more efficient encoding of problems than a pure Boolean representation. In this paper, we leverage the graph-theoretic capabilities of an open-source CAS, called SAGE. As case studies, we look at two long-standing open mathematical conjectures from graph theory regarding properties of hypercubes: the first conjecture states that any matching of any d-dimensional hypercube can be extended to a Hamiltonian cycle; and the second states that given an edge-antipodal coloring of a hypercube, there always exists a monochromatic path between two antipodal vertices. Previous results have shown the conjectures true up to certain low-dimensional hypercubes, and attempts to extend them have failed until now. Using our SAT+CAS system, MathCheck, we extend these two conjectures to higher-dimensional hypercubes. We provide detailed performance analysis and show an exponential reduction in search space via the SAT+CAS combination relative to finite brute-force search.
BibTeX
@inproceedings{zulkoski2016mathcheck,
  author = {Edward Zulkoski and Vijay Ganesh and Krzysztof Czarnecki},
  title = {{MATHCHECK: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure