Let $ p(x)$ be a cubic polynomial with rational coefficients. $ q_1$, $ q_2$, $ q_3$, ... is a sequence of rationals such that $ q_n = p(q_{n + 1})$ for all positive $ n$. Show that for some $ k$, we have $ q_{n + k} = q_n$ for all positive $ n$.
Problem
Source: IMO ShortList 1990, Problem 26 (USA 2)
Tags: algebra, polynomial, number theory, Cubic, Iteration, IMO Shortlist
10.04.2005 11:02
Suppose that $ p(x) = 1/e(ax^{3} + bx^{2} + cx + d) $ where $ a,b,c,d,e \in \mathbb{Z} $, $ e > 0 $. Then suppose that $ m,M \in \mathbb{Z} $, $ n,N \in \mathbb{N} $, the fractions $ \frac{m}{n} $ , $ \frac{M}{N} $ are reduced and $ p(\frac{m}{n}) = \frac{M}{N} $. But $ p(\frac{m}{n}) = \frac{am^{3} + bm^{2}n + cmn^{2} + dn^{3}}{en^{3}} $. Suppose $ k = gcd(am^{3} + bm^{2}n + cmn^{2} + dn^{3},en^{3}) $. Denote also $ x = am^{3} $, $ y = bm^{2}n + cmn^{2} + dn^{3} $. Then $ k | x+y $ and $ k | en^{3} $. Therefore $ k | e(x^{3} + y^{3}) $ ( because $ x+y | x^{3} + y^{3} ) $ , but $ k | en^{3} | ey^{3} $, so $ k | ex^{3} = ea^{3}m^{9} $ , and as before $ k | en^{3} $. So, at the end, $ k | ea^{3}m^{9} , ea^{3}n^{3} $. But $ gcd(m^{9},n^{3}) = 1 $, therefore $ k | ea^{3} $. So we get that $ gcd(am^{3} + bm^{2}n + cmn^{2} + dn^{3},en^{3}) | ea^{3} $, therefore $ Mea^{3} \geqslant en^{3} $ , so $ n \leqslant a \sqrt[3]{M} $ . Now suppose we have a sequence of rational numbers $ q_{1},q_{2}, \ldots $ such that $ q_{n} = p(q_{n+1}) $. Write $ q_{n} = \frac{a_{n}}{b_{n}} $ as a reduced fraction where $ a_{n},b_{n} \in \mathbb{Z} $, $ b_{n} > 0 $. Then, as we saw before, $ b_{n+1} \leqslant a \sqrt[3]{b_{n}} $. Therefore the sequence $ \{ b_{n} \} $ is bounded. Also note that the sequence $ \{ q_{n} \} $ is bounded. Indeed, there exists some $ C > 0 $ such that for every $ x \in \mathbb{R} $, $ |x| > C $ we have $ |p(x)| > 2|x| $. Therefore it is impossible that $ |q_{n}| > C $ for infinitely many $ n $'s, because $ q_{1} $ is bounded. So $ \{ b_{n} \} $ is bounded and $ \{ q_{n} \} $ is bounded, therefore $ \{ a_{n} \} $ is bounded. Therefore the sequence $ q_{n} $ takes only a finite number of values. Therefore there exists a rational number $ q $, which appears in the sequence $ \{ q_{n} \} $ infinitely many times. Because the number $ q $ appears at least two times, there is $ k \in \mathbb{N} $, such that $ \underbrace{p \circ p \circ \ldots \circ p}_{k times} (q) = q $. Therefore $ k $ is a period for $ q_{n} $, because there exists $ N $ as large as we want, such that $ q_{N} = q $, so because of $ q_{n-1} = p(q_{n}) $, we get that $ q_{n-k} = q_{n} $ for every $ k+1 \leqslant n \leqslant N $. So because we can take $ N $ to be as large as we want, we get that $ q_{n-k} = q_{n} $ for every $ k+1 \leqslant n $. Therefore $ q_{n} $ is periodic.