💻 computer science

SATisfying the High School Identities but not Wilkie's Identity

This paper resolves an open question in Tarski's High School Algebra problem by proving that no 11-element algebra can satisfy the High School Identities while refuting Wilkie's identity, a result established via SAT encoding and accompanied by the discovery of a new 12-element countermodel.

Original authors: Agon Hajdari, Johannes Niederhauser

Published 2026-08-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Agon Hajdari, Johannes Niederhauser

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

In the vast landscape of mathematics, there is a quiet corner dedicated to the rules that govern how we combine numbers. For centuries, mathematicians have relied on a standard set of rules for addition, multiplication, and raising numbers to powers—operations so fundamental that they are taught in high school. These rules feel absolute, like the laws of physics, because they work perfectly when we count apples or calculate distances. However, a deep question lingered in the minds of logicians: are these familiar high school rules enough to explain every single truth about these operations? Could there be a hidden rule, true for all natural numbers, that cannot be derived from the standard textbook formulas? This question, known as Tarski's High School Algebra problem, challenged the completeness of our mathematical foundation. If such a hidden rule existed, it would mean our standard set of axioms was incomplete, leaving a gap in our understanding of arithmetic.

For decades, the answer remained elusive. In the 1980s, a mathematician named Alex Wilkie discovered a specific, complex rule that is true for natural numbers but cannot be proven using only the standard high school identities. This was a breakthrough, but it left a new puzzle: how small can a "counterexample" be? A counterexample in this context is a made-up mathematical world where the standard rules hold true, but Wilkie's specific rule fails. Finding such a world proves that the standard rules are not enough. Researchers spent years searching for the smallest possible version of this world. By 2005, they had built a counterexample with twelve distinct elements, and they had rigorously proven that no counterexample could exist with ten or fewer elements. This left a single, stubborn gap: could a counterexample exist with exactly eleven elements?

A team of researchers from the University of Innsbruck has finally closed this gap. They approached the problem not by trying to construct the mathematical world by hand, but by translating the entire search into a massive logic puzzle that a computer could solve. They took the requirements for a valid mathematical world—where addition and multiplication behave normally—and the specific condition that Wilkie's rule must fail. They then asked a computer to check every possible way to arrange an eleven-element world to see if any of them satisfied the conditions. The computer, using advanced techniques to break down the problem into billions of tiny logical steps, found that no such arrangement exists. The search was exhaustive and the results were verified independently by different software tools to ensure absolute certainty. The conclusion is definitive: there is no counterexample with eleven elements. The smallest possible counterexample must have at least twelve elements.

The researchers did not stop at proving the negative. In the process of their search, they also looked at the twelve-element case, which was already known to be possible. They discovered a new, distinct twelve-element world that had never been seen before. This new world behaves differently from the one found in 2005, proving that there is more than one way to break the rules of high school algebra while keeping the rest of the system intact. To reach these conclusions, the team utilized powerful parallel computing resources, running the search across dozens of processors simultaneously. They generated a digital proof for their results, a certificate that other mathematicians can check to verify that the computer did not make a mistake. This verification process confirmed that the search for an eleven-element counterexample was truly complete and that the answer is a solid "no."

This work settles a long-standing open question in the field of equational logic, confirming that the number twelve is the critical threshold where these mathematical anomalies first appear. It demonstrates that the standard high school identities are sufficient to describe all arithmetic truths for any system smaller than twelve elements. The study also highlights the growing power of modern computing in solving deep theoretical problems. What was once a task requiring years of manual effort and clever human insight has been transformed into a rigorous, automated verification process. The researchers have provided the mathematical community with a complete map of the landscape up to size twelve, showing exactly where the known rules hold and where they finally break down. Their findings are not just a list of numbers, but a definitive boundary line in our understanding of arithmetic structure, drawn with the precision of a computer-verified proof.

Technical Summary: SATisfying the High School Identities but not Wilkie's Identity

