Permutation polynomials of the form $cx+\text {Tr}_{q^{l}/ q}(x^{a})$ and permutation trinomials over finite fields with even characteristic

Abstract

Permutation polynomials over finite fields constitute an active research area and have applications in many areas of science and engineering. Particularly, permutation polynomials with few terms are more popular for their simple algebraic form and additional extraordinary properties. Very recently, G. Kyureghyan and M.E. Zieve (2016) studied permutation polynomials over $\mathbb {F}_{q^{n}}$ of the form $x+\gamma \text {Tr}_{q^{n}/q}(x^{k})$, where q is odd, and nine classes of permutation polynomials were constructed. In this paper, we present fifteen new classes of permutation polynomials of the form $cx+\text {Tr}_{q^{l}/ q}(x^{a})$ over finite fields with even characteristic, which explain most of the examples with q = 2^k, k > 1, k l < 14 and $c\in \mathbb {F}_{q^{l}}^{*}$. Furthermore, we also construct four classes of permutation trinomials.

1 Introduction

Let $\mathbb {F}_{q}$ be the finite field with q elements and $\mathbb {F}_{q}^{*}$ be the multiplicative group with the nonzero elements in $\mathbb {F}_{q}$. A polynomial $f(x)\in \mathbb {F}_{q}[x]$ is called a permutation polynomial if the induced mapping x → f(x) is a permutation of ${\mathbb F}_{q}$. Permutation polynomials have various applications in coding theory [20, 30], cryptography [22, 26, 27] and combinatorial designs [8]. Therefore, the study about permutation polynomials attracts people’s interest for many years. Particularly, permutation polynomials with few terms are more popular thanks to their simple algebraic form and additional extraordinary properties. For example, in [10], Dobbertin first proved a well-known conjecture of Welch stating that the power function $x^{2^{m}+3}$ on $\mathbb {F}_{2^{2m+1}}$ is even maximally nonlinear, or, in other words the crosscorrelation function between a binary maximum-length linear shift register sequence of degree n and a decimation of that sequence by 2^m + 3 takes on precisely the three values − 1,−1 ± 2^m+1. And the key of his proof was a discovery of a class of permutation trinomials. More results about permutation polynomials can be found in [5, 6, 12, 13, 15,16,17,18, 24, 29].

Let q = 2^k. For $\alpha \in \mathbb {F}_{q^{l}}$, the trace function from $\mathbb {F}_{q^{l}}$ to its subfield $\mathbb {F}_{q}$ is defined as

$$\text{Tr}_{q^{l}/q}(\alpha)=\alpha+\alpha^{q}+\cdots+\alpha^{q^{l-1}}. $$

If q = 2, $\text {Tr}_{q^{l}/q}(\alpha )$ is called the absolute trace function, and it is simply denoted by $\text {Tr}_{q^{l}}(\alpha )$. The trace function is often used in constructing permutation polynomials over finite fields [5,6,7, 18, 33, 37]. In [5], P. Charpin and G. Kyureghyan considered a class of permutation polynomials of the shape G(x) + γ Tr _q (H(x)) over $\mathbb {F}_{q}$, where q = 2^k. They found that the considered problem can be reduced to looking for Boolean functions with linear structures. With this idea, they constructed sparse permutation polynomials by choosing both G(x) and H(x) to be monomials. In [7], they extended these results from finite fields with even characteristic to arbitrary finite fields. Very recently, G. Kyureghyan and M.E. Zieve [18] studied all permutation polynomials over $\mathbb {F}_{q^{n}}$ of the form $x+\gamma \text {Tr}_{q^{n}/q}(x^{k})$ with $\gamma \in \mathbb {F}_{q^{n}}^{*}$, q odd, n > 1, and q ⁿ < 5000. They constructed nine classes of permutation polynomials with this special form, which explained most of the experimental results under the aforementioned condition. This motivates us to study such permutation polynomials over finite fields with even characteristic. Hence this paper is devoted to construct new permutation polynomials of the form $cx+\text {Tr}_{q^{l}/q}(x^{a})$, where q = 2^k. To avoid repetitive work from [5], we do not consider the absolute trace function, in other words, we assume that q > 2.

We notice that a permutation polynomial of the form $cx+\text {Tr}_{q^{l}/ q}(x^{a})$ is a permutation trinomial when l = 2. Permutation trinomials have been widely studied for their simple structure and wide applications. For instances, the discovery of a class of permutation trinomials by Ball and Zieve [3] provided a way to prove the construction of the Ree-Tits symplectic spreads of P G(3, q). Hou [16, 17] acquired a necessary and sufficient condition about determining a special permutation trinomial. For more recent results about permutation trinomials, please refer to [9, 14, 24, 25, 28].

We also notice that a permutation polynomial of the form $cx+\text {Tr}_{q^{l}/ q}(x^{a})$ may also with the form $x^{r}h\left (x^{\left (q^{l}-1\right )/d}\right )$ in some special cases, while there are many results about the polynomials with this form over $\mathbb {F}_{q^{l}}$. For instances, let $Q={q_{0}^{m}}$, where q ₀ ≡ 1 (mod d) and d∣m, and $h\in \mathbb {F}_{q_{0}}[x]$. Akbary and Wang [2], Laigle-Chapug [20] proved that x ^r h(x ^(Q−1)/d) permutes $\mathbb {F}_{q}$ if and only if $\gcd (r+n,d)=\gcd \left (r,\left .(Q-1)\middle /d\right .\right )=1$. Zieve made important contributions to determining permutation polynomials with this form. In [34], Zieve obtained a necessary and sufficient condition about a complex form $h(x)=h_{k}(x)^{t}\hat {h}\left (h_{l}(x)^{d_{0}}\right )$, where h _k (x) = 1 + x + ⋯ + x ^k−1 and $t,d_{0},\hat {h}$ satisfy some conditions. For more results about permutation polynomials with this form, one can consult [14, 35, 36].

In this paper, we construct fifteen new classes of permutation polynomials of the form $cx+\text {Tr}_{q^{l}/ q}(x^{a})$ over finite fields with even characteristic. Moreover, four classes of permutation trinomials are also presented. According to the difference on the Hamming weight of a, which is defined to be the number of nonzero coefficients a _i in the binary expansion ${\sum }_{i=0}^{s}a_{i}2^{i}$ of a, we use three different methods to prove these results. In the following, we give the sketches of these methods. The first one is called the elementary approach. It was used in the case where the Hamming weight of a is small. Let $f(x)=cx+\text {Tr}_{q^{l}/ q}\left (x^{a}\right )=d$ and u = c x + d. Then $u=\text {Tr}_{q^{l}/ q}\left (x^{a}\right )\in \mathbb {F}_{q}$ and $x=\frac {1}{c}(u+d)$. Plugging $x=\frac {1}{c}(u+d)$ into f(x) = d leads to an equation of u with low degree. It is not difficult to show that this low degree equation has at most one solution in $\mathbb {F}_{q}$. We call the second method the fractional approach. It has been used in [12, 25], where the permutation trinomials over $\mathbb {F}_{q^{2}}$ of the form x ^r h(x ^q−1) were mainly considered, and p(x) = x ^r h(x)^q−1 was called a fractional polynomial. In the present paper, several new classes of permutation trinomials over $\mathbb {F}_{q^{2}},$where q = 2^k with such form are constructed, some of which are the generalizations of those in [25]. The final method is the multivariate method introduced by Dobbertin [11]. That is to prove the permutation property of a polynomial by algebraic calculations with multivariate equations. It had been widely used to prove permutation polynomials, such as [9, 18] and so on.

By using Magma, we search all permutation polynomials over $\mathbb {F}_{q^{l}}$ of the form $cx+\text {Tr}_{q^{l}/q}(x^{a})$ with q = 2^k, k l < 14, $c\in \mathbb {F}_{q^{l}}^{*}$ and a ∈ [1,q ^l − 2]. We also add some conditions in the process of obtaining the data in Table 1. First, the restriction k > 1 is added to distinguish our study from that of P. Charpin and G. Kyureghyan [5]. Second, we rule out the trivial cases that $\text {Tr}_{q^{l}/q}\left (x^{a}\right )\equiv 0$ for $x\in \mathbb {F}_{q^{l}}$, a is divided by q, and a is a power of 2, where the last case is corresponding to linearized polynomials. All experiment examples are given in Table 1. In Table 1, ω is a primitive element of the corresponding finite field and the overbar of an element denotes the set consisting of all its conjugate elements. Column Ref. refers to the theorem that explains the corresponding examples. It should be noted that an example may be explained by several theorems, however, we only list one for simplicity. Lastly, the symbol ”-” means that an example can not be explained by us up to now. We can see from Table 1 that most of the examples of this form can be generalized to a class of permutation polynomials.

Table 1 Permutation polynomials of the form $\protect cx+\text {Tr}_{2^{kl}/2^{k}}(x^{a})$ over $\protect \mathbb {F}_{2^{kl}}$, k > 1, k l < 14

The rest of this paper is organized as follows. In Section 2 we introduce some useful lemmas. Section 3 contains the permutation polynomials of the form $cx+\text {Tr}_{q^{l}/ q}(x^{a})$. It is divided into three subsections according to the value of l, which are the case that l > 2 is even, the case that l is odd and the case that l = 2. Four classes of permutation trinomials are introduced in Section 4.

2 Preliminary

The following result was discovered independently by several authors. It is also worth pointing out that it is actually the multiplicative case of a more general AGW criterion [1, Lemma 1.2]. Lemma 2.1 will be frequently employed in the sequel.

Lemma 2.1

[23, 31, 34] Pick d, r > 0 with d ∣ (q − 1), and let $h\in \mathbb {F}_{q}[x]$ . Then f (x) = x ^r h (x ^{(q−1) / d})permutes $\mathbb {F}_{q}$ if and only if both

• (1) $\gcd \left (r,\left .(q-1)\middle /d\right .\right )=1$ and

• (2) x ^r h(x)^(q−1)/d permutes μ _d , where $\mu _{d}=\{x\in \overline {{\mathbb F}}_{q}: x^{d}=1\}$ , and $\overline {\mathbb {F}}_{q}$ denotes the algebraic closure of $\mathbb {F}_{q}$ .

The following results on the number of the solutions of quadratic and cubic equations in ${\mathbb F}_{q}$ are useful in the subsequent proof.

Lemma 2.2

[19] Let q = 2^k , where k is a positive integer. The quadratic equation x ² + u x + v = 0, where $u,v\in \mathbb {F}_{q}$ and u ≠ 0, has roots in $\mathbb {F}_{q}$ if and only if $\text {Tr}_{q}\left (\frac {v}{u^{2}}\right )=0$ .

