Arithmetic with addition alone

“There is an $x$ such that …” asks whether a column of a grid contains a mark, and read that way a quantifier is a shadow: the set of parameters for which a solution exists is the projection of the solution set onto the parameter axis. Over the real numbers every such shadow can be described without the quantifier, by polynomial inequalities — Tarski’s theorem, of which “$x^2 + ax + 1 = 0$ has a solution exactly when $a^2 \ge 4$” is the smallest example. Over the whole numbers with both addition and multiplication, the opposite holds: shadows can be anything a computer can list, the primes included, and there is no general way to eliminate the quantifier.

Between those two extremes there is a system that behaves like the real numbers even though it lives on the whole numbers. Take the whole numbers with addition, order and nothing else — no multiplication of variables by variables. Mojżesz Presburger showed in 1929 that every statement in that language can have its quantifiers eliminated, provided one kind of expression is added: “$x$ leaves remainder $r$ on division by $m$”. The shadows are then never wild. They are always a finite exceptional stretch followed by a pattern that repeats for ever, and this essay draws what that looks like and why multiplication is exactly what breaks it.

A strip, and its shadow #

Take the whole-number points $(x, y)$ with $2x \le 5y \le 2x + 1$: a thin strip between two parallel lines of slope $2/5$. Ask for which $x$ some whole number $y$ fits.

Over the real numbers the question is trivial: for any $x$ there is a real $y$ between $2x/5$ and $(2x+1)/5$, so the shadow is everything. Over the whole numbers the strip is too thin to catch a lattice point above every $x$, and it catches one only when $2x$ lands within one of a multiple of $5$. That happens when $x$ leaves remainder $0$ or $2$ on division by five — for $x = 0$, $2x = 0$; for $x = 2$, $2x = 4$, one short of $5$ — and the pattern repeats every five. The figure checks that description against the drawn points for every $x$.

So the statement $\exists y\,(2x \le 5y \le 2x + 1)$ is equivalent to $x \equiv 0$ or $x \equiv 2 \pmod 5$, which has no quantifier in it. That is quantifier elimination in miniature, and it shows why the congruences have to be allowed: without them, the only quantifier-free statements about a single $x$ in the language of addition and order are finite combinations of inequalities, whose solution sets are unions of intervals — and a set that picks out two residues out of every five is not a union of finitely many intervals.

Change the strip and the shadow changes in exactly the predictable way. With $3x \le 7y \le 3x + 2$ the strip is wider relative to its slope and the shadow is three residues out of seven, $x \equiv 0, 2$ or $4 \pmod 7$. The period is the denominator of the slope and the number of residues caught is governed by the strip’s width — the same arithmetic that decided how multiplication by a fixed number moves residues round a dial.

Presburger’s elimination #

The general theorem says that this always works. Any formula of the language — built from whole-number variables, addition, constants, equality, order, the connectives and the two quantifiers — is equivalent to one with no quantifiers at all, once congruence conditions $x \equiv r \pmod m$ are allowed as atoms.

The proof eliminates one existential quantifier at a time, and the step is a generalisation of the strip. A formula $\exists y\, \varphi(x, y)$ with $\varphi$ quantifier-free says that $y$ satisfies some collection of inequalities and congruences involving $x$. Multiply through so that $y$ appears with the same coefficient everywhere; then the inequalities bound $y$ between some lower and upper expressions in $x$, and the congruences restrict $y$’s residue. A whole number $y$ satisfying all of that exists exactly when one of finitely many candidates does — the least value above each lower bound in each allowed residue class — and each candidate can be substituted in, leaving a quantifier-free formula in $x$. The price is that the formula grows, and each elimination multiplies the moduli, but it always finishes.

A small case shows every part of the step. Eliminate $y$ from

$$\exists y\,\big(x < 3y < x + 7 \;\wedge\; y \equiv 1 \pmod 2\big).$$

The condition on $y$ is that $3y$ lands strictly between $x$ and $x + 7$ and that $y$ is odd. Multiples of $3$ strictly between $x$ and $x + 7$ always exist — two of them, since the gap is six numbers wide — and they are $3y$ for two consecutive values of $y$, one odd and one even. So an odd $y$ always exists, and the formula is simply true for every $x$: the quantifier-free equivalent is “$x = x$”. Narrow the window to $x < 3y < x + 4$ and there is exactly one multiple of three inside, $3y$ for a single $y$, and whether that $y$ is odd depends on $x$’s remainder modulo six. Working it out case by case gives the quantifier-free equivalent $x \equiv 0, 1 \text{ or } 2 \pmod 6$. The remainder conditions on $x$ and on $y$ have combined into one condition modulo $6 = 2 \times 3$, exactly as two dials combine into one when their sizes share no factor.