Problem Statement
The paper addresses a specific instance of Tarski's High School Algebra problem, which asks whether every identity involving addition, multiplication, and exponentiation that holds over the natural numbers ( $\mathbb{N}$ ) is derivable from the High School Identities (HSI). Wilkie previously demonstrated that this is not the case by exhibiting an identity true in $\mathbb{N}$ but not derivable from HSI. To prove non-derivability, one must construct a finite model (a countermodel) that satisfies all HSI axioms but falsifies Wilkie's identity.

Prior to this work, the search for the smallest such countermodel had narrowed the gap to a single case: while a 12-element countermodel was known, exhaustive searches had ruled out sizes up to 10, leaving the existence of an 11-element countermodel as the final open question.

Methodology
The authors formulate the search for finite countermodels as a propositional satisfiability (SAT) problem. Their approach involves:

Algebraic Constraints and Pruning: The authors incorporate structural constraints derived from prior algebraic literature (Burris, Lee, Zhang) to reduce the search space. These include:
- Fixing the "integer" chain ( $1, 1+1, 1+1+1$ ) to distinct elements $1, 2, 3$.
- Fixing the witness pair $(a, b)$ that falsifies Wilkie's identity to specific non-integer elements $4$ and $5$.
- Enforcing "integer-collapse" conditions (inequalities) to prevent the model from degenerating into a structure where Wilkie's identity would accidentally hold.
- Enforcing divisibility lemmas to ensure the specific terms in Wilkie's identity do not satisfy relations that would force the identity to be true.
SAT Encoding: The problem is encoded into Conjunctive Normal Form (CNF).
- Variables: Boolean variables represent the operation tables for $+$ , $\times$ , and $\exp$ over a domain of size $n$ . Additional variables track the evaluation of composite terms within Wilkie's identity.
- Clauses: The encoding enforces that operations are total functions (exactly one output per input pair), satisfies all HSI axioms (associativity, commutativity, distributivity, exponentiation laws, identity laws), and explicitly encodes the negation of Wilkie's identity ( $LHS \neq RHS$ ).
- Complexity: The number of variables grows as $\Theta(n^3)$ , while the number of clauses grows as $\Theta(n^7)$ . For $n=11$ , the instance contains approximately 3,069 variables and 63.8 million clauses.
Solving and Verification: The authors utilize parallel SAT solvers (Gimsatul and MallobSat) to solve the generated instances. Crucially, they employ proof-producing solvers to generate certificates of unsatisfiability (DRAT and LRUP formats). These proofs are independently verified using formally verified checkers (GRAT and lrat_isa) to ensure the results are mathematically rigorous and free of solver implementation errors.

Key Contributions and Results

Resolution of the $n=11$ Case: The primary result is the proof that no 11-element algebra satisfies the HSI axioms while refuting Wilkie's identity. By showing that all SAT instances for $n \le 11$ are unsatisfiable, the authors settle the last open size below 12.
Verification: The unsatisfiability results are backed by independently verified certificates, providing a high degree of confidence in the conclusion.
New 12-Element Countermodel: As a byproduct of testing the encoding for $n=12$ , the authors discovered a 12-element countermodel that is not isomorphic to the previously known 12-element example. They also identified that there are more than 500 non-isomorphic 12-element Gurevič–Burris algebras (GBAs), though a complete enumeration was not feasible within their timeframe.
Performance Analysis: The study demonstrates that modern parallel SAT solvers are capable of handling the high equational complexity of this problem, a task that was previously considered too difficult for SAT-based approaches (as noted in Zhang's 2005 work). MallobSat proved significantly faster than Gimsatul and the single-threaded baseline (CaDiCaL) for larger instances ( $n \ge 10$ ).

Significance
The paper claims to settle the last open size for the search of finite countermodels to Wilkie's identity, confirming that 12 is the smallest size at which such countermodels can occur. The work serves as a demonstration of the progress in automated reasoning, showing that modern SAT solvers can effectively tackle complex equational logic problems that were previously intractable for these tools. The authors emphasize that their contribution is the definitive resolution of the $n=11$ case through rigorous, machine-verified SAT solving, rather than the discovery of new algebraic theory or applications beyond the scope of the Tarski problem.

Technical Summary: SATisfying the High School Identities but not Wilkie's Identity

More like this