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

Timothy Y. Chow tchow at alum.mit.edu
Thu Aug 5 14:40:39 EDT 2004

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


More information about the FOM mailing list