[FOM] Hard problems in the theory of addition
joeshipman at aol.com
Sat Nov 18 13:59:39 EST 2006
Some recent discussion here has focused on how simple a statement in
the language of arithmetic can be and still be either unprovable in PA,
or "hard" (having no short proof). Friedman has suggested that
Goldbach's conjecture and the twin prime conjecture are near the
boundary and that statements significantly simpler than them are
decidable in PA (I don't recall whether he ventured an opinion on
whether they are decidable with short proofs).
But ever since the work of Fischer and Rabin in 1974, it has been known
that there are hard statements even in decidable theories involving
only addition. (For simplicity, assume the constants 0 and 1 are in the
language, though this is not necessary.)
Their techniques are of very general applicability and deserve to be
better known. In particular, they showed that there exist formulas in
the language of addition of length O(n) which represent real
multiplication "up to 2^(2^n)", and which represent integer
multiplication "up to 2^(2^(2^n)))".
Thus, there is a formula An(x,y,z) in the language of addition of
length O(n) with a very reasonable constant, such that An(x,y,z) is
true in the structure of the real numbers iff xy=z and x,y, and z are
all less than 2^2^n.
This formula is constructed by an easy induction, using the fact that x
< 2^(2^(k+1)) iff there exist x1,x2,x3,x4 < 2^(2^k) with x = x1x2 + x3
There is another formula Bn(x,y,z) in the language of addition of
length O(n) such that Bn(x,y,z) is true in the structure of the natural
numbers iff xy=z and x,y, and z are all less than 2^2^2^n.
This formula is constructed by an induction which involves the
assertion that the previous formula B_(n-1) is true modulo all primes
up to 2^2^n, since the earlier definitions allow correspondingly
limited definitions of residues.
Correspondingly limited versions of exponentiation can be defined by
pretty much the same trick.
By a straightforward argument involving the representation of Turing
machine computations by integers whose base 2 representation consists
of the concatenation of their instantaneous descriptions, Fischer and
Rabin show that the theory of real addition has exponentially long
proofs in any proof system whose axioms can be recognized in polynomial
time, and Presburger arithmetic has double-exponentially long proofs.
An additional argument shows that Skolem arithmetic, the theory of
integer multiplication without addition, has triple-exponentially long
Although these constructions are quite straightforward, and the size of
the assertions with (super-)exponentially long proofs is a small
constant times the size of the description of the Turing machine
recognizing the axioms, these assertions are still much longer than,
for example, Goldbach's conjecture or the twin prime conjecture.
My question for this list is:
Can anyone state a SHORT sentence in the language of addition (OK to
use 0,1,< as well as +), where the intended model is EITHER the real
numbers or the natural numbers, which is a candidate for "hardness"
(that is, has only long known proofs, or is an open question)?
(If anyone can come up with such a sentence in the language of
multiplication, where it is OK to use constants for 0,1,2,... , that
would also be quite interesting.)
-- Joe Shipman
Check out the new AOL. Most comprehensive set of free safety and
security tools, free access to millions of high-quality videos from
across the web, free AOL Mail and more.
More information about the FOM