# §27.11 Asymptotic Formulas: Partial Sums

The behavior of a number-theoretic function $f(n)$ for large $n$ is often difficult to determine because the function values can fluctuate considerably as $n$ increases. It is more fruitful to study partial sums and seek asymptotic formulas of the form

 27.11.1 $\sum_{n\leq x}f(n)=F(x)+\mathop{O\/}\nolimits\!\left(g(x)\right),$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $n$: positive integer and $x$: real number Permalink: http://dlmf.nist.gov/27.11.E1 Encodings: TeX, pMML, png See also: info for 27.11

where $F(x)$ is a known function of $x$, and $\mathop{O\/}\nolimits\!\left(g(x)\right)$ represents the error, a function of smaller order than $F(x)$ for all $x$ in some prescribed range. For example, Dirichlet (1849) proves that for all $x\geq 1$,

 27.11.2 $\sum_{n\leq x}\mathop{d\/}\nolimits\!\left(n\right)=x\mathop{\ln\/}\nolimits x% +(2\EulerConstant-1)x+\mathop{O\/}\nolimits\!\left(\sqrt{x}\right),$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\EulerConstant$: Euler’s constant, $\mathop{d_{\NVar{k}}\/}\nolimits\!\left(\NVar{n}\right)$: divisor function, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number A&S Ref: 24.3.3 III Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E2 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11

where $\EulerConstant$ is Euler’s constant (§5.2(ii)). Dirichlet’s divisor problem (unsolved in 2009) is to determine the least number $\theta_{0}$ such that the error term in (27.11.2) is $\mathop{O\/}\nolimits\!\left(x^{\theta}\right)$ for all $\theta>\theta_{0}$. Kolesnik (1969) proves that $\theta_{0}\leq\frac{12}{37}$.

Equations (27.11.3)–(27.11.11) list further asymptotic formulas related to some of the functions listed in §27.2. They are valid for all $x\geq 2$. The error terms given here are not necessarily the best known.

 27.11.3 $\sum_{n\leq x}\frac{\mathop{d\/}\nolimits\!\left(n\right)}{n}=\frac{1}{2}(% \mathop{\ln\/}\nolimits x)^{2}+2\EulerConstant\mathop{\ln\/}\nolimits x+% \mathop{O\/}\nolimits\!\left(1\right),$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\EulerConstant$: Euler’s constant, $\mathop{d_{\NVar{k}}\/}\nolimits\!\left(\NVar{n}\right)$: divisor function, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E3 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11

where $\EulerConstant$ again is Euler’s constant.

 27.11.4 $\displaystyle\sum_{n\leq x}\mathop{\sigma_{1}\/}\nolimits\!\left(n\right)$ $\displaystyle=\frac{\pi^{2}}{12}x^{2}+\mathop{O\/}\nolimits\!\left(x\mathop{% \ln\/}\nolimits x\right).$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\sigma_{\NVar{\alpha}}\/}\nolimits\!\left(\NVar{n}\right)$: sum of powers of divisors of $n$, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number A&S Ref: 24.3.3 III (in slightly different form) Permalink: http://dlmf.nist.gov/27.11.E4 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11 27.11.5 $\displaystyle\sum_{n\leq x}\mathop{\sigma_{\alpha}\/}\nolimits\!\left(n\right)$ $\displaystyle=\frac{\mathop{\zeta\/}\nolimits\!\left(\alpha+1\right)}{\alpha+1% }x^{\alpha+1}+\mathop{O\/}\nolimits\!\left(x^{\beta}\right),$ $\alpha>0$, $\alpha\neq 1$, $\beta=\max(1,\alpha)$.
 27.11.6 $\displaystyle\sum_{n\leq x}\mathop{\phi\/}\nolimits\!\left(n\right)$ $\displaystyle=\frac{3}{\pi^{2}}x^{2}+\mathop{O\/}\nolimits\!\left(x\mathop{\ln% \/}\nolimits x\right).$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\phi_{\NVar{k}}\/}\nolimits\!\left(\NVar{n}\right)$: sum of powers of integers relatively prime to $n$, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number A&S Ref: 24.3.2 III (in slightly different form) Permalink: http://dlmf.nist.gov/27.11.E6 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11 27.11.7 $\displaystyle\sum_{n\leq x}\frac{\mathop{\phi\/}\nolimits\!\left(n\right)}{n}$ $\displaystyle=\frac{6}{\pi^{2}}x+\mathop{O\/}\nolimits\!\left(\mathop{\ln\/}% \nolimits x\right).$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\phi_{\NVar{k}}\/}\nolimits\!\left(\NVar{n}\right)$: sum of powers of integers relatively prime to $n$, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number Permalink: http://dlmf.nist.gov/27.11.E7 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11
 27.11.8 $\sum_{p\leq x}\frac{1}{p}=\mathop{\ln\/}\nolimits\mathop{\ln\/}\nolimits x+A+% \mathop{O\/}\nolimits\!\left(\frac{1}{\mathop{\ln\/}\nolimits x}\right),$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $p,p_{1},\ldots$: prime numbers, $x$: real number and $A$: constant Permalink: http://dlmf.nist.gov/27.11.E8 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11

