A fast algorithm for computing multiplicative relations between the roots of a generic polynomial. (May 2021)

• Record Type: Journal Article
• Authors: Zheng, Tao
• Is Part Of: Journal of symbolic computation. Volume 104(2021)
• Page Start: 381
• Page End: 401
• Publication Date: 2021-05
• Subjects: Exponent lattice -- Multiplicative relation -- Polynomial roots -- Basis -- Galois group; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.08.001
• Languages: English
• ISSNs: 0747-7171

Abstract

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.