Average Orders Divisor Sums and Representation Counts

Since $t\mapsto 1\mathrm{/}t$ is decreasing on $[1,\mathrm{\infty })$ by The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, monotonicity of the integral and additivity over subintervals give ${\int }_n^{n+1}\frac{dt}{t}\le \frac{1}{n}\text{for every integer }n\ge 1,$ and $\frac{1}{n}\le {\int }_{n-1}^n\frac{dt}{t}\text{for every integer }n\ge 2.$

Put $E_N:={\sum }_{n=1}^{N}1\mathrm{/}n-\log (N+1)$. Summing the first inequality of step 1.1 from $n=1$ to $N$ gives $E_N\ge 0$, and the same inequality at $n=N+1$ gives $E_{N+1}-E_N=\frac{1}{N+1}-{\int }_{N+1}^{N+2}\frac{dt}{t}\ge 0.$ Also summing the second inequality of step 1.1 from $n=2$ to $N$ gives ${\sum }_{n=1}^N\frac{1}{n}\le 1+\log N<1+\log (N+1),$ so $0\le E_N<1$. Thus $(E_N)$ is increasing and bounded, hence convergent by A nondecreasing sequence bounded above converges to the supremum of its range, and a nonincreasing sequence bounded below to the infimum.

Let $L:={\lim }_N{E}_N$. Since ${\sum }_{n=1}^N\frac{1}{n}-\log N=E_N+\log \text{\hspace{0.17em}⁣}(1+\frac{1}{N}),$ and $0\le \log (1+1\mathrm{/}N)\le 1\mathrm{/}N$ by step 1.1, the sequence in The Euler-Mascheroni constant has the same limit $L$. Therefore $L=\gamma$, and $0\le {\sum }_{n=1}^N\frac{1}{n}-\log N-\gamma \le \frac{1}{N}\mathrm{.}$

For the given real $x$, let $N:=\lfloor x\rfloor$. Then $N\le x<N+1$, so $0\le \log x-\log N=\log (x\mathrm{/}N)\le \log (1+1\mathrm{/}N)\le 1\mathrm{/}N$. Combining this with step 3.1 yields ${\sum }_{n\le x}\frac{1}{n}={\sum }_{n=1}^N\frac{1}{n}=\log x+\gamma +O(1\mathrm{/}N)=\log x+\gamma +O(1\mathrm{/}x),$ because $N\ge x\mathrm{/}2$ for every $x\ge 1$.

By Dirichlet convolution of arithmetic functions, ${\sum }_{n\le x}(f\ast g)(n)={\sum }_{n\le x}{\sum }_{d\mid n}f(d)g(n\mathrm{/}d)={\sum }_{ab\le x}f(a)g(b),$ where the last equality is the finite reindexing of Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule.

Every lattice point $(a,b)$ with $ab\le x=UV$ lies in at least one of the regions $a\le U$ or $b\le V$, for otherwise $a>U$ and $b>V$ would give $ab>UV=x$. Therefore ${\sum }_{ab\le x}f(a)g(b)={\sum }_{\begin{array}{c}ab\le x\\ a\le U\end{array}}f(a)g(b)+{\sum }_{\begin{array}{c}ab\le x\\ b\le V\end{array}}f(a)g(b)-{\sum }_{\begin{array}{c}a\le U\\ b\le V\end{array}}f(a)g(b)\mathrm{.}$

For fixed $a\le U$, the inner sum over $b$ is exactly $G(x\mathrm{/}a)$, and for fixed $b\le V$ the inner sum over $a$ is exactly $F(x\mathrm{/}b)$. The overlap sum factors as $({\sum }_{a\le U}f(a))({\sum }_{b\le V}g(b))=F(U)G(V)\mathrm{.}$ Substituting these identities into step 2.1 gives the claimed formula.

