Ramanujan's sum

Not to be confused with Ramanujan summation.

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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): 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. 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 b = ac. 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.

Formulas for c_q(n)

Trigonometry

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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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 ( A000012,  A033999,  A099837,  A176742,..,  A100051,...) They show that c_q(n) is always real.

Kluyver

Let $\zeta_q=e^{\frac{2\pi i}{q}}.$ Then ζ_q is a root of the equation x^q − 1 = 0. Each of its powers ζ_q, ζ_q², ... ζ_q^q = ζ_q⁰ = 1 is also a root. Therefore, since there are q of them, they are all of the roots. The numbers ζ_qⁿ where 1 ≤ n ≤ q 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 ζ_qⁿ = 1 is q. The other primitive q-th roots of are the numbers ζ_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 ζ_q are precisely the primitive roots for all the divisors of q.

Example. Let q = 12. Then

ζ₁₂, ζ₁₂⁵, ζ₁₂⁷, and ζ₁₂¹¹ are the primitive twelfth roots of unity,

ζ₁₂² and ζ₁₂¹⁰ are the primitive sixth roots of unity,

ζ₁₂³ = i and ζ₁₂⁹ = −i are the primitive fourth roots of unity,

ζ₁₂⁴ and ζ₁₂⁸ are the primitive third roots of unity,

ζ₁₂⁶ = −1 is the primitive second root of unity, and

ζ₁₂¹² = 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&\;\mbox{ if }q\nmid n\\ q&\;\mbox{ if }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,

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

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

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

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

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

c₁(n), c₂(n), ... is bounded by n.

If q > 1

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

Let m₁, m₂ > 0, m = lcm(m₁, m₂). Then Ramanujan's sums satisfy an orthogonality property:

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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 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 a_k ∈ C, is called a Ramanujan expansion 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).

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 r(n) and r′(n) 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 c_q(1), c_q(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 c₁(n), c₂(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)

σ_k(n) is the divisor function (i.e. the sum of the k-th powers of the divisors of n, including 1 and n). σ₀(n), the number of divisors of n, is usually written d(n) and σ₁(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)$

and

$\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}}+\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 Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): -\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)

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

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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)+ \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 \end{align}

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

φ(n)

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

$n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots$

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

$\phi_s(n)=n^s(1-p_1^{-s})(1-p_2^{-s})(1-p_3^{-s})\cdots,$

so that φ₁(n) = φ(n) is Euler's function.

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

$\frac{\phi_s(n)\zeta(s+1)}{n^s}=\frac{\mu(1)c_1(n)}{\phi_{s+1}(1)}+\frac{\mu(2)c_2(n)}{\phi_{s+1}(2)}+\frac{\mu(3)c_3(n)}{\phi_{s+1}(3)}+\dots.$

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 of the one in the formula for σ(n).

Λ(n)

Von Mangoldt's function Λ(n) = 0 unless n = p^k 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$

Zero

For all n > 0,

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

This is equivalent to the prime number theorem.

r_2s(n) (sums of squares)

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

Ramanujan defines a function δ_2s(n) and references a paper in which he proved that r_2s(n) = δ_2s(n) for s = 1, 2, 3, and 4. For s > 4 he shows that δ_2s(n) is a good approximation to r_2s(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,

$\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 ≡ 3 (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)$

and therefore,

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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) \\ 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) \end{align}

r′_2s(n) (sums of triangles)

r′_2s(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 r′_2s(n) = δ′_2s(n) for s = 1, 2, 3, and 4, and that for s > 4, δ′_2s(n) is a good approximation to r′_2s(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).$

Therefore,

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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}+ \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) \end{align}

Sums

Let

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \begin{align} T_q(n) &= c_q(1) + c_q(2) + \dots + c_q(n) \\ U_q(n) &= T_q(n) + \tfrac12\phi(q) \end{align}

Then for s > 1,

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \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}} +\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). \end{align}

See also

• Gaussian period
• Kloosterman sum

References

• .

• (pp. 179–199 of his Collected Papers)

• (pp. 136–163 of his Collected Papers)