Lemma 2.3

[4] Let $a, b \in \mathbb {F}_{q}$ , where q = 2^k and b ≠ 0. Then the cubic equation x ³ + a x + b = 0has a unique solution in $\mathbb {F}_{q}$ if and only if $\text {Tr}_{q}\left (\frac {a^{3}}{b^{2}}+1\right ) \neq 0$ .

We can work out a solution of a cubic equation by the following method.

Theorem 2.4

[32] Let q = 2^k and $f(x)=x^{3}+ax+b\in {\mathbb F}_{q}[x]$ and b ≠ 0.Let t ₁ be one solution of the quadratic derived equation t ² + b t + a ³ = 0. And let 𝜖 be one solution of x ³ = t ₁ . Then $\epsilon +\frac {a}{\epsilon }$ is a root of f(x).

Philip A. Leonard and Kenneth S. Williams characterized the factorization of a quartic polynomial over $\mathbb {F}_{2^{k}}$ in [21].

Lemma 2.5

[21] Let q = 2^k and $f(x)=x^{4}+a_{2}x^{2}+a_{1}x+a_{0}\in {\mathbb F}_{q}[x]$ , where a ₀≠0. Let g(y) = y ³ + a ₂ y + a ₁ . Then f(x)is irreducible if and only if g(y)only has one solution r in $\mathbb {F}_{q}$ and $\text {Tr}_{q}\left (\frac {a_{0}r^{2}}{{a_{1}^{2}}}\right )=1$ .

The following two theorems were obtained by G. Kyureghyan and M.E. Zieve in [18]. We list them here because they can explain some examples in Table 1.

Theorem 2.6

[18] If q ≡ 1 (mod 3), then $f(x)=x+\text {Tr}_{q^{2}/q}\left (x^{\frac {q^{2}+q+1}{3}}\right )$ permutes $\mathbb {F}_{q^{2}}$ .

Theorem 2.7

[18] For any prime power q and any positive integers l,n with 2l∣n , if $\gamma \in \mathbb {F}_{q^{n}}$ satisfies $\gamma ^{q^{2l}-1}=-1$ , then the polynomial $f(x)=x+\gamma \text {Tr}_{q^{n}/q}(x^{q^{l}+1})$ permutes $\mathbb {F}_{q^{n}}$ .

The following results can be proved similarly as [18, Theorem 6.1].

Theorem 2.8

Let q = 2^k and $f(x)=cx+\text {Tr}_{q^{4}/q^{2}}\left (x^{a}\right )\in {\mathbb F}_{q^{4}}[x].$ Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{4}}$ if one of the following conditions occurs:

• (1) a = q ³ − q + 1and c = 1;

• (2) a = q ⁴ − q ³ + q and c = 1.

3 Permutation polynomials of the form $\protect cx+\text {Tr}_{q^{l}/ q}(x^{a})$

In this section, we describe a few classes of permutation polynomials of the form $cx+\text {Tr}_{q^{l}/ q}(x^{a})$. We divide the results into three subsections according to the value of l. More precisely, they are the case l > 2 is even, l is odd and l = 2. We put the case l = 2 alone out since the results in this case constitute the majority.

3.1 The case l > 2 is even

Theorem 3.1

Let q = 2^k and $f(x)=cx+\text {Tr}_{q^{2n}/q}\left (x^{2^{i}(q+1)}\right )$ , where $c\in \mathbb {F}_{q^{2}}^{*}$ and n,k,i > 0are integers. Then f (x)is a permutation polynomial over $\mathbb {F}_{q^{2n}}$ .

Proof

We show that for any $d\in {\mathbb F}_{q^{2n}}$, the equation f(x) = d has at most one solution in ${\mathbb F}_{q^{2n}}$. Let u = c x + d. Then $u=\text {Tr}_{q^{2n}/q}(x^{2^{i}(q+1)})\in \mathbb {F}_{q}$ and $x=\frac {1}{c}(u+d)$. Plugging $x=\frac {1}{c}(u+d)$ into f(x) = d, we get

$$u+\frac{\text{Tr}_{q^{2n}/q}\left( u^{2^{i+1}}+\left( d^{2^{i}q}+d^{2^{i}}\right)u^{2^{i}}+d^{2^{i}(q+1)}\right)}{c^{2^{i}(q+1)}}=0. $$

Thanks to $u\in \mathbb {F}_{q}$, $\text {Tr}_{q^{2n}/q}\left (1\right )\equiv 0$ and $\text {Tr}_{q^{2n}/q}\left (d^{2^{i}q}+d^{2^{i}}\right )\equiv 0,$we have

$$u=\frac{\text{Tr}_{q^{2n}/q}\left( d^{2^{i}(q+1)}\right)}{c^{2^{i}(q+1)}}.$$

Hence f(x) = d has at most one solution in $\mathbb {F}_{q^{2n}}$. Moreover, f(x) is a permutation polynomial over $\mathbb {F}_{q^{2n}}$. □

Theorem 3.2

Let q = 2^k and $f(x)=cx+\text {Tr}_{q^{2n}/q}\left (x^{q^{2}+1}\right )$ , where $c\in {\mathbb F}_{q}^{*}$ and n,k > 0are integers. Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{2n}}$ .

Proof

It suffices to prove that for any $d\in \mathbb {F}_{q^{2n}}$, f(x) = d has at most one solution in $\mathbb {F}_{q^{2n}}$. Let u = c x + d. Then $u=\text {Tr}_{q^{2n}/q}\left (x^{q^{2}+1}\right )\in \mathbb {F}_{q}$ and $x=\frac {1}{c}(u+d)$. Plugging the above expression of x into f(x) = d, we get

$$u+\text{Tr}_{q^{2n}/q}\left( \frac{1}{c^{2}}(u^{2}+(d^{q^{2}}+d)u+d^{q^{2}+1})\right)=0, $$

i.e.,

$$u=\frac{\text{Tr}_{q^{2n}/q}\left( d^{q^{2}+1}\right)}{c^{2}}. $$

Hence f(x) = d has at most one solution in $\mathbb {F}_{q^{2n}}$. We finish the proof. □

Theorem 3.3

Let q = 2^k and $f(x)=cx+\text {Tr}_{q^{2n}/q}\left (x^{2^{i}\left (q^{2}+1\right )}\right )$ , where $c\in \mathbb {F}_{q^{2}}^{*}$ and n,k,i > 0are integers. Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{2n}}$ if one of the following conditions occurs:

• (1) n is even;

• (2) n is odd and $\left (\frac {1}{c^{2^{i+1}}}+\frac {1}{c^{2^{i+1}q}}\right )^{\frac {q-1}{\gcd (2^{i+1}-1,2^{k}-1)}}\neq 1$ .

Proof

We claim that f (x) = d has at most one solution in $\mathbb {F}_{q^{2n}}$ for any $d\in \mathbb {F}_{q^{2n}}$ in the above two cases. Let u = c x + d. Then $u=\text {Tr}_{q^{2n}/q}\left (x^{2^{i}\left (q^{2}+1\right )}\right )\in \mathbb {F}_{q}$ and $x=\frac {1}{c}(u+d)$. Moreover,

$$\begin{array}{@{}rcl@{}} x^{2^{i}\left( q^{2}+1\right)}&=&\frac{1}{c^{2^{i+1}}}(u+d)^{2^{i}\left( q^{2}+1\right)}\\ &=& \frac{1}{c^{2^{i+1}}}\left( u^{2^{i}}+d^{2^{i}q^{2}}\right)\left( u^{2^{i}}+d^{2^{i}}\right)\\ &=& \frac{1}{c^{2^{i+1}}}\left[u^{2^{i+1}}+(d^{2^{i}q^{2}}+d^{2^{i}})u^{2^{i}}+d^{2^{i}q^{2}+2^{i}}\right]. \end{array} $$

Then plugging the above equation and $x=\frac {1}{c}(u+d)$ into f(x) = d, we get:

• (1) If n is even,

  $$u=\frac{1}{c^{2^{i+1}}}\text{Tr}_{q^{2n}/q^{2}}\left( d^{2^{i}q^{2}+2^{i}}\right)+\frac{1}{c^{2^{i+1}q}}\text{Tr}_{q^{2n}/q^{2}}\left( d^{2^{i}q^{3}+2^{i}q}\right). $$

  Under the first condition, f(x) = d has at most one solution in $\mathbb {F}_{q^{2n}}$.

• (2) If n is odd,

  $$ \left( \frac{1}{c^{2^{i+1}}}\,+\,\frac{1}{c^{2^{i+1}q}}\right)u^{2^{i+1}}\!+u=\frac{1}{c^{2^{i+1}}}\text{Tr}_{q^{2n}/q^{2}}\left( d^{2^{i}q^{2}+2^{i}}\right)\,+\,\frac{1}{c^{2^{i+1}q}}\text{Tr}_{q^{2n}/q^{2}}\left( d^{2^{i}q^{3}+2^{i}q}\right). $$

  (1)

If $c\in \mathbb {F}_{q}^{*}$, then $u=\text {Tr}_{q^{2n}/q}\left (\frac {d^{2^{i}q^{2}+2^{i}}}{c^{2^{i+1}}}\right ).$ It follows that f(x) = d has at most one solution in $\mathbb {F}_{q^{2n}}$.

If $c\in \mathbb {F}_{q^{2}} \backslash \mathbb {F}_{q}$, let $a=\left (\frac {1}{c^{2^{i+1}}}+\frac {1}{c^{2^{i+1}q}}\right )^{-1}$ and $g(x)=x^{2^{i+1}}+ax\in \mathbb {F}_{q}[x]$. Obviously, a ≠ 0,1. Notice that g(x) permutes $\mathbb {F}_{q}$ if and only if g(x) only has zero root in $\mathbb {F}_{q}$. Considering $x^{2^{i+1}}=ax$, then either x = 0 or $x^{2^{i+1}-1}=a$ which is impossible since $\left (\frac {1}{c^{2^{i+1}}}+\frac {1}{c^{2^{i+1}q}}\right )^{\frac {q-1}{\gcd (2^{i+1}-1,2^{k}-1)}}\neq 1$. This means that x = 0 is the unique solution of g(x) = 0 in $\mathbb {F}_{q}$. Thus g(x) is a permutation polynomial over $\mathbb {F}_{q}$. Therefore, (1) has at most one solution in $\mathbb {F}_{q^{2n}}$.