By The divisor functions arise by Dirichlet convolution, $\tau =\mathbf{1}\ast \mathbf{1}$. Applying Dirichlet's hyperbola method for summatory convolutions with $f=g=\mathbf{1}$ and $U=V=\sqrt{x}$ gives ${\sum }_{n\le x}\tau (n)=2{\sum }_{a\le \sqrt{x}}\lfloor \frac{x}{a}\rfloor -\lfloor \sqrt{x}{\rfloor }^2=2{\sum }_{a=1}^N\lfloor \frac{x}{a}\rfloor -N^2\mathrm{.}$

Since $\lfloor x\mathrm{/}a\rfloor =x\mathrm{/}a+O(1)$ uniformly in $a$, summing over $1\le a\le N$ yields ${\sum }_{a=1}^N\lfloor \frac{x}{a}\rfloor =x{\sum }_{a=1}^N\frac{1}{a}+O(N)\mathrm{.}$

By The harmonic sum is log x plus gamma plus O(1/x), ${\sum }_{a=1}^{N}1\mathrm{/}a=\log N+\gamma +O(1\mathrm{/}N)$. Also $N^2\le x<(N+1{)}^2$, so $x=N^2+O(N)$ and $\log N=\frac{1}{2}\log x+O(1\mathrm{/}N)$. Substituting these into step 2.1 gives $2{\sum }_{a=1}^N\lfloor \frac{x}{a}\rfloor =x\log x+2\gamma x+O(\sqrt{x})\mathrm{.}$

Since $N^2=x+O(\sqrt{x})$, combining step 3.1 with step 1.1 yields ${\sum }_{n\le x}\tau (n)=x\log x+(2\gamma -1)x+O(\sqrt{x})\mathrm{.}$

The function $\log$ of The natural logarithm as the inverse of the exponential function is increasing on $(0,\mathrm{\infty })$ by The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, so monotonicity of the integral gives ${\int }_1^N\log tdt\le {\sum }_{n=1}^N\log n\le {\int }_1^{N+1}\log tdt\mathrm{.}$

By Sums, scalar multiples, products and quotients: $(f+g{)}^{\mathrm{\prime }}(c)=f^{\mathrm{\prime }}(c)+g^{\mathrm{\prime }}(c)$, $(\alpha f{)}^{\mathrm{\prime }}(c)=\alpha f^{\mathrm{\prime }}(c)$, $(fg{)}^{\mathrm{\prime }}(c)=f^{\mathrm{\prime }}(c)g(c)+f(c)g^{\mathrm{\prime }}(c)$, and $(f\mathrm{/}g{)}^{\mathrm{\prime }}(c)=(f^{\mathrm{\prime }}(c)g(c)-f(c)g^{\mathrm{\prime }}(c))\mathrm{/}g(c{)}^2$ when $g(c)\mathrm{\ne }0$ and The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, the function $G(t):=t\log t-t$ satisfies $G^{\mathrm{\prime }}(t)=\log t+t\cdot \frac{1}{t}-1=\log t$ for every $t>0$. Therefore The second fundamental theorem: if $G$ is differentiable on $[a,b]$ with $G^{\mathrm{\prime }}=f$ and $f$ is integrable, then ${\int }_a^{b}f=G(b)-G(a)$ yields ${\int }_1^Y\log tdt=Y\log Y-Y+1$ for every $Y\ge 1$. Applying this with $Y=N$ and $Y=N+1$ in step 1.1 gives ${\sum }_{n=1}^N\log n=N\log N-N+O(\log N)\mathrm{.}$

Since $N\le x<N+1$, one has $N=x+O(1)$ and therefore $N\log N=x\log x+O(\log x)$. Substituting this into step 2.1 and using ${\sum }_{n\le x}\log n={\sum }_{n=1}^N\log n$ proves ${\sum }_{n\le x}\log n=x\log x-x+O(\log x)\mathrm{.}$

By The summatory divisor-counting function is x log x plus (2 gamma - 1)x plus O(sqrt x) and The summatory logarithm is x log x minus x plus O(log x), ${\sum }_{n\le x}\tau (n)=x\log x+(2\gamma -1)x+O(\sqrt{x}),{\sum }_{n\le x}\log n=x\log x-x+O(\log x)\mathrm{.}$

