# The shortest interval for which the prime number theorem holds [closed]

It is well known that the prime number theorem on the form \begin{align*} \pi(x+y) - \pi(x) \sim \frac{y}{\log (x+y)} \end{align*} breaks down for short enough intervals, e.g. taking $y=(\log x)^\lambda$ for any $\lambda>1$, as shown by Maier. As to what is short enough (or long enough), both Granville, p. 7 and Soundararajan, p. 79 conjecture that the prime number theorem holds for all $x$ as long as $y\geq x^\epsilon$. However, I believe to have a heuristic argument for the following conjecture:

Conjecture The choice of $y= \sqrt{x}$ is necessary and sufficient for \begin{align*} \pi(x + y)-\pi(x) \sim \frac{y}{\log (x+y)} \end{align*} to hold for all $x$ as $x\rightarrow \infty$.

I understand that this can be considered a bold claim, so my question is:

Q: Considering the heuristic below, is the conjecture as stated reasonable?

Heuristic: To understand why this conjecture should hold, we need to look at the short intervals between consecutive primes squared, defined by $s_k:=\{p_{k}^2, \dots p_{k+1}^2-1\}$ for $k\geq 1$. These intervals naturally occur in the context of the sieve of Eratosthenes, and in particular, each $s_k$ has the specific quality of being fully sieved by the $k$ first primes; any element in $s_k$ is either divisible by some $p \in \mathcal{P}_k:=\{p_1, \dots,p_{k}\}$ or else is a prime $p \notin \mathcal P_k$. In addition, the exact distribution of primes in $s_k$ is in its entirety build up of the periodic sequences \begin{align*} \rho_{k}(n):=\begin{cases} p_k & \text{if } p_k \mid n,\\ 1 & \text{otherwise}, \end{cases} \end{align*} which we visualise for the specific example of $s_3$ by the following table: \begin{matrix} n & 25 & 26 & 27 & 28 & \bf{29} & 30 & \bf{31} & 32 & 33 & 34 & 35 & 36 & \bf{37} & \cdots & 48\\ \hline \\ \rho_1(n) & 1 & p_1 & 1 & p_1 & 1 & p_1 & 1 & p_1 & 1 & p_1 & 1 & p_1 & 1 & \cdots & p_1\\ \rho_2(n) &1 & 1 & p_2 & 1 & 1 & p_2 & 1 & 1 & p_2 & 1 & 1 & p_2 & 1 & \cdots & p_2\\ \rho_3(n) &p_3 & 1 & 1 & 1 & 1 & p_3 & 1 & 1 & 1 & 1 & p_3 & 1 & 1 & \cdots & 1 \end{matrix}

Observe that the lengths of the intervals $s_k$ are of the form $|s_k|=2 p_{k+1} g_k-g_k^2$, where $g_k:=p_{k+1}-p_k$, and hence lie on the curves $2 \sqrt{x} g - g^2$, with $g=2n$, $n\geq 1$.

Necessary part As $k\rightarrow \infty,$ Any interval growing slower than $\sqrt{x}$ will eventually be infinitesimal compared to arbitrarily many primes smaller than $p_k$, and cannot be expected to accurately sample the distribution of primes in $s_k$, which derives from the underlying periodic sequences $\rho_j(n)$, $1\leq j \leq k$, and where the largest period is $p_k$. What this suggests is that $y=\sqrt{x}$ is the sharp barrier below which the prime number theorem breaks down.

Sufficient part On the other hand, any interval growing faster than $\sqrt{x}$ will eventually cover arbitrarily many intervals $s_k, s_{k+1}, \dots, s_{m}$. But this results in an underestimate of $\pi(x + y)-\pi(x)$, since $y/\log (x+y)$ assumes constant density of primes across $[x,x+y]$, equal to the density in the final interval $s_m$ covered, hence suggesting that $y= \sqrt{x}$ is also sufficient. At its most extreme, the latter argument is exemplified by the estimate $\pi(x) \sim x/\log x$, which is well known to be an inferior guess of the number of primes up to $x$ compared to $\pi(x) \sim \textrm{li}(x)$.

