Concrete counting points on elliptic curves of the form $y^2 = x^3 + D$

In this post, I present explicit computations with elliptic curves of form $y^2=x^3+D$ (similar trick leads to curves $y^2 = x^3 + Dx$; the common point is they have complex multiplication). This was my TA for Ariane Mezard. at the Summer School on Galois Representations and Reciprocity last summer. The talk is based on the master thesis of Matteo Tamiozzo. 

Reminder on zeta functions

For a prime $p$ and let $f(x,y,z) \in \mathbb{F}_p[x,y,z]$ be a homogeneous polynomial so that

$$C = V(f) =  \left \{[x:y:z] \in \mathbb{P}^2_{\mathbb{F}_p} \mid f(x,y,z) = 0 \right \}$$ is a smooth, projective curve. We define

$$N_m = N_m(f) = \left \{P \ \text{has coordinates in} \ \mathbb{F}_{p^m} \right \}$$ to be the cardinality of solutions defined over the $\mathbb{F}_{p^m}$. We package these numbers $N_1,N_2,...,N_m,...$ into a zeta function

$$Z_C(t) = \exp \left(\sum_{m=1}^{\infty} \frac{N_m}{m}t^m \right).$$ The celebrated result due to Weil and the school of Grothendieck gives us the (particular case of) Weil conjecture

Theorem. If $C$ is a smooth projective curve of genus $g$, then 

$$Z_C(t) = \frac{(1-\alpha_1t)\cdots (1-\alpha_{2g}t)}{(1-t)(1-pt)}$$ with $\alpha_i$ complex numbers with $\left |\alpha_i \right | = \sqrt{p}$. This gives the Hasse bound

$$\left | N_m - p^m - 1 \right | \leq 2gp^{m/2}.$$ In particular, if $g=1$ (an elliptic curve), then 

$$Z_C(t) = \frac{1- a_p t + pt^2}{(1-t)(1-pt)} = \frac{(1-\pi)(1-\overline{\pi})}{(1-t)(1-pt)}$$ with $\left| \pi \right| = \sqrt{p}$ and 

$$\left | N_m - p^m - 1 \right| \leq 2p^{m/2}.$$ Readers with an eagle-eye will recognise that $a_p$ is the trace of the Frobenius on étale cohomology and the readers unfamiliar with these are recommended to carry the computation with the obvious examples $f(x,y,z)=x$. The objective of the materials below is to give novices a feeling of what is happening here before he tries to dig deeper to étale cohomology or the Weil conjectures. Explicitly, we are about to work with curves $y^2 = x^3 + D$ and prove their Weil conjecture (concrete!) and determine exactly numbers $a_p,\pi,\overline{\pi}$.

Setting for elliptic curves 

Let $k$ be a field, by an elliptic curve over $k$, we mean a smooth, projective curve $E$ of degree $3$ over $k$ together with a rational point $O \in E(k)$. This is, of course, the algebro-geometric definition, we work with more concrete equations and $k = \mathbb{Q}$ or $k = \mathbb{F}_q$ a finite field. Any elliptic curve can be transformed into the Weierstrass form

$$E = \left \{(x,y) \in \mathbb{A}^2_{\mathbb{Q}} \mid y^2 = x^3 - Ax+ B \right \} \cup \left \{\infty \right \}.$$ The smoothness of $E$ is tantamount to saying that the discriminant $\Delta = 16(4A^3-27B^2)$ nonzero. The transformation $(x,y) \mapsto (c^2x,c^3y)$ turns the equation into $y^2 = x^3 - c^4Ax + c^6B$ and hence we can assume that $A,B \in \mathbb{Z}$. For a prime $p$, we can consider its reduction mod $p$, 

$$E_p = \left \{(x,y) \in \mathbb{A}^2_{\mathbb{F}_p} \mid y^2 = x^3 - Ax + B \ \text{mod}  \ p \right \} \cup \left \{\infty \right \}$$ which is smooth over $\mathbb{F}_p$ iff $p \nmid \Delta$. In such a case, we say that $E_p$ has good reduction mod $p$. By the Weil conjecture, we know that for each $p$, there is a mod $p$ zeta function

$$Z_{E_p}(t) = \frac{1 - a_p t + pt^2}{(1-t)(1-pt)} = \frac{(1-\pi)(1-\overline{\pi})}{(1-t)(1-pt)}.$$ Thus, by Taylor expansion, one sees that

$$N_m= p^m+1 - \pi^m - \overline{\pi}^m$$ and in particular $N_1 = p + 1 - a_p$. This is incredible, since once we know $a_p$, we know $N_1$ and all $N_m$; in other words, the trace of Frobenius $a_p$ controls all numerical information of the curve. 

