Complete characterization of some permutation polynomials of the form $x^r(1+ax^{s_1(q-1)}+bx^{s_2(q-1)})$ over $\mathbb {F}_{q^2}$

Abstract

We completely characterize all permutation trinomials of the form $f(x)=x^3(1+ax^{q-1}+bx^{2(q-1)})$ over $\mathbb {F}_{q^2}$, where $a,b\in \mathbb {F}_q^*$ and all permutation trinomials of the form $f(x)=x^3(1+bx^{2(q-1)}+cx^{3(q-1)})$ over $\mathbb {F}_{q^2}$, where $b,c\in \mathbb {F}_q^*$ in both even and odd characteristic cases.

1 Introduction

Let q be a power of a prime, $\mathbb {F}_q$ be a finite field with q elements and $\mathbb {F}_q^*=\mathbb {F}_q\setminus \{0\}$. A polynomial is called a permutation polynomial if it induces a bijection on $\mathbb {F}_q$. Permutation polynomials over finite fields have been studied by many researchers for a rather long time. The main interest is to obtain permutation polynomials that look simple, having some additional properties which are required in some applications in some areas such as coding theory, crptography and combinatorial designs etc. In general permutation polynomials having such properties are hard to obtain.

To the best of our knowledge permutation polynomials were first studied by Dickson and Hermite (see, [11, 15]). For the interested readers, we believe that the books on finite fields (see, [28] and Chapter 8 in [30]) will be a good beginning to get into the topic, and moreover the survey papers (see, [17, 19, 32, 40]) will be very useful to go over many of the recent results on permutation polynomials. For some more results on permutation polynomials over finite fields we refer the interested reader to [5, 6, 13, 18, 26, 27] and the references therein.

In recent years there has been a great interest on determining permutation properties of polynomials of the form

$$\begin{aligned} f(x) = x^r(1+ax^{s_1(q-1)}+bx^{s_2(q-1)})\in \mathbb {F}_{q^2}[x], \end{aligned}$$

(1)

where $r,s_1,s_2$ are positive integers and $a,b\in \mathbb {F}_{q^2}$ (see for instance [4, 7, 21, 22, 25, 31, 36]).

In this paper we work on some types of permutation trinomials of the form as in (1) over the finite field $\mathbb {F}_{q^2}$. We develop a method to characterize certain permutation polynomials completely. Our method starts with a clever choice of polar coordinate transformation as an important technical step. Then we use an algorithmic method to decide whether the resulting polynomial in two variables is irreducible or not. This algorithmic method allows us to obtain all permutation polynomials in our classes as follows: The ones which lead to factorizations are easy to decide whether they are permutations or not. The ones which are irreducible turn out not to be permutations by using the well known Hasse-Weil inequality. We apply our method to some classes of polynomials of the form $x^r(1+ax^{s_1(q-1)}+bx^{s_2(q-1)})$ over $\mathbb {F}_{q^2}$. In particular, we obtain not only new permutation polynomials over $\mathbb {F}_{q^2}$ analogous to the ones in [18] and [42] but we also obtain a complete characterization.

The paper is organized as follows: In the preliminaries section we explain the ideas that we use throughout the paper in details. In [18] Hou determined all necessary and sufficient conditions for which the polynomial $g(x)=x(a+bx^{q-1}+x^{2(q-1)})$ permutes $\mathbb {F}_{q^2}$ for both even and odd characteristic finite fields. Inspired by this result, in Section 3, we study the permutation properties of the polynomial $f(x)=x^3(1+ax^{q-1}+bx^{2(q-1)})$ over $\mathbb {F}_{q^2}$, where $a,b\in \mathbb {F}_q^*$ and we find all necessary and sufficient conditions on a, b such that f(x) is a permutation trinomial of $\mathbb {F}_{q^2}$ in both even and odd characteristic cases.

In [42] Zha, Hu and Fan determined that the polynomials of the form $x^3+x^{2q+1}+x^{3q}=x^3(1+x^{2(q-1)}+x^{3(q-1)})$ are permutation polynomials over $\mathbb {F}_{q^2}$, where $q=2^m$ iff m is odd (see [42, Theorem 4.1]). In Section 4 we completely classify all permutation trinomials of a more general form $f(x)=x^3+bx^{2q+1}+cx^{3q}=x^3(1+bx^{2(q-1)}+cx^{3(q-1)})$ over $\mathbb {F}_{q^2}$, where $b,c\in \mathbb {F}_q^*$ in both even and odd characteristic cases.

We explain our contributions in each section via Remark 1, Remark 2. Finally in Section 5 we compare the results of our paper with the existing permutation trinomials in the literature under the quasi-multiplicative equivalence.

2 Preliminaries

There is a well known criterion due to Wan and Lidl [38], Park and Lee [34], Akbary and Wang [3], Wang [39] and Zieve [43] which is very useful for deciding whether a polynomial of the form $f\left( x\right) = x^rh\left( x^{\left( q^n-1\right) /d}\right)$ permutes $\mathbb {F}_{q^n}$ or not, which is given in the following lemma.

Lemma 1

[3, 34, 38, 39, 43] Let $h\left( x\right) \in \mathbb {F}_{q^n}[x]$ and d, r be positive integers with d dividing $q^n-1$. Then $f\left( x\right) = x^rh\left( x^{\left( q^n-1\right) /d}\right)$ permutes $\mathbb {F}_{q^n}$ if and only if the following conditions hold:

• i. $\gcd \left( r,\left( q^n-1\right) /d\right)$ = 1,

• ii. $x^rh\left( x\right) ^{\left( q^n-1\right) /d}$ permutes $\mu _{d}$, where $\mu _d=\{a\in \mathbb {F}_{q^n}^*\mid \, a^d=1\}$.

In all cases we study in this paper we plan to apply Lemma 1 over the finite field $\mathbb {F}_{q^2}$ with $d=q+1$, but instead of trying to find the conditions for which $f(x)=x^rh(x)^{q-1}$ permutes $\mu _{q+1}$ we use the following idea throughout the paper:

Let z be an arbitrary element in $\mathbb {F}_{q^2}\setminus \mathbb {F}_{q}$. We define the map $\displaystyle \phi \left( x\right) =\frac{x+z}{x+z^q}$, for any $x\in \mathbb {F}_q$ with $\phi \left( \infty \right) =1$. We first observe that $\phi$ is one to one from $\mathbb {F}_q \cup \{\infty \}$ to $\mu _{q+1}$ by the following discussion:

Assume that $\phi (x)=\phi (y)$ for some $x,y\in \mathbb {F}_q$, that is,

$$\begin{aligned} \frac{x+z}{x+z^q}=\frac{y+z}{y+z^q} \end{aligned}$$

which implies that $(x-y)z^q=(x-y)z$. Whenever $x\ne y$ we obtain $z^q=z$ which gives a contradiction since $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_{q}$. Thus $\phi$ is one to one. Moreover $\phi$ is also onto since we have the same number of elements on both sides. Then one obtains that $\displaystyle \phi ^{-1}\left( x\right) = \frac{xz^q-z}{1-x}$, for any $x\ne 1$ with $\phi ^{-1}\left( 1\right) =\infty$. In this setting, $f(x)=x^rh(x)^{q-1}$ is one to one on $\mu _{q+1}$ and thus permutes $\mu _{q+1}$ if and only if the map $\left( \phi ^{-1} \circ f \circ \phi \right)$ is one to one on $\mathbb {F}_q\cup \{\infty \}$.

The situation can be easily followed in the diagram below:

An important further technique we use is that we choose $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_{q}$ suitably so that the computations become simpler.

3 Permutation trinomials of the form $x^3+ax^{q+2}+bx^{2q+1}$ over $\mathbb {F}_{q^2}$, where $a,b\in \mathbb {F}_q^*$

In this section, aiming both necessity and sufficiency, we study the permutation properties of the polynomial $f(x)=x^3(1+ax^{q-1}+bx^{2(q-1)})$ over $\mathbb {F}_{q^2}$, where $a,b\in \mathbb {F}_q^*$ (see Remark 1 below).

We first observe that,

$$\begin{aligned} f(x)=x^3(1+ax^{q-1}+bx^{2(q-1)})=x^3h(x^{q-1}), \end{aligned}$$

where $h(x)=1+ax+bx^2$ with $a,b\in \mathbb {F}_q^*$. As we plan to apply Lemma 1, we must first find out $a,b\in \mathbb {F}_q^*$ for which the polynomial $h(x)=1+ax+bx^2\in \mathbb {F}_q[x]$ does not have any roots in $\mu _{q+1}$. If $h(1)=0$ or $h(-1)=0$, then h(x) has a root in $\mu _{q+1}$ trivially, therefore we characterize all such polynomials in the next proposition under the assumptions $h(1)\ne 0$ and $h(-1)\ne 0$.

Proposition 1

