If $p_n$ is the $n$'th prime, let $A_n(x) = x^n + p_1x^{n1}+\cdots + p_{n1}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.

6$\begingroup$ 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 "madeup" 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... $\endgroup$ – Kevin Buzzard Mar 13 '10 at 21:16

3$\begingroup$ 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 $\endgroup$ – Will Jagy Mar 13 '10 at 21:38

9$\begingroup$ 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? $\endgroup$ – Qiaochu Yuan Mar 13 '10 at 23:27

7$\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Mar 14 '10 at 1:38

5$\begingroup$ @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 noncyclotomic irreducible factor", by Borisov, Filaseta, Lam, Trifonov. $\endgroup$ – 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 $$(x1)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 $(x1)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.

6$\begingroup$ Fantastic! So the statement is actually stronger, right? The coefficients can be any sequence of nondecreasing positive integers as long as the constant term is prime. $\endgroup$ – Qiaochu Yuan Mar 14 '10 at 7:58

3$\begingroup$ 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. $\endgroup$ – Kevin Buzzard Mar 14 '10 at 8:04

$\begingroup$ I think Qiaochu said it right, and they need only be nondecreasing rather than strictly increasing. (You just need the b_k's to be nonnegative.) $\endgroup$ – Jonas Meyer Mar 14 '10 at 8:08

2$\begingroup$ @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. $\endgroup$ – Bjorn Poonen Mar 14 '10 at 8:28

$\begingroup$ 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$. $\endgroup$ – 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, 140142, 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).