Overview
In number theory, Ramanujan's sum, usually denoted c q (n), is a function of two positive integer variables q and n defined by the formula : c_q(n) = \sum_ 1 \le a \leq q \atop (a,q)=1 e^ 2 \pi i \tfrac a q n , where (a, q) = 1 means that a only takes on values coprime to q. Srinivasa Ramanujan mentioned the sums in a 1918 paper. 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.
Notation
For integers a and b, a\mid b is read "a divides b" and means that there is an integer c such that \frac b a = c. Similarly, a\nmid b is read "a does not divide b". The summation symbol : \sum_ d\,\mid\,m f(d) 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.
Trigonometry
These formulas come from the definition, Euler's formula e^ ix = \cos x + i \sin x, and elementary trigonometric identities. : \begin align 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 \\ \end align and so on (, , , ,.., ,...). c q (n) is always an integer.
Kluyver
Let \zeta_q=e^ \frac 2\pi i q . Then is a root of the equation . Each of its powers, : \zeta_q, \zeta_q^2, \ldots, \zeta_q^ q-1 , \zeta_q^q = \zeta_q^0 =1 is also a root. Therefore, since there are q of them, they are all of the roots. The numbers \zeta_q^n where 1 ≤ n ≤ q are called the q-th roots of unity. is called a primitive q-th root of unity because the smallest value of n that makes \zeta_q^n =1 is q. The other primitive q-th roots of unity are the numbers \zeta_q^a where (a, q) = 1. Therefore, there are φ(q) primitive q-th roots of unity. Thus, the Ramanujan sum c q (n) is the sum of the n-th powers of the primitive q-th roots of unity. It is a fact that the powers of are precisely the primitive roots for all the divisors of q. Example. Let q = 12.
Then : \zeta_ 12 , \zeta_ 12 ^5, \zeta_ 12 ^7, and \zeta_ 12 ^ 11 are the primitive twelfth roots of unity, : \zeta_ 12 ^2 and \zeta_ 12 ^ 10 are the primitive sixth roots of unity, : \zeta_ 12 ^3 = i and \zeta_ 12 ^9 = -i are the primitive fourth roots of unity, : \zeta_ 12 ^4 and \zeta_ 12 ^8 are the primitive third roots of unity, : \zeta_ 12 ^6 = -1 is the primitive second root of unity, and : \zeta_ 12 ^ 12 = 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 x q − 1 = (x − 1)(x q−1 + x q−2 + ... + x + 1) that : \eta_q(n) = \begin cases 0 & q\nmid n\\ q & q\mid n\\ \end cases 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. This shows that c q (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
It is easily shown from the definition that c q (n) is multiplicative when considered as a function of q for a fixed value of n: 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) = \begin cases -1 &\mbox if p\nmid n\\ \phi(p)&\mbox if p\mid n\\ \end cases , and if p k is a prime power where k > 1, : c_ p^k (n) = \begin cases 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\\ \end cases . 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. The equivalence of it and Ramanujan's sum is due to Hölder.
Other properties of c q (n)
For all positive integers q, : \begin align c_1(q) &= 1 \\ c_q(1) &= \mu(q) \\ c_q(q) &= \phi(q) \\ c_q(m) &= c_q(n) && \text for m \equiv n \pmod q \\ \end align For a fixed value of q the absolute value of the sequence \ c_q(1), c_q(2), \ldots\ is bounded by φ(q), and for a fixed value of n the absolute value of the sequence \ c_1(n), c_2(n), \ldots\ is bounded by n. If q > 1 : \sum_ n=a ^ a+q-1 c_q(n)=0. Let m 1 , m 2 > 0, m = lcm(m 1 , m 2 ). Then 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 : \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 : \sum_\stackrel 1\le k\le n \gcd(k,n)=1 c_n(k-a) = \mu(n)c_n(a), due to Cohen.
Ramanujan expansions
If 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 , is called a Ramanujan expansion of . 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). The expansion of the zero function depends on a result from the analytic theory of prime numbers, namely that the series : \sum_ n=1 ^\infty\frac \mu(n) n converges to 0, and the results for and depend on theorems in an earlier paper. All the formulas in this section are from Ramanujan's 1918 paper.
Generating functions
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 , , ... where 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 , , ... where 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 . The polynomial with Ramanujan sum's as coefficients can be expressed with cyclotomic polynomial : \sum_ n=1 ^q c_q(n) x^ n-1 = (x^q - 1) \frac \Phi_q'(x) \Phi_q(x) = \Phi_q'(x) \prod_ \begin array c d \mid q \\ -4pt d \neq q\end array \Phi_d(x)
σ k (n)
is the divisor function (i.e. the sum of the -th powers of the divisors of , including 1 and ). , the number of divisors of , is usually written and , the sum of the divisors of , is usually written . If , : \begin align \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 +\cdots\right) \\ \sigma_ -s (n) &=\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 +\cdots\right) \end align Setting gives : \sigma(n)= \frac \pi^2 6 n \left(\frac c_1(n) 1 + \frac c_2(n) 4 + \frac c_3(n) 9 + \cdots \right). If the Riemann hypothesis is true, and -\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 + \cdots \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 + \cdots \right).
d(n)
is the number of divisors of , including 1 and itself. : \begin align -d(n) &= \frac \log 1 1 c_1(n)+ \frac \log 2 2 c_2(n)+ \frac \log 3 3 c_3(n)+ \cdots \\ -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 \end align where is the Euler–Mascheroni constant.
φ(n)
Euler's totient function is the number of positive integers less than and coprime to . Ramanujan defines a generalization of it, if : n=p_1^ a_1 p_2^ a_2 p_3^ a_3 \cdots is the prime factorization of , and is a complex number, let : \varphi_s(n)=n^s(1-p_1^ -s )(1-p_2^ -s )(1-p_3^ -s )\cdots, so that is Euler's function. He proves that : \frac \mu(n)n^s \varphi_s(n)\zeta(s) = \sum_ \nu=1 ^\infty \frac \mu(n\nu) \nu^s and uses this to show that : \frac \varphi_s(n)\zeta(s+1) n^s =\frac \mu(1)c_1(n) \varphi_ s+1 (1) +\frac \mu(2)c_2(n) \varphi_ s+1 (2) +\frac \mu(3)c_3(n) \varphi_ s+1 (3) +\cdots. Letting , : \varphi(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) -\cdots \right). Note that the constant is the inverse of the one in the formula for .
Λ(n)
Von Mangoldt's function unless is a power of a prime number, in which case it is the natural logarithm . : -\Lambda(m) = c_m(1)+ \frac 1 2 c_m(2)+ \frac13c_m(3)+\cdots
Zero
For all , : 0= c_1(n)+ \frac12c_2(n)+ \frac13c_3(n)+ \cdots. This is equivalent to the prime number theorem.
r 2s (n) (sums of squares)
is the number of ways of representing as the sum of squares, counting different orders and signs as different (e.g., , as .) Ramanujan defines a function and references a paper in which he proved that for . For he shows that is a good approximation to . has a special formula: : \delta_2(n)= \pi \left(\frac c_1(n) 1 - \frac c_3(n) 3 + \frac c_5(n) 5 - \cdots \right).
In the following formulas the signs repeat with a period of 4. : \begin align \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 + \cdots \right) && s \equiv 0 \pmod 4 \\ 6pt \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 + \cdots \right) && s \equiv 2 \pmod 4 \\ 6pt \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 + \cdots \right) && s \equiv 1 \pmod 4 \text and s > 1 \\ 6pt \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 + \cdots \right) && s \equiv 3 \pmod 4 \\ \end align and therefore, : \begin align 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) \\ 6pt 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) \\ 6pt 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) \\ 6pt 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) \end align
r′ 2s (n) (sums of triangles)
r'_ 2s (n) is the number of ways can be represented as the sum of triangular numbers (i.e. the numbers 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4, 15, ...; the -th triangular number is given by the formula .) 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 \delta'_ 2s (n) such that r'_ 2s (n) = \delta'_ 2s (n) for , and that for , \delta'_ 2s (n) is a good approximation to r'_ 2s (n). Again, 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 + \cdots \right).
If is a multiple of 4, : \begin align \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 + \cdots \right) && s \equiv 0 \pmod 4 \\ 6pt \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 + \cdots \right) && s \equiv 2 \pmod 4 \\ 6pt \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 - \cdots \right) && s \equiv 1 \pmod 2 \text and s >1 \end align Therefore, : \begin align 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 + \cdots \right) \\ 6pt r'_4(n) &= \left(\frac \pi 2 \right)^2\left(n+\frac12\right) \left(\frac c_1(2n+1) 1 +\frac c_3(2n+1) 9 + \frac c_5(2n+1) 25 + \cdots \right) \\ 6pt r'_6(n) &= \frac (\frac \pi 2 )^3 2 \left(n+\frac34\right)^2 \left(\frac c_1(4n+3) 1 -\frac c_3(4n+3) 27 + \frac c_5(4n+3) 125 -\cdots \right)\\ 6pt r'_8(n) &= \frac (\frac \pi 2 )^4 6 (n+1)^3 \left(\frac c_1(n+1) 1 + \frac c_3(n+1) 81 + \frac c_5(n+1) 625 + \cdots \right) \end align
Sums
Let : \begin align T_q(n) &= c_q(1) + c_q(2) + \cdots + c_q(n) \\ U_q(n) &= T_q(n) + \tfrac12\phi(q) \end align Then for , : \begin align \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 +\cdots \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) \end align
See also
*Gaussian period *Kloosterman sum
References
* * * *. * * (pp. 179–199 of his Collected Papers) * (pp. 136–163 of his Collected Papers) * *