The sums of primitive roots are always whole

A root of unity of order $q$ is one that returns to $1$ after exactly $q$ multiplications and no fewer. Of the $q$ solutions of $z^q = 1$, the ones of order exactly $q$ are the primitive ones: $e^{2\pi i a/q}$ with $a$ sharing no factor with $q$. There are $\varphi(q)$ of them, Euler’s totient.

The polygon an equation forces found that the primitive $q$-th roots add up to a very small number: $1$, $-1$ or $0$, according to the Möbius function of $q$. Here is the generalisation Srinivasa Ramanujan wrote down in 1918. Raise every primitive $q$-th root to the same power $n$ before adding:

$$c_q(n) = \sum_{\substack{1 \le a \le q \\ \gcd(a, q) = 1}} e^{2\pi i a n/q}.$$

Each term is a point on the unit circle. There is no evident reason for the sum to be anything in particular.

And yet it is always a whole number. For $q = 15$ the eight primitive roots, raised to the first power, trace an irregular octagonal walk that ends at $1$. Raised to the third power they end at $-2$; to the fifth, at $-4$; to the fifteenth, all eight land on $1$ and the walk runs straight out to $8$. The sums $c_q(n)$ are Ramanujan’s sums, and this essay is about why they are whole, what formula they obey, and what Ramanujan used them for.

Why the sum cannot be anything but whole #

The reason is the one the sums that obey a smaller equation gave for Gauss’s periods, and Ramanujan’s sum is in fact the coarsest period of all.

Raising a root of unity to a power $g$ that shares no factor with $q$ sends primitive roots to primitive roots — it multiplies each exponent $a$ by $g$, and $ga$ still shares no factor with $q$ — and it sends distinct roots to distinct roots. So it permutes the set of primitive $q$-th roots. The same map applied to the sum permutes its terms, and leaves the sum unchanged. The sum is therefore fixed by every symmetry of the field generated by a primitive $q$-th root, and a number in that field fixed by every symmetry is rational.

It is also a sum of roots of unity, and so an algebraic integer; a rational algebraic integer is a whole number. The same argument applies with the exponent $an$ in place of $a$, for any fixed $n$, so every $c_q(n)$ is whole. The figures check it independently: each sum is added numerically and required to lie within a hundred-millionth of an integer, with an imaginary part that vanishes because the primitive roots come in conjugate pairs.

The smallest cases can be done in the head. The primitive fourth roots are $i$ and $-i$, and they add to $0$; squared, both become $-1$, and the sum is $-2$; raised to the fourth power, both become $1$, and the sum is $2$. The primitive sixth roots are $\tfrac12 \pm \tfrac{\sqrt3}{2} i$, whose imaginary parts cancel and whose real parts add to $1$; squared, they become the primitive cube roots $-\tfrac12 \pm \tfrac{\sqrt3}{2}i$, which add to $-1$. In each case the irrational parts — $i$, $\sqrt 3$ — are paired off by complex conjugation or by a larger symmetry, and only a whole number is left.

In the language of periods, $c_q(n)$ is the single period that uses the whole group — every primitive root in one coset — evaluated at the root $e^{2\pi i n/q}$. A period of index one has an equation of degree one, and an equation of degree one with whole-number coefficients has a whole-number root.

A prime, where there are only two answers #

When $q$ is a prime $p$, every root except $1$ is primitive, and there are only two cases.

If $p$ does not divide $n$, raising to the $n$-th power shuffles the $p - 1$ non-trivial roots among themselves, and their sum is always the same: the full sum of all $p$ roots is $0$, so the non-trivial ones add to $-1$. If $p$ divides $n$, every root is sent to $1$ and the sum is $p - 1$. So

$$c_p(n) = \begin{cases} -1 & p \nmid n, \\ p - 1 & p \mid n. \end{cases}$$

The walk for a prime is the regular polygon walked out of order: raising to the power $2$ visits the vertices of the heptagon two at a time, raising to $3$ three at a time, and every such order closes up one step short of the origin.