Let $\mathbb {F}_q$ be a finite field and $h(x)=1+ax+bx^2\in \mathbb {F}_q[x]$ where $a,b\in \mathbb {F}^*_q$. Assume that $h(1)=1+a+b\ne 0$, $h(-1)=1-a+b\ne 0$. Then h(x) has no roots in $\mu _{q+1}$ if and only if one of the following conditions hold:

• i. $b\ne 1$,

• ii. $b=1$ and

  $$\begin{aligned} \left\{ \begin{array}{rl} &{}{\text {Tr}}\left( \dfrac{1}{a}\right) =0, \,\,\text {if } char(\mathbb {F}_q) \,\,\text {is even},\\ \\ &{}a^2-4 \,\,\text {is a nonzero square in}\,\, \mathbb {F}_q, \,\,\text {if } char(\mathbb {F}_q)\,\, \text {is odd}. \end{array} \right. \end{aligned}$$

Proof

Let $x\in \mu _{q+1}$ such that $h(x)=0$, that is, $x^q=1/x$ and $1+ax+bx^2=0$. Taking the q-th power of the equation $1+ax+bx^2=0$ and inserting $x^q=1/x$ we obtain

$$\begin{aligned} x^2+ax+b=0. \end{aligned}$$

Hence there exists $x\in \mu _{q+1}$ such that $h(x)=0$ if and only if the following system

$$\begin{aligned} \left. \begin{array}{rl} bx^2+ax+1 &{}=0\\ bx^2+abx+b^2 &{}=0 \end{array} \right\} \end{aligned}$$

(2)

holds. Subtracting the equations in the above system (2) we get:

$$\begin{aligned} a(1-b)x+1-b^2=0. \end{aligned}$$

(3)

Assuming that $b\ne 1$ we get $x=\frac{-(1+b)}{a}\in \mathbb {F}_q\cap \mu _{q+1}=\{-1,1\}$ but this gives a contradiction since $h(1)\ne 0$ and $h(-1)\ne 0$. Thus h(x) has no roots in $\mu _{q+1}$ if $b\ne 1$. Now, assume that $b=1$, then $h(x)=x^2+ax+1$. Assume that $x\in \mu _{q+1}$ is a root of h(x), that is, $x^2+ax+1=0$. First, assume that $char(\mathbb {F}_q)=2$, then we obtain

$$\begin{aligned} x^2+ax=1\iff \dfrac{x^2}{a^2}+\dfrac{1}{a}x=\dfrac{1}{a^2}\iff y^2+y=\dfrac{1}{a^2}, \end{aligned}$$

where $y=x/a$. If ${\text {Tr}}\left( \dfrac{1}{a^2}\right) ={\text {Tr}}\left( \dfrac{1}{a}\right) =0$ then $x/a\in \mathbb {F}_q$ which implies that $x\in \mathbb {F}_q\cap \mu _{q+1}=\{-1,1\}$ but this is not possible since $h(1)\ne 0$ and $h(-1)\ne 0$. Therefore h(x) has no roots in $\mu _{q+1}$ iff ${\text {Tr}}\left( \dfrac{1}{a}\right) =0$ in the even characteristic case.

Next, assume that $char(\mathbb {F}_q)$ is odd. Then we have

$$\begin{aligned} 0=x^2+ax+1=x^2+ax+\dfrac{a^2}{4}+1-\dfrac{a^2}{4}\iff \left( x+\dfrac{a}{2}\right) ^2=\dfrac{a^2-4}{4}. \end{aligned}$$

Thus, h(x) has no roots in $\mu _{q+1}$ iff $a^2-4$ is a nonzero square in $\mathbb {F}_q$ in the odd characteristic case. $\square$

Now, suppose that h(x) has no roots in $\mu _{q+1}$, then for any $x\in \mu _{q+1}$ we have the following

$$\begin{aligned} x^3h(x)^{q-1}=\dfrac{x^3(bx^{2q}+ax^{q}+1)}{bx^2+ax+1}=\dfrac{x^3(bx^{-2}+ax^{-1}+1)}{bx^2+ax+1}=\dfrac{x^3+ax^2+bx}{bx^2+ax+1}.\nonumber \end{aligned}$$

Let ${g(x)}=\dfrac{x^3+ax^2+bx}{bx^2+ax+1}$, $\displaystyle \phi \left( x\right) =\frac{x+z}{x+z^q}$ and thus $\displaystyle \phi ^{-1}\left( x\right) = \frac{xz^q-z}{1-x}$, where $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_q$.

We define $\Delta (z;x):=(x+z)^3+a(x+z)^2(x+z^q)+b(x+z)(x+z^q)^2$. Then we have the following

$$\begin{aligned} ({g}\circ \phi )(x) =\dfrac{\Delta (z;x)}{\Delta (z^q;x)}= \dfrac{(x+z)^3+a(x+z)^2(x+z^q)+b(x+z)(x+z^q)^2}{b(x+z)^2(x+z^q)+a(x+z)(x+z^q)^2+(x+z^q)^3}\nonumber \end{aligned}$$

and thus

$$\begin{aligned} (\phi ^{-1}\circ {g}\circ \phi )(x) =\dfrac{\dfrac{\Delta (z;x)}{\Delta (z^q;x)}z^q-z}{1-\dfrac{\Delta (z;x)}{\Delta (z^q;x)}}= \dfrac{\Delta (z;x)z^q-z\Delta (z^q;x)}{\Delta (z^q;x)-\Delta (z;x)}.\nonumber \end{aligned}$$

Hereafter, in this section we deal with odd characteristic and even characteristic cases seperately.

First, assume that $\mathbb {F}_q$ is a finite field of odd characteristic and let $z^q=-z$, then we get the following

$$\begin{aligned} \Delta (z;x)z^q-z\Delta (z^q;x)=-2z\left( (1+a+b)x^3+(3-a-b)z^2x\right) \nonumber \end{aligned}$$

and

$$\begin{aligned} \Delta (z^q;x)-\Delta (z;x)=-2z\left( (3+a-b)x^2+(1+b-a)z^2\right) .\nonumber \end{aligned}$$

Thus,

$$\begin{aligned} (\phi ^{-1}\circ {g}\circ \phi )(x) =\dfrac{\Delta (z;x)z^q-z\Delta (z^q;x)}{\Delta (z^q;x)-\Delta (z;x)}=\dfrac{(1+a+b)x^3+(3-a-b)z^2x}{(3+a-b)x^2+(1+b-a)z^2}. \end{aligned}$$

(4)

First, we deal with the case where $3+a-b= 0$ in the following proposition.

Proposition 2

Let $\mathbb {F}_q$ be a finite field of odd characteristic, where $gcd(3,q-1)=1$. Let $h(x)=bx^2+ax+1$, with $a,b\in \mathbb {F}_q^*$. Assume that h(x) has no roots in $\mu _{q+1}$, that is, h(x) satisfies the conditions in Proposition 1, and $3+a-b= 0$. If $char(\mathbb {F}_q)\ne 3$ then there are no permutation polynomials of the form $f(x)=x^3h(x^{q-1})$ of $\mathbb {F}_{q^2}$. If $char(\mathbb {F}_q)=3$ then $f(x)=x^3h(x^{q-1})$ is a permutation polynomial of $\mathbb {F}_{q^2}$ iff $a=b$ and $\frac{b}{b-1}$ is a square in $\mathbb {F}_q$.

Proof

In this case, after computing

$$\begin{aligned} \dfrac{(\phi ^{-1}\circ g\circ \phi )(x)-(\phi ^{-1}\circ g\circ \phi )(y)}{x-y} \end{aligned}$$

using the equation in (4) and simplifying we obtain the following

$$\begin{aligned} \mathcal {C}(x,y):= x^2+xy+y^2+A, \,\text {where} \,A=\dfrac{(3-b)}{b-1}z^2. \end{aligned}$$

(5)

Note that, if $b-1=0$ then $3+a-b= 0$ implies that $a=-2$ and thus f is not a permutation polynomial since h(x) has a root (i.e., $h(1)=1+a+b=0$) in $\mu _{q+1}$ . Hence we assume that $b\ne 1$. We also have $A\ne 0$ otherwise $b=3$ and this implies $a=0$ but $a\in \mathbb {F}_q^*$.

First, assume that $\mathcal {C}(x,y)$ in (5) is not absolutely irreducible over the algebraic closure $\overline{\mathbb {F}}_q$ of $\mathbb {F}_{q}$ and it can be decomposed in the form:

$$\begin{aligned} (x+\alpha y+lot)(\beta _1 x+\beta _2 y+lot)=\beta _1 x^2+(\beta _2+\beta _1\alpha )xy+\beta _2\alpha y^2+lot \end{aligned}$$

(6)

