Bounds on factors in Z[x]

DOI10.1016/J.JSC.2012.09.004zbMATH Open1295.12010arXiv0904.3057OpenAlexW1619519317MaRDI QIDQ1930188FDOQ1930188

Authors: John Abbott 

Publication date: 10 January 2013

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: We gather together several bounds on the sizes of coefficients which can appear in factors of polynomials in Z[x]; we include a new bound which was latent in a paper by Mignotte, and a few minor improvements to some existing bounds. We compare these bounds and show that none is universally better than the others. In the second part of the paper we give several concrete examples of factorizations where the factors have "unexpectedly" large coefficients. These examples help us understand why the bounds must be larger than you might expect, and greatly extend the collection published by Collins.

Full work available at URL: https://arxiv.org/abs/0904.3057

Recommendations

• scientific article; zbMATH DE number 1419238
• Bounding the coefficients of a divisor of a given polynomial
• Single-factor coefficient bounds
• Polynomial factorization: Sharp bounds, efficient algorithms
• scientific article; zbMATH DE number 2107531

zbMATH Keywords

high-ratio factorizationlarge height polynomial factorspolynomial factor boundspolynomial root bounds

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials, factorization in commutative rings (13P05)

Cited In (9)

• Certifying irreducibility in \(\mathbb{Z}[x]\)
• A verified implementation of the Berlekamp-Zassenhaus factorization algorithm
• On the factorization of \(f(n)\) for \(f(x)\) in \(\mathbb Z[x]\)
• Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\)
• Single-factor coefficient bounds
• Title not available (Why is that?)
• [[Publication:2926272|On Hensel's roots and a factorization formula in \(\mathbb Zx\)]]
• Methodologies of Symbolic Computation
• Factorization in Z[x]

This page was built for publication: Bounds on factors in \(\mathbb Z[x]\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1930188)