Möbius inversion and Möbius function as sum of cosines

Question

Let $\mu (n)$ be the Möbius function. I want to prove the following formula: $$\mu (n)=\sum_{\substack{1\leq k \leq n\\ (k,n)=1}}\cos \frac{2k\pi}{n}.$$

Let $F(n)$ be the right hand side, then by Möbius Inversion, it suffices to show that $(F*1)(n)=\delta(n)$, where $*$ is the dirichlet convolution, $1(n)=1$ is the constant function and $\delta (n)=1$ if $n=1$ and $0$ otherwise is the delta function.

Now, $$(F*1)(n)=\sum_{d|n}\sum_{\substack{1\leq k \leq d\\ (k,d)=1}}\cos \frac{2k\pi}{d}$$ $$=\sum_{d|n}\sum_{\substack{1\leq k \leq d\\ (k,d)=1}}\cos \frac{2ke\pi}{ed}=\sum_{d|n}\sum_{\substack{1\leq k \leq d\\ (k,d)=1}}\cos \frac{2ke\pi}{n}$$, where $e=n/d \in \mathbb{N}$. I want to show that the above sum is equal to $\sum_{j=1}^n\cos \frac{2j\pi}{n}$ and the result will follow quickly as $\sum_{j=1}^n\cos \frac{2j\pi}{n} = \sum_{j=1}^n \operatorname{Re}\zeta_n^{j}$ where $\zeta_n=e^{2\pi i/n}$ is the primitive $n$-th root of unity.

To this end, it suffices to show that there is a bijection between the two sets: $S_1:=\{kn/d| 1\leq k \leq d, (k,d)=1, d|n\}$ and $S_2:=\{1,2\cdots, n\}$.

Now $S_1 \subseteq S_2$ is clear, however I have a hard time proving the other inclusion: for any $l\in S_2$, if $(l,d)=q$, then we set $k=l/q$ such that $(k,d)=1$ and we have $nk/d=nl/dq$ and we are done if we can show $dq=n$.

Actually this is problem 4.13 from the following handout https://web.evanchen.cc/handouts/Summation/Summation.pdf and I wonder if there is any quicker way since my method seems a bit overly complicated.

Thank you so much in advance.

Answer 1

If you divide all the elements of $S_1$ and $S_2$ by $n$, you get the sets $$ \tfrac1nS_1 = \{ \tfrac kd\colon 1\le k\le d,\, (k,d)=1,\, d\mid n\} \quad\text{and}\quad \tfrac1nS_2 = \{ \tfrac jn\colon 1\le j\le n\}. $$ But here it's actually clear that the two sets are in bijection: the elements of $\frac1nS_1$ are simply the reduced-to-lowest-terms forms of the elements of $\frac1nS_2$! (This is the same trick used to prove the identity $\sum_{d\mid n} \phi(d) = n$.)

Answer 2

Another approach. You may notice that $$ S(n)=\sum_{\substack{1\leq k\leq n\\(k,n)=1}}\exp\left(2\pi i \frac{k}{n}\right)$$ literally is the sum of the primitive $n$-th roots of unity, i.e. the sum of the roots of the cyclotomic polynomial $\Phi_n(x)$. Assuming $n>1$ we have that $\Phi_n(x)$ is palyndromic, $\Phi_n(x) = x^{\varphi(n)}\Phi_n(1/x)$, since if $\zeta$ is a primitive root of unity then $1/\zeta$ is also a primitive root of unity. By Vieta's theorem the sum of the roots is given by the opposite of the coefficient of $x^{\varphi(n)-1}$ in $\Phi_n(x)$, which by symmetry is also the coefficient of $x$. This leads to $$ S(n) = -\Phi_n'(0) = -\left. \frac{d}{dx}\log\Phi_n(x)\right|_{x=0}. $$ By the inclusion/exclusion principle or by Moebius inversion formula we have $$ \Phi_n(x) = \prod_{d\mid n}(x^{d}-1)^{\mu(n/d)} $$ so $$ \log\Phi_n(x) = \sum_{d\mid n}\mu(n/d)\log(x^d-1) $$ $$ \frac{d}{dx}\log\Phi_n(x) = \sum_{d\mid n}\mu(n/d)\frac{dx^{d-1}}{x^d-1} $$ and the evaluation at $x=0$ annihilates all the terms of the RHS, except the first one associated to $d=1$. This proves $S(n)=\mu(n)$ and by considering the real part of the sum defining $S(n)$ you have your claim.

