Paul Erdős and Bertrand's Conjecture

Paul Erdős ~1993.

Bertrand's Conjecture is:

For every integer \( n > 1 \), there is a prime number \( p \) such that:\[ n < p < 2n. \]

It's simple and easy to understand and seems certain, considering the plethora of primes (an infinite number!) and how dense they are — about 6% of all integers in the vicinity of 10,000,000, for example, and reasonably distributed. All the same, it took real work to prove it. Bertrand made the conjecture offhandedly in a celebrated paper in 1845 based on examining numbers up to 6,000,000.^[1] Chebyshev proved it convincingly in 1852 and in a way foreshadowing further developments — this is where he introduced \( \theta(x) = {\sum_{p \leq x} \log p} \)^[2]; Chebyshev's proof was inspired but involved some forbidding calculations leading to the thought, "Surely this can be done easier". It can, as Paul Erdős proved in 1932 in his first published article at the age of 19^[3].

Erdős was homeless and itinerant for decades, driven out of Europe by the Nazis and persecuted by the US government in the 1950s for nothing. He didn't even have a passport for years until his native Hungary took pity on him and issued one. He regarded personal possessions as a nuisance, going Proudhon one better ("Property is theft!"). He collaborated massively with hundreds of people, the ones who presumably actually wrote up the results he and they produced when talking at a blackboard in the math department lounge during one of his visits.

One story is that he saw some formulas on the blackboard culminating the work of a couple of functional analysts in a thirty page paper. He knew nothing about functional analysis, but derived a two-line solution in minutes. Conceivably those analysts were not amused, and he was not above imposing collaboration on the unwilling, like the great Atle Selberg, whose unpublished results leading to an elementary proof of the Prime Number Theorem he appropriated to prove said theorem in 1948 (elementary meaning no complex analysis). Of course that led Selberg to an expedited march to the proof, and history has accorded them joint credit. Erdős was God's fool, though not believing in the great one, the Supreme Fascist in his parlance. Don't deny yourself the pleasure of reading about this truly unique, amazing, and crazy-making human being in Joshua Hill's revealing and humorous account Paul Erdős: Mathematical Genius, Human (In That Order)^[4].

He wrote (or better, co-proved the results behind) over 1500 papers, many appearing years after his death in 1996, and was arguably more prolific than Euler, high praise. He may have been skeptical, but did believe in The Book, where God maintains all the perfect proofs to be discovered and brought to light by mere mortals in good time. Not benignly though, those proofs have to be wrestled away from a jealous SF with great effort. Other than his mother, Erdős cared only about Mathematics and thought about nothing else in every waking moment and some non-waking ones — he was notorious for waking up hosts in the middle of the night to share a new insight. What follows is based on William LeVeque's still excellent Topics in Number Theory^[5], Chapter 6, now available cheaply from Dover. Also on Proofs from THE BOOK^[6], Chapter 2, where Martin Aigner and Günter Ziegler collected together some of Erdős's best, working together with the man himself towards the end.

Erdős's proof of Bertrand's Conjecture is based on the numbers \( C_n = {2n \choose n} \), which seems odd until you start looking hard at them. Consider \( C_9 = {18 \choose 9} \), for example:

\[ {18 \choose 9} = {18! \over 9!} = {{18 \cdot \color{red}{17} \cdot 16 \cdot 15 \cdot 14 \cdot \color{red}{13} \cdot 12 \cdot \color{red}{11} \cdot 10} \over {9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}} = {2^2 \cdot 5 \cdot \color{red}{11} \cdot \color{red}{13} \cdot \color{red}{17}} = 48260. \]

All the primes between 9 and 18 occur in the final product exactly once, because they occur once in the numerator but not at all in the denominator and, being primes, nothing in the denominator divides into them. Bertrand's Conjecture is exactly that there are primes in the numerator for every \( n \). Notice also that \( C_n \) grows as \( 4^n \) because:

\[ {C_{n+1} \over C_n} = {{(2(n + 1))! \over {(n + 1)!^2}} \cdot {n!^2 \over {(2n)!}}} = {{2(n + 1)(2n + 1)} \over {(n + 1)(n + 1)}} = {2 \cdot {{2n + 1} \over {n+1}}} = {2\left({2 - {1 \over{n+1}}}\right)}. \]

Just a little slower than \( 4^n \) and, in fact:

\[ C_n = {2n \choose n} < 4^{n-1}, \hspace{15pt} n \geq 5. \]

The \( C_n \) are the red numbers down the middle in the even-numbered rows of Pascal's triangle, a few rows of which are shown in the left margin towards the top of this page. Click that graphic to show still more rows in a popup window (here is a C program to create the triangle). The blue numbers a bit off center in the odd rows are \( {2n + 1} \choose n \). The first step is to get an estimate on the product of all primes up to a given point:

The subscript on the product means that it is taken over all primes \( p \) less than or equal to \( x \). If this is true for the greatest prime \( q \) less than \( x \), then it's true for \( x \), so we can assume \( x \) is an odd prime: \( x = q = {2n + 1} \). It will be a proof by induction and the idea is to break the primes into two groups at the midpoint \( n + 1 \) and consider separately the products of the smaller primes and the product of the larger primes:

\[ {\prod_{p \leq q} p} = {\prod_{p \leq {2n + 1}} p} = \left({\prod_{p \leq {n + 1}} p}\right) \left({\prod_{{n + 1} < p \leq {2n + 1}} p}\right) < {4^n \cdot C_{n+1}} < {4^n \cdot 4^n} = 4^{2n} = 4^{q-1}. \]

(1) holds for the product of the smaller primes on the left, those for \( p \leq {n + 1} \), by induction. All the larger primes in the product on the right are factors of \( C_{n+1} \) as discussed, so their product is less than \( C_n \) and that is less than a power of 4. This establishes (1) for all \( x \).

Another pertinent fact is the absence of primes just less than \( n \) in the factorization of \( C_n = {2n \choose n} \):

This is evident in the table, where there is a paucity of primes just less than \( n \) in the factorization of \( 2n \choose n \); \( 14 \choose 7 \) has no factors of \( 5 \) or \( 7 \), for example, primes in the range \( 14/3 < p \leq 7 \). To see this in general, \( p \leq n \) implies that \( p \) appears in the denominator of \( 2n \choose n \) and will be cancelled by \( 2p \) in the numerator, but there is no \( 3p \) in the numerator because \( 3p > 2n \) by hypothesis, proving (2). The proof is ridiculously simple, but Erdős says this step is crucial — that's number theory for you.

Here's an old theorem of Legendre that will be needed:

\( \lfloor x \rfloor \) stands for the greatest integer less than or equal to \( x \), or the integer floor function. For \( n = 7 \) and \( p = 2 \), for example, this says that the power of \( 2 \) in the factorization of \( 7! \) is exactly:

\[ {\Big{\lfloor}{7 \over 2}\Big{\rfloor} + \Big{\lfloor}{7 \over 4}\Big{\rfloor} + \Big{\lfloor}{7 \over 8}\Big{\rfloor} + \cdots} = {3 + 1 + 0} = 4. \]

To see this, write out \(7! = 5040 = {7 \cdot \color{red}{6} \cdot 5 \cdot \color{red}{\underline{4}} \cdot 3 \cdot \color{red}{2} \cdot 1} \), and keep an eye on every other factor, the ones in red divided by \( 2 \). There are \( {\Big{\lfloor}{7 \over 2}\Big{\rfloor}} = 3 \) of them, as many times as \( 2 \) divides into \( 7 \), ignoring any remainder. Dividing \( 7 \) by \( 4 \) counts every fourth factor, those divided by \( 4 \) — \( 4, 8, 12, \) and so on — each of which contributes a factor of \( 2 \) not included in the original sweep. In this case, there is only one, \( 4 \) itself. Note that dividing by powers of \( p \) greater than \( n \) makes no contribution to the sum, \( \lfloor {7 \over 8} \rfloor \) in the example; the summands are all zero from that point on. The general proof proceeds exactly as indicated in this example.