Example. To illustrate with a tangible example, let's take $p=97$ and 

$$E = \left \{[x:y:z] \in \mathbb{P}^2_{\mathbb{F}_{97}} \mid x^3+y^3=z^3 \right \}$$

and one checks easily that $E$ is smooth, projective and hence an elliptic curve. This curve is given by the Fermat equation with $n=3$ and if one wants the Weierstrass form, he can simply perform the transformation 

$$(x,y) \longmapsto \left( \frac{12}{x+y}, \frac{36(x-y)}{x+y} \right)$$ which makes our curve become $\left \{y^2 = x^3-432 \right \} \cup \left \{\infty \right \}$. By hands, one can see that $N_1 = 117$ and hence $a_{97} = -19$, forcing $\pi = (-19 + 3\sqrt{-3})/2$. For example, if we want to compute $N_2$, it is given by $N_2 = 97^2 + 1 - \pi^2 - \overline{\pi}^2 = 9243$. 

Curves of the form $y^2 = x^3+D$

In fact, we can do the computation with any curve ofthe form $y^2 = x^3+D$, which includes the Fermat curve as a special case. Here $D \in \mathbb{Z}^{\times}$, and the discriminant is $\Delta = -2^43^3D^2$ and primes with bad reduction are $2,3$ and those dividing $D$. Clearly, we see that

$$N_1 = 1 + \# \left \{ y^2 = x^3 + D \ \text{mod} \ p \right \}.$$ Here comes two cases. The easier one is when $p = 2$ in $\mathbb{F}_3$. We claim that that $x \longmapsto x^3$ is an automorphism of $\mathbb{F}^{\times}_3$. To see this, write $p = 3k+2$ and we just have to show that $x \longmapsto x^3$ is injective, which follows from Fermat little theorem. Thus

$$ \# \left \{ y^2 = x^3 + D \ \text{mod} \ p \right \} = \# \left \{ y^2 = x + D \ \text{mod} \ p \right \} = p$$ and $N_1 = 1+ p$. The difficult case is when $p = 1$ in $\mathbb{F}_3$. To handle this case, we need some prerequisites on the theory of characters and Jacobi sums.

Theory of characters 

Given a finite group $G$, a character is a homomorphism $\chi \colon G \longrightarrow \mathbb{C}^{\times}$. There is always a trivial character $\epsilon(g) = 1$ for all $g \in G$. Here are some basic properties of characteristics with respect to groups $\mathbb{F}_p,\mathbb{F}_p^{\times}$:

• If $\chi \neq \epsilon$, then there exists $b \in \mathbb{F}_p^{\times}$ such $\chi(b)=1$.
• If $\chi \neq \epsilon$, then $\sum_{a \in \mathbb{F}_p}\chi(a) = 0$.

For the second point, we use the first point (which is obvious), to pick some $b$ with $\chi(b) \neq 1$, then 

$$\chi(b) \sum_{a\in \mathbb{F}_p}\chi(a) = \sum_{a \in \mathbb{F}_p}\chi(ba) \Rightarrow (\chi(b)-1)\sum_{a \in \mathbb{F}_p}\chi(a) = 0 \Rightarrow \sum_{a \in \mathbb{F}_p}\chi(a) =0$$

and cancellation finishes. The usage of characters is in the following

Lemma. Let $a \in \mathbb{F}_p$ and $n \mid p-1$, then 

$$\# \left \{x^n = a \right \} = \sum_{\chi^n = \epsilon} \chi(a).$$ Proof. If $a = 0$, this is obvious. When $a \neq 0$, it is clear that $x^n = a$ has either $0$ or $n$ solutions because once a solution is given, others differs by a root of unity.

• If $x^n = a$ has $n$ solutions, then for any character with $\chi^n=\epsilon$, we see that $\chi(a)=1$ (exercise!).
• If $x^n = a$ has no solution, there is some $\chi^n = \epsilon$ but $\chi(a) \neq 0$ (exercise!). By the same trick as above, the sum on RHS is zero. 

We provide here an useful class of characters, generalising Legendre symbols, namely, power residue symbol. 

Example. Let $F/\mathbb{Q}$ be a number field with ring of integers $\mathcal{O}_F$ containing a primitive $n$-th root of unity $\zeta_n$. Let $\mathfrak{p} \subset \mathcal{O}_F$ be a prime, the number (called norm) $N\mathfrak{p} = \left| \mathcal{O}_F /\mathfrak{p} \right|$ is finite and there is an analogue of Fermat little theorem 

