A great many problems in analytic number theory concern bounds for finite sums in which some amount of cancellation is to be expected. For example, one might study the partial sums of the Möbius function,

which satisfies the trivial bound . As the Möbius function changes sign infinitely often, we expect some amount of cancellation in , but such progress is hard won. Indeed, the unspecified improvement is already equivalent to the famous Prime Number Theorem (PNT).

Just how much cancellation do we expect in the sum ? Replacing the PNT with the Riemann hypothesis, we could show for all . (In fact, these two statements are equivalent.) Conversely, -results (due to Kotnik and te Riele, e.g.) imply that the exponent 1/2 is essentially optimal. We might say that is suspected to demonstrate * square-root cancellation*, since is (conjecturally) no larger than the square-root of the length of its defining sum.

A second example concerns bounds for the Kloosterman sums

in which . Here, the trivial bound was famously improved upon by Weil’s oh-so-non-trivial estimate

which is for fixed and . In other words, Kloosterman sums demonstrate square-root cancellation.

In this note, I’ll discuss why square-root cancellation is so typical in problems in number theory, and give a quick survey of important sums known or widely conjectured to satisfy bounds of this form.

**— RANDOM WALKS —**

It is widely speculated that the values of the Möbius function behave like a random variable on the square-free integers. Given this, what might we expect out of ?

Let be a “random” function (ie. chosen uniformly at random from the functions of this form). These are called * random walks*, and in this particular case, often lumped together as the

*on . The number of random walks that would give is*

**simple random walk**provided of course that and have the same parity. From here, various estimates can give bounds on the probability that exceeds . To spare you a slog, we might cite * Hoeffding’s inequality*, which here provides

Note that this probability becomes vanishingly small as exceeds , so we conclude that “most” random walks exhibit a form of square-root cancellation. Considering the partial sums of arithmetic functions as walks leads to the following moral principle, which I’ll call *The Philosophy of Square-Root Cancellation*:

**The Philosophy of Square-Root Cancellation:**

*We should expect square root cancellation in the partial sum of any arithmetic function that behaves “randomly”.*

Returning to the Möbius function, we note that the Riemann hypothesis follows from the conjecture that behaves like a random variable. (This is the ** probabilistic evidence** towards the Riemann hypothesis.)

**— A SURVEY OF SQUARE-ROOT CANCELLATION IN NUMBER THEORY —**

We have already seen two cases (Kloosterman sums and ) in which square-root cancellation is proven or widely conjectured. In this section, I’d like to fill out the picture with a great many more examples.

**I: The Pólya–Vinogradov Inequality. **In 1918 Pólya and Vinagrodov (independently) showed that

in which is any non-prinicipal Dirichlet character of modulus and are integers. Since the sum of over all of the residues mod is (by orthogonality), we may assume that the sum above is no longer than in length, so Pólya–Vinagradov represents square-root cancellation.

Under the assumption of GRH, Montgomery and Vaughn (1977) have given the slight improvement . On the other hand, it is known (Paley, 1932) that these character sums are infinitely often , so square-root cancellation is the best one can expect.

**II: Classical Gauss Sums.** The Gauss sum of a Dirichlet character of modulus is the finite sum

These sums were first considered by Gauss under the assumption that was the Legendre symbol. Here, Gauss proved that or depending on the residue of mod , and the generalization holds for any primitive character.

This cancellation is most easily seen as a consequence of the Plancherel formula with respect to Fourier inversion on .

**III: Counting Points on Elliptic Curves. **Fix and consider the elliptic curve

over the finite field , with prime. The number of points on the reduction of , which we write as , can be written in terms of the Legendre symbol:

Square-root cancellation suggests that may hold. This (proven) result is known as Hasse’s theorem, and essentially follows from a bound on the magnitude of the roots of the local zeta function of . (That is, Hasse’s theorem represents the analogue of the Riemann hypothesis for the local zeta function of .)

**IV: The Gauss Circle Problem. **The Gauss circle problem concerns estimates for the number of integer lattice points bounded by the circle of radius . One expects (and Gauss showed) that . More precisely, Gauss proved that

in which is an error term satisfying . To see this another way, let denote the number of representations of as a sum of two squares. Then, since

we recognize Gauss’ bound as a form of square-root cancellation after accounting for a main term. Surprisingly, * greater-than-squareroot cancellation* is conjectured to occur within , and we expect .

This deviation from “random'” behavior can be explained in practice by shortening the sum of length via Poisson summation. It may also be possible to recognize the additional cancellation as a consequence of the Hecke relations. (Indeed, a general greater-than-squareroot cancellation is known for sums of coefficients of other modular forms.)

**— EXERCISES —**

**Exercise 1.** Let be a random function as before, with random walk . Use Stirling’s approximation to prove that

Conclude that “most” random functions are for all .