Characterizing Triviality of the Exponent Lattice of a Polynomial Through Galois and Galois-Like Groups

摘要

The problem of computing 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 group (respectively, the Galois-like groups) and the triviality of the exponent lattice of a polynomial are investigated. The Q-trivial pairs, which are at the heart of the relations between the Galois group and the triviality of the exponent lattice of a polynomial, are characterized. An effective algorithm is developed to recognize these pairs. Based on this, a new algorithm is designed and implemented to prove the triviality of the exponent lattice of a generic irreducible polynomial, which considerably improves a state-of-the-art implementation of an algorithm of the same type when the polynomial degree becomes larger. In addition, the concept of the Galois-like groups of a polynomial is introduced. Some properties of the Galois-like groups are proved and, more importantly, a sufficient and necessary condition is given for a polynomial (which is not necessarily irreducible) to have trivial exponent lattice.