Hence f(x) is a permutation polynomial over $\mathbb {F}_{q^{2n}}$ in the above two cases. □

3.2 The case l is odd

In this subsection, we construct two classes of permutation polynomials of the form $cx+\text {Tr}_{q^{l}/ q}(x^{a})$.

Theorem 3.4

Let q = 2^k , where k is even and k≢0 (mod 3). Let n > 0,i≠j ≥ 0be integers and $f(x)=cx+\text {Tr}_{q^{2n+1}/q}\left (x^{2q^{i}+2q^{j}}\right )$ , where $c\in \mathbb {F}_{q}^{*}$ and $c^{\frac {q-1}{3}}\neq 1$ . Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{2n+1}}$ .

Proof

It suffices to show that for any $d\in \mathbb {F}_{q^{2n+1}}$, f(x) = d has at most one solution in $\mathbb {F}_{q^{2n+1}}$. Let u = c x + d. Then $u=\text {Tr}_{q^{2n+1}/q}\left (x^{2q^{i}+2q^{j}}\right )\in \mathbb {F}_{q}$. Plugging $x=\frac {1}{c}(u+d)$ into f(x) = d, we get

$$ u^{4}+c^{4}u=\text{Tr}_{q^{2n+1}/q}\left( d^{2q^{i}+2q^{j}}\right). $$

(2)

Let $g(u)=u^{4}+c^{4}u\in \mathbb {F}_{q}[u]$. Then g(u) is a permutation polynomial over $\mathbb {F}_{q}$ if and only if g(u) = 0 only has one solution in $\mathbb {F}_{q}$. If there exists $u\in \mathbb {F}_{q}^{*}$ such that g(u) = 0. Then u ³ = c ⁴, we have $c^{\frac {q-1}{3}}=\left (u^{q-1}\right )^{\frac {q}{4}}=1$, which is a contradiction. Therefore, g(u) is a permutation polynomial over $\mathbb {F}_{q}$. Moreover, (2) only has one solution in $\mathbb {F}_{q}$ for any $d\in \mathbb {F}_{q^{2n+1}}$. It follows that f(x) = d has at most one solution in $\mathbb {F}_{q^{2n+1}}$. The proof is finished. □

Theorem 3.5

Let q = 2^k and $f(x)=cx+\text {Tr}_{q^{2n+1}/q}\left (x^{\frac {q^{2}+q}{2}}\right )$ , where $c\in \mathbb {F}_{q}\backslash \{0,1\}$ and n,k > 0are integers. Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{2n+1}}$ .

Proof

Let $g(x)=f\left (x^{2}\right )=cx^{2}+\text {Tr}_{q^{2n+1}/q}\left (x^{{q^{2}+q}}\right )$. Then f(x) permutes $\mathbb {F}_{q^{2}}$ if and only if so does g(x). We show that for any $d\in \mathbb {F}_{q^{2}}$, the equation g(x) = d has at most one solution in $\mathbb {F}_{q^{2}}$.

Let $u=cx^{2}+d=\text {Tr}_{q^{2n+1}/q}\left (x^{{q^{2}+q}}\right )\in \mathbb {F}_{q}$. Then $x=\left (\frac {u+d}{c}\right )^{\frac {1}{2}}$, and

$$x^{q^{2}+q}=\frac{\left( u^{2}+(d^{q^{2}}+d^{q})u+d^{q^{2}+q}\right)^{\frac{1}{2}}}{c}. $$

Plugging the above equation into g(x) = d, we have

$$u+\frac{1}{c}\left( u^{2}+\text{Tr}_{q^{2n+1}/q}\left( d^{{q^{2}+q}}\right)\right)^{\frac{1}{2}}=0, $$

i.e.,

$$u=\frac{1}{1+c}\left( \text{Tr}_{q^{2n+1}/q}\left( d^{{q^{2}+q}}\right)\right)^{\frac{1}{2}}. $$

Hence, g(x) = d has at most one solution in $\mathbb {F}_{q^{2n+1}}$. It follows that g(x) permutes $\mathbb {F}_{q^{2n+1}}$. Then so f(x) does. The proof is complete. □

3.3 The case l = 2

Theorem 3.6

Let q = 2^k and $f(x)=cx+\text {Tr}_{q^{2}/q}\left (x^{2q-1}\right )\in {\mathbb F}_{q^{2}}[x]$ . Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{2}}$ if one of the following conditions occurs.

• (i) k is even and c = 1,

• (ii) k is odd and c ³ = 1.

Proof

• (i) When k is even and c = 1, f(x) = x + x ^2q−1 + x ^2−q. We refer the proof to Th 3.2 in [9].

• (ii) Now, $f(x)=cx+x^{2q-1}+x^{2q^{2}-q}$. We show that for any $d\in \mathbb {F}_{q^{2}}$, f(x) = d has at most one solution in $\mathbb {F}_{q^{2}}$. Put $u=cx+d=\text {Tr}_{q^{2}/q}\left (x^{2q-1}\right )\in \mathbb {F}_{q}$. Then x = c ²(u + d) since c ³ = 1.

If $d\in \mathbb {F}_{q}$, so does cx, i.e., c ^q x ^q = c x. On the other hand, c ^q = c ² since k is odd and c ³ = 1. Then x ^q = c ² x. Therefore, $x^{2q-1}=\frac {c^{4}x^{2}}{x}=cx\in \mathbb {F}_{q}.$ Moreover, $f(x)=cx+\text {Tr}_{q^{2}/q}(x^{2q-1})=cx=d$. Hence $x=\frac {d}{c}$ is the unique solution of f(x) = d in $\mathbb {F}_{q^{2}}$.

If $d\in \mathbb {F}_{q^{2}} \backslash \mathbb {F}_{q}$, then u + d = 0 is impossible. And $x^{2q-1}=c^{4q-2}(u+d)^{2q-1}=\frac {u^{2}+d^{2q}}{u+d}$ thanks to c ^q = c ². Then plugging the above expressions of x and x ^2q−1 into f(x) = d, we get

$$u+\frac{u^{2}+d^{2q}}{u+d}+\frac{u^{2}+d^{2}}{u+d^{q}}=0, $$

i.e.,

$$ u^{3}+\left( d^{q+1}+d^{2q}+d^{2}\right)u+d^{3q}+d^{3}=0. $$

(3)

Let e = d ^q−1 and $g(x)=x^{2}+x+\frac {e}{e^{2}+1}$. Then it is easy to verify that $e\in \mathbb {F}_{q^{2}} \backslash \mathbb {F}_{q}$ and $g(x)\in \mathbb {F}_{q}[x]$. Considering the equation g(x) = 0, we get

$$g(x)=\left( x+\frac{1}{e+1}\right)\left( x+\frac{e}{e+1}\right)=0. $$

Then $\frac {1}{e+1}, \frac {e}{e+1}$ are the solutions of g(x) = 0 in $\mathbb {F}_{q^{2}}$. Thanks to $\frac {1}{e+1}, \frac {e}{e+1}\not \in \mathbb {F}_{q}$, g(x) = 0 has no solution in $\mathbb {F}_{q}$. Therefore, according to Lemma 2.2,

$$ \text{Tr}_{q}\left( \frac{e}{e^{2}+1}\right)=1. $$

(4)

Let us return to (3): u ³ + a u + b = 0, where a = d ²(e ² + e + 1) and b = d ³(e ³ + 1). Then

$$\begin{array}{@{}rcl@{}} \text{Tr}_{q}\left( \frac{a^{3}}{b^{2}}+1\right)&=&\text{Tr}_{q}\left[\frac{\left( e^{2}+e+1\right)^{3}}{\left( e^{3}+1\right)^{2}}+1\right] \\&=&\text{Tr}_{q}\left( \frac{e^{2}+e+1}{e^{2}+1}+1\right)\\ &=&\text{Tr}_{q}\left( \frac{e}{e^{2}+1}\right)=1. \end{array} $$

Therefore, according to Lemma 2.3, (3) only has one solution in $\mathbb {F}_{q}$. Then f(x) = d has at most one solution in $\mathbb {F}_{q^{2}}$. We finish the proof. □

Theorem 3.7

Let q = 2^k , where k > 0is even. Let $a=\frac {(3q-2)\left (q^{2}+q+1\right )}{3}$ and $f(x)=cx+\text {Tr}_{q^{2}/q}\left (x^{a}\right )\in \mathbb {F}_{q^{2}}[x]$ , where c ³ = 1. Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{2}}$ .

Proof

Let g(x) = f(x ^q−2) = c x ^q−2 + x ^2q−3 + x ^2−3q = x ^q−2 h(x ^q−1), where h(x) = c + x + x ⁻⁴. If g(x) is a permutation polynomial over $\mathbb {F}_{q^{2}}$, then f(x) also permutes $\mathbb {F}_{q^{2}}$ since $\gcd \left (q-2,q^{2}-1\right )=gcd(q-2,3)=1$. From Lemma 2.1, it suffices to show that the fractional polynomial

$$p(x)=x^{q-2}h(x)^{q-1}=\frac{x^{5}+cx+1}{x^{5}+cx^{4}+1} $$

permutes μ _q+1. If c = 1, then $p(x)=\frac {x^{3}+x^{2}+1}{x^{3}+x+1}$, one can refer the proof in [25].

If c ≠ 1, p(x) can not be simplified. However, we can also prove that p(x) permutes μ _q+1. Assume that there exist two distinct elements x ₁,x ₂ ∈ μ _q+1 such that

$$\frac{{x_{1}^{5}}+cx_{1}+1}{{x_{1}^{5}}+c{x_{1}^{4}}+1}=\frac{{x_{2}^{5}}+cx_{2}+1}{{x_{2}^{5}}+c{x_{2}^{4}}+1}. $$

Let u = x ₁ + x ₂ and v = x ₁ x ₂. Simplifying the above equation, we obtain

$$ (1+v)u^{3}+cvu^{2}+v^{4}+cv^{2}+1=0. $$

(5)

Let y = u ⁻¹≠0. The following relationship between u and v will be employed in the sequel. And for convenience, we will use it directly in the following.

$$u^{q}={x_{1}^{q}}+{x_{2}^{q}}=\frac{1}{x_{1}}+\frac{1}{x_{2}}=\frac{x_{1}+x_{2}}{x_{1}x_{2}}=\frac{u}{v}. $$

Then v = u ^1−q = y ^q−1 and u = y ⁻¹. Substituting y ^q−1 and y ⁻¹ for u and v respectively in (5), we have