where $A$ is a constant.

 27.11.9 $\sum_{\begin{subarray}{c}p\leq x\\ p\equiv h\!\!\!\!\!\pmod{k}\end{subarray}}\frac{1}{p}=\frac{1}{\mathop{\phi\/}% \nolimits\!\left(k\right)}\mathop{\ln\/}\nolimits\mathop{\ln\/}\nolimits x+B+% \mathop{O\/}\nolimits\!\left(\frac{1}{\mathop{\ln\/}\nolimits x}\right),$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\phi_{\NVar{k}}\/}\nolimits\!\left(\NVar{n}\right)$: sum of powers of integers relatively prime to $n$, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $k$: positive integer, $p,p_{1},\ldots$: prime numbers and $x$: real number Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E9 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11

where $\left(h,k\right)=1$, $k>0$, and $B$ is a constant depending on $h$ and $k$.

 27.11.10 $\sum_{p\leq x}\frac{\mathop{\ln\/}\nolimits p}{p}=\mathop{\ln\/}\nolimits x+% \mathop{O\/}\nolimits\!\left(1\right).$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $p,p_{1},\ldots$: prime numbers and $x$: real number Permalink: http://dlmf.nist.gov/27.11.E10 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11
 27.11.11 $\sum_{\begin{subarray}{c}p\leq x\\ p\equiv h\!\!\!\!\!\pmod{k}\end{subarray}}\frac{\mathop{\ln\/}\nolimits p}{p}=% \frac{1}{\mathop{\phi\/}\nolimits\!\left(k\right)}\mathop{\ln\/}\nolimits x+% \mathop{O\/}\nolimits\!\left(1\right),$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\phi_{\NVar{k}}\/}\nolimits\!\left(\NVar{n}\right)$: sum of powers of integers relatively prime to $n$, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $k$: positive integer, $p,p_{1},\ldots$: prime numbers and $x$: real number Referenced by: §27.11, §27.11 Permalink: http://dlmf.nist.gov/27.11.E11 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11

where $\left(h,k\right)=1$, $k>0$.

Letting $x\to\infty$ in (27.11.9) or in (27.11.11) we see that there are infinitely many primes $p\equiv h\pmod{k}$ if $h,k$ are coprime; this is Dirichlet’s theorem on primes in arithmetic progressions.

 27.11.12 $\sum_{n\leq x}\mathop{\mu\/}\nolimits\!\left(n\right)=\mathop{O\/}\nolimits\!% \left(xe^{-C\sqrt{\mathop{\ln\/}\nolimits x}}\right),$ $x\to\infty$, Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\mu\/}\nolimits\!\left(\NVar{n}\right)$: Möbius function, $e$: base of exponential function, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $n$: positive integer, $x$: real number and $C$: constant A&S Ref: 24.3.1 III Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E12 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11

for some positive constant $C$,

 27.11.13 $\lim_{x\to\infty}\frac{1}{x}\sum_{n\leq x}\mathop{\mu\/}\nolimits\!\left(n% \right)=0,$ Symbols: $\mathop{\mu\/}\nolimits\!\left(\NVar{n}\right)$: Möbius function, $n$: positive integer and $x$: real number Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E13 Encodings: TeX, pMML, png See also: info for 27.11
 27.11.14 $\lim_{x\to\infty}\sum_{n\leq x}\frac{\mathop{\mu\/}\nolimits\!\left(n\right)}{% n}=0,$ Symbols: $\mathop{\mu\/}\nolimits\!\left(\NVar{n}\right)$: Möbius function, $n$: positive integer and $x$: real number A&S Ref: 24.3.1 III Referenced by: §27.11 Permalink: http://dlmf.nist.gov/27.11.E14 Encodings: TeX, pMML, png See also: info for 27.11
 27.11.15 $\lim_{x\to\infty}\sum_{n\leq x}\frac{\mathop{\mu\/}\nolimits\!\left(n\right)% \mathop{\ln\/}\nolimits n}{n}=-1.$ Symbols: $\mathop{\mu\/}\nolimits\!\left(\NVar{n}\right)$: Möbius function, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $x$: real number A&S Ref: 24.3.1 III Referenced by: §27.11, §27.11 Permalink: http://dlmf.nist.gov/27.11.E15 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: info for 27.11

Each of (27.11.13)–(27.11.15) is equivalent to the prime number theorem (27.2.3). The prime number theorem for arithmetic progressions—an extension of (27.2.3) and first proved in de la Vallée Poussin (1896a, b)—states that if $\left(h,k\right)=1$, then the number of primes $p\leq x$ with $p\equiv h\pmod{k}$ is asymptotic to $x/(\mathop{\phi\/}\nolimits\!\left(k\right)\mathop{\ln\/}\nolimits x)$ as $x\to\infty$.