# Irreducibility of a class of polynomials

This question is directly inspired by this question. Consider polynomials of the form $$p(x) = \prod_{i=1}^n(x-i)^2 - d.$$ For which values of $n$ and $d$ is $p(x)$ irreducible? There is a theorem of Polya, cited in the original question, which states that:

If for $n$ integral values of $x,$ a polynomial $q(x)$ of degree $n$ has values which are different from $0,$ are smaller in absolute value than $$\frac{\lceil n/2\rceil!}{2^{\lceil n/2\rceil}},$$ then $q(x)$ is irreducible over $\mathbb{Q}.$

This seems to not quite apply to the given type of polynomial (though it would, if there were no squares).

In this paper, there is a reference to a paper of Brauer, Brauer, and Hopf(!) from 1926 which addresses the question (of Schur) on irreducibility of polynomials of the form $g(f(x)),$ but it seems that their $g$ always has constant coefficient $1,$ so this is not directly applicable.

Surely, technology has advanced since those days, and even the Galois groups can be computed (I assume the Galois group is the full symmetric group for most choices of $n$ and $d.$)

What makes the whole thing strange is that the original question (with $n=2013$ and $d=2014$) was supposedly an entrance exam question at Peking university. So this is either child abuse, or there is some simple trick.

-
I don't think the bit about the Galois group is right. After adjoining the square root of $d$ (degree 2 extension), we are left with a degree $n$ equation. Thus, unless $d$ is a square, the Galois group has a subgroup of index 2 that is a subgroup of $S_n.$ Of course, if $d$ is a square, we get a subgroup of $S_n$ "on the nose". – Victor Protsak Jan 8 '14 at 7:04
@Igor: just to clarify, this problem was solved in an Annals paper from 1933. The standards of the Annals have changed dramatically in the past 80 years. – Michael Zieve Jan 9 '14 at 2:31
@Igor: first, that Annals paper doesn't answer the entrance exam question, since it only addresses the case $d=\pm 1$. Second, what is done in that Annals paper is certainly simple enough to be an exam problem. – Michael Zieve Jan 9 '14 at 3:56
I posted an answer to the entrance exam question (the case $n=2013$ and $d=2014$) over at math.SE math.stackexchange.com/a/630759/448. My argument applies for many other pairs of values $(n,d)$; I just need $n$ to be sufficiently large compared to the number of divisors of $d$. I don't know what happens when this condition fails. – Michael Zieve Jan 9 '14 at 5:08
Hello,This problem is from Peking university graduate record examination questions(2014,0401) – math110 Jan 9 '14 at 8:45

I prove here that $\prod_{i=1}^n (x-a_i)^2 + d$ is irreducible over $\mathbf{Q}$ whenever the $a_i$ are distinct integers, $n\ge 6$, and $d$ is squarefree, $d>1$, and $d\not\equiv 3\pmod{4}$.

The hypotheses on $d$ ensure that the ring of algebraic integers in $\mathbf{Q}(\sqrt{-d})$ is $\mathbf{Z}[\sqrt{-d}]$, and that the only units in this ring are $\pm 1$. Write $f(x):=\prod_{i=1}^n (x-a_i)$, and let $\alpha$ be a root of $f(x)^2+d$, so that $\beta:=f(\alpha)$ satisfies $\beta^2=-d$. Suppose that $f(x)^2+d$ is reducible over $\mathbf{Q}$, so that $[\mathbf{Q}(\alpha):\mathbf{Q}]<\deg(f(x)^2+d)=2n$. Since $$[\mathbf{Q}(\alpha):\mathbf{Q}]=[\mathbf{Q}(\alpha):\mathbf{Q}(\beta)]\cdot [\mathbf{Q}(\beta):\mathbf{Q}] = 2[\mathbf{Q}(\alpha):\mathbf{Q}(\beta)],$$ it follows that $[\mathbf{Q}(\alpha):\mathbf{Q}(\beta)]<n$, so that $f(x)-\beta$ is reducible over $\mathbf{Q}(\sqrt{-d})$. Write $f(x)-\beta=g(x)h(x)$ with $g,h$ nonconstant polynomials in $\mathbf{Q}(\sqrt{-d})[x]$. Since $f(x)-\beta$ is monic, we may assume that both $g$ and $h$ are monic. Since $f(x)-\beta$ is a monic polynomial whose coefficients are algebraic integers, all of its roots are algebraic integers. Therefore both $g$ and $h$ are monic polynomials all of whose roots are algebraic integers, so the coefficients of $g$ and $h$ are algebraic integers; since these coefficients are also in $\mathbf{Q}(\sqrt{-d})$, it follows that $g$ and $h$ are in $\mathbf{Z}[\sqrt{-d}][x]$.

Now substitute $x=a_i$ into the identity $f(x)-\beta=g(x)h(x)$, to get $-\beta=g(a_i)h(a_i)$. Hence $g(a_i)$ is an element of $\mathbf{Z}[\sqrt{-d}]$ which divides $\beta$, so taking norms gives $N(g(a_i))\mid N(\beta)=d$. Since $d$ is squarefree, the only elements of $\mathbf{Z}[\sqrt{-d}]$ whose norm divides $d$ are $\pm 1$ and $\pm\sqrt{-d}$. Thus $g(a_i)\in\{\pm 1,\pm\sqrt{-d}\}$.

First suppose that $g(a_i)$ takes the same value (call it $c$) for every $i$. Then $g(x)-c=f(x)G(x)$ for some $G(x)\in\mathbf{Z}[\sqrt{-d}][x]$, which is impossible since $0<\deg(g)<\deg(f)$.

Hence there exist $i,j$ with $g(a_i)\ne g(a_j)$. Since $n\ge 6$, it follows that there exist $r,s$ for which $g(a_r)\ne g(a_s)$ and $a_r\ge a_s+3$: for, this is clear if $\lvert a_i-a_j\rvert\ge 3$, and if $\lvert a_i-a_j\rvert<3$ then there exists $k$ such that $\lvert a_i-a_k\rvert\ge 3$ and $\lvert a_j-a_k\rvert\ge 3$, and we must have either $g(a_i)\ne g(a_k)$ or $g(a_j)\ne g(a_k)$.

Finally, $a_r-a_s$ divides $g(a_r)-g(a_s)$ in $\mathbf{Z}[\sqrt{-d}]$. Since $a_r-a_s$ is an integer $\ge 3$, and $g(a_r),g(a_s)$ are distinct elements of $\{\pm 1, \pm\sqrt{-d}\}$, this is impossible.

-