Later in this proof we determine exactly in which extensions of $\mathbb {F}_q$ $\alpha ,\beta _1,\beta _2$ lie. Here and throughout the paper we use “lot” as the abbreviated form of the so called “lower order terms”. Comparing the coefficients of degree 2 terms in (6) with the ones in $\mathcal {C}(x,y)$ in (5) we obtain: $\beta _1=1, \beta _2+\alpha =1$ and $\beta _2\alpha =1$ which implies that $\alpha (1-\alpha )=1$. Now, substituting $\beta _1=1$, $\beta _2=1-\alpha$ and $\alpha (1-\alpha )=1$ in (6) we get:

$$\begin{aligned}&(x+\alpha y+\alpha _1)(x+(1-\alpha ) y+\alpha _2)\\&=x^2+xy+y^2+(\alpha _2+\alpha _1)x+(\alpha \alpha _2+\alpha _1(1-\alpha ))y+\alpha _1\alpha _2\nonumber \end{aligned}$$

(7)

Comparing the coefficients of degree 1 terms in (6) with the ones in $\mathcal {C}(x,y)$ in (5) we obtain: $\alpha _1+\alpha _2=0$ so we have $\alpha _2=-\alpha _1$ and $\alpha \alpha _2+\alpha _1(1-\alpha )=0$ which implies that $\alpha _1(1-2\alpha )=0$. Note that $\alpha _1\ne 0$ as $A=-\alpha _1^2$ and $A\ne 0$. Thus we must have $\alpha =1/2$. Substituting $\alpha =1/2$ in $\alpha (1-\alpha )=1$ we obtain that $4=1$ which is only possible if $char(\mathbb {F}_q)=3$. Therefore, $\mathcal {C}(x,y)$ is absolutely irreducible in the case where $char(\mathbb {F}_q)\ne 3$. Homogenizing $\mathcal {C}(x,y)$ in (5) with $x=\frac{X}{Z}$ and $y=\frac{Y}{Z}$ we obtain a homogeneous polynomial of degree $d=2$. Then by the Hasse-Weil bound (see [20, Theorem 5.28]) we have the following:

$c(d)=\frac{1}{2}d(d-1)^2+1$, note that $c(d)=2$ as $d=2$, hence

$$\begin{aligned} \mid N - q \mid \le (d-1)(d-2)q^{1/2}+c(d)=2, \end{aligned}$$

where N is the number of affine $\mathbb {F}_q$-rational points of $\mathcal {C}(x,y)$. This implies that if $q- 2> 2$ then $\mathcal {C}(x,y)$ in (5) has an affine $\mathbb {F}_q$-rational point off the line $x=y$ and thus f(x) is not a permutation polynomial of $\mathbb {F}_{q^2}$.

Next, if $char(\mathbb {F}_q)=3$ then $\alpha =1/2$, $A=-\alpha _1^2=\dfrac{-b}{b-1}z^2$ and by $3+a-b= 0$ we have $a=b$. Assume that $x+\frac{1}{2}y+\alpha _1=0$ for some $x,y\in \mathbb {F}_q$. Taking its q-th power we obtain $x+\frac{1}{2}y+\alpha _1^q=0$. Subtracting these two equations we get that $\alpha _1^q=\alpha _1$, thus $\alpha _1\in \mathbb {F}_q$. On the other hand $\alpha _1^2=\frac{b}{b-1}z^2$, where $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_q$. Thus, $\alpha _1\notin \mathbb {F}_q$ iff $\frac{b}{b-1}$ is a square in $\mathbb {F}_q$. $\square$

Next, assume that $3+a-b\ne 0$. Note also that $1+b+a\ne 0, 1+b-a\ne 0$ since $h(-1)\ne 0, h(1)\ne 0$. Then by (4) we have:

$$\begin{aligned} \dfrac{x^3+\dfrac{(3-b-a)}{(1+b+a)}z^2x}{x^2+\dfrac{(1+b-a)}{(3-b+a)}z^2}=\dfrac{x^3+Ax}{x^2+B}, \end{aligned}$$

(8)

where $A=z^2\dfrac{(3-b-a)}{1+b+a}$ and $B=z^2\dfrac{(1+b-a)}{3-b+a}\ne 0$ since $h(-1)=1+b-a\ne 0$. First, we consider the case where $-B$ is a square in $\mathbb {F}_q$. In this case there exists $x\in \mathbb {F}_q$ such that the denominator of the fraction in (8), that is, $x^2+B$ becomes zero which implies that $\infty$ has at least three distinct preimages under the map $(\phi ^{-1}\circ {g}\circ \phi )(x)$ and therefore g(x) is not a permutation polynomial. Thus, from here on assume that $-B$ is not a square in $\mathbb {F}_q$, that is, $\dfrac{-(1+b-a)}{3-b+a}$ is a square in $\mathbb {F}_q$ since $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_q$.

Computing $\dfrac{\dfrac{x^3+Ax}{x^2+B}-\dfrac{y^3+Ay}{y^2+B}}{x-y}$ one gets the following

$$\begin{aligned} \mathcal {C}(x,y):= x^2y^2+(B-A)xy+B(x^2+y^2)+AB. \end{aligned}$$

(9)

In this setting, $(\phi ^{-1}\circ {g}\circ \phi )$ permutes $\mathbb {F}_q$ if and only $\mathcal {C}(x,y)$ defined in (9) is not zero for any $x,y\in \mathbb {F}_q$ with $x\ne y$. The following theorem completes the problem in the remaining case for finite fields of odd characteristic, where $3+a-b\ne 0$.

Theorem 3

Let $\mathbb {F}_q$ be a finite field of odd characteristic, where $gcd(3,q-1)=1$. Let $h(x)=bx^2+ax+1$, with $a,b\in \mathbb {F}_q^*$. Assume that $3+a-b\ne 0$. Then $f(x)=x^3h(x^{q-1})$ is a permutation polynomial of $\mathbb {F}_{q^2}$ iff one of the following conditions hold

• i $b=1$, $a\ne \pm 2$ and $a^2-4$ is a square in $\mathbb {F}_q$,

• ii $b\ne 1$, $b^2+3b-a^2=0$, $\dfrac{-(1+b-a)}{3+a-b}$ is a square in $\mathbb {F}_q$, $1+a+b\ne 0$ and $1+b-a\ne 0$.

Proof

We need to check all decompositions of the bivariate polynomial $\mathcal {C}(x,y)$ in (9) into absolutely irreducible factors in $\overline{\mathbb {F}}_q$, where $\overline{\mathbb {F}}_q$ stands for an algebraic closure of the finite field $\mathbb {F}_q$. Since the degree of the bivariate polynomial in (9) is 4, the possibilities are: $3+1$ decomposition and $2+2$ decomposition according to the degrees of the possible factors and finally the case where the bivariate polynomial $\mathcal {C}(x,y)$ in (9) is absolutely irreducible. We first fix a monomial ordering by taking $x\ge y$ without loss of generality.

We begin the discussion with $3+1$ decomposition. Let $\mathcal {C}(x,y)$ defined in (9) be decomposed in the following form

$$\begin{aligned}&(x+\alpha _1y+lot)(\beta _1x^3+\gamma _1x^2y+\delta _1xy^2+\eta _1y^3+lot)\\&=\beta _1 x^4+(\gamma _1+\alpha _1\beta _1)x^3y+(\delta _1+\alpha _1\gamma _1) x^2y^2+(\eta _1+\alpha _1\delta _1) xy^3+\alpha _1\eta _1y^4+lot.\nonumber \end{aligned}$$

(10)

By comparing the coefficients of the degree 4 terms in (10) with the ones in $\mathcal {C}(x,y)$ defined in (9), we obtain that: $\beta _1=0, \gamma _1=0,\delta _1=1,\alpha _1=0$ and $\eta _1=0$. Substituting these in (10) we have

$$\begin{aligned} (x+lot)(xy^2+lot),\nonumber \end{aligned}$$

that is, writing down the possible lower order terms, the decomposition is as follows:

$$\begin{aligned}&(x+\alpha )(xy^2+\alpha _2x^2+\beta _2xy+\gamma _2y^2+lot)\\&=x^2y^2+\alpha _2x^3+\beta _2x^2y+(\gamma _2+\alpha )xy^2+lot.\nonumber \end{aligned}$$

(11)

Now, by comparing the coefficients of the degree 3 terms in (11) with the ones in $\mathcal {C}(x,y)$ defined in (9), we observe that $\alpha _2=0, \beta _2=0, \gamma _2=-\alpha$. Thus we have

$$\begin{aligned}&(x+\alpha )(xy^2-\alpha y^2+\alpha _3x+\beta _3y+lot)\\&=x^2y^2+\alpha _3x^2+\beta _3xy-\alpha ^2y^2+lot\nonumber . \end{aligned}$$

(12)

By comparing the coefficients of the degree 2 terms in (12) with the ones in $\mathcal {C}(x,y)$ defined in (9), we observe that $\alpha _3=-\alpha ^2=B, \beta _3=B-A$. That is, we have

$$\begin{aligned}&(x+\alpha )(xy^2-\alpha y^2+Bx+(B-A)y+\beta )\\&=x^2y^2+(B-A)xy+B(x^2+y^2)+(\beta +\alpha B)x+\alpha (B-A)y+\alpha \beta \nonumber . \end{aligned}$$

