Chebyshev's Mémoire sur les nombres premiers

P. L. Chebyshev (1821-1894)

Mémoire sur les nombres premiers^[1] is Chebyshev's great work of 1850, where he used ingenious arguments to find the order of \(\pi(x),\) the number of prime numbers less than or equal to \(x,\) and proved Bertrand's postulate, that there is always at least one prime number strictly between \(n\) and \(2n-2\) for every integer \(n > 3.\)^[2] To this end, he introduced:
\begin{align}
\theta(x) &= \sum_{p \leq x} \log{p}\\[1em]
\psi(x) &= \theta(x) + \theta\left(x^{1/2}\right) + \theta\left(x^{1/3}\right) + \ldots,
\end{align}
where the first sum is taken over all primes less than or equal to the positive real number \(x.\) Note that the second sum has a finite number of terms, since for a given \(x, x^{1/n}\) is eventually less than 2 and for such \(n, \; \theta(x^{1/n}) = 0.\)

These functions seem mysterious and unmotivated but are the key to the puzzle.^[3] If the object is to find the number of primes between \(\alpha\) and \(\beta,\) where \(\alpha < \beta,\) then \(\theta(\beta) - \theta(\alpha)\) is the sum of the logarithms of the primes \(p\) such that \(\alpha < p \leq \beta\) and therefore:
\begin{align}
(\pi(\beta) - \pi(\alpha)) \cdot \log(\alpha) & \leq \theta(\beta) - \theta(\alpha) \leq (\pi(\beta) - \pi(\alpha))\cdot \log(\beta)\\[1em]
\therefore {{\theta(\beta) - \theta(\alpha)} \over {\log{\beta}}} & \leq \pi(\beta) - \pi(\alpha) \leq {{\theta(\beta) - \theta(\alpha)} \over {\log{\alpha}}}.\tag{1}
\end{align}
So finding bounds for \(\theta(x)\) will lead to bounds for \(\pi(x).\) If \(\beta = 2 \alpha - 2\) in (1), for example, Bertrand's postulate follows if the left side of (1) is greater than zero. And \(\alpha = 2\) will lead to bounds on \(\pi(\beta).\)

The strategy is:

• Use Stirling's formula to bound \(\psi(x).\)

• Use the bounds on \(\psi(x)\) to bound \(\theta(x).\)

• Use the bounds on \(\theta(x)\) to bound \(\pi(x).\)

