# Permutation polynomials mod $p$ of the form $(x+1)^n-x^n$

Among some permutation polynomials I've been studying, $f(x)=(x+1)^n-x^n$ is one of the polynomials that I cannot grasp.

Question : For a given odd prime $p$, how can we find every positive integer $n$ such that $f(x)=(x+1)^n-x^n$ is a permutation polynomial mod $p$ ?

The answer seems $n=(p-1)m+2\ \ (m=0,1,2,\cdots)$, but I'm facing difficulty in proving that. This question has been asked previously on math.SE without receiving any answers.

The followings are what I've got.

• $f(0)\equiv 1.$

• $f(p-1)\equiv -(-1)^n\Rightarrow \text{$n$has to be even}\Rightarrow f(p-1)\equiv p-1$.

• For $n=(p-1)m+r$, $f(x)\equiv (x+1)^r-x^r$ because $a^{p-1}\equiv 1$ for $a$ which is coprime to $p$.

• $f\left(\frac{p-1}{2}\right)\equiv 0$.

• $f\left(\frac{p-1}{2}+a\right)+f\left(\frac{p-1}{2}-a\right)\equiv 0$ for any $a$.

I would like to know any relevant references as well.

• Small remarks: we may consider only $n<p$, else replace $n$ to $n-(p-1)$. Next, $n/2$ should be coprime to $(p-1)/2$, else $f(x)$ has another root. Mar 10 '15 at 11:33
• Any numeric evidence, to begin with? Mar 10 '15 at 12:02
• A reference: arxiv.org/abs/1211.6044v1. Mar 10 '15 at 14:29

The expected answer is correct, it is a theorem by Norman Johnson, see here. Note that $(X+1)^n-X^n$ is a permutation polynomial if and only if $(X+a)^n-X^n$ is a permutation polynomial for each fixed nonzero $a$. This latter condition is a special case of planarity: A function $f:K\to K$ on a field $K$ is called planar, if $x\mapsto f(x+a)-f(x)$ is bijective for every nonzero $a$.
So you ask for planar monomials on $\mathbb F_p$ for odd primes $p$. Actually, it was later proved that any planar function on $\mathbb F_p$ is given by a quadratic polynomial, see this MO page for more information and references.