The two sums differ by $2\gamma x+O(\sqrt{x})$, while the comparison sum is $x\log x+O(x)$ and is therefore eventually positive. Hence $\frac{{\sum }_{n\le x}\tau (n)}{{\sum }_{n\le x}\log n}=1+O\text{\hspace{0.17em}⁣}\left(\frac{1}{\log x}\right)\to 1.$ By Summatory functions and average orders, this is exactly the statement that $\log n$ is an average order of $\tau$.

By The divisor functions arise by Dirichlet convolution, $\sigma (n)={\sum }_{d\mid n}d$. Summing over $n\le x$ and writing each such $n$ as $dm$ gives ${\sum }_{n\le x}\sigma (n)={\sum }_{m=1}^M{\sum }_{d=1}^{y_m}d\mathrm{.}$

For each $m$, ${\sum }_{d=1}^{y_m}d=\frac{y_m(y_m+1)}{2}=\frac{y_m^2}{2}+O(y_m)\mathrm{.}$ Therefore ${\sum }_{n\le x}\sigma (n)=\frac{1}{2}{\sum }_{m=1}^M{y}_m^2+O\text{\hspace{0.17em}⁣}\left({\sum }_{m=1}^M{y}_m\right)\mathrm{.}$

Since $y_m=x\mathrm{/}m+O(1)$ uniformly in $m$, one has $y_m^2=x^2\mathrm{/}{m}^2+O(x\mathrm{/}m)+O(1)$. Summing and using The Basel sum is pi squared over six by a residue computation together with The harmonic sum is log x plus gamma plus O(1/x) gives ${\sum }_{m=1}^M{y}_m^2=\frac{{\pi }^2}{6}{x}^2+O(x\log x),{\sum }_{m=1}^M{y}_m=O(x\log x)\mathrm{.}$

Substituting step 3.1 into step 2.1 yields ${\sum }_{n\le x}\sigma (n)=\frac{{\pi }^2}{12}{x}^2+O(x\log x)\mathrm{.}$

The comparison sum is exact: ${\sum }_{n\le x}\frac{{\pi }^2}{6}n=\frac{{\pi }^2}{6}{\sum }_{n=1}^{N}n=\frac{{\pi }^2}{12}N(N+1)=\frac{{\pi }^2}{12}{x}^2+O(x)\mathrm{.}$

By The summatory divisor-sum function is pi squared over 12 times x squared plus O(x log x), ${\sum }_{n\le x}\sigma (n)={\pi }^2{x}^2\mathrm{/}12+O(x\log x)$. Comparing this with step 1.1 shows that the ratio of the two summatory functions tends to $1$, and the comparison sum is eventually positive. Therefore Summatory functions and average orders makes $({\pi }^2\mathrm{/}6)n$ an average order of $\sigma$.

