← All papers
First page of A SAT Attack on Tarski's High School Algebra Problem

A SAT Attack on Tarski's High School Algebra Problem

Bernardo Subercaseaux, Benjamin Przybocki

math.LO Aug 9, 2026 · v1 cs.LO
Lean is used to verify that the SAT-derived unsatisfiability result correctly proves the size-12 lower bound for Wilkie-identity countermodels.
Tarski's high school algebra problem asks whether every true identity concerning addition, multiplication, and exponentiation of positive integers follows from a list of 11 elementary identities. Surprisingly, Wilkie showed that the following identity is valid over the positive integers and yet does not follow from Tarski's axioms: \begin{align*} &\left((1+x)^y + (1+x+x^2)^y\right)^x \cdot \left((1+x^3)^x + (1+x^2+x^4)^x\right)^y = \\ &\left((1+x)^x + (1+x+x^2)^x\right)^y \cdot \left((1+x^3)^y + (1+x^2+x^4)^y\right)^x. \end{align*} Gurevič gave an algebra on 59 elements that satisfies Tarski's axioms but not Wilkie's identity, and over the years several authors whittled down the size of such a countermodel, culminating in a countermodel of size 12 due to Burris and Yeats. On the other hand, Zhang proved that there is no countermodel with fewer than 11 elements. Using SAT, we prove that the smallest countermodels are of size 12, as conjectured by Burris and Yeats. Moreover, we show that there are exactly 8,957,952 countermodels on 12 elements up to isomorphism and provide a simple classification of them. Our SAT approach outperforms dedicated tools for finding countermodels in equational theories, namely Mace4 and SEM. Furthermore, using autoformalization, we prove the correctness of our main result in Lean.

Tarski's high school algebra problem asks whether 11 elementary identities axiomatize all valid identities over positive integers; Wilkie found an independent identity. The question of the minimum size of an HSI-algebra countermodel to Wilkie's identity remained open, conjectured to be 12.

Models of Tarski's axioms and the negation of Wilkie's identity are encoded as SAT instances, using auxiliary variables and lex-leader symmetry-breaking constraints. The solver Kissat determines satisfiability for each size n, and allsat-CaDiCaL enumerates all countermodels of size 12. The correctness of the main lower-bound result, that unsatisfiability of the order-11 formula proves size-12 minimality, is verified in Lean via autoformalization.

The smallest countermodels are proven to be of size 12, confirming the Burris–Yeats conjecture. Exactly 8,957,952 non-isomorphic countermodels of size 12 exist, admitting a simple template classification. The SAT approach outperforms Mace4 and SEM.

n#variables#clausesoutcomeruntime [s]
1049,1102,726,169UNSAT65.84
1174,8454,589,476UNSAT626.52
12110,0617,409,052SAT3,053.55
Runtimes for the full formula Ω_n