Legendre's formula^[4] gives an expression for the highest power of a given prime dividing \(n!\) for any positive integer \(n.\) For a positive real number \(x,\) denote the greatest integer less than or equal to \(x\) by \(\lfloor x \rfloor\); and for prime \(p,\) let \(\nu_p(x)\) be the highest power of \(p\) dividing \(x.\) Then Legendre says:
\[\displaystyle \nu _{p}(n!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor.\]
Proof. The sum is actually finite since eventually \(p^i > n,\) and from that point on the terms are all zero. Let \(n\) be a positive integer and assume \(p = 2\) for concreteness. Then there are exactly \(\lfloor n/2 \rfloor\) even numbers less than or equal to \(n,\) which account for that many factors of 2. But there are generally more — namely, the multiples of four, each of which provides another factor of 2, and there are \(\lfloor n/2^2 \rfloor\) of them contributing more factors of 2. Then there are the multiples of 8, which contribute \(\lfloor n/2^3 \rfloor\) more factors of 2. Continuing in this fashion accounts exactly for all the factors of 2 dividing \(n!.\) The argument is identical for any prime \(p,\) proving the theorem. QED.

Consider \(n = 10\) and \(p = 2\) to illustrate the effect, where \(10! = 3,628,800 = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7\):
\begin{alignat}{1}
10! &= \color{red}{2} \cdot 3 \cdot \color{red}{4} \cdot 5 \cdot \color{red}{6} \cdot 7 \cdot \color{red}{8} \cdot 9 \cdot \color{red}{10} \qquad &\longleftarrow \left\lfloor {\frac{10}{2}} \right\rfloor &= 5 \text{ multiples of } 2 \text{ in } 10!\\[1em]
\frac{10!}{2^5} &= 1 \cdot 3 \cdot \color{red}{2} \cdot 5 \cdot 3 \cdot 7 \cdot \color{red}{4} \cdot 9 \cdot 5 &\longleftarrow \left\lfloor \frac{10}{2^2} \right\rfloor &= 2 \text{ multiples of } 4 \text{ in } 10!\\[1em]
\frac{10!}{2^7} &= 1 \cdot 3 \cdot 1 \cdot 5 \cdot 3 \cdot 7 \cdot \color{red}{2} \cdot 9 \cdot 5 &\longleftarrow \left\lfloor \frac{10}{2^3} \right\rfloor &= 1 \text{ multiple of } 8 \text{ in } 10!\\[1em]
\frac{10!}{2^8} &= 1 \cdot 3 \cdot 1 \cdot 5 \cdot 3 \cdot 7 \cdot 1 \cdot 9 \cdot 5 &\longleftarrow \left\lfloor \frac{10}{2^4} \right\rfloor &= 0 \text{ multiples of } 16 \text{ in } 10!\\[1em]
\end{alignat}
\begin{align}
\therefore \displaystyle \nu _{2}(10!) &= \left\lfloor {\frac {10}{2}}\right\rfloor + \left\lfloor {\frac {10}{2^2}}\right\rfloor + \left\lfloor {\frac{10}{2^3}}\right\rfloor\\[1em]
&= 5 + 2 + 1\\
&= 8.
\end{align}

The relevance of \(T(x)\) is not an entire mystery considering that Stirling's formula, an approximation for \(n!,\) is about to be brought in. The plot thickens with:

Theorem. \(\; T(x) := \log{(\lfloor x \rfloor !)} = \displaystyle\sum_{m=1}^\infty \psi\left(\frac{x}{m}\right)\).

Proof. Here too the sum is finite. Consider:
\[\sum_{m=1}^\infty \sum_{k=1}^\infty \theta\left(\left(\frac{x}{m}\right)^{1/k}\right)=
\left\{
\begin{alignat}{1}\quad
&\theta(x) \! &+ \; \theta\left(x^{1/2}\right) &+ \theta\left(x^{1/3}\right) &+ \; \theta\left(x^{1/4}\right) &+\\
&\theta\left(\frac{x}{2}\right) &+ \; \theta\left(\left(\frac{x}{2}\right)^{1/2}\right) &+ \theta\left(\left(\frac{x}{2}\right)^{1/3}\right) &+ \; \theta\left(\left(\frac{x}{2}\right)^{1/4}\right) &+\\
&\theta\left(\frac{x}{3}\right) &+ \; \theta\left(\left(\frac{x}{3}\right)^{1/2}\right) &+ \theta\left(\left(\frac{x}{3}\right)^{1/3}\right) &+ \; \theta\left(\left(\frac{x}{3}\right)^{1/4}\right) &+\\
&\theta\left(\frac{x}{4}\right) \; &+ \; \theta\left(\left(\frac{x}{4}\right)^{1/2}\right) &+ \theta\left(\left(\frac{x}{4}\right)^{1/3}\right) \; &+ \; \theta\left(\left(\frac{x}{4}\right)^{1/4}\right) \; &+\\
&\cdots
\end{alignat}\right.\]
Every entry in this table is of the form \(\log{p}\) for some prime \(p,\) and \(T(x)\) is also the sum of logarithms of primes, so the task is to show that there are the same number of copies of \(\log{p}\) in the table as there are in \(T(x),\) where \(p\) is any prime. \(\log{p}\) is in column 1, row \(m\) exactly when \(p \leq x/m,\) that is, when \(m \leq x/p.\) There are exactly \(\lfloor x/p \rfloor\) values of \(m\) for which this holds. In the same way, column \(k\) has \(\lfloor x/p^k \rfloor\) values of \(m\) for which \(\log{p}\) appears in the table. Summing over the columns gives the expression in Legendre's formula for the number of copies of \(\log{p}\) in \(T(x).\) It follows that \(T(x)\) equals the double sum. Considering that the \(m\)th row of the table is \(\psi(x/m),\) this shows that:
\[T(x) = \sum_{m=1}^\infty \psi \left(\frac{x}{m}\right). \qquad \textbf{QED.}\tag{2}\]

One form of Stirling's formula is:
\begin{align}
\displaystyle {\sqrt {2\pi n}}\ \left({\frac {n}{e}}\right)^{n} < \; & n! < {\sqrt{2\pi n}} \left({\frac {n}{e}}\right)^{n} \cdot e^{\frac {1}{12n}}\\[1em]
\therefore \displaystyle \log{\left({\sqrt {2\pi n}}\ \left({\frac {n}{e}}\right)^{n}\right)} < \; & \log{n!} < \log{\left({\sqrt{2\pi n}} \left({\frac {n}{e}}\right)^{n} \cdot e^{\frac {1}{12n}}\right)}\\[1em]
\displaystyle \log{\sqrt {2\pi n}} + \log{\left({\frac {n}{e}}\right)^{n}} < \; & \log{n!} < \log{\sqrt {2\pi n}} + \log{\left({\frac {n}{e}}\right)^{n}} + \log{e^{\frac {1}{12n}}}\\[1em]
\tfrac{1}{2} \log{2\pi} + \tfrac{1}{2} \log{n} + n \log{n} - n < \; & \log{n!} < \tfrac{1}{2} \log{2\pi} + \tfrac{1}{2} \log{n} + n \log{n} - n + \tfrac{1}{12n}\tag{3}\\[1em]
\end{align}
Replacing \(n\) with \(n+1\) in the first inequality in (3) and subtracting \(\log{(n+1)}\) from both sides results in:
\begin{align}
\tfrac{1}{2} \log{2\pi} + \log{(n+1)} \cdot \left(n + \tfrac{1}{2}\right) - (n+1)& < \log{n!}\\[1em]
\therefore \tfrac{1}{2} \log{2\pi} + (n+1)\{\log{(n+1)} - 1\} - \tfrac{1}{2} \log{(n+1)} & < \log{n!}.
\end{align}
\(n+1\) can be replaced by anything less than \(n+1\) on the left side of this last inequality considering that the function \(f(y) = y(\log{y} - 1) - \frac{1}{2}\log{y}\) is increasing for \(y \geq 2.\) So putting \(n = \lfloor x \rfloor\) and considering that \(x < \lfloor x \rfloor + 1\) for any real \(x \geq 1:\)
\begin{align}
\tfrac{1}{2} \log{2\pi} + x(\log{x} - 1) - \tfrac{1}{2} \log{x} & < \log{n!} = \log{\lfloor x \rfloor!} = T(x).\tag{4}
\end{align}
The only possible issue is for \(1 \leq x \leq 2,\) and all good in this range since the left side is negative there. The second inequality in (3) is only strengthened when replacing \(\frac{1}{12n}\) by \(\frac{1}{12}\) and \(n\) by \(x,\) since \(1 \leq \lfloor x \rfloor < x\) and the function \(g(y) = \left(y+\frac{1}{2}\right) \log{y} - y\) is increasing for \(y \geq 1.\) So:
\[T(x) < \tfrac{1}{2} \log{2\pi} + x(\log{x}-1) + \tfrac{1}{2} \log{x} + \tfrac{1}{12}.\tag{5}\]
(4) and (5) bound \(T(x)\) below and above by simple expressions involving \(\log{x}.\)

Next define \(S(x)\) as in the subhead immediately above and consider this sum, expanding each \(T(\cdot)\) across a row by applying (2):
\[S(x)=
\left\{
\begin{alignat}{1}\quad
&\psi(x) \! &+ \; \psi\left(\frac{x}{2}\right) &+ \psi\left(\frac{x}{3}\right) &+ \; \psi\left(\frac{x}{4}\right) \; &+ \cdots\\[1em]
+ \; &\psi\left(\frac{x}{30}\right) \; &+ \; \psi\left(\frac{x}{2 \cdot 30}\right) &+ \psi\left(\frac{x}{3 \cdot 30}\right) &+ \; \psi\left(\frac{x}{4 \cdot 30}\right) \; &+ \cdots\\[1em]
- \; &\psi\left(\frac{x}{2}\right) \! &- \; \psi\left(\frac{x}{2 \cdot 2}\right) &- \psi\left(\frac{x}{3 \cdot 2}\right) &- \; \psi\left(\frac{x}{4 \cdot 2}\right) \; &- \cdots\\[1em]
- \; &\psi\left(\frac{x}{3}\right) \! &- \; \psi\left(\frac{x}{2 \cdot 3}\right) &- \psi\left(\frac{x}{3 \cdot 3}\right) &- \; \psi\left(\frac{x}{4 \cdot 3}\right) \; &- \cdots\\[1em]
- \; &\psi\left(\frac{x}{5}\right) \! &- \; \psi\left(\frac{x}{2 \cdot 5}\right) &- \psi\left(\frac{x}{3 \cdot 5}\right) &- \; \psi\left(\frac{x}{4 \cdot 5}\right) \; &- \cdots\\[1em]
\end{alignat}\right.\]
Each of the terms in the expanded sum is of the form \(\psi(x/n),\) so:
\[S(x) = \sum a_n \psi\left(\frac{x}{n}\right),\]
where \(a_n\) is an integer (possibly negative). There are three cases:

1) \(a_n = 1\) if \(n\) is relatively prime to each of \(2, 3,\) and \(5.\) This is true because then \(\psi(x/n)\) appears in the first row and only the first row, since every denominator in lower rows is a multiple of at least one of \(2, 3,\) or \(5.\)

2) \(a_n = 0\) if \(n\) is divisible by only one of \(2, 3,\) or \(5.\) Suppose, for example, that \(n\) is divisible by \(2\) but not by \(3\) or \(5.\) Then \(\psi(x/n)\) appears in the first row and the third row, but not the others, because the denominators in the other rows are divisible by at least one of \(3\) or \(5.\) The two instances have different signs, so \(a_n = 0.\) The same obtains if \(n\) is divisible only by \(3\) or only by \(5.\)

3) \(a_n = -1\) in all other cases. One possibility here is that \(n\) is divisible by just two of \(2, 3,\) or \(5.\) Suppose \(n\) is divisible by \(2\) and \(3\) but not by \(5,\) for example. In that case, \(\psi(x/n)\) appears in the first, third, and fourth rows, but not the second or fifth. The first row contributes \(+\psi(x/n),\) while each of the third and fourth rows contribute \(-\psi(x/n)\) so \(a_n = -1\) when the three are combined. The same effect prevails if \(n\) is divisible by any two of \(2, 3,\) or \(5,\) but not the third. Another possibility is that \(n\) is divisible by \(2, 3,\) and \(5.\) In this case, \(\psi(x/n)\) appears in each row and \(a_n = -1\) after cancellation.

