Does there exist an algorithm which computes the Galois group of a polynomial
$p(x) \in \mathbb{Z}[x]$? Feel free to interpret this question in any reasonable manner. For example, if the degree of $p(x)$ is $n$, then the algorithm could give a set of permutations $\pi \in Sym(n)$ which generate the Galois group.
Computing the Galois Group of a Polynomial – Methods and Examples
algorithmsgalois-theory
Best Answer
There is an algorithm described in an ancient and interesting book on Galois Theory by Leonard Eugene Dickson. Here is a brief sketch in the case of an irreducible polynomial $f\in \mathbb{Q}[x]$.
Suppose that $z_1\ldots z_n$ are the roots of $f$ in some splitting field of $f$ over $\mathbb{Q}$. (We don't need to construct the splitting field. The $z_i$ are mentioned here for the sake of explanation.) Let $x_1\ldots x_n$ be indeterminates. For a permutation $\sigma\in S_n$, let $$E_\sigma=x_1z_{\sigma(1)}+\ldots+ x_n z_{\sigma(n)}.$$ Let $g(x):=\prod _{\sigma} (x-E_\sigma)$, where $\sigma$ runs through all permutations in $S_n$. Each coefficient $c_i$ of $x^i$ in $g$ is symmetric in $z_1 \ldots z_n$, so (using the theorem on symmetric functions) we can write $c_i$ as a polynomial in $x_1\dots x_n$ with rational coefficients.
Assuming that this has been done, factor $g$ into irreducibles over the ring $\mathbb{Q}[x_1 \ldots x_n]$. Let $g_0$ be the irreducible factor of $g$ that is satisfied by $E_{Id}$, where $Id$ is the identity permuation. Then the galois group of $f$ consists of all permutations of $x_1\ldots x_n$ that fix $g_0$.
The point is that the computation of $g_0$ is effective (albeit horrendous) and so is the determination of the permutations that fix $g_0$.