Bounding the coefficients of a divisor of a given polynomial. (English) Zbl 0713.12001

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 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..\).
Reviewer: A.Granville


12D05 Polynomials in real and complex fields: factorization
11Y16 Number-theoretic algorithms; complexity
11C08 Polynomials in number theory


Zbl 0498.12019
Full Text: DOI EuDML


[1] Landau, S.: Factoring polynomials quickly. Notices Amer. Math. Soc.34, 3-8 (1987). · Zbl 0618.12001
[2] Mignotte, M.: Some useful bounds. In:Buchberger, B., et al. (eds.). Computer Algebra, Symbolic and Algebraic Computation, 259-263. Wien-New York: Springer 1982.
[3] Mignotte, M.: An inequality about irreducible factors of integer polynomials. J. Number Theory30, 156-166 (1988). · Zbl 0648.12002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.