No label defined (Q4252162)

A motivation to the paper is the following question of \textit{F. Cucker, P. Koiran} and \textit{S. Smale} [J. Symb. Comput. 27, 21-29 (1999; Zbl 0920.11085)]: can one find all rational zeros of a sparse integer polynomial \(\sum _{i} a_i x^i\) (that given by the list of pairs \((i, a_i)\) with \(a_i\neq 0\)) in polynomial time ? The author shows that this is indeed the case. More generally, there is a deterministic algorithm such that for a sparse polynomial \(f\) with coefficients in a number field \(K\), and a positive integer \(d\), the algorithm finds all monic irreducible factors of \(f\) (in \(K[x]\)) of degree at most \(d\), and their multiplicities, in time at most \((l+d)^c\), where \(l\) denotes the ``length'' of the input data, and \(c\) is a positive absolute and effectively computable constant. The precise definition of the length of the input data is given in his earlier paper [Bull. Am. Math. Soc. 26, 211-244 (1992; Zbl 0759.11046)], and it is essentially the number of bits needed to spell out the data in binary. There are also several auxiliary algorithms, one of which finds the cyclotomic factors of \(f\). The key proposition uses the uniform lower bound on the Mahler measure, \(\log M(\alpha)\geq 2\big(\log (3d)\big)^{-3}\), where \(\alpha\) is a non-cyclotomic algebraic number of degree at most \(d\), \(d \geq 2\). For the entire collection see [Zbl 0911.00025].