Fast recognition of alternating and symmetric Galois groups
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.\)
- Explicit determination of generalized symmetric and alternating Galois groups
- Computation of the Galois group of a polynomial with rational coefficients. II
- scientific article; zbMATH DE number 3924140
- Computation of the Galois group of a polynomial with rational coefficients. I
- A Polynomial Time Nilpotence Test for Galois Groups and Related Results
- Galois groups and the factorization of polynomials
- scientific article; zbMATH DE number 3137403 (Why is no real title available?)
- scientific article; zbMATH DE number 3563269 (Why is no real title available?)
- scientific article; zbMATH DE number 3223737 (Why is no real title available?)
- scientific article; zbMATH DE number 3392570 (Why is no real title available?)
- On polynomials with symmetric Galois group which are easy to compute
- On Random Generation of the Symmetric Group
- On the Efficiency of a Polynomial Irreducibility Test
- Poisson process approximations for the Ewens sampling formula
- Computing Galois groups of polynomials (especially over function fields of prime characteristic)
- Four random permutations conjugated by an adversary generate \(\mathcal{S}_{n}\) with high probability
- Detecting fast solvability of equations via small powerful Galois groups
- Ewens sampling and invariable generation
- Primitivity and Orbit Decomposition
- A black-box group algorithm for recognizing finite symmetric and alternating groups, I
- Testability in group theory
- Proving an execution of an algorithm correct?
- Explicit determination of generalized symmetric and alternating Galois groups
This page was built for publication: Fast recognition of alternating and symmetric Galois groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1585066)