$$ y^{q}+y+cy^{q+1}+y^{4q}+cy^{2q+2}+y^{4}=0. $$

(6)

Let α = y + y ^q and β = y ^q+1. Then $\alpha ,\beta \in \mathbb {F}_{q}$. Plugging them into the above equation, we get

$$ \alpha+\alpha^{4}+c\beta+c\beta^{2}=0, $$

(7)

i.e.,

$$\beta^{2}+\beta+c^{2}\alpha^{4}+c^{2}\alpha=0. $$

Then β = c α ² + c ² α or c α ² + c ² α + 1. If β = c α ² + c ² α, recalling that u = x ₁ + x ₂ and v = x ₁ x ₂, we know x ₁,x ₂ are the solutions of x ² + u x + v = 0, i.e., (y x)² + y x + y ^q+1 = 0. That is (y x)² + y x + c α ² + c ² α = 0. Without loss of generality, let x ₁ = c ²(1 + y ^q−1) and x ₂ = c ²(1 + y ^q−1) + y ⁻¹. Since x ₂ ∈ μ _q+1, we have

$$x_{2}^{q+1}=\left[c^{2}\left( 1\!+y^{1-q}\right)\,+\,y^{-q}\right]\left[c^{2}\left( 1+y^{q-1}\!+y^{-1}\right)\right]\!=c\left( y^{1-q}+y^{q-1}\right)+y^{-1-q}=1. $$

Hence, y ^q+1 = c(y ² + y ^2q) + 1, i.e., β = c α ² + 1. However, β = c α ² + c ² α. Then c ² α = 1, α = c and β = y = 0. It is a contradiction.

If β = c α ² + c ² α + 1, x ₁ and x ₂ are the solutions of (y x)² + y x + c α ² + c ² α + 1 = 0. Without loss of generality, let x ₁ = c ²(1 + y ^q−1) + c y ⁻¹ and x ₂ = c ²(1 + y ^q−1) + c ² y ⁻¹. Similarly, we can check that it is impossible in the case.

Therefore, p(x) permutes μ _q+1. It follows from Lemma 2.1 that f(x) permutes $\mathbb {F}_{q^{2}}$. We complete the proof. □

Theorem 3.8

Let q = 2^k , where k > 0is odd. Let $a=\frac {(3q^{2}-2)(q+4)}{5}$ and $f(x)=cx+\text {Tr}_{q^{2}/q}(x^{a})\in \mathbb {F}_{q^{2}}[x]$ , where c ³ = 1. Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{2}}$ .

Proof

Let $g(x)=f(x^{5})=cx+\text {Tr}_{q^{2}/q}\left (x^{q+4}\right )$. Then f(x) is a permutation polynomial over $\mathbb {F}_{q^{2}}$ if and only if g(x) permutes $\mathbb {F}_{q^{2}}$ since $\gcd (5,q^{2}-1)=\gcd \left (5,4^{2k+1}-1\right )=\gcd (5,2)=1$. According to Lemma 2.1, it suffices to show that the fractional polynomial

$$p(x)=\frac{c^{2}x^{5}+x^{4}+x}{x^{4}+x+c} $$

permutes μ _q+1. Assume that there exist two distinct elements x ₁,x ₂ ∈ μ _q+1 such that

$$\frac{c^{2}{x_{1}^{5}}+{x_{1}^{4}}+x_{1}}{{x_{1}^{4}}+x_{1}+c}=\frac{c^{2}{x_{2}^{5}}+{x_{2}^{4}}+x_{2}}{{x_{2}^{4}}+x_{2}+c}. $$

Let u = x ₁ + x ₂ and v = x ₁ x ₂. After simplifying the above equation, we get

$$u^{4}+\left( c^{2}v+c\right)u^{3}+vu^{2}+c^{2}v^{4}+v^{2}+c=0. $$

Let y = u ⁻¹. Then u = y ⁻¹ and v = y ^q−1. Plugging them into the above equation, we yield

$$1+c^{2}y^{q}+cy+y^{q+1}+y^{2q+2}+cy^{4}+c^{2}y^{4q}=0. $$

Then

$$\text{Tr}_{q}\left( 1+c^{2}y^{q}+cy+y^{q+1}+y^{2q+2}+cy^{4}+c^{2}y^{4q}\right)=0. $$

However, we also have

$$\begin{array}{@{}rcl@{}} && \text{Tr}_{q}\left( c^{2}y^{q}+cy+y^{q+1}+y^{2q+2}+cy^{4}+c^{2}y^{4q}\right) \\ &&\qquad= \text{Tr}_{q}\left[cy+c^{2}y^{q}+\left( cy+c^{2}y^{q}\right)^{4}+y^{q+1}+y^{2q+2}\right]=0. \end{array} $$

It follows that Tr _q (1) = 0, which contradicts the assumption that k is odd. Hence, p(x) permutes μ _q+1.

Therefore, f(x) is a permutation polynomial over $\mathbb {F}_{q^{2}}$. □

Theorem 3.9

Let q = 2^k , a = 2^2k−2 + 3 ⋅ 2^k−2 , $c\in \mathbb {F}_{q}$ and the equation x ³ + x + c = 0has no solution in $\mathbb {F}_{q}$ . Then $f(x)=cx+\text {Tr}_{q^{2}/q}\left (x^{a}\right )$ is a permutation polynomial over $\mathbb {F}_{q^{2}}$ .

Proof

Let $g(x)=f(x^{4})=cx^{4}+\text {Tr}_{q^{2}/q}\left (x^{3q+1}\right )=cx^{4}+x^{3q+1}+x^{3+q}=x^{4}\left (c+\right .$ x ^3q−3 + x ^q−1) = x ⁴ h(x ^q−1), where h(x) = c + x + x ³. Because of $\gcd \left (4,q^{2}-1\right )=1$, it suffices to show that g(x) permutes $\mathbb {F}_{q^{2}}$. In the following, we will prove that

$$p(x)=x^{4}h(x)^{q-1}=\frac{cx^{4}+x^{3}+x}{x^{3}+x+c} $$

permutes μ _q+1.

If the assertion would not hold, then there exist two distinct elements x ₁,x ₂ ∈ μ _q+1 such that p(x ₁) = p(x ₂). We have

$$\frac{c{x_{1}^{4}}+{x_{1}^{3}}+x_{1}}{{x_{1}^{3}}+x_{1}+c}=\frac{c{x_{2}^{4}}+{x_{2}^{3}}+x_{2}}{{x_{2}^{3}}+x_{2}+c}. $$

Let u = x ₁ + x ₂ and v = x ₁ x ₂. After simplifying the above equation and substituting u and v for x ₁ + x ₂ and x ₁ x ₂ respectively, we obtain

$$ cu^{3}+(v+1)u^{2}+v^{3}+v^{2}+v+1=0. $$

(8)

Let y = u ⁻¹. Then u = y ⁻¹, v = y ^q−1 and we have

$$c+y^{q}+y+y^{3q}+y^{2q+1}+y^{q+2}+y^{3}=0, $$

i.e.,

$$\alpha^{3}+\alpha+c=0, $$

where $\alpha =y+y^{q}\in \mathbb {F}_{q}$. This leads to a contradiction thanks to our assumption on c.

Thus we conclude that f(x) is a permutation polynomial over $\mathbb {F}_{q^{2}}$ according to Lemma 2.1. □

Theorem 3.10

Let q = 2^k and $f(x)=x+\text {Tr}_{q^{2}/q}(x^{a})$ , where