It follows from these rules that the \(a_n\) repeat in cycles of 30. For \(1 \leq n \leq 30,\) the \(a_n\) are as follows:
\begin{array}{ccc}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\
\text{case} & 1 & 2 & 2 & 2 & 2 & 3 & 1 & 2 & 2 & 3 & 1 & 3 & 1 & 2 & 3\\
a_n & 1 & 0 & 0 & 0 & 0 & -1& 1 & 0 & 0 & -1 & 1 & -1 & 1 & 0 & -1\\
\end{array}
\begin{array}{ccc}
n & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\
\text{case} & 2 & 1 & 3 & 1 & 3 & 2 & 2 & 1 & 3 & 2 & 2 & 2 & 2 & 1 & 3\\
a_n & 0 & 1 & -1 & 1 & -1 & 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 & 1 & -1,\\
\end{array}
so \(S(x)\) can be written out:
\[S(x) = \psi(x) - \psi\left(\frac{x}{6}\right) + \psi\left(\frac{x}{7}\right) - \psi\left(\frac{x}{10}\right) + \psi\left(\frac{x}{11}\right) - \psi\left(\frac{x}{12}\right) + \psi\left(\frac{x}{13}\right) + \cdots.\]
Note the alternating signs, which continue throughout. Since \(\psi(x)\) is non-negative and non-decreasing, this implies that:
\begin{gather}
\psi(x) - \psi\left(\frac{x}{6}\right) \leq S(x) \leq \psi(x),\tag{6}\\[1em]
\text{i.e., } \quad \psi(x) - \psi\left(\frac{x}{6}\right) \leq T(x) + T\left(\frac{x}{30}\right) - T\left(\frac{x}{2}\right) - T\left(\frac{x}{3}\right) - T\left(\frac{x}{5}\right) \leq \psi(x).\\
\end{gather}
Now (4) and (5) above can be brought in to replace each \(T(x/k)\) with expressions involving \(\log{x}.\) The positive and negative terms will have to be handled differently:
\begin{align}
T(x) + T\left(\frac{x}{30}\right) & > \log{2\pi} + \tfrac{31}{30} x \log{x} - \tfrac{1}{30} x \log{30} - \tfrac{31}{30} x - \log{x} + \tfrac{1}{2} \log{30},\\[1em]
T(x) + T\left(\frac{x}{30}\right) & < \log{2\pi} + \tfrac{31}{30} x \log{x} - \tfrac{1}{30} x \log{30} - \tfrac{31}{30} x + \log{x} - \tfrac{1}{2} \log{30} + \tfrac{1}{6},\\[1em]
T\left(\frac{x}{2}\right) + T\left(\frac{x}{3}\right) + T\left(\frac{x}{5}\right) & > \tfrac{3}{2} \log{2 \pi} + \tfrac{31}{30} x \log{x}- Bx - \tfrac{31}{30} x - \tfrac{3}{2}\log{x} + \tfrac{1}{2} \log{30},\\[1em]
T\left(\frac{x}{2}\right) + T\left(\frac{x}{3}\right) + T\left(\frac{x}{5}\right) & < \tfrac{3}{2} \log{2 \pi} + \tfrac{31}{30} x \log{x}- Bx - \tfrac{31}{30} x + \tfrac{3}{2}\log{x} - \tfrac{1}{2} \log{30} + \tfrac{1}{4},\\[1em]
\end{align}
where \(B = \tfrac{1}{2} \log{2} + \tfrac{1}{3} \log{3} +\tfrac{1}{5} \log{5}.\) The first and last of these inequalities gives a lower bound for \(S(x) = T(x) + T(x/30) - T(x/2) - \) \(T(x/3) - T(x/5)\) and the second and third give an upper bound for \(S(x):\)
\begin{align}
x(B - \tfrac{1}{30} \log{30}) - \tfrac{5}{2} \log{x} + \tfrac{1}{2} \log{\tfrac{450}{\pi}} - \tfrac{1}{4} < S(x),\\[1em]
S(x) < x(B - \tfrac{1}{30} \log{30}) + \tfrac{5}{2} \log{x} - \tfrac{1}{2} \log{1800 \pi} + \tfrac{1}{6}.
\end{align}
The constant \(A = B - \tfrac{1}{30} \log{30} = \tfrac{1}{2} \log{2} + \tfrac{1}{3} \log{3} +\tfrac{1}{5} \log{5} - \tfrac{1}{30} \log{30} = 0.92129202293\) is an important fixture in this development and appears in both lower and upper bounds, leading to the reframing:
\[Ax - \tfrac{5}{2} \log{x} + \tfrac{1}{2} \log{\tfrac{450}{\pi}} - \tfrac{1}{4} < S(x) < Ax + \tfrac{5}{2} \log{x} - \tfrac{1}{2} \log{1800 \pi} + \tfrac{1}{6},\]
which can be replaced by the weaker inequality
\[Ax - \tfrac{5}{2} \log{x} - 1 < S(x) < Ax + \tfrac{5}{2} \log{x}, \quad \text{ for } x \geq 1.\tag{7}\]

