Upper bounds for the number of factors of a polynomial over $\mathbb{Z}$

Question

Let $f(x) = a_nx^n +a_{n-1}x^{n-1}+\dots+a_1x+a_0$ be a polynomial of degree $n$ in $\mathbb{Z}[x]$. Assuming that $f(x)$ is reducible over $Z$, can we make any comments for a non-trivial ($<n$) upper bound for the number of factors of it?

Answer 1

Not only can you not say anything about such a polynomial having fewer than $n$ factors in general, you can’t even say it has at most $n$ irreducible factors!

As a consequence of Gauss’s Lemma, we know that the factorization of a polynomial with integer coefficients into irreducible factors will be of the form $$f(x) = p_1\cdots p_kq_1(x)\cdots q_r(x)$$ where $p_1,\ldots,p_k$ are prime numbers, and $q_1,\ldots,q_r$ are polynomials of degree at least one that are irreducible over $\mathbb{Q}$ and have trivial content; that is, the gcd of their coefficients is $1$.

We can certainly say that $r\leq n$ (but we cannot in general say whether it will be strictly less than $n$), but we can put no bounds on $k$. That is, $f(x)$ can have arbitrarily many irreducible factors in $\mathbb{Z}[x]$. For example, $7^Nx$ has $N+1$ irreducible factors, and is of degree $1$.

Primitive polynomials (polynomials with trivial content, as they are called in Number Theory [but not in Computer Science]) will have $k=0$, so we will have at most $\deg(f)$ irreducible factors; however, we have no way of bounding this number to anything less than $\deg(f)$ in general. Of course, one may take a particular polynomial and see whether it is irreducible over $\mathbb{Q}$ (sundry tests exist for that), but that is not a way to bound the number of factors in general, which is what this question asks.