(Both the published version and the arXiv version are available online.)

We prove that, if x^m+cxⁿ permutes the prime field F_p, where m>n>0 and c is in F_p^*, then  gcd(m-n, p-1) > p^½-1. This improves results of Wan and Turnwald, who gave a similar lower bound on m.

Conversely, we prove that if  q≥4 and  m>n>0 are fixed and satisfy  gcd(m-n, q-1) > 2q(log log q) / log q, then there exist permutation binomials over F_q of the form x^m+cxⁿ if and only if  gcd(m, n, q-1)=1. This refines and generalizes results of Carlitz–Wells and Laigle-Chapuy.

We also give a heuristic suggesting that there should be no permutation binomials x^m+cxⁿ over F_p with m>n>0 and gcd(m-n, p-1) < p / (2 log p). We verified this conclusion by computer for all  p<10⁵. Combined with the above existence result, this gives a rather clear picture of permutation binomials over prime fields (albeit based on a heuristic). The situation over nonprime fields remains mysterious, due to the existence of low-degree permutation binomials like x¹⁰+3x over F₃₄₃.

A weaker version of our nonexistence result can be proved using Weil's bound (the Riemann hypothesis for curves). If  g(x) := x^m+cxⁿ with c in F_p^* and m>n>0 but m/n is not a power of  p, then it can be shown that F(x, y) := (g(x)-g(y))/(x-y) is absolutely irreducible, so Weil's bound implies it has points off the diagonal (and thus g does not permute F_p) whenever p>m⁴. Our result improves this by replacing the exponent `4' by `2', and further replacing m by gcd(m-n, p-1). Thus, our nonexistence result yields a nontrivial lower bound on the number of  F_p-rational points on the curve F(x,y)=0, even in situations where Weil's lower bound is negative. However, our proof does not use algebraic geometry; instead we use a character sum argument due to Hermite. On the other hand, we use Weil's bound to prove our existence result.

Michael Zieve:  home page   publication list