💻 computer science

Tao's Equational Proof Challenge Accepted (Technical Report)

This paper introduces Krympa, a proof minimization tool that successfully reduces Terence Tao's 62-step equational proof to 20 steps and significantly compresses other complex proofs by combining brute force, heuristics, and multiple automated provers.

Original authors: Lydia Kondylidou, Jasmin Blanchette, Marijn J. H. Heule

Published 2026-05-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lydia Kondylidou, Jasmin Blanchette, Marijn J. H. Heule

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 trying to solve a massive, tangled knot of string. A super-fast robot (called Vampire) found a way to untie it, but it took 62 complicated moves to do so. The moves were so technical and jumbled that even a human mathematician, Fields Medalist Terence Tao, looked at the robot's solution and said, "This is too messy. Can anyone find a cleaner, shorter way to untie this knot?"

This paper is the story of how a team of researchers built a new tool called Krympa (which sounds like "crumple" or "compress") to do exactly that. They didn't just untie the knot; they found a way to do it in just 20 moves.

Here is how they did it, explained with simple analogies:

1. The Problem: The Robot's "Brute Force" Solution

The original robot, Vampire, works like a person trying to solve a maze by running down every single path until they hit a dead end. It eventually finds the exit, but the path it took is full of backtracking, dead ends, and unnecessary steps. In the math world, this resulted in a 62-step proof that was impossible for a human to read or understand.

2. The New Tool: The "Proof Minimizer" (Krympa)

The researchers built Krympa, a tool that acts like a smart editor or a chef refining a recipe. Instead of accepting the robot's messy 62-step recipe, Krympa breaks the problem down, tries different cooking methods, and reassembles the best parts into a shorter, tastier dish.

Krympa uses two different "chefs" (provers):

Vampire: The brute-force robot that is great at finding any solution.
Twee: A specialized chef that is better at finding elegant, structured solutions for this specific type of math problem (equations).

3. The Strategy: The "Mix-and-Match" Method

Krympa doesn't just pick one chef. It uses a clever three-step strategy to shrink the proof:

Step A: Break it Down (The Deconstruction)
Imagine the 62-step proof is a long chain of dominoes falling. Krympa stops the chain and looks at each domino. It asks, "Do we really need this specific domino to make the next one fall? Or is there a shorter way to get here?" It breaks the long chain into smaller, independent chunks called lemmas (which are just mini-proofs).
Step B: Try Different Angles (The Re-Proofing)
For each chunk, Krympa tries to prove it again using three different "lenses":
1. Big-Step: Can we prove this chunk from scratch using only the original rules?
2. Small-Step: Can we prove it using the original rules plus the smaller chunks we already solved?
3. Abstracted: Can we prove a simplified version of the chunk (like replacing a complex shape with a simple circle) and then use that to solve the real thing?
It runs both Vampire and Twee on these versions. If Twee finds a 3-step solution where Vampire needed 10, Krympa keeps the 3-step version.
Step C: Reassemble the Puzzle (The Reconstruction)
Once it has the shortest possible versions of all the chunks, Krympa tries to stitch them back together. It acts like a puzzle master, trying different combinations of "departure points" (where to start) and "arrival points" (where to end) to see which path creates the shortest total chain.

4. The Results: From Messy to Masterpiece

When they applied this to Tao's challenge:

Original: 62 steps (Vampire's messy solution).
New: 20 steps (Krympa's optimized solution).
- 13 of those steps came from the elegant chef (Twee).
- 7 came from the brute-force robot (Vampire).

But they didn't stop there. They tested Krympa on 1,431 other math problems from the same project.

One problem that took 151 steps was shrunk down to just 10 steps.
On average, they reduced the length of proofs by about 30% to 50%.

5. Why This Matters

Before this, automated math proofs were often like a "black box"—the computer said "Yes, it's true," but the explanation was a wall of text that no human could read.

Krympa changes the game by making the proof human-readable. It's like taking a 62-page legal contract written in confusing jargon and rewriting it into a clear, 20-page summary that a regular person can actually understand. The researchers showed that you don't have to sacrifice speed to get clarity; you can have both.

In short: They built a tool that takes a robot's messy, overly complicated math solution, breaks it into pieces, re-solves the pieces using smarter methods, and stitches them back together into a short, elegant proof that humans can finally read and appreciate.

Technical Summary: Tao's Equational Proof Challenge Accepted

Problem Statement
The paper addresses a challenge posed by Fields medalist Terence Tao within the context of the Equational Theories Project. The project explores relations between equational theories of magmas (algebraic structures with a single binary operation). Specifically, Tao challenged the community to find an alternative, more intelligible proof for the implication $650 \implies 448$ . The original proof, generated by the Vampire superposition prover, consisted of 62 inference steps. While logically valid, this proof was deemed "unintelligible" due to its complexity and length. The goal was to produce a shorter, human-readable proof using any means—human, semi-automated, or automated.

Methodology
The authors introduce Krympa, a proof minimization tool implemented in Rust, OCaml, and Python. The tool's core strategy involves "mixing and matching" proofs generated by two distinct automatic theorem provers: Vampire (a superposition-based prover) and Twee (an equational prover based on unfailing completion). The methodology proceeds through four main phases:

Conversion to Direct Proofs: Vampire typically generates proofs by refutation (deriving a contradiction from negated conjectures). Krympa first transforms these refutational proofs into direct proofs by introducing existential quantifiers for Skolem constants and applying contrapositives to convert disequations into positive equations.
Lemma Decomposition and Generation: The direct proof is analyzed to identify intermediate lemmas. For each lemma, the tool generates three types of problem variants to test for shorter derivations:
- Big-step: The axiom and the lemma as the conjecture (testing for radically new proofs).
- Small-step: The axiom, the lemma, and all previously derived lemmas as axioms (testing for variants of the original derivation).
- Abstracted: The axiom and an abstracted version of the lemma where specific subterms are replaced by fresh variables (testing for more general, shorter proofs).
  These variants are submitted to both Vampire and Twee.
Dependency Graph Construction: The tool constructs a Directed Acyclic Graph (DAG) representing the dependencies of candidate lemmas. It identifies "arrival lemmas" (candidates near the end of the proof, including the conjecture) and "departure lemmas" (dependencies of the arrival lemmas).
Three-Segment Proof Construction: To avoid combinatorial explosion, the final proof is synthesized in three segments:
- Segment 1: Derives the departure lemma from the axioms and its dependencies.
- Segment 2: Derives the arrival lemma from the departure lemma and its dependencies.
- Segment 3: Derives the original conjecture from the arrival lemma and its dependencies.
  The tool selects the shortest valid proofs for each segment from the results of the previous phase, concatenating them to form the final minimized proof.

Key Contributions

Krympa Tool: A novel system that decomposes complex equational proofs, re-proves intermediate lemmas using diverse strategies and provers, and reassembles them into concise, direct proofs.
Hybrid Proof Synthesis: The approach successfully combines the strengths of Vampire (efficient search and superposition) and Twee (structured equality chains and readability) to outperform either prover acting alone on specific problems.
Proof Minimization: The method demonstrates that proofs generated by saturation-based provers, which are often suboptimal due to their search heuristics, can be significantly compressed by treating them as a source of candidate lemmas rather than a fixed sequence.

Results

Tao's Challenge ( $650 \implies 448$ ): Krympa reduced the original 62-step Vampire proof to a 20-step proof. This new proof consists of 13 steps generated by Twee and 7 by Vampire, presented as a sequence of rewrite steps.
Empirical Evaluation: The tool was tested on 1,431 provable implications from the Equational Theories Project.
- Across all benchmarks, the average proof length decreased from 6.6 steps to 4.5 steps (a 31.5% reduction).
- For the subset of 117 problems with baseline proofs of at least 15 steps, the average reduction was 56.7% when using a combination of small-step and abstracted problem variants.
- Notable reductions include a 151-step proof reduced to 10 steps (problem $947 \implies 3897$ ), a 141-step proof reduced to 23 steps, and a 51-step proof reduced to 12 steps.
Output Format: The tool generates proofs in Lean format, utilizing the calc tactic and nth_rw for explicit rewrite steps, making them verifiable and readable by humans.

Significance and Claims
The paper claims that proof automation and readability can coexist. Historically, research has focused on finding proofs automatically rather than improving their presentation. This work demonstrates that by decomposing and recombining proofs from different provers, it is possible to produce shorter, more general, and human-intelligible proofs without sacrificing automation. The authors position their work as a fully automatic solution to Tao's challenge, offering a "loosely based" alternative to manual pen-and-paper proofs or semi-automated reconstruction methods. They note that while their approach is currently limited to the unit equality fragment of first-order logic, the methodology is orthogonal to existing reconstruction techniques and could be extended to full first-order or higher-order logic.