Density of outputs of divisor function

Question

We define the function: $$\sigma_k{(n)}=\sum_{d \mid n} d^k$$ as the sum of divisors function of the $k$th power, where $k \in \mathbb{N_0}$, for $n \in \mathbb{N}$. Now, we define: $$S_k=\{a \space | \space \exists \space m \in \mathbb{N} \space ; \sigma_k{(m)}=a\}$$ It is clear that $S_0$ is the same as $\mathbb{N}$ since for any $n \in \mathbb{N}$, we have $\sigma_0{(2^{n-1})}=n$. However, it is clear than this is not true for $S_k$ where $k>0$.

What is the density of $S_k$ in $\mathbb{N}$ for $k \in \mathbb{N}$?

Edit: As pointed out by @ThomasAndrews in the comments below, $k>1$ has zero density by bounding. Now, the problem is solved if anybody is able to find the density of the sum of divisors function $\sigma(x)$ ($1$st power).

Answer 1

Below shows that $\sigma_k(n) > n^k$ for $n>1$ and $k>0$. $\sigma_1(n) = \sum_{d|n}d = \sigma(n)$ is the very well known divisor function. Basic properties of $\sigma_k(n)$ and fundamental theorem of arithmetic will lead us to the result.

$\textbf{Property 1:}$ If $p$ is a prime number and $q \in \mathbb{N}$, then

$\sigma_k(p^q) = 1+p^k+p^{2k}+...+p^{qk}$

Proof of above property is straight forward as any integer of the form $p^i$ for $i \in \mathbb{N}$ and $i \leq q $ will divide $p^q$ with a quotient of $p^{q-i}$

$\textbf{Property 2:}$ If $gcd(a,b)=1$ then $\sigma_k(ab) = \sigma_k(a)\sigma_k(b)$

Proof: Let $d_a,d_b$ be such that $d_a|a$ and $d_b|b$. As $gcd(a,b) =1$ we also have $gcd(d_a,d_b) =1$ and thus there's a bijection between the sets $(d_a,d_b)\rightarrow d_ad_b$. Denote $d_{ab} = d_ad_b$ and we also have $d_{ab}|ab$.

