On the smallest divisor of a polynomial
type: Item
instance of: scholarly article
title: On the smallest divisor of a polynomial
zbMATH Open document ID: 0804.12001
author: Philippe Glesser
author: Maurice Mignotte
published in: Journal of Symbolic Computation
publication date: 1995-01-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 12D05
Mathematics Subject Classification ID: 11Y40
Mathematics Subject Classification ID: 12Y05
zbMATH DE Number: 638319
zbMATH Keywords: smallest divisor
zbMATH Keywords: univariate polynomial with integer coefficients
zbMATH Keywords: algorithms
zbMATH Keywords: factorization
zbMATH Keywords: Bombieri's norm
zbMATH Keywords: Mahler's measure
zbMATH Keywords: supremum
zbMATH Keywords: inequalities
reviewed by: David W. Boyd
MaRDI profile type: Publication
full work available at URL: jsco.1994.1017
OpenAlex ID: W2011129019
DOI: 10.1006/JSCO.1994.1017
description: scientific article; zbMATH DE number 638319