# Polynomial with the primes as coefficients irreducible?

If $p_n$ is the $n$'th prime, let $A_n(x) = x^n + p_1x^{n-1}+\cdots + p_{n-1}x+p_n$. Is $A_n$ then irreducible in $\mathbb{Z}[x]$ for any natural number $n$? I checked the first couple of hundred cases using Maple, and unless I made an error in the code those were all irreducible. I have thought about this for a long time now, and asked many others, with no answer yet.

-
You might want to entertain the possibility that this is a very hard problem. It might not be, but if it's not a "problem from a book", if it's just a "made-up" problem, then it might be hard. Reducibility of a polynomial is a very subtle fact about the coefficients, and we can't even prove if there are infinitely many primes of the form p+2, or n^2+1, or 2p+1, or... – Kevin Buzzard Mar 13 '10 at 21:16
Assuming one can rule out the rational root $-p_n$, I am trying to see the consequences of your coefficients being strictly positive and strictly increasing, ignoring primality. I just have this sense that reducible polynomial coefficients $a_j > 0$ "ought to" either exhibit faster growth themselves, as in $(x + B)^n$ for large fixed $B$, or have maximum value $a_j$ in the middle, not at either end. It worked for $n=4$, when I get access to Maple again I will experiment with this. Meanwhile, I like Ram Murty's article, through en.wikipedia.org/wiki/Cohn%27s_irreducibility_criterion – Will Jagy Mar 13 '10 at 21:38
A reducible monic polynomial with prime constant coefficient has to split into monic factors whose constant coefficients are either \pm 1 or \pm p, and the latter case occurs exactly once. In particular, such a polynomial has to have at least one root on or inside the unit circle and at least one root outside. Can anyone rule this out? – Qiaochu Yuan Mar 13 '10 at 23:27
@Kevin, Douglas: after multiplying this new polynomial by (x - 1), it's not hard to see by the triangle inequality that it can't have any roots inside or on the unit circle. – Qiaochu Yuan Mar 14 '10 at 1:38
@Kevin: For your last question, it has been proven so for almost all integers n. It was a conjecture of Filaseta. Reference: "Classes of polynomials having only one non-cyclotomic irreducible factor", by Borisov, Filaseta, Lam, Trifonov. – Gjergji Zaimi Mar 14 '10 at 1:47

I will prove that $A_n$ is irreducible for all $n$, but most of the credit goes to Qiaochu.

We have $$(x-1)A_n = b_{n+1} x^{n+1} + b_n x^n + \cdots + b_1 x - p_n$$ for some positive integers $b_{n+1},\ldots,b_1$ summing to $p_n$. If $|x| \le 1$, then $$|b_{n+1} x^{n+1} + b_n x^n + \cdots + b_1 x| \le b_{n+1}+\cdots+b_1 = p_n$$ with equality if and only $x=1$, so the only zero of $(x-1)A_n$ inside or on the unit circle is $x=1$. Moreover, $A_n(1)>0$, so $x=1$ is not a zero of $A_n$, so every zero of $A_n$ has absolute value greater than $1$.

If $A_n$ factors as $B C$, then $B(0) C(0) = A_n(0) = p_n$, so either $B(0)$ or $C(0)$ is $\pm 1$. Suppose that it is $B(0)$ that is $\pm 1$. On the other hand, $\pm B(0)$ is the product of the zeros of $B$, which are complex numbers of absolute value greater than $1$, so it must be an empty product, i.e., $\deg B=0$. Thus the factorization is trivial. Hence $A_n$ is irreducible.

-
Fantastic! So the statement is actually stronger, right? The coefficients can be any sequence of non-decreasing positive integers as long as the constant term is prime. – Qiaochu Yuan Mar 14 '10 at 7:58
All you use is that the coefficients are strictly increasing and the constant term is prime, right? Will Jagy also pointed out that strictly increasing was a funny property for a reducible polynomial to have. – Kevin Buzzard Mar 14 '10 at 8:04
I think Qiaochu said it right, and they need only be non-decreasing rather than strictly increasing. (You just need the b_k's to be nonnegative.) – Jonas Meyer Mar 14 '10 at 8:08
@Kevin: Yes, that's right. @Qiaochu and Jonas: Nondecreasing is not quite strong enough; consider $x^3+x^2+2x+2$. But you can say that if $f(x)$ is a monic irreducible polynomial with nondecreasing coefficients and $f(0)$ is prime and $f'(0)<f(0)$, then $f(x)$ is irreducible. – Bjorn Poonen Mar 14 '10 at 8:28
Thank you for the correction. I see one of my oversights: if some of the b_k's can be zero, equality in the inequality doesn't necessarily imply that x=1, e.g. if the odd indexed coefficients are zero and n is odd, like in your example. It seems to generalize to the case where the set of $k$ such that $b_k\neq 0$ has gcd 1. In particular, as you mentioned it works if $b_1\neq0$. – Jonas Meyer Mar 14 '10 at 8:57

Since I don't have enough "reputation" to comment on Bjorn's answer, I will write this in an answer. The remark about the location of the zeros of $A_n$ goes back at least to Kakeya, On the Limits of the Roots of an Algebraic Equation with Positive Coefficients, Tôhoku Math. J., vol. 2, 140-142, 1912. It also appears in the nice book by E. Landau, Darstellung und Begründung einiger neuerer Ergebnisse der Funktionentheorie, Springer 1916, (Hilfssatz p.20).

-