# Is the sum always bigger than $n^2$?

Let $s(n)$ an arithmetical function defined as $$s(n)=(p_1+1)^{e_1} (p_2+1)^{e_2} \cdots (p_m+1)^{e_m}$$ where prime factorization of $n$ is $n=p_1^ {e_1} p_2 ^{e_2} \cdots p_m^{e_m}$.
(For example, $s(49)=s(7^2)=8^2=64$, $s(60)=s(2^2 \times 3^1 \times 5^1)=3^2 \times 4^1 \times 6^1=216$)

Prove or disprove the following proposition;

$\phantom{a}\bullet$ There exists a positive integer $M$ such that $$\forall N>M(N\in\mathbb{N})\phantom{;}; \phantom{;}\sum_{n= 1}^{N}s(n)>N^2$$

-
I might be able to get a nice estimate on the summatory function for you, if you can give me some other way of representing your function, as it stands, I can give you a good estimate for $$\sum_{n=1}^N \ln(s(n))=\sum_{p\leq n}\ln(p+1)([\frac{n}{p}]+[\frac{n}{p^2}]+[\frac{n}{p^2}]...)\sim n\ln(n)$$ in addition if n is square free then we have the relation, $$s(n)=\sigma(n)$$ where $\sigma(n)$ is the divisor function. –  Ethan Jan 27 '13 at 4:27
It may be helpful to realize that $s(n)$ is the sum of the divisors of $n$ counted according to their multiplicities. E.g., the divisors of $60$, so counted, are $$1,2,2,3,4,5,6,6,10,10,12,15,20,30,30,60\;,$$ whose sum is $216$. –  Brian M. Scott Jan 27 '13 at 4:41
I get $\sum_{k\le n} s(k) \approx 1.337 n^2$, if I didn't flub my singular series constant. Experimentally, for $n=10000$ the sum is $1.3108 n^2$. –  Erick Wong Jan 27 '13 at 5:28

This is true. If $\nu_p(n)$ is maximal such that $p^{\nu_p(n)}\mid n$, then $$s(n)\ge (\frac32)^{\nu_2(n)} (\frac43)^{\nu_3(n)}n.$$ Therefore, for all $i=1$, $\dots$, $2^5 3^3$, $$s(2^5 3^3n+i)\ge (\frac32)^{\min(\nu_2(i),5)} (\frac43)^{\min(\nu_3(i),3)} (2^5 3^3 n+i).$$ Summing over $i=1$, $\dots$, $2^5 3^3$ gives \begin{eqnarray*} \sum_{1\le i\le 2^5 3^3} s(2^5 3^3n+i)&\ge&1555910n+ 785732\\ &\ge& 2.08 \sum_{1\le i\le 2^5 3^3}( 2^5 3^3n + i). \end{eqnarray*} This proves that $$\sum_{1\le n\le N} s(n)\ge 2.08 \frac{N(N+1)}{2}>N^2$$ whenever $N$ is a multiple of $2^5 3^3=864$. If $N$ is not a multiple of $864$, write $N=N'+N''$, where $N'$ is a multiple of $864$ and $1\le N''\le 863$. Then, since $s(n)\ge n$ for all $n$, $$\sum_{1\le n\le N} s(n)\ge 2.08 \frac{N'(N'+1)}{2} + N' N'' + \frac{N''(N''+1)}{2}$$ which will be bigger than $$N^2 = N'^2 + 2 N' N'' + N''^2$$ whenever $N'\ge 22464$. Also, computation shows that $$\sum_{1\le n\le N} s(n)> N^2$$ whenever $24\le N\le 22463$. So, we can take $M=23$.
Asymptotically, $s(n)/n$ should behave similarly to the random variable $$W:=\prod_p (1+\frac{1}{p})^{Z_p-1},$$ where the $Z_p$'s are independent geometrically distributed random variables with success probability $1-\frac{1}{p}$, and $${\Bbb E}(W) = \prod_p \frac{p(p-1)}{p^2-p-1} \approx 2.67411.$$