7

Given $n\in\mathbb{N},$ the interval of width $n$ containing the most amount of primes is $[2,n+2]$ ( rather than $[2+x, n+2+x]$ ).

This sounds like it should be true since the primes spread out more in general as $x$ increases. But general trends don't prove specific statements.

This is obviously true for $n=1$ as there is no even prime greater than $2,$ and so for any $x\geq 1,\ [x+2,x+3]$ contains at most one prime whereas $[2,3]$ contains two primes.

I think simple arguments like this can be made for small $n$.

For fixed even $n\geq 2, n$ even, and for all $x\geq 1:$ (number of primes in $[2, n+2]$ ) $\geq$ (number of primes in $[x+2, n+2+x]$ ) implies that (number of primes in $[2, (n+1)+2]$ ) $\geq$ (number of primes in $[x+2, (n+1)+2+x]$ ) because $\underset{x\geq 1}{\max}$(number of primes in $[x+2, n+3+x]$ ) $=\underset{x \text{ odd}}{\max}$ (number of primes in $[x+2, n+2+x]$ ) . Therefore, we only need to check even $n'$s going forward (because if it's true for even $n$ then it's true for $n+1$.)

$n=2:\ $ for any $x\geq 1,\ [x+2,x+4]$ contains at most two primes, which can only happen if $x$ is odd, which is not more than the number of primes in $[2,3].$

$n=4$ and $n=6$ are easy to check.

$n=8:\ [2,10]$ contains four primes. In order for $[x,x+8]$ to contain five primes, $x$ must be odd and $x, x+2, x+4, x+6, x+8$ must all be prime. But one of $x, x+2, x+4$ is divisible by three and so this is not possible.

Adam Rubinson
  • 20,052
  • Well, the disjoint union of $[2,n+2]$ and $[2+x,n+2+x]$ is $[2,2+A] \cup [N,N+A]$ where $N=(n+3)$ and $A=(x-1)$. I don't know of a proof off-hand but I am about positive that there are at least as many primes in $[2,2+A]$ as there are in $[N,N+A]$ for general positive integers $N$ and $A$. – Mike Jun 06 '22 at 22:44
  • 2
    Asymptotically this is true, since if $x\to\infty$, then the number of primes in $[2+x,n+2+x]$ will be approximately $\frac{2+x+n}{\ln(2+x+n)} - \frac{2+x}{\ln(2+x)} \stackrel{x\to\infty}{\rightarrow} 0$. However it is technically possible that there is a really dense interval of say length $100$, with more primes than the interval $[2,102]$ contains (which is $26$). I just wrote a quick Python program to check all primes up to $n=1,000,000$, and all interval sizes up to $x=500$, and in every case, the interval $[2+x,n+2+x]$ contained the most primes. But of course, this is far from a proof. – Daniel P Jun 06 '22 at 23:56
  • @Daniel P- you mean the interval $[2, n+2]$ contains the most primes? – Adam Rubinson Jun 07 '22 at 00:37
  • @AdamRubinson Ah, sorry. I meant $[2,n+2]$, not $[2+x,n+2+x]$. – Daniel P Jun 07 '22 at 00:58
  • 1
    I also watched the video you linked, and Tao didn't talk about this specifically. – Daniel P Jun 07 '22 at 01:24
  • For all $n\ge 2$, let $m_n\ge 2$ be an integer such that $[m_n,m_n+n]$ is optimal for $n$. If you can show that $m_n\le n+3$, you are done, because (abusing notation), we have $\pi([2,n+2])-\pi([m_n,m_n+n])=\pi([2,m_n-1])-\pi([n+3,m_n+n])$, and we can use induction on $n$ to show that this is non-negative. – Mastrem Jun 07 '22 at 11:27

4 Answers4

2

I am surprised that nobody has mentioned this yet, but this is essentially the Second Hardy-Littlewood conjecture and it is most likely false, since it contradicts the theoretically much more sound First Hardy-Littlewood conjecture. There might not be a counter-example below $10^{100}$ or even $10^{1000}$, however.

Woett
  • 929
1

For $n\ge 1$ a positive integer, let $m_n$ be the smallest positive integer for which $\pi(n+m_n)-\pi(m_n-1)$ is optimal.

Lemma For $n\ge 59$, we have $m_n\le n+1$.

Proof: For $n\ge 59$, we have the inequalities $$ \frac{n}{\log n - 1/2}\le \pi(n)\le \frac{n}{\log n-9/8}. $$ Therefore, if $m_n\ge n+2$, we have $$ \log(m_n+n)-9/8\ge \log(2)+\log(n+1)-9/8> \log(n+1)-1/2\quad\text{and}\quad \log(m_n-1)-1/2\ge \log(n+1)-1/2, $$ whence $$ \begin{align*} \pi(n+m_n)-\pi(m_n-1) &\le \frac{n+m_n}{\log(n+m_n)-9/8} - \frac{m_n-1}{\log(m_n-1)-1/2}\\ &\le \frac{n+m_n}{\log(n+1)-1/2} - \frac{m_n-1}{\log(n+1)-1/2}\\ &=\frac{n+1}{\log(n+1)-1/2}\le \pi(n+1). \end{align*} $$ So the interval $[2,n+2]$ contains more primes than $[m_n,m_n+n]$. This contradicts the definition of $m_n$. We conclude that $m_n\le n+1$. $\square$

