Let $Q\in \mathbb{Z}[x]$ be a polynomial defining an injective function $\mathbb{Z}\to\mathbb{Z}$. Does it define an injective function $\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$ for some prime $p$?
2 Answers
Consider $Q(x)=x(2x-1)(3x-1)$. This gives an injective map $\mathbb Z\to \mathbb Z$, because $n<m \implies Q(n)<Q(m)$. However, this $Q$ is not injective over $\mathbb Z/p\mathbb Z$ for any $p$ because $Q(x)=0$ has three solutions when $p\geq 5$ and two solutions when $p\in \{2,3\}$.
While the original question has been answered, there is a beautiful result of Fried in On a conjecture of Schur which is relevant to such questions. Suppose $Q$ is a polynomial in ${\Bbb Q}[x]$ such that for infinitely many primes the induced map from ${\Bbb Z}/p{\Bbb Z}$ to ${\Bbb Z}/p{\Bbb Z}$ is bijective. Then $Q$ must be of the form
(i) $Q(x) = ax^n + b$,
or
(ii) $Q(x) = T_n(x)$, where $T_n(x)$ denotes the $n$-th Chebyshev polynomial,
or
(iii) Compositions of functions of this type.
This established an old conjecture of Schur. See also the account Turnwald - On Schur's conjecture, which discusses the history of the problem, and gives a detailed proof, correcting inaccuracies in the earlier literature.
-
1$\begingroup$ how does a polynomial with rational coefficients induce a map $\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$? $\endgroup$– user158636Aug 9, 2020 at 19:29
-
2$\begingroup$ Just take the primes not dividing denominators of coefficients and reduce. $\endgroup$– LuciaAug 9, 2020 at 19:30
-
1$\begingroup$ That is to say, part of the quantification is "for infinitely many primes $p$, there is an induced self-map of $\mathbb Z/p\mathbb Z$ and it is bijective". (Of course, the first condition throws away only finitely many primes.) $\endgroup$– LSpiceAug 9, 2020 at 19:53