A sum that never leaves its circle

One sum squared two ways drew the quadratic Gauss sum as a walk of roots of unity, $p$ steps of length one, and found that it ends exactly $\sqrt p$ from where it started — not about $\sqrt p$, as a random walk would, but exactly. Give or take twice the square root found the same square root in a different place: a cubic curve over the integers modulo $p$ has $p + 1$ points give or take at most $2\sqrt p$, Hasse’s theorem. Both are sums of terms that look independent and are not, held in by a square root that the arithmetic of the finite field imposes.

The sum this essay draws is the next one in that family, and the most famous. For a prime $p$ and whole numbers $a$ and $b$ not divisible by $p$, the Kloosterman sum is

$$K(a, b;\, p) = \sum_{x = 1}^{p - 1} e^{2\pi i (ax + b\bar x)/p},$$

where $\bar x$ is the inverse of $x$ modulo $p$, the residue with $x\bar x \equiv 1$. Hendrik Kloosterman introduced it in 1926 to count the ways of writing a number as $ax^2 + by^2 + cz^2 + dt^2$, and it has turned up since in the theory of modular forms, in the spectral theory of the hyperbolic plane, and in the distribution of primes. It is not given by a formula. What is known about it is a bound, a distribution, and a conjecture.

A thousand steps that go twenty #

The hero adds the 1,008 terms of $K(1, 1; 1009)$ one at a time and draws the running total. Each term is a unit vector pointing at angle $2\pi(x + \bar x)/p$, and the inverse $\bar x$ jumps around the residues with no visible relation to $x$: the inverse of 2 is 505, of 3 is 673, of 4 is 757. The path wanders accordingly, making the fern-like figure in the middle, and ends at $20.2558$ on the real axis. A path of 1,008 unit steps could have gone as far as 1,008. A random one would typically end about $\sqrt{1008} \approx 32$ away, and occasionally much further. This one never strays further than 24.6 from the origin, and its end lies well inside the dashed circle of radius $2\sqrt{1009} = 63.53$.

Two symmetries shape the path. The term for $x$ and the term for $\bar x$ are equal, since swapping $x$ and its inverse leaves $x + \bar x$ unchanged; and the term for $-x$ is the complex conjugate of the term for $x$, since $-x$ has inverse $-\bar x$. So the steps come in conjugate pairs and the total is real; better, the last $k$ steps add up to the conjugate of the first $k$, so the second half of the path is the first half reflected in the vertical line through half the total, which is the left–right symmetry the drawing shows. The sum is $2\sqrt p \cos\theta$ for an angle $\theta$, here $71.41°$, and Weil’s theorem is the statement that such an angle exists at all — that $|K| \le 2\sqrt p$.

Weil’s bound, everywhere it can be checked #

André Weil proved the bound in 1948, as a consequence of his proof of the Riemann hypothesis for curves over finite fields. The proof is far from elementary: it identifies $K(a, b; p)$ with minus the sum of two numbers of absolute value $\sqrt p$, the two eigenvalues of Frobenius on a certain piece of the cohomology of a curve, so that $K = -(\alpha + \bar\alpha)$ with $|\alpha| = \sqrt p$ and the bound is the triangle inequality. Elementary methods give much weaker bounds — $p^{3/4}$ is the best Kloosterman himself reached — and the gap between $p^{3/4}$ and $\sqrt p$ is the gap between counting and geometry.

The figure checks it as far as patience allows: every $a$ for every odd prime up to 1,000, 75,958 sums. None exceeds $2\sqrt p$. The largest creep up towards it as $p$ grows — 0.99 of the bound and more for most primes beyond a few hundred — because with $p - 1$ values of $a$ to choose from, some angle $\theta_a$ lands close to 0 or $180°$. So the constant 2 cannot be lowered. Weil’s bound is not merely true; it is the truth about the largest values, and it is reached in the limit.

Every coefficient at one prime #

