### Counting Points on Elliptic Curves (Part 2)

#### Posted by John Baez

Last time I explained three ways that good curves can go bad. We start with an equation like

$y^2 = P(x)$

where $P$ is a cubic with integer coefficients. This may define a perfectly nice smooth curve over the complex numbers — called an ‘elliptic curve’ — and yet when we look at its solutions in finite fields, the resulting curves over those finite fields may fail to be smooth. And they can do it in three ways.

Let’s look at examples.

### The good

In The Riemann Hypothesis (Part 2) we looked at a case of **good reduction**: an elliptic curve that stays smooth when we work modulo some prime. This curve wasn’t in the standard form I’ve been talking about recently. Instead, it looked like this:

$y^2 + y = x^3 + x$

But that’s okay, it’s still an elliptic curve. It turns out to have good reduction at the prime $p=2$. And this manifests itself when we count points on this curve over the fields $\mathbb{F}_q$ where $q = p^n$. To count these points we just count solutions of the above equation in $\mathbb{F}_q$ and add $1$ for the ‘point at infinity’. We get a number I’ll call $|E(\mathbb{F}_q)|$, where $E$ is our elliptic curve:

$\begin{array}{rrr} n & q = 2^n \! & \; |E(\mathbb{F}_q)|\\ 1 & 2 & 5 \\ 2 & 4 & 5 \\ 3 & 8 & 5 \\ 4 & 16 & 25 \\ 5 & 32 & 25 \\ 6 & 64 & 65 \\ 7 & 128 & 145 \\ 8 & 256 & 225 \\ 9 & 512 & 545 \\ 10 & 1024 & 1025 \\ 11 & 2048 & 1985 \\ 12 & 4096 & 4225 \\ \end{array}$

You can see a lot of patterns here: for example, the number of points is $2^n$ plus a slower-growing correction. We thought about that correction, and ultimately guessed that

$|E(\mathbb{F}_q)| = 2^n - (-1 + i)^n - (-1 - i)^n + 1$

In fact this sort of formula is typical for primes of good reduction:

**Theorem 1: Hasse’s Theorem on Elliptic Curves.** Given a cubic equation with integer coefficients in two variables that defines an elliptic curve $E$ with good reduction at $p$, we have

$|E(\mathbb{F}_q)| = p^n - \alpha^n - \overline{\alpha}^n +1$

where $\alpha \in \mathbb{C}$ has $|\alpha| = \sqrt{p}$.

The Weil Conjectures, now theorems, say how this formula can be vastly generalized. Ultimately this led Grothendieck and others to think about ‘motives’. I said much more about this here. But now let’s move on to the other cases!

### The bad: additive reduction

One kind of ‘bad reduction’ happens when our elliptic curve gets a cusp over $\mathbb{F}_p$. To see this pattern it’s easiest to do a cubic curve that’s not even elliptic in the first place. Let’s try this one:

$y^2 = x^3$

This is not an elliptic curve because it already fails to be smooth over $\mathbb{C}$. It has a cusp, visible already in the real solutions:

The cusp is the pointy thing. So we should expect that working over some primes $p$ this curve will still have a cusp… and maybe this will affect the count of points in $\mathbb{F}_q$ when $q = p^n$.

It does! Let’s take the prime $2$ again:

$\begin{array}{rrr} n & q = 2^n \! & \; |C(\mathbb{F}_q)|\\ 1 & 2 & 3 \\ 2 & 4 & 5 \\ 3 & 8 & 9 \\ 4 & 16 & 17 \\ 5 & 32 & 33 \\ 6 & 64 & 65 \\ 7 & 128 & 129 \\ 8 & 256 & 257 \\ 9 & 512 & 513 \\ 10 & 1024 & 1025 \\ \end{array}$

You can see the pattern is very different, and it’s much simpler. We just get $2^n +1$.

When an elliptic curve has bad reduction at a prime $p$ because it gets a cusp, we say it has **additive reduction.** Here’s what happens then:

**Theorem 2.** Given a cubic equation with integer coefficients in two variables that defines an elliptic curve $E$ with additive reduction at $p$, we have

$|E(\mathbb{F}_{q})| = p^n + 1$

There’s a reason for this. You’ll notice that $p^n + 1 = q + 1$ is just the number of points in the projective line over $\mathbb{F}_q$. And indeed, it turns out that in this case the curve $E(\mathbb{F}_{q})$ is just a projective line that’s been mapped into the projective plane in a way that’s one-to-one, but fails to be smooth at the cusp.

Now what’s with this term ‘additive reduction’? Well, you may have heard that an elliptic curve is an algebraic group. There’s a way to add or subtract points on the curve —- a sneaky geometric construction that involves drawing lines between these points:

This still works over finite fields. So in cases of good reduction, $E(\mathbb{F}_{q})$ is an algebraic group.

All this still works when our curve has a cusp — *if* you remove the cusp. When you remove the cusp you still get an algebraic group. In particular, the identity of this group is the point at infinity, and we haven’t removed that. And remember, in this case $E(\mathbb{F}_{q})$ is secretly a projective line except for one non-smooth point at the cusp. So when you remove the cusp you get an ordinary *affine* line. So it’s not surprising that as an algebraic group, what’s left is isomorphic to the additive group of $\mathbb{F}_q$.

