A fast algorithm for computing multiplicative relations between the roots of a generic polynomial. (May 2021) - Zheng, Tao
Abstract: Multiplicative relations between the roots of a polynomial in Q [ x ] have drawn much attention in the field of arithmetic and algebra, while the problem of computing these relations is interesting to researchers in many other fields. In this paper, a sufficient condition is given for a polynomial f ∈ Q [ x ] to have only trivial multiplicative relations between its roots, which is a generalization of those sufficient conditions proposed in Smyth (1986), Baron et al. (1995) and Dixon (1997) . Based on the new condition, a subset E ⊂ Q [ x ] is defined and proved to be generic ( i.e., the set Q [ x ] \ E is very small). We develop an algorithm deciding whether a given polynomial f ∈ Q [ x ] is in E and returning a basis of the lattice consisting of the multiplicative relations between the roots of f whenever f ∈ E . The numerical experiments show that the new algorithm is very efficient for the polynomials in E . A large number of polynomials with much higher degrees, which were intractable before, can be handled successfully with the algorithm.