Perron's criterion for irreducibility of polynomials

hxtung · Riemann Hypothesis Offline Joined: 26 Jul 2003 Posts: 323

Let $P\left(x\right)=x^n+a_1x^{n-1}+a_2x^{n-2}+...+a_{n-1}x+a_n$ be a polynomial with integer coefficients such that $a_n$ is non-zero.

If $\left|a_1\right| > 1 + \left|a_2\right| + \left|a_3\right| + ... + \left|a_{n-1}\right| + \left|a_n\right|$ , then prove that $P\left(x\right)$ is irreducible in $\mathbb{Z}\left[x\right]$ .

**Posted:** Sun Jul 27, 2003 2:12 am

grobber

[Moderator edit: This post referred to a wrong version of the problem, where instead of $\left|a_1\right| > 1 + \left|a_2\right| + \left|a_3\right| + ... + \left|a_{n-1}\right| + \left|a_n\right|$ the condition was (incorrectly) written $\left|a_1\right| > 1 + \left|a_2\right| + \left|a_3\right| + ... + \left|a_{n-1}\right|$ .]

I think something is wrong here:

If we put n=3, a2=0, a1=2 then a1>1+|a2| because a2=an-1 but then we can take any a3 that we want, so if we have a3=-1 then the plymiomial=
x^3+2x^2-1=(x+1)*(x^2+x-1) so the problem is wrong. This is because we can choose any an that we want.

Maybe it's like this:a1>1+|a2|+..+|a(n-1)|+|an|. What do you think?

**Posted:** Wed Jul 30, 2003 1:00 am

hxtung · Riemann Hypothesis Offline Joined: 26 Jul 2003 Posts: 323

Sorry!
thank grobber

**Posted:** Wed Aug 06, 2003 2:16 am

Lagrangia

SO how is the problem then?

**Posted:** Wed Aug 06, 2003 2:19 am

_________________
As far as the laws of mathematics refer to reality, they are not certain, and as far as they are certain, they do not refer to reality.

Namdung

Hi all,

I will correct this problem (posted by hxtung):

P(x) is polynomial with integer coefficients, an is non zero
P(x) = x^n + a_1x^(n-1) + ...+ a_(n-1)x + a_n.
If |a1| > 1 + |a_2| + ... +|a_n|,
prove that P(x) is irreducible over Z[x]

It's well-known Perron critery. We also can show that if |a1| = 1 + |a_2| + ... +|a_n| and f( \pm 1) <> 0 then P(x) is irreducible over Z[x].

I have the proof of this theorem, but it is not very elementary (using Rushe theorem). Anyone can find elementary solution?

**Posted:** Sat Dec 20, 2003 1:08 am

fmathurin · P versus NP Offline Joined: 18 Jan 2005 Posts: 30

**Posted:** Mon Jan 24, 2005 4:01 pm

vess

**Posted:** Mon Jan 24, 2005 4:21 pm

pengshi

[quote="vess"]

**Posted:** Wed Jan 26, 2005 12:01 pm

_________________
...and the rest follows by induction.

Myth

Indeed, it is a well know result.
Consider $f(x)=a_1x^{n-1}$ and $g(x)=x^n+a_2x^{n-2}+...+a_n$ . Then $|f(z)|=|a_1|$ for all $z$ with $|z|=1$ , and in the same time $|g(z)|\leq |z^n|+|a_2z^{n-2}|+...+|a_n|=1+|a_2|+...+|a_n|$ if $|z|=1$ . So $|f(z)|>|g(z)|$ for all $z$ on the unit circle.
Due to Rouche's theorem we conclude $f(z)=a_1z^{n-1}$ and $f(z)+g(z)=z^n+a_1z^{n-1}+...+a_n=P(x)$ have the same number of complex roots inside the unit circle. But $f(z)=a_1z^{n-1}$ has exactly $n-1$ roots there. It follows that $P(x)$ has exactly 1 root outside of $|z|<1$ .

Suppose that $P(x)$ is a reducable polynomial. Then $P(x)=u(x)v(x)$ , there $u,v\in \mathbb{Z}$ . And we know $u(0),v(0)\neq 0$ . But each such polynomial has at least one root outside of $|z|<1$ (otherwise integer nonzero $u(0)$ is a product of complex numbers, where each numbers is less than 1 in magnitude). Therefore, $P(x)$ has at least two roots outside of $|z|<1$ . Contradiction.

