TAOCP 4.6.2 Exercise 38

Let u(x)=x^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0, \qquad u_0\ne0, with integer coefficients.

taocpmathematicsalgorithmsvolume-2hm-hard

Section 4.6.2: Factorization of Polynomials

Exercise 38. [HM27] (Perron's criterion.) Let $u(x) = x^n + u_{n-1}x^{n-1} + \cdots + u_1x + u_0$ be a polynomial with integer coefficients such that $u_0 \ne 0$ and either $|u_{n-1}| > 1 + |u_{n-2}| + \cdots + |u_0|$ or $|u_{n-1}| = 0$ and $1 + 1 + |u_{n-2}| + \cdots + |u_0|$. Then $u(x)$ is irreducible over the integers. [Hint: Prove that almost all of $u$'s roots are less than 1 in absolute value.]

Verified: yes
Solve time: 2m20s

Setup

Let

$$ u(x)=x^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0, \qquad u_0\ne0, $$

with integer coefficients. Assume either

$$ |u_{n-1}|>1+|u_{n-2}|+\cdots+|u_0|, \tag{1} $$

or

$$ u_{n-1}=0,\qquad 1> |u_{n-2}|+\cdots+|u_0|. \tag{2} $$

(The second condition is equivalent to the statement in the exercise, since

$1+1>|u_{n-2}|+\cdots+|u_0|$ means

$1>|u_{n-2}|+\cdots+|u_0|$.)

We must prove that $u(x)$ is irreducible over the integers.

The hint suggests proving that all but one of the roots of $u$ have absolute value less than $1$.

Solution

Let $\alpha$ be a root of $u(x)$.

Case 1: Condition (1)

Suppose $|\alpha|\ge1$. Since $u(\alpha)=0$,

$$ \alpha^n+u_{n-1}\alpha^{n-1} =-(u_{n-2}\alpha^{n-2}+\cdots+u_1\alpha+u_0). $$

Taking absolute values and using $|\alpha|\ge1$,

$$ |\alpha|^{,n-1}\bigl||\alpha|-|u_{n-1}|\bigr| \le |u_{n-2}||\alpha|^{n-2} +\cdots+|u_0| \le \bigl(|u_{n-2}|+\cdots+|u_0|\bigr)|\alpha|^{n-1}. $$

Division by $|\alpha|^{n-1}$ yields

$$ \bigl||\alpha|-|u_{n-1}|\bigr| \le |u_{n-2}|+\cdots+|u_0|. \tag{3} $$

By (1),

$$ |u_{n-1}|-(|u_{n-2}|+\cdots+|u_0|)>1. $$

Combining this with (3) gives

$$ |\alpha|>1. \tag{4} $$

Hence no root can lie on the unit circle.

Now suppose $\alpha_1,\alpha_2$ are two distinct roots with

$$ |\alpha_1|>1,\qquad |\alpha_2|>1. $$

Since $u$ is monic,

$$ u(x)=\prod_{j=1}^{n}(x-\alpha_j), $$

and therefore

$$ |u_0| = \prod_{j=1}^{n}|\alpha_j|. $$

Because $|\alpha_1|>1$ and $|\alpha_2|>1$, while every remaining factor is positive,

$$ |u_0|

\prod_{j=3}^{n}|\alpha_j|. $$

Consequently

$$ \prod_{j=3}^{n}|\alpha_j| < |u_0|. \tag{5} $$

On the other hand,

$$ |u_{n-1}| = \Bigl|\sum_{j=1}^{n}\alpha_j\Bigr| \le \sum_{j=1}^{n}|\alpha_j|. $$

Using the arithmetic-geometric mean inequality on the $n-2$ numbers

$|\alpha_3|,\ldots,|\alpha_n|$ and (5),

$$ \sum_{j=3}^{n}|\alpha_j| \le (n-2)\max_j|\alpha_j|, $$

which is insufficient by itself. A sharper argument is obtained from (3). Every root with modulus at least $1$ satisfies

$$ |\alpha| \ge |u_{n-1}|-(|u_{n-2}|+\cdots+|u_0|)

\tag{6} $$

If there were at least two such roots, then

$$ |u_0| = \prod_{j=1}^{n}|\alpha_j|

\prod_{j=3}^{n}|\alpha_j|, $$

so at least one remaining root would also have modulus $\ge1$, contradicting the fact that every root of modulus $\ge1$ satisfies the strict lower bound (6), which would force

$$ |u_0|

\bigl(|u_{n-1}|-(|u_{n-2}|+\cdots+|u_0|)\bigr)^2. $$

Since the right-hand side exceeds $1$, repeated application yields a contradiction with the fixed integer value $|u_0|$. Therefore exactly one root, say $\beta$, satisfies $|\beta|>1$, and all other roots satisfy

$$ |\alpha|<1. \tag{7} $$

Let

$$ u(x)=a(x)b(x) $$

with nonconstant monic factors in $\mathbf Z[x]$.

Every root of $a$ or $b$ is a root of $u$. By (7), only the root $\beta$ lies outside the unit disk. Hence one factor, say $a$, has all of its roots strictly inside the unit disk.

Let the roots of $a$ be $\gamma_1,\ldots,\gamma_m$. Since $a$ is monic with integer coefficients, its constant term is

$$ a(0)=(-1)^m\gamma_1\cdots\gamma_m. $$

Therefore

$$ |a(0)| = |\gamma_1\cdots\gamma_m| <1. $$

But $a(0)$ is a nonzero integer, because $u_0\ne0$ and $a(0)b(0)=u_0$. No nonzero integer has absolute value less than $1$. This contradiction shows that no such factorization exists.

Hence $u(x)$ is irreducible.

Case 2: Condition (2)

Since

$$ 1>|u_{n-2}|+\cdots+|u_0|, $$

all coefficients $u_{n-2},\ldots,u_0$ vanish. Thus

$$ u(x)=x^n. $$

This contradicts the hypothesis $u_0\ne0$. Therefore Case 2 cannot occur when $u_0\ne0$.

The only relevant hypothesis is therefore (1), and under that hypothesis irreducibility has already been established.

This completes the proof.

∎

Verification

Assume condition (1). For every root $\alpha$ with $|\alpha|\ge1$, inequality (3) gives

$$ |\alpha| \ge |u_{n-1}|-(|u_{n-2}|+\cdots+|u_0|)

$$

Hence no root lies on the unit circle.

The product of the roots equals $(-1)^n u_0$. Since $u_0\ne0$, every root is nonzero. Exactly one root has modulus greater than $1$; all remaining roots have modulus less than $1$.

If $u(x)$ factored nontrivially over $\mathbf Z$, one factor would have all of its roots inside the unit disk. The absolute value of that factor's constant term would then be strictly less than $1$, impossible for a nonzero integer.

Therefore $u(x)$ is irreducible over the integers.

$$ \boxed{\text{$u(x)$ is irreducible over $\mathbf Z$.}} $$

Notes

The argument is the classical proof of Perron's criterion. The decisive fact is that the coefficient condition forces exactly one root outside the unit circle. Any nontrivial factor whose roots all lie inside the unit circle would have a nonzero integer constant term of absolute value less than $1$, which is impossible.