Combining (6) and (7) leads to:
\begin{gather}
Ax - \tfrac{5}{2} \log{x} - 1 < \psi(x),\tag{8}\\[1em]
\psi(x) - \psi\left(\frac{x}{6}\right) < Ax + \tfrac{5}{2} \log{x}.\tag{9}
\end{gather}
The second inequality can be worked into an upper bound for \(\psi(x)\) with a telescoping strategy. Replacing \(x\) by \(x/6, x/6^2,\) and so on, results in:
\begin{align}
\psi(x) - \psi\left(\frac{x}{6}\right) & < Ax + \tfrac{5}{2} \log{x}\\[1em]
\psi\left(\frac{x}{6}\right) - \psi\left(\frac{x}{6^2}\right) & < A \cdot \left(\frac{x}{6}\right) + \tfrac{5}{2} \log{\left(\frac{x}{6}\right)}\\[1em]
\psi\left(\frac{x}{6^2}\right) - \psi\left(\frac{x}{6^3}\right) & < A \cdot \left(\frac{x}{6^2}\right) + \tfrac{5}{2} \log{\left(\frac{x}{6^2}\right)}\\[1em]
& \vdots\\[1em]
\psi\left(\frac{x}{6^n}\right) - \psi\left(\frac{x}{6^{n+1}}\right) & < A \cdot \left(\frac{x}{6^n}\right) + \tfrac{5}{2} \log{\left(\frac{x}{6^n}\right)}
\end{align}
Choosing \(n\) to be the smallest integer such that \(\psi(x/6^{n+1}) = 0\) and adding these inequalities:
\begin{align}
\psi(x) & < Ax \cdot \sum_{k=0}^n \left(\frac{x}{6^k}\right) + \tfrac{5}{2} \sum_{k=0}^n \log{\left(\frac{x}{6^k}\right)}\\[1em]
\psi(x) & < Ax \cdot \tfrac{6}{5} + \tfrac{5}{2} \sum_{k=0}^n \log{\left(\frac{x}{6^k}\right)}\tag{10}\\[1em]
\end{align}
\(\psi(x/6^{n+1}) = 0\) when \(x/6^{n+1} < 2.\) To get a sense of this, suppose \(x/6^{n+1} = 1,\) that is, \(n + 1 = \) \(\log{x} / \log{6}.\) Then the sum in (10) reduces after a series of calculations to:
\[\tfrac{5}{4 \log{6}} \log^2{x} + \tfrac{5}{4} \log{x}.\]
This isn't going to be exact, if for no other reason than that \(n\) is an integer, but it leads to an upper bound by defining:
\[f(x) = \tfrac{6}{5} Ax + \tfrac{5}{4 \log{6}} \log^2{x} + \tfrac{5}{4} \log{x}.\]
Note that:
\begin{align}
f(x) - f\left(\frac{x}{6}\right) &= \tfrac{6}{5} Ax + \tfrac{5}{4 \log{6}} \log^2{x} + \tfrac{5}{4} \log{x} - \left(\tfrac{6}{5} A \cdot \left(\frac{x}{6}\right) + \tfrac{5}{4 \log{6}} \log^2{ \left(\frac{x}{6}\right) + \tfrac{5}{4} \log{ \left(\frac{x}{6}\right) } } \right)\\[1em]
&= Ax + \tfrac{5}{4 \log{6}} \left( \log^2{x} - \log^2{ \left(\frac{x}{6}\right)}\right) + \tfrac{5}{4}\left(\log{x} - \log{ \left( \frac{x}{6} \right)}\right)\\[1em]
&= Ax + \tfrac{5}{4 \log{6}}\left( \log{x} - \log{ \left(\frac{x}{6}\right)}\right)\left( \log{x} + \log{ \left(\frac{x}{6}\right)}\right)+ \tfrac{5}{4}\left(\log{x} - \log{ \left( \frac{x}{6} \right)}\right)\\[1em]
&= Ax + \tfrac{5}{4 \log{6}}(\log{6})\left( \log{x} + \log{ \left(\frac{x}{6}\right)}\right)+ \tfrac{5}{4}(\log{6})\\[1em]
&= Ax + \tfrac{5}{4} \cdot (2\log{x} - \log{6}) + \tfrac{5}{4}\log{6}\\[1em]
&= Ax + \tfrac{5}{2} \log{x}.\\[1em]
\end{align}
Combining this with (9) leads to:
\begin{align}
\psi(x) - \psi\left(\frac{x}{6}\right) & < f(x) - f\left(\frac{x}{6}\right)\\[1em]
\text{ie. } \psi(x) - f(x) & < \psi\left(\frac{x}{6}\right) - f\left(\frac{x}{6}\right).\tag{11}
\end{align}
Let \(m\) be the greatest integer such that \(x/6^m \geq 1.\) Then \(\tfrac{1}{6} \leq x/6^{m+1} < 1,\) so \(\psi(x/6^{m+1}) = 0.\) Apply (11) to \(x, x/6, x/6^2, \; \ldots \; x/6^m:\)
\begin{align}
\psi(x) - f(x) & < \psi\left(\frac{x}{6}\right) - f\left(\frac{x}{6}\right)\\[1em]
\psi\left(\frac{x}{6}\right) - f\left(\frac{x}{6}\right) & < \psi\left(\frac{x}{6^2}\right) - f\left(\frac{x}{6^2}\right)\\[1em]
\psi\left(\frac{x}{6^2}\right) - f\left(\frac{x}{6^2}\right) & < \psi\left(\frac{x}{6^3}\right) - f\left(\frac{x}{6^3}\right)\\[1em]
& \vdots\\[1em]
\psi\left(\frac{x}{6^m}\right) - f\left(\frac{x}{6^m}\right) & < \psi\left(\frac{x}{6^{m+1}}\right) - f\left(\frac{x}{6^{m+1}}\right)\\[1em]
\end{align}

Chaining these together:
\begin{align}
\psi(x) - f(x) & < \psi\left(\frac{x}{6^{m+1}}\right) - f\left(\frac{x}{6^{m+1}}\right)\\[1em]
& < 1,
\end{align}
considering that \(f(u) > -1\) for \(u > 0.\) That is:
\begin{align}
\psi(x) & < f(x) + 1\\[1em]
&= \tfrac{6}{5} Ax + \tfrac{5}{4 \log{6}} \log^2{x} + \tfrac{5}{4} \log{x} + 1.
\end{align}
Combining this with (8) leads to lower and upper bounds on \(\psi(x):\)
\[Ax - \tfrac{5}{2} \log{x} - 1 < \psi(x) < \tfrac{6}{5} Ax + \tfrac{5}{4 \log{6}} \log^2{x} + \tfrac{5}{4} \log{x} + 1.\]

