# Elliptic Curve Isogenies, Frobenius endomorphism relation to characteristic equation

In Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i) states:

Let $\mathbb{E}$ be an elliptic curve over $\mathbb{F}_p$. Suppose that its $j$-invariant is not supersingular and that $j\neq 0$ or $1728$.

Then the modular polynomial $\Phi_l(j,T)$ has a zero $\tilde{\jmath} \in \mathbb{F}_{p^r}$ if and only if the kernel $C$ of the corresponding isogeny $E \mapsto E/C$ is a one-dimensional eigenspace of $\phi^r_p$ in $E[l]$, with $\phi_p$ the Frobenius endomorphism of $E$.

From the proof:

If $\Phi_l(j,\tilde{\jmath} )=0$, then there exists a cyclic subgroup $C$ of $E[l]$ such that the $j$ invariant of $E/C$ is equal to $\tilde{\jmath}\in \mathbb{F}_{p^r}$. Let $E^1$ be an elliptic curve over $\mathbb{F}_{p^r}$ with $j$ invariant equal to $\tilde{\jmath}$. Let $E/C \mapsto E^1$ be an $\bar{\mathbb{F}}_p$ isomorphism and let $f: E \mapsto E/C \mapsto E^1$ be the composite isogeny. It has kernel $C$.

I can see $f$ is defined over $\mathbb{F}_{p^r}$, so this implies existence of an isogeny $E \mapsto E^1$ over $\mathbb{F}_{p^r}$.

1. How does this imply that $C$ is an eigenspace of $\phi^r_p$?

2. How does the statement "The Frobenius endomorphism over $\mathbb{F}_{p^r}$ satisfies the same characteristic equation" imply that $C$ is an eigenspace of $\phi^r_p$?

I have struggled with this proof, but here is how I tried to reason through it:

The Frobenius endomorphism can be represented by a $2 \times 2$ matrix over the torsion group $\mathbb{E}[\ell]$. You may as well raise $\phi$ to some $r$ power, $\phi_q^r$, and get an eigenvalue equation for this matrix.

You get a subgroup $C$ of $\mathbb{E}[\ell]$ such that $\phi_q^r (P) = \kappa P$ if the characteristic equation has a root $\kappa$. From Vélu's formulas, we can build an isogeny from $\mathbb{E}$ to another elliptic curve $\mathbb{E}'$ such that the kernel of the isogeny is $C$. The Frobenius endomorphism only permutes the points in $C$, leaving the $j$-invariant of $\mathbb{E}'$, well...invariant.

So the $\phi_q^r$ define a subgroup / eigenspace that can, via Vélu, generate an isogeny where it's the kernel.

More discussion:

1. Are you familiar with Vélu's formulas? They may be the missing link for you. Basically: assume you have an elliptic curve $\mathbb{E}$ over some field $\bar{K}$, and let $C$ be a finite subgroup of $\mathbb{E}(\bar{K})$. Then, Vélu tells you that there is another group $\mathbb{E}'$ and an isogeny $\chi: \mathbb{E} \rightarrow \mathbb{E}'$ such that $C = \text{Ker}(\chi)$. They even explicitly give you a formula for the isogeny!

2. A homomorphism from $\mathbb{E}[\ell] \rightarrow \mathbb{E}[\ell]$ is represented as a $2 \times 2$ matrix (the points of $\mathbb{E}[\ell]$ are "$\ell$-torsion points") (page 233)

3. If the number points on a curve satisifies $\#\mathbb{E}(\mathbb{F}_p) = p + 1 - a$, then the Frobenius endomorphism $\phi_q$ satisfies $\phi_q^2 - a \phi_q + q = 0$ (page 234).

So, the Frobenius endomorphism acting on the $\ell$-torsion, $\phi_{q;\ell}$ can be represented as a matrix:

$$\phi_{q;\ell} = \begin{pmatrix} \lambda & b \\ 0 & \mu \\ \end{pmatrix}$$

Its characteristic polynomial is

$$\begin{vmatrix} \lambda - T & b \\ 0 & \mu - T \\ \end{vmatrix} = (T-\mu)(T-\lambda) \equiv 0 \bmod \ell$$

So a root $\lambda$ here satisfies a subgroup of $\mathbb{E}[\ell]$, $C$, such that for all the points in $C$, $\phi(P) = \lambda P$. Raising $\phi_q$ to some $r$ power will just give you another eigenvalue equation, say $\phi_q^r(P) = \kappa P$. From Velu's formulas, we can define an isogeny such that $C$ is the kernel of the isogeny, and $\phi_q^r$ just permutes all the coordinates of points in $C$, leaving the parameters of the equation for $\mathbb{E}'$ alone. That means the $j$-invariant of $\mathbb{E}'$ is left alone too.

Let $f:E\rightarrow E_1$ be an isogeny defined over $\mathbb{F}_{p^r}$. Then any $\sigma\in\operatorname{Gal}(\bar{\mathbb{F}}_{p^r}/\mathbb{F}_{p^r})$ fixes the coefficients of the rational functions defining $f$. As this Galois group is generated by $\phi_p^r$, this is saying that $\phi_p^r$ fixes the coefficients.

As that is the case, it is actually easy to see $$f\circ \phi_p^r = f^{\phi_p^r}\circ\phi_p^r=\phi_p^r\circ f,$$ using the fact that $(x+y)^{p^r} = x^{p^r} + y^{p^r}$ for any $x,y\in\bar{\mathbb{F}}_{p^r}$ (as we're in characteristic $p$). Thus $$\left(f\circ \phi_p^r\right)(C) = \left(\phi_p^r\circ f\right)(C) = 0,$$ i.e. $f(\phi_p^r(C))=0$. As $\ker f = C$, it follows that $\phi_p^r(C)\subset C$. As $C$ is cyclic, the result follows.

Note that I don't believe this is supposed to be the hard part. The tricky bit is showing that $f$ is actually defined over $\mathbb{F}_{p^r}$, which is what almost the whole proof consists of.