Now $$\sigma_k(a)\sigma_k(b) = (\sum_{d_a | a} d_a^k)(\sum_{d_b | b} d_b^k) = \sum_{d_a | a, \ d' | b} (d_ad_b)^k = \sum_{d_{ab} | ab} d_{ab}^k=\sigma_k(ab)$$

Look at a different approach for $k=1$ here: The sigma function (sum of divisors ) multiplicative proof

Let me know in the comments if the bijection is not obvious, I write some more on that if needed.

Now using the fundamental theorem of arithmetic, for any $n\in \mathbb{N}$, there exists $p_1,p_2,...,p_q,a_1,a_2,...,a_q$ where $p_1,p_2,...,p_q$ are prime numbers and $a_1,a_2,...,a_q$ are positive integers such that,

$$n = p_1^{a_1}p_2^{a_2}...p_q^{a_q}$$

Then, $\sigma_k(n) = \sigma_k(p_1^{a_1}p_2^{a_2}...p_q^{a_q}) = \sigma_k(p_1^{a_1})\sigma_k(p_2^{a_2})...\sigma_k(p_q^{a_q})$

$=(1+p_1^k+p_1^{2k}+...+p_1^{a_1k})(1+p_2^k+p_2^{2k}+...+p_2^{a_2k})...(1+p_q^k+p_q^{2k}+...+p_q^{qk}) > p_1^{a_1k}p_2^{a_2k}...p_q^{a_qk}$

$= (p_1^{a_1}p_2^{a_2}...p_q^{a_q})^k = n^k$

Note that the inequality holds true only if $k \neq 0$ and $n \neq 1$.

Thus the Natural Density (https://en.wikipedia.org/wiki/Natural_density) of $\sigma_k(n)$ is $0$ for $k>0$

Answer 2

The point is that $\sigma(n)$, as $n$ ranges, is usually very even (i.e. many powers of $2$ divide it).

Fix $M \ge 1$ large. Since $\sigma(n) \ge n$ for each $n$, $$\#\{1 \le m \le M : m = \sigma(n) \text{ for some } n\} \le \#\{\sigma(n) : 1 \le n \le M\} \cap [M].$$ Up to a set of density 0, every positive integer $n$ has at least $\frac{1}{2}\log\log n$ prime divisors. Therefore, we expect there to be at least $\frac{1}{4}\log\log n$ prime divisors of $n$ with highest exponent dividing $n$ being odd. The point is that for such prime divisors, since $\sigma$ is multiplicative, they contribute a power of $2$ to $\sigma(n)$, so we expect $\frac{1}{2}\log\log n$ powers of $2$ dividing $\sigma(n)$, so $$\#\{\sigma(n) : 1 \le n \le M\} \cap [M] \le \#\{m \le M : 2^{\frac{1}{4}\log\log M} \mid m\}$$ has density $0$. I don't think it should be hard to make this more rigorous, but I'm watching the finals.

Answer 3

The following answer is incorrect. The OP asked for the density of $S_1$, which is unambiguous. The following answer shows it's not the case that $\frac{1}{N}\sum_{n \le N} w(n)$ goes to $0$ as $N \to \infty$, where $w(n) := \#\{m \ge 1 : \sigma(m) = n\}$.

---

The density of $\{ \sigma_1(n), n \ge 1\}$ can't be zero because $$F(s)=\sum_{n=1}^\infty \frac{n}{\sigma_1(n)} n^{-s} =\prod_p(1+\sum_{k=1}^\infty \frac{p^k}{\sigma_1(p^k)}p^{-sk})= \prod_p (1+\frac{1}{1+p^{-1}}p^{-s}+O(p^{-2s}))\\= \exp(\sum_p p^{-s} + O(p^{-2s})+O(p^{-s-1}))$$ has a pole at $s=1$, if the density of $\{ \sigma_1(n), n \ge 1\}$ was $0$ since $\frac{n}{\sigma_1(n)} \in [0,1]$ we would have $$f(x)=\sum_{n \le x} \frac{n}{\sigma_1(n)}= o(x)$$ with $g(y) = \sup_{x > y} \frac{f(x)}{x}$ we'd have $\lim_{y \to \infty}g(y)=0$ and $$F(s) = s \int_1^\infty f(x)x^{-s-1}dx=O(s \int_1^y x x^{-\Re(s)-1}dx)+ O(s\int_y^\infty g(y)x x^{-\Re(s)-1}dx) \\ = O(|s| y) + O(\frac{|s|\, g(y)}{\Re(s)-1}) $$ wouldn't have a pole at $s=1$, since $g(y)$ can be taken arbitrary small.

---

That $\lim_{y \to \infty} g(y)$ converges to $Res(F(s),s=1)$ and that it is the density is a matter of the same Tauberian theorems as in the proof of the PNT (maybe applying the argument above as well as the tauberian theorems to $\sum_{n=1}^\infty \sigma_1(n)^{-s} = \prod_p (1+\sum_{k=1}^\infty (p+1)^{-s} + O(p^{-2s})$ is a better idea)

Answer 4

This result can be found in the paper R. Sita Rama Chandra Rao and G. Sri Rama Chandra Murty: On a Theorem of Niven, Canad. Math. Bull. 22 (1979), no. 1, 113–115. DOI: 10.4153/CMB-1979-018-5, Zbl: 0401.10069, MR532280

The paper relies on some results from the paper Ivan Niven: The asymptotic density of sequences. Bull. Amer. Math. Soc., 57(6):420-434, 1951; Zbl: 0044.03603, MR0044561.

---

The proof $k=1$ is short enough to be reproduced here.

We want to show that the set $$C=\{\sigma(n); n\in\mathbb N\}$$ has zero density.

We will denote \begin{align*} d(A)&=\lim_{n\to\infty} \frac{A(n)}n\\ \overline d(A)&=\limsup_{n\to\infty} \frac{A(n)}n\\ \end{align*} for $A\subseteq \mathbb N$, where $A(n)=|\{k\in A; k\le n\}|$ denotes the number of the element os $A$ which are less than or equal to $n$. I.e, $d(A)$ denotes the asymptotic density and $\overline d(A)$ denotes the upper asymptotic density. (You can notice that $d(A)$ is defined only for some sets, while $\overline d(A)$ exists for each set. However, if $\overline d(A)=0$, then we get also $d(A)=0$. It is also useful to notice that $\overline d(A\cup B)\le \overline d(A)+\overline d(B)$.)

Let us fix an integer $k$. We divide the set $C$ into \begin{align*} C_1&=\{s\in C; 2^k\mid C\}\\ C_2&=\{s\in C; 2^k\nmid C\} \end{align*} It is clear that $\overline d(C_1)\le\frac1{2^k}$.

If $s\in C_2$, then $s=\sigma(t)$ for some $t$ which has at most $k$ prime factors with exponent one.¹ Moreover, we have $t\le s$.

Let $D$ be the of all positive integers which have at most $k$ primes factors with exponent one. We see that $C_2(n)\le D(n)$, since if $s\in C_2$ and $s\le n$, then for the corresponding $t\in D$ we also have $t\le n$.

Since $d(D)=0$ (Niven, Corollary 2), we get $$d(C_2)=\lim_{n\to\infty} \frac{C_2(n)}n \le \lim_{n\to\infty} \frac{D(n)}n=0.$$ Consequently, we have $$\overline d(C)\le \overline d(C_1)+\overline d(C_2) = \frac1{2^k}.$$

Since the inequality $\overline d(C)\le\frac1{2^k}$ is true for every $k$, we get $\overline d(C)=0$ and, consequently, $d(C)=0$.

¹Recall that if $n=p_1^{a_1}p_2^{a_2}\dots p_t^{a_t}$, then $\sigma(n)=\prod\limits_{i=1}^t\sigma(p_i^{a_i})$. If $a_i=1$ and $p_i$ is odd, then $\sigma(p_i^{a_i})=p_i+1$ is even. So if $n$ contains at least $k+1$ prime factors in first power, then at least $k$ of them is odd and we get $2^k\mid \sigma(n)$.