Fix the prime and vary $a$. The figure computes all 10,006 sums $K(a, 1; 10007)$, scales each by $\sqrt p$ so that Weil’s bound becomes the interval $[-2, 2]$, and draws the histogram. It is not a bell. It is a semicircle — the density $\sqrt{4 - x^2}/2\pi$, highest in the middle and falling to nought exactly at $\pm 2$ — and the largest value is 1.9988.

The dashed curve is what chance would give: a sum of 10,006 random signs $\pm 1$, scaled the same way, so that it has the same mean square as the Kloosterman sums. It is a bell, the central limit theorem’s bell, taller in the middle and spilling past $\pm 2$ in five trials of every hundred. The Kloosterman sums have no tail at all. They are confined to the interval, and instead of thinning towards its edges they pile up there, as if pressed against a wall. The difference between a bell and a semicircle is the difference between noise and noise with a hidden constraint.

Nicholas Katz proved in 1988 that the semicircle is the limit: as $p$ grows, the angles $\theta_a$ for $a = 1, \ldots, p - 1$ become distributed by the Sato–Tate law $\tfrac{2}{\pi}\sin^2\theta\,d\theta$, which is exactly what makes $2\cos\theta$ semicircular. The law is the distribution of the trace of a random rotation of the three-sphere — a random element of the group $\mathrm{SU}(2)$ chosen uniformly — and Katz’s proof shows that the Frobenius eigenvalues of the curves behind the sums behave, collectively, like a random element of that group.

Moments that count non-crossing pairings #

A distribution is pinned down by its moments, and the semicircle’s are the Catalan numbers: the average of $x^{2k}$ over the semicircle on $[-2, 2]$ is $C_k = 1, 2, 5, 14, 42, \ldots$ The figure computes the averages of the 2nd to 10th powers of $K/\sqrt p$ over all $a$ at three primes. At $p = 101$ they are already 1.00, 1.99, 5.01, 14.24 and 43.36; at $p = 10{,}007$ they are 1.0000, 1.9999, 5.0020, 14.035 and 42.27.

The first two are not approximations. Expanding the square and fourth power of the sum and using the orthogonality of the characters of $\mathbb{Z}/p$ gives exact identities,

$$\sum_{a=1}^{p-1} K(a, 1; p)^2 = p^2 - p - 1, \qquad \sum_{a=1}^{p-1} K(a, 1; p)^4 = 2p^3 - 3p^2 - 3p - 1,$$

and the figure checks both at each prime. Divided by $(p - 1)p$ and $(p - 1)p^2$ they tend to 1 and 2. The higher moments need Katz’s theorem.

The first identity has a one-line explanation that is worth having. As a function of $a$, the sum $K(a, 1; p)$ is the discrete Fourier transform of the function $x \mapsto e^{2\pi i \bar x/p}$, which has absolute value one at each of the $p - 1$ nonzero residues and is nought at $x = 0$. Parseval’s identity says that the squares of a transform add up to $p$ times the squares of the function, so $\sum_{a=0}^{p-1} K(a, 1; p)^2 = p(p - 1)$. The term $a = 0$ is $\sum e^{2\pi i \bar x/p}$, a sum of all the nontrivial $p$-th roots of unity in another order, which is $-1$; taking away its square leaves $p^2 - p - 1$. The fourth moment needs a little more counting — the number of solutions of $x_1 + x_2 = x_3 + x_4$ with the same equation for the inverses — but it is the same kind of argument, and it is where the elementary theory ends.

The appearance of the Catalan numbers is the surprising connection. They count, among other things, the paths that never go wrong and the ways of pairing $2k$ points on a line with arcs that do not cross; and expanding $\left(\sum e^{i\phi_x}\right)^{2k}$ and averaging, the terms that survive are exactly those where the $2k$ factors cancel in pairs, with the arithmetic of the inverses forbidding the pairings that cross. The same numbers, for the same reason, are the moments of the eigenvalues of a large random symmetric matrix, whose density is also a semicircle — the Wigner law that eigenvalues that keep their distance drew. A sum over a finite field and the spectrum of a random matrix share a distribution, and the shared distribution is a count of non-crossing pairings.

