2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – runway44 Jun 27 at 2:30
  • $\begingroup$ @runway44 Ok. Thank you. $\endgroup$ – Quote Dave Jun 27 at 2:31
2
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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