Some Proposed Problems on Permutation Polynomials over Finite Fields

Abstract

From the 19th century, the theory of permutation polynomial over finite fields, that are arose in the work of Hermite and Dickson, has drawn general attention. Permutation polynomials over finite fields are an active area of research due to their rising applications in mathematics and engineering. The last three decades has seen rapid progress on the research on permutation polynomials due to their diverse applications in cryptography, coding theory, finite geometry, combinatorics and many more areas of mathematics and engineering. For this reason, the study of permutation polynomials is important nowadays. In this chapter, we propose some new problems in connection to permutation polynomials over finite fields by the help of prime numbers.

1. Introduction to permutation polynomials

In this section, we collect some basic facts about permutation polynomials over a finite field that will be frequently used throught the chapter. First it will be convenient to define permutation polynomial over a finite field.

Definition 1. A polynomial $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ is said to be a permutation polynomial over ${\mathbb{F}}_q$ for which the associated polynomial function $c\mapsto f\left(c\right)$ ia a permutation of ${\mathbb{F}}_q$, that is, the mapping from ${\mathbb{F}}_q$ to ${\mathbb{F}}_q$ defined by $f$ is one–one and onto.

Finite fields are polynomially complete, that is, every mapping from ${\mathbb{F}}_q$ into ${\mathbb{F}}_q$ can be represented by a unique polynomial over ${\mathbb{F}}_q$. Given any arbitrary function $\varphi :{\mathbb{F}}_q\to {\mathbb{F}}_q$, the unique polynomial $g\in {\mathbb{F}}_q\left[x\right]$ with $deg\left(g\right)<q$ representing $\varphi$ can be found by the formula $g\left(x\right)={\sum }_{c\in {\mathbb{F}}_q}\varphi \left(c\right)\left(1-{\left(x-c\right)}^{q-1}\right)$, see ([1], Chapter 7).

Two polynomials represent the same function if and only if they are the same by reduction modulo $x^q-x$, according to the following result.

Lemma 1. [1] For $f,g\in {\mathbb{F}}_q\left[x\right]$ we have $f\left(\alpha \right)=g\left(\alpha \right)$ for all $\alpha \in {\mathbb{F}}_q$ if and only if $f\left(x\right)\equiv g\left(x\right)\left(mod\left(x^q-x\right)\right)$.

Due to the finiteness of the field, the followings are the equivalent conditions for a polynomial to be a permutation polynomial.

Definition 2. The polynomial $f\in {\mathbb{F}}_q\left[x\right]$ is a permutation polynomial of ${\mathbb{F}}_q$ if and only if one of the following conditions holds:

1. the function $f:c\mapsto f\left(c\right)$ is onto;

2. the function $f:c\mapsto f\left(c\right)$ is one-to-one;

3. $f\left(x\right)=a$ has a solution in ${\mathbb{F}}_q$ for each $a\in {\mathbb{F}}_q$;

4. $f\left(x\right)=a$ has a unique solution in ${\mathbb{F}}_q$ for each $a\in {\mathbb{F}}_q$.

1.1 Criteria for permutation polynomials

Some well-known criteria for being permutation polynomials are the following.

1.1.1 First criterion for permutation polynomials

The first and in some way most useful, criterion was proved by Hermite for $q$ prime and by Dickson for general $q$. This criterion has special name what is called Hermite’s criterion.

Theorem 3 (Hermite’s criterion). [1] A polynomial $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ is a permutation polynomial of ${\mathbb{F}}_q$ if and only if following two conditions hold:

1. $f\left(x\right)$ has exactly one root in ${\mathbb{F}}_q$;

2. for each integer $t$ with $1\le t\le q-2$ and t not divisible by $p$, the residue $f{\left(x\right)}^t\left(\mathit{mod}\left(x^q-x\right)\right)$ has degree $\le q-2$.

For the detailed proof, one can see [1]. Above theorem is mainly used to show negative result. The following is a useful corollary for this purpose.

Corollary 4. There is no permutation polynomial of degree $d$ dividing $q-1$ over ${\mathbb{F}}_q$.

Proof. We note that $deg\left(f^{\frac{q-1}{d}}\right)=q-1$. The proof follows from the last condition of Hermite’s criterion.

Remark 5. Hermite’s criterion is interesting theoretically but difficult to use in practice.

1.1.2 Second criterion for permutation polynomials

Theorem 6. [1] Let $f\in {\mathbb{F}}_q\left[x\right]$. Write

