Computational Aspects of Modular Forms and Galois Representations: How One Can Compute in Polynomial Time the Value of Ramanujan's Tau at a Prime ... Studies) (Annals of Mathematics Studies, 176) - Softcover

Edixhoven, Bas; Couveignes, Jean–marc; De Jong, Robin; Merkl, Franz; Bosman, Johan

Softcover

ISBN 10: 0691142025 ISBN 13: 9780691142029

Publisher: Princeton University Press, 2011

Synopsis

Modular forms are tremendously important in various areas of mathematics, from number theory and algebraic geometry to combinatorics and lattices. Their Fourier coefficients, with Ramanujan's tau-function as a typical example, have deep arithmetic significance. Prior to this book, the fastest known algorithms for computing these Fourier coefficients took exponential time, except in some special cases. The case of elliptic curves (Schoof's algorithm) was at the birth of elliptic curve cryptography around 1985. This book gives an algorithm for computing coefficients of modular forms of level one in polynomial time. For example, Ramanujan's tau of a prime number p can be computed in time bounded by a fixed power of the logarithm of p. Such fast computation of Fourier coefficients is itself based on the main result of the book: the computation, in polynomial time, of Galois representations over finite fields attached to modular forms by the Langlands program. Because these Galois representations typically have a nonsolvable image, this result is a major step forward from explicit class field theory, and it could be described as the start of the explicit Langlands program. The computation of the Galois representations uses their realization, following Shimura and Deligne, in the torsion subgroup of Jacobian varieties of modular curves. The main challenge is then to perform the necessary computations in time polynomial in the dimension of these highly nonlinear algebraic varieties. Exact computations involving systems of polynomial equations in many variables take exponential time. This is avoided by numerical approximations with a precision that suffices to derive exact results from them. Bounds for the required precision--in other words, bounds for the height of the rational numbers that describe the Galois representation to be computed--are obtained from Arakelov theory. Two types of approximations are treated: one using complex uniformization and another one using geometry over finite fields. The book begins with a concise and concrete introduction that makes its accessible to readers without an extensive background in arithmetic geometry. And the book includes a chapter that describes actual computations.

About this title

About the Author

Bas Edixhoven is professor of mathematics at the University of Leiden. Jean-Marc Couveignes is professor of mathematics at the University of Toulouse le Mirail. Robin de Jong is assistant professor at the University of Leiden. Franz Merkl is professor of applied mathematics at the University of Munich. Johan Bosman is a postdoctoral researcher at the Institut fur Experimentelle Mathematik in Essen, Germany.

Excerpt. © Reprinted by permission. All rights reserved.

Computational Aspects of Modular Forms and Galois Representations

How One Can Compute in Polynomial Time the Value of Ramanujan's Tau at a Prime

PRINCETON UNIVERSITY PRESS

Copyright © 2011 Princeton University Press
All right reserved.
ISBN: 978-0-691-14202-9

Contents

Preface........................................................................................................ixAcknowledgments................................................................................................xAuthor information.............................................................................................xiDependencies between the chapters..............................................................................xiiChapter 1 Introduction, main results, context by B. Edixhoven..................................................1Chapter 2 Modular curves, modular forms, lattices, Galois representations by B. Edixhoven......................29Chapter 3 First description of the algorithms by J.-M. Couveignes and B. Edixhoven.............................69Chapter 4 Short introduction to heights and Arakelov theory by B. Edixhoven and R. de Jong.....................79Chapter 5 Computing complex zeros of polynomials and power series by J.-M. Couveignes..........................95Chapter 6 Computations with modular forms and Galois representations by J. Bosman..............................129Chapter 7 Polynomials for projective representations of level one forms by J. Bosman...........................159Chapter 8 Description of X15l/by B. Edixhoven..................................................................173Chapter 9 Applying Arakelov theory by B. Edixhoven and R. de Jong..............................................187Chapter 10 An upper bound for Green functions on Riemann surfaces by F. Merkl..................................203Chapter 11 Bounds for Arakelov invariants of modular curves by B. Edixhoven and R de Jong......................217Chapter 12 Approximating Vf over the complex numbers by J.-M. Couveignes............................257Chapter 13 Computing Vf modulo p by J.-M. Couveignes................................................337Chapter 14 Computing the residual Galois representations by B. Edixhoven.......................................371Chapter 15 Computing coefficients of modular forms by B. Edixhoven.............................................383Epilogue.......................................................................................................399Bibliography...................................................................................................403Index..........................................................................................................423

