4

A $n$-bit integer is an integer $x$ such that $2^{n-1} \le x < 2^n$. In [1] it is claimed without proof that a corollary of the prime number theorem is that:

For any $n > 1$, the fraction of $n$-bit integers that are prime is at least $\frac{1}{3n}$.

Can somebody point me to a proof of this?

It is (perhaps) worth noticing that a direct application of the prime number theorem allows to prove an asymptotic version of the above (with a slightly better constant). $$ \begin{align*} \lim_{n \to \infty} \frac{n \ln 2}{2^{n-1}} \bigg( \pi(2^n-1) - \pi(2^{n-1})\bigg) &= \lim_{n \to \infty} \frac{n \ln 2}{2^{n-1}} \bigg( \pi(2^n) - \pi(2^{n-1}) \bigg) \\&= \lim_{n \to \infty} \frac{n \ln 2}{2^{n-1}} \bigg( \frac{2^n}{n \ln 2} - \frac{2^{n-1}}{(n-1)\log2} \bigg)\\ & = \lim_{n \to \infty} \frac{n \ln 2}{2^{n-1}} \bigg( \frac{2^n}{2n \ln 2 } \cdot\frac{n-2}{n-1} \bigg) = 1. \end{align*} $$

Therefore $\frac{\pi(2^n-1) - \pi(2^{n-1})}{2^{n-1}} \sim \frac{1}{n \ln 2}$, and for every $\varepsilon >0$ there is some $n_0$ such that, for all $n \ge n_0$, the fraction of $n$-bit integers that are prime is at least $\frac{1-\varepsilon}{n \ln 2}$.

A not-so-elegant way to prove the the claim would be that of choosing $\varepsilon =1-\frac{\ln 2}{3} \approx 0.7689$ and finding an upper bound on $n_0$ that lies in the range for which $\pi(\cdot)$ has been computed. Are such upper bounds known?

[1] Jonathan Katz, Yehuda Lindell. Introduction to Modern Cryptography (3rd edition). CRC Press. ISBN 9781351133012.

Steven
  • 165
  • 3
    The prime number theorem, as far as I know, doesn't say anything about any particular interval $[2^n, 2^{n+1})$. It is purely a result about a limit (I don't even think the standard formulation of the theorem says anything about the rate of convergence). So that sounds strange to me. – Arthur Feb 20 '23 at 20:51
  • 1
    @Arthur. Agreed. Perhaps the authors is being a little bit sloppy and is actually referring to some related result. I would still be interested in seeing a proof of the claimed fact (whether that requires the prime number theorem of not). – Steven Feb 20 '23 at 21:18
  • 1
    FWIW, the exact number of $n+1$-digit primes is given by https://oeis.org/A036378 – Dan Feb 20 '23 at 21:58

2 Answers2

4

According to the classic article "Explicit Bounds for Some Functions of Prime Numbers", Barkley Rosser American Journal of Mathematics Vol. 63, No. 1 (Jan., 1941), pp. 211-232 (22 pages) for $x \ge 55$, $\dfrac{x}{\log x+2} \lt \pi(x) \lt \dfrac{ x}{\log x-4} $.

Therefore, putting $x=2^n$, $\dfrac{ 2^n}{n\log 2+2} \lt \pi(2^n) \lt \dfrac{ 2^n}{n\log 2-4} $.

Therefore $\dfrac{ 2^n}{n\log 2+2}-\dfrac{ 2^{n-1}}{(n-1)\log 2-4} \lt \pi(2^n)-\pi(2^{n-1}) \lt \dfrac{ 2^n}{n\log 2-4}-\dfrac{ 2^{n-1}}{(n-1)\log 2+2} $.

Those differences are about (more explicitness later)

$\begin{array}\\ D &=\dfrac{ 2^n}{n\log 2}-\dfrac{ 2^{n-1}}{(n-1)\log 2}\\ &=\dfrac{ 2^n}{n\log 2}\left(1-\dfrac{\frac12}{1-\frac1{2n}}\right)\\ &=\dfrac{ 2^n}{n\log 2}\left(\dfrac{1-\frac1{2n}-\frac12}{1-\frac1{2n}}\right)\\ &=\dfrac{ 2^n}{n\log 2}\left(\dfrac{\frac12-\frac1{2n}}{1-\frac1{2n}}\right)\\ &=\dfrac{ 2^n}{2n\log 2}\left(\dfrac{1-\frac1{n}}{1-\frac1{2n}}\right)\\ &=\dfrac{ 2^n}{2n\log 2}\left(\dfrac{1-\frac1{2n}-\frac1{2n}}{1-\frac1{2n}}\right)\\ &=\dfrac{2^n}{2n\log 2}\left(1-\dfrac{\frac1{2n}}{1-\frac1{2n}}\right)\\ &=\dfrac{2^n}{2n\log 2}\left(1-\dfrac{1}{2n-1}\right)\\ &\approx\dfrac{ 2^n}{2n\log 2}\\ \end{array} $