That’s why this case is called ‘additive reduction’.

### The ugly: split multiplicative reduction

Now for another kind of bad reduction. We say an elliptic curve has **multiplicative reduction** at the prime $p$ if gives a curve $\mathbb{F}_p$ that has a node. A node is a point with two different tangent lines — it’s easy to visualize in the real case:

But over a finite field, when you try to compute the slopes of the lines tangent to the node, they may or may not be defined over that field! The reason is that you need to solve some polynomial equations, and finite fields aren’t algebraically complete. If the tangent lines are defined over $\mathbb{F}_p$ we say our elliptic curve has **split** multiplicative reduction, otherwise we say it has **nonsplit** multiplicative reduction.

Here’s an elliptic curve with split multiplicative reduction over $\mathbb{F}_5$:

$y^2 = x^3 - x^2 + 5$

I only know this because someone says so — but I know how to check it, and someday I will. For now let’s just count the number of points over $\mathbb{F}_q$ when $q = 5^n$. I have some cheap software that gets really slow when our prime gets as big as $5$, so this table will be pretty small:

$\begin{array}{rrr} n & q = 5^n \! & \; |E(\mathbb{F}_q)|\\ 1 & 5 & 5 \\ 2 & 25 & 25 \\ 3 & 125 & 125 \\ 4 & 625 & 625 \\ \end{array}$

Luckily the pattern is obvious! And that’s how this case always works:

**Theorem 3.** Given a cubic equation with integer coefficients in two variables that defines an elliptic curve $E$ with split multiplicative reduction at $p$, we have

$|E(\mathbb{F}_{q})| = p^n$

Again there’s a reason. Now $p^n$ is *one less* than the number of points in the projective line over $\mathbb{F}_q$. The reason is that in this case, we get the curve $E(\mathbb{F}_{q})$ by mapping the projective line into the projective plane in a way that *crosses itself* at the node. In other words this map is one-to-one except at the node, where it’s two-to-one.

We can can also get an algebraic group out of $E(\mathbb{F}_{q})$ if we remove the node. When we do that, we’re left with projective line with *two* points removed — or an affine line with one point removed. So it’s not surprising that as an algebraic group, we get the multiplicative group of $\mathbb{F}_q$, namely

$\mathbb{F}_q^\times = \mathbb{F}_q - \{0\}$

with multiplication as its group operation.

That’s why this case is called ‘multiplicative’.

### The weird: nonsplit multiplicative reduction

Here’s a curve with non-split multiplicative reduction at $p = 3$:

$y^2 = x^3 - x^2$

And here is the count of points over $\mathbb{F}_q$ where $q = 3^n$:

$\begin{array}{rrr} n & q = 3^n \! & \; |E(\mathbb{F}_q)|\\ 1 & 3 & 5 \\ 2 & 9 & 9 \\ 3 & 27 & 29 \\ 4 & 81 & 81 \\ 5 & 243 & 245 \\ 6 & 729 & 729 \\ 7 & 2187 & 2189 \end{array}$

The pattern is again quite evident, and this case always works this way:

**Theorem 4.** Given a cubic equation with integer coefficients in two variables that defines an elliptic curve $E$ with nonsplit multiplicative reduction at $p$, we have

$|E(\mathbb{F}_{q})| = p^n$

when $n$ is even and

$|E(\mathbb{F}_{q})| = p^n + 2$

when $n$ is odd.

We can play the same game as before and remove the node from $E(\mathbb{F}_q)$. The result is again an algebraic group over $\mathbb{F}_q$. When $n$ is even everything works just as in the split case: this algebraic group has $q - 1$ points, it’s an affine line with one point removed, and it’s the multiplicative group $\mathbb{F}_q^\times$.

But when $n$ is odd things get weird! Now our algebraic group has $q + 1$ points. This is just as many points as the projective line over $\mathbb{F}_1$. But there’s no way to make the projective line into an algebraic group! So what are we getting?

Well, we’re getting some weird algebraic group that only exists thanks to the fact that $\mathbb{F}_q$ is not algebraically closed!

### 1-dimensional connected algebraic groups

Indeed there are some theorems that go like this:

**Theorem 5.** Over an algebraically closed field $k$ the only connected 1-dimensional algebraic groups are:

- elliptic curves (which are projective algebraic groups)
- the additive group of $k$ (which is an affine algebraic group)
- the multiplicative group $k^\times$ (which is an affine algebraic group).

**Theorem 6.** Over $\mathbb{F}_q$ the only connected 1-dimensional algebraic groups are:

- elliptic curves (which are projective algebraic groups)
- the additive group of $k$ (which is an affine algebraic group)
- the multiplicative group $k^\times$ (which is an affine algebraic group).
- one more connected 1-dimensional affine algebraic group.

Note that all these groups are abelian! The last one, the mysterious one, is what shows up when we study elliptic curves with non-split multiplicative reduction.

For more detail on *everything* I’ve said, and much more about that mysterious connected 1-dimensional affine algebraic group, go here:

