Ramanujan's sum

From Wikipedia, the free encyclopedia
  (Redirected from Ramanujan sum)
Jump to: navigation, search
Not to be confused with Ramanujan summation. ‹See Tfd›

In number theory, a branch of mathematics, Ramanujan's sum, usually denoted cq(n), is a function of two positive integer variables q and n defined by the formula

c_q(n)= \sum_{a=1\atop (a,q)=1}^q e^{2 \pi i \tfrac{a}{q} n},

where (a, q) = 1 means that a only takes on values coprime to q.

Srinivasa Ramanujan introduced the sums in a 1918 paper.[1] In addition to the expansions discussed in this article, Ramanujan's sums are used in the proof of Vinogradov's theorem that every sufficiently-large odd number is the sum of three primes.[2]


For integers a and b, a\mid b is read "a divides b" and means that there is an integer c such that b = ac. Similarly, a\nmid b is read "a does not divide b". The summation symbol


means that d goes through all the positive divisors of m, e.g.

\sum_{d\,\mid\,12}f(d) = f(1) + f(2) + f(3) + f(4) + f(6) + f(12).

(a,\,b)\; is the greatest common divisor,

\phi(n)\; is Euler's totient function,

\mu(n)\; is the Möbius function, and

\zeta(s)\; is the Riemann zeta function.

Formulas for cq(n)[edit]


These formulas come from the definition, Euler's formula e^{ix}= \cos x + i \sin x, and elementary trigonometric identities.

c_1(n) &= 1 \\
c_2(n) &= \cos n\pi \\
c_3(n) &= 2\cos \tfrac23 n\pi \\
c_4(n) &= 2\cos \tfrac12 n\pi \\
c_5(n) &= 2\cos \tfrac25 n\pi + 2\cos \tfrac45 n\pi \\
c_6(n) &= 2\cos \tfrac13 n\pi \\
c_7(n) &= 2\cos \tfrac27 n\pi + 2\cos \tfrac47 n\pi + 2\cos \tfrac67 n\pi \\
c_8(n) &= 2\cos \tfrac14 n\pi + 2\cos \tfrac34 n\pi \\
c_9(n) &= 2\cos \tfrac29 n\pi + 2\cos \tfrac49 n\pi + 2\cos \tfrac89 n\pi \\
c_{10}(n)&= 2\cos \tfrac15 n\pi + 2\cos \tfrac35 n\pi \\

and so on (OEISA000012, OEISA033999, OEISA099837, OEISA176742,.., OEISA100051,...) They show that cq(n) is always real.


Let \zeta_q=e^{\frac{2\pi i}{q}}. Then ζq is a root of the equation xq − 1 = 0. Each of its powers ζq, ζq2, ... ζqq = ζq0 = 1 is also a root. Therefore, since there are q of them, they are all of the roots. The numbers ζqn where 1 ≤ nq are called the q-th roots of unity. ζq is called a primitive q-th root of unity because the smallest value of n that makes ζqn = 1 is q. The other primitive q-th roots of are the numbers ζqa where (a, q) = 1. Therefore, there are φ(q) primitive q-th roots of unity.

Thus, the Ramanujan sum cq(n) is the sum of the n-th powers of the primitive q-th roots of unity.

It is a fact[3] that the powers of ζq are precisely the primitive roots for all the divisors of q.

Example. Let q = 12. Then

ζ12, ζ125, ζ127, and ζ1211 are the primitive twelfth roots of unity,
ζ122 and ζ1210 are the primitive sixth roots of unity,
ζ123 = i and ζ129 = −i are the primitive fourth roots of unity,
ζ124 and ζ128 are the primitive third roots of unity,
ζ126 = −1 is the primitive second root of unity, and
ζ1212 = 1 is the primitive first root of unity.

Therefore, if

\eta_q(n) = \sum_{k=1}^q \zeta_q^{kn}

is the sum of the n-th powers of all the roots, primitive and imprimitive,

\eta_q(n) = \sum_{d\,\mid\, q} c_d(n),

and by Möbius inversion,

