Csdrhrt

Question: How to quickly find explicit formula for roots of polynomials (solvable by radicals) like $f(x)=x^8+5992704x-304129728$?

My current approach is just a brute force - not very fast and convenient:

• observe that Galois group of above $f(x)$ is $C_2 wr S_4$, so one needs to find quartic polynomial $g(x)=x^4+cx^2+dx+e$ such that $f(x)$ splits into quadratic (and sextic) polynomial over it


• iterate over small integer triples $c,d,e$ until correct $g(x)$ is found


• to speed up the process I limited $g(x)$ to such that $Delta(g(x))$ divides $Delta(f(x))$ - here $Delta$ means discriminant

More explicitly, using GAP system:

x:=Indeterminate(Rationals, "x");

f:=x^8+5992704*x-304129728;

discrF:=Discriminant(f);



# define some arbitrary range of the c,d,e coefficients

for c in [-40..40] do

  for d in [1..6000] do

    for e in [-30000..30000] do

     # small perf trick, calculate discriminant

     # without actual construction of g(x)

     discrG:=256*e^3-128*c^2*e^2+144*c*d^2*e-27*d^4+16*c^4*e-4*c^3*d^2;

     if (discrG <> 0 and discrF mod discrG = 0) then

      g:=x^4+c*x^2+d*x+e;

      if IsIrreducible(g) then

        e:=AlgebraicExtension(Rationals,g);

        factors:=FactorsPolynomialAlgExt(e, f);

        if Size(factors) > 1 then

          Print("Success: g(x)=", g," : factors=", factors,"n");

        fi;

      fi;

     fi;

    od;

  od;

od;

Couple hours later...:

• $g(x)=x^4-34x^2+1632x-7871$


• $f(x)={ x^2+(-a^3/56-a^2/56+89a/56-1207/56)x+(3a^3/28+6a^2/7+153a/28+459/7) }times{x^6+(a^3/56+a^2/56-89a/56+1207/56)x^5+(3a^3/28+33a^2/14+153a/28+561/14)x^4+(-27a^3/14-153a^2/14+2907a/14-4743/14)x^3+(-153a^2-3060a+4437)x^2+(-153a^3/7+8415a^2/7+13617a/7-2078199/7)x+(-2754a^3-5508a^2+109242a-2465748) }$

where $g(a) = 0$

Now one can find (very long and fancy) explicit expression for roots of $f(x)$, using only $+$, $-$, $times$, $div$, and $sqrt{}$ operations.

Loosely related question: On solvable octic trinomials like $x^8-5x-5=0$

If I understand your question correctly, the abstract translation of your observation is that the Galois group is imprimitive, that is that the field of degree 8 defined by $f$ has a subfield of degree $2$ (over which it has degree $2$), that is over this subfield $f$ will have a quadratic factor.

Such subfields correspond to polynomial decompositions, that is pairs of polynomials $g,h$ such that $f(x)$ divides $g(h(x))$. The polynomial $g$ defines the subfield you are seeking, the polynomial $h$ expresses a root of $g$ in terms of a root of $f$.

In GAP, you can find such decompositions using the function DecomPoly. It takes a polynomial $f$ and returns a list of all possible decompositions (up to equality of the intermediate fields.

In your example, we indeed get the degree 2 factor you were seeking (and this is much faster than the hours you quote):

gap> DecomPoly(f);

[ [ x^4+273770356608*x^3+4408835773957146427392*x^2-      7845555523405311768791676626141184*x-986470018747508750165370725578689408242024448,

  3663*x^7-22492*x^6-364752*x^5-5179288*x^4-28801128*x^3+150835968*x^2+121269024*x-49235223744 ] ]

gap> g:=last[1][1];

x^4+273770356608*x^3+4408835773957146427392*x^2-  7845555523405311768791676626141184*x-986470018747508750165370725578689408242024448

gap> e:=AlgebraicExtension(Rationals,g);

<algebraic extension over the Rationals of degree 4>

gap> fe:=Value(f,X(e)); # write f over e

x_1^8+!5992704*x_1+(!-304129728)

gap> Factors(fe);

[ x_1^2+(-1/514753642938357559490856611217408*a^3-1/1141573548613903985664*a^2+1/233510010048*a+18)*x_1+1/1342011552*a,

  x_1^6+(1/514753642938357559490856611217408*a^3+1/1141573548613903985664*a^2-1/233510010048*a-18)*x_1^5+(-1/12256039117579941892639443124224*a^3-1/104457710330684024832*a^2+47/19459167504*a+408)*x_1^4+(5/14298712303843265541412683644928*a^3-1/26114427582671006208*a^2-9/926627024*a+1224)*x_1^3+(1/420550361877743104159196577792*a^3+1/932658127952535936*a^2-15/95388076*a-30600)*x_1^2+(-1/14501736616473900143420571648*a^3-1/112562187856340544*a^2+9/6578488*a+105264)*x_1+(-1/2416956102745650023903428608*a^3-1/8828406890693376*a^2-3/1644622*a+3246048) ]

The algorithm used by GAP is described (disclaimer: self-promotion) in

Hulpke, Alexander
Block systems of a Galois group, Experiment. Math. 4 (1995), no. 1, 1–9.

but there are by now better algorithms with

van Hoeij, Mark; Klüners, Jürgen; Novocin, Andrew
Generating subfields,
J. Symbolic Comput. 52 (2013), 17–34.

as far as I know the state of the art.