A polynomial over a finite field $\mathbb{F}_{q}$ is called a permutation polynomial (PP) of $\mathbb{F}_{q}$ if it induces a bijection of $\mathbb{F}_{q}$. The study of permutation polynomials (PPs) started with Hermite [1] for prime fields, and Dickson [2] for arbitrary finite fields. Recently, the applications of PPs of finite fields for cryptography [3-7] bring this subject to the front scene. Let M be a message (an element of $\mathbb{F}_{q}$) which is to be sent securely from Alice to Bob. If $f(x)$ is a PP of $\mathbb{F}_{q}$, then Alice sends to Bob the field element $N =f(M)$. Because $f(x)$ is bijective, Bob can recover the message M by computing $f^{-1}(N)=f^{-1}(f(M))=M$. In order to be useful in a cryptographic system, $f(x)$ have some additional properties [8].

Although PPs were a subject of study for a long time, only a handful of specific families of PPs of finite fields are known so far. Hence finding new classes of PPs is an interesting subject. Recently, it has achieved significant progress; see for example, [9-19].

Very recently, Li, Helleseth and Tang [9] investigated PPs of the form

$g(x)=(x^{q} - x + c)^{\frac{q^{2} -1}{d}+1} +x^{q}+x, $

where d=3 and $c\in\mathbb{F}_{q^2}$ with $c +c^{q} =0$. It was a further result of Theorem 1 presented by Zha and Hu [19]. It is an open problem to determine such kind of PPs for $d = 4$. This paper is motivated by the question: when does $g(x)$ permute $\mathbb{F}_{q^{2}}$ for $d \geq 4$?

In this paper we extend the integer d to an arbitrary positive factor of q-1. The main contribution of this paper is that we give a simple condition for which

$(x^{q} -x +c)^{\frac{k(q^2-1)}{d}\, +1} + x^{q} +x$

is a PP of $\mathbb{F}_{q^2}$, where d and k are integers such that $1\le k <d$ and $d \mid q-1$. This work gives a substantial extension of the result of Li, Helleseth and Tang [9].

The following lemma provides an interpolation method of constructing PPs. It is developed by Cao, Hu and Zha [11, Proposition 2], which is a generalization of a result of Fernando and Hou [13, Proposition 1].

Lemma 1  Let $\theta(x) \in \mathbb{F}_{q}[x]$ induce a map from $\mathbb{F}_{q}$ to its subset $\{e_{1}, \cdots, e_{n}\}$. Define

$\begin{equation} f(x) = \sum_{i =1}^{n} f_{i}(x)\big(1 -(\theta(x) -e_{i})^{q-1}\big), \end{equation}$

(2.1)

where $f_{1}(x)$, $\cdots$, $f_{n}(x) \in \mathbb{F}_{q}[x]$. Then $f(x)$ is a PP of, $\mathbb{F}_{q}$ if and only if

(ⅰ) $f_{i}$ is injective on %the non-empty set $\theta^{-1}(e_{i})$ for each $i \in \{1, 2, \cdots, n\};$ and

(ⅱ) $f_{i}(\theta^{-1}(e_{i})) \cap f_j(\theta^{-1}(e_{j})) = \emptyset$ for all $i \neq j \in \{1, 2, \cdots, n\}, $ here $\theta^{-1}(e_{i}) =\{x \mid \theta(x) =e_{i}\}$ %, the preimage of $e_{i}$ under $\theta$, and $f_{i}(\theta^{-1}(e_{i}))$ is the image set of $\theta^{-1}(e_{i})$ under $f_{i}$.

It is observed from (2.1) that $f(x) = f_{i}(x)$ for $x \in \theta^{-1}(e_{i})$. In other words, $f(x)$ is a piecewise polynomial composed of $f_{i}(x)$ as pieces. Clearly $\{\theta^{-1}(e_{i}) \mid i =1, 2, \cdots, n \}$ is a partition of $\mathbb{F}_{q}$. This lemma indicates that $f(x)$ is a PP of $\mathbb{F}_{q}$ if and only if $\{ f_{i}(\theta^{-1}(e_{i})) \mid i =1, 2, \cdots, n \}$ is a partition of $\mathbb{F}_{q}$. We also need the following lemmas.

Lemma 2  $\alpha x^{q} +\beta x +\gamma\in \mathbb{F}_{q^2}[x]$ is a PP of, $\mathbb{F}_{q^{2}}$ if and only if, $\alpha^{q+1} \neq \beta^{q+1}$.