Answer 3

Let $e(s)=e^{2\pi is}$, then it suffices to show that $$ S_n=\sum_{\substack{1\le k\le n\\(k,n)=1}}e(k/n)=\mu(n). $$ Using the fact that $$ \sum_{d|n}\mu(d)= \begin{cases} 1 & n=1 \\ 0 & n>1 \end{cases}, $$ we have $$ S_n=\sum_{d|n}\mu(d)\sum_{\substack{1\le k\le n\\d|k}}e(k/n)=\sum_{d|n}\mu(d)\sum_{1\le j\le n/d}e\left(j\over n/d\right). $$ By the properties of the $e(s)$, we observe the rightmost sum is zero whenever $d<n$, so we have $$ S_n=\sum_{\substack{d|n\\d=n}}\mu(d)\frac nd=\mu(n). $$

Answer 4

This problem is an example of the old adage that the shortest path between two things in the real numbers often goes through the complex numbers.

In field theory, if $\zeta_n$ is a primitive $n$th root of unity then ${\rm Tr}_{\mathbf Q(\zeta_n)/\mathbf Q}(\zeta_n) = \mu(n)$. (See Jack’s answer.) That trace is the sum of roots of the minimal polynomial of $\zeta_n$ over $\mathbf Q$, and that sum is $\sum_{(k,n)=1} \zeta_n^k$, where the sum runs over all $k$ from $1$ to $n$ that are relatively prime to $n$.

Using $\zeta_n = e^{2\pi i/n}$, we get $$ \sum_{(k,n)=1} e^{2\pi ik/n} = \mu(n). $$ Now take the real parts of both sides.

Answer 5

It is a special case of a more general formula. Let $F\left(n\right)=\sum_{d|n}f\left(d\right)$. Then $$F\left(\gcd(n,k)\right)=\sum_{d|\gcd(n,k)}f\left(d\right)=\sum_{d|n\\d|k}f\left(d\right)$$ By multiplying by $\exp \left(\frac{ i 2 \pi k}n \right)$ and summation over $k$ we will get the more general formula $$f\left(n\right)=\sum_{k=1}^{n}F\left(\gcd(n,k)\right)\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$ Using $f(n)=\mu(n)$ and $F(n)=e(n)$ you will get your formula $$\mu\left(n\right)=\sum_{ {k=1}\\{(n,k)=1}}^{n}\exp \left(\frac{i 2 \pi k}n \right)=\sum_{{k=1}\\(n,k)=1}^{n}\cos \left(\frac{2 \pi k}n \right)$$ Using $f(n)=\phi(n)$ and $F(n)=n$ you will get the famous Schramm formula for the totient function $$\phi\left(n\right)=\sum_{ {k=1}}^{n}\gcd(n,k)\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$ Using another pairs $F$ and $f$ you will get formulae for the absolute value of $\mu$ $$|\mu\left(n\right)|=\sum_{ {k=1}}^{n}\frac {\phi(n\cdot k)}{\phi(k)}\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$ for the Dirichlet inverse of $\phi$ $$\phi^{-1}\left(n\right)=\sum_{ {k=1}}^{n}\frac n{\gcd(n,k)}\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$ for the von Mangoldt function $$\Lambda\left(n\right)=\sum_{ {k=1}}^{n}\ln\left(\gcd(n,k)\right)\cdot\exp \left(\frac{ i 2 \pi k}n \right)$$ etc.

Answer 6

The $3$^rd equation line, where you introduced the variable $e$, is not necessary and it could be removed without affecting the argument. Also note the term $\zeta_n$ in your question is not a primitive $n$^th root of unity, but just a general $n$^th root of unity.

As you correctly state we need to show the double summation in the $2$^nd equation line equals $\sum_{j=1}^n\cos \frac{2j\pi}{n}$, and that to do that it suffices to show that the two sets $S_1$ and $S_2$ are equal. The $S_1 \subseteq S_2$ part is straightforward, however the other direction is not so obvious, but it can be arrived at by making use of the totient function $\phi$.

