The zeta function and elliptic curves

The last chapter ended by asking how accurate the guess was that Gauss made as a teenager: there are roughly $\frac{x}{\ln x}$ primes up to $x$. Let’s test it on a number that’s hard to write out on one line. Up to $10^{18}$ there are exactly $24{,}739{,}954{,}287{,}740{,}860$ primes. The formula $\frac{x}{\ln x}$ gives $24{,}127{,}471{,}216{,}847{,}324$: an error of two and a half per cent, and that’s more than six hundred trillion primes. But Gauss had a second, more accurate formula. It’s off by about $22$ million, less than one part in a billion.

Where does such accuracy come from, and where do the remaining $22$ million come from? This chapter is a climb. Base camp is the prime number theorem. The first stop is Euler’s identity, which ties the primes to the sum of a series. The pass is Riemann’s function on the complex plane. And higher still is a summit that nobody has reached in more than a hundred and sixty years: the Riemann hypothesis. On the way down we’ll cross to a neighbouring ridge, elliptic curves, and finish where the chapter on ciphers finished: at the lock that guards your bank.

Base camp

Gauss noticed that near a number $t$ primes occur with frequency about $\frac{1}{\ln t}$ (chapter 3). When the frequency changes, the right way to count isn’t to multiply but to add up piece by piece: to integrate (chapter 28).

How many primes there are up to $x$. The logarithmic integral: the sum of the “probabilities” $\frac1{\ln t}$ over all $t$ up to $x$. The average gap between primes near $t$: the further out, the rarer the primes. Example: $\operatorname{li}(10^6) \approx 78{,}627.5$, while there are $78{,}498$ primes up to a million. The error is $130$, almost fifty times smaller than for $\frac{x}{\ln x}$ (there it’s $6{,}116$). The ratio $\frac{\operatorname{li}x}{x/\ln x}$ tends to one, so the prime number theorem can also be written as $\pi(x) \sim \operatorname{li}x$.

The third column is the error, the fourth is $\sqrt x$ for comparison. The error grows, but more slowly than the square root: at $x = 10^{18}$ it’s forty-five times smaller than $\sqrt x$. Why the error behaves like something of order $\sqrt x$, and whether we know it always will, is the main question of the chapter. Riemann found the answer to “why”. The answer to “always?” is still unknown.

First stop: Euler’s identity

In chapter 30 Euler summed the series $1 + \frac1{2^2} + \frac1{3^2} + \dots = \frac{\pi^2}{6}$. Such sums can be formed for any power.

For now let’s think about real $s > 1$. The series converges (for instance by the integral test: $\sum_{n \ge 2} n^{-s} \le \int_1^\infty x^{-s}\,dx = \frac{1}{s - 1}$, chapter 30), and converges absolutely, so its terms can be rearranged and grouped any way we like. In 1737 Euler noticed that the sum over all natural numbers is a product over all primes.

The sum over all natural $n$: the zeta function. The product over all primes $p$. Each factor is the sum of a geometric series $1 + \frac1{p^s} + \frac1{p^{2s}} + \dots$ Example at $s = 2$: the factors for $p = 2, 3, 5, 7$ give $\frac43 \cdot \frac98 \cdot \frac{25}{24} \cdot \frac{49}{48} \approx 1.5951$, all the primes up to $100$ give $1.6419$, and $\frac{\pi^2}{6} \approx 1.6449$. The product creeps up on the sum slowly but surely.

The trick is to make multiplication by $1 - \frac1{p^s}$ work like the sieve of Eratosthenes: it strikes out of the sum all the terms that are multiples of $p$. A tile with the number $n$ stands for the term $\frac1{n^s}$.

