%alias l='latex modabvar; dvips -t landscape -f < modabvar.dvi > modabvar.ps;' %alias p='latex modabvar; dvips -Ppdf -t landscape -f < modabvar.dvi > modabvar.ps; ps2pdf modabvar.ps' % % make nup pages for printing: % psnup -r -d1 -nup 4 modabvar.ps modabvar_nup.ps % % Notes on showing presentation. % * use gsview modabvar.ps % with Media->Display Settings->Res = 120, make window big % so only middle visible (use alt-f4 to move) % * scroll pages using ``-'' and ``+'' on numerical keypad % (or space bar and backspace if window is big enough) % * use ``r'' to reload ps file. \documentclass[landscape]{slides} \usepackage[active]{srcltx} \voffset=-0.05\textheight \textheight=1.1\textheight \hoffset=0.06\textwidth \newcommand{\comment}[1]{#1} \usepackage{amsmath} \usepackage{amssymb} \usepackage{psfrag} \usepackage{graphicx} \usepackage{pstricks} \usepackage[all]{xy} \newrgbcolor{purple}{.5 .16 .6} \newrgbcolor{darkpurple}{.3 .05 .4} \newrgbcolor{darkred}{.5 0 0} \newrgbcolor{darkblue}{0 0 0.3} \newcommand{\pic}[2]{\includegraphics[width=#2in]% {pics/#1}} \newcommand{\captionpic}[2]{% \begin{tabular}{c}\includegraphics[height=2in]% {pics/#1}\\{\small #2}\end{tabular}\vspace{-7ex}} \newcommand{\ha}[2]{{\begin{center}% \hfill{\purple\large\bf #1}\hfill#2\mbox{}\end{center}}} \newcommand{\hb}[1]{{\darkpurple \large \noindent\bf #1}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\con}{\equiv} \newcommand{\C}{\mathbf{C}} \renewcommand{\P}{\mathbf{P}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cF}{\mathcal{F}} \renewcommand{\O}{\mathcal{O}} \newcommand{\meet}{\bigcap} \newcommand{\et}{\mbox{\rm\tiny \'et}} \newcommand{\Het}{H_{\et}} \newcommand{\F}{\mathbf{F}} \newcommand{\R}{\mathbf{R}} \DeclareFontEncoding{OT2}{}{} % to enable usage of cyrillic fonts \newcommand{\textcyr}[1]{% {\fontencoding{OT2}\fontfamily{wncyr}\fontseries{m}\fontshape{n}% \selectfont #1}} \newcommand{\Sha}{{\mbox{\textcyr{Sh}}}} \newcommand{\Shaan}{\Sha_{\mbox{\tiny \rm an}}} \newcommand{\Z}{\mathbf{Z}} \newcommand{\T}{\mathbf{T}} \newcommand{\Q}{\mathbf{Q}} \newcommand{\h}{\mathfrak{h}} \newcommand{\Qbar}{{\overline{\Q}}} \newcommand{\isom}{\cong} \newcommand{\onto}{\rightarrow\!\!\!\!\rightarrow} \newcommand{\cross}{\times} \newcommand{\tensor}{\otimes} \newcommand{\conjeq}{\stackrel{\mbox{\tiny \red conj}}{=}} \newcommand{\vphi}{\varphi} \newcommand{\eps}{\varepsilon} \DeclareMathOperator{\divx}{div} \DeclareMathOperator{\HH}{H} \renewcommand{\H}{\HH} \DeclareMathOperator{\Gal}{Gal} \DeclareMathOperator{\Frob}{Frob} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\Pic}{Pic} \renewcommand{\div}{\divx} \DeclareMathOperator{\Jac}{Jac} \DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\cond}{cond} \DeclareMathOperator{\Mat}{Mat} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Ker}{Ker} \DeclareMathOperator{\Coker}{Coker} \DeclareMathOperator{\Res}{Res} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\Reg}{Reg} \DeclareMathOperator{\tor}{tor} \DeclareMathOperator{\ord}{ord} \newcommand{\sB}{\boldsymbol{\mathcal{B}}} \newcommand{\sM}{\boldsymbol{\mathcal{M}}} \newcommand{\sS}{\boldsymbol{\mathcal{S}}} \newcommand{\sW}{\boldsymbol{\mathcal{W}}} \newcommand{\abcd}[4]{\left( \begin{smallmatrix}#1\\#3\end{smallmatrix}\right)} \newcommand{\mtwo}[4]{\left( \begin{matrix}#1\\#3 \end{matrix}\right)} \title{{\darkred\large Explicitly Computing With Modular Abelian Varieties}} \author{{\purple William Stein\\Harvard University}} \date{February 6, 2004\\Center for Communications Research in Princeton\vspace{3ex}\\ \mbox{ } \hfill \pic{code}{4.5} \hfill \mbox{ } } \begin{document} \maketitle \comment{\begin{slide} \ha{Overview of Talk}{} \vspace{2ex} \begin{enumerate} \item Modular Abelian Varieties \item Computing With Modular Abelian Varieties \end{enumerate} \end{slide}} \begin{slide} \ha{Modular Abelian Varieties}{\captionpic{abel1}{Abel}} \ul{Abelian variety}: A complete group variety \hb{Examples:\vspace{-1ex}} \begin{enumerate} \item Elliptic curves, e.g., $y^2 = x^3 +ax + b$ \item Jacobians of curves \item Quotients of Jacobians of curves \end{enumerate} \end{slide} \begin{slide} \ha{Connection with Cryptography}{} Modular abelian varieties over finite fields provide a large source of groups that can be used for cryptography (e.g., Elliptic Curve Cryptography). I will focus on modular abelian varieties over infinite fields today, but the results are relevant for understanding the reductions of those varieties modulo primes. \end{slide} \begin{slide} \ha{The Modular Curve $X_1(N)$}{\captionpic{hecke1}{Hecke}} \vspace{2ex} Let $\h^*=\{z\in\C : \Im(z)>0\}\cup\P^1(\Q)$. \begin{enumerate} \item $X_1(N)_\C = \Gamma_1(N) \backslash \h^*$ \,\,(compact Riemann surface) \item $X_1(N)$ has natural structure of algebraic curve over $\Q$ \item $X_1(N)(\C) = \{ (E,P) : \ord(P) = N\}/\sim$ \,\,(moduli space) \end{enumerate} $$ \begin{tabular}{c|c|c|c|c|c|c|c} $N$ & $\leq 10$ & 11 & 13 & 37 & 169 & 512 & 2003\\\hline genus$(X_1(N))$ & 0 & 1 & 2 & 40 & 1070 & 7809 & \red{166167} \end{tabular} $$ \end{slide} \begin{slide} \ha{Modular Forms}{\captionpic{hecke1}{Hecke}} \vspace{1ex} \begin{enumerate} \item Cuspidal modular forms (of weight 2): $$ S_2(N) = \H^0\left(X_1(N),\Omega^1_{X_1(N)}\right) $$ \item $f\in S_2(N)$ has Fourier expansion in terms of $q(z)=e^{2\pi i z}$ $$ f = \sum_{n=1}^{\infty} a_n q^n $$ \item Hecke algebra ({\em commutative} ring): $$ \T = \Z[T_1,T_2,\ldots] \hookrightarrow \End(S_2(N)) $$ \end{enumerate} \end{slide} \begin{slide} \ha{The Modular Jacobian $J_1(N)$}{\captionpic{jacobi1}{Jacobi}} \begin{enumerate} \item Jacobian of $X_1(N)$: $$ J_1(N) = \Jac(X_1(N)) $$ \item $J_1(N)$ is an abelian variety over $\Q$ of dimension $g(X_1(N))$. \item The elements of $J_1(N)$ parameterize divisor classes on $X_1(N)$ of degree $0$. \end{enumerate} \end{slide} \begin{slide} \ha{Modular Abelian Varieties}{\captionpic{shimura2}{Shimura}} A {\darkred{\bf modular abelian variety}} $A$ over a number\\field $K$ is any abelian variety $A$ (over $K$) such\\ that there is a homomorphism $$ A \to J_1(N) $$ with finite kernel. \vspace{1ex} \end{slide} \begin{slide} \ha{Examples and Conjectures}{} {\LARGE \red Suppose $\dim A = 1$.} \begin{itemize} \item {\bf Theorem (Wiles, Breuil, Conrad, Diamond, Taylor).} \\ If $K=\Q$ then $A$ is modular. \item {\bf Theorem (Shimura).} If $A$ has CM then $A$ is modular. \item {\bf Definition:} $A$ over $\Qbar$ is a {\bf $\Q$-curve} if for each Galois conjugate $A^{\sigma}$ of $A$ there is an isogeny $A\to A^{\sigma}$ (an isogeny is a map with finite kernel).\\ {\bf Conjecture (Ribet, Serre).} Over $\Qbar$ the non-CM modular elliptic curves are exactly the $\Q$-curves. \end{itemize} \end{slide} \begin{slide} \ha{{\bf GL}$_2$-type}{\captionpic{ribet}{Ken Ribet}} {\bf Defn.} A simple abelian variety $A/\Q$ is of\\ {\bf $\GL_2$-type} if $$\End_0(A/\Q) = \End(A/\Q)\tensor\Q$$ is a number field of degree $\dim(A)$. Shimura associated $\GL_2$-type modular abelian varieties to $\T$-eigenforms: \begin{align*} f &= q + \sum_{n\geq 2} a_n q^n \in S_2(N)\\ I_f &= \Ker(\T \to \Q(a_1,a_2,a_3,\ldots)),\,\, T_n\mapsto a_n \end{align*} Abelian variety $A_f$ over $\Q$ of $\dim =[ \Q(a_1,a_2,\ldots):\Q]$: $$ A_f := J_1(N)/I_fJ_1(N) $$ {\bf Theorem (Ribet).} Shimura's $A_f$ is $\Q$-isogeny simple since $$\End_0(A_f/\Q)=\Q(a_2,a_3,\ldots).$$ Also there is an isogeny $J_1(N) \sim \prod_f A_f$, where the product is over Galois-conjugacy classes of~$f$. \hb{Conjecture. (Ribet)}\\ The simple modular abelian varieties $A$ over $\Q$ are exactly the simple abelian varieties over $\Q$ of $\GL_2$-type. Ribet proved that his conjecture follows from Serre's unproven conjectures on modularity of odd mod $p$ Galois representations. \end{slide} \begin{slide} \ha{2. Computing With Abelian Varieties}{\captionpic{meccah}{}} \hb{Goal:} Develop a systematic theory for computing\\ with modular abelian varieties. \hb{Basic Problems:} Presentation, isogeny testing, isomorphism testing, endomorphism ring, enumeration. \hb{Arithmetic Problems:} Special values of $L$-functions, computing Shafarevich-Tate groups, Tamagawa numbers, enumerating elements of isogeny class. \end{slide} \begin{slide} \ha{Presentation}{} Modular abelian varieties can be specified in many ways: - Equations\\ - Built from newform abelian varieties $A_f$\\ - Arise theoretically (e.g., Jacobians of Shimura curves). For all our questions today we will view a modular abelian variety as being defined in the following way. Any modular abelian variety $B$ can be obtained by quotienting an abelian subvariety $A\subset J_1(N)$ by a finite subgroup $G$. {\darkblue Thus we represent $B$ by giving a pair $(A,G)$, where $G\subset A\subset J_1(N)$. } \end{slide} \begin{slide} \ha{Specifing $A$}{} An inclusion $\vphi:A\hookrightarrow J_1(N)$ induces an inclusion on homology $$ \H_1(A,\Q) \hookrightarrow \H_1(J_1(N),\Q), $$ and $A$ is completely determined by the image of $\H_1(A,\Q)$ in the vector space $\H_1(J_1(N),\Q)$. {\darkblue \mbox{} \hspace{2ex}{\bf We give $A$ by giving a subspace $V=V_\Q\subset \H_1(J_1(N),\Q)$.}} \ha{Specifing $G$}{} By the Abel-Jacobi theory there is a canonical isomorphism $$ J_1(N)(\C)\isom \H_1(J_1(N),\R)/\H_1(J_1(N),\Z). $$ Likewise $A(\C)\isom V_\R/V_\Z$, where $V_\Z=V\meet \H_1(J_1(N),\Z)$, so $$ A(\C)_{\tor} \isom V_\Q/V_\Z. $$ {\darkblue \mbox{} \hspace{2ex}{\bf We give $G$ by giving finitely many elements of $V_\Q/V_\Z$. }} \end{slide} \begin{slide} \ha{Recognition Problem}{} \hb{Problem:} When does a subspace $V\subset \H_1(J_1(N),\Q)$ correspond to an abelian subvariety $A$ of $J_1(N)$ over $K$? \hb{Solution:} Given an isogeny decomposition of $J_1(N)$ over $K$ as a direct sum of simple abelian varieties, I have an algorithm to solve this problem. (It is straightforward to compute such a decomposition when $K=\Q$.) %(Related: Find intersection %of all abelian variety subspaces that contain $V$.) \hb{Problem:} Given a group $G$ defined by a finite list of elements of $V_\Q/V_\Z$, find the smallest number field over which $G$ is defined. This is important because if $G$ is defined over $K$, then $B=A/G$ is defined over $K$. \hb{Solution??:} I have not solved this problem, which is likely very difficult. \end{slide} \begin{slide} \ha{Modular Symbols}{\captionpic{manin_barcelona}{Manin}} Modular symbols provide a presentation of $$H_1(X_1(N),\Z)$$ on which one can give formulas for Hecke and other operators. They have been intensively studied by Birch, Manin, Shokurov, Mazur, Merel, Cremona, and others. \begin{verbatim} > M := CuspidalSubspace(ModularSymbols(Gamma1(11))); > Basis(M); [ -1/5*{-1/2, 0} + -2/5*{-1/4, 0} + 3/5*{-1/7, 0} + -1/5*{7/15,1/2}, -2/5*{-1/2, 0} + 1/5*{-1/4, 0} + 1/5*{-1/7, 0} + -2/5*{7/15,1/2} ] \end{verbatim} \end{slide} \begin{slide} \ha{Enumeration Problem Over $\Q$}{} \hb{Problem:} Give an algorithm to systematically enumerate every modular abelian variety over $\Q$. The isogeny classes of simple modular abelian varieties over $\Q$ are in bijection with {\em newforms}, which are eigenvectors for Hecke operators in the space $S_2(\Gamma_1(N))$ of modular forms. Using the Atkin-Lehner-Li theory of newforms, modular symbols, and linear algebra, we can thus enumerate the isogeny classes over $\Q$. I {\bf do not know} how to find all abelian varieties in an isogeny class, except when $A$ has dimension $1$, where it is solved. Maybe at least find several by intersecting $A\subset J_1(N)$ with other abelian varieties over $\Q$, quotienting out by intersection, and proving quotient is not isomorphic to $A$. \end{slide} \begin{slide} \ha{Example}{} {\begin{verbatim} > Factorization(J1(17)); [* , *] \end{verbatim}} \end{slide} \begin{slide} \ha{Enumeration Problem Over $\Qbar$}{} \hb{Problem:} Give an algorithm to systematically enumerate every modular abelian variety over $\Qbar$. There is a huge amount of work by Shimura, Ribet, Gonz\'alez, Lario, and others, but still nobody has given an algorithm to enumerate all isogeny classes of modular abelian varieties over $\Qbar$ explicitly. By explicit, I mean in the sense of giving defining data, i.e., a pair $(V, \,\, G\subset V_\Q/V_\Z)$. \hb{Obstructions:}\\ - Difficulty of constructing $\End(A_f/\Qbar)$ explicitly (I have an algorithm, but it is {\em way too slow} to be useful)\\ - Difficulty of decomposing $A_f/\Qbar$ as a product of simples, even given $\End(A_f/\Qbar)$. Need a good ``Meataxe'' over $\Q$. \end{slide} \begin{slide} \ha{Computing Endomorphism Rings}{} \hb{Problem:} Given a modular abelian variety $A$ over $K$, compute $\End(A)$ explicitly, i.e., give matrices in $\End(V)$ that generate $\End(A)$ as an abelian group. \hb{Solution:} When $A\subset J_1(N)$ is simple, $\End(A)\tensor \Q$ is a skew field, which can be computed. For example, if $K=\Q$, then $A=A_f$ is attached to a newform and $\End(A)\tensor\Q$ is generated by the image of the Hecke algebra. We can then find $\End(A)$ in $\End(A)\tensor\Q$ as the $\Z$-submodule of elements that preserve the lattice $V_\Z$. We can also explicitly compute $\Hom(A,B)$ for any modular abelian varieties $A$ and $B$, by writing $A$ and $B$ as simples, computing endomorphism algebras, and finding the $\Z$-module of homomorphisms that induce a map that fixes integral homology. \end{slide} \begin{slide} \ha{Example}{} {\small\begin{verbatim} > A := J0(33); A; Modular abelian variety J0(33) of dimension 3 and level 3*11 over Q > End(A); Group of homomorphisms from J0(33) to J0(33) > Basis(End(A)); [ Homomorphism from J0(33) to J0(33) (not printing 6x6 matrix), Homomorphism from J0(33) to J0(33) (not printing 6x6 matrix), Homomorphism from J0(33) to J0(33) (not printing 6x6 matrix), Homomorphism from J0(33) to J0(33) (not printing 6x6 matrix), Homomorphism from J0(33) to J0(33) (not printing 6x6 matrix) ] > Matrix(Basis(End(A))[2]); [ 0 1 0 0 0 -1] [ 0 1 0 0 0 0] [ 0 1 0 0 -1 0] [ 0 1 -1 1 -1 0] [ 0 1 -1 0 0 0] [-1 1 0 0 0 0] \end{verbatim}} \end{slide} \begin{slide} \ha{Isogeny Testing}{} \hb{Problem:} Given modular abelian varieties $A$ and $B$, determine whether or not $A$ is isogenous to $B$. Determine whether $A$ is isogenous to $B$ is easy, since we may assume $A$ and $B$ are attached to newforms $\sum a_n q^n$ and $\sum b_n q^n$, and then $A$ is isogenous to $B$ if and only if the newforms are Galois conjugate. \end{slide} \begin{slide} \ha{Isomorphism Testing}{} \hb{Problem:} Suppose $A$ is isogenous to $B$. Decide whether $A$ is isomorphic to $B$. I {\bf do not know how to do this} in general. Assume we have computed $\End(A)$, $\End(B)$, and $\Hom(A,B)$ explicitly. Given a basis for $\Hom(A,B)$, how do we know if some linear combination of that basis has determinant 1? It's not clear (to me). If $A$ and $B$ are both simple and have commutative endomorphism ring, then I found an algorithm to decide whether $A$ is isomorphic to $B$. This algorithm can be extended to abelian varieties that are products of such $A$, assuming the factors occur with multiplicity~1 (up to isogeny). However, I do not know in general how to decide whether $A\oplus A$ is isomorphic to $B\oplus B$, though I have a vague strategy that I think might work. \end{slide} \begin{slide} \ha{Algorithm for Testing Isomorphism}{} Suppose $A$ and $B$ are explicitly defined modular abelian varieties over $\Q$ that are both isogenous to an abelian variety $A_f$. The following algorithm determine whether $A$ is isomorphic to $B$. Let $H=\Hom(A,B)$. Both $A$ and $B$ are given explicitly by pairs $(V,G_1)$ and $(V,G_2)$, so we can compute an isogeny $f:B\to A$. Let $H_f=\{ \phi \circ f : \phi \in H\} \subset \End(B)$. Note that $A$ is isomorphic to~$B$ if and only if $H_f$ contains an element of degree $\deg(f)$. Also note that $H_f$ has finite index in $\End(B)$. By hypothesis $K=\End(B)\tensor\Q$ is the field generated by the Fourier coefficients of~$f$. The norm of an element of~$K$ is the positive square root of the degree of the corresponding homomorphism (see Milne in Cornell-Silverman, pg 126, Prop. 12.12). Thus if $\deg(f)$ is not a perfect square, then there can be no element of $B$ of degree $\deg(f)$, so $A$ is not isomorphic to $B$. Thus suppose $\deg(f)=d^2$. Typically there will be infinitely many element in $\O_K$ of norm $d$, but there are only finitely many up to units. There is an algorithm, which involves computing the class group of $\O_K$, which enumerates representive elements of $\O_K$ of norm $d$, up to units (e.g., the {\tt NormEquation} command in MAGMA). Thus suppose we have computed representative elements $z_1,\ldots, z_n$ of the elements of $\O_K$ with norm~$d$. Then $A$ is isomorphic to $B$ if and only if there is a unit $u$ and a $z_i$ such that $u^{-1}z_i \in H_f \subset K$. Equivalently, such that $z_i \in u H_f$. There are only finitely many possibilities for $u H_f$, since $H_f$ has finite index in $\O_K$ and $[\O_K: u H_f] = [\O_K:H_f]$, since $\O_K = u\O_K$. We can thus list all subgroups $uH_f$ (since we can compute generaturs for $\O_K^*$) and hence determine whether $H_f$ contains an element of norm $d$, as required. \end{slide} \comment{\begin{slide} \ha{\Large \begin{minipage}{4in} Thank you for\\inviting me!\end{minipage}}{\pic{kite2}{3}} \vspace{1in} \hb{Acknowledgements:}\\ Papers of Ken Ribet, Goro Shimura, and Joan Lario.\\ Conversations with John Cannon, Enrique Gonzalez, David Kohel, Barry Mazur, Allan Steel\\ \vspace{-2ex} \end{slide}} \end{document}