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

Softcover

ISBN 10: 0691142025 ISBN 13: 9780691142029

Verlag: Princeton University Press, 2011

Inhaltsangabe

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.

Über diesen Titel

Über die Autorin bzw. den Autor

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 für Experimentelle Mathematik in Essen, Germany.

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

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:...

Details zur Ausgabe

• Verlag: Princeton University Press
• Erscheinungsdatum: 2011
• Sprache: Englisch
• ISBN 10: 0691142025
• ISBN 13: 9780691142029
• Einband: Taschenbuch
• Anzahl der Seiten: 425
• Herausgeber: Edixhoven Bas, Couveignes Jean-marc
• Kontakt zum Hersteller: Nicht verfügbar
• Verantwortliche Person: Nicht verfügbar