Proof  $\alpha x^{q} +\beta x$ is a PP of $\mathbb{F}_{q^2}$ if and only if $\big|\begin{smallmatrix} \, \alpha & \beta^q \\ \, \beta & \alpha^q \end{smallmatrix}\big| \ne 0$, i.e., $\alpha^{q+1}\! \ne \beta^{q+1}$.

Lemma 3  Let $\xi$ be a primitive element of, $\mathbb{F}_{q^{2}}$. Then the subfield

$\mathbb{F}_{q} =\{0\} \cup \{ \xi^{(q +1)i} \mid i= 1, 2, \cdots, q-1 \}.$

Proof  Since $\xi$ is a primitive element of $\mathbb{F}_{q^{2}}$, $\xi^{(q +1)i}$ are all distinct for $i \in \{ 1, 2, \cdots, q-1\}$. Also $(\xi^{(q +1)i})^q =\xi^{(q^2 +q)i} =\xi^{(1 +q)i} =\xi^{(q +1)i}$, hence the result holds true.

Theorem 1  Let q be an odd prime power, and let $k, d$ be integers with $1\le k <d$ and $d \mid q-1$. Let $c\in\mathbb{F}_{q^2}$ with $c +c^{q} =0$, and define

$f(x)=(x^{q} -x +c)^{\frac{k(q^2-1)}{d}\, +1} + x^{q} +x.$

Then the following statements hold

(ⅰ) for even d, $f(x)$ is a PP of, $\mathbb{F}_{q^2}$ if, $\gcd\big(\frac{k(q^2-1)}{d}+1, \, d \big) =1$.

(ⅱ) for odd d, $f(x)$ is a PP of, $\mathbb{F}_{q^2}$ if and only if, $\gcd\big(\frac{k(q^2-1)}{d}+1, \, d \big) =1$.

Theorem 1 describes explicit conditions for $f(x)$ to be a PP of $\mathbb{F}_{q^{2}}$. It provides a substantial extension of the result of Li, Helleseth and Tang [9]. It is well-known that the trace function $\mathrm{Tr}_{\mathbb{F}_{q^{2}}/\mathbb{F}_{q}}(c)=c +c^{q}=0$ if and only if $c=a^q-a$ for some $a \in \mathbb{F}_{q^{2}}$. Hence the conditions in Theorem 1 are easy to satisfied.

The remainder of this section is devoted to the proof of Theorem 1.

Proof of Theorem 1  Let $\xi$ be a primitive element of $\mathbb{F}_{q^2}$ and $\omega =\xi^{(q^2-1)/d}$. For simplicity, denote $\theta(x)= (x^{q} -x +c)^{\frac{q^2\!-1}{d}}$. Then $\theta$ induces a map from $ \mathbb{F}_{q^2}$ to $\{0, \omega, \omega^2, \cdots, \omega^d\}$. Denote $\theta^{-1}(0)= \{x \in \mathbb{F}_{q^2}\mid \theta(x) =0\}$ and $\theta^{-1}(\omega^{i})= \{x \in \mathbb{F}_{q^2} \mid \theta(x) =\omega^{i}\}$. Then

