# Dirichlet's product with number theoretic functions

How would you solve this problem:

Two arithmetic functions $f$ and $g$ may be multiplied using the Dirichlet product, which is defined by $(f * g)(n) = \displaystyle\sum\limits_{d \mid n} f(d)g(\frac{n}{d})$. Show that $(f * g) * h = f * (g * h)$ for the case when $f$ is the Euler-phi function, $g(n) = 1$ and $h(n) = \sigma(n)$

-
It would be quite useful if you explain the context of the problem, what you tried to far, and where you got stuck. – Ittay Weiss Nov 7 '12 at 4:25
When you put dirichlet product associative, you will find quite a lot of useful resources. (Soon that Google search will probably return this question, too.) – Martin Sleziak Nov 7 '12 at 7:17

This is true in general, not just for those functions. We have

$$((f*g)*h)(n)=\sum_{d|n}(f*g)(d)h\left(\frac nd\right)=\sum_{d|n}\left(\sum_{r|d}f(r)g\left(\frac dr\right)\right)h\left(\frac nd\right)$$

and

$$(f*(g*h))(n)=\sum_{d|n}f(d)(g*h)\left(\frac nd\right)=\sum_{d|n}f(d)\sum_{r|\frac nd}g(r)h\left(\frac n{rd}\right)\;,$$

and both of these are sums over all factorizations of $n$ into three factors and are thus equal to

$$\sum_{drs=n}f(d)g(r)h(s)\;.$$

-
True, but maybe there was some reason the person who wrote the problem wanted to draw attention to the special case. – Gerry Myerson Nov 7 '12 at 5:39

An answer has already been posted that shows that this holds in general. In this particular case, for $f = \varphi$, $g=1$, and $h=\sigma$, we may simplify matters by using the fact that each of $f,g,h$ are multiplicative (and that this holds true for their Dirichlet products too, because of this). Thus it suffices to derive our equality for $n=p^k$, with $p$ prime. We have $$f * g(n) =\sum_{d \mid n} \varphi(d)=n$$ by (for example) partitioning the cyclic group of order $n$ with respect to elemental order. Thus $$(f*g)*h(p^k)=\sum_{i=0}^k p^{k-i} \sigma(p^i)=\sum_{i=0}^k p^{k-i} \frac{p^{i+1}-1}{p-1}=\frac{(k+1)p^{k+2}-(k+2)p^{k+1}+1}{(p-1)^2}$$ Next, we calculate $$g * h(p^k)=\sum_{i=0}^k \sigma(p^i)=\sum_{i=0}^k \frac{p^{i+1}-1}{p-1}=\frac{1}{p-1}\sum_{i=0}^kp^{i+1}-1=\frac{p^{k+2}-p(k+2)+k+1}{(p-1)^2},$$ and so $$f*(g*h)(p^k)=\sum_{i=0}^k\varphi(p^{k-i})\frac{p^{i+2}-p(i+2)+i+1}{(p-1)^2}$$ $$=\frac{p^{k+2}-p(k+2)+k+1}{(p-1)^2}+\sum_{i=0}^{k-1} p^{k-i-1}\frac{p^{i+2}-p(i+2)+i+1}{p-1}$$ wherein we have had to split this sum because $\varphi(p^0) =1\neq p^{-1}(p-1)$, which requires a special case. I won't write out the final simplifications of this product because Mathematica can do all of what's left (with greater accuracy than me, too!), but suffice it to say that you will end up with $$\frac{(k+1)p^{k+2}-(k+2)p^{k+1}+1}{(p-1)^2}$$ as predicted.

As a general rule, you can always plod through these sorts of things when you have multiplicative functions.

-