China-TST-2023B

Proof. Lemma Let integers $a$ and real number $z$ satisfy $|a|\ge 2$. For any non-negative integer $n$, if $$||a^{n}z||<\frac{1}{|a|+1},$$ then $z$ is an integer. Here, $||x||$ is defined as the distance between the real number $x$ and the nearest integer, that is, $||x||=\min (\{x\},1-\{x\})$.

Proof of the lemma: Without loss of generality, assume $a\ge 2$ (otherwise, replace $a$ with $-a$). Suppose the conclusion is false. Without loss of generality, assume $0<z\le \frac{1}{2}$ (otherwise, replace $z$ with $m\mp z$, where $m$ is some suitable integer). Since $z\in (0,\frac{1}{a^{-1}(a+1)})$, we can assume that $$\frac{1}{a^k(a+1)}\le z<\frac{1}{a^{k-1}(a+1)}(k\in {\mathbb{Z}}_{\ge 0}),$$ which implies $\frac{1}{a+1}\le a^{k}z<1-\frac{1}{a+1}$. Consequently, $||a^{k}z||\ge \frac{1}{a+1}$, leading to a contradiction. Thus, the lemma is proven.

Back to the original question. Assume, for the sake of contradiction, that $f(x)=a_d{x}^d+a_{d-1}{x}^{d-1}+\cdots +a_{1}x+a_0$ is not a polynomial with rational coefficients. Let $t$ be the largest index such that $a_t\notin \mathbb{Q}$. Define $$\left\{\frac{f(n)a^n}{b}\right\}=\frac{r_n+{\epsilon }_n}{b},{\epsilon }_n\in [0,1).$$ Let $g(x)={\Delta }^{t}f(x)={\sum }_{i=0}^t(-1{)}^i(\genfrac{}{}{0ex}{}{t}{i})f(x+t-i)$, where $\Delta$ denotes the finite difference operator. It is easy to see that except for the constant term, all coefficients of $g(x)$ are rational numbers. Let $g(x)=c_{d-t}{x}^{d-t}+\cdots +c_{1}x+c_0$, and let $K$ be the least common multiple of the denominators of $c_1,c_2,\cdots ,c_{d-t}$. Now, $$\begin{gathered} \left\{\frac{g(n)a^{n+t}}{b}\right\}=\left\{\sum _{i=0}^t\frac{(-1{)}^i(\genfrac{}{}{0ex}{}{t}{i})f(n+t-i)a^{n+t-i}\cdot a^i}{b}\right\} \\ =\left\{\sum _{i=0}^t\frac{(-1{)}^i(\genfrac{}{}{0ex}{}{t}{i})a^i(r_{n+t-i}+{\epsilon }_{n+t-i})}{b}\right\} \\ =\left\{\sum _{i=0}^t{r}_{n+t-i}\frac{(-1{)}^i(\genfrac{}{}{0ex}{}{t}{i})a^i}{b}+\sum _{i=0}^t{\epsilon }_{n+t-i}\frac{(-1{)}^i(\genfrac{}{}{0ex}{}{t}{i})}{b}\right\}. \end{gathered}$$

Let ${\delta }_n={\sum }_{i=0}^t{\epsilon }_{n+t-i}\cdot \frac{(-1{)}^i(\genfrac{}{}{0ex}{}{t}{i})a^i}{b}$. Note that $$\sum _{i=0}^t\left|\frac{(-1{)}^i(\genfrac{}{}{0ex}{}{t}{i})a^i}{b}\right|=\sum _{i=0}^t\frac{\left(\genfrac{}{}{0ex}{}{t}{i}\right)|a{|}^i}{b}=\frac{(|a|+1{)}^t}{b}\le \frac{(|a|+1{)}^d}{b}\le \frac{1}{|a|+1},$$ which implies that for any positive integers $n$ and $n^{\prime }$, $$\left|{\delta }_n-{\delta }_{n^{\prime }}\right|\le \sum _{i=0}^t\left|{\epsilon }_{n+t-i}-{\epsilon }_{n^{\prime }+t-i}\right|\cdot \frac{\left(\genfrac{}{}{0ex}{}{t}{i}\right)|a{|}^i}{b}<\sum _{i=0}^t\frac{\left(\genfrac{}{}{0ex}{}{t}{i}\right)|a{|}^i}{b}\le \frac{1}{|a|+1}.$$ We choose positive integers $M$ and $n$ such that $M$ is a multiple of the smallest positive period of $\{r_n\}$ and $bK|M$, and when $n\ge n_0$, we have $bK|a^{n+M+t}-a^{n+t}$. Then, for $n\ge n_0$, $$\Vert \frac{g(n+M)a^{n+M+t}}{b}-\frac{g(n)a^{n+t}}{b}\Vert =\Vert {\delta }_{n+M}-{\delta }_n\Vert <\frac{1}{|a|+1},$$ where the first equality holds because $r_{n+M+t-i}=r_{n+t-i}$ for $i=0,1,\dots ,t$. On the other hand, $$\begin{array}{rl}& \left|\frac{g(n+M)a^{n+M+t}}{b}-\frac{g(n)a^{n+t}}{b}\right|\\ & =\left|\frac{c_0}{b}(a^{n+M+t}-a^{n+t})+\sum _{i=1}^{d-t}\frac{c_i}{b}((n+M{)}^i{a}^{n+M+t}-n^i{a}^{n+t})\right|\\ & =\left|\frac{c_0(a^M-1)a^{n_0+t}}{b}\cdot a^{n-n_0}\right|.\end{array}$$ According to the lemma, we have $\frac{c_0(a^M-1)a^{n_0+t}}{b}\in \mathbb{Z}$, but this contradicts the irrationality of $c_0$! Hence, the proof is complete. $\square$