When are those polynomials irreducible?

Question

Let $f_n (x) := x^n - x^{n-1} - x^{n-2} - ... - x^2 - x - 1$, which is an irreducible polynomial by corollary 2.2 of https://www.sciencedirect.com/science/article/pii/S0022404903002457.

Question: For which $m,n \geq 2$ is the polynomial $f_n(x^m)$ irreducible over the integers?

Especially interesting is the case when $n$ (or $m$) is a prime.

Question 2: Is $f_n(x^m)$ irreducible whenever $n$ is a prime?

Computer experiments found no counterexample so far.

Answer 1

We show that for all $m, n \geq 2$ the polynomial $f_n \left( x^m \right)$ is irreducible.

This answer is based on a wonderful technique I learnt a few years ago from an answer on MSE by Keith Conrad, and I encourage the reader to look at that answer first (it is not very long), as it shows the key ideas in a much nicer setup. I do here a lot of casework which can probably be shortened, but I didn't really attempt to streamline it. If $$p(x) = \sum_{i = 0}^{n} a_i x^i$$ is a polynomial of degree $n$, then we define $$\tilde{p} (x) = \sum_{i = 0}^{n} a_{n - i} x^i$$ that is the polynomial with coefficients reversed. Algebraically, $\tilde{p} (x) = x^{\mathrm{deg} (P)} p \left( \frac{1}{x} \right)$. Notice that $$(x - 1) f_n (x) = x^{n + 1} - 2 x^n + 1$$ Therefore, to understand the factorization of $f_n \left( x^m \right)$, it suffices to understand the factorization of $$x^{n m + m} - 2 x^{n m} + 1$$ Fix $n, m$ and from now on we will call this polynomial $f(x)$. Throughout, we will assume that $n > 2$: if $n = 2$ the method that we use shows that for all $m$ the polynomial $f_{n} \left( x^m \right)$ is irreducible.

Suppose that there was a factorization into nonconstant monic polynomials $g, h$ $$f = g h$$ Then, taking $k = g \tilde{h}$ or $k = - g \tilde{h}$ (according to whether $g(0) = 1$ or $- 1$ respectively), we see that $k$ is a monic polynomial such that $$f \tilde{f} = k \tilde{k}$$ We will show that this implies that $k = f$ or $k = \tilde{f}$. Write $$k(x) = \sum_{i = 0}^{n m + m} a_i x^i$$ and then $$\tilde{k} (x) = \sum_{i = 0}^{n m + m} a_{n m + m - i} x^i$$ We know that $a_{n m + m} = 1$, and by looking at the constant coefficient of $k \tilde{k} = f \tilde{f}$ we see that $a_0 = 1$. Now, the key point: compare the coefficient of $x^{n m + m}$ in $f \tilde{f} = k \tilde{k}$: it is the sum of the squares of the coefficients of $f$ and $k$ respectively, therefore $$\sum_{i = 0}^{n m + m} a_{i}^2 = 6$$ It will be useful in the cases below to see explicitly what $f \tilde{f}$ is: $$f \tilde{f} = x^{2 m n + 2 m} - 2 x^{2 m n + m} - 2 x^{m n + 2 m} + 6 x^{m n + m} - 2 x^{m n} - 2 x^{m} + 1$$ From the coefficients of $k$ we already now, there are two possibilities:

Case 1: There exist $m n + m > a > b > c > d > 0$ such that $$k(x) = x^{n m + m} \pm x^a \pm x^b \pm x^c \pm x^d + 1$$ Looking at the coefficient of $x^{2 n m + 2 m - 1}$ in $k \tilde{k}$ we see that we must have $a = n m + m - 1, \ d = 1$ and $x^a, x^d$ must both come with a minus sign. We must have $k(1) = 0$, and so without loss of generality (otherwise we look at $\tilde{k}$) $x^b$ comes with a plus sign and $x^c$ with a minus. Now,

$$k \tilde{k} = \left( x^{m n + m} - x^{m n} + x^b - x^c - x^m + 1 \right) \times \\ \left( x^{m n + m} - x^{m n} - x^{m n + m - c} + x^{m n + m - b} - x^m + 1 \right)$$ Looking at the coefficient of $x^{2 m n}$, since $n > 2$ the positive contribution of $\left( - x^{m n} \right) \left( x^{- m n} \right)$ must cancel out, and the only options are $c = 2 m, m n - m$. In particular $c$ is divisible by $m$. Substituting $x$ to be a primitive $m$-th root of unity, we get that $x^b = 1$, and therefore $b$ is divisible by $m$ as well. Since $m n > b > c$, this rules out the option of $c$ being $m n - m$, and therefore we have $c = 2 m$. Now looking at the coefficient of $x^{m n}$ we see that we must have $b = m n - m$, but this means that the coefficient of $x^{2 m n}$ is wrong, and so we get a contradiction. Therefore, what happens is

Case 2: for some $m n + m > a > 0$, we have $k(x) = x^{m n + m} \pm 2 x^a + 1$. It is immediate to see in this case that $a = mn, m$ and $x^a$ comes with a minus sign, that is $k = f, \tilde{f}$ and without loss of generality, $k = f$.

Therefore $g h = \pm g \tilde{h}$, that is $h = \pm \tilde{h}$. However, notice that $$\gcd \left( f, \tilde{f} \right) = \gcd \left( x^{m n + m} - 2 x^{m n} + 1, x^{m n - m} - 1 \right) = \\ = \gcd \left( x^{2 m} - 2 x^{m} + 1, x^{m n - m} - 1 \right)$$ It is easy to see that the only roots of $x^{2 m} - 2 x^m + 1$ which are on the unit circle are the $m$-th roots of unity, and they each appear with multiplicity $1$, therefore $\gcd \left( f, \tilde{f} \right) = x^m - 1$. Since $h | f, \ \tilde{h} | \tilde{f}$ we have $h | \gcd \left( f, \tilde{f} \right) = x^m - 1$.

Over all, we have shown that in every nontrivial factorization of $\left( x^m - 1 \right) f_n \left( x^m \right) = g h$, one of the factors on the right hand side divides $x^m - 1$, which immediately implies that $f_n \left( x^m \right)$ is irreducible: if there was a factorization $f_n \left( x^m \right) = u(x) v(x)$ then $g(x) = u(x), \ h(x) = \left( x^m - 1 \right) v(x)$ would be a counterexample. QED