c_q(n) = \sum_{d\,\mid\,q} \mu\left(\frac{q}d\right)\eta_d(n).

It follows from the identity xq − 1 = (x − 1)(xq−1 + xq−2 + ... + x + 1) that

\eta_q(n) = 
0&\;\mbox{  if }q\nmid n\\
q&\;\mbox{  if }q\mid n\\

and this leads to the formula

c_q(n)=\sum_{d\,\mid\,(q,n)}\mu\left(\frac{q}{d}\right) d,

published by Kluyver in 1906.[4]

This shows that cq(n) is always an integer. Compare it with the formula

\phi(q)=\sum_{d\,\mid\,q}\mu\left(\frac{q}{d}\right) d.

von Sterneck[edit]

It is easily shown from the definition that cq(n) is multiplicative when considered as a function of q for a fixed value of n:[5] i.e.

\mbox{If } \;(q,r) = 1 \;\mbox{ then }\; c_q(n)c_r(n)=c_{qr}(n).

From the definition (or Kluyver's formula) it is straightforward to prove that, if p is a prime number,

c_p(n) = 
-1     &\mbox{  if }p\nmid n\\
\phi(p)&\mbox{  if }p\mid n\\

and if pk is a prime power where k > 1,

c_{p^k}(n) = 
0         &\mbox{  if }p^{k-1}\nmid n\\
-p^{k-1}  &\mbox{  if }p^{k-1}\mid n \mbox{ and }p^k\nmid n\\
\phi(p^k) &\mbox{  if }p^k\mid n\\

This result and the multiplicative property can be used to prove

c_q(n)= \mu\left(\frac{q}{(q, n)}\right)\frac{\phi(q)}{\phi\left(\frac{q}{(q, n)}\right)}.

This is called von Sterneck's arithmetic function.[6] The equivalence of it and Ramanujan's sum is due to Hölder.[7][8]

Other properties of cq(n)[edit]

For all positive integers q,

c_1(q) = 1, \;\;
c_q(1) = \mu(q), \;
\mbox{  and  }\; c_q(q) =

\mbox{If }
m \equiv n \pmod q
\mbox{ then }
c_q(m) = 

For a fixed value of q the absolute value of the sequence

cq(1), cq(2), ... is bounded by φ(q), and

for a fixed value of n the absolute value of the sequence

c1(n), c2(n), ... is bounded by σ(n), the sum of the divisors of n.

If q > 1

\sum_{n=a}^{a+q-1} c_q(n)=0.

Let m1, m2 > 0, m = lcm(m1, m2). Then[9] Ramanujan's sums satisfy an orthogonality property:

\frac{1}{m}\sum_{k=1}^m c_{m_1}(k) c_{m_2}(k) = \begin{cases} \phi(m) & m_1=m_2=m,\\ 0 & \text{otherwise} \end{cases}

Let n, k > 0. Then[10]

\sum_\stackrel{d\mid n}{\gcd(d,k)=1} d\;\frac{\mu(\tfrac{n}{d})}{\phi(d)} =
\frac{\mu(n) c_n(k)}{\phi(n)},

known as the Brauer - Rademacher identity.

If n > 0 and a is any integer, we also have[11]

\sum_\stackrel{1\le k\le n}{\gcd(k,n)=1} c_n(k-a) =

due to Cohen.

Ramanujan expansions[edit]

If f(n) is an arithmetic function (i.e. a complex-valued function of the integers or natural numbers), then a convergent infinite series of the form

f(n)=\sum_{q=1}^\infty a_q c_q(n)

or of the form

f(q)=\sum_{n=1}^\infty a_n c_q(n)

where the akC, is called a Ramanujan expansion[12] of f(n).

Ramanujan found expansions of some of the well-known functions of number theory. All of these results are proved in an "elementary" manner (i.e. only using formal manipulations of series and the simplest results about convergence).[13][14][15]

The expansion of the zero function depends on a result from the analytic theory of prime numbers, namely that the series


converges to 0, and the results for r(n) and r′(n) depend on theorems in an earlier paper.[16]

All the formulas in this section are from Ramanujan's 1918 paper.

Generating functions[edit]

The generating functions of the Ramanujan sums are Dirichlet series:

 \zeta(s) \sum_{\delta\,\mid\,q} \mu\left(\frac{q}{\delta}\right) \delta^{1-s} = \sum_{n=1}^\infty \frac{c_q(n)}{n^s}

is a generating function for the sequence cq(1), cq(2), ... where q is kept constant, and

\frac{\sigma_{r-1}(n)}{n^{r-1}\zeta(r)}= \sum_{q=1}^\infty \frac{c_q(n)}{q^{r}}

is a generating function for the sequence c1(n), c2(n), ... where n is kept constant.

There is also the double Dirichlet series

\frac{\zeta(s) \zeta(r+s-1)}{\zeta(r)}= \sum_{q=1}^\infty \sum_{n=1}^\infty \frac{c_q(n)}{q^r n^s}.


σk(n) is the divisor function (i.e. the sum of the k-th powers of the divisors of n, including 1 and n). σ0(n), the number of divisors of n, is usually written d(n) and σ1(n), the sum of the divisors of n, is usually written σ(n).

If s > 0,

 \sigma_s(n)= n^s \zeta(s+1) \left( \frac{c_1(n)}{1^{s+1}}+ \frac{c_2(n)}{2^{s+1}}+ \frac{c_3(n)}{3^{s+1}}+\dots\right)



Setting s = 1 gives

\sigma(n)= \frac{\pi^2}{6}n \left( \frac{c_1(n)}{1}+ \frac{c_2(n)}{4}+ \frac{c_3(n)}{9}+ \dots \right).

If the Riemann hypothesis is true, and -\tfrac12<s<\tfrac12,

\sigma_s(n) = \zeta(1-s) \left( \frac{c_1(n)}{1^{1-s}}+ \frac{c_2(n)}{2^{1-s}}+ \frac{c_3(n)}{3^{1-s}}+ \dots \right) = n^s \zeta(1+s) \left( \frac{c_1(n)}{1^{1+s}}+ \frac{c_2(n)}{2^{1+s}}+ \frac{c_3(n)}{3^{1+s}}+ \dots \right).


d(n) = σ0(n) is the number of divisors of n, including 1 and n itself.

-d(n) &= \frac{\log 1}{1}c_1(n)+ \frac{\log 2}{2}c_2(n)+ \frac{\log 3}{3}c_3(n)+ \dots \\
-d(n)(2\gamma+\log n) &= \frac{\log^2 1}{1}c_1(n)+ \frac{\log^2 2}{2}c_2(n)+ \frac{\log^2 3}{3}c_3(n)+ \cdots 

where γ = 0.5772... is the Euler–Mascheroni constant.


Euler's totient function φ(n) is the number of positive integers less than n and coprime to n. Ramanujan defines a generalization of it, if


is the prime factorization of n, and s is a complex number, let


so that φ1(n) = φ(n) is Euler's function.[17]

He proves that

 \frac{\mu(n)n^s}{\phi_s(n)\zeta(s)}= \sum_{\nu=1}^\infty \frac{\mu(n\nu)}{\nu^s}

and uses this to show that


Letting s = 1,

\phi(n) = \frac{6}{\pi^2}n \left(c_1(n) -\frac{c_2(n)}{2^2-1} -\frac{c_3(n)}{3^2-1} -\frac{c_5(n)}{5^2-1}+\frac{c_6(n)}{(2^2-1)(3^2-1)} - \frac{c_7(n)}{7^2-1} +\frac{c_{10}(n)}{(2^2-1)(5^2-1)} -\dots \right ).

Note that the constant is the inverse[18] of the one in the formula for σ(n).


Von Mangoldt's function Λ(n) = 0 unless n = pk is a power of a prime number, in which case it is the natural logarithm log p.

 -\Lambda(m) = c_m(1)+ \frac{1}{2} c_m(2)+ \frac13c_m(3)+\dots


For all n > 0,

0= c_1(n)+ \frac12c_2(n)+ \frac13c_3(n)+ \dots.

This is equivalent to the prime number theorem.[19][20]

r2s(n) (sums of squares)[edit]

r2s(n) is the number of way of representing n as the sum of 2s squares, counting different orders and signs as different (e.g., r2(13) = 8, as 13 = (±2)2 + (±3)2 = (±3)2 + (±2)2.)

Ramanujan defines a function δ2s(n) and references a paper[21] in which he proved that r2s(n) = δ2s(n) for s = 1, 2, 3, and 4. For s > 4 he shows that δ2s(n) is a good approximation to r2s(n).

s = 1 has a special formula:

 \delta_2(n)= \pi \left( \frac{c_1(n)}{1}- \frac{c_3(n)}{3}+ \frac{c_5(n)}{5}- \dots \right).

In the following formulas the signs repeat with a period of 4.

If s ≡ 0 (mod 4),

\delta_{2s}(n)= \frac{\pi^s n^{s-1}}{(s-1)!} \left( \frac{c_1(n)}{1^s}+ \frac{c_4(n)}{2^s}+ \frac{c_3(n)}{3^s}+\frac{c_8(n)}{4^s}+ \frac{c_5(n)}{5^s}+ \frac{c_{12}(n)}{6^s}+ \frac{c_7(n)}{7^s}+ \frac{c_{16}(n)}{8^s}+ \dots \right)

If s ≡ 2 (mod 4),

\delta_{2s}(n)= \frac{\pi^s n^{s-1}}{(s-1)!} \left( \frac{c_1(n)}{1^s}- \frac{c_4(n)}{2^s}+ \frac{c_3(n)}{3^s}- \frac{c_8(n)}{4^s}+ \frac{c_5(n)}{5^s}- \frac{c_{12}(n)}{6^s}+ \frac{c_7(n)}{7^s}- \frac{c_{16}(n)}{8^s}+ \dots \right)

If s ≡ 1 (mod 4) and s > 1,

\frac{\pi^s n^{s-1}}{(s-1)!}

If s ≡ 3 (mod 4),

\frac{\pi^s n^{s-1}}{(s-1)!}

and therefore,

r_2(n) &= \pi \left(\frac{c_1(n)}{1}- \frac{c_3(n)}{3}+ \frac{c_5(n)}{5}- \frac{c_7(n)}{7}+ \frac{c_{11}(n)}{11}- \frac{c_{13}(n)}{13}+ \frac{c_{15}(n)}{15} - \frac{c_{17}(n)}{17} + \cdots \right) \\
r_4(n) &= \pi^2 n \left( \frac{c_1(n)}{1}- \frac{c_4(n)}{4}+ \frac{c_3(n)}{9}- \frac{c_8(n)}{16}+ \frac{c_5(n)}{25}- \frac{c_{12}(n)}{36}+ \frac{c_7(n)}{49}- \frac{c_{16}(n)}{64}+ \cdots \right) \\
r_6(n) &= \frac{\pi^3 n^2}{2} \left( \frac{c_1(n)}{1}- \frac{c_4(n)}{8}- \frac{c_3(n)}{27}- \frac{c_8(n)}{64}+ \frac{c_5(n)}{125}- \frac{c_{12}(n)}{216}- \frac{c_7(n)}{343} - \frac{c_{16}(n)}{512}+ \cdots \right) \\
r_8(n) &= \frac{\pi^4 n^3}{6} \left( \frac{c_1(n)}{1}+ \frac{c_4(n)}{16}+  \frac{c_3(n)}{81}+  \frac{c_8(n)}{256}+ \frac{c_5(n)}{625}+ \frac{c_{12}(n)}{1296}+ \frac{c_7(n)}{2401}+ \frac{c_{16}(n)}{4096}+ \cdots \right)

r2s(n) (sums of triangles)[edit]

r2s(n) is the number of ways n can be represented as the sum of 2s triangular numbers (i.e. the numbers 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4, 15, ...; the n-th triangular number is given by the formula n(n + 1)/2.)

The analysis here is similar to that for squares. Ramanujan refers to the same paper as he did for the squares, where he showed that there is a function δ′2s(n) such that r2s(n) = δ′2s(n) for s = 1, 2, 3, and 4, and that for s > 4, δ′2s(n) is a good approximation to r2s(n).

Again, s = 1 requires a special formula:

\delta'_2(n)= \frac{\pi}{4} \left( \frac{c_1(4n+1)}{1}- \frac{c_3(4n+1)}{3}+ \frac{c_5(4n+1)}{5}- \frac{c_7(4n+1)}{7}+ \dots \right).

If s is a multiple of 4,

 \delta'_{2s}(n)= \frac{(\frac{\pi}{2})^s}{(s-1)!}\left(n+\frac{s}4\right)^{s-1} \left( \frac{c_1(n+\frac{s}4)}{1^s}+ \frac{c_3(n+\frac{s}4)}{3^s}+
\frac{c_5(n+\frac{s}4)}{5^s}+ \dots \right).

