Bounding the coefficients of a divisor of a given polynomial
type: Item
instance of: scholarly article
title: Bounding the coefficients of a divisor of a given polynomial
zbMATH Open document ID: 0713.12001
DOI: 10.1007/BF01320692
author: Andrew Granville
published in: Monatshefte für Mathematik
publication date: 1990-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/178475
review text: Define \(\| P\|^ 2:=\sum^{d}_{i=0}p_ i^ 2\) for polynomial \(P=\sum^{d}_{i=0}p_ iX^ i\). If f(X) and g(X) are polynomials with integer coefficients such that g divides f then it is shown that \(\| g\| \leq \alpha^ n\| f\|\) where \(\alpha =(1+\sqrt{5})/2\) and n is the degree of f. This helps speed up algorithms for factoring polynomials, improving on a result of \textit{M. Mignotte} [Computer Algebra, Symbolic and Algebraic Computation, Comput. Suppl. 4, 259-263 (1982; Zbl 0498.12019)] who gave \(\alpha =2\). Therefore the smallest \(\beta\), such that the estimate \(\| g\| \leq \beta^{n\{1+o(1)\}}\| f\|\) holds uniformly, as \(n\to \infty\), for all g dividing f, is \(\leq (1/\sqrt{5})/2 \approx 1.61803...\); it is also shown that \(\beta\geq 1.208..\).
reviewed by: Andrew Granville
Mathematics Subject Classification ID: 12D05
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11C08
zbMATH DE Number: 4173144
zbMATH Keywords: coefficients of a divisor of a polynomial
zbMATH Keywords: algorithms for factoring polynomials
MaRDI profile type: Publication
cites work: Q3754695
cites work: An inequality about irreducible factors of integer polynomials
OpenAlex ID: W2049578302
Recommended article: Q4832606
Recommended article: Q3412738
Recommended article: Lower bounds for a polynomial in terms of its coefficients
Recommended article: Q5284970
Recommended article: Determining divisibility between polynomials with inexact coefficients
Recommended article: The Fixed Divisor of a Polynomial
Recommended article: Bounds for the coefficients of cyclotomic polynomials
Recommended article: On Pairs of Coefficients of Bounded Polynomials
Recommended article: Degree bounds for the division problem in polynomial ideals
description: scientific article; zbMATH DE number 4173144