POTW Ramanujan Sums: Showing $c_n(k)$

[Euge]

Consider the $n$th Ramanujan sum, $$c_n(k) = \sum_{\substack{m = 1\\(m,n) = 1}}^n \exp\left\{2\pi i \frac{k m}{n}\right\}$$ Show that $$c_n(k) = \sum_{d\mid (k,n)} d\, \mu\left(\frac{n}{d}\right)$$

 

[bob012345]

Consider the $n$th Ramanujan sum, $$c_n(k) = \sum_{\substack{m = 1\\(m,n) = 1}}^n \exp\left\{2\pi i \frac{k m}{n}\right\}$$ Show that $$c_n(k) = \sum_{d\mid (k,n)} d\, \mu\left(\frac{n}{d}\right)$$

Can you define the terms please?

 

[Euge]

The function $\mu$ is the Möbius function: it is defined by setting $\mu(1) = 1$ and for integers $n > 1$, $\mu(n) = (-1)^r$ if $n$ is a product of $r$ distinct prime factors. Otherwise $\mu(n) = 0$.

The notation $(a,b)$ means the gcd of $a$ and $b$, and $\sum_{d\mid (k,n)}$ means the sum over all positive divisors $d$ of $(k,n)$.

 

[julian]

Spoiler

I looked at the case where $k=1$ first. Proved the Mobius inversion formula. Answered the question for $k=1$. Then proved the general case.

Case $k=1$.

Consider
\begin{align*}
c_n (1) = \sum_{m=1 , (m,n)=1}^n \exp \left\{ 2 \pi i \frac{m}{n} \right\}
\end{align*}
We wish to show:
\begin{align*}
c_n (1) = \sum_{d|(1,n)} d \; \mu \left( \frac{n}{d} \right) = \mu (n)
\end{align*}

The fractions $\frac{l}{n}$, $l=1,2, \dots, n$ and the fractions defined by $\frac{m}{d}$, $(m,d)=1$, $1 \leq m \leq d$ for the set of divisors of $n$, $\{ d_1, d_2, \dots , d_s \}$, are the same set of fractions. As such:
\begin{align*}
\sum_{d|n} \sum_{m=1 , (m,d)=1}^d f \left( \frac{m}{d} \right) = \sum_{l=1}^n f \left( \frac{l}{n} \right)
\end{align*}
We use this, for $n>1$,
\begin{align*}
\sum_{d|n} c_d (1) = \sum_{d|n} \sum_{m=1 , (m,d)=1}^d \exp \left\{ 2 \pi i \frac{m}{d} \right\} = \sum_{l=1}^n \exp \left\{ 2 \pi i \frac{l}{n} \right\} = \dfrac{\exp \left\{ 2 \pi i \right\} - 1}{\exp \left\{ 2 \pi i \frac{1}{n} \right\} - 1} = 0
\end{align*}
If $n=1$:
\begin{align*}
\sum_{d|1} c_d (1) = \sum_{d|1} \sum_{m=1 , (m,d)=1}^d \exp \left\{ 2 \pi i \frac{m}{d} \right\} = 1
\end{align*}

Next consider the same sum for $\mu (n)$. First take $n>1$. We have $n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$. Note the divisors $d$ of $n$ such that $\mu (d) \not= 0$ are the product of members of subsets of: $\{ p_1 , p_2 , \cdots , p_r \}$ (the empty set corresponds to $d=1$). As there are $\dfrac{r!}{k! (r-k)!}$ ways of choosing subsets of size $k$, the following:
\begin{align*}
\sum_{k=0}^r \dfrac{r!}{k! (r-k)!} (-1)^k
\end{align*}
will tell us how many more subsets of even number there are than subsets of odd number (where $k=0$ term corresponds to the empty set). The above sum is equal to $[1 + (-1)]^r = 0$, meaning that there are an equal number of subsets of even number and subsets and odd number. As such:
\begin{align*}
\sum_{d|n} \mu (d) = 0 \qquad (n>1) .
\end{align*}
For $n=1$:
\begin{align*}
\sum_{d|1} \mu (1) = 1 .
\end{align*}