Lay out all the terms of $\zeta(s)$ in a row. The series converges absolutely, so its terms can be handled like a finite sum: series can be subtracted term by term and terms rearranged. Multiply $\zeta(s)$ by $\frac1{2^s}$: we get $\frac1{2^s} + \frac1{4^s} + \frac1{6^s} + \dots$, exactly the even tiles. Subtract this from $\zeta(s)$: in $\left(1 - \frac1{2^s}\right)\zeta(s)$ only the odd numbers are left. Multiply what’s left by $\frac1{3^s}$. We get the terms $\frac{1}{(3m)^s}$ with $m$ odd: precisely the remaining tiles that are multiples of three, each once. Subtract them: what’s left are the numbers divisible by neither $2$ nor $3$. The same with five: what’s left, multiplied by $\frac1{5^s}$, is the remaining multiples of $5$, because $5m$ is divisible by neither $2$ nor $3$ exactly when $m$ isn’t. And with seven. After the primes up to and including $P$, what remains is one and the numbers all of whose prime divisors exceed $P$. All such numbers except one are greater than $P$, so $\left|\zeta(s)\prod_{p \le P}\left(1 - \frac1{p^s}\right) - 1\right| \le \sum_{n > P}\frac{1}{n^{\operatorname{Re}s}}$, the tail of a convergent series, which tends to zero as $P \to \infty$. So the product over all primes, multiplied by $\zeta(s)$, equals $1$.

The identity is the fundamental theorem of arithmetic rewritten (chapter 3): if the brackets in the product of geometric series are multiplied out, each $\frac1{n^s}$ appears exactly once, one for each factorisation of $n$ into primes. The first thing it gives is yet another proof that there are infinitely many primes.

The pass: Riemann, 1859

In 1859 Bernhard Riemann was elected a corresponding member of the Berlin Academy, and in return he submitted a paper, “On the Number of Primes Less Than a Given Magnitude”. It’s under ten pages and his only work on number theory. Riemann did what Euler hadn’t: he allowed $s$ to be a complex number.

For $s = \sigma + it$ the term $\frac1{n^s} = e^{-s\ln n} = n^{-\sigma}\left(\cos(t\ln n) - i\sin(t\ln n)\right)$ has modulus $n^{-\sigma}$, so the series converges for $\sigma > 1$. Riemann continued $\zeta$ to the whole complex plane except the point $s = 1$, where it has a pole, and found its main property.

The idea of the proof, and why the whole of it isn’t here

Riemann wrote $\pi^{-s/2}\Gamma(s/2)n^{-s}$ as the integral $\int_0^\infty e^{-\pi n^2 x}x^{s/2 - 1}\,dx$, summed over all $n$ and got an integral of the “theta function” $\theta(x) = \sum_{n \in \mathbb Z} e^{-\pi n^2 x}$. It has a symmetry of its own, $\theta\!\left(\frac1x\right) = \sqrt x\,\theta(x)$, which follows from the Poisson summation formula, a relative of Fourier series. Cutting the integral at $x = 1$ and applying the symmetry to one piece, one gets an expression that doesn’t change under $s \to 1 - s$ and makes sense for all $s \ne 0, 1$. A careful proof takes several pages and needs the gamma function and complex analysis; it can be found in H. M. Edwards’s book Riemann’s Zeta Function or in E. C. Titchmarsh’s monograph.

The equation shows where $\zeta$ has zeros. At $s = -2, -4, -6, \dots$ the factor $\Gamma(s/2)$ is infinite while $\xi(s) = \xi(1 - s)$ is finite, so $\zeta(s) = 0$. These are the trivial zeros. To the right of the line $\operatorname{Re}s = 1$ there are no zeros.

The first non-trivial zeros are $\frac12 + 14.1347i$, $\frac12 + 21.0220i$, $\frac12 + 25.0109i$, $\frac12 + 30.4249i$, $\frac12 + 32.9351i$, and their mirror images below. All on the line $\operatorname{Re}s = \frac12$. Riemann computed the first few himself: in 1932 Carl Ludwig Siegel found these calculations in his papers, together with a formula Riemann had used and never published.

What is the sum $1 + 2 + 3 + 4 + \dots$?

$-\frac{1}{12}$ The series diverges: its partial sums grow without bound It’s infinity, and $-\frac1{12}$ is a misprint

At $s = -1$ the series $\sum n^{-s} = 1 + 2 + 3 + \dots$ diverges. The value $\zeta(-1) = -\frac1{12}$ comes from analytic continuation: the unique holomorphic function that agrees with the sum of the series where the series converges (chapter 34). No adding up happens at all.

