Nicolas Mascot
email: n.a.v.mascot@warwick.ac.uk

Certification of modular Galois representations

Keywords: 11Y70, 11S20, 11F80, 11F11, 11Y40, 20B40, 20J06

We show how the output of the algorithm to compute modular Galois representations described in [Mas13] can be certified. We have used this process to compute certified tables of such Galois representations obtained thanks to an improved version of this algorithm, including representations modulo primes up to 31 and representations attached to a newform with non-rational (but of course algebraic) coefficients, which had never been done before. These computations take place in the Jacobian of modular curves of genus up to 26. The resulting data are available on the author's webpage. script. I also thank J. Klüners for the useful discussions I have had with him in July 2015 in Oberwolfach about the algorithmic computation of Galois groups, D. Holt for his help in permutation group theory, and my friend and colleague A. Page for the clever suggestions that he provided me. Finally, I wish to address my thanks to the anonymous reviewer of the previous version of this article for suggesting a much simpler method to certify some Galois groups (cf. section 3.5) and more generally for his insightful suggestions

Introduction

Let f = q + +∞ n=2 a n q n ∈ S k Γ 1 (N ), ε be a classical newform of weight k ∈ N 2 , level N ∈ N 1 and nebentypus ε. Jean-Pierre Serre conjectured and Pierre Deligne proved in [START_REF] Deligne | Formes modulaires et représentations l-adiques[END_REF] that for every finite prime l of the number field K f = Q(a n , n 2) spanned by the coefficients a n of the q-expansion of f at infinity, there exists a continuous Galois representation

Gal(Q/Q) -→ GL 2 (Z K f,l )
which is unramified outside N and such that the image of any Frobenius element at p N has characteristic polynomial x 2 -a p x + ε(p)p k-1 ∈ Z K f,l [x], where Z K f,l denotes the l-adic completion of the ring of integers Z K f of K f , and is the rational prime lying below l.

Let F l be the residue field of l. By reducing the above l-adic Galois representation modulo l and semi-simplifying, we get a modulo l Galois representation ρ f,l : Gal(Q/Q) -→ GL 2 (F l ), which is unramified outside N and such that the image of any Frobenius element at p N has characteristic polynomial x 2 -a p x + ε(p)p k-1 ∈ F l [x]. In particular, the trace of this image is a p mod l.

In [START_REF] Mascot | Computing modular Galois representations[END_REF], we described an algorithm based on ideas from the book [CE11] edited by Jean-Marc Couveignes and Bas Edixhoven to compute such modulo l Galois representations, provided that the image of the Galois representation contains SL 2 (F l ) and that k < . This gives a way to quickly compute the coefficients a p modulo l for huge primes p. We have used this algorithm to compute representations attached to forms of level 1 for up to 31.

In what follows, we will assume that the inertial degree of l is 1, so that F l = F . Indeed, although there is no theoretical obstacle to allowing primes of higher degree, we will have to deal explicitly with objects such as polynomials whose roots are indexed by F 2 \{(0, 0)} and whose Galois group is GL 2 (F ), and this already requires considerable work when F l = F .

The condition that the image of the Galois representation contain SL 2 (F l ) is then generically satisfied. Indeed, by [START_REF] Ribet | On l-adic representations attached to modular forms II[END_REF]theorem 2.1] and [Swi72, lemma 2], for any non-CM newform f (and in particular for any newform f of level 1), the image of the representation ρ f,l contains SL 2 (F ) for almost every l of degree 1. The finitely many l of degree 1 for which SL 2 (F ) ⊂ Im ρ f,l are called exceptional primes of degree 1 for f , and we exclude them. They were explicitly determined by Sir Peter Swinnerton-Dyer in [START_REF] Swinnerton-Dyer | On -adic representations and congruences for coefficients of modular forms. Modular functions of one variable[END_REF] for the known1 newforms f of level 1 whose coefficients a n are rational. In our case, this means we exclude l = 23 for f = ∆ and l = 31 for f = E 4 ∆.

Our algorithm relies on the fact that if k < , then the Galois representation ρ f,l is afforded with multiplicity 1 by a subspace V f,l of the -torsion of the Jacobian J 1 ( N ) of the modular curve X 1 ( N ) under the natural Gal(Q/Q)-action, cf. [Gro90, proposition 9.3.2] and [Mas13, section 1].

The algorithm first computes the number field L = Q Ker ρ f,l cut out by the Galois representation, by evaluating a well-chosen function α ∈ Q J 1 ( N ) in the nonzero points of V f,l and forming the polynomial

F (x) = v∈V f,l v =0 x -α(v) ∈ Q[x]
of degree 2 -1 whose decomposition field is L. The algorithm then uses a method from T. and V. Dokchitser (cf [START_REF] Dokchitser | Identifying Frobenius elements in Galois groups[END_REF]) to compute the image of the Frobenius element at p given a rational prime p N . This method involves the computation of a family of resolvents

Γ C (x) = σ∈C     x - v∈V f,l v =0 h α(v) α(σ • v)     ∈ Q[x]
indexed by the conjugacy classes C of GL 2 (F ), where h(x) ∈ Z[x] is some fixed polynomial. These resolvents, which we will refer to as the Dokchitsers' resolvents, can then be used to determine which class the Frobenius element at p lies in for almost all p ∈ N.

Remark 1. Actually, in order to obtain certified results, we will see that we should certify the polynomial F (x) in the sense of section 3 before computing the Dokchitsers' resolvents.

Unfortunately, the output of the algorithm, although correct beyond reasonable doubt (cf. [START_REF] Mascot | Computing modular Galois representations[END_REF], end of section 1), is not certified since it relies on the identification of floating point numbers as rational numbers. The purpose of this article is to show how these computations can be formally certified subsequently. As a side effect, we also obtain much tidier outputs.

A word on notation

All along this article, we will be dealing with two versions of most of the objects in play, namely the actual value of this object, and the version computed by the algorithm described above. For instance, the function α ∈ Q J 1 ( N ) being fixed, the polynomial

F (x) = v∈V f,l v =0 x -α(v) ∈ Q[x]
is a well-defined object attached to α, f and l, but what the algorithm outputs is an approximate version of this polynomial over C, whose coefficients are then nonrigorously identified as rational numbers. Following the reviewer's comments on an older version of this article, we will denote the "true" value of F (x) with an aureole, F (x), so as to stress its "heavenly unattainable nature" (as the reviewer put it), and we will reserve the notation F (x) to the polynomial "guessed" by the algorithm, and similarly for the other objects at play. We will follow this convention from now on, and we hope that doing so will reduce the confusion between the two versions of each object, and make our certification process clearer.

Reducing the polynomials

Unfortunately, the coefficients of the polynomial F (x) produced by the algorithm described in [START_REF] Mascot | Computing modular Galois representations[END_REF] tend to have larger and larger height as grows. More precisely, in practice this polynomial is of the form

F (x) = x deg F + 1 d i<deg F c i x i ,
where d is an (unfortunately large) positive integer and the c i are integers whose gcd with d is several orders of magnitude smaller than d; in other words, apart from the leading one, these coefficients roughly all have the same denominator, with a few "accidental" simplifications here and there. The following table, which shows the genus g = ( -5) ( -7) of the modular curves X 1 ( ) and the rough number h ≈ log 10 d of decimal digits in the denominator d of the polynomials F (x) associated to newforms of level N = 1 that we computed using the algorithm described in [START_REF] Mascot | Computing modular Galois representations[END_REF], seems to indicate the heuristic h ≈ g 2.5 : While this is rather harmless for 17, it makes the Dokchitser's method intractable as soon as 29. It is thus necessary to reduce this polynomial, that is to say to compute another polynomial whose splitting field is isomorphic to the splitting field of F (x) but whose coefficients are much nicer. An algorithm to perform this task based on LLL lattice reduction is described in [Coh93, section 4.4.2] and implemented in [Pari/GP] under the name polred. Its complexity is polynomial in the degree and the height of the coefficients, provided that the factorisation of the discriminant of the corresponding field is known, which is the case for us. However, the polynomial F (x) has degree 2 -1 and tends to have really large coefficients, and this makes polred choke on it, even for small values of . Indeed, the fact that polred is based on LLL reduction means that its execution time is especially sensitive to the degree of the polynomial.

g
On the other hand, it would be amenable to apply the polred algorithm to the polynomial

F proj (x) = W ∈P(V f,l )    x - w∈W w =0 α(w)    ∈ Q[x]
whose splitting field is 2 the number field Lproj cut out by the projective Galois representation ρproj f,l : Gal(Q/Q) ρf,l / / GL 2 (F ) / / / / PGL 2 (F ) since the degree of this polynomial is only + 1. Unfortunately, this projective version of the representation does not contain enough information to recover 3 the values of a p mod l. However, we noted in [Mas13, section 3.7.2] that if S ⊂ F * denotes the largest subgroup of F * such that S -1, then the knowledge of the quotient representation ρS f,l : Gal(Q/Q) ρf,l / / GL 2 (F ) / / / / GL 2 (F )/S , combined with the fact that the image in GL 2 (F ) of a Frobenius element at p has determinant p k-1 ε(p) mod l, is enough to recover ρf,l and hence the values of a p mod l.

It is therefore enough for our purpose to compute this quotient representation, first by forming the polynomial

F S (x) = Sv∈V f,l /S v =0 x - s∈S α(sv) ∈ Q[x],
whose splitting field is the number field LS cut out by ρS f,l , and then by applying the Dokchitsers' method on it in order to compute the images of the Frobenius elements by ρS f,l , cf. [Mas13, section 3.7.2].

Note that since we assumed that f and l are such that ρf,l is not exceptional 4 , the quotient representations ρS f,l is surjective. Indeed, since f is a form of level N = 1 and of even weight, the determinant of ρ f,l is an odd power of the mod cyclotomic character. In particular, the polynomial F S (x) is irreducible over Q.

Also note that the complex roots of F (x) are approximately known as an output of the algorithm [START_REF] Mascot | Computing modular Galois representations[END_REF], and so is their indexation by V f,l -{0}. We thus have an indexation of the roots of F (x) by V f,l -{0}, and so we can compute an approximation F S (x) ∈ Q[x] of F S (x) by grouping the roots, expanding over C, and guessing the coefficients by continued fractions just like for F (x).

2 To be precise, it is clear that the splitting field of F proj (x) is contained in the number field Lproj cut out by the projective representation. Very often, this containment is an equality and so F proj (x) is irreducible, but it may sometimes happen that this containment is proper, in which case F proj (x) becomes reducible over Q. We can work around this pathological behaviour by replacing the summation over W in the definition of F proj (x) by another symmetric combination (e.g. a product), or by applying a Tschirnhausen transform. For notational convenience, we will henceforth assume that no such problem is encountered; should this not be the case, the necessary modifications are completely straightforward.

3 One could at most recover these values with a sign ambiguity, as in [START_REF]Computational aspects of modular forms and Galois representations[END_REF]. 4 In the sense that its image contains SL 2 (F ).

In practice, the coefficients of F S (x) have roughly the same denominator as the ones of F (x), so we are not improving anything on this side, but of course the degree of F S (x) can be much smaller, so we may try to polred it. Let -1 = 2 r s with s ∈ N odd. Since we have |S| = s, the degree of F S is 2 r ( + 1), so polreding is amenable in the cases = 19 or 23, but the cases = 29 or 31 remain impractical.

For these remaining cases, Bill Allombert suggested to the author that one can still reduce F S (x) in several steps, as we now explain. Since F * is cyclic, we have a filtration

F * = S 0 ⊃ 2 S 1 ⊃ 2 • • • ⊃ 2 S r = S
with [S i : S i+1 ] = 2 for all i, namely

S i = {x 2 i , x ∈ F * }.
For each i r, let us define

Fi (x) = S i v∈V f,l /S i v =0
x -

s∈S i α(sv) ∈ Q[x], let F i (x) ∈ Q[x]
be guesses for Fi (x) obtained as for F S (x) above, let

Ki = Q[x]/ Fi (x), K i = Q[x]/F i (x),
and let Li (resp. L i ) be the normal closure of Ki (resp. K i ), so that Li the number field cut out by the quotient representation

ρS i f,l : Gal(Q/Q) ρf,l / / GL 2 (F ) / / / / GL 2 (F )/S i .
In particular, we have ρS 0 f,l = ρproj f,l , L0 = Lproj , and we are looking for a nice model of K r .

Note that again because f is of level N = 1, and is not exceptional mod l, the polynomials Fi (x) are irreducible over Q, and so Ki is indeed a field. We assume that the F i (x) are also irreducible.

By construction, the degree of Ki over Q is # (V f,l -{0})/S i = 2 i ( + 1), so the fields Ki fit in an extension tower Kr

2 2 r . . . 2 K1 2 K0 +1 Q
and we are going to polred the polynomials F i (x) along this tower recursively from bottom up.

First, we apply directly the polred algorithm to F 0 (x) = F proj (x). Since the degree of this polynomial is only + 1, this is amenable, as mentioned above, and yields a monic reduced polynomial in Z[x].

Then, assuming we have managed to reduce F i (x), we have a nice model for

K i = Q[x]/F i (x)
, and so we can factor F i+1 (x) over K i . Since the extension K i+1 = Q[x]/F i+1 (x) should be quadratic over K i , there must be at least one factor of degree 2. Let G i+1 (x) be one of those, and let ∆ i ∈ K i be its discriminant, so that we have

K i+1 K i [x]/G i+1 (x) K i ∆ i .
In order to complete the recursion, all we have to do is to strip ∆ i from the largest square factor we can find, say ∆ i = A 2 i δ i with A i , δ i ∈ K i and δ i as small as possible. Indeed we then have K i+1 = K i √ δ i , and actually even K i+1 = Q √ δ i unless we are very unlucky5 , so that if we denote by χ i (x) ∈ Q[x] the minimal polynomial of δ i , then we have

K i+1 Q[x]/χ i (x 2 ), so that χ i (x 2
) is a reduced version of F i+1 (x). If its degree and coefficients are not too big, we can even apply the polred algorithm to this polynomial in order to further reduce it, which is what we do in practice. In order to write ∆ i = A 2 i δ i , we would like to factor ∆ i in K i , but even if K i is principal, this is not amenable whatsoever because ∆ i is huge. We can however consider the ideal generated by ∆ i in K i , and remove its N -part. The fractional ideal B i we obtain must then be a perfect square, since K i+1 is unramified outside N (since L is), and the very efficient idealsqrt script from [START_REF] Belabas | Ideal power detection over number fields[END_REF] can explicitly factor it into B i = A 2 i . If A i denotes an element in A i close to being a generator of A i (an actual generator, if amenable, would be even better), then δ i := ∆ i /A 2 i is small.