(13)

By comparing the coefficients of the degree 1 terms in (13) with the ones in $\mathcal {C}(x,y)$ defined in (9), we observe that $\beta =-\alpha B$ and $\alpha (B-A)=0$ which implies that $B=A$ since $\alpha \ne 0$ (as $-\alpha ^2=B\ne 0$). Finally, comparing the constant term in (13) with the one in $\mathcal {C}(x,y)$ we get $\alpha \beta =AB$ and substituting $\beta =-\alpha B$ in $\alpha \beta =AB$, we obtain that $A=B=-\alpha ^2$. Thus we have

$$\begin{aligned} (x+\alpha )(xy^2-\alpha y^2-\alpha ^2x+\alpha ^3)= (x+\alpha )(x-\alpha )(y+\alpha )(y-\alpha ), \end{aligned}$$

(14)

so we end up with the 1+1+1+1 decomposition of $\mathcal {C}(x,y)$. Now, we have

$$A=B\implies z^2\dfrac{(3-b-a)}{1+b+a}=z^2\dfrac{(1+b-a)}{3-b+a}\,\text {, that is, }$$

$$(3-b-a)(3-b+a)=(1+b-a)(1+b+a)$$

which implies that $b=1$. Note that $-\alpha ^2=B$, so $\alpha \notin \mathbb {F}_q$ since we have that $-B=z^2\dfrac{(a-2)}{a+2}$ is not a square in $\mathbb {F}_q$ (that is, $\dfrac{a-2}{a+2}$ is a square in $\mathbb {F}_q$) and thus none of the factors in the decomposition (14) can have a root in $\mathbb {F}_q$. Therefore, in this case, f(x) is a permutation poynomial iff $b=1, a\ne \pm 2$ and $\dfrac{a-2}{a+2}$ is a square in $\mathbb {F}_q$, that is, $a^2-4$ is a square in $\mathbb {F}_q$.

Next, we deal with the possible 2+2 decompositions of $\mathcal {C}(x,y)$. Here, there are two possibilities: $\mathcal {C}(x,y)$ defined in (9) is either decomposed in the form

$$\begin{aligned} (x^2+\alpha _1xy+\beta _1y^2+lot)(\alpha _2x^2+\beta _2xy+\gamma _2y^2+lot) \end{aligned}$$

(15)

or

$$\begin{aligned} (xy+\alpha _1x+\beta _1y+lot)(xy+\alpha _2x+\beta _2y+lot). \end{aligned}$$

(16)

First, assume that $\mathcal {C}(x,y)$ is decomposed in the form (15).

$$\begin{aligned}&(x^2+\alpha _1xy+\beta _1y^2+lot)(\alpha _2x^2+\beta _2xy+\gamma _2y^2+lot)\\&=\alpha _2x^4+(\beta _2+\alpha _1\alpha _2)x^3y+(\gamma _2+\alpha _1\beta _2+\alpha _2\beta _1)x^2y^2\nonumber \\&+(\alpha _1\gamma _2+\beta _1\beta _2)xy^3+\beta _1\gamma _2y^4+lot.\nonumber \end{aligned}$$

(17)

After comparing the coefficients of degree 4 terms of (15) with the ones in $\mathcal {C}(x,y)$ defined in (9) we get: $\alpha _1=0, \alpha _2=0, \beta _1=0,\beta _2=0,\gamma _2=1$, so we end up with the following decomposition

$$\begin{aligned}&(x^2+\alpha _3x+\beta _3y+lot)(y^2+\alpha _4x+\beta _4y+lot)\\&=x^2y^2+\alpha _4x^3+\beta _4x^2y+\alpha _3xy^2+\beta _3y^3+lot.\nonumber \end{aligned}$$

(18)

Comparing the coefficients of degree 3 terms of (18) with the ones in $\mathcal {C}(x,y)$ defined in (9) we get: $\alpha _4=0, \beta _4=0, \alpha _3=0, \beta _3=0$. Thus we have

$$\begin{aligned} (x^2+\eta )(y^2+\zeta )=x^2y^2+\zeta x^2+\eta y^2+\eta \zeta . \end{aligned}$$

(19)

Comparing the coefficients of (19) with the ones in $\mathcal {C}(x,y)$ defined in (9) we obtain that $B-A=0$, that is, $A=B$ (implying $b=1$) and $\eta =\zeta =B$. Now, if $x^2+\eta =0$ for some $x\in \mathbb {F}_q$ then we have $x^2=-\eta =-B$, that is, $-B$ is a square in $\mathbb {F}_q$ which gives a contradiction. Thus $x^2+\eta \ne 0$ and similarly $y^2+\zeta \ne 0$ for any $x,y\in \mathbb {F}_q$. Therefore in this case, f(x) is a permutation poynomial iff $b=1, a\ne \pm 2$ and $\dfrac{a-2}{a+2}$ is a square in $\mathbb {F}_q$, that is, $a^2-4$ is a square in $\mathbb {F}_q$.

Next, assume that $\mathcal {C}(x,y)$ is decomposed in the form (16).

$$\begin{aligned}&(xy+\alpha _1x+\beta _1y+lot)(xy+\alpha _2x+\beta _2y+lot)\\&=x^2y^2+(\alpha _1+\alpha _2)x^2y+(\beta _1+\beta _2)xy^2+lot.\nonumber \end{aligned}$$

(20)

After comparing the coefficients of degree 3 terms of (16) with the ones in $\mathcal {C}(x,y)$ we obtain: $\alpha _2=-\alpha _1$ and $\beta _2=-\beta _1$ and so we end up with the following decomposition

$$\begin{aligned}&(xy+\alpha _1x+\beta _1y+\alpha )(xy-\alpha _1x-\beta _1y+\beta )\\&=x^2y^2-\alpha _1^2x^2+(\beta +\alpha -2\alpha _1\beta _1)xy-\beta _1^2y^2+lot.\nonumber \end{aligned}$$

(21)

Comparing the coefficients of degree 2 terms in (21) with the ones in $\mathcal {C}(x,y)$ we obtain $-\alpha _1^2=-\beta _1^2=B$ and $\beta +\alpha -2\alpha _1\beta _1=B-A$. By $-\alpha _1^2=-\beta _1^2=B$ we deduce that $\alpha _1,\beta _1\notin \mathbb {F}_q$ since we have that $-B$ is not a square in $\mathbb {F}_q$, which further implies that $\alpha _1^q=-\alpha _1$ and $\beta _1^q=-\beta _1$ (as $-\alpha _1^2=-\beta _1^2=B\in \mathbb {F}_q$). Thus, we have $\alpha _1^2=\beta _1^2$ which implies that either $\alpha _1=\beta _1$ or $\alpha _1=-\beta _1$.

Now, assume that $\alpha _1=\beta _1$, then substituting $\alpha _1=\beta _1$ and $-\alpha _1^2=-\beta _1^2=B$ in $\beta +\alpha -2\alpha _1\beta _1=B-A$ we obtain $\beta =-(A+B+\alpha )$. Then the decomposition in (21) becomes the following:

$$\begin{aligned}&(xy+\alpha _1x+\alpha _1y+\alpha )(xy-\alpha _1x-\alpha _1y-(A+B+\alpha ))\\&=x^2y^2-\alpha _1^2(x^2+y^2)+(B-A)xy-\alpha _1(A+B+2\alpha )(x+y)-\alpha (A+B+\alpha )\nonumber . \end{aligned}$$

(22)

Comparing the coefficients of degree 1 terms and the constant terms in (22) with the ones in $\mathcal {C}(x,y)$, we obtain $A+B+2\alpha =0$ as $\alpha _1\ne 0$ and so $\alpha =\dfrac{-(A+B)}{2}$. Comparing the constant term in (22) with the one in $\mathcal {C}(x,y)$, we obtain $-\alpha (A+B+\alpha )=AB$. Substituting $\alpha =\dfrac{-(A+B)}{2}$ in $-\alpha (A+B+\alpha )=AB$ we obtain $AB=\dfrac{(A+B)^2}{4}$ which implies that $(A-B)^2=0$ then $A=B$ and so $b=1$.

Assume that there exists $x,y\in \mathbb {F}_q$ such that $xy+\alpha _1x+\alpha _1y+\alpha =0$. Taking its q-th power we get $xy-\alpha _1x-\alpha _1y+\alpha =0$. Subtracting these two equations we obtain $2\alpha _1(x+y)=0$ which implies that $x=-y$ since $\alpha _1\ne 0$ (as $-\alpha _1^2=B\ne 0$). Substituting $x=-y$ in the equation $xy+\alpha _1x+\alpha _1y+\alpha =0$ we get $-x^2+\alpha =-x^2-B=0$ which contradicts with the fact that $-B$ is not a square in $\mathbb {F}_q$. Thus, we conclude that none of the factors in the decomposition (22) can have roots in $\mathbb {F}_q$. Therefore, in this case, f(x) is a permutation poynomial iff $b=1, a\ne \pm 2$ and $\dfrac{a-2}{a+2}$ is a square in $\mathbb {F}_q$, that is, $a^2-4$ is a square in $\mathbb {F}_q$.

Finally, assume that $\alpha _1=-\beta _1$. Then by (21) we have the following decomposition:

$$\begin{aligned} (xy+\alpha _1x-\alpha _1y+\alpha )(xy-\alpha _1x+\alpha _1y-(A-3B+\alpha )). \end{aligned}$$

(23)

Comparing the coefficients of degree 1 terms and the constant terms in (23) with the ones in $\mathcal {C}(x,y)$ we obtain $\alpha =\beta$, $AB=\alpha ^2$ and $\alpha =\dfrac{3B-A}{2}$. Substituting $\alpha =\dfrac{3B-A}{2}$ in $AB=\alpha ^2$ we get $(9B-A)(B-A)=0$ implying that either $A=B$ or $A=9B$.

If $A=B$ then $b=1$ and we obtain that f(x) is a permutation poynomial iff $b=1, a\ne \pm 2$ and $\dfrac{a-2}{a+2}$ is a square in $\mathbb {F}_q$, that is, $a^2-4$ is a square in $\mathbb {F}_q$. If $9B=A$ then we obtain $b^2+3b-a^2=0$.

Assume that there exists $x,y\in \mathbb {F}_q$ such that $xy+\alpha _1x-\alpha _1y+\alpha =0$. Taking its q-th power we get $xy-\alpha _1x+\alpha _1y+\alpha =0$. Subtracting these two equations we obtain $2\alpha _1(x-y)=0$ implying that $x=y$ since $\alpha _1\ne 0$. Therefore, in this case f(x) is a permutation poynomial iff $b^2+3b-a^2=0$, $\dfrac{-(1+b-a)}{3+a-b}$ is a square in $\mathbb {F}_q$, $1-a+b\ne 0$, $1+a+b\ne 0$ and $b\ne 1$ (otherwise, if $b=1$, $b^2+3b-a^2=0$ implies that $a=\pm 2$ which contradicts with $1-a+b\ne 0$ or $1+a+b\ne 0$).

As the last step, we deal with the absolutely irreducible case. Assume that $\mathcal {C}(x,y)$ defined in (9) is absolutely irreducible. Homogenizing $\mathcal {C}(x,y)$ in (9) with $x=\frac{X}{Z}$ and $y=\frac{Y}{Z}$ we obtain a homogeneous polynomial of degree $d=4$. Then by the Hasse-Weil bound (see [20, Theorem 5.28]) we have the following:

$c(d)=\frac{1}{2}d(d-1)^2+1$, note that $c(d)=19$ as $d=4$, hence

$$\begin{aligned} \mid N - q \mid \le (d-1)(d-2)q^{1/2}+c(d)\le 6q^{1/2}+ 19, \end{aligned}$$

where N is the number of affine $\mathbb {F}_q$-rational points of $\mathcal {C}(x,y)$. This implies that if $q- 6q^{1/2}-19> 4$ then $\mathcal {C}(x,y)$ has an affine $\mathbb {F}_q$-rational point off the line $x=y$. As q is a prime power, we note that $q- 6q^{1/2}-19> 4$ for any such q provided that $q\ge 79$. As a result, we deduce that f(x) is not a permutation polynomial of $\mathbb {F}_{q^2}$ if $\mathcal {C}(x,y)$ is absolutely irreducible and $q\ge 79$. It remains to consider $q<79$. Now, since characteristic of $\mathbb {F}_q$ is odd and 3 does not divide $q-1$ we need to consider only $q\in \{3,5,9,11,17,23,27,29,41,47,53,59,71\}$. Using MAGMA [29], we observe that there are no other permutation polynomials of the form f(x) other than the ones obtained by Proposition 2 and Theorem 1. $\square$

Next, assume that $\mathbb {F}_q$ is a finite field of even characteristic. Note that if $char(\mathbb {F}_q)$ is even then in order to have $\gcd (3,q-1)=1$, q must be of the form $q=2^{2k+1}$, for some $k\in \mathbb {N}$.

Let $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_q$ satisfying $z^2+z+1=0$. Note that $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_q$ satisfying $z^q+z=1$. Then we get the following

$$\begin{aligned} \Delta (z;x)z^q-z\Delta (z^q;x)=(1+a+b)x^3+ax^2+(a+1)x+b+1 \end{aligned}$$

and

$$\begin{aligned} \Delta (z^q;x)-\Delta (z;x)=(1+a+b)x^2+(1+a+b)x+a+b. \end{aligned}$$

Thus, we get

$$\begin{aligned} (\phi ^{-1}\circ f\circ \phi )(x)= & {} \dfrac{\Delta (z;x)z^q-z\Delta (z^q;x)}{\Delta (z^q;x)-\Delta (z;x)}\\= & {} \dfrac{(1+a+b)x^3+ax^2+(a+1)x+b+1}{(1+a+b)x^2+(1+a+b)x+a+b}.\nonumber \end{aligned}$$

(24)

Let $A_2=\dfrac{a}{1+a+b}$, $A_1=\dfrac{a+1}{1+a+b}$, $A_0=\dfrac{b+1}{1+a+b}$ and $B_0=\dfrac{a+b}{1+a+b}$, so we have $B_0=A_1+A_0$.

Computing $\dfrac{\dfrac{x^3+A_2x^2+A_1x+A_0}{x^2+x+B_0}-\dfrac{y^3+A_2y^2+A_1y+A_0}{y^2+y+B_0}}{x-y}$ one gets the following

$$\begin{aligned} \mathcal {C}(x,y):= x^2y^2+x^2y+xy^2+B_0(x^2+y^2)+xy+(A_2B_0+A_0)(x+y)+A_1B_0+A_0. \end{aligned}$$

(25)

In this setting, $(\phi ^{-1}\circ f\circ \phi )$ permutes $\mathbb {F}_q$ if and only $\mathcal {C}(x,y)$ defined in (25) is not zero for any $x,y\in \mathbb {F}_q$ with $x\ne y$. Our second main result in this section is given in the following theorem.

Theorem 4

Let $\mathbb {F}_q$ be a finite field of even characteristic, where $q=2^{2k+1}$, for some $k\in \mathbb {N}$. Let $h(x)=bx^2+ax+1$, with $a,b\in \mathbb {F}_q^*$. Then $f(x)=x^3h(x^{q-1})$ is a permutation polynomial of $\mathbb {F}_{q^2}$ iff one of the following conditions hold

• i $b=1$ and ${\text {Tr}}\left( \dfrac{1}{a}\right) =0$,

• ii $b\ne 1$, $1+a+b\ne 0$ and $a^2=b(1+b)$.

Proof

The proof can be done in an analogous way to Theorem 1 therefore we omit the proof in order not to repeat the similar long discussions on all possible decompositions. $\square$

Table 1 List of all pairs of coefficients (a, b) of permutation polynomials of $\mathbb {F}_{81}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=bx^2+ax+1$, with $a,b\in \mathbb {F}_9^*$ and $x^2+2x+2\in \mathbb {F}_3[x]$ is the minimal polynomial of $\alpha$ obtained by Proposition 2

Table 2 List of all pairs of coefficients (a, b) of permutation polynomials of $\mathbb {F}_{81}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=bx^2+ax+1$, with $a,b\in \mathbb {F}_9^*$ and $x^2+2x+2\in \mathbb {F}_3[x]$ is the minimal polynomial of $\alpha$ obtained by Theorem 1

Example 1

In the following tables we explicitly give the coefficients over the finite field $\mathbb {F}_9$ of all permutation polynomials obtained from Proposition 2 and Theorem 1. Here, $\mathbb {F}_9$ is the smallest nontrivial finite field containing coefficients a, b which give rise to permutation polynomials of the form $f(x)=x^3h(x^{q-1})$ of $\mathbb {F}_{81}$, where $h(x)=bx^2+ax+1$. Let $x^2+2x+2\in \mathbb {F}_3[x]$ be the minimal polynomial of $\alpha$, that is $\mathbb {F}_9^*=<\alpha>$. In Tables 1 and 2 below we list all pairs of coefficients (a, b) of permutation polynomials of $\mathbb {F}_{81}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=bx^2+ax+1$, with $a,b\in \mathbb {F}_9^*$ obtained by Proposition 2 and Theorem 1 respectively .

Example 2

