Re: Fastest way to determine whether a simple extension is Galois, starting from a polynomial

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

On Tue, Jan 21, 2020 at 08:32:49PM +0100, Ricardo Buring wrote:
> Dear pari-users,
> 
> I notice that running e.g.
> 
>     length(nfgaloisconj(x^29 - 10*x + 13)) == 29
> 
> is much faster than
> 
>     length(nfgaloisconj(nfinit(x^29 - 10*x + 13))) == 29
> 
> Are both of these valid ways to discover that Q[x]/(x^29 - 10*x + 13)
> is not Galois? And do these two tests give the same result general?
> The documentation of nfgaloisconj only states that passing a
> polynomial is allowed; does it also mean that the answer to both
> questions is yes?
> 
> I am asking because SageMath uses the latter (slower) test for degrees >= 13.

I want to add that this method is not optimal.
What one should do instead is
-- call numberofconjugates(pol, 2) to get an upperbound on
the number of automorphisms
-- If the upperbound is < deg(pol) return "not Galois"
-- otherwise check it is actually Galois with nfgaloisconj.

What  length(nfgaloisconj(pol)) do is:
-- call numberofconjugates(pol, 2) to get an upperbound on
the number of automorphisms
-- If the upperbound is == 1 return "not Galois"
-- otherwise compute the exact number of automorphisms.

which is much slower when the upperbound is > 1 but < degpol.

Cheers,
Bill