6
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ What does "periodic" mean here? If, say, $p(x)=x^2+x$ and $n=7$, then starting at $x=3$ we get the sequence $\{3,5,2,6,0, 0\cdots\}\pmod 7$. So it is periodic (constant even) except for an initial stub. But it is not periodic from the start. Is this what you meant? $\endgroup$
    – lulu
    Dec 29, 2019 at 19:42
  • $\begingroup$ Why, for instance, does the polynomial $q(x)=\frac {x(x+1)}2$ fail? It passes the first test, clearly...does it not pass the second? There are only finitely many residues $\pmod n$, for any $n$, so of course iterations of $q(x)$ must hit the same one twice, after which it starts repeating. How then, does it differ from $p(x)=x(x+1)$? $\endgroup$
    – lulu
    Dec 29, 2019 at 19:45
  • $\begingroup$ I edited the question. $\endgroup$
    – richrow
    Dec 29, 2019 at 19:46
  • $\begingroup$ But, then, where does $\frac {x(x+1)}2$ fail? $\endgroup$
    – lulu
    Dec 29, 2019 at 19:46
  • 2
    $\begingroup$ @lulu In fact you are not far from an actual counterexample. $\endgroup$
    – WhatsUp
    Dec 30, 2019 at 0:40

1 Answer 1

6
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ I am sorry. Actually this problem was given us by teacher two years ago (as a part of training for math olympiads), but we didn't solve the problem and our teacher didn't us the solution. Now, I interested in this problem again and I just wanted to learn solution. Maybe, teacher gave us wrong statement (forget about some condition, etc.). Anyway, thanks! $\endgroup$
    – richrow
    Dec 30, 2019 at 7:15
  • 1
    $\begingroup$ Don't worry. It's still a high quality question. But next time when you're unsure whether the problem is correct, it'd be better to state it in the question. As you know, "prove this statement" and "is this statement true" lead to totally different strategies. $\endgroup$
    – WhatsUp
    Dec 30, 2019 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.