$$a^{N\mathfrak{p}-1} - 1 \in \mathfrak{p}$$ for any $a \in \mathcal{O}_F \setminus \mathfrak{p}$.  In case $N\mathfrak{p} - 1$ is divisible by $n$, this implies

$$a^{\frac{N\mathfrak{p}-1}{n}} - \zeta_n^s \in \mathfrak{p}$$ for some $s$ and in this case we define 

$$\left(\frac{a}{\mathfrak{p}} \right)_n = a^{\frac{N\mathfrak{p}-1}{n}} = \begin{cases} 0 & a \in \mathfrak{p} \\ 1 & a \not\in \mathfrak{p}, \exists \eta \in \mathcal{O}_F: \eta^n - a \in \mathfrak{p} \\ \zeta &  \text{otherwise} \end{cases}$$

Now we come to Jacobi sums, let $\chi,\lambda$ be characters on $\mathbb{F}_p$, the sum

$$J(\chi,\lambda) = \sum_{a+b=1} \chi(a)\lambda(b).$$ There are some (non-trivial, feel free to omit the proof) basic properties:

• $J(\chi,\chi) = p$.
• $J(\epsilon,\chi) = 0$.
• $J(\chi,\chi^{-1}) = -\chi(-1)$. 
• If $\zeta_p$ is a primitive $p$-th root of unity, then $$J(\chi,\lambda) = \frac{g(\chi)g(\lambda)}{g(\chi \lambda)},$$ where $g(\chi) = \sum_{a \in \mathbb{F}_p}\chi(a)\zeta_p^a$ is the Gauss sum.
  
• If $\chi,\lambda,\chi\lambda$ non-trivial, then $\left|J(\chi,\lambda) \right| = \sqrt{p}$. 

In particular, we get

Corollary. If $p \equiv 1 \ \text{mod} \ 3$, then there exist $a,b \in \mathbb{Z}$ so that $a^2 - ab + b^2=p$. 

Proof. Since $3 \mid p-1$, we can pick a character $\chi$ of order $3$ on $\mathbb{F}_p$, the last one above gives $J(\chi,\chi)^2 = p$. By representability of Jacobi sums in terms of Gauss sums, we know that $J(\chi,\chi) \in \mathbb{Z}[\omega]$, hence we get the desire.

Lemma. Let $p > 2$ be a prime, $\rho$ a character of order $2$ and $\chi$ non-trivial character on $\mathbb{F}_p$, then $J(\rho,\chi) = \chi(4)J(\chi,\chi)$. 

Proof. 

$$\begin{align*} J(\rho,\chi) & = \sum_{a+b=1}\rho(a)\chi(b) \\ & = \sum_{a+b}(1+\rho(a))\chi(b) \\ & = \sum_{a+b=1}\# \left \{ x^2 = a \right \}\chi(b) \\ & = \sum_b \chi(1-b^2) \\ & = \chi(4)\sum_b \chi(\frac{1+b}{2})\chi(\frac{1-b}{2}) \\ & = \chi(4)J(\chi,\chi) \end{align*}$$ as desired.  

In some special case, we can compute $J(\chi,\chi)$. Let $\omega = \zeta_3 = (-1+\sqrt{-3})/2$, and $\pi = a+b\omega \in \mathbb{Z}[\omega]$. The number $N(\pi)=a^2-ab+b^2$ is the norm of $\pi$, which equals $\left|\mathbb{Z}[\omega]/\mathfrak{p}\right|$. Using this norm, we can list all units and primes of $\mathbb{Z}[\omega]$: 

Units: $\pm 1, \pm \omega, \pm \omega^2$.

Primes: 

• $1- \omega$.
• $p \in \mathbb{Z}$ prime and $p \equiv 2 \ \text{mod} \ 3$.
• $a + b \omega$ with $a^2-ab+b^2=p \in \mathbb{Z}$ prime and $p \equiv 1 \ \text{mod} \ 3$.
  

Proposition. Let $\pi \in \mathbb{Z}[\omega]$ be a prime element (i.e. $(\pi)$ is a prime ideal) with $N(\pi)=p$ and $\pi \equiv 2 \ \text{mod} \ 3$, then 

$$J( \left( \frac{-}{\pi} \right), \left(\frac{-}{\pi} \right) ) = \pi.$$ and now we are equipped to attack the curves $y^2 = x^3 + D$. 

Back to $y^2 = x^3 + D$ 

We are dealing with $p \equiv 1 \ \text{mod} \ 3$. Let $\rho,\chi$ be characters of order $3,2$ on $\mathbb{F}_p$, respectively (specified later). Then

