Rewrite Systems as a Foundation for Automated Mathematical Discovery

The mathematical community has largely accepted that symbolic manipulation is a solved problem—a utility, not a frontier. This assumption is wrong, and it costs us discoveries.

Rewrite systems occupy a peculiar position in formal mathematics. They are simultaneously fundamental and overlooked. A rewrite system is simply a set of rules that transform expressions into equivalent forms. When you simplify an algebraic fraction, apply a trigonometric identity, or normalize a logical formula, you are executing a rewrite system. Yet we treat rewriting as infrastructure rather than as a primary object of study. We build theorem provers and computer algebra systems on top of rewrite systems without asking whether the systems themselves might reveal mathematical structure we've missed.

The oversight runs deeper than mere neglect. Most mathematicians think of rewriting as directional—a means to an end, a way to reach a canonical form. But rewrite systems encode something more fundamental: they capture the equivalence relations that structure a mathematical domain. When we specify that a + b = b + a, we are not merely stating a convenience for simplification. We are declaring that commutativity is a constitutive property of addition. The rules we choose determine what we can discover.

Consider what happens when you reverse this perspective. Instead of asking "how do I simplify this expression," ask "what expressions are equivalent under these rules?" This shift transforms rewriting from a computational tool into an investigative instrument. A rewrite system becomes a lens through which to examine the hidden symmetries and redundancies in a formal language. Automated systems can now explore the space of all possible rewrite sequences, not to reach a predetermined normal form, but to map the topology of equivalence classes themselves.

This matters because mathematical discovery often hinges on recognizing that two seemingly different objects are, under the right transformation, identical. The history of mathematics is littered with breakthroughs that amount to finding the right rewrite rules. Fourier analysis emerged from recognizing that periodic functions could be rewritten as infinite sums of sines and cosines. Category theory gained power by rewriting morphisms and objects in terms of commutative diagrams. In each case, the rewrite system was not a mere notational convenience—it was the discovery.

Automated systems working with rewrite systems can operate at a scale human mathematicians cannot. They can systematically explore vast spaces of possible transformations, identify unexpected equivalences, and surface patterns that emerge only when thousands of rewrite sequences are analyzed in aggregate. The system does not "understand" mathematics in the human sense, but it can detect regularities in the structure of rewrite spaces that humans would never notice through manual exploration.

The practical barrier has always been specification. Defining a rewrite system requires precision: the rules must be unambiguous, terminating (or at least well-behaved), and complete enough to be interesting. But this is precisely where formal methods and automated reasoning have matured. We now have the tools to specify, verify, and explore rewrite systems with rigor. The infrastructure exists. What remains is the conceptual shift: recognizing that rewrite systems are not merely servants of mathematics, but potential sources of mathematical insight.

There is a secondary benefit that deserves mention. Rewrite systems are inherently compositional. Small, well-defined rule sets can be combined to create larger systems. This modularity mirrors how mathematics itself is built—from axioms to theorems to theories. An automated system that learns to compose rewrite rules effectively is learning something about how mathematical knowledge itself is structured.

The question is not whether rewrite systems can be automated. They already are. The question is whether we will treat them as mere computational infrastructure or recognize them as a frontier for discovery. The difference between these two postures determines whether automated mathematics remains a tool for verification or becomes a genuine engine for finding truths we did not know to seek.