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 constantsc_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) forn \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.

Read the rest of this entry »

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.

Read the rest of this entry »