A SAT Attack on Tarski's High School Algebra Problem
Bernardo Subercaseaux, Benjamin Przybocki
math.LO
Aug 9, 2026 · v2
cs.LO
TL;DR
Uses autoformalization to verify in Lean that unsatisfiability of the SAT encoding for 11-element algebras implies no countermodel to Wilkie's identity exists.
Abstract
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.
Problem
Tarski's high school algebra problem has a known countermodel: Wilkie's identity fails in some algebras that satisfy the 11 high school identities. Earlier work bounded the smallest such countermodel between 11 (Zhang) and 12 (Burris and Yeats), so its exact size remained open.
Approach
Models of the high school identities with n elements are encoded as SAT formulas over addition, multiplication and exponentiation table variables, together with the negation of Wilkie's identity. Known lemmas from Burris–Lee and Zhang are added, along with lex-leader symmetry-breaking constraints. The formulas are solved with Kissat, and countermodels are enumerated with allsat-CaDiCaL. Lean, assisted by autoformalization, is used to verify that unsatisfiability of the size-11 formula proves the main theorem.
Results
No countermodel exists with 11 or fewer elements, so the smallest countermodels have exactly 12 elements. There are 8,957,952 non-isomorphic 12-element countermodels, all described by a simple parameterized template. The SAT approach outperforms Mace4 and SEM.
| n | # variables | # clauses | outcome | runtime [s] |
|---|
| 9 | 30,921 | 1,540,377 | UNSAT | 7.45 |
| 10 | 49,110 | 2,726,169 | UNSAT | 65.84 |
| 11 | 74,845 | 4,589,476 | UNSAT | 626.52 |
| 12 | 110,061 | 7,409,052 | SAT | 3,053.55 |
Runtimes for the full formula Ω_n (selected rows)