efficiently checking that a field extension is Galois

Question

Let $K \subset L$ be an algebraic extension of fields finitely presented over a prime field or over an algebraically closed field. Is there an efficient procedure to check that $L/K$ is Galois? To compute the minimal normal extension $K \subset L'$ containing L?

Answer 1

I assume that you have given your field extension $L=K(\alpha_1,\ldots,\alpha_n)$ in the form of a list of polynomials generating the kernel $I$ of $K[X_1,\ldots,X_n]\twoheadrightarrow L$. The intersection of this kernel with $K[X_i]$ is computable (Gröbner basis wrt an elimination ordering) and gives you the minimal polynomial $p_i$ of $\alpha_i$ over $K$. $K(\alpha_i)$ is separable over $K$ iff the derivative of $p_i$ does not vanish. Hence separability of $L|K$ is decidable.

The extension is normal iff there are enough roots of the $p_i$, i.e. iff there are $\deg(p_i)$ roots of $p_i$ in $L$ (which must be pairwise distinct to have a separable extension but we've already covered separability) and the minimal normal extension containing $L$ is exactly obtained by formally adjoining all missing roots. This seems to me to be equivalent to the problem of factorizing polynomials into irreducibles over finite extensions of $K$. Certainly if you can factorize polynomials (which is the case if $K$ is finite or $K=\mathbb{Q}$ but I'm not sure about more general fields), then you can check normality by testing if each $p_i$ completely split into linear factors and you can compute the normal closure by recursively adjoining formal zeros until all $p_i$ completely split.

Answer 2

A follow-up to @Johannes Hahn's excellent answer: How to factor polynomials in extensions was figured out by that young whipper-snapper Kronecker, but given a more efficient form by first Barry Trager, and then Susan Landau. See

S. Landau, Factoring Polynomials over Algebraic Number Fields, SIAM J. of Comput., Vol. 14, No. 1 (1985), pp. 184-195.