We have thus managed to reduce our polynomials F i (x). In what follows, we will use the notation F i (x) to refer to the reduced versions, which are monic and lie in Z[x]. They were each obtained from the non-reduced version by an explicit change of variable, and we can apply the same changes of variables to the "true" polynomials Fi (x), thus yielding new polynomials that we will denote by Fi (x) from now on.

Certification of the computations

The output of the algorithm relies on the identification as rational numbers of the coefficients of the polynomials F i (x) given in approximate form as floating-point numbers, by using continued fractions. In order to certify these results, it is thus necessary to make sure the we have correctly identified not only that the number fields cut out by the representation (i.e. that K i = Ki ), but also the Galois action on the roots of the F i (x), else we would be doing nonsense with the Dokchitsers' resolvents Γ C (x).

For this, a first possibility consists in proving bounds on the height of the rational numbers that the algorithm will have to identify (e.g. the coefficients of F (x)), and then to certify that the continued fraction identification process is correct, for instance by running the computation with high enough precision in C and controlling the round-off errors all along. Although it is indeed possible in theory to bound the height of these rational numbers by using Arakelov theory (cf. [START_REF]Computational aspects of modular forms and Galois representations[END_REF]theorem 11.7.6]), this approach gives unrealistic titanic bounds and thus seems ominously tedious, especially as it requires controlling the round-off error in the linear algebra steps of K. Khuri-Makdisi's algorithms to compute in the modular Jacobian (cf. [Mas13, section 3.3]). We have therefore not attempted to follow it.

Instead, we deemed it much better to first run the computations in order to obtain unproven results, and to prove these results afterwards. We explain in this section how to do so.

Sanity checks

Before attempting to prove the results, it is comforting to perform a few easy checks so as to ensure that they seem correct beyond reasonable doubt (cf. the end of section 1 in [START_REF] Mascot | Computing modular Galois representations[END_REF]). Namely,

• Since we are working with a form of level N = 1, the number field L cut out by the Galois representation ρf,l is ramified only at . Therefore, we can check that the discriminant of the polynomial

F (x) ∈ Q[x] is of the form ± n M 2
for some M ∈ Q * . Even better, we can compute the maximal order of the field K = Q[x]/F (x) whose Galois closure is L and check that its discriminant is, up to sign, a power of . Since a number field ramifies at the same primes as its Galois closure, this proves that the decomposition field L of F (x) is ramified only at , as expected. If the coefficients of F (x) are too horrible for that, we can apply this check on F r (x) instead.

• Since Galois representations attached to modular forms are odd, the image of complex conjugation by these representations is an involutory matrix in GL 2 (F l ) of determinant -1, hence similar to [ 1 0 0 -1 ] if 2. This means that the polynomial F (x) of degree 2 -1 computed by the algorithm should have exactly -1 roots in R, which can be checked numerically, and that the sign of its discriminant should be (-1) ( -1)/2 , which can be checked exactly.

• The fact that the resolvents Γ C (x) computed by the Dokchitsers' method and used to identify the image of Frobenius elements seem to have integer (and not just complex) coefficients hints that Gal(L/Q) is indeed isomorphic to a subgroup of GL 2 (F ), so that the number field L is indeed a number field cut out by a Galois representation, and that the Galois action on V f,l ⊂ J 1 ( )[ ] is linear. Again, we can replace F (x) with F r (x) and GL 2 (F ) with GL 2 (F )/S r to ease computation.

• The fact that the approximations F i (x) of the polynomials Fi (x) computed by regrouping the roots of F (x) along their S-orbits for the various subgroups S ⊆ F * considered during the polynomial reduction process (cf. section 2) seem to have rational coefficients with common denominator dividing the one of F (x) also hints that the coefficients of these polynomials have been correctly identified as rational numbers, that Gal(L/Q) is indeed isomorphic to a subgroup of GL 2 (F ), and that the Galois action on the roots of F (x) is the expected one.

• Finally, we can check that the values a p mod l obtained by the algorithm for a few small primes p are correct, by comparing them with the ones computed by "classical" methods such as based on modular symbol-based ones.

We will now present a method to formally prove rigorously our computations, while keeping the amount of required extra computations to a minimum.

A certification algorithm

We keep the notations of section 2: we fix a prime 5, and we let r ∈ N be such that -1 = 2 r m for some odd m ∈ N, so that we have the filtration

F * = S 0 ⊃ 2 S 1 ⊃ 2 • • • ⊃ 2 S r = S
with #S r odd and [S i : S i+1 ] = 2 for all i. Let V = F 2 -{0}, the vector plane minus the origin, on which GL 2 (F ) acts transitively, and let V i = V /S i , so that we have a natural transitive action of GL 2 (F )/S i on V i . We denote by π i : V i+1 / / / / V i the natural projection, and we note for future reference that each element of GL 2 (F )/S i has a well-defined trace in F /S i , as well as a well-defined determinant in F * /S 2 i , where

S 2 i = {s 2 , s ∈ S i } = S i+1 , if i < r, S i , if i = r.
For each 0 i r, we have constructed a monic, irreducible polynomial F i (x) ∈ Z[x] of degree 2 i ( + 1). Let K i be the root field of F i (x), let L i be its Galois closure. We have that K i+1 is a quadratic extension of K i , generated by the square root of some explicitly known integral primitive element δ i of K i , as this is a by-product of the reduction process presented in section 2.

For each i, let Z i ⊂ C denote the set of complex roots of F i (x). As noted in section 2, we have an indexation of Z i by V i , which we denote by θ i : Z i ∼ -→ V i . Via these indexations, the Galois action on the Z i should be "linear", but we do not know that yet.

Besides, by construction of the F i (x), for each root z ∈ Z i+1 there exists another root z ∈ Z i+1 such that z + z is extremely close to a root of F i (x). We can check numerically that each root of F i (x) is the sum of two roots of F i+1 (x) in a unique way, whence 2-to-1 projections map i :

Z i+1 / / / / Z i such that z ≈ z ∈Z i+1 i (z )=z z for all z ∈ Z i .
We can check that these approximate identities are in fact exact, i.e.

z = z ∈Z i+1 i (z )=z z , (T)
by computing rigorously6 for each i the polynomial

I∈( Z i 2 )
x -

z∈I z ∈ Z[x],
where Z i 2 denotes the set of 2-element subsets of Z i , and by checking that F i (x) divides this polynomial and that the complex roots match as expected. We can then also check numerically that the diagram

Z i+1 i ∼ θ i+1 / / V i+1 π i Z i ∼ θ i / / V i (Π)
commutes for each i, as expected. This proves that the projections π i are Galoisequivariant.

What we want to prove is that there exists a compatible7 system of isomorphisms between Gal(L i /Q) and GL 2 (F )/S i such that the Galois action on Z i is equivalent via our bijections θ i to the natural action of GL 2 (F )/S i on V i , so that the diagram

Gal(L i /Q) / / Sym(Z i ) Gal(L i+1 /Q) c c c c / / Sym(Z i+1 , i ) b b GL 2 (F )/S i / / Sym(V i ) GL 2 (F )/S i+1 c c c c / / Sym(V i+1 , π i ) b b
commutes for all i, where the vertical arrows are isomorphisms, Sym(V i+1 , π i ) denotes the group of permutations of V i+1 that admit the fibres of the projection π i as a block system, and similarly for Sym(Z i+1 , i ).

Furthermore, we also want to prove that for all i, the Galois action on Z i affords a quotient Galois representation ρ S i f,l which is equivalent to ρS i f,l . For brevity, we will then say that the polynomials F i (x) correspond to ρf,l .

We will present two methods to rigorously prove that our polynomials F i (x) correspond to a Galois representation ρ, the second one being more efficient but unfortunately much more complicated then the first one. We will then finally show how to prove that ρ ∼ ρf,l .

Both methods require that we first check that F 0 (x) indeed corresponds to ρproj f,l , so we start by showing how this can be done. We thus begin with the polynomial F 0 (x), which ought to correspond to the projective Galois representation ρproj f,l . The first thing to do is to make sure that this polynomial does define a projective Galois representation, by proving that there exists an indexation of Z 0 by P 1 (F ) such that Gal(L 0 /Q) is permutation isomorphic to a subgroup of PGL 2 (F ) acting of P 1 (F ). Since by assumption f has level N = 1 and is not exceptional mod l, we actually expect Gal(L 0 /Q) to be isomorphic to the whole of PGL 2 (F ).

Certification of the projective representation

In principle, we could prove this by computing the polynomial

R 4 (x) = z 1 ,z 2 ,z 3 ,z 4 ∈Z 0 pairwise distinct x - 4 n=1 λ n z n ∈ Z[x]
by rigorous methods (e.g. resultants), and by checking how it factors over Q. Here, the λ n are fixed integers chosen so that R 4 (x) is squarefree, so that R 4 (x) monitors the action of Galois on quadruplets of roots of F 0 (x). The point is that a permutation of P 1 F comes from PGL 2 (F ) if and only if it preserves cross-ratios, and this should become apparent in the factorisation of R 4 (x). However, the degree of R 4 (x) is approximately 4 , which is quite large for = 31, not to mention that since the parameters λ n must necessarily be distinct, the coefficients of R 4 (x) will be huge. As a result, computing R 4 (x) would be too slow in practice.

We can instead compute the polynomial

R 4,sym (x) = I∈( Z 0 4 ) x - z∈I z ∈ Z[x],
where the notation X n means the set of unordered subsets of cardinal n of the set X. This polynomial monitors the action of Galois on unordered quadruplets of roots of F 0 (x), and compared to R 4 (x), its degree is 24 times smaller, and its coefficients are much smaller, so that computing it is much more amenable. It turns out that the way R 4,sym (x) factors is enough to indicate that Gal(L 0 /Q) is a subgroup of PGL 2 (F ) in most cases.

To make this claim more precise, let us fix some notation: we let k be a field8 of characteristic different from 2, and H to be the so-called anharmonic group, that is to say the group of permutations of P 1 (k) generated by λ → 1 -λ and λ → 1/λ. It is well-known that H S 3 is the stabiliser of the set {∞, 0, 1} for the action of PGL 2 (k) on P 1 (k), and that if (a, b, c, d) ∈ P 1 (k) 4 is a quadruplet of pairwise distinct points, then the cross-ratios of all possible 24 permutations of this quadruplet form an orbit under H. Besides, since the fibres of the map

j : P 1 (k) \ {∞, 0, 1} -→ k λ -→ 256 (1-λ+λ 2 ) 3 λ 2 (1-λ) 2
are precisely the H-orbits9 , the composition of the cross-ratio with j yields a welldefined "unordered cross-ratio" map u :

P 1 (k) 4 -→ k {a, b, c, d} -→ j([a, b, c, d])
where [•, •, •, •] denotes the usual cross-ratio. This map is constant if and only if the anharmonic group H acts transitively on P 1 (F ) \ {∞, 0, 1}. Since a H-orbit has at most 6 elements, it is easy to see that for k = F with ∈ N prime, u is constant if and only if 5.

Theorem 2. If = 5, then the permutations of P 1 (F ) that preserve the unordered cross-ratio map u are precisely the ones that come from PGL 2 (F ).

Proof. If 3, then every permutation of P 1 (F ) comes from PGL 2 (F ) and so there is nothing to prove. We may therefore assume that 7. But then u : P 1 (k) 4 -→ k is not a constant map, so its stabiliser in S +1 is a strict subgroup S < S +1 which clearly contains PGL 2 (F ). But PGL 2 (F ) is a maximal subgroup of S +1 according to the following theorem, whence the result. Theorem 3. Let 5 be a prime. The permutation group PGL 2 (F ) of P 1 (F ) is a maximal subgroup of the symmetric group S +1 .

Proof. Since 5, PGL 2 (F ) is a strict subgroup of S +1 . Suppose that there is a group X such that PGL 2 (F ) < X < S +1 . Then X is at least 3-transitive. By looking through the list of 2-transitive finite permutation groups given in section 7.7 of [START_REF] Dixon | Permutation Groups[END_REF], it can be derived that the 3-transitive finite permutation groups are the following:

• the projective semilinear groups G with PSL 2 (F q ) G PΓL 2 (F q ), where q is a power of a prime p and G PΣL 2 (F q ) if p = 2, degree q + 1,

• the affine groups AGL n (F 2 ) = F n 2 GL n (F 2 ), degree 2 n ,
• the group F 4 2 A 7 , degree 16,

• the Mathieu groups M 11 , M 12 , M 22 , Aut(M 22 ), M 23 and M 24 , respective degrees 11 or 12, 12, 22, 22, 23, 24,

• the alternating groups A n (n 5), degree n,

• and the symmetric groups S n (n 3), degree n,

where PΓL 2 (k) (resp. PΣL 2 (k)) denotes the permutation group of P 1 (k) generated by PGL 2 (k) (resp. PSL 2 (k)) and by the automorphisms of the ground field k.

As we want degree + 1 with prime, this only leaves AGL n (F 2 ), M 11 , M 12 , M 24 and A +1 as candidates for X. However, these groups are all perfect, so they all act by even permutations and thus cannot contain PGL 2 (F ).

As far as we are concerned, the main consequence of this is that it is enough to see how R 4,sym (x) factors to prove that Gal(L 0 /Q) is permutation isomorphic to a subgroup of PGL 2 (F ), and this is a stark improvement compared to working with R 4 (x), whose degree is 24 times larger.

The computer algebra package [Magma] contains two functions named respectively GaloisGroup and GaloisProof whose aim is to compute Galois groups by the algorithm described in [START_REF] Fieker | Computation of Galois groups of rational polynomials[END_REF]. The former, when supplied with an irreducible polynomial f (x) ∈ Z[x] and a prime number v ∈ N, tries to guess the Galois group of f (x) as a permutation group acting on the v-adic roots of f (x), albeit non-rigorously; in order to get a certification of this result, it is necessary to then apply the latter function.