Now bounding \(\theta(x)\) won't be too hard. Start with:
\begin{align}
\psi(x) &= \theta(x) + \theta\left(x^{1/2}\right) + \theta\left(x^{1/3}\right) + \theta\left(x^{1/4}\right) + \ldots\\[1em]
\psi\left(x^{1/2}\right) &= \theta\left(x^{1/2}\right) + \theta\left(x^{1/4}\right) + \theta\left(x^{1/6}\right) + \theta\left(x^{1/8}\right) + \ldots\\[1em]
\therefore \psi(x) - \psi\left(x^{1/2}\right) &= \theta(x) + \theta\left(x^{1/3}\right) + \theta\left(x^{1/5}\right) + \theta\left(x^{1/7}\right) + \ldots
\end{align}
All the terms after \(\theta(x)\) on the last line are non-negative, so:
\[\theta(x) \leq \psi(x) - \psi\left(x^{1/2}\right).\]
Similarly:
\[\psi(x) - 2 \psi\left(x^{1/2}\right) = \theta(x) - \left\{\theta\left(x^{1/2}\right) - \theta\left(x^{1/3}\right)\right\} - \left\{\theta\left(x^{1/4}\right) - \theta\left(x^{1/5}\right)\right\} + \ldots\]
Here each difference in braces is non-negative, so \(\theta(x)\) is followed by a series of negative terms, implying:
\[\psi(x) - 2 \psi\left(x^{1/2}\right) \leq \theta(x).\]
Employing the lower bound on \(\psi\left(x^{1/2}\right)\) and the upper bound on \(\psi(x):\)
\begin{align}
-\psi\left(x^{1/2}\right) & < -A \left(x^{1/2}\right) + \tfrac{5}{2} \log{\left(x^{1/2}\right)} + 1\\[1em]
&= -A \left(x^{1/2}\right) + \tfrac{5}{4} \log{x} + 1\\[1em]
\therefore \theta(x) & \leq \psi(x) - \psi\left(x^{1/2}\right)\\[1em]
& < \tfrac{6}{5} Ax - A x^{1/2} + \tfrac{5}{4\log{6}} \log^2{x} + \tfrac{5}{2} \log{x} + 2.
\end{align}
And using the upper bound on \(\psi\left(x^{1/2}\right)\) and the lower bound on \(\psi(x):\)
\begin{align}
-2\psi\left(x^{1/2}\right) & > - 2 \cdot \tfrac{6}{5} A x^{1/2} - 2 \cdot \tfrac{5}{4\log{6}} \log^2{\left(x^{1/2}\right)} - 2 \cdot \tfrac{5}{4}\log{\left(x^{1/2}\right)} - 2 \cdot 1\\[1em]
&= -\tfrac{12}{5} A x^{1/2} -\tfrac{5} {8\log{6}} \log^2{x} -\tfrac{5}{4}\log{x} - 2\\[1em]
\therefore \theta(x) & \geq \psi(x) - 2 \psi\left(x^{1/2}\right)\\[1em]
& > Ax -\tfrac{12}{5} A x^{1/2} -\tfrac{5} {8\log{6}} \log^2{x} -\tfrac{15}{4}\log{x} - 3.
\end{align}
In summary:
\begin{align}
\theta(x) & < \theta_1(x) := \tfrac{6}{5} Ax - A x^{1/2} + \tfrac{5}{4\log{6}} \log^2{x} + \tfrac{5}{2} \log{x} + 2,\tag{12}\\[1em]
\theta(x) & > \theta_2(x) : =Ax -\tfrac{12}{5} A x^{1/2} -\tfrac{5} {8\log{6}} \log^2{x} -\tfrac{15}{4}\log{x} - 3.\tag{13}
\end{align}

These bounds on \(\theta(x)\) can be used to show the existence of prime numbers. Suppose \(1 < \alpha < \beta.\) Then by (12) and (13):
\begin{align}
\theta(\beta) - \theta(\alpha) & > \theta_2(\beta) - \theta_1(\alpha),\\[1em]
\theta(\beta) - \theta(\alpha) & < \theta_1(\beta) - \theta_2(\alpha).\\
\end{align}
Now:
\begin{align}
\theta(\beta) - \theta(\alpha) &= \sum_{\alpha < p \leq \beta} \log{p}\\[1em]
& \leq \log{\beta} \cdot \sum_{\alpha < p \leq \beta} 1\\[1em]
&= \log{\beta} \cdot (\pi(\beta) - \pi(\alpha)).
\end{align}
A similar result obtains for the upper bound, so:
\begin{align}
{{\theta(\beta) - \theta(\alpha)} \over {\log{\beta}}} & < \pi(\beta) - \pi(\alpha) < {{\theta(\beta) - \theta(\alpha)} \over {\log{\alpha}}},\\[1em]
\therefore {{\theta_2(\beta) - \theta_1(\alpha)} \over {\log{\beta}}} & < \pi(\beta) - \pi(\alpha) < {{\theta_1(\beta) - \theta_2(\alpha)} \over {\log{\alpha}}}.\\[1em]
\end{align}
So if \(k\) is an integer less than \((\theta_2(\beta) - \theta_1(\alpha)) / \log{\beta},\) then there are more than \(k\) primes between \(\alpha\) and \(\beta.\) That is:
\[k \log{\beta} < \theta_2(\beta) - \theta_1(\alpha) \Longrightarrow \text{ there are more than } k \text{ primes } p \text{ such that } \alpha < p \leq \beta.\tag{14}\]
(14) is the key and let's take a moment to reflect on what a remarkable statement it is. If \(k = 0,\) it is only necessary to prove that \(\theta_2(\beta) - \theta_1(\alpha),\) an expression involving \(\alpha\)s and \(\beta\)s and their square roots and logarithms, is positive in order to show that there is at least one prime number between \(\alpha\) and \(\beta.\) Continuing:
\begin{align}
\theta_2(\beta) - \theta_1(\alpha) &= A\beta - \tfrac{12}{5}A\beta^{1/2} - \tfrac{5}{8\log{6}}\log^2{\beta} - \tfrac{15}{4}\log{\beta} - 3\\[1em]
&\qquad -\tfrac{6}{5}A\alpha + A \alpha^{1/2} - \tfrac{5}{4\log{6}}\log^2{\alpha} - \tfrac{5}{2}\log{\alpha} - 2\\[1em]
&\hspace{-5em}= A\left(\beta-\tfrac{6}{5}\alpha\right) - A\left(\tfrac{12}{5}\beta^{1/2}-\alpha^{1/2}\right) - \tfrac{5}{8\log{6}}\left(\log^2{\beta}+2\log^2{\alpha}\right) - \tfrac{5}{4}(3\log{\beta}+2\log{\alpha}) - 5
\end{align}
This can be turned into an inequality by leaving out the positive term \(A\alpha^{1/2}\). Also the \( \log^2{\alpha}\) and \(\log{\alpha}\) can be replaced by \( \log^2{\beta},\) and \(\log{\beta}\) respectively, since those terms are negative and \(\alpha < \beta:\)
\[\theta_2(\beta) - \theta_1(\alpha) > A\left(\beta-\tfrac{6}{5}\alpha\right) - \tfrac{12}{5}A\beta^{1/2} -\tfrac{15}{8\log{6}}\log^2{\beta} - \tfrac{25}{4}\log{\beta} - 5.\tag{15}\]
Therefore, in order to prove that there is a prime \(p\) with \(\alpha < p \leq \beta,\) it is sufficient to show that the right side of (15) is positive:
\begin{align}
0 & < A\left(\beta-\tfrac{6}{5}\alpha\right) - \tfrac{12}{5}A\beta^{1/2} -\tfrac{15}{8\log{6}}\log^2{\beta} - \tfrac{25}{4}\log{\beta} - 5,\\[1em]
\text{ie. } \alpha & < \tfrac{5}{6}\beta - 2\beta^{1/2} - \tfrac{25}{16A\log{6}}\log^2{\beta} -\tfrac{125}{24A}\log{\beta} - \tfrac{25}{6A}.\tag{16}
\end{align}
(16) holds when \(\beta\) is sufficiently larger than \(\alpha.\) In fact:

Bertrand's Postulate: There is at least one prime number \(p\) such that \(\alpha < p < 2\alpha-2\) for every integer \(\alpha > 3.\)

Proof. Let \(\beta = 2\alpha - 3\) in (16) and rearrange to get:
\[\alpha > 3\sqrt{2\alpha-3} + \tfrac{75}{32A\log{6}}\log^2{(2\alpha-3)} + \tfrac{125}{16A}\log{(2\alpha-3)} + \left(\tfrac{15}{4} + \tfrac{25}{6A}\right).\]

\(\alpha\) eventually outstrips all of those slower growing functions of \(\alpha\) on the right side of this inequality, so it holds whenever \(\alpha\) is large enough. Turning the inequality into an equality and solving for \(\alpha\) results in \(\alpha = 156.44,\) so Bertrand's postulate holds for values of \(\alpha\) greater than that. It holds for smaller values of \(\alpha\) by directly checking. QED.

A much sharper result is available from (16), for if \(\beta > \tfrac{6}{5}\alpha,\) the same calculation as in the proof of Bertrand's postulate leads to the existence of at least one prime between \(\alpha\) and \(\beta\) inclusive for all \(\alpha\) such that:
\[\alpha > P \sqrt{\alpha} + Q \log^2{\alpha} + R \log{\alpha} + S,\]
where \(P, Q, R,\) and \(S\) are positive constants, and this inequality holds for sufficiently large \(\alpha,\) whatever the constants. The threshold might be higher than 3 though as it is for Bertrand's postulate. It's true that there is at least one prime strictly between \(\alpha\) and \(\tfrac{5}{4}\alpha\) for sufficiently large \(\alpha,\) for example, but it's not true for smaller values of \(\alpha.\) There is no prime strictly between \(\alpha = 23\) and \(\tfrac{5}{4}\alpha = 28 \tfrac{3}{4},\) so the threshold is at least 23.

Since 1800 or so, Legendre and Gauss had noticed through numerical work that \(\pi(x) \approx x/\log{x}\) and Chebyshev himself had proven that if \(\pi(x)/(x/\log{x})\) tends to a limit, then that limit is 1.^[5] The goal here is to prove that there are positive constants \(C_1\) and \(C_2\) such that:
\[C_1 {{x} \over {\log{x}}} < \pi(x) < C_2 {{x} \over {\log{x}}}\tag{17}\]
for all \(x\) or perhaps all \(x\) greater than some threshold \(x_0.\) The two statements are actually synonymous because if the second is true, then other constants can be produced accounting for the finite number of exceptions as well as all large \(x.\)

Chebyshev doesn't prove (17), though it follows from his analysis. For the lower bound, recall from (13) that:
\[\theta(x) > \theta_2(x) := Ax -Cx^{1/2} -D\log^2{x} -E\log{x} -F,\]
where \(C,D,E,F\) are positive constants. Also:
\begin{gathered}
\theta(x) = \sum_{p \leq x} \log{p} \leq \log{x} \cdot \sum_{p \leq x} 1 = \log{x} \cdot \pi(x).\\[1em]
\therefore {{\theta_2(x)} \over{\log{x}}} < {{\theta(x)} \over{\log{x}}} < \pi(x)\\[1em]
{{Ax -Cx^{1/2} -D\log^2{x} -E\log{x} -F} \over {\log{x}}} < \pi(x).\\[1em]
A {{x} \over {\log{x}}} - {{x} \over {\log{x}}} \left( {{C x^{1/2}} \over {x}} + {{D \log^2{x}} \over {x}} + {{E \log{x}} \over {x}} + {{F} \over {x}}\right) < \pi(x).
\end{gathered}
Each summand in the parenthesized expression goes to zero as \(x\) goes to infinity, so the same is true of the sum. It follows that for every \(\epsilon > 0,\) there is an \(x_0\) such that:
\[(A-\epsilon){{x} \over {\log{x}}} < \pi(x) \quad \text{ for } x > x_0.\tag{18}\]
Considering that \(A = \tfrac{1}{2} \log{2} + \tfrac{1}{3} \log{3} +\tfrac{1}{5} \log{5} - \tfrac{1}{30} \log{30} = 0.92129202293,\) this shows that \(\pi(x)\) is not too much less than \(x / \log{x},\) relatively speaking.

