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