# Constructions and Necessities of Some Permutation Polynomials over Finite Fields

Authors: Xiaogang Liu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

LetFq denote the finite field with q elements. Permutation polynomials over finite fields have important applications in many areas of science and engineering such as coding theory, cryptography, and combinatorial design. The study of permutation polynomials has a long history, and many results are obtained in recent years. In this paper, we obtain some further results about the permutation properties of permutation polynomials. Some new classes of permutation polynomials are constructed, and the necessities of some permutation polynomials are studied.


---

## Body

## 1. Introduction

For a prime powerq, let Fq denote the finite field of order q, and Fq∗ the multiplicative group. A polynomial fx∈Fq is called a permutation polynomial (PP) over Fq, if the associated polynomial mapping f:c⟶fc is a permutation of Fq. They have applications in coding theory, cryptography, and combinatorial design theory [1, 2]. Thus, in both theoretical and applied aspects, finding new PPs is of great interest. Permutation polynomials with few terms attract many authors’ attention for their simple algebraic structures. In particular, there are many results about permutation binomials and trinomials [3–5].Permutation polynomials attract peoples’ interest for their extraordinary properties and algebraic forms. Complete permutation polynomial (CPP) is a permutation polynomial such thatfx+x is also a permutation polynomial. Mann introduced CPPs in the construction of orthogonal Latin squares [6]. Orthomorphisms map each maximal subgroup of the additive group of Fq half into itself and half into its complement, and they have a single fixed point and are the same as CPPs in even characteristic. Nonlinear orthomorphisms (or CPPs) are of cryptographic interest, and Mittenthal used them for the design of a nonlinear dynamic substitution device [7, 8]. PPs have been applied in the Lay–Massey scheme, the block cipher SMS4, the stream cipher Loiss [1, 9, 10], the design of Hash functions, quasigroups, and also in the constructions of some cryptographically strong functions [2, 11–14]. In [15–17], the authors investigated the set stability of switched delayed logical networks (SDLNs), the optimal state estimation of finite-field networks (FFNs), and containment problem of finite-field networks (FFNs).A monomialxn permutes Fq if gcdn,q−1=1, and they are the simplest kind of permutation polynomials. For binomials and trinomials, the permutation properties are not so easy to determine. Carlitz studied permutation binomials in 1962 [3]. In [18], Carlitz and Wells found that for q large enough than d, the polynomial fx=xxq−1/d+a might be a permutation polynomial over Fq. Hou and Lappano studied permutation binomials of the forms ax+x3q−2 and ax+x5q−4 [19]. However, only a limited number of constructions are known for PPs. More recent constructions of PPs can be found in [4, 20–31], and the references therein.For two positive integersm and n with m|n, Trmn⋅ denotes the trace function from Fpn to Fpm, that is,(1)Trmnx=x+xpm+xp2m+⋯+xpn/m−1m.Permutation polynomials of the formx+γTrmnxk have been studied for special γ∈Fqn, with even characteristic [32, 33], and for the case n=2, i.e., permutation trinomials [4, 34]. Later, Zheng, Yuan, and Yu investigated permutation polynomials with the form(2)cx−xs+xqs,over Fqn, where s is a positive integer, and c∈Fq [35]. For this, they used the AGW criterion to prove three classes of permutation trinomials. For the fourth class of permutation trinomials, a symbolic computation method related with resultants was used. And, they found a new relation with a class of PPs of the form(3)xqk−x+δs+cx.over Fqn, where δ is arbitrary and c∈Fq. This class of permutation polynomials are related to δ. Based on their relationship, the aforementioned class of permutation trinomials without restriction on δ is derived.In the study of CPPs, Li et al., found that certain polynomials overF2n can have the same permutation properties as axk+bx over F2m for positive divisor m of n such that n/m is odd [36]. They constructed some permutation binomials, and thus more permutation polynomials of the form aTrmnxk+uc+xTrmnx+x+bx can be obtained, and here a,b,c,u∈F2m∗ are constants. They also studied permutation polynomials over Fp2m of the form axpm+bx+hxpm±x, and Niho-type permutation trinomials over Fp2m were constructed.In this paper, some preliminaries are presented first in Section2. In Sections 3 and 4, we construct some new classes of PPs including the following:(a)
In [35], permutation polynomials of the kind x+xs+xqs are proposed, but with all coefficients 1, here we add a variable to the coefficient to investigate more general situations. In Proposition 1, PPs of the kind cx+xs+cqxqs are studied.(b)
In [36], permutation behavior of x22m−1/3+1+bx is studied for odd value m, and here in Proposition 10, all positive values of m will be investigated.(c)
In [37], Xu et al. proposed a class of permutation polynomials of the form x2m+x+δ−s+bx for s,m satisfying 2m+1−s≡2m−1mod22m−1. In Proposition 11, the case of 2m+2−s≡2m−1mod22m−1 is studied.(d)
In Proposition13, a totally new class of PPs x2m+1+b′x2+bx is proposed.(e)
And the PPs in the other propositions are presented in these two sections.In [37], Xu et al. proposed two classes of permutation polynomials of the form x2m+x+δ22m−1+2m−1+bx and x2+x+δ22k−1−2k−1+bx over F22m and F22k, respectively, and sufficient conditions were given. In this work, we investigate the necessities of the above two classes of permutation polynomials, and the necessary conditions are given in Section 5.


## 2. Preliminaries

LetFqn be the finite field which is an extension of Fq of degree n and Fqn∗ denotes its multiplicative group. Use N to denote the norm function from Fqn to Fq, i.e., for x∈Fqn, Nx=x1+q+q2+⋯+qn−1. Let Lx=ax+bxq+xq2 be a linearized polynomial, with a,b∈Fqn∗. Define(4)u=aqbq+1.There is the following result about the number of solutions ofLx over Fq3.Lemma 1 (see [38]).
LetLx=ax+bxq+xq2 with a,b∈Fq3∗. Then Lx has 1 root in Fq3 if and only if 1+Nbuq2+uq+u+1+Na≠0.Lemma 2 (see [39]).
Letq=2k, where k is a positive integer. The quadratic equation x2+ux+v=0, where u,v∈Fq and u≠0, has roots in Fq if and only if Trqv/u2=0.Lemma 3 (see [40]).
For a positive integerm, a,b∈F22m∗ satisfying Tr1nb/a2=0. Then the quadratic equation x2+ax+b=0 has(i)
both solutions in the unit circle if and only ifb=a/a2m and Tr1mb/a2=Tr1m1/a2m+1=1,(ii)
exactly one solution in the unit circle if and only ifb≠a/a2m and 1+b2m+11+a2m+1+b2m+1+a2b2m+a2m+1b=0.Lemma 4 (see [35]).
Letm,k be integers with 0<k<m and l=gcdk,m. Let c∈Fql∗ and gx∈Fqmx. Then gxqk−x+δ+cx permutes Fqm for each δ∈Fqm if and only if hx=gxqk−gx+cx permutes Fqm.Lemma 5 (see [41]).
Letd,r>0 with d|q−1, and let hx∈Fqx. Then fx=xrhxq−1/d permutes Fq if and only if the following two conditions hold:(i)
gcdr,q−1/d=1,(ii)
xrhxq−1/d permutes μd, where μd denotes the d-th root of unity in Fq.
Using the same idea as in [[45], Proposition 3], we can get the following lemma.Lemma 6 (see [24]).
Letm,k be integers with 0<k<m and l=gcdk,m. Let c∈Fql∗ and gx∈Fqmx. Then gxqk+x+δ+cx permutes Fqm for each δ∈Fqm if and only if hx=gxqk+gx+cx permutes Fqm.For each elementx in the finite field F22m, define x¯=x2m. The unit circle of F22m is the set(5)U=η∈F22m:η2m+1=ηη¯=1,which is also denoted by μq+1 occasionally.The following lemma can be verified without much difficulty.Lemma 7 (see [24]).
Each nonzero elementx in the finite fields x has a unique expression of the following form:(6)x=uλ,with u∈F2m∗ and λ∈U.Lemma 8 (see [24]).
Letm be a positive integer, and a,b∈F23m∗. Then the equation the following equation:(7)x2m+ax+b=0,(i)
has at most one possible solutiona22mb2m+a22m+2mb+b22m/a22m+2m+1+1, when a22m+2m+1+1≠0,(ii)
has2m solutions, when a22m+2m+1+1=0 and a22mb2m+a22m+2mb+b22m=0,(iii)
has no solutions, whena22m+2m+1+1=0 and a22mb2m+a22m+2mb+b22m≠0.Proof. Letx be a solution, then(8)x2m=ax+b.Taking the2m power on both sides of the above equation,(9)x22m=a2mx2m+b2m.Substituting equation (8) into the above equation,(10)x22m=a2max+b+b2m.Taking the2m power of the above equation,(11)x23m=a22ma2mx2m+b2m+b22m.Substituting equation (8) into the above equation,(12)x23m=a22ma2max+b+b2m+b22m.Noting thatx23m=x, the above equation can be transformed into(13)a22m+2m+1+1x=a22mb2m+a22m+2mb+b22m.For case (ii), we need to show that there are2m solutions. Taking the 2m power of the right side of equation (13),(14)ab22m+a22m+1b2m+b=0.Then we can find thatx=a22mb2m is a solution of equation (8). Let us consider the equation(15)c2m−1=a.Sincea22m+2m+1=1 and 23m−1=2m−122m+2m+1, the above equation has 2m−1 solutions. For every such c, we can find that c+a22mb2m is a solution of (2).