$$a=\left\{\begin{array}{lll} \frac{(2q^{2}-1)(q+6)}{7}, & \text{if}\quad k\equiv1 \pmod 3;\\ -\frac{(q^{2}-2)(q+6)}{7}, & \text{if}\quad k\equiv2 \pmod 3. \end{array}\right. $$

Then f(x)is a permutationpolynomial over $\mathbb {F}_{q^{2}}$.

Proof

Put g(x) = f(x ⁷) = x ⁷ + x ^6q+1 + x ^q+6 = x ⁷ h(x ^q−1),where h(x) = 1 + x + x ⁶. We show that

$$p(x)=x^{7}h(x)^{q-1}=\frac{x^{7}+x^{6}+x}{x^{6}+x+1} $$

permutes μ _q+1 when k≢0 (mod 3). If there exist two distinct elements x ₁,x ₂ ∈ μ _q+1 such that

$$\frac{{x_{1}^{7}}+{x_{1}^{6}}+x_{1}}{{x_{1}^{6}}+x_{1}+1}=\frac{{x_{2}^{7}}+{x_{2}^{6}}+x_{2}}{{x_{2}^{6}}+x_{2}+1}. $$

Let u = x ₁ + x ₂ and v = x ₁ x ₂. We get

$$u^{6}+(1+v)u^{5}+vu^{4}+(v^{3}+v^{2})u+v^{6}+v^{3}+1=0. $$

Denote y = u ⁻¹. Then u = y ⁻¹ and v = y ^q−1. Let α = y + y ^q and β = y ^{1 + q}. Then we have

$$ \beta^{3}+(\alpha^{2}+\alpha)\beta^{2}+\beta+\alpha^{6}+\alpha+1=0. $$

(9)

Let γ = β + α ² + α. Then we get

$$ \gamma^{3}+a\gamma+b=0, $$

(10)

where

$$\begin{array}{@{}rcl@{}} a &=& \alpha^{4}+\alpha^{2}+1,\\ b &=& \alpha^{6}+\alpha^{2}+1. \end{array} $$

Now we compute the number of the solution of (10).

Since

$$\begin{array}{@{}rcl@{}} \frac{a^{3}}{b^{2}}&=&\frac{\left( \alpha^{4}+\alpha^{2}+1\right)^{3}}{\left( \alpha^{6}+\alpha^{2}+1\right)^{2}} \\&=& 1+\frac{\alpha^{10}+\alpha^{6}+\alpha^{4}+\alpha^{2}}{\alpha^{12}+\alpha^{4}+1}\\ &=& 1+\frac{\alpha^{4}}{\alpha^{6}+\alpha^{2}+1}+\frac{\alpha^{8}}{\alpha^{12}+\alpha^{4}+1}+\frac{\alpha^{2}}{\alpha^{6}+\alpha^{2}+1}+\frac{\alpha^{4}}{\alpha^{12}+\alpha^{4}+1}\\ &=&\left( w+\frac{\alpha^{4}+\alpha^{2}}{\alpha^{6}+\alpha^{2}+1}\right)+\left( w+\frac{\alpha^{4}+\alpha^{2}}{\alpha^{6}+\alpha^{2}+1}\right)^{2}, \end{array} $$

where w ³ = 1 and w ≠ 1, $\text {Tr}_{q}\left (\frac {a^{3}}{b^{2}}+1\right )=0$. According to Lemma 2.3, (10) has no solution or three solutions in $\mathbb {F}_{q}$. In the following, we claim that (10) has one solution which is not in $\mathbb {F}_{q}$. Then it follows that (10) has no solution in $\mathbb {F}_{q}$.

The quadratic derived equation of (10) is

$$ t^{2}+bt+a^{3}=0. $$

(11)

Let t = b z. Plugging it into the above equation, we get

$$z^{2}+z+\frac{a^{3}}{b^{2}}=z^{2}+z+\left( w+\frac{\alpha^{4}+\alpha^{2}}{\alpha^{6}+\alpha^{2}+1}\right)+\left( w+\frac{\alpha^{4}+\alpha^{2}}{\alpha^{6}+\alpha^{2}+1}\right)^{2}=0. $$

Then $z=w+\frac {\alpha ^{4}+\alpha ^{2}}{\alpha ^{6}+\alpha ^{2}+1}$ and t = b z = (α ⁶ + α ² + 1)w + α ⁴ + α ² = w(w α ² + 1)³. Thus 𝜖 ³ = t has the solution 𝜖 = σ(w α ² + 1), where σ ³ = w, i.e., σ ⁹ = 1 and σ ³≠1. Therefore,

$$\begin{array}{@{}rcl@{}} \epsilon+\frac{\alpha^{4}+\alpha^{2}+1}{\epsilon} &=&\sigma(w\alpha^{2}+1)+\sigma^{8}(w^{2}\alpha^{2}+1) \\&=&(\sigma^{4}+\sigma^{5})\alpha^{2}+\sigma+\sigma^{8}\\ &=& e^{4}\alpha^{2}+e, \end{array} $$

where $e=\sigma +\frac {1}{\sigma }$, is one solution of (10). Next we show that $e^{4}\alpha ^{2}+e\not \in \mathbb {F}_{q}$. The following of the proof is split into two cases.

C a s e I: k ≡ 1 (mod 3).

Let k = 3l + 1. Since $\sigma ^{q}=(\sigma ^{8^{l}})^{2}=\sigma ^{\pm 2}$, $e^{q}=\sigma ^{2}+\frac {1}{\sigma ^{2}}=e^{2}$. Then (e ⁴ α ² + e)^q = e ⁸ α ² + e ². If $e^{4}\alpha ^{2}+e\in \mathbb {F}_{q}$, then e ⁴ α ² + e = e ⁸ α ² + e ². Therefore, we get

$$\alpha^{2}=\frac{e^{2}+e}{e^{8}+e^{4}}.$$

It follows from $\alpha ^{2}\in \mathbb {F}_{q}$ that

$$\alpha^{2q}=\frac{e^{4}+e^{2}}{e^{16}+e^{8}}=\frac{e^{2}+e}{e^{8}+e^{4}},$$

i.e., α ⁴ = α ², α = 1. Then according to (9), we have β ³ + β + 1 = 0. So $\beta \in \mathbb {F}_{2^{3}}\cap \mathbb {F}_{q}=\mathbb {F}_{2}$, i.e., β = 1. Moreover, we have y ² + y + 1 = 0, y ³ = 1 since y + y ^q = 1 and y ^q+1 = 1. Due to $y\not \in \mathbb {F}_{q}$ and y ³ = 1, k is odd. So v = y ^q−1 = y. On the other hand, $x_{1},x_{2}\in \mathbb {F}_{q^{2}}$ is the solutions of x ² + u x + v = 0, i.e., x ² + y ⁻¹ x + y = 0. According to Lemma 2.2 and $\text {Tr}_{q}\left (\frac {v}{u^{2}}\right )=\text {Tr}_{q}\left (y^{3}\right )=\text {Tr}_{q}(1)=1$, we know that the equation x ² + u x + v = 0 has no solution in $\mathbb {F}_{q^{2}}$. It is impossible. Hence, in the case, $e^{4}\alpha ^{2}+e\not \in \mathbb {F}_{q}$.

C a s e I I: k ≡ 2 (mod 3).

This case can be proved similarly as C a s e I. We omit it here.

Hence (10) has a solution which is not in $\mathbb {F}_{q}$. It follows that p(x) permutes μ _q+1 when k≢0 (mod 3). Moreover, g(x) permutes $\mathbb {F}_{q^{2}}$ according to Lemma 2.1, so does f(x) since $\gcd (7,q^{2}-1)=1$ when k≢0 (mod 3). □

Theorem 3.11

Let q = 2^k , where k is odd. Let $a=\frac {2^{2k-1}+3\cdot 2^{k-1}+1}{3}$ and $f(x)=cx+\text {Tr}_{q^{2}/q}\left (x^{a}\right )\in \mathbb {F}_{q^{2}}[x],$ where $c^{\frac {q+1}{3}}=1$ . Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{2}}$ .

Proof

Let $h(x)=c+x^{\frac {2^{k-1}+2}{3}}+x^{\frac {1-2^{k-1}}{3}}$. Then $f(x)=cx+x^{\frac {2^{k-1}+2}{3}(2^{k}-1)+1}+x^{\frac {1-2^{k-1}}{3}(2^{k}-1)+1}=xh(x^{q-1})$. Let p(x) = x h(x)^q−1. Then for x ∈ μ _q+1,we have

$$p(x)=x\frac{c^{-1}+x^{-\frac{2^{k-1}+2}{3}}+x^{\frac{2^{k-1}-1}{3}}}{c+x^{\frac{2^{k-1}+2}{3}}+x^{\frac{1-2^{k-1}}{3}}}= \frac{c^{-1}x^{\frac{2^{k-1}+2}{3}}+x^{\frac{2^{k}+1}{3}}+1}{cx^{\frac{2^{k-1}-1}{3}}+x^{\frac{2^{k}+1}{3}}+1}. $$

Let p ₁(x) = p(x)². In the following, we show that p ₁(x) permutes μ _q+1. Then according to Lemma 2.1 and $\gcd (2,q+1)=1$, we can conclude that f(x) permutes $\mathbb {F}_{q^{2}}$.

Let $y=x^{\frac {2^{k}+1}{3}}$. Obviously, y ³ = 1. And we have

$$p_{1}(x)=\frac{yx^{2}+c^{2}\left( y^{2}+1\right)x}{c^{4}y+c^{2}\left( y^{2}+1\right)x}.$$

Let S ₁ = {x : x ∈ μ _q+1,y = 1} and S ₂ = {x : x ∈ μ _q+1,y ≠ 1}. Assume there exist two distinct elements x ₁,x ₂ ∈ μ _q+1 such that p ₁(x ₁) = p ₁(x ₂). The following proof is divided into four cases.

C a s e I: x ₁,x ₂ ∈ S ₁.

Then $p_{1}(x_{1})=\frac {1}{c^{4}}{x_{1}^{2}}$ and $p_{1}(x_{2})=\frac {1}{c^{4}}{x_{2}^{2}}$. It is clear that we can conclude x ₁ = x ₂ from p ₁(x ₁) = p ₁(x ₂), a contradiction.

C a s e I I: x ₁,x ₂ ∈ S ₂.

Then $p_{1}(x_{1})=\frac {1}{c^{2}}x_{1}$ and $p_{1}(x_{2})=\frac {1}{c^{2}}x_{2}$. We have x ₁ = x ₂ from p ₁(x ₁) = p ₁(x ₂), which is also impossible.

C a s e I I I: x ₁ ∈ S ₁ and x ₂ ∈ S ₂.

Then $p_{1}(x_{1})=\frac {1}{c^{4}}{x_{1}^{2}}$ and $p_{1}(x_{2})=\frac {1}{c^{2}}x_{2}$. So $x_{2}=\frac {1}{c^{2}}{x_{1}^{2}}$. But $x_{2}^{\frac {q+1}{3}}=\left (\frac {1}{c^{2}}{x_{1}^{2}}\right )^{\frac {q+1}{3}}=1$, which is a contradiction with x ₂ ∈ S ₂.

C a s e I V: x ₁ ∈ S ₂ and x ₂ ∈ S ₁.

This case is similar as Case III.

Hence, p ₁(x) permutes μ _q+1. Moreover, f(x) permutes $\mathbb {F}_{q^{2}}$. □

Theorem 3.12

Let q = 2^k and k be even. Then $f(x)=x+\text {Tr}_{q^{2}/q}\left (x^{\frac {q^{2}-2q+4}{3}}\right )$ is a permutation polynomial over $\mathbb {F}_{q^{2}}$ .

Proof

Let $h(x)=1+x^{\frac {q-1}{3}}+x^{\frac {4-q}{3}}$. Then $f(x)=x+x^{\frac {q-1}{3}(q-1)+1}+x^{\frac {4-q}{3}(q-1)+1}=xh(x^{q-1})$. According to Lemma 2.1, it suffices to show that

$$p(x)=xh(x)^{q-1}=x\frac{1+x^{\frac{1-q}{3}}+x^{\frac{q-4}{3}}}{1+x^{\frac{q-1}{3}}+x^{\frac{4-q}{3}}}$$

permutes μ _q+1. Let p ₁(x) = p(x ³). Since $\gcd (3,q+1)=1$, we only need to consider p ₁(x) whether permutes μ _q+1. A direct computation leads to

$$p_{1}(x)=\frac{x^{5}+x^{4}+x^{3}+x+1}{x^{5}+x^{4}+x^{2}+x+1}.$$

Assume there exist two distinct elements x ₁,x ₂ ∈ μ _q+1 such that p ₁(x ₁) = p ₁(x ₂). Let u = x ₁ + x ₂ and v = x ₁ x ₂. After a lengthy but direct computation, we get

$$\left( v^{2}+1\right)u^{2}+\left( v+1\right)^{3}u+v^{2}=0. $$

Obviously, we have v ≠ 1 from the above equation. Multiplying both sides of $\frac {1}{v^{4}+1}$ yields

$$ \left( \frac{u}{v+1}\right)^{2}+\frac{u}{v+1}+\frac{1}{v^{2}+1}+\frac{1}{v^{4}+1}=0. $$

(12)

