🤖 AI

Case study: proving sqrt(2) irrational with LPTP and an LLM

This paper presents a case study demonstrating how an LLM, guided by basic logic programming definitions and verified by the LPTP theorem prover, can successfully generate a complete, human-readable formal proof of the irrationality of the square root of 2.

Original authors: Fred Mesnard, Étienne Payet, Wim Vanhoof

Published 2026-07-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Fred Mesnard, Étienne Payet, Wim Vanhoof

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery that has baffled humans for over two thousand years: Is the square root of 2 a "rational" number? In the world of math, a rational number is like a perfect fraction, a clean slice of a pie (like 3/4 or 5/2). An irrational number is a messy, never-ending decimal that can never be written as a simple fraction. The square root of 2 is the length of the diagonal of a square with sides of length 1, and ancient mathematicians proved it is messy—it cannot be a fraction.

Now, imagine you have two very different tools to help you solve this. The first is a super-strict, robotic referee called LPTP. It speaks a very precise, logical language (based on Prolog) and will only accept a proof if every single step is mathematically perfect. If you make even a tiny mistake, it slams the gavel and says, "Nope, invalid." The second tool is a Large Language Model (LLM), which is like a super-smart, creative student who has read almost everything ever written. This student is great at guessing the next step in a story or a math problem, but sometimes it "hallucinates," making up facts that sound good but are actually wrong.

The big question for scientists today is: Can we team up these two? Can we let the creative student do the heavy lifting of writing the proof, while the strict referee checks every single sentence to make sure the student isn't lying? This paper explores exactly that partnership, using the ancient mystery of the square root of 2 as the test case.

The Great Proof-Checking Team-Up

In this paper, the authors set out to see if they could use a modern AI (specifically, a model called Claude) to help prove that the square root of 2 is irrational, but with a twist: the proof had to be written in a very specific, strict format that the robotic referee (LPTP) could understand and verify. They didn't just want the AI to say "it's true"; they wanted the AI to write the actual step-by-step logic, which the referee would then grade.

The story starts with a simple idea. To prove the square root of 2 is irrational, you usually assume the opposite: that it is a fraction made of two whole numbers, $p$ and $q$ , that don't share any common factors (they are "coprime"). If you do the math, you eventually run into a contradiction where both numbers must be even, which means they do share a factor (2). This breaks the rule that they were coprime, proving the original assumption was wrong.

The authors tried to get the AI to write this proof in the strict language of LPTP. At first, the AI was like a student who knows the story but can't write the essay in the required format. It would try to jump steps or make logical leaps that the referee wouldn't accept.

Here is where the teamwork happened. The authors set up a feedback loop:

The AI tries to write a proof step.
The referee (LPTP) checks it.
If the referee finds a mistake, it points out the exact line where the logic broke.
The authors show that error to the AI.
The AI tries again, fixing the specific error.

This process was like a game of "hot and cold." The referee didn't just say "wrong"; it said, "You made a mistake in step 4," allowing the AI to correct its course.

The Results: A Partial Victory

The experiment was a success, but with some caveats. The AI was able to prove many of the smaller, easier parts of the puzzle on its own. For example, it successfully proved that "if a number is even, its square is even" or that "2 times a number is even." The authors call these "lemmas" (small helper proofs). The AI got these right, sometimes even coming up with new helper ideas that the humans hadn't thought of.

However, for the trickiest part of the proof—the specific logic showing why the square root of 2 cannot be a fraction—the AI got stuck. It couldn't quite find the right path on its own. So, the human authors had to step in and give the AI a "hint" or even write the main structure of the proof themselves, asking the AI to fill in the smaller gaps.

In the end, they produced a complete, formal proof that the square root of 2 is irrational. This proof was partially written by the AI and fully checked by the robot referee. The referee gave it a passing grade, confirming that the logic was sound.

What This Means

The paper doesn't claim that AI can now solve all math problems on its own. In fact, the authors explicitly show that the AI cannot do it alone; without the human guidance and the strict checking of the referee, the AI would likely have produced a fake or broken proof.

Instead, the paper suggests a new way of working: AI as a draft writer, humans as editors, and formal tools as the fact-checkers. The AI is fast and creative, generating ideas and filling in details, while the formal tool (LPTP) acts as an unblinking eye that catches hallucinations and errors.

The authors also tested other automated math tools (called ATPs) to see if they could do the job faster. These tools were fast and free, but they produced proofs that were hard for humans to read and couldn't be easily added to the library of verified math. The AI approach, while slower and requiring human help, produced proofs that were readable and could be safely stored for future use.

In short, this paper shows that we don't need to choose between human intuition and machine precision. By letting the AI do the heavy lifting of drafting and the strict tools do the grading, we can build a system where AI helps us prove complex mathematical truths, as long as we keep a human in the loop to steer the ship and a strict referee to check the map. The square root of 2 remains irrational, but now we have a new, collaborative way to prove it.

