# Bounding the “complexity” of irreducible factors of an integer polynomial

Given an integer polynomial $P(x) = a_0 + a_1 x + \cdots + a_n x^n$, there ought to be a reasonable bound on the "complexity" of its possible irreducible integer polynomial factors that allows us to restrict to finitely many possible factors. This would allow us to use trial division to test the irreducibility of $P$ (although this is a pretty bad test of irreducibility).

As an example, in response to another math.SE question I gave a straightforward bound $$|x| \le \max(1, \left| \frac{a_0}{a_n} \right| + \cdots + \left| \frac{a_{n-1}}{a_n} \right|) = M$$

on the absolute value of the complex roots of $P$. This bound implies a horrible bound on the absolute values of the coefficients of an irreducible factor of degree $d$ (the $k^{th}$ coefficient has absolute value at most $a_n {d \choose k} M^k$), and I am wondering if it is possible to do substantially better.

Here's one precise form of this question. Given a polynomial $P \in \mathbb{Z}[x]$ of degree $n$ define its length $L(P)$ to be the sum of the absolute value of its coefficients.

What is the smallest exponent $e_{n,d}$ for which there exists a constant $c_{n, d}$ such that, for all $P \in \mathbb{Z}[X]$ of degree $n$ and all irreducible factors $Q$ of $P$ in $\mathbb{Z}[x]$ of degree $d$, we have the inequality $L(Q) \le c_{n, d} L(P)^{e_{n,d}}$?

-
David Boyd had a nice paper on such inequalities back in the 1970s or 80s. Sorry I can't be more specific, as I am away from my references. –  Gerry Myerson Jan 5 '12 at 1:23
@Gerry D. Boyd's results were also discovered independently by others, e.g. M. Laugevin, C. Stewart, and M. Mignotte. These and other related results are presented in Chapter 4 of Mignotte's Mathematics for Computer Algebra - which should prove of interest to Qiaochu. –  Bill Dubuque Jan 5 '12 at 2:17
I changed \text{max} to \max. It's a standard operator name in TeX. –  Michael Hardy Jan 5 '12 at 3:03
@Bill, my recollection is that Boyd's paper (or at least part of it) was of the nature of a survey, not claiming originality for the results, but collecting many in one place. Mignotte's book is more recent and I wish I had remembered it to recommend it to Qiaochu. –  Gerry Myerson Jan 5 '12 at 22:38