[FOM] Hard problems in the theory of addition

[joeshipman@aol.com]

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 
+ x4.

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 
proofs.

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.