Skip to main content
1 of 3
Terry Tao
  • 114.2k
  • 33
  • 462
  • 539

Just to flesh out Lucia's predicted negative answer a little bit using the older heuristic arguments from

Granville, Andrew, Harald Cramér and the distribution of prime numbers, Scand. Actuarial J. 1995, No. 1, 12-28 (1995). ZBL0833.01018.

(see also Prediction 17 of this blog post of mine).

Let $X$ be large. Let us restrict attention to intervals of the form $[WN-\log^2 X,WN+\log^2 X]$, where $W := \prod_{p \leq w} p$, $w := \frac{\log X}{\log\log X}$, and $X/W \leq X \leq 2X/W$. We have $W = X^{o(1)}$, so the number of such intervals for a given $X$ is $X^{1-o(1)}$. If each of these intervals has a "probability" of $\gg X^{-0.99}$ of containing fewer than $\log X$ primes, and we believe these probabilities to be independent, then in analogy with the law of large numbers, we expect at least one of these intervals to furnish a counterexample to your inequality.

The point is that most of the numbers in the interval $[WN-\log^2 X,WN+\log^2 X]$ are already known to be composite: the only numbers that have a chance of being prime are of the form $WN \pm 1$, $WN \pm p$ for some prime $w \leq p \leq \log^2 X$, or $WN \pm pq$ for some primes $w \leq p,q$ with $p q \leq \log^2 X$. One can check that the total number of candidates here is roughly $\frac{2\log^2 X}{\log(\log^2 X)} = \frac{\log^2 X}{\log\log X}$, by the prime number theorem (it is the $WN \pm p$ candidates that dominate).

On the other hand, the Cramer-Granville model (see previous reference) predicts that each such candidate has a "probability" of $\approx \frac{W}{\phi(W)} \frac{1}{\log X} \approx \frac{e^\gamma \log\log X}{\log X}$ of being prime (this calculation comes from Mertens' theorem). If we believe these events to be independent, then we expect the number of primes in $[WN - \log^2 X, WN + \log^2 X]$ to be distributed like a Poisson random variable of mean $$ \lambda := \frac{\log^2 X}{\log\log X} \frac{e^\gamma \log\log X}{\log X} = e^\gamma \log X.$$

Now, a standard application of Stirling's formula shows that the probability that a Poisson variable of mean $\lambda$ is less than $\lambda (1+u)$ for some $-1 < u < 0$ is about $\exp(-\lambda h(u))$ where $h(u) := (1+u) \log (1+u)-u$, ignoring lower order terms (see e.g., this blog post of mine, and compare also with Bennett's inequality). Applying this with $u = e^{-\gamma}-1$, we predict that the probability of having fewer than $\log X$ primes is approximately $$ \exp(-\lambda h(u)) \approx X^{-0.20386}$$ which well above our target of $X^{-0.99}$, giving the desired prediction. As noted by Lucia, the same analysis would in fact predict that one of these intervals would have $\lessapprox 0.27 \log X$ primes.

It's possible that a numerical search specifically targeting intervals of the above form may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.

Terry Tao
  • 114.2k
  • 33
  • 462
  • 539