$f(x)=\left\{ \begin{array}{*{35}{l}} {{f}_{0}}(x):=\psi (x) & \text{for }x\in {{\theta }^{-1}}(0), \\ {{f}_{i}}(x):={{\omega }^{ik}}\phi (x)+\psi (x) & \text{for}\ x\in {{\theta }^{\text{-1}}}({{\omega }^{i}})\ \text{and}\ i\in [d], \\ \end{array} \right.$

here $\phi(x)= x^{q} -x +c$, $\psi(x)= x^{q} +x$ and $[d] =\{1, 2, \cdots, d\}$.

(ⅰ) We will prove that $f(x)$ is a PP of, $\mathbb{F}_{q^2}$ if $\gcd(\frac{k(q^2-1)}{d}+1, \, d)=1$. The proof is divided into four steps. First, we show that $f_i(x)$ is a PP of $\mathbb{F}_{q^2}$ for each $i \in [d]$. In fact,

$f_i(x) = (\omega^{ik}+1)x^{q} +(1-\omega^{ik})x +\omega^{ik}c.$

Since $\omega^{d}=1$ and $d \mid q-1$, we have $\omega^{q} =\omega$. Because q is odd, it follows that

$\begin{split} & \quad (\omega^{ik}+1)^{q+1}-(1-\omega^{ik})^{q+1} \\ & = (\omega^{ik}+1)^{q}(\omega^{ik}+1)-(1-\omega^{ik})^{q}(1-\omega^{ik})\\ & = (\omega^{ikq}+1)(\omega^{ik}+1)-(1-\omega^{ikq})(1-\omega^{ik})\\ & = (\omega^{ik}+1)^2-(1-\omega^{ik})^2\\ & = 4\omega^{ik} \ne 0. \end{split}$

By Lemma 2, $f_i(x)$ is a PP of $\mathbb{F}_{q^2}$ for each $i \in [d]$.

Next, we need to verify that $f_{0}$ is injective on $\theta^{-1}(0)$, $f_{i}$ is injective on $\theta^{-1}(\omega^{i})$ and

$ f_{0}(\theta^{-1}(0)) \cap f_i(\theta^{-1}(\omega^{i})) =\emptyset $

for each $i \in [d]$. If $\theta^{-1}(0) =\emptyset$, then we are done. If $\theta^{-1}(0) \neq \emptyset$, there exists $e \in \theta^{-1}(0)$; that is, $\theta(e)=\phi(e)^{(q^2\!-1)/d}\! =0$. Then $\phi(e) =0$. Substituting e into $f_{i}(x)$ yields

$f_{i}(e) =\omega^{ik}\phi(e) +\psi(e) =\psi(e)=f_{0}(e). $

Hence $f_{i}(\theta^{-1}(0)) =f_{0}(\theta^{-1}(0))$. Since $f_i(x)$ is a PP of $\mathbb{F}_{q^2}$ for each $i \in [d]$, $f_{i}(x)$ is injective on $\theta^{-1}(0)$ and $\theta^{-1}(\omega^{i})$, and $f_{i}(\theta^{-1}(0)) \cap f_i(\theta^{-1}(\omega^{i})) =\emptyset$. Thus $f_{0}(x)$ is injective on $\theta^{-1}(0)$, and $f_{0}(\theta^{-1}(0)) \cap f_i(\theta^{-1}(\omega^{i})) =\emptyset$ for each $i \in [d]$.

Now we show that, for $i \ne j \in [d]$, $f_i(\theta^{-1}(\omega^i)) \cap f_j(\theta^{-1}(\omega^j)) = \emptyset$ if and only if eqs.(3.1) and (3.2) have no common solutions in $\mathbb{F}_{q^{2}}$. Assume that $y \in f_i(\theta^{-1}(\omega^i)) \cap f_j(\theta^{-1}(\omega^j))$, then there exist $e \in \theta^{-1}(\omega^i)$ and $e' \in \theta^{-1}(\omega^j)$ such that $y = f_{i}(e) = f_{j}(e')$. Combining $f_i(e) =y$ and $f_i(e)^{q} =y^{q}$ leads to

$e %= 4\omega^{-ik}[(\omega^{ik}+1)(y-\omega^{ik}c)^{q}-(1-\omega^{ik} )^{q}(y-\omega^{ik}c)]. = (4\omega^{ik})^{-1}[(\omega^{ik}+1)y^{q} +(\omega^{ik}-1)y + 2\omega^{ik}c].$

Substituting the above identity into $\theta(e)= \omega^{i}$ gives rise to

$\begin{equation} (-y^{q} +y)^{\frac{q^2 -1}{d}} = 2^{\frac{q^2 -1}{d}}\omega^{si}, \end{equation}$

(3.1)

where $s =\frac{k(q^2 -1)}{d}+1$. Similarly, for $e' \in \theta^{-1}(\omega^j)$, we have

$\begin{equation} (-y^{q} +y)^{\frac{q^2 -1}{d}} = 2^{\frac{q^2 -1}{d}}\omega^{sj}. \end{equation}$

(3.2)

So $f_i(\theta^{-1}(\omega^i)) \cap f_j(\theta^{-1}(\omega^j)) \ne \emptyset$ if and only if eqs.(3.1) and (3.2) have common solutions.

Finally, if $\gcd(s, d)=1$ then $si \not\equiv sj \pmod{d}$ and $\omega^{si} \ne \omega^{sj}$ for all $i \ne j \in [d]$, so eqs.(3.1) and (3.2) have no common solutions. Thus $f_i(\theta^{-1}(\omega^i)) \cap f_j(\theta^{-1}(\omega^j)) = \emptyset$. By Lemma 1, if $\gcd(\frac{k(q^2-1)}{d}+1, \, d)=1$ then $f(x)$ is a PP of, $\mathbb{F}_{q^2}$.

(ⅱ) To prove the latter part of the theorem, it suffices to show that if d is odd and $\gcd(s, d)>1$ then $f(x)$ is not a PP of $\mathbb{F}_{q^{2}}$. Let $\gcd(s, d) =a >1$, there exists an integer b such that $ab =d$ and $1 \le b < d$. Then

