> < ^ From:

< ^ Subject:

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

> < [top]