Chapter One

Introduction, main results, context

by Bas Edixhoven

1.1 STATEMENT OF THE MAIN RESULTS

As the final results in this book are about fast computation of coefficients of modular forms, we start by describing the state of the art in this subject.

A convenient way to view modular forms and their coefficients in this context is as follows, in terms of Hecke algebras. For N and k positive integers, let S_k([Lambda]₁(N)) be the finite dimensional complex vector space of cusp forms of weight k on the congruence subgroup [Lambda]₁(N) / of SL₂(Z). Each f in S_k([Lambda]₁(N)) has a power series expansion [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], a complex power series converging on the open unit disk. These an(f) are the coefficients of f that we want to compute, in particular for large n. For each positive integer n we have an endomorphism T_n of S_k([Lambda]₁(N)), and we let T(N, k) denote the sub-Z-algebra of S_k([Lambda]₁(N)) generated by them. The T(N, k) are commutative, and free Z-modules of rank the dimension of S_k([Lambda]₁(N)), which is of polynomially bounded growth in N and k. For each N, k, and n one has the identity a_n(f) = a₁ (T_n f). The C-valued pairing between S_k([Lambda]₁(N)) and T(N, k) given by (f, t) [??] a₁(tf) identifies S_k([Lambda]₁(N)) with the space of Z-linear maps from T(N, k) to C, and we can write f (T_n) for a_n(f). All together this means that the key to the computation of coefficients of modular forms is the computation of the Hecke algebras T(N, k) and their elements T_n. A modular form f in S_k([Lambda]₁(N)) is determined by the f(T_i) with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], hence if T_n is known as a Z-linear combination of these T_i, then f(T_n) can be computed as the same Z-linear combination of the f(T_i).

The state of the art in computing the algebras T(N, k) can now be summarized as follows.

There is a deterministic algorithm that on input positive integers N and k ≥ 2, computes T(N, k): it gives a Z-basis and the multiplication table for this basis, in running time polynomial in N and k. Moreover, the Hecke operator T_n can be expressed in this Z-basis in deterministic polynomial time in N, k and n.

We do not know a precise reference for this statement, but it is rather obvious from the literature on calculations with modular forms for which we refer to William Stein's book [Ste2], and in particular to Section 8.10.2 of it. The algorithms alluded to above use that S_k([Lambda]₁(N)), viewed as R-vector space, is naturally isomorphic to the R-vector space obtained from the so-called "cuspidal subspace":

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

