Re: Galois subextensions question

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Wed, Oct 02, 2013 at 09:42:40PM +0200, Bill Allombert wrote:
> Please find a new version that require a much smaller precision.
> 
> For example for PSL_2(F_7) in A7:
> ? \p38
> ? subfieldgen(x^7-x-1,[[2,3,4,5,6,7,1],[2,1,6,4,5,3,7]])
> %1 = x^30-14*x^29-301*x^28-1704*x^27-9649*x^26-168011*x^25-2142926*x^24-17102447*x^23-95949120*x^22-408214362*x^21-1378809373*x^20-3806867893*x^19-8760613215*x^18-17029306969*x^17-28219492898*x^16-40113925202*x^15-49109267452*x^14-51893154569*x^13-47364587090*x^12-37322433255*x^11-25348790841*x^10-14800563655*x^9-7402148473*x^8-3155652345*x^7-1139066802*x^6-344626560*x^5-85962626*x^4-17172449*x^3-2605551*x^2-273198*x-14786

Unfortunately this result was wrong due to insufficient precision.
I made a new version that computes the cosets instead of using algdep.
In case of failure it returns the needed precision increase.
The function does not call polredbest anymore since it was too slow
for examples of large degree.

Now we get
? subfieldgen(x^7-x-1,[[2,3,4,5,6,7,1],[2,1,6,4,5,3,7]])
  ***   at top-level: subfieldgen(x^7-x-1,
  ***                 ^--------------------
  ***   in function subfieldgen: ...al(round(R,&e));if(e>-30,error("subfieldgen:
  ***                                                        ^--------------------
  ***   user error: subfieldgen: unsufficient precision, need 5 digits more
  ***   Break loop: type 'break' to go back to GP prompt
break>

? \p43
   realprecision = 57 significant digits (43 digits displayed)
? subfieldgen(x^7-x-1,[[2,3,4,5,6,7,1],[2,1,6,4,5,3,7]])
%1 = x^30-288*x^29+40248*x^28-3634896*x^27+238368348*x^26-12090987792*x^25+493438224264*x^24-16638578726056*x^23+472419847780446*x^22-11452556178452472*x^21+239526144232400032*x^20-4355890754737984416*x^19+69280765926110797724*x^18-967847798366672998528*x^17+11910414673089999597983*x^16-129339029196298511256428*x^15+1240237062597620501506141*x^14-10497610358411569516313888*x^13+78319076608189977324262530*x^12-513722353570168525479220272*x^11+2951323667778201593052474708*x^10-14771597021589079470808538168*x^9+63951156724965371121761482103*x^8-237199765999048612644577993548*x^7+744067337500256598779774612352*x^6-1939231831705235946277679897728*x^5+4094559150310256573712885276672*x^4-6744345377894977947626409558016*x^3+8150593351117763495186075873280*x^2-6445807317993780262285261438976*x+2510969139342816737669225578496
? factor(nfdisc([%,10^7]))
%2 = [-1,1;776887,15]

which is correct.

Cheers,
Bill.

mkorb(P,v)=
{
  my(L,n);
  L=List([v]);
  until(#L==n,
      n=#L;
      for(i=1,#P,
        for(j=1,#L,
          listput(L,L[j]*P[i])));
      listsort(L,1));
  L;
}

gencoset(P,n)=
{
  my(i=0, q = n!, Q, S=vector(q));
  P=apply(x->Vecsmall(x),P);
  Q=mkorb(P,Vecsmall(numtoperm(n,i))); u=q/#Q;
  vector(u,j,
    while(S[i+1],i++);
    if (j>1,Q=mkorb(P,Vecsmall(numtoperm(n,i))));
    for(o=1,#Q,S[1+permtonum(Vec(Q[o]))]=j);
    Q);
}

subfieldgen(P,S)=
{
  my(M,R,V=polroots(P),k=0,X=variable(P));
  M=gencoset(S,#V);
  until(issquarefree(R),
    k++;
    R=prod(l=1,#M,X-sum(i=1,#M[l], prod(j=1,k,V[M[l][i][j]]^j)));
    R=real(round(R,&e)); 
    if(e>-30,
       error("subfieldgen: unsufficient precision, need ",
             2+round((e+30)*log(2)/log(10))," digits more"));
    );
  R;
}

subred(P,S)=polredbest(subfieldgen(P,S));
/*
\p100
\\ C5=<(1,2,3,4,5)> in S_5:
subred(x^5-x-1,[[2,3,4,5,1]])
\\ D5=<(1,2,3,4,5),(2,5)(3,4)> in S5
subred(x^5-x-1,[[2,3,4,5,1],[1,5,4,3,2]])
\\ the trivial S5 in S6 (we get back the original field, of course)
subred(x^6-x-1,[[2,3,4,5,1,6],[2,1,3,4,5,6]])
\\ The nontrivial S5 in S6 <(1,2,3,4,6), (1,2)(3,4)(5,6)>
subred(x^6-x-1,[[2,3,4,6,5,1],[2,1,4,3,6,5]])
\\ The nontrivial A5 in S6 <(1,2,3,4,6), (1,4)(5,6)>
subred(x^6-x-1,[[2,3,4,6,5,1],[4,2,3,1,6,5]])
\\ PSL_2(F_7) in S7
subred(x^7-x-1,[[2,3,4,5,6,7,1],[2,1,6,4,5,3,7]])
\\ AGL_3(F_2) in S8
subred(x^8-x-1,[[8,3,2,5,4,7,6,1],[3,8,1,6,7,4,5,2],[5,6,7,8,1,2,3,4],[7,1,6,3,4,2,5,8],[3,1,2,5,6,4,7,8],[2,1,3,4,6,5,7,8]])
*/