How far moments alone can reach #

The two exact identities are worth more than a check on the computation, because they already contain a bound — and the bound they contain is Kloosterman’s. Every term in the sum of fourth powers is positive, so no single term can exceed the whole:

$$K(a, 1; p)^4 \le \sum_{a'} K(a', 1; p)^4 = 2p^3 - 3p^2 - 3p - 1 < 2p^3,$$

which gives $|K| < 2^{1/4} p^{3/4}$, about $1.19\,p^{3/4}$. That is the exponent Kloosterman reached in 1926 by a different route, and here it falls out of one line of algebra about fourth powers. The second moment does worse — it gives only $|K| < p$, no better than the trivial count of terms — and each higher moment does better: if the $2k$-th moment were known to be about $C_k\,p^{k+1}$, the same argument would give $|K|$ at most about $p^{1/2 + 1/(2k)}$, creeping down towards $\sqrt p$ as $k$ grows.

That is the honest limit of averaging. Moments say what most of the sums do — the second moment says that the typical sum has size about $\sqrt p$, as a random walk of $p$ steps would, in the way a walk that comes home measured for the walks on a line — but they cannot rule out a single sum being much larger than the rest, because one exceptional value contributes only $1/(p-1)$ of the average. To get $2\sqrt p$ for every $a$ requires knowing all the moments exactly at once, which is what Weil’s geometry provides and no finite collection of identities can. The semicircle and the bound are two faces of one theorem: the bound says the support is $[-2, 2]$, and the moments say how the mass is spread inside it.

The same contrast runs through the other square-root sums of this family. The slope a Gauss sum leaves behind and the quadratic Gauss sum of the opening are evaluated exactly, because a quadratic phase can be completed and squared; the Kloosterman phase $ax + b\bar x$ cannot, which is why its sum has a law rather than a value.

One sum through every prime #

Katz’s theorem varies $a$ at a fixed prime. The natural question goes the other way: fix the sum, $K(1, 1; p)$, and let the prime vary. The figure computes it for every odd prime up to 30,000, 3,244 primes, and the histogram looks like the same semicircle, with second, fourth and sixth moments 1.017, 2.020 and 4.997 against 1, 2 and 5.

Here nothing is proved. That the angles of $K(1, 1; p)$, as $p$ runs through the primes, are distributed by the Sato–Tate law is Katz’s conjecture, and it has been open since the 1980s. The analogous statement for elliptic curves — that the angles in $p + 1 - |E(\mathbb{F}_p)| = 2\sqrt p\cos\theta_p$, the quantity the Hasse bound confines, follow the same law as $p$ varies — was the Sato–Tate conjecture, proved between 2008 and 2011 by Richard Taylor with Laurent Clozel, Michael Harris, Nicholas Shepherd-Barron, Thomas Barnet-Lamb and David Geraghty, through the modularity machinery of the Langlands programme. For Kloosterman sums no comparable machinery is known to apply. It is not even known, for prime moduli, that $K(1, 1; p)$ changes sign infinitely often; Étienne Fouvry and Philippe Michel proved sign changes in 2007 only along moduli with a bounded number of prime factors.

The difference between the two directions is a difference in what can be averaged. Varying $a$ at a fixed prime is averaging over a family of curves defined over one finite field, where Deligne’s and Katz’s geometry applies. Varying the prime is a statement about one equation over the rational numbers, reduced modulo each prime, which is an arithmetic statement of the deepest kind — of the same kind as the distribution of the primes themselves.

Where the sums do their work #

