# Ramanujan Sums: Showing $c_n(k)$

• POTW
• Euge
In summary, Ramanujan sums are a mathematical concept used in number theory, named after the Indian mathematician Srinivasa Ramanujan. They are calculated using a formula involving the Möbius function and have various applications in number theory and other areas of mathematics. They can also be generalized to include more variables and parameters. However, there are several open problems related to Ramanujan sums, including the unproven Ramanujan conjecture.
Euge
Gold Member
MHB
POTW Director
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)$$

topsquark and Greg Bernhardt
Euge said:
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?

topsquark
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)##.

topsquark and bob012345
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}
\end{align*}

This second result can be used to prove the Mobius inversion formula:
\begin{align*}
g (n) = \sum_{d|n} f(d)
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*}
g (n) = \sum_{d|n} f(d)
f (n) = \sum_{d|n} \mu \left( \frac{n}{d} \right) g (d) .
\end{align*}
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 \\
\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*}

Last edited:
Euge

Replies
3
Views
915
Replies
4
Views
911
Replies
1
Views
2K
Replies
16
Views
1K
Replies
1
Views
2K
Replies
10
Views
980
Replies
1
Views
2K
Replies
2
Views
2K
Replies
1
Views
1K
Replies
2
Views
2K