A naive question on values of an integral polynomial

Question

Let $P(t)$ be a polynomial with integral coefficients, in one variable. I want to know what is the g.c.d. of the set $\{P(n)|n \in \mathbb{Z}\}$. Is it the leading coefficient of $P(t)$?

Answer 1

Let $\mathcal{F}$ be the collection of real valued functions over $\mathbb{R}$. For any $f \in \mathcal{F}$, the finite difference of $f$ is a function $Df \in \mathcal{F}$ defined by the relation

$$(Df)(x) = f(x+1) - f(x)$$ In particular, if $P$ is a polynomial of degree $p$ with leading coefficients $a_p$, we have

$$\begin{align} P(x) & = a_p x^p + a_{p-1}x^{p-1} + \cdots + a_0\\ \implies DP(x) & = f(x+1) - f(x) \\ &= a_p ((x+1)^p - a_p x^p) + a_{p-1}((x+1)^{p-1} - x^p) + \cdots\\ & = a_p (px^{p-1} + O(x^{p-2})) + a_{p-1}((p-1)x^{p-2} + O(x^{p-3})) + \cdots \end{align} $$ The finite difference $DP$ will be a polynomial of degree $p-1$ with leading coefficient $p a_p$.
Apply this one more time, we find $$D^2P(x) = DP(x+1) - DP(x) = P(x+2) - 2P(x+1) + P(x)$$ is a polynomial of degree $p-2$ and leading coefficient $p(p-1) a_p$. When one repeat this process $p$ times, we will bring the degree of $D^pP(x)$ down to $0$ and $D^pP(x)$ become a constant with value $p(p-1)(p-2)\cdots(1) a_p = p! a_p$.

$$(D^p P)(x) \stackrel{def}{=} ((\underbrace{D\cdots D}_{p \text{times}}) P)(x) = \sum_{k=0}^p (-1)^{p-k} \binom{p}{k} P(x+k) = p!a_p$$

If integer $d$ divides $P(n)$ for every $n \in \mathbb{Z}$, then $d$ divides $(DP)(n) = P(n+1) - P(n)$ for every $n$. By a similar argument, $d$ divides $(D^2 P)(n) = (DP)(n+1) - (DP)(n)$ for every $n$. Repeat this procedure $p$ times, we find $d$ divides the constant $(D^p P)(n) = p!a_p$.

From these, we can deduce $\gcd\{ P(n) : n \in \mathbb{Z} \}$ divides $p!a_p$.

This bound is sort of optimal. Consider following family of polynomials:

$$S_p(x) = \begin{cases} \frac{1}{p!}x(x-1)(x-2)\cdots(x-p+1), & p > 0\\ 1, & p = 0 \end{cases}$$

It is easy to check they satisfy a recurrence relation

$$S_p(x+1) - S_p(x) = S_{p-1}(x),\quad\text{ for } p \ge 0$$

Notice $S_0(n) = 1$ for every integer $n$ and $S_p(0) = 0$ is an integer.
If $S_{p-1}(n)$ is an integer for every $n$, then

$$S_p(n) = S_p(0) + \sum_{k=1}^{n-1} S_{p-1}(k)$$ is also any integer for every $n$. By principle of induction, we find for any $p \ge 0$, $S_p(x)$ is a polynomial which take integer values at integer $x$.

Multiply $S_p(x)$ by $p!$, we obtain a polynomial $p!S_p(x)$ with integer coefficients, leading coefficient one and $p!$ divides $p!S_p(n)$ for every $n$. As a result, $p!$ divides $\gcd\{ p!S_p(n) : n \in \mathbb{Z} \}$.

$p!S_p(n)$ will be an example for $P$ where $\gcd\{ P(n) : n \in \mathbb{Z} \}$ equals to $p! a_p$.