Next is this:

Take \( 18 \choose 9 \) as an example again to see why this is so:

\[ {18 \choose 9} = {{18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} \over {(9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1)}^2}. \]

(4) is clear for primes \( n < p < 2n \) because they are all to the first power. Problems may arise with the smaller primes though; let's determine the power of \( 2 \) representing \( {18 \choose 9} \) in in its prime power factorization (it is \( 2^2 \)). Using the approach in Legendre's Theorem (3), \( 2 \) divides the numerator \( \Big{\lfloor}{18 \over 2}\Big{\rfloor} \) times and the denominator \( 2 \cdot \Big{\lfloor}{9 \over 2}\Big{\rfloor} \) times, so applying (3) results in the first summand, the one for \( 2^1 \), being \( {\Big{\lfloor}{18 \over 2}\Big{\rfloor}} - {2 \cdot \Big{\lfloor}{9 \over 2}\Big{\rfloor}} = {9 - 2 \cdot 4} = 1. \) Applying (3) systematically for all powers of \( p \) until zeros start coming up:

\[ {k = 1 :} \hskip{16pt} {\Big{\lfloor}{18 \over 2}\Big{\rfloor}} - {2 \cdot \Big{\lfloor}{9 \over 2}\Big{\rfloor}} = {9 - 2 \cdot 4} = 1 \\
{k = 2 :} \hskip{16pt} {\Big{\lfloor}{18 \over 4}\Big{\rfloor}} - {2 \cdot \Big{\lfloor}{9 \over 4}\Big{\rfloor}} = {4 - 2 \cdot 2} = 0 \\
{k = 3 :} \hskip{16pt} {\Big{\lfloor}{18 \over 8}\Big{\rfloor}} - {2 \cdot \Big{\lfloor}{9 \over 8}\Big{\rfloor}} = {2 - 2 \cdot 1} = 0 \\
{k = 4 :} \hskip{16pt} {\Big{\lfloor}{18 \over 16}\Big{\rfloor}} - {2 \cdot \Big{\lfloor}{9 \over 16}\Big{\rfloor}} = {1 - 0 = 1} \\
{k = 5 :} \hskip{16pt} {\Big{\lfloor}{18 \over 32}\Big{\rfloor}} - {2 \cdot \Big{\lfloor}{9 \over 32}\Big{\rfloor}} = {0 - 0 = 0}. \]

The sum of those values is the power of \( 2 \) being sought: \( {1 + 0 + 0 + 1 + 0} = 2 \). Notice that the summands are all \( 0 \) or \( 1 \), which follows from the general observation that \( 0 \leq {\big{\lfloor}{x}\big{\rfloor}} - 2 {\big{\lfloor}{x/2}\big{\rfloor}} \leq 1 \), so the expression in the middle, being an integer, is exactly \( 0 \) or \( 1 \). In this case, the sum really stops at \( k = 4 \), so certainly the highest power of \( 2 \) dividing \( 18 \choose 9 \) is less than or equal to the \( 4^{\text{th}}, 2^4 \). Here is the general formula, where \( r \) is highest power of \( p \) dividing \( 2n \choose n \):

\[ {\sum_{k=1}^r \left({\Big{\lfloor}{2n \over p^k}\Big{\rfloor}} - {2 \cdot \Big{\lfloor}{n \over p^k}\Big{\rfloor}}\right)} \leq r. \]

The idea is that each of the summands is \( 0 \) or \( 1 \) and there are no more of them than \( r \), the point beyond which they're all zero. \( p^r \leq 2n \), and the highest power of \( p \) dividing \( 2n \choose n \) is less than or equal to that. It follows immediately that if \( p | {2n \choose n} \) and \( p > \sqrt{2n} \), then \( p^2 \not | {2n \choose n} \) (otherwise \( p^2 | {2n \choose n} \), even though \( p^2 > 2n \)).

The plan of the proof is to bound \( 2n \choose n \) above and below and then derive a contradiction on the assumption that there are no primes \( n < p < 2n \). A simple lower bound is:

