Re: Galois subextensions question

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

On Mon, Sep 30, 2013 at 08:07:37PM -0500, Ariel Pacetti wrote:
> 
> Dear Pari users,
> 
> suppose I start with a degree n (say n small) polynomial for which I
> know the Galois closure is the whole S_n (this is not needed, but to
> easy the question). Then if I take any subgroup of S_n, there is an
> extension of Q fixed by this subgroup. Is there a way to compute
> such extension in GP without computing the whole Galois closure?
> (this is of huge dimension!). I couldn't find anything in this
> direction (since the original extension is not Galois).

I tried to solve the problem using resolvent polynomials.
I really need to find and read papers how to compute polynomials
invariants by some given group, but still I have made an attempt.

Please find a script with a function
subfieldgen(P,S) that takes a polynomial of degree n and a set of permutation
over 1..n and return a polynomial for the requested field, assuming the
precision is high enough (it uses algdep, since I did not implement coset
computation).

Some examples:
? \p1000
   realprecision = 1001 significant digits (1000 digits displayed)
1) C5=<(1,2,3,4,5)> in S_5:
? subfieldgen(x^5-x-1,[[2,3,4,5,1]])
%1 = x^24-8*x^23+36*x^22-120*x^21+322*x^20-728*x^19+1353*x^18-1992*x^17+2086*x^16-654*x^15-2697*x^14+7552*x^13-10969*x^12+7513*x^11+5959*x^10-29088*x^9+47425*x^8-44550*x^7+20627*x^6+12434*x^5-26272*x^4+15863*x^3-110*x^2-9761*x+5877

2) D5=<(1,2,3,4,5),(2,5)(3,4)>
? subfieldgen(x^5-x-1,[[2,3,4,5,1],[1,5,4,3,2]])
%2 = x^12-6*x^11-21*x^10+160*x^9-172*x^8-338*x^7+653*x^6-38*x^5-210*x^4-264*x^3+84*x^2+151*x+39

3) the trivial S5 in S6 (we get back the original field, of course)
? subfieldgen(x^6-x-1,[[2,3,4,5,1,6],[2,1,3,4,5,6]])
%3 = x^6-x-1

? \p4000
   realprecision = 4007 significant digits (4000 digits displayed)
4) The nontrivial S5 in S6 <(1,2,3,4,6), (1,2)(3,4)(5,6)>
? subfieldgen(x^6-x-1,[[2,3,4,6,5,1],[2,1,4,3,6,5]])
%4 = x^6-x^5-10*x^4+246*x^3-872*x^2+1099*x-468

5) The nontrivial A5 in S6 <(1,2,3,4,6), (1,4)(5,6)>
? subfieldgen(x^6-x-1,[[2,3,4,6,5,1],[4,2,3,1,6,5]])
%5 = x^12-60*x^10+1230*x^8-9740*x^6+22425*x^4-23381*x^2+6400

Cheers,
Bill.

mkgroup(P)=
{
  my(L,n);
  P=apply(x->Vecsmall(x),P);
  L=List([P[1]^0]);
  until(#L==n,
      n=#L;
      for(i=1,#P,
        for(j=1,#L,
          listput(L,P[i]*L[j])));
      listsort(L,1));
  L;
}
subfieldgen(P,S)=
{
  S=mkgroup(S);
  my(R,V=polroots(P),k=0,d=(#V)!/#S);
  until(poldegree(R)==d && polisirreducible(R),
    k++;
    R=algdep(prod(i=1,#S,sum(j=1,k,j*V[S[i][j]])),d);
    if (abs(pollead(R))!=1,error("subfieldgen: unsufficient precision"));
    );
  polredbest(R);
}

/* Examples
\p1000
\\ C5=<(1,2,3,4,5)> in S_5:
subfieldgen(x^5-x-1,[[2,3,4,5,1]])
\\ D5=<(1,2,3,4,5),(2,5)(3,4)> in S5
subfieldgen(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)
subfieldgen(x^6-x-1,[[2,3,4,5,1,6],[2,1,3,4,5,6]])
\p4000
\\ The nontrivial S5 in S6 <(1,2,3,4,6), (1,2)(3,4)(5,6)>
subfieldgen(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)>
subfieldgen(x^6-x-1,[[2,3,4,6,5,1],[4,2,3,1,6,5]])
*/