In our case, if we pick a prime p ∈ N such that F 0 (x) is irreducible10 mod p, then when we call GaloisGroup on F 0 (x), p), it only takes a few seconds (even for = 31) for [Magma] to return a guess for Gal(L 0 /Q), thanks to the efficiency of [START_REF] Fieker | Computation of Galois groups of rational polynomials[END_REF], the fact that F 0 (x) is of degree only +1 and has been polreded, and to the non-trivial information provided by the cyclic action of the Frobenius at p on the p-adic roots of F 0 (x). However, as explained above, this is not rigorous, so we then call GaloisProof, which forces [Magma] to compute and factor R 4,sym (x) rigorously so as to verify the output of GaloisGroup. This takes of course much longer (up to 4 days for = 31), and in fact this is by far the most time-consuming part of the whole certification process of our polynomials, at least for large .

We then check explicitly that this Galois group is permutation-isomorphic to PGL 2 (F ) acting on P 1 (F ). We fix such an isomorphism11 , and we will use it to identify Gal(L 0 /Q) with PGL 2 (F ) from now on. This yields a bijection θ 0 between the roots of F 0 (x) in Q p and P 1 (F ) which makes the Galois action equivalent to the natural action of PGL 2 (F ) on P 1 (F ).

Correctness of the projective representation

Now that we have made sure that the Galois action on the roots of F 0 (x) does define a projective representation

ρ proj : G Q / / / / Gal(L 0 /Q) PGL 2 (F ) ,
we want to prove that this representation is isomorphic to ρproj f,l as expected. For this, we use the following result from [Bos07, section 2]: Theorem 4. Let π : G Q -→ PGL 2 (F ) be an irreducible projective mod Galois representation, where 3. Let H < PGL 2 (F ) be the stabiliser of a point of P 1 (F ), and let K = Q π -1 (H) be the corresponding number field. If K has exactly two real places, and if there exists an integer k 3 such that

disc K = ± k+ -2 ,
then there exists a newform f ∈ S k (1) and a prime l of Q above such that

π ∼ ρproj f,l .

Sketch of proof.

By assumption, the image of complex conjugation by π is a nontrivial matrix which is diagonalisable over F , and so π is absolutely irreducible. The idea is then that π can be lifted to a linear representation

ρ : G Q -→ GL 2 (F )
which, just like π, is absolutely irreducible, odd, and ramifies only at . Serre's modularity conjecture (cf. [START_REF] Khare | Serre's modularity conjecture (I and II)[END_REF]) then applies and shows that ρ is modular, say ρ ∼ ρf,l for some newform f ∈ S kρ (N ρ , ε ρ ) and some prime l of Q above . Then, since ρ ramifies only at , its Artin conductor is a power of , so ρ comes from a form f of level N ρ = 1. Finally, if the lift ρ is chosen so that the weight k ρ of f is minimal, then [MT03, theorem 3] gives a formula for the -adic valuation of the discriminant of the Galois number field cut out by ρ, which by J. Bosman's work boils down to disc K = ± kρ+ -2 .

Thus, in order to prove that ρ proj ∼ ρproj f,l , all we have to do is count the real roots of F 0 (x), which can be done by using Sturm's method (cf. [Lan02, chapter XI, theorem 2.7]), and check that the discriminant of the root field

K proj = Q[x]/F 0 (x) is ± k+ -2 , which is a piece of cake for [Pari/GP]. If k is such that dim S k (1) = 1, e.g. k 22
, then this is enough to conclude that ρ proj ∼ ρproj f,l , as the coefficients of f then are rational so that the choice of the prime l lying above does not matter.

In the case dim S k (1) > 1, we can check that the newforms in S k (1) are all conjugate under Galois as predicted by Maeda's conjecture, and so we only have to make sure that ρ proj ∼ ρproj f,l for the right prime l above . For instance, in the case = 31, k = 24, we have that S 24 (1) has dimension 2 and is spanned by the two conjugates of a newform f 24 = n 1 τ 24 (n)q n whose eigenvalues lie in a quadratic field; since 31 splits in this field, say 31 = l 1 l 2 , we know that ρ proj is equivalent either to ρproj f 24 ,l 1 or to ρproj f 24 ,l 2 . In order to tell which, we pick a small prime p ∈ N such that F 0 (x) is squarefree mod p (in particular p = ), and such that τ 24 (p) ≡ 0 mod l 1 but τ 24 (p) ≡ 0 mod l 2 (the opposite would do too). Since an element of PGL 2 (F ) is of order 2 if and only if it has trace 0, looking at the factorisation of F 0 mod p allows us to tell l 1 and l 2 apart: if F 0 (x) mod p splits into linear and quadratic factors but does not split completely, then it is associated to ρproj f 24 ,l 1 , else it is associated to ρproj f 24 ,l 2 .

3.4 Two approaches to the certification of the Galois groups of the F i (x)

In principle, we could simply ask again [Magma] to determine the Galois group of the F i (x), as we did above for F 0 (x). However, the permutation groups GL 2 (F )/S i are not characterised as nicely as PGL 2 (F ), which can be defined as the group of permutations of P 1 (F ) that preserve cross-ratios. As a result, Magma would have to rely on much more involved group-algorithmic methods, which would make the computation much slower 12 . We are going to present methods which require much less computation, and which also yield proofs that are more human-readable.

We are actually going to present two methods to exhibit a permutation isomorphism between the Galois group of F r (x) and GL 2 (F )/S r acting naturally on V r = V /S r . The first one, which we present in section 3.5, is the more natural one, and is entirely due to the reviewer of an older version of this article; the author wishes to thank him profusely for this. Unfortunately, it leads to computations which, albeit not as slow as a blunt [Magma] attack, still require quite a bit of computation time. The method that we will present in the next section 3.6 requires much less computation time; unfortunately, it is also much more complicated to explain.

The geometric approach

The method presented in this section could be used with pretty much any representation ρ : Gal(K/K) -→ GL 2 (F ) whose quotients ρS i are surjective, where K can be any field 13 we can perform computations such as polynomial factorisation with.

In this section, we thus suppose that we have a collection of irreducible polynomials F i (x) ∈ K[x], 0 i r, which ought to correspond to such a Galois representation ρ. We also suppose that the F i (x) split completely in some extension 14 Ω of K, and that we have conjectured a compatible system a bijections (θ i ) 0 i r between the roots of F i (x) in Ω and the V i such that we expect the Galois action on the roots of F i (x) to be permutation isomorphic to GL 2 (F )/S i acting naturally on V i , and such that the relations (Π) and (T) defined on page 10 hold between the roots of F i (x) and those of F i+1 (x) for all i < r. For each i, we identify via θ i the set of roots of F i (x) with V i , and the Galois group of F i (x) with a permutation group of V i ; the projections π i : V i+1 / / / / V i are then Galois-equivariant. Finally, 12 In fact, the GaloisGroup function can still make the right guess pretty quickly, but this guess must then be proved by calling the GaloisProof function, and this is far too slow because of the degree of the polynomials F i (x) for i > 0. For instance, for ∆ mod 19, it takes [Magma] four days to laboriously manage to certify that the Galois group of F 1 (x) is permutation isomorphic to GL 2 (F 19 )/F * 2 19 . By comparison, the method presented in section 3.6 below merely takes a few minutes. 13 We have a number field in mind. 14 We have Ω = C or some finite extension of Q p in mind.

we also assume that we have managed to prove that the Galois group of F 0 (x) is indeed permutation isomorphic to PGL 2 (F ) via θ 0 by a method similar to the one described in section 3.3.1 above. We may thus identify the Galois group of F 0 (x) with PGL 2 (F ).

Our goal is to prove that the Galois group of F r (x) is contained in GL 2 (F )/S r . The key idea of the method presented in this section is to prove that its action on V r is "linear". However, as the addition of vectors does not descend to a well-defined operation on V r , this is not completely straightforward.

To begin with, the relation (T) tells us that the Galois group of F r (x) is a subgroup of the wreath product Sym(F * /S r ) PGL 2 (F ). We first want to prove that it is actually a subgroup of (F * /S r ) PGL 2 (F ), in other words that the action of Galois commutes with scalar multiplication.

Clearly, it is enough to prove that Galois commutes with the scalar multiplication by a generator ε of F * /S r . To do so, we compute by interpolation a polynomial E(x) ∈ Ω[x] which, for all v ∈ V r , maps the root of F r (x) indexed by v to the root indexed by ε • v. We then try to identify the coefficients of this polynomial as approximations of elements of K, whence a polynomial E(x) ∈ K[x]. If E(x) indeed approximately maps the root indexed by v to the one indexed by ε • v for all v ∈ V r and if F r (x) divides F r • E(x), this proves that the Galois action commutes with scalar multiplication on V r .

We expect this approach to succeed since multiplication by ε indeed defines an automorphism not only of the splitting field but also of the root field K[x]/ Fr (x) of Fr (x). Besides, interpolating over the roots of F r (x) amounts to solving a linear system whose determinant is the discriminant of F r (x), so that the coefficients of E(x) should not be too difficult to identify if the ones of F r (x) are nice. In practice, with our polreded polynomial F r (x) ∈ Z[x], it indeed takes just a few seconds to compute E(x) ∈ Q[x] and to check that F r • E(x) ≡ 0 mod F r (x).

We may thus assume henceforth that the Galois group of F r (x) is contained in P = (F * /S r ) PGL 2 (F ). Let us consider, for all triples (L 1 , L 2 , M ) ∈ P 1 (F ) 3 of pairwise distinct vector lines in F 2 , the map

t L 1 ,L 2 ,M : L 1 -→ L 2
that sends a point x ∈ L 1 to the intersection of L 2 and of the line through x that is parallel to M (cf. the figure below).

L 1 L 2 M M (0, 0) x t L 1 ,L 2 ,M (x)
Clearly, for all S F * , this map descends to a map

t S L 1 ,L 2 ,M : L 1 /S -→ L 2 /S.
If we now let X denote the set of triples (v 1 , v 2 , M ) ∈ V r × V r × P 1 (F ) such that the line L 1 spanned by v 1 , the line L 2 spanned by v 2 , and the line M are pairwise distinct, we can define another map

Λ : X -→ F * /S r by sending (v 1 , v 2 , M ) to the unique scalar λ ∈ F * /S r such that v 2 = λ • t S L 1 ,L 2 ,M (v 1
). The group GL 2 (F )/S r acts diagonally on X, and it is clear that Λ is invariant under this action. Conversely, we have the following:

Lemma 5. Let σ ∈ P . If Λ(σ •v 1 , σ •v 2 , σ •M ) = Λ(v 1 , v 2 , M ) for all (v 1 , v 2 , M ) ∈ X, then σ ∈ GL 2 (F )/S r .
Proof. Let σ ∈ P be such an element, and let g ∈ GL 2 (F )/S r have the same image in PGL 2 (F ) as σ. Then σ = g -1 σ lies in (F * /S r ) P 1 (F ) and leaves Λ invariant, and so in fact lies in the diagonal F * /S r . It follows that σ ∈ GL 2 (F )/S r .

As a result, all we need to do is check that Λ is invariant under Galois. This leads us to the resolvent

R(x) = (α 1 ,α 2 ,α 3 )∈Z x - 3 i=1 λ i α i ∈ K[x],
where the λ i ∈ Z are parameters chosen so that R(x) is squarefree, and Z is the set of triples (α 1 , α 2 , α 3 ) with α 3 a root F 0 (x), α 1 ,α 2 roots of F r (x), and α 1 , α 2 and α 3 corresponding to three distinct roots of F 0 (x) under the correspondence (T). If we can compute R(x) rigorously and prove that it factors along the fibres of Λ, then we have proved that the Galois group of F r (x) is contained in GL 2 (F )/S r .

Unfortunately, just like the resolvent R 4 (x) from section 3.3.1, the resolvent R(x) would take a lot of time to compute in our case. Indeed, its degree is 2 2r ( 3 -), and for us this is too much: we have 31 in mind, but even if we restricted ourselves to the primes ≡ -1 mod 4 so that r = 1 so as to get an asymptotic deg R(x) = O( 3 ) which is better than the degrees deg R 4 (x) = O( 4 ) of the resolvents considered in section 3.3.1, we would still have

deg R(x) deg R 4,sym (x),
due to the factor 24 in deg R 4,sym (x) = +1 4 ∼ 4 /24. In fact, it can easily be checked that deg R(x) > deg R 4,sym (x) for all < 103, which incidentally illustrates again how useful switching from R 4 (x) to R 4,sym (x) was in section 3.3.1.

As certifying the Galois group of F 0 (x) thanks to the resolvent R 4,sym (x) already took up to 4 days for = 31, this is a real problem. For this reason, we introduce another method to certify the Galois group of the F i (x) in the next section. This other method is much more complicated, but the computation time it requires is almost negligible compared to the time needed to certify the Galois group of F 0 (x), at least when r 2.

The group cohomology approach

Just like the method presented in the previous section, the method that we are now going to introduce could be applied to a more general framework than the case of modular Galois representations attached to forms of level 1. It is not as general as the previous one though, in that it requires working with representations ρ : Gal(Q/Q) -→ GL 2 (F ) whose image contains SL 2 (F ) and whose determinant is still an odd power of the mod cyclotomic character. For instance, it could be used to certify Galois representation computations attached to newforms of any level, but of trivial nebentypus.

Therefore, in this section we merely suppose that we want to prove that the polynomials F i (x) ∈ Z[x] correspond to such a Galois representation ρ. In particular, this implies that ρS i surjects to GL 2 (F )/S i for all i. We also suppose that we have a relation of the form (T) between the roots of F i (x) and F i+1 (x), that is to say that for all i < r, any root of F i (x) is the sum of precisely two roots of F i+1 (x). However, even though we want to prove the existence of a compatible system of indexations of the sets Z i of roots of F i (x) by V i making the Galois action permutation isomorphic to the natural action of GL 2 (F )/S i , this time we do not suppose that we already have a candidate for such a system of indexations. Indeed, we are going to work with p-adic roots, whereas our algorithm [START_REF] Mascot | Computing modular Galois representations[END_REF] returns a candidate indexation of the complex roots of the F i (x). We therefore let Z i denote the set of roots of F i (x) in some large enough extension of Q p , where p ∈ N is some fixed prime. We reserve the letter p for this prime from now on. Remark 6. It could be argued that since Magma's function GaloisGroup is so efficient, we could easily find a candidate for such a system of indexation of the Z i by the V i if we wanted to. However, we would still have to prove that this indexation is correct, and the method which we are going to present will involve constructing a certified system of indexations from scratch anyway.

