Intervals with large numbers of primes - MathOverflow

Intervals with large numbers of primes

2010-05-26T15:49:32Z

This is related to an older question about prime k-tuples and constellations, but takes a slightly different direction.

Given an integer k, we want to find n such that the interval {n+1, ..., n+k} contains as many primes as possible. (We consider only n ≥ k to eliminate certain exceptional cases, such as {3,5,7}, which is irregular since for k=5 there can be at most 2 primes in the interval if n>2.)

There is an obvious upper bound a_k on the number of primes in this interval, given by considering the numbers modulo p for all primes p ≤ k. More precisely, a_k is the largest possible cardinality of a set A ⊂ {1, ..., k} such that for some n, the set n+A does not contain any numbers divisible by any prime p ≤ k.

For example, a₃=2 since out of 3 consecutive numbers at least one is even, and a₇=3 since out of seven consecutive numbers at least three are even, and at least one of the odd numbers is divisible by 3. Similarly, a₉=4 and a₁₃=5.

The four bounds listed so far can be achieved by taking n=4, n=10, n=10, n=36, respectively. The natural question to ask is whether for every k there is a value of n such that the interval {n+1, ..., n+k} contains a_k primes, but the comments on the older question make me suspect that this may be open. (Another natural question is whether there are infinitely many such n, but since for k=3 this is the twin prime conjecture, that's definitely out of reach at present.)

Since the natural question to ask seems very hard, my question instead is this: Is anything about the asymptotics of this problem? More precisely, I'd like to know if something like the following statement is true: "For every ε>0, there exist infinitely many pairs (k,n) such that the interval {n+1, ..., n+k} contains at least (1-ε)a_k prime numbers."

There are a few different ways to tweak that statement -- for example, we could ask for infinitely many n for a fixed k, or we could let both k and n become arbitrarily large. (Of course k will need to become arbitrarily large as ε becomes small.) I'd be happy with any of them -- I'm asking this question out of curiosity rather than out of a need for a specific result.

Answer by Ben Green for Intervals with large numbers of primes

2010-05-26T17:20:48Z

For fixed $k$ this is definitely hopeless, since it would imply that for some $b$ there are infinitely many primes $p$ such that $p + b$ is prime, and this is a well-known open problem that seems out of reach of the latest techniques for finding small gaps between primes (see this survey article of Soundararajan for example: http://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01142-6/S0273-0979-06-01142-6.pdf)

For similar reasons this will also be hopeless if $k$ is too small depending on $n$.

If $k$ is huge compared with $n$ then the existence of many such pairs would follow immediately from the prime number theorem if only one knew that $a_k \leq (1 + o(1))\pi(k)$. However, I do not believe this is known and in fact I'm nigh-on certain that nothing better than $a_k \leq 2\pi(k)$ is known. This is a result of Montgomery and Vaughan; the slightly weaker bound of $a_k \leq (2 + o(1))\pi(k)$ follows rather easily from the Selberg upper bound sieve. Incidentally, the presence of the factor $2$ here reflects something called the parity problem in sieve theory: breaking it, even by a tiny amount, is generally very problematic.

In the previous discussion referenced above, the result of Hensley and Richards was mentioned. This is an example to show that it is \emph{not} true that $a_k \leq \pi(k)$. As you hint in the question, one might then conjecture that there is $n$ such that ${n+1,\dots, n+k}$ contains $a_k > \pi(k)$ primes, in which case one would have a violation of the triangle inequality $\pi(x+y) \leq \pi(x) + \pi(y)$. Such a conjecture would follow from the Hardy-Littlewood $k$-tuple conjecture which is, of course, hopelessly out of reach.

Answer by Karl Waugh for Intervals with large numbers of primes

2010-05-26T18:17:42Z

In some sense you're going to want to take n small as the difference between $\pi$(n) and $\pi$(n+k) is going to shrink as n gets large.

I know there are some results where the difference between $\pi$(n) and li(n) is bounded, so combinations of those may give you a bound. Wikipedia (ever reliable source) claims that

|$\pi (n) - li(n) $|$ \le \frac{\sqrt{x}ln(n)}{8\pi}$

is a result of Lowell Schoenfeld. (it says it assumes the Riemann hypothesis, so take it or leave it as you will) but then you could bound $\pi(n+k) - \pi(n)$. I don't know how well this works

Answer by tdnoe for Intervals with large numbers of primes

2010-05-26T19:10:28Z

OEIS sequence A120934 gives the least prime $p$ such that the interval $[p,p+\log(p)]$ contains $n$ primes.