Give or take twice the square root

Take the equation $y^2 = x^3 + ax + b$ with $a$ and $b$ whole numbers, and read it modulo a prime $p$. For each of the $p$ values of $x$ the right-hand side is some remainder, and it has two square roots, one or none. So the curve has some number of points $(x, y)$ with both coordinates remainders modulo $p$ — and, by the convention that makes these curves behave, one more point at infinity.

How many? A guess is easy. About half the non-zero remainders are squares, and a square has two square roots, so on average each $x$ contributes one point, and the total should be about $p + 1$.

The guess is right on average and wrong for every individual curve, and the question is by how much. Hasse proved in 1933 that the number of points is always within $2\sqrt p$ of $p + 1$. Over the integers modulo 43 that allows anything from 31 to 57, the two curves drawn reach both ends, and every count in between is the count of some curve.

Why these curves, and why a point at infinity #

Of all the equations one could count solutions of, the cubics $y^2 = x^3 + ax + b$ are singled out because their points can be added to each other.

A straight line meets a cubic curve in three points, counted properly. Given two points of the curve, the line through them meets it in a third, and that third point — reflected in the $x$-axis — is defined to be their sum. It is the construction every Pythagorean triple is found by, with a line through known points finding a new one, carried from a conic to a cubic, where the line meets the curve once more instead of once. The point at infinity is where every vertical line meets the curve for the third time, and it plays the part of zero.

With that rule the points of the curve form a group, and over a finite field it is a finite group whose size is exactly the count $N$. So counting the points of a cubic is finding the size of a group, and the size constrains everything else about it: by Lagrange’s theorem, the number of times any point must be added to itself to reach zero divides $N$. Hasse’s theorem is therefore a statement about which group sizes a cubic over the integers modulo $p$ can have, and it is why these particular curves were the first whose counts anybody could bound.

One step for each value of x #

The count has an exact formula that makes the guess precise. For a non-zero remainder $r$, write $\left(\frac{r}{p}\right)$ for $+1$ if $r$ is a square modulo $p$ and $-1$ if it is not, and set it to 0 when $r$ is 0. That is the Legendre symbol, the object quadratic reciprocity is about, and $1 + \left(\frac{r}{p}\right)$ is exactly the number of square roots of $r$: two, none, or one.

So the number of points is

$$N = 1 + \sum_{x = 0}^{p-1}\left(1 + \left(\frac{x^3 + ax + b}{p}\right)\right) = p + 1 + \sum_{x=0}^{p-1}\left(\frac{x^3 + ax + b}{p}\right),$$

and everything interesting is in the sum of $p$ signs at the end.

Read the sum as a walk. Start at 0, take one step for each value of $x$ — up when the cubic’s value there is a square, down when it is not — and the walk ends at $N - (p + 1)$. The curve with 57 points walks up to 13; the curve with 31 walks down to $-13$. The dashed lines are at $\pm 2\sqrt{43}$, and Hasse’s theorem is the statement that no cubic’s walk ever ends outside them.

The walk is short enough to take by hand at a small prime. Modulo 7 the squares are 0, 1, 2 and 4. For $y^2 = x^3 + x + 1$ the right-hand side takes the values 1, 3, 4, 3, 6, 5 and 6 as $x$ runs from 0 to 6. Only the first and third are non-zero squares, so the walk steps up twice and down five times and ends at $-3$; the curve has two points above $x = 0$, two above $x = 2$, and none elsewhere, which with the point at infinity makes $1 + 2 + 2 = 5$ — three short of $p + 1 = 8$. Change the curve to $y^2 = x^3 + 3$ and the values become 3, 4, 4, 2, 4, 2 and 2: every one but the first is a non-zero square, the walk ends at $+5$, and the curve has 13 points. Twice the square root of 7 is 5.29, so $+5$ is as far as any cubic modulo 7 can go.

Why the square root is the right size, and why that is not a proof #

A walk of 43 steps of $\pm 1$ chosen by coin tosses would typically end about $\sqrt{43} \approx 6.6$ from its start, because the spread of a random walk grows like the square root of its length. The squares modulo $p$ are not coin tosses, but they are scattered with so little pattern that the walk behaves as though they were, and the bound $2\sqrt p$ is exactly the size a random walk would make plausible.

That is a heuristic and not a proof, and the difference is real. A random walk can end anywhere, only improbably far out; Hasse’s theorem says the walk cannot end beyond $2\sqrt p$, for any curve and any prime, with no exceptions and no probability anywhere in it. The square roots in the squares modulo $p$ are fixed arithmetic, and the theorem is a fact about that arithmetic.