Kloosterman’s original use shows why a bound mattered. Counting representations by $ax^2 + by^2 + cz^2 + dt^2$ by the circle method produces a main term and an error, and the error is a sum of Kloosterman sums; any bound better than the trivial $p - 1$ makes the error smaller than the main term for large numbers, and Kloosterman’s $p^{3/4}$ was enough to prove that every large number is represented whenever no congruence forbids it. The same structure recurs. In the spectral theory of the modular group, the Kuznetsov formula ties sums of Kloosterman sums to the eigenvalues of the Laplacian on the modular surface, and Selberg’s conjecture about the smallest of those eigenvalues is, in one form, a statement about cancellation in such sums. In the distribution of primes in arithmetic progressions, the best results beyond the Bombieri–Vinogradov theorem, including the work behind bounded gaps between primes, rest on bounds for sums of Kloosterman sums over many moduli.

What the applications need is usually not the individual bound but cancellation on average — that a sum of $K(a, b; c)$ over many moduli $c$ is much smaller than the sum of their absolute values. Linnik and Selberg conjectured square-root cancellation of that kind, and it remains open; the semicircle of the last figure, with its mean near nought, is a picture of what it would mean along the primes.

A semicircle on 3,244 primes is not the Sato–Tate law #

The sums are computed exactly up to rounding — each a sum of cosines from a table of the residues, with inverses from the recursion $\bar\imath = -\lfloor p/i \rfloor\,\overline{(p \bmod i)}$ — and the identities for the second and fourth moments are checked to the rounding of the arithmetic. The Weil bound is checked on 75,958 sums; it is a theorem, and the check confirms the computation, not the theorem. The histograms at a fixed prime show Katz’s limit arriving at $p = 10{,}007$, as the theorem says it must.

The last figure proves nothing about the primes beyond 30,000, and nothing at all about the conjecture it illustrates. A distribution that looks semicircular on 3,244 primes is consistent with the Sato–Tate law and with many laws close to it; its moments agree to two decimals with Catalan numbers, and that is all a finite census can say. The figures also show only the sums with $b = 1$; by the substitution $x \mapsto b^{-1}x$, $K(a, b; p) = K(ab, 1; p)$, so nothing is lost at a fixed prime, but the horizontal question for other $a$ and $b$ is a separate conjecture for each.

Still open: the sign, the law, the average #

Three questions stand in increasing order of depth. Does $K(1, 1; p)$ change sign infinitely often as $p$ runs through the primes? Almost certainly, and no one can prove it. Are its angles distributed by the Sato–Tate law? That is Katz’s conjecture, and it would follow from a modularity statement for the family of Kloosterman sheaves that nobody knows how to formulate in a form the Langlands methods can reach. And do sums of Kloosterman sums over moduli up to $X$ cancel to size about $\sqrt X$, as Linnik and Selberg conjectured? That would have consequences throughout analytic number theory, from the spectral gap of the modular surface to primes in progressions to large moduli.

What the computations make vivid is that the second and third questions are the same picture as Katz’s theorem with the axes swapped. At a fixed prime, the family of coefficients behaves like random rotations, and geometry proves it. Along the primes, one sum appears to behave like random rotations too, and the only thing missing is a proof that a single equation’s reductions modulo different primes are as unrelated as the members of one family over one field.

Bounded, semicircular, and unexplained along the primes #

Kloosterman’s sum adds $p - 1$ unit vectors and never ends further than $2\sqrt p$ from the origin, which Weil proved by reading it as two eigenvalues of Frobenius; at a fixed prime its values over all coefficients fill the interval allowed with a semicircle, whose moments are the Catalan numbers counting non-crossing pairings — exactly for the second and fourth, by Katz’s theorem for the rest. A sum of random signs with the same mean square spreads into a bell and leaves the interval; the Kloosterman sums pile up against its walls. Followed through the primes, one fixed sum looks semicircular as well, with moments 1.017, 2.020 and 4.997 over 3,244 primes, and that is Katz’s conjecture, open, with not even its sign changes proved.