Sharedwww / tables / model.gpOpen in CoCalc
Author: William A. Stein
1\\ model.gp -- find models for modular curves.
2\\
3\\ As usual, it is assumed that a matrix E of new eigenforms exists
4\\ on the PARI stack before this program is run.
5\\ The format of E is
6\\     E[N,i] = [f(x), [a1(x), a2(x), ..., an(x)]].
7\\ where each ai is a polynomial in Q[x] of deg < d = deg f
8\\ and f is an irreducible polynomial in Z[x].  The ai
9\\ should be thought of as expressions in a root of f,
10\\ and we assume that they are integral over Z.
11\\
12\\ bg.gp is assumed "available".
13\\
14\\ William A. Stein ([email protected]), Nov 12, 1998.
15
16{nrows(M)=matsize(M)[1];}
17{ncols(M)=matsize(M)[2];}
18{find(v,a,i=0)=for(i=1,ncols(v),if(v[i]==a,return(i)));return(0);}
19
20\\ intbasis1: -- int basis for space spanned by a single conjugacy class.
21\\ INPUT  : N,i which defines an E[N,i] = [f,[a1,...,an]]
22\\ OUTPUT : vector of q-expansions.
23{intbasisclass(N,i,
24  M,K,v,j,k)=
25  K=nfinit(E[N,i][1]);
26  M=matrix(poldegree(E[N,i][1]),ncols(E[N,i][2]),j,k,0);
27  for(j=1,ncols(E[N,i][2]),M[,j]=nfalgtobasis(K,E[N,i][2][j]));
28  vector(nrows(M),j,sum(k=1,ncols(M),M[j,k]*q^k)+O(q^(ncols(M)+1)));
29}
30
31{intbasisnew(N,
32  i,j,k,n,last,v,w)=
33  print1("Integral basis of newforms at level ", N);
34  n=0;last=0;
35\\  if(nrows(E)<N,print("Need data for level ",N," to proceed!"); return(););
36  for(i=1,ncols(E),
37    if(E[N,i]!=0,
38      n+=poldegree(E[N,i][1]),last=i-1;break())
39  );
40\\  if(n==0,print("Need data for level ",N," to proceed!"); return(););
41  v=vector(n,i,0);
42  j=1;
43  for(i=1,last,
44    w=intbasisclass(N,i);
45    for(k=1,ncols(w), v[j]=w[k]; j++)
46  );
47  print(" -- ",ncols(v)," newforms.");
48  v;
49}
50
51
52\\ intbasis:
53\\ Find a Q-basis for S_2(Gamma_0(N)) consisting of forms with q-expansion
54\\ coefficients in Z.
55
56{intbasis(N,
57  fac,i,j,k,l,m,v,d,t,Snew)=
58  fac=factor(N);
59  v=vector(nrows(fac)*N*20,i,0);   \\ way over estimate.
60  j=1;
61  fordiv(N,d,
62    Snew=intbasisnew(N/d);
63    fordiv(d,t,
64      for(k=1,ncols(Snew),v[j]=subst(Snew[k],q,q^t);j++);
65    );
66  );
67  print("Finished computing integral basis at level ",N," dim = ", j-1);
68  vector(j-1,i,v[i]);               \\ truncate away extra zeros.
69}
70
71
72\\ reducedintbasis:
73\\ Compute a "reduced" integral basis for S_2(Gamma_0(N)),
74\\ that is a Z-basis for the free abelian group of modular forms
75\\ whose q-expansion coefficients lie in Z.
76
77\\ save for later -- not sure how to do this in pari.
78
79\\    if(sum(i=1,s,e[i])==d,  \\ monomial of degree d,
80
81\\ monomials
82\\ returns list of exponents of monomials of degree d in s variables.
83{monomials(s,d,
84  v,w,i,j,k,n) =
85  if(s<1||d<1,return([]));
86  if(s+d-1==d,v=vector(1,i,0),       \\ bug in PARI binomial function.
87    v = vector(binomial(s+d-1,d),i,vector(s,n,d)));
88  k=1;
89  v[k]=vector(s,n,if(n==1,d,0)); k++;
90  for(i=0,d,
91    w = monomials(s-1,d-i);
92    for(j=1,ncols(w),v[k]=vector(s,n,if(n==1,i,w[j][n-1]));k++)
93  );
94  v;
95}
96
97\\ findrels:
98\\ This function finds all linear degree d relations satisfied by a
99\\ a list {f1, ..., fs} of power series.
100\\
101\\ INPUT:  * A list f1,...,fs of q-expansions a1*q+a2*q^2+...+O(q^(prec+1)).
102\\         * An integer n.
103\\         * prec = precision of the fi's.
104\\
105\\ OUTPUT: * A matrix of integers.  The rows of the matrix represent
106\\           linear relations satisfied by f1^d, f1^{d-1}f2, ..., fs^d.
107\\           The rows are linear independent.
108\\
109\\ AUTHOR:  William Stein ([email protected]), Nov 1998.
110
111{findrelmat(v, d, prec,
112   M, i, j, k, mon, g) =
113  \\ A: construct M.
114  \\    iterate through the set of monomials in s variables of degree d.
115  print("Computing monomials of degree ", d,".");
116  mon = monomials(ncols(v),d);
117\\  prec=poldegree(truncate(v[1]));
118\\  for(i=2,ncols(v),prec=min(prec,poldegree(truncate(v[i]))));
119  print("Building ", prec,"x", ncols(mon),
120        " matrix of monials in modular forms.");
121  M = matrix(prec,ncols(mon),i,k,0);
122  j=1;
123  for(i=1,ncols(mon),
124    g = 1;
125    for(k=1,ncols(v),
126      g*=(v[k]+O(q^(prec+1)))^mon[i][k]);         \\ g <--  "f1^{e1}*f2^e2*..."
127    for(k=1,prec,
128      M[k,j]=polcoeff(g,k-1));
129    j++;
130  );
131  M;
132}
133
134
135{findrels(v, d, prec,
136    M)=
137  M = findrelmat(v,d,prec);
138  print("Computing LLL reduced relations using matkerint.");
139  R=matkerint(M);    \\ LLL reduced kernel.
140  print("Done computing relations.");
141  R;
142}
143
144
145
146\\ findindeprels:
147\\ Find all _independent_ relations of degree <= d.
148\\
149\\ Method: Compute relations of degree 2.  These automatically give
150\\         rise to several relations of degree 3.  Compute the
151
152
153
154
155{itoa(n)=if(n==1,return("a"));if(n==2,return("b"));if(n==3,return("c"));
156if(n==4,return("d"));if(n==5,return("e"));if(n==6,return("f"));
157if(n==7,return("g"));if(n==8,return("h"));if(n==9,return("i"));if(n==10,return("j"));
158if(n==11,return("k"));if(n==12,return("l"));if(n==13,return("m"));if(n==14,return("n"));
159if(n==15,return("o"));if(n==16,return("p"));if(n==17,return("q"));if(n==18,return("r"));
160if(n==19,return("s"));if(n==20,return("t"));if(n==21,return("u"));if(n==22,return("v"));
161if(n==23,return("w"));if(n==24,return("x"));if(n==25,return("y"));if(n==26,return("z"));
162}
163
164{printbasis(v, prec=10,
165  i)=
166  for(i=1,ncols(v),
167    if(i<=26,print1(itoa(i)),print1("f",i,));
168    print(" = ",v[i]+O(q^prec)));
169}
170
171show_basis(N)=printbasis(intbasis(N),10);
172
173{printmon(mon,
174  i,first)=
175  first=1;
176  for(i=1,ncols(mon),
177    if(mon[i]!=0,
178      if(!first,print1("*"));
179      first=0;
180      if(i<=26,print1(itoa(i)),
181        print1("f",i));
182      if(mon[i]>1,
183        print1("^",mon[i])
184      )
185    );
186  );
187}
188
189{printrel(r, s, d,
190  i, j, k, mon, rel,first) =
191  mon = monomials(s,d);
192  if(nrows(r)==0, print("no relations of degree ", d); return());
193  for(k=1,ncols(r),
194    first=1;
195    for(i=1,ncols(mon),
196      if(r[i,k]!=0,
197        if(!first && r[i,k]>0,print1(" + "));
198        first=0;
199        if(r[i,k]<0, print1(" - "); r[i,k]=-r[i,k]);
200        if(abs(r[i,k])!=1,
201          print1(r[i,k],"*"));
202        printmon(mon[i]);
203      );
204    );
205    print(" = 0");
206  );
207
208}
209
210
211{show_rels(N,d,prec,
212  v,r)=
213  v=intbasis(N);
214  r=findrels(v,d,prec);
215  printrel(r, ncols(v), d);
216}
217
218{initleveldata()=
219E=matrix(400,40,x,y,0);
220print("reading levels to 100");
221read("1-100.gp");
222print("reading levels to 200");
223read("101-200.gp");
224print("reading levels to 300");
225read("201-300.gp");
226\\print("reading levels to 400");
227\\read("301-400.gp");
2280;
229}
230
231
232\\ Let r be a list of relations of degree d.
233\\ This function returns the list of relations of degree d+1 induced by the
234\\ relations r.  For example, if r "is"
235\\        3*a^2+b^2
236\\ Then this function would return the 2 relations
237\\      3*a^3+a*b^2 and 3*a^2*b+b^3
238
239{inducedrels(r,s,d,
240  ind,i,j,k,l,mon_d,mon_dp1,mon,xmon,v)=
241  mon_d = monomials(s,d);      \\ monomials of degree d
242  mon_dp1 = monomials(s,d+1);  \\ monomials of degree d+1.
243  \\ v=vector(ncols(mon_d),i,0);
244  ind=matrix(ncols(mon_dp1),s*ncols(r), i,j,0);
245  j=1;
246  for(i=1,s,
247    for(k=1,ncols(r),
248      for(l=1,nrows(r),
249        if(r[l,k]!=0,
250          mon=mon_d[l];
251          mon[i]++;                \\ multiply by ith variable
252          xmon=find(mon_dp1,mon);  \\ find in the degree d+1 monomial list
253          if(xmon==0,print("inducedrels: ERROR IN PROGRAMMING!"));
254          ind[xmon,j]=r[l,k];
255        );
256      );
257      j++;
258    );
259  );
260  ind;
261}
262
263{numcubicrels(N,
264  g)=
265  g=g0(N);
266  g*(g+7)*(g-4)/6 + 5;
267}
268
269{show_inducedrels(N,d,prec,
270  v,r,r2)=
271  v=intbasis(N);
272  r=findrels(v,d,prec);
273  print("THE DEGREE ", d, " RELATIONS:");
274  printrel(r, ncols(v), d);
275  print("THE INDUCED DEGREE ", d+1, " RELATIONS:");
276  r2=inducedrels(r,ncols(v),d);
277\\  printrel(r2, ncols(v), d+1);
278  print("computing rank of an ",matsize(r2)," matrix");
279  print("THERE RANK OF INDUCED RELS IS ", matrank(r2));
280  print("THE NUMBER OF CUBIC RELS IS   ", numcubicrels(N));
281}
282
283
284print("initleveldata() = load data for levels <= 300");
285print("show_basis(N)   = show Q-basis at level N");
286print("show_rels(N,d,prec) = compute the relations of degree d at level N, ");
287print("                      to precision prec<=500.");
288print("show_inducedrels(N,d,prec) = ");
289
290{systematic(N,
291   m,prec)
292  while(N<=220,
293    prec=floor(mu0(N)/3.0)+15;
294    show_inducedrels(N,2,prec);
295    N+=2;
296  );
297}
298