[FOM] Addition with Primality: Decidability and Heuristics

[Dmytro Taranovsky]

Question:  Is the first order theory of natural numbers under addition and
primality predicate decidable?

It is interesting to note that many questions relating to primes can be answered
heuristically by assuming that the distribution of primes is, in a sense,
random.  This way, the twin primes conjecture is true with probability one,
Goldbach's conjecture is almost certain to be true, and, with probability one,
every sufficiently large (with high probability, larger than 7 suffices) odd
number is equal to 2m+n where m and n are odd primes.  

I conjecture that for every (a_1, a_2, ..., a_n), there are infinitely many
n+1-tuples of primes in the form (m, m+a_1, m+a_2, ..., m+a_n) iff for every
prime p<n+2, there is (an integer) q such that no member of {q, q+a_1, ...,
q+a_n} is divisible by p.  The condition is necessary and sufficient so that
for every positive integer p, there is m such that no member of {m, m+a_1, 
..., m+a_n} is divisible by a factor of p (excluding 1).  Assuming that,
subject to basic constraints, the distribution of primes behaves like a random
one, with probability roughly 1/log m number m is prime, and, for a given (a_1,
..., an) satisfying the conditions, with probability roughly 1/(log m)^(n+1)
every member of {m, m+a_1, ..., m+a_n} is prime.  Since for every n, the sum as
m ranges from 2 to infinity of  1/(log m)^n diverges, there should be
infinitely many n+1-tuples of primes of the desired form.

I have not been able to express multiplication or the halting problem in the
language of addition with primality.  However, the function n --> the least
positive integer m such that there are no primes strictly between m and m+n
should have a superpolynomial rate of growth.

Dmytro Taranovsky