In the last steps of the method presented in this section, it will be necessary to assume that p is such that F r (x) (and hence all the F i (x)) is irreducible mod p, and it will be convenient to further assume that p is rather large, say roughly the size of a machine word. Just as in the projective case, there are plenty of elements of GL 2 (F )/S r which act as transitive cycles on V r , so such a prime should not be too difficult to come by. We thus henceforth assume that p is such a prime, and that we gave this p as a parameter to [Magma] when we certified that the Galois group of F 0 (x) may be identified to PGL 2 (F ) as a permutation group of Z 0 .

Finally, we let as before K i denote the root field

K i = Q[x]/F i (x) of F i (x)
, and L i denote its Galois closure, and we suppose that for each i < R we know a primitive integral element

δ i ∈ K i such that K i+1 = K i ( √ δ i
). The idea of the method which we are going to present is to first see the Galois group of F i (x) as a group extension of PGL 2 (F ) of a certain kind, then to use explicit group cohomology arguments so as to establish a finite list of possibilities for this group, and next to rely on ramification arguments to eliminate all possibilities but one15 . This process will rely on an induction on i, and will allow us to prove that Gal(L i /Q) GL 2 (F )/S i as an abstract group. We will then prove, again by induction on i, that this isomorphism can be turned into an isomorphism of permutation groups, in other words that Galois acts on Z i in the expected way. Finally, we will use the Frobenius at p to determine explicitly a system of indexation of the Z i by the V i corresponding to this isomorphism.

Certification of the Galois group of F i (x) as an abstract group

Let Q = κ 0 2 κ 1 2 • • • 2 κ r ⊆ odd Q(µ )
be the subfields of the cyclotomic extension Q(µ ) such that for all 0 i r, Gal(κ i /Q) Z/2 i Z. Thus for instance κ 1 = Q( √ * ), where * = -1 . Consider the following assertions:

(A1) If C ⊆ L r is a Galois subfield of L r such that Gal(C/Q)
Z/2 k Z for some integer k r + 1, then C ramifies only at . (A2) For each i < r, let ∆ i (x) ∈ Z[x] be the monic minimal polynomial of δ i over Q, and let

Q i (x) = Res y ∆ i (y), ∆ i (xy) (x -1) 2 i ( +1) ∈ Z[x].
Then, for each irreducible factor R(x) of Q i (x) over Q, there exists an integer j i such that the field Q[x]/R(x) does not contain κ j+1 , whereas the algebra Q[x]/R(x 2 ) does contain κ j+1 (as a subalgebra with unit).

(A3) For each i < r, there exists a prime v ∈ N such that F i (x) is squarefree and totally split mod v, but F i+1 (x) is not.

We do not know yet whether these assertions hold, but, we expect them to:

1. Since the abelianisation of GL 2 (F ) is given by the determinant, if, as expected, the polynomials F i (x) have Galois group GL 2 (F )/S i and correspond to a Galois representation whose determinant is a power of the mod cyclotomic character, then the maximal Abelian subextension of L r will be contained in the cyclotomic extension Q(µ ); we therefore expect (A1) to hold.

Conversely, we note that if (A1) holds, then any 2-cyclic subextension field L r is contained in Q(µ ∞ ), hence in Q(µ ). Since PGL 2 (F ) has a quotient PGL 2 (F )/ PSL 2 (F ) of order 2, the fields L i ⊃ L 0 all have at least one quadratic subfield, which must then be κ 1 = Q( √ * ), and in particular be unique. We will use this fact repeatedly to prove theorem 7 below.

2. We expect (A2) to hold, but it will make much more sense to explain why after the proof of lemma 9 below, so we postpone the explanation to remark 10.

For now, we just note that for any polynomial P (x) = n i=1 (x -α i ) such that P (0) = 0, Res y P (y), P (xy) = (-1) n P (0) i,j

x -α i α j , so that Res y P (y), P (xy) (x -1) n = (-1) n P (0)

i =j x - α i α j .
Therefore, Q i (x) is indeed a polynomial.

3. Finally, we also expect (A3) to hold: for each i, it suffices to consider a prime at which the Frobenius element is [ ε 0 0 ε ] for some ε ∈ S i -S i+1 . We can thus even predict that at such a prime, while F i (x) splits in linear factors, F i+1 (x) will split in quadratic factors.

Conversely, in this subsection and the next one, we are going to prove the following result, which thus yields an efficient method to formally prove our computations: Theorem 7. Assume that the assertions (A1), (A2) and (A3) hold. In addition, if is such that r 3, also assume that κ i+1 ⊂ L i for all 2 i < r. Then, for all i r, (i) Gal(L i /Q) is isomorphic to GL 2 (F )/S i , not only abstractly, but also as an extension of PGL 2 (F ), and

(ii) there exists such an isomorphism which makes the Galois action on the roots of F i (x) equivalent to the natural action of GL 2 (F )/S i on V i .

Remark 8. It is unfortunate that we have to make the extra assumption that κ i+1 ⊂ L i for all 2 i < r when r 3, especially as the author does not know of any computationally cheap way to check this assumption rigorously. Indeed, if as expected the polynomials F i (x) correspond to a Galois representation ρ, then under the isomorphism Gal(L i /Q) GL 2 (F )/S i , κ i+1 corresponds to the kernel of the determinant, whereas the bigger compositum of K i with itself (cf. remark 10 below) corresponds to {[ s 0 0 s ] mod S i | s, s ∈ S i } and so does not contain κ i+1 , so that unfortunately one has to deal with the 3-fold compositum of K i to show that κ i+1 ⊂ L i . The method presented in the previous section does not suffer from this shortcoming; on the other hand, the values of for which we have data to use theorem 7 on, namely 31, are all such that r 2, except for = 17 for which even the method presented in section 2 does not suffice to reduce the polynomials F i (x) anyway.

Before we start proving theorem 7, let us indicate how the assertions (A1), (A2) and (A3) can be checked in practice.

1. Let N be the product of the odd primes different from that ramify in L r , and let C be a 2-cyclic sub extension of L r of degree 2 k , k r + 1. Then C ⊆ Q(µ 2 r+3 N ), and so Gal Q(µ 2 r+3 N )/C is the kernel of some surjective morphism

ϕ : Gal Q(µ 2 r+3 N )/Q (Z/2 r+3 N Z) * -→ Z/2 k Z.
By Chinese remainders, we can write ϕ = ϕ + ψ, where ϕ : (Z/ Z) * -→ Z/2 k Z and ψ : (Z/2 r+3 N Z) * -→ Z/2 k Z.

We then look for odd primes v ∈ N such that v ≡ 1 mod and F r (x) is squarefree and splits completely mod v. For such v, we have ϕ (v) = 0 and ϕ(v) = 0, so that ψ(v) = 0 too. Therefore, if we can find a collection of such v that spans (Z/2 r+3 N Z) * ⊗ Z/2 r+1 Z, then this proves that ψ is necessarily trivial, and thus that (A1) holds.

In practice, finding primes v which split F r (x) completely should not be too difficult since we expect Gal(L r /Q) to be isomorphic to the GL 2 (F )/S r . Then, the fact that a collection of primes v spans (Z/2 r+3 N Z) * ⊗ Z/2 r+1 Z can be checked by expressing the latter group explicitly as a product of cyclic groups, by determining the image of the primes v in these groups thanks to a discrete logarithm computation, and finally by computing a Smith normal form. This should all be painless, as N will typically involve few prime factors, and these primes will not be very large. Note that even in the case where r is large, the (Z/2 r+3 Z) * -part can be treated easily, since for any integer a 3, a subgroup of (Z/2 a Z) * which surjects onto (Z/8Z) * is necessarily the whole of (Z/2 a Z) * .

We expect this approach to succeed, because if, as expected, Gal(L r /Q) is isomorphic to GL 2 (F )/S r and the determinant of the associated Galois representation is a power of the mod cyclotomic character, then L r will have a unique maximal 2-cyclic subextension C, which has no non-trivial Abelian subextensions since

Gal(L r /C) = {A ∈ GL 2 (F )/S r | det A = 1} SL 2 (F )
has trivial abelianisation.

Note that in the particular case of a Galois representation of level 1, there is much less work to do: it suffices to check that the discriminant of K r is, up to a sign, a power of .

Also note that if (A1) does hold, then L r cannot actually have any subextension C such that Gal(C/Q) Z/2 r+1 Z, by definition of r.

2. We explain in remark 10 below why we expect Q i (x) to factor into 2 i -1 irreducible factors of degree 2 i ( + 1) and one large irreducible factor, and why (A2) should be satisfied for j = 0 for the small factors and j = 1 for the large factor. To check that κ j+1 ⊂ Q[x]/R(x), it suffices to find a prime v ∈ N such that the splitting behaviour of R(x) mod v is inconsistent with the splitting behaviour of v in κ j+1 , for instance such that v is not a square mod and such that R(x) mod v is squarefree and splits into factors whose degrees are not all divisible by 2 j+1 . To prove that κ j+1 ⊂ Q[x]/R(x 2 ), we check that R(x 2 ) splits into 2 j+1 factors over κ j+1 , which means that the Q-algebra

κ j+1 ⊗ Q Q[x]/R(x 2
) has 2 j+1 factors and thus that the minimal polynomial of a primitive element of κ j+1 splits completely