Then $u=\frac {1}{v+1}$ or $u=\frac {1}{v+1}+v+1$. If $u=\frac {1}{v+1}$, then $u^{q}=\frac {1}{v^{q}+1}=\frac {v}{v+1}$. However, $u^{q}={x_{1}^{q}}+{x_{2}^{q}}=\frac {1}{x_{1}}+\frac {1}{x_{2}}=\frac {u}{v}$. So $\frac {v}{v+1}=\frac {u}{v}=\frac {1}{v^{2}+v}$, i.e., v ² = 1, a contradiction. If $u=\frac {1}{v+1}+v+1$, we can also obtain v ² = 1, which is impossible. Thus p ₁(x) permutes μ _q+1.

Hence, f(x) is a permutation polynomial over $\mathbb {F}_{q^{2}}$. The proof is complete. □

The following theorem is proved by the multivariate method.

Theorem 3.13

Let q = 2^k , a = 2^4k−1 − 2^3k−1 + 2^2k−1 + 2^k−1 and $c\in \mathbb {F}_{q}^{*}$ . Then $f(x)=cx+\text {Tr}_{q^{4}/q^{2}}\left (x^{a}\right )$ is a permutation polynomial over $\mathbb {F}_{q^{4}}$ .

Proof

Let $g(x)=f(x^{2})=cx^{2}+\text {Tr}_{q^{4}/q^{2}}\left (x^{2a}\right )=cx^{2}+x^{q^{4}-q^{3}+q^{2}+q}+x^{q^{3}+q^{2}-q+1}$. It suffices to show that g(x) permutes $\mathbb {F}_{q^{4}}$.

First of all, we claim that g(x) = 0 only has zero solution in $\mathbb {F}_{q^{4}}$. If g(x) = 0, then either x = 0 or $c+x^{-q^{3}+q^{2}+q-1}+x^{q^{3}+q^{2}-q-1}=0$. So we only need to prove the equation

$$ c+x^{-q^{3}+q^{2}+q-1}+x^{q^{3}+q^{2}-q-1}=0 $$

(13)

has no solution in $\mathbb {F}_{q^{4}}^{*}$. Raising (13) to its q-th power leads to

$$ c+x^{q^{3}+q^{2}-q-1}+x^{q^{3}-q^{2}-q+1}=0. $$

(14)

Adding (13) and (14), we have

$$x^{-q^{3}+q^{2}+q-1}=x^{q^{3}-q^{2}-q+1},$$

i.e.,

$$x^{q^{3}-q^{2}-q+1}=1.$$

Since $\gcd \left (q^{3}-q^{2}-q+1,q^{4}-1\right )=q^{2}-1$, we have $x\in \mathbb {F}_{q^{2}}$. Plugging it into (13), we get c = 0, which is contradiction. Thus g(x) = 0 only has zero solution in $\mathbb {F}_{q^{4}}$.

Next, we show that g(x) = α has at most one solution in $\mathbb {F}_{q^{4}}$ for any $\alpha \in \mathbb {F}_{q^{4}}^{*}$. Obviously, x = 0 is not a solution of g(x) = α if α ≠ 0. Let y = x ^q, z = y ^q, w = z ^q, β = α ^q, γ = β ^q and δ = γ ^q. Then x,y,z,w,α,β,γ,δ ≠ 0, and we have

$$ cx^{2}+\frac{xyz}{w}+\frac{xzw}{y}=\alpha. $$

(15)

Raising (15) into its q-th, q ²-th and q ³-th power, we get the following equations respectively.

$$ cy^{2}+\frac{yzw}{x}+\frac{xyw}{z}=\beta, $$

(16)

$$ cz^{2}+\frac{xzw}{y}+\frac{xyz}{w}=\gamma $$

(17)

and

$$ cw^{2}+\frac{xyw}{z}+\frac{yzw}{x}=\delta. $$

(18)

We compute the sum of (15) and (17), and get z = x + B, where $B=\left (\frac {\alpha +\gamma }{c}\right )^{\frac {1}{2}}$. Likely, we have w = y + A, where $A=\left (\frac {\beta +\delta }{c}\right )^{\frac {1}{2}}$ through adding (16) and (18). Plugging z = x + B and w = y + A into (15) and (16) and then simplifying, we obtain

$$ \left( \alpha+cx^{2}\right)y^{2}+\left( \alpha A+cAx^{2}\right)y+BA^{2}x+A^{2}x^{2}=0 $$

(19)

and

$$ \left( B^{2}+Bcx+cx^{2}\right)y^{2}+B^{2}Ay+\beta x(B+x)=0. $$

(20)

Computing (19) ∗ B ² + (20) ∗(α + c x ²), we yield

$$ D_{1}y^{2}=D_{0}, $$

(21)

where

$$D_{1}=c\left( \alpha+cx^{2}\right)$$

and

$$D_{0}=B^{2}A^{2}+\alpha\beta+\beta c x^{2}.$$

We compute (19) ∗ c + (21), we get

$$ D_{3}y=D_{2}, $$

(22)

where

$$D_{3}=cA\left( \alpha+cx^{2}\right)$$

and

$$D_{2}=B^{2}A^{2}+\alpha\beta+cBA^{2}x+cA^{2}x^{2}+\beta cx^{2}.$$

If α + c x ² = 0, then $x=\left (\frac {\alpha }{c}\right )^{\frac {1}{2}}$. Then g(x) = α has at most one solution in $\mathbb {F}_{q^{4}}$. Otherwise, computing (22) ²/ (21) and simplifying it, we obtain

$$D_{5}x^{4}=D_{4},$$

where

$$D_{5}=\beta A^{2}c^{3}+c^{2}A^{4}+\beta^{2}c^{2}$$

and

$$D_{4}=B^{4}A^{4}+\alpha^{2}\beta^{2}+\alpha^{2}\beta A^{2}c+\alpha B^{2}A^{4}c.$$

We claim that D ₅≠0 when β ≠ 0. If D ₅ = 0, then we have

$$ \beta^{2}+\delta^{2}+c^{2}\beta\delta=0. $$

(23)

Let $t=\frac {\delta }{\beta }$. Then $c^{2}=t+\frac {1}{t}\in \mathbb {F}_{q}$. Thus $\left (t+\frac {1}{t}\right )^{q}=t+\frac {1}{t}$, i.e., (t ^q+1 + 1)(t ^q−1 + 1) = 0. Therefore, t ^q+1 = 1 or t ^q−1 = 1. In the first case, $\beta ^{\left (q^{2}-1\right )(q-1)}=1$. Due to $\gcd \left (q^{4}-1,\left (q^{2}-1\right )(q-1)\right )=q^{2}-1$, $\beta \in \mathbb {F}_{q^{2}}$. Then δ = β. Moreover, it follows that c = 0 from (23), which is a contradiction. The other case is the same as the first one, we omit it here.

Above all, $x^{4}=\frac {D_{4}}{D_{5}}$. Thus, g(x) = α has at most one solution in $\mathbb {F}_{q^{4}}$. We finish the proof. □

4 Permutation trinomials

In this section, we construct four classes of permutation trinomials over finite fields with even characteristic.

Theorem 4.1

Let q = 2^k , k ≥ 1,l be integers and f(x) = x ^{lq + l+3} + x ^{(l+6)q + l−3} + x ^{(l−2)q + l+5} . Then f(x)is a permutation trinomial over $\mathbb {F}_{q^{2}}$ if $\gcd (3+2l, q-1)=1$ and k≢0 (mod 4).

Proof

Let h(x) = 1 + x ⁶ + x ⁻². Then f(x) = x ^{lq + l+3} h(x ^q−1). According to Lemma 2.1, f(x) permutes $\mathbb {F}_{q^{2}}$ if and only if $\gcd (lq+l+3,q-1)=1,$i.e., $\gcd (3+2l, q-1)=1$ and

$$p(x)=x^{3+lq+l}h(x)^{q-1}=\frac{x^{8}+x^{6}+1}{x^{9}+x^{3}+x}$$

permutes μ _q+1. Assume that there exist two distinct elements x ₁,x ₂ ∈ μ _q+1 such that

$$\frac{{x_{1}^{8}}+{x_{1}^{6}}+1}{{x_{1}^{9}}+{x_{1}^{3}}+x_{1}}=\frac{{x_{2}^{8}}+{x_{2}^{6}}+1}{{x_{2}^{9}}+{x_{2}^{3}}+x_{2}}.$$

After a complex computation and substituting u and v for x ₁ + x ₂ and x ₁ x ₂ respectively, we get

$$ u^{8}+(v^{3}+v)u^{4}+(v^{6}+v^{4}+v^{3}+v^{2}+1)u^{2}+v^{8}+v^{7}+v^{5}+v^{4}+v^{3}+v+1=0. $$

(24)

Let y = u ⁻¹. Then u = y ⁻¹ and v = y ^q−1. Plugging them into (24), we obtain

$$ \beta^{4}+\beta^{3}+(\alpha^{6}+\alpha^{2})\beta+\alpha^{8}+\alpha^{6}+1=0, $$

(25)

where

$$\begin{array}{@{}rcl@{}} \beta &=& y^{q+1},\\ \alpha &=& y+y^{q}. \end{array} $$

Let $g(x)=x^{4}+x^{3}+(\alpha ^{6}+\alpha ^{2})x+\alpha ^{8}+\alpha ^{6}+1\in \mathbb {F}_{q}[x]$. In the following, we prove that g(x) has no root in $\mathbb {F}_{q}$ when k≢0 (mod 4). The rest of the proof is split into two cases.

Case I: k is odd.

We show that g(x) is an irreducible polynomial. Let $g_{1}(x)=x^{4}g\left (\frac {1}{x}+\alpha ^{3}+\alpha \right )$. Then we can compute

$$g_{1}(x)=a_{1}x^{4}+a_{2}x^{2}+x+1,$$

where

$$\begin{array}{@{}rcl@{}} a_{1} &=& \alpha^{12}+\alpha^{8}+\alpha^{6}+\alpha^{4}+1,\\ a_{2} &=& \alpha^{3}+\alpha. \end{array} $$

We claim that a ₁≠0 for any $\alpha \in \mathbb {F}_{q}$. Otherwise, there exists $\alpha \in \mathbb {F}_{q}$ such that a ₁ = 0. Then

$$\alpha^{6}+\alpha^{4}+\alpha^{3}+\alpha^{2}+1=0, $$

i.e.,

$$\left( \alpha^{4}+\alpha^{3}+\alpha^{2}+\alpha+1\right)\left( \alpha^{2}+\alpha+1\right)=0. $$

Thus, α ⁴ + α ³ + α ² + α + 1 = 0 or α ² + α + 1 = 0. In the first case, let α ₁ = α + 1. Then ${\alpha _{1}^{4}}+{\alpha _{1}^{3}}=1$. Moreover, we have

