Function: galoisinit
Section: number_fields
C-Name: galoisinit
Prototype: GDG
Help: galoisinit(pol,{den}): pol being a polynomial or a number field as
 output by nfinit defining a Galois extension of Q, compute the Galois group
 and all necessary information for computing fixed fields. den is optional
 and has the same meaning as in nfgaloisconj(,4)(see manual).
Description:
 (gen, ?int):gal        galoisinit($1, $2)
Doc: computes the Galois group
 and all necessary information for computing the fixed fields of the
 Galois extension $K/\Q$ where $K$ is the number field defined by
 $\var{pol}$ (monic irreducible polynomial in $\Z[X]$ or
 a number field as output by \tet{nfinit}). The extension $K/\Q$ must be
 Galois with Galois group ``weakly'' super-solvable, see below;
 returns 0 otherwise. Hence this permits to quickly check whether a polynomial
 of order strictly less than $36$ is Galois or not.

 The algorithm used is an improved version of the paper
 ``An efficient algorithm for the computation of Galois automorphisms'',
 Bill Allombert, Math.~Comp, vol.~73, 245, 2001, pp.~359--375.

 A group $G$ is said to be ``weakly'' super-solvable if there exists a
 normal series

 $\{1\} = H_0 \triangleleft H_1 \triangleleft \cdots \triangleleft H_{n-1}
 \triangleleft H_n$

 such that each $H_i$ is normal in $G$ and for $i<n$, each quotient group
 $H_{i+1}/H_i$ is cyclic, and either $H_n=G$ (then $G$ is super-solvable) or
 $G/H_n$ is isomorphic to either $A_4$ or $S_4$.

 In practice, almost all small groups are WKSS, the exceptions having order
 36(1 exception), 48(2), 56(1), 60(1), 72(5), 75(1), 80(1), 96(10) and $\geq
 108$.

 This function is a prerequisite for most of the \kbd{galois}$xxx$ routines.
 For instance:

 \bprog
 P = x^6 + 108;
 G = galoisinit(P);
 L = galoissubgroups(G);
 vector(#L, i, galoisisabelian(L[i],1))
 vector(#L, i, galoisidentify(L[i]))
 @eprog

 The output is an 8-component vector \var{gal}.

 $\var{gal}[1]$ contains the polynomial \var{pol}
 (\kbd{\var{gal}.pol}).

 $\var{gal}[2]$ is a three-components vector $[p,e,q]$ where $p$ is a
 prime number (\kbd{\var{gal}.p}) such that \var{pol} totally split
 modulo $p$ , $e$ is an integer and $q=p^e$ (\kbd{\var{gal}.mod}) is the
 modulus of the roots in \kbd{\var{gal}.roots}.

 $\var{gal}[3]$ is a vector $L$ containing the $p$-adic roots of
 \var{pol} as integers implicitly modulo \kbd{\var{gal}.mod}.
 (\kbd{\var{gal}.roots}).

 $\var{gal}[4]$ is the inverse of the Vandermonde matrix of the
 $p$-adic roots of \var{pol}, multiplied by $\var{gal}[5]$.

 $\var{gal}[5]$ is a multiple of the least common denominator of the
 automorphisms expressed as polynomial in a root of \var{pol}.

 $\var{gal}[6]$ is the Galois group $G$ expressed as a vector of
 permutations of $L$ (\kbd{\var{gal}.group}).

 $\var{gal}[7]$ is a generating subset $S=[s_1,\ldots,s_g]$ of $G$
 expressed as a vector of permutations of $L$ (\kbd{\var{gal}.gen}).

 $\var{gal}[8]$ contains the relative orders $[o_1,\ldots,o_g]$ of
 the generators of $S$ (\kbd{\var{gal}.orders}).

 Let $H_n$ be as above, we have the following properties:

 \quad\item if $G/H_n\simeq A_4$ then $[o_1,\ldots,o_g]$ ends by
 $[2,2,3]$.

 \quad\item if $G/H_n\simeq S_4$ then $[o_1,\ldots,o_g]$ ends by
 $[2,2,3,2]$.

 \quad\item for $1\leq i \leq g$ the subgroup of $G$ generated by
 $[s_1,\ldots,s_g]$ is normal, with the exception of $i=g-2$ in the
 $A_4$ case and of $i=g-3$ in the $S_A$ case.

 \quad\item the relative order $o_i$ of $s_i$ is its order in the
 quotient group $G/\langle s_1,\ldots,s_{i-1}\rangle$, with the same
 exceptions.

 \quad\item for any $x\in G$ there exists a unique family
 $[e_1,\ldots,e_g]$ such that (no exceptions):

 -- for $1\leq i \leq g$ we have $0\leq e_i<o_i$

 -- $x=g_1^{e_1}g_2^{e_2}\ldots g_n^{e_n}$

 If present $den$ must be a suitable value for $\var{gal}[5]$.