15
$\begingroup$

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$?

$\endgroup$
32
$\begingroup$

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\}$.

| cite | improve this answer | |
$\endgroup$
20
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ how does a polynomial with rational coefficients induce a map $\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z}$? $\endgroup$ – user158636 Aug 9 at 19:29
  • 2
    $\begingroup$ Just take the primes not dividing denominators of coefficients and reduce. $\endgroup$ – Lucia Aug 9 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$ – LSpice Aug 9 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy