Bas Edixhoven
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0002
- Subject:
- Mathematics, Number Theory
This chapter provides the necessary background concerning modular curves and modular forms. It covers modular curves, modular forms, lattices and modular forms, Galois representations attached to ...
More
This chapter provides the necessary background concerning modular curves and modular forms. It covers modular curves, modular forms, lattices and modular forms, Galois representations attached to eigenforms, and Galois representations over finite fields and reduction to torsion in Jacobians.Less
This chapter provides the necessary background concerning modular curves and modular forms. It covers modular curves, modular forms, lattices and modular forms, Galois representations attached to eigenforms, and Galois representations over finite fields and reduction to torsion in Jacobians.
Jean-Marc Couveignes
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0012
- Subject:
- Mathematics, Number Theory
This chapter addresses the problem of computing torsion divisors on modular curves with an application to the explicit calculation of modular representations. The final result of the chapter is ...
More
This chapter addresses the problem of computing torsion divisors on modular curves with an application to the explicit calculation of modular representations. The final result of the chapter is Theorem 12.14.1 (approximating Vsubscript f). It identifies two differences between this Theorem 12.14.1 and Theorem 12.10.7. First, it claims that it can separate the cuspidal and the finite part of Qₓ. Second, it returns algebraic coordinates b and x for the points Qsubscript x,n rather than analytic ones.Less
This chapter addresses the problem of computing torsion divisors on modular curves with an application to the explicit calculation of modular representations. The final result of the chapter is Theorem 12.14.1 (approximating Vsubscript f). It identifies two differences between this Theorem 12.14.1 and Theorem 12.10.7. First, it claims that it can separate the cuspidal and the finite part of Qₓ. Second, it returns algebraic coordinates b and x for the points Qsubscript x,n rather than analytic ones.
Bas Edixhoven and Jean-Marc Couveignes (eds)
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- book
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.001.0001
- Subject:
- Mathematics, Number Theory
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 ...
More
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. 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 book begins with a concise and concrete introduction that makes it accessible to readers without an extensive background in arithmetic geometry, and it includes a chapter that describes actual computations.Less
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. 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 book begins with a concise and concrete introduction that makes it accessible to readers without an extensive background in arithmetic geometry, and it includes a chapter that describes actual computations.
Johan Bosman
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0006
- Subject:
- Mathematics, Number Theory
This chapter discusses several aspects of the practical side of computing with modular forms and Galois representations. It starts by discussing computations with modular forms, and from there work ...
More
This chapter discusses several aspects of the practical side of computing with modular forms and Galois representations. It starts by discussing computations with modular forms, and from there work towards the computation of polynomials that give the Galois representations associated with modular forms. Throughout, the chapter denotes the space of cusp forms of weight k, group Γ₁(N), and character ε by Sₖ(N, ε).Less
This chapter discusses several aspects of the practical side of computing with modular forms and Galois representations. It starts by discussing computations with modular forms, and from there work towards the computation of polynomials that give the Galois representations associated with modular forms. Throughout, the chapter denotes the space of cusp forms of weight k, group Γ₁(N), and character ε by Sₖ(N, ε).
Bas Edixhoven and Jean-Marc Couveignes (eds)
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0016
- Subject:
- Mathematics, Number Theory
This epilogue describes some work on generalizations and applications, as well as a direction of further research outside the context of modular forms. Theorems 14.1.1 and 15.2.1 will certainly be ...
More
This epilogue describes some work on generalizations and applications, as well as a direction of further research outside the context of modular forms. Theorems 14.1.1 and 15.2.1 will certainly be generalized to spaces of cusp forms of arbitrarily varying level and weight. This has already been done for the probabilistic variant of Theorem 14.1.1, in the case of square-free levels (and of level two times a square-free number). Some details and some applications of Bruin's work, as well as a perspective on point counting outside the context of modular forms are described. Deterministic generalizations of the two theorems mentioned above will lead to deterministic applications.Less
This epilogue describes some work on generalizations and applications, as well as a direction of further research outside the context of modular forms. Theorems 14.1.1 and 15.2.1 will certainly be generalized to spaces of cusp forms of arbitrarily varying level and weight. This has already been done for the probabilistic variant of Theorem 14.1.1, in the case of square-free levels (and of level two times a square-free number). Some details and some applications of Bruin's work, as well as a perspective on point counting outside the context of modular forms are described. Deterministic generalizations of the two theorems mentioned above will lead to deterministic applications.
Bas Edixhoven
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0001
- Subject:
- Mathematics, Number Theory
This chapter provides an introduction to the subject, precise statements of the main results, and places these in a somewhat wider context. Topics discussed include statement of the main results, ...
More
This chapter provides an introduction to the subject, precise statements of the main results, and places these in a somewhat wider context. Topics discussed include statement of the main results, Schoof's algorithm, Schoof's algorithm described in terms of ètale cohomology, other cases where ètale cohomology can be used to construct polynomial time algorithms for counting rational points of varieties over finite fields, congruences for Ramanujan's tau-function, and comparison with p-adic methods.Less
This chapter provides an introduction to the subject, precise statements of the main results, and places these in a somewhat wider context. Topics discussed include statement of the main results, Schoof's algorithm, Schoof's algorithm described in terms of ètale cohomology, other cases where ètale cohomology can be used to construct polynomial time algorithms for counting rational points of varieties over finite fields, congruences for Ramanujan's tau-function, and comparison with p-adic methods.
Bas Edixhoven
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0015
- Subject:
- Mathematics, Number Theory
This chapter applies the main result on the computation of Galois representations attached to modular forms of level one to the computation of coefficients of modular forms. It treats the case of the ...
More
This chapter applies the main result on the computation of Galois representations attached to modular forms of level one to the computation of coefficients of modular forms. It treats the case of the discriminant modular form, that is, the computation of Ramanujan's tau-function at primes, and then deals with the more general case of forms of level one and arbitrary weight k, reformulated as the computation of Hecke operators Tⁿ as ℤ-linear combinations of the Tᵢ with i < k = 12. The chapter gives an application to theta functions of even, unimodular positive definite quadratic forms over ℤ.Less
This chapter applies the main result on the computation of Galois representations attached to modular forms of level one to the computation of coefficients of modular forms. It treats the case of the discriminant modular form, that is, the computation of Ramanujan's tau-function at primes, and then deals with the more general case of forms of level one and arbitrary weight k, reformulated as the computation of Hecke operators Tⁿ as ℤ-linear combinations of the Tᵢ with i < k = 12. The chapter gives an application to theta functions of even, unimodular positive definite quadratic forms over ℤ.
Bas Edixhoven and Robin de Jong
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0011
- Subject:
- Mathematics, Number Theory
This chapter gives bounds for all quantities on the right-hand side in the inequality in Theorems 9.1.1 and 9.2.5, in the context of the modular curves X₁(5l) with l > 5 prime, using the upper bounds ...
More
This chapter gives bounds for all quantities on the right-hand side in the inequality in Theorems 9.1.1 and 9.2.5, in the context of the modular curves X₁(5l) with l > 5 prime, using the upper bounds for Green functions from Chapter 10. The final estimates are given in the last section of the chapter.Less
This chapter gives bounds for all quantities on the right-hand side in the inequality in Theorems 9.1.1 and 9.2.5, in the context of the modular curves X₁(5l) with l > 5 prime, using the upper bounds for Green functions from Chapter 10. The final estimates are given in the last section of the chapter.
Johan Bosman
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0007
- Subject:
- Mathematics, Number Theory
This chapter explicitly computes mod-ℓ Galois representations attached to modular forms. To be precise, it looks at cases with l ≤ 23, and the modular forms considered will be cusp forms of level 1 ...
More
This chapter explicitly computes mod-ℓ Galois representations attached to modular forms. To be precise, it looks at cases with l ≤ 23, and the modular forms considered will be cusp forms of level 1 and weight up to 22. The chapter presents the result in terms of polynomials associated with the projectivized representations. As an application, it will improve a known result on Lehmer's nonvanishing conjecture for Ramanujan's tau function.Less
This chapter explicitly computes mod-ℓ Galois representations attached to modular forms. To be precise, it looks at cases with l ≤ 23, and the modular forms considered will be cusp forms of level 1 and weight up to 22. The chapter presents the result in terms of polynomials associated with the projectivized representations. As an application, it will improve a known result on Lehmer's nonvanishing conjecture for Ramanujan's tau function.
Jean-Marc Couveignes
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0013
- Subject:
- Mathematics, Number Theory
This chapter addresses the problem of computing in the group of lsuperscript k-torsion rational points in the Jacobian variety of algebraic curves over finite fields, with an application to computing ...
More
This chapter addresses the problem of computing in the group of lsuperscript k-torsion rational points in the Jacobian variety of algebraic curves over finite fields, with an application to computing modular representations. An algorithm in this chapter usually means a probabilistic Las Vegas algorithm. In some places it gives deterministic or probabilistic Monte Carlo algorithms, but this will be stated explicitly. The main reason for using probabilistic Turing machines is that there is a need to construct generating sets for the Picard group of curves over finite fields. Solving such a problem in the deterministic world is out of reach at this time. The unique goal is to prove, as quickly as possible, that the problems studied in this chapter can be solved in probabilistic polynomial time.Less
This chapter addresses the problem of computing in the group of lsuperscript k-torsion rational points in the Jacobian variety of algebraic curves over finite fields, with an application to computing modular representations. An algorithm in this chapter usually means a probabilistic Las Vegas algorithm. In some places it gives deterministic or probabilistic Monte Carlo algorithms, but this will be stated explicitly. The main reason for using probabilistic Turing machines is that there is a need to construct generating sets for the Picard group of curves over finite fields. Solving such a problem in the deterministic world is out of reach at this time. The unique goal is to prove, as quickly as possible, that the problems studied in this chapter can be solved in probabilistic polynomial time.
Jean-Marc Couveignes and Bas Edixhoven
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0003
- Subject:
- Mathematics, Number Theory
This chapter provides the first, informal description of the algorithms. It explains how the computation of the Galois representations V attached to modular forms over finite fields should proceed. ...
More
This chapter provides the first, informal description of the algorithms. It explains how the computation of the Galois representations V attached to modular forms over finite fields should proceed. The essential step is to approximate the minimal polynomial P of (3.1) with sufficient precision so that P itself can be obtained.Less
This chapter provides the first, informal description of the algorithms. It explains how the computation of the Galois representations V attached to modular forms over finite fields should proceed. The essential step is to approximate the minimal polynomial P of (3.1) with sufficient precision so that P itself can be obtained.
Bas Edixhoven and Robin de Jong
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0009
- Subject:
- Mathematics, Number Theory
This chapter starts applying Arakelov theory in order to derive a bound for the height of the coefficients of the polynomials Pno hexa conversion found as in (8.2.10). It proceeds in a few steps. The ...
More
This chapter starts applying Arakelov theory in order to derive a bound for the height of the coefficients of the polynomials Pno hexa conversion found as in (8.2.10). It proceeds in a few steps. The first step is to relate the height of the bₗ(Qsubscript x,i) as in the ptrevious chapter to intersection numbers on Xₗ. The second step is to get some control on the difference of the divisors D₀ and Dₓ as in (3.4). Certain intersection numbers concerning this difference are bounded in Theorem 9.2.5, in terms of a number of invariants in the Arakelov theory on modular curves Xₗ. These invariants will then be bounded in terms of l in Chapter 11. The chapter formulates the most important results, Theorem 9.1.3, Theorem 9.2.1, and Theorem 9.2.5, in the context of curves over number fields, that is, outside the context of modular curves.Less
This chapter starts applying Arakelov theory in order to derive a bound for the height of the coefficients of the polynomials Pno hexa conversion found as in (8.2.10). It proceeds in a few steps. The first step is to relate the height of the bₗ(Qsubscript x,i) as in the ptrevious chapter to intersection numbers on Xₗ. The second step is to get some control on the difference of the divisors D₀ and Dₓ as in (3.4). Certain intersection numbers concerning this difference are bounded in Theorem 9.2.5, in terms of a number of invariants in the Arakelov theory on modular curves Xₗ. These invariants will then be bounded in terms of l in Chapter 11. The chapter formulates the most important results, Theorem 9.1.3, Theorem 9.2.1, and Theorem 9.2.5, in the context of curves over number fields, that is, outside the context of modular curves.
Bas Edixhoven
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0008
- Subject:
- Mathematics, Number Theory
This chapter first discusses the construction of a suitable cuspidal divisor on X₁(5l). It then describes the strategy for computing the residual representations V in the situation of Theorem 2.5.13.
This chapter first discusses the construction of a suitable cuspidal divisor on X₁(5l). It then describes the strategy for computing the residual representations V in the situation of Theorem 2.5.13.
Franz Merkl
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0010
- Subject:
- Mathematics, Number Theory
This chapter deals with an upper bound for Green functions on Riemann surfaces.
This chapter deals with an upper bound for Green functions on Riemann surfaces.
Bas Edixhoven and Robin de Jong
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0004
- Subject:
- Mathematics, Number Theory
This chapter discusses bounding the heights of the coefficients of minimal polynomial P. As was hinted at in Chapter 3, such bounds are obtained using Arakelov theory, a tool that is discussed in ...
More
This chapter discusses bounding the heights of the coefficients of minimal polynomial P. As was hinted at in Chapter 3, such bounds are obtained using Arakelov theory, a tool that is discussed in this chapter. It is not at all excluded that a direct approach to bound the coefficients of P exists, thus avoiding the complicated theory that we use. On the other hand, it is clear that the use of Arakelov theory provides a way to split the work into smaller steps, and that the quantities occurring in each step are intrinsic in the sense that they do not depend on coordinate systems or other choices one could make. This method does not depend on cancellations of terms in the estimates we will do; all contributions encountered can be bounded appropriately.Less
This chapter discusses bounding the heights of the coefficients of minimal polynomial P. As was hinted at in Chapter 3, such bounds are obtained using Arakelov theory, a tool that is discussed in this chapter. It is not at all excluded that a direct approach to bound the coefficients of P exists, thus avoiding the complicated theory that we use. On the other hand, it is clear that the use of Arakelov theory provides a way to split the work into smaller steps, and that the quantities occurring in each step are intrinsic in the sense that they do not depend on coordinate systems or other choices one could make. This method does not depend on cancellations of terms in the estimates we will do; all contributions encountered can be bounded appropriately.
Jean-Marc Couveignes
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0005
- Subject:
- Mathematics, Number Theory
The purpose of this chapter is twofold. First, it will prove two theorems (5.3.1 and 5.4.2) about the complexity of computing complex roots of polynomials and zeros of power series. The existence of ...
More
The purpose of this chapter is twofold. First, it will prove two theorems (5.3.1 and 5.4.2) about the complexity of computing complex roots of polynomials and zeros of power series. The existence of a deterministic polynomial time algorithm for these purposes plays an important role in this book. More important, it will also explain what it means to compute with real or complex data in polynomial time. The chapter first recalls basic definitions in computational complexity theory, it then deals with the problem of computing square roots. The more general problem of computing complex roots of polynomials is treated thereafter and, finally, the chapter studies the problem of finding zeros of a converging power series.Less
The purpose of this chapter is twofold. First, it will prove two theorems (5.3.1 and 5.4.2) about the complexity of computing complex roots of polynomials and zeros of power series. The existence of a deterministic polynomial time algorithm for these purposes plays an important role in this book. More important, it will also explain what it means to compute with real or complex data in polynomial time. The chapter first recalls basic definitions in computational complexity theory, it then deals with the problem of computing square roots. The more general problem of computing complex roots of polynomials is treated thereafter and, finally, the chapter studies the problem of finding zeros of a converging power series.
Bas Edixhoven
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691142012
- eISBN:
- 9781400839001
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691142012.003.0014
- Subject:
- Mathematics, Number Theory
This chapter proves the main result on the computation of Galois representations. It provides a detailed description of the algorithm and a rigorous proof of the complexity. It first combines the ...
More
This chapter proves the main result on the computation of Galois representations. It provides a detailed description of the algorithm and a rigorous proof of the complexity. It first combines the results of chapters 11 and 12 in order to work out the strategy of Chapter 3. This gives the main result, Theorem 14.1.1: a deterministic polynomial time algorithm, based on computations with complex numbers. The crucial transition from approximations to exact values is done, and the proof of Theorem 14.1.1 is finished later in the chapter. The chapter then replaces the complex computations with the computations over finite fields from Chapter 13, and gives a probabilistic (Las Vegas type) polynomial time variant of the algorithm in Theorem 14.1.1.Less
This chapter proves the main result on the computation of Galois representations. It provides a detailed description of the algorithm and a rigorous proof of the complexity. It first combines the results of chapters 11 and 12 in order to work out the strategy of Chapter 3. This gives the main result, Theorem 14.1.1: a deterministic polynomial time algorithm, based on computations with complex numbers. The crucial transition from approximations to exact values is done, and the proof of Theorem 14.1.1 is finished later in the chapter. The chapter then replaces the complex computations with the computations over finite fields from Chapter 13, and gives a probabilistic (Las Vegas type) polynomial time variant of the algorithm in Theorem 14.1.1.
