Bounding the coefficients of a divisor of a given polynomial
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..\).
coefficients of a divisor of a polynomial
scientific article; zbMATH DE number 4173144