In the following table we explicitly give the coefficients over the finite field $\mathbb {F}_8$ of all permutation polynomials obtained from Theorem 2. Here, $\mathbb {F}_8$ is the smallest nontrivial finite field containing coefficients a, b which give rise to permutation polynomials of the form $f(x)=x^3h(x^{q-1})$ of $\mathbb {F}_{64}$, where $h(x)=bx^2+ax+1$. Let $x^3+x+1\in \mathbb {F}_2[x]$ be the minimal polynomial of $\alpha$, that is $\mathbb {F}_8^*=<\alpha>$. In Table 3 below we list all pairs of coefficients (a, b) of permutation polynomials of $\mathbb {F}_{64}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=bx^2+ax+1$, with $a,b\in \mathbb {F}_8^*$ and $x^3+x+1\in \mathbb {F}_2[x]$ is the minimal polynomial of $\alpha$, obtained by Theorem 2.

Remark 1

In recent years, there have been many attempts to find new classes of permutation trinomials of the form $f(x) = x^r(1+ax^{s_1(q-1)}+bx^{s_2(q-1)})\in \mathbb {F}_{q^2}[x],$ where $r,s_1,s_2$ are positive integers and $a,b\in \mathbb {F}_{q^2}$. In [18] Hou determined all necessary and sufficient conditions for which the polynomial $g(x)=x(a+bx^{q-1}+x^{2(q-1)})$ permutes $\mathbb {F}_{q^2}$ for both even and odd characteristic finite fields. Inspired by this result, in this section, we studied on the permutation properties of the polynomial $f(x)=x^3(1+ax^{q-1}+bx^{2(q-1)})$ over $\mathbb {F}_{q^2}$, where $a,b\in \mathbb {F}_q^*$ and we completely determined all necessary and sufficient conditions on a, b such that f(x) is a permutation trinomial of $\mathbb {F}_{q^2}$ in both even and odd characteristic cases.

4 Permutation trinomials of the form $x^3+bx^{2q+1}+cx^{3q}$ over $\mathbb {F}_{q^2}$, where $b,c\in \mathbb {F}_q^*$

In [42] Zha, Hu and Fan determined that the polynomials of the form $x^3+x^{2q+1}+x^{3q}$ are permutation polynomials over $\mathbb {F}_{q^2}$, where $q=2^m$ iff m is odd (see [42, Theorem 4.1]). Inspired by this result, in this section we study the permutation properties of the more general polynomial $f(x)=x^3+bx^{2q+1}+cx^{3q}$ over $\mathbb {F}_{q^2}$, where $b,c\in \mathbb {F}_q^*$ in both odd and even characteristic cases (see Remark 2 below).

Table 3 List of all pairs of coefficients (a, b) of permutation polynomials of $\mathbb {F}_{64}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=bx^2+ax+1$, with $a,b\in \mathbb {F}_8^*$ and $x^3+x+1\in \mathbb {F}_2[x]$ is the minimal polynomial of $\alpha$, obtained by Theorem 2

We first observe that,

$$\begin{aligned} f(x)=x^3+bx^{2q+1}+cx^{3q}=x^3(1+bx^{2q-2}+cx^{3q-3})=x^3h(x^{q-1}), \end{aligned}$$

where $h(x)=1+bx^2+cx^3$ with $b,c\in \mathbb {F}_q^*$. As we plan to apply Lemma 1, we must first find out $b,c\in \mathbb {F}_q^*$ for which the polynomial $h(x)=1+bx^2+cx^3\in \mathbb {F}_q^*[x]$ have roots in $\mu _{q+1}$.

Proposition 5

Let $h(x)=1+bx^2+cx^3\in \mathbb {F}_q[x]$ where $b,c\in \mathbb {F}^*_q$. Assume that $h(1)=1+b+c\ne 0$, $h(-1)=1+b-c\ne 0$. Then there exists $x\in \mu _{q+1}$ such that $h(x)=0$ if and only if one the following conditions hold according to the characteristic of the finite field $\mathbb {F}_q$:

• i $b=1-c^2$ and ${\text {Tr}}(1/c)=1$ if $char(\mathbb {F}_q)$ is even.

• ii $b=1-c^2$ and $c^2-4$ is a nonsquare in $\mathbb {F}_q$ if $char(\mathbb {F}_q)$ is odd.

Proof

We first claim that if h(x) has a root in $\mu _{q+1}$ then it must be in $\mathbb {F}_{q^2}\setminus \mathbb {F}_q$. Assume that there exists $x\in \mu _{q+1}\cap \mathbb {F}_q$ such that $h(x)=0$, then we have $x=x^q=1/x$ implying $x^2=1$, that is, $x=1$ or $x=-1$ both of which contradict with the assumptions $h(1)\ne 0$ and $h(-1)\ne 0$. Now, let $x\in \mu _{q+1}$ such that $h(x)=0$, that is, $x^q=1/x$ and

$$\begin{aligned} 1+bx^2+cx^3=0\Leftrightarrow x^3+\frac{b}{c}x^2+\frac{1}{c}=0. \end{aligned}$$

Taking the q-th power of the equation $1+bx^2+cx^3=0$ and inserting $x^q=1/x$ we obtain

$$\begin{aligned} 1+bx^{2q}+cx^{3q}=1+b\dfrac{1}{x^2}+c\dfrac{1}{x^3}=0 \Leftrightarrow x^3+bx+c=0. \end{aligned}$$

(26)

Hence, there exists $x\in \mu _{q+1}$ such that $h(x)=0$ if and only if the following system

$$\begin{aligned} \left. \begin{array}{rl} x^3+bx+c &{}=0\\ x^3+\dfrac{b}{c}x^2+\dfrac{1}{c} &{}=0 \end{array} \right\} \end{aligned}$$

(27)

holds. Subtracting the equations in the above system (27) we get:

$$\begin{aligned} \dfrac{b}{c}x^2-bx+\dfrac{1}{c}-c=0 \end{aligned}$$

(28)

and then multiplying the equation in (28) by $\dfrac{c}{b}$ we have:

$$\begin{aligned} x^2-cx+\dfrac{1}{b}-\dfrac{c^2}{b}=0. \end{aligned}$$

(29)

Letting $\delta =\dfrac{1-c^2}{b}$, the equation in (29) becomes

$$\begin{aligned} x^2-cx+\delta =0. \end{aligned}$$

(30)

Here, we note that $\delta \ne 0$, because otherwise the equation in (30) implies that either $x=0$ or $x=c$, which contradicts with the claim as $0,c\in \mathbb {F}_q$. Note also that $\delta \in \mathbb {F}_q$. Taking the q-th power of the equation in (30) and substituting $x^q=1/x$, we obtain

$$\begin{aligned} \dfrac{1}{x^2}-\dfrac{c}{x}+\delta =0 \Leftrightarrow \delta x^2-cx+1=0 \Leftrightarrow x^2-\dfrac{c}{\delta }x+\dfrac{1}{\delta }=0. \end{aligned}$$

(31)

Now, subtracting the equations in (30) and (31) we have

$$\begin{aligned} -cx+\dfrac{c}{\delta }x+\delta -\frac{1}{\delta }=0, \end{aligned}$$

(32)

which is equivalent to

$$\begin{aligned} \displaystyle c\left( \dfrac{1}{\delta }-1\right) x+\dfrac{\delta ^2 -1}{\delta }=0 \Leftrightarrow c(1-\delta )x+(\delta ^2 -1)=0. \end{aligned}$$

(33)

If $\delta \ne 1$, then by the equation in (33) we get

$$\begin{aligned} cx-(\delta +1)=0 \Leftrightarrow x=\dfrac{\delta +1}{c}\nonumber , \end{aligned}$$

which contradicts with the claim, since $\dfrac{\delta +1}{c}=\dfrac{1-c^2+b}{bc}\in \mathbb {F}_q$. Thus, $\delta =1$, that is, $b=1-c^2$, so the proof of the first condition in both cases is complete. First, assume that $char(\mathbb {F}_q)=2$. Using the equation in (30) and that $\delta =1$, we obtain

$$\begin{aligned} x^2+cx=1\iff \frac{x^2}{c^2}+\frac{x}{c}=\frac{1}{c^2}\iff y^2+y=\frac{1}{c^2} \end{aligned}$$

(34)

where $y=x/c$. Note that, if ${\text {Tr}}(1/c^2)={\text {Tr}}(1/c)=0$ then $y=x/c\in \mathbb {F}_q$, so $x\in \mathbb {F}_q\cap \mu _{q+1}=\{1\}$ which is not possible by the assumption $h(1)\ne 0$, therefore ${\text {Tr}}(1/c)=1$. Next, assume that $char(\mathbb {F}_q)$ is odd. Using the equation in (30) and that $\delta =1$, we obtain

$$\begin{aligned} x^2-cx+1=x^2-cx+\dfrac{c^2}{4}+1-\dfrac{c^2}{4}=0 \Leftrightarrow x^2-cx+\dfrac{c^2}{4}=\dfrac{c^2-4}{4}\nonumber , \end{aligned}$$

which holds if and only if

$$\begin{aligned} \left( x-\dfrac{c}{2}\right) ^2=\dfrac{c^2-4}{4}. \end{aligned}$$

(35)

