\documentclass[handout]{beamer}
\usetheme{CambridgeUS}
\setbeamertemplate{navigation symbols}{}
\setbeamercovered{transparent=50}
\usepackage{hyperref}
\usepackage[all]{xy}
\hypersetup{
colorlinks = true,
linkcolor = blue
}
\usepackage{sagetex}
\newcommand{\AAA}{\mathbb{A}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\Fp}{\mathbb{F}_p}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\Qp}{\mathbb{Q}_p}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\Zp}{\mathbb{Z}_p}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\frakp}{\mathfrak{p}}
\DeclareMathOperator{\ab}{ab}
\DeclareMathOperator{\alg}{alg}
\DeclareMathOperator{\Br}{Br}
\DeclareMathOperator{\NS}{NS}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\odd}{odd}
\DeclareMathOperator{\PGL}{PGL}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\SO}{SO}
\DeclareMathOperator{\trc}{trc}
\begin{document}
\title[Linear algebra and tabulation of eigenforms]{Mod 2 linear algebra and \\ tabulation of rational eigenforms}
\author[K.S. Kedlaya]{Kiran S. Kedlaya}
\institute[UC San Diego]{Department of Mathematics, University of California, San Diego \\
\texttt{kedlaya@ucsd.edu} \\
\url{http://kskedlaya.org/slides/} (see also
\href{https://cloud.sagemath.com/projects/f1e7d26f-7a19-402c-97da-4f4dae623ceb/files/london-talk/}{this SageMathCloud project})}
\date[London, September 9, 2016]{Automorphic forms: theory and computation \\
King's College, London \\
September 9, 2016}
\AtBeginSection[]
{
\begin{frame}<beamer>
\frametitle{Contents}
\tableofcontents[currentsection]
\end{frame}
}
\begin{frame}
\titlepage
Joint work \emph{in progress} with Anna Medvedovsky (MPI, Bonn).
\medskip
\tiny
Kedlaya was supported by NSF grant DMS-1501214 and UCSD (Warschawski chair).
\end{frame}
\section{Introduction}
\begin{frame}
\frametitle{A fool's errand?}
Over the past two decades, Cremona has developed a highly efficient algorithm for enumerating rational $\Gamma_0(N)$-newforms of weight 2 and their associated elliptic curves (which we now know exhausts all elliptic curves over $\QQ$), documented in \href{http://homepages.warwick.ac.uk/~masgaj/book/fulltext/index.html}{his book \emph{Algorithms for Modular Elliptic Curves}}.
\medskip
\pause
Cremona also has developed a highly efficient C/C++ implementation of this algorithm, which to date has enumerated all elliptic curves over $\QQ$ of conductor $\leq 379998$ (see \href{http://pari.math.u-bordeaux.fr/}{Pari}, \href{http://magma.maths.usyd.edu.au/magma}{Magma}, \href{http://www.sagemath.org}{Sage}, or \href{http://www.lmfdb.org}{LMFDB}).
\medskip
\pause
Further extension of these tables would have, among other applications, consequences for the effective solution of $S$-unit equations; see \href{http://arxiv.org/abs/1605.06079}{arXiv:1605.06079} (von K\"anel-Matschke).
\medskip
\pause
Is there room for improvement here?
It is unlikely that any easy optimization in the algorithm or implementation has been missed!
\end{frame}
\begin{frame}[fragile]
\frametitle{Perhaps not...}
Most positive integers do not occur as conductors of rational elliptic curves. For example, in the range 378000-378999,
\href{http://www.lmfdb.org/EllipticCurve/Q/?start=0&conductor=378000-378999&jinv=&include_cm=include&rank=&torsion=&torsion_structure=&sha=&surj_primes=&surj_quantifier=include&nonsurj_primes=&optimal=&count=100}{this LMFDB query} returns 5885 curves of 566 different conductors:
\pause
\begin{sagecommandline}
sage: load("ec-378000-378999.sage");
sage: l = [EllipticCurve(i) for i in data];
sage: l2 = [i.conductor() for i in l];
sage: s = set(l2);
sage: len(s) \end{sagecommandline}
\pause
This is consistent with the expectation that the number of positive integers up to $X$ which occur as conductors is $\sim C X^{5/6}$ (this being true for heights).
\end{frame}
\begin{frame}
\frametitle{TSA Precheck for conductors?}
For a given $N$, the rate-limiting step in Cremona's computation of the elliptic curves of conductor $N$ occurs at the very beginning, before one knows whether or not any such curves exist. (More on this shortly.)
\medskip
\pause
Consequently, one can try to speed up the tabulation by prefixing a fast computation that cuts down the list of eligible conductors. For example, Cremona already excludes $N$ divisible by $2^9$, $3^6$, or $p^3$ for any prime $p >3$; but these form only $1.6\%$ of all levels.
\medskip
\pause
We discuss some precomputations based on:
\begin{itemize}
\pause
\item
linear algebra over $\FF_2$;
\pause
\item
results about mod 2 modular forms, including Serre reciprocity.
\end{itemize}
\pause
This will serve as an excuse to discuss some questions about mod 2 Hecke algebra multiplicities to which we have not found complete answers.
\end{frame}
\section{Review of Cremona's algorithm}
\begin{frame}
\frametitle{A high-level description}
\[
\xymatrix{
\mbox{Positive integer $N$ (whose divisors are already done)}
\ar[d] \\
\mbox{Rational (old and new) Hecke eigensystems for $S_2(\Gamma_0(N), \QQ)$}
\ar[d] \\
\mbox{Rational newforms for $S_2(\Gamma_0(N), \QQ)$}
\ar[d] \\
\mbox{Elliptic curves over $\QQ$ of conductor $N$}
}
\]
\pause
The first step is rate-limiting because very few possibilities survive to the later steps. We thus focus on this step; see Cremona's book for discussion of the others.
\end{frame}
\begin{frame}
\frametitle{Computation of eigensystems}
Cremona computes not with $S_2(\Gamma_0(N), \QQ)$, but with the homology of $X_0(N)$ as represented via Manin's modular symbols. For $p \not| N$, the action of $T_p$ is given by a sparse\footnote{This crucial property would be lost if we restricted to newforms; we must thus identify new eigensystems as such solely by comparing them to old eigensystems.} integer\footnote{In some cases, Cremona's code returns $2T_p$ because the computed matrix of $2T_p$ is not integral. However, we only work with the minus eigenspace for complex conjugation, where we have yet to observe a failure of integrality.} matrix. By strong multiplicity one, for the purpose of distinguishing eigensystems we may ignore $T_p$ for $p |N$ (which are not implemented by Cremona).
\medskip
\pause
Let $p$ be the smallest prime not dividing $N$. The rate-limiting step is to compute the kernel of $T_p - a_p$ for each $a_p \in [-2\sqrt{p}, 2 \sqrt{p}] \cap \ZZ$. This involves matrices of size $\sim N/12$.
\medskip
\pause
By contrast, the dimensions of these kernels are far smaller. Thus, further decomposing these kernels into joint eigenspaces is of negligible difficulty.
\end{frame}
\begin{frame}
\frametitle{Linear algebra (not) over $\QQ$}
The complexity of linear algebra over a field is typically costed in terms of field operations. This gives reasonable results over a finite field.
\medskip
\pause
However, this costing model does not work well over $\QQ$: the cost of arithmetic operations depends on the heights of the operands. Moreover, direct use of conventional algorithms (e.g., Gaussian elimination) tends to incur \emph{intermediate coefficient blowup}: heights of matrix entries increase steadily throughout the computation.
\medskip
\pause
However, one can typically bound the height of the result of a computation (e.g., determinant) directly in terms of the heights of the entries. One can then use a \emph{multimodular} approach: reduce from $\QQ$ to various finite fields, do the linear algebra there, and reconstruct the answer using the Chinese remainder theorem. For instance, this is implemented in Magma and FLINT (the latter wrapped in Sage).
\end{frame}
\begin{frame}
\frametitle{Short-circuiting the multimodular approach}
To compute the kernel of the matrix representing $T_p - a_p$ on modular symbols,
it is not necessary to use as many primes as theoretically required by the height bound. One can instead guess the kernel based on fewer primes, and then directly verify the result by multiplying with the original matrix. This is particularly cheap because the matrix is sparse.
\medskip
\pause
In practice, Cremona works modulo the single prime $\ell = 2^{30}-35$; experimentally, this always suffices to determine the kernel over $\QQ$.
It would be worth comparing with a multimodular approach starting from $\ell=2$ and guessing after each prime.
\end{frame}
\begin{frame}[fragile]
\frametitle{Linear algebra over finite fields (Magma)}
How does the complexity of linear algebra over $\FF_{\ell}$ vary with $\ell$? A sensible behavior is exhibited by Magma 2.21-11:
\pause
\begin{verbatim}
> C := ModularSymbols(100001, 2, -1);
> M := HeckeOperator(C, 2);
> M2 := Matrix(GF(2), M); time Rank(M2);
9047
Time: 1.710
> M3 := Matrix(GF(3), M); time Rank(M3);
9085
Time: 4.220
> p := 2^30 - 35;
> Mp := Matrix(GF(p), M); time Rank(Mp);
9091
Time: 17.160
\end{verbatim}
\end{frame}
\begin{frame}
\frametitle{Linear algebra over finite fields (Sage)}
By contrast, in Sage, linear algebra over $\FF_{\ell}$ is far worse than Magma for $\ell > 2$ (and essentially unusable for $p >2^{16}$), but notably better for $\ell=2$ (see \href{https://cloud.sagemath.com/projects/f1e7d26f-7a19-402c-97da-4f4dae623ceb/files/london-talk/slides-demo.sagews}{this demo}).
\medskip
\pause
This is because for $\ell=2$, Sage uses the \href{https://bitbucket.org/malb/m4ri}{m4ri} library by Gregory Bard, which implements the ``Method of four Russians'' algorithm.
This algorithm makes special\footnote{There is a bitslicing approach that adapts the method to other small finite fields, but serious implementation seems not to have been pursued. See \href{http://128.84.21.199/abs/0901.1413?context=cs}{arXiv:0901.1413}.} use of the graph-theoretic interpretation of binary matrices, in order to save some logarithmic factors ahead of the Strassen crossover.
\medskip
\pause
This raises the question: can we gain useful prescreening information by working solely over $\FF_2$? A precise analysis of this question involves some interesting ingredients!
\end{frame}
\section{Prescreening, part 1: invertibility mod 2}
\begin{frame}
\frametitle{A general framework for prescreening}
To simplify matters, hereafter we only consider odd $N$, so that we can take $p=2$ in Cremona's algorithm. In this case, it is natural to modify our high-level description as follows:
\[
\xymatrix{
\mbox{Odd positive integer $N$, integer $e \in \{0,1\}$}
\ar[d] \\
\mbox{Rational Hecke eigensystems for $S_2(\Gamma_0(N), \QQ)$
with $a_2 \equiv e \pmod{2}$}
\ar[d] \\
\mbox{Rational newforms for $S_2(\Gamma_0(N), \QQ)$ with $a_2 \equiv e \pmod{2}$}
\ar[d] \\
\mbox{Elliptic curves over $\QQ$ of conductor $N$ with $a_2 \equiv e \pmod{2}$}
}
\]
\pause
Reminder: the options for $a_2$ are $-2, 0, 2$ if $e=0$, and $-1, 1$ if $e=1$.
\end{frame}
\begin{frame}
\frametitle{Hecke matrices mod 2: some stupid models}
If the matrix of the $\ZZ$-matrix $T_2 - e$ is invertible mod 2, then its determinant is odd, so $T_2$ has no $\QQ$-eigenvalues congruent to $e$ mod 2.
How often does this occur?
\medskip
\pause
Baseline: a random matrix over $\FF_2$ fails to be invertible with probability
\[
1 - \prod_{n=1}^\infty (1 - 2^{-n}) \approx 71.1 \%.
\]
\pause
Since $T_2$ is self-adjoint in some basis, a better baseline is a random \emph{symmetric} matrix over $\FF_2$, which fails to be invertible with probability
\[
1 - \prod_{n=1}^\infty (1 - 2^{1-2n}) \approx 58.1 \%.
\]
\end{frame}
\begin{frame}
\frametitle{Why are these models stupid?}
These models are stupid for (at least) two reasons.
\begin{itemize}
\pause
\item
For $N$ composite, we get a contribution from oldforms, so the probability that $T_2-e$ has nontrivial kernel mod 2 is much higher than for $N$ prime. (This also makes this test nearly useless for $N$ compossite.)
\pause
\item
The existence of a nontrivial kernel mod 2 is explained by Serre reciprocity.
Consequently, the correct probability modeling will be given by certain heuristics concerning the distribution of number fields.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Ranks mod 2: data for prime levels}
For prime $N < 500000$ and $e=0,1$, we used Sage (calling Cremona's eclib and Bard's m4ri)
to determine whether $T_2 - e$ has nontrivial kernel mod 2. Estimated runtime: about 3 weeks on 24 Intel Xeon X5690 cores (3.47GHz).
\medskip
\pause
Results (see \href{https://cloud.sagemath.com/projects/f1e7d26f-7a19-402c-97da-4f4dae623ceb/files/london-talk/data-analysis-prime-level.sagews}{this demo} for some data analysis):
\pause
\begin{center}
\begin{tabular}{c|c|c}
$N \pmod{8}$ & $e=0$ & $e=1$ \\
\hline
1 & 16.8\% & Always \\
3 & Always for $N>3$ & Always for $N > 163$ \\
5 & 42.2\% & Always for $N > 37$ \\
7 & 17.3\% & 47.9\%
\end{tabular}
\end{center}
\pause
We will explain the ``always'' statements a bit later.
In any case, for prime $N$, $38.7\%$ of the kernel calculations over $\QQ$ can be short-circuited by working over $\FF_2$; that said, prime levels are already handled by Stein-Watkins and Bennett well beyond the range of interest.
\end{frame}
\section{Prescreening, part 2: multiplicities mod 2}
\begin{frame}
\frametitle{Eigenvalue multiplicities}
This time, instead of simply testing whether $T_2 - e$ is invertible mod 2, let us compute the multiplicity of 0 as a generalized eigenvalue of the reduced matrix. This equals the number of eigenvalues of $T_2$ in $\overline{\QQ}_2$ in the open unit ball around $e$. (This computation is a bit more expensive than testing invertibility, but still quite efficient.)
\medskip
\pause
This time, we can rule out $(N,e)$ if we can account for the entire multiplicity using mod 2 representations which cannot lift to $\QQ$ (e.g., because they take values in a larger field than $\FF_2$). For $N$ composite, we also remove the multiplicity coming from divisors of $N$.
\medskip
\pause
Warning: the dimension of the kernel mod 2 is not mathematically significant! It is an artifact of the choice of basis used to express $T_2$, which is not the one coming from the integral Hecke algebra.
\end{frame}
\begin{frame}
\frametitle{Some data analysis}
\end{frame}
\begin{frame}
\frametitle{Data collection using Google Compute Engine}
Google Compute Engine is a cloud platform (like Amazon EC2) which seems particularly well-adapted for mathematics research. SageMathCloud is built on GCE, and LMFDB is hosted using GCE.
\medskip
\pause
Using GCE, one can easily\footnote{At least using free software! Using Magma this way is not straightforward.} run a trivially parallel computation on large numbers of virtual machines. Pricing is based on memory, disk usage, and CPU-minutes, with hugely preferential pricing for \emph{preemptible} VMs.
\medskip
\pause
We used VMs totaling 128 cores\footnote{These only ran at 2.2GHz, but had much bigger L3 cache than my ``faster'' 24-core machine; in practice, this seemed to provide some advantage.}, to compute eigenvalue multiplicities of $T_2 - e$ for $e=0,1$ for all odd $N < 200000$. This took 5.5 days\footnote{Wall time. Due to preemptibility and other factors, CPU uptime was somewhat less.} at a cost\footnote{This ``cost'' was actually a promotional credit; we did not optimize it heavily.} of about \$250. See \href{https://cloud.sagemath.com/projects/f1e7d26f-7a19-402c-97da-4f4dae623ceb/files/london-talk/data-analysis-odd-level.sagews}{this demo} for some data analysis.
\end{frame}
\section{Some theoretical analysis}
\begin{frame}
\frametitle{Lower bounds for multiplicities}
Suppose (for convenience) that $N$ is squarefree. We will obtain the following lower bounds on the eigenvalue multiplicities mod 2:
\begin{center}
\begin{tabular}{c|c|c}
$N \pmod{8}$ & Multiplicity for $e=0$ & Multiplicity for $e=1$ \\
\hline
1 & 0 & $2 \overline{\#} \frac{K(N)}{\langle \frakp_2 \rangle} + \overline{\#} K(-N) + 1$ \\
3 & $\overline{\#} K_2(-N)- \overline{\#} K(-N)$
& $\overline{\#} K(N) + 2 \overline{\#} K(-N)$ \\
5 & $\overline{\#} K_2(N)-\overline{\#} K(N)$ & $2 \overline{\#} K(N) + \overline{\#} K(-N)$ \\
7 & 0 & $\overline{\#} K(N) + 2 \overline{\#} \frac{K(-N)}{\langle \frakp_2 \rangle}$
\end{tabular}
\end{center}
\pause
Notation in this table:
\begin{itemize}
\item
for any abelian group $G$, $\overline{\#} G = \frac{1}{2} (\# G_{\odd} - 1)$;
\item
$K(\pm N), K_2(\pm N)$ are the class group, 2-ray class group of $\QQ(\sqrt{\pm N})$;
\item
$\frakp_2$ is a prime of $\QQ(\sqrt{\pm N})$ above 2.
\end{itemize}
\pause
We will also see from data that these bounds are \emph{very often} not best possible.
\end{frame}
\begin{frame}
\frametitle{Contributors to eigenvalue multiplicity}
\begin{itemize}
\item
Excluding the $+1$ for $N \equiv 1 \pmod{8}$, each lower bound for $e=1$ is a sum of contributions arising (via Serre reciprocity) from dihedral representations associated to characters of $G = \Gal(H/E)$, where $E = \QQ(\sqrt{\pm N})$ and $H$ is the maximal odd-order abelian unramified extension of $K$ in which the primes above 2 split completely.
\pause
\item
Each lower bound for $e=0$ is a sum of contributions arising from dihedral representations associated to characters of $G_2 = \Gal(H_2/E)$ not factoring through $G$, where $H_2$ is analogous to $H$ except that ramification at 2 is now allowed.
\pause
\item
The extra contribution of $1$ for $N \equiv 1 \pmod{8}$, $e=1$ comes from Eisenstein ideals above 2 in the Hecke algebra.
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Additional multiplicity, explained and unexplained}
The previous discussion does not explain the factors of 2 appearing in the $e=1$ multiplicities. These arise from an observation of Edixhoven: there is a ``degeneracy map''
\[
S_1(\Gamma_0(N), \overline{\FF}_2)^{\oplus 2}_{\mathrm{Katz}} \to S_2(\Gamma_0(N), \overline{\FF}_2)_{\mathrm{Katz}}
\]
which ensures that each representation which is unramified at 2 contributes at least 2. This completes the explanation of the table.
\medskip
\pause
However, experimentally it seems that additional multiplicities appear.
For example:
\begin{itemize}
\pause
\item
for $e=1$, \emph{all} of the class group terms should carry a factor of 2;
\item
for $N \equiv 5 \pmod{8}$, the $e=0$ terms should also carry a factor of 2;
\item
there should be additional contributions from even parts of class groups (possibly explained by exhibiting suitable Galois deformations);
\item
there are failures of strong multiplicity 1 mod 2 (Kilford, Wiese).
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{A basic example}
For $N = 89$, all 7 of the eigenvalues of $T_2$ on $S_2(\Gamma_0(N), \FF_2)$ equal 1. As per \href{http://www.lmfdb.org/ModularForm/GL2/Q/holomorphic/89/2/?group=0}{LMFDB}, this includes one rational Eisenstein-at-2 newform
(89.2.1.b), plus two others which are congruent to each other mod 2, one rational (89.2.1.a) and one not (89.2.1.c).
\medskip
\pause
We thus have a unique dihedral representation contributing 6 to the multiplicity of $e=1$. Is there a generic reason for this?
\end{frame}
\begin{frame}
\frametitle{Eisenstein ideals revisited}
There is a further source of additional multiplicity for $N$ composite: for $e=1$, there is \emph{always} an Eisenstein contribution no matter how $N$ reduces mod 8 (Takagi, Yoo).
\medskip
\pause
This means that as it stands, for $N$ composite, this precomputation is of some use for $e=0$ but useless for $e=1$. However, the work of Yoo gives a detailed description of Eisenstein ideals (at least for $N$ squarefree). Perhaps this can be used to make 2-adic computations of forms which are Eisenstein mod 2?
\end{frame}
\section{Future prospects}
\begin{frame}
\frametitle{An alternative to modular symbols}
In his 2016 Dartmouth PhD thesis (under John Voight, with additional contributions from Gonzalo Tornar\'\i a), Jeffery Hein develops a construction of Birch into an algorithm for computing Hecke operators on $S_k(\Gamma_0(N), \QQ)$ for $k \geq 2$ and $N$ squarefree\footnote{This condition has since been relaxed to require only that $N$ is not a perfect square.} using an analogue of the ``method of graphs'' replacing isogenies of supersingular elliptic curves with $p$-neighbors of ternary quadratic forms.
\medskip
\pause
In this approach, one gets direct access to spaces of newforms of specified Atkin-Lehner involution type; this is highly advantageous for calculations in large composite (but squarefree) level. Moreover, the matrices that are obtained are automatically defined over $\ZZ$, so one may work directly mod 2 without having to change basis (unlike in the current Sage or Magma packages).
\end{frame}
\begin{frame}
\frametitle{Higher weights}
As David Roberts described in his talk, for weights above 2 one expects rational newforms to occur rather infrequently. The methods we have described could in principle be used to investigate this further.
\medskip
\pause
One catch is that matrices of higher weight Hecke operators computed using modular symbols, as in Magma and Sage, tend to have nontrivial denominators. The method of Birch--Hein--Tornar\'\i a--Voight does not suffer from this defect.
\end{frame}
\end{document}
