Fast recognition of alternating and symmetric Galois groups (Q1585066)

The authors present a probabilistic test which will, for any polynomial over \(\mathbb{Q},\) return either the answer ``the Galois group is definitely one of \(S_n\) or \(A_n\)'' or ``the Galois group is likely to be smaller''. The method involves reducing the polynomial modulo primes, using the Chebotarev Density Theorem and properties of transitive permutation groups. Based on computational experiments the paper concludes with the following conjecture: For a fixed probability \(\epsilon\), the number of tests required to ensure that the wrong answer, i.e. saying ``probably not \(S_n\) or \(A_n\)'' when in fact the group is one of these, is given with probability less than \(\epsilon,\) is in fact bounded independent of \(n.\)