$$D\left(f\right)=\left\{\frac{f\left(b\right)-f\left(a\right)}{b-a}:a\ne b\in {\mathbb{F}}_q\right\}.$$

Then $f\left(x\right)$ is a permutation polynomial of ${\mathbb{F}}_q$ if and only if $0\notin D\left(f\right)$.

1.1.3 Third criterion for permutation polynomials

Theorem 7. [1] The polynomial $f\in {\mathbb{F}}_q\left[x\right]$ is a permutation polynomial of ${\mathbb{F}}_q$ if and only if

$$\sum _{c\in {\mathbb{F}}_q}\chi \left(f\left(c\right)\right)=0$$

for all nontrivial additive characters $\chi$ of ${\mathbb{F}}_q$.

1.1.4 Fourth criterion for permutation polynomials

Theorem 8. [1] Let the trace map $\mathit{Tr}:{\mathbb{F}}_{q^n}\to {\mathbb{F}}_q$ be defined as $\mathit{Tr}\left(x\right)=x+x^q+\cdots +x^{q^{n-1}}$. Then the polynomial $f\in {\mathbb{F}}_q\left[x\right]$ is a permutation polynomial of ${\mathbb{F}}_q$ if and only if for every nonzero $\eta \in {\mathbb{F}}_q$,

$$\sum _{x\in {\mathbb{F}}_q}{\zeta }^{\mathrm{Tr}\left(\mathit{\eta f}\left(x\right)\right)}=0,$$

where $\zeta =e^{\frac{2\mathit{\pi i}}{p}}$ is a primitive $p$-th root of unity.

In what follows, we will discuss some well known classes of permutation polynomials which are commonly used.

1.2 Some well-known classes of permutation polynomials

In this subsection, several basic results on permutation polynomials are presented. Many times, we see that one of these general classes are obtained by simplifying complicated classes of permutation polynomials for proving their permutation nature.

Theorem 9. [1] Every linear polynomial, that is, polynomial of the form $\mathit{ax}+b,a\ne 0$ over finite field is a permutation polynomial.

Theorem 10. [1] The monomial $x^n$ is a permutation polynomial over ${\mathbb{F}}_q$ if and only if $gcd\left(n,q-1\right)=1$.

Theorem 11. Let $g\left(x\right)$ and $h\left(x\right)$ be two polynomials over ${\mathbb{F}}_q$. Then $f\left(x\right)=g\left(h\left(x\right)\right)$ is a permutation polynomial over ${\mathbb{F}}_q$ if and only if both $g\left(x\right)$ and $h\left(x\right)$ permute ${\mathbb{F}}_q$.

1.3 Open problems on permutation polynomials

Very little is known concerning which polynomials are permutation polynomials, despite the attention of numerous authors. There are so many open problems and conjectures on permutation polynomials over finite fields but here we are listing few of them.

Open Problem 12. [2] Find new classes of permutation polynomials of ${\mathbb{F}}_q$.

Although several classes of permutation polynomials have been found in recent years, but, an explicit and unified characterization of permutation polynomials is not known and seems to be elusive today. Therefore, it is both interesting and important to find more explicit classes of permutation polynomials.

Open Problem 13. [2] Find inverse polynomial of known classes of permutation polynomials over ${\mathbb{F}}_q$.

The construction of permutation polynomials over finite fields is an old and difficult problem that continues to attract interest due to their applications in various area of mathematics. However, the problem of determining the compositional inverse of known classes of permutation polynomial seems to be an even more complicated problem. In fact, there are very few known permutation polynomials whose explicit compositional inverses have been obtained, and the resulting expressions are usually of a complicated nature except for the classes of the permutation linear polynomials, monomials, Dickson polynomials.

Open Problem 14. [2] Find $N_d$, where $N_d=N_d\left(q\right)$ denote the number of permutation polynomials of degree $d$ over ${\mathbb{F}}_q$.

To date, there is no method for counting the exact number of permutation polynomials of given degree. However, Koyagin and Pappalardi [3, 4], found the asymptotic formula for the number of permutations for which the associated permutation polynomial has degree smaller than $q-2$.

1.4 Applications of permutation polynomials

The study of permutation polynomials would not complete without mentioning their applications in other area of mathematics and engineering. It is a major subject in the theory and applications of finite fields. The study of permutation polynomials over the finite fields is essentially about relations between the algebraic and combinatoric structures of finite fields. Nontrivial permutation polynomials are usually the results of the intricate and sometimes mysterious interplay between the two structures. Here we mention some applications of permutation polynomials.

1.5 Coding theory