That is the whole method, repeated: find the finitely many candidate witnesses in each residue class, substitute each, and collect the conditions on the remaining variables, merging congruences as they meet. The dials of modular arithmetic are not an addition to Presburger’s language for convenience. They are what the shadows of addition are made of.

Two consequences follow at once. The system is decidable: to decide whether a sentence with no free variables is true, eliminate its quantifiers, leaving a variable-free combination of numerical comparisons, which can simply be evaluated. And it is complete: every sentence is provable or refutable from Presburger’s axioms, since the elimination is itself a sequence of provable equivalences. Both are exactly what Gödel’s theorem says cannot hold of arithmetic with multiplication, and the next sections are about why addition alone escapes it.

The order of quantifiers, with arithmetic in it #

The order of quantifiers matters here as everywhere, and the elimination makes the difference computable rather than merely visible. The sentence $\forall x\, \exists y\, (x = y + y \vee x = y + y + 1)$ says every whole number is even or odd, and eliminating $y$ turns the inside into “$x \equiv 0$ or $x \equiv 1 \pmod 2$”, which holds for every $x$: true. Swap the quantifiers — $\exists y\, \forall x\, (x = y + y \vee x = y + y + 1)$ — and it claims a single $y$ that halves every number, which elimination reduces to a falsehood. Of the six sentences two quantifiers can make from one relation, Presburger’s procedure settles every one, for every relation definable with addition, by the same mechanical steps.

What the procedure cannot settle is a sentence it cannot write. There is no formula in the language saying “$x$ is a square” or “$x$ is prime”, and the diagrams of relations that those predicates would draw — the divisor grid whose shadow is the composite numbers — are exactly the ones that lie outside it.

What coins can pay #

The most familiar Presburger shadows are the totals a set of coins can make. With coins worth $3$ and $5$, a total $x$ can be paid exactly when $\exists y\, \exists z\, (x = 3y + 5z)$ with $y, z \ge 0$ — two quantifiers, over whole numbers, with only addition.

The shadow is $\{0, 3, 5, 6\}$ together with every whole number from $8$ on. The four totals that cannot be paid are $1, 2, 4$ and $7$, and the largest, $7$, is $3 \times 5 - 3 - 5$. James Joseph Sylvester proved in 1884 that for two coin values $a$ and $b$ with no common factor, the largest total that cannot be paid is always $ab - a - b$, and exactly half of the numbers below it are unpayable. The reason for the formula is a count on a dial: the multiples of $b$ fall into different residue classes modulo $a$, the multiple $kb$ opens up its residue class for every total from $kb$ on, and the last class to open is opened by $(a-1)b$, so the last gap is $(a-1)b - a$.

With three values the picture is the same and the arithmetic is not. Boxes of 6, 9 and 20 can make every total from 44 on, and 43 is the largest that none of them can make — a fact about packets of chicken nuggets that has become the standard example. But there is no formula like Sylvester’s: Frank Curtis showed in 1990 that no polynomial in the three values gives the largest gap. The largest unpayable total is still perfectly definable in Presburger’s language — it is the largest $x$ such that $\neg\exists y\,\exists z\,\exists w\,(x = 6y + 9z + 20w)$ — and so it can always be computed by elimination; what fails is only the hope that the answer has a shape as simple as the question.

Every shadow eventually repeats #

The strips and the coins share a shape, and the shape is the theorem. Every set of whole numbers definable from addition — every shadow in this language — is eventually periodic: past some threshold it repeats with some period. The period may be one, as with the coins, where the pattern is “everything”; it may be five, as with the strip.

The theorem follows from the elimination: a quantifier-free formula in one variable is a combination of inequalities, which are eventually constant, and congruences, which are periodic, and any combination of such things is eventually periodic with period the product of the moduli. Seymour Ginsburg and Edwin Spanier proved the multi-dimensional version in 1966: the sets definable in Presburger’s language are exactly the semilinear sets, finite unions of translated lattice cones.

The squares are the set that shows what is missing. The gaps between consecutive squares are $1, 3, 5, 7, \ldots$, growing without bound, so no period can ever fit them, and so the squares are not definable from addition. Nor, therefore, is multiplication: if $x \cdot y$ were definable, $x \cdot x$ would be, and so would the squares. That single figure is the reason Presburger’s system cannot talk about multiplication — and the reason it escapes incompleteness.

Why addition alone escapes Gödel #

