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.

  • 1
    $\begingroup$ 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. $\endgroup$ Mar 10 '15 at 11:33
  • $\begingroup$ Any numeric evidence, to begin with? $\endgroup$ Mar 10 '15 at 12:02
  • 1
    $\begingroup$ A reference: arxiv.org/abs/1211.6044v1. $\endgroup$
    – MrSelberg
    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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.