Skip to main content

Section 3.3 Chebychev's Functions

Definition 3.3.1.

Let \(x\in\mathbb{R}\)>. Then \(\lfloor x\rfloor\) denotes the greatest integer less than or equal to x. This is sometimes called the integer part of \(x,\) or the floor function.

Note that for all \(x\) we have

\begin{equation*} 2x- 1 \lt \lfloor 2x\rfloor \leq 2x \end{equation*}

and

\begin{equation*} 2x- 2 \lt 2\lfloor x\rfloor \leq 2x. \end{equation*}

Thus

\begin{equation*} - 1 \lt \lfloor 2x\rfloor-2\lfloor x\rfloor \leq 2, \end{equation*}

but since \(\lfloor 2x\rfloor-2\lfloor x\rfloor\) must be an integer, and the only integers in \((-1, 2)\) are \(0\) and \(1,\) only these values can be attained.

Note that if \(p\gt n\) then \(p\) does not appear in the prime factorization of \(n!\) and every term in \(\sum_{j=1}^{\infty}\left\lfloor\frac{n}{p^j}\right\rfloor\) is zero as desired.

If \(p\leq n,\) then \(\left\lfloor\frac{n}{p^j}\right\rfloor\) integers in \(\{1, 2,...,n\}\) are divisible by \(p,\) namely

\begin{equation*} p, 2p, 3p,...,\left\lfloor\frac{n}{p}\right\rfloor p. \end{equation*}

Of these integers, \(\left\lfloor\frac{n}{p^2}\right\rfloor\) are again divisible by \(p\text{:}\)

\begin{equation*} p^2, 2p^2, 3p^2,...,\left\lfloor\frac{n}{p^2}\right\rfloor p^2. \end{equation*}

By the same logic, \(\left\lfloor\frac{n}{p^3}\right\rfloor\) of these are divisible by \(p\) a third time:

\begin{equation*} p^3, 2p^3, 3p^3,...,\left\lfloor\frac{n}{p^3}\right\rfloor p^3. \end{equation*}

After finitely many repetitions of this argument, we see that the total number of times \(p\) divides numbers in \(\{1, 2, 3,...,n\}\) is precisely \(\sum_{j=1}^{\infty}\left\lfloor\frac{n}{p^j}\right\rfloor;\) consequently, this sum is the exponent of \(p\) appearing in the prime factorization of \(n!.\)

Definition 3.3.4.

We define Chebyshev's functions as

\begin{equation*} \theta(x)=\sum_{p\leq x}\log(p) \end{equation*}

and

\begin{equation*} \varphi(x)=\sum_{p^m\leq x}\log(p) \end{equation*}

where the sum is over all combinations of a prime \(p\) and a positive integer \(m\) for which \(p^m \leq x.\)

Note that if we gather together terms with equal \(m\) we have

\begin{equation*} \varphi(x)=\theta(x)+\theta(x^{\frac{1}{2}})+\theta(x^{\frac{1}{3}})+..., \end{equation*}

where the series on the right contains only a finite number of nonzero terms, since \(\theta(y)=0\) when \(y \lt 2.\)

If we gather terms with equal \(p\) (\(p \leq x\)), then

\begin{equation*} \varphi(x)=\sum_{p\leq x}\left\lfloor\frac{\log(x)}{\log(p)}\right\rfloor \log(p), \end{equation*}

since the number of values of \(m\) associated with a given \(p\) is the number of positive \(m\) satisfying \(m \log(p)\leq \log(x),\) which is

\begin{equation*} m\leq \left\lfloor\frac{\log(x)}{\log(p)}\right\rfloor. \end{equation*}

Using these definitions we show in the following theorem, that for large values of \(x,\) the behavior of any one of the functions \(\pi(x),\) \(\theta(x),\) and \(\varphi(x)\) can be inferred from that of any other.

Let the upper limits (possibly \(+\infty\)) be \(L_1, L_2, L_3,\) and the lower limits be \(l_1, l_2, l_3,\) respectively. From the equalities in the previous paragraph we have

\begin{equation*} \theta(x)\leq \varphi(x)\leq \sum_{p\leq x}\frac{\log(x)}{\log(p)}\log(p)=\pi(x)\log(x), \end{equation*}

so dividing by \(x\) and taking upper limits we have \(L_2 \lt L_3 \lt L_1.\)

Now if \(0 \lt\alpha\lt 1\) and \(x\gt 1,\) then

\begin{equation*} \theta(x)\geq \sum_{x^{\alpha}\lt p\leq x}\log(p)\geq [\pi(x)-\pi(x^{\alpha})]\log(x^{\alpha}), \end{equation*}

so that since \(\pi(x^{\alpha})\lt x^{\alpha},\) we have

\begin{equation*} \frac{\theta(x)}{x}\gt \alpha\left(\frac{\pi(x)\log(x)}{x}-\frac{\log(x)}{x^{1-\alpha}}\right). \end{equation*}

If we keep \(\alpha\) fixed and let \(x\rightarrow\infty,\) then

\begin{equation*} \frac{\log(x)}{x^{1-\alpha}}\rightarrow 0, \end{equation*}

so that \(L_2 \geq \alpha L_1,\) so that since \(\alpha\) can be as close to \(1\) as we want,

\begin{equation*} L_2\geq L_1. \end{equation*}

This combined with the previous inequality gives

\begin{equation*} L_1 = L_2 = L_3. \end{equation*}

If we just replace \(L_i\) with \(l_i,\) then the exact argument above yields \(l_1 =l_2 = l_3.\)