In coding theory, error correcting codes are fundamental to many digital communication and storage systems, to improve the error performance over noisy channels. First proposed in the seminal work of Claude Shannon [5], they are now ubiquitous and included even in consumer electronic systems such as compact disc players and many others. Permutation polynomials have been used to construct error correcting codes. Laigle-Chapuy [6] proposed a conjecture equivalent to a conjecture related to cross-correlation functions in coding theory. In [7], Chunlei and Helleseth derived several classes of $p$-ary quasi-perfect codes using permutation polynomials over finite fields. In 2005, Carlet, Ding and Yuan [8] obtained Linear codes using planar polynomials over finite fields.

1.6 Cryptography

The advent of public key cryptography in the 1970’s has generated innumerable security protocols which find widespread application in securing digital communications, electronic funds transfer, email, internet transactions and the like. In recent years, permutation polynomials over finite fields has been used to design public key cryptosystem. Singh, Saikia and Sarma [9, 10, 11, 12, 13, 14, 15] designed efficient multivariate public key cryptosystem using permutation polynomials over finite fields. The same authors used a group of linearized permutation polynomials to design an efficient multivariate public key cryptosystem [16].

Permutation polynomials with low differential uniformity are important candidate functions to design substitution boxes (S-boxes) of block ciphers. S-boxes can be constructed from permutation polynomials over even characteristics [17] with desired cryptographic properties such as low differential uniformity and play important role in iterated block ciphers.

1.7 Finite geometry

Permutation polynomial $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ is called a complete permutation polynomial if $f\left(x\right)+x$ is also a permutation polynomial and an orthomorphism polynomial if $f\left(x\right)-x$ is also a permutation polynomial. Orthomorphism polynomials can be used in check digit systems to detect single errors and adjacent transpositions whereas complete permutation polynomials to detect single and twin errors. For more details on complete mappings and orthomorphisms over finite fields, we refer to the reader [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]. In addition, complete permutation polynomials are very useful in the study of orthogonal latin squares and orthomorphism polynomials are useful in close connection to hyperovals in finite projective plane. In 1968, planar functions were introduced by Dembowski and Ostrom [20] in context of finite geometry to describe projective planes with specific properties. Since 1991, planar functions have attracted interest also from cryptography as functions with optimal resistance to differential cryptanalysis.

2. Some proposed problems

Let ${\mathbb{F}}_q$ denotes finite fields with $q=2^m$ elements. Nowaday permutation polynomials are an interesting subject for study not for only research purposes but also for their various applications in many areas of mathematics and engineering. We refer [21] to the reader for recent advances and contributions to the area.

The rising applications of permutation polynomials in mathematics and engineering from last decade propels us to do new research. Recently, permutation polynomials with few terms over finite fields paying more attention due to their simple algebraic form and some extraordinary properties. We refer to the reader [22, 23, 24, 25] for some recent developments. This motivates us to propose some new problems. In this chapter, by the help of prime numbers, we constructed several new polynomials that have no root in ${\mu }_{2^m+1}$ and two of them are generalizations of known ones. The constructed polynomials here may lay a good foundation for finding new classes of permutation polynomials.

Throughout the chapter, for a positive integer $d$, the set of $d$-th roots of unity in the algebraic closure ${\overline{\mathbb{F}}}_q$ of ${\mathbb{F}}_q$ is denoted by ${\mu }_d$. That is,

$${\mu }_d=\left\{x\in {\overline{\mathbb{F}}}_q:x^d=1\right\}.$$

For every element $x\in {\mathbb{F}}_q$, we denote $x^{2^m}$ by $\overline{x}$ in analogous to the usual complex conjugation. Clearly, $x\overline{x},x+\overline{x}\in {\mathbb{F}}_q$. Define the unit circle of ${\mathbb{F}}_q$ as

$${\mu }_{2^m+1}=\left\{x\in {\mathbb{F}}_q:x^{2^m+1}=x\overline{x}=1\right\}.$$

The permutation polynomial of the form $x^{r}h\left(x^{\frac{q-1}{d}}\right)$ are interesting and have been paid attention, where $h\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ with $d$ dividing $q-1$ and $1\le r\le \frac{q-1}{d}$. The permutation behavior of this type of polynomials are investigated by Park and Lee [26] and Zieve [27].

Lemma 2 ([26, 27]). Let $r,d>0$ with $d$ dividing $q-1$ and $h\left(x\right)\in {\mathbb{F}}_q\left[x\right]$. Then $f\left(x\right)=x^{r}h\left(x^{\frac{q-1}{d}}\right)$ permutes ${\mathbb{F}}_q$ if and only if

