Сharacteristic property of polynomials with integer coefficients

Question

Here is the problem which was proposed on some contest.

Problem. Polymomial $P(x)$ is satisfying the following conditions

1. If $x\in\mathbb{Z}$ then $P(x)\in \mathbb{Z}$;

2. For every positive integer $n$ and for every integer $x$ the sequence $x, P(x), P(P(x)), \dots$ is periodic modulo $n$.

Prove that $P(x)\in\mathbb{Z}[x]$ i. e. all coefficients of $P(x)$ are integers.

Comment. In this problem we call the sequence $\{a_n\}_{n=1}^{\infty}$ periodic if there are positive integers $n_0$ and $t$ such that for all $n\ge n_0$ the equality $a_{n}=a_{n+t}$ holds.

It's well-known that all polynomials which satisfy first condition are linear combinations with integer coefficients of polynimials $p_k(x)$, where $$ p_k(x):=\binom{x}{k}=\frac{x(x-1)\ldots(x-k+1)}{k!}. $$ Hence, there are integers $c_0,c_1,\ldots, c_n$ such that $$ P(x)=\sum_{k=0}^{n}c_k\cdot p_k(x). $$ Then, we need to prove that $k!\mid c_k$ for $k\ge 0$ (it's equivalent to $P(x)\in\mathbb{Z}[x]$).

However, it's unclear how we should use the second condition. It can be shown that polynomial $c\cdot p_r(x)$ where $r$ is a prime number doesn't satisfy the second condition if $r\nmid c$ (consider modulo $n=r$ in the second condition; it requires some work). It's hard even in this case to prove that $r!\mid c$.

Moreover, it's clear that polynomials with integer coefficients satisfy both conditions. That's why this actually is a characteristic property of such polynomials.

---

Let me explain why the polynomial $P(x)=\frac{x(x-1)}{2}$ doesn't satisfy the conditions of the problem.

Proof. Suppose the contrary. Define the sequence $\{x_k\}_{k=1}^{\infty}$ as follows: $$ x_0=4, \\ x_{k+1}=P(x_k). $$ It's clear that $\{x_n\}_{k=1}^{\infty}$ is an increasing sequence of positive integers. From the second condtion for $n=2$ we obtain that there are positive integers $k_0$ and $t$ such that $x_{k+t}\equiv x_k\pmod 2$ for all $k\ge k_0$. Hence, for all $k\ge k_0$ we have $x_{k+t}-x_k\equiv 0\pmod 2$. Note that $x_{k_0+t}-x_{k_0}>0$, so there is an $s$ such that $2^s\mid x_{k_0+t}-x_{k_0}$, but $2^{s+1}\nmid x_{k_0+t}-x_{k_0}$.

Now, define the new sequence $\{a_k\}_{k=k_0}^{\infty}$ as $a_k:=x_{k+t}-x_k$. Notice that $a_k\equiv 0\pmod 2$ for all $k$ and $$ a_{k+1}=P(x_{k+t})-P(x_k)=\frac{x_{k+t}-x_k}{2}\cdot(x_{k+t}+x_k+1)= \frac{a_k}{2}\cdot(x_{k+t}+x_k+1). $$ Due to our assumption $x_{k+t}+x_k+1$ is an odd number. Thus, the sequence of 2-adic valuations of $a_k$ is a strcictly decreasing sequence, which is impossible beacuse all $a_k$ are integers (or, equivalently, $a_{k_0+s}$ is odd which contradicts $a_{k}\equiv 0\pmod 2$). Therefore, $P(x)$ doesn't satisfy the conditions of the problem, as desired.

---

How we can approach this problem?

---

Update. Actually, as WhatsUp noticed the statement of the problem is wrong, namely, the polynomial $P(x)=\frac{(x^2-x)^2}{2}$ is a counterexample. For more details see WhatsUp's answer below.

Answer 1

I'm not very happy with this question.

The way it is posted makes it look like a problem with a solution ("the problem which was proposed on some contest"). So I spent much time trying to prove it.

And finally it all comes to a counterexample: $P(x) = \frac{(x^2 - x)^2}{2}$.

• For any $x \in \Bbb Z$, we have $P(x) \in 2\Bbb Z$.
• For any $x,y \in 2\Bbb Z$, we have $x - y\mid P(x) - P(y)$.

It follows that, for any $n$ and any $x \in \Bbb Z$, the sequence $(x_k)_k$ defined by $x_0 = x$ and $x_{k + 1} = P(x_k)$ is eventually periodic mod $n$.

This is because, starting from $k = 1$, the sequence stays in $2\Bbb Z$. Since there are only finitely many residues mod $n$, the sequence eventually has a repeated term mod $n$, say $x_s \equiv x_t\mod n$, with $1 \leq s < t$. But then $n \mid x_s - x_t \mid P(x_s) - P(x_t) = x_{s + 1} - x_{t + 1}$, and by induction we see that the sequence $(x_k)_k$ is periodic mod $n$, starting from $k = s$.