Intervals with large numbers of primes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T06:32:09Z http://mathoverflow.net/feeds/question/26032 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/26032/intervals-with-large-numbers-of-primes Intervals with large numbers of primes Vaughn Climenhaga 2010-05-26T15:49:32Z 2011-11-16T16:50:37Z <p>This is related to an <a href="http://mathoverflow.net/questions/17597/prime-numbers-with-given-difference" rel="nofollow">older question</a> about <a href="http://en.wikipedia.org/wiki/Prime_k-tuple" rel="nofollow">prime k-tuples and constellations</a>, but takes a slightly different direction.</p> <p>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 &ge; 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.)</p> <p>There is an obvious upper bound a<sub>k</sub> on the number of primes in this interval, given by considering the numbers modulo p for all primes p &le; k. More precisely, a<sub>k</sub> is the largest possible cardinality of a set A &sub; {1, ..., k} such that for some n, the set n+A does not contain any numbers divisible by any prime p &le; k.</p> <p>For example, a<sub>3</sub>=2 since out of 3 consecutive numbers at least one is even, and a<sub>7</sub>=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<sub>9</sub>=4 and a<sub>13</sub>=5.</p> <p>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<sub>k</sub> primes, but the comments on the <a href="http://mathoverflow.net/questions/17597/prime-numbers-with-given-difference" rel="nofollow">older question</a> 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.)</p> <p>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 &epsilon;>0, there exist infinitely many pairs (k,n) such that the interval {n+1, ..., n+k} contains at least (1-&epsilon;)a<sub>k</sub> prime numbers."</p> <p>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 &epsilon; 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.</p> http://mathoverflow.net/questions/26032/intervals-with-large-numbers-of-primes/26042#26042 Answer by Ben Green for Intervals with large numbers of primes Ben Green 2010-05-26T17:20:48Z 2010-05-26T17:20:48Z <p>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: <a href="http://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01142-6/S0273-0979-06-01142-6.pdf" rel="nofollow">http://www.ams.org/journals/bull/2007-44-01/S0273-0979-06-01142-6/S0273-0979-06-01142-6.pdf</a>)</p> <p>For similar reasons this will also be hopeless if $k$ is too small depending on $n$. </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/26032/intervals-with-large-numbers-of-primes/26046#26046 Answer by Karl Waugh for Intervals with large numbers of primes Karl Waugh 2010-05-26T18:17:42Z 2010-05-26T18:17:42Z <p>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. </p> <p>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 </p> <p>|$\pi (n) - li(n)$|$\le \frac{\sqrt{x}ln(n)}{8\pi}$</p> <p>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 </p> http://mathoverflow.net/questions/26032/intervals-with-large-numbers-of-primes/26052#26052 Answer by tdnoe for Intervals with large numbers of primes tdnoe 2010-05-26T19:10:28Z 2011-11-16T16:50:37Z <p>OEIS sequence <a href="http://oeis.org/A120934" rel="nofollow">A120934</a> gives the least prime $p$ such that the interval $[p,p+\log(p)]$ contains $n$ primes.</p>