There has been some discussion of computing the Galois group of a polynomial over the integers, but I can't seem to find any results, or even a question of what the complexity of this might be. For example, I assume that this is NOT in NP, and IS NP-hard (at least), but am not aware of any reduction...
-
3$\begingroup$ One of my fellow students wrote a bachelor's thesis on computing the size of the Galois group: math.leidenuniv.nl/nl/theses/311 . I realise that the size forgets the whole group structure, but I still thought this might be relevant as comment. $\endgroup$– jmcNov 21, 2013 at 8:11
-
$\begingroup$ @jmc I had actually seen this thesis before (thanks to Google), and was quite impressed! Hope your colleague is still in mathematics! $\endgroup$– Igor RivinNov 21, 2013 at 13:47
-
$\begingroup$ Dear Igor Rivin, he definitely is! (Finishing his master's right now, if I am not mistaken.) $\endgroup$– jmcNov 21, 2013 at 15:02
1 Answer
According to a paper Upper bounds on the complexity of some Galois Theory problems by Arvind and Kurur here, a theorem of Landau gives an exponential upper bound in the size of the polynomial under a certain definition of size. More precisely, her theorem gives a polynomial bound in terms of the size of the Galois group and the size of the polynomial. But the size of the group can be exponential in the size of the polynomial. They show if the Galois group is solvable, then the order can be computed by a randomized polynomial time algorithm with an NP oracle.
This paper gives some complexity bounds on computing the order (they show this is in $P^{\# P}$ see the complexity zoo). Google seems to say there is a paper proving that nilpotence of the Galois group is decidable in polynomial time.
-
$\begingroup$ The Landau in question is Susan Landau, so "her theorem". But anyway, as you say, the size of the Galois group can be (and usually is) $n!$ so this is not a particularly useful bound. Landau and Gary Miller (if memory serves) had a rather complicated algorithm computing solvable Galois groups in polynomial time thirty years ago. I believe they computed the structure, not just the order. I do recall seeing something about nilpotent groups, but in some sense the most interesting case is of [nonabelian] simple groups (which are not $A_n$ -- that can be done in poly time). $\endgroup$ Nov 21, 2013 at 13:52
-
$\begingroup$ n! is not so bad as long as you don't use unary. This is why they get exponential. $\endgroup$ Nov 21, 2013 at 14:08
-
$\begingroup$ Unfortunately, the order of the group (in Landau's work) is the degree of extension you have to factor [the resolvent] over, so you can only wish unary was your only problem... $\endgroup$ Nov 21, 2013 at 14:20
-
1$\begingroup$ The Landau-Miller reference is Solvability by radicals is in polynomial time, J. Comput. System Sci. 30 (1985), no. 2, 179–208, MR0801822 (86k:12001). $\endgroup$ Nov 21, 2013 at 22:59