9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @BeKind Thanks! $\endgroup$
    – Brian
    Jul 19 at 14:06
  • 1
    $\begingroup$ 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... $\endgroup$ Jul 19 at 14:38
  • $\begingroup$ @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. $\endgroup$
    – Brian
    Jul 19 at 14:53

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – TonyK
    Jul 19 at 17:14
  • $\begingroup$ 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. $\endgroup$
    – sbares
    Jul 19 at 21:54
  • $\begingroup$ @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. $\endgroup$ Jul 20 at 9:13
4
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Gary
    Jul 21 at 4:42
  • 1
    $\begingroup$ @Brian Are you able to check the cases $N<678407$ using a computer programme? $\endgroup$
    – Gary
    Jul 21 at 5:49
  • 1
    $\begingroup$ @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! $\endgroup$
    – Brian
    Jul 21 at 5:53
2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Brian
    Jul 21 at 13:05
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.