# Irreducibility of $x^n-x-1$ over $\mathbb Q$

I want to prove that

$p(x):=x^n-x-1 \in \mathbb Q[x]$ for $n\ge 2$ is irreducible.

My attempt.

1. GCD of coefficients is $1$, $\mathbb Q$ is the field of fractions of $\mathbb Z$, and $\mathbb Z$ is UFD. Hence, $p(x)$ is irreducible over $\mathbb Q$ iff it's irreducible over $\mathbb Z$ (Gauss's lemma).

2. Let $m\in \mathbb Z$ such that $\varphi(m)=n$ (Euler's totient). Make reduction of $p(x)$ by modulo $m$. Because of $\overline{x^n}=\overline{x^{\varphi(m)}}=\overline{1}$, we get $\overline{p(x)}=\overline{1-x-1}=\overline{-x}$, which is irreducible. Hence, $p(x)$ is irreducible.

Does this proof is correct?

UPDATE. Thanks to Calvin Lin. My mistake is: not for all $n$ we can find such $m$. OK, but as for the rest, does my proof is correct for such $n$, that $n=\varphi(m)$ for an integer $m$? And can it be some changed for all $n$, i.e. can we find such modulo that $\overline{p(x)}$ is irreducible for every $n\ge 2$?

-
How do you know that there is an $m$ such that $\phi(m) = n$? –  Calvin Lin May 16 '13 at 16:04
Just knowing $k^{\phi(m)}\equiv 1\pmod m$ for all $k\in\mathbb Z$ does not make the equality $x^{\phi(m)}=1$ hold in $\mathbb Z_m[x]$. –  Ted Shifrin May 16 '13 at 16:15
@Ted Shifrin: Why? –  Corvus May 16 '13 at 16:20
@user14284: the congruence $k^{\varphi(m)} \equiv 1 \bmod m$ is not true for all integers $k$, only those $k$ that are rel. prime to the modulus $m$, Your polynomial congruence $x^{\varphi(m)} \equiv 1 \bmod m{\mathbf Z}[x]$ is just false. Try it when $m = 3$: is $x^2 \equiv 1 \bmod 3{\mathbf Z}[x]$? Nope.... –  KCd May 16 '13 at 18:40
The point I was making is a rather subtle one, which students struggle with in abstract algebra. There is a big difference between $f(x)\in F[x]$ and $f(x)$ as a function that you'd study in calculus. For example, baby Fermat says that $f(x)=x^p-x\in(\mathbb Z/p\mathbb Z)[x]$ has the value $0$ when you evaluate it at every element of $\mathbb Z/p\mathbb Z$. Nevertheless, it is not the $0$-polynomial! –  Ted Shifrin May 19 '13 at 18:06

I doubt an easy proof of the irreducibility exists in general. If $n$ is a prime, then the polynomial is Artin-Schreier and handled easily.

Selmer gave a clever proof in the general case, working explicitly with the roots of the polynomial in $\mathbb{C}$. See E. S. Selmer, On the irreducibility of certain trinomials, Math. Scand. 4 (1956), 287-302, available here.

-
Not only is the proof of irreducibility of $x^n-x-1$ over ${\mathbf Q}$ nontrivial, but Selmer points out in Section 6 of his paper that the method that he developed to prove irreducibility of these polynomials doesn't seem viable as an irreducibility test for other families of polynomials, aside from the one other family he considers in his paper. –  KCd May 16 '13 at 18:31
There is a paper from 1960 by Ljunggren with another approach to proving the irreducibility of these trinomials. See the answer to mathoverflow.net/questions/56579/about-irreducible-trinomials –  KCd Jun 20 '13 at 0:32
@KCd: That is interesting. Thanks! –  Brandon Carter Jun 20 '13 at 14:23
See my answer for a sketch of a proof that is easier to work through than Selmer's. –  KCd May 18 '14 at 21:46
@awllower: It's updated now. –  Brandon Carter Oct 30 '14 at 0:43

I will sketch a proof of the irreducibility of $x^n - x - 1$ over ${\mathbf Q}$ for $n \geq 2$ that is simpler than Selmer's argument. I learned of this approach from David Rohrlich, who learned it from Michael Filaseta.

Let $f(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$ be nonzero in $F[x]$ for any field $F$. Let $\tilde{f}(x) = x^{\deg f}f(1/x)$ be its reciprocal polynomial: $\tilde{f}(x) = a_0x^n + a_1x^{n-1} + \cdots + a_{n-1}x + a_n$. If $f(0) \not= 0$ then $f$ and $\tilde f$ have the same degree. Easily if $f = gh$ then $\tilde{f} = \tilde{g}\tilde{h}$, and $\widetilde{cf} = c\tilde{f}$ for any constant $c$.

In terms of factorization over roots, if $f(0) \not= 0$ then $$f(x) = c(x-r_1)\cdots(x-r_n) \Longrightarrow \tilde{f}(x) = f(0)c(x - 1/r_1)\cdots(x-1/r_n).$$

Step 1: Let $f(x) \in {\mathbf Z}[x]$ satisfy (i) $f(0) \not= 0$ and (ii) $f(x)$ and $\tilde{f}(x)$ have no common roots. If $f(x) = g(x)h(x)$ for some nonconstant $g(x)$ and $h(x)$ in $\mathbf Z[x]$, show there is a $k(x)$ in $\mathbf Z[x]$ with $\deg k = \deg f$ such that $f\tilde{f} = k\tilde{k}$ and $k \not= \pm f$ or $\pm\tilde f$. If $f(x)$ is monic and $f(0) = \pm 1$, show you can take $k$ to be monic. (Hint: Use $k = \pm g\tilde{h}$ for a suitable choice of sign.)

Step 2: For $n \geq 2$, show the polynomial $x^n - x - 1$ doesn't have any roots in common with its reciprocal.

Step 3: Let $f(x) = x^n - x - 1$ for $n \geq 2$. Suppose $f\tilde{f} = k\tilde{k}$ for some monic $k \in \mathbf Z[x]$ of degree $n$. Compare the degree $n$ coefficients on both sides of the equation $f\tilde{f} = k\tilde{k}$ to show that $k$ must be a sum of 3 monomials whose coefficients are all $\pm 1$. Then look at the top 3 nonzero terms on both sides to show $k = f$ or $k = -\tilde{f}$.

Step 4: Combine all the previous steps to deduce irreducibility of $x^n - x - 1$ over $\mathbf Q$.

Exercise: Use the same argument to determine when $x^n + x + 1$, $x^n - x + 1$, and $x^n + x - 1$ are irreducible over $\mathbf Q$. (With a computer you can find in each case that there is a congruence condition on $n$ for it to be reducible, and this turns out to be exactly the condition for $f(x)$ and $\tilde{f}(x)$ to have a common root, which will be either a 3rd or 6th root of unity.)

-
This is outlandishly clever! Make sure it gets included into some textbook or lecture notes :-) –  fedja Jun 16 '14 at 3:56
Could the argument presented here be used to solve this problem as well ? –  Lucian Feb 7 at 14:51