# A classification of permutation binomials of the form $x^{i}+ax$ over
$\mathbb{F}_{2^{n}}$ for dimensions up to $8$

Yi Li, Xiutao Feng  Qiang Wang

###### Abstract

Permutation polynomials with few terms (especially permutation binomials)
attract many people due to their simple algebraic structure. Despite the great
interests in the study of permutation binomials, a complete characterization
of permutation binomials is still unknown. In this paper, we give a
classification of permutation binomials of the form $x^{i}+ax$ over
$\mathbb{F}_{2^{n}}$, where $n\leq 8$ by characterizing three new classes of
permutation binomials. In particular one of them has relatively large index
$\frac{q^{2}+q+1}{3}$ over $\mathbb{F}_{q^{3}}$.

###### keywords:

permutation binomials , classification , Hermite’s criterion , the AGW
criterion

###### MSC:

[2020] 11T06, 11T55

††journal: XX

[1]organization=Key Laboratory of Mathematics Mechanization, Academy of
Mathematics and Systems Science, Chinese Academy of Sciences,city=Beijing,
postcode=100190, country=China

[2]organization=University of Chinese Academy of Sciences, city=Beijing,
postcode=100049, country=China [3]organization=School of Mathematics and
Statistics, Carleton University,city=Ottawa, Ontario, postcode=K1S 5B6,
country=Canada

##  1 Introduction

Let $q=p^{n}$ be a prime power, $\mathbb{F}_{q}$ denote the finite field with
$q$ elements. A polynomial $f\in\mathbb{F}_{q}[x]$ is called a
$permutation\hskip 3.99994ptpolynomial$ (PP) over $\mathbb{F}_{q}$ if the
associated polynomial function $f:c\rightarrow f(c)$ from $\mathbb{F}_{q}$
into $\mathbb{F}_{q}$ is a permutation. Permutation polynomial is an active
research area because of its applications in coding theory [16, 26],
cryptography [43, 44] and combinatorial designs [17], and we refer the reader
to [22, 39, 58] for more details of the recent advances and contributions on
them.

Permutation polynomials with few terms attract many people due to their simple
algebraic structure. It is well known that $x^{i}$ is a permutation monomial
if and only if $\text{gcd}(i,q-1)=1$. In 1993, Lidl and Mullen proposed an
open problem (Problem 3.1) in [31]: determine conditions on $k$, $r$, and $q$
so that $P(x)=x^{k}+ax^{r}$ permutes $\mathbb{F}_{q}$ with
$a\in\mathbb{F}_{q}^{*}$. There are many papers on permutation binomials
published in the past thirty years. In particular, different types of
characterizations were given. We refer the reader to [50, 30, 21, 24, 27, 18,
13, 9, 8, 59, 60, 7, 6, 23, 10, 49, 34, 41, 25, 33, 37, 51, 61, 64, 4, 11, 12,
40, 47, 53, 54, 3, 5, 14, 38, 48, 52, 42, 55, 57, 56, 62]. Despite the great
interests in the study of permutation binomials, a complete characterization
of permutation binomials is still unknown.

Motivated by these results, we perform an exhaustive search on permutation
binomials of the form $P(x)=x^{i}+ax$ over $\mathbb{F}_{q}$, where $q=2^{n}$
such that $n\leq 12$. Let $s=\gcd(i-1,2^{n}-1)$ and $d=\frac{q-1}{s}$. Then
$P(x)=x(x^{es}+a)$ for some positive integer $e$. Here $d$ is called the index
of $P(x)$ [1]. In general, the smaller their indices, the simpler are these
PPs. Indeed, we can compute all the coefficients of these PPs of small indices
using Inverse Discrete Fourier Transform. We refer to [58] for more results
and details on the index of any polynomial over a finite field
$\mathbb{F}_{q}$. Also in [58], Wang proposed to classify permutation
polynomials by their indices and we follow this approach to study permutation
binomials of the form $x^{i}+ax$ over $\mathbb{F}_{2^{n}}$ in terms of their
indices. Since it is easy to determine when a linearized binomial
$x^{2^{j}}+ax$ is a PP over $\mathbb{F}_{2^{n}}$ (i.e., $a$ is not a
($2^{\gcd(j,n)}-1$)-th power), we focus on non-linearzied permutation
binomials from now on.

Below are some tables of non-linearized permutation binomial $x^{i}+ax$ over
$\mathbb{F}_{2^{n}}$, where $6\leq n\leq 12$. In each table, we provide the
values of $i$ such that $x^{i}+ax$ is permutation binomial for some
$a\in\mathbb{F}_{2^{n}}^{*}$, the indices of corresponding permutation
binomials, as well as the references where we can use general classes of PPs
to explain these examples. In some cases, we don’t have explicitly
characterized classes to include these examples, instead, we provide some
references for general implicit characterizations. We observe that most of
non-linearized permutation binomials over $\mathbb{F}_{q}$ have small indices,
which are less than $\sqrt{q}+1$. However, we find three permutation binomials
over $\mathbb{F}_{2^{12}}$ whose indices are larger than 65, that is,
$x^{136}+ax$, $x^{271}+ax$ and $x^{1846}+ax$, which have an index $91$ and
they are listed in Table 5. In contrast, the indices of permutation binomials
over prime fields are always less than $\sqrt{q}+1$ (see [36]). This indicates
the different behaviors of permutation binomials between prime fields and non
prime fields.

Motivated by these examples, we characterize three new classes of permutation
binomials over $\mathbb{F}_{2^{n}}$ and use them to complete the
classification of all permutation binomial of the form $x^{i}+ax$ over
$\mathbb{F}_{2^{n}}$ where $n\leq 8$. We also note that one of these new
classes provides permutation binomials with relatively large indices
$\frac{q^{2}+q+1}{3}$ over $\mathbb{F}_{q^{3}}$, which can explain two of
three permutation binomials of index $91$ over $\mathbb{F}_{2^{12}}$. This
also provides a new class of PPs to answer Problem 7 in [58].

We note that there are no permutation binomials of the form $x^{i}+ax$ in
$\mathbb{F}_{2^{5}}$, $\mathbb{F}_{2^{7}}$, and $\mathbb{F}_{2^{11}}$. Indeed,
using Corollary 3 in [35], we can explain that there is no permutation
binomial over $\mathbb{F}_{2^{5}}$ or $\mathbb{F}_{2^{7}}$ because $31,127$
are Mersenne primes. However, $2^{11}-1=23\times 89$ is not a prime. So, it
still remains to answer why there is no permutation binomial of the form
$x^{i}+ax$ over $\mathbb{F}_{2^{11}}$.

The rest of the paper is organized as follows. In Section 2, we introduce some
preliminary results and techniques such as Hermite’s criterion and the AGW
criterion. In Section 3, we state and prove three new classes of permutation
binomials $x^{i}+ax$ over $\mathbb{F}_{q^{2}}$, $\mathbb{F}_{q^{3}}$, and
$\mathbb{F}_{q^{4}}$ respectively and a nonexistence result. The discussion in
Section 4 provides a complete explanation of all permutation binomials of the
form $x^{i}+ax$ over $\mathbb{F}_{2^{n}}$ where $n\leq 8$. The conclusion and
future work are given in Section 5.

Table 1:  Non-linearized permutation binomials $x^{i}+ax$ over $\mathbb{F}_{2^{6}}$ $i$ | Index | Refs
---|---|---
10 | 7 |  this paper, [64]
19 | 7 |  this paper, [64]
22 | 3 | [24]
43 | 3 | this paper
Table 2:  Non-linearized permutation binomials $x^{i}+ax$ over $\mathbb{F}_{2^{8}}$ $i$ | Index | Refs
---|---|---
86 | 3 | [8]
154 | 5 | this paper
171 | 3 | this paper
Table 3:  Non-linearized permutation binomials $x^{i}+ax$ over $\mathbb{F}_{2^{9}}$ $i$ | Index | Refs
---|---|---
74 | 7 | [9, 64]
366 | 7 | Implicit characterization [55, 57, 58]
Table 4:  Non-linearized permutation binomials $x^{i}+ax$ over $\mathbb{F}_{2^{10}}$ $i$ | 34 | 67 | 94 | 187
---|---|---|---|---
Index | 31 | 31 | 11 | 11
Refs | [9, 64] | [46, 64] | [24] | this paper
$i$ | 280 | 331 | 342 | 397
Index | 11 | 31 | 3 | 31
Refs | Implicit characterization [55, 57, 58]
$i$ | 466 | 559 | 652 | 683
Index | 11 | 11 | 11 | 3
Refs | Implicit characterization [55, 57, 58]
$i$ | 745 | 838 | 931 |
Index | 11 | 11 | 11 |
Refs | Implicit characterization [55, 57, 58] |
Table 5:  Non-linearized permutation binomials $x^{i}+ax$ over $\mathbb{F}_{2^{12}}$ $i$ | 136 | 271 | 274 | 316
---|---|---|---|---
Index | 91 | 91 | 15 | 13
Refs | this paper | this paper | [9, 64] | [27]
$i$ | 547 | 586 | 631 | 820
Index | 15 | 7 | 13 | 5
Refs | Implicit characterization [55, 57, 58]
$i$ | 946 | 1093 | 1171 | 1260
Index | 13 | 15 | 7 | 13
Refs | Implicit characterization [55, 57, 58]
$i$ | 1366 | 1576 | 1639 | 1846
Index | 3 | 15 | 5 | 91
Refs | Implicit characterization [55, 57, 58]
$i$ | 1890 | 2146 | 2206 | 2276
Index | 13 | 21 | 15 | 9
Refs | Implicit characterization [55, 57, 58]
$i$ | 2341 | 2458 | 2521 | 2536
Index | 7 | 5 | 13 | 21
Refs | Implicit characterization [55, 57, 58]
$i$ | 2731 | 2836 | 3004 | 3151
Index | 3 | 13 | 15 | 13
Refs | Implicit characterization [55, 57, 58]
$i$ | 3277 | 3466 | 3511 | 3781
Index | 5 | 13 | 7 | 13
Refs | Implicit characterization [55, 57, 58]

