Machine-Verified Proofs

In mathematics, a proof is a chain of justifications that fully secures a statement. Normally, humans write down such proofs as text, and other humans read them and look for errors. In machine-verified proofs, this checking is taken over by a program. To do this, the proof must be formulated in a particularly strict language in which every single step follows from predetermined rules. The program then works through the chain from beginning to end and reports every point at which a step is not properly justified. Only once there is no objection left is the proof considered machine-verified.

Certainty that no reviewer can guarantee

Human review is good, but not perfect. A proof in a journal is often dozens of pages long and relies on theorems from other papers. Reviewers sometimes overlook gaps in the process. There have been cases where an error was only discovered years after publication. A program, on the other hand, does not accept any step that it cannot trace back to the basic rules. It also does not get tired and is not impressed by the author’s reputation.

The distinction between finding proofs and checking proofs is important. These programs mostly do not find anything on their own. They are inspectors, not inventors. A common misconception is that the computer proved the theorem. Usually, a human has written the proof in the formal language, and the machine has only confirmed that it is complete.

For AI systems, this is interesting for a second reason. Language models occasionally invent plausible-sounding nonsense. In the case of a mathematical claim, this can be clearly exposed with a checking program. You get a hard verdict: passed or not passed. Such unambiguous feedback is rare and therefore valuable.

From idea to formal code

First, the statement is translated. A sentence like “every natural number greater than one has a prime divisor” becomes a formal claim in the language of the checking system. This language looks more like program code than school mathematics. Then comes the proof, also written as code, built from many small steps and from theorems that were formalized earlier.

The core of the system is a very small checking program, often only a few thousand lines long. Only this core is allowed to decide whether a step is valid. Because it is so small, it can itself be examined thoroughly. Everything else builds on top of it. Well-known systems of this kind are called Lean, Coq, Isabelle, and HOL Light.

The price of this rigor is effort. A proof that fills one page on paper can, when formalized, result in hundreds of lines. This is because the text contains leaps such as “the analogous case follows” or “it is obvious that,” which the machine does not accept. Large undertakings such as the formalization of a modern proof therefore keep entire teams busy for months or years.

Math competitions, chip design, and railway control systems

In the news, machine-verified proofs mainly appear in connection with AI and mathematics. When a company announces that its model has solved problems from a math olympiad, a checking system is often behind it. The model proposes proofs, the system checks them, and only proposals that pass count. This way, the success cannot be talked up.

The same technique is used outside of mathematics for software and hardware. This is then called formal verification. Chip manufacturers use it to check computing circuits before they go into production. Control software for railways or airplanes is also secured this way, because testing alone can never cover all cases.

As a student, one is most likely to encounter this topic in reports about the mathematics library Mathlib. There, volunteers collect thousands of formalized theorems in the Lean system. A glance inside shows clearly how far the language of the machine is removed from that of a textbook.