# irreducibility of polynomials with integer coefficients

Consider the polynomial $$p(x)=x^9+18x^8+132x^7+501x^6+1011x^5+933x^4+269x^3+906x^2+2529x+1733$$ Is there a way to prove irreducubility of $p(x)$ in $\mathbb{Q}[x]$ different from asking to PARI/GP?

-
$1733$ is a prime. –  Inceptio Mar 19 '13 at 10:46
@Inceptio: But then $3$ divides the leading coefficient, and you can't apply this criterion... –  Lior B-S Mar 19 '13 at 11:13
This looks (but I have only experiments, no proof) like one of those polynomials that are irreducible over the rationals, but is reducible modulo each prime. –  Andreas Caranti Mar 19 '13 at 11:27
This polynomial is probably the one OP is discussing here. At least it has the prescribed zero (also sprach Mathematica 3.0). AFAICT that also explains the observation made by @AndreasCaranti - over a finite prime field the two polynomials either split or don't, and you never get more than a sextic extension as their compositum. –  Jyrki Lahtonen Mar 19 '13 at 11:54
@Inceptio. No! The polynomial $x^2+4x$ is reducible. Adding the prime $3$ to it gives us another reducible polynomial $x^2+4x+3=(x+3)(x+1)$. No such simple rule holds. –  Jyrki Lahtonen Mar 19 '13 at 12:38

A starting point: Modulo $3$ the polynomial $p$ takes the form $$red_3(p) = x^9-x^3-1\in \mathbb{F}_3[x].$$ Since raising to $3$ is the frobenius automorphism we have $$red_3(p) = (x^3-x-1)^3.$$ The polynomial $x^3-x-1$ is irreducible modulo three.

From all of this we get that if $p$ factors to a product $$p=p_1\cdots p_r,$$ with $p_1, \ldots, p_r\in \mathbb{Z}[x]$ monic and irreducible over $\mathbb{Q}$, then $r\leq 3$ and the degree of each factor is at least $3$.

-
why the last line of your answer implies $p$ irreducible? –  bateman Mar 19 '13 at 11:04
It doesn't. As I wrote in the first line, it's just a starting point... –  Lior B-S Mar 19 '13 at 11:08
ok, thank you for suggestion –  bateman Mar 19 '13 at 11:12
@bateman: This route (reduce modulo a prime) will never prove this polynomial to be irreducible. –  Jyrki Lahtonen Mar 19 '13 at 12:02
@JyrkiLahtonen: True, proves it is irreducible for certain modulo prime. –  Inceptio Mar 19 '13 at 12:04

This polynomial has the element $\alpha^2+\beta$ described in this question as a root. My answer to that question implies among other things that the minimal polynomial of that element is of degree 9, so this polynomial has to be irreducible.

-
Is there any different way? Using the fact that $1733$ is a prime. And other coefficients of $x^n(n \epsilon 1,2,3,4,5,6,7,8)$ are divisible by $3$? –  Inceptio Mar 19 '13 at 15:00
@Inceptio: I'm sure there are other ways, but I don't see a cleaner one. The coefficient of the cubic term, 269, is not divisible by three. Modulo 3 information is already utilized in Lior's answer. That shows that it suffices to exclude the possibility of a cubic factor. May be you can do that by some brute force trick? The constant term of such a factor would have to be $\pm1$ or $\pm 1733$, so there are only those four cases, each with two unknown parameters. Go for it :-) –  Jyrki Lahtonen Mar 19 '13 at 15:06
Yeah, I always miss a fact. And the cases you're talking about. I assumed $(\pm1+a_1x+a_2x^2+a_3x^3+...a_nx^n)(\pm 1733+b_1x+b_2x^2+b_3x^3+...b_kx^k)=p(x)$. I just need to prove this it is impossible.? –  Inceptio Mar 19 '13 at 15:12

If you don't mind evaluating $p(x)$ several times and factoring large numbers, you could find $10$ values for $x$ which are separated by more than $2$, for which $p(x)$ is prime (or a unit). This would imply that $p(x)$ (having degree $9$) is irreducible.

The logic being: If $p(\alpha)$ is prime and if $p(x) = q(x) r(x)$, then $q(\alpha)$ or $r(\alpha)$ must be a unit ($\pm1$). Given that $q(x), r(x)$ must also have degrees that sum to that of $p(x)$, the number of times they can take the value of a unit is restricted - maximum is two times the degree of $p(x)$, to account for two possible signs for the units. However, if the $x$ values are separated by more than $2$, then for any of $q(x)$ and $r(x)$ the sign of the unit must be the same, and then there cannot be then more prime values than the degree of $p(x)$.

Here, we have $p(x)$ prime for $x \in \mathrm{A} = \{-16, -10, -3, 0, 3, 6, 14, 17, 28, 39 \}$. (I have omitted values such as $\{-12, -4, -2, -1, 5\}$ which also give primes but are too close to elements of $\mathrm{A}$, to avoid having to find $19$ prime values). As these are $10$ values separated by more than $2$, $p(x)$ is irreducible.

-