Sharedwww / merel-stein / merel-stein.mOpen in CoCalc
Author: William A. Stein
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
13intrinsic MerelNumberOfIsogenyClasses(MOG::SeqEnum, p::RngIntElt) -> RngIntElt
14{Returns the number of isogeny classes at level p.}
15   return #MOG[p]Eigenvectors;
16end intrinsic;
17
18intrinsic 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)];
29end intrinsic;
30
31intrinsic 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);
36end intrinsic;
37
38intrinsic 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!vDefiningPolynomial);
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]SupersingularBasisDefiningPolynomial;
70   bet := Roots(RR!ss_f)[1][1];         // first is good enough.
71   coor:=MOG[p]SupersingularBasisCoordinates;
72   ss_j:= [ Evaluate(RR!coor[n],bet) : n in [1..#coor] ];
73   FF<j>:= FieldOfFractions(RR);
74   return &+ [
75      FF!Evaluate(RR!vCoordinates[n],alp)           // n_e
76       / (FF!ss_j[n]-j)^u  : n in [1..#ss_j]
77   ];
78end 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////////////////////////////////////////////////////////////
87function 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;
128end function;
129
130intrinsic 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;
145end intrinsic;
146
147
148////////////////////////////////////////////////////////////
149// Criterion when p = 3 (mod 4):
150function 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;
171end function;
172
173intrinsic 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
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;
192end intrinsic;
193
194intrinsic 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   */
207end intrinsic;
208
209
210
211
212
213
214
215
216
217
218