The table, and the formula behind it #

For a composite $q$ the values are more varied, but the pattern is visible in a table.

Three things stand out, and all three are forced.

Each row is periodic in $n$ with period $q$, because $e^{2\pi i a n/q}$ depends on $n$ only modulo $q$.

Each row reaches its maximum $\varphi(q)$ exactly at the multiples of $q$, where every term is $1$.

Each row depends on $n$ only through $\gcd(n, q)$. Row $12$ reads $0, 2, 0, -2, 0, -4, 0, -2, 0, 2, 0, 4$ and then repeats; the value at $n = 10$ equals the value at $n = 2$ because both share exactly $2$ with $12$. The reason is the permutation argument once more: multiplying $n$ by a number coprime to $q$ only permutes the terms of the sum.

The closed form, found by Robert von Sterneck in 1902 and independently by Otto Hölder, writes the value directly. With $g = \gcd(n, q)$,

$$c_q(n) = \mu\!\left(\frac{q}{g}\right) \frac{\varphi(q)}{\varphi(q/g)}.$$

Every entry in every figure is checked against it. For $q = 15$ and $n = 6$, $g = 3$, $q/g = 5$, $\mu(5) = -1$ and $\varphi(15)/\varphi(5) = 8/4 = 2$, so $c_{15}(6) = -2$ — the walk in the first figure that ends two units to the left of the origin.

A second formula, a sum over the common divisors, shows the structure differently:

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

It comes from the fact that the sum of all $q$-th roots raised to the $n$-th power is $q$ if $q$ divides $n$ and $0$ otherwise — the filter that every third coefficient used to pick out terms of a polynomial — combined with Möbius inversion to strip off the roots of smaller order.

Thirty, built from two, three and five #

When $q$ has several prime factors, the sum splits along them.

The Ramanujan sum is multiplicative in $q$: if $q$ and $r$ share no factor, then $c_{qr}(n) = c_q(n)\, c_r(n)$ for every $n$. The reason is the Chinese remainder theorem. A primitive $qr$-th root of unity is, uniquely, a product of a primitive $q$-th root and a primitive $r$-th root, so the sum over primitive $qr$-th roots is the product of the two smaller sums.

So $c_{30}$ is a product of three prime cases, each of which takes only two values. For $n = 5$: $c_2(5) = -1$ since $2 \nmid 5$, $c_3(5) = -1$ since $3 \nmid 5$, and $c_5(5) = 4$ since $5 \mid 5$; the product is $4$, and the eight-step walk for $n = 5$ ends four units to the right. For $n = 6$, $c_2(6) = 1$, $c_3(6) = 2$, $c_5(6) = -1$, and the product is $-2$. Every value in the table is a product of numbers of the form $-1$ or $p - 1$, with the correction for prime powers that von Sterneck’s formula carries: $c_{p^k}(n)$ is $0$ unless $p^{k-1}$ divides $n$, which is why the rows for $4$, $8$ and $9$ are mostly empty.

That is also why the sums are so much smaller than they might be. Eight unit vectors could add to anything up to $8$ in length; for $q = 30$ they reach that length only when $15$ divides $n$ — $+8$ at the multiples of $30$, $-8$ at the odd multiples of $15$ — and otherwise stay within $4$ of the origin. The primitive roots are spread so evenly round the circle that most of them cancel, and what survives is decided prime by prime.

The rows are orthogonal, like sines and cosines #

The table’s rows are more than periodic. Take two different rows, $q$ and $r$, multiply them entry by entry over a common period — any multiple of both $q$ and $r$ — and add. The answer is exactly $0$.

$$\sum_{n=1}^{L} c_q(n)\, c_r(n) = 0 \qquad (q \ne r,\ q \mid L,\ r \mid L).$$

