While reading some course notes from MIT 18.703 (Modern Algebra), I came across the following statement on page 3:
Lemma 22.3. The product of all primes $r$ between $N$ and $2N$ is greater than $2^{N}$.
However, this can quickly be shown false for $N = 8$.
So I had a question: “How many more counterexamples are there?”
Let $\displaystyle{f\left(N\right) = \prod_{N\leq p\leq 2N}p}$.
The inequality in the lemma is $f\left(N\right)\geq 2^{N}$, and our goal is to find all counterexamples to this inequality.
My first instinct was the write some code. [1] The idea was to start searching for counterexamples up to some finite limit and make a conjecture from there. The following code is the main loop, written in C++ using the Number Theory Library (NTL) [2]:
#pragma omp for schedule(dynamic)
for( auto n{ 1 }; n <= upper_bound; ++n )
{
// Get primes between n and 2n.
auto prime_list{ primes_between( n, 2 * n ) };
// Calculate 2^n
exponentials[id].value = NTL::power( NTL::ZZ{ 2 }, n );
exponentials[id].exponent = n;
// Calculate product of primes from list.
auto product{ std::accumulate( std::begin( prime_list ),
std::end( prime_list ),
NTL::ZZ{ 1 },
[]( NTL::ZZ a, std::int64_t b )
{ return a * b; } ) };
// Collect counterexamples.
if( product < exponentials[id].value )
{
buffers[id].push_back({ n, product, exponentials[id].value });
}
}
Simple enough: Spawn a bunch of threads and collect counterexamples by directly checking the inequality for a bunch of integers. The code isn’t very optimized, since each iteration recomputes $2^{n}$ from scratch without shortcutting it by using the previous iteration’s work, but this was just a quick start to get something to work with.
Running my code with up to $N = 100000$ returned three counterexamples: $N = 8,$ $14,$ and $20.$
At $N = 8$, the product of primes between $8$ and $16$ is $143 \lt 256 = 2^{8}$.
At $N = 14$, the product of primes between $14$ and $28$ is $7429 \lt 16384 = 2^{14}$.
At $N = 20$, the product of primes between $20$ and $40$ is $765049 \lt 1048576 = 2^{20}$.
My conjecture was that these were the only ones, and I decided to post a question about it on Math Stack Exchange.
I received the following answer by Joel Moreira soon after.
Proposition 1. There are only finitely many counterexamples. [3]
Proof.
By the prime number theorem, there are $\frac{N}{\log N}\left(1 + o\left(1\right)\right)$ prime numbers up to $N$. Hence, there are about $\frac{2N}{\log\left(2N\right)}\left(1 + o\left(1\right)\right) – \frac{N}{\log N}\left(1 + o\left(1\right)\right) = \frac{N}{\log N}\left(1 + o\left(1\right)\right)$ primes between $N$ and $2N$.
Since any prime in our interval is at least $N$, $f\left(N\right)$ satisfies
$$\log\left(f\left(N\right)\right)\geq \log\left(N^{\frac{N}{\log N}\left(1 + o\left(1\right)\right)}\right) = N\left(1 + o\left(1\right)\right).$$
The inequality $f\left(N\right)\geq 2^{N}$ is satisfied whenever $\log f\left(N\right) \geq \log\left(2^{N}\right) = N\log2.$ Since $\log 2 < 1$, there exists $M > 0$ such that $f\left(N\right)\geq 2^{N}$ for all $N\geq M$.
QED
Of course, this result gives no explicit bounds, so that’s the next line of inquiry. After Joel’s post, I wrote up an analysis for an explicit bound that contained a very basic error, but the error was correctable. We will return to this at the end.
The first correct bound was found by Juan José Alba González.
Proposition 2. $f\left(N\right)\geq 2^{N}$ for all $N\geq10544111$. [4]
Proof.
Let $\displaystyle{g\left(N\right) = \prod_{N<p\leq2N} p} \leq f\left(N\right)$. Then,
$$\log g\left(N\right) = \sum_{N < p\leq2N} \log p = \vartheta\left(2N\right)-\vartheta\left(N\right),$$ where $\vartheta$ is the Chebyshev function.
From [5], we have the inequality
$$\left|\vartheta\left(x\right) – x\right|\leq 0.006788\frac{x}{\log x}$$
for $x\geq 10544111,$ and so we get
$$\vartheta\left(2N\right) – \vartheta\left(N\right) \geq N – 0.006788\frac{N}{\log N}\left(1 + \frac{2\log N}{\log\left(2N\right)}\right)$$
$$\geq N – 0.006788\frac{3N}{\log N} \geq N\log2$$
for $N\geq 10544111$.
QED
This was improved by the user named Gary in a comment to Juan’s answer.
Proposition 3. $f\left(N\right)\geq 2^{N}$ for all $N\geq 678407$.
Proof.
We have a sharper bound for $\vartheta$ [6], namely $\left|\vartheta\left(x\right) – x\right| < \frac{1}{40}\frac{x}{\log x}$ for $x\geq 678407$. Hence, $$\vartheta\left(2N\right) – \vartheta\left(N\right) \geq N\left(1 – \frac{1}{40}\left[\frac{2}{\log\left(2N\right)} + \frac{1}{\log N}\right]\right) > N\log2$$
for $N\geq 678407$.
QED
This bound finally seemed almost computationally tractable, but required a little more insight to optimize the code enough to reach it. The following lemma allows for a much more optimized main loop.
Lemma. Let $\displaystyle{N_{k} = \frac{p_{k} – 1}{2}},$ where $p_{k}$ is the $k$th prime. For all $k\gt 2$ and integers $\nu$ such that $N_{k-1} \lt \nu \lt N_{k}$, we have $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(N_{k}\right)\leq f\left(\nu\right)$.
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$.
Hence, we need only check $N_{k} \lt 678407$, which occurs for $k \lt 104044$.
With this, we have made our search space much smaller, and so I rewrote the main loop in my program.
#pragma omp for schedule(dynamic)
for( auto n{ 1 }; n <= bound; ++n )
{
auto N{ ( primes[n] - 1 ) / 2 };
// Get primes between N and 2N.
auto prime_list{ primes_between(N, 2 * N) };
// Calculate 2^n
exponentials[id].value <<= N - exponentials[id].exponent;
exponentials[id].exponent = N;
// Calculate product of primes from list.
auto product{ std::accumulate( std::begin( prime_list ),
std::end( prime_list ),
NTL::ZZ{ 1 },
[]( NTL::ZZ a, std::int64_t b )
{ return a * b; } ) };
// Collect counterexamples.
if( product < exponentials[id].value )
{
buffers[id].push_back({ N, product, exponentials[id].value });
}
}
I ran this code over night, resulting in no new counterexamples above 20 after 6 hours, 42 minutes, and 43.1 seconds of computation! However, I woke up to the following tightening of the bound by Gary.
Proposition 4. $f\left(N\right)\geq 2^{N}$ for all $N\geq 328$. [7]
Proof.
An even sharper bound for $\vartheta$ can be found in [8].
$$\left|\vartheta\left(x\right) – x\right| \leq 3.965 \frac{x}{\log^{2} x}$$
for all $x\geq 2$.
Hence,
$$\vartheta\left(2N\right) – \vartheta\left(N\right) \geq N\left( 1 – 3.965\left[ \frac{2}{\log^{2}\left(2N\right)} + \frac{1}{\log^{2} N} \right] \right) > N\log 2$$
for all $N\geq 328$.
QED
This lowered the computation time to something like 0.006 seconds, which is much less than 7 hours.
Either way, we have the following result:
Theorem. The product of all primes between $N$ and $2N$ is $\geq 2^{N}$ for all $N\geq 1$, except for $N = 8,$ $14,$ and $20.$
Prior to Juan José Alba González’s analysis, I had done my own analysis, but I retracted it after noticing an error in my work. If I had taken the time to stop and fix the error, this problem would have been solved much sooner.
Proposition 5. $f\left(N\right)\geq 2^{N}$ for all $N\geq 1845$. [9]
Proof.
From [10], we have
$$\frac{x}{\log x} < \pi\left(x\right) < 1.25506\frac{x}{\log x},$$
where the left inequality holds for $x\geq 17$ and the right for $x > 1$.
Therefore, for $N\geq 9$, we have
$$\pi\left(2N\right) – \pi\left(N\right) > \frac{2N}{\log\left(2N\right)} – \frac{1.25506N}{\log N}.$$
We want to find 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 N\geq N\log 2$, is true for all $N\geq M$.
Using the inequality above, we need only find a bound on $N$ such that
$$\left(\frac{2N}{\log\left(2N\right)} – \frac{1.25506N}{\log N}\right)\log N\geq N\log 2.$$
This holds for all $N\geq 1845$.
QED
This would have been a much more reasonable bound than the one I ran my program on, and was already fully searched by the initial implementation. However, I’m glad that I waited to look back at my work, because Gary’s responses gave me some good papers to read.
References
[1] The Code.
[2] The Number Theory Library.
[3] Joel Moreira’s Answer, Math Stack Exchange.
[4] Juan José Alba González’s Bound, Math Stack Exchange.
[5] Pierre Dusart, “Sharper bounds for $\psi$, $\theta$, $\pi$, $p_{k}$.” Rapport de recherche, no. 1998-06, Université de Limoges.
[6] J. Barkley Rosser and Lowell Schoenfeld, “Sharper Bounds for the Chebyshev Functions $\theta\left(x\right)$ and $\psi\left(x\right)$.” Mathematics of Computation, vol. 29, no. 129, Jan. 1975, p. 243.
[7] Gary’s Bound, Math Stack Exchange.
[8] Samuel Broadbent, Habiba Kadiri, Allysa Lumley, Nathan Ng, and Kirsten Wilk, “Sharper Bounds for the Chebyshev Function $\theta\left(x\right)$.” Mathematics of Computation, vol. 90, no. 331, 15 June 2021, pp. 2281–2315.
[9] My Bound (After Correction), Math Stack Exchange.
[10] J. Barkley Rosser and Lowell Schoenfeld, “Approximate Formulas for Some Functions of Prime Numbers.” Illinois Journal of Mathematics, vol. 6, no. 1, Mar. 1962, pp. 64–94.