Open in CoCalc
1
////////////////////////////////////////////////////////////////////////
2
// //
3
// merel-stein.m -- MAGMA code for verifying conditions 1)-3) in the //
4
// paper "The field generated by the points of small prime order on //
5
// an elliptic curve." //
6
// //
7
////////////////////////////////////////////////////////////////////////
8
9
// Note: The sequence MOG, LChiZero, and Anomalous are all defined
10
// in other files available with this file.
11
12
13
intrinsic MerelNumberOfIsogenyClasses(MOG::SeqEnum, p::RngIntElt) -> RngIntElt
14
{Returns the number of isogeny classes at level p.}
15
return #MOG[p]`Eigenvectors;
16
end intrinsic;
17
18
intrinsic MerelNumberOfEmbeddings(MOG::SeqEnum,
19
p::RngIntElt,
20
IsogenyClass::RngIntElt
21
: Factors := true) -> RngIntElt
22
{Number of factors mod p of the polynomial defining IsogenyClass i.}
23
R := PolynomialRing(GF(p));
24
f := R ! MOG[p]`Eigenvectors[IsogenyClass]`DefiningPolynomial;
25
if Factors then
26
return #Factorization(f);
27
end if;
28
return &+[Degree(a[1]) : a in Factorization(f)];
29
end intrinsic;
30
31
intrinsic MerelDimension(MOG::SeqEnum,
32
p::RngIntElt,
33
IsogenyClass::RngIntElt) -> RngIntElt
34
{Number of factors mod p of the polynomial defining IsogenyClass i.}
35
return Degree(MOG[p]`Eigenvectors[IsogenyClass]`DefiningPolynomial);
36
end intrinsic;
37
38
intrinsic MerelIota(MOG::SeqEnum,
39
p::RngIntElt,
40
IsogenyClass::RngIntElt,
41
u::RngIntElt,
42
Embedding::RngIntElt
43
: Factors := true) -> .
44
{Given a level p <= 997, an IsogenyClass, an integer u,
45
and an Embedding number <= MerelNumberOfEmbeddings(p,IsogenyClass),
46
return the rational function sum n_E/((j-j(E))^u. This function
47
is defined in section 1.4 of Merel's paper "Sur la nature
48
non-cyclotomique des points d'ordre fini des courbes elliptiques."
49
The optional parameter Factors controls how the Embedding number
50
is defined.}
51
R := PolynomialRing(GF(p));
52
v := MOG[p]`Eigenvectors[IsogenyClass];
53
fac := Factorization(R!v`DefiningPolynomial);
54
if Factors then
55
f := R!fac[Embedding][1];
56
i := 1;
57
else
58
i := 1;
59
while Embedding gt Degree(fac[i][1]) do
60
Embedding -:= Degree(fac[i][1]);
61
i +:= 1;
62
end while;
63
f := R!fac[i][1];
64
i := Embedding;
65
end if;
66
Fq<a>:= GF(p^LCM(2,Degree(f))); // need the s.s j-invariants.
67
RR := PolynomialRing(Fq);
68
alp := Roots(RR!f)[i][1]; // assuming output of Roots sorted.
69
ss_f:= MOG[p]`SupersingularBasis`DefiningPolynomial;
70
bet := Roots(RR!ss_f)[1][1]; // first is good enough.
71
coor:=MOG[p]`SupersingularBasis`Coordinates;
72
ss_j:= [ Evaluate(RR!coor[n],bet) : n in [1..#coor] ];
73
FF<j>:= FieldOfFractions(RR);
74
return &+ [
75
FF!Evaluate(RR!v`Coordinates[n],alp) // n_e
76
/ (FF!ss_j[n]-j)^u : n in [1..#ss_j]
77
];
78
end intrinsic;
79
80
////////////////////////////////////////////////////////////
81
// Criterion when p = 1 (mod 4):
82
// It turns out that this more complicated criterion, which
83
// was mentioned in Merel's first paper [2], is not needed.
84
// We instead only must verify the criterion
85
// "for p=3 (mod 4)" below.
86
////////////////////////////////////////////////////////////
87
function MerelCriterion1Degree(MOG, LChiZero, Anomalous, p, d)
88
assert p mod 4 eq 1;
89
assert d gt 0 and (p-1) mod d eq 0;
90
assert d ne 2;
91
92
NumberOfClasses := MerelNumberOfIsogenyClasses(MOG,p);
93
Anom := Anomalous[p];
94
for iso1 in [1..NumberOfClasses] do
95
for iso2 in [iso1..NumberOfClasses] do
96
if Index(LChiZero[p][iso1],d) eq 0 and
97
Index(LChiZero[p][iso2],d) eq 0 then
98
for embedding1 in
99
[1..MerelNumberOfEmbeddings(MOG,p,iso1 : Factors:=false)] do
100
for embedding2 in
101
[1..MerelNumberOfEmbeddings(MOG,p,iso2 : Factors:=false)] do
102
f11 := MerelIota(MOG, p, iso1, 1, embedding1 : Factors := false);
103
f12 := MerelIota(MOG, p, iso1, 2, embedding1 : Factors := false);
104
f21 := MerelIota(MOG, p, iso2, 1, embedding2 : Factors := false);
105
f22 := MerelIota(MOG, p, iso2, 2, embedding2 : Factors := false);
106
// Magma is clever enough to force the following to
107
// to take place in a common finite extension of
108
// the finite fields over which each fij is defined.
109
f := f11*f22 - f12*f21;
110
//"f11=",f11;
111
//"f12=",f12;
112
//"f21=",f21;
113
//"f22=",f22;
114
//"f=",f;
115
vals := [Evaluate(f,j) : j in Anom];
116
if Index(vals,0) eq 0 then
117
printf "verified with A=%o%o(dim=%o), B=%o%o(dim=%o)\n",
118
p, ToIsogenyCode(iso1), MerelDimension(MOG,p,iso1),
119
p, ToIsogenyCode(iso2), MerelDimension(MOG,p,iso2);
120
return true;
121
end if;
122
end for;
123
end for;
124
end if;
125
end for;
126
end for;
127
return false;
128
end function;
129
130
intrinsic MerelCriterion1(MOG::SeqEnum, LChiZero::SeqEnum,
131
Anomalous::SeqEnum, p::RngIntElt
132
) -> BoolElt
133
{}
134
assert p mod 4 eq 1;
135
"--------->>>>>> p =",p, " <<<<<<<---------";
136
for d in [e : e in Divisors(p-1) | e ne 2] do
137
printf "deg(chi)=%3o ",d;
138
if not MerelCriterion1Degree(MOG, LChiZero, Anomalous,p,d) then
139
"FAILED!";
140
return false;
141
end if;
142
end for;
143
"TRUE.";
144
return true;
145
end intrinsic;
146
147
148
////////////////////////////////////////////////////////////
149
// Criterion when p = 3 (mod 4):
150
function MerelCriterion3Degree(MOG, LChiZero, Anomalous, p, d)
151
/* assert p mod 4 eq 3; */ // commented out, because this
152
// criterion is also valid for p=1(mod 4).
153
assert d gt 0 and (p-1) mod d eq 0;
154
NumberOfClasses := MerelNumberOfIsogenyClasses(MOG,p);
155
Anom := Anomalous[p];
156
for iso in [1..NumberOfClasses] do
157
if Index(LChiZero[p][iso],d) eq 0 then // L(iso,[d],1) =/= 0.
158
for embedding in [1..MerelNumberOfEmbeddings(MOG,p,iso)] do
159
f := MerelIota(MOG, p, iso, 1, embedding);
160
vals := [Evaluate(f,j) : j in Anom];
161
if Index(vals,0) eq 0 then
162
printf "verified with %o%o, (dim=%o)\n",
163
p, ToIsogenyCode(iso),
164
MerelDimension(MOG,p,iso);
165
return true;
166
end if;
167
end for;
168
end if;
169
end for;
170
return false;
171
end function;
172
173
intrinsic MerelCriterion3(MOG::SeqEnum, LChiZero::SeqEnum,
174
Anomalous::SeqEnum, p::RngIntElt
175
) -> BoolElt
176
{}
177
/* assert p mod 4 eq 3; */
178
"--------->>>>>> p =",p, " <<<<<<<---------";
179
for d in Divisors(p-1) do
180
printf "deg(chi)=%3o ",d;
181
if p mod 4 eq 1 and d eq 2 then
182
"Quadratic, hence skipping...";
183
else
184
if not MerelCriterion3Degree(MOG, LChiZero, Anomalous,p,d) then
185
"FAILED!";
186
return false;
187
end if;
188
end if;
189
end for;
190
"TRUE.";
191
return true;
192
end intrinsic;
193
194
intrinsic MerelCriterion(MOG::SeqEnum, LChiZero::SeqEnum,
195
Anomalous::SeqEnum, p::RngIntElt) -> BoolElt
196
{Verifies the criterion of Merel for the prime number p.
197
The sequence MOG, LChiZero, and Anomalous are all defined
198
in other files available with this file.}
199
assert IsPrime(p) and p ge 11;
200
return MerelCriterion3(MOG,LChiZero,Anomalous,p);
201
/* because the 3 mod 4 criterion suffices for both cases, as it turns out.
202
case p mod 4:
203
when 1: return MerelCriterion1(MOG,LChiZero,Anomalous,p);
204
when 3: return MerelCriterion3(MOG,LChiZero,Anomalous,p);
205
end case;
206
*/
207
end intrinsic;
208
209
210
211
212
213
214
215
216
217
218