Theorem If $m_n=2$ for all $n\le 58$, then $m_n=2$ for all $n\ge 1$.

Proof: By induction on $n$. The base case $n=1$ is clear. Let $n\ge 2$ and assume that $m_k=2$ for all $k=1,\ldots,n-1$. If $n\le 58$, we are done. Otherwise, $n\ge 59$ and by the lemma, $m_n\le n+1$. Now, $$ \begin{align*} \left(\pi(n+2)-\pi(1)\right) - \left(\pi(n+m_n)-\pi(m_n-1)\right) =& \left(\pi(m_n-1)-\pi(1)\right) - \left(\pi(n+m_n)-\pi(n+2)\right)\ge 0, \end{align*} $$ because $m_{m_n-2}=2$, by the induction hypothesis. $\square$

Mastrem
  • 8,331
  • (1) We have $\frac{n}{\log n-1} \le \pi(n) \le \frac{n}{\log n - 9/8}$ for all $n \ge 4$ (as I mentioned here; it's enough to check that this holds for $4 \le n \le 60183$). That should reduce the number of cases to check by hand. – Misha Lavrov Jun 07 '22 at 14:02
  • @MishaLavrov Ooh, that's super useful. I'll edit my answer. – Mastrem Jun 07 '22 at 14:04
  • (2) I don't see how the second inequality on $\pi(n+m_n)-\pi(m_n-1)$ works - what lets you replace $\log(m_n - 1)$ by $\log(n+1)$? Or maybe we assume $m_n \ge n+2$, but then we get a slightly weaker result. – Misha Lavrov Jun 07 '22 at 14:04
  • @MishaLavrov Good catch. The result will be slightly weaker, but still strong enough, since ultimately, we need $m_{m_n-2}=2$ – Mastrem Jun 07 '22 at 14:05
  • Sorry, I misquoted myself. Though we get $\pi(n) \le \frac{n}{\log n - 9/8}$ at $n \ge 4$, we don't have $\pi(n) \ge \frac{n}{\log n - 1}$ until much later. My observation is much less useful now! We do get $\frac{n}{\log n - 1/2} < \pi(n) < \frac{n}{\log n - 9/8}$ for $n \ge 59$. – Misha Lavrov Jun 07 '22 at 14:07
  • @MishaLavrov I've edited my answer. – Mastrem Jun 07 '22 at 14:12
0

This is far from a proof, I just wanted to share some code to find potential counterexamples. Though so far, the statement in the question seems to be true.

I wrote a Python program to check all primes up to $n=1,000,000$, and all interval sizes up to $x=500$, and in every case, the interval $[2,n+2]$ contained the most primes.

The way it works is it lists all the consecutive gaps between primes (dPrimes), then for every possible interval length I = 2...500 it adds up the size of all I consecutive gaps. In each case, this sum is clearly the difference between the first and last prime in the interval, and if this difference is smaller than the sum of the first I gaps, then we have found an interval more dense than $[2,n+2]$.

def main(N = 1000000, X = 500):

import math

primes = [i for i in range(2,N+1) if all(i % j != 0 for j in range(2,int(math.sqrt(i))+1))]
foundDenserInterval = False

def diff(L):
    return [L[i+1]-L[i] for i in range(len(L)-1)]

dPrimes = diff(primes)

for I in range(2,X+1):
    print(I) # not necessary, just shows progress
    orig_gapsums = sum(dPrimes[:I])
    all_gapsums = [sum(dPrimes[j:j+I]) for j in range(1,len(dPrimes)-I)]
    for g in range(len(all_gapsums)):
        if all_gapsums[g] &lt;= orig_gapsums:
            print(&quot;FOUND DENSER INTERNVAL:&quot;, [p for p in primes[g+1:] if p &lt;= primes[g+1]+I])
            foundDenserInterval = True

if not foundDenserInterval:
    print(&quot;DID NOT FIND A DENSER INTERVAL THAN [2,N+2]&quot;)




if name == "main":
    main()

It took around $4$ minutes to run this on my PC (with a dual-core $2 \times 2.8$ GHz processor), so if anyone has a beefier computer, feel free to run it for even larger $N$ and $X$! Or feel free to improve on my code. :)

Daniel P
  • 2,710
  • Here is a c++ code that does the same thing: https://pastebin.com/XVq9cwhV Compile with something like g++ -O3 prime-intervals.cpp -o a && ./a. It uses a sorted queue (maybe priority queue is quicker) to process the events. For a fixed interval size $x$, it takes $O(\pi(n) \log\pi(n))$ where $\pi(n)$ is the number of primes $\leq n$. With constraints 1e6 and 500 (same as yours), it takes 2 seconds, while with 1e8 and 1000, it's still running but expected to take a few minutes. – Gareth Ma Jun 07 '22 at 02:10
0

This is a strategy on how (I think) this can be proved not a complete answer.

The wikipedia page on the prime counting function has an explicit bound on the difference between the prime counting function and the logarithmic integral function. This can be used to get an explicit interval bound for the number of primes in any interval $[a,b]$. As the error term is decaying faster than the number of primes, this should suffice to prove that there can be no counter example for $a,b$ sufficiently big with explicit bounds on how big $a,b$ need to be. One can then in principle brute force the smaller cases numerically.

quarague
  • 5,921