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$.

allone needs to do is to show that $c_2 < 2$. – Victor Miller Feb 8 '12 at 18:33J. Number Theory4(1972), 118–143.) – Noam D. Elkies Feb 8 '12 at 18:44