16 in Q[x]/R(x 2 ).
Although this is the most computation time-demanding part of the certification process, it is quite fast when r = 1 (for = 31 it merely takes a few minutes on the author's laptop), which occurs for half of the values of , and for r = 2 it remains quite tractable. This is a major improvement compared to the geometric method presented in section 3.5.

3. For (A3), we simply loop over primes v ∈ N and factor the polynomials F i (x) mod v until all the couples (i, i + 1) have been dealt with. As explained above, such primes v should not be too hard to come by.

We assume henceforth that (A1), (A2) and (A3) hold, and proceed to the proof of part (i) of theorem 7. Our proof consists in examining Gal(L i /Q) inductively for i = 1, . . . , r. For clarity, we have divided the induction loop into six steps.

Step 1: The Galois closures are not so large

Since K i+1 = K i ( √ δ i ), we know that L i+1 = L i δ σ i , σ ∈ Gal(L i /Q) . Lemma 9. Actually, L i+1 = L i ( √ δ i ) is a nontrivial quadratic extension of L i .
Proof. According to (A3), for each i, there exists a rational prime that is totally split in L i but not in L i+1 , which proves that the extension L i+1 /L i is not trivial. Showing that it is quadratic amounts to proving that

δ σ i δ i is a square in L i for all σ ∈ Gal(L i /Q). To see this, pick a σ ∈ G Q such that δ σ i = δ i , so that Q δ σ i δ i is isomorphic to Q[x]/R(x) for some irreducible factor R(x) of Q i (x) over Q. The polynomial R(x 2 ) may be reducible, but in any case Q δ σ i δ i is a factor of the algebra Q[x]/R(x 2 ).
We claim that κ i+1 ⊂ L i for all i < r. Indeed,

• for i = 0 it follows from the fact that Gal(L 0 /Q) = PGL 2 (F ) has a quotient of order 2 so that L 0 has a quadratic subfield, which can only be κ 1 = Q( √ * ) according to (A1),

• for i = 1 (which we only need to consider when r 2), it follows again from (A1) and the fact that we know after one induction loop (cf. proposition 14) that Gal(L 1 /Q) is isomorphic to GL 2 (F )/S 1 and thus has a quotient isomorphic to Z/4Z since r 2,

• and finally, for i 2, this is the extra hypothesis of theorem 7 (which we thus only need when r 3).

Therefore, for j i we may consider then the extension diagram

L i κ j δ σ i δ i ? κ j+1 δ σ i δ i κ j δ σ i δ i 2 2 κ j+1 κ j
The two extensions marked with a 2 in this diagram are at most quadratic.

We may assume that the extension κ j

δ σ i δ i /κ j δ σ i δ i
is not trivial, since the proof that

δ σ i δ i ∈ L i is over if it is.
According to (A2), we may pick j such that

κ j+1 ⊂ Q δ σ i δ i . But then we must have κ j δ σ i δ i = κ j+1 δ σ i δ i , so that δ σ i δ i ∈ L i as claimed.
As a consequence, L i+1 = L i ( √ δ i ) and Gal(L i+1 /Q) is an extension of Gal(L i /Q) by C 2 . This extension is necessarily central, since Aut(Z/2Z) is trivial. Remark 10. If F i (x) corresponds to ρS i as expected, and if it holds that

K i = Q(δ i ) and that Q δ σ i δ i = Q(δ i , δ σ
i ) (which is extremely likely), then we get an indexation of the conjugates of δ i by V i , and under the identification of Gal(L i /Q) with GL 2 (F )/S i provided by ρ S i , the field Q

δ σ i δ i
corresponds by Galois theory to a conjugate of the subgroup {[ s * 0 * ] mod S i , s ∈ S i } or {[ s 0 0 s ] mod S i , s, s ∈ S i } of GL 2 (F )/S i , depending on whether the vectors indexing δ i and δ σ i are collinear or not. Therefore, we expect Q i (x) to split over Q into 2 i -1 irreducible factors of degree 2 i ( + 1), corresponding to the nontrivial scalar elements in GL 2 (F )/S i , plus one large irreducible factor corresponding to nonscalar elements.

Besides, in the case when the vectors indexing δ i and δ σ i are not collinear, for j = i the Galois subgroup diagram corresponding to the subfield diagram in the above proof would be 1 ?

[

s 0 0 s ] mod S i s,s ∈S i , ss ∈S i+1 [ s 0 0 s ] mod S i (s,s ∈S i ) 2 2 det -1 (S i+1 ) det -1 (S i )
But the group {[ s 0 0 s ] mod S i , s, s ∈ S i } is isomorphic to S i , hence is cyclic, so the two quadratic extensions of Q

δ σ i δ i
marked with a 2 in the above diagrams should coincide. We therefore expect (A2) to hold for the large factor R(x) of Q i (x) with j = i.

Similarly, when the vectors indexing δ i and δ σ i are collinear, we get for j = 0 the subgroup diagram 1 ?

[

s * 0 s ] mod S i (s∈S i , ss ∈F * 2 ) [ s * 0 * ] mod S i (s∈S i ) 2 2 det -1 (F * 2 ) GL 2 (F )/S i and since {[ s * 0 * ] mod S i , s ∈ S i } F
F * has only one subgroup of index 2, we expect (A2) to hold for the small factors of Q i (x) with j = 0.

Step 2: Central 2-cyclic extensions of PGL 2 (F )

In what follows, for n ∈ N we denote by C n the cyclic group of order n. In order to go on with the proof, we will need to know the classification of the central extensions of PGL 2 (F ) by C 2 i , i ∈ N.

It is well-known (cf. for instance [NSW08, theorem 1.2.4]) that given a group G and a G-module M , the extensions of G by M such that the conjugation action of lifts of elements of G on M corresponds to the G-module structure on M are classified by the cohomology group H 2 (G, M ). The class of the cocycle β : G × G -→ M corresponds to the set M × G endowed with the group law

(m, g) • (m , g ) = m + g • m + β(g, g ), gg .
In particular, the following result is immediate:

Lemma 11. Consider a (necessarily central) extension

1 -→ C 2 -→ G -→ G -→ 1
of a group G by C 2 . Let β : G×G -→ C 2 be a cocycle representing the corresponding cohomology class, and let g ∈ G be an element of G of order 2. Then the lifts of g in G have order 2 if β(g, g) is trivial, but have order 4 else. Furthermore (cf. [Kar87, theorem 2.1.19]), if the G-action on M is trivial, then there is a split exact sequence of Abelian groups

0 / / Ext 1 Z (G ab , M ) φ / / H 2 (G, M ) ψ / / Hom M , H 2 (G, C * ) o o / / 0 ( )
where Ext 1 Z (G ab , M ) classifies the abelian extensions of the abelianised G ab of G by M , M = Hom(M, C * ) is the group of complex-valued characters on M , H 2 (G, C * ) (with trivial G-action on C * ) is the so-called Schur multiplier of G, and ψ maps the class of the cocycle β ∈ H 2 (G, M ) to the transgression map (not to be confused with a trace)

Tra Theorem 12. Let i 1 be an integer.

β : M -→ H 2 (G, C * ) χ -→ χ • β associated to the class of β. Besides, the Schur multiplier H 2 (G, C * ) is trivial if G is cyclic (cf. [Kar87,
(i) H 2 PGL 2 (F ), C 2 i
C 2 × C 2 , so that there are four central extensions of PGL 2 (F ) by C 2 i .

(ii) These extensions are

• the trivial extension C 2 i × PGL 2 (F ), corresponding to the trivial coho- mology class β 0 ∈ H 2 PGL 2 (F ), C 2 i ,
• the group 2 i det PGL 2 (F ), whose class

β det ∈ H 2 PGL 2 (F ), C 2 i is the inflation of the non-trivial element of H 2 PGL 2 (F ) ab , C 2 i C 2
(in other words, β det (g, g ) is non-zero if and only if neither g nor g lie in PSL 2 (F )),

• the group

2 i -PGL 2 (F ), with class β -∈ H 2 PGL 2 (F ), C 2 i , defined for i = 1 as 2 -PGL 2 (F ) = SL 2 (F ) √ ε 0 0 1/ √ ε SL 2 (F ) ⊂ SL 2 (F 2 )
where ε denotes a generator of F * , and that for i 2 corresponds to the image of the cohomology class of 2 -PGL 2 (F ) by the map

H 2 PGL 2 (F ), C 2 -→ H 2 PGL 2 (F ), C 2 i induced by the embedding of C 2 into C 2 i ,
• and the group 2 i + PGL 2 (F ), whose associated cohomology class β + is the sum in H 2 PGL 2 (F ), C 2 i of β det and of β -.

(iii) Identify C 2 with Z/2Z, let g ∈ PGL 2 (F ) be an element of order 2, and let β 0 , β det , β -and β + be normalised cocycles (that is to say β(1, h) = β(h, 1) = 0 for all h ∈ PGL 2 (F )) representing the cohomology classes of these four extensions. If i = 1, then their value at (g, g) does not depend on the choice of these cocycles, and are

• β 0 (g, g) = 0 ∀g, • β det (g, g) = 0, g ∈ PSL 2 (F ), 1, g ∈ PSL 2 (F ), • β -(g, g) = 1 ∀g of order 2, • β + (g, g) = 1, g ∈ PSL 2 (F ), 0, g ∈ PSL 2 (F ).
(iv) For i 2, the abelianisations of these extensions are

• C 2 i × PGL 2 (F ) ab C 2 i × C 2 , • 2 i det PGL 2 (F ) ab C 2 i+1 , • 2 i -PGL 2 (F ) ab C 2 i-1 × C 2 , • 2 i + PGL 2 (F ) ab C 2 i .
Proof. We shall only give the idea of the proof here, and refer the reader to [Que95, proposition 2.4 and lemma 3.2].

(i) On the one hand, the abelianised of PGL

2 (F ) is PGL 2 (F )/ PSL 2 (F ) C 2 , so that Ext 1 Z (PGL 2 (F ) ab , C 2 i ) Ext 1 Z (C 2 , C 2 i ) C 2 .
On the other hand, the Schur multiplier H 2 PGL 2 (F ), C * is isomorphic to C 2 (cf. [Que95, proposition 2.3]). The result then follows from the split exact sequence ( ).

(ii) Consider again the exact sequence ( ). Then β det lies in the image of φ since it is inflated from PGL 2 (F ) ab . On the other hand, for i = 1, β -does not lie in Im φ, for if it did, then the associated transgression map would be trivial, so that the commutator subgroup of 2 -PGL 2 (F ) would meet the kernel ± [ 1 0 0 1 ] of the extension trivially, which is clearly not the case since

-1 0 0 -1 is a commutator in SL 2 (F ) ⊂ 2 -PGL 2 (F ). For i 2, the commutative diagram 1 / / C 2 / / _ 2 -PGL 2 (F ) / / _ PGL 2 (F ) / / _ 1 1 / / C 2 i / / 2 i -PGL 2 (F ) / / PGL 2 (F ) / / 1
shows that C 2 i still intersects the commutator subgroup of 2 i -PGL 2 (F ) nontrivially, so that β -does not lie in Im φ either. The extensions 2 i det PGL 2 (F ) and 2 i -PGL 2 (F ) thus represent different non-trivial cohomology classes in

H 2 PGL 2 (F ), C 2 i C 2 × C 2 , hence the result.
(iii) It is a general fact (cf. [Que95, lemma 3.1] that the image at (g, g) of a normalised cocycle representing an extension of a group G by C 2 only depends on the cohomology class of this cocycle in H 2 (G, C 2 ).

• The case of the trivial extension is obvious since the trivial cohomology class is represented by the trivial cocycle.

• The case of β det follows from its very definition.

• Since it is a subgroup of SL 2 (F 2 ), the group 2 -PGL 2 (F ) has only one element of order 2, namely the central element -1 0 0 -1 . In particular, no element g ∈ PGL 2 (F ) of order 2 remains of order 2 when lifted to 2 -PGL 2 (F ), and the result follows from lemma 11.

• The case of β + follows since we may take β + = β det + β -.

(iv) Again, the case of the trivial extension is clear. In the other cases, the result follows from the fact that the intersection of C 2 i with the commutator subgroup of the extension is isomorphic to the image of the transgression map

Tra β : C 2 i -→ H 2 PGL 2 (F ), C * C 2 ,
which is trivial in the case of β det and non-trivial in the case of β -and β + .

We shall now use this classification to prove by elimination that Gal(L i /Q) is isomorphic to GL 2 (F )/S i for all i.

Remark 13. The group GL 2 (F )/S i must be one of the cases presented in theorem 12, but at this point it is not clear at all which one. We will eventually determine this, cf. remark 15 below.

Step 3: The case of L 1 /L 0 We first deal with the first extension

L 1 /L 0 in the quadratic tower L r / • • • /L 0 . The Galois group Gal(L 1 /Q) is a (necessarily central) extension of Gal(L 0 /Q) PGL 2 (F ) by C 2 . Proposition 14. Gal(L 1 /Q) is isomorphic to GL 2 (F )/S 1 as an extension of PGL 2 (F ).
Proof. Let β be a normalised cocycle representing the cohomology class corresponding to the extension Gal(L 1 /Q) of PGL 2 (F ). According to theorem 12(ii),

Gal(L 1 /Q) is isomorphic either to C 2 × PGL 2 (F ), 2 det PGL 2 (F ), 2 -PGL 2 (F ) or 2 + PGL 2 (F ), and β is correspondingly cohomologous to β 0 , β det , β -or β + .
If Gal(L 1 /Q) were the trivial extension C 2 × PGL 2 (F ), then L 1 would have a subextension L ab 1 with Galois group isomorphic to

C 2 × PGL 2 (F ) ab C 2 × C 2 ,
and hence three distinct quadratic subfields, which contradicts (A1). Let now τ 1 ∈ Gal(L 1 /Q) be the complex conjugation relative to some embedding of L 1 into C. It induces an element τ 0 ∈ Gal(L 0 /Q), which is not the identity since its image by ρ proj f,l is conjugate to g = [ 1 0 0 -1 ] ∈ PGL 2 (F ). In particular, τ 1 is not trivial either, so it has order 2. Therefore τ 0 has a lift to Gal(L 1 /Q) of order 2, so that β(τ 0 , τ 0 ) is trivial by lemma 11. Theorem 12(iii) then only leaves one possibility: if ≡ 1 mod 4, then g ∈ PSL 2 (F ), so that β cannot be cohomologous to β -nor to β + and so Gal(L 1 /Q) must be isomorphic to 2 det PGL 2 (F ), whereas if ≡ -1 mod 4, then g ∈ PSL 2 (F ), so that β cannot be cohomologous to β -nor to β det and so Gal(L 1 /Q) must be isomorphic to 2 + PGL 2 (F ).

Besides, L1 is a quadratic extension of L0 and has only one quadratic subfield since its Galois group is isomorphic to GL 2 (F )/S 1 , so that the same reasoning applies and shows that Gal( L1 /Q) is isomorphic to 2 det PGL 2 (F ) if ≡ 1 mod 4 and to 2 + PGL 2 (F ) if ≡ 1 mod 4. Either way, we have

Gal(L 1 /Q) Gal( L1 /Q) GL 2 (F )/S 1 .
Step 4:

Gal(L i /Q) is an extension of PGL 2 (F ) by C 2 i
If ≡ -1 mod 4, then r = 1, so that the proof that Gal(L r /Q) GL 2 (F )/S r is over. We therefore assume that ≡ 1 mod 4 henceforth until we finish proving part (i) of theorem 7. We shall first prove by induction on i that Gal(L i /Q) is an extension of PGL 2 (F ) by F * /S i C 2 i , then that this extension is central, and finally that it is isomorphic to GL 2 (F )/S i . Note that we have just proved above that it is so for i = 1.

Besides, κ 2 cannot be contained in L 0 because PGL 2 (F ) ab C 2 , and since κ 2 is a quadratic extension of

κ 1 = Q( √ * ) ⊂ L 0 and L 1 is a quadratic extension of L 0 , we have L 1 = κ 2 L 0 : L 1 = κ 2 L 0 L 0 2 κ 2 κ 1 2 Q 2 Now if Gal(L i+1 /L 0 ) were isomorphic to C 2 i × C 2 , then
, letting E be the subfield of L i+1 fixed by C 2 i × {1}, we would have the extension tower

L i+1 L i {1}×C 2 L 1 = κ 2 L 0 C 2 i-1 ×C 2 E C 2 i ×{1} L 0 2 2 C 2 i ×C 2 κ 2 κ 1 2 Q 2
where C 2 i-1 denotes the subgroup of C 2 i of index 2. The extensions E/L 0 and L 1 /L 0 are both quadratic subextensions of L i+1 /L 0 , but they are distinct since they correspond respectively to the distinct subgroups

C 2 i × {1} and C 2 i-1 × C 2 of Gal(L i+1 /L 0 ) = C 2 i × C 2 .
On the other hand, the field E is contained in L i+1 and thus has only one quadratic subfield according to (A1), so that the same reasoning as in step 3 above shows that Gal(E/Q) is isomorphic to GL 2 (F )/S 1 . But then E has a C 4 -subfield, which can only be κ 2 , and so E ⊇ κ 2 L 0 = L 1 , hence E = L 1 since they are both quadratic extensions of L 0 , a contradiction. This shows that Gal(L i+1 /L 0 ) cannot be isomorphic to C 2 i × C 2 , so must be isomorphic to C 2 i+1 . It follows that Gal(L i+1 /Q) is an extension of PGL 2 (F ) by Gal(L i+1 /L 0 ) C 2 i+1 , and the induction is complete.

Step 5:

Gal(L i /Q) is a central extension of PGL 2 (F )
We shall now prove by induction on i that the extension

1 -→ C 2 i -→ Gal(L i /Q) -→ PGL 2 (F ) -→ 1 is central. Note that it is so for i = 1 since Aut(C 2 ) is trivial.
Let i 2, and assume on the contrary that this extension is not central.

Since Aut(C 2 i ) C 2 × C 2 i-2 is Abelian, the morphism PGL 2 (F ) -→ Aut(C 2 i ) expressing the conjugation action of PGL 2 (F ) on C 2 i factors through PGL 2 (F ) ab = PGL 2 (F )/ PSL 2 (F ) C 2 ,
so that PSL 2 (F ) acts trivially whereas there exists an involution φ of C 2 i such that gxg -1 = φ(x) for all g ∈ PGL 2 (F ) -PSL 2 (F ) and x ∈ C 2 i . If we identify C 2 i with Z/2 i Z, then by induction hypothesis this involution induces the identity on Z/2 i-1 Z, so it must be x → (1 + 2 i-1 )x.

There is thus only one possible non-trivial conjugation action of PGL 2 (F ). In order to compute H 2 PGL 2 (F ), C 2 i for this non-trivial action, we use the inflationrestriction exact sequence (cf. [Ser79, proposition VII.6.5])

0 -→ H 2 (C 2 , C 2 i ) Inf -→ H 2 PGL 2 (F ), C 2 i Res -→ H 2 PSL 2 (F ), C 2 i . ( †)
This is legitimate since, as PSL 2 (F ) acts trivially, we have

H 1 PSL 2 (F ), C 2 i = Hom PSL 2 (F ), C 2 i = 0 since PSL 2 (F ) is simple.
On the one hand, since C 2 = {1, ε} is cyclic, the groups H q (C 2 , M ) are the cohomology groups of the complex

0 -→ M ε-1 -→ M ε+1 -→ M ε-1 -→ M ε+1 -→ • • • for any C 2 -module M (cf. [Lan02, chapter XX exercise 16]). In particular, H 2 (C 2 , C 2 i ) = ker(ε -1) Im(ε + 1) = (Z/2 i Z)[2 i-1 ] (2 + 2 i-1 )(Z/2 i Z) C 2 , i = 2, 0, i 3.
On the other hand, as PSL 2 (F ) acts trivially, the group H 2 PSL 2 (F ), C 2 i can be computed by using the split exact sequence ( ). As PSL 2 (F ) ab = {1} since PSL 2 (F ) is simple, and as the Schur multiplier is

H 2 PSL 2 (F ), C * C 2 (Steinberg, cf. [Kar87, theorem 7.1.1.(ii)]), it follows that H 2 PSL 2 (F ), C 2 i C 2 .
Let 2 i PSL 2 (F ) denote the non-trivial extension. One has

2PSL 2 (F ) SL 2 (F ),
and the non-trivial element of H 2 PSL 2 (F ), C 2 i is the image of the non-trivial element γ SL 2 ∈ H 2 PSL 2 (F ), C 2 corresponding to SL 2 (F ) by the map

H 2 PSL 2 (F ), C 2 -→ H 2 PSL 2 (F ), C 2 i induced by the embedding of C 2 into C 2 i .
Consider the inflation-restriction exact sequence ( †), and let

β ∈ H 2 PGL 2 (F ), C 2 i
be the cohomology class corresponding to the extension

1 -→ C 2 i -→ Gal(L i /Q) -→ PGL 2 (F ) -→ 1. If γ = Res β ∈ H 2 PSL 2 (F ), C 2 i were trivial, then β = Inf α would be the inflation of some α ∈ H 2 C 2 , C 2 i , so that Gal(L i /Q) would be isomorphic to the fibred product G α × C 2 PGL 2 (F ), where G α is the group extension 1 -→ C 2 i -→ G α -→ C 2 -→ 1 corresponding to α. Actually, if i 3, then β = Inf α would be trivial since H 2 C 2 , C 2 i = 0, so that Gal(L i /Q) would be isomorphic to the semi-direct product C 2 i PGL 2 (F ), whereas if i = 2, then H 2 C 2 , C 2 i C 2 , so that Gal(L 2 /Q) would be isomorphic either to C 4 PGL 2 (F ) or to Q 8 × C 2
PGL 2 (F ), where Q 8 , the quaternionic group {±1, ±i, ±j, ±k}, is the extension

1 -→ C 4 -→ Q 8 -→ C 2 -→ 1
corresponding to the non-trivial element of H 2 (C 2 , C 4 ). However, the abelianisations

C 2 i PGL 2 (F ) ab C 2 i-1 × C 2 and Q 8 × C 2 PGL 2 (F ) ab C 2 × C 2 contradict (A1). It follows that γ = Res β ∈ H 2 PSL 2 (F ), C 2 i cannot be trivial, so it must be γ SL 2 ∈ H 2 PSL 2 (F ), C 2 followed by the embedding of C 2 into C 2 i . Let g = [ 1 0 0 -1 ] ∈ PGL 2 (F ).
As ≡ 1 mod 4, g lies in PSL 2 (F ), and since the only element of order 2 of SL 2 (F ) is -1 0 0 -1 , g cannot be lifted to an element of order 2 of SL 2 (F ), so that γ SL 2 (g, g) = 0 by lemma 11. On the other hand, since g is the image of the complex conjugation (with respect to some embedding of L 0 into C) by the projective Galois representation ρ proj , it must lift to an element of order 2 of Gal(L i /Q), which is contradictory: in the extension Gal(L i /Q), seen as the set Z/2 i Z × PGL 2 (F ) endowed with the group law

(x 1 , g 1 ) • (x 2 , g 2 ) = x 1 + g 1 • x 2 + β(g 1 , g 2 ), g 1 g 2 , we compute that (x, g) • (x, g) = x + g • x + β(g, g), g 2 = β(g, g), 1
as g ∈ PSL 2 (F ) acts trivially, so β(g, g) must be zero, but β(g, g) = γ SL 2 (g, g) = 0 since g ∈ PSL 2 (F ).

It is therefore impossible that the extension

1 -→ C 2 i -→ Gal(L i /Q) -→ PGL 2 (F ) -→ 1
be not central, which completes the induction.

Step 6:

Gal(L i /Q) GL 2 (F )/S i
We may now apply again theorem 12 to Gal(L r /Q). Part (iv) of this theorem combined with (A1) means that Gal(L r /Q) cannot be isomorphic to C 2 r ×PGL 2 (F ) nor to 2 r -PGL 2 (F ). It cannot be isomorphic to 2 r det PGL 2 (F ) either, else L r would have a C 2 r+1 -subfield by part (iv) of theorem 12, which would be contained in the cyclotomic extension Q(µ ) according to (A1), but this would contradict the definition of r. Therefore, Gal(L r /Q) must therefore be isomorphic to 2 r + PGL 2 (F ). Besides, the same reasoning applies to Lr , whose Galois group is isomorphic GL 2 (F )/S r since det ρ is by assumption an odd power of the mod cyclotomic character. Therefore, we have

Gal(L r /Q) 2 r + PGL 2 (F ) Gal( Lr /Q) GL 2 (F )/S r ,
and the proof of part (i) of theorem 7 is now complete.

Remark 15. We can now go back down the quadratic tower L r / • • • /L 0 and see that Gal(L i /Q) GL 2 (F )/S i for all i. Besides, it is easy to see that the abelianisation of GL 2 (F )/S i is det : GL 2 (F )/S i -→ F * /S 2 i , and since S 2 i = S i+1 S i for i < r whereas S 2 r = S r as -1 ∈ S r , theorem 12 part (iv) leads to the unified formula

Gal(L i /Q) GL 2 (F )/S i    PGL 2 (F ), i = 0, 2 i det PGL 2 (F ), 0 < i < r, 2 r + PGL 2 (F ), i = r,
which is valid for ≡ 1 mod 4 as well as ≡ -1 mod 4. This allows us to identify for each i the extension GL 2 (F )/S i of PGL 2 (F ) amongst the ones listed in part (ii) of theorem 12.

Certification of the Galois action

At this point, we have proved that Gal(L i /Q) is abstractly isomorphic to GL 2 (F )/S i for each 0 i r, but only for i = 0 do we know that it is permutation-isomorphic to GL 2 (F )/S i acting naturally on V i = V /S i . For each i > 0, we will now determine an isomorphism between Gal(L i /Q) and GL 2 (F )/S i and a bijection θ i : Z i ∼ -→ V i which make the Galois action on Z i permutation-isomorphic to the natural action of GL 2 (F )/S i on V i in a compatible way as i varies. This data can then be used to compute the Dokchitsers' resolvents Γ C (x), and thus to compute trace of Frobenius elements, in a certified way.

Let us first fix an isomorphism ϕ r from the Gal(L r /Q) to GL 2 (F )/S r . Since the Galois groups Gal(L i /Q) are isomorphic to GL 2 (F )/S i as extensions of PGL 2 (F ) in a compatible way, ϕ r induces a system of isomorphisms

ϕ i : Gal(L i /Q) GL 2 (F )/S i 0 i r such that the diagram Gal(L r /Q)
agrees with the one we determined with the help of [Magma] in section 3.3.1, and we will use the isomorphisms ϕ i to identify Gal(L i /Q) with GL 2 (F )/S i from now on.

Since, by section 3.3.1, the action of Gal(L 0 /Q) on Z 0 is equivalent to the natural action of PGL 2 (F ) on P 1 (F ), we know that the stabiliser of a root of F 0 (x) is conjugate to a group of upper triangular matrices in PGL 2 (F ). Therefore, the stabiliser of a root of F 1 (x) is a subgroup of index 2 of the subgroup of upper triangular matrices in GL 2 (F )/S 1 .

Lemma 16. Let B be a subgroup of GL 2 (F ) of the form

B = [ s x 0 s ] s ∈ S, s ∈ S , x ∈ F ,
where S, S F * are subgroups of the multiplicative group of F . If neither S nor S is reduced to {1}, then B has exactly 3 subgroups of index 2, namely

[ s x 0 s ] s ∈ S 2 , [ s x 0 s ] s ∈ S 2 , and [ s x 0 s ] s ∈ S 2 ⇔ s ∈ S 2 ,
where we write S 2 for {s 2 , s ∈ S}, and similarly for S 2 .

Proof. Since a subgroup of index 2 is always normal, such a subgroup is the kernel of a non-trivial morphism from B to C 2 . As the latter group is Abelian, such a morphism factors through the abelianisation of B. Let s ∈ S, s = 1. The identity

ghg -1 h -1 = [ 1 1-s 0 1 ] where g = [ 1 1 0 1 ], h = [ s 0 0 1 ] ∈ B shows that [ 1 1 0 1
] lies in the commutator subgroup of B, so that the abelinanisation of B is

B -→ S × S [ s x 0 s ] -→ (s, s ).
Therefore, we have canonically Hom(B, C 2 ) Hom(S × S , C 2 ) Hom(S, C 2 ) × Hom(S , C 2 ).

Since S and S are cyclic because F * is, the result follows.

According to this lemma, the stabiliser of a root of F 1 (x) in Gal(L 1 /Q) could be either

H + = [ s x 0 s ] s ∈ F * 2 , s ∈ F * , x ∈ F /S 1 , H -= [ s x 0 s ] s ∈ F * , s ∈ F * 2 , x ∈ F /S 1 , or H 0 = [ s x 0 s ] s, s ∈ F * , x ∈ F , ss ∈ F * 2 /S 1 .
However, the nontrivial element [ ε 0 0 ε ] ∈ GL 2 (F )/S 1 , where ε ∈ F * /F * 2 , is central and lies in H 0 , so it lies in the intersection of the conjugates of H 0 , so that the action of GL 2 (F )/S 1 on its H 0 -cosets is not faithful. Therefore, the stabiliser of a root of F 1 (x) must be conjugate either to H + or to H -.

Consider now the compatible collection of involutory automorphisms

Ψ i : GL 2 (F )/S i -→ GL 2 (F )/S i A -→ 1 det A A.
Since Ψ 0 is the identity on PGL 2 (F ), we may replace the isomorphisms ϕ i with Ψ i • ϕ i without breaking the compatibility with the identification of Gal(L 0 /Q) with PGL 2 (F ) made in section 3.3.1, and since Ψ 1 swaps H + and H -, we may assume without loss of generality that the stabiliser of a root of F 1 (x) is conjugate to H + . An induction on i then reveals that the stabiliser in Gal(L i /Q) of a root of F i (x) is conjugate to [ s x 0 y ] s ∈ S i , y ∈ F * , x ∈ F /S i . Indeed, at each step of the induction, lemma 16 gives us 3 possibilities, but only one of them yields a faithful action of GL 2 (F )/S i on its cosets, for the same reason as above.

As a consequence, we now know that for each i there exists a bijection

θ i : Z i ∼ -→ V i
which makes the Galois action on Z i equivalent to the natural action of GL 2 (F )/S i on V i , so we have proved part (ii) of theorem 7. However, we must make the indexation θ r of Z r by V r explicit, so as to be able to proceed with the computation of the Dokchitsers' resolvents Γ C (x). We do so as follows.

Recovering the indexation of the p-adic roots

Recall that we have fixed a large prime p ∈ N such that F r (x) mod p is irreducible. Consider the field K r = F p [t]/F r (t). The t p j , 0 j < 2 r ( + 1), are the roots of F r in K r , and so by the hypothesis we have made on the relation between the roots of F i (x) and the ones of F i+1 (x), all the polynomials F i (x) are squarefree and split completely over K r . Let Z i be the set of the roots of F i (x) in K r , so that we have17 2-to-1 projection maps i : Z i+1 / / / / Z i such that for all z ∈ Z i+1 , there exists a unique z ∈ Z i+1 such that z + z = i (z) ∈ Z i . In section 3.3.1, [Magma] computed for us the Galois group Gal(L 0 /Q) as a permutation group on the roots of F 0 (x) in some extension M of F p , which unfortunately is not isomorphic18 to K r . Magma also gave us an indexation (m P ) P ∈P 1 (F ) of these roots, and we would like to transfer this indexation to Z 0 ⊂ K r while keeping compatibility with the action of Gal(L 0 /Q) = PGL 2 (F ). We do so by computing mod p the factors R 4,P (x) = P 1 ,P 2 ,P 3 ,P 4 ∈P 1 (F ) pairwise distinct [P 1 ,P 2 ,P 3 ,P 4 ]=P

x -

4 i=1 λ i m P i ∈ F p [x]
of the resolvent R 4 (x) from section 3.3.1 for each P ∈ P 1 (F ) -{∞, 0, 1}, where [•, •, •, •] denotes the cross-ratio and the (λ i ) 1 i 4 are fixed distinct integers chosen so that these polynomials are pairwise coprime mod p. Although we did mention that the resolvent R 4 (x) is horribly expensive to compute, computing these factors is much easier, for three reasons : they are merely factors and so their degree is much smaller, we compute them mod p so the size of their coefficients is no longer a problem, and now we know that Gal(L 0 /Q) = PGL 2 (F ), it is rigorous to compute them by expanding the product that defines them instead of using resultants. Then, since the action of PGL 2 (F ) on P 1 (F ) is 3-transitive, we may index 3 distinct arbitrarily chosen points z ∞ , z 0 and z 1 of Z 0 respectively by ∞, 0 and 1, after what we index each remaining point z ∈ Z 0 by the unique

P ∈ P 1 (F ) such that R P (λ 1 z ∞ + λ 2 z 0 + λ 3 z 1 + λ 4 z) = 0.
Next, by looking at how the Frobenius of K r permutes Z 0 , we may deduce which element Φ ∈ PGL 2 (F ) it corresponds to. Let now z = z (r) ∈ Z r be a fixed root of F r (x) in K r . By finding which other point of Z r must be added to it to get a root z (r-1) of F r-1 (x) mod p, then which point of Z r-1 must be added to this new root to get a root z (r-2) of F r-2 (x) mod p, and so on until we get to z (0) ∈ Z 0 , we can determine which point P of P 1 (F ) corresponds to z. We index this z by a vector v of V r whose reduction to P 1 (F ) is P . Now that we have indexed one root of F r (x), we index the other ones as follows: Let Φ be an arbitrary lift of Φ ∈ PGL 2 (F ) to GL 2 (F )/S r . We know that the Frobenius of K r acts as λΦ for some λ ∈ F * /S r . If we knew the value of λ, we would be able to complete the indexation of Z r by V r , since z p j must be indexed by (λΦ) j v for all j < 2 r ( + 1). Each value of λ thus corresponds to a candidate indexation of Z r by V r . In order to find out which is the correct one, we use the Dokchitsers' resolvents Γ C (x), albeit in an unusual way : we lift the elements of Z r to some moderate p-adic precision in Q p [t]/F r (t), and we compute one coefficient of one of the resolvents Γ C (x) for each of these candidate indexations. The point is that we expect the correct indexation to yield a nice value, and the other ones to yield rubbish. Curiously, the wrong indexations yield values which are still rational over 19 Q p ; however, in practice they will contradict archimedian bounds which can be derived from the modulus of the complex roots of F r (x), and so we can rigorously tell the right indexation apart from the wrong ones.

Remark 17. Let Γ C (x) = σ∈C x -z∈Zr σ(z)h(z) be the resolvent whose coefficient we compute, where h(x) ∈ Z[x] and C is a conjugacy class, and let n = #C be its degree. Clearly, the coefficients of x n , of x n-1 and of x 0 do not depend on the indexation and therefore give no information. Besides, in practice the height of the coefficient of x n-i is a roughly increasing function of i, so a good choice is to compute the coefficient of x n-2 , which can be done quickly by expanding the product to order 2 at infinity. Remark 18. If r is large, it may be better to determine the image of the Frobenius in GL 2 (F )/S i inductively on i = 1, • • • , r, since this reduces the number of trials to perform from 2 r to 2r. On the other hand, in practice r is small (recall that 2 r < ), so one may parallelise and treat all of the 2 r cases at once if one has enough cores to spare.

Remark 19. If we have some information about the trace or the determinant of the image by ρ of the Frobenius at p, we can make a partial prediction on which indexation is the correct one. However, we have not proved yet that the Galois-set Z r affords ρSr and not another Galois representation, so to be rigorous we must try out all the possibilities. Once we know the correct indexation of Z r , we may compute the Dokchitsers' resolvents Γ C (x) by lifting p-adically the roots into Z r . Indeed, we can deduce a bound on the necessary p-adic precision from archimedian bounds as above. We thus get a completely proved output.

Certification of the representation

Either by the geometric approach (section 3.5) or by the group cohomology one (section 3.6), we have now certified that the Galois action on the set Z r of roots of F r (x) affords a quotient Galois representation ρ Sr , for which we are able to compute the image of the Frobenius element at v for almost every prime v ∈ N thanks to the Dokchitsers' resolvents Γ C (x). We are now going to explain how to certify that this representation ρ Sr is equivalent to the expected representation ρSr .

By assumption, ρ Sr and ρSr induce the same projective representation, so there exists a Galois character

ψ : Gal(Q/Q) -→ F * /S r Z/2 r Z
19 This fact can be proved by a painful computation which we do not reproduce here.

such that ρ Sr = ρSr ⊗ ψ. Let (p j ) j∈J be the primes at which K r ramifies. Since we expect ρ Sr to be equivalent to ρSr , these should be the same primes as the (known) ones at which ρSr ramifies, and we assume that it is indeed the case. For each j ∈ J, let

a j = r + 2 if p j = 2, 1 else, so that Z * p j ⊗ Z/2 r Z (Z/p a j j Z) * ⊗ Z/2 r
Z for all j ∈ J. Since ψ is unramified outside the p j and assumes values in Z/2 r Z, it factors through Gal Q(µ N )/Q , where N = j∈J p a j j . It then suffices to find primes v ∈ N

• which span (Z/N Z) * ⊗ Z/2 r Z,

• for which the Dokchitser resolvents can 20 determine the trace in F /S r of the image by ρ Sr of the Frobenius at v,

• such that this trace is nonzero,

• and which are small enough so that we can determine the trace of the image by ρ of the Frobenius at v (for instance, if ρ = ρf,l , we can compute the coefficients a v (f ) mod l using methods based on modular symbols).

If for each of these v the trace is the same for ρ Sr and ρSr , this proves that ψ is trivial, so that ρ Sr is equivalent to ρSr .

Remark 20. In particular, it then follows that the splitting field L r of F r (x) is indeed the field Lr cut out by ρSr . Besides, since the Galois representation ρ can be recovered from its quotient ρSr and its determinant character det ρ, the field L cut out by ρ is the compositum of L r and of the field cut out by det ρ, which is by assumption a subfield of the cyclotomic field Q(µ ). Using the [Pari/GP] functions polsubcyclo and polcompositum to compute explicitly this latter field and then its compositum with L r , we can thus easily compute a nice monic polynomial in Z[x] whose splitting field is L. This is useful since, as explained in section 2, the polynomial F (x) ∈ Q[x] of degree 2 -1 computed by the algorithm described in [START_REF] Mascot | Computing modular Galois representations[END_REF] is usually too big to be reduced directly. 20 There are at most finitely many exceptions.

Application

Let R be the set of couples (f, l), where l a prime ideal of degree 1 of the Hecke field21 of f lying above a prime number 31, and f ∈ S k (1) a newform of level N = 1 and weight k < , and let R R be the subset formed by the couples (f, l) such that the Galois representation ρf,l attached to f mod l is not exceptional22 .

For each (f, l) in R , we have used the algorithm described in [START_REF] Mascot | Computing modular Galois representations[END_REF] to compute a polynomial F (x) ∈ Q[x] supposedly attached to ρf,l . For = 17, we have then reduced each of these data by the method presented in section 2, thus getting a collection of polynomials F i (x) ∈ Z[x], 0 i r = ord 2 ( -1), and we have applied the group cohomology method described in sections 3.3.1 and 3.6 to certify that these data do define the correct Galois representations. We have finally computed the Dokchitsers' resolvents corresponding to these representations, and we have used them to determine the image in GL 2 (F l ) (up to similarity of course) of the Frobenius at p by each of these representations for the 40 first primes p ∈ N above 10 1000 , so as to illustrate the fact that huge values of p are not a problem for our algorithm. In particular, we have determined the value of a p (f ) mod l for such p. All of these certified data (the reduced polynomials F i (x) with their ordered roots, the Dokchitser's resolvents, and the tables of images of Frobenius elements) may be found on the author's webpage.

Remark 21. In [START_REF] Mascot | Computing modular Galois representations[END_REF], we noted that it took [SAGE] about 30 minutes of CPU time to compute one coefficient a p mod l for p ≈ 10 1000 via our Galois representation data. As we reran the computations with the certified resolvents, we realised that [Pari/GP] can do the same thing in less than 1 minute. The reason for this is that [SAGE] takes the time to check rigorously that p is prime before starting computations mod p, whereas [Pari/GP] does not. Amusingly, this shows that it takes much more time to find a prime number p of this size than to compute a p mod l by the Galois representation method.

We have certified that the 40 values of p used in the tables below are indeed prime, because we are not sure what would happen if we ran our algorithm with a composite pseudoprime. As a result, the values of a p mod l displayed in these tables are completely rigorous.

In order to give an idea of the size of the objects that our algorithms manipulate, we present here two cases extracted from the aforementioned tables. Instead of representing a similarity class in GL 2 (F l ) by a matrix as we did in [START_REF] Mascot | Computing modular Galois representations[END_REF], we deemed it more elegant to give its minimal polynomial in factored form over F l . Since GL 2 (F ) splits into similarity classes as follows, this is a faithful representation.

Type of class

Representative Minimal polynomial # of classes # of elements in class

Scalar λ 0 0 λ x -λ -1 1 Split semisimple λ 0 0 µ (x -λ)(x -µ) ( -1)( -2) 2 ( + 1) Non-split semisimple 0 -n 1 t x 2 -tx + n irreducible over F ( -1) 2 ( -1) Non-semisimple λ 1 0 λ (x -λ) 2 -1 ( + 1)( -1)
The images of the Frobenius elements are the following: Example 2: f 24 mod 31.

For the second example, we pick f = f 24 = q + 24(22 + α)q 2 + 36(4731 -32α)q 3 + O(q 4 ), the unique (up to Galois conjugacy) newform of level 1 and of weight 24, because it is the one of lowest weight whose Hecke field is strictly larger than Q. More precisely, the Hecke field of f 24 is the real quadratic field Q(α), α = 1+ √ 144169 2

. Its ring of integers is Z[α].

In this field, the prime 31 splits into (31) = l 5 l 27 , where l 5 = (31, α -5) and l 27 = (31, α -27). Instead of presenting the results for the Galois representations attached to f 24 modulo l 5 and l 27 separately, it is more interesting to present them together, since we can then compute the coefficients τ 24 (p) mod 31Z[α] by putting together the information coming from both representations and using Chinese remainders. This is what we do in the table below.

Since = 31, we have r = 1. The polynomial F r (x) corresponding to ρf 24 ,l 5 is

F 1 (x) =

3. 3 . 1

 31 Certification of the Galois group of F 0 (x)

  proposition 2.1.1.(ii)]), and for each central extension G of G by M , the subgroup M ∩ D G of G is isomorphic to the image of Tra β , where β ∈ H 2 (G, M ) is the cohomology class corresponding to G, and D G denotes the commutator subgroup of G (cf. [Kar87, proposition 2.1.7]).Applying this to the group G = PGL 2 (F ) and the trivial G-module M = C 2 i yields the following result (cf.[START_REF] Quer | Liftings of projective 2-dimensional Galois representations and embedding problems[END_REF]):

  x 64 -26 x 63 + 138 x 62 + 2883 x 61 -50530 x 60 + 284952 x 59 + 1532392 x 58 -42378023 x 57 + 313778342 x 56 -30967109 x 55 -15952723659 x 54 + 120293225685 x 53 -294956419293 x 52 -2450725406897 x 51 + 28694976228508 x 50 -82028806284207 x 49 -33797566443141 x 48 + 30936396673955 x 47 -25385922046683633 x 46 + 285017809626505879 x 45 -101340567457478942 x 44 -5967948306452799555 x 43 + 18835587705819950118 x 42 -144943245205521339710 x 41 + 602219044044458739742 x 40 +2200535330299713709469 x 39 -16686864181478594950667 x 38 + 107977341642646415867192 x 37 -475668786864492416295472 x 36 -225298037681795144992586 x 35 + 13039469950621100673089867 x 34 -37880916977102172639162818 x 33 +23877972000622578505000183 x 32 -379716355409906474595592883 x 31 -358561841745924661422683747 x 30 +21467502653993360143238405812 x 29 -62531950374059451763223031677 x 28 -141363172107640187136259273515 x 27 +920893472769088633347279277260 x 26 -764513501934547521440643050277 x 25 -2227564891412996848197832943852 x 24 +471803614818821627606852431704 x 23 -6403474778189117882143498765256 x 22 + 128945287900586639765937294055323 x 21 -267130197468879823675069343083282 x 20 -609942322537763774798637252351357 x 19 + 2843848149794156824379251546718928 x 18 -1449008974308249876681217755422392 x 17 -8609964732085444739115712428740443 x 16 + 11462233793731819908607681612424601 x 15 +16721010272893391334932201233417682 x 14 -29850257116492845020236438390839168 x 13 -85528053082348511322543845120538291 x 12 +288505635781109866818884753868632113 x 11 -35293229333983240796518647599225700 x 10 -1277262158496478519737058759156656914 x 9 +1834010042289159626253642058051818796 x 8 + 1354316757902805387817418179095807350 x 7 -4163881920776421128809003897947900249 x 6 +988630283825310945520835533908582035 x 5 + 2040826308855028479392640356469898542 x 4 -781074320529157534608502496794137429 x 3 +709576849443416690978774803765082127 x 2 -1543465475906955668641522308642611594 x + 688413259803358313348163539065291572, and the one corresponding to ρf 24 ,l 27 is F 1 (x) = x 64 -13 x 63 -12 x 62 + 1798 x 61 -2480 x 60 -301351 x 59 + 2427920 x 58 + 3549779 x 57 -128622131 x 56 -605195516 x 55 +18083445605 x 54 -76623104240 x 53 -136111338385 x 52 + 163365709662 x 51 + 36207027735933 x 50 -333393729013025 x 49 +1353870749023624 x 48 -4874235588482263 x 47 + 57952977575049072 x 46 -607896973953769424 x 45 + 3885848486411353707 x 44 -19706433793139872315 x 43 + 120488579146025627521 x 42 -883909787742651393957 x 41 + 5725316882860134327765 x 40 -30772173337138099500438 x 39 + 159943917207673058062651 x 38 -902780142644635221738911 x 37 + 5191270923286965360402518 x 36 -27218300530032866515284399 x 35 + 131834043223355056977306359 x 34 -634566137578102285193778876 x 33 +3121681910932332495500670500 x 32 -14916061491879244185623832302 x 31 + 66502847707000774372555381722 x 30 -280063144491158854648848327512 x 29 + 1151797920191329188089219069705 x 28 -4647562082419563017250271030629 x 27 +17964227685904653209413452332198 x 26 -65006898495556449638155640530135 x 25 + 220529771543741523242617521771165 x 24 -708030865546251742399340304689884 x 23 + 2183095437906409520271539169052977 x 22 -6466045440189753384271760806624755 x 21 +18519022770605982324844617113128582 x 20 -50903095666736365236595239907177352 x 19 + 135712299725345417719982183578217245 x 18 -349024414927084414313298879270239332 x 17 + 879282617681138593506051646342160011 x 16 -2128887636785999977543247137539912626 x 15 +4959567391946018954079733252123119870 x 14 -10698310092805038208309504750205888318 x 13 + 21185126053660446928251211870565927064 x 12 -37034974052822943124568751376502208132 x 11 + 57682303937811470679764738932557333147 x 10 -77659172323156765855997312303575730246 x 9 +91059874206416211006654087253008834453 x 8 -92285656456264804316815032164880452414 x 7 + 79794573183910939847907389673931597531 x 6 -60780767548452665962995019987085052653 x 5 + 37996038264233396745310228794005562702 x 4 -20277402785975735994777964167007154402 x 3 +7574966450629297705011250772005345004 x 2 -1351637429742600734951332369647381173 x + 193569924383211730931468549048466113. The images of the Frobenius elements are the following: p ρf 24 ,l 5 (Frob p ) ρf 24 ,l 27 (Frob p ) a(f 24 , p) mod 31Z[α]

	10 1000 + 453	x 2 + 26x + 21	(x -20)(x -15)	1 + 7α
	10 1000 + 1357	(x -18)(x -3)	(x -25)(x -22)	1 + 4α
	10 1000 + 2713	(x -24)(x -2)	(x -29)(x -7)	4 + 23α
	10 1000 + 4351	(x -17)(x -13)	(x -11)(x -6)	9 + 29α
	10 1000 + 5733	(x -19)(x -12)	(x -15)(x -9)	3 + 18α
	10 1000 + 7383	x 2 + 4x + 14	(x -7)(x -2)	17 + 2α
	10 1000 + 10401	(x -22)(x -5)	x 2 + 24x + 17	9 + 16α
	10 1000 + 11979	x 2 + 17x + 7	x 2 + 19x + 7	6 + 14α
	10 1000 + 17557	(x -26)(x -24)	(x -17)(x -13)	1 + 16α
	10 1000 + 21567	x 2 + 6x + 29	x 2 + 2x + 29	10 + 3α
	10 1000 + 22273	x 2 + 10x + 19	(x -16)(x -7)	29 + 17α
	10 1000 + 24493	(x -22)(x -12)	(x -25)(x -18)	8 + 30α
	10 1000 + 25947	(x -15)(x -12)	(x -24)(x -23)	14 + 15α
	10 1000 + 27057	x 2 + 10x + 30	(x -26)(x -25)	17 + 7α
	10 1000 + 29737	x 2 + 3x + 24	x 2 + 13x + 24	19 + 8α
	10 1000 + 41599	x 2 + 11x + 8	x 2 + 27x + 8	18 + 19α
	10 1000 + 43789	x 2 + 14x + 3	x 2 + 7x + 3	14 + 13α
	10 1000 + 46227	x 2 + 15x + 12	x 2 + 4x + 12	29 + 16α
	10 1000 + 46339	(x -24)(x -9)	x 2 + 5x + 30	5 + 18α
	10 1000 + 52423	(x -10)(x -1)	x 2 + 16x + 10	27 + 3α
	10 1000 + 55831	x 2 + 7x + 25	(x -28)(x -2)	17 + 20α
	10 1000 + 57867	x 2 + 12x + 6	x 2 + 6x + 6	12 + 20α
	10 1000 + 59743	x 2 + 16x + 12	(x -21)(x -5)	28 + 16α
	10 1000 + 61053	(x -18)(x -16)	x 2 + 15x + 9	24 + 2α
	10 1000 + 61353	(x -26)(x -13)	x 2 + 30x + 28	11 + 18α
	10 1000 + 63729	x 2 + 4x + 23	(x -18)(x -3)	3 + 11α
	10 1000 + 64047	(x -19)(x -3)	(x -13)(x -2)	25 + 18α
	10 1000 + 64749	(x -13)(x -10)	(x -17)(x -4)	15 + 14α
	10 1000 + 68139	x 2 + 2x + 26	(x -19)(x -3)	1 + 18α
	10 1000 + 68367	(x -22)(x -2)	x 2 + 21x + 13	30 + 5α
	10 1000 + 70897	x 2 + 8x + 25	(x -26) 2	15 + 14α
	10 1000 + 72237	(x -11)(x -2)	(x -12)(x -7)	6 + 20α
	10 1000 + 77611	x 2 + 5x + 15	x 2 + 28x + 15	27 + 6α
	10 1000 + 78199	(x -30)(x -28)	(x -25)(x -15)	17 + 2α
	10 1000 + 79237	x 2 + 10x + 26	(x -27)(x -9)	19 + 19α
	10 1000 + 79767	(x -15)(x -6)	(x -7)(x -4)	12 + 8α
	10 1000 + 82767	(x -13)(x -3)	(x -24)(x -21)	8 + 14α
	10 1000 + 93559	(x -15)(x -10)	x 2 + 8x + 26	17 + 14α
	10 1000 + 95107	(x -28)(x -20)	(x -18)(x -7)	18 + 6α
	10 1000 + 100003	x 2 + 21x + 8	(x -10)(x -7)	7 + 13α

According to Maeda's conjecture (cf[START_REF] Farmer | The irreducibility of some level 1 Hecke polynomials[END_REF]), there are only 6 such forms, namely ∆, E 4 ∆, E 6 ∆, E 8 ∆, E 10 ∆ and E 14 ∆, of respective weights 12, 16, 18,

20, 22 and 26.

In practice, the case K i+1 Q √ δ i has never happened to us. Should it happen, it can be corrected by multiplying δ i by the square of an (hopefully small) element in K i .

Here and in what follows, by rigorously we mean by the use of exact methods such as resultants, as opposed to the expansion of the product over a non-exact field followed by the identification of the coefficients as elements of Z or Q.

Here and in what follows, by compatible we mean compatible with the natural projections from objects at level i + 1 to objects at level i.

We have k = F in mind, but we would like to make general statements.

This is because j(λ) is the j-invariant of the Legendre curve y 2 = x(x -1)(x -λ), so that the map j we define is the projection from the modular curve X(2) (identified to the λ-line via Legendre curves) to X(1) (identified to the j-line), and because H is the Galois group of the covering X(2) -→ X(1) under these identifications. The author thanks S. Siksek for bringing this to his attention.

Such a prime should exist and should not be too hard to come by, as a non-negligible proportion ϕ( +1) 2( +1) , to be precise of elements of PGL 2 (F ) act as ( + 1)-cycles on P 1 (F ).

Note that as every automorphism of PGL 2 (F ) is inner, our isomorphism must be the "right" one.

This is where we need the hypothesis that det ρ is a power of the mod cyclotomic character for our approach to have a chance to work.

In principle one may directly factor over Q[x]/R(x 2 ) the minimal polynomial of a primitive element of κ j+1 , but this would involve performing arithmetic in Q[x]/R(x 2 ) and in particular to compute an integral basis thereof, which is much slower than working over κ j+1 .

Although we certainly have such projections maps in characteristic zero, it might happen that these maps are not well-defined anymore in characteristic p. However, as p is large, this problem should not occur for us.

Indeed, unlike K r , M is an extension of F p of degree + 1 = deg F 0 (x). To make things worse, curiously Magma does not construct M as F p [t]/F 0 (t) but as F p [t]/G(t) instead, where G(t) is a sparse polynomial of degree + 1 which it cooks up.

By Hecke field of a newform, we mean the number field generated by its Fourier coefficients.

So we exclude precisely ∆ mod

and E 4 ∆ mod 31.

Acknowledgements

The computations presented here would not have been amenable without Bill Allombert, who suggested to me the idea of step-by-step polynomial reduction, and Karim Belabas and Denis Simon, who provided me their [BS14]

, which have helped me to make this article clearer.

This research was supported by the French ANR-12-BS01-0010-01 through the project PEACE, by the DGA maîtrise de l'information, and by the EPSRC Programme Grant EP/K034383/1 "LMF: L-Functions and Modular Forms".

The computations presented in this paper were partly carried out using the PlaFRIM experimental testbed, being developed under the Inria PlaFRIM development action with support from LABRI and IMB and other entities: Conseil Régional d'Aquitaine, FeDER, Université de Bordeaux and CNRS (see https://plafrim.bordeaux.inria.fr/), and partly on the Warwick mathematics institute computer cluster provided by the aforementioned EPSRC grant. The computer algebra packages used were [SAGE], [Pari/GP] and [Magma]. 2010

Example 1: ∆ mod 29.

It seems natural to start with an example with f = ∆ = q -24q 2 +252q 3 +O(q 4 ), the most famous cuspform of all. While for = 31 we have r = 1, for = 29 we have r = 2, so the polynomials F r (x) are more impressive for = 29 than for = 31. Here is the one corresponding to ∆ mod 29:

39 x 119 + 52 x 118 + 18802 x 117 -260738 x 116 -2224996 x 115 + 78123651 x 114 -328828100 x 113 -8263917952 x 112 +105418992285 x 111 -9281370047 x 110 -8673650394390 x 109 + 67175813321912 x 108 + 3240223696313 x 107 -3625273840703346 x 106 +28868328866222299 x 105 -55712181926653112 x 104 -831213186859484809 x 103 + 6400389530587512440 x 102 + 5664948473704761298 x 101 -236599099025809755837 x 100 -86149046526574607141 x 99 + 18049361157398735512827 x 98 -143034171738473324654141 x 97 +309908279927036114408948 x 96 + 4110452935977502930211262 x 95 -49808587507684086841613272 x 94 + 255718390797761218980112249 x 93 -370938232422515550238030706 x 92 -4239746526064029063336974560 x 91 + 40059260137839079990324735682 x 90 -205134100035408647490709294925 x 89 + 690810959665321724654129463170 x 88 -1150913531696070804731460240641 x 87 -2905017526953691499670077418670 x 86 + 47322659102097465506352390635856 x 85 -425792292478079616843046706314083 x 84 +2739838234183913689504417826249525 x 83 -12377247662589064428784865815958075 x 82 + 41296251300763242911291874924492236 x 81 -86096254481992808573240127681847534 x 80 -174161987438617330069511957454948216 x 79 + 3004945442865208465399646864785306007 x 78 -19426609866780659578962841182962714865 x 77 + 108199453121858544562274337695731535951 x 76 -540562354485415170568171856724347249028 x 75 + 2003170329279473549264139360014033008269 x 74 -4906345350745852789161273456858421483526 x 73 + 6852101959985515455407213317694533880854 x 72 +21744835456542777978544010432017957570998 x 71 -354531601960104186814288045752985534837356 x 70 +2415813767710375355007174048785369337370619 x 69 -11795476320637187447112847890157256430641818 x 68 +51949786215458201865850168647651038718083533 x 67 -205837760707652251236618469331715307953868772 x 66 +632794675891664554262532875475585224624885501 x 65 -1549984687081576409789267803107087061300626754 x 64 +3780171680443736629265587788531817043101358021 x 63 -2032042888653854240770004273667014042737914619 x 62 -75296586398944854033134144067268466018165634371 x 61 + 492438774401604429008913700838759413140834029077 x 60 -1872146628576921265301617989405459118651511828249 x 59 + 7889534315510055163849348514205854835317146183354 x 58 -37623219532998612719188117562544690312647851443329 x 57 + 133715149099087666221878622209330023885832980173762 x 56 -358527853259357643101016413194439711168998587653646 x 55 + 1150214873720403752145704516777301458540259708566007 x 54 -4251058748128336628769990060481020773188738825695702 x 53 + 10642612653109338583300281664637819808188791020684468 x 52 -17402914533613728148979826342208602338942607463119246 x 51 + 48633429629872181118699939461795124668503022992755678 x 50 -165403276792631997282371651395087674782654230366714124 x 49 + 145015997107909021398686766742679587247121061293408986 x 48 +492392849280060573773565340461610525259317147507294865 x 47 -271511458296438382488111693610775002497465128417170394 x 46 -652664619248620330391026643444817961046333282136405757 x 45 -16367594587199289948998686451709338569385261309703750822 x 44 +44978511235283376299343780035953332879799842232519914312 x 43 + 19646073668559858224023650929822622112934080573795228422 x 42 +28535167429260816202303363626597519751307292203748180524 x 41 -498090822280959521158336743012213915583277009997639543769 x 40 -940364373679220067932549479979755134636234011579427914542 x 39 + 2521673052520748698612222377227238872725904760567919548740 x 38 +7019283132304011272238795849686785307621156377148940945457 x 37 + 12407898598890801572422838737227607844456571501921254925864 x 36 -54774940542932812395031549315157134292675987516857162936933 x 35 -167280160291743112243902528169268456978957939558833200506384 x 34 +66685231231069675353959106828906025058508433889848745908446 x 33 +1144200200071295796141746982232629332102662041133194625544527 x 32 +1465380778516325802890225143289120143844003938597799565942015 x 31 -4546042233752493082553255798793744033071375504699352571051582 x 30 -12691048529690820177670723551290387902258432599474582511011324 x 29 +5219645215184371778852291796118549498037264765670011997356903 x 28 +59536146913870227752311679132874695245690076312069901091973737 x 27 +42271202746576508837242051054585488179771161211530729060009727 x 26 -167593661120219565661536403962471583120422676161951086004048721 x 25 -286368937487543599711899983016552475758462484909274064469481002 x 24 +230382055771017547055677721234005290186180568652972820922049224 x 23 +928283302209877157721534651901436783095651772196213609374878685 x 22 +175585932223464736559299592405845533688516285207784943808278420 x 21 -1758850016954365463305055994507463367031764582472365647306994534 x 20 -1465327287102397863683326389027330201118347359802335300172559328 x 19 +1773321220836307165702143644634692168610741013365613960356877087 x 18 +2904606733860530703041514422127534636066546248303444459223252869 x 17 -520308669130339394544399063835249522615387011157258025834606131 x 16 -2906947132318789204808524108533368321356173905644648961284835769 x 15 -393534993004425879883701416875089550520476893473247289746770881 x 14 +2113255440095432232134067491875625170919662276031515339003865608 x 13 +343521455053064377858576614861077606598382997902674984475727361 x 12 -1980733816420089301985076580314504281378403676364093859856750280 x 11 -841423938599508546949037276545037161554893873562770775547347936 x 10 +1511611164721597762311281100747394082476044535180259343320913007 x 9 +1865894071033615040665160647561792975872738246766682774064852296 x 8 +887398778985804089226899981553259732564931621689808536397397622 x 7 +327959598838061445269659568556871680486016836452609211222699063 x 6 +280807031529596339466111600718026859424625249954985059771350709 x 5 +234434262697623313809637590557065036950844063730534986852355367 x 4 +128418383859788691330267355023441549682203671844754849186711248 x 3 +47862235923713816575492173460515921299171434171423149409051143 x 2 +7941532444376844604785215172809295246343317508709928231445127 x -804139180569965777035407848426442222962300357108066928039835.

We first prove that Gal(L i /Q) is an extension of PGL 2 (F ) by C 2 i . Let 1 i < r. By induction hypothesis, we have a commutative diagram

whose middle row and right column are exact. A diagram chase then reveals that the top row and the diagonal short sequence

, so the extensions of C 2 i by C 2 are all Abelian by the exact sequence ( ), so that q -1 (C

We shall now prove that the latter is impossible.

Since ≡ 1 mod 4, the group S 2 1 = F * 4 is a strict subgroup of S 1 = F * 2 . The determinant induces a surjective morphism

so that L 1 has a C 4 -subfield, which can only be field κ 2 ⊂ Q(µ ) according to (A1).