The music of the primes

To see how the zeros control the primes, it’s more convenient to count primes with weights. This function was introduced by Pafnuty Chebyshev.

Each prime $p$ weighs $\ln p$, and the frequency of primes near $t$ is about $\frac1{\ln t}$, so “on average” each number adds one to $\psi$, and $\psi(x) \approx x$. It’s not hard to show that $\frac{\psi(x)}{x} \to 1$ if and only if $\frac{\pi(x)}{x/\ln x} \to 1$: there are few heavy prime powers. Riemann found a formula that says what the error is. In 1895 Hans von Mangoldt proved it in this form.

The main term: the prime number theorem. The sum over all non-trivial zeros $\rho = \beta + i\gamma$ (pairs $\rho, \bar\rho$ are added in order of increasing $|\gamma|$). A pair gives the wave $\frac{2x^\beta}{|\rho|}\cos(\gamma\ln x - \arg\rho)$: its frequency is the imaginary part of the zero, its height is $x^\beta$, where $\beta$ is the real part. Small change: the contribution of the trivial zeros and the pole. Example at $x = 10.5$: $\psi(10.5) \approx 7.832$. Without zeros the formula gives $8.667$, with ten pairs of zeros $7.702$, with a hundred pairs $7.835$. The formula holds for $x$ that aren’t prime powers.

Each zero is a note, and the primes are a chord of infinitely many notes. The first few waves draw a smooth curve, the next ones carve steps out of it. For $\pi(x)$ itself Riemann has a similar formula, a little more complicated: in place of $x$ it has the smooth function $R(x) = \sum_{n \ge 1}\frac{\mu(n)}{n}\operatorname{li}\!\left(x^{1/n}\right)$, where $\mu(n)$ is the Möbius function (zero if $n$ is divisible by the square of a prime, otherwise $+1$ or $-1$ for an even or odd number of prime factors), and each pair of zeros again adds a wave.

Now you can see why it matters where the zeros lie. The wave from a pair of zeros with real part $\beta$ grows like $x^\beta$. If there were a zero with $\beta = 1$, its wave would grow like the main term $x$ itself, and the prime number theorem might fail. In 1896 Hadamard and de la Vallée Poussin proved that there are no zeros on the line $\operatorname{Re}s = 1$, and so settled the question Gauss had raised a century earlier.

The idea of the proof, and why the whole of it isn’t here

Take the logarithm of Euler’s identity and differentiate: $-\frac{\zeta'(s)}{\zeta(s)} = \sum_{n}\frac{\Lambda(n)}{n^s}$, where $\Lambda(n) = \ln p$ if $n = p^k$ and $0$ otherwise; this is the “derivative” of $\psi$. An integral along a vertical line in the complex plane turns this function back into $\psi(x)$, and the residues at the poles of $-\frac{\zeta'}{\zeta}$, at the pole $s = 1$ and at the zeros of $\zeta$, give the explicit formula (residues, chapter 34). To get $\psi(x) \sim x$, one has to prove there are no zeros on the line $\operatorname{Re}s = 1$ and estimate the integrals carefully; even the shortest proof (Donald Newman’s, 1980) relies on Cauchy’s theorem and takes several pages. In 1949 Selberg and Erdős found a proof without complex analysis, but it’s longer. This is the path promised in chapter 3.

The summit: the Riemann hypothesis

The further to the right a zero lies, the higher its wave. If all the zeros lie on the middle line, the height of each wave is at most $\frac{2\sqrt x}{|\rho|}$, and the error in the prime number theorem is of order the square root of $x$. The table at the start of the chapter suggests exactly this.

Riemann himself wrote one sentence about it: “It is very probable that all roots are real. Of course one would wish for a rigorous proof here; I have for the time being, after some fleeting vain attempts, provisionally put aside the search for this” (real roots in his notation are the zeros on the critical line). The search hasn’t stopped since. In 1900 David Hilbert put the hypothesis on his list of the most important problems as number eight; in 2000 the Clay Mathematics Institute offered a million dollars for its solution.

