modular.tex

\section{Modular polynomials}
This section will serve as an introduction to modular polynomials.
I will be following \cite{Lang2} and \cite{Adv}, and I refer to those for a more thorough examination
with proofs.

These polynomials get their name from the theory of modular functions. That is a topic which is
well beyond the scope of this article, but they are functions invariant under some fractional linear
transform. 

Given a matrix
$$ \gamma = \begin{pmatrix}
 a & b \\ c & d
\end{pmatrix} \in SL_2(\mathbb{Z})$$
we can define an action of $\gamma$ on some $\tau \in \mathbb{C}$ as
$$\gamma(\tau) = \frac{a\tau + b}{c\tau + d}. $$

Recall that an elliptic curve over $\mathbb{C}$ is isomorphic to a lattice
$$\Lambda = \mathbb{Z}\omega_1 + \mathbb{Z}\omega_2$$ in $\mathbb{C}$.
Letting $\tau = \frac{\omega_1}{\omega_2}$ we consider the $j$-invariant as a function
on the upper half-plane. $j(\tau)$ is the $j$-invariant of the curve given by such a lattice.

It can be shown that $j$ is a modular function of weight $0$ satisfying
$$ j(\tau) = j(\tau + 1) \quad \text{and} \quad j(\tau) = j(-\frac{1}{\tau}). $$
These are exactly the transformations given by the matrices
$$ \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \quad \text{and} \quad
   \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}. $$
It can be shown that these matrices generate the modular group $SL_2(\mathbb{Z})$,
so we have that
$$j(\tau) = j(\alpha \tau) \quad \alpha \in SL_2(\mathbb{Z}). $$

We are not so much interested in how $j$ stays invariant under the modular group,
but rather how it is acted upon by matrices of the bigger group $GL_2(\mathbb{Z})$.
We thus define
$$ j \alpha(\tau) = j\left(\frac{a\tau + b}{c\tau + d}\right) $$
to be the $j$-invariant of the curve given by the lattice $\mathbb{Z}+\mathbb{Z}\tau'$
with $$\tau' = \frac{a\tau + b}{c\tau + d}.$$

Letting $n$ be a positive integer we define a subgroup
$$ S_n^* = \left\{ \alpha = \begin{pmatrix} a & b \\ 0 & d \end{pmatrix} \mid \det(\alpha)=n,\, \gcd(a,b,d)=1,\, 0 \leq b < d \right\} \subset GL_2(\mathbb{Z}). $$
It can be shown that if $n = \ell$ a prime number we have that $\#S_n^* = \ell + 1$.

\begin{mydef}
 The \emph{modular polynomial of degree $\ell$} is given by
$$\Phi_\ell(x,j) = \Phi_\ell(j,x) = \prod_{\alpha \in S_\ell^*}(x - j \alpha) $$
and is of degree $\ell-1$.
\end{mydef}
Notice that the roots of the above polynomials is by definition some $j'$ which is one of transformations
of $j$ under the subgroup $S_\ell^*$. The next theorem gives us a connection between the roots of the
modular polynomial and isogenies between elliptic curves, a proof can be found in \cite{Lang2}.

\begin{thm} \label{modpol}
 Let $E_1$ and $E_2$ be two elliptic curves with $j$-invariants $j(E_1)$ and $j(E_2)$ respectively.
Then there exits an isogeny $f: E_1 \rightarrow E_2$ with $\ker(f)$ cyclic of size $\ell$ if and only if
$$\Phi_\ell(j(E_1), j(E_2)) = 0. $$
\end{thm}

This theorem holds in any field of characteristic $0$ and for a finite field of characteristic $p$ where
$\ell \neq p$.

\begin{ex}
 The following are the two modular polynomials $\Phi_2(x,y)$ and $\Phi_3(x,y)$. They were
calculated using the mathematics software \emph{Sage}. 

\begin{eqnarray}
 \Phi_2(x,y) &=& -x^2y^2 + x^3 + 1488x^2y + 1488xy^2 + y^3 -\nonumber \\
	      && 162000x^2 + 40773375xy - 162000y^2 + 8748000000x +\nonumber \\
	      && 8748000000y - 157464000000000 \nonumber
\end{eqnarray}

\begin{eqnarray}
  \Phi_3(x,y) &=& -x^3y^3 + 2232x^3y^2 + 2232x^2y^3 + x^4 - 1069956x^3y +\nonumber \\
	      &&  2587918086x^2y^2-1069956xy^3 + y^4 + 36864000x^3 + \nonumber \\ 
	      &&  8900222976000x^2y + 8900222976000xy^2+36864000y^3 +\nonumber \\
	      &&  452984832000000x^2 - 770845966336000000xy + 452984832000000y^2+\nonumber \\
	      &&  1855425871872000000000x + 1855425871872000000000y \nonumber
\end{eqnarray}

This clearly serves as a demonstration of how large the coefficients are. In fact the largest
coefficient of the polynomial $\Phi_{41}(x,y)$ has length about $10^{607}$. With coefficients growing this
rapidly it is makes these polynomials very inefficient in practice. Other variants of these polynomials
do exist, an example is the \emph{Atkins modular polynomials}. The same coefficient for the $41^{th}$ Atkins
polynomial is $64000000$ which is a huge improvement over the classical modular polynomials.

More information about such improvements can be found in \cite{Handbook} and \cite{Blake}.
\end{ex}


We end this section with a theorem of Kronecker which gives us explicitly the modular polynomials
modulo $p$.
\begin{thm} \label{kroenecker}
 Let $\Phi_p(x,y)$ be the modular polynomial, then we have that
$$ \Phi_p(x,y) \equiv (x^p-y)(x-y^p)\,(mod\,p).$$
\end{thm}