6 ms·
A SAT Attack on Tarski's High School Algebra Problem
- munchler 2mo agoWhy is subtraction not part of the algebra? It’s certainly familiar to every high school math student. This omission allows the counterexample, so the reveal is a bit of a disappointment IMHO.
- stevefan1999 2mo agoI'm not sure, but maybe it is due to that the expression a - b can be replaced as a + (-b)? Similarly, I think a * b and a / b can be replaced with the same trick, but then I realized it may not work on non-abelian, or where multiplicative inverse is not available...
- Sharlin 2mo agoWe’re in the semiring of positive integers, so there are no additive (or multiplicative) inverses.
- Sharlin 2mo agoSubtraction is not closed over positive integers, which is untidy. The point of Tarski’s conjecture was to propose a minimal number of axioms and operations, AFAICS they define the standard semiring of positive integers (with the natural definition of exponentiation added). (Edit: positive integers aren’t exactly a semiring because 0 is excluded, although some authors do define a semiring without the requirement of an additive identity element.)
- Transformanshen 2mo agoThe subtraction point is interesting but I don't think it makes the result disappointing. The whole point of Tarski's problem is what follows from that very restricted set of elementary identities so finding the exact minimum countermodel under those rules still seems like a pretty satisfying result.
- woadwarrior01 2mo agoBecause subtraction is not a total operation on positive integers. Negative numbers leave the domain.
- CamperBob2 2mo agoWhy was it important to Tarski to limit the domain to positive integers? That seems pointlessly arbitrary.
- LPisGood 2mo agoTruly, you could say that about many conjectures, especially more “fun” classical ones.
- QuesnayJr 2mo agoIf you allow negative integers, you get negative exponents. To accomodate negative exponents, you can expand the domain again, to rational numbers. If you allow rational numbers, then you have to allow rational exponents, which means you can take arbitrary nth roots. Which you could do, but now you're most of the way to the complex numbers (plus roots aren't unique anymore).
- skinner_ 2mo agoIf subtraction is allowed but negative numbers are not, that's known to be undecidable, even without exponentiation. There are several ways to deal with a subtraction with a negative result, but each variant is undecidable. If we allow negatives but disallow exponentiation, that's decidable. If we allow negatives and partial exponentiation that stays within the integers, that's undecidable again.
- NooneAtAll3 2mo agoI love SAT solver papers, always interesting to see auxiliary variable techniques, since those aren't really listed anywhere central here for example, instead of saying {f(x,y,z)==g(x,y,z)}, authors instead make variable group a_w:=(f(x,y,z)=w||g(x,y,z)=w), and then apply "at most 1" to it. Can't be unequal if both functions only can have 1 result in total this adds an index to iterate over, but separates internal subexpressions of f() and g(), removing 2 indixes (in this problem) and thus dropping whole power of n of clauses --- what I don't get is that they aren't searching Tarski's problem per se, but for one specific solution to it (one identity that isn't resulting from given). I'd totally look for arithmetic models that violate expectations in other ways than Wilkie
- yorwba 2mo agoThey use the properties of Wilkie's counterexample to restrict the search space. So you can't just pick arbitrary identities that hold over the positive integers and repeat the process until you've found a smaller model.
- kryogen1c 2mo agoMan I wish I understood anything you said, or anything in tfa. Math has to have my personal gold medal for highest desire to learn coupled with total unwillingness to.
- NooneAtAll3 2mo agoin a sense it's about a game. or... maybe it's better to call it a "challenge" Tarski said "hey, what if we limit ourself only to positive integers? subtraction/division doesn't always work, so let's get rid of it. What can we say about +^? there are some obvious properties, like x+y=y+x for whatever x and y. Is that enough to describe all the equalities?". Wilkie answered No, and a whole different hunt began - trying to find a set of pseudo "numbers" with pseudo "+^", that would have the same obvious properties, but not the non-obvious one and SAT-solving is essentially asking computer to find things by describing what they are not - "1+2 is not invalid and can't be 2 different values", "1+(1+1) must not differ from (1+1)+1". A lot of such properties are easily expressible as "not the opposite" - but devil's in the details and some choices of opposites are faster for computer than others. Also symmetries are evil :)
- 406380581 2mo agoThe lower bound had already been established in prior work: https://zenodo.org/records/18568303 https://zenodo.org/records/18568303
- MableCookie 2mo agoI think you are right, it's weird that the paper doesn't mention it
- emil-lp 2mo agoI don't know if it's weird. Is there an actual publication to cite? Or just a GitHub repo?
- bsubs 2mo agoI'm one of the authors of the arXiv paper. Thanks for bringing this to our attention! We were fully unaware of this repository, and it unfortunately did not come up during our literature search. Our approaches to the lower bound are pretty similar, although some technical differences make ours more efficient. For example, to show that there is no counterexample of size 10, we generate a formula with ~50k variables and ~2.7M clauses, which takes about 85 seconds to solve with Kissat. The encoder from this repository generates a formula with ~2k variables and ~33M clauses, which takes about 50 minutes to solve. We have sent an email to the authors of the Zenodo artifact to decide how to proceed!
- dooglius 2mo agoIsn't the underlying question proved impossible by Godel's incompletness theorem?
- deleted 2mo ago[deleted]
- LegionMammal978 2mo agoNo, Gödel's incompleteness theorem applies to theories that can interpret first-order arithmetic, which includes quantified statements like "for all x, there exists a prime p > x". In this case, we have the much simpler equational theory of positive integers under addition, multiplication, and exponentiation, which does not include any quantifiers. In fact, Gurevič showed that this theory is decidable [0]. On the other hand, Gurevič later showed that this theory is not finitely axiomatizable [1], so an infinite (but still computable) set of axioms is needed to fully characterize the theory. [0] R. Gurevič, Equational theory of positive numbers with exponentiation, 1985, https://doi.org/10.2307/2044966 https://doi.org/10.2307/2044966 [1] R. Gurevič, Equational theory of positive numbers with exponentiation is not finitely axiomatizable, 1990, https://doi.org/10.1016/0168-0072(90)90049-8 https://doi.org/10.1016/0168-0072(90)90049-8
- cubefox 2mo agoNot finitely axiomatizable using first-order logic, I assume.
- LegionMammal978 2mo agoNot using a set of axioms written in the original signature, of equations using the three operations and the constant 1. It's certainly possible to come up with a finite description of the true sentences in the theory, but only by extending the signature or using some method of description other than a set of axioms.
- cubefox 2mo ago
- Abh1Works 2mo agoI thought SAT like the high school admissions test
- Suppafly 2mo agoYeah as someone that doesn't participate in a bunch of math stuff, I was really confused because it mentions SAT and High School algebra, but isn't about High School SAT testing at all.
- EA-3167 2mo agoSorry that people downvoted you rather than lending you a hand. You might find this useful as a place to start: https://pmc.ncbi.nlm.nih.gov/articles/PMC9464179/ https://pmc.ncbi.nlm.nih.gov/articles/PMC9464179/
- Abh1Works 2mo agothanks!
- LPisGood 2mo agoThey address the following concern of Zhang (2005), which contained prior work involving similar techniques: > […] Of course, this conclusion is not proved mathematically. It is possible that the programs have some bugs, or the user (myself made some errors. They address it as follows: > We address this [… through] ChatGPT 5.5 Pro, through Codex, to automatically generate a Lean formalization that we then checked ourselves to confirm the statements and definitions indeed match their expected semantics. This process took multiple iterations and discussions with the model over several days, and generated over 10,000 lines of code. This is extremely unconvincing. Manual review of 10,000 lines of AI generated code is a terrifying prospect. I’m sure the result is correct, however I am deeply uncomfortable with this being mankind’s new mathematical process. Similar concerns have been expressed since the days of the 4 color theorem, but this feels different. Perhaps it is just new. >in a nutshell, it defines an executable function encode that takes a natural number n ≥ 5 and emits a CNF formula, which is byte-for-byte equal to the output of our Python encoding The phrase “byte-for-byte equal” makes my eye twitch these days.
- dev_dan_2 2mo ago> This is extremely unconvincing. Manual review of 10,000 lines of AI generated code is a terrifying prospect. With https://en.wikipedia.org/wiki/Lean_(proof_assistant) https://en.wikipedia.org/wiki/Lean_(proof_assistant) (and other proof assistants), you need to review only the lines that correspond to the theorem that you want to prove and their types (I am not very experienced when it comes to lean, but I would assume that comes down to a few hundred lines of code, at most). The rest is left to typechecking (which, I would expect many in the field to agree, is at as reliable than your average peer review process in professional mathematics, and likely much more). That's the reason why Lean4 is making such a fuzz now. That itself is not trivial too, but way easier than reviewing every function and definition used to prove that the theorems have indeed the types they claim. If one accepts the proof of the https://en.wikipedia.org/wiki/Four_color_theorem https://en.wikipedia.org/wiki/Four_color_theorem, then there should not be new reservations these proofs; except from the maybe new additional failure scenario that the authors (still correctly!) proved theorems that don't state what they think they stated. To sum it up: There is IMO no domain more suited for using LLMs than mathematical proofs that can be formalized using Lean4. The fact the hype-circle started earlier in software than in maths is due to the difference in monetary incentives I would assume. (Or another, rather radical and not really serious phrasing: "When it comes to Lean4 proofs that typechecks, there is no AI slop" - the theorem being proven might be uninteresting, but the proof itself is very very very very likely to be correct) > “byte-for-byte equal” The term itself or its association with LLMs? I would get the latter, if its the former: It's an desirable property to have, I always like seeing people going that far (assuming obviously that they indeed did so, and in the places where it matters!)
- zero_k 2mo agoMarkus Anders, who wrote the symmetry breaking system (satsuma) they use for SAT is pretty much a genius. His version of Kissat won the SAT Competition this year, with satsuma of course: https://satcompetition.github.io/2026/downloads/satcomp26slides.pdf https://satcompetition.github.io/2026/downloads/satcomp26sli... See slide 18. It was really nice to see him win. I have always been a huge fan of symmetry breaking, CryptoMiniSat (that I develop) had a symmetry breaking system, BreakID (which is _way_ slower than Markus' satsuma), in it for many years now.