A general construction of permutation polynomials of \(\mathbb{F}_{q^2}\) (Q6156901)

Let \(p\) be a prime, \(q\) a power of \(p\), and \(\mathbb{F}_q\) denote the finite field with \(q\) elements. A polynomial \(f\in \mathbb{F}_q[x]\) is called a \textit{permutation polynomial} (PP) of \(\mathbb{F}_q\) if the associated mapping \(x\mapsto f(x)\) from \(\mathbb{F}_q\) to \(\mathbb{F}_q\) is a permutation of \(\mathbb{F}_q\). Let \(r\) be a positive integer, \(d\,|\,q-1\), and \(h(X)\in \mathbb{F}_q[x]\). It is well known that \(X^rh(X^{(q-1)/d})\) is a permutation polynomial of \(\mathbb{F}_q\) if and only if \(\text{gcd}(r,(q-1)/d)=1\) and \(X^rh(X)^{(q-1)/d}\) permutes the multiplicative group \(\mu_d:=\{x\in \mathbb{F}_q^*\,:\,x^d=1\}\). Replacing \(q\) with \(q^2\) and \(d\) with \(q+1\), we see that for \(h(X)\in \mathbb{F}_{q^2}[X]\), \(X^rh(X^{q-1})\) is a permutation polynomial of \(\mathbb{F}_{q^2}\) if and only if \(\text{gcd}(r,q-1)=1\) and \(X^rh(X)^{q-1}\) permutes \(\mu_{q+1}\). The following idea has been used by several authors to construct permutations of \(\mu_{q+1}\) of the form \(X^rh(X)^{q-1}\): Let \(H\) be a subgroup of \(\mu_{q+1}\) of small index. Construct a polynomial \(h(X)\in\mathbb{F}_{q^2}[X]\) such that \(h(X)^{q-1}\) induces monomial functions on each coset of \(H\) in \(\mu_{q+1}\). With such a property, \(X^rh(X)^{q-1}\) permutes \(\mu_{q+1}\) if and only if some simple number theoretic conditions on the parameters are satisfied. This method has produced many results. However, these results only deal with specific situations, leaving a unified treatment to be desired. In the paper under review, the authors take a general approach to the question. The main result is an algorithm, which is given at the end of this review, that produces {\em all} permutation polynomials of \(\mathbb{F}_{q^2}\) of the form \(X^rh(X^{q-1})\) such that \(h(X)^{q-1}\) induces monomial functions on the cosets of a subgroup in \(\mu_{q+1}\). The authors determine all permutation polynomials of \(\mathbb{F}_{q^2}\) resulting from this algorithm and it turns out that all these permutation binomials were all known previously. The authors also determine all permutation trinomials of \(\mathbb{F}_{q^2}\) resulting from the algorithm. There are four classes of such permutation trinomials, excluding those that were previously known. These four classes, in their generality, appear to be new, although many special cases have been discovered by other authors. Overall, this approach reveals many permutation polynomials that were not known previously. \textbf{Algorithm} Let \(r\) be a positive integer such that \(gcd(r,q-1)=1\) and let \(d\mid q+1\). \medskip \textbf{Input:} Sequences \(s_k\), \(t_k\), \(\tau_k\), \(\pi(k)\), \(\lambda_k\), \(0\le k<d\), described below. \medskip \textbf{Output:} A PP of \(\mathbb{F}_{q^2}\) of the form \(X^rh(X^{q-1})\) such that \(X^rh(X)^{q-1}\) is a monomial function on each \(A_k\), \(0\le k<d\). \medskip \textbf{Note:} All PPs of \(\mathbb{F}_{q^2}\) with such properties can be produced by this algorithm. \textbf{Step 1} Choose integer sequence \(s_k,t_k,\tau_k\ge \), \(0\le k<d\), such that \(s_k+t_k<(q+1)/d\), \(\tau_k\in\{0\}\cup[(q+1)/d-t_k,t_k]\), and \(e_k:=r-2s_k-t_k+\tau_k\) satisfies \(\gcd(e_k,(q+1)/d)=1\). \textbf{Step 2} Choose a sequence \(\pi(k)\in\mathbb Z/d\mathbb Z\), \(0\le k<d\), such that \(k\mapsto \pi(k)+e_kk\) permutes \(\mathbb Z/d\mathbb Z\). \textbf{Step 3} For each \(0\le k<d\), choose \(\lambda_k\in A_{\pi(k)}\) and \(L_k\in\mathcal L_k(t_k,\tau_k;\lambda_k)\). \medskip \textbf{Step 4} Compute the \(((q+1)/d)\times d\) matrix \([M_{ik}]\) such that \[ X^{s_k}L_k=\sum_iM_{ik}X^i, \] and compute the \(((q+1)/d)\times d\) matrix \[ [a_{ij}]=\frac 1d[M_{ik}][\varepsilon^{-kj}]. \] \textbf{Step 5} Let \[ h(X)=\sum_{i,j}a_{ij}X^{i+j(q+1)/d}. \] Then \(X^rh(X^{q-1})\) is the output PP of \(\mathbb{F}_{q^2}\). \textbf{Remark} In Step 3, when choosing \(L_k\in\mathcal L_k(t_k,\tau_k;\lambda_k)\), it is required that \(\gcd(L_k,X^{(q+1)/d}-\varepsilon^k)=1\). However, this condition is automatically satisfied if \(h(X)\) in Step 5 satisfies \(\gcd(h,X^{q+1}-1)=1\). In fact, \(\gcd(L_k,X^{(q+1)/d}-\varepsilon^k)=1\) for all \(0\le k<d\) if and only if \(\gcd(h,X^{q+1}-1)=1\).