For the lower bound,

$\begin{array}\\ L(n) &=\dfrac{ 2^n}{n\log 2+2}-\dfrac{ 2^{n-1}}{(n-1)\log 2-4}\\ &=\dfrac{ 2^n((n-1)\log 2-4)-2^{n-1}(n\log 2+2)}{(n\log 2+2)((n-1)\log 2-4)}\\ &=\dfrac{ 2^{n-1}(2(n-1)\log 2-8)-(n\log 2+2))}{n(n-1)\log^22-4n\log 2+2(n-1)\log 2-8}\\ &=\dfrac{2^{n-1}(n \log 2-2\log 2-10)}{n(n-1)\log^22-2n\log 2+2\log 2-8}\\ \end{array} $

I will leave it at this for now, and a similar expression can be derived for the upper bound.

Steven
  • 165
marty cohen
  • 107,799
1

This is just a more detailed write-up of the strategy proposed by Marty Cohen's answer.

We can prove the stronger claim: for $n \ge 1$ there are at least $\frac{2^{n-2}}{2n}$ $n$-bit prime numbers (i.e., the fraction of $n$-bit prime numbers is at least $\frac{1}{2n}$).

According to [1], for $x \ge 55$, $\dfrac{x}{\log x+2} \lt \pi(x) \lt \dfrac{ n}{\log x-4} $.

Defining $L(n) = \dfrac{2^n}{n\log 2+2}-\dfrac{ 2^{n-1}}{(n-1)\log 2-4}$ we have: $ \pi(2^n -1 )-\pi(2^{n-1}) = \pi(2^n)-\pi(2^{n-1}) \ge L(n). $

As a hint that we are going towards the right direction, we notice that $L(n)$ is roughly: $$ \dfrac{ 2^n}{n\log 2}-\dfrac{ 2^{n-1}}{(n-1)\log 2} \approx \dfrac{2^n}{n\log 2}-\dfrac{ 2^{n-1}}{n\log 2} = \dfrac{2^{n-1}}{n\log 2} > \dfrac{2^{n-1}}{n}. $$

More formally, let $\ell(n) = \dfrac{2n \log 2}{n \log 2 + 2} - \dfrac{n \log 2}{(n-1) \log 2 - 4}$: $$ L(n) = \dfrac{2^n}{n\log 2+2}-\dfrac{ 2^{n-1}}{(n-1)\log 2-4} = \dfrac{2^{n-1}}{n \log2} \left( \dfrac{2n \log 2}{n \log 2 + 2} - \dfrac{n \log 2}{(n-1) \log 2 - 4} \right) = \dfrac{2^{n-1}}{n \log2} \cdot \ell(n). $$

Taking the derivative of $\ell(n)$ we see that: $$ \dfrac{d \ell(n)}{dn} = \dfrac{4 \log 2}{(2 + n \log 2)^2} + \frac{(4 + \log 2) \log 2}{(n \log 2 - 4 - \log 2)^2} \ge 0, $$ therefore $\ell(n)$ is defined for all $n \ge 10$ and monotonically increasing. Evaluating $\ell(10)$ we see that $\ell(10) \ge \frac{1}{2}$. Therefore: $$ L(n) \ge \dfrac{2^{n-1}}{n \log2} \cdot \dfrac{1}{2} \ge \frac{2^{n-1}}{2n}. $$

This proves the claim for $n \ge 10$. For $ 2 \le n < 10$ we can exhaustively inspect $\pi(2^n -1 )-\pi(2^{n-1})$.

[1] "Explicit Bounds for Some Functions of Prime Numbers", Barkley Rosser American Journal of Mathematics Vol. 63, No. 1 (Jan., 1941), pp. 211-232

Steven
  • 165