1. $gcd\left(r,\frac{q-1}{d}\right)=1$ and

2. $x^{r}h{\left(x\right)}^{\frac{q-1}{d}}$ permutes ${\mu }_d$.

In view of Lemma 2, the permutation property of $x^{r}h\left(x^{\frac{q-1}{d}}\right)$ is decided by whether $x^{r}h{\left(x\right)}^{\frac{q-1}{d}}$ permutes ${\mu }_d$. In the process to prove that $x^{r}h{\left(x\right)}^{\frac{q-1}{d}}$ permutes ${\mu }_d$, first we need to prove that $h\left(x\right)$ has no root in ${\mu }_d$ [22]. Thus the polynomials which have no roots in ${\mu }_d$ are interesting and can be used to construct new classes of permutation polynomials. Therefore, it is is both interesting and important to find more polynomials that have no roots in ${\mu }_d$ which play key role in showing the permutation property of $x^{r}h{\left(x\right)}^{\frac{q-1}{d}}$. For more recent progresses about this type of constructions, we refer [23, 25]. In next section, we also need the following definition.

Definition 15. Two polynomials are said to be conjugate to each other if one is obtained by raising $2^m$-th power and multiplying them by the highest degree term of the other.

Next, we propose some new problems by reviewing various recent contributions. The polynomials that have no roots in ${\mu }_{2^m+1}$ play important role in theory of finite fields because these polynomials may give rise to a new class of permutation polynomials.

Let $p\in \left\{1,2,\dots ,2^m-1\right\}$, and let the binary representation of $p$ be

$$p=\sum _{k=0}^{m-1}{p}_k{2}^k$$

with $p_k\in \left\{0,1\right\}$. Define the weight of $p$ by

$$w\left(p\right)=\sum _{k=0}^{m-1}{p}_k.$$

We define a polynomial function over ${\mathbb{F}}_{2^m}$ as

$$L_p\left(x\right)=\sum _{k=0}^{m-1}{p}_k\cdot x^{2^k}.$$

For example,

$$L_{11}\left(x\right)=1+x+x^3$$

$$L_{13}\left(x\right)=1+x^2+x^3$$

$$L_{19}\left(x\right)=1+x+x^4.$$

We observe that there is a good connection between prime numbers and polynomials that have no roots in ${\mu }_{2^m+1}$ in the sense that most of these polynomials can be derived from prime numbers. In this way, for the prime numbers 11, 13 and 19 we get the polynomials $L_{11}\left(x\right),L_{13}\left(x\right)$ and $L_{19}\left(x\right)$ respectively that have no roots in ${\mu }_{2^m+1}$. This result is obtained by Gupta and Sharma in [22]. More precisely,

Lemma 3 ([22]). Let $m>0$ be integer. Then each of the polynomials $1+x+x^3,1+x^2+x^3$ and $1+x+x^4$ have no roots in ${\mu }_{2^m+1}$.

Similarly, for the primes 59 and 109, we obtain the same polynomials as in [25] of Xu Guangkui et al.

Lemma 4 ([25]). Let $m>0$ be integer. Then each of the polynomials $1+x+x^3+x^4+x^5$ and $1+x^2+x^3+x^5+x^6$ have no roots in ${\mu }_{2^m+1}$.

It is not necessary that all polynomials are obtained from prime numbers. For example, the polynomials $1+x^3+x^4$ by Gupta and Sharma in [22] and $1+x+x^2+x^4+x^5$ by Xu Guangkui et al. [25] are obtained corresponding to the number 25 and 55 respectively. In this respect, we propose the following problem.

Problem 16. Which prime numbers will give polynomials that have no roots in ${\mu }_{2^m+1}?$.

The generalization of Lemma 2.2 of [22] corresponding to the polynomials $1+x+x^3$ and $1+x^2+x^3$ are given by the following lemma.

Lemma 5. For sufficiently large positive integers $m$ and $n$, each of the polynomials $1+x^n+x^{2n-1}$ and $1+x^n+x^{2n+1}$ have no roots in ${\mu }_{2^m+1}$.

Proof. Suppose $\alpha \in {\mu }_{2^m+1}$ satisfies the equation

$$1+{\alpha }^n+{\alpha }^{2n-1}=0.$$E1

Raising both sides of (1) to the $2^m$-th power and multiplying by ${\alpha }^{2n-1}$, we get

$$1+{\alpha }^{n-1}+{\alpha }^{2n-1}=0.$$E2

Adding (1) and (2), we get

