November 15, 2012
Computational Galois theory, in particular the problem of computing the Galois group of a given polynomial is a very old problem. Currently, the best algorithmic solution is Stauduhar's method. Computationally, one of the key challenges in the application of Stauduhar's method is to find, for a given pair of groups H<G a G-relative H-invariant, that is a multivariate polynomial F that is H-invariant, but not G-invariant. While generic, theoretical methods are known to find such F, in general they yield impractical answers. We give a general method for computing invariants of large degree which improves on previous known methods, as well as various special invariants that are derived from the structure of the groups. We then apply our new invariants to the task of computing the Galois groups of polynomials over the rational numbers, resulting in the first practical degree independent algorithm.
Similar papers 1
May 15, 2008
Let G=Aut_K (K(x)) be the Galois group of the transcendental degree one pure field extension K(x)/K. In this paper we describe polynomial time algorithms for computing the field Fix(H) fixed by a subgroup H < G and for computing the fixing group G_f of a rational function f in K(x).
March 12, 2020
We present a family of algorithms for computing the Galois group of a polynomial defined over a $p$-adic field. Apart from the "naive" algorithm, these are the first general algorithms for this task. As an application, we compute the Galois groups of all totally ramified extensions of $\mathbb{Q}_2$ of degrees 18, 20 and 22, tables of which are available online.
April 16, 2022
These notes are an exposition of Galois Theory from the original Lagrangian and Galoisian point of view. A particular effort was made here to better understand the connection between Lagrange's purely combinatorial approach and Galois algebraic extensions of the latter. Moreover, stimulated by the necessities of present day computer explorations, the algorithmic approach has been given priority here over every other aspect of presentation. In particular, you may not find here...
April 12, 2018
These notes are a self-contained introduction to Galois theory, designed for the student who has done a first course in abstract algebra.
February 6, 2001
We report on a database of field extensions of the rationals, its properties and the methods used to compute it. At the moment the database encompasses roughly 100,000 polynomials generating distinct number fields over the rationals, of degrees up to 15. It contains polynomials for all transitive permutation groups up to that degree, and even for most of the possible combinations of signature and Galois group in that range. Moreover, whenever these are known, the fields of mi...
March 8, 2015
We present an algorithm that determines the Galois group of linear difference equations with rational function coefficients.
March 22, 2022
This work provides a method(an algorithm) for solving the solvable unary algebraic equation $f(x)=0$ ($f(x)\in\mathbb{Q}[x]$) of arbitrary degree and obtaining the exact radical roots. This method requires that we know the Galois group as the permutation group of the roots of $f(x)$ and the approximate roots with sufficient precision beforehand. Of course, the approximate roots are not necessary but can help reduce the quantity of computation. The algorithm complexity is appr...
August 15, 2017
Let $P\in\mathbb Q[t,x]$ be a polynomial in two variables with rational coefficients, and let $G$ be the Galois group of $P$ over the field $\mathbb Q(t)$. It follows from Hilbert's Irreducibility Theorem that for most rational numbers $c$ the specialized polynomial $P(c,x)$ has Galois group isomorphic to $G$ and factors in the same way as $P$. In this paper we discuss methods for computing the group $G$ and obtaining an explicit description of the exceptional numbers $c$, i....
May 5, 2020
The problem of computing \emph{the exponent lattice} which consists of all the multiplicative relations between the roots of a univariate polynomial has drawn much attention in the field of computer algebra. As is known, almost all irreducible polynomials with integer coefficients have only trivial exponent lattices. However, the algorithms in the literature have difficulty in proving such triviality for a generic polynomial. In this paper, the relations between the Galois gr...
March 19, 2022
We report on an implementation of Galois groups in the new computer algebra system OSCAR. As an application we compute Galois groups of Ehrhart polynomials of lattice polytope