(I should add that the heuristic argument is presented in greater detail in a draft manuscript I recently added to arXiv, titled Primes in the intervals between primes squared).

ADDED: CLARIFICATION OF HEURISTIC ARGUMENT In an attempt to make the heuristic clearer, consider the table above. If we move across this with intervals smaller than $p_3=5$, there will be some places where we underestimate the number of primes and some places where we overestimate. This effect magnifies for larger $k$ and intervals growing slower than $\sqrt{x}$, and suggests the necessary part of the heuristic. (Consider even measuring the density across $\rho_3(n)$ only. It should be even more obvious then.)

-

## closed as off-topic by Daniel Loughran, Stefan Kohl, quid, Will Jagy, Felipe VolochAug 5 '14 at 21:09

This question appears to be off-topic. The users who voted to close gave these specific reasons:

• "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Daniel Loughran, Stefan Kohl, Felipe Voloch
• "This question does not appear to be about research level mathematics within the scope defined in the help center." – quid, Will Jagy
If this question can be reworded to fit the rules in the help center, please edit the question.

Pardon me, but this does not look like a question, but rather like commercial for your recent paper on arxiv. If you put it on arxiv, it is a preprint (right), and you will get response from the editor and the reviewers of the journal you submit the paper to. Besides, you spend 29 pages in your paper on arxiv arguing for your conjecture, so I personally find it unlikely you will get an answer of the same caliber. –  Per Alexandersson Aug 5 '14 at 11:49
Not my intention to make it a commercial. I'm truly interested in the answer. I'm not a professional mathematician, but have some interesting findings and have found this forum great for getting serious answers and many times better insights than what I could have achieved alone. I have removed the link to the paper. You could also remove these comments if you feel the question would be better off like that. –  user45947 Aug 5 '14 at 12:04
Where is page 79 of Sundararajan’s 20-page paper? –  Emil Jeřábek Aug 5 '14 at 15:41
Meta post: meta.mathoverflow.net/questions/1818 –  Emil Jeřábek Aug 5 '14 at 18:25

I'm not an analytic number theorist, so take this all with many grains of salt.

Let $S(x,y,p)$ be the set of integers in the interval $(x,x+y)$ which are NOT divisible by $p$. The argument you are imagining for the prime number theorem is $$\pi(x+y)-\pi(x) = \left| \bigcap_{p \leq \sqrt{x}} S(x,y,p) \right| \approx y \prod_{p \leq \sqrt{x}} \frac{|S(x,y,p)|}{y} \approx y \prod_{p \leq \sqrt{x}} \left( 1 - \frac{1}{p} \right).$$ Your point is that the second $\approx$ is not good on a term by term basis if $p>y$, because the true value of $|S(x,y,p)|/y$ will be either $1$ or $1-1/y$, not $1-1/p$. You therefore suggest that the whole composite approximation should also not be good. I see two immediate issues:

A product of inequalities is not an inequality While it is true that $|S(x,y,p)|/y$ is not $1-1/p$, this formula can be wrong in either direction. So it is possible that the errors cancel and the products are close to equal.

The sketched proof doesn't work for large $y$ Even when $y$ is as large as $x$, there is a huge issue: $\prod_{p \leq \sqrt{x}} (1-1/p) \approx e^{- \gamma}/\log \sqrt{x} = 2 e^{-\gamma}/\log x$, not $1/\log x$ as we want. So there is already something sketchy here. I don't have an intuition for why the right constant in the PNT is $1$, not $e^{-\gamma}$ or $2 e^{- \gamma}$, but since I already know that there is an issue with this sort of argument, I wouldn't take it too seriously in predicting exactly when PNT would fail. (To clarify, I know many arguments why the constant must be $1$: For example, $\sum_{p \leq n} \frac{n}{p} \log p$ should be $\approx \log n! \approx n \log n$, and this only works if the constant is $1$. And I know why the sieve argument doesn't rigorously prove that $\pi(x) \approx e^{-\gamma} x / \log x$. What I don't have is a gut level understanding of why the sieve formula is right up to the constant factor, but not actually right.)