$${\alpha }^{n-1}+{\alpha }^n=0$$

Since $\alpha \ne 0$, which gives $\alpha =1$. But $\alpha =1$ does not satisfy (1), a contradiction. Hence $1+x^n+x^{2n-1}$ has no roots in ${\mu }_{2^m+1}$. Similarly, we can show that the polynomial $1+x^n+x^{2n+1}$ has no roots in ${\mu }_{2^m+1}$.

In particular, we get the following lemma by Gupta and Sharma [22].

Lemma 6 ([22]). Let $m>0$ be integer. Then each of the polynomials $1+x+x^3$ and $1+x^2+x^3$ have no roots in ${\mu }_{2^m+1}$.

Based on the Lemma 5, we propose the following problem.

Problem 17. Let $h_1\left(x\right)=1+x^n+x^{2n-1}$ and $h_2\left(x\right)=1+x^n+x^{2n+1}$. Characterize $n$ and $r$ such that the polynomials $x^r{h}_1{\left(x\right)}^{2^m-1}$ and $x^r{h}_2{\left(x\right)}^{2^m-1}$ permutes ${\mu }_{2^m+1}$.

By the help of prime numbers below 1000, we obtain the following polynomials that have no roots in ${\mu }_{2^m+1}$. Most of these polynomials are directly or indirectly associated with prime numbers in the sense that corresponding to either each polynomial or their conjugate polynomial, a prime number can be obtained. The proof of the following lemmas can be done in similar fashion as in [22].

Lemma 7. For a positive integer $m$, each of the polynomials $1+x+x^2+x^7+x^8$, $1+x+x^6+x^7+x^8$, $1+x+x^3+x^7+x^8$, $1+x+x^5+x^7+x^8$, $1+x+x^4+x^8+x^9$, $1+x+x^5+x^8+x^9$, $1+x^2+x^3+x^5+x^8$, $1+x^3+x^5+x^6+x^8$, $1+x+x^3+x^4+x^8$, $1+x^4+x^5+x^7+x^8$, $1+x^2+x^3+x^6+x^8$, $1+x^2+x^5+x^6+x^8$, $1+x^3+x^4+x^7+x^8$, $1+x+x^4+x^5+x^8$, $1+x^3+x^4+x^6+x^9$, $1+x^3+x^5+x^6+x^9$, $1+x+x^2+x^7+x^9$, $1+x^2+x^7+x^8+x^9$, $1+x^2+x^4+x^7+x^9$, $1+x^2+x^5+x^7+x^9$ have no roots in ${\mu }_{2^m+1}$.

Lemma 8. For a positive integer $m$, each of the polynomials $1+x+x^3+x^5+x^6+x^7+x^8$, $1+x+x^2+x^3+x^5+x^7+x^8$, $1+x+x^2+x^3+x^6+x^7+x^8$, $1+x+x^2+x^5+x^6+x^7+x^8$, $1+x+x^4+x^5+x^6+x^7+x^8$, $1+x+x^2+x^3+x^4+x^7+x^8$, $1+x+x^3+x^5+x^6+x^8+x^9$, $1+x+x^3+x^4+x^6+x^8+x^9$, $1+x+x^3+x^4+x^5+x^8+x^9$, $1+x+x^4+x^5+x^6+x^8+x^9$, $1+x+x^2+x^3+x^7+x^8+x^9$, $1+x+x^2+x^6+x^7+x^8+x^9$, $1+x+x^2+x^4+x^7+x^8+x^9$, $1+x+x^2+x^5+x^7+x^8+x^9$, $1+x^2+x^3+x^4+x^6+x^7+x^9$, $1+x^2+x^3+x^5+x^6+x^7+x^9$, $1+x^2+x^3+x^4+x^5+x^7+x^9$, $1+x^2+x^4+x^5+x^6+x^7+x^9$, have no roots in ${\mu }_{2^m+1}$.

Lemma 9. For a positive integer $m$, each of the polynomials $1+x+x^2+x^3+x^4+x^6+x^7+x^8+x^9$, $1+x+x^2+x^3+x^5+x^6+x^7+x^8+x^9$ have no roots in ${\mu }_{2^m+1}$.

The above list of polynomials are not complete. However, computational experiments shows that there should be more polynomials. A complete determination of all polynomials with few terms over finite fields seems to be out of reach for the time bing.

Now, we are in condition to propose the following problem in connection to above three lemmas.

Problem 18. Find new classes of permutation polynomials corresponding to polynomials obtained in Lemmas 7, 8 and 9.

Classification

AMS 2020 MSC: 11T06.