Averages of non-negative multiplicative functions
1. Asymptotic estimates
When looking for averages of functions that look like 1 or like the divisor function, Lemma 3.2 of offers an efficient easy path. The technique of comparison of two arithmetical function via their Dirichlet series is known as the Convolution method and is for instance decribed at length in , and in the course that can be found here.
Theorem (1995)
Let $(g_n)_{n\ge1}$, $(h_n)_{n\ge1}$ and $(k_n)_{n\ge1}$ be three complex sequences. Let $H(s)=\sum_nh_nn^{-s}$, and $\overline{H}(s)=\sum_n|h_n|n^{-s}$. We assume that $g=h\star k$, that $\overline{H}(s)$ is convergent for $\Re(s)\ge-1/3$ and further that there exist four constants $A$, $B$, $C$ and $D$ such that $$ \sum_{n\le t}k_n = A\log^2t+B\log t+C+\mathcal{O}^*(D t^{-1/3}) \text{ for $t>0$.} $$ Then we have for all $t>0$ : $$ \sum_{n\le t}g_n = u\log^2t+v\log t+w+\mathcal{O}^*(D t^{-1/3}\overline{H}(-1/3)) $$ with $u=AH(0)$, $v=2AH^{\prime}(0)+BH(0)$ and $w=AH^{\prime\prime}(0)+BH^{\prime}(0)+CH(0)$. We have also $$ \sum_{n\le t}ng_n = Ut\log t+Vt+W+\mathcal{O}^*(2.5D t^{2/3}\overline{H}(-1/3)) $$ with $$ \begin{aligned} U=&2AH(0), V=-2AH(0)+2AH^{\prime}(0)+BH(0),\\ W=&A(H^{\prime\prime}(0)-2H^{\prime}(0)+2H(0))+B(H^{\prime}(0)-H(0))+CH(0). \end{aligned} $$
This Lemma says that one derives information from $g_n$ from informations on the model $k_n$. When this model is $k_n=1$, the values concerning $A$, $B$ and $C$ are given by the first half of Lemma 3.3 of :
Lemma (1995)
For all $t>0$, we have $ \sum_{n\le t}1/n=\log t+\gamma+\mathcal{O}^*(0.9105 t^{-1/3}). $
When this model is $k_n=\tau(n)$, the number of divisors of $n$, the values concerning $A$, $B$ and $C$ are given by Corollary 2.2 of . Please note the "$\gamma^2-2\gamma_1$" which is wrongly typed as "$\gamma^2-\gamma_1$" in the aforementioned paper (and thanks to Tim Trudgian and David Platt for spotting this typo):
Lemma (2011)
We have, for all $t>0$, $ \sum_{n\le t}\tau(n)/n =\tfrac12\log^2t+2\gamma\log t +\gamma^2-2\gamma_1+ \mathcal{O}^*(1.16/t^{1/3}) $ where $\gamma_1$ is the second Laurent-Stieljes constant -- for instance and . In particular, we have $ \gamma_1= -0.0728158454836767248605863758749013191377 + \mathcal{O}^*(10^{-40}). $
The constants $H(0)$, $H'(0)$ and $H''(0)$ are to be computed. In most cases, the Dirichlet series has an Euler product, in which case, (see section 3 of ) we have
$ H(0)=\prod_p(1+\sum_mh_{p^m}), $ then $\displaystyle \frac{H^{\prime}(0)}{H(0)}= \sum_p \frac{\sum_mmh_{p^m}}{1+\sum_mh_{p^m}}(-\log p), $ and also
$$ \frac{H^{\prime\prime}(0)}{H(0)}= \left( \frac{H^{\prime}(0)}{H(0)} \right)^2+ \sum_p \left\{ \frac{\sum_mm^2h_{p^m}}{1+\sum_mh_{p^m}} -\left[\frac{\sum_mmh_{p^m}}{1+\sum_mh_{p^m}}\right]^2 \right\} \log^2p. $$ It is sometimes more expedient to use the same convolution method but by comparing the function to the function $q\mapsto q$. In such a case, the next lemma, Lemma 4.3 from , is handy.
Theorem (2015)
We have, for any real number $x\ge0$ and any real number $c\in[1,2]$, $\displaystyle \sum_{q\le x}q=\tfrac12 x^2+O^*(x^c/2)$.
This leads to the next theorem.
Theorem
Let $(h_n)_{n\ge1}$ be a complex sequences. Let $H(s)=\sum_nh_nn^{-s}$, and $\overline{H}(s)=\sum_n|h_n|n^{-s}$. We assume that $\overline{H}(s)$ is convergent for $\Re(s)\ge c$, for some $c\in[1,2]$. Then we have for all $t>0$ : $$ \sum_{n\le t}\sum_{d|n}\frac{n}{d}h(d) = \frac{t^2}{2}H(2)+O^*(t^c\overline{H}(c)/2). $$
A typical usage is to evaluate $\sum_{n\le t}\phi(n)$, with $h(d)=\mu(d)$.
The convolution method has been brought one step further in where the following theorem is proved.
Theorem (2017)
Let $(g(m))_{m\ge1}$ be a sequence of complex numbers such that both series $\sum_{m\ge1} g(m)/m$ and $\sum_{m\ge1} g(m)(\log m)/m$ converge. We define $G^\sharp(x)=\sum_{m> x} g(m)/m$ and assume that $\int_1^\infty |G^\sharp(t)|dt/t$ converges. Let $A_0\ge1$ be a real parameter. We have \begin{equation*} \sum_{n\le D}\frac{(g\star{1\!\!1})(n)}{n} =\sum_{m\ge1}\frac{g(m)}{m}\Bigl(\log\frac{D}{m}+\gamma\Bigr) +\int_{D/A_0}^\infty G^\sharp(t)\frac{dt}{t} +O^*(\mathfrak{R}) \end{equation*} where $\mathfrak{R}$ is defined by \begin{equation*} \mathfrak{R} = \left|\sum_{1\le a\le A_0}\frac{1}{a}G^\sharp\left(\frac{D}{a}\right)+ G^\sharp\left(\frac{D}{A_0}\right)\left(\log\frac{A_0}{[A_0]} -R([A_0])\right) \right| +\frac{6/11}{D}\sum_{m\le D/A_0}|g(m)| \end{equation*} where $[A_0]$ is the integer part of $A_0$, while the remainder $R$ is defined by $R(X)=\sum_{n\le X}1/n-\log X-\gamma$.
The remainder $R(X)$ is shown in Lemma to verify $|R(X)|\le \gamma/X$ for every $X > 0$, and $|R(X)|\le (6/11)/X$ when $X\ge1$.
Theorem 21.1 of offers a fully explicit estimate for the average of a general non-negative multiplicative function, but it is often numerically rather poor. It relies on the technique developped by .
Theorem (2009)
Let $g$ be a non-negative multiplicative function. Let $A$ and $\kappa$ be three positive real parameters such that, for any $Q\ge1$, one has $$ \sum_{\substack{ p\ge2, \nu\ge1\\ p^{\nu}\le Q}} g\bigl(p^{\nu}\bigr)\log\bigl(p^{\nu}\bigr) = \kappa\log Q+\mathcal{O}^*(L) $$ and $ \sum_{p\ge2} \sum_{\nu,k\ge1}g\bigl(p^k\bigr)g\bigl(p^{\nu}\bigr)\log\bigl(p^{\nu}\bigr) \le A. $ Then, when $D\ge\exp(2(L+A))$, we have $$ \sum_{d\le D}g(d)= C\left(\log D\right)^{\kappa} \left(1+\mathcal{O}^*\bigl(B/\log D\bigr)\right) $$ where $B=2(L+A)\bigl(1+2(\kappa+1)e^{\kappa+1}\bigr)$ and $$ C=\frac{1}{\Gamma(\kappa+1)} \prod_{p\ge2}\biggl\{ \biggl(\sum_{\nu\ge0}g\bigl(p^{\nu}\bigr)\biggr) \biggl(1-\frac1p\biggr)^{\kappa}\biggr\}. $$
2. Upper bounds
When looking for an upper bound, it is common to compare sums to an Euler product, via, $$ \sum_{n\le y}f(n)/n\le \prod_{p\le y} \left(1+\sum_{1\le m\le \log y/\log p}f(p^m)\right) $$ valid when $f$ is non-negative and multiplicative. Lemma 4 of extends this. Let $z$ be a parameter and $v_z(n)$ be the characteristic function of those integers that have all their prime factors $p\le z$.
Theorem (2000)
Let $z\ge2$, $f$ a multiplicative function with $f\ge0$ and $S=\sum_{p\le z}\frac{f(p)}{1+f(p)}\log p$. We assume that $S>0$ and write $K(t)=\log t-1-(1/t)$. For any $y$ such that $\log y\ge S$, we have $$ \sum_{n > y}v_z(n)\mu^2(n)f(n) \le \prod_{p\le z}(1+f(p))\exp\left(-\frac{\log y}{\log z} K\left(\frac{\log y}{S}\right)\right) $$ $$ \sum_{n \le y}v_z(n)\mu^2(n)f(n) \ge \prod_{p\le z}(1+f(p))\left\{1-\exp\left(-\frac{\log y}{\log z} K\left(\frac{\log y}{S}\right)\right)\right\} $$ and in particular, when $\log y\ge 7S$, we have $$ \sum_{n > y}v_z(n)\mu^2(n)f(n) \le \prod_{p\le z}(1+f(p))\exp\left(-\frac{\log y}{\log z}\right) $$ $$ \sum_{n \le y}v_z(n)\mu^2(n)f(n) \ge \prod_{p\le z}(1+f(p))\left\{1-\exp\left(-\frac{\log y}{\log z}\right)\right\}. $$
It is sometimes required to compare a function close to $1$ (or more generally to the divisor function $\tau_k$) to a function close to $1/n$ or $\tau_k(n)/n$. Theorem 01 of offers a fast way of doing so.
Theorem (1988)
Let $f$ be a non-negative multiplicative function such that, for some $A$ and $B$, $$ \sum_{p\le y} f(p)\log p\le Ay \quad(y\ge 0),\quad \sum_p\sum_{\nu\ge2} \frac{f(p^\nu)}{p^\nu}\log p^{\nu}\le B. $$ Then, for $x > 1$, $$ \sum_{n\le x}f(n)\le (A+B+1)\frac{x}{\log x}\sum_{n\le x}\frac{f(n)}{n} $$
See also Section 4.6, and for instance Theorem 4.22, of . In particular, in case a further condition is assumed, we have Theorem 4.28 of at our disposal.
Theorem (2012)
Let $f$ be a non-negative multiplicative function such that, for every prime $p$ and every non-negative power $a$ the condition $f(p^{a+1})\ge f(p^a)$ holds, we have for $x \ge 1$ $$ \sum_{n\le x}f(n)\le x\prod_{p\le x} \Bigl(1-\frac{1}{p}\Bigr)\Bigl( 1+\sum_{a\ge 1}\frac{f(p^a)}{p^a}\Bigr). $$
The next lemma is handy to remove coprimality conditions. It originates from .
Theorem (1965)
Let $f$ be a non-negative multiplicative function and let $d$ be a positive integer. We have for $x \ge 0$ $$ \sum_{n\le x}\mu^2(n)f(n)\le \prod_{p|d}(1+f(p)) \sum_{\substack{n\le x,\\ (n,d)=1}}\mu^2(n)f(n) \le \sum_{n\le xd}\mu^2(n)f(n). $$
Though it is somewhat difficult to get, this lemma has been further generalized in Lemma 4.1 of .
3. Estimates of some special functions
contains the following Theorem.
Theorem (1988)
Let $R(x)=\sum_{n\le x}\mu^2(n)-6x/\pi^2$. We have $ |R(x+y)-R(x)|\le 1.6749\sqrt{y}+0.6212 x/y$ and $ |R(x+y)-R(x)|\le 0.7343y/x^{1/3}+1.4327 x^{1/3}$ for $x,y\ge1$.
See also . and contains:
Theorem (2008)
We have $ |\sum_{n\le x}\mu^2(n)-6x/\pi^2|\le 0.02767\sqrt{x}$ for $x\ge 438653$. One can replace $(0.02767, 438653)$ by $(0.036438, 82005)$, by $(0.1333, 1004)$, by $(1/2, 8)$ or by $(1,1)$.

