BUNTES Isogeny graphs: background and motivation (Maria Ines)

Section 3.1 Isogeny graphs: background and motivation (Maria Ines)

Subsection 3.1.1 Background

Let \(k = \FF_q\text{,}\) \(\characteristic (k) = p \ne 2,3\text{.}\)

Definition 3.1.1. Elliptic curves.

An elliptic curve \(E/k\) is a smooth projective curve of genus 1 together with a point \(\infty \in E(k)\text{.}\)

We can always write such a curve using a Weierstrass equation

\begin{equation*} E\colon y^2= x^3 + ax +b,\,a,b \in k \end{equation*}

\(E\) is really the projective closure of this affine equation.

Definition 3.1.2. \(j\)-invariants.

The \(j\)-invariant of an elliptic curve \(E\) is

\begin{equation*} j(E) = j(a,b) = 1728 \frac{4a^3}{4a^3 + 27b^2} \end{equation*}

doesn't depend on the choice of Weierstrass equation.

Fact 3.1.3.

\(E,E'\) are isomorphic over \(\overline k \iff j(E) = j(E')\text{.}\)
There is a 1-1 correspondence
\begin{equation*} k \leftrightarrow \overline k \text{-isomorphism classes of EC's }/k\text{.} \end{equation*}

Definition 3.1.4. Isogenies.

Let \(E,E'/k\) be elliptic curves. An isogeny, \(\phi \colon E\to E'\) is a non-constant morphism of pointed curves. The degree \(\deg \phi \) is the degree as a morphism. \(E,E'\) are said to be \(n\)-isogenous if there exists \(\phi\colon E\to E'\) of degree \(n\text{.}\) \(j,j'\in k\) are \(n\)-isogenous if the corresponding elliptic curves are.

Fact 3.1.5.

If \(p \nmid n = \deg \phi\) then the kernel of \(\phi\) has size \(n\) (\(\phi\) is separable).
every finite subgoup of \(E(\overline k )\) is the kernel of a separable isogeny from \(E\text{,}\) unique up to isomorphism.
Every \(n\)-isogeny \(\phi\colon E \to E'\) has a dual isogeny \(\hat \phi \colon E' \to E\) such that
\begin{equation*} \phi\circ \hat\phi = \hat\phi \circ \phi = \lb n \rb\text{,} \end{equation*}
the multiplication-by-\(n \) map.
The \(n\)-torsion subgroup
\begin{equation*} E\lb n \rb = \left\{ P \in E(\overline k) : nP = \infty\right\} \end{equation*}
is isomorphic to \((\ZZ/n)^2\) if \(p\nmid n\text{.}\)

Lemma 3.1.6.

Let \(E/k\) be an elliptic curve with \(j(E) \not\in\{0,1728\}\) and let \(l\ne p\) be prime, up to isomorphism the number of \(l\)-isogenies from \(E\) defined over \(k\) is 0,1,2 or \(l+1\text{.}\)

Proof.

In Maria's notes.

The modular equation.

Let \(j(\tau)\) be the modular \(j\)-function. For each prime \(l\) the minimal polynomial \(\phi_l\) of \(j(l\tau)\) over \(\CC (j(\tau))\) is the modular polynomial

\begin{equation*} \phi_l \in \ZZ[j(\tau)][y] \simeq \ZZ[x,y]\text{.} \end{equation*}

Fact 3.1.7.

\(\phi_l\) is symmetric in \(x,y\) and has a degree \(l+1\) in both variables.
The modular equation
\begin{equation*} \phi_l (x,y) = 0 \end{equation*}
is a canonical model for
\begin{equation*} Y_0(l) = \Gamma_0(l) \backslash \HH \end{equation*}
it parameterises pairs of elliptic curves related by an \(l\)-isogeny. This moduli interpretation is still valid when we use any field \(F\) with \(\characteristic(F) \ne l\text{.}\)
Let \(m_l(j,j') = \ord_{t = j'} \phi_l(j,t)\text{,}\) whenever \(j,j' \ne 0,1728\text{,}\)
\begin{equation*} m_l(j,j') = m_l(j',j)\text{.} \end{equation*}

The endomorphism ring.

Definition 3.1.8. Endomorphisms of elliptic curves.

An endomorphism of an elliptic curve \(E\) is either the zero map or an isogeny from \(E\) to itself. They form a ring \(\End(E)\text{.}\)

For \(n \in ZZ\) we ahve \(\lb n \rb \in \End(E)\) so \(\ZZ \subseteq \End(E)\) over a finite field \(k\text{,}\) \(\End(E)\) is always larger than \(\ZZ\text{.}\) It is either an order in an imaginary quadratic field, in which case we say \(E\) is ordinary. Or an order in an quaternion algebra, in which case we say \(E\) is supersingular. We say \(E\) has complex multiplication by \(\ints\text{.}\)

Proposition 3.1.9.

Let \(E/k = \FF_{p^n}\) be an elliptic curve, TFAE

\(E\) is supersingular.
\(E\lb p\rb\) is trivial.
The map \(\lb p\rb \colon E\to E\) is purely inseparable and \(j(E) \in \FF_{p^2}\text{.}\)

Note 3.1.10.

If \(E,E'\) are isogenous elliptic curves then \(\End(E) \otimes_\ZZ \QQ \simeq \End(E')\otimes_\ZZ \QQ\text{.}\) So supersingularity is preserved by isogenies.

Isogeny graphs of elliptic curves.

Let \(k = \FF_q\) with \(\characteristic(k) = p\) and \(l \ne p \) be prime.

Definition 3.1.11. Isogeny graphs.

The \(l\)-isogeny graph \(G_l(k)\) is the directed graph with vertex set \(k\) and edges \((j,j')\) present with multiplicity

\begin{equation*} m_j(l,l') = \ord_{t=j} \phi_l(j,t) \end{equation*}

vertices are \(\overline k\) isomorphism classes of elliptic curves \(/k\text{,}\) edges are isomorphism classes of \(l\)-isogenies defined over \(k\text{.}\)

Since \(m_l(j,j') = m(j',j)\) whenever \(j,j' \ne 0,1728\) the subgraph of \(G_l(k)\) supported on \(k\smallsetminus \{0,1728\}\) can be thought of as undirected. By the last note \(G_l(k)\) consists of ordinary and supersingular components.

Supersingular isogeny graphs.

Since every supersingular \(j\)-invariant lives in \(\FF_{p^2}\) if \(E\) is supersingular all roots of \(\phi_l(j(E), y)\) live in \(\FF_{p^2}\text{.}\) Every vertex in a supersingular component has out-degree \(l+1\text{.}\)

Moreover by a result of Kohel \(G_l(\FF_{p^2})\) has only one supersingular component.

By the above if \(p \equiv 1 \pmod {12}\) then the supersingular component of \(G_l(\FF_{p^2})\) is an undirected \((l+1)\)-regular graph with around \(p/12\) vertices.

Theorem 3.1.12. Pizer.

The supersingular component of \(G_l(\FF_{p^2})\) is a Ramanujan graph.

Definition 3.1.13. Ramanujan graphs.

A connected \(d\)-regular graph is a Ramanujan graph if \(\lambda_2 \le \sqrt{d-1}\) where \(\lambda_2\) is the second largest eigenvalue of its adjacent matrix. (The largest one is always \(d\text{,}\) by \(d\)-regularity.)

Ordinary isogeny graphs.

Let \(E/\FF_q\) be an ordinary elliptic curve, then \(\End(E) \simeq \ints\) is an order in an imaginary quadratic field \(K\) with \(\ZZ\lb \pi \rb \subseteq \ints \subseteq \ints_K\) where \(\pi\) is Frobenius and

\begin{equation*} K = \QQ(\sqrt{(\trace \pi)^2 - 4q}) \end{equation*}

by Tate, isogenous elliptic curves have the same \(\trace \pi\text{.}\)

We can separate the vertices in the component \(V\) of \(G_l(k)\) containing \(j(E)\) into levels \(V_0, \ldots, V_d\) so that \(j(E') \in V_i\) if \(i = v_l(\lb \ints_K : \ints'\rb)\text{.}\) We'll see that \(\bigcup_{i=0}^d V_i\) is connected.

Let \(\phi\colon E\to E'\) be an \(l\)-isogeny between two elliptic curves with CM by \(\ints = \ZZ+\tau\ZZ\text{,}\) \(\ints ' = \ZZ+\tau'\ZZ\text{.}\) Then \(\hat\phi \tau' \phi \in \End(E) \implies l\tau ' \in \ints\text{.}\) Similarly \(l\tau \in \ints'\text{.}\) There are 3 cases

\(\ints = \ints'\) (\(\phi\) is horizontal).
\(\lb\ints : \ints' \rb = l\) (\(\phi\) is descending).
\(\lb\ints' : \ints \rb = l\) (\(\phi\) is ascending).

In the last two cases we say \(\phi\) is critical.

Horizontal isogenies.

\(E/k\) with CM by \(\ints \subseteq K\) imaginary quadratic. Let \(\ideal a\) be an invertible ideal.

\begin{equation*} E\lb \ideal a \rb = \{ P \in E(\overline k) : \alpha (P) = 0\, \forall \alpha \in \ideal a\} \end{equation*}

this is a finite group so it is the kernel of a separable isogeny \(\phi_{\ideal a }\text{.}\) If \(p \nmid N(\ideal a)\) then \(\deg(\phi_{\ideal a}) = N(\ideal a)\) with \(\ideal a\) invertible implying \(\phi_{\ideal a} \) is horizontal.

Each horizontal \(l\)-isogeny \(\phi\) arises from some invertible ideal \(\ideal a\) of norm \(l\text{.}\)

If \(l | \lb \ints_K : \ints \rb \) no such ideals exist, otherwise the number of invertible ideals of norm \(l\) is

\begin{equation*} 1+ \left(\frac {\disc(K)}{l}\right) = \begin{cases}0\amp\text{ if }l \text{ inert }\\ 1\amp\text{ if }l \text{ ramified }\\ 2\amp\text{ if }l \text{ splits}\end{cases} \end{equation*}

Vertical isogenies.

Let \(\ints\) be an order in an imaginary quadratic field \(K \) of discriminant \(D \lt -4\) and let \(\ints' = \ZZ+l\ints\text{.}\)

Lemma 3.1.14.

Let \(E' / k\) be an elliptic curve with CM by \(\ints '\) then there is a unique ascending \(l\)-isogeny \(E'\to E\) with \(E/k\) an elliptic curve with CM by \(\ints\text{.}\)

Definition 3.1.15.

An \(l\)-volcano \(V\) is a connected undirected graph whose vertices are partitioned into levels \(V_0, \ldots, V_d\text{.}\)

The subgraph \(V_0\) is regular of degree \(\le 2\text{.}\)
For each \(i \gt 0\) each vertex in \(V_i\) has exactly one neighbour in level \(V_{i-1}\text{,}\) and this accounts for all edges outside of \(V_0\text{.}\)
For \(i \lt d\) each vertex has degree \(l+1\text{.}\)

The number \(d\) is the depth.

Figure 3.1.16. A \(3\)-volcano

The Sage code used to make this picture was:

Theorem 3.1.17. Kohel.

Let \(V\) be an ordinary component of \(G_l(\FF_q)\) that doesn't contain \(0\) or \(1728\) then \(V\) is an \(l\)-volcano s.t.

All vertices in \(V_i\) have the same endomorphism ring \(\ints_i\text{.}\)
The subgraph on \(V_0\) has degree
\begin{equation*} 1+ \left(\frac {\disc(K)}{l}\right) \end{equation*}
where \(K = \Frac(\ints_0)\)
If
\begin{equation*} \left(\frac {\disc(K)}{l}\right) \ge 0 \end{equation*}
then \(\#V_0\) is the order \(\lb l \rb\) in \(\Cl (\ints_0)\) else \(\#V_0 = 1\text{.}\)
The depth of \(V\) is \(d = v_l (\lb \ints_K : \ZZ\lb\pi \rb\rb)\) where \(\pi\) is the Frobenius morphism on any \(E\) with \(j(E) \in V\text{.}\)
\(l \nmid \lb \ints_K : \ints_0 \rb\text{,}\) \(\lb \ints_i : \ints_{i+1}\rb = l\) for \(0\le i \lt d\text{.}\)

Application: Identifying supersingular elliptic curves.

Algorithm 3.1.18. Sutherland.

Input: Elliptic curve \(E/k\text{,}\) \(\characteristic k = p\text{.}\)

Output: Ordinary or supersingular.

If \(j(E) \not \in \FF_{p^2}\) then ordinary.
If \(p =2,3\) return supersingular if \(j(E) = 0\) or ordinary otherwise.
Find 3 roots of \(\phi_2(j(E), 4)\) over \(\FF_{p^2}\) if not possible return ordinary.
Walk 3 paths in parallel for up to \(\lceil \log_2 p \rceil + 1 \) steps. If any of these paths get to \(V_d\text{,}\) return ordinary.
Otherwise supersingular.