##  2 Preliminaries

The following Hermite’s criterion is one of the most useful tools to
characterize permutation polynomials.

######  Lemma 1.

[20, 32] (Hermite’s criterion) Let $\mathbb{F}_{q}$ be a finite field of
characteristic p. Then $f\in\mathbb{F}_{q}[x]$ is a permutation polynomial of
$\mathbb{F}_{q}$ if and only if the following two conditions hold:

(i) $f$ has exactly one root in $\mathbb{F}_{q}$;

(ii) for each integer $t$ with $1\leq t\leq q-2$ and $t\not\equiv 0\hskip
5.0pt(\text{mod}\hskip 5.0ptp)$, the reduction of $f(x)^{t}\mod(x^{q}-x)$ has
degree $\leq q-2$.

To apply Hermite’s criterion on permutation binomials, we need to show the
coefficient of $x^{q-1}$ in the reduction of $f(x)^{t}\mod(x^{q}-x)$ vanishes.
The following result is very useful to compute binomials coefficients over
extension fields.

######  Lemma 2.

(Lucas’ lemma) Let $n,i$ be positive integers and $p$ be a prime. Assume
$n=a_{m}p^{m}+a_{m-1}p^{m-1}+...+a_{1}p+a_{0}$ and
$i=b_{m}p^{m}+...+b_{1}p+b_{0}$, where $m$ is a non-negative integer and
$0\leq a_{i},b_{i}<p$ for $i=0,1,\cdots,m$. Then

$\binom{n}{i}\equiv\binom{a_{m}}{b_{m}}\binom{a_{m-1}}{b_{m-1}}...\binom{a_{0}}{b_{0}}\hskip
5.0pt(\text{mod}\hskip 5.0ptp).$

In recent years, the AGW criterion has become another important tool to
characterize and construct new classes of permutation polynomials.

######  Lemma 3.

[2] (The AGW criterion) Let $A,S$ and $\bar{S}$ be finite sets with
$|S|=|\bar{S}|$. Let $f,\bar{f},\lambda,\bar{\lambda}$ be maps on finite sets
such that $f:A\rightarrow A$, $\bar{f}:S\rightarrow\bar{S}$,
$\lambda:A\rightarrow S$, $\bar{\lambda}:A\rightarrow\bar{S}$, and
$\bar{\lambda}\circ f=\bar{f}\circ\lambda$.

${A}$${A}$${S}$${\bar{S}}$$\scriptstyle{f}$$\scriptstyle{\lambda}$$\scriptstyle{\bar{\lambda}}$$\scriptstyle{\bar{f}}$

If $\lambda$ and $\bar{\lambda}$ are surjective, then the following are
equivalent:

(i) $f$ is a bijection from $A$ to itself;

(ii) $\bar{f}$ is a bijection from $S$ to $\bar{S}$ and $f$ is injective on
$\lambda^{-1}(s)$ for each $s\in S$.

In particular, if we let $A=\mathbb{F}_{q}^{*}$ and the maps
$\lambda=\bar{\lambda}=x^{s}$, where $q-1=ds$ for some positive integers
$s,d$, then we obtain the so-called multiplicative case of the AGW criterion.

######  Corollary 4.

[28, 63, 57, 55] Let $q-1=ds$, where $d$ and $s$ are two positive integers and
$q$ is a prime power. Then $p(x)=x^{r}f(x^{s})$ is a permutation polynomial
over $\mathbb{F}_{q}$ if and only if $\text{gcd}(r,s)=1$ and $x^{r}f(x)^{s}$
permutes the set $\mu_{d}$ of $d$-th roots of unity.

As for some special form of permutation binomials, some characterizations were
given. For example, a characterization of permutation binomials of the form
$x^{1+\frac{q-1}{m}}+ax$ over $\mathbb{F}_{q}$ was given in [40]. For the
polynomials which have low indices, Wang [58] proposed an algorithm to
classify all PPs over $\mathbb{F}_{q}$ of small indices explicitly in terms of
their coefficients. These results can make our tables more accurate.

An exceptional polynomial over $\mathbb{F}_{q}$ is a polynomial
$f\in\mathbb{F}_{q}[x]$ which is a permutation polynomial on
$\mathbb{F}_{q^{m}}$ for infinitely many $m$. In the sequel, we also need some
results on exceptional polynomials.

######  Lemma 5.

[39] A permutation polynomial over $\mathbb{F}_{q}$ of degree at most
$q^{\frac{1}{4}}$ is exceptional over $\mathbb{F}_{q}$.

######  Lemma 6.

(Carlitz-Wan conjecture/theorem)[39, 15, 19] Exceptional polynomials over
$\mathbb{F}_{q}$ have degree coprime to $q-1$.

##  3 Three new classes of permutation binomials and a nonexistence result

Let $q=2^{n}$. In this section we characterize three new classes of
permutation binomials $x^{i}+ax$ over $\mathbb{F}_{q^{2}}$,
$\mathbb{F}_{q^{3}}$, and $\mathbb{F}_{q^{4}}$ respectively. We also prove
that there is no permutation binomial of the form
$x^{2(q^{3}+q^{2}+q+1)+1}+ax$ over $\mathbb{F}_{q^{4}}$ with index $q-1$,
where $m$ even and $m\geq 4$.

###  3.1 Permutation binomials over $\mathbb{F}_{q^{2}}$

In [65], Zieve proved $x^{r(q-1)+1}+ax$ is a PP of $\mathbb{F}_{q^{2}}$ if and
only if $(-a)^{\frac{q+1}{\text{gcd}(r,q+1)}}\neq 1$ and
$\text{gcd}(r-1,q-1)=1$ under the assumption that $a^{q+1}=1$. In [21, 24,
27], Hou and Lappano used Hermite’s criterion to determine several explicit
classes of permutation binomials with the forms $x^{2q-1}+ax$, $x^{3q-2}+ax$,
$x^{5q-4}+ax$ and $x^{7q-6}+ax$ over $\mathbb{F}_{q^{2}}$. Later, in [23], Hou
proved that let $r>2$ be a fixed prime, under the assumption $a^{q+1}\neq
1(a\in\mathbb{F}_{q}^{*})$, there are only finitely many $(q,a)$ for which
$x^{r(q-1)+1}+ax$ is a PP of $\mathbb{F}_{q^{2}}$. Motivated by these results,
Li et al [30] completely characterized when $x^{r}(x^{q-1}+a)$ can be a
permutation binomial. In [50], sufficient conditions on $x^{r}(x^{3(q-1)}+a)$
were given. Very recently, in [25], Hou and Lavorante gave two nonexistence
results about permutation binomials of the form $x^{r}(x^{d(q-1)}+a)$ over
$\mathbb{F}_{q^{2}}$.

The following new class of permutation binomials over $\mathbb{F}_{q^{2}}$ is
motivated by the permutation binomial $x^{43}+ax$ over $\mathbb{F}_{2^{6}}$
and $x^{187}+ax$ over $\mathbb{F}_{2^{10}}$. We use both Hermite’s criterion
and the AGW criterion in the proof.

######  Theorem 7.

Let $q=2^{n}$, $n\geq 3$ is odd, and $a\in\mathbb{F}_{q^{2}}^{*}$. Then the
polynomial

$f_{1}(x)=x^{6q-5}+ax$

is a permutation polynomial in $\mathbb{F}_{q^{2}}$ if and only if one of the
following occurs

  1. 1.

$n\geq 5$, $a\in\mu_{q+1}$ and $a\not\in\mu_{\frac{q+1}{3}}$;

  2. 2.

$n=3$,
$a\in\\{\gamma^{3},\gamma^{6},\gamma^{7},\gamma^{12},\gamma^{14},\gamma^{24},\gamma^{27},\gamma^{28}$,
$\gamma^{33},\gamma^{35},\gamma^{45},\gamma^{48},\gamma^{49},\gamma^{54},\gamma^{56}$},
where $\gamma$ is a primitive element in $\mathbb{F}_{2^{6}}$.

