TL;DR
This paper revisits and reimplements Fajtlowicz's "Dalmatian heuristic" for automated mathematical conjecture generation. The authors demonstrate that this general-purpose heuristic, when combined with existing theorems, can produce novel and significant mathematical statements without requiring domain-specific expertise, suggesting a path towards more intelligent machines.
What Problem Does This Paper Address?
The paper tackles the challenge of automating mathematical discovery, a cornerstone of intelligence. While significant progress has been made in automated theorem proving, the generation of new mathematical knowledge (conjectures) has been less explored. The authors aim to revive and extend Fajtlowicz's Dalmatian heuristic, a method for generating plausible mathematical statements based on limited data, and demonstrate its effectiveness in various mathematical domains. They highlight the potential for such programs to act as a central feature in intelligent systems, assisting human researchers by proposing new avenues of inquiry.
Methods
The core of the paper lies in the reimplementation of Fajtlowicz's Dalmatian heuristic. This heuristic operates by generating algebraic expressions involving numerical invariants of objects. These expressions are then used to form potential inequalities (conjectures) that are tested against a database of known objects. A conjecture is accepted if it passes two tests:
- Truth Test: The conjecture must be true for all currently stored objects.
- Significance Test: The conjecture must provide a "better" bound for at least one object than any previously stored conjecture. This embodies the "Principle of the Strongest Conjecture."
The authors also introduce an enhancement: incorporating existing theorems into the process. This ensures that generated conjectures are not merely restatements of known results, but rather advance existing mathematical knowledge. Their program, "Conjecturing," is built as a package within the Sage open-source mathematical software system.
Datasets
The paper does not explicitly list or introduce formal datasets in the machine learning sense. Instead, it relies on:
- A collection of objects: These can be of various types (graphs, numbers, matrices) and are added to the program's knowledge base. Counterexamples to existing conjectures are also added as objects.
- Pre-defined graph generators: For graph theory experiments, the authors utilize Brendan McKay's
gengprogram to generate a stream of graphs of increasing size.
The key idea is that the program can operate with a limited number of examples, and the "dataset" grows organically as new objects (including counterexamples) are added.
Key Insights and Ideas
- Domain-agnostic discovery: The Dalmatian heuristic is remarkably general and can be applied to diverse mathematical domains (graph theory, number theory, matrix theory) without requiring specialized knowledge of those fields.
- Power of limited data: Plausible and useful conjectures can be generated from surprisingly small sets of examples.
- Advancing existing knowledge: A crucial aspect is the program's ability to produce conjectures that go beyond current understanding, addressing open questions and offering new insights.
- Intelligence as conjecture and revision: The authors propose that the ability to make guesses, learn from errors (counterexamples), and revise hypotheses is a fundamental aspect of intelligence.
- The role of existing theorems: Incorporating known theorems is vital for ensuring that generated conjectures are novel and contribute new knowledge.
Key Results
The paper presents several experimental results, particularly in graph theory:
- The program successfully generated conjectures for the domination number of graphs.
- In one experiment, the program generated the conjecture that the domination number of a graph is no more than its matching number. This is a known, provable result, but the program discovered it without prior knowledge.
- After removing known bounds from the input, the program generated three new conjectures, two of which were known to be true, and one was found to be false by a human researcher (Ryan Pepper).
- After incorporating a counterexample, the program generated a new set of conjectures, some of which were later identified as false by experts, demonstrating the iterative nature of discovery and the need for robust counterexample finding.
Limitations and Future Work
- Counterexample finding: While the program can generate conjectures, finding counterexamples to potentially false conjectures often requires human intervention or specialized automated tools. The authors suggest the need for an "intelligent" counterexample-finder.
- Scalability: The generation of expressions can become computationally intensive as complexity increases.
- Future Work: The authors envision a massive, long-term project to codify all properties, invariants, graphs, and theorems in graph theory literature. This would enable their program to produce simpler conjectures than any human could, which are true for all published graphs and improve upon all known theorems, potentially ushering in a new era of mathematical research. They also plan to advance research on bounds for the independence number of graphs.
Summary updated