- Alexis Youcis, Classifying one-dimensional algebraic groups,
*Hard Arithmetic*.

Reid Barton pointed me to this article. It’s really great, and the only reason for writing mine is that I feel this subject deserves a more elementary introduction.

But before I quit, I want to look at an *example* of this mysterious connected 1-dimensional affine algebraic group. I want to hold this exotic entity in my hand and gaze at it.

Youcis says it’s the kernel $K$ of some homomorphism from the multiplicative group $\mathbb{F}^\times_{q^2}$ onto the multiplicative group $\mathbb{F}^\times_q$. In other words, it fits into an exact sequence

$1 \longrightarrow K \longrightarrow \mathbb{F}^\times_{q^2} \stackrel{f}{\longrightarrow} \mathbb{F}^\times_q \longrightarrow 1$

Let’s do a couple sanity checks. First of all, $\mathbb{F}^\times_q$ is a 1-dimensional algebraic group over $\mathbb{F}_q$, while $\mathbb{F}^\times_{q^2}$ is 2-dimensional. So, just counting dimensions naively, we expect that $K$ is 1-dimensonal.

We can also count points: our exact sequence implies

$|\mathbb{F}^\times_{q^2}| = |K| \cdot | \mathbb{F}^\times_q |$

or in other words

$(q^2 - 1) = |K| \cdot (q-1)$

so

$|K| = \frac{q^2 - 1}{q - 1} = q + 1$

as we want. And if you’ve ever read my stuff on $q$-arithmetic, this should bring back fond memories.

But what is this group like?

For that, we need to understand the map $f$ here a bit better:

$1 \longrightarrow K \longrightarrow \mathbb{F}^\times_{q^2} \stackrel{f}{\longrightarrow} \mathbb{F}^\times_q \longrightarrow 1$

The field $\mathbb{F}_{q^2}$ is a quadratic extension of $\mathbb{F}_q$ whose Galois group is $\mathbb{Z}_2$. This means there’s some automorphism

$z \mapsto \overline{z}$

of $\mathbb{F}_{q^2}$, whose fixed points form the subfield $\mathbb{F}_q$, such that

$\overline{\overline{z}} = z$

Youcis claims that $f$ is the ‘norm’ of this quadratic extension, namely

$f(z) = z \overline{z}$

All this should remind you a lot of ideas familiar from the real and complex numbers. The group $K$, the kernel of $f$, is analogous to the unit circle in the complex plane since

$K = \{ z \in \mathbb{F}_{q^2} \; \vert \; z \overline{z} = 1 \}$

Let’s look at an example: our friend the prime power $q = 3$, which is actually prime. A cute thing about $\mathbb{F}_3$ is that has three elements $-1, 0, 1$, and we *multiply* these just as if they were real numbers! So it’s like a baby version of the real numbers. In other words, there’s an inclusion of multiplicative groups $\mathbb{F}_3^\times \to \mathbb{R}^\times$. It’s only when we start adding that things get wonky. Well… actually, adding $0$ works as usual, and adding $1$ and $-1$ works as usual too! So the only problem is that now $1 + 1 = -1$.

The field $\mathbb{F}_3$ doesn’t contain a square root of $-1$, so we can throw in a square root of $-1$ and get a quadratic extension. This is a concrete way of thinking about $\mathbb{F}_9$: it consists of guys

$z = a + b i$

where $a,b \in \{-1,0,1\} = \mathbb{F}_3$. So it’s like a baby version of the complex numbers. In particular, we can define an automorphism

$\overline{z} = a - b i$

and then

$f(z) = z \overline{z}$

Thus our desired group $K$, the kernel of $f$, consists of guys $a + b i$ with $a^2 + b^2 = 1$. We know there must be 4, so they must be just the obvious ones:

$K = \{1, i, -1, -i \}$

So $K$ is a baby version of the unit circle in the complex plane! And as a group it’s $\mathbb{Z}/4$.

Now, we’ve seen that the elliptic curve

$y^2 = x^3 - x^2$

has nonsplit multiplicative reduction at $p = 3$. So, Theorem 4 assures us that we can look at the curve it defines over $\mathbb{F}_3$, remove the node from that curve, and get this group $K$.

The equation $y^2 = x^3 - x^2$ has four solutions in $\mathbb{F}_3$:

$(0, 0)$ $(1, 0)$ $(-1, 1)$ $(-1, -1)$

Together with the point at infinity, our curve over $\mathbb{F}_3$ has 5 points. When we remove the node at $(0,0)$ that leaves 4… and I’m claiming these are the points of a connected 1-dimensional algebraic group isomorphic to $K$!

I still haven’t worked out the addition of points in our curve with the node removed, using that well-known but to me somewhat annoying geometrical recipe for adding points on elliptic curves. I should do this and check that this gives a group isomorphic to $\mathbb{Z}/4$. But I’m already much happier having looked at this example. The idea of a connected abelian 1-dimensional algebraic group with the same number of points as the projective line really shocked me!

## Re: Counting Points on Elliptic Curves (Part 2)

Your theorem 6 is also true over the real numbers! Some might find the theorem there more understandable.