in group cohomology. Here, Z[x, y_k-2 is the homogeneous part of degree k-2 of the polynomial ring Z[x, y on which SL₂(Z) acts via its standard representation on Z[x, y1. In this way, H¹([Lambda]₁(N) Z[x, y_{k-2cusp, modulo its torsion subgroup, is a free Z-module of finite rank that is a faithful T(N, k)-module, and the action of the Tn is described explicitly. The algorithms then use a presentation of H¹([Lambda]1(N), Z[x, yk-2)cusp} in terms of so-called "modular symbols" and we call them therefore modular symbols algorithms. The theory of modular symbols was developed by Birch, Manin, Shokurov, Cremona, Merel, .... It has led to many algorithms, implementations, and calculations, which together form the point of departure for this book.

The computation of the element T_n of T(N, k), using modular symbols algorithms, involves sums in which the number of terms grows at least linearly in n. If one computes such sums by evaluating and adding the terms one by one, the computation of T_n, for N and k fixed, will take time at least linear in n, and hence exponential in log n. The same is true for other methods for computing T_n that we know of: computations with q-expansions that involve multiplication of power series, using linear combinations of theta series, the "graph method" of Mestre and Oesterlé, and the Lefschetz trace formula for correspondences, holomorphic or not. Efforts to evaluate the encountered sums more quickly seem to lead, in each case, to the problem of computing coefficients of modular forms. For example, the graph method leads to the problem of quickly computing representation numbers of integer quadratic forms in 4 variables. In the case of the trace formula, there are maybe only O([square root of n]) terms, but they contain class numbers of imaginary quadratic orders, these numbers being themselves directly related to coefficients of modular forms of half integral weight.

Let us now state one of the main results in this book, Theorem 15.2.1.

Assume that the generalized Riemann hypothesis (GRH) for zeta functions of number fields holds. There exists a deterministic algorithm that on input positive integers n and k, together with the factorization of n into prime factors, computes the element T_n of T(1, k) in running time polynomial in k and log n.

The restriction to modular forms of level 1 in this result is there for a technical reason. The result will certainly be generalized to much more general levels; see the Epilogue. The condition that the factorization of n into primes must be part of the input is necessary because we do not have a polynomial time algorithm for factoring integers. Conversely, see Remark 2.2.4 for evidence that factoring is not harder than computing coefficients of modular forms.

Let us describe how the computation of Galois representations is used for the computation of T_n. Standard identities express T_n in terms of the T_p for p dividing n. These T_p are computed, via the LLL basis reduction algorithm, from sufficiently many of their images under morphisms f from T(1, k) to finite fields, analogously to Schoof's algorithm for counting points of an elliptic curve over a finite field. Indeed, for such an f from T(1, k) to F, with p not the characteristic, l, say, of F, the image f(T_p) is equal to the trace of ρ_f(Frob_p), where ρ_f: Gal(Q/Q) -> GL₂(F) is the Galois representation attached to f, and ρ_{f(Frobp) a Frobenius element at p. The representation ρf is characterized by the following three conditions: it is semisimple, it is unramified outside l, and for all prime numbers p [not equal to] l one has}

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is the main result of this book, Theorem 14.1.1, plus some standard computational number theory, that enables us to compute ρ_{f(Frobp) in time polynomial in k, #F, and log p (note the log!). Under GRH, existence of sufficiently many maximal ideals of small enough index is guaranteed. We partly quote Theorem 14.1.1:}

There is a deterministic algorithm that on input a positive integer k, a finite field F, and a surjective ring morphism f from T(1, k) to F such that the associated Galois representation ρ.sub>f : Gal(Q/Q) -> GL₂(F) is reducible or has image containing GL₂(F), computes ρ_f in time polynomial in k and #F.

By "computing ρ_f" we mean the following. Let K_f [subset] [bar.Q] be the finite Galois extension such that ρ_f factors as the natural surjection from Gal([bar.Q]/Q) to Gal(K_f/Q), followed by an injection into GL2.F/. Then to give ρ_f means to give K_f as Q-algebra, in terms of a multiplication table with respect to a Q-basis, together with a list of all elements of Gal(K.sub>f/Q), as matrices with coefficients in Q, and, for each σ in Gal(K.sub>f/Q), to give the corresponding element ρ_f(σ) of GL₂(F).

Before we describe in more detail, in the next sections, some history and context concerning our main results, we give one example and make some brief remarks. Many of these remarks are treated with more detail farther on.

The first nontrivial example is given by k = 12. The space of cuspidal modular forms of level one and weight 12 is one-dimensional, generated by the discriminant modular form [Delta], whose coefficients are given by Ramanujan's τ-function:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this case, the Hecke algebra T(1; 12) is the ring Z, and, for each n in Z_>0, we have T_n D τ(n). The results above mean that

for p prime, Ramanujan's τ(p) can be computed in time polynomial in log p.

For l prime, let ρ_l denote the Galois representation to GL₂(F_l) attached to [Delta]. It was proved by Swinnerton-Dyer that for l not in {2, 3, 5, 7, 23, 691} the image of ρ_l contains SL_{2(Fl). This means that for all ρl not in this short list the representation ρl has nonsolvable image, and so cannot be computed using computational class field theory. The classical congruences for Ramanujan's τ-function correspond to the l in the list above. Our results provide a generalization of these congruences in the sense that the number fields Kl that give the ρl "encode" the τ(p) mod l in such a way that τ(p) mod l can be computed in time polynomial in l and log p, that is, just the same complexity as in the case where one has explicit congruences.}

More generally, we hope that nonsolvable global field extensions whose existence and local properties are implied by the Langlands program can be made accessible to computation and so become even more useful members of the society of mathematical objects. Explicit descriptions of these fields make the study of global properties such as class groups and groups of units possible. Certainly, if we only knew the maximal Abelian extension of Q as described by general class field theory, then roots of unity would be very much welcomed.

The natural habitat for Galois representations such as the ρ_l above is that of higher degree étale cohomology with F_l-coefficients of algebraic varieties over [bar.Q], together with the action of Gal([bar.Q]/Q). Our results provide some evidence that, also in interesting cases, such objects can be computed in reasonable time. We stress that this question is not restricted to varieties related to modular forms or automorphic forms. In fact, thinking of elliptic curves, over Q, say, knowing that these are modular does not help for computing their number of points over finite fields: Schoof's algorithm uses algebraic geometry, not modularity.

The problem of computing étale cohomology with Galois action is clearly related to the question of the existence of polynomial time algorithms for computing the number of solutions in F_p of a fixed system of polynomial equations over Z, when p varies. Our results treat this problem for the 11-dimensional variety that gives rise to [Delta]; see Section 1.5 for more details and also for an explicit variety of dimension 19 related to this.

The Epilogue describes a striking application of a generalization of our results to the problem of computing representation numbers of the Z²k equipped with their standard inner products. This again is an example where there are explicit formulas only for small k, but where in general there (surely) exists an algorithm that computes such numbers as quickly as if such formulas did exist. Hence, from a computational perspective, such algorithms form a natural generalization of the finite series of formulas.

We very briefly describe the method by which we compute the ρ_f. Their duals occur in the higher degree étale cohomology of certain higher dimensional varieties, but no-one seems to know how to compute with this directly.

Via some standard methods in étale cohomology (the Leray spectral sequence, and passing to a finite cover to trivialize a locally constant sheaf of finite dimensional F_l-vector spaces), or from the theory of congruences between modular forms, it is well known that the ρ_f are realized by subspaces V_f in the l-torsion J_l([bar.Q])[l] of the Jacobian variety Jl of some modular curve X_l defined over Q. The field K_f is then the field generated by suitable "coordinates" of the points x [element of] V_f [subset] J_l([bar.Q])[l]. We are now in the more familiar situation of torsion points on Abelian varieties. But the price that we have paid for this is that the Abelian variety J_l depends on l , and that its dimension, equal to the genus of X_l, that is, equal to (l - 5)(l - 7)24, grows quadratically with l. This makes it impossible to directly compute the x [element of] V_l using computer algebra: known algorithms for solving systems of nonlinear polynomial equations take time exponential in the dimension, that is, exponential in l.

Instead of using computer algebra directly, Jean-Marc Couveignes suggested that we use approximations and height bounds. In its simplest form, this works as follows. Suppose that x is a rational number, x = a/b, with a and b in Z coprime. Suppose that we have an upper bound M for max(|a|, |b|). Then x is determined by any approximation y [element of] R of x such that |y - x| < 1/2M², simply because for all x' [not equal to] x with x' = a'/b', where a' and b' in Z satisfy max(|a|, |b'|) < M, we have |x' - x| = |(a' b - ab'| ≥ 1/M².

For the computation of K_f, we consider the minimal polynomial P_f in Q[T] of a carefully theoretically constructed generator α of K_f. We use approximations of all Galois conjugates of α, that is, of all roots of P_f. Instead of working directly with torsion points of J_l , we work with divisors on the curve X_l. Using this strategy, the problem of showing that P_f can be computed in time polynomial in k and #F is divided into two different tasks. First, to show that the number of digits necessary for a good enough approximation of P_f is bounded by a fixed power of #F. Second, to show that, given f and n, the coefficients of P_f can be approximated with a precision of n digits in time polynomial in n_ #F. The first problem is dealt with in Chapters 9, 10, and 11, using Arakelov geometry. The second problem is solved in Chapters 12 and 13, in two ways: complex approximations (numerical analysis), and approximations in the sense of reductions modulo many small primes, using exact computations in Jacobians of modular curves over finite fields. These five chapters form the technical heart of this book. The preceding chapters are meant as an introduction to them, or motivation for them, and the two chapters following them give the main results as relatively straightforward applications.

(Continues...)

Excerpted from Computational Aspects of Modular Forms and Galois Representations Copyright © 2011 by Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

Edition details

• Publisher: Princeton University Press
• Publication date: 2011
• Language: English
• ISBN 10: 0691142025
• ISBN 13: 9780691142029
• Binding: Paperback
• Number of pages: 440