/* Description : Prime degree isogenies of elliptic curves over number fields Author : Nicolas Billerey (2017-05-03, initial implementation) Maintainer : Nicolas Billerey Based on Th\'eor\`emes 2.4 and 2.8 of the following article: N. Billerey, Crit\`eres d'irr\'eductibilit\'e pour les repr\'esentations des courbes elliptiques, Int. J. Number Theory 7 (2011), no. 4, 1001-1032. Tested with: PARI/GP 2.9.1 Main Function : ellisoprimedeg Help : ellisoprimedeg(E): E being an elliptic curve over the number field E.nf, returns a finite set of primes that contains the degrees of the prime degree isogenies of E defined over E.nf provided that E does not have CM. In other words, under the non-CM assumption, ellisoprimedeg(E) returns a finite set that contains all primes p for which the mod p representation of the absolute Galois group of E.nf acting on the p-torsion E[p] is reducible. (for curves over enter nfinit(x) for the base field) FIX ME : The command ellisoprimedeg may return a set that contains more primes than those of interest (increasing the parameter "prec" may help to discard such fake reducible primes though). TO DO : 1) Code the certification step, that is check that each prime returned is indeed the degree of K-rational isogeny of E (here K=E.nf). 2) Output the corresponding isogenies and isogenous curves. 3) Extend this to arbitrary cyclic isogenies (not necessarily of prime degree). (See command ellisomat for rational elliptic curves.) EXAMPLES : \\ Elliptic curve over Q with CM over C and a rational isogeny of degree 163 E = ellinit([0,0,1,-2174420,1234136692],nfinit(x)); ellisoprimedeg(E); \\ Elliptic Curve 529.15-a1 over Number Field 5.5.14641.1 in LMFDB K = nfinit(a^5 - a^4 - 4*a^3 + 3*a^2 + 3*a - 1); E = ellinit([a^2 - 1, -a^4 + 5*a^2 - a - 5, a^3 - 3*a, -9701*a^4 + 4825*a^3 + 37011*a^2 - 14694*a - 30397, 683650*a^4 - 332513*a^3 - 2681517*a^2 + 978125*a + 2147146],K); ellisoprimedeg(E) %8 = [2, 5] \\ Elliptic Curve 3364.2-c1 over Number Field 2.2.5.1 in LMFDB K = nfinit(phi^2 - phi - 1); E = ellinit([phi + 1, phi + 1, phi + 1, 57314*phi - 158565, -17645583*phi + 21953067],K); ellisoprimedeg(E) %5 = [17] \\ Elliptic Curve 385.1-A1 over Number Field 3.1.23.1. See also Example 4.4 in \\ Donnelly, Steve; Gunnells, Paul E.; Klages-Mundt, Ariah; Yasaki, Dan \\ A table of elliptic curves over the cubic field of discriminant −23. Exp. Math. 24 (2015), no. 4, 375–390. K = nfinit(a^3 - a^2 + 1); E = ellinit([a^2 + 1, -a^2 + a - 1, 0, 1, 0],K); ellisoprimedeg(E) %17 = [2, 3] \\ Example 4.4 of Billerey, Crit\`eres d'irr\'eductibilit\'e pour les repr\'esentations des courbes elliptiques, \\ Int. J. Number Theory 7 (2011), no. 4, 1001-1032. \\ For that specific (non-CM) Q-curve the "B-algorithm" (based on Th\'eor\`eme 2.4 in loc. cit.) fails \\ to find a finite list for the possible prime degree isogenies. Try ellisoBbound(E). \\ Hence we use the "R-algorithm" (based on Th\'eor\`eme 2.8). L=bnfinit(polcompositum(x^2+3,x^2+7)[1]); sqrt_3=1/8*x^3 + 2*x; \\ square root of -3 in L sqrt_7=1/8*x^3 + 3*x; \\ square root of -7 in L sqrt21=-sqrt_3*sqrt_7; a4=81/4*(69+43*sqrt_3+29*sqrt_7+17*sqrt21); a6=162*(207-84*sqrt_3-54*sqrt_7+46*sqrt21); E=ellinit([a4,a6],L); ellisoprimedeg(E) %16 = [2, 3, 5] \\ If the curve has over the base field, the algorithm fails and returns the following "error" message : \\ "Failed to bound the reducible primes... Is the curve CM ?" K = nfinit(i^2 + 1); E = ellinit([i + 1, i, i, 0, 0],K); ellisoprimedeg(E); */ \\ Computes the star product of polynomials p and q as defined in Section 2 of loc. cit. starlaw(p,q)={ my(P,Q,QQ); P=subst(p,variable(p),z); Q=subst(q,variable(q),x); QQ=z^poldegree(q)*subst(Q,x,x/z); return(polresultant(P,QQ,z)); } \\ Given a polynomial p and an integer r, computes the polynomial p^{(r)} defined in Lemme 2.2 startor(p,r)={ my(psir); psir=x^r-1; return(substpol(starlaw(p,psir),x^r,x)); } \\ Given a polynomial p and an integer r, returns the polynomial p^{*r}=p*p*...*p (r-th star iterate of p). stariter(p,r)={ my(politer); politer=x-1; for(k=1,r,politer=starlaw(politer,p)); return(politer); } \\ Characteristic polynomial of the Frobenius at prime ideal pr acting on the Tate module of E ellcharpoly(E,pr)={ my(nf); nf=E.nf; return(x^2-ellap(E,pr)*x+idealnorm(nf,pr)); } \\ Given a prime ideal pr in a number field K, computes the minimal \\ polynomial of g where g is the generator of pr^h (here h denotes the class number of K) \\ as given by the command bnfisprincipal. ellminpoly(K,pr)={ my(bnf,h); bnf=bnfinit(K.pol); h=bnf.clgp.no; return(minpoly(subst(bnf.zk*bnfisprincipal(bnf,idealpow(bnf,pr,h))[2],variable(bnf.pol),Mod(variable(bnf.pol),bnf.pol)))) } \\ Given E and a "good" prime l (in the terminology of loc. cit.), returns [starl,listcharpoly,B] \\ where starl is the polynomial P_l^*, listcharpoly is the list of characteristic polynomials of \\ Frobenius at primes above l, and B is the integer B_l. stardataB(E,l)={ my(nf,d,starl,dec,listcharpoly,pr,q); nf=E.nf; d=poldegree(nf.pol); starl=x-1; dec=idealprimedec(nf,l); listcharpoly=[]; for(i=1,matsize(dec)[2], pr=dec[i]; q=ellcharpoly(E,pr); starl=starlaw(starl,startor(q,12*pr[3])); listcharpoly=setunion(listcharpoly,[q]); ); return([starl,listcharpoly,prod(k=0,floor(d/2),subst(starl,x,l^(12*k)))]); } \\ Given E and a good prime ideal pr, returns [polchar,R] \\ where polchar is the characteristic polynomaial of E at pr, \\ and R is the integer R_pr defined in Th\'eor\`eme 2.8. stardataR(E,pr)={ my(nf,bnf,d,h,pol,politer,polchar); nf=E.nf; bnf=bnfinit(nf.pol); d=poldegree(bnf.pol); h=bnf.clgp.no; pol=ellminpoly(bnf,pr); politer=prod(k=0,floor(d/2),stariter(startor(pol,12),k)); polchar=ellcharpoly(E,pr); return([polchar,polresultant(startor(polchar,12*h),politer)]); } \\ Given a set of primes S and a list of characteristic polynomials of Frobenius elements, \\ returns S deprived of the primes p for which at least one of the polynomials is irreducible mod p. ellisoclean(S,L)={ my(R,p,Lp); R=[]; for(i=1,#S, p=S[i]; Lp=apply(polisirreducible,Mod(L,p)); if(Lp==vector(#L),R=setunion(R,[p])); ); return(R); } \\ Given a curve E, returns (if possible) a set that contains all reducible primes \\ using the "B-algorithm" (based on Th\'eor\`eme 2.4). ellisoBbound(E,{bound=200},{prec=250})={ my(nf,faN,badprimes,S1,S,l0,L,B,S1current,starl,charpolys,Bell,S2); nf=E.nf; faN=ellglobalred(E)[4][,1]~; badprimes=apply(x->x.p,faN); S1=setunion(factor(6*nf.disc^2)[,1]~,badprimes); S=S1; l0=2; while((setsearch(badprimes,l0)||stardataB(E,l0)[3]==0)&(l0=bound,return([0])); \\ Failed to bound reducible primes with the "B-algorithm". [L,B]=[stardataB(E,l0)[2],l0*stardataB(E,l0)[3]]; S1current=S1; forprime(l=l0+1,l0+prec, if(setsearch(badprimes,l)==0&S<>[], [starl,charpolys,Bell]=stardataB(E,l); L=setunion(L,charpolys); if(Bell!=0,B=gcd(B,l*Bell);S2=factor(B)[,1]~;S=setunion(S1current,S2);S=ellisoclean(S,L);S1current=setintersect(S,S1current); ))); return(S); } \\ Given a curve E, returns (if possible) a set that contains all reducible primes \\ using the "R-algorithm" (based on Th\'eor\`eme 2.8). ellisoRbound(E,{bound=200},{prec=250})={ my(nf,faN,badprimes,S1,S,l0,R0,i,dec,pr,L,R,S1current,Pq,Rq,S2); nf=E.nf; faN=ellglobalred(E)[4][,1]~; badprimes=apply(x->x.p,faN); S1=setunion(factor(6*nf.disc^2)[,1]~,badprimes); S=S1; l0=2; R0=0; while((l0=bound,return([0])); L=[stardataR(E,pr)[1]]; R=l0*stardataR(E,pr)[2]; S1current=S1; forprime(l=l0+1,l0+prec, if(setsearch(badprimes,l)==0&S<>[], dec=idealprimedec(nf,l); for(i=1,matsize(dec)[2], pr=dec[i]; [Pq,Rq]=stardataR(E,pr); L=setunion(L,[Pq]); if(Rq!=0,R=gcd(R,l*Rq);S2=factor(R)[,1]~;S=setunion(S1current,S2);S=ellisoclean(S,L);S1current=setintersect(S,S1current); )))); return(S); } \\ Main function. Returns a set that contains all prime degrees of prime degree isogenies of E over E.nf. ellisoprimedeg(E,{bound=200},{prec=250})={ my(S); S=ellisoBbound(E,bound,prec); if(S<>[0],return(S)); S=ellisoRbound(E,bound,prec); if(S<>[0],return(S),"Failed to bound the reducible primes... Is the curve CM ?"); }