Take the tour ×

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)$

Thanks in advance!

share|improve this question
It would be quite useful if you explain the context of the problem, what you tried to far, and where you got stuck. Also, if this is a homework question please tag it as such. –  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
add comment

2 Answers

up vote 2 down vote accepted

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) $$


$$ (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)\;. $$

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

Your Answer

