Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$$ \sum_{k=1}^n\sigma(k)=\frac{\pi^2}{12}n^2+O(n\log n). $$

Is the next asymptotic term known? That is, is there a monotonic increasing function $f(x)$ such that $$ \sum_{k=1}^n\sigma(k)=\frac{\pi^2}{12}n^2+f(n)+o(f(n)) $$ ? (I would guess something like $f(x)=cx$ if $f$ exists.) Alternately, are there monotonic increasing functions $f(x),g(x)$ with $$ \sum_{k=1}^n\sigma(k)=\frac{\pi^2}{12}n^2+f(n)+\Omega_\pm(g(n)) $$ ?

Apologies for what may be a basic reference question; I've misplaced by copy of Hardy & Wright and lack more advanced references like Apostol.

share|cite|improve this question
What you give is Theorem 324 on page 266 of H+W. They finally prove Gronwall's Theorem in section 22.9, pages 353-354, which is a lim sup result, precursor to Robin's proof that a certain condition on the maximum size of $\sigma(n)$ is equivalent to RH. But they do not seem to typically give more than a principal term and a single error estimate. – Will Jagy May 17 '12 at 2:32
@WillJagy: Thanks for looking that up. I found a copy of Apostol's Introduction to Analytic Number Theory and his Theorem 2.4 is the same as Theorem 324. – Charles May 17 '12 at 17:55
I'm not sure it will help, but Bach and Shallit collect together a bunch of published estimates from a variety of sources, kind of a glossary in the middle of the book,… – Will Jagy May 18 '12 at 0:41
up vote 3 down vote accepted

In Apostol's Introduction to Analytic Number Theory he uses $\sum_{q<x}q = x^2/2+O(x)$ to prove this bound as Theorem 3.4. We may be able to do better by using the exact expression $$ \begin{align} \sum_{q<x} q &= \frac{1}{2}\left(\lfloor x \rfloor^2+\lfloor x \rfloor \right) \\ & = \frac{1}{2}\left((x-\{x\})^2+x-\{x\}\right) \\ & = \frac{x^2}{2} - x\{x\}+\frac{x}{2} + O(1) \end{align} $$ where $\{x\}$ is the fractional part of $x$.

Then proceeding in the same way $$ \begin{align} S(n) = \sum_{k\le n}\sigma(k) & = \sum_{d\le n}\sum_{q\le n/d}q \\ & = \sum_{d\le n}\left(\frac{n^2}{2d^2}+\frac{n}{2d}-\frac{n\{n/d\}}{d}+O(1)\right) \\ & = \frac{1}{2}n^2\zeta(2)+\frac{1}{2}n\log(n)-n\sum_{q\le n}\frac{\{n/d\}}{d}+O(n) \end{align} $$

Write $t(n)=n\sum\{n/d\}/d$ for the third term. Since $|\{n/d\}|<1$, $t(n)=O(n\log(n))$.

Let $S(n)=n^2\pi^2/12+F(n)$. Gronwall's Theorem gives us that there are arbitrarily large $N$ with $\sigma(N)>N\log\log(N)$. For such a $N$ we have $$ \begin{align} S(N)-S(N-1) & =\sigma(N)>N\log\log(N) \\ F(N)-F(N-1) & > N \log\log(N)-(2N-1)\pi^2/12 \\ \max(|F(N)|,|F(N-1)|) & > N\log\log(N)/2 - N \end{align} $$ So $F(n)=\Omega(n\log\log(n))$. But $F(n) = n\log(n)/2-t(n)+O(n)$.

Write $t(n)=An\log(n)-f(n)$ with $f(n)=o(n\log(n))$. Then either:

$A\neq \frac{1}{2}$ and $F(n) = \left(\frac{1}{2}-A\right)n\log(n)+o(n\log(n))$


$A = \frac{1}{2}$ and $F(n) = f(n) + O(n)$, with $f(n)=o(n\log(n))$ and $f(n)=\Omega(n\log\log(n))$

Unfortunately I can't resolve which case applies, and in fact, if it's the second then I haven't really answered the question after all.

share|cite|improve this answer
It is the second case, as it happens. – Charles May 23 '12 at 14:05
That was my guess from calculating some numbers. Do you have a clean answer to your question? I'd be curious to see it now that I have spent some time thinking about this. I was too hasty posting this; I realized I also missed the possibility that it might not be possible to write $t(n)=An\log(n)+o(n\log(n))$. – Zander May 23 '12 at 23:42
I don't have an answer for my question, no. I (now) know that the residual is between $n(log n)^{3/4}$ and $n\log\log n$ but not what the next term might be, if indeed there is a nonoscillating next term. But your answer was helpful regardless, so +1. – Charles May 24 '12 at 13:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.