Today I Learned

May 26th

Today I learned the proof that there are infinitely many primes start with the string $1234,$ from here Ultimately, this is a size issue: the distance between $1234\cdot10^n$ and $1235\cdot10^n$ is potentially too large to avoid $\pi(n)\sim n/\log n.$ To that end, we show the following.

This is a generalization of Bertrand's postulate (which is $\delta=1$), so we kill it with the prime number theorem machinery that kills Bertrand's postulate. Starting from the top, we want to be sure that, for sufficiently large $n,$\[\pi((1+\delta)n)\stackrel? \gt \pi(n).\]We would like to use the prime number theorem to estimate $\pi(n)\sim n/\log n,$ but of course this is continuous while the above is discrete. So the inequality we actually will attack is\[\pi((1+\delta)n)\stackrel?\ge\pi(n)+1.\]Because $\pi$ is discrete, this is equivalent to the earlier one, but now we can more readily make things discrete.

The prime number theorem is what moves things to continuous; we know\[\lim_{n\to\infty}\frac{\pi(n)}{n/\log n}=1.\]The problem using with this statement is that it is relatively ineffective: we have a rough estimate of the number of primes, but we need to be sure a prime exists for our lemma. To make this effective, we use the definition of a limit: take $\varepsilon \gt 0$ small (fixed later) so that we can pick up $N$ so that $n\ge N$ implies\[1+\varepsilon \gt \frac{\pi(n)}{n/\log n} \gt 1-\varepsilon.\]This is an estimate we can use! Namely, $n\ge N$ also has $(1+\delta)n\ge N,$ so we can say\[\pi((1+\delta)n) \gt (1-\varepsilon)\frac{(1+\delta)n}{\log((1+\delta)n)},\]and similarly $(1+\varepsilon)\frac n{\log((1+\delta)n)} \gt (1+\varepsilon)\frac n{\log(n)} \gt \pi(n).$ Now, to prove the inequality of interest, it suffices for\[(1-\varepsilon)\frac{(1+\delta)n}{\log((1+\delta)n)}\stackrel?\ge(1+\varepsilon)\frac n{\log((1+\delta)n)}+1.\]We remark here that we have made the denominators equal so that the expansion is less painful. In particular, we now need\[(1-\varepsilon)(1+\delta)n-(1+\varepsilon)n\stackrel?\ge\log((1+\delta)n).\]Now, $(1-\varepsilon)(1+\delta)-(1+\varepsilon)$ simplifies to $\delta-(2+\delta)\varepsilon,$ so we can set $\varepsilon:=\frac12\cdot\frac{\delta}{2+\delta}$ so that $\delta-(2+\delta)\varepsilon=:\varepsilon_0$ is some positive constant. Thus, we have left to show\[\varepsilon_0n\stackrel?\ge\log((1+\delta)n).\]The right-hand side is linear while the left-hand is logarithmic, so this inequality will hold for sufficiently large $n.$ For example, we can say that\[e^{\varepsilon_0n}=\sum_{k=0}^\infty\frac{(\varepsilon_0n)^k}{k!} \gt \frac12\varepsilon_0^2n^2\]is greater than $(1+\delta)n$ for $n \gt 2(1+\delta)/\varepsilon_0^2.$ This completes the proof. $\blacksquare$

We quickly remark that the above proof can also tell us that there are $2$ primes in the desired range by simply making the desired inequality $\pi((1+\delta)n) \gt \pi(n)+2.$ Nothing in the proof changes except now we need\[\varepsilon_0n \gt 2\log((1+\delta)n),\]which still holds, albeit for a larger "sufficiently large $n.$''

This quickly translates into the desired result.

The integers with base-$b$ prefix $B$ are those $n$ for which there exists a nonnegative integer $k$ such that\[n\in\left[Bb^k,(B+1)b^k\right).\]Thus, we are requiring the existence of primes in $\left[Bb^k,(B+1)b^k\right).$ The key observation is that this actually requiring a primes in\[\left[Bb^k,\frac{B+1}B\cdot Bb^k\right).\]Because $Bb^k$ and $\frac{B+1}BBb^k$ are not prime for $k \gt 2$ (they're divisible by $b^2$) it suffices to find primes in $\left(Bb^k,\frac{B+1}B\cdot Bb^k\right],$ for which the lemma applies. Namely, there will always be a prime for sufficiently large $Bb^k,$ which means there will always be a prime for sufficiently large $k.$ This finishes. $\blacksquare$

The usual tricks to prove Bertrand's postulate without the Prime number theorem probably still work, but I suspect that they will be a lot less effective because the $1+\delta$ bound is potentially quite unforgiving. In the given proof, I don't have to keep track of subtle bounds, but I fear that we might if we try to use Chebychev's bounds or similar.