The Product of Primes Between $N$ and $2N$ Compared to $2^N$

Question

While reading some course notes from MIT 18.703 (Modern Algebra) on a primality test, I found this lemma (stated without proof):

Lemma 22.3. The product of all prime numbers $r$ between $N$ and $2N$ is greater than $2^{N}$ for all $N\geq1$.

However, one quickly finds that this lemma is false for $N=8$. The primes between $8$ and $16$ are $11$ and $13$, and $11\cdot13 = 143 < 256 = 2^{8}$.

I wondered if there were any more counterexamples, so I decided to write a quick program to test this lemma (the code may be found here). My code is not very optimized, with only very basic parallelism using OpenMP, and so I haven't taken the time to go beyond $N = 100000$. With my code, I have found only three counterexamples:

At $N = 8$, the product of primes between $8$ and $16$ is $143 < 256 = 2^{8}$.

At $N = 14$, the product of primes between $14$ and $28$ is $7429 < 16384 = 2^{14}$.

At $N = 20$, the product of primes between $20$ and $40$ is $765049 < 1048576 = 2^{20}$.

My Questions

1. Are these the only counterexamples?

2. If so, how do we prove it?

3. If not, what are some others, and are there infinitely many? -- Answer: There are not infinitely many, though there may still be further counterexamples.

EDIT 1: Thanks to the responses to this post, I have attempted an analysis of this problem. If possible, I would appreciate any feedback, just in case I made an error or if any improvement could be made by a more careful analysis. -- This analysis was flawed and has been retracted.

EDIT 2: Due to the answer posted by jjagmath, the bound has been lowered to 10544111. I will try to run my program to search for counterexamples below this number, but hopefully even tighter analyses come that lower the bound to a more tractable number to search.

EDIT 3: I retract the analysis that I did because of a mistake. The jjagmath analysis still holds.

EDIT 4:

Let $p_{k}$ be the $k$th prime number, let $\displaystyle{N_{k} = \frac{p_{k} - 1}{2}}$, and let $\displaystyle{f\left(N\right)=\prod_{N\leq p\leq 2N}p}$.

Proposition. Let $k > 2$ be an integer and let $\nu$ be an integer such that $N_{k-1} < \nu\leq N_{k}$. Then, $f\left(N_{k}\right)\leq f\left(\nu\right)$.

Proof. Any prime in the interval $\left[N_{k},2N_{k}\right]$ is also in the interval $\left[\nu, 2\nu\right]$, and so $f\left(\nu\right)$ can only get smaller as $\nu$ increases to $N_{k}$. QED

Corollary. If any counterexamples above $20$ exist, some of them must be of the form $\displaystyle{N_{k} = \frac{p_{k} - 1}{2}}$ for some $k$.

Observation. All counterexamples currently known are in this form: $N_{7} = 8$, $N_{10} = 14$, and $N_{13} = 20$.

At the time of writing, it is known that all integers $N\geq 10544111$ satisfy $f\left(N\right)\geq 2^{N}$, and so we need only check $N_{k} < 10544111$ ($k < 698306$) to see if there are any further counterexamples.

Question. Are there better explicit lower bounds for $N$ beyond which the inequality $\displaystyle{\prod_{N\leq p\leq 2N}p \geq 2^{N}}$ holds?

If we can find a more computationally tractable bound, say $N\geq 1299709$ (so $k \geq 100000$ can be ruled out of the search), then I may be able to run (a modified form of) my program to search for possible counterexamples beyond $N = 20$. Of course, any improvement is welcome!

EDIT 5:

With Gary's comment, the bound has been tightened to $N\geq 678407,$ which should be tractable. I will be running my program overnight and will update with the results!

EDIT 6:

Gary's latest answer has finally finished this problem off! The bound has been tightened to $N \geq 328$ via Chebyshev function bounds, and finally to all $N\geq1$ except $N=8,14,20$ by numerical computation.

This has been a very fun problem to work on, and I thank everyone who was involved! I suppose I will end this post with a revised Lemma 22.3.

Lemma 22.3.$'$ The product of all prime numbers $r$ between $N$ and $2N$ is greater than $2^{N}$ for all $N\geq1$, except for $N = 8, 14, 20$.

EDIT 7:

I went back to my initial analysis where I had made a very trivial error, and it turns out that I would have already had a tractable bound if I decided to look at it again. My analysis seems to show that $f\left(N\right)\geq 2^{N}$ for all $N\geq 1845$.

Gary's analysis still provides a better bound, but I'm happy to know that I would have eventually solved this with just another look at my own work.

Answer 1