By For every positive integer $n$, ${\sum }_{d\mid n,d>0}\phi (d)=n$, one has ${\sum }_{d\mid n}\phi (d)=n={\mathrm{id}}_1(n)$, where ${\mathrm{id}}_1$ is from The power functions ${\mathrm{id}}_k$ and the divisor-power-sum functions ${\sigma }_k$. Applying Classical Möbius inversion over positive divisors gives $\phi (n)={\sum }_{d\mid n}\mu (d)\frac{n}{d}\mathrm{.}$ The same inversion applied to the identity ${\sum }_{d\mid n}\epsilon (d)=1$, with $\epsilon$ from The Dirichlet-convolution identity and the constant-one function, yields ${\sum }_{d\mid n}\mu (d)=\epsilon (n)=\{\begin{array}{ll}1,& n=1,\\ 0,& n>1.\end{array}$

Summing the divisor formula from step 1.1 over $n\le x$ and writing $n=dm$ gives ${\sum }_{n\le x}\phi (n)={\sum }_{d\le x}\mu (d){\sum }_{m\le x\mathrm{/}d}m\mathrm{.}$ Also, multiplying the second identity of step 1.1 by $1\mathrm{/}{n}^2$ and summing over $n\le x$ yields the finite identity $1={\sum }_{d\le x}\frac{\mu (d)}{d^2}{\sum }_{m\le x\mathrm{/}d}\frac{1}{m^2}\mathrm{.}$

For a positive integer $Y$, let $S(Y):={\sum }_{m\le Y}1\mathrm{/}{m}^2$. For every $m\ge Y+1$ one has $\frac{1}{m^2}\le \frac{1}{m(m-1)}=\frac{1}{m-1}-\frac{1}{m},$ so ${\sum }_{m>Y}\frac{1}{m^2}\le {\sum }_{m>Y}(\frac{1}{m-1}-\frac{1}{m})=\frac{1}{Y}\mathrm{.}$ Since The Basel sum is pi squared over six by a residue computation gives ${\sum }_{m=1}^{\mathrm{\infty }}1\mathrm{/}{m}^2={\pi }^2\mathrm{/}6$, it follows that $S(Y)={\pi }^2\mathrm{/}6+O(1\mathrm{/}Y)$. Apply this in the second formula of step 2.1 with $Y=y_d$. Because $1\mathrm{/}{y}_d\le 2d\mathrm{/}x$ for every $d\le x$, one gets ${\sum }_{d\le x}\frac{1}{d^2{y}_d}=O\text{\hspace{0.17em}⁣}\left(\frac{1}{x}{\sum }_{d\le x}\frac{1}{d}\right)\mathrm{.}$ Together with $\mathrm{\mid }\mu (d)\mathrm{\mid }\le 1$ from The number-theoretic Möbius function $\mu (n)$ from prime factorisation and The harmonic sum is log x plus gamma plus O(1/x), this yields ${\sum }_{d\le x}\frac{\mu (d)}{d^2}=\frac{6}{{\pi }^2}+O\text{\hspace{0.17em}⁣}\left(\frac{\log x}{x}\right)\mathrm{.}$

For each $d\le x$, ${\sum }_{m\le x\mathrm{/}d}m=\frac{y_d(y_d+1)}{2}=\frac{y_d^2}{2}+O(y_d),y_d=\frac{x}{d}+O(1)\mathrm{.}$ Therefore step 2.1 becomes ${\sum }_{n\le x}\phi (n)=\frac{x^2}{2}{\sum }_{d\le x}\frac{\mu (d)}{d^2}+O\text{\hspace{0.17em}⁣}\left(x{\sum }_{d\le x}\frac{1}{d}\right)\mathrm{.}$ Using step 3.1 and The harmonic sum is log x plus gamma plus O(1/x) now yields ${\sum }_{n\le x}\phi (n)=\frac{3}{{\pi }^2}{x}^2+O(x\log x)\mathrm{.}$

The comparison sum satisfies ${\sum }_{n\le x}\frac{6n}{{\pi }^2}=\frac{6}{{\pi }^2}{\sum }_{n=1}^{N}n=\frac{3}{{\pi }^2}N(N+1)=\frac{3}{{\pi }^2}{x}^2+O(x)\mathrm{.}$

By The summatory totient function is 3 over pi squared times x squared plus O(x log x), ${\sum }_{n\le x}\phi (n)=3x^2\mathrm{/}{\pi }^2+O(x\log x)$. Comparing with step 1.1 shows that the two summatory functions are asymptotic, with the comparison sum eventually positive. Hence Summatory functions and average orders says that $6n\mathrm{/}{\pi }^2$ is an average order of $\phi$.

Since $a,b\le x$ is equivalent to $a,b\le N$, the count is unchanged if $x$ is replaced by $N$. For $m=1$ there is exactly one coprime pair with $\max (a,b)=1$, namely $(1,1)$. For $m\ge 2$, the coprime pairs with $\max (a,b)=m$ are exactly $(m,b)$ with $1\le b\le m$ and $\gcd (m,b)=1$, together with $(a,m)$ with $1\le a\le m$ and $\gcd (a,m)=1$; these two families are disjoint because $(m,m)$ is not coprime. Hence $C(x)=1+2{\sum }_{m=2}^N\phi (m)=2{\sum }_{m=1}^N\phi (m)-1.$

Applying The summatory totient function is 3 over pi squared times x squared plus O(x log x) at $x=N$ gives $C(x)=\frac{6}{{\pi }^2}{N}^2+O(N\log N)\mathrm{.}$ Since $N=x+O(1)$, this is $C(x)=\frac{6}{{\pi }^2}{x}^2+O(x\log x)\mathrm{.}$

By Ordered coprime pairs in a box have asymptotic density 6 over pi squared, the number of coprime pairs in $\{1,\dots ,n{\}}^2$ is $\frac{6}{{\pi }^2}{n}^2+O(n\log n)\mathrm{.}$

Dividing by the total number $n^2$ of ordered pairs gives $\frac{\mathrm{\#}\{(a,b)\in \{1,\dots ,n{\}}^2:\gcd (a,b)=1\}}{n^2}=\frac{6}{{\pi }^2}+O\text{\hspace{0.17em}⁣}\left(\frac{\log n}{n}\right),$ and the error term tends to $0$.

The ordered-sign representations of $1$ are $(\pm 1,0)$ and $(0,\pm 1)$, so $r_2(1)=4$ and therefore $f(1)=1$.

Write a positive integer $N$ as $N=2^{\alpha }{\prod }_{i=1}^r{p}_i^{e_i}{\prod }_{j=1}^s{q}_j^{b_j},$ where the $p_i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$, the $q_j\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$, and all listed primes are distinct. If some $b_j$ is odd and $N=x^2+y^2$, write $N=q_j^{2k+1}M$ with $q_j\nmid M$. Repeatedly applying A prime congruent to $3$ modulo $4$ divides both coordinates of a divisible two-square sum shows that $x=q_j^k{x}_0$ and $y=q_j^k{y}_0$, so $q_{j}M=x_0^2+y_0^2$. One more application of the same lemma forces $q_j\mid x_0$ and $q_j\mid y_0$, hence $q_j^2\mid q_{j}M$, contradiction. Therefore $r_2(N)=0$ whenever some $b_j$ is odd. If every $b_j$ is even, the cited Hackman theorem gives $\frac{r_2(N)}{4}={\prod }_{i=1}^r(e_i+1)\mathrm{.}$ Applying this to $N=2^a$, $N=p^a$, and $N=q^a$ yields $\frac{r_2(2^a)}{4}=1,\frac{r_2(p^a)}{4}=a+1,\frac{r_2(q^a)}{4}=\{\begin{array}{ll}1,& a\text{ even},\\ 0,& a\text{ odd}\mathrm{.}\end{array}$

Let $f(n):=r_2(n)\mathrm{/}4$. If $\gcd (m,n)=1$, the prime supports of $m$ and $n$ are disjoint. If step 2.1 gives $f(m)=0$ or $f(n)=0$, then some prime $q\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$ has odd exponent in one factor, hence still odd exponent in $mn$, so step 2.1 also gives $f(mn)=0=f(m)f(n)$. Otherwise every prime $q\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$ occurs to even exponent in both $m$ and $n$, so also in $mn$, and the primes $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$ occurring in $mn$ are exactly those occurring in one factor or the other, with the same exponents. Step 2.1 therefore factors the nonzero case as $f(mn)={\prod }_{p^e\parallel m,p\equiv 1(4)}(e+1){\prod }_{p^{e^{\mathrm{\prime }}}\parallel n,p\equiv 1(4)}(e^{\mathrm{\prime }}+1)=f(m)f(n)\mathrm{.}$ Together with $f(1)=1$ from step 1.1, this is exactly the multiplicativity condition of Multiplicative arithmetic functions.

Steps 1.1, 2.1, and 3.1 prove the stated prime-power values and multiplicativity.

Put $g(n):={\sum }_{d\mid n}{\chi }_4(d)$. If $\gcd (m,n^{\mathrm{\prime }})=1$, every positive divisor of $m{n}^{\mathrm{\prime }}$ is uniquely of the form $ab$ with $a\mid m$ and $b\mid n^{\mathrm{\prime }}$; because odd residue classes modulo $4$ multiply and every even divisor has ${\chi }_4$-value $0$, one gets ${\chi }_4(ab)={\chi }_4(a){\chi }_4(b)$. Therefore $g(m{n}^{\mathrm{\prime }})={\sum }_{a\mid m,b\mid n^{\mathrm{\prime }}}{\chi }_4(ab)=({\sum }_{a\mid m}{\chi }_4(a))({\sum }_{b\mid n^{\mathrm{\prime }}}{\chi }_4(b))=g(m)g(n^{\mathrm{\prime }}),$ so $g$ is multiplicative.

The prime-power values of $g$ are immediate from the definition: $g(2^a)=1$ because only the divisor $1$ contributes; if $p\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}4)$, then every divisor $p^j$ is $1$ modulo $4$, so $g(p^a)=a+1$; and if $q\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$, then the divisor residues alternate, so $g(q^a)=1-1+1-\cdots =\{\begin{array}{ll}1,& a\text{ even},\\ 0,& a\text{ odd}\mathrm{.}\end{array}$

By The normalized two-square count is multiplicative with the expected prime-power values, the function $r_2\mathrm{/}4$ is multiplicative with exactly the same prime-power values as in step 2.1. Hence Multiplicative functions are determined by their prime-power values gives $\frac{r_2(n)}{4}=g(n)={\sum }_{d\mid n}{\chi }_4(d)\mathrm{.}$

Among the positive divisors of $n$, the even ones contribute $0$, the divisors congruent to $1$ modulo $4$ contribute $+1$, and the divisors congruent to $3$ modulo $4$ contribute $-1$. Thus ${\sum }_{d\mid n}{\chi }_4(d)=d_1(n)-d_3(n)$, and step 3.1 gives the claimed formula for $r_2(n)$.

By The divisor formula for the two-square representation count, $r_2=4(\mathbf{1}\ast {\chi }_4)$. Applying Dirichlet's hyperbola method for summatory convolutions with $f=\mathbf{1}$, $g={\chi }_4$, and $U=V=\sqrt{x}$ gives ${\sum }_{n\le x}{r}_2(n)=4({\sum }_{a\le N}G(x\mathrm{/}a)+{\sum }_{b\le N}{\chi }_4(b)\lfloor \frac{x}{b}\rfloor -NG(N))\mathrm{.}$

The values of ${\chi }_4$ repeat as $1,0,-1,0$, so every complete block of length $4$ has sum $0$ and every initial partial block has sum $0$ or $1$. Hence $G(y)=O(1)$ uniformly in $y$, and step 1.1 gives ${\sum }_{a\le N}G(x\mathrm{/}a)=O(N),NG(N)=O(N)\mathrm{.}$ Also $\lfloor x\mathrm{/}b\rfloor =x\mathrm{/}b+O(1)$, so ${\sum }_{b\le N}{\chi }_4(b)\lfloor \frac{x}{b}\rfloor =x{\sum }_{b\le N}\frac{{\chi }_4(b)}{b}+O(N)\mathrm{.}$

Deleting the zero even terms identifies ${\sum }_{b\le N}{\chi }_4(b)\mathrm{/}b$ with a partial Gregory-Leibniz sum. Therefore The Gregory-Leibniz series: pi over four equals 1-1/3+1/5-1/7+... gives ${\sum }_{b\le N}\frac{{\chi }_4(b)}{b}=\frac{\pi }{4}+O(1\mathrm{/}N)\mathrm{.}$

Substituting step 3.1 into step 2.1 and then into step 1.1 yields ${\sum }_{n\le x}{r}_2(n)=4(x\cdot \frac{\pi }{4}+O(N))=\pi x+O(\sqrt{x})\mathrm{.}$ Since ${\sum }_{n\le x}\pi =\pi \lfloor x\rfloor =\pi x+O(1)$, Summatory functions and average orders now says that the constant function $\pi$ is an average order of $r_2$.