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

calculussummationupper-lower-bounds

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?

Best Answer

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$

Related Solutions

Binomial Coefficients – Best Upper and Lower Bounds

For the special case $n = 2k$, we can get narrower bounds:

$$\frac{1}{2k} 2^{2k} \leq \binom{2k}{k} \leq 2^{2k}$$

The proof is given as an exercise in Robert J. Vanderbei, Linear Programming: Foundations and Extensions, ch. 4.

Upper Bounds on a Ratio Concerning the Sum of Divisors

umm. For $n \geq 16,$ we get $\log \log n > 1, $ using log base $e = 2.71828...$ Then for $n \geq 16,$ $$ \frac{\sigma(n)}{n \log \log n} $$ does have an upper bound.

From Robin we have an unconditional result (1984) that says that your ratio of interest is, for $n \geq 13,$ smaller than $$ \frac{\sigma(n)}{n \log \log n} < e^\gamma + \frac{0.64821364942...}{(\log \log n)^2},$$ with the constant in the numerator giving equality for $n=12.$ Note $\gamma \approx 0.5772156649,$ while $e^\gamma \approx 1.7810724$

In particular, for $n \geq 268,$ we get $ \frac{\sigma(n)}{n \log \log n} < 2$ Below are the ratios bigger than $1.9$ with $n \geq 3.$

  14.17718374918197           3
   5.357674360663709          4
   2.521617642462445          5
   3.429366566700587          6
   2.561127739941722          8
   2.158189420874225         10
   2.563440313761713         12
   2.041357661635523         18
   1.913982525796606         20
   2.162126621182643         24
   1.960580021444964         30
   1.980481186664786         36
   1.908540572163114         48
   1.98636974867664          60
   1.915700702020492        120

Best Answer

Related Solutions

Binomial Coefficients – Best Upper and Lower Bounds

Upper Bounds on a Ratio Concerning the Sum of Divisors

Related Question