View source for Perron's criterion

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

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

Now, let the roots of <math>f(x)</math> be <math>\phi_1, \phi_2,\cdots ,\phi_n</math>. Since <math>\phi_1\phi_2\cdots \phi_n=a_0</math>, one of the roots, say <math>\phi_1</math>, satisfies <math>|\phi_1|>1</math>. Then, let <math>f(x)=(x-\phi_1)g(x)</math>, where <math>g(x)=x^{n-1}+g_{n-2}x^{n-2}+\cdots+g_1x+g_0</math>. We know that <math>a_0=-g_0\phi_1</math>, and <math>a_i=g_{i-1}-g_{i}\phi_1</math>. Therefore,
<cmath>|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|</cmath><cmath>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|)</cmath>

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

This means, for all <math>|\rho|>1</math>, we have:
<cmath>|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</cmath>

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



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