# Prove that $\sigma(n^2)=\sum_{d\mid n} 2^{\omega(d)}$

Let $\omega(n)$ denote the number of distinct prime divisors of $n>1$, with $\omega(1)=0$.

(a) Show that $2^{\omega(n)}$ is a multiplicative function.

(b) Prove that $$\sigma(n^2)=\sum_{d\mid n} 2^{\omega(d)}.$$

I have done the part (a) and I am stuck by (b).

First, I set $d=p_1^{e_1}\cdots p_k^{e_{k}}$ be a factor of $n$. Then I don't know what's the next step.

• it is enough to show that $\sigma(p^{2k}) = \sum_{d | p^k} 2^{w(d)}$ and that $f(n) = \sigma(n^2)$ is multiplicative – reuns Mar 28 '16 at 17:00
• (because if $g(n)$ is multiplicative, then $h(n) = \sum_{d | n} g(d)$ is multiplicative, and to prove that two multiplicative functions $f(n) ,g(n)$ are equal, it is enough to show that $f(p^k) = g(p^k)$ for every prime power $p^k$) – reuns Mar 28 '16 at 17:04
• Is this even true? With $n$ a prime number $p$ we get $$\sigma(n^2) = 1+p+p^2$$ and $$\sum_{d|n} 2^{\omega(d)} = 1 + 2 + 2 = 5,$$ a constant. – Marko Riedel Mar 28 '16 at 22:24

Suppose we seek to show that $$\tau(n^2) = \sum_{d|n} 2^{\omega(d)}.$$

This can be done using Dirichlet series and Euler products. We have for the RHS and $$\sum_{n\ge 1} \frac{1}{n^s} 2^{\omega(n)}$$ the Euler product $$\prod_p \left(1 + \frac{2}{p^s} + \frac{2}{p^{2s}} + \frac{2}{p^{3s}} +\cdots\right).$$ which is $$\prod_p \left(-1 + 2\frac{1}{1-1/p^s}\right) = \prod_p \frac{-1+1/p^s+2}{1-1/p^s} \\ = \prod_p \frac{1+1/p^s}{1-1/p^s} = \prod_p \frac{1-1/p^{2s}}{(1-1/p^s)^2} = \frac{\zeta(s)^2}{\zeta(2s)}.$$

Therefore $$\sum_{n\ge 1} \frac{1}{n^s} \sum_{d|n} 2^{\omega(d)} = \frac{\zeta(s)^3}{\zeta(2s)}.$$

On the other hand we have $$\sum_{n\ge 1} \frac{1}{n^s} \tau(n^2) \\= \prod_p \left(1 + (2+1) \frac{1}{p^s} + (4+1) \frac{1}{p^{2s}} + (6+1) \frac{1}{p^{3s}} + (8+1) \frac{1}{p^{4s}} + \cdots\right).$$

This is $$\prod_p \left(1+\frac{1/p^s}{1-1/p^s} + \sum_{k\ge 1} \frac{2k}{p^{ks}} \right) \\ = \prod_p \left(1+\frac{1/p^s}{1-1/p^s} + 2 \frac{1/p^s}{(1-1/p^s)^2} \right).$$

To aid in simplification we put $z=1/p^s$ to get for the inner term

$$1 + \frac{z}{1-z} + \frac{2z}{(1-z)^2}$$

This simplifies to $$\frac{1+z}{(1-z)^2}.$$

On the other hand $$\frac{\zeta(s)^3}{\zeta(2s)} = \prod_p \frac{1-z^2}{(1-z)^3} = \prod_p \frac{1+z}{(1-z)^2}.$$

We have equality, QED.

A Combinatorial Proof (Sketch)

I assume that, by $\sigma$, you mean $\sigma_0=\tau$, the divisor-counting function. Let $$S(n):=\Big\{(t,d)\in\mathbb{N}\times\mathbb{N}\,\Big|\,t\mid n^2,\,d\mid n,\text{ and }d\text{ is smallest such that }n^2\mid td^2\Big\}\,.$$ First, verify that, for each $t\in\mathbb{N}$ such that $t\mid n^2$, there exists a unique $d\in\mathbb{N}$ such that $(t,d)\in S(n)$. This proves that $\big|S(n)\big|=\sigma_0\left(n^2\right)$.

Next, justify that, for each $d\in\mathbb{N}$ such that $d\mid n$, there are precisely $2^{\omega(d)}$ values of $t\in\mathbb{N}$ such that $(t,d)\in S(n)$. This shows that $\big|S(n)\big|=\sum\limits_{d\mid n}\,2^{\omega(d)}$. Therefore, $\sigma_0\left(n^2\right)=\sum\limits_{d\mid n}\,2^{\omega(d)}$.