## 3. Permutation Polynomials That Can be Transformed to the Case of Monomials

In this section, we study the permutation behavior of six kinds of polynomials. Propositions1 and 2 have the property that after some operations the complicated terms can be canceled. Propositions 3–6 have the property that exponents can be simplified. Denote μq+1=x|xq+1=1.Proposition 1.
Letq=2m be even with q≡1mod3, and s=q2+q+1/3. Then(16)fx=cx+xs+cqxqs,and it is a permutation polynomial over Fq2 for c∈Fq2∗ satisfying Tr1mcq+1=0.Proof. It can be found that3|q+2 from the assumption q≡1mod3. Let us rewrite the polynomial fx in the following:(17)fx=cx+xq+2/3q−1+1+cqxqq+2/3+1q−1+1.Setu=q+2/3, equation (83) becomes(18)fx=xc+xq−1u+cqxqu+1q−1.By Lemma5, fx is a permutation polynomial if and only if(19)gx=xc+xu+cqxqu+1q−1permutes μq+1. On the set μq+1, x3u=xq+2=x and gx become(20)gx=xc+xu+cqx−u+1q−1.It is necessary to show that(21)c+xu+cqx−u+1=0has no zeros on μq+1. The above equation can be written as(22)c+xu+cqx2u=0.We can find thatgcdu,q+1=gcdq+2/3,q+1=1. Set z=xu, then equation (22) becomes(23)z2+1cqz+ccq=0.For Lemma3, we have b/a2=cq+1 which lies in Fq. And equation (23) has no solutions in the unit circle by our assumption.Let us make the following transformations forgx on the unit circle μq+1:(24)gx=xcq+x−u+cx−1+uc+xu+cqx−u+1=cqx+x1−u+cxuc+xu+cqx−u+1=cqx3u+x2u+cxuc+xu+cqx2u=xucqx2u+xu+cc+xu+cqx2u=xu.Thus,gx is a permutation of μq+1.Example 1.
Setm=4. Using Magma, it can be verified that(25)fx=cx+x91+c16x1456is a permutation polynomial over F256 for Tr14c17=0.Proposition 2.
Letr,i,m be positive integers with gcdr−i,2m+1=1 and gcdr,i2m−1=1, and b∈F22m∗ satisfying b22m−1/gcdi2m−1,22m−1≠1,b2m+1=1. Then the polynomial(26)fx=xi2m−1+r+bxris a permutation polynomial over F22m∗.Proof. Letgx=xrx+bi2m−1 and S=xi2m−1|x∈F22m∗.It can be verified that the above diagram is commutative. By assumption, we havex+b≠0 for x∈S. So, gx maps S to S. We need to check that gx is bijective on S. For x∈S, it is not difficult to show that(27)x2m+1=1,which means that x2m=x−1. Thus(28)gx=xrx2m+b2mix+bi=xrx−1+b−1ix+bi=xr−ibipermutes S since gcdr−i,2m+1=1.Forx1,x2∈F22m∗ satisfying x1i2m−1=x2i2m−1, the following holds(29)x1x2i2m−1=1.If(30)fx1=fx2,then x1r=x2r. Since gcdr,i2m−1=1, we have x1=x2. That is fx is injective on the set x|xi2m−1=z for z∈S. Using the AGW criterion [42], fx is a permutation over F22m∗.Example 2.
Setm=3,r=4,i=3. Using Magma, it can be verified that the following polynomial:(31)fx=x25+bx4,is a permutation polynomial over F64 for b3≠1,b9=1.
In the following, Propositions3 and 4 are concerned with degree two extensions, but with different exponents and coefficients. Propositions 5 and 6 are concerned with degree three extensions.Proposition 3.
Ler,s,m be positive integers with s>1,gcdr,22m−1=1, and a,δ∈F22m satisfying Tr1ma2m+1δ2m+1/a2m+1+δ2m+1+12=0. Then the polynomial(32)fx=xrxs2m−1+ax2m−1+δ2m+1is a permutation over F22m.Proof. For Lemma5, we have d=2m+1. Since gcdr,22m−1=1, fx is a permutation polynomial if and only if(33)gx=xrxs+ax+δ22m−1permutes the unit circle μ2m+1. We claim that(34)xs+ax+δ=0has no zeros in the unit circle. Otherwise, take the 2m power on both sides of the above equation(35)x−s+a2mx−1+δ2m=0.From the above two equations, we have(36)xsx−s=a2mx−1+δ2max+δ=1,which is equivalent to(37)a2m+δ2mxax+δ=x.After simplification, the above equation can be transformed into(38)aδ2mx2+a2m+1+δ2m+1+1x+a2mδ=0.Thus(39)x2+a2m+1+δ2m+1+1aδ2mx+a2mδaδ2m=0.By Lemma3, the above equation has no zeros in the unit circle since Tr1ma2m+1δ2m+1/a2m+1+δ2m+1+12=0.Now, equation (33) becomes(40)gx=xr,which permutes μ2m+1 since gcdr,22m−1=1.Example 3.
Setr=4,s=3,m=4. Let ω be a primitive element of F256 and δ=ω. Then the polynomial(41)fx=x4x45+ax15+δ17is a permutation polynomial over F256 when Tr14a17δ17/a17+δ17+12=0.Proposition 4.
Letr,s,m be positive integers with gcdr,22m−1=1, and a,δ∈F2m∗ satisfying Tr1maδ=1. Then the polynomial(42)fx=xrx2m−12m+1+ax2m+1+δs2m−1is a permutation polynomial over F22m.Proof. For Lemma5, we have d=2m−1. Since gcdr,22m−1=1, fx is a permutation polynomial if and only if(43)gx=xrx2m−1+ax+δs22m−1permutes F2m∗, which means that(44)x2m−1+ax+δ=0has no zeros in F2m∗. Squaring both sides of the above equation(45)x+a2x2+δ2=0,which is equivalent to(46)x2+1a2x+δ2a2=0.By Lemma2, the above equation has no solutions in F2m.Example 4.
Setm=4,r=4,s=3. Let ω be a primitive element of F256, and δ=w85. Using Magma, it can be verified that(47)fx=x4x136+ax17+δ45is a permutation polynomial when Tr1maδ=1.Proposition 5.
Letr,m,s be positive integers, and a,b∈F23m∗. Then the polynomial(48)fx=xrx2m2m−1+ax2m−1+bs22m+2m+1is a permutation polynomial for the following two cases:(i)
a22m+2m+1+1≠0 and a22mb2m+a22m+2mb+b22m/a22m+2m+1+122m+2m+1≠1,(ii)
a22m+2m+1+1=0 and a22mb2m+a22m+2mb+b22m≠0.
Heregcdr,23m−1=1.Proof. For Lemma5, we have d=22m+2m+1. Since gcdr,23m−1=1, then fx is a permutation polynomial over if and only if(49)gx=xrx2m+ax+b2m−122m+2m+1=xrx2m+ax+bs23m−1permutes μ22m+2m+1. We only need to show that x2m+ax+b23m−1 is nonzero on the set μ22m+2m+1, which can be deduced from Lemma 8.Example 5.
Letr=4,m=3,s=3,b=1. Using Magma, it can be verified that the following polynomial(50)fx=x4x56+ax7+1219is a permutation polynomial over F29 when a73≠1 and a64+a72+1/a7373≠1.Proposition 6.
Letr,s,m be positive integers satisfying gcdr,23m−1=1,gcd3,2m−1=1. Then the polynomial(51)fx=xrx22m2m−1+bx2m2m−1+ax2m−1+δs22m+2m+1is a permutation polynomial over F23m, where a+b+1≠0,δ/a+b+1∈F2m∗, a+b+δ+1≠0 and 1+Nbuq2+uq+u+1+Na≠0. Here u is defined as in (1).Proof. For Lemma5, we have d=22m+2m+1. Since gcdr,23m−1=1, fx is a permutation polynomial over F23m if and only if(52)gx=xrx22m+bx2m+ax+δs23m−1permutes μ22m+2m+1, which is equivalent to(53)x22m+bx2m+ax+δ=0,which has no solutions in μ22m+2m+1.Sincea+b+1≠0,δ/a+b+1∈F2m∗, the above equation has a solution x0=δ/a+b+1 in F2m∗. But gcd3,2m−1=1, and x0 lies in μ22m+2m+1 if and only x0=1. This is contradiction with the assumption that a+b+δ+1≠0.By Lemma1, equation (53) is in fact a permutation polynomial over F23m. It has only one solution x0, which does not belong to the set μ22m+2m+1.Example 6.
Setm=3,b=1,r=4,s=2,δ=1. Then for all values a≠0,1 in F23, using Magma, it can be verified that(54)fx=x4x448+x56+ax7+1146is a permutation polynomial over F29.


