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 [Ramaré, 1995] 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 [Berment and Ramaré, 2012], and in the course that can be found
herefootnote{url{https://ramare-olivier.github.io/CoursNouakchott/index.html}}.
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
Then we have for all \(t>0\) :
with \(u=AH(0)\), \(v=2AH^{\prime}(0)+BH(0)\) and \(w=AH^{\prime\prime}(0)+BH^{\prime}(0)+CH(0)\). We have also
with
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 [Ramaré, 1995]:
Lemma (1995)
\(\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 [Berkane et al., 2012]. 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)
where \(\gamma_1\) is the second Laurent-Stieljes constant, see for instance [Kreminski, 2003] and [Coffey, 2006]. 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 [Ramaré, 1995]) we have
\(H(0)=\prod_p(1+\sum_mh_{p^m}),\) then
and also
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 [Ramaré, 2016], is handy.
Theorem (2015)
We have, for any real number \(x\ge0\) and any real number \(c\in[1,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\) :
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 [P. and Ramaré, 2017] 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
where \(\mathfrak{R}\) is defined by
and 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 [Ramaré, 2009] 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 [Levin and Fainleib, 1967].
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
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 \(\displaystyle \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
2. Upper bounds¶
When looking for an upper bound, it is common to compare sums to an Euler product, via,
\(\displaystyle \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 [Daboussi and Rivat, 2001] 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 \(\displaystyle \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)\) \(\displaystyle \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 \(\displaystyle \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)\) \(\displaystyle \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 [Hall and Tenenbaum, 1988] offers a fast way of doing so.
Theorem (1988)
Let \(f\) be a non-negative multiplicative function such that, for some \(A\) and \(B\), \(\displaystyle \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\), \(\displaystyle \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 Bordell:cite:`Bordelles12. In particular, in case a further condition is assumed, we have Theorem 4.28 of Bordell:cite:`Bordelles12 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\) \(\displaystyle \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 [van Lint and Richert, 1965].
Theorem (1965)
Let \(f\) be a non-negative multiplicative function and let \(d\) be a positive integer. We have for \(x \ge 0\) \(\displaystyle \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 [Ramaré, 2012].
3. Estimates of some special functions¶
[Cohen and Dress, 1988] 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 [Costa Pereira, 1989]. [Moser and MacLeod, 1966] and [Cohen et al., 2007] 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, 1664)\), by \((1/2, 8)\) or by \((1,1)\).
This estimate is (slightly) improved in Corollary 3.4 of [Ramaré, 2019] in the next one.
Theorem (2019)
When \(x > 1\), we have \(\displaystyle\sum_{n\le x}\mu^2(n)=\frac{6}{\pi^2}x+O^*(1.06\sqrt{x/\log x}).\)
Lemma 3.4 of [Ramaré, 2016] 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 Theorem 3.2 and Corollary 3.3 of [Ramaré, 2019], we find the next result.
Theorem (2019)
When \(x \ge 3475\), we have \(\displaystyle \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^*(0.073/\sqrt{x}).\) And when \(x\ge 1665\), the error term may be (asymptotically) improved to \(O^*(0.35/\sqrt{x\log x})\).
See also Lemma 1 of [Schoenfeld, 1969] for an earlier version.
Lemma 2 of [Riesel and Vaughan, 1983] contains the next evaluation.
Theorem (1983)
For \(y \ge 1\), we have \(\displaystyle \sum_{q\le y}\mu^2(q)\prod_{\substack{p|q\\p\neq2}}\frac{2}{p-2} = \tfrac14\prod_{p > 2}\frac{(p-1)^2}{p(p-2)} \biggl((\log y)^2-A_3\log y -A_4+\mathcal{O}^*(1088/y^{1/3})\biggr)\) where \(A_3=6.023476\cdots\) and \(A_4=1.114073\cdots\).
The main result [Berkane et al., 2012] 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 [Deshouillers and Dress, 1988].
For more complicated sums and when \(x\) is large with respect to \(k\), one can use [Mardjanichvili, 1939].
Theorem (1939)
Let \(k\) and \(\ell\) be two positive integers. We have for any real number \(x\ge1\) \(\displaystyle \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 [Deshouillers and Dress, 1988] for some upper bounds linked with \(\tau_3\).
[Bordellès, 2002] 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 [Cully-Hugill and Trudgian, 2021], we find the next result.
Theorem (2021)
For \(x\ge 2\), we have \(\displaystyle \sum_{n\le x} \tau_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}\tau_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 \(\displaystyle \sum_{n\le x} \tau(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}\tau(n)^2\le(1/4)x(\log x)^3\) when \(x\ge 433\) and that \(\sum_{n\le x}\tau(n)^2\le x(\log x)^3\) when \(x\ge 7\).
In [Lapkova, 2016], 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 \(\displaystyle \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 \(\displaystyle 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 [Lapkova, 2017] for the number of divisors of a reducible quadratic polynomial.
Evaluations of Lemma 4.3 of [Cipu, 2015] are improved in Lemma 12 of [Trudgian, 2015]. 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 [Cipu, 2015].
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 [Treviño, 2015], 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 [P. and Ramaré, 2017], [Ramaré and Viswanadham, 2021] and in [Ramaré, 2019].
For instance Theorem 3.1 in the latter paper contains the following.
Theorem (2018)
Let \(x\ge1\) be a real number. We have \(\sum_{n\le x}\mu^2(n)/\phi(n)= \log x +c_0+O^*(2.44/\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^*(11/\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 [Montgomery and Vaughan, 1973], Lemma 3.4-3.5 of [Ramaré, 1995], the earlier paper [Ward, 1927] and Lemma 4.5 of [Büthe, 2014] where the error term \(O^*(58/\sqrt{x})\) is achieved. The constant \(c_0\) is evaluated precisely in (2.11) of [Rosser and Schoenfeld, 1962].
4. Euler products¶
[Rosser and Schoenfeld, 1962] 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 [Dusart, 2018], 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 [Bordellés, 2005], 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 [Mawia, 2017] 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 [Rosser and Schoenfeld, 1962] gives an approximate value for \(B\).