Let $$ \theta (x) = \sum\limits_{p \le x} {\log p} $$ be the Chebyshev function of the first kind. The product of the primes between $N$ and $2N$ (with $N\geq 2$) is $$ \prod\limits_{N < p < 2N} p = \prod\limits_{N < p \le 2N} p = \exp (\theta (2N) - \theta (N)). $$ By Corollary $11.2$ in this paper, we have $$ \left| {\theta (x) - x} \right| \le 3.965\frac{x}{{\log ^2 x}} $$ for all $x\geq 2$. Hence, $$ \theta (2N) - \theta (N) \ge N\left( {1 - 3.965\!\left[ {\frac{2}{{\log ^2 (2N)}} + \frac{1}{{\log ^2 N}}} \right]} \right) > N\log 2 $$ for all $N \ge 328$. Consequently, $$ \prod\limits_{N < p < 2N} p > 2^N $$ for $N \ge 328$. Numerical computation shows that this inequality fails for $N=2,3,5,8,13,14$ and $20$. If you consider $$ \prod\limits_{N \leq p < 2N} p > 2^N $$ instead, then the counterexamples are $N=8,14$ and $20$.

Answer 2

As Adam Rubinson mentions in the comments, the number of primes up to $N$ is $\frac N{\log N}(1+o(1))$, where $o(1)$ denotes a quantity that tends to $0$ as $N\to\infty$. Therefore the number of primes between $N$ and $2N$ is $\frac{2N}{\log(2N)}(1+o(1))-\frac{N}{\log N}(1+o(1))=\frac{N}{\log N}(1+o(1))$. Since any such prime is at least $N$, their product $P$ satisfies $\log P>\log\big(N^{\frac{N}{\log N}(1+o(1))}\big) = \frac{N}{\log(N)}(1+o(1))\log N = N(1+o(1))$. Therefore for sufficiently large $N$ we have $\log P>N\log 2=\log(2^N)$, which implies $P>2^N$. This shows that there are only finitely many counterexamples.

Reverse engeneering the proof, it will work as soon as the number of primes between $N$ and $2N$ is at least $\frac N{\log N}\log 2$; since $\log 2\approx 0.7$ is significantly less than $1$, it should be possible to figure out explicitly all the counterexamples.

Answer 3

EDIT: I have fixed the error in my analysis, and actually got a very tractable bound, so I have undeleted this corrected answer.

Thanks to the others who responded, I have the following answer.

Using the top inequality found here, we have that the number of primes in the interval $\left[N,2N\right]$ is

$$\pi\left(2N\right)-\pi\left(N\right) > \frac{2N}{\log\left(2N\right)} - \frac{1.25506N}{\log\left(N\right)}$$

for $N\geq9$.

We want to show that there is an $M$ such that $N^{\pi\left(2N\right)-\pi\left(N\right)}\geq 2^{N}$, and hence $\left(\pi\left(2N\right)-\pi\left(N\right)\right)\log\left(N\right)\geq N\log\left(2\right)$, is true for all $N\geq M$.

Using the inequality above, we can need only find $N$ such that

$$\left(\frac{2N}{\log\left(2N\right)} - \frac{1.25506N}{\log\left(N\right)}\right)\log\left(N\right)\geq N\log\left(2\right).$$

Expanding the left hand side algebraically, we get

$$\left(\frac{2N}{\log\left(N\right) + \log\left(2\right)} - \frac{1.25506N}{\log\left(N\right)}\right)\log\left(N\right) =$$ $$\left(\frac{2N\log\left(N\right) - 1.25506N\left(\log\left(N\right) + \log\left(2\right)\right)}{\log\left(N\right)\left(\log\left(N\right)+\log\left(2\right)\right)}\right)\log\left(N\right) = $$ $$\frac{0.74494N\log\left(N\right) - 1.25506N\log\left(2\right)}{\log\left(N\right)+\log\left(2\right)}$$

Since we want this to be $\geq N\log\left(2\right)$, we may divide both sides by $N$ to get

$$\frac{0.74494\log\left(N\right) - 1.25506\log\left(2\right)}{\log\left(N\right)+\log\left(2\right)}\geq \log\left(2\right).$$

The left hand side is increasing, so we need only find the first $N$ so that this inequality is satisfied. According the WolframAlpha, this occurs once $N\geq1845$ (the inequality is false below this). So we just need to use a computer to test this up to that limit.

Answer 4

We want to estimate $$f(N)=\prod_{N<p\le 2N} p$$

Taking $\log$ we have $$\log f(N) = \sum_{N<p\le 2N} \log p = \theta(2N)-\theta(N)$$ where $\theta$ is the Chebyshev function.

We can use the known bound for $\theta$:

$$|\theta(x)-x|\le .006788 \frac{x}{\log x}$$ valid for $x \ge 10544111$ to get $$\theta(2N)-\theta(N)\ge N -.006788\frac{N}{\log N}\left(1+\frac{2 \log N}{\log(2N)}\right)\ge N-.006788\frac{3N}{\log N}\ge N \log 2$$

for $N\ge 10544111$.

So the inequality $f(N)\ge 2^N$ is true for all $N\ge 10544111$.