# Finding compositional inverses of permutations from the AGW criterion

Tailin Niu, Kangquan Li, Longjiang Qu and Qiang Wang Tailin Niu, Kangquan Li
and Longjiang Qu are with the College of Liberal Arts and Sciences, National
University of Defense Technology, Changsha, 410073, China. Longjiang Qu is
also with the State Key Laboratory of Cryptology, Beijing, 100878, China.
Qiang Wang is with School of Mathematics and Statistics, Carleton University,
1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada. The research of
Longjiang Qu is partially supported by the National Key Research and
Development Program of China under 2017YFB0802000, the Nature Science
Foundation of China (NSFC) under Grant 61722213, 11771451, 62032009, and the
Open Foundation of State Key Laboratory of Cryptology. The research of Qiang
Wang is partially supported by NSERC of Canada. E-mail: Tailin Niu:
<EMAIL_ADDRESS>Kangquan Li<EMAIL_ADDRESS>Longjiang Qu:
<EMAIL_ADDRESS>Qiang Wang<EMAIL_ADDRESS>
###### Abstract

Permutation polynomials and their compositional inverses have wide
applications in cryptography, coding theory, and combinatorial designs.
Motivated by several previous results on finding compositional inverses of
permutation polynomials of different forms, we propose a general method for
finding these inverses of permutation polynomials constructed by the AGW
criterion. As a result, we have reduced the problem of finding the
compositional inverse of such a permutation polynomial over a finite field to
that of finding the inverse of a bijection over a smaller set. We demonstrate
our method by interpreting several recent known results, as well as by
providing new explicit results on more classes of permutation polynomials in
different types. In addition, we give new criteria for these permutation
polynomials being involutions. Explicit constructions are also provided for
all involutory criteria.

###### Index Terms:

Finite Fields, Permutation Polynomials, AGW Criterion, Compositional Inverses,
Involutions

##  1 Introduction

Let $q$ be a prime power and ${\mathbb{F}}_{q}$ be the finite field with $q$
elements. We call a polynomial $f(x)\in{\mathbb{F}}_{q}[x]$ a permutation
polynomial (PP for short) when the evaluation map $f:a\mapsto f(a)$ is a
bijection. The unique polynomial $f^{-1}(x)$ over ${\mathbb{F}}_{q}$ such that
$f\circ f^{-1}=f^{-1}\circ f=I$ is called the compositional inverse of $f(x)$,
where $I$ denotes the identity map. Furthermore, if a PP $f$ satisfies $f\circ
f=I$, then $f$ is called an involution. Throughout this paper, for the
multiplicative inverse function $f(x)=x^{-1}$, we always define $f(0)=0$.
Because PPs play important roles in finite field theory and they have broad
applications in coding theory, combinatorial designs, and cryptography [1, 2,
3, 4, 5, 6, 7, 8, 9, 10, 11], the construction of PPs over finite fields has
attracted a lot of attention. For recent surveys on constructing PPs, we
invite the interested readers to consult [12], [13, Section 5], [14] and [15,
Section 5]. Explicitly determining the compositional inverse of a PP is useful
because both a PP and its inverse are required in many applications. For
example, during the decryption process in a cryptographic algorithm with SPN
structure, the compositional inverse of the S-box plays an essential role.
Moreover, explicitly determining the compositional inverse will advance the
further research of involutions, which are particularly useful (as part of a
block cipher) in devices with limited resources [16, 17]. For recent research
of involutions and permutations with small cycles, we refer the readers to
[16, 17, 18, 19, 20].

In general, it is difficult to obtain the explicit compositional inverse of a
random PP, except for several well known classes of PPs such as linear
polynomial, monomials [21, 22], and Dickson polynomials [23, 24]. In recent
years, compositional inverses of several classes of PPs of special forms have
been obtained in explicit or implicit forms; see [25, 26, 27, 28, 29, 30, 23,
31, 17, 32, 33, 34, 35] for more details. A short survey on this topic can be
found in [32]. In 2011, Akbary et al. proposed a useful method called the AGW
criterion for constructing PPs [36]. For the sake of convenience, when a PP is
constructed using the AGW criterion or it can be interpreted by the AGW
criterion, we call it an AGW-PP. Many classes of AGW-PPs have been constructed
up to today and they can be divided into three types: multiplicative type [37,
38, 39, 40, 41, 42, 43], additive type [44, 36, 45, 46] and hybrid type [36,
47, 48, 49]. Despite of recent progress on finding compositional inverses of
several classes of AGW-PPs, e.g. [25, 29, 23, 18], there are many other
classes of AGW-PPs whose compositional inverses are still unknown. This
motivates us to explore a general method to find compositional inverses of
these AGW-PPs.

