# Upper and Lower bounds of Sum of Sum-of-Divisors

I want to know an upper bound of this function: $$\sum_{n\le x}\sigma(n)$$ where $$\sigma(x)$$ is the sum of divisors.

Are there any known upper and lower bounds?

• I'm guessing it's an asymptotic, meaning the ratio between them converges to $1$ as $x\to\infty$. That means it may very well be neither an upper or lower bound, even eventually - sometimes estimates can oscillate above and below the true value infinitely often. (I have no idea if that's the case here, it could actually be a bound too.) – runway44 Jun 27 at 2:30
• @runway44 Ok. Thank you. – Quote Dave Jun 27 at 2:31

This sum actually has a surprisingly nice upper and lower bound. It turns out

$$\frac{x(x+1)}{2} \le \sum_{n\le x}\sigma(n) \le x^2$$

You can verify this for yourself with a python script such as this one

Now let's discuss how I arrived at these bounds:

We can reframe this problem to make it a little simpler to think about. Instead of adding up $$\sigma(i)$$ for every $$i$$ from $$1$$ to $$x$$, we can instead try to find out how many times each factor(from $$1$$ to $$x$$) is counted, and use this to find our answer.

For example in the case of $$x=9$$ we know:

$$1$$ will be counted $$9$$ times (at $$1,2,3,4,5,6,7,8,9$$)

$$2$$ will be counted $$4$$ times (at $$2,4,6,8$$)

$$3$$ will be counted $$3$$ times (at $$3,6,9$$)

$$4$$ will be counted $$2$$ times (at $$4,8$$)

...

In general each factor $$k$$ is counted $$\lfloor \frac{x}{k} \rfloor$$ times.

This means we can rewrite our sum as

$$\sum_{k=1}^x k \cdot \lfloor \frac{x}{k} \rfloor$$

We can set $$\lfloor \frac{x}{k} \rfloor=1$$ to get our lower bound of $$\frac{x(x+1)}{2}$$

And we can set $$\lfloor \frac{x}{k} \rfloor= \frac{x}{k}$$ to get our upper bound of $$x^2$$

• Wow, thank you! – Quote Dave Jul 1 at 2:33
• No problem the question was pretty fun to figure out. – Anirudh Jul 1 at 3:20
• However $x^2$ is not the tightest bound. – Quote Dave Jul 5 at 16:44
• Is there a better one? – Anirudh Jul 5 at 19:21