$$\begin{align*} \# \left \{y^2 = x^3 + D \right \} & = \sum_{a+b=D} \# \left \{y^2 = a \right \} \# \left \{x^3 = -b \right \} \\ & = \sum_{a+b = D} (1 + \rho(a))(1+\chi(-b)+\chi^2(-b)) \\ & = p + \sum_{a+b=D}\rho(a)\chi(b) + \sum_{a+b = D}\rho(a)\chi^2(b) \end{align*}$$ by lemmas above and the fact that $\chi(-1)=1$. Using the subsitution $a = Du,b = Dv$, we get

$$\begin{align*} N_1 & = p+1 + \rho(D)\chi(D)J(\rho,\chi) + \overline{\rho(D)\chi(D)J(\rho,\chi)} \\ & = p +1 + \rho(4D)\chi(4D)J(\chi,\chi) + \overline{\rho(4D)\chi(4D)J(\chi,\chi)}. \end{align*}$$ Now let's specify $\rho,\chi$. Since $ p \equiv 1 \ \text{mod} \ 3$, we can write $p =  \pi \overline{\pi}$ in $\mathbb{Z}[\omega]$ with $\pi$ prime and we can even take $\pi \equiv 2 \ \text{mod} 3$ (by multiplying with a suitable unit). We set

$$\rho(a) = \left( \frac{a}{\pi}\right)^3_6 \ \ \ \ \text{and} \ \ \ \ \chi(a) = \left(\frac{a}{\pi} \right)_6^2$$ resulting in 

$$N_1 = p+1 + \left( \frac{4D}{\pi} \right)^5_6 \pi + \left( \frac{\overline{4D}}{\pi} \right)^5_6 \overline{\pi} = p+1 + \left( \frac{\overline{4D}}{\pi} \right)_6 \pi + \left( \frac{4D}{\pi} \right)_6 \overline{\pi}$$ In summary, we find a theorem

Theorem. Let $p \neq 2,3$ and $p \nmid D$, the number of $\mathbb{F}_p$-points on 

$$E_p = \left \{y^2 = x^3 + D \right \} \cup \left \{\infty \right \}$$ is given by:

• If $p \equiv 2 \ \text{mod} \ 3$, then $N_1= p+1$.
  
• If $p \equiv 1 \ \text{mod} \ 3$, then $$N_1 = p + 1 + \left( \frac{\overline{4D}}{\pi} \right)_6 \pi + \left( \frac{4D}{\pi} \right)_6 \overline{\pi}$$ with some $\pi \in \mathbb{Z}[\omega]$ such that $p = \pi \overline{\pi}$.

In particular, the Hasse bound $\left| N_1- p-1 \right| \leq 2\sqrt{p}$ is satisfied and the trace of the Frobenius in the latter case is $a_p = \pi + \overline{\pi}$.

With a little further effort, one can deduce the higher Hasse bound, given the $a_p$. We leave it to the reader and end by an example. 

Example. Let's consider the curve $y^2 = x^3+1$ modulo $19$. We find easily that $19=(5+3\omega)(5+3\omega^2)$ so 

$$N_1 = 20 + \overline{\left( \frac{4}{5+3\omega}\right)_6}(5+3\omega) + \left( \frac{4}{5+3\omega} \right)_6 (5+3\omega^2).$$ Therefore it remains to calculate

$$\left( \frac{4}{5+3\omega} \right)_6 = \left( \frac{2}{5+3\omega} \right)_3.$$ A direct calculation shows that

$$2^{(19-1)/3} \equiv 2^6 \equiv 64 \equiv 64 - 19 \times 3 \equiv 7 \ \text{mod} \ 5 + 3\omega$$ and $5 + 3\omega \mid 7 - \omega^2$ and hence 

$$\left( \frac{4}{5+3\omega} \right)_6 = \left( \frac{2}{5+3\omega} \right)_3 = \omega^2.$$ Thus, we obtain that

$$N_1 = 20 + \omega(5+3\omega) + \omega^2(5+3\omega^2) = 12,$$ and the zeta function is

$$Z_{E_{19}}(t )= \frac{1 - a_{19}t + 19t^2}{(1-t)(1-19t)},$$ where $a_{19} = 19 + 1- N_1 = 8$, so we see that $\pi = (4+\sqrt{-3})$. As we noted before, this is enough to determine all $N_r$. For instance, $r=4$, we get $N_4 = 19^4 + 1-\pi^4- \overline{\pi}^4 = 130368$ points defined over $\mathbb{F}_{19^4}$.