6
$\begingroup$

Following a discussion with a number theory professor, we arrived at the following question : Can we find an elliptic curve (short form : $y^2=x^3+ax+b$) with an identical number of points on two different finite fields: $GF(q)$ and $GF(q^r)$ with $q$ prime.

Looking at some brute force results, we found only one result : the elliptic curve defined by $y^2=x^3+2x+1$ with fields of order 3 and 9.

We only looked at first 100's primes $q$, with power up to 10 so far, but we cannot understand what's specific about this choice, and why is this the only solution we can find so far...

any idea? Any clue as how we could attack this problem?

Thanks

Edit : Using Weil conjecture, we can start with, $\forall q$, $\exists \alpha \in \mathbb{C}$ such that $\forall r$ : $$ \#E(\mathbb{F}_{q^r})= (q^r+1) - (\alpha^r+\bar{\alpha}^r) $$ with $\alpha$ and $\bar{\alpha}$ conjugate, such that $\mid\alpha\mid=\sqrt{q}$

$\endgroup$
  • $\begingroup$ Welcome to MSE. That's a nice first question! $\endgroup$ – José Carlos Santos Oct 8 '18 at 13:06
  • 1
    $\begingroup$ A very rough way to restrict prime powers to search would be Hasse's bound on the number of points on an elliptic curve. For example, an elliptic curve over $\Bbb{F}_3$ has at most $7$ points, and an elliptic curve over $\Bbb{F}_q$ with $q\geq16$ has at least $9$ points. $\endgroup$ – Servaes Oct 8 '18 at 13:07
  • $\begingroup$ The fields should be of the same characteristic?, in other words, only fields and its extensions? (like your examples, $\mathbb F_3$ and $\mathbb F_9$). $\endgroup$ – Piquito Oct 8 '18 at 15:07
  • 1
    $\begingroup$ Yes that was our intent. But clearly the error term (of Hasse bound) increase slowly compared to $q^r$. We can show that as soon as $q=5$ it cannot happen, and for $q=3$ it requires $r<3$. Hence our only solution. I'll post a fully written solution tomorrow. Thanks all! $\endgroup$ – Thomas Lesgourgues Oct 8 '18 at 20:00
2
$\begingroup$

In characteristics two and three you don't have the short Weierstrass form, and this leaves room for more examples. Below there are examples of

  • $q=2$, $r=2$,
  • $q=2$, $r=3$,
  • $q=4$, $r=2$.

Consider the elliptic curve $$ y^2+y=x^3+x $$ defined over $\Bbb{F}_2$. It is relatively easy to see that all the solutions with $x,y\in\Bbb{F}_4$ actually have $x,y\in\Bbb{F}_2$. Basically because $y^2+y=0$ when $y\in \Bbb{F}_2$, and $y^2+y=1$ when $y\in\Bbb{F}_4\setminus \Bbb{F}_2$, but $x^3+x\neq0,1$ when $x\in\Bbb{F}_4\setminus\Bbb{F}_2$.

An explanation in terms of Hasse-Weil formula is to observe that $\# E(\Bbb{F}_2)=5$, Every point $(x,y)\in\Bbb{F}_2\times\Bbb{F}_2$ is a solution, and then we have the point at infinity. Therefore $$ \alpha+\overline{\alpha}=\alpha+\frac2\alpha=-2. $$ Squaring this equation gives $$ \alpha^2+\overline{\alpha^2}=\alpha^2+\frac4{\alpha^2}=(\alpha+\frac2\alpha)^2-4=(-2)^2-4=0. $$ Therefore $\# E(\Bbb{F}_4)=4+1-0=5=\# E(\Bbb{F}_2).$


Other characteristic two examples are the curves $$ y^2+xy=x^3+1 $$ and $$ y^2+xy=x^3+x. $$ Both have four points over $\Bbb{F}_2$ but no other solutions over $\Bbb{F}_8$.

From $\#E(\Bbb{F}_2)=4$ we can solve $\alpha=(-1+i\sqrt7)/2$. Then $\alpha^3=(5-i\sqrt7)/2$ and thus, by Hasse-Weil $$ \# E(\Bbb{F}_8)=8+1-(\alpha^3+\overline{\alpha^3})=8+1-5=4. $$ An alternative explanation comes from the fact that the trace of $(x+\dfrac1x)$ is equal to $1$ for all $x\in\Bbb{F}_8\setminus\Bbb{F}_2$. The solvability criterion for having a solution $y\in\Bbb{F}_8$ would dictate this trace to vanish. Hence, no new points.


Yet another characteristic two example.

Consider the curve $$y^2+y=x^3.$$ With $x$ ranging over the field $\Bbb{F}_4$ we have $x^3\in\Bbb{F}_2$, therefore two solutions for $y$ to each $x$ and therefore nine points altogether. In this maximal case we must have $\alpha=\overline{\alpha}=-2$. But, then $\alpha^2=\overline{\alpha}^2=4$, so over the field $\Bbb{F}_{16}$ we have $16+1-(\alpha^2+\overline{\alpha}^2)=9$ points also. The trace condition for solvability of a quadratic leads to the same conclusion. After all, the cube of an element $x\in\Bbb{F}_{16}\setminus\Bbb{F}_4$ is of order five, and those all have trace $1$.

$\endgroup$
  • $\begingroup$ I removed the cheating example given that you specify that the two fields should share the same characteristics. $\endgroup$ – Jyrki Lahtonen Oct 12 '18 at 11:52
1
$\begingroup$

There are no examples for $q>4$, of elliptic curves $E$ over $\mathbb{ F}_q$ such that $E(\mathbb{ F}_q)=E(\mathbb{ F}_{q^r})$ for some $r\ge 2$.

Proof

Using the Hasse-Weil bounds, that can be deduced from Hasse's theorem that you stated, we have $$ |E(\mathbb{ F}_q)| \le q+1 + 2 \sqrt{q}$$ and $$ |E(\mathbb{ F}_{q^r})| \ge q^r+1 - 2 \sqrt{q^r}\ge q^2+1-2q$$ if $r\ge 2$ (as $q>1$). Hence $$ |E(\mathbb{ F}_{q^r})|- |E(\mathbb{ F}_q)| \ge q^2-3q- 2\sqrt{q}=\sqrt{q}(\sqrt{q}+1)^2(\sqrt{q}-2) $$ which is $ >0$ if $q>4$.

$\endgroup$
  • $\begingroup$ That's all there is to it :-) $\endgroup$ – Jyrki Lahtonen Oct 13 '18 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.