Lemma 3.4 of gives us:
Theorem (2013)
We have $\frac{6}{\pi^2}\log x+0.578\le \sum_{n\le x}\mu^2(n)/n\le \frac{6}{\pi^2}\log x+1.166$ for $x\ge1$ When $x\ge1000$, one can also replace the couple $(0.578, 1.166)$ by $(1.040, 1.048)$.
In fact, in the same paper, the asymptotic $$ \sum_{n\le x}\frac{\mu^2(n)}{n} =\frac{6}{\pi^2}\Bigl(\log x+2\sum_{p\ge2}\frac{\log p}{p^2-1}+\gamma\Bigr) +O^*(3/x^{1/3}) $$ valid for $x\ge1$ is proved. A script using SAGE and another one using GP/PARI are then displayed to explain how to cover the initial range in $x$. See also Lemma 1 of for an earlier version.
The main result reads as follows.
Theorem (2012)
We define $\Delta(x)=\sum_{n\le x}\tau(n)-x(\log x+2\gamma-1)$. We have
  • When $x\ge 1$, we have $|\Delta(x)|\le 0.961\, {x^{1/2}}$.
  • When $x\ge 1\,981$, we have $|\Delta(x)|\le 0.482\, {x^{1/2}}$.
  • When $x\ge 5\,560$, we have $|\Delta(x)|\le 0.397\, {x^{1/2}}$.
  • When $x\ge 5$, we have $|\Delta(x)|\le 0.764\, {x^{1/3}\log x}$.
