Metraipolis › archive › dc_e43cecaccd28
A SAT Attack on Tarski's High School Algebra Problem — arXiv:2608.08421
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.08421
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:17:55.647Z
- SHA-256 of the archived text
835235a45978c99ff34401b10ed2cd1f590954a4d3eb84513346faf417786588- Stable URL of this page
https://metraipolis.com/documento/dc_e43cecaccd28
How to cite
A SAT Attack on Tarski's High School Algebra Problem — arXiv:2608.08421 — arXiv (en), https://arxiv.org/abs/2608.08421 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e43cecaccd28 (Metraipolis archive dc_e43cecaccd28, sha256 835235a45978c99ff34401b10ed2cd1f590954a4d3eb84513346faf417786588)
BibTeX
@misc{dce43cecaccd28,
title = {A SAT Attack on Tarski's High School Algebra Problem — arXiv:2608.08421},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.08421},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e43cecaccd28; sha256 835235a45978c99ff34401b10ed2cd1f590954a4d3eb84513346faf417786588},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08421. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in cs.LO).
Categorie arXiv: Logic (math.LO) ; Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2608.08421 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:14:28.547Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).