show/hide this revision's text 4 changed "a ring of integers" to "an order" to avoid possible confusion with "the ring of integers"

In your last paragraph, you suggest that you are particularly interested in the case of elliptic curves. This is much easier than the general case, which is addressed well by Torsten's answer.

If $q$ is prime, and $|a| \leq 2 \sqrt{q}$, then there is always an elliptic curve with $\zeta$-function $(1-au+qu^2)/(1-u)(1-qu)$. This is the one dimensional case of Honda's theorem. I'll sketch the proof. As you will see, it uses some very sophisticated methods, and it will be very hard to make it effective.

Sidenote: What happens when $q = p^k$ for $k>1$? Then there are $2 p^{k-1}-1$ ways to choose $a$ to be $0 \mod p$. When $a=0$, the elliptic curve must be supersingular. But there are only $\approx p/12$ supersingular elliptic curves over $\mathbb{F}_{p^k}$. So, once $2 p^{k-1}$ is much greater than $p/12$, there will be $a$'s which don't occur. To be honest, I am not clear what happens if you feed one of these $a$'s into Honda's theorem.

Proof Sketch: Let $R$ be the ring $\mathbb{Z}[\phi]/(\phi^2 - a \phi + q)$. $R$ is a ring of integers an order in a quadratic an imaginary quadratic field (the inequality $a^2-4q<0$ is used to show that this is an imaginary extension.) Let $K$ be the the fraction field of $R$ and let $H$ be its class field. Let $\mathfrak{p}$ be the ideal $(\phi)$ in $\mathcal{O}_K$. Since $\mathfrak{p}$ is principal, it splits in $H$; let $\mathfrak{q}$ lie over $\mathfrak{p}$. So $\mathcal{O}_H/\mathfrak{q} \cong \mathbb{F}_p$.

Let $E$ be an elliptic curve with complex multiplication by $R$; then $E$ can be defined over $H$. ($E$ is only well defined up to a quadratic twist, at this point.) Take a model of $E$ over $\mathcal{O}_H$. Let $E_0$ be the fiber over $\mathfrak{q}$. Then $E_0$ is an elliptic curve over $\mathbb{F}_p$. One can show that the Frobenius acts on $E_0$ by $\pm \phi$ or $\pm \overline{\phi}$, where the bar is the automorphism of $R$ over $\mathbb{Z}$ coming from complex conjugation. By changing the quadratic twist, one can make sure the sign is $+$. Then the trace of the Frobenius is $\mathrm{Tr}(\phi)$, which is $a$, as desired.

Sorry for making this so advanced, I don't know an easier way. I think you can find most of the tools I am using in Silverman's Advanced topics in the arithmetic of elliptic curves.
show/hide this revision's text 3 added 286 characters in body

In your last paragraph, you suggest that you are particularly interested in the case of elliptic curves. This is much easier than the general case, which is addressed well by Torsten's answer.

For an elliptic curve

If $q$ is prime, if and $|a| \leq 2 \sqrt{q}$, then there is always an elliptic curve with $\zeta$-function $(1-au+qu^2)/(1-u)(1-qu)$. This is the one dimensional case of Honda's theorem. I'll sketch the proof. As you will see, it uses some very sophisticated methods, and it will be very hard to make it effective.UPDATE

Sidenote:I think this isn't quite right What happens when $q$ is a $q = p^k$ for $k>1$. I'll try k>1$? Then there are $2 p^{k-1}-1$ ways to clear this up.

For simplicity, I'll take choose $q$ a$ to be prime$0 \mod p$. When $a=0$, the elliptic curve must be supersingular. But there are only $\approx p/12$ supersingular elliptic curves over $\mathbb{F}_{p^k}$. So, and once $|a|$ strictly less that 2 p^{k-1}$ is much greater than $\sqrt{q}$. p/12$, there will be $a$'s which don't occur. To be honest, I am not clear what happens if you feed one of these $a$'s into Honda's theorem.

