Local Mathematical Competitions

For any function $f$, denote its $n$-th iterate $f^n$. Take $d=\mathrm{deg}f\ge 2$. One can write $f(x)=\frac{1}{N}(a{x}^d+g(x))$ for some $N\in {\mathbb{Z}}_{+}^{\ast }$, $a\in {\mathbb{Z}}^{\ast }$, and some $g\in \mathbb{Z}[x]$, with $\mathrm{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\},\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)=er$, $a=eb$, 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+erz,e^d{r}^d)=Ne\cdot \gcd (b\mu (x{)}^d+rz,e^{d-1}{r}^d)=Ne\cdot \gcd (b\mu (x{)}^d+rz,e^{d-1})$, since from previous relations $\gcd (b\mu (x),r)=1$. Lastly $\delta \le Ne\cdot \gcd (b\mu (x{)}^d+rz,e^{d-1})\le Ne{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$