## 4. Construction of Permutation Polynomials with Two or More terms

### 4.1. Three Classes of Permutation Polynomials of Degree Three or Four Extensions overFq

In the following, Propositions7–9 are concerned with PPs over field extensions of degrees 3 and 4.Proposition 7.
Letc∈Fq∗, δ∈Fq3. Then fx=gxq−x+δ+cx is a class of permutation polynomials of Fq3 if one of the following conditions holds:(i)
gx=uxq2+uxq+ux, and ux is a polynomial over Fq3,(ii)
gx=xiq2+q+1, and i is a positive integer.Proof. We only prove case (ii), and case (i) can be proved similarly.Due to Lemma4, fx is a permutation polynomial if and only if(55)hx=gxq−gx+cxis a permutation of Fq3. But(56)gxq−gx=xiq2+q+1q−xiq2+q+1=0.That ishx=cx, which is a permutation of Fq3 for c∈Fq∗.Remark 1.
Forfx=gxq−x+δ+cx to be a permutation polynomial over Fq3, gx satisfies gxq=gx. Here we give two explicit expressions of gx.Proposition 8.
Letc∈Fq∗, δ∈Fq4. Then fx=gxq+x+δ+cx is a permutation polynomial if one of the following conditions holds:(i)
gx=c0uxq3+uxq2+uxq+ux, where ux is a polynomial over Fq4 and c0∈Fq4∗ satisfying c0q+c0=0,(ii)
gx=c0xiq3+q2+q+1, where i is a positive integer and c0∈Fq4∗ satisfying c0q+c0=0.Proof. We only consider case (i), and case (ii) can be proved in a similar way.Due to Lemma6, fx is a permutation polynomial if and only if(57)hx=gxq+gx+cxis a permutation of Fq4. But(58)gxq+gx=c0xiq3+q2+q+1q+c0xiq3+q2+q+1=c0+c0qxiq3+q2+q+1=0.That ishx=cx, which is a permutation of Fq4 for c∈Fq∗.Remark 2.
Note that in the above propositionc0∉Fq∗ for odd characteristic.Proposition 9.
For a positive integerm, a fixed δ∈F23m, and c∈F2m∗, the polynomial(59)fx=x2m+x+δ22m+1+cxis a permutation of F23m.Proof. [[43], Proposition 4] says that(60)gx=x2m+x+δ22m+1+xis a permutation of Fq3m. Set x=c0y, with c0∈F2m∗. Then we have(61)gx=gc0y=c0y2m+c0y+δ22m+1+c0y=c02y2m+y+1c0δ22m+1+c0y=c02y2m+y+1c0δ22m+1+1c0y.Sincegx is a permutation for every δ∈Fq3m, setting δ0=1/c0δ,(62)f0y=y2m+y+δ022m+1+1c0yis a permutation of Fq3m for every δ0∈Fq3m. Let c0=1/c.(63)fy=y2m+y+δ022m+1+cyis a permutation of Fq3m for every δ0∈Fq3m.Note that, in Proposition9, c is unconnected with δ. Combining with Lemma 4, the following result is obtained.Corollary 1For a positive integerm and c∈F2m∗, the polynomial(64)gx=x2m22m+1+x22m+1+cxis a permutation of F23m.Example 7.
Setm=3. Using Magma, it can be verified that the following polynomial:(65)gx=x520+x65+cx,is a permutation over F512 for c∈F8∗.


### 4.2. PPs of Typex22m−1/3+1+bx over F22m

The following proposition is concerned with PPs of both odd and even positive values ofm.Proposition 10.
Letm be a positive integer, b∈F22m, and γ is a primitive element of F22m. Then gx=x22m−1/3+1+bx is a permutation polynomial of F22m if and only if(66)b≠γ22m−1/3i′γ3k−k′+i−i′+1γ3k−k′+22m+2/3i−i′+1andb≠γ22m−1/3s,where 0≤i≠i′≤2,0≤s≤2 and 1≤k,k′≤22m−1/3.Proof. We can find that(67)gx=xx22m−1/3+b,and g0=0. Let us consider the nonzero elements in F22m∗.It is not difficult to check that(68)F22m∗=U0∪U1∪U2,with(69)Ui=γ3k+i|1≤k≤22m−13,for i=0,1,2. And we have(70)Ui∩Uj=∅,for i≠j. Then gx maps Ui to the set(71)Vi=γ3k+iγ22m−1/3i+b|1≤k≤22m−13,for i=0,1,2. For fixed i, the elements in Vi are different. Then gx is a permutation polynomial if and only if(72)Vi∩Vj=∅and0∉Vs,for i≠j, which is equivalent to that(73)γ3k+iγ22m−1/3i+b≠γ3k′+i′γ22m−1/3i′+bandb≠γ22m−1/3s,for i≠i′ and 1≤k,k′≤22m−1/3. After simplification, we get the result.Example 8.
Letm=4, and γ be a primitive element of F256. For i=2,i′=1, the polynomial(74)gx=x86+bxis not a permutation polynomial when b=γ85/γ3k−k′+1+1γ3k−k′+86+1, and here 1≤k,k′≤85.


### 4.3. PPs of Typebx+δ2m+1+x2m+cx over F2km

In the following proposition, we study PPs of typebx+δ2m+1+x2m+cx over F2km with constant c.Proposition 11.
For positive integersm,n,k with n=km,2|k. For any δ∈F2n, the polynomial(75)gx=bx+δ2m+1+x2m+cxis a permutation of F2n, where b,c∈F2n\F2 satisfying c=b/b22m.Proof. We prove thatgx=d has at most one solution for any d∈F2n, which is equivalent to(76)x2m+cx+d=bx+δ2m+1,which has a unique solution.It can be verified thatgcd2m+1,2n−1=1 for n=km when 2∤k. Let y=bx+δ, then x=y/b+δ/b. Equation (76) can be rewritten as(77)yb+δb2m+cyb+δb+d=y2m+1,which is equivalent to(78)y2m+1+1b2my2m+cby+δ2mb2m+cδb+d=0.That is,(79)y2m+cby+1b2m+cb2m+1+δ2mb2m+cδb+d=0.So,(80)y+1b2m2m+1=cb2m+1+δ2mb2m+cδb+d,by the assumption. Now, gcd2m+1,2n−1=1 means that y2m+1 is a permutation of F2n. Therefore there is a unique y satisfying equation (80).Example 9.
Letm=2,k=3, then n=6. Let δ∈F26 be any element, b,c∈F26/F2, satisfying c=b48. Using Magma, it can be verified that(81)gx=bx+δ5+x4+cxis a permutation polynomial over F26.


### 4.4. PPs of Typex2m+x+δ−s+bx over F22m

In the following proposition, we consider PPs of typex2m+x+δ−s+bx over F22m.Proposition 12.
Lets,m be positive integers satisfying 2m+2−s≡2m−1mod22m−1, where m is an odd integer. Let δ∈F2m, then the polynomial(82)gx=x2m+x+δ−s+bxis a permutation of F22m, with b∈F2m\F2.Proof. Sincegcd2m+2,2m+1=1, and gcd2m+2,2m−1=gcd3,2m−1=1 for m odd,(83)gcd2m+2,22m−1=1.To prove thatgx is a permutation polynomial, it is enough to prove that for any d∈F22m, gx=d has a unique solution. That is(84)x2m+x+δ−s=bx+dis satisfied by at most one x. By (83), taking the 2m+2th power on both sides of the above equation gives the equivalent equation:(85)x2m+x+δ2m−1=bx+d2m+2.First, if there exists a solutionx such that(86)x2m+x+δ=0,then x=d/b, for the right side of equation (85) is also zero. In this case, the above equation becomes(87)d2mb2m+db+δ=0.Second, let us assume thatx2m+x+δ≠0. Since taking the 2m+1th power, the left side of equation (85) is 1, and the right side is in the unit circle U, that is,(88)bx+d2m+2=λ0,for some λ0∈U. But since gcd2m+2,2m+1=1,(89)bx+d=λ,for some λ∈U. Thus(90)bx+d2m+2=λ2m+2=λ=bx+d.And equation (85) can be rewritten as(91)x2m+x+δ2m−1=bx+d.Sinceδ2m=δ, the left side of the above equation becomes(92)x2m+x+δ2mx2m+x+δ=1.So, we havex=d+1/b.Now, the above two situations can be summarized. For every elementd∈F22m, if d satisfies equation (87), there are two possibilities for the values of x as considered above. But x=d+1/b is not the solution. For substituting it into equation (85), the left side becomes(93)d2mb2m+db+δ+1b2m+1b2m−1=1b2m+1b2m−1=0.It is not equal to the right side which now becomes 1. Ifd does not satisfy equation (87), and if x is a solution of equation (85), then x2m+x+δ≠0. The second situation tells us that the only solution is x=d+1/b.Example 10.
Setm=3,s=6. Let δ∈F23 be any element, and b∈F23\F2. Using Magma, it can be verified that(94)gx=x8+x+δ57+bxis a permutation polynomial over F26.


### 4.5. PPs of Typex2m+1+b′x2+bx over F22m

In the following proposition, we consider PPs of typex2m+1+b′x2+bx over F22m.Proposition 13.
For the finite fieldF22m, let b′∈U be in the unit circle, and b∉F2m satisfying b22m−1b′3=1. Then the linearized polynomial(95)gx=x2m+1+b′x2+bxis a permutation polynomial of F22m.Proof. By the assumption, it can be checked that(96)b′≠b1−2m.Otherwise fromb22m−1b′3=1, we have b2m−1=1, contradiction with the condition that b∉F2m.Sincegx is a linearized polynomial; to verify that it is a permutation polynomial, it is necessary to check that(97)gx=x2m+1+b′x2+bx=0has only the zero solution. There are two situations to be considered.First assume thatx∈F2m∗ is a solution of (97), and then(98)gx=x2m+1+b′x2+bx=x2+b′x2+bx=0.That is,(99)1+b′x+b=0.Ifb′=1, the above equation becomes b=0, contradiction. So, let us assume that b′≠1, then(100)x=b1+b′.But we havex∈F2m∗, that is, x2m=x, and thus(101)b2m1+b′2m=b1+b′.So,(102)b2mb′1+b′=b1+b′,which implies that(103)b′=b1−2m,contradiction with equation (96).Second let us assume thatx∈F22mF2m; by Lemma 7, we can write(104)x=uλ.with u∈F2m∗ and λ∈U. Substituting the above x into equation (97),(105)gx=x2m+1+b′x2+bx=u21λ2+b′u2λ2+buλ=0.That is,(106)u1λ2+b′uλ2+bλ=u1λ2+b′λ2+bλ=0.Ifλ4=1/b′=b′2m. The above equation becomes bλ=0, contradiction. So, λ4≠1/b′; that is,(107)1λ2+b′λ2≠0.Then from equation (106),(108)u=bλb′λ2+1/λ2.Sinceu∈F2m∗, we have that u2m=u. The above equation becomes(109)bλb′λ2+1/λ2=b2mλ2mb′2mλ2m+1+1/λ2m+1=b2m1/λb′2m1/λ2+λ2.That is,(110)bλ3b′λ4+1=b2mλb′2m+λ4⟺bλ2b′λ4+1=b2mb′2m+λ4,which can be rewritten as(111)bλ6+bb′2mλ2=b′b2mλ4+b2m⟺λ6+b′b2m−1λ4+b′2mλ2+b2m−1=0.Letλ0=λ2; equation (111) can be transformed into(112)λ03+b′b2m−1λ02+b′2mλ0+b2m−1=0.Take derivative of the above equation;(113)λ02+b′2m=0.Substitutingλ02=b′2m into equation (112),(114)b′2mλ0+b′2m+1b2m−1+b′2mλ0+b2m−1=b2m−1+b2m−1=0.That is,λ0=b′2m−1 is a double root of (21), which has three roots at most counting multiplicity. But,(115)λ4=λ02=b′2m,contradiction with equation (107).The third root of (112) is(116)λ1=b2m−1b′2m=b2m−1b′.So(117)λ2=λ1=b2m−1b′⟺λ4=b22m−1b′2.And equation (106) becomes(118)u1+b′λ4λ2+bλ=u1+b22m−1b′3λ2+bλ=bλ=0,by assumption, contradiction.Example 11.
Setm=4. Let b′∈U be any element of the unit circle in F28\F24, b∈F28\F24 satisfying b30b′3=1. Using Magma, it can be verified that(119)gx=x32+b′x2+bxis a permutation polynomial over F28.