If s is twice an odd number,

 \delta'_{2s}(n)= \frac{(\frac{\pi}{2})^s}{(s-1)!}\left(n+\frac{s}4\right)^{s-1} \left( \frac{c_1(2n+\frac{s}2)}{1^s}+ \frac{c_3(2n+\frac{s}2)}{3^s}+ \frac{c_5(2n+\frac{s}2)}{5^s}+ \dots \right).

If s is an odd number and s > 1,

 \delta'_{2s}(n)= \frac{(\frac{\pi}{2})^s}{(s-1)!}\left(n+\frac{s}4\right)^{s-1} \left( \frac{c_1(4n+s)}{1^s}- \frac{c_3(4n+s)}{3^s}+
\frac{c_5(4n+s)}{5^s}- \dots \right).


r'_2(n) &= \frac{\pi}{4} \left(\frac{c_1(4n+1)}{1}- \frac{c_3(4n+1)}{3}+ \frac{c_5(4n+1)}{5}- \frac{c_7(4n+1)}{7}+ \dots \right) \\
r'_4(n) &= \left(\tfrac{\pi}{2}\right)^2\left(n+\tfrac12\right) \left(\frac{c_1(2n+1)}{1}+\frac{c_3(2n+1)}{9}+ \frac{c_5(2n+1)}{25}+ \dots \right) \\
r'_6(n) &= \frac{(\tfrac{\pi}{2})^3}{2}\left(n+\tfrac34\right)^2 \left(\frac{c_1(4n+3)}{1}-\frac{c_3(4n+3)}{27}+ \frac{c_5(4n+3)}{125}-\dots \right)\\ 
r'_8(n) &= \frac{(\frac12\pi)^4}{6}(n+1)^3 \left( \frac{c_1(n+1)}{1}+ \frac{c_3(n+1)}{81}+ \frac{c_5(n+1)}{625}+ \dots \right) 



