Perron's criterion

Perron's Criterion states: Let $f(x)=x^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0\in \mathbb{Z}[x]$ with $a_0\neq 0$ and $|a_{n-1}|>1+|a_{n-2}|+\cdots +|a_1|+|a_0|$ $f(x)$ is then irreducible.

Proof

We start of with a lemma: exactly one zero of $f(x)$ satisfies $|z|>1$ and the rest satisfy $|z|<1$ . Proof (due to Laurentiu Panaitopol): First, we will prove that no $\phi$ exists such that $f(\phi)=0$ and $|\phi|=1$ . Suppose we find such an root. Then, we have that $-a_{n-1}\phi^{n-1}=\phi^n+a_{n-2}\phi^{n-2}+\cdots+a_1\phi+a_0$ However, this means that $|a_{n-1}|=|a_{n-1}\phi^{n-1}|=|\phi^n+a_{n-2}\phi^{n-2}+\cdots+a_1\phi+a_0| \leq |\phi^n|+|a_{n-2}\phi^{n-2}|+\cdots+|a_1\phi|+|a_0|=1+|a_{n-2}|+\cdots +|a_1|+|a_0|$ This is a contradiction, so such a root can not exist.

Now, let the roots of $f(x)$ be $\phi_1, \phi_2,\cdots ,\phi_n$ . Since $\phi_1\phi_2\cdots \phi_n=a_0$ , one of the roots, say $\phi_1$ , satisfies $|\phi_1|>1$ . Then, let $f(x)=(x-\phi_1)g(x)$ , where $g(x)=x^{n-1}+g_{n-2}x^{n-2}+\cdots+g_1x+g_0$ . We know that $a_0=-g_0\phi_1$ , and $a_i=g_{i-1}-g_{i}\phi_1$ . Therefore, $|b_{n-2}|+|\phi_1|\geq |b_{n-2}-\phi_1|>1+|b_{n-3}-b_{n-2}\phi_1|+\cdots+|b_0\phi_1|$ $1+|b_{n-3}-b_{n-2}\phi_1|+\cdots+|b_0\phi_1|\geq 1-|b_{n-3}|+|b_{n-2}||\phi_1|-|b_{n-4}|+|b_{n-3}||\phi_1|-\cdots-|b_0|+|b_1||\phi_1|+|b_0||\phi_1|=1+|b_{n-2}|+(|\phi_1|-1)(|b_{n-2}|+|b_{n-3}|+\cdots+|b_0|)$

This means that $|b_{n-2}|+|b_{n-3}|+\cdots+|b_0|<1$ .

This means, for all $|\rho|>1$ , we have: $|g(\rho)|=|\rho^{n-1}+g_{n-2}\rho^{n-2}+\cdots+g_1\rho+g_0|\geq |\rho|^{n-1}-(|g_{n-2}\rho^{n-2}|+|g_{n-3}\rho^{n-3}|+\cdots+|g_1\rho|+g_0|)\geq |\rho|^{n-1}(1-(|b_{n-2}|+|b_{n-3}|+\cdots+|b_0|))>0$

Therefore, all of the other zeroes of $f(x)$ satisfy $|\phi|<1$ .

Now, we will prove Perron's Criterion. Let $f(x)=g(x)h(x)$ , where $g(x)=x^r+g_{r-1}x^{r-1}+\cdots+g_1x+g_0$ . Since $f(x)$ has only one root outside the unit circle, $\phi_1$ , assume that it is a root of $h(x)$ . Then, we get that the roots of $g(x)$ , $\psi_1, \psi_2,\cdots,\psi_r$ , have a product of $g_0$ , a nonzero integer. However, $|\psi_1\psi_2\cdots \psi_r|=|g_0|<1$ , a contradiction. Thus, $f(x)$ is irreducible.

Page

Toolbox

Search

Perron's criterion

Proof