Is $x^{n}-x-1$ irreducible?

Question

Is it true that for every $n \in \mathbb{N}$, $x^{n}-x-1$ is irreducible in $\mathbb{Z}[x]$?

The standard irreducibility criteria seem to fail.

Answer 1

This is true; it is due to Selmer. Ljunggren (On the irreducibility of certain trinomials and quadrinomials, Math. Scand. 1960) has obtained the complete list of reducible trinomials with $\pm 1$ coefficients. For more details see Gerry Myerson's answer to this question, which contains a review of Ljunggren's paper: About irreducible trinomials . To this I may add Prasolov's monograph Polynomials as a (probably) more accessible reference; there, you will find a complete treatment of Ljunggren's result.

Added. As Greg Martin notes, the trinomial $x^n-x-1$ in fact has Galois group $S_n$. Osada's paper to which he refers is The Galois groups of the polynomials $X^n + aX^l+b$ (J. Number Theory 25, pp. 230-238, 1987), although the result already appears in an earlier paper by E. Nart and N. Vila, quoted [7] in loc.cit. However, the proof of the maximality of the Galois group uses Selmer's result that the trinomial is irreducible, and does not yield a new proof of irreducibility.

The argument [that Selmer's result implies full Galois group] is presented in section 4.4 of Serre's 1988 course Topics in Galois Theory, see Remark 2 on page 42. You may find this text on the web:

http://www.msc.uky.edu/sohum/ma561/notes/workspace/books/serre_galois_theory.pdf

To summarize the argument, which also works for a wider class of irreducible trinomials, one checks directly that $x^n-x-1$ has at most one double root at each ramified prime. Consequently, all non-trivial inertia subgroups are generated by a transposition. Since $\mathbb{Q}$ has no unramified extensions, the Galois group of any polynomial over $\mathbb{Q}$ is generated by its inertia subgroups, and hence we see that our $G \subset S_n$ is generated by transpositions of $S_n$. Selmer's result implies that $G$ is also transitive, and it is a standard fact (proved in every course in Galois theory) that a transitive subgroup of $S_n$ generated by transpositions must be the full $S_n$.