$$ \left( \frac{1}{\alpha_{1}}\right)^{4}+\frac{1}{\alpha_{1}}=1. $$

(26)

Raising the above equation to its 4-th power, we obtain

$$ \left( \frac{1}{\alpha_{1}}\right)^{16}+\left( \frac{1}{\alpha_{1}}\right)^{4}=1. $$

(27)

Computing (26) + (27) , we get $\left (\frac {1}{\alpha _{1}}\right )^{15}=1$. Then thanks to $\gcd (15,q-1)=1$ when k is odd, we get α ₁ = 1. However α ₁ = 1 is not the solution of (26). Therefore, α ⁴ + α ³ + α ² + α + 1≠0. In the other case, let $t(\alpha )=\alpha ^{2}+\alpha +1\in \mathbb {F}_{q}[\alpha ]$. Obviously, t(α) is irreducible in $\mathbb {F}_{2}[\alpha ]$. Thanks to $\gcd (2,k)=1$, t(α) is also irreducible in $\mathbb {F}_{q}[\alpha ]$. So, α ² + α + 1≠0 for any $\alpha \in \mathbb {F}_{q}$. Hence, a ₁≠0.

Next we let $g_{2}(x)=\frac {1}{a_{1}}g_{1}(x)=x^{4}+\frac {a_{2}}{a_{1}}x^{2}+\frac {1}{a_{1}}x+\frac {1}{a_{1}}\in \mathbb {F}_{q}[x]$. Then it suffices to show that g ₂(x) is irreducible in $\mathbb {F}_{q}[x]$. Let us consider the cubic equation

$$ y^{3}+\frac{a_{2}}{a_{1}}y+\frac{1}{a_{1}}=0. $$

(28)

Then the quadratic derived equation of (28) is

$$ t^{2}+\frac{1}{a_{1}}t+\left( \frac{a_{2}}{a_{1}}\right)^{3}=0. $$

(29)

Let $t=\frac {1}{a_{1}}z$. Then $z^{2}+z+\frac {{a_{2}^{3}}}{a_{1}}=0$. In fact,

$$\begin{array}{@{}rcl@{}} \frac{{a_{2}^{3}}}{a_{1}} &=& \frac{\left( \alpha^{3}+\alpha\right)^{3}}{\alpha^{12}+\alpha^{8}+\alpha^{6}+\alpha^{4}+1} \\&=& \frac{\alpha^{9}+\alpha^{7}+\alpha^{5}+\alpha^{3}}{\alpha^{12}+\alpha^{8}+\alpha^{6}+\alpha^{4}+1}\\ &=& \frac{\alpha^{3}}{\alpha^{6}+\alpha^{4}+\alpha^{3}+\alpha^{2}+1}+\left( \frac{\alpha^{3}}{\alpha^{6}+\alpha^{4}+\alpha^{3}+\alpha^{2}+1}\right)^{2}. \end{array} $$

On one hand, for (28), we have $\text {Tr}_{q}\left (\frac {(a_{2}/a_{1})^{3}}{(1/a_{1})^{2}}+1\right )=\text {Tr}_{q}\left (\frac {{a_{2}^{3}}}{a_{1}}+1\right )=1$. According to Lemma 2.3, (28) only has one solution in $\mathbb {F}_{q}$. On the other hand, for (29),

$$\begin{array}{@{}rcl@{}} t_{1}&=&\frac{1}{\alpha^{12}+\alpha^{8}+\alpha^{6}+\alpha^{4}+1}\cdot\left( \frac{\alpha^{3}}{\alpha^{6}+\alpha^{4}+\alpha^{3}+\alpha^{2}+1}\right)\\ &=& \left( \frac{\alpha}{\alpha^{6}+\alpha^{4}+\alpha^{3}+\alpha^{2}+1}\right)^{3}, \end{array} $$

is one solution of (29). Let $\epsilon =\frac {\alpha }{\alpha ^{6}+\alpha ^{4}+\alpha ^{3}+\alpha ^{2}+1}$ be a solution of x ³ = t ₁. Then

$$r=\epsilon+\frac{a_{2}}{a_{1}\epsilon}=\frac{1}{\alpha^{4}+\alpha^{3}+\alpha^{2}+\alpha+1}$$

is the unique solution of (28) in $\mathbb {F}_{q}$. In the following, we compute

$$\begin{array}{@{}rcl@{}} \text{Tr}_{q}\left( a_{1}r^{2}\right) &=& \text{Tr}_{q}\left[{\left( \alpha^{12}+\alpha^{8}+\alpha^{6}+\alpha^{4}+1\right)\left( \frac{1}{\alpha^{4}+\alpha^{3}+\alpha^{2}+\alpha+1}\right)^{2}}\right]\\ &=& \text{Tr}_{q}\left( \alpha^{4}+\alpha^{2}+1\right)\\ &=& 1. \end{array} $$

According to Lemma 2.5, in the Case k is odd, g(x) is irreducible in $\mathbb {F}_{q}[x]$. Particularly, g(x) has no roots in $\mathbb {F}_{q}$.

Case II: k ≡ 2 (mod 4).

Assume that ω satisfies ω ² + ω = 1. Then g(x) = G ₁(x)G ₂(x), where

$$\begin{array}{@{}rcl@{}} G_{1}(x) &=& x^{2}+(\alpha+\omega)x+\omega^{2}\alpha^{2}+\omega\alpha+\omega,\\ G_{2}(x) &=& x^{2}+(\alpha+\omega^{2})x+\omega\alpha^{2}+\omega^{2}\alpha+\omega^{2}. \end{array} $$

We have

$$\begin{array}{@{}rcl@{}} \text{Tr}_{q}\left( \frac{\omega^{2}\alpha^{2}+\omega\alpha+\omega}{\alpha^{2}+\omega^{2}}\right)&=&\text{Tr}_{q}\left( \frac{\omega\alpha}{\alpha^{2}+\omega^{2}}+\omega^{2}\right)\\ &=&\text{Tr}_{q}\left( \frac{\omega\alpha}{\alpha^{2}+\omega^{2}}\right)+1\\ &=&\text{Tr}_{q}\left( \frac{\omega}{\alpha+\omega}+\frac{\omega^{2}}{\alpha^{2}+\omega^{2}}\right)+1\\ & =& 1, \end{array} $$

since

$$\begin{array}{@{}rcl@{}} \text{Tr}_{q}(\omega)&=&\underbrace{\omega+\omega^{2}+\cdots+\omega+\omega^{2}}_{k} =\underbrace{1+\cdots+1}_{\frac{k}{2}} =\frac{k}{2}=1 \end{array} $$

when k ≡ 2 (mod 4). Hence G ₁(x) has no roots in $\mathbb {F}_{q}$ according to Lemma 2.2. Similarly, we claim that G ₂(x) = 0 has no solution in $\mathbb {F}_{q}$. Thus g(x) = G ₁(x)G ₂(x) has no roots in $\mathbb {F}_{q}$.

Therefore, g(x) has no roots in $\mathbb {F}_{q}$ when k≢0 (mod 4). Moreover, (25) can not hold. Then p(x) permutes μ _q+1. We complete the proof. □

Theorem 4.2

Let q = 2^k , where k is odd, and $f(x)=x+x^{\frac {q^{2}-3q+5}{3}}+x^{\frac {2q^{2}-3q+4}{3}}$ . Then f(x)is a permutation trinomial over $\mathbb {F}_{q^{2}}$ .

Proof

Let $f(x)=x\left (1+x^{\frac {q-2}{3}(q-1)}+x^{\frac {2q-1}{3}(q-1)}\right )=xh\left (x^{q-1}\right )$, where $h(x)=1+x^{\frac {q-2}{3}}+x^{\frac {2q-1}{3}}$. Put p(x) = x h(x)^q−1 ∈ μ _q+1[x] and $y=x^{\frac {q+1}{3}}$. Obviously, y ³ = 1. Then for x ∈ μ _q+1,we have

$$\begin{array}{@{}rcl@{}} p(x) = x\frac{1+x^{\frac{2-q}{3}}+x^{\frac{1-2q}{3}}}{1+x^{\frac{q-2}{3}}+x^{\frac{2q-1}{3}}} = x^{2}\frac{\left( y^{2}+y\right)x+1}{y^{2}+y+x}, \end{array} $$

Let S ₁ = {x|x ∈ μ _q+1,y = 1} and S ₂ = {x|x ∈ μ _q+1,y ≠ 1}. We claim that p(x) permutes μ _q+1. Otherwise, there exist two distinct elements x ₁,x ₂ ∈ μ _q+1 such that p(x ₁) = p(x ₂). The following proof is divided into four cases.

C a s e I: x ₁,x ₂ ∈ S ₁.

Then p(x ₁) = x ₁ and p(x ₂) = x ₂. So x ₁ = x ₂ from p(x ₁) = p(x ₂).

C a s e I I: x ₁,x ₂ ∈ S ₂.

Then $p(x_{1})={x_{1}^{2}}$ and $p(x_{2})={x_{2}^{2}}$. We have x ₁ = x ₂ from p(x ₁) = p(x ₂).

C a s e I I I: x ₁ ∈ S ₁ and x ₂ ∈ S ₂.

Then p(x ₁) = x ₁ and $p(x_{2})={x_{2}^{2}}$. So $x_{1}={x_{2}^{2}}$. But $x_{1}^{\frac {q+1}{3}}=\left ({x_{2}^{2}}\right )^{\frac {q+1}{3}}\neq 1$, which is a contradiction with x ₁ ∈ S ₁.

C a s e I V: x ₁ ∈ S ₂ and x ₂ ∈ S ₁.

This case is similar as Case III.

Hence, p(x) permutes μ _q+1. Moreover, f(x) permutes $\mathbb {F}_{q^{2}}$ according to Lemma 2.1. □

Theorem 4.3

Let q = 2^k and k≢1 (mod 3). Then $f(x)=x+x^{q^{2}+q-1}+x^{q^{3}-q^{2}+q}$ is a permutation polynomial over $\mathbb {F}_{q^{3}}$ .

Proof

First, we show that f(x) = 0 only has zero solution in $\mathbb {F}_{q^{3}}$. If f(x) = 0, then either x = 0 or $1+x^{q-q^{2}}+x^{q^{2}+q-2}=0$. Thus, we only need to prove that the equation

$$ 1+x^{q-q^{2}}+x^{q^{2}+q-2}=0 $$

(30)