Here’s what’s known for certain. In 1914 Godfrey Hardy proved that infinitely many zeros lie on the critical line. In 1989 Brian Conrey showed that more than two fifths of all the zeros lie on it. Computers have checked a great deal: in 2021 David Platt and Timothy Trudgian proved that all the zeros with imaginary part from $0$ to $3 \cdot 10^{12}$ lie on the line, and there are more than twelve trillion of them. Not a single zero off the line has been found.

The idea of the proof

One direction goes through the explicit formula: if all the $\beta = \frac12$, each wave is at most $\frac{2\sqrt x}{|\rho|}$ high, and there are about $\frac{T}{2\pi}\ln\frac{T}{2\pi}$ zeros with $|\gamma| \le T$. Cutting the sum off at a suitable $T$ and estimating the remainder, one gets an error of order $\sqrt x\ln^2 x$ for $\psi$ and then $\sqrt x\ln x$ for $\pi$. The other: if the error is that small, then the function $\frac{\zeta'}{\zeta}$, expressed through $\psi$ by an integral, continues without singularities into the half-plane $\operatorname{Re}s > \frac12$, and there are no zeros there; by symmetry there are none to the left of $\frac12$ either. The detailed estimates are in the books by Edwards and Titchmarsh. In 1976 Lowell Schoenfeld found an explicit constant: if the hypothesis is true, then $|\pi(x) - \operatorname{li}x| < \frac{\sqrt x\ln x}{8\pi}$ for $x \ge 2657$. For $x = 10^{18}$ that’s $1.65 \cdot 10^9$, while the actual error is $2.2 \cdot 10^7$.

More than twelve trillion zeros have been checked, and all lie on the line. Can the Riemann hypothesis be considered proved?

Yes: that many coincidences can’t be chance No: in number theory patterns break even at huge numbers No, because computers calculate with rounding errors

A famous example is the error $\operatorname{li}x - \pi(x)$ itself. Throughout the table above it’s positive, and so it is for every $x$ that computations have reached. But in 1914 John Littlewood proved that it changes sign infinitely often. Where the first sign change happens isn’t known exactly; it’s only known that it’s no later than about $1.4 \cdot 10^{316}$, far beyond any computation.

The neighbouring ridge: elliptic curves

An ancient problem: which natural numbers are areas of right triangles with rational sides? The triangle with sides $3, 4, 5$ has area $6$. Leonardo of Pisa (Fibonacci) found a triangle of area $5$ around 1225: $\frac32$, $\frac{20}{3}$, $\frac{41}{6}$. Fermat proved that area $1$ is impossible. Such numbers are called congruent numbers, and the problem reduces to a curve: $n$ is congruent if and only if the curve $y^2 = x^3 - n^2x$ has a rational point with $y \ne 0$. The triangle $3, 4, 5$ corresponds to the point $\left(\frac{25}{4},\ \frac{35}{8}\right)$ on the curve $y^2 = x^3 - 36x$: check that $\frac{15{,}625}{64} - 225 = \frac{1225}{64}$.

These curves have almost nothing to do with ellipses: they got the name from elliptic integrals, which are used to compute the arc length of an ellipse. Their main property is that points on the curve can be added. The line through two points of the curve meets it in a third: on the line the equation of the curve becomes a cubic, and a cubic equation with two known roots has a third.

The slope of the line $PQ$. If $P = Q$, take the tangent: $\lambda = \frac{3x_P^2 + a}{2y_P}$. The $x$-coordinates of the two known points; the third is found by Vieta’s formulas. Example on the curve $y^2 = x^3 - x + 1$: $P = (-1, 1)$, $Q = (0, 1)$. The slope is $\lambda = 0$, the line $y = 1$ gives $x^3 - x = 0$, so the third point is $R = (1, 1)$. By the formula $x_{P+Q} = 0 + 1 - 0 = 1$, $y_{P+Q} = 0 - 1 = -1$, that is, $P + Q = (1, -1)$.

The trick is that instead of searching for the intersection point we solve a cubic equation two of whose roots are already known, and Vieta’s formulas are enough.

Take two points $P$ and $Q$ of the curve with different $x$-coordinates. The line through them: $y = \lambda x + \nu$, where $\lambda = \frac{y_Q - y_P}{x_Q - x_P}$ and $\nu = y_P - \lambda x_P$. Substitute the line into the equation of the curve: $(\lambda x + \nu)^2 = x^3 + ax + b$, that is, $x^3 - \lambda^2x^2 + (a - 2\lambda\nu)x + b - \nu^2 = 0$. The intersection points are the roots of this cubic. We know two roots, $x_P$ and $x_Q$, so by the factor theorem the polynomial is divisible by $(x - x_P)(x - x_Q)$, and the third factor $x - x_R$ gives the third point $R$ on the same line. By Vieta’s formulas (chapter 14) the sum of the roots equals the coefficient of $x^2$ with the opposite sign: $x_P + x_Q + x_R = \lambda^2$. So $x_R = \lambda^2 - x_P - x_Q$, and $y_R = \lambda x_R + \nu = \lambda(x_R - x_P) + y_P$. The sum $P + Q$ is by definition the mirror image of $R$ in the $x$-axis (the curve is symmetric: along with $(x, y)$ it contains $(x, -y)$). Its coordinates $x_{P+Q} = x_R = \lambda^2 - x_P - x_Q$ and $y_{P+Q} = -y_R = \lambda(x_P - x_{P+Q}) - y_P$ are exactly the formula.

If the line is vertical, there’s no third point in the plane: we say the line meets the curve at the point at infinity $O$, and $P + Q = O$. The point $O$ plays the role of zero: $P + O = P$, and the point opposite to $(x, y)$ is $(x, -y)$.

On the curve $y^2 = x^3 - x + 1$ add the points $P = (-1, 1)$ and $Q = (1, 1)$.

The line through $P$ and $Q$ is horizontal: $y = 1$, $\lambda = 0$. Substituting, we get $x^3 - x + 1 = 1$, that is, $x(x - 1)(x + 1) = 0$: the third point is $R = (0, 1)$. By the formula $x_{P+Q} = 0^2 - (-1) - 1 = 0$, $y_{P+Q} = 0 - 1 = -1$. Answer: $P + Q = (0, -1)$, the mirror image of $R$.

From two rational points addition makes a third, from that one the next, and in this way infinitely many rational points can be obtained. How many do you need to start with?

Louis Mordell’s proof develops Fermat’s “method of descent” (chapter 18): points are given a “height” (the size of the numerators and denominators), and one shows that from any point one can descend to points of bounded height. It takes a chapter in Silverman and Tate’s textbook, and we’ll take it on trust. The number $r$ is called the rank of the curve. For the curve $y^2 = x^3 - 36x$ the rank is $1$, for $y^2 = x^3 - x$ it’s zero: its rational points are just $O$, $(0, 0)$ and $(\pm1, 0)$, and that’s why $1$ isn’t a congruent number. How to find the rank of a curve is unknown in general.

How curves proved Fermat’s Last Theorem

In chapter 18 we left Fermat’s Last Theorem (the equation $a^n + b^n = c^n$ has no solutions in natural numbers for $n \ge 3$) with a promise to tell you which curves helped prove it. The path went like this. In 1985 Gerhard Frey noticed that if a solution $a^p + b^p = c^p$ with a prime $p \ge 5$ existed, the curve $y^2 = x(x - a^p)(x + b^p)$ would be so strange that it could hardly be modular. Modularity is a deep property: the numbers $p + 1 - N_p$, computed for the curve modulo each prime, turn out to be the coefficients of a function with enormous symmetry on the complex upper half-plane, a modular form. The Taniyama–Shimura conjecture (1955–1957) claimed that every elliptic curve with rational coefficients is modular.

In 1986 Ken Ribet proved that Frey’s curve can’t be modular. So Fermat’s Last Theorem followed from the Taniyama–Shimura conjecture. In June 1993 Andrew Wiles, who had worked almost alone for seven years, announced in Cambridge a proof of modularity for a class of curves that included Frey’s curve. A gap was found in the proof; in September 1994 Wiles, together with his former student Richard Taylor, closed it. The two papers appeared in 1995 in the Annals of Mathematics. The full Taniyama–Shimura conjecture was proved in 2001 by Breuil, Conrad, Diamond and Taylor. All these proofs run to hundreds of pages and rest on mathematics far beyond this course; but at their centre are those very curves $y^2 = x^3 + ax + b$ and the counting of their points modulo $p$.

Curves in your browser

The addition formulas work in any field where you can divide. Take remainders modulo a prime $p$ (chapter 42): division is multiplication by the inverse modulo $p$. The curve turns into a finite cloud of points, addition shuffles them by invisible rules, and the group properties survive.

The intuition: for each $x$ the right-hand side $x^3 + ax + b$ is a square in about half the cases and then gives two points, otherwise none; on average that’s about $p$ points plus $O$. The theorem says how far “luck” can stray from the average. Its proof (Helmut Hasse, 1930s) rests on algebraic geometry, and we’ll accept it without proof, but we’ll check it in the widget.

The point $P = (5, 1)$ lies on the curve $y^2 = x^3 + 2x + 2$ over $\mathbb Z_{17}$. Find $2P$.

The tangent: $\lambda = \frac{3 \cdot 5^2 + 2}{2 \cdot 1} = \frac{77}{2}$. Modulo $17$: $77 \equiv 9$, and the inverse of $2$ is $9$ ($2 \cdot 9 = 18 \equiv 1$), so $\lambda \equiv 9 \cdot 9 = 81 \equiv 13$. Then $x_{2P} = 13^2 - 5 - 5 = 159 \equiv 6$, $y_{2P} = 13 \cdot (5 - 6) - 1 = -14 \equiv 3$. Answer: $2P = (6, 3)$. Check: $3^2 = 9$ and $6^3 + 2 \cdot 6 + 2 = 230 = 13 \cdot 17 + 9$.

Adding points is worth practising until it’s automatic: chord, tangent, and the same modulo $p$. All the course’s trainers are on the practice page.

The Diffie–Hellman key exchange from chapter 41 carries over to a curve word for word. In place of the power $g^a$ we take the multiple $aG = G + G + \dots + G$: it’s computed quickly by doubling, like fast exponentiation. Alice picks a secret $a$ and sends $aG$, Bob picks $b$ and sends $bG$. Alice computes $a(bG)$, Bob computes $b(aG)$, and it’s the same point $abG$. An eavesdropper has to find $a$ from $G$ and $aG$: that’s the discrete logarithm on the curve.

Elliptic-curve cryptography was proposed independently in 1985 by Neal Koblitz and Victor Miller. Its advantage is size. The best known ways of computing a discrete logarithm on a good curve, variations on “baby-step giant-step” and Pollard’s rho method, need about $\sqrt N$ operations. For a curve over a field of about $2^{256}$ elements that’s $2^{128}$ steps, the same security as RSA with a $3072$-bit key, with a key twelve times shorter.

The second part of the answer. When you open your bank’s website, the browser and the server agree on a key using the TLS 1.3 protocol (2018) with a Diffie–Hellman exchange on an elliptic curve, most often Daniel Bernstein’s Curve25519 (2006) or the curve P-256 from the NIST standard. An eavesdropper sees the public point and both multiples, but to get the key they’d have to solve the discrete logarithm problem on the curve, and no way of doing that faster than about $2^{128}$ steps is known. A quantum computer running Shor’s algorithm would break this protection (chapter 41), so since 2024 browsers have increasingly added to the curve exchange the post-quantum algorithm ML-KEM, whose security rests on different problems.

Where next

All along we’ve talked about the primes as something almost random: frequency $\frac{1}{\ln t}$, an error of order $\sqrt x$, as for a sum of random terms, zeros that look like the spectra of random matrices. But to talk about randomness seriously you have to begin with the simplest thing: being able to count possibilities. Why, with three dice, does a total of $10$ come up more often than a total of $9$, even though both can be made in six ways? That question opens the next chapter.