On the smallest divisor of a polynomial (Q1333166)

Let \(F(x)\) be a reducible univariate polynomial with integer coefficients. Let \(b(F)\) denote the minimal value of \(H(G)\) where \(G\) runs over the divisors of \(F\) with integer coefficients and where \(H(G)\) denotes the maximum absolute value of the coefficients of \(G\). Estimates of \(b(G)\) can be used in algorithms for factorization of integer polynomials [as in \textit{B. Beauzamy}, \textit{V. Trevisan} and \textit{P. Wang}, J. Symb. Comput. 13, 463-472 (1992; Zbl 0801.12007)]. Using a variety of known inequalities, the authors produce four different estimates for \(b(F)\) in terms of \([F]_ 2\), \(M(F)\) and \(\| F\|_ \infty\), where these denote, respectively, Bombieri's norm, Mahler's measure and the supremum of \(| F(z)|\) on the unit circle. They compare the estimates on a variety of polynomials. The reviewer has obtained inequalities of this type in terms of the general Bombieri norm \([F]_ p\) [J. Symb. Comput. 16, 131-145 (1993; Zbl 0802.12002)]. A disadvantage of all these estimates is that they grow exponentially with the degree of \(F\). The true rate of growth of \(b(F)\) with \(\deg(F)\) seems to be unknown.