## 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 2012 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 2012 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 2012 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 2012 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 2012 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.

-

You can compute the average and standard deviation of the number of points on y^2=f, choosing f randomly. That should give you (something close to) what you wanted about H_p': there must be an elliptic curve with that number of points, otherwise standard deviation would be too small. (Also, you can always twist so you have more than p+1 points rather than less.)

-
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/… 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 2012 at 1:11