###### Proof.

When $q=2^{3}$, it is easy to verify the conditions. Hence we assume $n\geq 5$
from now on. If $f_{1}(x)$ is a permutation polynomial, then by Hermite’s
criterion, we know for any $1\leq t\leq q^{2}-2$, the coefficient of
$x^{q^{2}-1}$ in the reduction of $f_{1}(x)^{t}\mod(x^{q^{2}}-x)$ vanishes.
Let $t=3q-3$. We consider

$\displaystyle\begin{aligned} f_{1}(x)^{t}&=(x^{6q-5}+ax)^{3q-3}\\\
&=x^{3q-3}\sum\limits_{i=0}^{3q-3}\binom{3q-3}{i}x^{(6q-6)i}a^{3q-3-i}\\\
&=\sum\limits_{i=0}^{3q-3}\binom{3q-3}{i}a^{3q-3-i}x^{3q-3+(6q-6)i}.\end{aligned}$
(1)

It is clear to see that the coefficient of $x^{q^{2}-1}$ is
$\sum\limits_{i=0}^{3q-3}\binom{3q-3}{i}a^{3q-3-i}$ such that $1+2i\equiv
0\hskip 5.0pt(\text{mod}\hskip 5.0pt\frac{q+1}{3})$. Next we determine all
possible values of $i$ such that $1+2i\equiv 0\hskip 5.0pt(\text{mod}\hskip
5.0pt\frac{q+1}{3})$, that is,

$\displaystyle 1+2i=k\frac{q+1}{3},$ (2)

where $k\in\mathbb{Z}$. From Equation (2), we can get

$\displaystyle i=k\frac{q+1}{6}-\frac{1}{2}.$ (3)

Because $i$ is a nonnegative integer and $i\leq 3q-3$, $k$ must be odd and
$k\leq 17$. Plugging these 9 possible values of $k$ into Equation (3), we
obtain

$i\in
S:=\left\\{\frac{q-2}{6},\frac{q}{2},\frac{5q+2}{6},\frac{7q+4}{6},\frac{9q+6}{6},\frac{11q+8}{6},\frac{13q+10}{6},\frac{15q+12}{6},\frac{17q+14}{6}\right\\}.$

Hence the coefficient of $x^{q^{2}-1}$ in Equation (1) is

$\displaystyle\sum\limits_{i\in S}\binom{3q-3}{i}a^{3q-3-i}=0.$ (4)

We note that $3q-3=2(q-1)+(q-1)=2q+\frac{q}{2}+\frac{q}{4}+...+4+1$. Using
$q=2^{n}$, by Lucas’ lemma, $\binom{3q-3}{i}\neq 0$ if and only if the
$(n+1)$th bit and second lowest bit of the binary expansion of $i$ are $0$. We
denote by $S_{0}\subseteq S$ the subset of $S$ such that the $(n+1)$th bit and
second lowest bit of the binary expansion of $i$ are $0$.

Next we explicitly determine $S_{0}$. Obviously $\frac{q}{2}\in S_{0}$. On the
other hand, neither $\frac{9q+6}{6}=q+\frac{q}{2}+1$ nor
$\frac{15q+12}{6}=2q+\frac{q}{2}+2$ belongs to $S_{0}$. Then we look at
$2$-adic expansion of $\frac{q-2}{6}$, that is
$\frac{q-2}{6}=\frac{q}{8}+\frac{q}{32}+...+4+1$, which implies that
$\frac{q-2}{6}\in S_{0}$. Because
$\frac{q+1}{3}=2(\frac{q-2}{6})+1=\frac{q}{4}+\frac{q}{16}+...+8+2+1$, we
obtain $\frac{5q+2}{6}\not\in S_{0}$. This also implies that
$\frac{11q+8}{6}=q+\frac{q}{2}+1+\frac{q+1}{3}\not\in S_{0}$. Similarly,
$\frac{7q+4}{6}\not\in S_{0}$ because
$\frac{7q+4}{6}=q+\frac{q+4}{6}=q+1+\frac{q-2}{6}=q+\frac{q}{8}+\frac{q}{32}+...+4+2$.
Moroever, $\frac{13q+10}{6}\not\in S_{0}$ because
$\frac{13q+10}{6}=2q+2+\frac{q-2}{6}$. Finally
$\frac{17q+14}{6}=2q+\frac{q}{2}+\frac{q+1}{3}+2$ implies that
$\frac{17q+14}{6}\in S_{0}$. Hence, we know
$S_{0}=\\{\frac{q}{2},\frac{q-2}{6},\frac{17q+14}{6}\\}$.

Hence the coefficient of $x^{q^{2}-1}$ in Equation (1) is

$\displaystyle\begin{aligned} \sum\limits_{i\in
S}\binom{3q-3}{i}a^{3q-3-i}&=\sum\limits_{i\in
S_{0}}\binom{3q-3}{i}a^{3q-3-i}\\\
&=a^{\frac{17q-16}{6}}+a^{\frac{5q}{2}-3}+a^{\frac{q-32}{6}}\\\
&=a^{\frac{q-32}{6}}(a^{\frac{8q+8}{3}}+a^{\frac{7q+7}{3}}+1)=0.\end{aligned}$
(5)

Therefore $a^{\frac{8q+8}{3}}+a^{\frac{7q+7}{3}}+1=0$. Let
$y=a^{-\frac{q+1}{3}}$. Then $y\in\mu_{3(q-1)}$ and

$\displaystyle y^{8}+y+1=0.$ (6)

It is easy to check that $\omega,\omega^{2}$ are solutions of $y^{8}+y+1=0$,
where $\omega$ is a primitive $3$-th root of unity. In fact, there are no
other solutions in $\mu_{3(q-1)}$. Because $y^{8}+y+1=0$ is an affine
equation, all the solutions are of the form $\omega+b$, where
$b\in\mathbb{F}_{2^{3}}$. If $3\nmid m$, then $\omega$, $\omega+1=\omega^{2}$
are the only two solutions in $\mathbb{F}_{2^{2m}}$. If $3\mid m$ and
$\omega+b$ is a solution in $\mu_{3(q-1)}$, then we have
$(\omega+b)^{3q}=(\omega+b)^{3}$. Obviously,

$(\omega+b)^{3}=1+\omega^{2}b+b^{2}\omega+b^{3},$ (7)

$\displaystyle\begin{aligned}
(\omega+b)^{3q}=(\omega^{q}+b)^{3}=(\omega^{2}+b)^{3}=1+b\omega+b^{2}\omega^{2}+b^{3}.\end{aligned}$
(8)

From Equations (7) and (8), we have

$\displaystyle b^{2}\omega+b\omega^{2}=b\omega+b^{2}\omega^{2}.$ (9)

From Equation (9), we have $(b^{2}+b)\omega=(b^{2}+b)\omega^{2}$. Hence
$b^{2}+b=0$ and thus $b\in\\{0,1\\}$. Therefore there are no other solutions
in $\mu_{3(q-1)}$. Hence $y=a^{-\frac{q+1}{3}}=\omega$ or $\omega^{2}$ and
thus $a^{q+1}=1$ but $a^{\frac{q+1}{3}}\neq 1$.

Conversely, by the AGW criterion, we have the following diagram:

${\mathbb{F}_{q^{2}}^{*}}$${\mathbb{F}_{q^{2}}^{*}}$${\mu_{q+1}}$${\mu_{q+1}}$$\scriptstyle{x^{q-1}}$$\scriptstyle{x(x^{6q-6}+a)}$$\scriptstyle{x^{q-1}}$$\scriptstyle{x(x^{6}+a)^{q-1}}$

From this diagram, we know $x(x^{6q-6}+a)$ is a permutation over
$\mathbb{F}_{q^{2}}$ if and only if $x(x^{6}+a)^{q-1}$ permutes $\mu_{q+1}$.
If $a\in\mu_{q+1}$ and $a\not\in\mu_{\frac{q+1}{3}}$, then $x^{6}+a$ has no
root in $\mu_{q+1}$. In this case, we have

$\displaystyle\begin{aligned}
x(x^{6}+a)^{q-1}=\frac{x(x^{-6}+a^{-1})}{x^{6}+a}=a^{-1}x^{-5}.\end{aligned}$
(10)

Because $n$ is odd, $\text{gcd}(5,2^{n}+1)=1$. Therefore $x(x^{6}+a)^{q-1}$
permutes $\mu_{q+1}$ and thus $x(x^{6q-6}+a)$ is a permutation binomial of
$\mathbb{F}_{q^{2}}$. ∎

###  3.2 Permutation binomials over $\mathbb{F}_{q^{3}}$

Next we characterize another two new classes of permutation binomials over
$\mathbb{F}_{q^{3}}$. These classes contain permutation binomials $x^{10}+ax$
and $x^{19}+ax$ over $\mathbb{F}_{2^{6}}$.

######  Theorem 8.