Proof Sketch: Let $R$ be the ring $\mathbb{Z}[\phi]/(\phi^2 - a \phi + q)$. $R$ is a ring of integers in a quadratic imaginary field (the inequality $a^2-4q<0$ is used to show that this is an imaginary extension.) Let $K$ be the the fraction field of $R$ and let $H$ be its class field. Let $\mathfrak{p}$ be the ideal $(\phi)$ in $\mathcal{O}_K$. Since $\mathfrak{p}$ is principal, it splits in $H$; let $\mathfrak{q}$ lie over $\mathfrak{p}$. So $\mathcal{O}_H/\mathfrak{q} \cong \mathbb{F}_p$.

Let $E$ be an elliptic curve with complex multiplication by $R$; then $E$ can be defined over $H$. ($E$ is only well defined up to a quadratic twist, at this point.) Take a model of $E$ over $\mathcal{O}_H$. Let $E_0$ be the fiber over $\mathfrak{q}$. Then $E_0$ is an elliptic curve over $\mathbb{F}_p$. One can show that the Frobenius acts on $E_0$ by $\pm \phi$ or $\pm \overline{\phi}$, where the bar is the automorphism of $R$ over $\mathbb{Z}$ coming from complex conjugation. By changing the quadratic twist, one can make sure the sign is $+$. Then the trace of the Frobenius is $\mathrm{Tr}(\phi)$, which is $a$, as desired.

Sorry for making this so advanced, I don't know an easier way. I think you can find most of the tools I am using in Silverman's Advanced topics in the arithmetic of elliptic curves.
show/hide this revision's text 2 added 96 characters in body

In your last paragraph, you suggest that you are particularly interested in the case of elliptic curves. This is much easier than the general case, which is addressed well by Torsten's answer.

For an elliptic curve, if $|a| \leq 2 \sqrt{q}$, there is always an elliptic curve with $\zeta$-function $(1-au+qu^2)/(1-u)(1-qu)$. This is the one dimensional case of Honda's theorem. I'll sketch the proof. As you will see, it uses some very sophisticated methods, and it will be very hard to make it effective. UPDATE: I think this isn't quite right when $q$ is a $p^k$ for $k>1$. I'll try to clear this up.

For simplicity, I'll take $q$ to be prime, and $|a|$ strictly less that $\sqrt{q}$. Let $R$ be the ring $\mathbb{Z}[\phi]/(\phi^2 - a \phi + q)$. $R$ is a ring of integers in a quadratic imaginary field (the inequality $a^2-4q<0$ is used to show that this is an imaginary extension.) Let $K$ be the the fraction field of $R$ and let $H$ be its class field. Let $\mathfrak{p}$ be the ideal $(\phi)$ in $\mathcal{O}_K$. Since $\mathfrak{p}$ is principal, it splits in $H$; let $\mathfrak{q}$ lie over $\mathfrak{p}$. So $\mathcal{O}_H/\mathfrak{q} \cong \mathbb{F}_p$.

Let $E$ be an elliptic curve with complex multiplication by $R$; then $E$ can be defined over $H$. ($E$ is only well defined up to a quadratic twist, at this point.) Take a model of $E$ over $\mathcal{O}_H$. Let $E_0$ be the fiber over $\mathfrak{q}$. Then $E_0$ is an elliptic curve over $\mathbb{F}_p$. One can show that the Frobenius acts on $E_0$ by $\pm \phi$ or $\pm \overline{\phi}$, where the bar is the automorphism of $R$ over $\mathbb{Z}$ coming from complex conjugation. By changing the quadratic twist, one can make sure the sign is $+$. Then the trace of the Frobenius is $\mathrm{Tr}(\phi)$, which is $a$, as desired.

Sorry for making this so advanced, I don't know an easier way. I think you can find most of the tools I am using in Silverman's Advanced topics in the arithmetic of elliptic curves.
show/hide this revision's text 1