CoCalc Public Fileswww / tables / magma_src / ModFrm / level1.mOpen with one click!
Author: William A. Stein
1
freeze;
2
3
/****-*-magma-* EXPORT DATE: 2004-03-08 ************************************
4
5
MODFORM: Modular Forms in MAGMA
6
7
William A. Stein
8
9
FILE: level1.m -- tricks for computing with modular forms
10
in the special case of level 1.
11
12
04/06/03: programmed around stupid shortcoming in MAGMA;
13
See comments in EigenvectorOfMatrixWithCharpoly
14
15
$Log: level1.m,v $
16
Revision 1.2 2002/04/25 05:33:51 was
17
some improvements.
18
19
Revision 1.1 2001/05/30 18:55:12 was
20
Initial revision
21
22
Revision 1.1 2001/05/16 03:50:33 was
23
Initial revision
24
25
26
***************************************************************************/
27
28
/* The functions below are used in q-expansions.m and operators.m in the
29
special case of level one to speed things up. */
30
31
32
forward CharpolyModp,
33
CRT_vec,
34
CRT_mat,
35
EigenvectorOfMatrixWithCharpoly,
36
Level1Basis,
37
Level1CharacteristicPolynomialOfTp,
38
LiftToZ,
39
Tp;
40
41
42
function Level1Basis(k, prec)
43
assert Type(k) eq RngIntElt;
44
assert Type(prec) eq RngIntElt;
45
46
if IsOdd(k) or k lt 4 then
47
return [];
48
end if;
49
S := PowerSeriesRing(RationalField());
50
q := S.1;
51
E4 := Eisenstein(4,q+O(q^prec));
52
E6 := Eisenstein(6,q+O(q^prec));
53
54
ab := [<Integers()!((k-6*b)/4),b> : b in [0..Floor(k/6)]
55
| (k-6*b)/4 in Integers()];
56
E4pows := [1, E4];
57
for i in [1..Max([x[1] : x in ab])] do
58
Append(~E4pows, E4pows[#E4pows]*E4);
59
end for;
60
E6pows := [1, E6];
61
for i in [1..Max([x[2] : x in ab])] do
62
Append(~E6pows, E6pows[#E6pows]*E6);
63
end for;
64
65
gens := [E4pows[x[1]+1]*E6pows[x[2]+1] : x in ab];
66
V := VectorSpace(RationalField(),prec);
67
vecs := [V![Coefficient(g,n) : n in [0..prec-1]] : g in gens];
68
W := sub<V|vecs>; // reduced row-echelon form
69
basis := [S!Eltseq(b) + O(q^prec): b in Basis(W)];
70
return basis;
71
end function;
72
73
function Level1CharacteristicPolynomialOfTp(k,p,d,eigen)
74
// The characteristic polynomial of the nth Hecke operator acting
75
// on weight k CUSP FORMS for SL_2(Z).
76
// eigen is an eigenvector of T2 over an extension field, e.g.,
77
// eigen := EigenvectorOfMatrixWithCharpoly(T2, f2) where f2 is
78
// the charpoly of T2.
79
80
assert Type(k) eq RngIntElt;
81
assert Type(p) eq RngIntElt;
82
assert Type(d) eq RngIntElt;
83
assert k ge 2;
84
assert p gt 2 and p le d ;
85
// assert IsPrime(p);
86
87
/*
88
vprint ModularForms, 2: "First computing characteristic polynomial of T_2 using standard algorithm.";
89
t := Cputime();
90
f := CharacteristicPolynomial(T2 :
91
Proof := false, Al := "Modular");
92
vprintf ModularForms, 2: "Time = %o seconds\n", Cputime(t);
93
*/
94
95
N := 1;
96
ell := 17;
97
t := 1;
98
M := [* *];
99
100
tm := Cputime();
101
while true do
102
f := CharpolyModp(eigen[1],eigen[p],ell);
103
if Type(f) eq RngUPolElt and Degree(f) eq d then
104
Append(~M,Eltseq(f));
105
t +:= 1;
106
if t mod 5 eq 0 then
107
v := CRT_vec(M);
108
if LiftToZ(v) eq LiftToZ(M[1]) then
109
break;
110
end if;
111
M := [* v *];
112
vprintf ModularForms,2: "CRT step: Now ell = %o. (%o seconds elapsed)\n", ell, Cputime(tm);
113
end if;
114
end if;
115
ell := NextPrime(ell);
116
end while;
117
118
return PolynomialRing(Integers())!LiftToZ(v);
119
end function;
120
121
/* The characteristic polynomial of b / a modulo p */
122
function CharpolyModp(a, b, p)
123
assert Type(a) eq RngUPolResElt;
124
assert Type(b) eq RngUPolResElt;
125
assert Type(p) eq RngIntElt and IsPrime(p);
126
127
K := GF(p);
128
R := PolynomialRing(K);
129
S := Parent(a);
130
f := R!Modulus(S);
131
if (Discriminant(f) eq 0) or (Coefficient(f,0) eq 0) then
132
return false;
133
end if;
134
L := quo<R|f>;
135
t, a := IsCoercible(R,(S!a));
136
if not t then
137
return false;
138
end if;
139
amod := L!a;
140
if Coefficient(MinimalPolynomial(amod),0) eq 0 then
141
return false;
142
end if;
143
t, b := IsCoercible(R,(S!b));
144
if not t then
145
return false;
146
end if;
147
bmod := L!b;
148
149
return MinimalPolynomial(bmod/amod);
150
end function;
151
152
function LiftToZ(T)
153
if Type(T) eq AlgMatElt then
154
return MatrixAlgebra(Rationals(),Degree(Parent(T)))!LiftToZ(Eltseq(T));
155
end if;
156
assert Type(T) eq SeqEnum;
157
158
d := #T;
159
N := Characteristic(Parent(T[1]));
160
161
T0 := [];
162
for i in [1..d] do
163
if (Integers()!T[i]) ge N/2 then // or something like this.
164
T0[i] := (Integers()!T[i])-N;
165
else
166
T0[i] := Integers()!T[i];
167
end if;
168
end for;
169
170
return T0;
171
end function;
172
173
174
function CRT_vec(list)
175
// input is a list of vectors of the same degree modulo various primes
176
assert Type(list) eq List;
177
assert #list gt 0;
178
179
d := #list[1];
180
assert d gt 0;
181
M := [Characteristic(Parent(v[1])) : v in list];
182
return [Integers(LCM(M))| CRT([Integers()!v[i] : v in list], M) : i in [1..d] ];
183
end function;
184
185
/*
186
function CRT_mat(M)
187
assert Type(M) eq List;
188
V := [* *];
189
for m in M do
190
Append(~V, Eltseq(m));
191
end for;
192
crt := CRT_vec(V);
193
N := Characteristic(Parent(crt[1]));
194
return MatrixAlgebra(IntegerRing(N),Degree(Parent(M[1])))!crt;
195
end function;
196
*/
197
198
function MatrixAction(v, T)
199
// v is a sequence and T is a matrix and this computes v*T.
200
return [&+[v[i]*T[i,j] : i in [1..#v]] : j in [1..#v]];
201
end function;
202
203
function EigenvectorOfMatrixWithCharpoly(T, f)
204
/* Let T be an nxn matrix over K with irreducible characteristic
205
polynomial f. This function returns an eigenvector for T
206
over the extension field K[x]/(f(x)). */
207
assert Type(T) eq AlgMatElt;
208
assert Type(f) eq RngUPolElt;
209
assert Type(BaseRing(Parent(f))) eq Type(BaseRing(Parent(T)));
210
211
// This is implemented using a quotient of a polynomial ring
212
// because this works generically for any field.
213
n := Degree(f);
214
K := RationalField();
215
if n eq 1 then
216
return VectorSpace(K,n)![1];
217
end if;
218
R<x> := PolynomialRing(K);
219
L<a> := quo<R | f>;
220
if Coefficient(f,0) eq 0 then
221
return false;
222
end if;
223
b := 1/a;
224
c := [-b*Coefficient(f,0)];
225
for i in [1..Degree(f)-1] do
226
Append(~c, (c[i] - Coefficient(f,i))*b);
227
end for;
228
229
/*
230
// this is what we *should* do, because it is sensible.
231
// HOWEVER, it is an example in which MAGMA is *ANNOYING*, in that
232
// creating the RSpace over L can easily take *hours* even though
233
// the rest of the computation takes no time. I think the creation
234
// of the RSpace involves checking whether or not L is a field (we
235
// know it is...), and the irreducibility test in MAGMA isn't good
236
// enough. So we instead fake all this below by working with sequences,
237
// which might seem slower, but is vastly faster since we avoid
238
// the problem of trying to create RSpace(L,n).
239
// An example in which creating this RSpace is VERY hard:
240
// SetVerbose("ModularForms",2);S := CuspForms(1,130);time f := HeckePolynomial(S,3);
241
242
Ln := RSpace(L,n);
243
v := Ln!0;
244
v[Random(1,n)] +:= Random(1,10);
245
v[Random(1,n)] +:= Random(1,10);
246
T := RMatrixSpace(L,n,n)!T;
247
cnt := 0;
248
repeat
249
v[Random(1,n)] +:= 1;
250
w := c[1]*v;
251
vv := v;
252
for i in [2..#c] do
253
vv := vv*T;
254
w +:= c[i]*vv;
255
end for;
256
cnt := cnt + 1;
257
if cnt gt 100 then
258
print "WARNING: EigenvectorOfMatrixWithCharpoly -- algorithm not converging!";
259
end if;
260
until w ne 0;
261
*/
262
263
v := [L!0 : i in [1..n]];
264
v[Random(1,n)] +:= Random(1,10);
265
v[Random(1,n)] +:= Random(1,10);
266
cnt := 0;
267
repeat
268
v[Random(1,n)] +:= 1;
269
w := [c[1]*x : x in v];
270
vv := v;
271
for i in [2..#c] do
272
vv := MatrixAction(vv,T);
273
w := [w[j] + c[i]*vv[j] : j in [1..n]];
274
end for;
275
cnt := cnt + 1;
276
if cnt gt 100 then
277
print "WARNING: EigenvectorOfMatrixWithCharpoly -- algorithm not converging!";
278
end if;
279
until exists(i){w[i] : i in [1..#w] | w[i] ne 0};
280
281
return w;
282
end function;
283
284
285