has no solution in $\mathbb {F}_{q^{3}}^{*}$. Let t = x ^q−1≠0. Then $t^{q^{2}+q+1}=1$, and (30) turns to

$$1+t^{-q}+t^{q+2}=0, $$

i.e.,

$$ 1+t^{q}+t^{2q+2}=0. $$

(31)

Raising (31) to its q-th power, we get

$$1+t^{q^{2}}+t^{2q^{2}+2q}=0. $$

Plugging $t^{q^{2}+q+1}=1$ into the above equation leads to

$$ t+t^{q}+t^{q+2}=0. $$

(32)

Computing (31) + (32), we get (1 + t ^q+1)(1 + t + t ^q+1) = 0. Then either t ^q+1 + 1 = 0 or t ^q+1 + t + 1 = 0.

If t ^q+1 = 1, then t = 1 since $\gcd \left (q+1,q^{2}+q+1\right )=\gcd \left (q+1,q^{2}\right )=1$. However, t = 1 is not the solution of (31). Therefore,

$$ 1+t+t^{q+1}=0. $$

(33)

Computing (31) + (33) ², we yield t ^q−2 = 1, then $t^{\gcd \left (q-2,q^{2}+q+1\right )}=1.$ Moreover, t = 1 thanks to $\gcd \left (q-2,q^{2}+q+1\right )=\gcd (2^{k-1}-1,7)=1$ when k≢1 (mod 3). However, it is impossible!

Therefore, f(x) = 0 only has zero solution in $\mathbb {F}_{q^{3}}$.

Next, we prove f(x) = a has at most one solution in $\mathbb {F}_{q^{3}}$ for any $a\in \mathbb {F}_{q^{3}}^{*}$. It is obvious that x = 0 is not the solution of f(x) = a when a ≠ 0. Let y = x ^q, z = y ^q, b = a ^q, c = b ^q and A = a + b + c. Then a,b,c,x,y,z ≠ 0 and $A\in \mathbb {F}_{q}$. And it follows from f(x) = a that

$$ x+\frac{xy}{z}+\frac{yz}{x}=a. $$

(34)

Raising (34) to its q-th and q ²-th power respectively, we get

$$ y+\frac{yz}{x}+\frac{xz}{y}=b $$

(35)

and

$$ z+\frac{zx}{y}+\frac{xy}{z}=c. $$

(36)

Computing (34) + (35) + (36), we have

$$x+y+z=a+b+c=A.$$

On one hand, after computing x z ∗ (34) + x y ∗ (35), we get y(x + z)A + x(b y + a z) = 0. Plugging y = x + z + A into the above equation and simplifying it, we have

$$ (A+b)x^{2}+Az^{2}+(a+b)xz+A(A+b)x+A^{2}z=0. $$

(37)

Let x = u z. Plugging it into (37), we have

$$ B_{1}z+B_{0}=0, $$

(38)

where

$$B_{1}=(A+b)u^{2}+(a+b)u+A, $$

$$B_{0}=A(A+b)u+A^{2}. $$

On the other hand, plugging y = x + z + A into (34) ∗ x z, we get x ³ + z ³ + x z ² + A(x ² + z ²) + a x z = 0. And plugging x = u z into the above equation, we obtain

$$ C_{1}z+C_{0}=0, $$

(39)

where

$$C_{1}=u^{3}+u+1, $$

$$C_{0}=Au^{2}+au+A. $$

Computing (38) ∗ C ₁ + (39) ∗ B ₁, we have

$$B_{0}C_{1}+B_{1}C_{0}=0,$$

i.e.,

$$ D_{1}u+D_{0}=0, $$

(40)

where

$$D_{1}=A^{2}+Ab+ab, $$

$$D_{0}=A^{2}+a^{2}+ab. $$

We claim that D ₁≠0. Otherwise,

$$ A^{2}+Ab+ab=0. $$

(41)

Computing (41) + (41) ^q + (41) $^{q^{2}}$, we get a b + a c + b c = 0, i.e., $1+a^{q^{2}-q}+a^{q^{2}-1}=0$. Let e = a ^1−q. Then 1 + e + e ^q+1 = 0, which is (33). And it is impossible. Thus

$$u=\frac{D_{0}}{D_{1}}.$$

Recalling the definition of A, we know y = A + x + z = A + (1 + u)z. Plugging x = u z and y = A + (1 + u)z into (34), we get

$$\left( u^{3}+u+1\right)z=\left( u^{2}+1\right)A+au.$$

If u ³ + u + 1 = 0, we can conclude that u ⁷ = 1 easily. In fact,

$$u^{q}=\left\{\begin{array}{lll} u^{2}, & \text{if } k\equiv1\pmod3,\\ u^{4}, & \text{if } k\equiv2\pmod3,\\ u, & \text{if } k\equiv0\pmod3. \end{array}\right. $$

When k ≡ 2 (mod 3), z = u ⁻¹ x = u ⁶ x and y = x ^q = (u z)^q = u ^q x = u ⁴ x. Plugging them into (34), we get (1 + u ³ + u ⁵)x = a. If 1 + u ³ + u ⁵ = 0, then 1 + u ³ + u ⁻² = 0,i.e., 1 + u ² + u ⁵ = 0 due to u ⁷ = 1. So u ³ = u ², u = 1. However, u = 1 does not satisfy 1 + u ³ + u ⁵ = 0. Therefore, 1 + u ³ + u ⁵≠0. It follows that $x=\frac {a}{1+u^{3}+u^{5}}$ is the unique solution of f(x) = a in the case. When k ≡ 0 (mod 3),the case is similar as the above one, we omit it here.

If u ³ + u + 1≠0, then x = z ^q,where $z=\frac {\left (u^{2}+1\right )A+au}{u^{3}+u+1}.$ In other words, f(x) = a also has at most one solution in $\mathbb {F}_{q^{3}}$ in the case.

Therefore, for any $a\in {\mathbb F}_{q^{3}}$, f(x) = a has at most one solution in $\mathbb {F}_{q^{3}}$. We finish the proof. □

Theorem 4.4

Let q = 2^k and k≢1 (mod 3). Let $f(x)=x+x^{q^{2}}+x^{q^{3}-q^{2}+q}$ . Then f(x)is a permutation polynomial over $\mathbb {F}_{q^{3}}$ .

Proof

It suffices to prove that f(x) = a has at most one solution in $\mathbb {F}_{q^{3}}$ for any $a\in \mathbb {F}_{q^{3}}$. If a = 0, then we obtain x = 0 or

$$ 1+x^{q^{2}-1}+x^{q-q^{2}}=0. $$

(42)

We claim that (42) has no solution in $\mathbb {F}_{q^{3}}^{*}$. Otherwise, $\text {Tr}_{q^{3}/q}\left (1+x^{q^{2}-1}+x^{q-q^{2}}\right )=0$. Moreover, it follows from $\text {Tr}_{q^{3}/q}\left (x^{q^{2}-1}+x^{q-q^{2}}\right )=0$ that $\text {Tr}_{q^{3}/q}\left (1\right )=0$, which is a contradiction.

In the following, we assume that a ≠ 0. Put y = x ^q, z = y ^q, b = a ^q, c = b ^q and A = a + b + c. Obviously, x,y,z,b,c ≠ 0 when a ≠ 0 and $A\in \mathbb {F}_{q}$. Then we have

$$ \left\{ \begin{array}{ll} x+\frac{xy}{z}+z=a,\\ y+\frac{yz}{x}+x=b,\\ z+\frac{zx}{y}+y=c.\\ \end{array} \right. $$

(43)

Let $\alpha =\frac {xy}{z}$, $\beta =\frac {yz}{x}$, $\gamma =\frac {zx}{y}$. They are clear that β = α ^q and $\gamma =\alpha ^{q^{2}}$. Then

$$ \left\{ \begin{array}{ll} x^{2}=\alpha\gamma,\\ y^{2}=\alpha\beta,\\ z^{2}=\beta\gamma.\\ \end{array} \right. $$

(44)

Plugging (44) into (43), we obtain

$$ \left\{ \begin{array}{ll} \alpha^{2}+\alpha\gamma+\beta\gamma=a^{2},\\ \beta^{2}+\alpha\beta+\alpha\gamma=b^{2},\\ \gamma^{2}+\beta\gamma+\alpha\beta=c^{2}.\\ \end{array} \right. $$

(45)

Adding the above three equations together leads to α + β + γ = a + b + c = A. Then plugging γ = A + α + β into (45), we yield

$$ \beta^{2}+A\beta+A\alpha+a^{2}=0, $$

(46)

and

$$ \beta^{2}+\alpha^{2}+A\alpha+b^{2}=0. $$

(47)

If A = 0,then (α,β,γ) = (c,a,b),and $x=\left (\alpha \gamma \right )^{\frac {1}{2}}=\left (cb\right )^{\frac {1}{2}}$ is uniquely determined.

If A ≠ 0,after adding (46) and (47), we can get $\beta =\frac {1}{A}\left (\alpha ^{2}+a^{2}+b^{2}\right )$. Then plugging it into (46), we have

$$ \alpha^{4}+A^{2}\alpha^{2}+A^{3}\alpha+a^{4}+b^{4}+A^{2}b^{2}=0. $$

(48)

To finish the proof, it suffices to prove that there exists at most one element $\alpha \in {\mathbb F}_{q^{3}}$ satisfying (47) and (48) since then x is uniquely determined by α by (44).

Otherwise, suppose that there exist $\alpha _{1}\neq \alpha _{2}\in {\mathbb F}_{q^{3}}$ satisfy (47) and (48) and put $\delta =\frac {\alpha _{1}+\alpha _{2}}{A}\neq 0$. Then we can obtain

$$ \delta^{2q}+\delta^{2}+\delta=0 $$

(49)

and

$$ \delta^{4}+\delta^{2}+\delta=0 $$

(50)

from (47) and (48) respectively. It is trivial to obtain δ ⁷ = 1 from (50). In fact,

$$\delta^{2q}=\left\{\begin{array}{lllll} \delta^{4}, & \text{if } k\equiv1\pmod3,\\ \delta, & \text{if } k\equiv2\pmod3,\\ \delta^{2}, & \text{if } k\equiv0\pmod3. \end{array}\right.$$

When k ≡ 2 (mod 3),according to (49), we have δ ² = 0, which is impossible! The case k ≡ 0 (mod 3) is the same as the above case, we omit it here.

Therefore, when k≢1 (mod 3), f(x) = a has at most one solution in $\mathbb {F}_{q^{3}}$ for any $a\in \mathbb {F}_{q^{3}}$. We finish the proof. □