6
$\begingroup$

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...

$\endgroup$
3
  • 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$
    – jmc
    Nov 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 Rivin
    Nov 21, 2013 at 13:47
  • $\begingroup$ Dear Igor Rivin, he definitely is! (Finishing his master's right now, if I am not mistaken.) $\endgroup$
    – jmc
    Nov 21, 2013 at 15:02

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\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$
    – Igor Rivin
    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$
    – Igor Rivin
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.