In fact, one can show also that $$\sigma_0\left(n^k\right)=\sum\limits_{d\mid n}\,k^{\omega(d)}$$ for all $k\in\mathbb{N}_0$ (where $0^0:=1$). One needs to only count the number of the elements of the set $$S(n,k):=\Big\{(t,d)\in\mathbb{N}\times\mathbb{N}\,\Big|\,t\mid n^k,\,d\mid n,\text{ and }d\text{ is smallest such that }n^k\mid td^k\Big\}\,.$$

The hidden portion below is a remark, almost completely unrelated to the question.

Maybe, we can use this result to extend $\sigma_0$ onto $\mathbb{Q}_{>0}$, by defining $\sigma_0\left(\frac{1}{n}\right):=\sum\limits_{d\mid n}\,(-1)^{\omega(d)}$ and $\sigma_0\left(\frac{u}{v}\right):=\sigma_0(u)\,\sigma_0\left(\frac{1}{v}\right)$ if $\gcd(u,v)=1$. For example, if $p$ is a prime natural number and $j\in\mathbb{N}_0$, then $\sigma_0\left(\frac{1}{p^j}\right)=1-j$. This result is consistent with a more natural definition $\sigma_0\left(\prod\limits_{i=1}^\ell\,p_i^{\alpha_i}\right):=\prod\limits_{i=1}^\ell\,\left(1+\alpha_i\right)$ if $p_1,\ldots,p_\ell$ are pairwise distinct prime natural numbers and $\alpha_1,\ldots,\alpha_\ell\in\mathbb{Z}$.
We also have the identity $$\sigma_0\left(n^k\right)=\sum\limits_{d\mid n}\,k^{\omega(d)}$$ for all $n\in\mathbb{N}$ and $k\in\mathbb{Z}$. This identity can be yet again extended in the form $$\sigma_0\left(r^k\right)=\sum\limits_{q\mid r}\,s(q)\,k^{\omega(q)}$$ for all $r\in\mathbb{Q}_{>0}$ and $k\in\mathbb{Z}$ as follows. For $q,r\in\mathbb{Q}_{>0}$, we say that $q\mid r$ if $q=\frac{u}{v}$ and $r=\frac{x}{y}$, with $u,v,x,y\in\mathbb{N}$, $\gcd(u,v)=1$, and $\gcd(x,y)=1$, satisfy $u\mid x$ and $v\mid y$. For $q\in\mathbb{Q}_{>0}$, $\omega(q):=\omega(u)+\omega(v)$ and $s(q):=(-1)^{\omega(v)}$ if $q=\frac{u}{v}$ with $u,v\in\mathbb{N}$ and $\gcd(u,v)=1$.
Indeed, if $\sigma_z(n):=\sum\limits_{d\mid n}\,n^z=\prod\limits_{i=1}^\ell\,\left(\frac{p_i^{z\left(1+\alpha_i\right)}-1}{p_i^z-1}\right)$, where $z\in\mathbb{C}\setminus\{0\}$ and $n=\prod\limits_{i=1}^\ell\,p_i^{\alpha_i}$ with distinct primes $p_1,\ldots,p_\ell$ and positive integers $\alpha_1,\ldots,\alpha_\ell$, then we obtain a similar identity $$\sigma_z\left(n^k\right)=\sum\limits_{d\mid n}\,\left(\frac{n}{d}\right)^{kz}\,\varpi_z^k(d)\,,$$ where $\varpi_z^k(n):=\prod\limits_{\substack{{p\mid n}\\p\text{ is prime}}}\,\left(\frac{p^{kz}-1}{p^z-1}\right)$ for $z\neq 0$ and $\varpi_0^k(n):=k^{\omega(n)}$. We extend $\sigma_z$ onto $\mathbb{Q}_{>0}$ similarly. Furthermore, if $q=\frac{u}{v}$ where $u,v\in\mathbb{N}$ with $\gcd(u,v)=1$, then we define $\varpi^k_z(q):=\varpi^k_z(u)\,\varpi^k_z(v)$ and $s_z(q):=\prod\limits_{\substack{{p\mid v}\\{p\text{ is prime}}}}\,\left(\frac{-1}{p^z}\right)=\frac{s(q)}{\big(\text{rad}(v)\big)^z}$. Finally, we get the identity $$\sigma_z\left(r^k\right)=\sum\limits_{q\mid r}\,s_z(q)\,\left(\frac{r}{q}\right)^{kz}\,\varpi^k_z(q)$$ for all rational numbers $r>0$, for every integer $k$, and for every complex number $z\neq 0$.