Let $q=2^{n}$, $n$ even, and $a\in\mathbb{F}_{q^{3}}^{*}$. Then the polynomial

$f_{2}(x)=x^{\frac{q^{2}+q}{2}}+ax$

is a permutation polynomial in $\mathbb{F}_{q^{3}}$ if and only if
$a\in\mu_{q^{2}+q+1}$ and $a\not\in\mu_{\frac{q^{2}+q+1}{3}}$.

###### Proof.

If $f_{2}(x)$ is a permutation polynomial, then by Hermite’s criterion, the
coefficient of $x^{q^{3}-1}$ in the reduction of
$f_{2}(x)^{t}\mod(x^{q^{3}}-x)$ vanishes for any $1\leq t\leq q^{3}-2$. Let
$t=2q^{2}-q-1$. We have

$\displaystyle\begin{aligned}
f_{2}(x)^{t}&=(x^{\frac{q^{2}+q}{2}}+ax)^{2q^{2}-q-1}\\\
&=x^{2q^{2}-q-1}\sum\limits_{i=0}^{2q^{2}-q-1}\binom{2q^{2}-q-1}{i}x^{\frac{(q^{2}+q-2)i}{2}}a^{2q^{2}-q-1-i}\\\
&=\sum\limits_{i=0}^{2q^{2}-q-1}\binom{2q^{2}-q-1}{i}a^{2q^{2}-q-1-i}x^{2q^{2}-q-1+\frac{(q^{2}+q-2)i}{2}}.\end{aligned}$
(11)

The coefficient of $x^{q^{3}-1}$ in Equation (11) is
$\sum\limits_{i=0}^{2q^{2}-q-1}\binom{2q^{2}-q-1}{i}a^{2q^{2}-q-1-i}$ such
that $(2q+1)+\frac{q+2}{2}i\equiv 0\hskip 5.0pt(\text{mod}\hskip
5.0pt(q^{2}+q+1))$, which is equivalent to $4q+2+(q+2)i\equiv 0\hskip
5.0pt(\text{mod}\hskip 5.0pt2(q^{2}+q+1))$.

Let

$\displaystyle(q+2)i+4q+2=2k(q^{2}+q+1),$ (12)

where $k\in\mathbb{Z}$. Then

$\displaystyle i=k(2q-2)-4+\frac{6k+6}{q+2}.$ (13)

Because $i$ is an integer, we obtain

$\displaystyle 6k+6\equiv 0\hskip 5.0pt(\text{mod}\hskip 5.0ptq+2).$ (14)

Because $6\mid(q+2)$, Equation (14) is equivalent to

$\displaystyle k+1\equiv 0\hskip 5.0pt(\text{mod}\hskip 5.0pt\frac{q+2}{6}).$
(15)

Because $i\leq 2q^{2}-q-1$, we obtain $k\leq q$. Together with Equation (15),
we know that $k$ can take up to five values: $\frac{q+2}{6}-1$,
$\frac{q+2}{3}-1$, $\frac{q+2}{2}-1$, $\frac{2(q+2)}{3}-1$,
$\frac{5(q+2)}{6}-1$. Plugging these values into Equation (13), we obtain
$i\in
S=\\{\frac{q^{2}-5q-5}{3},\frac{2q^{2}-4q-4}{3},q^{2}-q-1,\frac{4q^{2}-2q-2}{3},\frac{5q^{2}-q-1}{3}\\}$.

Hence the coefficient of $x^{q^{3}-1}$ is

$\displaystyle\sum\limits_{i\in
S}\binom{2q^{2}-q-1}{i}a^{2q^{2}-q-1-i}=\sum\limits_{j\in
S^{\prime}}\binom{2q^{2}-q-1}{j}a^{j},$ (16)

where
$S^{\prime}=\\{q^{2}+\frac{2}{3}(q^{2}+q+1),q^{2}+\frac{1}{3}(q^{2}+q+1),q^{2},q^{2}-\frac{1}{3}(q^{2}+q+1),q^{2}-\frac{2}{3}(q^{2}+q+1)\\}$.

We note that
$2q^{2}-q-1=q^{2}+\frac{q^{2}}{2}+\cdots+2q+\frac{q}{2}+\cdots+1$. From Lucas’
lemma, $\binom{2q^{2}-q-1}{j}\neq 0$ if and only if the $(n+1)$ th bit of the
binary expansion of $j$ is $0$. We denote by $S_{0}\subseteq S^{\prime}$ such
that the $(n+1)$ th bit of the binary expansion of $j\in S^{\prime}$ is $0$.
Clearly $j=q^{2}\in S_{0}$.

When $q>4$, we first look at the $2$-adic expansion of
$\frac{q^{2}+q+1}{3}=\frac{1}{3}(q^{2}+q-2)+1=\frac{1}{3}(q-1)(q+2)+1$.
Because $q=2^{n}$ and $n$ is even, we can easily determine $\frac{q-1}{3}$’s
$2$-adic expansion, that is
$\frac{q-1}{3}=\frac{q}{4}+\frac{q}{16}+\frac{q}{64}+\cdots+1$. Using
$\frac{q^{2}+q+1}{3}=\frac{1}{3}(q-1)(q+2)+1$, we obtain
$\frac{1}{3}(q^{2}+q+1)=\frac{q^{2}}{4}+\frac{q^{2}}{16}+\frac{q^{2}}{64}+\cdots+q+\frac{q}{2}+\frac{q}{8}+\cdots+2+1$.

Therefore the $(n+1)$ th bit of $q^{2}+\frac{1}{3}(q^{2}+q+1)$ and
$q^{2}+\frac{2}{3}(q^{2}+q+1)$ is not $0$ respectively. Hence both
$q^{2}+\frac{2}{3}(q^{2}+q+1)$ and $q^{2}+\frac{1}{3}(q^{2}+q+1)$ do not
belong to $S_{0}$.

Similarly, we obtain
$q^{2}-\frac{1}{3}(q^{2}+q+1)=\frac{q^{2}}{2}+\frac{q^{2}}{8}+\frac{q^{2}}{32}+\cdots+2q+\frac{q}{4}+\frac{q}{16}+\cdots+1$
and
$q^{2}-\frac{2}{3}(q^{2}+q+1)=\frac{q^{2}}{4}+\frac{q^{2}}{16}+\frac{q^{2}}{64}+\cdots+\frac{q}{2}+\frac{q}{8}+\cdots+2$.
Hence $j=q^{2}-\frac{1}{3}(q^{2}+q+1),q^{2}-\frac{2}{3}(q^{2}+q+1)\in S_{0}$.
It is easy to verify when $q=4$, $q^{2}-\frac{1}{3}(q^{2}+q+1)$,
$q^{2}-\frac{2}{3}(q^{2}+q+1)\in S_{0}$. Hence we know
$S_{0}=\\{q^{2},q^{2}-\frac{1}{3}(q^{2}+q+1),q^{2}-\frac{2}{3}(q^{2}+q+1)\\}$.

Therefore the coefficient of $x^{q^{3}-1}$ is

$\displaystyle\begin{aligned} \sum\limits_{j\in
S^{\prime}}\binom{2q^{2}-q-1}{j}a^{j}&=a^{q^{2}}+a^{q^{2}-\frac{1}{3}(q^{2}+q+1)}+a^{q^{2}-\frac{2}{3}(q^{2}+q+1)}\\\
&=a^{q^{2}-\frac{2}{3}(q^{2}+q+1)}(a^{\frac{2}{3}(q^{2}+q+1)}+a^{\frac{1}{3}(q^{2}+q+1)}+1).\\\
\end{aligned}$ (17)

If $a\in\mu_{\frac{q^{2}+q+1}{3}}$, then the coefficient of $x^{q^{3}-1}$ is
$a^{q^{2}-\frac{2}{3}(q^{2}+q+1)}\neq 0$, contradicts the fact that $f_{2}(x)$
is a permutation binomial. Hence $a\not\in\mu_{\frac{q^{2}+q+1}{3}}$. In this
case, we must have $a^{q^{2}+q+1}=1$.

Conversely, it suffices to prove $f_{2}(x)=b$ has at most one solution for all
$b\in\mathbb{F}_{q^{3}}$ when $a\in\mu_{q^{2}+q+1}$ and
$a\not\in\mu_{\frac{q^{2}+q+1}{3}}$. Let $g_{2}(x)=f_{2}(x^{2})$. Obviously
$f_{2}(x)$ is a permutation polynomial of $\mathbb{F}_{q^{3}}$ if and only if
$g_{2}(x)$ is a permutation polynomial of $\mathbb{F}_{q^{3}}$. Therefore we
will show that $g_{2}(x)=b$ has at most one solution for any
$b\in\mathbb{F}_{q^{3}}$. If $b=0$, then $a\not\in\mu_{\frac{q^{2}+q+1}{3}}$
implies that $x^{q^{2}+q}+ax^{2}=0$ has only zero solution.

From now on, we assume $b\neq 0$. Let $y=x^{q}$, $z=y^{q}$, $b_{1}=b$,
$b_{2}=b^{q}$, $b_{3}=b_{2}^{q}$. Raising $q$-th power to $g_{2}(x)=b$, we
obtain a system of equations

