Checking Irreducibility to a Polynomial with Non-constant Degree over Integer

Question

Let the n-th Polynomial $P_n(x)$ be $$P_n(x) = n + \prod_{k=1}^{n} (x - k)= (x - 1)(x - 2)(x - 3)\cdots(x - n) + n$$

How to prove that for every $n$, $P_n(x)$ is irreducible over integers, or more generally rational field?

I tried using Wolfram Alpha to check some values, and it results in irreducible. As $n$ gets bigger and bigger, it is hard to check if it is irreducible or not. And, I tried to use the fact that $1$ to $n$ is a root of $P_n(x) - n$, but got stuck.

Answer 1

The following is only a partial answer, but I believe it is relevant to the question.

For $\,n \ge 13\,$ the result follows from a far more general, albeit lesser known, irreducibility criterion of Pólya from Verschiedene Bemerkungen zur Zahlentheorie (1919). Below is the English translation of Prasolov's Russian translation in his book Polynomials.

2.2.3 Irreducibility of polynomials attaining small values

Theorem 2.2.8 (Pólya). Let $\,f\,$ be a polynomial of degree $\,n\,$ with integer coefficients and define $\,m = \left\lfloor\frac{n+1}{2}\right\rfloor\,$. Suppose that, for $\,n\,$ different integers $\,a_1,\ldots,a_n\,$ we have $\,|f(a_i)| \lt 2^{-m}m!\,$ and the numbers $\,a_1,\ldots,a_n\,$ are not roots of $\,f\,$. Then $\,f\,$ is irreducible.

With $\,a_i=i\,$, the criterion implies that all polynomials $\,(x-1)(x-2)\ldots(x-n) \pm k\,$ are irreducible for $\,k = 1, 2, \ldots, \left\lfloor\dfrac{m!}{2^m}\right\rfloor\,$ where $\,m = \left\lfloor\dfrac{n+1}{2}\right\rfloor\,$. For $\,n \ge 13\,$ it is straightforward to show that $\,n \lt \left\lfloor\dfrac{m!}{2^m}\right\rfloor\,$, so the conclusion in OP's question follows.

I can't read German, but the very specific example $\,x(x-1)\ldots(x-n+1) + \lambda n\,$ appears to be mentioned in Pólya's paper as a concrete solution $\lambda=\pm 1$ to Hilbert's existential irreducibility theorem in this case.

---

An English translation of Pólya's proof (adapted to the present case):

Assume contrariwise that $P_n(x)=g(x) h(x)$ for some $g,h\in\Bbb{Q}[x]$. By Gauss' Lemma we can w.l.o.g. assume that $g,h\in\Bbb{Z}[x]$. One of the factors, say $g(x)$, has degree at least $m\ge\lfloor\dfrac{n+1}2\rfloor$. Observe that $m+1=\deg g(x)+1\le n$ as otherwise the other factor $h(x)$ is a constant.

By Lagrange interpolation formula we can write $$ g(x)=\sum_{i=1}^{m+1} g(i) \Delta_i(x), $$ where for all $i, 0< i\le m+1$, $$\Delta_i(x)=\frac{\prod_{0< j\le m+1, j\neq i}(x-j)}{\prod_{0< j\le m+1, j\neq i}(i-j)}.$$ The leading coefficient $c_i$ of $\Delta_i(x)$ has absolute value $$|c_i|=\frac1{i!(m-i)!}=\frac1{m!}\binom m i.$$ Furthermore, $g(i)$ must be a factor of $P_n(i)=n$, so $|g(i)|\le n$.

Putting all these pieces together, the triangle inequality says that the leading coefficient $c=1$ of $g(x)$ has an upper bound $$ |c|\le\sum_{i=1}^{m+1} |g(i)|\cdot |c_i|\le \frac{n}{m!}\sum_{i=0}^m\binom m i=\frac{n\cdot 2^m}{m!}. $$ As $c=1$, this is a contradiction whenever $n\cdot 2^m<m!$.

Answer 2

The dxiv's answer provides a sufficient criterion of Pólya (which I have completely missed as I was writing this answer), here is nevertheless an alternative that uses generalized but slightly more complicated version of the same criterion allowing to prove the result for $n\geq 7$.

We can show the irreducibility using Theorem 2 from Irreducibility of Polynomials with Low Absolute Values by R. J. Levit:

Theorem (Levit). Let $f(x)$ be an integral polynomial of exact degree $n$, and let $N=\lfloor \frac{n+1}{2} \rfloor$. If there are $n$ integers, $x_1 <x_2 < \dots < x_n$ such that $$ 0<|f(x_i)|<\frac{1}{2^{N-1}}\left(\frac{1}{2}\left\lfloor \frac{n}{2} \right\rfloor\right)^{(N)} \ \ \ (i=1,2,\dots,n), $$ then $f(x)$ is irreducible over the field of rational numbers.

Proof. See Levit's article.

Here $(x)^{(N)}=x(x+1)\cdots(x+N-1)$ is the rising factorial.

In our case, let $x_i=i$ for $i=1,\dots,n$. Then $P_n(x_i)=n>0$ and irreducibility follows from the inequality:

Let $n\geq 7$ be an integer and $N=\lfloor \frac{n+1}{2} \rfloor$. Then $$ n<\frac{1}{2^{N-1}}\left(\frac{1}{2}\left\lfloor \frac{n}{2} \right\rfloor\right)\left(\frac{1}{2}\left\lfloor \frac{n}{2} \right\rfloor+1\right)\cdots\left(\frac{1}{2}\left\lfloor \frac{n}{2} \right\rfloor +N-1\right)\tag{1} $$

The proof can be done for example by induction, also it might be helpful to split to two cases by parity. Let me just sketch the case for even $n$, odd case can be done similarly. Let $n=2k$, the inequality can be rearranged equivalently into $$ 2^{2k}k< k \left( k +2\right)\cdots\left( k +2(k-1)\right). $$ Base case is given by $k=4$. For the induction step notice \begin{align} 2^{2k+2}(k+1) &=2^{2k}k\cdot 4\frac{k+1}{k}\\ &< k \left( k +2\right)\cdots\left( k +2(k-1)\right)\cdot 4\frac{k+1}{k}\\ &<(k+1)(k+3)\dots(k+1+2k) \end{align} where for the last term we used $4\frac{k+1}{k} < ( k+1 +2k)$, which is equivalent to $3k^2-3k-4>0$.

I leave it up to you (or to some perhaps even stronger criterion) to verify that handful of remaining polynomials with $n\leq 6$ are irreducible as well.