6
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 7
    $\begingroup$ 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". $\endgroup$
    – user30035
    Commented Dec 31, 2012 at 8:52

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ So, does this rigorously establish a randomized polynomial time algorithm for the original question, assuming GRH? $\endgroup$
    – Greg Kuperberg
    Commented Jan 1, 2013 at 22:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – JSE
    Commented Jan 2, 2013 at 1:53
  • $\begingroup$ +1 for "the value of 1000 which actually gives you a proof" $\endgroup$
    – Filippo Alberto Edoardo
    Commented Jan 2, 2013 at 4:37
  • $\begingroup$ 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. $\endgroup$
    – Jonah Sinick
    Commented Jan 2, 2013 at 4:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .