Is $x^n-\sum_{i=0}^{n-1}x^i$ irreducible in $\mathbb{Z}[x]$, for all $n$?

Question

Let the sequence of polynomials $p_n$ from $\mathbb{Z}[x]$ be defined recursively as $$p_n(x)= xp_{n-1}(x)-1$$ with initial term $p_0(x)=1$.

Then $$p_n(x)= x^n-\sum_{i=0}^{n-1}x^i $$

Question 1: is it true that $p_n(x)$ is always irreducible in $\mathbb{Z}[x]$?

The usual Eisenstein's criterion can not be applied directly here.

I also know that in order to prove the irreducibility over $\mathbb{Z}[x]$ it would suffice to find a prime $q$ for which $p_n(x)$ is irreducible in $\mathbb{Z}/q \mathbb{Z} [x]$.

In $\mathbb{Z}/q \mathbb{Z} [x]$ one may write $$p_n(x)= x^n+\sum_{i=0}^{n-1}(q-1)x^i .$$

Question 2: Can we also use Eisenstein criterion to prove irreducibility in $\mathbb{Z}/q \mathbb{Z} [x]$?

If yes, then the answer to question 1 would be yes as well, as it would suffice to choose $q=3$ since $2^2$ does not divide $3$. Is this correct?

Answer 1

The tool required here is Brauer's theorem. It is Theorem $2.2.6$ in the book

Prasolov, Victor V., Polynomials. Translated from the second Russian edition by Dimitry Leites., Algorithms and Computation in Mathematics 11. Berlin: Springer (ISBN 3-540-40714-6/hbk). xiv, 301 p. (2004). ZBL1063.12001.

The result states that

Let $a_{n-1} \geq ... \geq a_0$ be a decreasing sequence of positive integers for $n \geq 1$. Then $$ p(x) = x^n - a_{n-1}x^{n-1} - a_{n-2}x^{n-2} -\ldots - a_0 $$ is irreducible over $\mathbb Z$.

This applies to your case where $a_{n-1}=\ldots = a_0 = 1$, so that applying this for each $n$, you are done.

---

I'll provide a proof-with-spoilers of Brauer's theorem. It's based on the fact that the roots of the polynomial $p$ (which would be complex numbers) locate themselves in a certain way that disallows the possibility of factorization. This method is also used to prove other criteria such as Perron's criterion or any criterion involving domination of coefficients (where the coefficients have certain dominance properties over the other coefficients). This will be broken into two parts : a general principle, and the specific calculation. I'll not have any spoilers for the general principle.

The general principle involves Vieta's formulas (or just the fact that for a polynomial $p$, the constant term is the product of all the roots), and the specific calculation requires Rouche's theorem.

---

General principle : Let $f$ be a polynomial with integer coefficients and non-zero constant coefficient, such that all roots, except at most one, of $f$ lie in the region $\{z : |z| < 1\}$ (which we will shorten to $\{|z|<1\}$). Then, $f$ is irreducible over $\mathbb Z$.

Proof : Suppose that $f = f_1f_2$. Then we know that $f(0)= f_1(0)f_2(0)$ where $f_1(0),f_2(0)$ are both non-zero integers, because either one being zero would imply that $f(0)=0$, a contradiction. Now, because they are non-zero integers, we know that $|f_1(0)| \geq 1$ and $|f_2(0)| \geq 1$.

Suppose that $f$ has at most one root outside $\{|z|<1\}$. Then, since the roots of $f_1$ and the roots of $f_2$ together make up the roots of $f$, it follows that either all the roots of $f_1$ , or all the roots of $f_2$, lie inside $\{|z|<1\}$. Suppose that all the roots of $f_1$ lie in $\{|z|<1\}$.

Then $|f_1(0)| \geq 1$, but $f_1(0)$ is also equal to the product of all the roots of $f_1$, each of which is less than $1$ in modulus, hence $|f_1(0)|<1$, a contradiction.

Thus, $f$ cannot be factored i.e. it is irreducible.

---

We will now prove that exactly one root of $p(x)$ lies outside $\{|z|<1\}$, hence $p(x)$ is irreducible by the general principle.

• The idea is to first use the relationship between the $a_i$. To this effect, consider the polynomial $q(x) = (x-1)p(x)$. If we write $$ q(x) = x^{n+1} - b_{n-1}x^n + b_{n-2}x^{n-1} + b_{n-3}x^{n-2} + \ldots + b_{-1} $$ (so only $b_{n-1}x^n$ is subtracted, the rest are added) then what are the $b_i$ in terms of the $a_i$?

We have $b_{n-1} = a_{n-1}+1$, $b_{n-2} = a_{n-1} - a_{n-2},...,b_{-1} = a_0$.

• In particular, the $b_i$ are positive integers for all $i$, and $b_{n-1} = 1+b_{n-2}+...+b_0 + b_{-1}$. We now claim, that the only root of $q(z)$ on the disk $\{|z| = 1\}$ is $1$. Hint : When does equality hold in the reverse triangle inequality?

We have $|-b_{n-1}z^n + z^{n+1} + b_{n-2}z^{n-1} + \ldots + b_{-1}| \geq b_{n-1} -1-b_{n-2}-\ldots-b_{-1} = 0$, and equality occurs precisely when all the quantities $-b_{n-1}z^n,b_{n-2}z^{n-1},...,b_{-1}$ lie on a straight line that passes through $0$. Since $b_{-1}$ is a real number, this line can only be the real line i.e. we must have $z =\pm 1$ for equality , and $z=-1$ clearly fails, hence $z=+1$ is the only root.

Now, we prepare to apply Rouche's theorem to $q(z)$ so we look at $q(z) = z^{n+1} - r(z)$ where $$ r(z) = b_{n-1}z^n - b_{n-2}z^{n-1} - b_{n-3}z^{n-2} - \ldots - b_{-1} $$ and will now analyse $r(z)$. First claim : $r(z)$ has all its roots in the region $\{|z|<1\}$.

If $|z| \geq 1$, then we can use the relationship between the $b_i$ along with the triangle inequality to show that $|r(z)| \geq b_{n-1}|z|^n - b_{n-2}|z|^{n-1} - \ldots - b_{-1} \geq |z|^n(b_{n-1}-b_{n-2}-\ldots-b_{-1}) = |z|^{n} > 0$.

Second claim : For sufficiently small $\epsilon>0$, the inequality $|r(z)| >|q(z)+r(z)| = |z^{n+1}|$ holds in the region $\{|z|<1+\epsilon\}$. Hint : If $|z| = 1+\epsilon$, then bound $|r(z)| - |z^{n+1}|$ from below, by a polynomial in $\epsilon$ where the coefficient of $\epsilon$ is positive.

If $|z| = 1+\epsilon$ then $|r(z)| - |z^{n+1}| \geq b_{n-1}(1+\epsilon)^{n} - b_{n-2}(1+\epsilon)^{n-1} - \ldots - b_{-1} - (1+\epsilon)^{n+1}$ via the triangle inequality. The coefficient of $\epsilon$ on the RHS is $b_{n-2}+2b_{n-3}+\ldots + (n-1)b_{0}+nb_{-1} - 1$ which is positive. Hence, as $\epsilon \to 0$ the terms containing $\epsilon^k$ for $k>1$ will eventually be usurped in absolute value by the $\epsilon$ term which is positive. It follows that for $\epsilon>0$ small enough, we have $|r(z)| - |z^{n+1}|>0$ for $|z| = 1+\epsilon$.

• Combining both facts above, by Rouche's theorem $r(z)$ and $q(z)$ have the same number of roots inside the disk of radius $1+\epsilon$ around $0$, for every $\epsilon$ close to $0$. We conclude by taking $\epsilon\to 0$ and using the nature of $r$ that $q$ has exactly $n$ roots in the region $\{|z| \leq 1\}$. Excluding the root $1$, we know that $q$ and hence $p$ has exactly $n-1$ roots in the region $\{|z|<1\}$. Therefore, $p$ has exactly one root outside this region, completing the proof.

---

---

I forgot to add : I'm not sure how to prove that for any $n$ there is a prime $p$ such that $p_n$ must be irreducible in $Z/pZ$, and I don't even know if this is true. This is far more difficult to investigate, since one would need the exact roots of $p_n$ to calculate the discriminant of $p_n$, and then see which primes divide the discriminant : these are the only primes in which $p_n$ cannot possibly factor in that particular field. So this is a more difficult question.