For evaluation of the average of the divisor function on integers belonging to a fixed residue class modulo 6, see Corollary to Proposition 3.2 of . For more complicated sums and when $x$ is large with respect to $k$, one can use .
Theorem (1939)
Let $k$ and $\ell$ be two positive integers. We have for any real number $x\ge1$ $$ \sum_{m\le x}\tau_k^\ell(m) \le x\frac{k^\ell}{(k!)^{\frac{k^\ell-1}{k-1}}}(\log x+k^\ell-1)^{k^\ell-1}. $$
See for some upper bounds linked with $\tau_3$.
contains the following bounds, better than the above when $x$ is small with respect to $k$.
Theorem (2002)
Let $k\ge1$ be a positive integer.
  • When $x\ge1$ is a real number, we have $\sum_{m\le x}\tau_k(m)\le x(\log x+\gamma+(1/x))^{k-1}$.
  • When $x\ge6$ is a real number, we have $\sum_{m\le x}\tau_k(m)\le 2x(\log x)^{k-1}$.
In , we find the next result.
Theorem (2021)
For $x\ge 2$, we have $$ \sum_{n\le x} d_4(n) = C_1x(\log x)^3 + C_2x(\log x)^2 +C_3x(\log x +C_4x +\mathcal{O}^*(4.48\,x^{3/4}\log x) $$ where the constants $C_1=1/6$, $C_2=2\gamma-1/2$, and $C_3$ and $C_4$ are the expected ones and may be expressed in terms of the Stieltjes constants $\gamma_i$.
They deduce for instance from this that $\sum_{n\le x}d_4(n)\le(1/3)x(\log x)^3$ when $x\ge 193$. In the same paper, these authors also establish the next estimate.
Theorem (2021)
For $x\ge 2$, we have $$ \sum_{n\le x} d(n)^2 = D_1x(\log x)^3 + D_2x(\log x)^2 +D_3x(\log x +D_4x +\mathcal{O}^*(9.73\,4.48\,x^{3/4}\log x+0.73\,\sqrt{x}) $$ where the constants $D_1=1/\pi^2$, and $D_2$, $D_3$ and $D_4$ are the expected ones and may be expressed in terms of usual constants.
They deduce for instance from this that $\sum_{n\le x}d(n)^2\le(1/4)x(\log x)^3$ when $x\ge 433$ and that $\sum_{n\le x}d(n)^2\le x(\log x)^3$ when $x\ge 7$. In , we find the next result.
Theorem (2015)
Let $b$ and $c$ be two integers such that $\delta=b^2-c$  is non-zero, square-free and not congruent to 1 modulo 4. Assume further that the function $n^2+2bn+c$ is positive and non-decreasing when $n\ge1$.Then, for $N\ge1$, we have $$ \sum_{n\le N}\tau(n^2+2bn+c)\le C_1 N\log N+C_2+C_3 $$ where the constants $C_1$, $C_2$  and $C_3$  are defined as follows. We first define $\xi=\sqrt{1+2|b|+|c|}$ and $\kappa=\frac{4}{\pi^2}\sqrt{4|\delta|}(\log(4|\delta|)+0.648)$. Then $$ C_1=\frac{12}{\pi^2}(\log\kappa+1), C_2=2\biggl[\kappa+(\log\kappa+1)\Bigl(\frac{6}{\pi^2}\log\xi+1.166\Bigr)\biggr], C_3=2\kappa (\max(|b|,|c|^{1/2})+1). $$
See for the number of divisors of a reducible quadratic polynomial.
Evaluations of Lemma 4.3 of are improved in Lemma 12 of . Only upper bounds are given, but the proof given there gives the lower bounds as well. This gives the first two estimates, while the third one comes from Lemma 4.3 of .
Theorem (2015)
Let $x\ge1$ be a real number. We have
  • $\displaystyle 0.786x-0.3761-8.14x^{2/3} \le \sum_{n\le x}2^{\omega(n)}-\frac{6}{\pi^2}x\log x \le 0.787x-0.3762+8.14x^{2/3}$
  • $\displaystyle 1.3947\log x+0.4106-3.253x^{-1/3} \le \sum_{n\le x}\frac{2^{\omega(n)}}{n}-\frac{3}{\pi^2}(\log x)^2 \le 1.3948\log x+0.4107+3.253x^{-1/3}$,
  • $\displaystyle \sum_{n\le x}\frac{2^{\omega(2n-1)}}{2n-1} \le \frac{3}{2\pi^2}(\log x)^2+3.123\log x+3.569+\frac{0.525}{x}$.
We take the next lemma from , Lemma 2.
Theorem (2015)
Let $x\ge1$ be a real number. We have $\sum_{n\le x}\phi(n)/n\le \frac{6}{\pi^2}x+\log x +1$.
Lemma 3 of the same paper is as follows.
Theorem (2015)
Let $x\ge1$ be a real number. We have $\sum_{n\le x}n\phi(n)\le \frac{2}{\pi^2}x^3+\frac12x^2\log x +x^2$.
Several estimates are proved in . For instance Theorem 1.2 gives the following.
Theorem (2017)
Let $x\ge1$ be a real number. We have $\sum_{n\le x}\mu^2(n)/\phi(n)= \log x +c_0+O^*(3.95/\sqrt{x})$ where $\displaystyle c_0=\gamma+\sum_{p\ge2}\frac{\log p}{p(p-1)}$. When $x > 1$, this $O^*$ can be replaced by $O^*(21/\sqrt{x\log x})$.
The function $\sum_{n\le x}\mu^2(n)/\phi(n)$ has been the subject of several estimates, see for instance Lemma 7 of , Lemma 3.4-3.5 of , the earlier paper and Lemma 4.5 of where the error term $O^*(58/\sqrt{x})$ is achieved. The constant $c_0$ is evaluated precisely in (2.11) of .
4. Euler products
contains estimates regarding $\prod_{p}(1-1/p)$ and its inverse. In particular we find the next results therein.
Theorem (1962)
  • When $x > 1$, we have $\displaystyle 1-\frac{1}{\log^2x}\le e^\gamma(\log x)\prod_{p\le x}\Bigl(1-\frac{1}{p}\Bigr)\le 1+\frac{1}{2\log^2x}$.
  • When $x > 1$, we have $\displaystyle 1-\frac{1}{2\log^2x}\le e^{-\gamma}\prod_{p\le x}\Bigl(1-\frac{1}{p}\Bigr)^{-1}/\log x\le 1+\frac{1}{\log^2x}$.
Several other estimates are proven. In , it is proved that
Theorem (2016)
  • When $x > 2\,278\,382$, we have $\displaystyle 1-\frac{1}{5\log^3x}\le e^\gamma(\log x)\prod_{p\le x}\Bigl(1-\frac{1}{p}\Bigr)\le 1+\frac{1}{5\log^3x}$.
  • When $x > 2\,278\,382$, we have $\displaystyle 1-\frac{1}{5\log^3x}\le e^{-\gamma}\prod_{p\le x}\Bigl(1-\frac{1}{p}\Bigr)^{-1}/\log x\le 1+\frac{1}{5\log^3x}$.
In , the reader will find explicit upper bounds for $\displaystyle \prod_{\substack{p\le x,\\ p\equiv a[q]}}\Bigl(1-\frac{1}{p}\Bigr)^{-1}$ Theorem 5 of contains the next result.
Theorem (2017)
Let $\epsilon$ be a complex number such that $|\epsilon|\le 2$. When $x\ge\exp(22)$, we have $\displaystyle\prod_{p\le x}\Bigl(1+\frac{\epsilon}{p}\Bigr) =e^{\gamma(\epsilon)+\epsilon B}(\log x)^\epsilon \biggl\{1+O^*\Bigl(\frac{0.841}{\log^3x}\Bigr)\biggr\}$ where $\displaystyle\gamma(\epsilon)=\sum_{p\ge2}\sum_{n\ge2}(-1)^{n+1}\frac{\epsilon^n}{np^n}$ and $\displaystyle B=\gamma+\sum_{p\ge2}\bigl(\log(1-1/p)+(1/p)\bigr)$.
Equation (2.2) of gives an approximate value for $B$.
Last updated on June 10th, 2019, by Olivier Ramaré