[FOM] Re: Addition with Primality: Decidability and Heuristics

[Timothy Y. Chow]

Dmytro Taranovsky <dmytro at mit.edu> wrote:
> Question:  Is the first order theory of natural numbers under addition
> and primality predicate decidable?

Of course, if the answer is yes, then proving it is hopeless, so I assume 
you suspect the answer is no?

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

I believe this is a special case of Schinzel's hypothesis.

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

This is closely related to the claim that sequence A000230 in Sloane's
encyclopedia has superpolynomial growth.

ID Number: A000230 (Formerly M2685)
URL:       http://www.research.att.com/projects/OEIS?Anum=A000230
Sequence:  2,3,7,23,89,139,199,113,1831,523,887,1129,1669,2477,2971,
           4297,5591,1327,9551,30593,19333,16141,15683,81463,28229,
           31907,19609,35617,82073,44293,43331,34061,89689,162143,
           134513,173359,31397,404597,212701,188029,542603,265621,
           461717,155921,544279,404851,927869,1100977,360653,604073
Name: Smallest prime p such that there is a gap of 2n between p and next prime.

The difference, I think, is just that you want to replace "gap of 2n" here 
by "gap of at least n."

Tim