**Posted:** Wed Jan 26, 2005 12:31 pm

_________________
Myth is out of here

Myth

Valentin said me some time ago that he knows a proof without use of complex analysis (Rouche's theorem).

**Posted:** Wed Jan 26, 2005 12:36 pm

_________________
Myth is out of here

vess

A proof that $P(x)$ has precisely $n-1$ roots inside the unit circle without complex analysis??!!!??

**Posted:** Wed Jan 26, 2005 1:20 pm

Myth

A proof that $P(x)$ is irreducible.

**Posted:** Wed Jan 26, 2005 1:23 pm

_________________
Myth is out of here

Valentin Vornicu

**Posted:** Wed Jan 26, 2005 2:56 pm

_________________
We all use math everyday: to forecast weather, to tell time, to handle money; we also use math to analyze crime, reveal patterns, predict behavior. Using numbers we can solve the biggest mysteries we know.

Valentin Vornicu

So, let's take $P(X) = X^n + a_{n-1}X^{n-1} + \cdots + a_1X + a_0$ , $a_k \in \mathbb{Z}$ , $k=\overline{0,n-1}$ such that $|a_{n-1}| > 1 + |a_{n-2}| + \cdots + |a_1| + |a_0|$ .

We can obviously suppose that $a_0 \neq 0$ because otherwise we just extract the largest $X^j$ type factor we can find out of $P(X)$ . Let's first prove that there is no root $\alpha$ of $P(X)$ with absolute value $|\alpha |=1$ .

We have that $-a_{n-1}\alpha^{n-1} = \alpha^n + a_{n-2} \alpha^{n-2} + \cdots + a_1 \alpha + a_0$ thus
$|a_{n-1} \alpha^{n-1} | = | \alpha^n + a_{n-2} \alpha^{n-2} + \cdots + a_1 \alpha + a_0 |$
$|a_{n-1} \alpha^{n-1} | \leq | \alpha^n | + | a_{n-2} \alpha^{n-2}| + \cdots + | a_1 \alpha | + | a_0 |$
and because $|\alpha=1|$ it follows that $|a_{n-1}| \leq 1 + |a_{n-2}|+\cdots + |a_1|+|a_0|$ which is a contradiction.

Let's denote with $\alpha_1$ , $\alpha_2$ , $\ldots$ , $\alpha_n$ be the roots of $P(X)$ . Because $|\alpha_1 \cdot \alpha_2 \cdots \alpha_n| = a_0$ it follows that at least one of the roots is larger than 1 in absolute value.

Let $|\alpha_1 | >1$ and let $Q(X) = X^{n-1} + b_{n-2}X^{n-2} + \cdots + b_1X + b_0$ polynomial with roots $\alpha_2$ , $\alpha_3$ , $\ldots$ , $\alpha_n$ . We have that

$P(X) = (X-\alpha_1)Q(X) = X^n + (b_{n-2}-\alpha_1)X^{n-1} + (b_{n-3}- b_{n-2}\alpha_1)X^{n-2}+$ $\cdots + X(b_0 - b_1\alpha_1)-b_0\alpha_1$

It follows that $a_k = b_{k-1} - b_k \alpha_1$ , for all $1 \leq k \leq n-1$ , $b_{n-1}=1$ , and $a_0 = - b_0 \alpha_1$ , therefore the condition in the statement becomes

$|b_2 - \alpha_1 | > 1 + |b_{n-3} - b_{n-2}\alpha_1 | + \cdots + |b_0\alpha_1 | \geq$
$\geq 1 + |b_{n-2}||\alpha_1| - |b_{n-3}| + |b_{n-3}||\alpha_1| - |b_{n-4}| + \cdots + |b_1||x_1| - |b_0| + |b_0||x_1| =$
$= 1 + |b_{n-2} | + (|\alpha_1| -1 ) (|b_{n-2} | + |b_{n-3} | + \cdots + |b_1 | + |b_0| ).$

But as $|b_{n-2} - \alpha_1 | \leq |b_{n-2} | + |\alpha_1|$ it follows that

$|b_{n-2} | + |\alpha_1 | > 1 + |b_{n-2}| + (|\alpha_1| -1 ) \sum^{n-2}_{k=0} b_k \ \Rightarrow 1 > \sum^{n-2}_{k=0} |b...$

Suppose now that there exists an $j>1$ such that $|\alpha_j |>1$ . As $Q(\alpha_j) = 0$ we have
$\alpha_j^{n-1} = - \sum^{n-2}_{k=0} b_k \alpha_j^k \ \Rightarrow \ 1 = - \sum^{n-2}_{k=0} b_k \frac 1{\alpha_j^{n-1-k}} \ \R...$
$1 = \left| \sum^{n-2}_{k=0} b_k \frac 1{\alpha_j^{n-1-k}} \right| \leq \sum^{n-2}_{k=0} |b_k| \frac 1 {|\alpha_j^{n-1-k}|} \l...$ which is a contradiction with (*). Because $|\alpha_j |\neq 1$ it follows that $|\alpha_j| < 1$ , and as $j$ was chosen arbitrarily, all $\alpha_2$ , $\alpha_3$ , $\ldots$ , $\alpha_n$ are smaller than 1 in absolute value.

No complex analysis whatsoever. Vess I'd expect you of all people never to say never in mathematics Wink

**Posted:** Wed Jan 26, 2005 4:01 pm

_________________
We all use math everyday: to forecast weather, to tell time, to handle money; we also use math to analyze crime, reveal patterns, predict behavior. Using numbers we can solve the biggest mysteries we know.

vess

**Posted:** Wed Jan 26, 2005 5:12 pm

grobber

There are also non-elementary but interesting ways of avoiding complex analysis, I think.

It's easier for me to write it as $P(x)=a_nx^n+x^{n-1}+a_{n-2}x^{n-2}+\ldots+a_1x+a_0$ , with $|a_n|+|a_{n-2}|+\ldots+|a_1|+|a_0|<1$ .

First we show, just as Valentint did, that there are no roots on the unit circle. Then, we construct the homotopy $h(x,t)=x^{n-1}+(1-t)\cdot(P(x)-x^{n-1})$ . We have $h(x,0)=P(x),\ h(x,1)=x^{n-1}$ . The important thing here is to notice that, just like we showed that there are no roots on the unit circle for $P$ , we can show that there are no roots on the unit circle for $h(x,t)$ , for any $t\in[0,1]$ . This means that it makes sense to talk about $H(x,t):S^1\to S^1,\ H(x,t)=\frac{h(x,t)}{|h(x,t)|}$ (here $S^1$ is the unit circle). Since the order of a curve wrt a point does not change with a homotopy if the curve does not cross that point during the process, it means that $\frac{P(x)}{|P(x)|}=H(x,0)$ has the same order as $H(x,1)=\frac{x^{n-1}}{|x|^{n-1}}=x^{n-1}$ (remember that $x$ takes values on the unit circle) wrt the origin of the plane, and this order must then be $n-1$ .

However, there is a theorem stating that the number of roots inside the unit disk for a polynomial $P$ with no roots on the unit disk is precisely the order of $H(x,0)$ defined as above wrt the origin (this isn't hard to show either).

P.S. I really hope there are no mistakes. You see, I'm a newbie in the field, so be forgiving Smile

**Posted:** Wed Jan 26, 2005 5:37 pm

vess

This, in essense, immitates the proof of Rouche's theorem, so it's basically the same idea.

**Posted:** Wed Jan 26, 2005 5:45 pm

grobber

I can see that, but there's still no complex analysis involved Smile

.

**Posted:** Wed Jan 26, 2005 5:50 pm

Valentin Vornicu

**Posted:** Wed Jan 26, 2005 9:48 pm

_________________
We all use math everyday: to forecast weather, to tell time, to handle money; we also use math to analyze crime, reveal patterns, predict behavior. Using numbers we can solve the biggest mysteries we know.

spx2 · Yang-Mills Theory Offline Joined: 07 Feb 2005 Posts: 646

i did not quite understand it,what am i supposed to do?

**Posted:** Fri Apr 08, 2005 10:43 pm