3

Let $P(x) \in \mathbb{Z}[x]$ for which $S = \{n\in\mathbb{Z} : P(P(P(n)))=n\}$ is nonempty. Prove that $P(n) = n$ for all $n\in S$.

My attempt :

Let $n=k$ for which $P(P(P(k)))=k$, so $P(P(P(k)))-k=0$

Let $Q(x)$ be polynomial such that $Q(Q(Q(x)))=P(P(P(x)))-x$

so $Q(Q(Q(x)))=0$ for $x=k$

so $Q(Q(k))$ is one root of the polynomial $Q(x)$.

Michael L.
  • 5,521
user403160
  • 3,286
  • 2
    When you say that $P(P(P(n)))=n$ for some integers $n$, do you have any restrictions on that? Otherwise $f(x)=x^m$ for any positive integer $m$ suffices as any number of iterates of $f$ at $x=0$ and $x=1$ give $0$ and $1$, respectively. – Clayton Aug 03 '17 at 13:13
  • I think the question is to prove that $P(P(P(n))) = n$ implies $P(n) = n$ for $P(x)\in \mathbb{Z}[x]$. Your example would give $P(0) = 0$ and $P(1) = 1$, so it's not a counterexample. – Michael L. Aug 03 '17 at 13:25
  • @Clayton Hopefully the OP can provide some clarification. – Michael L. Aug 03 '17 at 13:30
  • @MichaelLee: I misread your comment before; my apologies. I'm not sure which question is intended here (I originally read it as proving the polynomial was the identity $P(x)=x$, but perhaps the OP means to ask something more like $P(P(P(n)))=n\Longrightarrow P(n)=n$ for a fixed integer $n$ ). – Clayton Aug 03 '17 at 13:35
  • @Clayton, $P(P(P(n)))=n\Longrightarrow P(n)=n$ for a some integers $n$ is correct. – user403160 Aug 03 '17 at 13:57
  • @MichaelLee, your understanding in 2nd post is correct. – user403160 Aug 03 '17 at 14:02
  • How would you know such a $Q$ exists? – Thomas Andrews Aug 03 '17 at 14:08
  • You can reduce to the case where $n=0$ since otherwise, you can define $P_0(x)=P(x+n)-n$. Then $P_0(P_0(P_0(0)))=P(P(P(n)))-n=0$. – Thomas Andrews Aug 03 '17 at 14:12
  • @Thomas Andrews, I'm not sure. It may be wrong. – user403160 Aug 03 '17 at 14:13

1 Answers1

5

You can reduce the problem to the case of $n=0$. If $P(P(P(n)))=n$, define $P_0(x)=P(x+n)-n$. Then $P_0(P_0(P_0(0)))=P(P(P(n)))-n$, so, if the theorem is true for $0$, then $P_0(0)=P(n)-n=0$.

Assume $P(0)\neq 0$ and $P(P(P(0)))=0$.

We also know that $P(P(0))\neq 0$ or else $P(P(P(0)))=P(0)\neq 0$. We also have that $P(0)\neq P(P(0))$, because otherwise, $0=P(P(P(0)))=P(P(0))\neq 0$.

We will now use the following standard result:

For $q(x)\in\mathbb Z[x]$ you have that $q(m)\equiv q(n)\pmod{m-n}$ for all integers $m,n$.

We will prove that $P(0)\mid P(P(0))$ and $P(P(0))\mid P(0)$. From this we deduce that $P(P(0))=-P(0)$ and hence that $2P(0)\mid P(P(0))$, which is only possible if $P(0)=P(P(0))=0$.

Proof:

(1) With $q(x)=P(P(x))$ and $m=P(0), n=0$ you get that $$P(0)\mid P(P(0)).$$

(2) With $q=P(x),m=P(P(0)), n=0$ you $$P(P(0))\mid P(0).$$

(3) So $P(0)=\pm P(P(0))$. If $P(P(0))=P(0)$ then $0=P(P(P(0))=P(0)$. So assume $P(0)=-P(P(0))$.

(4) Now, letting $q(x)=P(x), m=P(0), n=P(P(0))=-P(0)$, you get $P(P(0))\equiv 0\pmod{2P(0)}.$

So $2P(0)\mid P(P(0))$ which contradicts $P(0)=\pm P(P(0))$ unless $P(0)= 0$.

This proof shows that this works for any function $f:\mathbb Z\to\mathbb Z$ such that $f(n)\equiv f(m)\pmod{n-m}$ for all integers $n,m$. There are uncountably many non-polynomial $f$, but there are also some polynomials with non-integer coefficients, like $f(x)=\frac{x^4+x^2}{2}$.

So the short proof is (writing $P^2(x)=P(P(x)), P^3(x)=P(P(P(x)))$):

Assume $P^3(n)= n.$ Then:

$$\begin{align}P^2(n)&\equiv P(n)\equiv n\pmod{P(n)-n}\\ n= P^3(n)&\equiv P(n)\pmod{P^2(n)-n}\\ n=P^3(n)&\equiv P^2(n)\pmod{P^2(n)-P(n)} \end{align}$$

The first two lines mean that $P^2(n)-n=\pm \left(P(n)-n\right).$

If $P^2(n)-n=P(n)-n$, then $P^2(n)=P(n)$ and hence $n=P(P^2(n))=P(P(n))=P(n).$

If $P^2(n)-n=n-P(n)$ then $P^2(n)-P(n)=2(n-P(n))$. So $$n=P(P^2(n))\equiv P(P(n))\pmod{2(n-P(n))}$$

So we get that $2(n-P(n))\mid (n-P^2(n))$. But $n-P^2(n)=\pm (n-P(n))$, contradiction, unless $n-P^2(n)=0$ and hence $P^2(n)=n$ and then $P(n)=P(P^2(n))=n$.

Thomas Andrews
  • 177,126