Polynomial bijections from $\mathbb{Q}$ to $\mathbb{Q}$ Prove or Improve: Polynomials $f\in \mathbb{Q}[x]$ which induce a bijection $\mathbb{Q}\to\mathbb{Q}$ are linear.
The question of existence of a polynomial bijection $\mathbb{Q}\times\mathbb{Q}\to \mathbb{Q}$ is open, as discussed in this MO thread, this post by Terry Tao, and many more places. However, I cannot find much about the simpler question of polynomial bijections $\mathbb{Q}\to \mathbb{Q}$ (probably because this is easier and less interesting). Here are a few somewhat immediate observations:

*

*One quickly notes that any such bijection can always be put in the form
$$a_nx^n+\dots+a_1x$$ for $a_1,\dots,a_n\in \mathbb{Z}$ by composing with an appropriate linear polynomial. From there, I have tried to use the rational root theorem to obtain some sort of result, but to no avail.


*Note that, unlike the $\mathbb{Q}\times\mathbb{Q}\to \mathbb{Q}$ case, it is quite easy to obtain an injection. For example, $f(x)=x^3+x$ is clearly injective, but unfortunately fails to be surjective ($f(x)=1$ yields $x^3+x-1=0$, which has only irrational roots by the rational root theorem, hence $1$ has no rational inverse).
Is this a known result, and if so, how would one prove it? Or is there some higher order bijective polynomial on $\mathbb{Q}$?
 A: Assume $f(x)=a_nx^n+\ldots +a_1x+a_0\in\Bbb Q[x]$ with $a_n\ne0$ induces a surjection $\Bbb Q\to \Bbb Q$.
