Return to Answer

I'll write $T_f$ for the set of primes $p$ such that $f(x)$ is a bijection $\mathbb{F}_p \to \mathbb{F}_p$. I claim that $T_f$ is always either finite or else $\# \{ p \in T_f : p \leq y \} \sim c \tfrac{y}{\log y}$ for some $c>0$.

The following result is known as Schur's conjecture; a flawed proof was given by Fried, with corrected versions by Turnwald and Müller:

Theorem Let $f(x) \in \mathbb{Z}[x]$. If $T_f$ is infinite, then $f(x)$ is a composition of linear polynomials and Dickson polynomials.

One should note that the Dickson polynomial $D_n(x,0)$ is just $x^n$, so this includes the possibility of including monomials in our composition.

A composition of functions $\mathbb{F}_p \to \mathbb{F}_p$ will be bijective if and only if all the functions composed are bijective. Linear functions are always bijective; the monomial $D_n(x,0)=x^n$ is bijective iff $GCD(n,p-1)=1$ and, for $a \neq 0$, the Dickson polynomial $D_n(x,a)$ is bijective iff $GCD(n,p^2-1)=1$ or, equivalently, $GCD(n,p-1) = GCD(n,p+1)=1$. (This last statement is copied from Lemma 1.4 in Turnwald; I didn't check it.) In short, imposing that our composition is bijective imposes finitely many conditions on the residue class of $p$ modulo various integers.

If these modular conditions can be satisfied by infinitely many primes, then they are satisfied by $\sim c \tfrac{y}{\log y}$ primes $\leq y$, by the PNT in arithmetic progressions.

Polynomials where $T_f$ is infinite are exceptional polynomials. (The definition of "exceptional" is that there are infinitely many prime powers $q$ such that $f$ is bijective on $\mathbb{F}_q$, so it also allows examples like $x^2$ which is bijective on $\mathbb{F}_{2^k}$ but not on $\mathbb{F}_p$ for any odd $p$; imposing bijectivity for infinitely many primes rather than prime powers is obviously even more restrictive.)

As the name suggests, exceptional polynomials are very rare for degree $\geq 5$. For example, they all have solvable Galois group, where as almost all degree $n$ polynomials have Galois group $S_n$.

In degrees $2$, $3$ and $4$, your condition that $T_f$ be infinite is still very rare (although polynomials which are bijective on infinitely many $\mathbb{F}_{2^k}$ or infinitely many $\mathbb{F}_{3^k}$ are not so rare). Indeed, a composition of Dickson polynomials of degree $\leq 4$ must be a composition of $D_2(x,\alpha)$, $D_3(x,\alpha)$ and $D_4(x, \alpha)$ for various values of $\alpha$. The condition that these are bijective imposes either that $GCD(p-1,2)=1$ (impossible for odd $p$), that $GCD(p^2-1,3)=1$ (impossible for $p \neq 3$) or that $GCD(p-1,3)=1$ (this case can happen). So the only case which occurs is the pre-and-post-composition of $D_3(x,0)=x^3$ with linear polynomial. But then the Galois group of $f$ is $A_3$, and almost all cubics hae Galois group $S_3$.

I'll write $T_f$ for the set of primes $p$ such that $f(x)$ is a bijection $\mathbb{F}_p \to \mathbb{F}_p$. I claim that $T_f$ is always either finite or else $\# \{ p \in T_f : p \leq y \} \sim c \tfrac{y}{\log y}$ for some $c>0$.

The following result is known as Schur's conjecture; a flawed proof was given by Fried, with corrected versions by Turnwald and Müller:

Theorem Let $f(x) \in \mathbb{Z}[x]$. If $T_f$ is infinite, then $f(x)$ is a composition of linear polynomials and Dickson polynomials.

One should note that the Dickson polynomial $D_n(x,0)$ is just $x^n$, so this includes the possibility of including monomials in our composition.

A composition of functions $\mathbb{F}_p \to \mathbb{F}_p$ will be bijective if and only if all the functions composed are bijective. Linear functions are always bijective; the monomial $D_n(x,0)=x^n$ is bijective iff $GCD(n,p-1)=1$ and, for $a \neq 0$, the Dickson polynomial $D_n(x,a)$ is bijective iff $GCD(n,p^2-1)=1$ or, equivalently, $GCD(n,p-1) = GCD(n,p+1)=1$. (This last statement is copied from Lemma 1.4 in Turnwald; I didn't check it.) In short, imposing that our composition is bijective imposes finitely many conditions on the residue class of $p$ modulo various integers.

If these modular conditions can be satisfied by infinitely many primes, then they are satisfied by $\sim c \tfrac{y}{\log y}$ primes $\leq y$, by the PNT in arithmetic progressions.

Polynomials where $T_f$ is infinite are exceptional polynomials. (The definition of "exceptional" is that there are infinitely many prime powers $q$ such that $f$ is bijective on $\mathbb{F}_q$, so it also allows examples like $x^2$ which is bijective on $\mathbb{F}_{2^k}$ but not on $\mathbb{F}_p$ for any odd $p$; imposing bijectivity for infinitely many primes rather than prime powers is obviously even more restrictive.)

As the name suggests, exceptional polynomials are very rare for degree $\geq 5$. For example, they induced maps $\mathbb{C} \to \mathbb{C}$ all have solvable monodromy, where as almost all degree $n$ polynomials have monodromy group $S_n$. (Indeed, as Will Sawin points out, this is even a Zariski open condition.)

In degrees $2$, $3$ and $4$, your condition that $T_f$ be infinite is still very rare (although polynomials which are bijective on infinitely many $\mathbb{F}_{2^k}$ or infinitely many $\mathbb{F}_{3^k}$ are not so rare). Indeed, a composition of Dickson polynomials of degree $\leq 4$ must be a composition of $D_2(x,\alpha)$, $D_3(x,\alpha)$ and $D_4(x, \alpha)$ for various values of $\alpha$. The condition that these are bijective imposes either that $GCD(p-1,2)=1$ (impossible for odd $p$), that $GCD(p^2-1,3)=1$ (impossible for $p \neq 3$) or that $GCD(p-1,3)=1$ (this case can happen). So the only case which occurs is the pre-and-post-composition of $D_3(x,0)=x^3$ with linear polynomial. But then the monodromy of $f : \mathbb{C} \to \mathbb{C}$ is $A_3$ (in other words, $f'(x)$ has a double root), and this does not happen on a Zariski open set.

I'll write $T_f$ for the set of primes $p$ such that $f(x)$ is a bijection $\mathbb{F}_p \to \mathbb{F}_p$. I claim that $T_f$ is always either finite or else $\# \{ p \in T_f : p \leq y \} \sim c \tfrac{y}{\log y}$ for some $c>0$.

The following result is known as Schur's conjecture; a flawed proof was given by Fried, with corrected versions by Turnwald and Müller:

Theorem Let $f(x) \in \mathbb{Z}[x]$. If $T_f$ is infinite, then $f(x)$ is a composition of linear polynomials and Dickson polynomials.

One should note that the Dickson polynomial $D_n(x,0)$ is just $x^n$, so this includes the possibility of including monomials in our composition.

A composition of functions $\mathbb{F}_p \to \mathbb{F}_p$ will be bijective if and only if all the functions composed are bijective. Linear functions are always bijective; the monomial $D_n(x,0)=x^n$ is bijective iff $GCD(n,p-1)=1$ and, for $a \neq 0$, the Dickson polynomial $D_n(x,a)$ is bijective iff $GCD(n,p^2-1)=1$ or, equivalently, $GCD(n,p-1) = GCD(n,p+1)=1$. (This last statement is copied from Lemma 1.4 in Turnwald; I didn't check it.) In short, imposing that our composition is bijective imposes finitely many conditions on the residue class of $p$ modulo various integers.

If these modular conditions can be satisfied by infinitely many primes, then they are satisfied by $\sim c \tfrac{y}{\log y}$ primes $\leq y$, by the PNT in arithmetic progressions.

Polynomials where $T_f$ is infinite are exceptional polynomials. (The definition of "exceptional" is that there are infinitely many prime powers $q$ such that $f$ is bijective on $\mathbb{F}_q$, so it also allows examples like $x^2$ which is bijective on $\mathbb{F}_{2^k}$ but not on $\mathbb{F}_p$ for any odd $p$; imposing bijectivity for infinitely many primes rather than prime powers is obviously even more restrictive.)

As the name suggests, exceptional polynomials are very rare for degree $\geq 5$. For example, they all have solvable Galois group, where as almost all degree $n$ polynomials have Galois group $S_n$. Also, by completing the square, quadratics won't have $T_f$ infinite, although they might be exceptional because of $\mathbb{F}_{2^k}$. I'm not sure what happens in degrees $3$ and $4$.

I'll write $T_f$ for the set of primes $p$ such that $f(x)$ is a bijection $\mathbb{F}_p \to \mathbb{F}_p$. I claim that $T_f$ is always either finite or else $\# \{ p \in T_f : p \leq y \} \sim c \tfrac{y}{\log y}$ for some $c>0$.

The following result is known as Schur's conjecture; a flawed proof was given by Fried, with corrected versions by Turnwald and Müller:

Theorem Let $f(x) \in \mathbb{Z}[x]$. If $T_f$ is infinite, then $f(x)$ is a composition of linear polynomials and Dickson polynomials.

One should note that the Dickson polynomial $D_n(x,0)$ is just $x^n$, so this includes the possibility of including monomials in our composition.

A composition of functions $\mathbb{F}_p \to \mathbb{F}_p$ will be bijective if and only if all the functions composed are bijective. Linear functions are always bijective; the monomial $D_n(x,0)=x^n$ is bijective iff $GCD(n,p-1)=1$ and, for $a \neq 0$, the Dickson polynomial $D_n(x,a)$ is bijective iff $GCD(n,p^2-1)=1$ or, equivalently, $GCD(n,p-1) = GCD(n,p+1)=1$. (This last statement is copied from Lemma 1.4 in Turnwald; I didn't check it.) In short, imposing that our composition is bijective imposes finitely many conditions on the residue class of $p$ modulo various integers.

If these modular conditions can be satisfied by infinitely many primes, then they are satisfied by $\sim c \tfrac{y}{\log y}$ primes $\leq y$, by the PNT in arithmetic progressions.

Polynomials where $T_f$ is infinite are exceptional polynomials. (The definition of "exceptional" is that there are infinitely many prime powers $q$ such that $f$ is bijective on $\mathbb{F}_q$, so it also allows examples like $x^2$ which is bijective on $\mathbb{F}_{2^k}$ but not on $\mathbb{F}_p$ for any odd $p$; imposing bijectivity for infinitely many primes rather than prime powers is obviously even more restrictive.)

As the name suggests, exceptional polynomials are very rare for degree $\geq 5$. For example, they all have solvable Galois group, where as almost all degree $n$ polynomials have Galois group $S_n$.

In degrees $2$, $3$ and $4$, your condition that $T_f$ be infinite is still very rare (although polynomials which are bijective on infinitely many $\mathbb{F}_{2^k}$ or infinitely many $\mathbb{F}_{3^k}$ are not so rare). Indeed, a composition of Dickson polynomials of degree $\leq 4$ must be a composition of $D_2(x,\alpha)$, $D_3(x,\alpha)$ and $D_4(x, \alpha)$ for various values of $\alpha$. The condition that these are bijective imposes either that $GCD(p-1,2)=1$ (impossible for odd $p$), that $GCD(p^2-1,3)=1$ (impossible for $p \neq 3$) or that $GCD(p-1,3)=1$ (this case can happen). So the only case which occurs is the pre-and-post-composition of $D_3(x,0)=x^3$ with linear polynomial. But then the Galois group of $f$ is $A_3$, and almost all cubics hae Galois group $S_3$.

I'll write $T_f$ for the set of primes $p$ such that $f(x)$ is a bijection $\mathbb{F}_p \to \mathbb{F}_p$. I claim that $T_f$ is always either finite or else $\# \{ p \in T_f : p \leq y \} \sim c \tfrac{y}{\log y}$ for some $c>0$.

The following result is known as Schur's conjecture; a flawed proof was given by Fried, with corrected versions by Turnwald and Müller:

Theorem Let $f(x) \in \mathbb{Z}[x]$. If $T_f$ is infinite, then $f(x)$ is a composition of linear polynomials and Dickson polynomials.

One should note that the Dickson polynomial $D_n(x,0)$ is just $x^n$, so this includes the possibility of including monomials in our composition.

A composition of functions $\mathbb{F}_p \to \mathbb{F}_p$ will be bijective if and only if all the functions composed are bijective. Linear functions are always bijective; the monomial $D_n(x,0)=x^n$ is bijective iff $GCD(n,p-1)=1$ and, for $a \neq 0$, the Dickson polynomial $D_n(x,a)$ is bijective iff $GCD(n,p^2-1)=1$ or, equivalently, $GCD(n,p-1) = GCD(n,p+1)=1$. (This last statement is copied from Lemma 1.4 in Turnwald; I didn't check it.) In short, imposing that our composition is bijective imposes finitely many conditions on the residue class of $p$ modulo various integers.

If these modular conditions can be satisfied by infinitely many primes, then they are satisfied by $\sim c \tfrac{y}{\log y}$ primes $\leq y$, by the PNT in arithmetic progressions.

I'll write $T_f$ for the set of primes $p$ such that $f(x)$ is a bijection $\mathbb{F}_p \to \mathbb{F}_p$. I claim that $T_f$ is always either finite or else $\# \{ p \in T_f : p \leq y \} \sim c \tfrac{y}{\log y}$ for some $c>0$.

The following result is known as Schur's conjecture; a flawed proof was given by Fried, with corrected versions by Turnwald and Müller:

Theorem Let $f(x) \in \mathbb{Z}[x]$. If $T_f$ is infinite, then $f(x)$ is a composition of linear polynomials and Dickson polynomials.

One should note that the Dickson polynomial $D_n(x,0)$ is just $x^n$, so this includes the possibility of including monomials in our composition.

A composition of functions $\mathbb{F}_p \to \mathbb{F}_p$ will be bijective if and only if all the functions composed are bijective. Linear functions are always bijective; the monomial $D_n(x,0)=x^n$ is bijective iff $GCD(n,p-1)=1$ and, for $a \neq 0$, the Dickson polynomial $D_n(x,a)$ is bijective iff $GCD(n,p^2-1)=1$ or, equivalently, $GCD(n,p-1) = GCD(n,p+1)=1$. (This last statement is copied from Lemma 1.4 in Turnwald; I didn't check it.) In short, imposing that our composition is bijective imposes finitely many conditions on the residue class of $p$ modulo various integers.

If these modular conditions can be satisfied by infinitely many primes, then they are satisfied by $\sim c \tfrac{y}{\log y}$ primes $\leq y$, by the PNT in arithmetic progressions.

Polynomials where $T_f$ is infinite are exceptional polynomials. (The definition of "exceptional" is that there are infinitely many prime powers $q$ such that $f$ is bijective on $\mathbb{F}_q$, so it also allows examples like $x^2$ which is bijective on $\mathbb{F}_{2^k}$ but not on $\mathbb{F}_p$ for any odd $p$; imposing bijectivity for infinitely many primes rather than prime powers is obviously even more restrictive.)

As the name suggests, exceptional polynomials are very rare for degree $\geq 5$. For example, they all have solvable Galois group, where as almost all degree $n$ polynomials have Galois group $S_n$. Also, by completing the square, quadratics won't have $T_f$ infinite, although they might be exceptional because of $\mathbb{F}_{2^k}$. I'm not sure what happens in degrees $3$ and $4$.