Instead of showing $S_2 \subseteq S_1$ to complete the proof of $S_1 = S_2$, since we are dealing with finite sets we can instead show $|S_1| = |S_2|$, ie. $|S_1| = n$, since we already know $S_1 \subseteq S_2$.

So, using a slightly different definition from yours, for a fixed $n \geq 1$ let : \begin{eqnarray*} S_1 & = & \{\textstyle{\frac{k}{d}} : d \mid n, k \in [1, d], (k, d) = 1 \}, \\ S_2 & = & \{ \textstyle{\frac{j}{n}} : j \in [1, n] \} \end{eqnarray*}

We can write $S_1$ as a union of the subsets $S_1^{(d)}$ that come from particular divisors $d$ of $n$ : $$ S_1 = \bigcup_{d \mid n} S_1^{(d)} $$

where, with $n \geq 1$ fixed and $d$ a divisor of $n$ : $$ S_1^{(d)} = \{ \textstyle{\frac{k}{d}} : k \in [1, d], (k, d) = 1 \}. $$

Then we have $|S_1^{(d)}| = \phi(d) \; \forall d$, and so if the $S_1^{(d)}$'s are mutually disjoint, forming a partition of $S_1$, then using the divisor sum of the totient (eg here or [1, p26, Theorem 2.2]) : $$ |S_1| = \sum_{d \mid n} |S_1^{(d)}| = \sum_{d \mid n} \phi(d) = n = |S_2| $$

as required. Thus it suffices to show the $S_1^{(d)}$'s are mutually disjoint. Consider an $x \in S_1^{(d_1)} \cap S_1^{(d_2)}$. Then there exists $k_1 \in [1, d_1]$ with $(k_1, d_1) = 1$, and $k_2 \in [1, d_2]$ with $(k_2, d_2) = 1$ such that : $$ x = \frac{k_1}{d_1} = \frac{k_2}{d_2}. $$

But these are fractions in their simplest form so their numerators and denominators must be the same, due to the uniqueness of the simplest form of a fraction, and hence in particular $d_1 = d_2$. Thus the $S_1^{(d)}$'s are mutually disjoint. Alternatively we could say $k_1 d_2 = k_2 d_1$ and then in terms of the 'multisets' which are the prime decompositions, the primes of $d_2$ must all be contained within $d_1$, as $d_2$ shares no primes with $k_2$, so that '$d_2 \subseteq d_1$', and likewise as $d_1$ shares no primes with $k_1$, so '$d_1 \subseteq d_2$', and thus $d_1 = d_2$ - which is how the uniqueness of the simplest form is proved.

The same method of proving $S_1 = S_2$ can be used to solve a more general problem (see [1, Problem 2.14, p48]), namely if : \begin{eqnarray*} F(n) & = & \sum_{k = 1}^n f(k/n) \\ \mbox{and} \hspace{2em} F^*(n) & = & \sum_{ \substack{k = 1 \\ (k, n) = 1} }^n f(k/n) \end{eqnarray*} then $F$ and $F^*$ are related by $F^* = \mu * F$.

From this we can arrive at the following relation for the sum of the primitive $n$^th roots of unity (from which the relation you require can be deduced by taking the real part) : $$ \sum_{ \substack{k = 1 \\ (k, n) = 1} }^n e^{2 \pi i k / n} = \mu(n), \hspace{3em} \forall n \geq 1 $$

by putting $f(x) = e^{2 \pi i x}$, so that the LHS is $F^*(n)$ and : $$ F(n) = \sum_{k = 1}^n e^{2 \pi i k / n} \hspace{1em} = \mbox{sum of $n^{\mathrm{th}}$ roots of unity.} $$

But for $n > 1$, the sum of the $n$^th roots of unity $\{ \alpha_r \}$ is minus the coefficient of $z^{n - 1}$ in the complex polynomial $z^n - 1 = (z - \alpha_1) \cdots (z - \alpha_n)$, thus : $$ F(n) = \left\{ \begin{array}{ll} 1, & \mbox{when $n = 1$}, \\ 0, & \mbox{when $n > 1$} \end{array} \right. $$

which equals the identity $\delta$ in the Dirichlet ring, and hence $F^* = \mu$, as required.

References

[1] Tom M. Apostol (1976), Introduction to Analytic Number Theory, Springer-Verlag.