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

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.

• @BeKind Thanks! Jul 19 at 14:06
• I think asymptotically it might be true. That is, if we say there are approximately $\frac{2N}{\log(2N)} - \frac{N}{\log(N)}$ primes between $N$ and $2N$. Each prime is $\geq N.$ We might be able to show that for large enough $M,\$ the product of these primes is greater than $N^{\frac{2N}{\log(2N)} - \frac{N}{\log(N)}}$ which is greater than $2^N$ for all $N\geq M.$ I'm not sure of this but it could be worth investigating... Jul 19 at 14:38
• @AdamRubinson That's true, the Prime Number Theorem does give us a lot of primes between $N$ and $2N$ for sufficiently large $N$. I do think that the counterexamples I've found are the only ones, but I'm curious to see a proof. Jul 19 at 14:53

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.

• You say "as soon as", but the number of primes between $N$ and $2N$ is not monotonic in $N$; so there might conceivably be a later counterexample. Jul 19 at 17:14
• All that is needed to complete this are explicit upper and lower bounds for $\pi(x)$. Some results are listed on wikipedia en.wikipedia.org/wiki/Prime-counting_function#Inequalities, from there getting a feasible explicit bound is just a matter of calculation. Jul 19 at 21:54
• @TonyK That was, perhaps, a poor choice of words. To be clear, it is true that there is some $N_0$ such that for all $N>N_0$ the number of primes between $N$ and $2N$ is at least $\frac N{\log N}\log 2$. Such an $N_0$ can be found explicitly using the estimates linked by sbares. Jul 20 at 9:13

We want to estimate $$f(N)=\prod_{N

Taking $$\log$$ we have $$\log f(N) = \sum_{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$$.

• A somewhat better result comes from the 1975 paper of J. Barkley Rosser and Lowell Schoenfeld. Namely $\left| {\theta (x) - x} \right| < \frac{1}{{40}}\frac{x}{{\log x}}$ for $x \ge 678407$. Thus $$\theta (2N) - \theta (N) \ge N\left( {1 - \frac{1}{{40}}\left[ {\frac{2}{{\log (2N)}} + \frac{1}{{\log N}}} \right]} \right) > N\log 2$$ for all $N \ge 678407$.
– Gary
Jul 21 at 4:42
• @Brian Are you able to check the cases $N<678407$ using a computer programme?
– Gary
Jul 21 at 5:49
• @Gary I should be able to. After optimizing a bit, I was able to get to about 250,000 in half an hour. I'll try running it overnight to see if I get there. Thanks so much! Jul 21 at 5:53

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$$.

• This is incredible, thank you! I had reached the previous bound over night after 24163.1 seconds (6h42m43.1s), but now this bound completely negates the need for that. I am very happy with this result, so I have accepted this answer. Jul 21 at 13:05

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.