None of this amounts to an argument FOR the conjectures of Granville and Soundararajan, it just argues that I wouldn't take your heuristic particularly seriously.

-
I need to digest your answer a bit more, but just a comment on your second part: The Euler product must be used a bit carefully. E.g. in the intervals $s_k=\{p_k^2,\dots,p_{k+1}^2\}$ should only products of primes smaller than $p_{k+1}^2$ be included in the expansion of the Euler product. This alone significantly reduces the constant (from $2\textrm{e}^{-\gamma}\approx 1.12$ to $\approx 1.03$). –  user45947 Aug 5 '14 at 20:58
Not sure whether I agree with that or not, but it gives a good example of why the intersection isn't close enough to the product to conclude that the individual terms of the product being off would necessarily drag the size of the intersection off. –  David Speyer Aug 5 '14 at 21:28
To put it another way, if you are thinking in terms of expanding the Euler product and handling each term separately, than you should also expect problems for $y \approx x$, since then the $p_i p_j$ terms are not well approximated by $y/(p_i p_j)$ for $p_i$, $p_j \approx \sqrt{x}$. –  David Speyer Aug 5 '14 at 21:30
There is some miracle happening already to let this argument work for $y \approx x$. Since I don't know where the miracle is coming from, I don't feel confident that I can predict when the miracle will stop working. –  David Speyer Aug 5 '14 at 21:54
In your comment, it wounds like you are saying that $y \sum_{n \leq \sqrt{x}} \frac{\mu(n)}{n}$ is a better approximation to $\pi(x+y)-\pi(x)$ than $y \prod_{p \leq \sqrt{x}} (1-1/p)$ is. But that is very false! Assuming RH and summing by parts, $\sum_{n \leq w} \frac{\mu(n)}{n} = O(w^{1/2+\epsilon}/w) = O(w^{-1/2+\epsilon})$, which is completely the wrong order. –  David Speyer Aug 5 '14 at 23:23

The short answer is no. It is likely to be sufficient, although right now the best known is actually that pi(x + x^{0.525}) > pi(x) for all large x (and likely all x > 117). If it were necessary, this would go against the conjectures of Granville and Soundararajan that you cite, as epsilon smaller than 1/2 would not be good enough.

-
I am making assumptions about the meaning of ~. In particular, if x is less than 2, ~ should handle a lot of error, and ~ should handle "enough" error for x at least 2 and reasonably small. I expect future work will show better sufficient values for y, and it will take some time before good necessary values appear. –  The Masked Avenger Aug 5 '14 at 15:26
To be fair, this answer is not based on the heuristic. As I state, I already know that it goes against the conjectures of Granville and Soundararajan. I'll add a clarification in the question to make the heuristic clearer. See if you agree then. If you disagree I would be very happy to have any fallacy in my argument pointed out. That is, after all, why I posed the question. –  user45947 Aug 5 '14 at 17:38
Then you are asking the wrong question. If you replaced the conjecture with "76543 is composite", the only reasonable short answer to your question is no. While the conjecture stated is not as certain, it will contradict things no matter what your heuristic. You should be more concerned with isolating the assumptions and possible flaws in your heuristic, and less about trying to turn implausible things plausible. –  The Masked Avenger Aug 5 '14 at 17:58
I'm not really sure what you mean here. What I'm saying is that the distribution of primes across an interval $s_k$ can be seen as a construct of the periodic sequences $\rho_i(n)$, $1\leq i \leq k$. That is a fact. Now, my claim is that to sample correctly across this construct, we need to use a sample length longer than the largest underlying period. These are the assumptions, and I wonder if I this is correct, or if I possibly have managed to miss something of importance that would flaw the heuristic. –  user45947 Aug 5 '14 at 18:04
For example, a better question (but not for MO) is "Does the argument below constitute a proof or sketch thereof that the stated heuristic implies the stated conjecture?" You might get a better response by asking if a piece of the result is already in the literature, but you have to do the work of making that part of the argument an actual result. –  The Masked Avenger Aug 5 '14 at 18:05