The figure’s table is checked this way for every pair of rows up to twelve, over a period of $27{,}720$. When $q = r$ the same sum is $L\,\varphi(q)$, never zero. That is the defining property of an orthogonal family, the property the sines and cosines of a Fourier series have: $\sin(jx)$ and $\sin(kx)$ multiplied and integrated over a period give nought unless $j = k$.

The analogy is exact in one direction. A function of $n$ that depends only on $n$ modulo $q$ can be written as a combination of the rows $c_d(n)$ for the divisors $d$ of $q$ — provided it depends on $n$ only through $\gcd(n, q)$, the functions called even modulo $q$. The Ramanujan sums are the Fourier basis for such functions, with divisibility playing the part of frequency: a row $c_d$ is a “tone” that repeats every $d$ steps.

Rebuilding the sum of divisors #

Ramanujan’s paper of 1918 used the analogy in the other direction. An arithmetic function like $\sigma(n)$, the sum of the divisors of $n$, is not periodic at all. But Ramanujan found that it can still be expanded in the $c_q(n)$, exactly as a non-periodic signal is expanded in sines of every frequency:

$$\frac{\sigma(n)}{n} = \frac{\pi^2}{6} \sum_{q=1}^{\infty} \frac{c_q(n)}{q^2}.$$

For $n = 7$, a prime, the terms are $c_q(7) = \mu(q)$ unless $7$ divides $q$; the series is $\frac{\pi^2}{6}\left(1 - \frac14 - \frac19 - \dots\right)$ with a correction at every multiple of $7$, and it settles on $\sigma(7)/7 = 8/7$. For $n = 6$ it settles on $2$ — six is perfect, so its divisors add to twice itself — and for $n = 60$ on $168/60 = 2.8$.

The factor $\pi^2/6$ is $\sum 1/q^2$, the value of $\zeta(2)$ that sums of powers, read off a staircase places among the even zeta values, and it enters because the average of $\sigma(n)/n$ over all $n$ is exactly that. The Ramanujan sums supply the deviation of each particular $n$ from the average. A function defined by divisibility is being written as a superposition of sums of roots of unity, each of which encodes one divisibility test.

The expansion also makes the special numbers visible. A number whose divisors add to exactly twice itself, like $6$ or $28$, has $\sigma(n)/n = 2$, so its Ramanujan series sums to exactly $2$; the numbers whose divisors add to three times themselves, which divisors that add to three times the number catalogued, have series summing to $3$. The series does not make such numbers easier to find — each term needs $\gcd(n, q)$, and so knowledge of the factors of $n$ — but it says in what sense being perfect is a statement about how $n$ sits against every modulus at once: each term records whether $q$, or a part of it, divides $n$, and the weights $1/q^2$ make the small moduli count most.

Ramanujan gave several such expansions in the same paper, among them one for the number of divisors, $d(n) = -\sum_q \frac{\ln q}{q} c_q(n)$, which converges only conditionally, and one for the number of ways of writing $n$ as a sum of two squares.

A sum that is nought, and the primes #

The most striking of Ramanujan’s identities is the simplest to state:

$$\sum_{q=1}^{\infty} \frac{c_q(n)}{q} = 0 \qquad \text{for every } n.$$

For $n = 1$ the terms are $\mu(q)/q$, and the statement becomes

$$\sum_{q=1}^{\infty} \frac{\mu(q)}{q} = 0,$$

which Edmund Landau showed in 1899 to be equivalent to the prime number theorem — the statement, followed in counting what has no formula, that the primes up to $x$ number about $x/\ln x$. The equivalence runs through the product Euler wrote for the zeta function, the sieve written as a product: the reciprocal of that product is the series $\sum \mu(q)/q^s$, and its value at $s = 1$ is the sum in the figure. The figure’s curves approach nought slowly and irregularly, and the slowness is honest: the rate at which $\sum \mu(q)/q$ approaches its limit is controlled by the zeros of the Riemann zeta function, and an estimate good enough to settle the Riemann hypothesis would be a statement about exactly this kind of curve.