### 4.6. PPs of Typexrxq−1+a over Fqe

In the following proposition, we study PPs of typexrxq−1+a over Fqe.Proposition 14.
LetFq be the finite field with q elements, then(120)gx=xrxq−1+ais a permutation polynomial over Fqe for r=1,qe−1+qe−2+⋯+q2+1. Here a∈Fqe∗ satisfying aqe−1+qe−2+⋯+q+1≠−1e, and gcd (e-1, q-1) = 1.Proof. This can be obtained using Lemma5.Example 12.
Letq=5,e=4, and ω be a primitive root of the finite field F54, then r=1,q3+q2+1=151. Using Magma, it can be verified that for a=wi, with 1≤i≤623,i≠0mod4,(121)gx=xrx4+ais a permutation polynomial over F54.


## 4.1. Three Classes of Permutation Polynomials of Degree Three or Four Extensions overFq

In the following, Propositions7–9 are concerned with PPs over field extensions of degrees 3 and 4.Proposition 7.
Letc∈Fq∗, δ∈Fq3. Then fx=gxq−x+δ+cx is a class of permutation polynomials of Fq3 if one of the following conditions holds:(i)
gx=uxq2+uxq+ux, and ux is a polynomial over Fq3,(ii)
gx=xiq2+q+1, and i is a positive integer.Proof. We only prove case (ii), and case (i) can be proved similarly.Due to Lemma4, fx is a permutation polynomial if and only if(55)hx=gxq−gx+cxis a permutation of Fq3. But(56)gxq−gx=xiq2+q+1q−xiq2+q+1=0.That ishx=cx, which is a permutation of Fq3 for c∈Fq∗.Remark 1.
Forfx=gxq−x+δ+cx to be a permutation polynomial over Fq3, gx satisfies gxq=gx. Here we give two explicit expressions of gx.Proposition 8.
Letc∈Fq∗, δ∈Fq4. Then fx=gxq+x+δ+cx is a permutation polynomial if one of the following conditions holds:(i)
gx=c0uxq3+uxq2+uxq+ux, where ux is a polynomial over Fq4 and c0∈Fq4∗ satisfying c0q+c0=0,(ii)
gx=c0xiq3+q2+q+1, where i is a positive integer and c0∈Fq4∗ satisfying c0q+c0=0.Proof. We only consider case (i), and case (ii) can be proved in a similar way.Due to Lemma6, fx is a permutation polynomial if and only if(57)hx=gxq+gx+cxis a permutation of Fq4. But(58)gxq+gx=c0xiq3+q2+q+1q+c0xiq3+q2+q+1=c0+c0qxiq3+q2+q+1=0.That ishx=cx, which is a permutation of Fq4 for c∈Fq∗.Remark 2.
Note that in the above propositionc0∉Fq∗ for odd characteristic.Proposition 9.
For a positive integerm, a fixed δ∈F23m, and c∈F2m∗, the polynomial(59)fx=x2m+x+δ22m+1+cxis a permutation of F23m.Proof. [[43], Proposition 4] says that(60)gx=x2m+x+δ22m+1+xis a permutation of Fq3m. Set x=c0y, with c0∈F2m∗. Then we have(61)gx=gc0y=c0y2m+c0y+δ22m+1+c0y=c02y2m+y+1c0δ22m+1+c0y=c02y2m+y+1c0δ22m+1+1c0y.Sincegx is a permutation for every δ∈Fq3m, setting δ0=1/c0δ,(62)f0y=y2m+y+δ022m+1+1c0yis a permutation of Fq3m for every δ0∈Fq3m. Let c0=1/c.(63)fy=y2m+y+δ022m+1+cyis a permutation of Fq3m for every δ0∈Fq3m.Note that, in Proposition9, c is unconnected with δ. Combining with Lemma 4, the following result is obtained.Corollary 1For a positive integerm and c∈F2m∗, the polynomial(64)gx=x2m22m+1+x22m+1+cxis a permutation of F23m.Example 7.
Setm=3. Using Magma, it can be verified that the following polynomial:(65)gx=x520+x65+cx,is a permutation over F512 for c∈F8∗.


## 4.2. PPs of Typex22m−1/3+1+bx over F22m

The following proposition is concerned with PPs of both odd and even positive values ofm.Proposition 10.
Letm be a positive integer, b∈F22m, and γ is a primitive element of F22m. Then gx=x22m−1/3+1+bx is a permutation polynomial of F22m if and only if(66)b≠γ22m−1/3i′γ3k−k′+i−i′+1γ3k−k′+22m+2/3i−i′+1andb≠γ22m−1/3s,where 0≤i≠i′≤2,0≤s≤2 and 1≤k,k′≤22m−1/3.Proof. We can find that(67)gx=xx22m−1/3+b,and g0=0. Let us consider the nonzero elements in F22m∗.It is not difficult to check that(68)F22m∗=U0∪U1∪U2,with(69)Ui=γ3k+i|1≤k≤22m−13,for i=0,1,2. And we have(70)Ui∩Uj=∅,for i≠j. Then gx maps Ui to the set(71)Vi=γ3k+iγ22m−1/3i+b|1≤k≤22m−13,for i=0,1,2. For fixed i, the elements in Vi are different. Then gx is a permutation polynomial if and only if(72)Vi∩Vj=∅and0∉Vs,for i≠j, which is equivalent to that(73)γ3k+iγ22m−1/3i+b≠γ3k′+i′γ22m−1/3i′+bandb≠γ22m−1/3s,for i≠i′ and 1≤k,k′≤22m−1/3. After simplification, we get the result.Example 8.
Letm=4, and γ be a primitive element of F256. For i=2,i′=1, the polynomial(74)gx=x86+bxis not a permutation polynomial when b=γ85/γ3k−k′+1+1γ3k−k′+86+1, and here 1≤k,k′≤85.


## 4.3. PPs of Typebx+δ2m+1+x2m+cx over F2km