Gödel’s theorem needs a system strong enough to describe its own proofs, and describing proofs needs a way to code finite sequences of numbers as single numbers and to extract the entries — which in turn needs multiplication, or at least some function that grows like it. Presburger arithmetic cannot code sequences: the sets it defines are eventually periodic, and a coding of arbitrary finite sequences would have to produce sets of every shape. So the diagonal that builds Gödel’s sentence cannot be run inside it, and the system is complete.

The boundary is sharp. Add squaring to addition and multiplication becomes definable at once, from the identity $2xy = (x + y)^2 - x^2 - y^2$, and with it the full incompleteness of arithmetic. Keep multiplication and drop addition instead, and the result is Skolem arithmetic, which Thoralf Skolem showed in 1930 is also decidable: multiplication alone, like addition alone, is tame. It is the two together that can describe computation, and that is exactly what Matiyasevich’s theorem uses to show that a polynomial equation’s shadow over the whole numbers can be any listable set.

The history has a sad and pointed irony. Presburger proved his theorem in 1929 as a student in Tarski’s seminar in Warsaw, and it was judged not substantial enough for a doctorate; he received a master’s degree for it instead, left mathematics for an insurance company, and died in the Holocaust, probably in 1943. Two years after his thesis, Gödel’s theorem showed that the result Presburger had proved for addition was impossible for arithmetic with multiplication — which made his decidable, complete fragment one of the most instructive facts in logic, because it marks exactly where incompleteness begins.

The same sets, read by a machine #

There is a second characterisation of the Presburger sets that looks unrelated and is the same. Write whole numbers in base two and feed their digits to a finite automaton — a machine with finitely many states that reads a word and accepts or rejects it, the machines that sets of positions turned out to describe. The eventually periodic sets are recognisable by such a machine in every base, since checking a remainder modulo $m$ needs only $m$ states.

Alan Cobham proved the converse in 1969: a set of whole numbers that is recognisable by a finite automaton in two bases that are not powers of a common number — base two and base three, say — must be eventually periodic, and so Presburger-definable. The powers of two are recognisable in base two, where they are a one followed by zeros, and not in base three. Cobham’s theorem says that only the sets with no preferred base are the ones addition can define, which is the same statement as the eventual periodicity, reached from the side of machines instead of formulas.

What the strips cannot show #

They cannot show all $x$. Every figure checks its shadow on a finite range — thirty numbers, sixty, a few hundred for the coins. That the pattern continues for ever is the content of the periodicity theorem, proved from the elimination, and a finite strip is consistent with any continuation.

They cannot show the elimination’s cost. The quantifier-free equivalent of a formula can be enormously longer than the formula, because each elimination multiplies the moduli. How much longer, and how much work deciding a sentence takes, is a question about the cost of a procedure rather than about what the language can say, and it belongs to the theory of computation rather than to this one.

And they cannot show higher dimensions. The strip’s shadow is the one-dimensional case of the Ginsburg–Spanier theorem; the semilinear sets in the plane and beyond — unions of translated lattice cones — are described in words, and the figures draw only their one-dimensional shadows.

Still open: addition and the primes #

Presburger arithmetic is decidable and so is Skolem’s; arithmetic with both is not. A natural question is what happens between: take addition and add a single set as a new predicate. Adding the powers of two keeps the system decidable, as Alexei Semenov showed. Adding the squares makes it undecidable, by the identity above.

Adding the primes is not settled. The trouble is that the resulting language can state famous open problems directly: “for every $n$ there is a prime $p > n$ with $p + 2$ also prime” is a sentence using only addition, order and the primes, and it is the twin prime conjecture. A procedure deciding every sentence of that language would decide the twin prime conjecture, along with Goldbach’s conjecture and a great many others. Patrick Bateman, Carl Jockusch and Alan Woods showed in 1993 that, assuming the linear case of a strong conjecture about prime patterns known as Schinzel’s hypothesis, the language with addition and the primes is undecidable. Without that assumption, nobody knows.

Shadows that repeat #

In arithmetic with addition and order but no multiplication, every quantifier can be eliminated once remainder conditions are allowed, so every sentence is decidable and every definable set of whole numbers is eventually periodic. A thin strip’s lattice points cast a shadow that repeats with the slope’s denominator; the totals coins can pay are a finite exception followed by everything, with Sylvester’s $ab - a - b$ as the last gap for two coins and no such formula for three.

The squares, whose gaps grow without bound, are not eventually periodic, so neither squaring nor multiplication can be defined from addition — which is why Presburger’s system cannot code its own proofs and so escapes incompleteness. Add squaring and the full undecidability of arithmetic returns; add the primes and the answer is unknown, because the language could then state the twin prime conjecture.

Before asking whether a question can be decided, ask what the language can define — a language whose every definable set repeats cannot express a problem hard enough to be undecidable.