\[ {4^n \over {2n + 1}} < {2n \choose n}. \]

To see this, write \( 2^m = {(1 + 1)}^m = \sum_{k=1}^m {m \choose k} \); that is, the sum of the binomial coefficients on the \( m^{th} \) row is \( 2^m \). Therefore their average is \( 2^m / {(m + 1)}\), which must be less than the greatest of them, the one in the middle, \(m \choose m/2 \) if m is even. The result follows by putting \( m = 2n \). Now we can sandwich \( 2n \choose n \):

Here's where it all comes together. The factors in the first product come in clumps \( p^r \) with each clump less than \( 2n \) by (4), so including a factor of \( 2n \) for eachclump accounts for the first product. The middle product includes each prime in the range \( \sqrt{2n} < {p \leq {2 /3} \cdot n} \) just once, as justified a bit above. Note there is no accounting for primes between \( {2 /3} \cdot n \) and \( n \), because there are none. The crux of the proof is assuming that there are no primes between \( n \) and \( 2n \) — that is, that the third product is \( 1 \) — and then deriving a contradiction.

The first product in (5) is less than \( {(2n)}^{\sqrt{2n}} \), because there are fewer primes under \( \sqrt{2n} \) than \( \sqrt{2n} \) itself, the simpler expression just taking \( 2n \) as a factor that many times. The second product is bounded by \( 4^{2/3 \cdot n - 1} \) according to (1), and the third product is assumed to be \( 1 \). This boils down to:

\[ {4^n \over {2n + 1}} < {(2n)}^{\sqrt{2n}} \cdot 4^{2/3 \cdot n - 1}. \]

The \( 2n + 1 \) in the denominator on the left can be replaced by \( 4n^2 \), because \( {2n + 1} < n^2 \text{ for } n \geq 1 \). Further simplification results in:

But the left side of (6) grows faster than the right side, eventually becoming and staying larger than it as \( n \) increases. In other words, (6) is true for only finitely many \( n \). To see this, take \( \log_4 \) of both sides of (6), substituting \( x^2 \) for \( 2n \):

\[ {{n \over 3} + 1} < {(\sqrt{2n} + 2)} \log_4 2n. \]

\[ {{x^2 \over 6} + 1} < {(x + 2)} \log_4 x. \]

These inequalities are true if and only if (6) is, since \( \log \) increases monotonically. The left side is \( \mathcal{O}(x^2) \), the right side \( \mathcal{O} (x \log{x}) \), proving that (6) is true for only finitely many \( n \). The entire argument collapses without the two-thirds rule (2), as Erdős said — the \( n / 3 \) in the exponent of (6) on the left becomes \( 0 \) and the final key inequality becomes vacuous. A short program shows that (6) fails for \( n \geq 499 \), so Bertrand's Conjecture holds in that range. Simple direct calculations show that it holds for \( n < 499 \), so the conjecture is true for all \( n \). QED.

Mike Bertrand

February 20, 2015

^ 1. Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme (Memoir on the number of values that a function can take when the letters it contains are permuted), by Joseph Bertrand, Journal De L'Ecole Royale Polytechnique, Tome I, 1845 (p 123-140).

^ 2. Mémoire sur les nombres premiers (Memoir on the prime numbers), by Pafnuty Chebyshev, Oeuvres de P. L. Tchebychef (ed A. Markoff and N Sonin), Tome XVIII, 1845 (p 51-70). Mémoire originally published in 1852.

^ 3. Beweis eines Satzes von Tschebyschef (Proof of a theorem of Chebyshev), by Paul Erdős, Acta Universitatis Szegediensis (Szeged, Hungary), 5, 1932 (p 194-198).

^ 4. Paul Erdős: Mathematical Genius, Human (In That Order) , by Joshua Hill, June 4, 2004.

^ 5. Topics in Number Theory, Volume I, by William LeVeque (Addison-Wesley, 1956).

^ 6. Proofs from THE BOOK, by Martin Aigner and Günter Ziegler (Springer, 1998), ISBN 3-540-63698-6.