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

Granville, Andrew

Monatsh. Math. 109, No. 4, 271-277 (1990).

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

MSC:

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

Keywords:

coefficients of a divisor of a polynomial; algorithms for factoring polynomials

Citations:

Zbl 0498.12019

References:

[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