Derivation of a formula for computing sums of Ramanujan’s sums

Ramanujan’s sums are sums of powers of primitive roots of unity of the form

c_k(m) = \sum_{\substack{q\hspace{1 mm} mod \hspace{1 mm}k \\ gcd(q, k)=1}} e^{2\pi iqm/k}        (1)

where m is a fixed positive integer and here we are summing the m-th powers of the primitive k-th roots of unity. Ramanujan showed that these sums are always integers, using the following equivalent expression for them (which I will derive in detail in a later note):

c_k(m) = \sum_{d|gcd(m, k)}d\mu\big(\frac{k}{d}\big)        (2)

Here, \mu is the Möbius function. Sometimes it is necessary to sum these over m, but this can get very tedious if the form in (1) above is used. In this short note, which is mainly intended as a technical memo for myself, I want to give a detailed derivation of a more convenient formula for finding sums of Ramanujan’s sums, using the form in (2). I will also give a couple of brief illustrative examples. (It is not hugely difficult, but I am not aware of any explicit derivation of this formula in the literature, and I found the process instructive).

Noting that (2) can be written equivalently as

c_k(m) = \sum_{\substack{d|m \\ d|k}}d\mu\big(\frac{k}{d}\big)

and summing over m from 1 to n we get

\sum_{m=1}^n c_k(m) = \sum_{m=1}^n \sum_{\substack{d|m \\ d|k}}d\mu\big(\frac{k}{d}\big)

We can write m = cd for integer c (since d|m) and observe that, since it is required that d|m in the above sum, it must be the case that the index c runs from 1 to n/d. Then we have

\sum_{m=1}^n c_k(m) = \sum_{m=1}^n \sum_{\substack{d|m \\ d|k}}d\mu\big(\frac{k}{d}\big) = \sum_{d|k}\sum_{c=1}^{n/d} d\mu \big(\frac{k}{d}\big)

= \sum_{d|k}d\mu\big(\frac{k}{d}\big)\sum_{c=1}^{n/d}1

= \sum_{d|k}d\mu\big(\frac{k}{d}\big)\big[\frac{n}{d}\big]

The formula

\sum_{m=1}^n c_k(m) = \sum_{d|k}d\mu\big(\frac{k}{d}\big)\big[\frac{n}{d}\big]

is the one required.

To illustrate its use, suppose we are given k = 10. Then we have d = 1, 2, 5, 10, and so, for example,

c_{10}(1) + c_{10}(2) + \cdots + c_{10}(7)

= \mu(10)[7] + 2\mu(5)[7/2] + 5\mu(2)[7/5] + 10\mu(1)[7/10] = -4

We can also compute sums of Ramanujan’s sums to an unspecified limit n if we know the residue class to which n belongs modulo some number. For example, when k = 4, we have d = 1, 2, 4. When n \equiv 3 (mod 4) we have n = 4c + 3, where c denotes an integer. Then:

\big[\frac{n}{1}\big] = 4c + 3    \big[\frac{n}{2}\big] = 2c + 1     \big[\frac{n}{4}\big] = c

and so

\sum_{m=1}^nc_4(m) = \sum_{d|4}d\mu\big(\frac{4}{d}\big)\big[\frac{n}{d}\big]

= 0 + (2)(-1)(2c + 1) + (4)(1)(c) = -2