Let $X$ be a positive integer. Then $\pi{(X+\ln^2{X})}-\pi{(X-\ln^2{X})}>\ln{X}$?

Question

• The prime-counting function is the function counting the number of prime numbers less than or equal to some real number $x$. It is denoted by $\pi{(x)}$. Using my computer I found that for any positive integer $X\leq 10^{9}$, $$\pi{(X+\ln^2{X})}-\pi{(X-\ln^2{X})}>\ln{X}$$

• Question: Does the result hold for all positive integers $X$?

Answer 1

The answer is No.

According to Mathematica, for $X=1693182318746937$, we have

$$ \pi{(X+\ln^2{X})}-\pi{(X-\ln^2{X})} = 34 < 35.065... = \ln{X} $$

Why this $X$? The Cramér–Shanks–Granville ratio is the ratio of the largest gap between consecutive primes up to $N$ and $\ln^2 N$. The largest known value of this ratio is $0.92...$ for the sequence of $1131$ consecutive composites starting from prime $1693182318746371$. So I just tried X to be the midpoint of this sequence and it worked. Because there are no primes at all at distance less than $0.46 \ln^2 X$ from this $X$, it is not surprising that the number of primes at distance $\ln^2 X$ is smaller than $\ln X$.

Answer 2

Concerning lower bounds, we don't even know that the left-hand side is positive for every sufficiently large $X$. The best result of this kind is that, for every sufficiently large $X$, $$\pi(X+X^{0.525})-\pi(X)\geq\frac{9}{100}\frac{X^{0.525}}{\ln x}.$$ See the last display in Baker-Harman-Pintz: The difference between consecutive primes, II. Note that $X^{0.525}$ is much larger than $\ln^2 X$, and the above result is the state-of-the-art.

Concerning upper bounds, Maier (1985) proved the surprising result that there is a constant $c<1$ such that for any $X_0>0$ there exists $X>X_0$ satisfying $$\pi(X+\ln^2 X)-\pi(X)<c\ln X.$$

Answer 3

It is a subtle matter even to make a guess on how many primes must exist in such short intervals. A recent study of this, and related problems, was made in the paper of Granville and Lumley (the paper has appeared in Experimental Math). In different ranges of $x$ and $y$, Granville and Lumley study $$ M(x,y) = \max_{X \in [x,2x]} (\pi(X+y)-\pi(X)) $$ and $$ m(x,y) = \min_{X\in [x,2x]} (\pi(X+y)-\pi(X)); $$ the maximum and minimum number of primes in an interval of length $y$. Particularly interesting is the range when $y$ is around $t (\log x)^2$, for a constant $t$. Here they conjecture (even if a bit tentatively) that $$ M(x,y) \sim u_{+}(Ct) \log x, \text{ and } m(x,y) \sim u_{-}(ct) \log x, $$ for certain constants $C$ and $c$. Here, for all $t>0$, $u_+(t)$ is the unique solution with $u_+(t) > t$ to the equation $$ u (\log u - \log t -1) + t=1, $$ and for $t>1$ we define $u_{-}(t)$ to be the unique solution to the same equation that lies below $t$. The constant $c$ is suggested to be $e^{\gamma}/2=0.890536\ldots$, and the constant $C$ is another quantity arising in sieve theory, about $1.015$.

In the question at hand, the length of the interval $y$ is about $2(\log x)^2$. So applying the Granville-Lumley prediction, one would obtain that $$ m(x,y) \sim u_{-}(e^{\gamma}) \log x \approx 0.27 (\log x). $$ In other words, the question raised here is predicted by Granville and Lumley to be false.

But these questions are very delicate, and even obtaining with some confidence what the right conjecture should be is not an easy task. The numerical data is inconclusive, and the heuristics developed in Granville and Lumley are in keeping with all we know so far, but there could still be surprises.

Answer 4

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/2W \leq N \leq X/W$ is an integer. 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 < p \leq \log^2 X$, or $WN \pm pq$ for some primes $w < 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 is 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 (maybe after numerically optimizing the $w, X$ parameters to maximize the predicted probability of success for a given budget of search time, and maybe also shifting to $[WN, WN+2\log^2 X]$ instead which has marginally fewer candidates) may actually produce an explicit counterexample, although in practice convergence to these sorts of predictions is quite slow.