Tao’s Equational Proof Challenge Accepted (Technical Report)
Lydia Kondylidou, Jasmin Blanchette, Marijn J.H. Heule · 2026
Read Tao’s Equational Proof Challenge Accepted (Technical Report) by Lydia Kondylidou, Jasmin Blanchette, Marijn J.H. Heule (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21200.txt.
Introduction
Lydia Kondylidou, Jasmin Blanchette, and Marijn J. H. Heule take up Terence Tao's equational proof challenge from the Equational Theories Project. Tao sought alternatives to a complicated sixty-two-step proof found by the Vampire prover. Their Krympa tool, mixing brute force with heuristics and using Vampire and the Twee prover, cuts that proof to twenty steps, each a rewrite. On fourteen hundred thirty-one related problems, it also shrank a one hundred fifty-one-step proof to ten steps.
Catalog record
| CREATOR | Lydia Kondylidou, Jasmin Blanchette, Marijn J.H. Heule |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55586 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21200
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tao’s Equational Proof Challenge Accepted (Technical Report) Lydia Kondylidou, Jasmin Blanchette, Marijn J.H. Heule Abstract In the context of the Equational Theories Project, Terence Tao posed the challenge of finding alternatives to a complicated 62-step proof found by the Vampire superposition prover. We introduce a proof minimization tool called Krympa. Using a combination of brute force and heuristics, and exploiting both Vampire and the Twee equational prover, the tool reduces the 62-step proof to 20 steps, each corresponding to a rewrite. In an empirical evaluation, it also performs well on 1431 equational problems originating from the same project, reducing in particular a 151-step proof to only 10 steps. 1 Introduction The Equational Theories Project [ 6 ] , launched in September 2024 by Fields medalist Terence Tao, aims at exploring the relations between different equational theories of magmas. A magma is a basic algebraic structure consisting of a set equipped with a single binary operation \diamond closed on that set. The project’s first phase, concluded in April 2025, focused on equational laws for magmas that contain at most four applications of \diamond . The project uses the Lean [ 24 ] proof assistant to express proofs and counterexamples but depends on automatic theorem provers and other external tools. The problems explored in the project’s first phase all fall within first-order logic’s unit equality fragment: They consist of a universally quantified equation as the sole axiom and a universally quantified equation as the proof goal, or conjecture. For the problem 650\Longrightarrow 448 , where 650 denotes the axiom \forall x,y,z.\;x=x\,\diamond\,(y\,\diamond\,((z\,\diamond\,x)\,\diamond\,y)) and 448 denotes the conjecture \forall x,y,z.\;x=x\,\diamond\,(y\,\diamond\,(z\,\diamond\,(x\,\diamond\,z))) , the Vampire [ 4 ] superposition prover found a particularly complex proof, with 62 inference steps, excluding clausification and Skolemization. Given that the proof is unintelligible, Tao challenged the community to find “an alternate proof, by whatever means you wish—human, semi-automated, or automated” [ 30 ] . One idea was to run a specialized equational prover, Twee [ 26 ] , instead of Vampire, but this results in a very long, 137-step proof. Another approach would be to use Lean’s automation, such as the aesop [ 21 ] , canonical [ 25 ] , duper [ 8 ] , and grind [ 23 ] tactics and LeanHammer [ 32 ] , to reconstruct and compress consecutive superposition steps, in the style of Sledgehammer’s structured proof reconstruction [ 5 , Sect. 6.3] . This would yield a shorter and more high-level proof, in which each step may combine multiple rewrites. Our approach is orthogonal. Our working hypothesis is that the 62-step Vampire proof, which emerged as the byproduct of a saturation process, is likely suboptimal. By mixing and matching proofs generated by different automatic provers, as proposed by Sutcliffe et al. [ 29 ] , we hoped to achieve a shorter, simpler proof. We introduce Krympa, a tool that minimizes equational proofs by decomposing them into independently provable parts and reassembling them into more concise, intelligible proofs. Specifically, starting from a Vampire-generated proof, the tool transforms it into a direct proof (Sect. 3 ) and analyzes its inferences to break it down into intermediate results that serve as candidate lemmas. Each of these lemmas is then proved independently using Vampire and Twee (Sect. 4 ), the two leading systems in the unit equality division of the 2025 edition of CASC [ 28 ] . The resulting proofs are then combined into a single proof using heuristics that favor shorter derivations (Sect. 5 ). Given the 62-step Vampire proof of 650\Longrightarrow 448 , our tool produces a 20-step proof, where 13 steps are generated by Twee and 7 steps are generated by Vampire (Sect. 6 ). In a larger empirical evaluation, we applied the tool to 1431 provable implications from the Equational Theories Project and obtained positive results (Sect. 7 ). In particular, the tool reduced a 151-step Vampire proof to 10 steps. Our tool is implemented in Rust, OCaml, and Python. Its source code is available at https://github.com/kondylidou/Krympa . The files associated with Tao’s challenge and our empirical evaluation data are also available online [ 20 ] . 2 Background We briefly review the Vampire and Twee automatic provers and their respective proof formats. 2.1 Vampire and Superposition Proofs Vampire is a saturation-based theorem prover for first-order logic with equality based on the superposition calculus [ 3 ] . It implements highly optimized search strategies and data structures, and integrates techniques such as literal selection, term orders, redundancy elimination, strategy scheduling, and portfolios. Superposition works on implicitly universally quantified clauses. A preprocessor performs clausification and Skolemization. For example, the axiom \forall x.\;\mathsf{f}(x)=\mathsf{g}(x) is transformed into \mathsf{f}(x)=\mathsf{g}(x) , where x is a free variable, and the conjecture \forall x.\;\mathsf{f}(x)=\mathsf{g}(x) is negated and transformed into \mathsf{f}(\mathsf{sk})\not=\mathsf{g}(\mathsf{sk}) , where \mathsf{sk} is a Skolem constant. The objective is to derive the contradictory clause \bot . For the unit equality fragment, the calculus’s two relevant inference rules are as follows: \displaystyle{t\not=u}\mathstrut equality resolution \displaystyle\bot\mathstrut \displaystyle{t=t^{\prime}}\mathstrut \displaystyle\hskip 15.00002pt{s[u]\mathbin{\Bowtie}s^{\prime}}\mathstrut superposition \displaystyle\mu(s[t^{\prime}]\mathbin{\Bowtie}s^{\prime})\mathstrut The equality resolution rule has one premise, t\not=u , one conclusion, \bot , and one side condition: that t and u are unifiable. The superposition rule has two premises and one conclusion. The \bowtie symbol denotes either = or \not= throughout the rule. The = and \not= operators are commutative; for example, the premise t\not=u can match the disequation \mathsf{f}(\mathsf{a})\not=x either as is or as x\not=\mathsf{f}(\mathsf{a}) . The premises are assumed to have mutually disjoint sets of variables, which can be achieved by renaming. The notation s[\,] represents a term with a hole, the terms s[u] and s[t^{\prime}] are obtained by filling the hole in s[\,] with u and t^{\prime} , and \mu is a most general unifier of t and u . For example, the most general unifier of the terms \mathsf{h}(\mathsf{a},y) and \mathsf{h}(x,\mathsf{b}) is \{x\mapsto\mathsf{a}{,}~y\mapsto\mathsf{b}\} ; applying it on both terms yields \mathsf{h}(\mathsf{a},\mathsf{b}) . Finally, the rule has further side conditions, not shown here, that restrict the search space. Example 1 A subtle case of the superposition rule arises when both premises are the same clause. In the following, the variable in the second premise has been renamed to avoid a clash: \displaystyle{\mathsf{f}(\mathsf{f}(x))=\mathsf{g}(x)}\mathstrut \displaystyle\hskip 15.00002pt{\mathsf{f}(\mathsf{f}(x^{\prime}))=\mathsf{g}(x^{\prime})}\mathstrut superposition \displaystyle\mathsf{f}(\mathsf{g}(x))=\mathsf{g}(\mathsf{f}(x))\mathstrut This instance is obtained by taking t:=\mathsf{f}(\mathsf{f}(x)) , t^{\prime}:=\mathsf{g}(x) , {\bowtie}:={=} , s[\,]:=\mathsf{f}([\,]) , u:=\mathsf{f}(x^{\prime}) , s^{\prime}:=\mathsf{g}(x^{\prime}) , and \mu=\{x^{\prime}\mapsto\mathsf{f}(x)\} . Applying the unifier \mu to both premises yields the equations \mathsf{f}(\mathsf{f}(x))=\mathsf{g}(x) and \mathsf{f}(\mathsf{f}(\mathsf{f}(x)))=\mathsf{g}(\mathsf{f}(x)) . The inference replaces the subterm \mathsf{f}(\mathsf{f}(x)) in the second equation with \mathsf{g}(x) using the first equation as a left-to-right rewrite rule, and derives the conclusion. Example 2 Vampire implements parallel superposition , a variant of the superposition rule in which all subterms that match a term are replaced. The following inference illustrates this: \displaystyle{\mathsf{b}=\mathsf{a}}\mathstrut \displaystyle\hskip 15.00002pt{\mathsf{h}(\mathsf{b},\mathsf{a},\mathsf{b})\not=\mathsf{h}(\mathsf{a},\mathsf{b},\mathsf{a})}\mathstrut parallel superposition \displaystyle\mathsf{h}(\mathsf{a},\mathsf{a},\mathsf{a})\not=\mathsf{h}(\mathsf{a},\mathsf{a},\mathsf{a})\mathstrut Superposition proofs are expressed in a linear format. They are refutational and show how to derive \bot from the input axioms and the negated conjecture. Example 3 The following is a superposition proof from clauses 1–3: 1. \mathsf{a}=\mathsf{b} axiom 2. \mathsf{f}(x)=x axiom 3. \mathsf{h}(\mathsf{f}(\mathsf{b}),\mathsf{a})\not=\mathsf{h}(\mathsf{a},\mathsf{f}(\mathsf{b})) negated conjecture 4. \mathsf{h}(\mathsf{b},\mathsf{a})\not=\mathsf{h}(\mathsf{a},\mathsf{b}) by parallel superposition from 2 and 3 5. \mathsf{h}(\mathsf{a},\mathsf{a})\not=\mathsf{h}(\mathsf{a},\mathsf{a}) by parallel superposition from 1 and 4 6. \bot by equality resolution from 5 2.2 Twee and Structured Equational Chain