Inspired by the recent work in [30, 25, 29, 23, 18], we propose a general
framework to solve the compositional inverse of an arbitrary AGW-PP, say $f$
on a finite set $A$. It is well known that there are two surjective mappings
$\lambda,\bar{\lambda}$ from $A$ to finite sets $S$ and $\bar{S}$,
respectively, and a bijection $g$ from $S$ to $\bar{S}$ satisfying
$\overline{\lambda}\circ f=g\circ\lambda$ (i.e., Fig. 1 is commutative).

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{\lambda}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{\lambda}}$$\textstyle{S\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{\overline{S}}$
Figure 1: the AGW criterion

In order to find the inverse of the given AGW-PP $f$, we can construct two
other mappings $\eta,\overline{\eta}$ such that $\overline{\phi}\circ
f=\psi\circ\phi$, where $\phi=(\lambda,\eta)$ and
$\overline{\phi}=(\overline{\lambda},\overline{\eta})$ are bijections from $A$
to two other sets $\phi(A)$ and $\overline{\phi}(A)$ respectively (see Fig.
2). Namely, we have the following commutative diagram and then the
compositional inverse of $f$ is expressed by
$f^{-1}=\phi^{-1}\circ\psi^{-1}\circ\overline{\phi}$.

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{\phi=(\lambda,\eta)}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{\phi}=(\overline{\lambda},\overline{\eta})}$$\textstyle{\phi(A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi=(g,\tau)}$$\textstyle{\overline{\phi}(A)}$
Figure 2: a framework to obtain the inverse

Generally speaking, there are three types of AGW-PPs (multiplicative,
additive, and hybrid) which are classified based on the properties of
$\lambda$ and $\overline{\lambda}$. The classes studied by Li et al. [23]
belong to the multiplicative case, while the classes studied by Wu [30, 25]
and Tuxanidy et al. [29, 34] belong to the additive case. Our general
framework interprets all these recent results and provides a recipe to find
compositional inverses of many other classes of AGW-PPs. The key point of our
approach is to design “suitable” mappings $\eta$ and $\bar{\eta}$ such that
both $\phi=(\lambda,\eta)$ and $\bar{\phi}=(\bar{\lambda},\bar{\eta})$ are
bijections, and $\tau$ can be computed easily. Moreover, compositional
inverses of $\phi$ and $\psi=(g,\tau)$ can be efficiently computed. To
demonstrate our approach, we propose several new explicit choices of $\eta$
and $\bar{\eta}$ and use them to find the compositional inverses of four
classes of AGW-PPs in different types. As a consequence, we have reduced the
problem of finding compositional inverse of a permutation polynomial over a
finite field to that of finding the inverse of a bijection over a smaller set
(see for example, Theorems 3.2, Theorem 4.2, Theorem 5.2, Theorem 5.7.)

The rest of this paper is organized as follows. In Section 2, we present this
unified method to find compositional inverses of any AGW-PP and recall some
known results of computing compositional inverses under our framework. As
applications, we explicitly solve the compositional inverses of another four
classes of AGW-PPs. These results, as well as the characterization of
involutions, are divided into multiplicative, additive and hybrid cases, which
are presented in Sections 3, 4 and 5 respectively.

##  2 The unified method

In this section, we present our unified approach to finding the compositional
inverses of AGW-PPs. First of all, we recall the following AGW criterion.

######  Lemma 2.1.

([36, Lemma 1.2], the AGW Criterion) Let $A,S$, and $\overline{S}$ be finite
sets with $\\#S=\\#\overline{S}$, and let $f:A\to A,$ $g:S\to\overline{S}$,
$\lambda:A\to S$ and $\overline{\lambda}:A\to\overline{S}$ be maps such that
$\bar{\lambda}\circ f=g\circ\lambda$. If both $\lambda$ and $\bar{\lambda}$
are surjective, then the following statements are equivalent:

  1. (1)

$f$ is a bijection and

  2. (2)

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

The AGW criterion can be illustrated in the commutative diagram of Fig. 1.
This criterion is very useful to explain many earlier constructions and to
construct new classes of PPs. The key of AGW criterion lies in transforming
the problem of constructing permutations $f$ of a finite set $A$ into finding
a bijections $g$ from $S$ to $\bar{S}$, whose cardinalities are both smaller
than the size of $A$. Since $\lambda$ and $\overline{\lambda}$ both are
surjective (normally they are not bijective because we prefer the sizes of $S$
and $\bar{S}$ are smaller), one can not simply obtain the compositional
inverse of $f$ using only mappings $\lambda$, $\overline{\lambda}$ and $g$.

When $A=\mathbb{F}_{q^{n}}$ and $\lambda=\bar{\lambda}$ are additive, Tuxanidy
and Wang [29], [34] converted the problem of computing the inverse of a PP
over ${\mathbb{F}}_{q}$ into that of computing two inverses of two other
bijections over two subspaces (one of them is
$\lambda\left(\mathbb{F}_{q^{n}}\right)$) respectively. A key ingredient is to
decompose $\mathbb{F}_{q^{n}}$ into two subspaces. This generalized a result
of Wu et al. [25] who focused on the case that $\lambda$ is the trace
function. When $A={\mathbb{F}}_{q}$ and $\lambda=\bar{\lambda}$ are monomials,
Li et al. [23] provided a multiplicative analogue of [29, 34, 25]. The main
idea of Li et al. relies on transforming the problem of computing the
compositional inverses of permutation polynomials of the form $x^{r}h(x^{s})$
over ${\mathbb{F}}_{q}$ into computing the compositional inverses of two
restricted permutation mappings, where one of them is a monomial over
$\mathbb{F}_{q}$ and the other is the polynomial $x^{r}h(x)^{s}$ over a
particular subgroup of $\mathbb{F}_{q}$ with order $(q-1)/s$. A key ingredient
is a bijection from ${\mathbb{F}}_{q}$ to another set
$F_{q,s}=\\{(x^{q-s},x^{s}):x\in{\mathbb{F}}_{q}\\}$ whose inverse can be
easily computed. A variant of this result can be found in Niu et al. [18].

We note that the similar idea works for an arbitrary AGW-PP $f$. Namely, we
can find the compositional inverse of an arbitrary AGW-PP $f$ over a set $A$
by constructing two other mappings, i.e., $\eta$ and $\overline{\eta}$ such
that

  1. (1)

$\phi=(\lambda,\eta),\overline{\phi}=(\overline{\lambda},\overline{\eta})$
become bijective from $A$ to some subsets of $A\times A$ as shown by Fig. 2.

  2. (2)

Fig. 2 is a commutative diagram, i.e., $\overline{\phi}\circ f=\psi\circ\phi$.

Then, it is clear that the compositional inverse of $f$ can be expressed as
$f^{-1}=\phi^{-1}\circ\psi^{-1}\circ\overline{\phi}$. Here we do not need to
decompose the finite field into subspaces, as previously done for the additive
case, neither we have restrictions on special types of AGW-PPs. Instead, we
emphasize that it is crucial to find simple mappings $\eta$ and
$\overline{\eta}$ so that the compositional inverse of $\phi=(\lambda,\eta)$
and the compositional inverse of $\psi=(g,\tau)$ can be computed easily.

To summarize the above discussion, we have the following theorem.

######  Theorem 2.2.

Let $A$ be a finite set, $f:A\to A$, and let $\phi=(\lambda,\eta)$ and
$\overline{\phi}=(\overline{\lambda},\overline{\eta})$ be two bijective
mappings from $A$ to some subsets of $A\times A$, and denote by ${\phi}^{-1}$,
${\bar{\phi}}^{-1}$ their compositional inverses respectively. Let
$\psi=(g,\tau):\phi(A)\to\overline{\phi}(A)$ be a mapping such that
$\bar{\phi}\circ f=\psi\circ\phi$. Then $f$ is bijective if and only if $\psi$
is bijective. Furthermore, if $\psi$ is bijective and its compositional
inverse is denoted by $\psi^{-1}$, then

$f^{-1}={\phi}^{-1}\circ\psi^{-1}\circ{\bar{\phi}}$

is the compositional inverse of $f$ on $A$.

We remark that the above theorem can be viewed as a special version of the AGW
criterion, where the mappings $\lambda$ and $\bar{\lambda}$ are both
bijections and the cardinalities of $S$ and $\bar{S}$ are both equal to that
of $A$. However, earlier constructions of AGW-PPs focused on bijections over
smaller sets. This result can be viewed as a new application of the AGW
criterion in computing compositional inverses.

In fact, our method provides a possibility to solve the compositional inverses
of all AGW-PPs and the process can be summarized as follows:

  1. (1)

Design $\eta$ and $\overline{\eta}$ such that $\phi=(\lambda,\eta)$ and
$\overline{\phi}=(\overline{\lambda},\overline{\eta})$ are both bijective, and
compute the compositional inverse $\phi^{-1}$ of $\phi.$

  2. (2)

Compute the unique expression of $\psi$ such that
$\psi\circ\phi=\overline{\phi}\circ f$.

  3. (3)

Compute the compositional inverses $\psi^{-1}$ of $\psi$.

  4. (4)

Obtain the compositional inverse $f^{-1}$ of $f$ by Theorem 2.2, i.e.,
$f^{-1}={\phi}^{-1}\circ\psi^{-1}\circ{\bar{\phi}}$.

In the following, we demonstrate the explicit choices of
$\phi,\bar{\phi},\psi$ in several known results using Theorem 2.2. In order to
improve readability, we have adapted all the notations of these results in
terms of Lemma 2.1 and Theorem 2.2.

######  Example 2.3.

[23, Theorem 2.3] We take

  1. (1)

$A={\mathbb{F}}_{q}$;

  2. (2)

$f(x)=x^{r}h\left(x^{s}\right)$ permutes ${\mathbb{F}}_{q}$, where
$s\mid(q-1),\gcd(r,q-1)=1$ and $h(0)\neq 0$;

  3. (3)

$\phi(x)=\overline{\phi}(x)=\left(x^{q-s},x^{s}\right)$;

  4. (4)

$\phi(A)=\overline{\phi}(A)$;

  5. (5)

$\psi(y,z)=\left(y^{r}h(z)^{q-s},z^{r}h(z)^{s}\right)$; and

  6. (6)

Let $l(x)$ be the compositional inverse of $g(x)=x^{r}h(x)^{s}$ over
$\mu_{\frac{q-1}{s}}=\left\\{x\in{{\mathbb{F}}}_{q}^{*}:x^{\frac{q-1}{s}}=1\right\\}$
and $r^{\prime}$ be an integer which satisfies $rr^{\prime}\equiv
1\pmod{q-1}$.

Then it follows from Theorem 2.2 that

$f^{-1}(x)=\left(\alpha(x)h(l(\beta(x)))^{s-1}\right)^{r^{{}^{\prime}}}l(\beta(x))$

is the compositional inverse of $f(x)$, where $\alpha(x)=x^{q-s}$ and
$\beta(x)=x^{s}$.

######  Example 2.4.

[18, Theorem 3.7] Assume that

  1. (1)

$A={\mathbb{F}}_{q^{m}}$;

  2. (2)

$f(x)=g\left(x^{q^{i}}-x+\delta\right)+cx\in{\mathbb{F}}_{q^{m}}[x]$ permutes
${\mathbb{F}}_{q^{m}}$, where $q$ is a prime power, $m,i$ be positive integers
with $1\leq i\leq m-1$, $c\in{\mathbb{F}}_{q^{\gcd(i,m)}}^{*}$ and
$g(x)\in{\mathbb{F}}_{q^{m}}[x]$. Then
$h(x)=g(x)^{q^{i}}-g(x)+cx+(1-c)\delta\in{\mathbb{F}}_{q^{m}}[x]$ permutes
${\mathbb{F}}_{q^{m}}$ (see [44, Proposition 3]), where
$\delta\in{\mathbb{F}}_{q^{m}}$.

  3. (3)

$\phi(x)=\overline{\phi}(x)=\left(-x^{q^{i}},x^{q^{i}}-x+\delta\right)$;

  4. (4)

$\phi(A)=\overline{\phi}(A)$;

  5. (5)

$\psi(y,z)=\left(c^{q^{i}}y-g(z)^{q^{i}},h(z)\right)$; and

  6. (6)

Assume $H(x)$ is the compositional inverse of $h(x)$.

Then it follows from Theorem 2.2 that, for any
$\delta\in{\mathbb{F}}_{q^{m}}$, the compositional inverse of $f(x)$ is

$f^{-1}(x)=c^{-1}x^{q^{i}}-c^{-1}g\left(H(x^{q^{i}}-x+\delta)\right)^{q^{i}}-H(x^{q^{i}}-x+\delta)+\delta.$

######  Example 2.5.

[29, Theorem 1.2] Let

  1. (1)

$A={\mathbb{F}}_{q^{n}}$;

  2. (2)

$f(x)=h(\psi_{0}(x))\varphi_{0}(x)+g_{0}(\psi_{0}(x))$ permute
${\mathbb{F}}_{q^{n}}$, where
${\varphi_{0}},\psi_{0}\in{\mathbb{F}}_{q^{n}}[x]$ are additive polynomials,
$q$-polynomial $\overline{\psi_{0}}$ satisfies
$\varphi_{0}\circ\psi_{0}=\overline{\psi_{0}}\circ\varphi_{0}$ and
$\left|\psi_{0}\left({{\mathbb{F}}_{q^{n}}}\right)\right|=\left|\overline{\psi_{0}}\left({{\mathbb{F}}_{q^{n}}}\right)\right|$,
and polynomial $h\in{\mathbb{F}}_{q^{n}}[x]$ such that
$h\left(\psi_{0}\left(\mathbb{F}_{q^{n}}\right)\right)\subseteq\mathbb{F}_{q}\backslash\\{0\\}$;

  3. (3)

$\phi(x)=\phi_{\psi_{0}}\left(x\right)=\left(\psi_{0}(x),x-\psi_{0}(x)\right)$,
$\overline{\phi}=\phi_{\overline{\psi_{0}}}\left(x\right)=\left(\overline{\psi_{0}}(x),x-\overline{\psi_{0}}(x)\right)$
in [29, Lemma 2.10];

  4. (4)

$\phi(A)=\phi_{\psi_{0}}\left(\mathbb{F}_{q^{n}}\right),\overline{\phi}(A)=\phi_{\overline{\psi_{0}}}\left(\mathbb{F}_{q^{n}}\right)$;

  5. (5)

$\psi(y,z)=\left(h(y)\varphi_{0}(y)+\overline{\psi_{0}}(g_{0}(y)),h(y)\varphi_{0}(z)+g_{0}(y)-\overline{\psi_{0}}(g_{0}(y))\right)$;
and

  6. (6)

Assume that $\left|S_{\psi_{0}}\right|=\left|S_{\overline{\psi_{0}}}\right|$
and $\ker(\varphi_{0})\cap\psi_{0}\left(S_{\psi_{0}}\right)=\\{0\\}$. Then
$\varphi_{0}$ induces a bijection from $S_{\overline{\psi_{0}}}$ to
$S_{\overline{\psi_{0}}}$. Let $\overline{f}^{-1}$ and
$\left.\varphi_{0}^{-1}\right|_{S_{\overline{\psi_{0}}}}\in{\mathbb{F}}_{q^{n}}[x]$
induce the inverses of
$\left.\overline{f}\right|_{\psi_{0}\left(\mathbb{F}_{q^{n}}\right)}(x)=h(x)\varphi_{0}(x)+\overline{\psi_{0}}(g_{0}(x))$
and $\varphi_{0}|_{S_{\psi_{0}}}$ respectively,

Then it follows from Theorem 2.2 that the compositional inverse of $f(x)$ is
given by

$f^{-1}(x)=\overline{f}^{-1}(\overline{\psi_{0}}(x))+\left.\varphi_{0}^{-1}\right|_{S_{\overline{\psi_{0}}}}\left(\frac{x-\overline{\psi_{0}}(x)-g_{0}\left(\overline{f}^{-1}(\overline{\psi_{0}}(x))\right)+\overline{\psi_{0}}\left(g_{0}\left(\overline{f}^{-1}(\overline{\psi_{0}}(x))\right)\right)}{h\left(\overline{f}^{-1}(\overline{\psi_{0}}(x))\right)}\right).$

######  Example 2.6.

[25, Theorem 2.3] Let

  1. (1)

$A={\mathbb{F}}_{q^{n}}$, where $q$ is even and $n$ is odd;

  2. (2)

$f(x)=x(L({\rm Tr}_{q^{n}/q}(x))+a{\rm Tr}_{q^{n}/q}(x)+ax)$ permute
${\mathbb{F}}_{q^{n}}$, where $xL(x)$ is a bilinear PP over ${\mathbb{F}}_{q}$
for a linearized polynomial $L(x)\in{\mathbb{F}}_{q}[x]$,
$a\in{\mathbb{F}}_{q}^{*}$, and the trace function from ${\mathbb{F}}_{q^{n}}$
to ${\mathbb{F}}_{q}$ is denoted by ${\rm
Tr}_{q^{n}/q}(\cdot):x\to\sum_{i=0}^{n-1}x^{q^{i}}$;

  3. (3)

$\phi(x)=\overline{\phi}(x)=\left({\rm Tr}_{q^{n}/q}(x),x+{\rm
Tr}_{q^{n}/q}(x)\right)$;

  4. (4)

$\phi(A)=\overline{\phi}(A)={\mathbb{F}}_{q}\oplus{\ker({\rm Tr}_{q^{n}/q})}$;

  5. (5)

$\psi(y,z)=\left(yL(y),az^{2}+(L(y)+ay)z\right)$; and

  6. (6)

Let $q=2^{m}$ for a positive integer $m$. Assume the compositional inverse of
$xL(x)$ is $g_{0}(x)\in{\mathbb{F}}_{q}[x]$.

Then it follows from Theorem 2.2 that the compositional inverse of $f(x)$ is

$f^{-1}(x)=a^{2^{m-1}-1}x^{2^{nm-1}}+\left(g_{0}({\rm
Tr}_{q^{n}/q}(x))+a^{2^{m-1}-1}\sum_{k=1}^{\frac{n-1}{2}}x^{2^{(2k-1)m-1}}\right)$
${\times}\left(\frac{{\rm Tr}_{q^{n}/q}(x)}{g_{0}({\rm
Tr}_{q^{n}/q}(x))}+ag_{0}({\rm Tr}_{q^{n}/q}(x))\right)^{q-1}$
$+\sum_{j=0}^{m-2}a^{2^{j}-1}\left(\frac{{\rm Tr}_{q^{n}/q}(x)}{g_{0}({\rm
Tr}_{q^{n}/q}(x))}+ag_{0}({\rm
Tr}_{q^{n}/q}(x))\right)^{2^{m}-2^{j+1}}\left(\sum_{k=0}^{\frac{n-1}{2}}x^{q^{2k}}\right)^{2^{j}}.$

As illustrated above, the key step of this approach is to design suitable
mappings $\phi=(\lambda,\eta)$,
$\bar{\phi}=(\overline{\lambda},\overline{\eta})$ satisfying the required
properties. In the following we provide two new results which generalize the
choices of $\eta$ and $\overline{\eta}$ in Examples 2.3-2.5.

######  Corollary 2.7.

Let $A$ be a finite set and $f$, $g$, $\lambda,\overline{\lambda}$ be mappings
satisfying the assumption of Lemma 2.1 (e.g., satisfy the commutative diagram
in Fig. 1). We assume
$\eta(x)=P(x)-\lambda(x),\overline{\eta}(x)=P(x)-\overline{\lambda}(x)$, and
$\tau$ are mappings such that $\bar{\eta}\circ f=\tau\circ\eta$, where $P(x)$
permutes $A$. Then both $\phi=(\lambda,\eta)$ and
$\overline{\phi}=(\overline{\lambda},\overline{\eta})$ are bijective mappings
from $A$ to some subsets of $A\times A$ and ${\phi}^{-1}(y,z)=P^{-1}(y+z)$,
${\bar{\phi}}^{-1}(\alpha,\beta)=P^{-1}(\alpha+\beta)$ are their compositional
inverses respectively. Moreover, $f$ is bijective if and only if
$\psi=(g,\tau)$ is bijective. Furthermore, if both $g$, $\psi$ are bijective
and their compositional inverses are denoted by $g^{-1}(\alpha)$ and
$\psi^{-1}(\alpha,\beta)=\left(g^{-1}(\alpha),M(\alpha,\beta)\right)$
respectively, where $M(\alpha,\beta):{\rm Im}(\overline{\phi})\to{\rm
Im}(\eta)$, then

$f^{-1}(x)=P^{-1}\left(g^{-1}(\overline{\lambda}(x))+M(\overline{\lambda}(x),P(x)-\overline{\lambda}(x))\right)$

is the compositional inverse of $f$ on $A$.

###### Proof.

Assume $\phi(x)=\phi(x^{\prime})$. Then $\lambda(x)=\lambda(x^{\prime})$ and
$P(x)-\lambda(x)=\eta(x)=\eta(x^{\prime})=P(x^{\prime})-\lambda(x^{\prime})$.
Hence $P(x)=P(x^{\prime})$. Because $P(x)$ permutes $A$, we must have
$x=x^{\prime}$ and thus $\phi$ is a bijection. Plug
$y=\lambda(x),z=P(x)-\lambda(x)$ into $P^{-1}(y+z)$, one can obtain
$P^{-1}(\lambda(x)+P(x)-\lambda(x))=x$. Thus ${\phi}^{-1}(y,z)=P^{-1}(y+z)$.
Similarly, $\bar{\phi}$ is bijective and
${\bar{\phi}}^{-1}(\alpha,\beta)=P^{-1}(\alpha+\beta)$. The rest of proof
follows from Theorem 2.2. ∎

######  Corollary 2.8.

Let $A$ be a finite set and $f$, $g$, $\lambda,\overline{\lambda}$ be mappings
satisfying the assumption of Lemma 2.1 (e.g., satisfy the commutative diagram
in Fig. 1). Let $\lambda(x),\bar{\lambda}(x)\neq 0$ for any $x\in A$. We
assume $\eta(x)=P\left(\frac{x}{\lambda(x)}\right)$,
$\overline{\eta}(x)=P\left(\frac{x}{\overline{\lambda}(x)}\right)$, and $\tau$
are mappings such that $\bar{\eta}\circ f=\tau\circ\eta$, where $P(x)$
permutes $A$. Then both $\phi=(\lambda,\eta)$ and
$\overline{\phi}=(\overline{\lambda},\overline{\eta})$ are bijective mappings
from $A$ to some subsets of $A\times A$ and ${\phi}^{-1}(y,z)=yP^{-1}(z)$,
${\bar{\phi}}^{-1}(\alpha,\beta)=\alpha P^{-1}(\beta)$ are their compositional
inverses respectively. Moreover, $f$ is bijective if and only if
$\psi=(g,\tau)$ is bijective. Furthermore, if both $g$, $\psi$ are bijective
and their compositional inverses are respectively denoted by $g^{-1}(\alpha)$,
$\psi^{-1}(\alpha,\beta)=\left(g^{-1}(\alpha),M(\alpha,\beta)\right)$, where
$M(\alpha,\beta):{\rm Im}(\overline{\phi})\to{\rm Im}(\eta)$, then

$f^{-1}(x)=g^{-1}\left(\overline{\lambda}(x)\right)P^{-1}\left(M\left(\overline{\lambda}(x),P\left(\frac{x}{\overline{\lambda}(x)}\right)\right)\right)$

is the compositional inverse of $f$ on $A$.

###### Proof.

Assume $\phi(x)=\phi(x^{\prime})$. Then $\lambda(x)=\lambda(x^{\prime})$ and
$P(\frac{x}{\lambda(x)})=\eta(x)=\eta(x^{\prime})=P(\frac{x^{\prime}}{\lambda(x^{\prime})})$.
Because $P(x)$ permutes $A$, the latter implies that
$\frac{x}{\lambda(x)}=\frac{x^{\prime}}{\lambda(x^{\prime})}$. Since
$\lambda(x)=\lambda(x^{\prime})$, we must have $x=x^{\prime}$ and thus $\phi$
is a bijection. Plug $y=\lambda(x),z=P\left(\frac{x}{\lambda(x)}\right)$ into
$yP^{-1}(z)$, one can obtain
$\lambda(x)P^{-1}(P\left(\frac{x}{\lambda(x)}\right))=x$. Thus
${\phi}^{-1}(y,z)=yP^{-1}(z)$. Similarly, $\bar{\phi}$ is bijective and
${\bar{\phi}}^{-1}(\alpha,\beta)=\alpha P^{-1}(\beta)$. The rest of proof
follows from Theorem 2.2. ∎

We demonstrate more specific choices of $\eta$ and $\overline{\eta}$ in the
next few sections and explicitly compute the compositional invereses of four
more classes of AGW-PPs. In addition, we analyze the results of compositional
inverses to obtain conditions for being involutions. Furthermore, we provide
at least one explicit involutory construction for each involutory criterion
for the purpose of demonstration, although we believe that it may be not hard
to find more general involutory constructions. In the sequel, we need the
following lemma on involutions over finite sets.

######  Lemma 2.9.

Let $A$ and $S$ be finite sets, and let $f:A\to A$, $g:S\to S$, $\lambda:A\to
S$ be maps such that $\lambda$ is surjective and $\lambda\circ
f=g\circ\lambda$. Assume $f$ is an involution on $A$. Then $g$ is an
involution on $S$.

###### Proof.

We obtain $\lambda=\lambda\circ f\circ f=g\circ\lambda\circ f=g\circ
g\circ\lambda$. Since $\lambda$ is surjective, $g$ is an involution on $S$
according to $\lambda=g\circ g\circ\lambda$. ∎

This is a direct consequence of [18, Proposition 2.2]. From now on, we always
assume $g$ is an involution whenever we consider the involution $f$.

##  3 Compositional inverses of AGW-PPs in the multiplicative case

In order to state our results we need the following terminology in [50]. For
any nonconstant monic polynomial $f(x)\in\mathbb{F}_{q}[x]$ of degree
$\leqslant q-1$ with $f(0)=0,$ let $r$ be the vanishing order of $f(x)$ at
zero and let $f_{1}(x):=f(x)/x^{r}$. Let $\ell$ be the least divisor of $q-1$
with the property that there exists a polynomial $h(x)$ such that
$f_{1}(x)=h\left(x^{(q-1)/\ell}\right).$ So $f(x)$ can be written uniquely as
$x^{r}h\left(x^{(q-1)/\ell}\right)$. The integer $\ell$ is called the index of
$f$. The AGW criterion is very useful to study PPs of the form
$x^{r}h(x^{(q-1)/\ell})$ such that $\ell<q-1$. More details can be found in
[50, 51].

The following result was discovered independently by several authors, and we
want to point it out that it is actually the multiplicative case of the AGW
criterion.

######  Lemma 3.1.

[52, Theorem 2.3] [53, Theorem 1] [54, Lemma 2.1] Let $q$ be a prime power and
$f(x)=x^{r}h\left(x^{s}\right)\in{\mathbb{F}}_{q}[x]$, where
$s=\frac{q-1}{\ell}$ and $\ell$ is an integer. Then $f(x)$ permutes
${\mathbb{F}}_{q}$ if and only if

  1. (1)

$\gcd\left(r,s\right)=1$ and

  2. (2)

$g(x)=x^{r}h(x)^{s}$ permutes $\mu_{\ell},$ where
$\mu_{\ell}=\left\\{x\in{{\mathbb{F}}}_{q}^{*}:~{}~{}x^{\ell}=1\right\\}$.

For any $s\mid{(q-1)}$, by Lemma 3.1, the key point to determine the
permutation property of $f(x)=x^{r}h\left(x^{s}\right)$ over
${\mathbb{F}}_{q}$ is to consider whether $g(x)=x^{r}h(x)^{s}$ permutes
$\mu_{\ell}$ or not. It should be noted that $g(x)$ is always restricted over
$\mu_{\ell}$. Also we always assume that $h(x)\neq 0$ for any
$x\in\mu_{\ell}$. Otherwise, it is easy to see that $f(x)=x^{r}h(x^{s})$ can
not permute ${\mathbb{F}}_{q}$.

Using our method introduced in Section 2, we can explicitly give the
compositional inverse of a PP $f(x)=x^{r}h(x^{s})$ in terms of the
compositional inverse of $g(x)=x^{r}h(x)^{s}$. This extends an earlier result
by Li et al. in [23], who transformed the problem of computing the
compositional inverse of $x^{r}h\left(x^{s}\right)$ into computing the
compositional inverses of two restricted permutation mappings, where one of
them is $g(x)=x^{r}h(x)^{s}$, and the other is $x^{q-s}$.  In terms of the
language described in Theorem 2.2, Li et al. used
$\eta=\overline{\eta}=x^{q-s}$ in order to assure that
$\phi=\overline{\phi}=\left(x^{s},x^{q-s}\right)$ is a bijection. However,
their result only works when $\gcd\left(r,q-1\right)=1$. In fact, from Lemma
3.1, the permutation property of $f$ only requires that $g$ is bijective and
$\gcd(r,s)=1$. Therefore we deal with this most general case and fill up the
gap.

######  Theorem 3.2.

Let $f(x)=x^{r}h\left(x^{s}\right)$ defined as in Lemma 3.1 be a permutation
over ${\mathbb{F}}_{q}$ and $g^{-1}(x)$ be the compositional inverse of
$g(x)=x^{r}h(x)^{s}$ over $\mu_{\frac{q-1}{s}}$. Suppose $a$ and $b$ are two
integers satisfying $as+br=1$. Then the compositional inverse of $f(x)$ in
${\mathbb{F}}_{q}[x]$ is given by

$f^{-1}(x)=g^{-1}(x^{s})^{a}x^{b}h\left(g^{-1}(x^{s})\right)^{-b}.$

###### Proof.

Let $\phi$ be a map defined by

$\phi:{\mathbb{F}}_{q}\to\phi({\mathbb{F}}_{q}),$
$x\mapsto\left(\lambda(x),\eta(x)\right)=\left(x^{s},x^{r}\right),$

where
$\phi({\mathbb{F}}_{q})=\left\\{\left(x^{s},x^{r}\right):~{}~{}x\in{\mathbb{F}}_{q}\right\\}.$
Given one element $\left(y,z\right)\in\phi({\mathbb{F}}_{q})$, there exists
$x_{0}\in{\mathbb{F}}_{q}$ such that $y=x_{0}^{s}$ and $z=x_{0}^{r}$.
Furthermore, it is clear that $y^{a}z^{b}=x_{0}^{as+br}=x_{0}$. Thus $\phi$ is
a bijection and $\phi^{-1}(y,z)=y^{a}z^{b}$.

Next, we compute the expression of $\psi$ from the relation
$\psi\circ\phi(x)=\phi\circ f(x)$. From a simple computation, we get

$\phi\circ f(x)=\left(x^{sr}h(x^{s})^{s},x^{r^{2}}h(x^{s})^{r}\right).$ (1)

Substituting $x^{s}$ and $x^{r}$ in Eq. (1) with $y$ and $z$ respectively, we
obtain

$\psi(y,z):\phi({\mathbb{F}}_{q})\to\phi({\mathbb{F}}_{q}),$
$(y,z)\mapsto\left(y^{r}h(y)^{s},z^{r}h(y)^{r}\right).$

Now we compute the compositional inverse of $\psi$. For
$(y,z),(\alpha,\beta)\in\phi({\mathbb{F}}_{q})$ with
$\psi(y,z)=(\alpha,\beta)$, we have

$\left\\{\begin{aligned} y^{r}h(y)^{s}&=&\alpha,\\\ z^{r}h(y)^{r}&=&\beta.\\\
\end{aligned}\right.$

Then we get

$y=g^{-1}(\alpha).$

Moreover,

$z^{r}=\beta h(y)^{-r}=\beta h\left(g^{-1}(\alpha)\right)^{-r}.$ (2)

Clearly, for any given $(\alpha,\beta)\in\phi({\mathbb{F}}_{q})$, there exists
a unique element denoted by ${x_{(\alpha,\beta)}}\in{\mathbb{F}}_{q}$ such
that $\alpha={x_{(\alpha,\beta)}}^{s}$ and $\beta={x_{(\alpha,\beta)}}^{r}$.
Therefore, $z^{r}=\beta
h\left(g^{-1}(\alpha)\right)^{-r}={x_{(\alpha,\beta)}}^{r}h\left(g^{-1}({x_{(\alpha,\beta)}}^{s})\right)^{-r}$.
To show that
$z=x_{(\alpha,\beta)}h\left(g^{-1}({x_{(\alpha,\beta)}}^{s})\right)^{-1}$ is
the unique solution to Eq. (2), it suffices to prove that
$x_{(\alpha,\beta)}h\left(g^{-1}({x_{(\alpha,\beta)}}^{s})\right)^{-1}\in\\{x^{r}:~{}~{}x\in{\mathbb{F}}_{q}\\}$.
Since $f$ is a PP, there exists a unique $x_{0}\in{\mathbb{F}}_{q}$ such that
${x_{(\alpha,\beta)}}=f(x_{0})=x_{0}^{r}h\left(x_{0}^{s}\right)$. Furthermore,
we have

$g^{-1}(f(x_{0})^{s})=g^{-1}(x_{0}^{rs}h(x_{0}^{s})^{s})=g^{-1}(g(x_{0}^{s}))=x_{0}^{s}.$

Plugging ${x_{(\alpha,\beta)}}=x_{0}^{r}h\left(x_{0}^{s}\right)$ into
${x_{(\alpha,\beta)}}h\left(g^{-1}({x_{(\alpha,\beta)}}^{s})\right)^{-1}$, we
obtain

${x_{(\alpha,\beta)}}h\left(g^{-1}({x_{(\alpha,\beta)}}^{s})\right)^{-1}=x_{0}^{r}h\left(x_{0}^{s}\right)h(g^{-1}(f(x_{0})^{s}))^{-1}=x_{0}^{r}h\left(x_{0}^{s}\right)h\left(x_{0}^{s}\right)^{-1}=x_{0}^{r},$

which belongs to $\\{x^{r}:~{}~{}x\in{\mathbb{F}}_{q}\\}$. Thus
$z={x_{(\alpha,\beta)}}h\left(g^{-1}({x_{(\alpha,\beta)}}^{s})\right)^{-1}$
and then

$\psi^{-1}\left(\alpha,\beta\right)=\left(g^{-1}(\alpha),{x_{(\alpha,\beta)}}h\left(g^{-1}({x_{(\alpha,\beta)}}^{s})\right)^{-1}\right).$

According to Theorem 2.2, the compositional inverse of $f(x)$ is

$f^{-1}(x)={\phi}^{-1}\circ\psi^{-1}\circ{\phi}(x)=g^{-1}(\alpha)^{a}z^{b}=g^{-1}(x^{s})^{a}x^{b}h\left(g^{-1}(x^{s})\right)^{-b}.$

∎

Theorem 3.2 can be verified by $f^{-1}(f(x))=x$ for any
$x\in{\mathbb{F}}_{q}^{*}$. First, it is clear that
$g^{-1}(f(x)^{s})=g^{-1}(x^{rs}h(x^{s})^{s})=g^{-1}(g(x^{s}))=x^{s}$. Then we
have

$\displaystyle f^{-1}\left(f(x)\right)$
$\displaystyle=g^{-1}(f(x)^{s})^{a}(x^{r}h\left(x^{s}\right))^{b}h\left(g^{-1}(f(x)^{s})\right)^{-b}$
$\displaystyle=x^{as}x^{br}h(x^{s})^{b}h(x^{s})^{-b}$
$\displaystyle=x^{as+br}=x.$

Although this provides a shorter proof of Theorem 3.2, we preferred to give
the current proof so that we can demonstrate how to use our approach to find
the compositional inverse.

Theorem 3.2 provides the explicit compositional inverse of a PP of the form
$f(x)=x^{r}h(x^{s})$ on ${\mathbb{F}}_{q}$ by computing the compositional
inverse of $g(x)=x^{r}h(x)^{s}$ on $\mu_{\frac{q-1}{s}}$, extending the result
[23, Theorem 2.3] which needs an additional condition
$\gcd\left(r,q-1\right)=1$. In the following, we explain that Theorem 3.2 is
consistent with [23, Theorem 2.3] under the condition
$\gcd\left(r,q-1\right)=1$. In [23, Theorem 2.3], the authors obtained that
the compositional inverse of $f(x)=x^{r}h(x^{s})$ is

$f^{-1}(x)=\left(x^{q-s}h(g^{-1}(x^{s}))^{s-1}\right)^{r^{\prime}}g^{-1}(x^{s}),$
(3)

where $\gcd\left(r,q-1\right)=1$ and $r^{\prime}$ be an integer satisfying
$rr^{\prime}\equiv 1\pmod{q-1}$. Let $k$ be an integer satisfying
$r^{\prime}r+k(q-1)=1$. Since $\gcd\left(r,s\right)=1$, we assume
$k_{a}s+k_{b}r=1$. By letting $a=1+k(1-s)k_{a}(q-1)$ and
$b=(1-s)r^{\prime}+k(1-s)k_{b}(q-1)$, one can verify $as+br=1$ and thus derive
(3) using the expression of $f^{-1}(x)$ in Theorem 3.2. As consequences, many
explicit compositional inverses of PPs of the form $x^{r}h(x^{s})$ given in
[23] can be obtained without the assumption $\gcd\left(r,q-1\right)=1$.

We remark that an explicit expression of the compositional inverse of
$x^{r}h(x^{s})$ in terms of roots of unities was given in [55] and more
generally the inverses of cyclotomic mappings were provided in [31, Theorem 2]
and [56, Theorem 3.3]. In [31], a fast algorithm to generate cyclotomic PPs,
their inverses, and involutions was provided. In contrast, our method explores
the connections between the inverses of $f$ and $g$, sometimes, it can help us
to obtain simpler expression of the compositional inverse.

Next we demonstrate how to use Theorem 3.2 to obtain the compsitional inverses
of PPs in [57, Theorem 1.2] or [58, Theorem 4.1]. There are many concrete
examples satisfying conditions in Corollary 3.3, and one of them can be found
in Example 3.5.

######  Corollary 3.3.

Let $s\mid(q-1),h(x)\in\mathbb{F}_{q}[x]$ satisfies that
$h(\zeta)^{s}=\zeta^{n}$ for every $\zeta\in\mu_{(q-1)/s}$. Suppose
$\gcd(r+n,(q-1)/s)=1$ and $t,a,b$ be integers that satisfy $(r+n)t\equiv
1(\bmod(q-1)/s)$ and $ar+bs=1$. Then $f(x)=x^{r}h\left(x^{s}\right)$ permutes
$\mathbb{F}_{q}$, $g(\zeta)=\zeta^{r}h(\zeta)^{s}=\zeta^{r+n}$, and
$g^{-1}(\zeta)=\zeta^{t}$. Moreover, the compositional inverse of $f(x)$ in
$\mathbb{F}_{q}[x]$ is

$f^{-1}(x)=x^{ast+b}h\left(x^{st}\right)^{-b}.$

In addition, we give a criterion for PPs of the form $x^{r}h(x^{s})$ being
involutions.

######  Corollary 3.4.

The PP $f(x)=x^{r}h(x^{s})$ over ${\mathbb{F}}_{q}$ defined as in Lemma 3.1 is
an involution if and only if

  1. (1)

$g(x)=x^{r}h(x)^{s}$ is involutory on $\mu_{\frac{q-1}{s}}$ and

  2. (2)

$\varphi(x)=g(x^{s})^{a}x^{b-r}h\left(g(x^{s})\right)^{-b}h(x^{s})^{-1}=1$
holds for any $x\in{\mathbb{F}}_{q}^{*}$, where integers $a$ and $b$ satisfy
$as+br=1$.

###### Proof.

Since $g(x)$ being involutory is necessary for $f(x)$ being involutory by
Lemma 2.9, we have $g^{-1}(x)=g(x)$ on $\mu_{\frac{q-1}{s}}$. In this case, by
Theorem 3.2, $f^{-1}(x)=f(x)$ if and only if

$g(x^{s})^{a}x^{b-r}h\left(g(x^{s})\right)^{-b}h(x^{s})^{-1}=1.$

∎

Many explicit classes of involutions in [17, 18] can be constructed by
Corollary 3.4. We give the following example that has significantly simplified
the earlier proof.

######  Example 3.5.

[18, Corollary 2.17] Let $q$ be a power of $2$ and $k$ be a positive integer
such that $\gcd(k,q+1)=1$. Then for any $\gamma,\beta\in{\mathbb{F}}_{q}^{*}$
such that ${\rm Tr}_{q/2}(\beta)=0$, the polynomial
$f(x)=x^{q^{2}-2}h\left(x^{q-1}\right)$ is an involution on
${\mathbb{F}}_{q^{2}}$, where $h(x)=\gamma\left(x^{-1}+\beta x^{-k-1}+\beta
x^{k-1}\right)$.

###### Proof.

According to the proof of [18, Corollary 2.17], we obtain $h(x)\neq 0$ and
$g(x)=x^{-1}h(x)^{q-1}=x$, for any $x\in\mu_{q+1}$. Let $a=-1,b=-q,r=-1,s=q-1$
in Corollary 3.4. Then
$\varphi(x)=x^{1-q}x^{-q+1}h\left(x^{s}\right)^{q}h(x^{s})^{-1}=x^{1-q}(x^{-q+1}h(x^{q-1})^{q-1})=x^{1-q}x^{q-1}=1$.
Thus $f$ is an involution. ∎

##  4 Compositional inverses of AGW-PPs in the additive case

As demonstrated in Section 2, our method can be used to find the compositional
inverses for several classes of AGW-PPs in the additive case. In this section,
we further illustrate the new method by providing explicit compositional
inverse of one more class of AGW-PPs of this type. These PPs are of the form
$g(x)+g_{0}(\lambda(x))$ which is specified in Lemma 4.1.

######  Lemma 4.1.

[46, Theorem 6.1] Assume that $F$ is a finite field and $S,\overline{S}$ are
finite subsets of $F$ with $\\#S=\\#\overline{S}$ such that the maps
$\lambda:F\rightarrow S$ and $\overline{\lambda}:F\rightarrow\overline{S}$ are
surjective and $\overline{\lambda}$ is additive, i.e.,

$\overline{\lambda}(x+y)=\overline{\lambda}(x)+\overline{\lambda}(y),\ \ \ \ \
x,y\in F.$

Let $g_{0}:S\rightarrow F$, and $g:F\rightarrow F$ be maps such that

$\overline{\lambda}\circ(g+g_{0}\circ\lambda)=g\circ\lambda,$

$g(S)=\bar{S}$ and $\overline{\lambda}(g_{0}(\lambda(x)))=0$ for every $x\in
F$. Then the map $f(x)=g(x)+g_{0}(\lambda(x))$ permutes $F$ if and only if $g$
permutes $F$.

The commutative diagram for the above AGW-PP is as follows.

$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f=g+g_{0}\circ\lambda}$$\scriptstyle{\lambda}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{\lambda}}$$\textstyle{S\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{\overline{S}}$

The compositional inverse of the PP in Lemma 4.1 can be found in the following
theorem.

######  Theorem 4.2.

Let the symbols be defined as in Lemma 4.1. Let $f(x)=g(x)+g_{0}(\lambda(x))$
be a permutation over $F$ and $g^{-1}(x)$ be the compositional inverse of
$g(x)$ over $S$. Then the compositional inverse of $f(x)$ is given by

$f^{-1}(x)=g^{-1}\left(x-g_{0}(g^{-1}(\overline{\lambda}(x)))\right).$

###### Proof.

Let $L(x)$ be a linearized PP over $F$ and $\phi,\overline{\phi}$ be maps
defined by

$\phi:F\to\phi(F)$ $x\mapsto\left(\lambda(x),L(x)-\lambda(x)\right),$

and

$\overline{\phi}:F\to\overline{\phi}(F)$
$x\mapsto\left(\overline{\lambda}(x),L(x)-\overline{\lambda}(x)\right).$

Then $\phi$ and $\overline{\phi}$ are bijections, and for $(y,z)\in\phi(F)$,
we have $\phi^{-1}(y,z)=L^{-1}(y+z)$, where $\phi^{-1}$ and $L^{-1}$ denote
the compositional inverses of $\phi$ and $L$ respectively. Here is the
commutative diagram as stated in Theorem 2.2.

$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f=g+g_{0}\circ\lambda}$$\scriptstyle{\phi=(\lambda,\eta)}$$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{\phi}=(\overline{\lambda},\overline{\eta})}$$\textstyle{\phi(F)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi=(g,\tau)}$$\textstyle{\overline{\phi}(F)}$

