constant function under convolution with 3 *

Question

$p$ is prime

Can someone show the intermediate steps, I don't understand the $1$st step even with the definition of a convolution in front of me. Thank you :)

Answer 1

I knew the straight formula $\underbrace{(1*1*...*1)}_{i}(p^k)=\binom{k+i-1}{k}$ but not the intermediates. $(1*1)(p^i)=\sigma_0(p^i)=(i+1)$ and $1(p^{k-i})$ is just $1$.

The first step is just the sum over divisors expressed another way: $(1*1*1)(p^k)=\sum\limits_{d\mid p^k}(1*1)(d)\cdot (1)(\frac{p^k}{d})$ where divisors of $p^k$ are the $p^i$

Answer 2

We obtain \begin{align*} \color{blue}{(\mathbf{1}\star\mathbf{1}\star\mathbf{1})\left(p^k\right)} &=\sum_{d|p^k}\left(\mathbf{1}\star\mathbf{1}\right)(d)(\mathbf{1})\left(\frac{p^k}{d}\right)\tag{1}\\ &=\sum_{d|p^k}\left(\mathbf{1}\star\mathbf{1}\right)(d)\tag{2}\\ &=\sum_{j=0}^k(\mathbf{1}\star \mathbf{1})\left(p^j\right)\tag{3}\\ &=\sum_{j=0}^k\sum_{d|p^j}\left(\mathbf{1}\right)(d)\left(\mathbf{1}\right)\left(\frac{p^j}{d}\right)\tag{4}\\ &=\sum_{j=0}^k\sum_{i=0}^j\left(\mathbf{1}\right)\left(p^i\right)\left(\mathbf{1}\right)\left({p^{j-i}}\right)\tag{5}\\ &=\sum_{j=0}^k\sum_{i=0}^j1\tag{6}\\ &=\sum_{j=0}^k(j+1)\\ &=\sum_{j=1}^{k+1}j\\ &\,\,\color{blue}{=\frac{1}{2}(k+1)(k+2)} \end{align*} and the claim follows.

Comment:

• In (1) and (4) we do the convolution according to the definition $(f\star g)(n)=\sum_{d|n}f(d)g\left(\frac{n}{d}\right)$.

• In (2) and (6) we apply the definition of the unit function $\mathbf{1}(n)=1, n\geq 1$.

• In (3) and (5) we note the positive divisors $d$ of $p^r$, $p$ prime are $p^j,0\leq j\leq r$.