Using the equation in (35) and the claim, we obtain that $\dfrac{c^2-4}{4}$ must be a nonsquare in $\mathbb {F}_q$, or equivalently $c^2-4$ must be a nonsquare in $\mathbb {F}_q$ and this completes the proof of the secod condition. $\square$

Now, suppose that h(x) has no roots in $\mu _{q+1}$, then for any $x\in \mu _{q+1}$ we have:

$$\begin{aligned} x^3h(x)^{q-1}=\dfrac{x^3(1+bx^{2q}+cx^{3q})}{1+bx^2+cx^3}=\dfrac{x^3(1+bx^{-2}+cx^{-3})}{1+bx^2+cx^3}=\dfrac{x^3+bx+c}{cx^3+bx^2+1}.\nonumber \end{aligned}$$

Let $g(x)=\dfrac{x^3+bx+c}{cx^3+bx^2+1}$, $\displaystyle \phi \left( x\right) =\frac{x+z}{x+z^q}$ and thus $\displaystyle \phi ^{-1}\left( x\right) = \frac{xz^q-z}{1-x}$, where $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_q$. Let $\mathbb {F}_q$ be a finite field of odd characteristic and $z^q=-z$, $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_q$. We define $\Delta (z;x):=(x+z)^3+b(x+z)(x+z^q)^2+c(x+z^q)^3$ and so we obtain $\Delta (z^q;x)=c(x+z)^3+b(x+z)^2(x+z^q)+(x+z^q)^3$. Then we have

$$\begin{aligned} (g\circ \phi )(x) =\dfrac{\Delta (z;x)}{\Delta (z^q;x)}= \dfrac{(x+z)^3+b(x+z)(x+z^q)^2+c(x+z^q)^3}{c(x+z)^3+b(x+z)^2(x+z^q)+(x+z^q)^3}\nonumber \end{aligned}$$

and thus

$$\begin{aligned} (\phi ^{-1}\circ g\circ \phi )(x) =\dfrac{\dfrac{\Delta (z;x)}{\Delta (z^q;x)}z^q-z}{1-\dfrac{\Delta (z;x)}{\Delta (z^q;x)}}= \dfrac{\Delta (z;x)z^q-z\Delta (z^q;x)}{\Delta (z^q;x)-\Delta (z;x)},\nonumber \end{aligned}$$

where

$$\begin{aligned} \Delta (z;x)z^q-z\Delta (z^q;x)=-2z\left( (1+b+c)x^3+z^2(3-b+3c)x\right) \nonumber \end{aligned}$$

and

$$\begin{aligned} \Delta (z^q;x)-\Delta (z;x)=2z\left( (3c+b-3)x^2+z^2(c-1-b)\right) .\nonumber \end{aligned}$$

Thus,

$$(\phi ^{-1}\circ g\circ \phi )(x) =\dfrac{\Delta (z;x)z^q-z\Delta (z^q;x)}{\Delta (z^q;x)-\Delta (z;x)}=-\dfrac{(1+b+c)x^3+z^2(3+3c-b)x}{(3c+b-3)x^2+z^2(c-1-b)}.$$

First we deal with the case where $3-b-3c=0$ in the following proposition.

Proposition 6

Let $\mathbb {F}_q$ be finite field of odd characteristic, where $\gcd (3,q-1)=1$. Let $h(x)=1+bx^2+cx^3$ with $b,c\in \mathbb {F}_q^*$. Assume that $3-b-3c=0$. There are no permutation polynomials of the form $f(x)=x^3h(x^{q-1})$ of $\mathbb {F}_{q^2}$ in this case.

Proof

The proof can be done in an analogous way to Proposition 2 therefore we omit the proof in order not to repeat the similar long discussions. $\square$

Next, assume that $3-b-3c\ne 0$. Note also that $1+b-c\ne 0, 1+b+c\ne 0$ since $h(-1)\ne 0, h(1)\ne 0$. Then we have:

$$\begin{aligned} \dfrac{x^3+z^2\dfrac{(3-b+3c)}{(1+b+c)x}}{x^2+\dfrac{(1+b-c)}{(3-b-3c)}z^2}=\dfrac{x^3+Ax}{x^2+B}, \end{aligned}$$

(36)

where $A=z^2\dfrac{(3-b+3c)}{1+b+c}$ and $B=z^2\dfrac{(1+b-c)}{3-b-3c}$. First, we consider the case where $-B$ is a square in $\mathbb {F}_q$. In this case there exists $x\in \mathbb {F}_q$ such that the denominator of the fraction in (36), that is $x^2+B$, becomes zero which implies that $\infty$ has at least three distinct preimages under the map $(\phi ^{-1}\circ f\circ \phi )(x)$ and therefore f(x) is not a permutation polynomial. Thus, from here on assume that $-B$ is not a square in $\mathbb {F}_q$, that is, $\frac{(1+b-c)}{3c+b-3}$ is a square in $\mathbb {F}_q$ since $z\in \mathbb {F}_{q^2}\setminus \mathbb {F}_q$. Computing $\dfrac{\dfrac{x^3+Ax}{x^2+B}-\dfrac{y^3+Ay}{y^2+B}}{x-y}$ and simplifying one gets:

$$\begin{aligned} \mathcal {C}(x,y):=x^2y^2+(B-A)xy+B(x^2+y^2)+AB. \end{aligned}$$

(37)

That is, $(\phi ^{-1}\circ g\circ \phi )$ permutes $\mathbb {F}_q$ if and only $\mathcal {C}(x,y)$ defined in (37) is not zero for any $x,y\in \mathbb {F}_q$ with $x\ne y$.

The following theorem completes the problem in the remaining case for finite fields of odd characteristic, where $3-b-3c\ne 0$.

Theorem 7

Let $\mathbb {F}_q$ be a finite field of odd characteristic, where $gcd(3,q-1)=1$. Let $h(x)=1+bx^2+cx^3$ with $b,c\in \mathbb {F}_q^*$. Assume that $3-b-3c\ne 0$. Then $x^3h(x^{q-1})$ is a permutation polynomial of $\mathbb {F}_{q^2}$ iff one of the following conditions hold:

• i $b=1-c^2$ and $c^2-4$ is a nonzero square in $\mathbb {F}_q$,

• ii $char(\mathbb {F}_q)\ne 3$, $b=-3$, $c\ne -2,2$ and $\dfrac{4-c^2}{3}$ is a nonzero square in $\mathbb {F}_q$.

Proof

The proof can be done in an analogous way to Theorem 1 therefore we omit the proof in order not to repeat the similar long discussions on all possible decompositions. $\square$

Now, let $\mathbb {F}_q$ be a finte field with even characteristic. The following theorem is the main result of this section in even characteristic case.

Theorem 8

Let $\mathbb {F}_q$ be a finite field of even characteristic, where $q=2^{2k+1}, k\in \mathbb {N}$. Let $h(x)=1+bx^2+cx^3$ with $b,c\in \mathbb {F}_q^*$. Then $x^3h(x^{q-1})$ is a permutation polynomial of $\mathbb {F}_{q^2}$ iff one of the following conditions hold:

• i $b=1+c^2$ and ${\text {Tr}}(1/c)=0$,

• ii $b=1$ and ${\text {Tr}}(1/c)=1$.

Proof

The proof can be done in an analogous way to Theorem 2 therefore we omit the proof in order not to repeat the similar long discussions on all possible decompositions. $\square$

Example 3

In the following tables we explicitly give the coefficients over the finite fields $\mathbb {F}_5, \mathbb {F}_7, \mathbb {F}_9$ and $\mathbb {F}_{11}$ of all permutation polynomials obtained from Theorem 3. Here, $\mathbb {F}_5$ is the smallest nontrivial finite field containing coefficients b, c which give rise to permutation polynomials of the form $f(x)=x^3h(x^{q-1})$ of $\mathbb {F}_{25}$, where $h(x)=1+bx^2+cx^3$ with $b,c\in \mathbb {F}_{5}^*$. In Tables 4, 5, 6 and 7 below we list all pairs of coefficients (b, c) of permutation polynomials of $\mathbb {F}_{q^2}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=1+bx^2+cx^3$ with $b,c\in \mathbb {F}_q^*$, obtained by Theorem 3 for $q=5,7,9,11$ respectively. Note that, in Table 6, $x^2+2x+2\in \mathbb {F}_3[x]$ is the minimal polynomial of $\alpha$, that is $\mathbb {F}_9^*=<\alpha>$.

Table 4 List of all pairs of coefficients (b, c) of permutation polynomials of $\mathbb {F}_{25}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=1+bx^2+cx^3$, with $b,c\in \mathbb {F}_5^*$, obtained by Theorem 3

Table 5 List of all pairs of coefficients (b, c) of permutation polynomials of $\mathbb {F}_{49}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=1+bx^2+cx^3$, with $b,c\in \mathbb {F}_7^*$, obtained by Theorem 3

Table 6 List of all pairs of coefficients (b, c) of permutation polynomials of $\mathbb {F}_{81}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=1+bx^2+cx^3$, with $b,c\in \mathbb {F}_9^*$, obtained by Theorem 3