The upper bound is harder to prove. Since \(x/\log{x}\) is strictly increasing for \( x \geq 3\) and \(\pi(x)\) is a non-decreasing step function changing value only at some integers (primes!), it suffices to prove the upper bound for integers. Start with this, for any integer \( n \geq 2:\)
\[\pi(n) = {{\theta(2)-\theta(1)} \over {\log{2}}} + {{\theta(3)-\theta(2)} \over {\log{3}}} + {{\theta(4)-\theta(3)} \over {\log{4}}} + \cdots + {{\theta(n)-\theta(n-1)} \over {\log{n}}}.\tag{19}\]
The equation holds because \(\theta(k)-\theta(k-1)\) is \(\log{k}\) if \(k\) is prime and 0 if not, so the fraction is 1 if \(k\) is prime and 0 otherwise. The upshot is that the sum just counts the primes less than or equal to \(n.\) Rearranging (19) results in:
\begin{align}
\pi(n) &= -{{\theta(1)} \over {\log{2}}} + \left({{1} \over {\log{2}}} - {{1} \over {\log{3}}}\right)\theta(2) + \cdots + \left({{1} \over {\log{n}}} - {{1} \over {\log{(n+1)}}}\right)\theta(n) + {{\theta(n)} \over {\log{(n+1)}}}\\[1em]
& < -{{\theta_2(1)} \over {\log{2}}} + \left({{1} \over {\log{2}}} - {{1} \over {\log{3}}}\right)\theta_1(2) + \cdots + \left({{1} \over {\log{n}}} - {{1} \over {\log{(n+1)}}}\right)\theta_1(n) + {{\theta_1(n)} \over {\log{(n+1)}}}\\[1em]
&= {{\theta_1(1)} \over {\log{2}}} - {{\theta_2(1)} \over {\log{2}}} + {{\theta_1(2)-\theta_1(1)} \over {\log{2}}} + {{\theta_1(3)-\theta_1(2)} \over {\log{3}}} + \cdots + {{\theta_1(n)-\theta_1(n-1)} \over {\log{n}}}\\[1em]
&= {{\theta_1(1)} \over {\log{2}}} - {{\theta_2(1)} \over {\log{2}}} + \sum_{k=2}^n {{\theta_1(k)-\theta_1(k-1)} \over {\log{k}}}\\[1em]
&= K + \sum_{k=2}^n {{\theta_1(k)-\theta_1(k-1)} \over {\log{k}}}\\[1em]
&= K + \sum_{k=2}^n {{1}\over{\log{k}}} \huge ( \normalsize \tfrac{6}{5}A - A\left(k^{1/2} - (k-1)^{1/2}\right) + G\left(\log^2{k} - \log^2{(k-1)}\right)\\
&\hspace{90pt} + H (\log{k} - \log{(k-1)}) \huge ) \normalsize , \hspace{120pt}(20)
\end{align}
where \(K, G\) and \(H\) are positive constants. There are four terms in the long parenthesized sum within the summation sign in (20), and I'll address them one by one as separate sums:

\(\displaystyle 1) \hspace{10pt} S_1 = \sum_{k=2}^n \left({{1}\over{\log{k}}} \cdot \tfrac{6}{5}A\right) = \tfrac{6}{5}A \cdot \sum_{k=2}^n {{1}\over{\log{k}}}.\)

To evaluate this sum, consider that:
\begin{align}
\sum_{k=3}^n {{1}\over{\log{k}}} & < \int_2^n {{\mathrm{d}t} \over {\log{t}}}\\[1em]
\therefore \sum_{k=2}^n {{1}\over{\log{k}}} & < {{1} \over {\log{2}}} + \int_2^n {{\mathrm{d}t} \over {\log{t}}}\\[1em]
&= {{1} \over {\log{2}}} + \text{ Li}(n),\\[1em]
\end{align}
where \(\text{ Li}(n)\) is defined as the indicated definite integral. It is a fact (proof here) that:
\begin{align}
{{\text{ Li}(x)} \over {x / \log{x}}} & \rightarrow 1 \text{ as } x \rightarrow \infty\\[1em]
\therefore {\displaystyle {\sum_{k=2}^n {{1}\over{\log{k}}}} \over {n / \log{n}}} & < {{{{\displaystyle{{1} \over {\log{2}}} + \text{ Li}(n)}} \over n / \log{n}}} \rightarrow 1 \text{ as } n \rightarrow \infty\\[1em]
\therefore S_1 & < \left(\tfrac{6}{5}A + \epsilon_1\right) {{n} \over {\log{n}}} \text{ for large } n \text{ for every } \epsilon_1 > 0.
\end{align}
\(\displaystyle 2) \hspace{10pt} S_2 = \sum_{k=2}^n \left({-A\left(k^{1/2} - (k-1)^{1/2}\right)}\over\log{k}\right).\)

\(S_2\) can be left out when seeking an upper bound since it's negative.

\(\displaystyle 3) \hspace{10pt} S_3 = \sum_{k=2}^n \left({G\left(\log^2{k} - \log^2{(k-1)}\right)}\over\log{k}\right).\)

A larger sum results from replacing the \(\log{k}\) in the denominator by \(\log{2},\) so:
\[S_3 < {{G} \over {\log{2}}} \cdot \sum_{k=2}^n \left(\log^2{k} - \log^2{(k-1)}\right).\]
The sum telescopes and collapses to \(\log^2{n},\) so:
\begin{align}
S_3 & < {{G} \over {\log{2}}} \cdot \log^2{n}\\[1em]
&= {n \over {\log{n}}}\left({{\log{n}} \over n} \cdot {{G} \over {\log{2}}} \cdot \log^2{n}\right)\\[1em]
&= {n \over {\log{n}}}\left( {{G} \over {\log{2}}} \cdot {{\log^3{n}} \over n}\right)\\[1em]
\therefore S_3 & < \epsilon_3 \cdot {{n} \over {\log{n}}} \text{ for large } n \text{ for every } \epsilon_3 > 0,
\end{align}
considering that \(\log^3{n} / n \rightarrow 0\) as \(n \rightarrow \infty.\)

\(\displaystyle 4) \hspace{10pt} S_4 = \sum_{k=2}^n \left({H\left(\log{k} - \log{(k-1)}\right)}\over\log{k}\right).\)

