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+1- 2 \sqrt{p},p+1+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$.
 A: 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.) 
A: 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.
