I saw a proof for the above that went \begin{align*} f(n) &= \sum_{k=1}^{n}\left(\sum_{d\mid (k,n)} \mu(d)e^{\frac{2\pi ik}{n}} \right)\\ &= \sum_{d\mid n} \left( \mu(d) \sum_{k=0}^{(n/d)-1} e^{\frac{2\pi idk}{n}} \right), \end{align*} in which case for $g(n)=\sum_{k=0}^{n-1} e^{\frac{2\pi ik}{n}}$ we have \begin{equation*} f(n)=\sum_{d\mid n} \mu(d) g(n/d) \implies g(n) = \sum_{d\mid n} f(d), \end{equation*} which then proves the statement above by Mobius Inversion once more, since $g$ is $0$ for all $n>1$.

I understand most of the proof; I'm just not sure how we went through the first two steps of transforming $f(n)$ to get to the point where we can apply the inversion. If anyone can explain the first two steps for me I would appreciate it, thanks!


1 Answer 1


We would do : $$ f(n) = \sum_{\ \ \ k=1 \\(k,n) = 1}^n e^{\frac{2 \pi i k}n} = \sum_{k=1}^n 1_{\{(k,n) = 1\}}e^{\frac{2 \pi ik}n} $$ where $1_X = 1$ whenever something belongs in the set $X$ and $0$ otherwise.

Now use the basic inversion formula : $\sum_{d | t} \mu(d) = 0$ for any $t \neq 1$, and $1 $for $t = 1$. That is, we have $1_{\{t\}} = \sum_{d | t} \mu(d)$. With this, we get : $$ \sum_{k=1}^n \sum_{d | (k,n)} \mu(d)e^{\frac{2 \pi i k}n} $$

As the first line required.

For the second line, we do a "reindexing". See, the term $\mu(d) e^{\frac{2 \pi i k}n}$ is being first summed over all $d$ dividing $(k,n)$, and then running over all $k=1 $ to $n$. Suppose we wanted to run over all $k$ first, then over all $d$. The question is , how would this be done?

It would be as follows : certainly $d$ must be a divisor of $n$, so $d$ can be allowed to run over all divisors of $n$, i.e. $\sum_{d |n}$ is justifiable. Now, fixing $d$, which $k$ can be such that $d | (k,n)$? Certainly those which are multiples of $d$! That is, numbers of the form $d , 2d, ... , \frac{(n-1)d}{d}$.

Let us take an example, say $n=6$. Let's go over all pairs $(d,k)$ for which $\mu(d)e^{\frac{2\pi ik}{n}}$ appears in the summation.

For $k=1,5$ we have $d = 1$. For $k=2,4$ we have $d = 1,2$. For $k = 3$ we have $d = 1,3$, and finally for $k=6$ we have $d = 1,2,3,6$.

Now, reverse it : for $d =1$ we have $k=1,2,3,4,5,6$. For $d = 2 $ we have $k = 2,4,6$, for $d = 3$ we have $k=3,6$, for $d = 6$ we have $k = 6$. You can see the reindexing is exactly as I have described.

Thus, we do a reindexing : $$ \sum_{k = 1}^n \sum_{d | (k,n)} \mu(d)e^{\frac{2 \pi i k}{n}} = \sum_{d | n} \sum_{k \textrm{ multiple of } d} \mu(d)e^{\frac{2 \pi ik}n} = \sum_{d | n} \sum_{l = 1}^{\frac{n}d -1} \mu(d) e^{\frac{2 \pi i dl}n} $$

as required.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.