# Simple proofs for the existence of elliptic curves having a given number of points

Yesterday, after he gave a nice talk, Dick Gross and I were chatting and he brought up the following annoying problem: suppose that for $p$ a prime that $H_p$ is the "Hasse interval" $[p - 2 \sqrt{p},p+2\sqrt{p}]$. Then, for every point $r \in H_p$ there is an elliptic curve $E_{a,b}: y^2 = x^3 + a x + b$ over $\mathbb{F}_p$ such that $N_p(E_{a,b}) = r$, where $N_p(C)$ denotes the number of projective points of the curve $C$. But the only proof that we knew of this fact involved the whole theory of complex multiplication and Deuring's theorems about reduction. So the question arose if there is a simpler proof of this fact, say by using $p$-adic methods. I even asked for the weaker case: let $H_p' = [p+\sqrt{p},p+2\sqrt{p}]$. Can you prove the existence of an $E_{a,b}$ with $N_p(E_{a,b}) \in H_p'$ with a fairly simple proof?

On the converse side, there's Hasse's proof of the Riemann Hypothesis for elliptic curves over finite fields, that $N_p(E_{a,b}) \in H_p$, which does involve a fair amount of machinery (even though it's been simplified). Suppose that we're after the weaker statement:

There are absolute constants $0 < c_1 < c_2$ such that if $y^2 = x^3 + a x + b$ is an elliptic curve over $\mathbb{Q}$ then, for sufficiently large primes $p$

$c_1 p \le N_p(E_{a,b}) \le c_2 p$.

More generally, if $f(x,y) \in \mathbb{Q}[x,y]$ is an absolutely irreducible polynomial of total degree $d$ that there are $0 < c_1 < c_2$ only depending on $d$ such that

$c_1 p \le N_p(f) \le c_2 p$ for all sufficiently large primes $p$.

Again, how simple a proof is there for this statement?

When $f(x,y) = a x^2 + b y^2 + c$ which is genus 0, the simplest proof I know of consists in showing

1) If there is a point $P$ in $\mathbb{F}_p^2$ on $f$, then one can explicitly construct a one-to-one correspondence between the projective points on $f$ and the projective line, by using the pencil of lines through $P$.

2) Use the pigeon hole principle to show the existence of a point on $f$:

If $a \ne 0$ there are exactly $(p+1)/2$ values of $a x^2$, so we can see that the intersection $\{ax^2\} \cap \{-(c + by^2)\}$ has at least one point (we just barely made it).

I know of no such simple proof for an elliptic curve $E$.

-
Re your sentence starting "more generally": The upper bound is easy. There is a $d \to 1$ map to $\mathbb{P}^1$, so there can't be more than $d (p+1)$ points. But I think the lower bound will already be nontrivial, since it is not true for $f$ reducible. –  David Speyer Feb 8 '12 at 18:30
For an elliptic curve in Weierstrass form $c_2=2$ is obvious and $c_2=d$ is equally obvious by letting $x$ vary and solving for $y$. Note also that, in the elliptic curve case $c_1=2-c_2$ because of twisting. These are just obvious remarks. –  Felipe Voloch Feb 8 '12 at 18:31
@Felipe and @David, thanks. So for elliptic curves, all one needs to do is to show that $c_2 < 2$. –  Victor Miller Feb 8 '12 at 18:33
Is Stepanov's method elementary enough? ("An elementary proof of the Hasse-Weil theorem for hyperelliptic curves", J. Number Theory 4 (1972), 118–143.) –  Noam D. Elkies Feb 8 '12 at 18:44
@Noam, I had remembered Stepanov's proof (though had forgotten the reference). It is fairly elementary, but does involve a bit of machinery. See Felipe's answer below for something which is pretty concise. –  Victor Miller Feb 8 '12 at 19:01

If you write your cubic as $y^2=f(x)$, let $M$ be the cardinality of of $S =\lbrace x \in \mathbb{F}_p, f(x)^{(p-1)/2} = 1 \rbrace$, so $M$ is related to the number of points on the cubic in an obvious way.
Define $G(x) = f(x)(f(x)^{(p-1)/2}-1) - f'(x)(x^p-x)/2$. Exercise, check that $G$ has double zeros on the elements of $S$. As $G$ has degree $3(p+1)/2$ we get $M \le 3(p+1)/4$ and $c_2=3/2, c_1=1/2$.
Edit: In the case of a general plane curve $f=0$ of degree $d$, you can use $G= (x^p-x)\partial f/\partial x + (y^p-y)\partial f/\partial y$. Again $G$ has double zeros on the $\mathbb{F}_p$-rational points of curve and meets the curve in finitely many points if $d$ is less than $p$ and $f=0$ has no linear component. So, in this case, the number of points is at most $d(d+p-1)/2$ by Bezout, i.e. $c_2= d/2$. Details are slightly harder to fill than the elliptic curve case. Also, there is no twisting so no corresponding lower bound.
This reminds me of an old paper of Bryan Birch "How the number of points on an elliptic curve over a fixed prime field varies": jlms.oxfordjournals.org/content/s1-43/1/57.full.pdf In it he calculates exact values for the moments of the distribution: $C_k(p) := (1/p^2) \sum_{a,b} N_p(E_{a,b})^k$ in terms of coefficients of modular forms. –  Victor Miller Feb 9 '12 at 1:11