The square root has appeared before, in the same kind of sum. One sum, squared two ways shows that the Gauss sum — a sum of $p$ roots of unity weighted by Legendre symbols — has size exactly $\sqrt p$, and that the error in counting the points of $x^2 + y^2 = 1$ is controlled by it. The cubic’s error is not a Gauss sum, and bounding it needed a different idea. The standard proof today uses a map of the curve to itself that raises each point’s coordinates to the $p$-th power. Its fixed points are exactly the points being counted, it satisfies a quadratic equation whose middle coefficient is the error, and that quadratic’s discriminant cannot be positive — which says the error squared is at most $4p$.

A bound that divisibility could never give #

The previous way of saying something about a count of solutions was Chevalley and Warning’s: if an equation has more variables than its degree, its number of solutions is a multiple of $p$. For $y^2 = x^3 + ax + b$ that says nothing at all. The equation has two variables and degree three, the degree is too large, and the affine count — 56 for one curve over the integers modulo 43, 30 for the other — is no multiple of 43.

Hasse’s theorem is information of a completely different kind. It does not say what the count is congruent to; it says how large the count can be. And no argument of the divisibility kind could reach it, because divisibility is a statement about a count’s remainder, and a remainder modulo $p$ is shared by infinitely many whole numbers of every size; knowing it says nothing about which of them the count is. Two curves with 31 and 57 points differ by 26, which is no multiple of anything useful, and the bound that confines both of them is a statement about distance from $p + 1$ measured on the ordinary number line.

That is why the two theorems need such different proofs. The divisibility comes from summing a polynomial over the whole field and watching its monomials vanish, which sees only whether a total is zero modulo $p$. The size bound comes from a map of the curve to itself and an inequality between real numbers, which sees how big the total is. Counting modulo $p$ and counting on the number line are two different questions about the same finite set of points, and a count can be completely unconstrained by the first while tightly confined by the second.

Every curve at every small prime #

The theorem can be checked where it can be exhausted.

For every prime from 5 to 61, every choice of $a$ and $b$ that gives a curve without a repeated root — nearly 20,000 curves — is counted by listing its points. Not one lies outside $\pm 2\sqrt p$, and at every prime the bar runs all the way to the whole numbers nearest the two curves. Hasse’s bound is not merely true but tight: the largest and smallest counts it allows are always achieved.

The bound is also the edge of a much stranger fact. Nothing in the figure’s construction forces the bars to be solid — a prime could have curves with 20 points and 22 points and none with 21. It never happens.

Every count that is allowed happens #

Deuring proved in 1941 that for every prime $p$ and every whole number $N$ with $|N - (p + 1)| \le 2\sqrt p$, some curve over the integers modulo $p$ has exactly $N$ points. The bound is not only an upper limit; it is a description of exactly which counts occur.

Over the integers modulo 101 the allowed counts run from 82 to 122, and all 41 of them occur among the 10,100 curves. How many curves share a count is far less regular. The bars jump from 100 to 600 between neighbours, and the jumps are not noise: the number of curves with a given count is governed by the class numbers of imaginary quadratic fields — for a count $N$, of the ring obtained by adjoining the square root of $(N - p - 1)^2 - 4p$, a negative number — and class numbers, which measure how badly unique factorisation fails in such rings, are notoriously irregular. They are the same numbers that decide which primes a quadratic form can take, and there too they are what makes the answer stop being a simple congruence.

How the counts spread #

Beneath the raggedness there is a smooth shape, and it is a surprising one.

Measure each curve’s error in units of $2\sqrt p$, so that every error lies between $-1$ and $1$. Averaged over all the curves at one prime, the errors behave as if drawn from a semicircle: their mean square is exactly a quarter and their mean fourth power exactly an eighth, which are the semicircle’s values, to four decimal places at $p = 101$. The bars are ragged and their moments are not. Birch proved in 1968 that this holds in the limit for every such moment, so the semicircle is the shape of the counts once the class-number noise is averaged away.

The fourth power is also what shows the counts are not a random walk. If each curve’s error were a walk of $p$ fair coin tosses, its normalised spread would follow the bell curve coin tosses assemble, and a bell curve with the same mean square of a quarter has a mean fourth power of three sixteenths, 0.1875. The curves give 0.1250. The errors are more tightly packed than chance would make them — fewer large deviations than a walk of coin tosses produces, and none at all beyond the bound, where a bell curve’s tails run on for ever.

