Dear Gap Forum,
Stefan Kohl asked:
> Would it be in principle possible to give a valid algorithm for Galois group
> computation for arbitrary degrees,
This is certainly possible: Construct a polynomial $g$ which defines the
splitting field $L$ of $f$ and factor $g$ over $L$. It splits in linear
factors. The Galois group consists of those elements that map one (fixed)
root of $g$ to any of the other roots.
(If we denote one root of $g$ by $\alpha$ the linear factors express
all roots of $g$ as polynomials in $\alpha$, so we can compute with these.)
GAP3 provides a function `GaloisGroup' which does this in case $f$ already
spans a normal extension.
The problem however is that these polynomial factorizations become
enormously expensive and so practically the calculations can't be done
beyond degree 4 or 5.
One can improve on this algorithm, this and a complexity analysis has been
done in:
Landau, Susan: Polynomial time algorithms for Galois groups. EUROSAM 84
(Cambridge, 1984), 225--236, Lecture Notes in Comput. Sci., 174, Springer,
Berlin-New York, 1984.
The resulting algorithm does not require knowledge about permutation groups
and is even polynomial time, the time polynomial itself and the involved
constants however are ghastly so that again this is not of much practical
use. I'm not aware of any system which has it implemented.
(This is quite similar to polynomial factorization. A - famous - polynomial
time algorithm exists, but all systems I know use an exponential algorithm
because the break-even point is too high.)
> This might perhaps require a general algorithm for the construction of the
> transitive permutation groups of a given degree - does such an algorithm
> exist,
Yes! (see http://www-gap.dcs.st-and.ac.uk/~ahulpke/publ.html#thesis )
Finally let me take the opportunity and update a remark in a recent mail of
mine: Katharina Geissler, who wrote the Galois Group identification in
KANT, told me that the most recent version now uses p-adic approximation and
thus is free from the rounding problems I alluded to and thus gives proven
results!
I hope this is of help,
Alexander Hulpke
Miles-Receive-Header: reply