In the following proposition, we study PPs of typebx+δ2m+1+x2m+cx over F2km with constant c.Proposition 11.
For positive integersm,n,k with n=km,2|k. For any δ∈F2n, the polynomial(75)gx=bx+δ2m+1+x2m+cxis a permutation of F2n, where b,c∈F2n\F2 satisfying c=b/b22m.Proof. We prove thatgx=d has at most one solution for any d∈F2n, which is equivalent to(76)x2m+cx+d=bx+δ2m+1,which has a unique solution.It can be verified thatgcd2m+1,2n−1=1 for n=km when 2∤k. Let y=bx+δ, then x=y/b+δ/b. Equation (76) can be rewritten as(77)yb+δb2m+cyb+δb+d=y2m+1,which is equivalent to(78)y2m+1+1b2my2m+cby+δ2mb2m+cδb+d=0.That is,(79)y2m+cby+1b2m+cb2m+1+δ2mb2m+cδb+d=0.So,(80)y+1b2m2m+1=cb2m+1+δ2mb2m+cδb+d,by the assumption. Now, gcd2m+1,2n−1=1 means that y2m+1 is a permutation of F2n. Therefore there is a unique y satisfying equation (80).Example 9.
Letm=2,k=3, then n=6. Let δ∈F26 be any element, b,c∈F26/F2, satisfying c=b48. Using Magma, it can be verified that(81)gx=bx+δ5+x4+cxis a permutation polynomial over F26.


## 4.4. PPs of Typex2m+x+δ−s+bx over F22m

In the following proposition, we consider PPs of typex2m+x+δ−s+bx over F22m.Proposition 12.
Lets,m be positive integers satisfying 2m+2−s≡2m−1mod22m−1, where m is an odd integer. Let δ∈F2m, then the polynomial(82)gx=x2m+x+δ−s+bxis a permutation of F22m, with b∈F2m\F2.Proof. Sincegcd2m+2,2m+1=1, and gcd2m+2,2m−1=gcd3,2m−1=1 for m odd,(83)gcd2m+2,22m−1=1.To prove thatgx is a permutation polynomial, it is enough to prove that for any d∈F22m, gx=d has a unique solution. That is(84)x2m+x+δ−s=bx+dis satisfied by at most one x. By (83), taking the 2m+2th power on both sides of the above equation gives the equivalent equation:(85)x2m+x+δ2m−1=bx+d2m+2.First, if there exists a solutionx such that(86)x2m+x+δ=0,then x=d/b, for the right side of equation (85) is also zero. In this case, the above equation becomes(87)d2mb2m+db+δ=0.Second, let us assume thatx2m+x+δ≠0. Since taking the 2m+1th power, the left side of equation (85) is 1, and the right side is in the unit circle U, that is,(88)bx+d2m+2=λ0,for some λ0∈U. But since gcd2m+2,2m+1=1,(89)bx+d=λ,for some λ∈U. Thus(90)bx+d2m+2=λ2m+2=λ=bx+d.And equation (85) can be rewritten as(91)x2m+x+δ2m−1=bx+d.Sinceδ2m=δ, the left side of the above equation becomes(92)x2m+x+δ2mx2m+x+δ=1.So, we havex=d+1/b.Now, the above two situations can be summarized. For every elementd∈F22m, if d satisfies equation (87), there are two possibilities for the values of x as considered above. But x=d+1/b is not the solution. For substituting it into equation (85), the left side becomes(93)d2mb2m+db+δ+1b2m+1b2m−1=1b2m+1b2m−1=0.It is not equal to the right side which now becomes 1. Ifd does not satisfy equation (87), and if x is a solution of equation (85), then x2m+x+δ≠0. The second situation tells us that the only solution is x=d+1/b.Example 10.
Setm=3,s=6. Let δ∈F23 be any element, and b∈F23\F2. Using Magma, it can be verified that(94)gx=x8+x+δ57+bxis a permutation polynomial over F26.


## 4.5. PPs of Typex2m+1+b′x2+bx over F22m

In the following proposition, we consider PPs of typex2m+1+b′x2+bx over F22m.Proposition 13.
For the finite fieldF22m, let b′∈U be in the unit circle, and b∉F2m satisfying b22m−1b′3=1. Then the linearized polynomial(95)gx=x2m+1+b′x2+bxis a permutation polynomial of F22m.Proof. By the assumption, it can be checked that(96)b′≠b1−2m.Otherwise fromb22m−1b′3=1, we have b2m−1=1, contradiction with the condition that b∉F2m.Sincegx is a linearized polynomial; to verify that it is a permutation polynomial, it is necessary to check that(97)gx=x2m+1+b′x2+bx=0has only the zero solution. There are two situations to be considered.First assume thatx∈F2m∗ is a solution of (97), and then(98)gx=x2m+1+b′x2+bx=x2+b′x2+bx=0.That is,(99)1+b′x+b=0.Ifb′=1, the above equation becomes b=0, contradiction. So, let us assume that b′≠1, then(100)x=b1+b′.But we havex∈F2m∗, that is, x2m=x, and thus(101)b2m1+b′2m=b1+b′.So,(102)b2mb′1+b′=b1+b′,which implies that(103)b′=b1−2m,contradiction with equation (96).Second let us assume thatx∈F22mF2m; by Lemma 7, we can write(104)x=uλ.with u∈F2m∗ and λ∈U. Substituting the above x into equation (97),(105)gx=x2m+1+b′x2+bx=u21λ2+b′u2λ2+buλ=0.That is,(106)u1λ2+b′uλ2+bλ=u1λ2+b′λ2+bλ=0.Ifλ4=1/b′=b′2m. The above equation becomes bλ=0, contradiction. So, λ4≠1/b′; that is,(107)1λ2+b′λ2≠0.Then from equation (106),(108)u=bλb′λ2+1/λ2.Sinceu∈F2m∗, we have that u2m=u. The above equation becomes(109)bλb′λ2+1/λ2=b2mλ2mb′2mλ2m+1+1/λ2m+1=b2m1/λb′2m1/λ2+λ2.That is,(110)bλ3b′λ4+1=b2mλb′2m+λ4⟺bλ2b′λ4+1=b2mb′2m+λ4,which can be rewritten as(111)bλ6+bb′2mλ2=b′b2mλ4+b2m⟺λ6+b′b2m−1λ4+b′2mλ2+b2m−1=0.Letλ0=λ2; equation (111) can be transformed into(112)λ03+b′b2m−1λ02+b′2mλ0+b2m−1=0.Take derivative of the above equation;(113)λ02+b′2m=0.Substitutingλ02=b′2m into equation (112),(114)b′2mλ0+b′2m+1b2m−1+b′2mλ0+b2m−1=b2m−1+b2m−1=0.That is,λ0=b′2m−1 is a double root of (21), which has three roots at most counting multiplicity. But,(115)λ4=λ02=b′2m,contradiction with equation (107).The third root of (112) is(116)λ1=b2m−1b′2m=b2m−1b′.So(117)λ2=λ1=b2m−1b′⟺λ4=b22m−1b′2.And equation (106) becomes(118)u1+b′λ4λ2+bλ=u1+b22m−1b′3λ2+bλ=bλ=0,by assumption, contradiction.Example 11.
Setm=4. Let b′∈U be any element of the unit circle in F28\F24, b∈F28\F24 satisfying b30b′3=1. Using Magma, it can be verified that(119)gx=x32+b′x2+bxis a permutation polynomial over F28.


## 4.6. PPs of Typexrxq−1+a over Fqe

In the following proposition, we study PPs of typexrxq−1+a over Fqe.Proposition 14.
LetFq be the finite field with q elements, then(120)gx=xrxq−1+ais a permutation polynomial over Fqe for r=1,qe−1+qe−2+⋯+q2+1. Here a∈Fqe∗ satisfying aqe−1+qe−2+⋯+q+1≠−1e, and gcd (e-1, q-1) = 1.Proof. This can be obtained using Lemma5.Example 12.
Letq=5,e=4, and ω be a primitive root of the finite field F54, then r=1,q3+q2+1=151. Using Magma, it can be verified that for a=wi, with 1≤i≤623,i≠0mod4,(121)gx=xrx4+ais a permutation polynomial over F54.


