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.

  • $\begingroup$ How large have you searched up to? What range of $m$ and $n$? $\endgroup$
    – JoshuaZ
    Sep 16 at 15:58
  • $\begingroup$ @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. $\endgroup$
    – Mare
    Sep 16 at 15:59
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 18 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

  • $\begingroup$ Thank you very much. Is it possible to contact you via email? $\endgroup$
    – Mare
    Sep 21 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.