Search Results

Modular curves, modular forms, lattices, Galois representations

Bas Edixhoven

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

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

Approximating V_f over the complex numbers

Jean-Marc Couveignes

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

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

Computations with modular forms and Galois representations

Johan Bosman

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

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

Epilogue

Bas Edixhoven and Jean-Marc Couveignes (eds)

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

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

Introduction, main results, context

Bas Edixhoven

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

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

Computing coefficients of modular forms

Bas Edixhoven

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

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

Bounds for Arakelov invariants of modular curves

Bas Edixhoven and Robin de Jong

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

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

Polynomials for projective representations of level one forms

Johan Bosman

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

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

Computing V_f modulo p

Jean-Marc Couveignes

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

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

First description of the algorithms

Jean-Marc Couveignes and Bas Edixhoven

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

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

Applying Arakelov theory

Bas Edixhoven and Robin de Jong

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

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

Description of X₁(5l)

Bas Edixhoven

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

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.

An upper bound for Green functions on Riemann surfaces

Franz Merkl

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

This chapter deals with an upper bound for Green functions on Riemann surfaces.

Short introduction to heights and Arakelov theory

Bas Edixhoven and Robin de Jong

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

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

Computing complex zeros of polynomials and power series

Jean-Marc Couveignes

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

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

Computing the residual Galois representations

Bas Edixhoven

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

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