Table 7 List of all pairs of coefficients (b, c) of permutation polynomials of $\mathbb {F}_{121}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=1+bx^2+cx^3$, with $b,c\in \mathbb {F}_{11}^*$, obtained by Theorem 3

Example 4

In the following table we explicitly give the coefficients over the finite field $\mathbb {F}_8$ of all permutation polynomials of $\mathbb {F}_{64}$ obtained from Theorem 2. Let $x^3+x+1\in \mathbb {F}_2[x]$ be the minimal polynomial of $\alpha$, that is $\mathbb {F}_8^*=<\alpha>$. In Table 8 below we list all pairs of coefficients (b, c) of permutation polynomials of $\mathbb {F}_{64}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=1+bx^2+cx^3$, with $b,c\in \mathbb {F}_8^*$ obtained by Theorem 2.

Remark 2

In [42] Zha, Hu and Fan found out that the polynomials of the form $x^3+x^{2q+1}+x^{3q}$ are permutation polynomials over $\mathbb {F}_{q^2}$, where $q=2^m$ iff m is odd (see [42, Theorem 4.1]). In this section we worked on the more general polynomial $f(x)=x^3+bx^{2q+1}+cx^{3q}$ over $\mathbb {F}_{q^2}$, where $b,c\in \mathbb {F}_q^*$ for both odd and even characteristic cases and we completely determined all necessary and sufficient conditions for f(x) to be a permutation polynomial of $\mathbb {F}_{q^2}$.

5 A comparison with known permutation trinomials

Definition 1

[36] Two permutation polynomials $f(x),g(x)\in \mathbb {F}_q[x]$ are called quasi-multiplicative equivalent (abbreviated as QM equivalent), if there exists $d\in \mathbb {Z}$, $1\le d\le q-1$ with $\gcd (d,q-1)=1$ and $f(x)=ag(cx^d)$, where $a,c\in \mathbb {F}_q^*$.

The above definition which was introduced by Wu, Yuan, Ding and Ma [41], is being used in the literature (see for instance [12, 33, 36]) in order to decide whether permutations which are proposed to be new are really new or not. In general it is nontrivial to determine the QM equivalence of two permutation polynomials theoretically.

In this section we prove that the classses of permutation trinomials obtained in this paper are not QM equivalent to known classes. We first observe that two QM equivalent permutations must have exactly the same number of terms. Therefore, we only need to compare the permuation trinomials found in this paper with known permutation trinomials over $\mathbb {F}_{q^2}$. We use the method in [36] for this purpose.

In order to determine whether the permutation polynomials $f(x)=x^3(1+ax^{q-1}+bx^{2(q-1)})$ and $f(x)=x^3(1+bx^{2q-2}+cx^{3q-3})$ over $\mathbb {F}_{q^2}$, where $a,b,c \in \mathbb {F}_q^*$ are QM equivalent to any permutation trinomial of the form $g(x)=a_1x^{k_1}+a_2x^{k_2}+a_3x^{k_3}\in \mathbb {F}_q[x]$ we will use the following strategy:

• Step 1: Determining whether there exists an integer k, $1\le k\le q^2-1$, such that $\gcd (k,q^2-1)=1$ and $\{k_1,k_2,k_3 \bmod (q^2-1)\}=\{3k,(q+2)k,(2q+1)k\}$.

• Step 2: Comparison of the coefficients of $b_2f(b_1x^k)$ and g(x).

In the above strategy, if Step 1 is not satisfied then f(x) and g(x) will not be QM equivalent, otherwise we will go on with Step 2 and compare the coefficients of $b_2f(b_1x^k)$ and g(x). In Step 1 we observe that in any permutation polynomial which is QM equivalent to our classes of permutation polynomials, at least one of the $k_i$’s must be a multiple of 3. For this purpose we constructed Table 9 by collecting all known permutation trinomials of this form over finite fields of both even and odd characteristic.

Table 8 List of all pairs of coefficients (b, c) of permutation polynomials of $\mathbb {F}_{64}$ of the form $f(x)=x^3h(x^{q-1})$, where $h(x)=1+bx^2+cx^3$, with $b,c\in \mathbb {F}_8^*$, obtained by Theorem 4

Table 9 List of all known classes of permutation trinomials of the form $ax^{3r}+bx^s+cx^t$ over $\mathbb {F}_{q^{2}}$

Let $f(x)=x^3(1+ax^{q-1}+bx^{2(q-1)})$ which we considered in Section 3. First we compare f(x) with the polynomial $g_1(x)=x^3+x^{3.2^m}+x^{2^{m+2}-1}\in \mathbb {F}_{2^{2m}}[x]$ in [14, Theorem 3.5] in Table 9. Note that $3\mid q^2-1$, where $q=2^m$. Let $(a_1,a_2,a_3)=(3,3+(q-1),3+2(q-1))$ and $(b_1,b_2,b_3)=(3,3q,4q-1)$. Note that $\{a_1,a_2,a_3\}$ is the set of the exponents of f(x) and $\{b_1,b_2,b_3\}$ is the set of exponents of $g_1(x)$. Assume that there exists an integer k, $1\le k\le q^2-1$ with $\gcd (k,q^2-1)=1$ such that $\{ka_1\,(\bmod \,\,q^2-1),ka_2\,(\bmod \,\,q^2-1),ka_3\,(\bmod \,\,q^2-1)\}=\{b_1,b_2,b_3\}$. As $3\mid q^2-1$, $b_1\equiv 0\,(\bmod \,\,3)$ and $b_2\equiv 0\,(\bmod \,\,3)$ then it is necessary that there are at least two elements $a\in \{a_1,a_2,a_3\}$ such that $a\equiv 0\,(\bmod \,\,3)$. However $a_2\not \equiv 0\,(\bmod \,\, 3)$ and $a_3\not \equiv 0\,(\bmod \,\, 3)$. This proves that f(x) can not be QM equivalent to $g_1(x)$. Let $g_i(x)$ be the corresponding polynomial in the i-th row of Table 9 for $i=1,2,3,4,5$. The same argument we used above works for $g_i(x)$ for $1\le i\le 3$ and hence f(x) is not QM equivalent to $g_i(x)$ for $1\le i\le 3$. Next we consider $g_i(x)$ for $i=4,5$. Note that $\gcd (3,q-1)=1$ for f(x). Hence, if $char(\mathbb {F}_q)\ne 3$ then $3\mid q^2-1$. The same argument we used above works for $g_i(x)$ for $i=4,5$ when $char(\mathbb {F}_q)\ne 3$. Assume that $char(\mathbb {F}_q)=3$. Then $8\mid q^2-1$. In this case $q-1\equiv 0$ or $2\,(\bmod \,\,8)$. Let $(a_1,a_2,a_3)$ be the exponents as above and let $(b_1,b_2,b_3)=3(q-1, q-1,3)$ be the exponents of $g_i(x)$. Note that $a_j\not \equiv 0\,(\bmod \,\,8)$ for $1\le j\le 3$. However $b_1\equiv 0$ or $6\,(\bmod \,\,8)$. Hence it is impossible to choose $1\le k\le q^2-1$ such that $\gcd (k,q^2-1)=1$ and $ka_j\equiv b\,(\bmod \,\,q^2-1)$. This completes the proof of the fact that f(x) can not be QM equivalent to any $g_i(x)$ in Table 9 for each $1\le i \le 5$. Let $f(x)=x^3(1+bx^{2q-2}+cx^{3q-3})$ that we considered in Section 4. Assume that f(x) is QM equivalent to $g_1(x)$ in Table 9. This implies that there exists $\alpha ,\beta \in \mathbb {F}_{q^2}$ and $1\le k\le q^2-1$ with $\gcd (k,q^2-1)=1$ such that $\alpha g_1(\beta x^k)=f(x)$. Consequently we obtain that either

$$\begin{aligned} \alpha \beta ^3=1, \alpha \beta ^{4q-1}=b, \alpha \beta ^{3q}=c \end{aligned}$$

(38)

or

$$\begin{aligned} \alpha \beta ^3=c, \alpha \beta ^{3q}=1, \alpha \beta ^{4q-1}=b . \end{aligned}$$

(39)

If (38) and (26) hold, then $b=c=1$. This completes the proof of the fact that f(x) in Section 4 is not QM equivalent to $g_1(x)$ if $(b,c)\ne (1,1)$. The argument above also show that f(x) in 4 is not QM equivalent to $g_i(x)$ with $1\le i\le 3$ if $(b,c)\ne (1,1)$.

Similarly we observe that the polynomial f(x) in Section 4 is not QM equivalent to $g_4(x)$ and $g_5(x)$. Thus the classes of permutation polynomials obtained in this paper are completely new except the case $(b,c)=(1,1)$ for the polynomial $f(x)=x^3(1+bx^{2q-2}+cx^{3q-3})$.