Re: the minimal polynomial over the composite field

[macsyma <macsyma@yahoo.co.jp>]

> Bill Allombert on Fri, 23 Aug 2019 12:17:19 +0200
> Could you give more background about why you would like to compute that ?
My goal is to create a procedure based on Galois theory 
that expresses all roots of given polynomial by radicals 
(mentioned earlier K is the base field of the tower of radical extensions), 
and I have already written a code using PARI/GP,
GAP (for getting the composition series), 
Nemo/Julia and Maxima (for the calculations with algebraic numbers 
defined by multivariate polynomials). 
It has performance comparable to MAGMA's SolveByRadicals() 
and it don't make a composite reduction like GAP's RootsOfPolynomialAsRadicals(). 
However, I posted some parts of processing in search of room for improvement.

> In particular, are your polynomials g random ?
> (in your examples they ave very specific shapes which allow to do the
> computation nearly by hand).
The reason for selecting trivial (in a sense) x^n-2 as an example is 
simply the shape is concise. The input polynomial for my procedure is
in principle arbitrary as long as it is solvable and irreducibele over Q. 
For example, if we input a polynomial in your database
http://pari.math.u-bordeaux.fr/galpol/30/1/index.html , 
it outputs
http://macsyma.starfree.jp/maxima/galpol30.txt ,
where A is a primitive element of a splitting field of the input, 
[p,v] = [the defining polynomial of v, a radical or a root of unity], 
since it is too long, the representation of roots by A is omitted.

> Apparently your code factor first over Q(zeta_p+(zeta_p)^-1) and after
> over Q(zeta_p). Does this give a measurable improvement ?
An example of improvement by dividing into steps is

? g=nfsplitting(x^35-2,840);
? tst002(g);
time = 24,721 ms.
? tst003(g);
time = 33,824 ms.

where

tst002(gx) =
{
  my(P = select(r -> r - 2, factor(poldegree(gx))[, 1]),
     p, q, s, t, u, A = gx, gi);
  for(i = 1, #P,
    q = polcyclo(p = P[i], u = eval(concat("c", p)));
    [s, t] = nfsubfields(q)[-2..-2][1];
    gi = nffactor(q, subst(liftpol(nffactor(s, gx)[1, 1]), u, t))[1, 1];
    A = if(#variables(A) == 1, gi, if(#variables(gi) == 1, A, RgX_gcd_simple(A, gi) )));
  liftpol(A/pollead(A))
};

tst003(gx) =
{
  my(P = select(r -> r - 2, factor(poldegree(gx))[, 1]),
     p, q, A = gx, gi);
  for(i = 1, #P,
    q = polcyclo(p = P[i], u = eval(concat("c", p)));
    gi = nffactor(q, gx)[1, 1];
    A = if(#variables(A) == 1, gi, if(#variables(gi) == 1, A, RgX_gcd_simple(A, gi) )));
  liftpol(A/pollead(A))
};

(In general, the factors extracted by tst002() and tst003() are different.)

> If yes why> not try all the subfields from the smallest to the largest in turn ?
I don't know how best to select subfields,
but too many steps would be counterproductive,
so I currently insert the second subfield step only.

macsyma