The semicircle then turned out to describe something far harder: a single curve with whole-number coefficients, reduced modulo every prime in turn. Sato and Tate conjectured in the 1960s that its normalised errors, over all primes, follow the same semicircle — unless the curve has extra symmetry. That was proved in stages between 2008 and 2011 — first by Clozel, Harris, Shepherd-Barron and Taylor for most curves, then for all of them by Barnet-Lamb, Geraghty, Harris and Taylor — as one of the major results of its decade. All curves at one prime and one curve at all primes spread in the same way, and nobody has an explanation for the coincidence that does not go through the whole of the proof.

A family with no error at all #

The extremes of the first figure were both reached by curves of the form $y^2 = x^3 + b$, with no $x$ term. Over some primes those curves have no error whatever.

If $p$ leaves remainder 2 on division by 3, then cubing is a one-to-one map on the remainders modulo $p$. The non-zero remainders are the powers of a single one of them, so cubing multiplies every exponent by 3, and when 3 shares no factor with $p - 1$ that multiplication shuffles the exponents without repeating any: no two remainders have the same cube. So for each value of $y$, the equation $x^3 = y^2 - b$ has exactly one solution $x$. That is $p$ points, one for each $y$, and with the point at infinity every curve $y^2 = x^3 + b$ has exactly $p + 1$ points — for $p = 5, 11, 17, 23, \dots$, whatever $b$ is.

Over $p = 43$, which leaves remainder 1, cubing is three-to-one on the non-zero remainders, the argument fails, and the same family produces both extremes instead. A family that is perfectly balanced at one kind of prime and as unbalanced as the bound allows at the other is a strong hint that the count is controlled by arithmetic rather than by chance — here, by whether the cube roots of unity exist modulo $p$.

The genus sets the bound #

The cubic curves are one family among many, and the bound depends on the family in a precise way.

A conic $y^2 = x^2 + b$ has exactly $p - 1$ solutions for every non-zero $b$, because $(y - x)(y + x) = b$ has one solution for each non-zero value of $y - x$; its error is always 1. The cubics reach errors up to twice $\sqrt p$. The quintics $y^2 = x^5 + ax + b$ reach well past twice $\sqrt p$ — 3.20 times it over the integers modulo 43 — and never past four times.

The multipliers 0, 2 and 4 are twice the genus of each curve. Over the complex numbers, the solutions of $y^2 =$ a polynomial form a surface, and the branch points of the square root decide its genus: a quadratic gives a sphere, genus 0; a cubic gives a torus, genus 1; a quintic gives a surface with two handles, genus 2 — and every closed surface is a sphere with some number of handles, so the genus is the one number that tells these surfaces apart. Weil proved in 1948 that a curve of genus $g$ over a finite field with $q$ elements has a number of points within $2g\sqrt q$ of $q + 1$. The number of holes in a surface over the complex numbers sets the size of the error in a count over a finite field — two worlds with nothing apparently in common, connected by a factor of two.

Weil’s bound was the first of the conjectures that bear his name, and the general version, for varieties of any dimension, was completed by Deligne in 1974. Its content is often called the Riemann hypothesis for curves over finite fields, because the bound is equivalent to the zeros of a certain function lying on a line — the finite-field analogue of the most famous open problem in mathematics, and one that was proved.

What the searches cannot show #

Every prime drawn is small. The theorem is about every prime and every curve, and the figures exhaust primes up to 61 and all curves at 101. What they show is that the bound holds, and is reached, exactly where they look.

The point at infinity is a convention made visible only in the count. It is where the curve closes up in the projective plane, and every figure adds it as the extra 1 in $p + 1$ without drawing it.

And the raggedness is attributed, not measured. The counts of curves per value are computed exactly; the statement that class numbers govern them is Deuring’s theorem, quoted and not reproduced.

Still open: how often a single curve lands on a given error #

For a single curve with whole-number coefficients, the errors at the successive primes follow the semicircle — that much is now proved. How often the error is exactly a given value is not.

Lang and Trotter conjectured in 1976 that, for a curve without extra symmetry, the number of primes below $X$ at which the error is exactly $t$ grows like a constant times $\sqrt X/\log X$, with a constant they could describe. It is not known for any single curve. For the error 0 — the primes at which the curve has exactly $p + 1$ points, as the family above has at every other prime — Elkies proved in 1987 that there are infinitely many, which settles existence and leaves the rate open.

A count that knows the shape of a surface #

The number of points on a curve over a finite field is a sum of $p$ signs, and the signs are as scattered as coin tosses. Their total nevertheless never strays beyond twice the square root of $p$, every total inside that range occurs, and the totals spread in a semicircle.

When a sum of many signs looks random and is not, ask what fixed structure bounds it — here a map of the curve to itself, and behind it the genus of a surface, which decides how far the count can go.