You are currently browsing the tag archive for the ‘Prime Number Theorem’ tag.

In 1737, Euler presented a novel proof of the infinitude of the primes, in showing that the harmonic sum of the primes diverges.  Explicitly, Euler’s work furnishes the estimate

$\displaystyle\sum_{p \leq x} 1/p=\log \log x + O(1),$

in which the sum exhausts the rational primes at most $x$.  At this point, it becomes quite elementary to derive the two inequalities

$\displaystyle\limsup_{n \to \infty} \frac{p_n}{n \log n} \geq 1 \quad \text{and} \quad \liminf_{n \to \infty} \frac{p_n}{n \log n} \leq 1.$

Results of this flavor remained essentially unimproved for over a century, until Chebyshev presented the following landmark theorem in 1852:

Theorem (Chebyshev): There exist positive constants $c_1,c_2$ such that

$\displaystyle c_1 \leq \liminf_{x \to \infty} \frac{\pi(x)\log x}{x} \leq \limsup_{x \to \infty} \frac{\pi(x) \log x}{x} \leq c_2.$

Thus Chebyshev’s Theorem shows that $x/\log x$ represents the growth rate (up to constants) of $\pi(x)$; stated equivalently in Bachmann-Landau notation, we have $\pi(x) \in \Theta(x/\log x)$.  Yet more is true: the constants$c_1,c_2>0$ in Chebyshev’s proof are therein made effective, and can be taken as

$c_1 =\frac{\log 2}{2} +\frac{\log 3}{3} + \frac{\log 5}{5}-\frac{\log 30}{30} \approx 0.921292;$

$c_2 = \frac{6}{5}\left(\frac{\log 2}{2} +\frac{\log 3}{3} + \frac{\log 5}{5}-\frac{\log 30}{30}\right)\approx1.10555.$

As a corollary to Chebyshev’s Theorem, we have $\pi(2n-3)>\pi(n)$ for$n \gg 0$.  By making this implicit bound on $n$ precise, Chebyshev was able to prove Bertrand’s Postulate (thereafter known as the Bertrand-Chebyshev Theorem).

In this post, we’ll prove a variant of Chebyshev’s Theorem in great generality, and discuss some historically competitive bounds on the constants $c_1$ and $c_2$ given above.  Lastly, we’ll discuss how Chebyshev’s Theorem relates to proposed “elementary” proofs of the PNT.

Let $S_n$ denote the permutation group on n letters.  Herein, we consider the following question, brought to light by Landau in 1902:

Question: What is the maximal order of an element in $S_n$?

By convention, we shall refer to this maximal order as $g(n)$.  Thus, for instance, Lagrange’s theorem gives the elementary bound $g(n) \leq n!$.  We may obtain sharper bounds by noting that $S_n$ is centerless, but tweaks like this will fail to give more than a gain of a multiplicative constant.  A far more productive route comes from the following Proposition:

Proposition: Let $\{a_1,\ldots, a_k\}$ be a partition of n into positive integers.  Then $\prod_i a_i \leq 3^{n/3}$, with equality if and only if $a_i = 3$ for all i.

Proof: Let $\{a_1,\ldots, a_k\}$ be a partition of n such that $\prod a_i$ is maximized.  If $a_i >3$ for any i, we have $2(a_i-2)>a_i$, and the partition

$\{a_1,\ldots, a_{i-1}, 2, a_i-2,a_{i+1},\ldots, a_k\}$

admits a strictly larger product.  Thus, we may assume that $a_i =2,3$ for all i. Furthermore, the relation $2^3 <3^2$ implies that in a maximal partition we may have $a_i =2$ for at most two such i.  It now follows (by cases) that our maximal product $A(n)$ takes the form

$A(n) = \begin{cases} 3^{n/3}, \hspace{15.5 mm} n \equiv 0 \mod 3 \\ 4 \cdot 3^{(n-4)/3}, \quad n \equiv 1 \mod 3 \\ 2 \cdot 3^{(n-2)/3}, \quad n \equiv 2 \mod 3 \end{cases}.$

Our result follows from the inequalities $4 \cdot 3^{-4/3} < 2 \cdot 3^{-2/3} <1$. $\square$

Note: buried under all of this is the fact that the function $f(x) = x^{1/x}$ attains a global maximum at $x=e$, and that 3 is the closest integer to e (this also underlies the marginal appearance of 2, as the second closest integer approximation to e).  This will become more evident as we continue.

As a Corollary, we obtain a new upper bound for the function $g(n)$:

Corollary: For all n, we have $g(n) \leq 3^{n/3}$, with equality if and only if $n=3$.

Proof: We note that $g(n)$ is the maximum value of $\mathrm{lcm}(a_1,\ldots a_k)$, as $\{a_i\}$ varies over the partitions of n.  But $\mathrm{lcm}(a_1\ldots, a_k) \leq \prod a_i \leq 3^{n/3}$, with equality if and only if (1) $a_i =3$ for all and (2) the $\{a_i\}$ are pairwise coprime.  In particular, equality holds above if and only if $n=3$ (achieved with the partition $\{3\}$). $\square$

Note: this result is stronger than the commonly-cited bound $g(n) < e^{n/e}$, which holds for all n.

The bound arising from our Proposition is nevertheless weak in method (in that we have only used the fact that $\mathrm{lcm}(a_1,\ldots,a_k)$ divides $a_1\cdots a_k$), and to strengthen it significantly requires the Prime number theorem (PNT).  In fact, Landau’s classical result

$\log g(n) \sim \sqrt{n \log n}$

(which we will derive after the fold) is equivalent to the PNT by means of elementary methods.