Let $p$ be a large prime such that $|a_i|_p=1$ for all non-zero $a_i$. Then $$|f(x)|_p\le\max\{\,|a_kx^k|_p\mid k\ge0\,\}=\max\{\,|x|^k_p\mid a_k\ne 0\,\}$$ with equality if these are distinct, i.e., if $|x|_p\ne 1$. In particular, either $|x|_p\le 1$ and so $|f(x)|_p\le 1$, or $|x|_p\ge p$ and so $|f(x)|_p\ge p^n$. For surjectivity, we need some $x\in\Bbb Q$ with $|f(x)|_p=p$. Therefore we need $n\le 1$.
A: Here’s yet another effort:
We may assume that our polynomial $f(x)\in\Bbb Q[x]$ is monic, just by dividing the whole polynomial by the coefficient of the highest-degree term $x^d$.
Now let $p$ be a prime not dividing any of the numerators of the coefficients of $f$. I claim that there is no $z\in\Bbb Q$ with $f(z)=1/p$. It’s the proof of Eisenstein upside-down:
Let $z=m/n$, with coprime integers $m$ and $n$. If $p\nmid n$, then $p\nmid f(z)$, while if $p\mid n$, then $p^d$ is exactly the power of $p$ dividing the numerator of $f(z)$. (In $p$-adic language, if $v_p(z)\ge0$, then $v_p(f(z))\ge0$, while if $v_p(z)<0$, then $v_p(f(z))=dv_p(z)$.)
In any case, the numerator of $f(z)$ can not be only singly divisible by $q$.
A: You could use the Hilbert irreducibility theorem: let $p(X) \in \mathbb Q[X]$ be such a polynomial, and consider the polynomial
$$f(Q,X) = p(X) + Q\in\mathbb Q(Q)[X].$$
This is irreducible over $\mathbb Q(Q)$: by Gauss' lemma it is irreducible as soon as it is irreducible in $\mathbb Q[Q,X] = \mathbb Q[X][Q]$, and as a polynomial in $Q$ it is monic and linear.
As the conditions for the Hilbert irreducibility theorem are met, it can be concluded that there exists a $q\in\mathbb Q$ such that $f(q,X)$ is irreducible. In particular $p(X) + q$ does not have a rational root, so $-q$ is not in the image.
A: First, we may assume that $P$ has integer coefficients, as we may just scale it up by any factor.
Claim. There exist infinitely many primes $p$ for which there exist $a$ and $b$ so that $p|P(a)-P(b)$, but $p\nmid a-b$.
First, we see that this finishes. Take some such prime $p$ greater than the leading coefficient of $P$, and consider the set of integers reached by taking $P(m)\bmod p$ for any integer $m$. This set cannot be all of $\mathbb{Z}/p\mathbb Z$, since $P(x)\equiv P(x+p)\bmod p$ for any $x$ and $P(a)\equiv P(b)$ as well. So, there is some integer $i$ so that $P(x)\not\equiv i\bmod p$ for any $x\in\mathbb Z$.
Now, assume that $P(q)=i$ for some rational $q$. If $q$ has no factors of $p$ in its denominator, then $q$ is equivalent to $m\bmod p$ for some integer $m$, and
$$P(q)\equiv P(m)\not\equiv i\bmod p.$$
However, if $q$ has some factors of $p$ in its denominator, then $P(q)$ must have $p^{\operatorname{deg}P}$ in its denominator, since $p$ can't divide $P$'s leading coefficient.
Now all that's left is to prove the claim.
Proof. Assume for the sake of contradiction that there are only finitely many such primes, and that they are all less than some $N$. Pick some integer $c$. A prime $p>N$ may only divide $P(x)-P(c)$ if $p|x-c$. As a result, the only primes that can divide $P(p+c)-P(c)$ are primes less than $N$ and the prime $p$.
We claim that there exist some $a,b$ so that $P(p+c)-P(c)=ap^b$ for infinitely many primes $p$. Let $t$ be the product of all primes less than $N$, and let $u$ be some number relatively prime to $t$ so that $P(c+u)\neq P(c)$. Now, let $T$ be some large power of $t$ so that $$\nu_q(P(c+u)-P(c))<\nu_q(T).$$ For any integer $k$,
$$P(c+Tk+u)-P(c)\equiv P(c+u)-P(c)\bmod T,$$
so
$$\nu_q\left(P(c+Tk+u)-P(c)\right)=\nu_q\left(P(c+u)-P(c)\right);$$
as a result, if $Tk+u$ is a prime $p$,
$$P(p+c)-P(c) \big| \left(P(c+u)-P(c)\right)p^B$$
for some integer $B$. Write $P(p+c)-P(c)=ap^b$ with $p\nmid a$; we will show that both $a$ and $b$ are bounded. For large $p$, $P(p+c)-P(c)$ is bounded by $p^{\deg P+1}$, so $b$ must be in $\{0,1,\dots,\deg P\}$. Also, $a$ must be one of the finitely many divisors of $P(p+c)-P(c)$. So, by the infinite pigeonhole principle, there exists some pair $(a,b)$ so that there are infinitely many primes $p$ for which $P(p+c)-P(c)=ap^b$, and so $P(x+c)-P(c)=ap^b$.
Now, we have
$$P(x)-P(0)=a_0x^{b_0}\text{ and }P(x+1)-P(1)=a_1x^{b_1}.$$
It is clear that $a_0=a_1$ and $b_0=b_1$ by comparing leading terms, so $P(x+1)-P(1)=P(x)-P(0)$, which means $P$ is linear, a contradiction.
Firstly, we may replace $P(x)$ with $P(x)-P(0)$ so that $P(0)=0$. Thus, we get that a prime $p$ can divide $P(x)$ if and only if $p|x$. As a result, $P(p)$ is a power of $p$ for any large prime $p$; as $P(x)$ is bounded by $x^{\deg P+1}$ for large $x$, there are finitely many possible exponents, so there must exist some positive integer $n$ for which $P(p)=p^n$ for infinitely many primes $p$, whence $P(x)=x^n$ everywhere. However, by repeating the same process at $P(1)$ instead of $P(0)$, we have that
$$P(x)-P(1)=(x-1)^k$$
as well for some $k$; these cannot both be true.