So a sum of roots of unity, weighted by $1/q$, contains the distribution of the primes. That is the surprising connection Ramanujan’s sums make, and it is not a coincidence of notation: the Möbius function is the sum of the primitive roots, and the Möbius function is the device by which counting primes is turned into analysis.

Where the sums are used now #

The sums found their largest use in the circle method of Hardy, Littlewood and Ramanujan himself, the technique for counting the ways of writing a number as a sum of primes or of powers.

When the method predicts how many ways a large even number $N$ can be written as a sum of two primes, the prediction has two factors. One is smooth, about $N/(\ln N)^2$. The other, the singular series, adjusts for divisibility: it is larger when $N$ has many small prime factors, because then fewer residue classes are ruled out. The singular series is a sum over $q$ of Ramanujan’s sums $c_q(N)$ weighted by the square of $\mu(q)/\varphi(q)$ — one term per modulus, each asking how $N$ sits relative to the multiples of $q$. The predicted counts match computation to high accuracy for every even number anyone has checked, though the prediction itself remains unproved.

In signal processing, the rows of the table have been used since the 2010s as a basis for detecting hidden periods in integer-valued sequences, since they are integer-valued and orthogonal and a period of $q$ shows up as energy in the rows $c_d$ with $d \mid q$.

What the walks and tables cannot show #

The integrality is checked, then proved. Each drawn sum is computed as a sum of floating-point cosines and required to be within $10^{-8}$ of a whole number; each also agrees with von Sterneck’s closed form. The proof is the permutation argument, which the figures do not show.

The expansions are drawn only to finitely many terms. The partial sums of $\sigma(n)/n$ at sixty terms are within a few thousandths of their targets, and the partial sums of $c_q(n)/q$ at three thousand terms are within a hundredth of nought. Neither is a proof of convergence. Ramanujan’s expansion of $\sigma(n)/n$ converges absolutely and the proof is short; the one for $\sum c_q(n)/q$ lies at the depth of the prime number theorem, and the figure is only a picture of it.

The analogy with Fourier series is exact only for functions that are even modulo $q$. For general arithmetic functions, when a Ramanujan expansion exists, whether it is unique is a subtle question, and some functions have expansions of different kinds that converge to the same values.

Still open: how fast the Möbius sums settle #

The sum $\sum_{q \le Q} \mu(q)/q$ tends to nought, and the prime number theorem is equivalent to that. How fast it tends to nought is not known. If the Riemann hypothesis is true, the partial sums shrink faster than $Q^{-1/2+\varepsilon}$ for every positive $\varepsilon$; the best unconditional bound, from the zero-free region of the zeta function, is much weaker: it shrinks like $\exp\big(-c(\ln Q)^{3/5}\big)$ up to smaller factors — faster than any power of $1/\ln Q$, but slower than any power of $1/Q$.

The same holds for the unweighted sums $M(Q) = \sum_{q \le Q} \mu(q)$, Mertens’s function, which how evenly the fractions spread met as the measure of how evenly the Farey fractions fill the interval: the Riemann hypothesis is equivalent to $M(Q)$ growing no faster than $Q^{1/2 + \varepsilon}$. Franz Mertens conjectured in 1897 that $|M(Q)| < \sqrt Q$ always; Andrew Odlyzko and Herman te Riele disproved that in 1985 without exhibiting a counterexample, and the smallest $Q$ where it fails is still unknown. The curves in the last figure are the gentlest possible view of the same unknown.

A sum that forgets everything but a divisor #

The habit worth keeping is to ask what a sum is invariant under.

Eight points on a circle, added, could land anywhere. Because they are all the primitive roots of one order, every symmetry of the number system shuffles them among themselves, and the sum has nowhere to go but the whole numbers. Raising them to a power $n$ keeps that property and adds one more: the answer can see only what $n$ shares with $q$. Invariance under shuffling made the sums whole; invariance under coprime scaling made them depend only on a divisor; and those two facts together are what let Ramanujan write the sum of divisors, and the distribution of the primes, in terms of roots of unity.