$\displaystyle\left\\{\begin{array}[]{c}yz+ax^{2}=b_{1},\\\
zx+a^{q}y^{2}=b_{2},\\\ xy+a^{q^{2}}z^{2}=b_{3}.\end{array}\right.$ (21)

Since $b_{1}=b\neq 0$, we must have $x\neq 0$. From the second equation of
(21), we write

$\displaystyle z=\frac{b_{2}+a^{q}y^{2}}{x}.$ (22)

Plugging Equation (22) into the first and third equation of (21), we get

$\displaystyle\left\\{\begin{array}[]{c}h_{1}(x,y)=ax^{3}+b_{1}x+a^{q}y^{3}+b_{2}y=0,\\\
h_{2}(x,y)=x^{3}y+b_{3}x^{2}+a^{q^{2}+2q}y^{4}+a^{q^{2}}b_{2}^{2}=0.\end{array}\right.$
(25)

The resultant of Equation (25) with respect to the indeterminate $y$ is

$\displaystyle(a^{3q-2}b_{1}^{3}+a^{3q-1}b_{1}b_{2}b_{3}+a^{2q-1}b_{2}^{3}+a^{4q}b_{3}^{3})x^{6}+(a^{3q-3}b_{1}^{4}+a^{3q-1}b_{2}^{2}b_{3}^{2})x^{4}=0.$
(26)

Let
$A=a^{3q-2}b_{1}^{3}+a^{3q-1}b_{1}b_{2}b_{3}+a^{2q-1}b_{2}^{3}+a^{4q}b_{3}^{3}$
and $B=a^{3q-3}b_{1}^{4}+a^{3q-1}b_{2}^{2}b_{3}^{2}$. If exactly one of $A$
and $B$ is zero, then $x$ is zero, a contradiction. Next we show both $A$ and
$B$ are not zero. Assume, to the contrary, that $A=B=0$. We can get a system
of equations

$\displaystyle\left\\{\begin{array}[]{c}a^{3q-2}b_{1}^{3}+a^{3q-1}b_{1}b_{2}b_{3}+a^{2q-1}b_{2}^{3}+a^{4q}b_{3}^{3}=0,\\\
a^{3q-3}b_{1}^{4}+a^{3q-1}b_{2}^{2}b_{3}^{2}=0.\end{array}\right.$ (29)

From the second equation of (29), we get $b_{1}^{2}=ab_{2}b_{3}$, which is
equivalent to saying $a^{-1}=b_{1}^{q^{2}+q-2}$. But
$\text{gcd}(q^{2}+q-2,q^{3}-1)=3(q-1)$ implies
$a\in\mu_{\frac{q^{2}+q+1}{3}}$, a contradiction. Hence $AB\neq 0$ and thus
Equation (26) has at most one non zero solution for each $b_{1}$. Hence
$g_{2}(x)=b$ has at most one solution for any $b\in\mathbb{F}_{q^{3}}$. ∎

######  Remark 1.

In [34], the authors constructed a class of complete permutation monomials:
$x^{2^{4k-1}+2^{2k-1}}$ over $\mathbb{F}_{2^{6k}}$, where $k$ is a positive
integer with gcd$(k,3)=1$. Our theorem generalizes their result.

Because $(q^{2}+q-1)\frac{q^{2}+q}{2}\equiv 1\hskip 5.0pt(\text{mod}\hskip
5.0pt(q^{3}-1))$, we have the following permutation polynomial
$h_{2}(x)=a^{-1}g_{2}(x^{q^{2}+q-1})$.

######  Corollary 9.

Let $q=2^{n}$, $n$ even, and $a\in\mathbb{F}_{q^{3}}^{*}$. Then the polynomial

$h_{2}(x)=x^{q^{2}+q-1}+ax$

is a permutation polynomial in $\mathbb{F}_{q^{3}}$ if and only if
$a\in\mu_{q^{2}+q+1}$ and $a\not\in\mu_{\frac{q^{2}+q+1}{3}}$.

######  Remark 2.

Theorem 8 and Corollary 9 give us two classes of permutation binomials which
have relatively large index $\frac{q^{2}+q+1}{3}$.

###  3.3 Permutation binomials over $\mathbb{F}_{q^{4}}$

To explain the permutation behavior of $x^{154}+ax$ in $\mathbb{F}_{2^{8}}$,
we generalize it into an infinite class of permutation binomials over
$\mathbb{F}_{q^{4}}$.

######  Theorem 10.

Let $q=2^{n}$, $n>1$ and $a\in\mathbb{F}_{q^{4}}^{*}$. The polynomial

$f_{3}(x)=x^{\frac{q^{3}-q^{2}+q-1}{2}+1}+ax$

is a permutation polynomial in $\mathbb{F}_{q^{4}}$ if and only if
$a\in\mu_{q^{2}-1}$ and $a\not\in\mu_{q+1}$.

###### Proof.

Let $g_{3}(x)=f_{3}(x^{2})$. Obviously $f_{3}(x)$ is a permutation polynomial
if and only if $g_{3}(x)$ is a permutation polynomial. Next we show $g_{3}(x)$
is a permutation polynomial if and only if $a\in\mu_{q^{2}-1}$ and
$a\not\in\mu_{q+1}$.

By the AGW criterion, we have the following diagram:

${\mathbb{F}_{q^{4}}^{*}}$${\mathbb{F}_{q^{4}}^{*}}$${\mu_{q+1}}$${\mu_{q+1}}$$\scriptstyle{g_{3}(x)=x^{2}(x^{(q-1)(q^{2}+1)}+a)}$$\scriptstyle{x^{(q-1)(q^{2}+1)}}$$\scriptstyle{x^{(q-1)(q^{2}+1)}}$$\scriptstyle{h_{3}(x)=x^{2}(x+a)^{(q-1)(q^{2}+1)}}$

Because $\text{gcd}(2,(q-1)(q^{2}+1))=1$, $g_{3}(x)$ is a permutation
polynomial if and only if $h_{3}(x)=x^{2}(x+a)^{(q-1)(q^{2}+1)}$ permutes
$\mu_{q+1}$. Note $\text{gcd}((q-1)(q^{2}+1),q^{4}-1)=(q-1)(q^{2}+1)$. If
$a\in\mu_{q+1}$, then $x^{(q-1)(q^{2}+1)}+a$ has nonzero roots and thus
$g_{3}(x)$ can not be a permutation polynomial.

Next we study when $h_{3}(x)=x^{2}(x+a)^{(q-1)(q^{2}+1)}$ permutes
$\mu_{q+1}$. Consider:
$\phi(x):\mathbb{F}_{q}\cup\\{\infty\\}\rightarrow\mu_{q+1}$ such that
$\phi(x)=\frac{x+z}{x+z^{q}}$, where
$z\in\mathbb{F}_{q^{2}}\setminus\mathbb{F}_{q}$, and
$\phi^{-1}(x):\mu_{q+1}\rightarrow\mathbb{F}_{q}\cup\\{\infty\\}$ such that
$\phi^{-1}(x)=\frac{z^{q}x+z}{x+1}$. It is easy to check
$\phi^{-1}(\phi(x))=x$. Then $h_{3}(x)$ permutes $\mu_{q+1}$ if and only if
$l_{3}(x)=\phi^{-1}(h_{3}(\phi(x))$ permutes $\mathbb{F}_{q}\cup\\{\infty\\}$.
Here is the diagram illustrating this relation.

${\mu_{q+1}}$${\mu_{q+1}}$${\mathbb{F}_{q}\cup\\{\infty\\}}$${\mathbb{F}_{q}\cup\\{\infty\\}}$$\scriptstyle{h_{3}(x)}$$\scriptstyle{\phi^{-1}(x)}$$\scriptstyle{\phi(x)}$$\scriptstyle{l_{3}(x)}$

Now let us compute $l_{3}(x)$. First, we compute $h_{3}(\phi(x))$, that is

$\displaystyle\begin{aligned}
h_{3}(\phi(x))&=\bigg{(}\frac{x+z}{x+z^{q}}\bigg{)}^{2}\frac{\left(\bigg{(}\frac{x+z}{x+z^{q}}\bigg{)}^{2}+a\right)^{q^{3}+q}}{\left(\bigg{(}\frac{x+z}{x+z^{q}}\bigg{)}^{2}+a\right)^{q^{2}+1}}\\\
&=\frac{a^{q^{3}+q}\bigg{(}\frac{x+z}{x+z^{q}}\bigg{)}^{2}+(a^{q}+a^{q^{3}})\bigg{(}\frac{x+z}{x+z^{q}}\bigg{)}+1}{\bigg{(}\frac{x+z}{x+z^{q}}\bigg{)}^{2}+(a+a^{q^{2}})\bigg{(}\frac{x+z}{x+z^{q}}\bigg{)}+a^{q^{2}+1}}\\\
&=\frac{a^{q^{3}+q}(x+z)^{2}+(a^{q}+a^{q^{3}})(x+z)(x+z^{q})+(x+z^{q})^{2}}{(x+z)^{2}+(a+a^{q^{2}})(x+z)(x+z^{q})+a^{q^{2}+1}(x+z^{q})^{2}}\\\
&=\frac{(a^{q}+1)(a^{q^{3}}+1)x^{2}+(a^{q}+a^{q^{3}})(z+z^{q})x+a^{q^{3}+q}z^{2}+(a^{q}+a^{q^{3}})z^{q+1}+z^{2q}}{(a^{q^{2}}+1)(a+1)x^{2}+(a+a^{q^{2}})(z+z^{q})x+z^{2}+(a+a^{q^{2}})z^{q+1}+a^{q^{2}+1}z^{2q}}.\end{aligned}$
(30)

This gives

$\displaystyle\begin{aligned} l_{3}(x)&=\phi^{-1}(h_{3}(\phi(x)))\\\
&=\frac{z^{q}\frac{(a^{q}+1)(a^{q^{3}}+1)x^{2}+(a^{q}+a^{q^{3}})(z+z^{q})x+a^{q^{3}+q}z^{2}+(a^{q}+a^{q^{3}})z^{q+1}+z^{2q}}{(a^{q^{2}}+1)(a+1)x^{2}+(a+a^{q^{2}})(z+z^{q})x+z^{2}+(a+a^{q^{2}})z^{q+1}+a^{q^{2}+1}z^{2q}}+z}{\frac{(a^{q}+1)(a^{q^{3}}+1)x^{2}+(a^{q}+a^{q^{3}})(z+z^{q})x+a^{q^{3}+q}z^{2}+(a^{q}+a^{q^{3}})z^{q+1}+z^{2q}}{(a^{q^{2}}+1)(a+1)x^{2}+(a+a^{q^{2}})(z+z^{q})x+z^{2}+(a+a^{q^{2}})z^{q+1}+a^{q^{2}+1}z^{2q}}+1}\\\
&=\frac{Ax^{2}+Bx+C}{Dx^{2}+Ex+F}\in\mathbb{F}_{q}(x),\end{aligned}$ (31)

where

$\displaystyle A=z^{q}(a^{q}+1)(a^{q^{3}}+1)+z(a^{q^{2}}+1)(a+1),$ (32)
$\displaystyle B=z^{q}(a^{q}+a^{q^{3}})(z+z^{q})+z(a+a^{q^{2}})(z+z^{q}),$
(33) $\displaystyle
C=z^{q}(a^{q^{3}+q}z^{2}+(a^{q}+a^{q^{3}})z^{q+1}+z^{2q})+z(a^{q^{2}+1}z^{2q}+(a+a^{q^{2}})z^{q+1}+z^{2}),$
(34) $\displaystyle D=(a^{q}+1)(a^{q^{3}}+1)+(a^{q^{2}}+1)(a+1),$ (35)
$\displaystyle E=(a^{q}+a^{q^{3}})(z+z^{q})+(a+a^{q^{2}})(z+z^{q}),$ (36)
$\displaystyle
F=a^{q^{3}+q}z^{2}+(a^{q}+a^{q^{3}})z^{q+1}+z^{2q}+z^{2}+(a+a^{q^{2}})z^{q+1}+a^{q^{2}+1}z^{2q}.$
(37)

If $a\in\mu_{q^{2}-1}$, then
$l_{3}(x)=\frac{((a^{q}+1)^{2}z^{q}+(a+1)^{2}z)x^{2}+z^{q}(a^{2q}z^{2}+z^{2q})+z(a^{2}z^{2q}+z^{2})}{((a^{q}+1)^{2}+(a+1)^{2})x^{2}+(a^{2q}z^{2}+z^{2q}+z^{2}+a^{2}z^{2q})}$
is a composition of degree-one rational function $\frac{Gx+H}{Mx+N}$ and
$x^{2}$, where

$\displaystyle G=(a^{q}+1)^{2}z^{q}+(a+1)^{2}z,$ (38) $\displaystyle
H=z^{q}(a^{2q}z^{2}+z^{2q})+z(a^{2}z^{2q}+z^{2}),$ (39) $\displaystyle
M=(a^{q}+1)^{2}+(a+1)^{2},$ (40) $\displaystyle
N=a^{2q}z^{2}+z^{2q}+z^{2}+a^{2}z^{2q}.$ (41)

Next we show $\frac{Gx+H}{Mx+N}$ is invertible over $\mathbb{F}_{q}(x)$. It
suffices to check $GN-HM\neq 0$. Indeed,

$\displaystyle\begin{aligned} GN-
HM&=(L^{q}z^{q}+Lz)(L^{q}z^{2}+Lz^{2q})+(L+L^{q})(a^{2}z^{2q+1}+z^{3}+z^{3q}+a^{2q}z^{q+2})\\\
&=(L^{q+1}+L^{q}+L)z^{3q}+(L^{2}+a^{2}(L+L^{q}))z^{2q+1}\\\ &\hskip
10.00002pt+(L^{2q}+a^{2q}(L+L^{q}))z^{q+2}+(L^{q+1}+L^{q}+L)z^{3},\\\
\end{aligned}$ (42)

where $L=(a+1)^{2}$.

From Equation (42), we know $(GN-HM)(z)$ is a polynomial, whose degree is
$3q$. We note that we can choose any
$z\in\mathbb{F}_{q^{2}}\setminus\mathbb{F}_{q}$, whose cardinality is
$q^{2}-q$. When $q^{2}-q>3q$, i.e. $q>4$, if all such $z$’s are zeroes of $GN-
HM$, then $(GN-HM)(z)$ is a zero polynomial by the fundamental theorem of
algebra. From the fact that $(GN-HM)(z)$ is a zero polynomial, we have

$\displaystyle\left\\{\begin{array}[]{c}a^{2}(L+L^{q})=L^{2},\\\
L+L^{q}=L^{q+1}.\end{array}\right.$ (45)

Plugging $L=(a+1)^{2}$ into the second equation of (45), we get
$a^{2(q+2)}=1$, which is a contradiction because $a\not\in\mu_{q+1}$.
Thererfore $GN-HM\neq 0$ and thus $l_{3}(x)$ permutes
$\mathbb{F}_{q}\cup\\{\infty\\}$ for $q>4$. Hence $g_{3}(x)$ is a permutation
polynomial when $q>4$. The cases for small $q$’s can be verified directly or
by a computer search.

Conversely, we first prove at least one of $A$ and $D$ in Equation (31) is
nonzero . Assume both $A$ and $D$ are $0$, we have

$\displaystyle\left\\{\begin{array}[]{c}z^{q}(a^{q}+1)(a^{q^{3}}+1)+z(a^{q^{2}}+1)(a+1)=0,\\\
(a^{q}+1)(a^{q^{3}}+1)+(a^{q^{2}}+1)(a+1)=0.\\\ \end{array}\right.$ (48)

From Equation (48) and $z\not\in\mathbb{F}_{q}$, we have $a=1$, which is a
contradiction. It is well known that a degree-two rational function
$f(x)\in\mathbb{F}_{q}(x)$ permutes $\mathbb{P}^{1}(\mathbb{F}_{q})$ if and
only if $q$ is even and $f(x)$ is equivalent to $x^{2}$. Specifically, there
exist some degree one $\mu,\nu\in\mathbb{F}_{q}(x)$ such that $f=\mu\circ
x^{2}\circ\nu$. Applying this result to the permutation rational function
$l_{3}(x)$, we must have $B=E=0$. From $E=0$, we get

$\displaystyle a+a^{q^{2}}=a^{q}+a^{q^{3}}.$ (49)

Plugging it into the equation $B=0$, we get

$\displaystyle(a+a^{q^{2}})(z+z^{q})^{2}=0.$ (50)

From Equation (50), we get $a=a^{q^{2}}$. In other words, $a\in\mu_{q^{2}-1}$,
because $a$ is nonzero. ∎

Finally we prove a nonexistence result over $\mathbb{F}_{q^{4}}$.

######  Theorem 11.

Let $q=2^{n}$, $n$ even, and $n\geq 4$. Then the polynomial

$f_{4}(x)=x^{2q^{3}+2q^{2}+2q+3}+ax$

is not a permutation polynomial over $\mathbb{F}_{q^{4}}$ for any
$a\in\mathbb{F}_{q^{4}}^{*}$.

###### Proof.

By the AGW criterion, we have the following diagram:

${\mathbb{F}_{q^{4}}^{*}}$${\mathbb{F}_{q^{4}}^{*}}$${\mathbb{F}_{q}^{*}}$${\mathbb{F}_{q}^{*}}$$\scriptstyle{f_{4}(x)=x^{2q^{3}+2q^{2}+2q+3}+ax}$$\scriptstyle{x^{q^{3}+q^{2}+q+1}}$$\scriptstyle{x^{q^{3}+q^{2}+q+1}}$$\scriptstyle{g_{4}(x)=x(x^{2}+a)^{q^{3}+q^{2}+q+1}}$

Therefore $f_{4}(x)=x^{2q^{3}+2q^{2}+2q+3}+ax$ is a permutation polynomial if
and only if $g_{4}(x)=x(x^{2}+a)^{q^{3}+q^{2}+q+1}$ permutes
$\mathbb{F}_{q}^{*}$.

Let us consider $G(x)=x^{9}+Ax^{7}+Bx^{5}+Cx^{3}+Dx$, where
$A,B,C,D\in\mathbb{F}_{q}$. Assume $G(x)$ is a permutation polynomial over
$\mathbb{F}_{q}$. Since $\text{gcd}(9,q-1)>1$, by the Carlitz-Wan conjecture,
$G(x)$ is not exceptional. By Lemma 5, if $q^{\frac{1}{4}}\geq 9$, i.e. $q\geq
6561$, then $G(x)$ is exceptional, which is impossible. Hence $q<6561$. By
Hermite’s criterion, $G(x)$ is not a permutation polynomial over
$\mathbb{F}_{4096}$ since $9\mid 4095$. As for $4\leq m<12$, by a computer
search, no permutation polynomials of the form $x^{2q^{3}+2q^{2}+2q+3}+ax$
exist. Hence we complete the proof. ∎

By a computer search, for some $a\in\mathbb{F}_{2^{8}}$, $x^{171}+ax$ can be a
permutation binomial. Hence we have the following corollary:

######  Corollary 12.

Let $q=2^{n}$, $n$ even. Then the polynomial $x^{2q^{3}+2q^{2}+2q+3}+ax$ can
be a permutation binomial over $\mathbb{F}_{q^{4}}$ only when $q=4$.

##  4 Discussion

With these newly constructed permutation binomials and previous results in the
literature, we can classify all permutation binomials of the form $x^{i}+ax$
over $\mathbb{F}_{2^{n}}$, where $n\leq 8$.

For any linearized binomial $x^{2^{j}}+ax$, it is a PP over
$\mathbb{F}_{2^{n}}$ if and only if it has only trivial root. Hence
$x^{2^{j}-1}+a\neq 0$. This is equivalent to say that $a$ is not a
($2^{\gcd(j,n)}-1$)-th power in $\mathbb{F}_{2^{n}}$. Hence we only need to
focus on the non-linearizd PPs over $\mathbb{F}_{2^{n}}$. By a computer
search, when $n=4$, only linearized permutation polynomials exist. For this
reason, the smallest case that allows the non-linearized PPs of this form is
$n=6$.

We note that there are no permutation binomials of the form $x^{i}+ax$ in
$\mathbb{F}_{2^{5}}$, $\mathbb{F}_{2^{7}}$ respectively. Indeed, using
Corollary 3 in [35], we can explain that there is no permutation binomial over
$\mathbb{F}_{2^{5}}$ or $\mathbb{F}_{2^{7}}$ because $31,127$ are Mersenne
primes.

In $\mathbb{F}_{2^{6}}$, we can use Theorem 8 and Corollary 9 or [64] to
explain when $x^{10}+ax$ and $x^{19}+ax$ can be permutation binomials. As for
$x^{22}+ax$, we use the result of [24] to explain. As for the last polynomial
$x^{43}+ax$ in Table 1, we can use Theorem 7 to explain its permutation
behavior.

In $\mathbb{F}_{2^{8}}$, we can use the result in [8] to explain when
$x^{86}+ax$ is a permutation binomial. As for $x^{154}+ax$ and $x^{171}+ax$,
we can use Theorem 10 and Corollary 12 to demonstrate that they are indeed
permutation binomials. Thus we have provided a full explanation of permutation
binomials of the form $x^{i}+ax$ over $\mathbb{F}_{2^{n}}$, where $n\leq 8$.

######  Remark 3.

As for $x^{366}+ax$ over $\mathbb{F}_{2^{9}}$, from the AGW criterion, we know
$x^{366}+ax$ is a permutation binomial over $\mathbb{F}_{2^{9}}$ if and only
if $x(x^{5}+a^{64})(x^{5}+a^{8})(x^{5}+a)$ permutes $\mathbb{F}_{2^{3}}$.
Using $5\times 3\equiv 1\pmod{7}$, the latter is equivalent to
$x^{3}(x+a^{64})(x+a^{8})(x+a)$ permutes $\mathbb{F}_{2^{3}}$. Hence, we can
use the classification of permutation polynomial of degree $6$ [29, 45] or
Hermite’s criterion to obtain conditions on the coefficient $a$ so that
$x^{366}+ax$ permutes $\mathbb{F}_{2^{9}}$. Indeed, $x^{366}+ax$ permutes
$\mathbb{F}_{2^{9}}$ if and only if $a\not\in\mathbb{F}_{2^{3}}$,
$(a^{2}+a^{16}+a^{128})(a^{65}+a^{9}+a^{72})+(a^{130}+a^{18}+a^{144})=0$ and
$(a^{65}+a^{9}+a^{72})+(a^{260}+a^{36}+a^{288})(a+a^{8}+a^{64})=0$, or
$a^{65}+a^{9}+a^{72}=0$ and $\frac{a^{73}}{(a+a^{8}+a^{64})^{3}}$ is a root of
$x^{3}+x+1$ over $\mathbb{F}_{2^{9}}$. Similarly, when $3e\equiv
1\pmod{(q-1)}$, using the classification of permutation polynomial of degree
$6$, we can get similar conditions on $a$ so that $x(x^{e(q^{2}+q+1)}+a)$
permutes $\mathbb{F}_{q^{3}}$.

##  5 Conclusion

In this paper, we gave a full explanation of permutation binomials of the form
$x^{i}+ax$ over $\mathbb{F}_{2^{n}}$ where $n\leq 8$, using new and known
classes of PPs. In particular, we gave three classes of permutation binomials
over $\mathbb{F}_{2^{n}}$ and a nonexistence result. It would be interesting
to follow this path to complete the classification for arbitrary $n$, as well
as give a classification of the form $x^{i}+ax$ over $\mathbb{F}_{p^{n}}$,
where $p$ is an odd prime number.

## References

  * Akbary et al. [2009] A. Akbary, D. Ghioca, Q. Wang, On permutation polynomials of prescribed shape, Finite Fields Appl. 15 (2) (2009) 195–206.
  * Akbary et al. [2011] A. Akbary, D. Ghioca, Q. Wang, On constructing permutations of finite fields, Finite Fields Appl. 17 (1) (2011) 51–67.
  * Akbary and Wang [2005] A. Akbary, Q. Wang, On some permutation polynomials over finite fields, Int. J. Math. Math. Sci. 16 (2005) 2631–2640.
  * Akbary and Wang [2006] A. Akbary, Q. Wang, A generalized Lucas sequence and permutation binomials, Proc. Amer. Math. Soc. 134 (1) (2006) 15–22.
  * Akbary and Wang [2007] A. Akbary, Q. Wang, On polynomials of the form $x^{r}f(x^{(q-1)/l})$, Int. J. Math. Math. Sci. (2007) Art. ID 23408 7pages.
  * Bartoli et al. [2017] D. Bartoli, M. Giulietti, L. Quoos, G. Zini, Complete permutation polynomials from exceptional polynomials, J. Number Theory 176 (2017) 46–66.
  * Bartoli et al. [2016] D. Bartoli, M. Giulietti, G. Zini, On monomial complete permutation polynomials, Finite Fields Appl. 41 (2016) 132–158.
  * Bassalygo and Zinoviev [2015b] L. A. Bassalygo, V. A. Zinoviev, On one class of permutation polynomials over finite fields of characteristic two, in: WCC2015-9th International Workshop on Coding and Cryptography 2015, 2015b.
  * Bassalygo and Zinoviev [2015a] L. A. Bassalygo, V. A. Zinoviev, Permutation and complete permutation polynomials, Finite Fields Appl. 33 (2015a) 198–211.
  * Bhattacharya and Sarkar [2017] S. Bhattacharya, S. Sarkar, On some permutation binomials and trinomials over $\mathbb{F}_{2}^{n}$, Des. Codes Cryptogr. 82 (2017) 149–160.
  * Carlitz [1962] L. Carlitz, Some theorems on permutation polynomials, Bull. Amer. Math. Soc. 68 (2) (1962) 120 – 122.
  * Carlitz and Wells [1966] L. Carlitz, C. Wells, The number of solutions of a special system of equations in a finite field, Acta Arith. 12 (1) (1966) 77–84.
  * Charpin and Kyureghyan [2008] P. Charpin, G. M. Kyureghyan, Cubic monomial bent functions: a subclass of $\mathcal{M}$, SIAM J. Discrete Math. 22 (2) (2008) 650–665.
  * Chou [1988] W. S. Chou, Binomial permutations of finite fields, Bull. Austral. Math. Soc. 38 (3) (1988) 325–327.
  * Cohen and Fried [1995] S. Cohen, M. Fried, Lenstra’s proof of the Carlitz-Wan conjecture on exceptional polynomials: an elementary version, Finite Fields Appl. 1 (3) (1995) 372–375.
  * Ding and Helleseth [2013] C. Ding, T. Helleseth, Optimal ternary cyclic codes from monomials, IEEE Trans. Inf. Theory 59 (9) (2013) 5898–5904.
  * Ding and Yuan [2006] C. Ding, J. Yuan, A family of skew Hadamard difference sets, J. Comb. Theory, Ser. A 113 (7) (2006) 1526–1535.
  * Feng et al. [2019] X. Feng, D. Lin, L. Wang, Q. Wang, Further results on complete permutation monomials over finite fields, Finite Fields Appl. 57 (2019) 47–59.
  * Guralnick and Müller [1997] R. M. Guralnick, P. Müller, Exceptional polynomials of affine type, J. Algebra 194 (2) (1997) 429–454.
  * Hermite [1863] C. Hermite, Sur les Fonctions de Sept Lettres, C.R. Acad. Sci. Paris. 57 (1863) 750–757.
  * Hou [2013] X. Hou, A class of permutation binomials over finite fields, J. Number Theory 133 (10) (2013) 3549–3558.
  * Hou [2015] X. Hou, Permutation polynomials over finite fields — A survey of recent advances, Finite Fields Appl. 32 (2015) 82–119.
  * Hou [2016] X. Hou, Permutation polynomials of of the form $ax+x^{r(q-1)+1}$, in: Contemporary developments in finite fields and applications, World Scientific, 74–101, 2016.
  * Hou and Lappano [2015] X. Hou, S. D. Lappano, Determination of a type of permutation binomials over finite fields, J. Number Theory 147 (2015) 14–23.
  * Hou and Lavorante [2023] X. Hou, V. P. Lavorante, New results on permutation binomials of finite fields, Finite Fields Appl. 88 (2023) 102179.
  * Laigle-Chapuy [2007] Y. Laigle-Chapuy, Permutation polynomials and applications to coding theory, Finite Fields Appl. 13 (1) (2007) 58–70.
  * Lappano [2015] S. D. Lappano, A note regarding permutation binomials over $\mathbb{F}_{q}^{2}$, Finite Fields Appl. 34 (2015) 153–160.
  * Lee and Park [1997] J. B. Lee, Y. H. Park, Some permuting trinomials over finite fields, Acta Math. Sci. 17 (3) (1997) 250–254.
  * Li et al. [2010] J. Li, D. B. Chandler, Q. Xiang, Permutation polynomials of degree 6 or 7 over finite fields of characteristic 2, Finite Fields Appl. 16 (6) (2010) 406–419.
  * Li et al. [2017] K. Li, L. Qu, X. Chen, New classes of permutation binomials and permutation trinomials over finite fields, Finite Fields Appl. 43 (2017) 69–85.
  * Lidi and Mullen [1993] R. Lidi, G. L. Mullen, When does a polynomial over a finite field permute the elements of the field?, II, Amer. Math. Monthly 100 (1) (1993) 71–74.
  * Lidl and Niederreiter [1997] R. Lidl, H. Niederreiter, Finite fields, 20, Cambridge university press, 1997.
  * Liu [2022] X. Liu, Necessary and sufficient conditions of two classes of permutation polynomials, Finite Fields Appl. 77 (2022) 101949.
  * Ma et al. [2017] J. Ma, T. Zhang, T. Feng, G. Ge, Some new results on permutation polynomials over finite fields, Des. Codes Cryptogr. 83 (2017) 425–443.
  * Masuda et al. [2006] A. Masuda, D. Panario, Q. Wang, The number of permutation binomials over $f_{4p+1}$ where $p$ and $4p+1$ are primes, Electron J. Comb. 13 (1) (2006) 65\.
  * Masuda and Zieve [2009] A. Masuda, M. E. Zieve, Permutation binomials over finite fields, Trans. Amer. Math. Soc. 361 (8) (2009) 4169–4180.
  * Masuda et al. [2022] A. M. Masuda, I. M. Rubio, J. Santiago, Permutation binomials of the form $x^{r}(x^{q-1}+a)$ over $\mathbb{F}_{q}^{e}$, Finite Fields Appl. 79 (2022) 102003\.
  * Mollin and Small [1987] R. A. Mollin, C. Small, On permutation polynomials over finite fields, Int. J. Math. Math. Sci. 10 (1987) 535–543.
  * Mullen and Panario [2013] G. L. Mullen, D. Panario, Handbook of Finite Fields, CRC press, 2013\.
  * Niederreiter and Robinson [1982] H. Niederreiter, K. H. Robinson, Complete mappings of finite fields, J. Aust. Math. Soc. A 33 (2) (1982) 197–212.
  * Oliveira and Martínez [2022] J. A. Oliveira, F. B. Martínez, Permutation binomials over finite fields, Discrete Math. 345 (3) (2022) 112732.
  * Park [2005] H. G. Park, On certain binomials over finite fields, J. Appl. Math. Computing 18 (2005) 679–684.
  * Rivest et al. [1978] R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21 (2) (1978) 120–126.
  * Schwenk and Huber [1998] J. Schwenk, K. Huber, Public key encryption and digital signatures based on permutation polynomials, Electron. Lett. 34 (1998) 759–760.
  * Shallue and Wanless [2013] C. J. Shallue, I. M. Wanless, Permutation polynomials and orthomorphism polynomials of degree six, Finite Fields Appl. 20 (2013) 84–92.
  * Sharma and Gupta [2020] R. Sharma, R. Gupta, Determination of a type of permutation binomials and trinomials, Appl. Algebra Eng. Commun. Comput. 31 (1) (2020) 65–86.
  * Small [1990] C. Small, Permutation binomials, International J. Math. Math. Sci. 13 (1990) 337–342.
  * Small [1991] C. Small, Arithmetic of finite fields, vol. 148, CRC Press, 1991.
  * Tu et al. [2014] Z. Tu, X. Zeng, L. Hu, Several classes of complete permutation polynomials, Finite Fields Appl. 25 (2014) 182–193.
  * Tu et al. [2021] Z. Tu, X. Zeng, Y. Jiang, Y. Li, Binomial permutations over finite fields with even characteristic, Des. Codes Cryptogr. 89 (2021) 2869–2888.
  * Tu et al. [2020] Z. Tu, X. Zeng, J. Mao, J. Zhou, Several classes of complete permutation polynomials over finite fields of even characteristic, Finite Fields Appl. 68 (2020) 101737.
  * Turnwald [1988] G. Turnwald, Permutation polynomials of binomial type, Contributions to general algebra 6 (1988) 281–286.
  * Wan [1987] D. Wan, Permutation polynomials over finite fields, Acta Math. Sinica (N.S.) 3 (1987) 1–5.
  * Wan [1994] D. Wan, Permutation binomials over finite fields, Acta Math. Sinica (N.S.) 10 (1994) 30–35.
  * Wan and Lidl [1991] D. Wan, R. Lidl, Permutation polynomials of the form $x^{r}f(x^{(q-1)/d})$ and their group structure, Monatsh. Math. 112 (1991) 149–163.
  * Wang [2002] L. Wang, On permutation polynomials, Finite Fields Appl. 8 (3) (2002) 311–322.
  * Wang [2007] Q. Wang, Cyclotomic mapping permutation polynomials over finite fields, in: Sequences, Subsequences, and Consequences, 119–128, 2007\.
  * Wang [2019] Q. Wang, Polynomials over finite fields: an index approach, Combinatorics and Finite Fields (2019) 319–348.
  * Wu et al. [2014] G. Wu, N. Li, T. Helleseth, Y. Zhang, Some classes of monomial complete permutation polynomials over finite fields of characteristic two, Finite Fields Appl. 28 (2014) 148–165.
  * Wu et al. [2015] G. Wu, N. Li, T. Helleseth, Y. Zhang, Some classes of complete permutation polynomials over $\mathbb{F}_{q}$, Sci. China Math. 58 (10) (2015) 1–14.
  * Xu and Cao [2015] G. Xu, X. Cao, Complete permutation polynomials over finite fields of odd characteristic, Finite Fields Appl. 31 (2015) 228–240.
  * Zieve [2008] M. E. Zieve, Some families of permutation polynomials over finite fields, Int. J. Number Theory 04 (05) (2008) 851–857.
  * Zieve [2009] M. E. Zieve, On some permutation polynomials over $\mathbb{F}_{q}$ of the form $x^{r}h(x^{(q-1)/d})$, Proc. Amer. Math. Soc. 137 (7) (2009) 2209–2216.
  * Zieve [2013a] M. E. Zieve, Permutation polynomials induced from permutations of subfields, and some complete sets of mutually orthogonal latin squares, arXiv preprint arXiv:1312.1325 .
  * Zieve [2013b] M. E. Zieve, Permutation polynomials on $\mathbb{F}_{q}$ induced from bijective Redei functions on subgroups of the multiplicative group of $\mathbb{F}_{q}$, arXiv preprint arXiv:1310.0776 .