51

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.

Yemon Choi
  • 25,496
Tobias Kildetoft
  • 2,488
  • 6
    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
  • 3
    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 http://en.wikipedia.org/wiki/Cohn%27s_irreducibility_criterion – Will Jagy Mar 13 '10 at 21:38
  • 1
    I just confirmed your calculations up to n=1000, so I'm inclined to believe the statement. I'm also inclined to believe it is difficult. – Ben Weiss Mar 13 '10 at 23:01
  • @Will: if n>2 then x=-p_n can't be a root because |x^n|=|p_n^n| is bigger than the sum of the absolute values of the other coefficients, e.g. 5^3=45^2+45+5>25^2+35+5. – Kevin Buzzard Mar 13 '10 at 23:02
  • PS @Will if you have access to a computer and the internet then you can probably give yourself access to pari, which is free and does polynomials in 1 variable cheerfully. – Kevin Buzzard Mar 13 '10 at 23:19
  • 9
    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
  • 2
    @Qiaochu: I can't rule it out, and indeed it seems hard to make this line of attack go anywhere. I am more inclined to follow up Will's observation. Here's another question: is x^n+2x^{n-1}+3x^{n-2}+...+(n+1) always irreducible for n>=1? This question is of course inspired by Will's observations and is perhaps more likely to be tractable... – Kevin Buzzard Mar 13 '10 at 23:50
  • Numerically, it looks like all roots are outside the unit circle for a few cases of degree 100-500, both for the original and Kevin Buzzard's variation. – Douglas Zare Mar 14 '10 at 01:05
  • 7
    @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 01:38
  • 5
    @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 01:47
  • @Qiaochu: yes. Bjorn's argument seemed to put together both of the ideas here :-) – Kevin Buzzard Mar 14 '10 at 08:42

2 Answers2

76

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.

Bjorn Poonen
  • 23,617
  • 7
    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 07:58
  • 3
    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 08: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 08:08
  • 3
    @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 08: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 08:57
  • Wonderful solution just magical !! – Aditya Guha Roy Jul 22 '17 at 10:36
12

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).

Francesco Sica
  • 271