Permutations of the elements of $\mathbb Z_p$

Question

Let $p$ be prime. Describe all permutations $\sigma$ of the elements of $\mathbb Z_p$, having the property that $\{\sigma(i)-i: i\in\mathbb Z_p\}=\mathbb Z_p$

---

(Added by Robert Lewis in an attempt to provide background, motivation, and other context for this engaging problem)

This problem essentially asks for a method of representing permutations $\sigma$ of the finite field $\Bbb Z_p$ which respects the algebraic structure/computations inherent in such fields.

Answer 1

Let $\Bbb F$ be any finite field of characteristic $p$ a prime; as is well-known, $\vert \Bbb F \vert = p^n$ for some $n \in \Bbb N$, the natural numbers. We begin with the following

Proposition: Any function $g:\Bbb F \to \Bbb F$ may be represented by a polynomial $p_g(x) \in \Bbb F[x]$.

Proof: We use Lagrange interpolation. Letting the elements of $\Bbb F$ be denoted by $f_0 = 0, f_1 = 1, f_2, \ldots, f_{q - 1}$, we define the polynomials $\lambda_i(x) \in \Bbb F[x]$, $0 \le i \le q -1$, via

$\lambda_i(x) = \prod_{j = 0, j \ne i}^{j = q - 1}\dfrac{x - f_j}{f_i - f_j}; \tag{1}$

it is easily seen that

$\lambda_i(f_k) = 0, k \ne i , \tag{2}$

since a factor of $f_k - f_k = 0$ will occur as one of the numerators in the product

$\lambda_i(f_k) = \prod_{j = 0, j \ne i}^{j = q - 1}\dfrac{f_k - f_j}{f_i - f_j}; \tag{3}$

also,

$\lambda_i(f_i) = \prod_{j = 0, j \ne i}^{j = q - 1}\dfrac{f_i - f_j}{f_i - f_j} = 1. \tag{4}$

We now see that the polynomial

$p_g(x) = \sum_0^{q -1} g(f_i) \lambda_i(x) \tag{5}$

satisfies

$p_g(x) = g(x) \tag{6}$

for all $f_k \in \Bbb F$, since

$p_g(f_k) = \sum_0^{q -1} g(f_i) \lambda_i(f_k) = g(f_k), \tag{5}$

using (2) and (4). QED.

To be continued . . .

Answer 2

Take all linear polynomials of the form $f(x) = ax+b$ with $a=2,3,\ldots p-1$ and $b=0,1,2,\ldots p-1$. Then $f(x)-x$ is also a non-constant linear polynomial and hence has a unique zero, hence fixed point for $f$. As $a$ is coprime to $p$ these functions are bijective and provide permutations as desired.

Answer 3

We use the OEIS method. First observe that the problem makes sense even if $p$ is not prime. Let $a_n$ denote the number of permutations $\pi$ of the ring $R=\mathbb{Z}/n\mathbb{Z}$ such that $\{\pi(x)-x\mid x\in R\}=R$. Direct calculation for small $n$ shows that $a_n=0$ if $n$ is even; for odd $n$ we get the sequence $1,3,15,133,2025,\ldots$

This sequence appears in OEIS as A006717, which contains more terms and some references. In particular, we find this page, which gives the nice interpretation of $a_n$ as the number of non-attacking semi-queens on an $n\times n$ toroidal chessboard. (A "semi-queen" can only attack along diagonals of slope $1$ (not $-1$).) No closed form appears to be known.

Answer 4

These are known as complete mappings of the finite field $\mathbb{F}_{p}$. I think you will find that it is quite a difficult problem to describe all such permutations. Here is a good overview:

Niederreiter, Harald; Robinson, Karl H., Complete mappings of finite fields, J. Aust. Math. Soc., Ser. A 33, 197-212 (1982). ZBL0495.12018.

You will see that this is very dependent on $p$, for example when $p=7$ we have $\pm {(x+a)}^{4} +3x + b$ giving examples for any choice of $a,b \in \mathbb{F}_{7}$; but finding and describing such polynomials relies on ad-hoc methods.