T_q(n) &=  c_q(1) + c_q(2) + \dots + c_q(n) \\
U_q(n) &=  T_q(n) +  \tfrac12\phi(q)

Then for s > 1,

\sigma_{-s}(1) + \cdots+ \sigma_{-s}(n) &= \zeta(s+1) \left(n+ \frac{T_2(n)}{2^{s+1}}+ \frac{T_3(n)}{3^{s+1}}+\frac{T_4(n)}{4^{s+1}} +\dots \right) \\
&= \zeta(s+1) \left( n+\tfrac12+ \frac{U_2(n)}{2^{s+1}}+ \frac{U_3(n)}{3^{s+1}}+ \frac{U_4(n)}{4^{s+1}} +\cdots \right)- \tfrac12\zeta(s) \\
d(1)+ \cdots+ d(n) &= - \frac{T_2(n)\log2}{2} - \frac{T_3(n)\log3}{3} - \frac{T_4(n)\log4}{4} - \cdots, \\
d(1)\log 1 + \cdots + d(n)\log n &= -\frac{T_2(n)(2\gamma\log2-\log^22)}{2} -\frac{T_3(n)(2\gamma\log3-\log^23)}{3} -\frac{T_4(n)(2\gamma\log4-\log^24)}{4} -\cdots, \\
r_2(1)+ \cdots+ r_2(n) &= \pi \left( n -\frac{T_3(n)}{3} +\frac{T_5(n)}{5} -\frac{T_7(n)}{7} +\cdots \right).