The analysis is identical to that for \(S_3\), so:
\[S_4 < \epsilon_4 \cdot {{n} \over {\log{n}}} \text{ for large } n \text{ for every } \epsilon_4 > 0.\]
The leading \(K\) is not an obstacle because:
\[K < \epsilon_0 \cdot {{n} \over {\log{n}}} \text{ for large } n \text{ for every } \epsilon_0 > 0.\]
With these substitutions, (20) becomes:
\begin{align}
\pi(n) & < K + S_1 +S_3 + S_4\\[1em]
& < \epsilon_0 \cdot {{n} \over {\log{n}}} + \left(\tfrac{6}{5}A + \epsilon_1\right) \cdot {{n} \over {\log{n}}} + \epsilon_3 \cdot {{n} \over {\log{n}}} + \epsilon_4 \cdot {{n} \over {\log{n}}}\\[1em]
& < \left(\tfrac{6}{5}A + \epsilon_0 + \epsilon_1 + \epsilon_3 + \epsilon_4\right) \cdot{{n} \over {\log{n}}}\\[1em]
&= \left( \tfrac{6}{5}A + \epsilon\right) \cdot{{n} \over {\log{n}}} \text{ for large } n \text{ for every } \epsilon > 0.\tag{21}
\end{align}
Combining (18) and (21) and keeping in mind that the upper bound can be converted from integers to real numbers:
\[(A-\epsilon){{x} \over {\log{x}}} < \pi(x) < \left( \tfrac{6}{5}A + \epsilon\right) \cdot{{x} \over {\log{x}}} \quad \text{ for large } x \text{ for every } \epsilon > 0,\tag{22}\]
where \(A = 0.92129202293\) and \(\tfrac{6}{5}A = 1.10555042752.\)

Here are \(\pi(x)\) and its proposed upper and lower bounds for powers of 2 up to \(2^{23},\) "proposed" since they've only been proven to bound \(\pi(x)\) beyond some unspecified threshold and up to a tolerance of \(\epsilon.\)

This table suggests that \(A \cdot x/\log{x} < \pi(x) \) except for a few small values of \(x\) and indeed this is the case for all \(x > 10.\) The proposed upper bound runs closer to \(\pi(x)\) but slightly below it until \(x = 131,072\) in the chart. In fact the threshold is \(x = 96,097,\) above which \(\pi(x) < \frac{6}{5}A \cdot x/\log{x}.\) \(\pi(x)\) continues to follow the upper bound closely until \(x = 1,000,000\) or so.

Although complicated, Chebyshev's approach uses elementary tools and provides constants close to 1. Much simpler methods are available if the goal is simply to provide positive constants \(C_1\) and \(C_2\) in (17). For example, Tom Apostol uses the binomial coefficient \(\binom{2n}{n}\) to show that^[6]:
\[\frac{1}{6} {{n} \over {\log{n}}} < \pi(n) < 6 {{n} \over {\log{n}}} \text{ for all integers } n > 2.\]
It does make sense that \(\binom{2n}{n} = \frac{(2n)!}{n! \cdot n!}\) figures into these matters, since \(\binom{2n}{n}\) contains all primes between \(n\) and \(2n\) in its factorization. That's because every such prime divides \((2n)!\) but does not divide \(n!\). For example:
\[\binom{20}{10} = \frac{(20)!}{10! \cdot 10!} = 2^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19.\]
Paul Pollack proves (17) very much in Chebyshev's spirit^[7], without specifying the constants however. He too use what amounts to \(\binom{2n}{n},\) considering that:
\begin{align}
\log{\binom{2n}{n}} &= \log{\frac{(2n)!}{n! \cdot n!}}\\[1em]
&=\log{(2n)!} - 2\log{n!}\\[1em]
&=T(2n) - 2T(n),
\end{align}
where \(T(\cdot)\) is Chebyshev's function defined above. Instead of \(S(x),\) Pollack uses \(Q(x) = T(x) - 2T(x/2)\) and works it into a proof of Bertrand's postulate as well.

A quick glance at Apostol or Pollock makes it abundantly clear that the details of Chebyshev's approach have long since been abandoned. Its spirit lives on however, as do \(\theta(x)\) and \(\psi(x).\) Who would have thought that these analytical processes involving logarithms and continuous real functions would be the key to understanding the highly unruly distribution of prime numbers? This is part of a large subject today, analytic number theory — applying analysis to the study of integers — and Chebyshev was an early founder. (17) is generally taken as the first step to:

Prime Number Theorem: \(\displaystyle \lim_{x \rightarrow \infty} {{\pi(x)}\over{x/\log{x}}} = 1.\)

The Prime Number Theorem, one of the gems of modern mathematics, was proven independently by Hadamard and de la Vallée Poussin in 1896 using complex number theory and then in 1949 by Selberg and Erdős using "elementary" methods (no complex number theory). Chebyshev showed the way.

Mike Bertrand

March 14, 2023

^ 1. "Mémoire sur les nombres premiers", by P. L. Chebyshev, Journal de mathématiques pures et appliquées 1^re série, tome 17 (1852), pp. 366-390. The paper was originally read to the St. Petersburg Academy of Sciences in September 1850. It also appears in the Oeuvres here, but care is in order with that edition, which includes at least one set of egregious typos in the important expressions (11) on p. 70. About half of the Mémoire was translated into English by J. D. Tamarkin and is included in A Source Book in Mathematics, Vol 1, by David Eugene Smith, McGraw-Hill (1929). There are some less grievous typos, like putting the inequality sign the wrong way.

^ 2. "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), pp. 123-140. See p. 129 for the postulate.

^ 3. Some nineteenth century works helpfully reprise the Mémoire up to Bertrand's postulate. See Theory of Numbers, Part I, by G. B. Mathews, Deighton, Bell and Co. (1892), pp. 278-287. Joseph Serret closely follows Chebyshev in his influential Cours d'algèbre supérieure, quatrième éd., Gauthier-Villars (1879), pp. 225-239. This textbook was first published in 1849 and much updated over the years.

^ 4. See Théorie des nombres, troisième éd., by Adrien-Marie Legendre, Didot Frères (1830). His formula is on p. 10. He gives the example:
\begin{align}
\displaystyle \nu _{7}(10,000!) &= \left\lfloor {\frac {10,000}{7}}\right\rfloor + \left\lfloor {\frac {10,000}{7^{2}}}\right\rfloor + \left\lfloor {\frac {10,000}{7^{3}}}\right\rfloor + \left\lfloor {\frac {10,000}{7^{4}}}\right\rfloor + \left\lfloor {\frac {10,000}{7^{5}}}\right\rfloor\\[1em]
&= 1428 + 204 + 29 + 4 + 0\\[1em]
&= 1665.
\end{align}
^ 5. See "Sur la totalité des nombres premiers inférieurs à une limite donnée", by P. L. Chebyshev, Journal de mathématiques pures et appliquées 1^re série, tome 17 (1852), pp. 341-365. The paper was originally read to the St. Petersburg Academy of Sciences in May 1848. There is an English translation in the source book cited in footnote 1.

^ 6. Introduction to Analytic Number Theory, by Tom Apostol, Springer (1976), ISBN 0-387-90163-9, p. 82ff.

^ 7. Not Always Buried Deep: A Second Course in Analytic Number Theory, by Paul Pollack, American Mathematical Society (2009), ISBN 978-8218-4880-7, pp. 89-95.