## 5. Necessities of Two Kinds of Permutation Polynomials

In this section, we investigate the necessities of two classes of permutation polynomials studied in [37], where the sufficient conditions are given.


### 5.1. PPs of Typex2m+x+δ22m−1+2m−1+bx over F22m

In [[42], Proposition 10], X. Xu et al. proposed a class of permutation polynomials of the form x2m+x+δ22m−1+2m−1+bx over F22m, and sufficient conditions were given. In the following proposition, we consider its necessary conditions.Proposition 15.
For a positive integerm and a fixed δ∈F22m with Trm2mδ≠0, let(122)gx=x2m+x+δ22m−1+2m−1+bx,where b∈F22m. When b∉F2m, gx is permutation polynomial if and only if b+bm=b2m+1.Proof. As pointed out at the beginning of this subsection, ([42], Proposition 10) gives the sufficiency verification. Now let us consider the necessity.Assume thatgx is a permutation polynomial. Then for every d∈F22m, gx=d has a unique solution. That is,(123)x2m+x+δ22m−1+2m−1+bx=dhas at most one possible root in F22m. Squaring both sides of the above equation, we get the following equivalent equation(124)x2m+x+δ22m+2m+b2x2=d2.That is,(125)x2m+x+δx2m+x+δ2m=b2x2+d2,which can be transformed into(126)x2m+x2+δ+δ2mx2m+x+δ2m+1=b2x2+d2,which implies that(127)x2m+1+δ+δ2mx2m+b2+1x2+δ+δ2mx+δ2m+1+d2=0has a unique solution in F22m.Then forx1≠x2∈F22m with x1 a solution of equation (127), the following equation:(128)x22m+1+δ+δ2mx22m+b2+1x22+δ+δ2mx2+δ2m+1+d2=0,cannot hold. Adding the above two equations,(129)x1+x22m+1+δ+δ2mx1+x22m+b2+1x1+x22+δ+δ2mx1+x2=0does not hold for any x2 different from x1. Now let y=x1+x2. With x1 fixed and x2 varying, y can be any nonzero element of the finite field F22m. So,(130)y2m+1+δ+δ2my2m+b2+1y2+δ+δ2my=0has only the solution zero in F22m, and this is from the assumption that gx is a permutation polynomial.If a nonzero solutiony∈F22m of equation (130) exists. Taking the 2mth power,(131)y2+δ+δ2my+b2m+1+1y2m+1+δ+δ2my2m=0.Adding equations (130) and (131),(132)b2m+1y2m+1+b2y2=b2y22m+b2y2=0.Thus,(133)by2m+by=0,that is, by lies in the field F2m. By Lemma 7, we can write(134)b=c0λ0,for some fixed c0∈F2m\0, and λ0∈U the unit circle. If y is written in the following form:(135)y=cλ,for c∈F2m and λ∈U. Since by∈F2m, we must have λ=λ0. That is,(136)y=cλ0,for some c∈F2m\0.Substituting (134) and (136) into equation (130),(137)c2λ02+δ+δ2mcλ0+c02λ02+1c2λ02+δ+δ2mcλ0=0.Dividingc on both sides of the above equation,(138)cλ02+δ+δ2m1λ0+c02λ02+1cλ02+δ+δ2mλ0=0,which can be transformed into(139)c02+λ02+1λ02c=δ+δ2m1λ0+δ+δ2mλ0.By our assumption, equation (130) has no nonzero solution; then(140)c02+λ02+1λ02=0,which is equivalent to(141)c0=λ0+1λ0,for some λ0≠1 in U, because b∉F2m. By equation (134),(142)b=1+1λ02,That is,(143)b=1+1λ,for some λ∈U\1. So, we have(144)b2m+1=1+1λ1+λ=1λ+λ.And(145)b2m+b=1+λ+1+1λ=1λ+λ,which implies that(146)b2m+b=b2m+1,that is, the necessity of our proposition.Example 13.
Letm=4, δ∈F28 with Trm2mδ≠0. Using Magma, it can be verified that for b∈F28\F24,(147)gx=x16+x+δ136+bxis not a permutation polynomial over F28 when b16+b≠b17.


### 5.2. PPs of Typex2+x+δ22k−1−2k−1+bx over F22k

In [[42], Proposition 6], Xu et al. proposed a class of permutation polynomials of the form x2+x+δ22k−1−2k−1+bx over F22k, and sufficient conditions are given. In the following proposition, we consider its necessary conditions.Proposition 16.
For nonnegative integersn,k with n=2k,k>1, let δ∈F2n with Tr1nδ=1. Then the polynomial(148)gx=x2+x+δ22k−1−2k−1+bxis a permutation of F2n if and only if b∈F2k\0.Proof. The sufficiency is given in [[42], Proposition 6]. In the following, we only consider the necessity.Assume thatb∉F2k and gx is a PP.SinceTr1nδ=1, x2+x+δ is always nonzero by Lemma 2. For any d∈F2n, the following equation:(149)x2+x+δ22k−1−2k−1+bx=d,has only one solution, which can be transformed into(150)x2+x+δ22k−1−2k−1=bx+d.Taking the2k+1th power on both sides of the above equation,(151)1=bx+d2k+1.So,bx+d=λ; that is,(152)x=λ+db,for some element λ in the unit circle U. Squaring both sides of equation (150)(153)x2+x+δ1−2k=bx+d2,that is,(154)x2+x+δx2k+1+x2k+δ2k=λ2,which is equivalent to(155)x2+x+δ=λ2x2k+1+x2k+δ2k.Substituting (152) into the above equation,(156)1b2+d2k+1b2k+1+d2kb2k+δ2kλ2+1b+1b2kλ+d2b2+db+1b2k+1+δ=0.We can choosed such that(157)1b2+d2k+1b2k+1+d2kb2k+δ2k≠0.Sincegx is a permutation polynomial, there must exists λ1 in the unit circle U, satisfying equation (156). Then(158)x1=λ1+dbsatisfies equation (153), and in fact gx=d, since they are equivalent. Equation (156) can be transformed into(159)λ2+1/b+1/b2k1/b2+d2k+1/b2k+1+d2k/b2k+δ2kλ+1/b2+d2k+1/b2k+1+d2k/b2k+δ2k2k1/b2+d2k+1/b2k+1+d2k/b2k+δ2k=0.Since1/b2+d2k+1/b2k+1+d2k/b2k+δ2k2k/1/b2+d2k+1/b2k+1+d2k/b2k+δ2k is in the unit circle, the other root of equation (156), which we denote λ2, is also in the unit circle U. And(160)λ1≠λ2,since λ1+λ2=1/b+1/b2k≠0 for b∉F2k.Now, for equation (152), set(161)x2=λ2+db.Thenx2 satisfies equation (153) also, that is, gx=d has two solutions x1,x2 for such d, contradiction.Example 14.
Setk=4; then n=8. Let δ∈F2n with Trδ=1. Using Magma, it can be verified that, for b∈F2n\F2k,(162)gx=x2+x+δ120+bxis not a permutation polynomial over F28.


## 5.1. PPs of Typex2m+x+δ22m−1+2m−1+bx over F22m

