CoCalc Public Fileswww / tables / modsymold.gp
Author: William A. Stein
1\\ Weight 2 modular symbols in GP/PARI pre 2.0
2\\  (by Joseph L. Wetherell)
3
4
5\\ the M-symbol n(c:d) is represented by [c,d,n]
6
7\\ We identify the symbols (c:d)=(-c:d)=(c:-d)=(-c:-d)
8\\                           = -(d:c) = -(d:-c) = -(-d:c) = -(-d:-c)
9\\ This gives all of the 2-term and neg-eigenspace identities,
10\\ and reduces the size of the spaces.
11{mnormal(cond,v,
12	tmp)=
13  v = lift(v*mod(1,cond));
14  if(v[1]>cond/2, v[1]=cond-v[1] ,);
15  if(v[2]>cond/2, v[2]=cond-v[2] ,);
16  if(v[1]>v[2],   tmp=v[1]; v[1]=v[2]; v[2]=tmp; v[3]=-v[3] ,);
17  v;
18}
19
20{generatemsymbols(cond,
21	num,ret,curn)=
22\\ num = [\Gamma:\Gamma_0(N)] = N * Prod_{p|cond} (1+p^-1)
23  num = cond;
24  v = factor(cond);
25  for(n=1,length(v~),
26    num = num*(1+1/v[n,1]);
27  );
28
29\\ initialize M-symbol list
30  ret = vector(num,c,0);
31  curn = 1;
32
33\\ generate M-symbols in three lists:
34\\ list 1: (c:1) for 0 <= c < N
35  for(c=0, cond-1,
36    ret[curn] = [c,1,1];
37    curn = curn + 1;
38  );
39
40\\ list 2: (1:d) for 0 <= d < N and gcd(d,N)>1
41  for(d=0, cond-1,
42    if(gcd(d,cond)>1,
43      ret[curn] = [1,d,1];
44      curn = curn + 1;
45    ,);
46  );
47
48\\ list 3: (c:d) with c|N, c<>1,N,  gcd(c,d)=1, gcd(d,N)>1
49  v = curn;
50  for(d=2, cond-1,
51    if(gcd(d,cond)>1,
52        fordiv(cond,c,
53          if(c<>1 && c<>cond && gcd(c,d)==1,
54            if(0 == sum(0, n=v,curn-1, ((ret[n][1]*d-c*ret[n][2])%cond)==0 ),
55              ret[curn] = [c,d,1];
56              curn = curn + 1;
57            ,);
58	  ,);
59        );
60    ,);
61  );
62
63\\ normalize all of the m-symbols
64  for(n=1,num,
65    ret[n] = mnormal(cond,ret[n]);
66    ret[n] = ret[n][2]*cond+ret[n][1];
67  );
68\\ remove duplicates
69  ret = set(ret);
70
71  ret = vector(length(ret), n, [ret[n]%cond, ret[n]\cond, 1] );
72  for(n=1,length(ret),
73    while(gcd(ret[n][1],ret[n][2])<>1,
74       ret[n] = ret[n] + [cond,0,0];
75    );
76  );
77  ret;
78}
79
80
81{hashmsymbols(cond,msymbols,
82	ret,tmp) =
83  ret = matrix(cond\2+1,cond\2+1,c1,d1,0);
84  for(n=1,cond-1,
85    if(gcd(n,cond)==1,
86      for(k=1,length(msymbols),
87        tmp = [msymbols[k][1]*n,msymbols[k][2]*n,msymbols[k][3]];
88        tmp = mnormal(cond,tmp);
89        ret[tmp[1]+1,tmp[2]+1] = tmp[3]*k;
90      );
91    ,);
92  );
93  ret;
94}
95
96{dohash(cond,hash,v,
97	tmp)=
98  v=mnormal(cond,v);
99  tmp = hash[v[1]+1,v[2]+1];
100  [abs(tmp), sign(tmp)*v[3]];
101}
102doT1(v) = [v[1]+v[2],v[1],v[3]]
103doT2(v) = [v[2],v[1]+v[2],v[3]]
104
105{msymbolrelations(cond,msymbols,hash,
107        tempr) =
108  nsym  = length(msymbols);
109  relat = idmat(nsym);
111
112  for(n=1,nsym,
113    n1 = msymbols[n];
114    n2 = doT1(msymbols[n]);
115    n3 = doT2(msymbols[n]);
116    n1 = dohash(cond,hash,n1);  s1=n1[2]; n1=n1[1];
117    n2 = dohash(cond,hash,n2);  s2=n2[2]; n2=n2[1];
118    n3 = dohash(cond,hash,n3);  s3=n3[2]; n3=n3[1];
119    r = s1*relat[n1,] + s2*relat[n2,] + s3*relat[n3,];
120    minc = vecmax(abs(r));
121    for(k=1,nsym,
122      if(r[k] && abs(minc)>=abs(r[k]),
123        minc = r[k];
124        mincloc = k;
125      ,);
126    );
127    if(minc,
129      r = r/minc;
130      relat = relat - relat[,mincloc]*r;
131    ,);
132  );
133
135  n2 = set(simplify(n1));
136  freebasis = vector(length(n2)-1,n,n2[n+1]);
137  symtofree = matrix(nsym,length(freebasis),n1,n2,relat[n1,freebasis[n2]]);
138  [freebasis,symtofree~];
139}
140
141cusps;
142{initcusps() = cusps=[];}
143
144{testcuspeq(cond,cusp1,cusp2,
145 	p1,q1,p2,q2,s1,s2,n)=
146  p1 = cusp1[1];
147  q1 = cusp1[2];
148  p2 = cusp2[1];
149  q2 = cusp2[2];
150  s1 = if(q1>2, lift(mod(1/p1,q1)), 1);
151  s2 = if(q2>2, lift(mod(1/p2,q2)), 1);
152
153  mod(s1*q2-s2*q1, gcd(q1*q2,cond))==0;
154}
155
156{getcusp(cond,v,
157	ret,negv) =
158  ret = 0;
159  negv = [-v[1],v[2]];
160  for(n=1,length(cusps),
161    if(testcuspeq(cond,v,cusps[n]), ret=n, );
162    if(testcuspeq(cond,negv,cusps[n]), ret=n, );
163  );
164  if(ret==0,
165    cusps = concat(cusps,[v]);
166    ret = length(cusps);
167  ,);
168  ret;
169}
170
171
172{delta(cond,msymbol,
173	v,c1,c2,ret)=
174  v = bezout(msymbol[1],msymbol[2]);
175  if(v[3]<>1, print("msymbol not coprime:", msymbol);1/0 ,);
176  c1 = [v[2],msymbol[1]];
177  c2 = [-v[1],msymbol[2]];
178  ret=[c2/gcd(c2[1],c2[2]), c1/gcd(c1[1],c1[2])];
179  ret;
180}
181
182{kerdelta(cond,msymbols,hash,freebasis,
183	rels,m,k,kinv,ksz)=
184  rels = vector(length(freebasis),n, delta(cond,msymbols[freebasis[n]]) );
185  for(n=1,length(rels),
186    rels[n] = [getcusp(cond,rels[n][1]),getcusp(cond,rels[n][2])];
187  );
188  m = matrix(length(cusps),length(freebasis),n1,n2,0);
189  for(n=1,length(rels),
190    m[rels[n][1],n] = m[rels[n][1],n] + 1;
191    m[rels[n][2],n] = m[rels[n][2],n] - 1;
192  );
193  k = ker(m);
194  ksz = matsize(k);
195  kinvr = matinvr(supplement(k));
196  [k, matextract(kinvr,2^ksz[2]-1,2^ksz[1]-1)];
197}
198
199{modulartofree(cond,hash,symtofree,v,
200	q,hashval,n1,s1,sym,mods,ret)=
201  if(v[2]==0, v=[1,cond]; ,);
202  q = cf(v[1]/v[2]);
203  q[1]=1;
204  for(n=3,length(q),
205    q[n]=q[n]*q[n-1]+q[n-2];
206  );
207  sym = vector(matsize(symtofree)[2],n,0)~;
208  for(n=2,length(q),
209    mods = [(-1)^(n)*q[n],q[n-1],1];
210    hashval = dohash(cond,hash,mods);
211	s1=hashval[2]; n1=hashval[1];
212    sym[n1] = sym[n1]+s1;
213  );
214  ret=symtofree*sym;
215  ret;
216}
217
218{tpmatrix(cond,msymbols,hash,relations,hdata,p,
219	freebasis,symtofree,hbase,hdual,
220	sz,ret,col,sym,cusp,a)=
221  freebasis = relations[1];
222  symtofree = relations[2];
223  hbase = hdata[1];
224  hdual = hdata[2];
225
226  sz = matsize(hbase);
227  ret = matrix(sz[2],sz[2],n1,n2,0);
228
229  for(c=1,sz[2],
230    col = vector(sz[1],n,0)~;
231    for(r=1,sz[1],
232
233      a = hbase[r,c];
234      if(a,
235        sym = msymbols[freebasis[r]];
236		cusp = delta(cond,sym);
237        col = col - a*modulartofree(cond,hash,symtofree,cusp[1]*[p,0;0,1]);
238        col = col + a*modulartofree(cond,hash,symtofree,cusp[2]*[p,0;0,1]);
239        for(n=0,p-1,
240          col = col - a*modulartofree(cond,hash,symtofree,cusp[1]*[1,0;n,p]);
241          col = col + a*modulartofree(cond,hash,symtofree,cusp[2]*[1,0;n,p]);
242        );
243      ,);
244    );
245    ret[,c] = hdual*col;
246  );
247
248  ret;
249}
250
251{gammap(cond,msymbols,hash,relations,hdata,p,
252	freebasis,symtofree,hbase,hdual,
253	sz,ret,col,sym,cusp,a)=
254  freebasis = relations[1];
255  symtofree = relations[2];
256  hbase = hdata[1];
257  hdual = hdata[2];
258
259  sz = matsize(hbase);
260
261  col = vector(sz[1],n,0)~;
262  for(n=1,p-1,
263    col = col + modulartofree(cond,hash,symtofree,[n,p]);
264  );
265
266  hdual*col;
267}
268