Automatic Concept Formation in Pure Mathematics

Simon Colton, Alan Bundy, Toby WalshIJCAI 1999 · OpenReview

Abstract

The HR program forms concepts and makes conjectures in domains of pure mathematics and uses theorem prover OTTER and model generator MACE to prove or disprove the conjectures. HR measures properties of concepts and assesses the theorems and proofs involving them to estimate the interestingness of each concept and employ a best first search. This approach has led HR to the discovery of interesting new mathematics and enables it to build theories from just the axioms of finite algebras.

Introduction

Mathematical discovery has long been considered a hallmark of human creativity. While early AI systems like Lenat’s AM (1976) demonstrated that machines could "re-invent" fundamental concepts such as prime numbers, they often lacked the rigor to formally prove their findings or systematically identify counterexamples. The HR program (named after mathematicians Hardy and Ramanujan) seeks to bridge this gap by automating the "spiral of creativity." It addresses the challenge of building an autonomous system capable of generating definitions, evaluating their utility through heuristics, identifying patterns, and validating those patterns using formal logic.

Methodology

The HR program operates through a cycle of concept formation, conjecture making, and formal validation, integrated with external tools: the theorem prover OTTER and the model finder MACE.

HR begins with basic axioms (e.g., group theory) and applies eight production rules—such as exists, forall, and conjunct—to derive increasingly complex concepts. For instance, it can derive the concept of "Abelian groups" by combining group operation axioms with rules that check for commutativity.

Figure 1: The construction path for the concept of Abelian groups using production rules.

To manage the potential combinatorial explosion of definitions, HR employs a best-first search guided by measures of "interestingness." These include parsimony (preferring smaller data tables), complexity (preferring simpler definitions), and novelty (valuing unique categorizations).

The Discovery Cycle

When HR identifies that two distinct definitions describe the same set of objects, it generates a conjecture. This conjecture is then sent to OTTER for proof. If OTTER fails, HR utilizes MACE to search for a counterexample. Any new model found by MACE is added to HR’s database, providing empirical evidence that prevents the system from repeating false conjectures and ensuring that the generated models themselves possess interesting properties.

Results and Discussion

HR has demonstrated significant success in both re-inventing established mathematics and discovering novel concepts.

Discovery of New Mathematics

The system discovered several previously unknown integer sequences, eight of which were accepted into the Online Encyclopedia of Integer Sequences (OEIS). A notable example is "refactorable numbers"—integers where the count of divisors is itself a divisor. In group theory, HR successfully re-invented 9 out of 20 standard textbook definitions, including centers of groups and cyclic groups.

Search Performance

A key finding is the efficacy of heuristic search over brute force. As shown in the comparative analysis of theory formation sessions, a best-first search (B) consistently yields theorems with a higher "Average Proof Length" compared to random (R) or exhaustive (E) searches. This suggests that HR's heuristics effectively steer the system toward deeper, more mathematically significant truths rather than trivial identities.

Table 1: Performance metrics across different mathematical domains and search heuristics.

Conclusion

The HR program represents a significant step toward autonomous mathematical discovery. By integrating model generation with theorem proving, it creates a robust feedback loop that mimics human mathematical intuition. While current limitations include the complexity thresholds of external provers and a lack of inductive reasoning for deep number theory, future work aims to utilize previously proved theorems as "lemmas" to tackle more complex open conjectures.

Summary updated

Abstract

The HR program forms concepts and makes conjectures in domains of pure mathematics and uses theorem prover OTTER and model generator MACE to prove or disprove the conjectures. HR measures properties of concepts and assesses the theorems and proofs involving them to estimate the interestingness of each concept and employ a best first search. This approach has led HR to the discovery of interesting new mathematics and enables it to build theories from just the axioms of finite algebras.
BibTeX
@inproceedings{colton1999automatic,
  author = {Simon Colton and Alan Bundy and Toby Walsh},
  title = {{Automatic Concept Formation in Pure Mathematics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=SJZS2Xf_bS},
}
Figure