Next, we find the map $\psi$ such that $\psi\circ\phi=\overline{\phi}\circ f$.
After direct calculation, we have

$\overline{\phi}\circ
f(x)=\left(g(\lambda(x)),L\left(g(x)\right)+L\left(g_{0}(\lambda(x))\right)-g(\lambda(x))\right).$
(4)

To compute $\psi(y,z)$ accordingly such that $\bar{\phi}\circ
f(x)=\psi\circ\phi(x)$, we substitute $\lambda(x)$ and $L(x)-\lambda(x)$ in
Eq. (4) with $y$ and $z$ respectively. We obtain

$\psi(y,z):\phi(F)\to\overline{\phi}(F),$
$(y,z)\mapsto\left(g(y),L(g(L^{-1}(y+z)))+L(g_{0}(y))-g(y)\right).$

Clearly $\psi$ is a bijection, since $\psi\circ\phi(x)=\phi\circ f(x)$. Now we
compute the compositional inverse of $\psi$. Since $f$ permutes $F$, $g$
permutes $F$, and we assume that $g^{-1}$ is the compositional inverse of $g$.
For any $(y,z)\in\phi(F)$ with
$\psi(y,z)=(\alpha,\beta)\in\overline{\phi}(F)$, we have

$\left\\{\begin{aligned} g(y)&=&\alpha,\\\
L(g(L^{-1}(y+z)))+L(g_{0}(y))-g(y)&=&\beta.\\\ \end{aligned}\right.$

Clearly,

$y=g^{-1}(\alpha).$

Moreover,

$L(g(L^{-1}(y+z)))=\alpha+\beta-L(g_{0}(y)).$ (5)

Composing $L\circ g^{-1}\circ L^{-1}$ on Eq. (5) and simplifying it, we have

$z=L\left(g^{-1}\left(L^{-1}(\alpha+\beta)-g_{0}(g^{-1}(\alpha))\right)\right)-g^{-1}(\alpha).$

Hence we have

$\psi^{-1}\left(\alpha,\beta\right)=\left(g^{-1}(\alpha),L\left(g^{-1}\left(L^{-1}(\alpha+\beta)-g_{0}(g^{-1}(\alpha))\right)\right)-g^{-1}(\alpha)\right).$

Finally we compute the compositional inverse of $f(x)$. According to Theorem
2.2, together with $\alpha=\overline{\lambda}(x)$ and
$\beta=L(x)-\overline{\lambda}(x)$, we obtain the compositional inverse of
$f(x)$ is

$f^{-1}(x)={\phi}^{-1}\circ\psi^{-1}\circ\overline{\phi}(x)=g^{-1}\left(L^{-1}(\alpha+\beta)-g_{0}(g^{-1}(\alpha))\right)=g^{-1}\left(x-g_{0}(g^{-1}(\overline{\lambda}(x)))\right).$

∎

Theorem 4.2 can be checked directly by $f^{-1}(f(x))=x$ for any $x\in F$ (we
omit the details here). The compositional inverse of
$f(x)=g_{1}(\lambda(x))^{s}+g(x)$ in [46, Corollary 6.2] is given in Corollary
4.3, as an example of Theorem 4.2. Since $g$ is a linearized PP on
$\mathbb{F}_{q^{n}}$, its compositional inverse $g^{-1}$ can be explicitly
obtained (see [59]).

######  Corollary 4.3.

Let $n$ and $k$ be positive integers such that $\gcd(n,k)=d>1$, let $s$ be any
positive integer with $s\left(q^{k}-1\right)\equiv 0\pmod{q^{n}-1}.$ Let
$g(x)\in\mathbb{F}_{q}[x]$ be a linearized polynomial permuting
$\mathbb{F}_{q^{n}}$, $\lambda(x)=\overline{\lambda}(x)$ be a
$q^{d}$-polynomial with $\lambda(1)=0$ and $g_{1}(x)\in\mathbb{F}_{q^{n}}[x]$.
Then the compositional inverse of
$f(x)=\left(g_{1}(\lambda(x))\right)^{s}+g(x)$ over $\mathbb{F}_{q^{n}}$ is

$f^{-1}(x)=g^{-1}\left(x-g_{1}(g^{-1}({\lambda}(x)))^{s}\right).$

In addition, we give a criterion for PPs of the form $g(x)+g_{0}(\lambda(x))$
being involutions.

######  Corollary 4.4.

In Lemma 4.1, let $\lambda=\bar{\lambda}$, $S=\bar{S}$ be a finite subset of
$F$ such that $\lambda(F)=S$, and let $g$ be a bijection from $S$ to $S$.
Then, the PP $f(x)=g(x)+g_{0}(\lambda(x))$ over $F$ defined as in Lemma 4.1 is
an involution if and only if
$\varphi(x)=g^{-1}\left(x-g_{0}(g({\lambda}(x)))\right)-g(x)-g_{0}(\lambda(x))=0$
holds for any $x\in F$.

###### Proof.

Its proof can be easily derived by applying Theorem 4.2 and thus we omit the
details. ∎

Below, we provide some explicit constructions of involutions from Corollary
4.4.

######  Corollary 4.5.

Let $q$ be an even prime power and $\lambda(g_{0}(\lambda(x)))=0$ hold for any
$x\in F={\mathbb{F}}_{q^{n}}$ defined as in Lemma 4.1, with
$\overline{\lambda}=\lambda$ being additive. Then the PP
$f(x)=x+g_{0}(\lambda(x))$ is an involution on ${\mathbb{F}}_{q^{n}}$.

######  Example 4.6.

Let $q$ be a power of $2$, $S={\mathbb{F}}_{q}$, and $g_{0}$ be any polynomial
such that $g_{0}({\mathbb{F}}_{q})\subseteq{\mathbb{F}}_{q}$. Assume $n$ is an
even integer, $\lambda(x)={\rm Tr}_{q^{n}/q}(x)$. Thus we have ${\rm
Tr}_{q^{n}/q}(1)=0$ and ${\rm Tr}_{q^{n}/q}(g_{0}({\rm Tr}_{q^{n}/q}(x)))={\rm
Tr}_{q^{n}/q}(1)g_{0}({\rm Tr}_{q^{n}/q}(x))=0$ holds for any $x\in
F={\mathbb{F}}_{q^{n}}$. Then $f(x)=x+g_{0}({\rm Tr}_{q^{n}/q}(x))$ is an
involution on ${\mathbb{F}}_{q^{n}}$.

##  5 Compositional inverses of AGW-PPs in the hybrid case

In this section, we use our method to study AGW-PPs in the hybrid case, and to
obtain the compositional inverses of $xh(\lambda(x))$ in Lemma 5.1 and
$x+\gamma G(\lambda(x))$ in Lemma 5.6 as examples. For each class, we obtain
the inverses of these PPs and present some explicit classes. We also provide
an involutory criterion and demonstrate some involutory constructions.

######  Lemma 5.1.

[36, Theorem 6.3] Let $q$ be any power of the prime number $p$, let $n$ be any
positive integer, and let $S$ be any subset of ${\mathbb{F}}_{q^{n}}$
containing 0. Let $h,k\in{\mathbb{F}}_{q^{n}}$ be any polynomials such that
$h(0)\neq 0$ and $k(0)=0$, and let ${\lambda(x)}\in{\mathbb{F}}_{q^{n}}[x]$ be
any polynomial satisfying

  1. (1)

$h(\lambda({\mathbb{F}}_{q^{n}}))\subseteq S$; and

  2. (2)

$\lambda(a\alpha)=k(a)\lambda(\alpha)$ for all $a\in S$ and all
$\alpha\in{\mathbb{F}}_{q^{n}}$.

Then the polynomial $f(x)=xh(\lambda(x))$ is a permutation polynomial for
${\mathbb{F}}_{q^{n}}$ if and only if $g(x)=xk(h(x))$ induces a permutation of
$\lambda({\mathbb{F}}_{q^{n}})$.

The above AGW-PPs can be illustrated by the following commutative diagram.

$\textstyle{{\mathbb{F}}_{q^{n}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f(x)=xh(\lambda(x))}$$\scriptstyle{\lambda}$$\textstyle{{\mathbb{F}}_{q^{n}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda}$$\textstyle{\lambda({\mathbb{F}}_{q^{n}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{{g(x)}=xk(h(x))}$$\textstyle{\lambda({\mathbb{F}}_{q^{n}}).}$

Using our unified approach, we choose $\eta(x)=x-\lambda(x)$ such that
$\phi(x)=(\lambda(x),x-\lambda(x))$ is bijective and thus obtain the
compositional inverses in the following theorem.

######  Theorem 5.2.

Let the symbols be defined as in Lemma 5.1. Let $f(x)=xh(\lambda(x))$ permute
${\mathbb{F}}_{q^{n}}$ and $g^{-1}(x)$ be the compositional inverse of
$g(x)=xk(h(x))$ over $\lambda({\mathbb{F}}_{q^{n}})$. Then the compositional
inverse of $f(x)$ is given by

$f^{-1}(x)=\frac{x-\lambda(x)+k\left(h\left(g^{-1}\left(\lambda(x)\right)\right)\right)g^{-1}\left(\lambda(x)\right)}{h\left(g^{-1}\left(\lambda(x)\right)\right)}.$

###### Proof.

Let $\eta(x)=x-\lambda(x)$ and $\phi$ be a map defined by

$\phi:{\mathbb{F}}_{q^{n}}\to\phi({\mathbb{F}}_{q^{n}}),$
$x\mapsto\left(\lambda(x),x-\lambda(x)\right).$

Then $\phi$ is a bijection and for $(y,z)\in\phi({\mathbb{F}}_{q^{n}}),\
\phi^{-1}(y,z)=y+z.$ Let us consider the following commutative diagram.

$\textstyle{{\mathbb{F}}_{q^{n}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f(x)=xh(\lambda(x))}$$\scriptstyle{\phi=(\lambda,\eta)}$$\textstyle{{\mathbb{F}}_{q^{n}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\phi=(\lambda,\eta)}$$\textstyle{\phi({\mathbb{F}}_{q^{n}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi=(g,\tau)}$$\textstyle{\phi({\mathbb{F}}_{q^{n}})}$

First we determine the expression of $\psi$ to establish the connection
${\phi}\circ f(x)=\psi\circ\phi(x)$. After direct computation, we have

$\phi\circ
f(x)=\left(\lambda(x)k(h(\lambda(x))),xh(\lambda(x))-k(h(\lambda(x)))\lambda(x)\right).$
(6)

Then, substituting $\lambda(x)$ and $x-\lambda(x)$ in Eq. (6) with $y$ and $z$
respectively, we obtain

$\psi(y,z):\phi({\mathbb{F}}_{q^{n}})\to\phi({\mathbb{F}}_{q^{n}}),$
$(y,z)\mapsto\left(yk(h(y)),(y+z)h(y)-k(h(y))y\right).$

Since $f(x)=xh(\lambda(x))$ permutes ${\mathbb{F}}_{q^{n}}$, we have that both
$\psi$ and $g(x)=xk(h(x))$ are bijective. Recall that $g^{-1}$ denotes the
compositional inverse of $g(y)=yk(h(y))$ over $\lambda({\mathbb{F}}_{q^{n}})$.
In the following, we compute the compositional inverse of $\psi$. Let
$(y,z),(\alpha,\beta)\in\phi({\mathbb{F}}_{q^{n}}),$ satisfy
$\psi(y,z)=(\alpha,\beta)$, i.e.,

$\left\\{\begin{aligned} yk(h(y))&=&\alpha,\\\ (y+z)h(y)-k(h(y))y&=&\beta.\\\
\end{aligned}\right.$ (7)

Then, we have

$y=g^{-1}(\alpha).$

Moreover, for $z$, we firstly explain $h(y)\neq 0$ for any
$y\in\lambda({\mathbb{F}}_{q^{n}})$. Assume that there exists some
$y_{0}\in\lambda({\mathbb{F}}_{q^{n}})$ such that $h(y_{0})=0$. We have
$g(y_{0})=y_{0}k(h(y_{0}))=0$ and $g(0)=0$. Since $g(y)$ is bijective, we have
$y_{0}=0$, which is conflict with $h(0)\neq 0$. Thus $h(y)\neq 0$ for any
$y\in\lambda({\mathbb{F}}_{q^{n}})$. Then it follows from Eq.(7) that

$z=\frac{\beta+k\left(h\left(y\right)\right)y}{h\left(y\right)}-y.$

Hence, we have

$\psi^{-1}\left(\alpha,\beta\right)=\left(g^{-1}(\alpha),\frac{\beta+k\left(h\left(g^{-1}(\alpha)\right)\right)g^{-1}(\alpha)}{h\left(g^{-1}(\alpha)\right)}-g^{-1}(\alpha)\right).$

Finally, we compute the compositional inverse of $f(x)$. From Theorem 2.2,
together with the compositional inverses of $\phi,\psi$ and
$\alpha=\lambda(x)$, $\beta=x-\lambda(x)$, the compositional inverse of $f(x)$
is

$\displaystyle f^{-1}(x)$
$\displaystyle={\phi}^{-1}\circ\psi^{-1}\circ{\phi}(x)$
$\displaystyle=g^{-1}(\alpha)+\frac{\beta+k\left(h\left(g^{-1}(\alpha)\right)\right)g^{-1}(\alpha)}{h\left(g^{-1}(\alpha)\right)}-g^{-1}(\alpha)$
$\displaystyle=\frac{x-\lambda(x)+k\left(h\left(g^{-1}\left(\lambda(x)\right)\right)\right)g^{-1}\left(\lambda(x)\right)}{h\left(g^{-1}\left(\lambda(x)\right)\right)}.$

∎

Theorem 5.2 can also be verified by $f^{-1}(f(x))=x$ for any $x\in F$ (we omit
the details here). A special case of Theorem 5.2 with $k(x)=x^{2}$ and
$S={\mathbb{F}}_{p}$ (see [60, Proposition 12]) is given in the following
corollary.

######  Corollary 5.3.

Let $\lambda(x)$ be either $\lambda_{2}(x)=\sum\limits_{0\leq i<j\leq
n-1}{{x^{{p^{i}}+{p^{j}}}}}$ or $T_{2}(x)={\rm Tr}_{p^{n}/p}(x^{2})$. Let
$h(x)\in{\mathbb{F}}_{p}[x]$ such that $h(0)\neq 0$. If the polynomial
$g(x)=x(h(x))^{2}$ permutes ${\mathbb{F}}_{p}$, then the polynomial
$f(x)=xh(\lambda(x))$ permutes ${\mathbb{F}}_{p^{n}}$, and the compositional
inverse of $f(x)$ is given by

$f^{-1}(x)=\frac{x-\lambda(x)+\left(h\left(g^{-1}\left(\lambda(x)\right)\right)\right)^{2}g^{-1}\left(\lambda(x)\right)}{h\left(g^{-1}\left(\lambda(x)\right)\right)}.$

In addition, we propose a criterion for PPs of the form $xh(\lambda(x))$ being
involutions, and give some involutory constructions.

######  Corollary 5.4.

Let $f(x)=xh(\lambda(x))$, $g(x)=xk(h(x))$ and $h,k,\lambda$ defined as in
Lemma 5.1. Let $\theta(x)=k(h(x))$ for any $x\in{\mathbb{F}}_{q^{n}}$. Then
$f$ is an involution over ${\mathbb{F}}_{q^{n}}$ if and only if

  1. (1)

$\theta\left(\theta(y)y\right)\theta(y)=1$ holds for any
$y\in\lambda({\mathbb{F}}_{q^{n}}^{*})$, and

  2. (2)

$\varphi(y)=h\left(g(y)\right)h(y)-1=0$ holds for any
$y\in\lambda({\mathbb{F}}_{q^{n}}^{*})$.

###### Proof.

Since $f(0)=0$, we only need to consider the nonzero situation. Assume $f$ is
an involution. By Lemma 2.9, we have $g$ is an involution, which is equivalent
to
$\theta\left(\theta(y)y\right)\theta(y)=k\left(h\left(k(h(y))y\right)\right)k(h(y))=1$
for $y\in\lambda({\mathbb{F}}_{q^{n}}^{*})$. From now on, we assume (1) hold
and prove that $f$ is an involution if and only if $\varphi(x)=0$. Plugging

$k\left(h\left(k(h(y))y\right)\right)k(h(y))=1$

for $y\in\lambda({\mathbb{F}}_{q^{n}}^{*})$, $g^{-1}(x)=g(x)$ and $f^{-1}(x)$
by Theorem 5.2 into $\varphi(x)$, we have

$\displaystyle x\varphi(x)$ $\displaystyle=$ $\displaystyle
h\left(k(h(\lambda(x)))\lambda(x)\right)xh(\lambda(x))-x$ $\displaystyle=$
$\displaystyle
h\left(k(h(\lambda(x)))\lambda(x)\right)xh(\lambda(x))-x+\lambda(x)-\lambda(x)k\left(h\left(k(h(\lambda(x)))\lambda(x)\right)\right)k(h(\lambda(x)))$
$\displaystyle=$ $\displaystyle
h\left(g\left(\lambda(x)\right)\right)\left(xh(\lambda(x))-\frac{x-\lambda(x)+k\left(h\left(g^{-1}\left(\lambda(x)\right)\right)\right)g^{-1}\left(\lambda(x)\right)}{h\left(g^{-1}\left(\lambda(x)\right)\right)}\right)$
$\displaystyle=$ $\displaystyle
h\left(g\left(\lambda(x)\right)\right)\left(f(x)-f^{-1}(x)\right),$

for $x\in{\mathbb{F}}_{q^{n}}^{*}$. Note $h(y)\neq 0$ because
$f(x)=xh(\lambda(x))$ permutes ${\mathbb{F}}_{q^{n}}$ and $f(0)=0$. Hence
$f(x)$ is an involution if and only if $\varphi=0$. ∎

######  Example 5.5.

Let $q=3^{n}$. Then, $f(x)=x(\lambda(x)^{2}+1)$ is an involution over
${\mathbb{F}}_{q}$, where $\lambda(x)=\sum\limits_{0\leq i<j\leq
n-1}{{x^{{3^{i}}+{3^{j}}}}}$.

###### Proof.

Let $h(x)=x^{2}+1$, $S={\mathbb{F}}_{3}$ in Lemma 5.1. We have $k(x)=x^{2}$
and $\lambda({\mathbb{F}}_{q}^{*})={\mathbb{F}}_{3}$. One can obtain
$g(y)=y(y^{2}+1)^{2}=y$ and $\theta(y)=(y^{2}+1)^{2}=1$ for
$y\in{\mathbb{F}}_{3}$. Hence
$\theta(\theta(y)y)\theta(y)=\theta(g(y))\theta(y)=\theta(y)^{2}=1$ and
$\varphi(y)=h\left(g(y)\right)h(y)-1=h(y)^{2}-1=0$. By Corollary 5.4, $f(x)$
is an involution. ∎

In the following, we will give explicitly the compositional inverse of a PP
containing a $b$-linear translator. For
$S\subset{\mathbb{F}}_{q},\gamma,b\in{\mathbb{F}}_{q}$ and a map
${\lambda}:{\mathbb{F}}_{q}\rightarrow{\mathbb{F}}_{q},\ \gamma$ is called a
$b$-linear translator [36, 61, 47] of $\lambda$ with respect to $S$ if
$\lambda(x+u\gamma)=\lambda(x)+ub$ for all $x\in{\mathbb{F}}_{q}$ and $u\in
S$.

######  Lemma 5.6.

[36, Theorem 6.4] Let $S\subseteq{\mathbb{F}}_{q}$ and
$\lambda:{\mathbb{F}}_{q}\rightarrow S$ be a surjective map. Let
$\gamma\in{\mathbb{F}}_{q}^{*}$ be a $b$-linear translator with respect to $S$
for the map $\lambda$. Then for any $G\in{\mathbb{F}}_{q}[x]$ which maps $S$
into $S$, we have that $f(x)=x+\gamma G(\lambda(x))$ is a permutation
polynomial of ${\mathbb{F}}_{q}$ if and only if $g(x)=x+bG(x)$ permutes $S$.

It can be illustrated by the following commutative diagram.

$\textstyle{{\mathbb{F}}_{q}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{\lambda}$$\textstyle{{\mathbb{F}}_{q}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\lambda}$$\textstyle{\lambda({\mathbb{F}}_{q})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{g}$$\textstyle{\lambda({\mathbb{F}}_{q}).}$

Below, we describe how to obtaining the compositional inverses of PPs
$f(x)=x+\gamma G(\lambda(x))$. The fundamental idea of our approach is the
following commutative diagram, where we design $\eta(x)=x-\lambda(x)$ such
that $\phi(x)=(\lambda(x),x-\lambda(x))$ is bijective, see Theorem 5.7.

$\textstyle{{\mathbb{F}}_{q}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{f}$$\scriptstyle{\phi=(\lambda,\eta)}$$\textstyle{{\mathbb{F}}_{q}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\phi=(\lambda,\eta)}$$\textstyle{\phi({\mathbb{F}}_{q})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi=(g,\tau)}$$\textstyle{\phi({\mathbb{F}}_{q}).}$

We obtain the compositional inverses in the following theorem:

######  Theorem 5.7.

Let $f(x)=x+\gamma G(\lambda(x))$ defined as in Lemma 5.6 be a PP on
${\mathbb{F}}_{q}$ and $g^{-1}(x)$ be the compositional inverse of
$g(x)=x+bG(x)$. Then the compositional inverse of $f(x)$ is given by

$f^{-1}(x)=(b-\gamma)G\left(g^{-1}(\lambda(x))\right)+g^{-1}(\lambda(x))-\lambda(x)+x.$

###### Proof.

Using the same notation and assumptions of Lemma 5.6, let $\phi$ be a map
defined by

$\phi:{\mathbb{F}}_{q^{n}}\to\phi({\mathbb{F}}_{q^{n}}),$
$x\mapsto\left(\lambda(x),x-\lambda(x)\right).$

Then $\psi$ is a bijection and for $(y,z)\in\phi({\mathbb{F}}_{q^{n}}),\
\psi^{-1}(y,z)=y+z.$

Next, we determine the expression of $\psi$ from the equation ${\phi}\circ
f(x)=\psi\circ\phi(x)$. After direct computation, we have

${\phi}\circ
f(x)=\left(\lambda(x)+bG(\lambda(x)),x-\lambda(x)+(\gamma-b)G(\lambda(x))\right).$
(8)

Substituting $\lambda(x)$ and $x-\lambda(x)$ in Eq. (8) with $y$ and $z$
respectively, we obtain

$\psi(y,z):\phi({\mathbb{F}}_{q^{n}})\to\phi({\mathbb{F}}_{q^{n}}),$
$(y,z)\mapsto\left(y+bG(y),z+(\gamma-b)G(y)\right).$

Since $f(x)=x+\gamma G(\lambda(x))$ is a PP on ${\mathbb{F}}_{q}$, $\psi$ and
$g(x)=x+bG(x)$ are both bijective. We assume that $g^{-1}$ denotes the
compositional inverse of $g(x)=x+bG(x)$ over $S$. In the following, we compute
the compositional inverse of $\psi$. Let
$(y,z),(\alpha,\beta)\in\phi({\mathbb{F}}_{q^{n}}),$ satisfy
$\psi(y,z)=(\alpha,\beta)$, i.e.,

$\left\\{\begin{aligned} y+bG(y)&=&\alpha,\\\ z+(\gamma-b)G(y)&=&\beta.\\\
\end{aligned}\right.$

We have

$y=g^{-1}(\alpha).$

Moreover,

$z=\beta+(b-\gamma)G\left(g^{-1}(\alpha)\right).$

Hence, we obtain

$\psi^{-1}\left(\alpha,\beta\right)=\left(g^{-1}(\alpha),\beta+(b-\gamma)G\left(g^{-1}(\alpha)\right)\right).$

Finally, we compute the compositional inverse of $f(x)$. From Theorem 2.2,
together with the compositional inverses of $\phi,\psi$ and
$\alpha=\lambda(x)$, $\beta=x-\lambda(x)$, the compositional inverse of $f(x)$
is

$\displaystyle f^{-1}(x)$
$\displaystyle={\phi}^{-1}\circ\psi^{-1}\circ{\phi}(x)$
$\displaystyle=g^{-1}(\alpha)+\beta+(b-\gamma)G\left(g^{-1}(\alpha)\right)$
$\displaystyle=(b-\gamma)G\left(g^{-1}(\lambda(x))\right)+g^{-1}(\lambda(x))-\lambda(x)+x.$

∎

Theorem 5.7 can be verified drectly by $f^{-1}(f(x))=x$ for any
$x\in{\mathbb{F}}_{q}$. Firstly, for any $x\in{\mathbb{F}}_{q}$, we have

$\displaystyle g^{-1}(\lambda(f(x)))$ $\displaystyle=$ $\displaystyle
g^{-1}\left(\lambda(x+\gamma G(\lambda(x)))\right)$ $\displaystyle=$
$\displaystyle
g^{-1}(\lambda(x)+bG(\lambda(x)))=g^{-1}(g(\lambda(x)))=\lambda(x),$

where the second equality is due to the fact that $\gamma$ is a $b$-linear
translator with respect to $S$ for the map $\lambda$. Therefore we obtain

$\displaystyle f^{-1}(f(x))$ $\displaystyle=$
$\displaystyle(b-\gamma)G(\lambda(x))+\lambda(x)-\lambda(x+\gamma
G(\lambda(x)))+x+\gamma G(\lambda(x))$ $\displaystyle=$
$\displaystyle(b-\gamma)G(\lambda(x))+\lambda(x)-(\lambda(x)+bG(\lambda(x)))+x+\gamma
G(\lambda(x))=x.$

Note that [29, Theorem 1.2] requires its $\psi$ to be additive. However, we
focus more on $\lambda(x)$ such that it has a $b$-linear translator with
respect to $S$, especially the case when $\lambda(x)$ is not additive and even
$\lambda(0)\neq 0$. Specifically, when $\lambda(x)={\rm Tr}_{q^{n}/q}(x)$ or
$G$ is a $q$-polynomial, Theorem 5.7 is consistent with [29, Corollary 1.6].

A special case of Theorem 5.7 with $G(x)=x$ (see [36, Corollary 6.5]) is the
following corollary:

######  Corollary 5.8.

[47, Theorem 3] If $b\neq-1$, then the compositional inverse of the
permutation $x+\gamma\lambda(x)$ on ${\mathbb{F}}_{q}$ is
$\frac{-\gamma}{b+1}\lambda(x)+x$.

Furthermore, we propose a criterion for PPs of the form $x+\gamma
G(\lambda(x))$ being involutions, and give some involutory constructions.

######  Corollary 5.9.

Suppose $\gamma\in{\mathbb{F}}_{q}^{*}$. Then the PP $f(x)=x+\gamma
G(\lambda(x))$ over ${\mathbb{F}}_{q}$ defined as in Lemma 5.6 is an
involution if and only if

  1. (1)

$bG(y)+bG(y+bG(y))=0$, for $y\in\lambda({\mathbb{F}}_{q})$ and

  2. (2)

anyone of the following holds:

    1. (i)

$b\neq 0$;

    2. (ii)

$q$ is even;

    3. (iii)

$G(\lambda(x))=0$ when $q$ is odd and $b=0$.

###### Proof.

Assume $f$ is an involution. By Lemma 2.9, we have $bG(y)+bG(y+bG(y))=0$ for
$y\in\lambda({\mathbb{F}}_{q})$, where $g(x)=x+bG(x)$ is defined as in Lemma
5.6. From now on, we assume Condition (1) holds. Then, it suffices to prove
that $f$ is an involution if and only if $\varphi(x)=0$. Let
$\varphi(x)=\gamma G(\lambda(x))+\gamma
G\left(\lambda(x)+bG(\lambda(x))\right)$. Plugging $bG(y)+bG(y+bG(y))=0$ for
$y\in\lambda({\mathbb{F}}_{q})$, $g^{-1}(x)=g(x)$ and $f^{-1}(x)$ by Theorem
5.7 into $\varphi(x)$, we have $f(x)$ is an involution if and only if
$\varphi(x)=0$ holds for any $x\in{\mathbb{F}}_{q}$. If $b\neq 0$, then
Condition (1) implies that $G(\lambda(x))=-G(\lambda(x)+bG(\lambda(x)))$ and
thus $\varphi(x)=0$ for any $x\in{\mathbb{F}}_{q}$. If $b=0$ and $q$ is even,
then $\varphi(x)=2\gamma G(\lambda(x))=0$ as well. If $b=0$ and $q$ is odd,
then

$\varphi(x)=\gamma G(\lambda(x))+\gamma G(\lambda(x)+bG(\lambda(x)))=2\gamma
G(\lambda(x)).$

In this case, $\varphi(x)=0$ if and only if $G(\lambda(x))=0$.

∎

When we consider $0$-linear translator in a finite field of even
characteristic, the following explicit involution can be obtained easily.

######  Corollary 5.10.

Let $q$ be a power of $2$. Assume $S\subseteq{\mathbb{F}}_{q}$ and
$\lambda:{\mathbb{F}}_{q}\rightarrow S$ is a surjective map. Let
$\gamma\in{\mathbb{F}}_{q}$ be a $0$-linear translator with respect to $S$ for
the map $\lambda$. Then for any $G\in{\mathbb{F}}_{q}[x]$ which maps $S$ into
$S$, we have that $f(x)=x+\gamma G(\lambda(x))$ is an involution on
${\mathbb{F}}_{q}$.

We provide a specific construction as an example of Corollary 5.10.

######  Example 5.11.

Let $q$ be a power of $2$ and $n>2$ be any integer. Let $S={\mathbb{F}}_{q}$
and $\lambda(x)=\sum\limits_{1\leq i<j\leq
n}{\beta_{i}(x^{q^{i}}+x^{q^{j}})}\in\mathbb{F}_{q^{n}}[x]$. Clearly, each
$\gamma\in{\mathbb{F}}_{q}$ is a $0$-linear translator with respect to
${\mathbb{F}}_{q}$ for the map $\lambda(x)$. Then for any
$G\in{\mathbb{F}}_{q^{n}}[x]$ which maps ${\mathbb{F}}_{q}$ into
${\mathbb{F}}_{q}$, we have that $f(x)=x+\gamma G\left(\sum\limits_{1\leq
i<j\leq n}{\beta_{i}(x^{q^{i}}+x^{q^{j}})}\right)$ is an involution on
${\mathbb{F}}_{q^{n}}$.

## Acknowledgement

We thank the editor Sudhir R Ghorpade and anonymous referees for their helpful
suggestions.

## References

  * [1] C. Carlet, P. Charpin, and V. Zinoviev, “Codes, bent functions and permutations suitable for DES-like cryptosystems,” _Designs, Codes and Cryptography_ , vol. 15, no. 2, pp. 125–156, 1998.
  * [2] C. Ding, L. Qu, Q. Wang, J. Yuan, and P. Yuan, “Permutation trinomials over finite fields with even characteristic,” _SIAM Journal on Discrete Mathematics_ , vol. 29, no. 1, pp. 79–92, 2015.
  * [3] X.-d. Hou, “Determination of a type of permutation trinomials over finite fields, II,” _Finite Fields and Their Applications_ , vol. 35, pp. 16–35, 2015.
  * [4] C. Ding and J. Yuan, “A family of skew Hadamard difference sets,” _Journal of Combinatorial Theory, Series A_ , vol. 113, no. 7, pp. 1526–1535, 2006.
  * [5] H. Dobbertin, “Almost perfect nonlinear power functions on GF($2^{n}$): the Welch case,” _IEEE Transactions on Information Theory_ , vol. 45, no. 4, pp. 1271–1275, 1999.
  * [6] W. Muller, “Some remarks on public key cryptography,” _Studia Sci. Math. Hung._ , vol. 16, pp. 71–76, 1981.
  * [7] R. Lidl and W. B. Müller, “Permutation polynomials in RSA-cryptosystems,” in _Advances in Cryptology_. Springer, 1984, pp. 293–301.
  * [8] H. Dobbertin, “Almost perfect nonlinear power functions on GF($2^{n}$): the Niho case,” _Information and Computation_ , vol. 151, no. 1-2, pp. 57–72, 1999.
  * [9] R. L. McFarland, “A family of difference sets in non-cyclic groups,” _Journal of Combinatorial Theory, Series A_ , vol. 15, no. 1, pp. 1–10, 1973\.
  * [10] C. Ding, “Cyclic codes from some monomials and trinomials,” _SIAM Journal on Discrete Mathematics_ , vol. 27, no. 4, pp. 1977–1994, 2013.
  * [11] U. Dempwolff and P. Müller, “Permutation polynomials and translation planes of even order,” _Advances in Geometry_ , vol. 13, no. 2, pp. 293–313, 2013.
  * [12] X.-d. Hou, “Permutation polynomials over finite fields—a survey of recent advances,” _Finite Fields and Their Applications_ , vol. 32, pp. 82–119, 2015.
  * [13] N. Li and X. Zeng, “A survey on the applications of Niho exponents,” _Cryptography and Communications_ , vol. 11, no. 3, pp. 509–548, 2019.
  * [14] G. L. Mullen and Q. Wang, “Permutation polynomials of one variable,” in _Handbook of Finite Fields_. CRC, 2014, pp. 215–230.
  * [15] Q. Wang, “Polynomials over finite fields: an index approach,” in _Combinatorics and Finite Fields. Difference Sets, Polynomials, Pseudorandomness and Applications_. Degruyter, 2019, pp. 319–348.
  * [16] P. Charpin, S. Mesnager, and S. Sarkar, “Involutions over the galois field ${\mathbb{F}}_{2^{n}}$,” _IEEE Transactions on Information Theory_ , vol. 62, no. 4, pp. 2266–2276, 2016.
  * [17] D. Zheng, M. Yuan, N. Li, L. Hu, and X. Zeng, “Constructions of involutions over finite fields,” _IEEE Transactions on Information Theory_ , vol. 65, no. 12, pp. 7876–7883, 2019.
  * [18] T. Niu, K. Li, L. Qu, and Q. Wang, “New constructions of involutions over finite fields,” _Cryptography and Communications_ , vol. 12, no. 2, pp. 165–185, 2020.
  * [19] M. Wu, C. Li, and Z. Wang, “Characterizations and constructions of triple-cycle permutations of the form $x^{r}h(x^{s})$,” _Designs, Codes and Cryptography_ , vol. 88, no. 10, pp. 2119–2132, 2020.
  * [20] Y. Chen, L. Wang, and S. Zhu, “On the constructions of $n$-cycle permutations,” _arXiv:2007.14865_ , Jul. 2020.
  * [21] G. M. Kyureghyan and V. Suder, “On inverses of APN exponents,” in _Proceedings of the 2012 IEEE International Symposium on Information Theory, ISIT 2012, Cambridge, MA, USA, July 1-6, 2012_. IEEE, 2012, pp. 1207–1211.
  * [22] G. M. M. Kyureghyan and V. Suder, “On inversion in $\mathbb{Z}_{2^{n}-1}$,” _Finite Fields Their Applications_ , vol. 25, pp. 234–254, 2014.
  * [23] K. Li, L. Qu, and Q. Wang, “Compositional inverses of permutation polynomials of the form $x^{r}h(x^{s})$ over finite fields,” _Cryptography and Communications_ , vol. 11, no. 2, pp. 279–298, 2019.
  * [24] R. Lidl, G. L. Mullen, and G. Turnwald, _Dickson Polynomials_. Longman Scientific and Technical, 1993.
  * [25] B. Wu and Z. Liu, “The compositional inverse of a class of bilinear permutation polynomials over finite fields of characteristic $2$,” _Finite Fields and Their Applications_ , vol. 24, pp. 136–147, 2013.
  * [26] R. Lidl and H. Niederreiter, _Finite fields_. Cambridge university press, 1997, vol. 20.
  * [27] B. Wu and Z. Liu, “Linearized polynomials over finite fields revisited,” _Finite Fields and Their Applications_ , vol. 22, pp. 79–100, Jul. 2013.
  * [28] ——, “The compositional inverse of a class of bilinear permutation polynomials over finite fields of characteristic 2,” _Finite Fields and Their Applications_ , vol. 24, pp. 136–147, Nov. 2013.
  * [29] A. Tuxanidy and Q. Wang, “On the inverses of some classes of permutations of finite fields,” _Finite Fields and Their Applications_ , vol. 28, pp. 244–281, 2014.
  * [30] B. Wu, “The compositional inverse of a class of linearized permutation polynomials over $\mathbb{F}_{2^{n}}$, $n$ odd,” _Finite Fields and Their Applications_ , vol. 29, pp. 34–48, 2014.
  * [31] Q. Wang, “A note on inverses of cyclotomic mapping permutation polynomials over finite fields,” _Finite Fields and Their Applications_ , vol. 45, pp. 422–427, 2017.
  * [32] Y. Zheng, Q. Wang, and W. Wei, “On inverses of permutation polynomials of small degree over finite fields,” _IEEE Transactions on Information Theory_ , 2019.
  * [33] R. S. Coulter and M. Henderson, “The compositional inverse of a class of permutation polynomials over a finite field,” _Bulletin of the Australian Mathematical Society_ , vol. 65, no. 3, pp. 521–526, 2002.
  * [34] A. Tuxanidy and Q. Wang, “Compositional inverses and complete mappings over finite fields,” _Discrete Applied Mathematics_ , vol. 217, pp. 318–329, 2017\.
  * [35] Y. Zheng, “Inverse of large class of permutation polynomials of finite fields,” _arXiv preprint arXiv:1812.11812_ , 2018. [Online]. Available: https://arxiv.org/abs/1812.11812
  * [36] A. Akbary, D. Ghioca, and Q. Wang, “On constructing permutations of finite fields,” _Finite Fields and Their Applications_ , vol. 17, no. 1, pp. 51–67, 2011.
  * [37] R. Gupta and R. Sharma, “Some new classes of permutation trinomials over finite fields with even characteristic,” _Finite Fields and Their Applications_ , vol. 41, pp. 89–96, 2016.
  * [38] N. Li and T. Helleseth, “Several classes of permutation trinomials from Niho exponents,” _Cryptography and Communications_ , vol. 9, no. 6, pp. 693–705, 2017.
  * [39] K. Li, L. Qu, and X. Chen, “New classes of permutation binomials and permutation trinomials over finite fields,” _Finite Fields and Their Applications_ , vol. 43, pp. 69–85, 2017.
  * [40] Z. Zha, L. Hu, and S. Fan, “Further results on permutation trinomials over finite fields with even characteristic,” _Finite Fields and Their Applications_ , vol. 45, pp. 43–52, 2017.
  * [41] N. Cepak, P. Charpin, and E. Pasalic, “Permutations via linear translators,” _Finite Fields and Their Applications_ , vol. 45, pp. 19–42, 2017.
  * [42] K. Li, L. Qu, C. Li, and S. Fu, “New permutation trinomials constructed from fractional polynomials,” _Acta Arithmetica_ , vol. 183, pp. 101–116, 2018\.
  * [43] Z. Tu and X. Zeng, “Two classes of permutation trinomials with Niho exponents,” _Finite Fields and Their Applications_ , vol. 53, pp. 99–112, 2018.
  * [44] D. Zheng, M. Yuan, and L. Yu, “Two types of permutation polynomials with special forms,” _Finite Fields and Their Applications_ , vol. 56, pp. 1–16, 2019.
  * [45] Y. Laigle-Chapuy, “A note on a class of quadratic permutations over ${\mathbb f}_{{2n̂}}$,” in _Applied Algebra, Algebraic Algorithms and Error-Correcting Codes_ , ser. Lecture Notes in Computer Science, S. Boztaş and H.-F. F. Lu, Eds. Springer, 2007, pp. 130–137.
  * [46] P. Yuan and C. Ding, “Permutation polynomials over finite fields from a powerful lemma,” _Finite Fields and Their Applications_ , vol. 17, no. 6, pp. 560–574, 2011.
  * [47] G. M. Kyureghyan, “Constructing permutations of finite fields via linear translators,” _Journal of Combinatorial Theory, Series A_ , vol. 118, no. 3, pp. 1052–1061, 2011.
  * [48] K. Li, L. Qu, and Q. Wang, “New constructions of permutation polynomials of the form $x^{r}h\left(x^{q-1}\right)$ over ${\mathbb{F}}_{q^{2}}$,” _Designs, Codes and Cryptography_ , vol. 86, no. 10, pp. 2379–2405, 2018.
  * [49] Y. Zheng, P. Yuan, and D. Pei, “Large classes of permutation polynomials over $\mathbb{F}_{q^{2}}$,” _Designs, Codes and Cryptography_ , vol. 81, no. 3, pp. 505–521, 2016.
  * [50] A. Akbary, D. Ghioca, and Q. Wang, “On permutation polynomials of prescribed shape,” _Finite Fields and Their Applications_ , vol. 15, no. 2, pp. 195–206, 2009.
  * [51] Q. Wang, “Cyclotomy and permutation polynomials of large indices,” _Finite Fields and Their Applications_ , vol. 22, pp. 57–69, 2013.
  * [52] Y. H. Park and J. B. Lee, “Permutation polynomials and group permutation polynomials,” _Bulletin of the Australian Mathematical Society_ , vol. 63, no. 1, pp. 67–74, 2001.
  * [53] Q. Wang, “Cyclotomic mapping permutation polynomials over finite fields,” in _Sequences, Subsequences, and Consequences_. Springer, 2007, pp. 119–128.
  * [54] M. E. Zieve, “On some permutation polynomials over ${\mathbb{F}}_{q}$ of the form $x^{r}h(x^{(q-1)/d})$,” _Proceedings of the American Mathematical Society_ , pp. 2209–2216, 2009.
  * [55] Q. Wang, “On inverse permutation polynomials,” _Finite Fields and Their Applications_ , vol. 15, pp. 207–213, 2009.
  * [56] Y. Zheng, Y. Yu, Y. Zhang, and D. Pei, “Piecewise constructions of inverses of cyclotomic mapping permutation polynomials,” _Finite Fields and Their Applications_ , vol. 40, pp. 1–9, 2016.
  * [57] M. Zieve, “On some permutation polynomials over $\mathbb{F}_{q}$ of the form $x^{r}h(x^{(q-1)/d})$,” _Proceedings of the American Mathematical Society_ , vol. 137, no. 7, pp. 2209–2216, 2009.
  * [58] A. Akbary and Q. Wang, “On polynomials of the form $x^{r}h(x^{(q-1)/l})$,” p. 023408, Jan. 2008.
  * [59] R. Lidl and H. Niederreiter, _Finite fields_. Cambridge university press, 1997, vol. 20.
  * [60] J. E. Marcos, “Specific permutation polynomials over finite fields,” _Finite Fields and Their Applications_ , vol. 17, no. 2, pp. 105–112, 2011\.
  * [61] P. Charpin and G. Kyureghyan, “When does ${G}(x)+\gamma{\rm Tr}({H}(x))$ permute ${\mathbb{F}}_{p^{n}}$,” _Finite Fields and Their Applications_ , vol. 15, no. 5, pp. 615–632, 2009.