Local Mathematical Competitions

For any function $f$, denote its $n$-th iterate $f^n$. Take $d = \deg f \ge 2$. One can write $f(x) = \frac{1}{N}(a x^d + g(x))$ for some $N \in \mathbb{Z}_+^*$, $a \in \mathbb{Z}^*$, and some $g \in \mathbb{Z}[x]$, with $\deg g \le d-1$, $g(x) = \sum_{i=0}^{d-1} a_i x^i$, $a_i \in \mathbb{Z}$, for all $0 \le i \le d-1$.
Finally, $f^\omega(\mathbb{Q}) \subset f^n(\mathbb{Q}) \subset f^{n-1}(\mathbb{Q}) \subseteq \mathbb{Q}$, for $n \ge 1$.
For any $x \in \mathbb{Q}$, one can uniquely write $x = \frac{\mu(x)}{\nu(x)}$, with $\mu(x), \nu(x) \in \mathbb{Z}$, and $\nu(x) > 0$, $\gcd(\mu(x), \nu(x)) = 1$. Take now $M = \frac{\sum_{i=0}^{d-1} |a_i| + 2N}{|a|} + 1$, and
$$\mathcal{M} := \{x \in \mathbb{Q} ; |x| > M\}, \quad \mathcal{F} := \{x \in \mathbb{Q} ; \nu(x) > a^2\}.$$
Now, $(\mathbb{Q} \setminus \mathcal{F}) \cap (\mathbb{Q} \setminus \mathcal{M})$ is obviously finite; take $\mathfrak{m}$ to be its cardinality.
For $x \in \mathcal{M}$ one has $|f(x)| \ge |x| + 1 > M$ (see LEMMA 1), hence $f(x) \in \mathcal{M}$. Then $|f^n(x)| \ge |x| + n$. For $x \in \mathcal{F}$ one has $\nu(f(x)) \ge \nu(x) + 1 > a^2$ (see LEMMA 2), hence $f(x) \in \mathcal{F}$. Then $\nu(f^n(x)) \ge \nu(x) + n$.
Take $x \in f^\omega(\mathbb{Q})$, and take $n$ large enough. Then we will have $x \in f^n(\mathbb{Q})$, hence there will exist $x_n \in \mathbb{Q}$ such that $f^n(x_n) = x$. If $f^k(x_n) \in \mathcal{M}$ for $n-k > |x|$, then $|x| = |f^n(x_n)| = |f^{n-k}(f^k(x_n))| \ge |f^k(x_n)| + (n-k) > |x|$, absurd. If $f^k(x_n) \in \mathcal{F}$ for $n-k > \nu(x)$, then $\nu(x) = \nu(f^n(x_n)) = \nu(f^{n-k}(f^k(x_n))) \ge \nu(f^k(x_n)) + (n-k) > \nu(x)$, absurd.
Take $n$ large enough so that $n > \mathfrak{m} + \max\{|x|, \nu(x)\}$.
One then has $f^k(x_n) \in (\mathbb{Q} \setminus \mathcal{F}) \cap (\mathbb{Q} \setminus \mathcal{M})$, for $0 \le k \le \mathfrak{m}$, therefore there will exist $0 \le i < j \le \mathfrak{m}$ such that $f^i(x_n) = f^j(x_n)$, therefore $f^n(x_n) = f^k(x_n)$ for some $i \le k \le j$, hence $x = f^n(x_n) = f^k(x_n) \in (\mathbb{Q} \setminus \mathcal{F}) \cap (\mathbb{Q} \setminus \mathcal{M})$.
This implies $f^\omega(\mathbb{Q}) \subseteq (\mathbb{Q} \setminus \mathcal{F}) \cap (\mathbb{Q} \setminus \mathcal{M})$, thus a finite set.

LEMMA 1. For $x \in \mathcal{M}$ one has $|f(x)| \ge |x| + 1 > M$.
Proof. Clearly then $|x| > M > 1$. Now $\frac{|a||x|^d}{N} > \frac{\sum_{i=0}^{d-1} |a_i||x|^{d-1}}{N} + |x|^d + |x|^d > \frac{\sum_{i=0}^{d-1} |a_i||x|^i}{N} + |x| + 1 \ge \frac{|g(x)|}{N} + |x| + 1$. It follows that $|f(x)| = \left| \frac{a x^d + g(x)}{N} \right| \ge \left( \frac{|a||x|^d}{N} - \frac{|g(x)|}{N} \right) > |x| + 1 > M$. $\square$

LEMMA 2. For $x \in \mathcal{F}$ one has $\nu(f(x)) \ge \nu(x) + 1 > a^2$.
Proof. For $x \in \mathcal{F}$ one can write $f(x) = \frac{1}{N \nu(x)^d}(a \mu(x)^d + \nu(x) z) = \frac{\mu(f(x))}{\nu(f(x))}$, with $z = \nu(x)^{d-1} g(x) \in \mathbb{Z}$. Now, for $e = \gcd(\nu(x), a)$, one has $\nu(x) = e r$, $a = e b$, with $\gcd(r, b) = 1$.
Then it follows that $\delta = \gcd(a \mu(x)^d + \nu(x) z, N \nu(x)^d) \le N \cdot \gcd(e \mu(x)^d + e r z, e^d r^d) = N e \cdot \gcd(b \mu(x)^d + r z, e^{d-1} r^d) = N e \cdot \gcd(b \mu(x)^d + r z, e^{d-1})$, since from previous relations $\gcd(b \mu(x), r) = 1$. Lastly $\delta \le N e \cdot \gcd(b \mu(x)^d + r z, e^{d-1}) \le N e e^{d-1} = N e^d \le N |a|^d$.
Therefore $\nu(f(x)) = \frac{N \nu(x)^d}{\delta} \ge \frac{N \nu(x)^d}{N |a|^d} > \nu(x)$, since $\nu(x) > a^2 \ge |a|^{\frac{d}{d-1}}$. It follows that $\nu(f(x)) \ge \nu(x) + 1 > a^2$. $\square$