$sb =s(d/a) =d(s/a) \equiv 0 \equiv sd\!\pmod{d}, $

so $\omega^{sb} = \omega^{sd}$. We assert that $f_b(\theta^{-1}(\omega^b)) \cap f_d(\theta^{-1}(\omega^d)) \ne \emptyset$, namely $f(x)$ is not a PP of $\mathbb{F}_{q^{2}}$.

It is enough to prove that eqs.(3.1) and (3.2) have a common solution for $i=b$ and $j=d$, i.e., the following equation

$\begin{equation} \left\{ \begin{array}{l} (-x^{q} +x)^{\frac{q^2 -1}{d}} = 2^{\frac{q^2 -1}{d}}\omega^{sb}, \\ (-x^{q} +x)^{\frac{q^2 -1}{d}} = 2^{\frac{q^2 -1}{d}}\omega^{sd} \end{array} \right. \end{equation}$

(3.3)

has a solution in $\mathbb{F}_{q^{2}}$ if d is an odd divisor of q-1. By $\omega^{sb} = \omega^{sd}=1$, eq.(3.3) reduces to

$\begin{equation} (-x^{q} +x)^{\frac{q^2 -1}{d}} = 2^{\frac{q^2 -1}{d}}. \end{equation}$

(3.4)

From $-1=\xi^{\frac{q^2-1}{2}}=(\xi^{\frac{q+1}{2}})^{q-1}$, it follows that $-x^{q} +x =C^{-1}((Cx)^{q} +Cx)$, where $C=\xi^{\frac{q+1}{2}}$. Because $((2C)^{\frac{q^2 -1}{d}})^d =1$ and $\omega$ is a primitive d-th root of unity, $(2C)^{\frac{q^2 -1}{d}}$ is a power of $\omega$. We may assume $(2C)^{\frac{q^2 -1}{d}}=\omega^k$ for some $k \in [d]$. Then eq. (3.4) can be rewritten as

$\begin{equation} \big((Cx)^{q} +Cx\big)^{(q^{2} -1)/d} = \omega^k. \end{equation}$

(3.5)

As the trace function $\mathrm{Tr}_{\mathbb{F}_{q^{2}}/\mathbb{F}_{q}}(x)=x^{q} +x$ induces a surjection from $\mathbb{F}_{q^{2}}$ to $\mathbb{F}_{q}$,

$\begin{equation} \{x^{q} +x \mid x \in \mathbb{F}_{q^{2}}\} = \mathbb{F}_{q}. \end{equation}$

(3.6)

Both x and Cx permute $\mathbb{F}_{q^{2}}$, it follows that

$\begin{equation} \{(Cx)^{q} +Cx \mid x \in \mathbb{F}_{q^{2}}\} = \{x^{q} +x \mid x \in \mathbb{F}_{q^{2}}\}. \end{equation}$

(3.7)

Combining (3.6), (3.7) and Lemma 3 yields

$\{(Cx)^{q} +Cx \mid x \in \mathbb{F}_{q^{2}}\}=\{ 0\} \cup\{ \xi^{(q +1)i}: i= 1, 2, \cdots, q-1 \}.$

Since $\omega =\xi^{(q^{2} -1)/d}$, we have

$\{\big( (Cx)^{q} +Cx \big)^{(q^{2} -1)/d} \mid x \in \mathbb{F}_{q^{2}}\} = \{ 0\}\cup \{ \omega^{(q +1)i}: i= 1, 2, \cdots, q-1 \}.$

Since d is an odd divisor of q-1,

$\gcd(q+1, d)=\gcd(q-1+2, d)=\gcd(2, d)=1, $

and so $\{(q+1)i \mid i=1, \cdots, d \}$ is a complete set of residues modulo d. Consequently,

$\{\big( (Cx)^{q} +Cx \big)^{(q^{2} -1)/d} \mid x \in \mathbb{F}_{q^{2}}\} = \{ 0, \omega, \omega^2, \cdots, \omega^d \} $

and eq. (3.5) has a solution for any $k \in [d]$. Therefore $f_b(\theta^{-1}(\omega^b)) \cap f_d(\theta^{-1}(\omega^d)) \ne \emptyset$, and so $f(x)$ is not a PP of $\mathbb{F}_{q^{2}}$.

Permutation polynomials of the form $(x^{q} -x +c)^{\frac{k(q^{2}-1)}{d}\, +1} +x^{q} +x$ over $\mathbb{F}_{q^{2}}$ are presented, where $1 \le k <d$ and d is an arbitrary positive divisor of q-1. This result generalizes a known class of permutation polynomials.