Author: William A. Stein
1/***************************************************
2  fns.m -- Functions for ...
3
4  Jennifer Sinnott, 2004
5 ***************************************************/
6
7/**********
8Here is a collection of functions and procedures that will allow you to
9generate large tables of elliptic curves over a chosen number field with
10class number 1.
11
12To use, make directories "newdata" and "tables" and "isotables".
13Then open Magma and load these commands; e.g.,
14
16
17Then calculate data as follows:
18
19> m := <irreducible polynomial of your choice>; (e.g., m := x^2+1;)
20> B := <positive integer, a "bound" of your choice; (e.g., B := 3;)
21> K<a> := NumberField(m);
22> calculate(K, B);
23
24Data will be calculated and saved into the directory "newdata".
25The "bound" B will be explained later; note that data will be calculated
26up through bound 1 and saved, then from bound 1 to bound 2 and saved, and
27so forth (so if you set B so high that it takes too long to calculate all
28the way up through B, you will still get saved data for lower bounds).
29Then make tables as follows:
30
31> goodtablefile(m, B);;
32
33This will generate a table sorted by norm of the conductor of information
34about the curve, including its torsion subgroup.  This table will be
35stored in "tables".
36One can also generate tables of curves sorted into probable isogeny
37classes by:
38
39>isotablefile(m, B);
40
41This table will be stored in "isotables".
42**********/
43
44
45
46R<x>:=PolynomialRing(RationalField()); // for convenience.
47
48
49
50/**********
51I. Useful functions.
52**********/
53
54
55
56/***
57Increment function.  Use for generating strings of coefficients in a given
58numerical range.  Input:  X is a sequence of nonnegative integers.  B is a
59positive integer > 1.  Output:  a sequence got by “incrementing” the
60sequence X by 1 in base B.
61***/
62
63function inc(X, B)
64
65   assert Type(X) eq SeqEnum;
66   assert Type(B) eq RngIntElt;
67
68   if X eq [] then
69      return [];
70   end if;
71   X[#X] +:= 1;
72   if X[#X] eq B then
73      Y := inc([X[i] : i in [1..#X-1]], B);
74      return Y cat ;
75   end if;
76
77   return X;
78
79end function;
80
81
82
83/***
84Flatten function.  Flattens a sequence of sequences into a single
85sequence.  Input:  x is a sequence of sequences.  Output:  a sequence got
86by concatenating the sequences in x.
87***/
88
89function flatten(x)
90
91   return &cat x;
92
93end function;
94
95
96
97/***
98Filename maker.  Changes a sequence (e.g. [a, b, c]) to a string
99(“a_b_c� This and the function parsename below are used for making and
100understanding filenames when we will later save data.
101***/
102
103function makename(seq)
104
105   s2 := Sprintf("%o", seq);
106   n := #s2;
107   S := "";
108   for i in [1..n] do
109      if s2[i] eq "[" then
110      elif s2[i] eq "," then
111         S cat:= "_";
112      elif s2[i] eq " " then
113      elif s2[i] eq "]" then
114      else
115         S cat:= s2[i];
116      end if;
117   end for;
118
119   return S;
120
121end function;
122
123
124
125/***
126Filename understand-er.  Takes a file name as generated by makename and
127gives back the integer sequence.
128***/
129
130function parsename(str)
131   n := #str;
132   k := "";
133   for i in [1..n] do
134      if str[i] eq "_" then
135         k cat:= " ";
136      else
137         k cat:= str[i];
138      end if;
139   end for;
140   return StringToIntegerSequence(k);
141end function;
142
143
144
145/**********
146II. Curve listing functions.  These generate elliptic curves with
147coefficients in a certain "bound": we take curves in the form Y^2 = X^3
148+AX + B, where A and B are linear combinations of the power basis ( 1, a,
149a^2, ..., a^(n-1) ) of the field K=Q(a), where a is a root of the
150defining polynomial for K.  Then, curves "bounded" by an integer N will
151be curves whose A and B have coefficients on the power basis in the
152range [-B, B].  We will be generating lists of all curves in a certain
153"bound", and also generating "cleanlists" in which the curves are
154pairwise nonisomorphic over K.
155**********/
156
157
158
159/***
160A basic list function. Generates a list of all elliptic curves with
161coefficients in a certain range Input:  K is a number field.  B is a
162positive integer. Output:  A list of elliptic curves Y^2 = X^3 +aX + b,
163where a and b are linear combinations of the power basis of the field K
164defined by m, with coefficients in the range [-B, B].
165Uses: inc function.
166***/
167
168function list(K, B)
169
170   assert Type(K) eq FldNum;
171   assert Type(B) eq RngIntElt;
172
173   K<a> := K;
174   n := Degree(K);
175   L := [];
176   A4 := [0 : i in [1..n]];
177   A6 := [0 : i in [1..n]];
178   s := K![-B : i in [1..n]];
179   for i in [1..(2*B+1)^n] do
180      a4 := K!(K!A4 + s);  A4 := inc(A4,2*B+1);
181      for j in [1..(2*B+1)^n] do
182         a6 := K!(K!A6 + s);  A6 := inc(A6,2*B+1);
183         if IsEllipticCurve([a4,a6]) then
184            Append(~L, EllipticCurve([a4,a6]));
185         end if;
186      end for;
187   end for;
188
189   return L;
190
191end function;
192
193
194
195/***
196A basic list extending function.  Generates a list of all elliptic curves
197with coefficients in some range that are not all in a specified smaller
198range. Input:  K is a number field; B & C are integers with B < C.
199Output:  A list of elliptic curves Y^2 = X^3 +aX + b, where a and b are
200linear combinations of the integral basis elements with coefficients in
201the range [-C, C] which are not all in the range [-B, B].
202Uses: inc function.
203***/
204
205function extendlist(K, B, C);
206
207   assert Type(K) eq FldNum;
208   assert Type(B) eq RngIntElt;
209   assert Type(C) eq RngIntElt;
210
211   K<a> := K;
212   L := [];
213   n := Degree(K);
214   A4 := [0 : i in [1..n]];
215   A6 := [0 : i in [1..n]];
216   s := K![-C : i in [1..n]];
217   for i in [1..(2*C+1)^(n)] do
218      f := false;
219      for k in [1..n] do
220         if A4[k] in [0..C-B-1] or A4[k] in [C+B+1..2*C] then
221            f := true;
222            break;
223         end if;
224      end for;
225      if f then
226         a4 := K!(K!A4 + s);  A4 := inc(A4,2*C+1);
227         for j in [1..(2*C+1)^n] do
228            a6 := K!(K!A6 + s);  A6 := inc(A6,2*C+1);
229            if IsEllipticCurve([a4,a6]) then
230               Append(~L, EllipticCurve([a4,a6]));
231            end if;
232         end for;
233      else
234         a4 := K!(K!A4 + s);  A4 := inc(A4,2*C+1);
235         for j in [1..(2*C+1)^n] do
236            g := false;
237            for k in [1..n] do
238              if A6[k] in [0..C-B-1] or A6[k] in [C+B+1..2*C] then
239                 g := true;
240                 break;
241              end if;
242            end for;
243            if g then
244               a6 := K!(K!A6 + s);  A6 := inc(A6,2*C+1);
245               if IsEllipticCurve([a4,a6]) then
246                  Append(~L, EllipticCurve([a4,a6]));
247               end if;
248            else
249               A6 := inc(A6, 2*C+1);
250            end if;
251         end for;
252      end if;
253   end for;
254
255   return L;
256
257end function;
258
259
260
261/***
262A clean-list function.  Generates a list of all pairwise non-isomorphic
263elliptic curves with coefficients in some range.
264Input:  K is a number field.  B is a positive integer.
265Output:  A list of elliptic curves Y^2 = X^3 +aX + b, where a and b are
266linear combinations of the integral basis elements with coefficients in
267the range [-B, B], then throws out a curve if it is isomorphic to one
268earlier in the list; returns also a list of their j-invariants.
269Uses: list function, inc function.
270***/
271
272function cleanlist(K, B)
273
274   assert Type(K) eq FldNum;
275   assert Type(B) eq RngIntElt;
276
277   K<a> := K;
278   L := list(K, B);
279   L2 := [];
280   J := [];
281   J2 := [];
282   for i in [1..#L] do
283      j := jInvariant(L[i]);  Append (~J, j);
284      t := true;
285      if #J gt 1 then
286         for d in [1..#J-1] do
287            if J[#J] eq J[d] then
288               if IsIsomorphic(L[#J], L[d]) then
289                  t:=false;
290                  break;
291               end if;
292            end if;
293         end for;
294      end if;
295      if t eq true then
296         Append(~L2, L[i]);
297         Append(~J2, J[i]);
298      end if;
299   end for;
300
301   return <L2, J2>;
302
303end function;
304
305
306
307/***
308A clean-list extending function.  Extends a list of nonisomorphic curves
309over a field K up through a bound B and extends it through a bound C.
310Input:  A number field K, a list L2 of nonisomorphic curves up
311through B with associated j-invariants C, and extends the list up through
312C.  The resulting list is "clean"; also returns list of their
313j-invariants.
314Uses: extendlist function, inc function.
315***/
316
317function extendcleanlist(K, L2, J2, B, C);
318
319   assert Type(K) eq FldNum;
320   assert Type(L2) eq SeqEnum;
321   assert Type(J2) eq SeqEnum;
322   assert Type(B) eq RngIntElt;
323   assert Type(C) eq RngIntElt;
324
325   K<a> := K;
326   S := #L2;
327   L3 :=extendlist(K, B, C);
328   for i in [1..#L3] do
329      j := jInvariant(L3[i]);
330      t := true;
331      if #J2 ge 1 then
332         for d in [1..#J2] do
333            if j eq J2[d] then
334               if IsIsomorphic(L3[i], L2[d]) then
335                  t:=false;
336                  break;
337               end if;
338            end if;
339         end for;
340      end if;
341      if t eq true then
342         Append(~L2, L3[i]);
343         Append(~J2, j);
344      end if;
345   end for;
346   L4:=[];
347   J4:=[];
348   for i in [S+1..#L2] do
349      Append(~L4, L2[i]);
350      Append(~J4, J2[i]);
351   end for;
352
353   return <L4, J4>;
354
355end function;
356
357
358
359/**********
361in a
362directory called "newdata"; one can go through and change that name in
363the following four functions so that everything is saved in a different
364directory.
365**********/
366
367
368
369/***
370Save-to-file procedure.  Saves an integer sequence to a file. (Creates or
371overwrites the file given by filename.)
372***/
373
374procedure save_to_file(seq, filename)
375
376   assert Type(filename) eq MonStgElt;
377   assert Type(seq) eq SeqEnum;
378
379   file := Open("newdata/"*filename, "w");
380   for x in seq do
381      fprintf file, "%o ", x;
382   end for;
383
384end procedure;
385
386
387
388/***
389Append-to-file procedure.  This would append a sequence to a file; I
390don't actually use this, but it could be useful so I include it.
391***/
392
393procedure append_to_file(seq, filename)
394
395   assert Type(filename) eq MonStgElt;
396   assert Type(seq) eq SeqEnum;
397
398   file := Open("newdata/"*filename, "a");
399   for x in seq do
400      fprintf file, "%o ", x;
401   end for;
402
403end procedure;
404
405
406
407/***
408Load-from-file function.  Opens a file and converts it to an integer
409string.  Will get mad if file does not consist of a string of integers.
410***/
411
413
415
416   return StringToIntegerSequence(str);
417
418end function;
419
420
421
422/***
423Checks if a file exists.
424***/
425
426function Exists(path)
427   assert Type(path) eq MonStgElt;
428   x := Gets(POpen("ls newdata/"*path,"r"));
429   return not IsEof(x);
430end function;
431
432
433
434/**********
435IV. Elldata functions.  We are interested in saving "elldata":
436
437elldata is a 4-tuple < elliptic curve, j-invariant, conductor,
438torsion subgroup > where
439  elliptic_curve -- elliptic curve E over a number field K
440  j-invariant -- the j-invariant of E
441  conductor -- the conductor of E, as an integral ideal of K
442  torsion subgp -- an abstract abelian group
443
444These functions convert elldata to integer strings so that they can be
445saved, or interprete back integer strings into elldata.  Here is where we
446will be using that the class number of the field K is 1: Magma's
447"Conductor" only works when that assumption is true.
448**********/
449
450
451
452/***
453Elldata to integer sequence conversion.
454Input: elldata is a 4-tuple < elliptic curve, j-invariant, conductor,
455torsion subgroup > where
456Output: an integer list representing the curve, of length 4n+4, where
457n is the degree of the field extension.
458Uses: flatten function.
459***/
460
461function elldata_to_sequence(elldata)
462
463   Z := RingOfIntegers();
464   ans := [];
465   E, j, N, tor := Explode(elldata);
466   K := BaseField(E);
467   _,_,_,a,b := Explode(aInvariants(E));
468   Append(~ans, Eltseq(a));
469   Append(~ans, Eltseq(b));
470   Append(~ans, Eltseq(Numerator(j)));
471   Append(~ans, [Denominator(j)]);
472   truth, gen := IsPrincipal(N);
473   Append(~ans, Eltseq(Numerator(K!gen)));
474   Append(~ans, [Denominator(K!gen)]);
475   tor := Invariants(tor);
476   for i in [1..2-#tor] do
477      Append(~tor,);
478   end for;
479   Append(~ans, tor);
480   f := flatten(ans);
481   K := #f;
482   f2:= [];
483   for i in [1..K] do
484      assert Denominator(f[i]) eq 1;
485      Append(~f2, Z!f[i]);
486   end for;
487   return f2;
488
489end function;
490
491
492
493/***
494Integer sequence to elldata conversion.
495Input: K is a number field of degree n.  seq is an integer sequence of
496length 4n+4.
497Output: elldata 4-tuple.
498***/
499
500function sequence_to_elldata(K, seq)
501
502   assert Type(K) eq FldNum;
503   assert Type(seq) eq SeqEnum;
504
505   n := Degree(K);
506   k := 0;
507   a := K![seq[k+i] : i in [1..n]]; k +:= n;
508   b := K![seq[k+i] : i in [1..n]]; k +:= n;
509   E := EllipticCurve([a,b]);
510   jn := K![seq[k+i] : i in [1..n]]; k +:= n;
511   jd := K!seq[k+1]; k +:= 1;
512   j := jn/jd;
513   cn := K![seq[k+i] : i in [1..n]]; k +:= n;
514   cd := K!seq[k+1]; k +:= 1;
515   N := (cn/cd)*MaximalOrder(K);
516   tor := AbelianGroup([seq[k+i] : i in [1..2]]); k +:= 2;
517   assert k eq #seq;
518
519   return <E, j, N, tor>;
520
521end function;
522
523
524
525/***
526A data extracting-from-file function.
527The calculate function below will take a number field and a "bound"
528and produce files which are lists of curves given in integer
529sequence form (as in the above elldata_to_sequence function); this
530function takes a number field and a file name and converts the
531integer sequence into a list of elldata four-tuples.
533***/
534
535function Extract(K, filename)
536
537   R<x> := PolynomialRing(RationalField());
538   Z := RingOfIntegers();
539   P := parsename(filename);
540
541  assert Degree(K) eq P;
542
543   n := Degree(K);
544
545  assert R!DefiningPolynomial(K) eq R!Polynomial([P[i+1] : i in [1..n+1]]);
546
547   List:=[];
548
549   N := 4*n+4;
551   l := #datastring/N;
552   assert Denominator(l) eq 1;
553   l := Z!l;
554   for j in [0..l-1] do
555      L := [];
556      for k in [1..N] do
557         Append(~L, datastring[j*N+k]);
558      end for;
559      s := sequence_to_elldata(K, L);
560      Append(~List, s);
561   end for;
562   return List;
563
564end function;
565
566
567
568/**********
569V.  Sorting procedures: uses quicksort.
570**********/
571
572
573
574/***
575Procedure underlying quicksort.
576***/
577
578procedure QuickSort_recurse(~items, low, high, lessthan)
579  // sorts Seqenum using the quick sort algorithm
580   if low ge high then
581      return;
582   end if;
583   if #items le 2 then
584      t := items[high];
585      items[high] := items[low];
586      items[low] := t;
587      assert lessthan(items,items);
588      return;
589   end if;
590
591   lo := low;
592   hi := high + 1;
593   elem := items[low];
594   while true do
595      while lo lt high and
596            lessthan(items[lo+1],elem) do
597         lo +:= 1;
598      end while;
599      lo +:= 1;
600      while lessthan(elem,items[hi-1]) do
601         hi -:= 1;
602      end while;
603      hi -:= 1;
604      if lo lt hi then
605         t := items[hi];
606         items[hi] := items[lo];
607         items[lo] := t;
608      else
609         break;
610      end if;
611   end while;
612   t := items[hi];
613   items[hi] := items[low];
614   items[low] := t;
615   QuickSort_recurse(~items,low,hi-1,lessthan);
616   QuickSort_recurse(~items,hi + 1,high,lessthan);
617end procedure;
618
619
620
621/***
622Quicksort procedure that will be called.
623***/
624
625procedure QuickSort(~items, lessthan)
626   // items    -- a sequence
627   // lessthan -- a function that takes two arguments, and returns true
628   //             if and only if the first is "less than" the second.
629   QuickSort_recurse(~items,1,#items, lessthan);
630end procedure;
631
632
633
634/***
635One lessthan function for use with quicksort.
636***/
637
638function lessthan(a, b)
639   if Norm(a) lt Norm(b) then
640      return true;
641   else
642      return false;
643   end if;
644end function;
645
646
647
648/***
649Another lessthan function for use with quicksort.
650***/
651
652function llessthan(A, B)
653   if StringToInteger(A) lt StringToInteger(B) then
654      return true;
655   end if;
656   if StringToInteger(A) gt StringToInteger(B) then
657      return false;
658   end if;
659   for i in [8..#A] do         // bad is less than everything (but bad)
660      if A[i] eq "bad" then
661         if B[i] ne "bad" then
662             return true;
663         else
664             continue;
665         end if;
666      end if;
667      a := StringToInteger(A[i]);
668      if B[i] eq "bad" then
669         return false;
670      end if;
671      b := StringToInteger(B[i]);
672      if a lt b then
673         return true;
674      elif a gt b then
675         return false;
676      end if;
677   end for;
678   return false;
679end function;
680
681
682
683/**********
684VI.  Calculating and table-making functions and procedures.
685**********/
686
687
688
689/***
690Generates data; checks if it already exists before making it anew; saves
691it to files.  File names are given by, for a field K with defining
692polynomial m:
693<n=degree of K> _ <constant term of m> _ <coefficient on x in m> _
694... _ <coefficient on x^n in m> _ <bound>
695where bound is a bound in the sense described in the listing functions,
696and where curves "bounded" by B-1 do not appear in the file saved with
697bound B.
698Uses: makename, flatten, Exists, Extract, cleanlist, extendcleanlist,
699elldata_to_sequence, save_to_file.
700***/
701
702procedure calculate(K, B);
703
704   assert Type(K) eq FldNum;
705   assert Type(B) eq RngIntElt;
706
707   K<a> := K;
708   m := DefiningPolynomial(K);
709   n := Degree(K);
710   M := [];
711   L2 := [];
712   J2 := [];
713
714   for i in [1..B] do
715      name:= [];
716      Append(~name, [Degree(K)]);
717      Append(~name, Coefficients(m));
718      Append(~name, [i]);
719      Append(~M, makename(flatten(name)));
720   end for;
721
722   for i in [1..B] do
723      if Exists(M[i]) eq true then
724         print "found data for size", i;
725         Starter := Extract(K, M[i]);
726         for k in [1..#Starter] do
727            Append(~L2, Starter[k]);
728            Append(~J2, Starter[k]);
729         end for;
730      else
731         if i eq 1 then
732            L := cleanlist(K, 1);
733            seq_i := [];
734            Starter := [];
735            for j in [1..#L] do
736               G:=TorsionSubgroup(L[j]);
737               C:=Conductor(L[j]);
738               Info:= <L[j], L[j], C, G>;
739               Append(~Starter, Info);
740               seq:=elldata_to_sequence(Info);
741               Append(~seq_i, seq);
742            end for;
743            for k in [1..#Starter] do
744               Append(~L2, Starter[k]);
745               Append(~J2, Starter[k]);
746            end for;
747            finalseq := flatten(seq_i);
748            save_to_file(finalseq, M[i]);
749            print "done with 1";
750         else
751            P := extendcleanlist(K, L2, J2, i-1, i);
752            seq_i := [];
753            Starter := [];
754            for j in [1..#P] do
755               G := TorsionSubgroup(P[j]);
756               C := Conductor(P[j]);
757               Info := <P[j], P[j], C, G>;
758               Append(~Starter, Info);
759               seq := elldata_to_sequence(Info);
760               Append(~seq_i, seq);
761            end for;
762            for k in [1..#Starter] do
763               Append(~L2, Starter[k]);
764               Append(~J2, Starter[k]);
765            end for;
766            finalseq := flatten(seq_i);
767            save_to_file(finalseq, M[i]);
768            print "done with", i;
769         end if;
770      end if;
771   end for;
772
773end procedure;
774
775
776
777/***
778An initial table-making procedure. Once data has been calculated, this
779accesses it and sorts it.  Data is given as a sequence of <>-sequences,
780each <>-sequence listing information about one curve.
781Uses: makename, flatten, Extract, Quicksort with lessthan.
782***/
783
784function maketable(K, B);
785
786  assert Type(K) eq FldNum;
787  assert Type(B) eq RngIntElt;
788
789   R<x>:=PolynomialRing(Rationals());
790   K<a>:=K;
791   m:=DefiningPolynomial(K);
792   M:=[];
793
794   for i in [1..B] do
795      name := [];
796      Append(~name, [Degree(K)]);
797      Append(~name, Coefficients(m));
798      Append(~name, [i]);
799      Append(~M, makename(flatten(name)));
800   end for;
801
802   for i in [1..B] do
803      if Exists(M[i]) eq false then
804         return "data has not yet been computed for", i;
805      end if;
806   end for;
807
808   BigList:=[];
809   for i in [1..B] do
810      Append(~BigList, Extract(K, M[i]));
811   end for;
812
813   L:=flatten(BigList);
814   QuickSort(~L, lessthan);
815
816   LL:=[];
817   for i in [1..#L] do
818      s0 := Norm(L[i]);
819      _,_,_,a,b := Explode(aInvariants(L[i]));
820      s1:=a;
821      s2 := b;
822      s3 := L[i];
823      t, s := IsPrincipal(L[i]);
824      s4 := K!s;
825      tor := Invariants(L[i]);
826      for i in [1..2-#tor] do
827         Append(~tor, );
828      end for;
829      s5 := tor;
830      s6 := tor;
831      Append(~LL, <s0, s1, s2, [s5, s6], s5*s6, s3, s4>);
832   end for;
833
834   return LL;
835
836end function;
837
838
839
840/***
841Makes a table in the style of those on the website.
842Uses: maketable.
843***/
844
845function goodtable(K, B)
846  assert Type(K) eq FldNum;
847  assert Type(B) eq RngIntElt;
848   K<a>:=K;
849   n:=Degree(K);
850   m:=DefiningPolynomial(K);
851   M:=maketable(K, B);
852   list:="";
853   length:=12*n-9;
854   for i in [1..#M] do
855      f:="";
856      s1:=Sprintf("%o", M[i]);
857      s11:="";
858      for j in [1..#s1] do
859         if s1[j] eq " " then
860         else
861            s11 cat:= s1[j];
862         end if;
863      end for;
864      s2:=Sprintf("%o", M[i]);
865      s22:="";
866      for j in [1..#s2] do
867         if s2[j] eq " " then
868         else
869            s22 cat:= s2[j];
870         end if;
871      end for;
872      length1:=#s11;
873      length2:=#s22;
874      L:=length1+length2+3;
875      for j in [1..#M] do
876         s:=Sprintf("%o", M[i][j]);
877         if j eq 2 then
878            f cat:= "["*s*",";
879         elif j eq 3 then
880            gap:=length-L;
881            f cat:=s*"]"*"_"^(gap+1);
882         elif j eq 6 then
883            if #s le 7 then
884               f cat:= s*"\t\t\t";
885            elif #s gt 7 and #s le 14 then
886               f cat:= s*"\t\t";
887            else
888               f cat:= s*"\t";
889            end if;
890         elif j eq 7 then
891            f cat:= "("*s*")"*"\n";
892         else
893            f cat:= s*"\t";
894         end if;
895      end for;
896      f2:="";
897      for j in [1..#f] do
898         if f[j] eq " " then
899         elif f[j] eq "_" then
900            f2 cat:= " ";
901         else
902            f2 cat:= f[j];
903         end if;
904      end for;
905      list cat:= f2;
906   end for;
907   return list;
908end function;
909
910
911
912/***
913Creates a table in the style of those on the website, and saves it into a
914directory "tables".
915Uses: makename, goodtable.
916***/
917
918procedure goodtablefile(m, B)
919      R<x>:=PolynomialRing(Rationals());
920      m:=R!m;
921      K<a>:=NumberField(m);
922      n:=Sprintf("%o", Degree(K));
923      c:=makename(Coefficients(m));
924      b:=Sprintf("%o", B);
925      filename := "table_degree_"*n*"_poly_"*c*"_size_"*b*".txt";
926      s := goodtable(K,B);
927      F := Open("tables/"*filename,"w");
928      fprintf F, "%o", s;
929end procedure;
930
931
932
933/***
934This function produces a table in which curves, given by conductor, norm
935of the conductor, and coefficients a and b, are divided up into probable
936isogeny classes, where two curves in the same probable isogeny class both
937with conductor N are listed with the same capital letter (e.g., two
938curves of conductor with norm 16 which are probably isogenous would be
939listed as 16A and 16A; two definitely non-isogenous such curves would be
940listed as 16A and 16B.)
941Uses: maketable.
942 ***/
943
944function divideup(m, B)
945
946   assert Type(m) eq RngUPolElt;
947   assert Type(B) eq RngIntElt;
948
949   Z:=RingOfIntegers;
950   K<a>:=NumberField(m);
951   n:=Degree(K);
952   OK := MaximalOrder(K);
953   M:=maketable(K, B);
954   M2:=[];
955   for i in [1..#M] do
956      if M[i] le 100000 then
957         Append(~M2, M[i]);
958      else
959         break;
960      end if;
961   end for;
962   primes := [];
963   Zprimes := [ p: p in [1..100] | IsPrime(p) eq true];
964   for i in [1..#Zprimes] do
965      F:=Factorization(Zprimes[i]*OK);
966      for j in [1..#F] do
967         Append(~primes, F[j]);
968      end for;
969   end for;
970   list:=[ ];
971   for i in [1..#M2] do
972      M3:=[];
973      for j in [1..#M2[i]] do
974         Append(~M3, Sprintf("%o", M2[i][j]));
975      end for;
976      K:=[];
978      for j in [1..#primes] do
979         if primes[j] in bad then
981         else
982            ER:=Reduction(EllipticCurve([M2[i], M2[i]]), primes[j]);
983            Append(~K, Sprintf("%o", TraceOfFrobenius(ER)));
984         end if;
985      end for;
986      Append(~list, M3 cat K);
987   end for;
988   QuickSort(~list, llessthan);
989   alphabet:=["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K",
990"L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y",
991"Z"];
992   for i in [1..#list] do
993      if i eq 1 then
994         k := 1;
995         list[i] cat:= " "*alphabet[k];
996      elif list[i]*" "*alphabet[k] eq list[i-1] then
997         t:=true;
998         for j in [8..#list] do
999            if list[i][j] eq list[i-1][j] then
1000            else
1001               t:=false;
1002               break;
1003            end if;
1004         end for;
1005         if t eq true then
1006            list[i] cat:= " "*alphabet[k];
1007         else
1008            k +:= 1;
1009            list[i] cat:= " "*alphabet[k];
1010         end if;
1011      else
1012         k := 1;
1013         list[i] cat:= " "*alphabet[k];
1014      end if;
1015   end for;
1016   M:=list;
1017   list:="";
1018   length:=12*n-9;
1019   for i in [1..#M] do
1020      f:="";
1021      s1:=M[i];
1022      s11:="";
1023      for j in [1..#s1] do
1024         if s1[j] eq " " then
1025         else
1026            s11 cat:= s1[j];
1027         end if;
1028      end for;
1029      s2:=M[i];
1030      s22:="";
1031      for j in [1..#s2] do
1032         if s2[j] eq " " then
1033         else
1034            s22 cat:= s2[j];
1035         end if;
1036      end for;
1037      length1:=#s11;
1038      length2:=#s22;
1039      L:=length1+length2+3;
1040      for j in [1..#M] do
1041         s:=M[i][j];
1042         if j eq 2 then
1043            f cat:= "["*s*",";
1044         elif j eq 3 then
1045            gap:=length-L;
1046            f cat:=s*"]"*"_"^(gap+1);
1047         elif j eq 6 or j eq 5 or j eq 4 then
1048         elif j eq 7 then
1049            s1:="";
1050            for i in [1..#s] do
1051               if s[i] eq " " then
1052               else
1053                  s1 cat:= s[i];
1054               end if;
1055            end for;
1056            if #s1+1 lt 7 then
1057               f cat:= "("*s*")\t\t";
1058            else
1059               f cat:= "("*s*")\t";
1060            end if;
1061         elif j eq #M then
1062            f cat:= s*"\n";
1063         else
1064            f cat:= s*"\t";
1065         end if;
1066      end for;
1067      f2:="";
1068      for j in [1..#f] do
1069         if f[j] eq " " then
1070         elif f[j] eq "_" then
1071            f2 cat:= " ";
1072         else
1073            f2 cat:= f[j];
1074         end if;
1075      end for;
1076      list cat:= f2;
1077   end for;
1078   return list;
1079end function;
1080
1081
1082
1083/***
1084Computes the same table of probable isogeny classes, this time saving to
1085a file.
1086Uses: makename, divideup.
1087***/
1088
1089procedure isotablefile(m, B)
1090      R<x>:=PolynomialRing(Rationals());
1091      m:=R!m;
1092      K<a>:=NumberField(m);
1093      n:=Sprintf("%o", Degree(K));
1094      c:=makename(Coefficients(m));
1095      b:=Sprintf("%o", B);
1096      filename := "isotable_degree_"*n*"_poly_"*c*"_size_"*b*".txt";
1097      s := divideup(m, B);
1098      F := Open("isotables/"*filename,"w");
1099      fprintf F, "%o", s;
1100end procedure;
1101
1102
1103
1104/**********
1105Miscellaneous.
1106**********/
1107
1108
1109/***
1110Arbitrary curve generator. Gives you elldata of some curve
1111over your field (i.e., produces <curve, j-invariant, conductor, torsion
1112subgroup>).  This is useful to have around to test things out, but is not
1113used in any later function.
1114***/
1115
1116function somecurve(K);
1117
1118   assert Type(K) eq FldNum;
1119
1120   K<a> := K;
1121   n := Degree(K);
1122   A4 := [Random(-50, 50) : i in [1..n]];
1123   A6 := [Random(-50, 50) : i in [1..n]];
1124   a4 := K!(K!A4); a6 := K!(K!A6);
1125   if IsEllipticCurve([a4, a6]) eq true then
1126      EC := EllipticCurve([a4, a6]);
1127      J := jInvariant(EC);
1128      C := Conductor(EC);
1129      G := TorsionSubgroup(EC);
1130      return <EC, J, C, G>;
1131   else