# When are those polynomials irreducible?

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.

• How large have you searched up to? What range of $m$ and $n$? Sep 16, 2021 at 15:58
• @JoshuaZ It holds for $n$ a prime less than 100 and for $m <100$ there. Some random experiments were also done with random primes and $m$ and no counter example was found.
– Mare
Sep 16, 2021 at 15:59
• I don't know if small values of n interest you, but this paper (mscand.dk/article/view/10593) appears to provide a positive answer to Question 2 when n=2 or 3. Sep 18, 2021 at 19:35

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

• Thank you very much. Is it possible to contact you via email?
– Mare
Sep 21, 2021 at 9:06