Summarising, we have
\begin{align*}
\sum_{d|n} \sum_{m=1 , (m,d)=1}^d \exp \left\{ 2 \pi i \frac{m}{d} \right\} = \left\{
\begin{matrix}
1 & n=1 \\
0 & n>1
\end{matrix}
\right.
\end{align*}
and
\begin{align*}
\sum_{d|n} \mu (d) = \left\{
\begin{matrix}
1 & n=1 \\
0 & n>1
\end{matrix}
\right. \qquad (*)
\end{align*}

This second result can be used to prove the Mobius inversion formula:
\begin{align*}
\text{if} \qquad
g (n) = \sum_{d|n} f(d)
\qquad \text{then} \qquad
f (n) = \sum_{d|n} \mu(d) g \left( \frac{n}{d} \right)
\end{align*}
If the divisors of $n$ are $\{ d_1 , d_2, \dots d_s \}$, define $\tilde{d}_i = \frac{n}{d_i}$ for each $i$. The $\{ \tilde{d}_1 , \tilde{d}_2, \dots \tilde{d}_s \}$ are the $s$ original distinct divisors in a new order, and obviously, $d_i = \frac{n}{\tilde{d}_i}$. So that
\begin{align*}
\sum_{d|n} \mu(d) g \left( \frac{n}{d} \right) = \sum_{i=1}^s \mu (d_i) g (\tilde{d}_i) = \sum_{i=1}^s \mu (\tilde{d}_i) g (d_i) = \sum_{d|n} \mu \left( \frac{n}{d} \right) g (d)
\end{align*}
So we have the alternative version of the Mobius inversion formula:
\begin{align*}
\text{if} \qquad
g (n) = \sum_{d|n} f(d)
\qquad \text{then} \qquad
f (n) = \sum_{d|n} \mu \left( \frac{n}{d} \right) g (d) .
\end{align*}

Spoiler: proof of the Mobius inversion formula

Taking an example:

\begin{align*}
& \sum_{d|8} \mu(d) g \left( \frac{8}{d} \right)
\nonumber \\
& = \sum_{d|8} \mu(d) \sum_{d'|\frac{8}{d}} f \left( d' \right)
\nonumber \\
& = \mu(1) \sum_{d'|8} f \left( d' \right) + \mu(2) \sum_{d'|\frac{8}{2}} f \left( d' \right) + \mu(4) \sum_{d'|\frac{8}{4}} f \left( d' \right) + \mu(8) \sum_{d'|\frac{8}{8}} f \left( d' \right)
\nonumber \\
& = \mu(1) f \left( 1 \right) + \mu(2) f \left( 1 \right) + \mu(4) f \left( 1 \right) + \mu(4) f \left( 1 \right)
\nonumber \\
& + \mu(1) f \left( 2 \right) + \mu(2) f \left( 2 \right) + \mu(4) f \left( 2 \right) + \qquad 0
\nonumber \\
& + \mu(1) f \left( 4 \right) + \mu(2) f \left( 4 \right) + \qquad 0 \qquad + \quad \;\; 0
\nonumber \\
& + \mu(1) f \left( 8 \right) + \quad \;\;\; 0 \quad \;\;\; + \quad \;\;\; 0 \quad \;\;\; + \quad \;\;\; 0
\nonumber \\
& = f \left( 1 \right) \sum_{d|8} \mu(d) + f \left( 2 \right) \sum_{d|4} \mu(d) + f \left( 4 \right) \sum_{d|2} \mu(d) + f \left( 8 \right) \sum_{d|1} \mu(1)
\nonumber \\
& = \sum_{d'|8} f \left( d' \right) \sum_{d|\frac{8}{d'}} \mu(d)
\nonumber \\
& = f \left( 8 \right) .
\end{align*}
where we have used $(*)$.

Let $\{ d_1 , d_2, \dots d_s \}$ be the divisors of $n$. Define
\begin{align*}
\epsilon (d_i',d_j) =
\left\{
\begin{matrix}
1 & d_i' | \frac{n}{d_j} \\
0 & d_i' \nmid \frac{n}{d_j}
\end{matrix}
\right.
\end{align*}
Note $d_i' | \frac{n}{d_j}$ if and only if $d_j | \frac{n}{d_i'}$. Thus
\begin{align*}
\epsilon (d_i',d_j) =
\left\{
\begin{matrix}
1 & d_j | \frac{n}{d_i'} \\
0 & d_j \nmid \frac{n}{d_i'}
\end{matrix}
\right.
\end{align*}
So
\begin{align*}
\sum_{d|n} \mu(d) g \left( \frac{n}{d} \right) & = \sum_{d|n} \mu(d) \sum_{d'|\frac{n}{d}} f \left( d' \right)
\nonumber \\
& = \sum_{j=1}^s \mu(d_j) \sum_{i=1}^s \epsilon (d_i',d_j) f \left( d_i' \right)
\nonumber \\
& = \sum_{i=1}^s f \left( d_i' \right) \sum_{j=1}^s \epsilon (d_i',d_j) \mu(d_j)
\nonumber \\
& = \sum_{d'|n} f \left( d' \right) \sum_{d|\frac{n}{d'}} \mu(d)
\nonumber \\
& = f \left( n \right)
\end{align*}
where we have used $(*)$.

Write
\begin{align*}
f (n) = \sum_{m=1 , (m,n)=1}^n \exp \left\{ 2 \pi i \frac{m}{n} \right\}
\end{align*}
then
\begin{align*}
g (n) = \sum_{d|n} \sum_{m=1 , (m,n)=1}^d \exp \left\{ 2 \pi i \frac{m}{d} \right\}
= \left\{
\begin{matrix}
1 & n=1 \\
0 & n>1
\end{matrix}
\right.
\end{align*}
and then
\begin{align*}
f (n) = \sum_{d|n} \mu \left( \frac{n}{d} \right) g(d) = \mu (n)
\end{align*}
So finally,
\begin{align*}
\mu (n) = \sum_{m=1 , (m,n)=1}^n \exp \left\{ 2 \pi i \frac{m}{n} \right\}
\end{align*}Next, the general case, $1 \leq k$:

Consider
\begin{align*}
c_n (k) = \sum_{m=1 , (m,n)=1}^n \exp \left\{ 2 \pi i \frac{km}{n} \right\}
\end{align*}
We wish to prove
\begin{align*}
c_n (k) = \sum_{d|(k,n)} d \; \mu \left( \frac{n}{d} \right)
\end{align*}

Write $f(n) = c_n (k)$. When $n \nmid k$,
\begin{align*}
g (n) = \sum_{d|n} \sum_{m=1 , (m,d)=1}^d \exp \left\{ 2 \pi i \frac{km}{d} \right\}
= \sum_{l=1}^n \exp \left\{ 2 \pi i \frac{kl}{n} \right\}
= \dfrac{\exp \left\{ 2 \pi i k \right\} - 1}{\exp \left\{ 2 \pi i \frac{k}{n} \right\} - 1} = 0
\end{align*}
When $n | k$,
\begin{align*}
g (n) = \sum_{d|n} \sum_{m=1 , (m,d)=1}^d \exp \left\{ 2 \pi i \frac{km}{d} \right\}
= \sum_{l=1}^n \exp \left\{ 2 \pi i \frac{kl}{n} \right\}
= n .
\end{align*}
That is:
\begin{align*}
g (n) = \sum_{d|n} \sum_{m=1 , (m,d)=1}^d \exp \left\{ 2 \pi i \frac{km}{d} \right\} =
\left\{
\begin{matrix}
n & n | k \\
0 & n \nmid k
\end{matrix}
\right.
\end{align*}
So that
\begin{align*}
f (n) = \sum_{d|n} \mu \left( \frac{n}{d} \right) g (d) = \sum_{d|(k,n)} d \; \mu \left( \frac{n}{d} \right)
\end{align*}