Technical Summary: Case Study Proving $\sqrt{2}$ Irrational with LPTP and an LLM

Problem Statement
The paper addresses the challenge of formally proving that the square root of 2 is irrational within the context of Logic Programming (LP). Specifically, the authors aim to prove that no two coprime natural numbers $p$ and $q$ exist such that $p^2 = 2q^2$ . While this is a classical mathematical result, standard resolution-based logic programming engines (like Prolog) cannot provide a negative answer to the corresponding query because the search space over natural numbers is infinite. The authors seek to bridge this gap by using the LPTP (Logic Program Theorem Prover) system to generate a formal proof and evaluating the extent to which a Large Language Model (LLM) can assist in constructing this proof.

Methodology
The authors employ a hybrid approach combining the LPTP formal verification system with an LLM (specifically Claude Opus 4.5 from Anthropic).

Formal Framework (LPTP):
- LPTP is used to verify properties of logic programs based on first-order logic and Clark's completion.
- The system distinguishes between success, failure, and termination of predicates using specific operators ( $S$ , $F$ , $T$ ) and supports induction schemas for recursive predicates.
- The proof language is based on natural deduction, ensuring human readability.
- The authors define the problem using pure Prolog predicates for natural numbers (Peano arithmetic), addition, multiplication, and GCD.
LLM Integration Strategy:
- In-Context Learning: The LLM is provided with the LPTP user manual (PDF) and two basic libraries (Peano numbers and lists) containing Prolog code and existing proofs.
- Iterative Feedback Loop: The authors submit lemmas to the LLM in LPTP syntax (or natural language). The LLM generates a proof attempt, which is immediately fed into the LPTP proof checker.
- Error Correction: If the LPTP checker rejects the proof, it reports the first incorrect derivation step. This specific error is fed back to the LLM to refine the proof.
- Human Oversight: A human developer manages the order of lemmas, decides when to abandon unproductive loops, and provides high-level hints or the proof structure for difficult steps.
Auxiliary Tools:
- The authors also utilized off-the-shelf First-Order Logic (FOL) Automated Theorem Provers (ATPs) like Vampire and E by translating LPTP axioms into FOF syntax. These were used to verify lemmas independently, though their resolution-based proofs could not be directly integrated into LPTP's natural deduction framework.

Key Contributions and Results

Proof Construction: The team successfully constructed a complete, machine-checked formal proof of the irrationality of $\sqrt{2}$ in LPTP. The proof was partially generated by the LLM and fully validated by the LPTP checker.
Lemma Generation:
- The LLM successfully proved several auxiliary lemmas directly (e.g., $2^2=4$ , properties of even/odd numbers) or after a few iterations of error correction (e.g., simplification lemmas).
- For the most complex lemma, evenpp:evenp (proving that if the square of a number is even, the number itself is even), the LLM initially failed. The authors provided a natural language hint outlining the proof by cases (even vs. odd), after which the LLM successfully generated the formal proof.
- The main theorem (sqrt2:irrational) required the authors to provide the proof skeleton; the LLM then filled in the necessary steps and auxiliary lemmas.
ATP Comparison: While ATPs could prove 9 out of 12 lemmas in the final version, they failed to prove the main theorem within the 20-second timeout, likely due to the expanded search space. Crucially, ATP proofs could not be directly converted into the natural deduction proofs required by LPTP.
Dependency Management: The paper details the dependency graph of the lemmas, showing how the LLM's ability to prove simple properties (like nat:natsquare or sqr2:4) was essential for proving higher-level properties.

Significance and Claims
The authors claim this work represents one of the first interactions between LPTP and an LLM. Their primary contribution is demonstrating a semi-automated workflow where:

The Proof Checker is Central: The LPTP checker acts as the critical filter against LLM hallucinations. It provides precise feedback (the first incorrect step), enabling the LLM to self-correct effectively.
Complementary Roles: ATPs are fast and local but produce proofs in a format (resolution/superposition) incompatible with LPTP's natural deduction. LLMs, guided by the checker, can generate proofs in the correct format, though they require human guidance for complex structural steps.
Feasibility for LP: The study validates that LLMs can be effectively integrated into the verification of Logic Programming properties, provided a rigorous proof-checking loop is in place.

The paper concludes modestly, noting that while the LLM could not generate the entire proof structure autonomously for the main theorem, it successfully handled the granular logical steps once the structure was defined. This paves the way for future AI-enhanced approaches to proving Prolog properties, with the authors planning to evaluate this combination on a broader set of verification problems.

The Great Proof-Checking Team-Up

The Results: A Partial Victory

What This Means

Technical Summary: Case Study Proving 2\sqrt{2}2​ Irrational with LPTP and an LLM

More like this

Technical Summary: Case Study Proving $\sqrt{2}$ Irrational with LPTP and an LLM