Bounds for divisor and Euler’s totient function

The divisor function $d(n)$ counts the number of divisors of an integer $n$. It is a multiplicative function and so can be written as
\[
d(n) = \prod_{p^a || n} (a + 1).
\] We will now show that $d(n) \ll_{\varepsilon} n^{\varepsilon}$ for every $\varepsilon > 0$. Let $\varepsilon > 0$ be fixed. Then we have
\[
\frac{d(n)}{n^{\varepsilon}} = \prod_{p^a || n} \frac{a + 1}{p^{a \varepsilon}} \leq \prod_{\scriptstyle p^a || n \atop \scriptstyle p < 2^{1/\varepsilon}} \frac{a + 1}{p^{a \varepsilon}}
\] for if $p \geq 2^{1/{\varepsilon}}$, then $p^{\varepsilon} \geq 2$ and so $p^{a \varepsilon} \geq 2^{a} \geq a + 1$ which gives $(a + 1)/p^{a \varepsilon} \leq 1$. Now observe that
\[
\frac{d(n)}{n^{\varepsilon}} \leq \prod_{\scriptstyle p^a || n \atop \scriptstyle p < 2^{1/\varepsilon}} \frac{a + 1}{2^{a \varepsilon}} \leq \prod_{\scriptstyle p^a || n \atop \scriptstyle p < 2^{1/\varepsilon}} \frac{a + 1}{{a \varepsilon \log 2}}
\] as $2^{a \varepsilon} = e ^{a \varepsilon \log 2} \geq a \varepsilon \log 2$. Finally we have
\[
\frac{d(n)}{n^{\varepsilon}} \leq \prod_{p < 2^{1/\varepsilon}} \frac{2}{\varepsilon \log 2} \leq \left( \frac{2}{\varepsilon \log 2} \right)^{\pi(2^{1/\varepsilon})}.
\] Because the right-hand side depends only on $\varepsilon$ we conclude that $d(n) \ll_{\varepsilon} n^{\varepsilon}$.

One can readily obtain a lower bound for $\varphi(n)$ using the above upper bound for $d(n)$. Note that
\[
\varphi(n) = n\prod_{p \, | \, n} \left(1- \frac{1}{p} \right) \geq \frac{n}{2^{\omega(n)}} \geq \frac{n}{d(n)} \gg_{\varepsilon} n^{1- \varepsilon}
\] as $1- 1/p \geq 1/2$ for every prime $p$ and $d(n) \geq 2^{\omega(n)}$ for every $n \in \mathbb{N}$.

I present another proof of the bound $\varphi(n) \gg_{\varepsilon} n^{1 -\varepsilon}$ which was casually discovered by me. My bound is effective in the sense that the constant is explicit. The idea is to show that $\prod_{p \, | \, n} \left( 1 -1/p \right) \gg_{\varepsilon} n^{-\varepsilon}$ for every $\varepsilon > 0$. Taking the logarithm we obtain
\[
\log \prod_{p \, | \, n} \left( 1 -\frac{1}{p} \right) = \sum_{p \, | \, n} \log \left( 1 -\frac{1}{p} \right) = -\sum_{p \, | \, n} \sum_{k = 1}^{\infty} \frac{1}{k p^k} = -\sum_{k = 1}^{\infty} \frac{1}{k} \sum_{p \, | \, n} \frac{1}{p^k}.
\] Now observe that for any $k \in \mathbb{N}$ and $U \geq 1$ we have
\[
\sum_{p \, | \, n} \frac{1}{p^k} \leq \sum_{p \leq U} \frac{1}{p^k} + \frac{\omega(n)}{U^k}.
\] Thus we obtain
\[ \begin{align} \sum_{k = 1}^{\infty} \frac{1}{k} \sum_{p \, | \, n} \frac{1}{p^k} &\leq \sum_{k = 1}^{\infty} \frac{1}{k} \sum_{p \leq U} \frac{1}{p^k} + \omega(n)\sum_{k = 1}^{\infty} \frac{1}{k U^k} \\ &= -\sum_{p \leq U} \log \left( 1- \frac{1}{p}\right)-\omega(n) \log \left( 1- \frac{1}{U} \right). \end{align}
\] Using the inequality $\omega(n) \leq \log_2 n$ we get
\[
\log \prod_{p \, | \, n} \left( 1- \frac{1}{p} \right) \geq \sum_{p \leq U} \log \left( 1- \frac{1}{p} \right) + \frac{\log n}{\log 2} \log \left( 1- \frac{1}{U} \right)
\] If we denote the sum to the right by $C_U$ and $\varepsilon_U = -\frac{1}{\log 2} \log \left( 1- \frac{1}{U} \right)$, then we get
\[
\log \prod_{p \, | \, n} \left( 1- \frac{1}{p} \right) \geq C_U -\varepsilon_U \log n.
\] Finally, taking exponential we find that
\[
\prod_{p \, | \, n} \left( 1- \frac{1}{p} \right) \geq e^{C_U} n^{-\varepsilon_U}.
\] Since $\varepsilon_U \to 0$ as $U \to \infty$ we obtain the desired conclusion.

One can obtain a stronger lower bound for $\varphi(n)$ without much effort as follow: Observe that
\[\begin{align} \varphi(n)\sigma(n) &= \prod_{p^a || n} \varphi(p^a) \sigma(p^a) = \prod_{p^a || n} p^{a-1} (p- 1) \left( \frac{p^{a + 1}- 1}{p- 1} \right) \\ &= \prod_{p^{a} || n} p^{a- 1}(p^{a + 1}- 1) = n^2 \prod_{p^a || n} \left( 1- \frac{1}{p^{a + 1}} \right). \end{align}
\] Since each of the factor is $\leq 1$ we obtain the inequality $\varphi(n) \sigma(n) \leq 1$. Moreover, note that
\[
\prod_{p^a || n} \left( 1- \frac{1}{p^{a + 1}} \right) \geq \prod_{p} \left( 1- \frac{1}{p^2} \right) = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}.
\] Thus we have
\[
\frac{6n^2}{\pi^2} \leq \varphi(n) \sigma(n) \leq n^2. \tag{1}
\] By definition of $\sigma(n)$ we have
\[
\sigma(n) = n \sum_{d \, | \, n} \frac{1}{d} \leq n (\log n + 1).
\] This combined with (1) leads to
\[
\varphi(n) \geq \frac{6n^2}{\pi^2 \sigma(n)} \geq \frac{6n}{\pi^2 (\log n + 1)},
\] i.e., $\varphi(n) \gg n/\log n$.

This entry was posted in Analytic Number Theory, Divisor function, Euler's totient function and tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *