Sharedwww / eck / fns.mOpen in CoCalc
Author: William A. Stein
1
/***************************************************
2
fns.m -- Functions for ...
3
4
Jennifer Sinnott, 2004
5
***************************************************/
6
7
/**********
8
Here is a collection of functions and procedures that will allow you to
9
generate large tables of elliptic curves over a chosen number field with
10
class number 1.
11
12
To use, make directories "newdata" and "tables" and "isotables".
13
Then open Magma and load these commands; e.g.,
14
15
>load "fns.m";
16
17
Then 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
24
Data will be calculated and saved into the directory "newdata".
25
The "bound" B will be explained later; note that data will be calculated
26
up through bound 1 and saved, then from bound 1 to bound 2 and saved, and
27
so forth (so if you set B so high that it takes too long to calculate all
28
the way up through B, you will still get saved data for lower bounds).
29
Then make tables as follows:
30
31
> goodtablefile(m, B);;
32
33
This will generate a table sorted by norm of the conductor of information
34
about the curve, including its torsion subgroup. This table will be
35
stored in "tables".
36
One can also generate tables of curves sorted into probable isogeny
37
classes by:
38
39
>isotablefile(m, B);
40
41
This table will be stored in "isotables".
42
**********/
43
44
45
46
R<x>:=PolynomialRing(RationalField()); // for convenience.
47
48
49
50
/**********
51
I. Useful functions.
52
**********/
53
54
55
56
/***
57
Increment function. Use for generating strings of coefficients in a given
58
numerical range. Input: X is a sequence of nonnegative integers. B is a
59
positive integer > 1. Output: a sequence got by “incrementing” the
60
sequence X by 1 in base B.
61
***/
62
63
function 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 [0];
75
end if;
76
77
return X;
78
79
end function;
80
81
82
83
/***
84
Flatten function. Flattens a sequence of sequences into a single
85
sequence. Input: x is a sequence of sequences. Output: a sequence got
86
by concatenating the sequences in x.
87
***/
88
89
function flatten(x)
90
91
return &cat x;
92
93
end function;
94
95
96
97
/***
98
Filename 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
100
understanding filenames when we will later save data.
101
***/
102
103
function 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
121
end function;
122
123
124
125
/***
126
Filename understand-er. Takes a file name as generated by makename and
127
gives back the integer sequence.
128
***/
129
130
function 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);
141
end function;
142
143
144
145
/**********
146
II. Curve listing functions. These generate elliptic curves with
147
coefficients 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,
149
a^2, ..., a^(n-1) ) of the field K=Q(a), where a is a root of the
150
defining polynomial for K. Then, curves "bounded" by an integer N will
151
be curves whose A and B have coefficients on the power basis in the
152
range [-B, B]. We will be generating lists of all curves in a certain
153
"bound", and also generating "cleanlists" in which the curves are
154
pairwise nonisomorphic over K.
155
**********/
156
157
158
159
/***
160
A basic list function. Generates a list of all elliptic curves with
161
coefficients in a certain range Input: K is a number field. B is a
162
positive integer. Output: A list of elliptic curves Y^2 = X^3 +aX + b,
163
where a and b are linear combinations of the power basis of the field K
164
defined by m, with coefficients in the range [-B, B].
165
Uses: inc function.
166
***/
167
168
function 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
191
end function;
192
193
194
195
/***
196
A basic list extending function. Generates a list of all elliptic curves
197
with coefficients in some range that are not all in a specified smaller
198
range. Input: K is a number field; B & C are integers with B < C.
199
Output: A list of elliptic curves Y^2 = X^3 +aX + b, where a and b are
200
linear combinations of the integral basis elements with coefficients in
201
the range [-C, C] which are not all in the range [-B, B].
202
Uses: inc function.
203
***/
204
205
function 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
257
end function;
258
259
260
261
/***
262
A clean-list function. Generates a list of all pairwise non-isomorphic
263
elliptic curves with coefficients in some range.
264
Input: K is a number field. B is a positive integer.
265
Output: A list of elliptic curves Y^2 = X^3 +aX + b, where a and b are
266
linear combinations of the integral basis elements with coefficients in
267
the range [-B, B], then throws out a curve if it is isomorphic to one
268
earlier in the list; returns also a list of their j-invariants.
269
Uses: list function, inc function.
270
***/
271
272
function 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
303
end function;
304
305
306
307
/***
308
A clean-list extending function. Extends a list of nonisomorphic curves
309
over a field K up through a bound B and extends it through a bound C.
310
Input: A number field K, a list L2 of nonisomorphic curves up
311
through B with associated j-invariants C, and extends the list up through
312
C. The resulting list is "clean"; also returns list of their
313
j-invariants.
314
Uses: extendlist function, inc function.
315
***/
316
317
function 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
355
end function;
356
357
358
359
/**********
360
III. Some file saving, loading, etc. procedures. Things are being saved
361
in a
362
directory called "newdata"; one can go through and change that name in
363
the following four functions so that everything is saved in a different
364
directory.
365
**********/
366
367
368
369
/***
370
Save-to-file procedure. Saves an integer sequence to a file. (Creates or
371
overwrites the file given by filename.)
372
***/
373
374
procedure 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
384
end procedure;
385
386
387
388
/***
389
Append-to-file procedure. This would append a sequence to a file; I
390
don't actually use this, but it could be useful so I include it.
391
***/
392
393
procedure 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
403
end procedure;
404
405
406
407
/***
408
Load-from-file function. Opens a file and converts it to an integer
409
string. Will get mad if file does not consist of a string of integers.
410
***/
411
412
function load_from_file(filename)
413
414
str := Read("newdata/"*filename);
415
416
return StringToIntegerSequence(str);
417
418
end function;
419
420
421
422
/***
423
Checks if a file exists.
424
***/
425
426
function Exists(path)
427
assert Type(path) eq MonStgElt;
428
x := Gets(POpen("ls newdata/"*path,"r"));
429
return not IsEof(x);
430
end function;
431
432
433
434
/**********
435
IV. Elldata functions. We are interested in saving "elldata":
436
437
elldata is a 4-tuple < elliptic curve, j-invariant, conductor,
438
torsion 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
444
These functions convert elldata to integer strings so that they can be
445
saved, or interprete back integer strings into elldata. Here is where we
446
will 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
/***
453
Elldata to integer sequence conversion.
454
Input: elldata is a 4-tuple < elliptic curve, j-invariant, conductor,
455
torsion subgroup > where
456
Output: an integer list representing the curve, of length 4n+4, where
457
n is the degree of the field extension.
458
Uses: flatten function.
459
***/
460
461
function 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,[1]);
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
489
end function;
490
491
492
493
/***
494
Integer sequence to elldata conversion.
495
Input: K is a number field of degree n. seq is an integer sequence of
496
length 4n+4.
497
Output: elldata 4-tuple.
498
***/
499
500
function 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
521
end function;
522
523
524
525
/***
526
A data extracting-from-file function.
527
The calculate function below will take a number field and a "bound"
528
and produce files which are lists of curves given in integer
529
sequence form (as in the above elldata_to_sequence function); this
530
function takes a number field and a file name and converts the
531
integer sequence into a list of elldata four-tuples.
532
Uses: parsename, load_from_file, sequence_to_elldata.
533
***/
534
535
function Extract(K, filename)
536
537
R<x> := PolynomialRing(RationalField());
538
Z := RingOfIntegers();
539
P := parsename(filename);
540
541
assert Degree(K) eq P[1];
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;
550
datastring := load_from_file(filename);
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
564
end function;
565
566
567
568
/**********
569
V. Sorting procedures: uses quicksort.
570
**********/
571
572
573
574
/***
575
Procedure underlying quicksort.
576
***/
577
578
procedure 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[1],items[2]);
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);
617
end procedure;
618
619
620
621
/***
622
Quicksort procedure that will be called.
623
***/
624
625
procedure 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);
630
end procedure;
631
632
633
634
/***
635
One lessthan function for use with quicksort.
636
***/
637
638
function lessthan(a, b)
639
if Norm(a[3]) lt Norm(b[3]) then
640
return true;
641
else
642
return false;
643
end if;
644
end function;
645
646
647
648
/***
649
Another lessthan function for use with quicksort.
650
***/
651
652
function llessthan(A, B)
653
if StringToInteger(A[1]) lt StringToInteger(B[1]) then
654
return true;
655
end if;
656
if StringToInteger(A[1]) gt StringToInteger(B[1]) 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;
679
end function;
680
681
682
683
/**********
684
VI. Calculating and table-making functions and procedures.
685
**********/
686
687
688
689
/***
690
Generates data; checks if it already exists before making it anew; saves
691
it to files. File names are given by, for a field K with defining
692
polynomial m:
693
<n=degree of K> _ <constant term of m> _ <coefficient on x in m> _
694
... _ <coefficient on x^n in m> _ <bound>
695
where bound is a bound in the sense described in the listing functions,
696
and where curves "bounded" by B-1 do not appear in the file saved with
697
bound B.
698
Uses: makename, flatten, Exists, Extract, cleanlist, extendcleanlist,
699
elldata_to_sequence, save_to_file.
700
***/
701
702
procedure 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][1]);
728
Append(~J2, Starter[k][2]);
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[1]] do
736
G:=TorsionSubgroup(L[1][j]);
737
C:=Conductor(L[1][j]);
738
Info:= <L[1][j], L[2][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][1]);
745
Append(~J2, Starter[k][2]);
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[1]] do
755
G := TorsionSubgroup(P[1][j]);
756
C := Conductor(P[1][j]);
757
Info := <P[1][j], P[2][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][1]);
764
Append(~J2, Starter[k][2]);
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
773
end procedure;
774
775
776
777
/***
778
An initial table-making procedure. Once data has been calculated, this
779
accesses it and sorts it. Data is given as a sequence of <>-sequences,
780
each <>-sequence listing information about one curve.
781
Uses: makename, flatten, Extract, Quicksort with lessthan.
782
***/
783
784
function 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][3]);
819
_,_,_,a,b := Explode(aInvariants(L[i][1]));
820
s1:=a;
821
s2 := b;
822
s3 := L[i][2];
823
t, s := IsPrincipal(L[i][3]);
824
s4 := K!s;
825
tor := Invariants(L[i][4]);
826
for i in [1..2-#tor] do
827
Append(~tor, [1]);
828
end for;
829
s5 := tor[1];
830
s6 := tor[2];
831
Append(~LL, <s0, s1, s2, [s5, s6], s5*s6, s3, s4>);
832
end for;
833
834
return LL;
835
836
end function;
837
838
839
840
/***
841
Makes a table in the style of those on the website.
842
Uses: maketable.
843
***/
844
845
function 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][2]);
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][3]);
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[1]] 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;
908
end function;
909
910
911
912
/***
913
Creates a table in the style of those on the website, and saves it into a
914
directory "tables".
915
Uses: makename, goodtable.
916
***/
917
918
procedure 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;
929
end procedure;
930
931
932
933
/***
934
This function produces a table in which curves, given by conductor, norm
935
of the conductor, and coefficients a and b, are divided up into probable
936
isogeny classes, where two curves in the same probable isogeny class both
937
with conductor N are listed with the same capital letter (e.g., two
938
curves of conductor with norm 16 which are probably isogenous would be
939
listed as 16A and 16A; two definitely non-isogenous such curves would be
940
listed as 16A and 16B.)
941
Uses: maketable.
942
***/
943
944
function 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][1] 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][1]);
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:=[];
977
bad:=BadPlaces(EllipticCurve([M2[i][2], M2[i][3]]));
978
for j in [1..#primes] do
979
if primes[j] in bad then
980
Append(~K, "bad");
981
else
982
ER:=Reduction(EllipticCurve([M2[i][2], M2[i][3]]), 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][1] cat:= " "*alphabet[k];
996
elif list[i][1]*" "*alphabet[k] eq list[i-1][1] then
997
t:=true;
998
for j in [8..#list[1]] 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][1] cat:= " "*alphabet[k];
1007
else
1008
k +:= 1;
1009
list[i][1] cat:= " "*alphabet[k];
1010
end if;
1011
else
1012
k := 1;
1013
list[i][1] 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][2];
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][3];
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[1]] 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[1] 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;
1079
end function;
1080
1081
1082
1083
/***
1084
Computes the same table of probable isogeny classes, this time saving to
1085
a file.
1086
Uses: makename, divideup.
1087
***/
1088
1089
procedure 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;
1100
end procedure;
1101
1102
1103
1104
/**********
1105
Miscellaneous.
1106
**********/
1107
1108
1109
/***
1110
Arbitrary curve generator. Gives you elldata of some curve
1111
over your field (i.e., produces <curve, j-invariant, conductor, torsion
1112
subgroup>). This is useful to have around to test things out, but is not
1113
used in any later function.
1114
***/
1115
1116
function 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
1132
return "please try again";
1133
end if;
1134
1135
end function;
1136