In [[42], Proposition 10], X. Xu et al. proposed a class of permutation polynomials of the form x2m+x+δ22m−1+2m−1+bx over F22m, and sufficient conditions were given. In the following proposition, we consider its necessary conditions.Proposition 15.
For a positive integerm and a fixed δ∈F22m with Trm2mδ≠0, let(122)gx=x2m+x+δ22m−1+2m−1+bx,where b∈F22m. When b∉F2m, gx is permutation polynomial if and only if b+bm=b2m+1.Proof. As pointed out at the beginning of this subsection, ([42], Proposition 10) gives the sufficiency verification. Now let us consider the necessity.Assume thatgx is a permutation polynomial. Then for every d∈F22m, gx=d has a unique solution. That is,(123)x2m+x+δ22m−1+2m−1+bx=dhas at most one possible root in F22m. Squaring both sides of the above equation, we get the following equivalent equation(124)x2m+x+δ22m+2m+b2x2=d2.That is,(125)x2m+x+δx2m+x+δ2m=b2x2+d2,which can be transformed into(126)x2m+x2+δ+δ2mx2m+x+δ2m+1=b2x2+d2,which implies that(127)x2m+1+δ+δ2mx2m+b2+1x2+δ+δ2mx+δ2m+1+d2=0has a unique solution in F22m.Then forx1≠x2∈F22m with x1 a solution of equation (127), the following equation:(128)x22m+1+δ+δ2mx22m+b2+1x22+δ+δ2mx2+δ2m+1+d2=0,cannot hold. Adding the above two equations,(129)x1+x22m+1+δ+δ2mx1+x22m+b2+1x1+x22+δ+δ2mx1+x2=0does not hold for any x2 different from x1. Now let y=x1+x2. With x1 fixed and x2 varying, y can be any nonzero element of the finite field F22m. So,(130)y2m+1+δ+δ2my2m+b2+1y2+δ+δ2my=0has only the solution zero in F22m, and this is from the assumption that gx is a permutation polynomial.If a nonzero solutiony∈F22m of equation (130) exists. Taking the 2mth power,(131)y2+δ+δ2my+b2m+1+1y2m+1+δ+δ2my2m=0.Adding equations (130) and (131),(132)b2m+1y2m+1+b2y2=b2y22m+b2y2=0.Thus,(133)by2m+by=0,that is, by lies in the field F2m. By Lemma 7, we can write(134)b=c0λ0,for some fixed c0∈F2m\0, and λ0∈U the unit circle. If y is written in the following form:(135)y=cλ,for c∈F2m and λ∈U. Since by∈F2m, we must have λ=λ0. That is,(136)y=cλ0,for some c∈F2m\0.Substituting (134) and (136) into equation (130),(137)c2λ02+δ+δ2mcλ0+c02λ02+1c2λ02+δ+δ2mcλ0=0.Dividingc on both sides of the above equation,(138)cλ02+δ+δ2m1λ0+c02λ02+1cλ02+δ+δ2mλ0=0,which can be transformed into(139)c02+λ02+1λ02c=δ+δ2m1λ0+δ+δ2mλ0.By our assumption, equation (130) has no nonzero solution; then(140)c02+λ02+1λ02=0,which is equivalent to(141)c0=λ0+1λ0,for some λ0≠1 in U, because b∉F2m. By equation (134),(142)b=1+1λ02,That is,(143)b=1+1λ,for some λ∈U\1. So, we have(144)b2m+1=1+1λ1+λ=1λ+λ.And(145)b2m+b=1+λ+1+1λ=1λ+λ,which implies that(146)b2m+b=b2m+1,that is, the necessity of our proposition.Example 13.
Letm=4, δ∈F28 with Trm2mδ≠0. Using Magma, it can be verified that for b∈F28\F24,(147)gx=x16+x+δ136+bxis not a permutation polynomial over F28 when b16+b≠b17.


## 5.2. PPs of Typex2+x+δ22k−1−2k−1+bx over F22k

In [[42], Proposition 6], Xu et al. proposed a class of permutation polynomials of the form x2+x+δ22k−1−2k−1+bx over F22k, and sufficient conditions are given. In the following proposition, we consider its necessary conditions.Proposition 16.
For nonnegative integersn,k with n=2k,k>1, let δ∈F2n with Tr1nδ=1. Then the polynomial(148)gx=x2+x+δ22k−1−2k−1+bxis a permutation of F2n if and only if b∈F2k\0.Proof. The sufficiency is given in [[42], Proposition 6]. In the following, we only consider the necessity.Assume thatb∉F2k and gx is a PP.SinceTr1nδ=1, x2+x+δ is always nonzero by Lemma 2. For any d∈F2n, the following equation:(149)x2+x+δ22k−1−2k−1+bx=d,has only one solution, which can be transformed into(150)x2+x+δ22k−1−2k−1=bx+d.Taking the2k+1th power on both sides of the above equation,(151)1=bx+d2k+1.So,bx+d=λ; that is,(152)x=λ+db,for some element λ in the unit circle U. Squaring both sides of equation (150)(153)x2+x+δ1−2k=bx+d2,that is,(154)x2+x+δx2k+1+x2k+δ2k=λ2,which is equivalent to(155)x2+x+δ=λ2x2k+1+x2k+δ2k.Substituting (152) into the above equation,(156)1b2+d2k+1b2k+1+d2kb2k+δ2kλ2+1b+1b2kλ+d2b2+db+1b2k+1+δ=0.We can choosed such that(157)1b2+d2k+1b2k+1+d2kb2k+δ2k≠0.Sincegx is a permutation polynomial, there must exists λ1 in the unit circle U, satisfying equation (156). Then(158)x1=λ1+dbsatisfies equation (153), and in fact gx=d, since they are equivalent. Equation (156) can be transformed into(159)λ2+1/b+1/b2k1/b2+d2k+1/b2k+1+d2k/b2k+δ2kλ+1/b2+d2k+1/b2k+1+d2k/b2k+δ2k2k1/b2+d2k+1/b2k+1+d2k/b2k+δ2k=0.Since1/b2+d2k+1/b2k+1+d2k/b2k+δ2k2k/1/b2+d2k+1/b2k+1+d2k/b2k+δ2k is in the unit circle, the other root of equation (156), which we denote λ2, is also in the unit circle U. And(160)λ1≠λ2,since λ1+λ2=1/b+1/b2k≠0 for b∉F2k.Now, for equation (152), set(161)x2=λ2+db.Thenx2 satisfies equation (153) also, that is, gx=d has two solutions x1,x2 for such d, contradiction.Example 14.
Setk=4; then n=8. Let δ∈F2n with Trδ=1. Using Magma, it can be verified that, for b∈F2n\F2k,(162)gx=x2+x+δ120+bxis not a permutation polynomial over F28.


## 6. Conclusion

In this paper, based on the results obtained recently about permutation polynomials, we get some further PPs. Also, with suitable modifications on the conditions, some new classes of PPs are proposed. To do this, some coefficients of the original permutation polynomials are made to be variable, or the exponents are unfixed, or the field extensions are different from their work. We also investigate the necessities of permutation properties of the polynomials studied in [37], where the sufficient conditions are given. For future work, Lie et al. [44] combine network aggregation and algebraic state space representation (ASSR) to solve the state feedback stabilization problem of large-scale logical control networks (LCNs), stability analysis of nonlinear systems on time scales is further investigated in [45], the H∞ problem of nonlinear descriptor systems (NDSs) is investigated in [46], and the containment problem of finite-field networks (FFNs) with fixed topology (FT-FFNs) and switching topology (ST-FFNs) is studied in [17]. In these works, the authors utilized algebraic properties of some state space representations, and containment problem of finite-field networks (FFNs) is studied using semitensor product (STP) of matrices. By considering their permutation properties, some further results might be obtained.



---

*Source: 9409130-2021-12-31.xml*