Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question asks how to tell whether two cubic polynomials with coefficients in $\mathbb{Q}$ have the same splitting field. There are several answers to the question, but they don't include proofs. Also, it's not clear how the results generalize to higher degree polynomials. Is there an algorithm for determining whether two polynomials in in $\mathbb{Q}[x]$ have the same splitting field? If so, what is it, and why does it work?

(Reposted from Math Stack Exchange.)

share|improve this question
7  
This question just boils down to the question of whether a polynomial with coefficients in a given number field has a root (apply this repeatedly), and there are algorithms for this -- see e.g. Cohen's "a course in number theory and cryptography". –  user30035 Dec 31 '12 at 8:52

1 Answer 1

up vote 10 down vote accepted

In practice, you can reduce f and g mod the first 1000 primes (deleting those where f and g are ramified) and see if the primes all have the same splitting behavior. If they don't, the splitting fields are not the same, and if they do, you can be pretty darn sure that they are. If you want to replace "be pretty darn sure" with "have proved" you can use the effective Chebotarev of Lagarias and Odlyzko to figure out the value of 1000 which actually gives you a proof.

share|improve this answer
1  
So, does this rigorously establish a randomized polynomial time algorithm for the original question, assuming GRH? –  Greg Kuperberg Jan 1 '13 at 22:33
1  
Depends what the bounds in Lagarias-Odlyzko are and I don't have them in my head right now. You might look at a recent paper of Kowalski and Zywina which carries out a computation of this kind in real life. –  JSE Jan 2 '13 at 1:53
    
+1 for "the value of 1000 which actually gives you a proof" –  Filippo Alberto Edoardo Jan 2 '13 at 4:37
    
This is nice. I don't immediately see why the effective Chebotarev density theorem tells you when you're done. But it's nice. wccanard's answer seems potentially more conceptually primitive, but I guess one would need to take a close look at the algorithm to be sure. –  Jonah Sinick Jan 2 '13 at 4:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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