See also[edit]


  1. ^ Ramanujan, On Certain Trigonometric Sums ...

    These sums are obviously of great interest, and a few of their properties have been discussed already. But, so far as I know, they have never been considered from the point of view which I adopt in this paper; and I believe that all the results which it contains are new.

    (Papers, p. 179). In a footnote cites pp. 360–370 of the Dirichlet-Dedekind Vorlesungen über Zahlentheorie, 4th ed.
  2. ^ Nathanson, ch. 8
  3. ^ Hardy & Wright, Thms 65, 66
  4. ^ G. H. Hardy, P. V. Seshu Aiyar, & B. M. Wilson, notes to On certain trigonometrical sums ..., Ramanujan, Papers, p. 343
  5. ^ Schwarz & Spilken (1994) p.16
  6. ^ B. Berndt, commentary to On certain trigonometrical sums..., Ramanujan, Papers, p. 371
  7. ^ Knopfmacher, p. 196
  8. ^ Hardy & Wright, p. 243
  9. ^ Tóth, external links, eq. 6
  10. ^ Tóth, external links, eq. 17.
  11. ^ Tóth, external links, eq. 8.
  12. ^ B. Berndt, commentary to On certain trigonometrical sums..., Ramanujan, Papers, pp. 369–371
  13. ^ Ramanujan, On certain trigonometrical sums...

    The majority of my formulae are "elementary" in the technical sense of the word — they can (that is to say) be proved by a combination of processes involving only finite algebra and simple general theorems concerning infinite series

    (Papers, p. 179)
  14. ^ The theory of formal Dirichlet series is discussed in Hardy & Wright, § 17.6 and in Knopfmacher.
  15. ^ Knopfmacher, ch. 7, discusses Ramanujan expansions as a type of Fourier expansion in an inner product space which has the cq as an orthogonal basis.
  16. ^ Ramanujan, On Certain Arithmetical Functions
  17. ^ This is Jordan's totient function, Js(n).
  18. ^ Cf. Hardy & Wright, Thm. 329, which states that \;\frac{6}{\pi^2}<\frac{\sigma(n)\phi(n)}{n^2}<1.
  19. ^ Hardy, Ramanujan, p. 141
  20. ^ B. Berndt, commentary to On certain trigonometrical sums..., Ramanujan, Papers, p. 371
  21. ^ Ramanujan, On Certain Arithmetical Functions


  • Hardy, G. H. (1999), Ramanujan: Twelve Lectures on Subjects Suggested by his Life and Work, Providence RI: AMS / Chelsea, ISBN 978-0-8218-2023-0 
  • Nathanson, Melvyn B. (1996), Additive Number Theory: the Classical Bases, Graduate Texts in Mathematics 164, Springer-Verlag, Section A.7, ISBN 0-387-94656-X, Zbl 0859.11002 .
  • Ramanujan, Srinivasa (1918), "On Certain Trigonometric Sums and their Applications in the Theory of Numbers", Transactions of the Cambridge Philosophical Society 22 (15): 259–276  (pp. 179–199 of his Collected Papers)
  • Ramanujan, Srinivasa (1916), "On Certain Arithmetical Functions", Transactions of the Cambridge Philosophical Society 22 (9): 159–184  (pp. 136–163 of his Collected Papers)
  • Schwarz, Wolfgang; Spilker, Jürgen (1994), Arithmetical Functions. An introduction to elementary and analytic properties of arithmetic functions and to some of their almost-periodic properties, London Mathematical Society Lecture Note Series 184, Cambridge University Press, ISBN 0-521-42725-8, Zbl 0807.11001 

External links[edit]