On many-to-one mappings over finite fields

Yanbin Zheng [email protected] Yanjin Ding Meiying Zhang Pingzhi Yuan [email protected] Qiang Wang [email protected] School of Mathematical Sciences, Qufu Normal University, Qufu 273165, China School of of Mathematical Science, South China Normal University, Guangzhou 510631, China School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, ON K1S 5B6, Canada
In Memory of Professor Dingyi Pei (1941–2023)

Abstract

The definition of many-to-one mapping, or $m$ -to- $1$ mapping for short, between two finite sets is introduced in this paper, which unifies and generalizes the definitions of $2$ -to- $1$ mappings and $n$ -to- $1$ mappings. A generalized local criterion is given, which is an abstract criterion for a mapping to be $m$ -to- $1$ . By employing the generalized local criterion, three constructions of $m$ -to- $1$ mapping are proposed, which unify and generalize all the previous constructions of $2$ -to- $1$ mappings and $n$ -to- $1$ mappings. Then the $m$ -to- $1$ property of polynomials $f(x)=x^{r}h(x^{s})$ on $\mathbb{F}_{q}^{*}$ is studied by using these three constructions. A series of explicit conditions for $f$ to be an $m$ -to- $1$ mapping on $\mathbb{F}_{q}^{*}$ are found through the detailed discussion of the parameters $m$ , $s$ , $q$ and the polynomial $h$ . These results extend many conclusions in the literature.

keywords:

Permutations , Two-to-one mappings , Many-to-one mappings

MSC:

[2010] 11T06 , 11T71

^†^†journal: XXX^t1^t1footnotetext: This work was partially supported by the Natural Science Foundation of Shandong (No. ZR2021MA061), the National Natural Science Foundation of China (No. 62072222), and NSERC of Canada (RGPIN-2023-04673).

1 Introdution

One-to-one mappings from a finite field $\mathbb{F}_{q}$ to itself (i.e., permutations of $\mathbb{F}_{q}$ ) have been extensively studied; see for example [28, 34, 18, 41, 42, 48] and the references therein. We now briefly review the progress of many-to-one mapping from $\mathbb{F}_{q}$ to itself.

1.1 The progress of many-to-one mapping

Assume $A$ and $B$ are finite sets and $f$ is a mapping from $A$ to $B$ . For any $b\in B$ , let $\#f^{-1}(b)$ denote the number of preimages of $b$ in $A$ under $f$ .

Refer to caption — Figure 1: Schematic diagrams of many-to-one mappings

In 2019, Mesnager and Qu [30] introduced the definition of $2$ -to- $1$ mappings: $f$ is called $2$ -to- $1$ if $\#f^{-1}(b)\in\{0,2\}$ for each $b\in B$ , except for at most a single $b^{\prime}\in B$ for which $\#f^{-1}(b^{\prime})=1$ ; see the first column of Fig. 1. They provided a systematic study of $2$ -to- $1$ mappings over finite fields. They presented several constructions of $2$ -to- $1$ mappings from an AGW-like criterion (see Fig. 8), from permutation polynomials, from linear translators, and from APN functions. They also listed several classical types of known $2$ -to- $1$ polynomial mappings, including linearized polynomials [7], Dickson polynomials, Muller-Cohen-Matthews polynomials, etc. Moreover, all $2$ -to- $1$ polynomials of degree $\leq 4$ over any finite field were determined in [30]. In 2021, all $2$ -to- $1$ polynomials of degree 5 over $\mathbb{F}_{2^{n}}$ were completely determined by using the Hasse-Weil bound, and some $2$ -to- $1$ mappings with few terms, mainly trinomials and quadrinomials, over $\mathbb{F}_{2^{n}}$ were also given in [26]. In the same year, a new AGW-like criterion (see Fig. 8) for $2$ -to- $1$ mappings was given in [44]. Using this criterion, some new constructions of $2$ -to- $1$ mappings were proposed and eight classes of $2$ -to- $1$ mappings of the form $(x^{2^{k}}+x+\delta)^{s}+cx$ over $\mathbb{F}_{2^{n}}$ were obtained. In 2023, some classes of $2$ -to- $1$ mappings of the form $x^{r}+x^{s}+x^{t}+x^{3}+x^{2}+x$ , $(x^{2^{k}}+x+\delta)^{s_{1}}+(x^{2^{k}}+x+\delta)^{s_{2}}+cx$ , or $h(x)\circ(x^{2^{e}}+x)$ over $\mathbb{F}_{2^{n}}$ were proposed in [33], where $(e,n)=1$ and $h$ is $1$ -to- $1$ on the image set of $x^{2^{e}}+x$ . Very recently, Kölsch and Kyureghyan [22] observed that on $\mathbb{F}_{2^{n}}$ the classification of $2$ -to- $1$ binomials is equivalent to the classification of o-monomials, which is a well-studied and elusive problem in finite geometry. They also provided some connections between $2$ -to- $1$ maps and hyperovals in non-desarguesian planes.

The $2$ -to- $1$ mappings over $\mathbb{F}_{q}$ play an important role in cryptography and coding theory. Such mappings are used in [30] to construct bent functions, semi-bent functions, planar functions, and permutation polynomials. Moreover, they are also used to construct linear codes [9, 10, 25, 31, 32], involutions over $\mathbb{F}_{2^{n}}$ [44, 33], and (almost) perfect $c$ -nonlinear functions [17, 43].

In 2021, the concept of $2$ -to- $1$ mappings was generalized in [15] to $n$ -to- $1$ mappings when $\#A\equiv 0,1\pmod{n}$ . Specifically, $f$ is called a $n$ -to- $1$ mapping if $\#f^{-1}(b)\in\{0,n\}$ for each $b\in B$ , except for at most a single $b^{\prime}\in B$ for which $\#f^{-1}(b^{\prime})=1$ ; see the second column of Fig. 1.

Later, a more general definition of $n$ -to- $1$ mappings was introduced in [6] (on finite field $A$ ) and independently in [35] (on finite set $A$ ), which allows $\#A\bmod{n}\in\{0,1,\ldots,n-1\}$ . Specifically, $f$ is called a $n$ -to- $1$ mapping if $\#f^{-1}(b)\in\{0,n\}$ for each $b\in B$ , except for at most a single $b^{\prime}\in B$ for which $\#f^{-1}(b^{\prime})=r$ , where $r=\#A\bmod n$ ; see the third column of Fig. 1. In particular, $f$ maps the remaining $r$ elements in $A$ to the same image $b^{\prime}$ if $r\neq 0$ . Under this definition, a new method to obtain $n$ -to- $1$ mappings based on Galois groups of rational functions was proposed, and two explicit classes of $2$ -to- $1$ and $3$ -to- $1$ rational functions over finite fields were given in [6]. The main result of [6] was refined and generalized by Ding and Zieve [13]. Under this definition, all $3$ -to- $1$ polynomials of degree $\leq 4$ over finite fields were determined in [35]. Moreover, an AGW-like criterion (see Fig. 8) for characterizing $n$ -to- $1$ mappings was presented in [35], and this criterion was applied to polynomials of the forms $h(\psi(x))\phi(x)+g(\psi(x))$ , $L_{1}(x)+L_{2}(x)g(L_{3}(x))$ , $x^{r}h(x^{s})$ , and $g(x^{q^{k}}-x+\delta)+cx$ over finite fields. In particular, some explicit $n$ -to- $1$ mappings were provided.

The definition of $n$ -to- $1$ in [6, 35] requires that $f$ maps the remaining $r$ elements in $A$ to the same image $b^{\prime}$ if $r\neq 0$ . In this paper, we introduce a more general definition which allows the number of images of the remaining $r$ elements in $A$ to be any integer in $\{1,2,\ldots,r\}$ if $r\neq 0$ ; see the fourth column of Fig. 1.

Definition 1.1.

Let $A$ be a finite set and $m\in\mathbb{Z}$ with $1\leq m\leq\#A$ . Write $\#A=km+r$ , where $k$ , $r\in\mathbb{Z}$ with $0\leq r<m$ . Let $f$ be a mapping from $A$ to another finite set $B$ . Then $f$ is called many-to-one, or $m$ -to- $1$ for short, on $A$ if there are $k$ distinct elements in $B$ such that each element has exactly $m$ preimages in $A$ under $f$ . The remaining $r$ elements in $A$ are called the exceptional elements of $f$ on $A$ , and the set of these $r$ exceptional elements is called the exceptional set of $f$ on $A$ and denoted by $E_{f}(A)$ . In particular, $E_{f}(A)=\varnothing$ if and only if $r=0$ , i.e., $m\mid\#A$ .

In the case $r=0$ or $r\neq 0$ and $\#f(E_{f}(A))=1$ , Definition 1.1 is the same as the definitions in [30, 15, 6, 35]. In other cases, Definition 1.1 is a generalization of the definitions mentioned above. Throughout this paper, we use Definition 1.1 in all of our results. Moreover, it should be noted that $f$ is $1$ -to- $1$ on $A$ means that $f$ is $1$ -to- $1$ from $A$ to $f(A)$ , where $f(A)$ may not equal $A$ . If $f$ is $m$ -to- $1$ on $A$ , then any $b\in f(A)$ has at most $m$ preimages in $A$ under $f$ .

Definition 1.2.

A polynomial $f(x)\in\mathbb{F}_{q}[x]$ is called many-to-one, or $m$ -to- $1$ for short, on $\mathbb{F}_{q}$ if the mapping $f\colon c\mapsto f(c)$ from $\mathbb{F}_{q}$ to itself is $m$ -to- $1$ on $\mathbb{F}_{q}$ .

Example 1.1.

Let $f(x)=x^{3}+x$ . Then $f$ maps $0,1,2,3,4$ to $0,2,0,0,3$ in $\mathbb{F}_{5}$ , respectively. Thus $f$ is $3$ -to- $1$ on $\mathbb{F}_{5}$ and the exceptional set $E_{f}(\mathbb{F}_{5})=\{1,4\}$ .

Example 1.2.

The monomial $x^{n}$ with $n\in\mathbb{N}$ is $(n,q-1)$ -to- $1$ on $\mathbb{F}_{q}^{*}$ and $E_{x^{n}}(\mathbb{F}_{q}^{*})=\varnothing$ .

The next example is a generalization of Example 1.2.

Example 1.3.

Let $f$ be an endomorphism of a finite group $G$ and $\ker(f)=\{x\in G:f(x)=e\}$ , where $e$ is the identity of $G$ . It is easy to verify that $\{x\in G:f(x)=f(a)\}=a\ker(f)$ for any $a\in G$ . Hence $f$ is $m$ -to- $1$ on $G$ and $E_{f}(G)=\varnothing$ , where $m=\#\ker(f)$ .

1.2 The constructions of many-to-one mappings

In this subsection, we will take an in-depth look at the constructions based on commutative diagrams of many-to-one mappings.

Inspired by the work of Marcos [29] and Zieve [50], the following construction of $1$ -to- $1$ mappings was presented by Akbary, Ghioca, and Wang [2] in 2011, which is often referred to as the AGW criterion.

Theorem 1.1 (The AGW criterion).

Let $A$ , $S$ , and $\bar{S}$ be finite sets with $\#S=\#\bar{S}$ , and let $f:A\rightarrow A$ , $\bar{f}:S\rightarrow\bar{S}$ , $\lambda:A\rightarrow S$ , and $\bar{\lambda}:A\rightarrow\bar{S}$ be mappings such that $\bar{\lambda}\circ f=\bar{f}\circ\lambda$ . If both $\lambda$ and $\bar{\lambda}$ are surjective, then the following statements are equivalent:

\edefitn(1)

$f$ is $1$ -to- $1$ from $A$ to $A$ (permutes $A$ ).
\edefitn(2)

$\bar{f}$ is $1$ -to- $1$ from $S$ to $\bar{S}$ and $f$ is $1$ -to- $1$ on $\lambda^{-1}(s)$ for each $s\in S$ .

The AGW criterion can be illustrated by Fig. 2. It gives us a recipe in which under suitable conditions one can construct permutations of $A$ from $1$ -to- $1$ mappings between two smaller sets $S$ and $\bar{S}$ .

Figure 2: Commutative diagram of the AGW criterion

In recent years, the AGW criterion had been generalized to construct $2$ -to- $1$ and $n$ -to- $1$ mappings in [30, 15, 35, 44]. The main ideas can be illustrated by Figs. 8, 8, 8 and 8. All these constructions have the same assumption: $A$ , $\bar{A}$ , $S$ , and $\bar{S}$ are finite sets, and $f:A\rightarrow A$ or $\bar{A}$ , $\bar{f}:S\rightarrow\bar{S}$ , $\lambda:A\rightarrow S$ , and $\bar{\lambda}:A\rightarrow\bar{S}$ are mappings such that $\bar{\lambda}\circ f=\bar{f}\circ\lambda$ . We now review these constructions.

Figure 3:

2

-to-

1

in [30]

Figure 4:

n

-to-

1

in [15]

Figure 5: Our Construction 1

Figure 6:

2

-to-

1

in [44]

Figure 7:

n

-to-

1

in [35]

Figure 8: Our Construction 2

•

[30, Proposition 6] states that, if $\#S=\#\bar{S}$ , $\bar{f}$ is $1$ -to- $1$ from $S$ to $\bar{S}$ , $f|_{\lambda^{-1}(s)}$ is $2$ -to- $1$ for any $s\in S$ , and there is at most one $s\in S$ such that $\#\lambda^{-1}(s)$ is odd, then $f$ is $2$ -to- $1$ on $A$ .
•

[15, Proposition 1] states that, if $\#A\equiv 0,1\pmod{n}$ , $\#S=\#\bar{S}$ , $\bar{f}$ is $1$ -to- $1$ from $S$ to $\bar{S}$ , $f|_{\lambda^{-1}(s)}$ is $n$ -to- $1$ for any $s\in S$ , and there is at most one $s\in S$ such that $\#\lambda^{-1}(s)\equiv 1\pmod{m}$ , then $f$ is $n$ -to- $1$ on $A$ .
•

[44, Proposition 4.2] states that, if $f$ , $\bar{f}$ , $\lambda$ , $\bar{\lambda}$ are surjective, $f$ is $1$ -to- $1$ from $\lambda^{-1}(s)$ to $\bar{\lambda}^{-1}(\bar{f}(s))$ for any $s\in S$ , $\#S$ is even, and $\bar{f}$ is $2$ -to- $1$ from $S$ to $\bar{S}$ , then $f$ is $2$ -to- $1$ on $A$ .
•

[35, Theorem 4.3] assumes that $\lambda$ and $\bar{\lambda}$ are surjective, $\#S=\#\bar{S}$ , $\#A\equiv\#S\pmod{n}$ , $f$ is $1$ -to- $1$ from $\lambda^{-1}(s)$ to $\bar{\lambda}^{-1}(\bar{f}(s))$ for any $s\in S$ . When $n\mid\#S$ , $f$ is $n$ -to- $1$ on $A$ if and only if $\bar{f}$ is $n$ -to- $1$ on $S$ . When $n\nmid\#S$ , [35, Theorem 4.3] does not give a necessary and sufficient condition for $f$ to be $n$ -to- $1$ on $A$ .

Very recently, the local criterion for a mapping to be a permutation of $A$ was provided by Yuan [45], which is equivalent to the AGW criterion.

Theorem 1.2 (Local criterion [45]).

Let $A$ and $S$ be finite sets and let $f:A\rightarrow A$ be a map. Then $f$ is a bijection if and only if for any surjection $\psi:A\rightarrow S$ , $\varphi=\psi\circ f$ is a surjection and $f$ is injective on $\varphi^{-1}(s)$ for each $s\in S$ .

In this paper, we present a generalized local criterion for a mapping to be $m$ -to- $1$ on $A$ ; see Lemma 3.1. By employing the generalized local criterion, three constructions of $m$ -to- $1$ mapping are proposed. The first two structures an be illustrated by Figs. 8 and 8, and they unify and generalize all the constructions of $2$ -to- $1$ and $n$ -to- $1$ mappings in [30, 15, 35, 44]. We next give a detailed analysis.

•

The restrictions $\#S=\#\bar{S}$ and $\#A\equiv 0,1\pmod{n}$ in [30, 15] are redundant. A necessary and sufficient condition for $f$ to be $m$ -to- $1$ on $A$ is given in our Construction 1 without the restrictions above. Specifically, if $\bar{f}$ is $1$ -to- $1$ on $S$ , then for $1\leq m\leq\#A$ , $f$ is $m$ -to- $1$ on $A$ if and only if $f|_{\lambda^{-1}(s)}$ is $m$ -to- $1$ for any $\#\lambda^{-1}(s)\geq m$ and an identity about exceptional sets holds. Construction 1 generalizes [30, Proposition 6] and [15, Proposition 1]; each of them only gives the sufficient condition.
•

The following conditions in [35, 44] are redundant: $f$ , $\bar{f}$ , $\bar{\lambda}$ are surjective, $\#S=\#\bar{S}$ , and $\#A\equiv\#S\pmod{n}$ . The condition $f$ is $1$ -to- $1$ from $\lambda^{-1}(s)$ to $\bar{\lambda}^{-1}(\bar{f}(s))$ in [35, 44] can be replaced by the weaker assumption $\#\lambda^{-1}(s)=m_{1}\,\#\bar{\lambda}^{-1}(\bar{f}(s))$ and $f$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ for some $m_{1}\in\mathbb{N}$ . Under the weaker assumption, our Construction 2 gives a necessary and sufficient condition for $f$ to be $m$ -to- $1$ on $A$ . Specifically, if $\lambda$ is surjective and the weaker assumption holds, then for $1\leq m\leq m_{1}\,\#S$ , $f$ is $m$ -to- $1$ on $A$ if and only if $m_{1}\mid m$ , $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $S$ , and an identity about exceptional sets holds. Construction 2 generalizes [44, Proposition 4.2] and [35, Theorem 4.3].

1.3 The organization of the paper

Section 2 introduces some properties of $m$ -to- $1$ mappings on finite sets. Section 3 presents a generalized local criterion, which characterizes an abstract necessary and sufficient condition of $m$ -to- $1$ mapping. Then three constructions of $m$ -to- $1$ mapping are proposed by employing the generalized local criterion. The first construction reduces the problem whether $f$ is an $m$ -to- $1$ mapping on a finite set $A$ to a relatively simple problem whether $f$ is an $m$ -to- $1$ mapping on some subsets of $A$ . The second one converts the problem whether $f$ is an $m$ -to- $1$ mapping on $A$ into another problem whether an associated mapping $\bar{f}$ is $m_{2}$ -to- $1$ on a finite set $S$ , where $m_{2}\mid m$ . These two constructions unify and generalize all the previous constructions of $2$ -to- $1$ mappings and $n$ -to- $1$ mappings in the literature. The third construction reduces the problem whether $f\ast u$ is an $m$ -to- $1$ mapping on a finite group $A$ to that whether $f$ is an $m$ -to- $1$ mapping on $A$ . In Section 4, by using the second construction, the problem whether $f(x)\coloneq x^{r}h(x^{s})$ is $m$ -to- $1$ on the multiplicative group $\mathbb{F}_{q}^{*}$ is converted into another problem whether $g(x)\coloneq x^{r_{1}}h(x)^{s_{1}}$ is $m_{2}$ -to- $1$ on the multiplicative subgroup $U_{\ell}$ , where $\ell=(q-1)/s$ . Then, the $m_{2}$ -to- $1$ property of $g$ on $U_{\ell}$ is discussed from five aspects: (1) $m=2,3$ ; (2) $\ell=2,3$ ; (3) $g$ behaves like a monomial on $U_{\ell}$ ; (4) $g$ behaves like a rational function on $U_{\ell}$ ; (5) $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ is converted into that an associated mapping $\bar{g}$ is $m_{3}$ -to- $1$ on a finite set $\lambda(U_{\ell})$ by using the second construction again.

1.4 Notations

The letter $\mathbb{Z}$ will denote the set of all integers, $\mathbb{N}$ the set of all positive integers, $\#S$ the cardinality of a finite set $S$ , and $\varnothing$ the empty set containing no elements. The greatest common divisor of two integers $a$ and $b$ is written as $(a,b)$ . Denote $a\bmod m$ as the smallest non-negative remainder obtained when $a$ is divided by $m$ . That is, $\mathrm{mod}~{}m$ is a function from the set of integers to the set of $\{0,1,2,\ldots,m-1\}$ . For a prime power $q$ , let $\mathbb{F}_{q}$ denote the finite field with $q$ elements, $\mathbb{F}_{q}^{*}=\mathbb{F}_{q}\setminus\{0\}$ , and $\mathbb{F}_{q}[x]$ the ring of polynomials over $\mathbb{F}_{q}$ . Denote $U_{\ell}$ as the cyclic group of all $\ell$ -th roots of unity over $\mathbb{F}_{q}$ , i.e., $U_{\ell}=\{\alpha\in\mathbb{F}_{q}^{*}:\alpha^{\ell}=1\}$ . The trace function from $\mathbb{F}_{q^{n}}$ to $\mathbb{F}_{q}$ is defined by $\mathrm{Tr}_{q^{n}/q}(x)=\sum_{i=0}^{n-1}x^{q^{i}}$ .

2 Some properties of $m$ -to- $1$ mappings

We first calculate the number of all $m$ -to- $1$ mappings on $\mathbb{F}_{q}$ .

Theorem 2.1.

Let $q=km+r$ , where $1\leq m\leq q$ and $0\leq r<m$ . Denote by $N_{m}$ the number of all $m$ -to- $1$ mappings from $\mathbb{F}_{q}$ to itself. Then

N_{m}=\frac{(q!)^{2}\,(q-k)^{r}}{k!\,r!\,(m!)^{k}(q-k)!}.

Proof.

For any $m$ -to- $1$ mapping $f$ on $\mathbb{F}_{q}$ , by $q=km+r$ , we get $\#E_{f}(\mathbb{F}_{q})=r$ and $\#f(\mathbb{F}_{q}\setminus E_{f}(\mathbb{F}_{q}))=k$ . Then $f(\mathbb{F}_{q}\setminus E_{f}(\mathbb{F}_{q}))$ has $\binom{q}{k}$ choices. For the first element in $f(\mathbb{F}_{q}\setminus E_{f}(\mathbb{F}_{q}))$ , its preimage has $\binom{q}{m}$ choices. For the second elements, its preimage has $\binom{q-m}{m}$ choices, …, the last element has $\binom{m+r}{m}$ choices. Moreover, the image of each element in $E_{f}(\mathbb{F}_{q})$ has $q-k$ choices. Hence

	$\displaystyle N_{m}$	$\displaystyle=\binom{q}{k}\binom{q}{m}\binom{q-m}{m}\cdots\binom{m+r}{m}(q-k)^{r}$
		$\displaystyle=\binom{q}{k}\frac{q!\,(q-k)^{r}}{r!\,(m!)^{k}}.\qed$

We next consider some $m$ -to- $1$ properties of composition of mappings.

Theorem 2.2.

Let $\varphi$ be a mapping from $A$ to $B$ and let $\sigma$ be a $1$ -to- $1$ mapping from $B$ to $C$ , where $A$ , $B$ , $C$ are finite sets. Then, for $1\leq m\leq\#A$ , the composition $\sigma\circ\varphi$ is $m$ -to- $1$ on $A$ if and only if $\varphi$ is $m$ -to- $1$ on $A$ .

Proof.

Let $\#A=km+r$ with $0\leq r<m$ . The sufficiency follows from Definition 1.1. Conversely, if $\sigma\circ\varphi$ is $m$ -to- $1$ on $A$ , then there are $k$ distinct elements $c_{1}$ , $c_{2}$ , …, $c_{k}\in C$ such that each $c_{i}$ has exactly $m$ preimages in $A$ , say,

\sigma(\varphi(a_{i1}))=\sigma(\varphi(a_{i2}))=\cdots=\sigma(\varphi(a_{im}))=c_{i}\quad\text{with}\quad a_{ij}\in A.

Since $\sigma$ is $1$ -to- $1$ from $B$ to $C$ , there exists unique $b_{i}\in B$ such that $\sigma(b_{i})=c_{i}$ for any $c_{i}$ , and so

\varphi(a_{i1})=\varphi(a_{i2})=\cdots=\varphi(a_{im})=b_{i}\quad\text{for any}\quad 1\leq i\leq k,

that is, $\varphi$ is $m$ -to- $1$ on $A$ . ∎

Theorem 2.3.

Let $\lambda\colon A\to B$ and $\theta\colon B\to C$ be mappings such that $\#A=m_{1}\,\#B$ and $\lambda$ is $m_{1}$ -to- $1$ on $A$ , where $A$ , $B$ , $C$ are finite sets and $m_{1}\in\mathbb{N}$ . Then, for $1\leq m\leq\#A$ , the composition $\theta\circ\lambda$ is $m$ -to- $1$ on $A$ if and only if $m_{1}\mid m$ and $\theta$ is $(m/m_{1})$ -to- $1$ on $B$ .

Proof.

Let $\#A=km+r$ with $0\leq r<m$ and let $\#B=\#A/m_{1}=k(m/m_{1})+(r/m_{1})$ if $m_{1}\mid m$ . Since $\#A=m_{1}\,\#B$ and $\lambda$ is $m_{1}$ -to- $1$ on $A$ , each element in $B$ has $m_{1}$ preimages in $A$ under $\lambda$ . Hence the following statements are equivalent:

(a)

$\theta\circ\lambda$ is $m$ -to- $1$ on $A$ ;
(b)

There are $k$ distinct elements in $C$ such that each element has exactly $m$ preimages in $A$ under $\theta\circ\lambda$ ;
(c)

$m_{1}\mid m$ and there are $k$ distinct elements in $C$ such that each element has exactly $m/m_{1}$ preimages in $B$ under $\theta$ ;
(d)

$m_{1}\mid m$ and $\theta$ is $(m/m_{1})$ -to- $1$ on $B$ . ∎

When $m_{1}=1$ , Theorem 2.3 reduces to the following form.

Corollary 2.4.

Let $\lambda$ be a $1$ -to- $1$ mapping from $A$ to $B$ and $\theta$ be a mapping from $B$ to $C$ , where $A$ , $B$ , $C$ are finite sets and $\#A=\#B$ . Then, for $1\leq m\leq\#A$ , the composition $\theta\circ\lambda$ is $m$ -to- $1$ on $A$ if and only if $\theta$ is $m$ -to- $1$ on $B$ .

Combining Theorem 2.2 and Corollary 2.4 yields the next result.

Corollary 2.5.

Let $f$ be a mapping from a finite set $A$ to its subset $B$ . Suppose $\sigma_{1}$ and $\sigma_{2}$ permute $A$ . Then the composition $\sigma_{2}\circ f\circ\sigma_{1}$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $A$ .

That is, a composition of permutations and $f$ preserves the $m$ -to- $1$ property of $f$ , which is an intuitive result. Combining Corollary 2.5 and Example 1.2 yields the following example.

Example 2.1.

Let $\sigma\in\mathbb{F}_{q}[x]$ permute $\mathbb{F}_{q}^{*}$ and $n\in\mathbb{N}$ . Then $\sigma(x^{n})$ is $(n,q-1)$ -to- $1$ on $\mathbb{F}_{q}^{*}$ .

This result builds a link between permutations and $m$ -to- $1$ mappings.

3 Three constructions for $m$ -to- $1$ mappings

Lemma 2.1 in [45] gives the local criterion for a mapping to be a permutation of $A$ . We now present a generalization of it for a mapping to be $m$ -to- $1$ on $A$ .

Lemma 3.1 (Generalized local criterion).

Let $A$ , $B$ , and $C$ be finite sets. Let $f:A\to B$ , $\psi:B\to C$ , and $\varphi:A\to C$ be mappings such that $\varphi=\psi\circ f$ , i.e., the following diagram is commutative:

For any $c\in\varphi(A)$ , let $\varphi^{-1}(c)=\{a\in A:\varphi(a)=c\}$ . Then, for $1\leq m\leq\#A$ , $f$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $\varphi^{-1}(c)$ for any $\#\varphi^{-1}(c)\geq m$ and

\sum_{\#\varphi^{-1}(c)\geq m}\#E_{f}(\varphi^{-1}(c))+\sum_{\#\varphi^{-1}(c)<m}\#\varphi^{-1}(c)=\#A\bmod{m},

(3.1)

where $c$ runs through $\varphi(A)$ and $E_{f}(\varphi^{-1}(c))$ is the exceptional set of $f$ being $m$ -to- $1$ on $\varphi^{-1}(c)$ .

Proof.

Assume that $\varphi(A)=\{c_{1},c_{2},\ldots,c_{n}\}$ . Then

A=\varphi^{-1}(c_{1})\uplus\varphi^{-1}(c_{2})\uplus\cdots\uplus\varphi^{-1}(c_{n}),

where $\uplus$ denote the union of disjoint sets. Thus

f(A)=f(\varphi^{-1}(c_{1}))\cup f(\varphi^{-1}(c_{2}))\cup\cdots\cup f(\varphi^{-1}(c_{n})).

By $\varphi=\psi\circ f$ , we have $\psi(f(\varphi^{-1}(c_{i})))=\varphi(\varphi^{-1}(c_{i}))=c_{i}$ , and so

f(\varphi^{-1}(c_{i}))\subseteq\psi^{-1}(c_{i}).

If $c_{i}\neq c_{j}$ , then $\psi^{-1}(c_{i})\cap\psi^{-1}(c_{j})=\varnothing$ , and so $f(\varphi^{-1}(c_{i}))\cap f(\varphi^{-1}(c_{j}))=\varnothing$ . Hence

f(A)=f(\varphi^{-1}(c_{1}))\uplus f(\varphi^{-1}(c_{2}))\uplus\cdots\uplus f(\varphi^{-1}(c_{n})).

(3.2)

Let $\#A=km+r$ , where $0\leq r<m$ . ( $\Leftarrow$ ) Assume $f$ is $m$ -to- $1$ on $\varphi^{-1}(c_{i})$ for any $\#\varphi^{-1}(c_{i})\geq m$ and Eq. 3.1 holds. Then there are $(\#A-r)/m=k$ distinct elements in $f(A)$ such that each element has exactly $m$ preimages in $A$ under $f$ . Hence $f$ is $m$ -to- $1$ on $A$ . ( $\Rightarrow$ ) Assume $f$ is $m$ -to- $1$ on $A$ . Then there are at most $m$ preimages in $\varphi^{-1}(c_{i})$ for any element in $f(\varphi^{-1}(c_{i}))$ and $\#E_{f}(A)=r<m$ , where $E_{f}(A)$ is the exceptional set of $f$ being $m$ -to- $1$ on $A$ . If $\#\varphi^{-1}(c_{i})\geq m$ , let $\#\varphi^{-1}(c_{i})=k_{i}m+r_{i}$ with $k_{i}\geq 1$ and $0\leq r_{i}<m$ , and let $k^{\prime}_{i}$ be the number of $b\in f(\varphi^{-1}(c_{i}))$ which has exactly $m$ preimages in $\varphi^{-1}(c_{i})$ . If $k^{\prime}_{i}<k_{i}$ , then $\#E_{f}(\varphi^{-1}(c_{i}))=\#\varphi^{-1}(c_{i})-k^{\prime}_{i}m=(k_{i}-k^{\prime}_{i})m+r_{i}\geq m$ , contrary to $\#E_{f}(A)<m$ . Thus $k^{\prime}_{i}=k_{i}$ , i.e., $f$ is $m$ -to- $1$ on $\varphi^{-1}(c_{i})$ if $\#\varphi^{-1}(c_{i})\geq m$ . If $\#\varphi^{-1}(c_{i})<m$ , then $\varphi^{-1}(c_{i})\subseteq E_{f}(A)$ by Eq. 3.2. Thus

\big{(}\underset{\#\varphi^{-1}(c)\geq m}{\uplus}E_{f}(\varphi^{-1}(c))\big{)}\uplus\big{(}\underset{\#\varphi^{-1}(c)<m}{\uplus}\varphi^{-1}(c)\big{)}=E_{f}(A)

(3.3)

and so Eq. 3.1 holds. ∎

The generalized local criterion converts the problem whether $f$ is an $m$ -to- $1$ mapping on $A$ to another problem whether $f$ is an $m$ -to- $1$ mapping on some subsets $\varphi^{-1}(c)$ of $A$ . The identities Eqs. 3.1 and 3.3 describe the relationship between the exceptional sets $E_{f}(A)$ and $E_{f}(\varphi^{-1}(c))$ . We next use this criterion to deduce three constructions of $m$ -to- $1$ mappings.

3.1 The first construction

Construction 1.

For any $s\in\lambda(A)$ , let $\lambda^{-1}(s)=\{a\in A:\lambda(a)=s\}$ . Suppose $\bar{f}$ is $1$ -to- $1$ on $S$ . Then, for $1\leq m\leq\#A$ , $f$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $\lambda^{-1}(s)$ for any $\#\lambda^{-1}(s)\geq m$ and

\sum_{\#\lambda^{-1}(s)\geq m}\#E_{f}(\lambda^{-1}(s))+\sum_{\#\lambda^{-1}(s)<m}\#\lambda^{-1}(s)=\#A\bmod{m},

where $s$ runs through $\lambda(A)$ and $E_{f}(\lambda^{-1}(s))$ is the exceptional set of $f$ being $m$ -to- $1$ on $\lambda^{-1}(s)$ .

Proof.

Let $\varphi=\bar{f}\circ\lambda$ , i.e., the following diagram is commutative:

Since $\bar{f}$ is $1$ -to- $1$ on $S$ , there is a unique $s\in\lambda(A)$ such that $\bar{f}(s)=\bar{s}$ for any $\bar{s}\in\varphi(A)=\bar{f}(\lambda(A))$ . Thus $\varphi^{-1}(\bar{s})=\lambda^{-1}(s)$ . Then the result follows from Lemma 3.1. ∎

This result is equivalent to Lemma 3.1 under the condition $\bar{f}$ is $1$ -to- $1$ on $S$ . It generalizes [30, Proposition 6] and [15, Proposition 1]; each of them only gives the sufficient conditions.

3.2 The second construction

Construction 2.

Suppose $\lambda$ is surjective, $\#\lambda^{-1}(s)=m_{1}\,\#\bar{\lambda}^{-1}(\bar{f}(s))$ , and $f$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ for any $s\in S$ and a fixed $m_{1}\in\mathbb{N}$ , where

\lambda^{-1}(s)\coloneq\{a\in A:\lambda(a)=s\}\quad\text{and}\quad\bar{\lambda}^{-1}(\bar{f}(s))\coloneq\{b\in\bar{A}:\bar{\lambda}(b)=\bar{f}(s)\}.

Then, for $1\leq m\leq m_{1}\,\#S$ , $f$ is $m$ -to- $1$ on $A$ if and only if $m_{1}\mid m$ , $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $S$ , and

\sum_{s\in E_{\bar{f}}(S)}\#\lambda^{-1}(s)=\#A\bmod{m},

(3.4)

where $E_{\bar{f}}(S)$ is the exceptional set of $\bar{f}$ being $(m/m_{1})$ -to- $1$ on $S$ .

Proof.

Since $\lambda\colon A\rightarrow S$ is surjective, we get $A=\uplus_{s\in S}\lambda^{-1}(s)$ , and so

\#A=\sum_{s\in S}\#\lambda^{-1}(s)=\sum_{s\in S}m_{1}\,\#\bar{\lambda}^{-1}(\bar{f}(s))\geq\sum_{s\in S}m_{1}=m_{1}\#S.

Thus the definitions that $f$ is $m$ -to- $1$ on $A$ and $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $S$ are meaningful when $1\leq m\leq m_{1}\,\#S$ . For any $s\in S$ , it follows from $\bar{\lambda}\circ f=\bar{f}\circ\lambda$ that

(\bar{\lambda}\circ f)(\lambda^{-1}(s))=(\bar{f}\circ\lambda)(\lambda^{-1}(s))=\bar{f}(s),

and so $f(\lambda^{-1}(s))\subseteq\bar{\lambda}^{-1}(\bar{f}(s))$ . Because $m_{1}\mid\#\lambda^{-1}(s)$ and $f$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ , we have

\#f(\lambda^{-1}(s))=\#\lambda^{-1}(s)/m_{1}=\#\bar{\lambda}^{-1}(\bar{f}(s)).

Therefore,

f(\lambda^{-1}(s))=\bar{\lambda}^{-1}(\bar{f}(s))\quad\text{for each $s\in S$.}

(3.5)

Let $\varphi=\bar{\lambda}\circ f=\bar{f}\circ\lambda$ , i.e., the following diagram is commutative:

By Lemma 3.1, $f$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $\varphi^{-1}(\bar{s})$ for any $\#\varphi^{-1}(\bar{s})\geq m$ and

\sum_{\#\varphi^{-1}(\bar{s})\geq m}\#E_{f}(\varphi^{-1}(\bar{s}))+\sum_{\#\varphi^{-1}(\bar{s})<m}\#\varphi^{-1}(\bar{s})=\#A\bmod{m},

(3.6)

where $\bar{s}$ runs through $\varphi(A)$ .

For any $\bar{s}\in\varphi(A)$ , assume there are exactly $m_{\bar{s}}$ distinct elements $s_{1},s_{2},\ldots,s_{m_{\bar{s}}}\in S$ such that

\bar{f}(s_{1})=\bar{f}(s_{2})=\cdots=\bar{f}(s_{m_{\bar{s}}})=\bar{s},

(3.7)

i.e., the set of preimages of $\bar{s}$ under $\bar{f}$ is $\bar{f}^{-1}(\bar{s})=\{s_{1},s_{2},\ldots,s_{m_{\bar{s}}}\}$ . Then by Eq. 3.5,

f(\lambda^{-1}(s_{i}))=\bar{\lambda}^{-1}(\bar{f}(s_{i}))=\bar{\lambda}^{-1}(\bar{s})

(3.8)

for any $1\leq i\leq m_{\bar{s}}$ . For any $s^{\prime}\in S\setminus\bar{f}^{-1}(\bar{s})$ , we have $\bar{f}(s^{\prime})\neq\bar{f}(s_{1})$ and so

$\displaystyle\varnothing$	$\displaystyle=\bar{\lambda}^{-1}(\bar{f}(s^{\prime}))\cap\bar{\lambda}^{-1}(\bar{f}(s_{1}))$	(3.9)
	$\displaystyle=f(\lambda^{-1}(s^{\prime}))\cap f(\lambda^{-1}(s_{1}))$
	$\displaystyle=f(\lambda^{-1}(s^{\prime}))\cap\bar{\lambda}^{-1}(\bar{s}).$

It follows from $\varphi=\bar{f}\circ\lambda$ and Eq. 3.7 that

\varphi^{-1}(\bar{s})=\lambda^{-1}(s_{1})\uplus\lambda^{-1}(s_{2})\uplus\cdots\uplus\lambda^{-1}(s_{m_{\bar{s}}}).

(3.10)

Then by Eq. 3.8,

f(\varphi^{-1}(\bar{s}))=f(\lambda^{-1}(s_{1}))\cup\cdots\cup f(\lambda^{-1}(s_{m_{\bar{s}}}))=\bar{\lambda}^{-1}(\bar{s}).

Since $A=\uplus_{s\in S}\lambda^{-1}(s)$ , $S=\bar{f}^{-1}(\bar{s})\cup(S\setminus\bar{f}^{-1}(\bar{s}))$ , and Eq. 3.9 holds, it follows that the preimage set of $\bar{\lambda}^{-1}(\bar{s})$ under $f$ is $\varphi^{-1}(\bar{s})$ . Because

\#\lambda^{-1}(s_{i})=m_{1}\#\bar{\lambda}^{-1}(\bar{f}(s_{i}))=m_{1}\#\bar{\lambda}^{-1}(\bar{s})

(3.11)

and $f$ is $m_{1}$ -to- $1$ from $\lambda^{-1}(s_{i})$ to $f(\lambda^{-1}(s_{i}))=\bar{\lambda}^{-1}(\bar{f}(s_{i}))=\bar{\lambda}^{-1}(\bar{s})$ for $1\leq i\leq m_{\bar{s}}$ , we get

\#\varphi^{-1}(\bar{s})=m_{1}m_{\bar{s}}\#\bar{\lambda}^{-1}(\bar{s})\text{~{}~{}and $f$ is $m_{1}m_{\bar{s}}$-to-$1$ from $\varphi^{-1}(\bar{s})$ onto $\bar{\lambda}^{-1}(\bar{s})$. }

(3.12)

We first prove the sufficiency. Suppose that $m_{1}\mid m$ , $\bar{f}$ is $m_{2}$ -to- $1$ on $S$ , and Eq. 3.4 holds, where $m_{2}=m/m_{1}$ . Define

B_{1}=\{\bar{f}(s):s\in S\setminus E_{\bar{f}}(S)\}\quad\text{and}\quad B_{2}=\{\bar{f}(s):s\in E_{\bar{f}}(S)\}.

Then $\varphi(A)=B_{1}\uplus B_{2}$ . When $\bar{s}\in B_{1}$ , since $\bar{f}$ is $m_{2}$ -to- $1$ on $S$ , we have $\#\bar{f}^{-1}(\bar{s})=m_{2}$ . By Eq. 3.12,

\#\varphi^{-1}(\bar{s})=m_{1}m_{2}\#\bar{\lambda}^{-1}(\bar{s})=m\#\bar{\lambda}^{-1}(\bar{s})\geq m

(3.13)

and $f$ is $m$ -to- $1$ from $\varphi^{-1}(\bar{s})$ onto $\bar{\lambda}^{-1}(\bar{s})$ . Thus

\sum_{\bar{s}\in B_{1}}\#E_{f}(\varphi^{-1}(\bar{s}))=0.

(3.14)

When $\bar{s}\in B_{2}$ , we get $E_{\bar{f}}(S)=\uplus_{\bar{s}\in B_{2}}\bar{f}^{-1}(\bar{s})$ . Then by Eq. 3.10 and Eq. 3.4,

\sum_{\bar{s}\in B_{2}}\#\varphi^{-1}(\bar{s})=\sum_{\bar{s}\in B_{2}}\sum_{s_{i}\in\bar{f}^{-1}(\bar{s})}\#\lambda^{-1}(s_{i})=\sum_{s_{i}\in E_{\bar{f}}(S)}\#\lambda^{-1}(s_{i})=\#A\bmod{m}<m.

(3.15)

The equations Eq. 3.13, Eq. 3.14, and Eq. 3.15 imply Eq. 3.6. Then the sufficiency follows from Lemma 3.1.

We next prove the necessity. Suppose $f$ is $m$ -to- $1$ on $A$ and define

C_{1}=\{\bar{s}\in\varphi(A):\#\varphi^{-1}(\bar{s})\geq m\}\quad\text{and}\quad C_{2}=\{\bar{s}\in\varphi(A):\#\varphi^{-1}(\bar{s})<m\}.

Then $\varphi(A)=C_{1}\uplus C_{2}$ and $S=\uplus_{\bar{s}\in\varphi(A)}\bar{f}^{-1}(\bar{s})$ . When $\bar{s}\in C_{1}$ , by Lemma 3.1 and Eq. 3.12, we obtain some equivalent statements: (a) $f$ is $m$ -to- $1$ on $\varphi^{-1}(\bar{s})$ ; (b) $m=m_{1}m_{\bar{s}}$ ; (c) $m_{1}\mid m$ and $m_{\bar{s}}=m/m_{1}$ ; (d) $m_{1}\mid m$ and $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $\bar{f}^{-1}(\bar{s})$ . Also note that $\#\varphi^{-1}(\bar{s})=m\#\bar{\lambda}^{-1}(\bar{s})$ . Thus

\sum_{\bar{s}\in C_{1}}\#E_{f}(\varphi^{-1}(\bar{s}))=0.

(3.16)

Then Eq. 3.6 minus Eq. 3.16 gives

\sum_{\bar{s}\in C_{2}}\#\varphi^{-1}(\bar{s})=r\quad\text{i.e.,}\quad\sum_{\bar{s}\in C_{2}}m_{1}\#\bar{f}^{-1}(\bar{s})\#\bar{\lambda}^{-1}(\bar{s})=r

(3.17)

by Eq. 3.12, where $r=\#A\bmod m<m$ . Hence

\sum_{\bar{s}\in C_{2}}\#\bar{f}^{-1}(\bar{s})\leq r/m_{1}<m/m_{1}.

(3.18)

Combining (d) and Eq. 3.18 yields that $m_{1}\mid m$ , $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $\uplus_{\bar{s}\in\varphi(A)}\bar{f}^{-1}(\bar{s})=S$ , and $E_{\bar{f}}(S)=\uplus_{\bar{s}\in C_{2}}\bar{f}^{-1}(\bar{s})$ . By Eq. 3.11 and Eq. 3.17, we have

\displaystyle r=\sum_{\bar{s}\in C_{2}}\#\bar{f}^{-1}(\bar{s})\#\lambda^{-1}(s_{i})=\sum_{\bar{s}\in C_{2}}\sum_{s_{i}\in\bar{f}^{-1}(\bar{s})}\#\lambda^{-1}(s_{i})=\sum_{s_{i}\in E_{\bar{f}}(S)}\#\lambda^{-1}(s_{i}).

That is, Eq. 3.4 holds. ∎

The identity Eq. 3.5 plays an important role in the proof above. Using this identity, the fact that $f$ is $m$ -to- $1$ on $A$ is divided into two parts: $f$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ and $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $S$ . When the first part holds, the problem whether $f$ is $m$ -to- $1$ on $A$ is converted into that whether $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $S$ . In particular, if $\bar{\lambda}(x)=x$ , then Construction 2 reduces to Theorem 2.3.

The significance of Construction 2 resides in the fact that it not only unifies and generalizes the constructions in [44, 35] but also facilitates numerous new discoveries in this paper.

Applying Construction 2 to $m_{1}=1$ or $m\mid m_{1}\,\#S$ yields the following results.

Corollary 3.2.

Let $A$ , $\bar{A}$ , $S$ , $\bar{S}$ be finite sets and $f\colon A\rightarrow\bar{A}$ , $\bar{f}\colon S\rightarrow\bar{S}$ , $\lambda\colon A\rightarrow S$ , $\bar{\lambda}\colon\bar{A}\rightarrow\bar{S}$ be mappings such that $\bar{\lambda}\circ f=\bar{f}\circ\lambda$ . Suppose $\lambda$ is surjective, $\#\lambda^{-1}(s)=\#\bar{\lambda}^{-1}(\bar{f}(s))$ , and $f$ is $1$ -to- $1$ on $\lambda^{-1}(s)$ for any $s\in S$ . Then, for $1\leq m\leq\#S$ , $f$ is $m$ -to- $1$ on $A$ if and only if $\bar{f}$ is $m$ -to- $1$ on $S$ and $\sum_{s\in E_{\bar{f}}(S)}\#\lambda^{-1}(s)=\#A\bmod{m}$ .

Corollary 3.2 is a generalization of [35, Theorem 4.3] which uses the $n$ -to- $1$ definition, requires $\#A\equiv\#S\pmod{n}$ , and does not give a necessary and sufficient condition when $n\nmid\#S$ .

Corollary 3.3.

With the notation and the hypotheses of Construction 2, suppose $m\mid m_{1}\,\#S$ . Then $f$ is $m$ -to- $1$ on $A$ if and only if $m_{1}\mid m$ and $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $S$ .

Proof.

We need only show that Eq. 3.4 holds when $m_{1}\mid m$ and $\bar{f}$ is $(m/m_{1})$ -to- $1$ on $S$ . In this case, $(m/m_{1})\mid\#S$ and so $E_{\bar{f}}(S)=\varnothing$ , which is equivalent to $\sum_{s\in E_{\bar{f}}(S)}\#\lambda^{-1}(s)=0$ . Then $\#\varphi^{-1}(\bar{s})=m\#\bar{\lambda}^{-1}(\bar{s})$ for any $\bar{s}\in\varphi(A)$ by Eq. 3.13. Note that $A=\uplus_{\bar{s}\in\varphi(A)}\varphi^{-1}(\bar{s})$ . Thus $m\mid\#A$ , and so Eq. 3.4 holds. ∎

Corollary 3.3 generalizes [44, Proposition 4.2] in which $m=2$ , $m_{1}=1$ , $\#S$ is even, and only the suﬀicient condition is given. Corollary 3.3 reduces to the following form when $m=m_{1}$ .

Corollary 3.4.

Let $A$ , $\bar{A}$ , $S$ , $\bar{S}$ be finite sets and $f\colon A\rightarrow\bar{A}$ , $\bar{f}\colon S\rightarrow\bar{S}$ , $\lambda\colon A\rightarrow S$ , $\bar{\lambda}\colon\bar{A}\rightarrow\bar{S}$ be mappings such that $\bar{\lambda}\circ f=\bar{f}\circ\lambda$ . Suppose $\lambda$ is surjective, $\#\lambda^{-1}(s)=m_{1}\,\#\bar{\lambda}^{-1}(\bar{f}(s))$ , and $f$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ for any $s\in S$ and a fixed $m_{1}\in\mathbb{N}$ . Then $f$ is $m_{1}$ -to- $1$ on $A$ if and only if $\bar{f}$ is $1$ -to- $1$ on $S$ .

Construction 1 reduces to the sufficiency part of Corollary 3.4 under the conditions that $\lambda$ is surjective, $\#\lambda^{-1}(s)=m\,\#\bar{\lambda}^{-1}(\bar{f}(s))$ , and $f$ is $m$ -to- $1$ on $\lambda^{-1}(s)$ for any $s\in S$ and a fixed $m\in\mathbb{N}$ .

3.3 The third construction

Construction 3.

Let $(A,\ast)$ be a finite group and $S$ , $\bar{S}$ be subsets of $A$ . Let $f\colon A\rightarrow A$ , $\bar{f}\colon S\rightarrow\bar{S}$ , $\lambda\colon A\rightarrow S$ , $\bar{\lambda}\colon A\rightarrow\bar{S}$ be mappings such that $\bar{\lambda}\circ f=\bar{f}\circ\lambda$ , i.e., the following diagram is commutative:

Assume $\bar{\lambda}$ is a homomorphism from $A$ onto $\bar{S}$ and $u$ is a mapping from $A$ to $A$ such that $\bar{\lambda}(u(a))=c$ for any $a\in A$ and a fixed $c\in\bar{S}$ . Let $f\ast u$ be the mapping defined by $f(a)\ast u(a)$ for $a\in A$ .

\edefitn(1)

Suppose $\bar{f}$ is $1$ -to- $1$ on $S$ and $u=v\circ\lambda$ , where $v$ is a mapping from $A$ to $A$ . Then $f\ast u$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $A$ , where $1\leq m\leq\#A$ .
\edefitn(2)

Suppose $\lambda$ is surjective, $\#\lambda^{-1}(s)=m_{1}\,\#\bar{\lambda}^{-1}(\bar{f}(s))$ , and both $f$ and $f\ast u$ are $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ for any $s\in S$ and a fixed $m_{1}\in\mathbb{N}$ . Then $f\ast u$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $A$ , where $1\leq m\leq m_{1}\#S$ .

Proof.

Since $\bar{\lambda}$ is an endomorphism of $A$ , $\bar{\lambda}(u(a))=c$ , and $\bar{\lambda}\circ f=\bar{f}\circ\lambda$ , we have

\displaystyle\bar{\lambda}\circ(f\ast u)=(\bar{\lambda}\circ f)\ast(\bar{\lambda}\circ u)=(\bar{f}\circ\lambda)\ast c=(\bar{f}\ast c)\circ\lambda,

i.e., the following diagram is commutative:

We first prove Item 1. Since $\bar{\lambda}$ is a homomorphism from the group $A$ onto $\bar{S}$ , it follows that $\bar{S}$ is a subgroup of $A$ , and so $I\ast c$ permutes $\bar{S}$ , where $I$ is the identity mapping on $\bar{S}$ . Also note that $\bar{f}$ maps $S$ to $\bar{S}$ and $\bar{f}\ast c=(I\ast c)\circ\bar{f}$ . Hence, by Theorem 2.2, $\bar{f}\ast c$ is $1$ -to- $1$ on $S$ if and only if $\bar{f}$ is $1$ -to- $1$ on $S$ . By Construction 1, $f\ast u$ is $m$ -to- $1$ on $A$ if and only if $f\ast u$ is $m$ -to- $1$ on $\lambda^{-1}(s)$ for any $\#\lambda^{-1}(s)\geq m$ and

\sum_{\#\lambda^{-1}(s)\geq m}\#E_{f\ast u}(\lambda^{-1}(s))+\sum_{\#\lambda^{-1}(s)<m}\#\lambda^{-1}(s)=\#A\bmod{m}.

By Construction 1, $f$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $\lambda^{-1}(s)$ for any $\#\lambda^{-1}(s)\geq m$ and

\sum_{\#\lambda^{-1}(s)\geq m}\#E_{f}(\lambda^{-1}(s))+\sum_{\#\lambda^{-1}(s)<m}\#\lambda^{-1}(s)=\#A\bmod{m}.

For any $a\in\lambda^{-1}(s)$ , i.e., $\lambda(a)=s$ , we get $u(a)=v(\lambda(a))=v(s)$ and so

(f\ast u)(a)=f(a)\ast u(a)=f(a)\ast v(s).

(3.19)

Hence $f\ast u$ is $m$ -to- $1$ on $\lambda^{-1}(s)$ if and only if $f$ is $m$ -to- $1$ on $\lambda^{-1}(s)$ , and $E_{f\ast u}(\lambda^{-1}(s))=E_{f}(\lambda^{-1}(s))$ . Thus $f\ast u$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $A$ .

We now prove Item 2. Since $\bar{\lambda}$ is an endomorphism of $A$ , we get $\#\bar{\lambda}^{-1}(\bar{f}(s)\ast c)=\#\ker(\bar{\lambda})=\#\bar{\lambda}^{-1}(\bar{f}(s))$ by Example 1.3, and so $\#\lambda^{-1}(s)=m_{1}\,\#\bar{\lambda}^{-1}(\bar{f}(s)\ast c)$ . Also note that $\lambda$ is surjective and $f\ast u$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ . Thus, by Construction 2, $f\ast u$ is $m$ -to- $1$ on $A$ if and only if $m_{1}\mid m$ , $\bar{f}\ast c$ is $m_{2}$ -to- $1$ on $S$ , and

\sum_{s\in E_{\bar{f}\ast c}(S)}\#\lambda^{-1}(s)=\#A\bmod{m},

(3.20)

where $m_{2}=m/m_{1}\leq\#S$ . By Construction 2 again, $f$ is $m$ -to- $1$ on $A$ if and only if $m_{1}\mid m$ , $\bar{f}$ is $m_{2}$ -to- $1$ on $S$ , and

\sum_{s\in E_{\bar{f}}(S)}\#\lambda^{-1}(s)=\#A\bmod{m},

(3.21)

where $m_{2}=m/m_{1}\leq\#S$ . Note that $\bar{f}$ maps $S$ to $\bar{S}$ , $I\ast c$ permutes $\bar{S}$ , and $\bar{f}\ast c=(I\ast c)\circ\bar{f}$ . Hence $\bar{f}\ast c$ is $m_{2}$ -to- $1$ on $S$ if and only if $\bar{f}$ is $m_{2}$ -to- $1$ on $S$ by Theorem 2.2, and $E_{\bar{f}\ast c}(S)=E_{\bar{f}}(S)$ , i.e., Eq. 3.20 is equivalent to Eq. 3.21. Thus $f\ast u$ is $m$ -to- $1$ on $A$ if and only if $f$ is $m$ -to- $1$ on $A$ . ∎

This result reduces the problem whether $f\ast u$ is an $m$ -to- $1$ mapping on $A$ to that whether $f$ is an $m$ -to- $1$ mapping on $A$ . Thus it provides a method for constructing new $m$ -to- $1$ mapping $f\ast u$ from known $m$ -to- $1$ mapping $f$ under certain conditions.

Remark 1.

When $u=v\circ\lambda$ , Eq. 3.19 implies that $f$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ if and only if $f\ast u$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ . Thus Item 2 also holds without the restriction that $f\ast u$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(s)$ if $u=v\circ\lambda$ . However Theorems 4.7, 8.11 and 8.15 are in the case $u\neq v\circ\lambda$ of Construction 3.

Remark 2.

When $(A,\ast)=(\mathbb{F}_{q},+)$ , $c=0$ and $m_{1}=m=1$ , Item 2 of Construction 3 is reduced to [46, Theorem 3.2].

4 Many-to-one mappings of the form $x^{r}h(x^{s})$

In the rest of the paper, we consider only the $m$ -to- $1$ mappings of the form $x^{r}h(x^{s})$ over finite fields. We first recall the well-known $1$ -to- $1$ property of such polynomials.

Theorem 4.1.

Let $q-1=\ell s$ for some $\ell,s\in\mathbb{N}$ and $h\in\mathbb{F}_{q}[x]$ . Then $x^{r}h(x^{s})$ permutes $\mathbb{F}_{q}$ if and only if $(r,s)=1$ and $x^{r}h(x)^{s}$ permutes $U_{\ell}$ .

This result appeared in different forms in many references such as [39, 38, 1, 40, 49]. Many classes of permutation polynomials are constructed via an application of this result.

For simplicity we consider only the case that $x^{r}h(x^{s})$ has only the root $0$ in $\mathbb{F}_{q}$ . The following $m$ -to- $1$ relationship between $\mathbb{F}_{q}$ and $\mathbb{F}_{q}^{*}$ is a consequence of Definition 1.1.

Lemma 4.2.

Assume $f\in\mathbb{F}_{q}[x]$ has only the root $0$ in $\mathbb{F}_{q}$ . Then $f$ is $1$ -to- $1$ on $\mathbb{F}_{q}$ if and only if $f$ is $1$ -to- $1$ on $\mathbb{F}_{q}^{*}$ . If $m\geq 2$ , then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}$ if and only if $m\nmid q$ and $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ .

Proof.

The first part is obvious. Assume $m\geq 2$ and $q=km+r$ , where $0\leq r\leq m-1$ . If $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}$ , then $0\in E_{f}(\mathbb{F}_{q})$ and so $r\geq 1$ . Hence $m\nmid q$ and $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ with $E_{f}(\mathbb{F}_{q}^{*})=E_{f}(\mathbb{F}_{q})\setminus\{0\}$ . If $m\nmid q$ and $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ , then $r\neq 0$ and so $\#E_{f}(\mathbb{F}_{q}^{*})=(q-1)\bmod{m}\leq m-2$ . Hence $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}$ with $E_{f}(\mathbb{F}_{q})=E_{f}(\mathbb{F}_{q}^{*})\cup\{0\}$ . ∎

By this result, to determine the $m$ -to- $1$ property of $f$ on $\mathbb{F}_{q}$ , we need only find the conditions that $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ . We now give the main theorem of this paper.

Theorem 4.3.

Let $q-1=\ell s$ and $m_{1}=(r,s)$ , where $\ell,r,s\in\mathbb{N}$ . Let $f(x)=x^{r}h(x^{s})$ and $g(x)=x^{r_{1}}h(x)^{s_{1}}$ , where $r_{1}=r/m_{1}$ , $s_{1}=s/m_{1}$ , and $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{\ell}\coloneq\{\alpha\in\mathbb{F}_{q}^{*}:\alpha^{\ell}=1\}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $m_{1}\mid m$ , $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ , and $s(\ell\bmod{m_{2}})<m$ , where $1\leq m\leq\ell m_{1}$ and $m_{2}=m/m_{1}$ .

Proof.

Evidently, $x^{s_{1}}\circ f=x^{rs_{1}}h(x^{s})^{s_{1}}=x^{r_{1}s}h(x^{s})^{s_{1}}=g\circ x^{s}$ . Since $\mathbb{F}_{q}^{*}$ is a cyclic group and $s\mid q-1$ , $x^{s}$ is $s$ -to- $1$ from $\mathbb{F}_{q}^{*}$ onto $U_{\ell}$ . Because $h$ has no roots in $U_{\ell}$ , $h(x^{s})\neq 0$ for any $x\in\mathbb{F}_{q}^{*}$ , and so $f(\mathbb{F}_{q}^{*})\subseteq\mathbb{F}_{q}^{*}$ . Since $s_{1}\mid q-1$ , $x^{s_{1}}$ is $s_{1}$ -to- $1$ from $\mathbb{F}_{q}^{*}$ onto $U_{\ell m_{1}}$ . For any $\alpha\in U_{\ell}$ , $g(\alpha)^{\ell m_{1}}=\alpha^{r_{1}\ell m_{1}}h(\alpha)^{s_{1}\ell m_{1}}=(\alpha^{\ell})^{r_{1}m_{1}}h(\alpha)^{\ell s}=1$ and so $g(U_{\ell})\subseteq U_{\ell m_{1}}$ . Hence the following diagram is commutative:

Put $\lambda=x^{s}$ and $\bar{\lambda}=x^{s_{1}}$ . It follows from $s=m_{1}s_{1}$ that $\#\lambda^{-1}(\alpha)=m_{1}\#\bar{\lambda}^{-1}(g(\alpha))$ for any $\alpha\in U_{\ell}$ . Write $\alpha=\xi^{is}$ for $\alpha\in U_{\ell}$ , where $1\leq i\leq\ell$ and $\xi$ is a primitive element of $\mathbb{F}_{q}$ . Then $\lambda^{-1}(\alpha)=\xi^{i}\langle\xi^{\ell}\rangle$ , where $\langle\xi^{\ell}\rangle$ is a cyclic group of order $s$ . Thus $f$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(\alpha)$ by $(r,s)=m_{1}$ . According to Construction 2, for $1\leq m\leq m_{1}\#U_{\ell}$ , $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $m_{1}\mid m$ , $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ , and

\sum_{\alpha\in E_{g}(U_{\ell})}\#\lambda^{-1}(\alpha)=\#\mathbb{F}_{q}^{*}\bmod m.

(4.1)

Let $\ell=\ell_{2}m_{2}+t$ with $0\leq t<m_{2}$ . Then $\#E_{g}(U_{\ell})=t$ and $q-1=\ell s=\ell_{2}sm_{2}+st=\ell_{2}(s/m_{1})m+st$ . Hence the right-hand side of Eq. 4.1 is $st\bmod m$ . Since $\lambda$ is $s$ -to- $1$ from $\mathbb{F}_{q}^{*}$ onto $U_{\ell}$ , the left-hand side of Eq. 4.1 is $st$ . Now Eq. 4.1 becomes $st=st\bmod m$ , i.e., $st<m$ . ∎

From the proof above, we see that Theorem 4.3 is a special case of Construction 2, and the explicit condition $s(\ell\bmod{m_{2}})<m$ is a simplified version of the restriction Eq. 4.1 about exceptional sets. The main theorem gives us a recipe in which under suitable conditions one can construct $m$ -to- $1$ mappings on $\mathbb{F}_{q}^{*}$ from $m_{2}$ -to- $1$ mappings on its subgroup $U_{\ell}$ .

Example 4.1.

Let $f(x)=x^{2}h(x^{4})$ and $g(x)=xh(x)^{2}$ , where $h(x)=x^{5}+x^{4}+15x^{3}+1\in\mathbb{F}_{29}[x]$ . Note that $h$ has no roots in $U_{7}$ and $g$ is $6$ -to- $1$ on $U_{7}$ , where $U_{7}=\{1,7,16,20,23,24,25\}$ . Thus $f$ is $12$ -to- $1$ on $\mathbb{F}_{29}^{*}$ and the exceptional set of $f$ on $\mathbb{F}_{29}^{*}$ is $\{\pm 1,\pm 12\}$ .

When $m=1$ , Theorem 4.3 is equivalent to Theorem 4.1. Moreover, applying Theorem 4.3 to $m_{1}=1$ or $m_{2}=1$ yields the following results.

Corollary 4.4.

Let $q-1=\ell s$ and $(r,s)=1$ , where $\ell,r,s\in\mathbb{N}$ . Let $f(x)=x^{r}h(x^{s})$ and $g(x)=x^{r}h(x)^{s}$ , where $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{\ell}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $g$ is $m$ -to- $1$ on $U_{\ell}$ and $s(\ell\bmod{m})<m$ , where $1\leq m\leq\ell$ .

Corollary 4.4 generalizes [35, Propsition 4.9] in which $m\mid\ell$ .

Corollary 4.5.

When $f=x^{r}h(x^{s})$ , $\lambda=x^{s}$ , and $\bar{\lambda}=x^{s_{1}}$ , Construction 1 reduces to the sufficiency part of Corollary 4.5, and so Construction 2 contains Construction 1. Thus we will not consider Construction 1 in the sequel.

We next give two methods for constructing $m$ -to- $1$ mappings from known results.

Theorem 4.6.

Let $q-1=\ell s$ and let $M\in\mathbb{F}_{q}[x]$ satisfy $\varepsilon x^{t}M(x)^{s}=1$ for any $x\in U_{\ell}$ , where $\ell,s,t\in\mathbb{N}$ and $\varepsilon\in U_{\ell}$ . Let

f(x)=x^{r}h(x^{s})\quad\text{and}\quad F(x)=x^{kt}M(x^{s})^{k}f(x),

where $r,k\in\mathbb{N}$ and $h\in\mathbb{F}_{q}[x]$ . If $f$ permutes $\mathbb{F}_{q}$ , then $F$ is $(r+kt,s)$ -to- $1$ on $\mathbb{F}_{q}^{*}$ .

Proof.

Clearly, $F(x)=x^{r+kt}M(x^{s})^{k}h(x^{s})$ . Put $m_{1}=(r+kt,s)$ and $g(x)=x^{(r+kt)/m_{1}}(M(x)^{k}h(x))^{s/m_{1}}$ . Since $f$ permutes $\mathbb{F}_{q}$ and $\varepsilon x^{t}M(x)^{s}=1$ , it follows that $h$ and $M$ have no roots in $U_{\ell}$ . By Corollary 4.5, $F$ is $m_{1}$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $g$ is $1$ -to- $1$ on $U_{\ell}$ . For any $x\in U_{\ell}$ ,

x^{m_{1}}\circ g(x)=x^{r+kt}M(x)^{ks}h(x)^{s}=(x^{t}M(x)^{s})^{k}x^{r}h(x)^{s}=\varepsilon^{-k}x^{r}h(x)^{s}.

Since $f$ permutes $\mathbb{F}_{q}$ , we get $x^{r}h(x)^{s}$ permutes $U_{\ell}$ by Theorem 4.1. Hence $\varepsilon^{-k}x^{r}h(x)^{s}$ (i.e., $x^{m_{1}}\circ g(x)$ ) permutes $U_{\ell}$ , and so $g$ is $1$ -to- $1$ on $U_{\ell}$ . Thus $F$ is $m_{1}$ -to- $1$ on $\mathbb{F}_{q}^{*}$ . ∎

By this result, we can use known permutations of $\mathbb{F}_{q}$ to construct $m$ -to- $1$ mappings on $\mathbb{F}_{q}^{*}$ . Thus it establishes an important and interesting link between permutations and $m$ -to- $1$ mappings.

Combining Constructions 3 and 4.3 yields the next result.

Theorem 4.7.

Let $k,\ell,r,s,t\in\mathbb{N}$ satisfy $q-1=\ell s$ , $(r,s)\mid t$ , and $(r,s)=(r+kt,s)$ . Suppose $M\in\mathbb{F}_{q}[x]$ satisfies $\varepsilon x^{t/m_{1}}M(x)^{s/m_{1}}=1$ for any $x\in U_{\ell}$ , where $m_{1}=(r,s)$ and $\varepsilon\in U_{\ell m_{1}}$ . Let

f(x)=x^{r}h(x^{s})\quad\text{and}\quad F(x)=x^{kt}M(x^{s})^{k}f(x),

where $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{\ell}$ . Then $F$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ , where $1\leq m\leq\ell m_{1}$ .

Proof.

Put $\lambda=x^{s}$ , $\bar{\lambda}=x^{s_{1}}$ , and $g(x)\coloneq x^{r_{1}}h(x)^{s_{1}}$ , where $r_{1}=r/m_{1}$ and $s_{1}=s/m_{1}$ . In the proof of Theorem 4.3, we have already shown that $\bar{\lambda}\circ f=g\circ\lambda$ , $\lambda$ is surjective from $\mathbb{F}_{q}^{*}$ to $U_{\ell}$ , $\#\lambda^{-1}(\alpha)=m_{1}\,\#\bar{\lambda}^{-1}(g(\alpha))$ , and $f$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(\alpha)$ for any $\alpha\in U_{\ell}$ . For $x\in\lambda^{-1}(\alpha)$ , i.e., $\lambda(x)=\alpha$ , we get $F(x)=x^{r+kt}M(\alpha)^{k}h(\alpha)$ , and so $F$ is $m_{1}$ -to- $1$ on $\lambda^{-1}(\alpha)$ by $(r+kt,s)=m_{1}$ . Clearly, $\bar{\lambda}$ is a homomorphism from $\mathbb{F}_{q}^{*}$ onto $U_{\ell m_{1}}$ and

\displaystyle(x^{kt}M(x^{s})^{k})^{s_{1}}=(x^{s_{1}t}M(x^{s})^{s_{1}})^{k}=(x^{st_{1}}M(x^{s})^{s_{1}})^{k}=\varepsilon^{-k}\in U_{\ell m_{1}}

for any $x\in\mathbb{F}_{q}^{*}$ , where $t_{1}=t/m_{1}$ . Then the result follows from Construction 3. ∎

In this result, the polynomials $f$ and $F$ have the same $m$ -to- $1$ property. Thus we can use know $m$ -to- $1$ mapping $f$ to construct new $m$ -to- $1$ mapping $F$ by Theorem 4.7; see for example Theorems 8.11 and 8.15.

The main theorem converts the problem whether $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ to the second problem whether $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ . In the following sections, we will make an in-depth study of the second problem in the special cases:

\edefnn(1)

$m=2,3$ ;
\edefnn(2)

$\ell=2,3$ ;
\edefnn(3)

$g$ behaves like a monomial on $U_{\ell}$ ;
\edefnn(4)

$g$ behaves like a rational function on $U_{\ell}$ ;
\edefnn(5)

the second problem is converted to another problem by using Construction 2 again.

5 The case $m=2,3$

Applying Theorem 4.3 to $m=2$ , $3$ yields the following results.

Theorem 5.1.

Let $q-1=\ell s$ and $m_{1}=(r,s)$ , where $r\geq 1$ , $s\geq 2$ , and $\ell\geq 2$ . Let $f(x)=x^{r}h(x^{s})$ and $g(x)=x^{r_{1}}h(x)^{s_{1}}$ , where $r_{1}=r/m_{1}$ , $s_{1}=s/m_{1}$ , and $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{\ell}$ . Then $f$ is $2$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if one of the following holds:

\edefitn(1)

$m_{1}=1$ , $\ell$ is even, and $g$ is $2$ -to- $1$ on $U_{\ell}$ ;
\edefitn(2)

$m_{1}=2$ and $g$ is $1$ -to- $1$ on $U_{\ell}$ .

Proof.

By Theorem 4.3, $f$ is $2$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $m_{1}\mid 2$ , $s(\ell\bmod{m_{2}})<2$ , and $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ , where $m_{2}=2/m_{1}$ . If $m_{1}=1$ , then $m_{2}=2$ . Since $s\geq 2$ , $s(\ell\bmod{2})<2$ is equivalent to $2\mid\ell$ . If $m_{1}=2$ , then $m_{2}=1$ and $s(\ell\bmod{1})=0<2$ . ∎

Item 2 of Theorem 5.1 generalizes [30, Proposition 16] which only gives the sufficiency. We next give an example of Theorem 5.1.

Corollary 5.2.

Let $f(x)=x^{r}(x^{\frac{2q-2}{3}}+x^{\frac{q-1}{3}}+a)$ , where $r\geq 1$ , $q\geq 7$ , $3\mid q-1$ , and $a\in\mathbb{F}_{q}\setminus\{1,-2\}$ . Then $f$ is $2$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $(r,\frac{q-1}{3})=2$ , $r\equiv 2,4\pmod{6}$ , and $((a-1)^{5}(a+2))^{\frac{q-1}{6}}\notin\{\omega,\omega^{2}\}$ , where $\omega$ is a primitive $3$ -th root of unity over $\mathbb{F}_{q}$ .

Proof.

Clearly, $\ell=3$ and $U_{3}=\{1,\omega,\omega^{2}\}$ . Let $h(x)=x^{2}+x+a$ . Then $h(1)=a+2$ and $h(\omega)=h(\omega^{2})=a-1$ , and so $h$ has no roots in $U_{3}$ . By Theorem 5.1, $f$ is $2$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $(r,\frac{q-1}{3})=2$ and $g(x)\coloneq x^{\frac{r}{2}}h(x)^{\frac{q-1}{6}}$ is $1$ -to- $1$ on $U_{3}$ , i.e., $g(1)$ , $g(\omega)$ , and $g(\omega^{2})$ are distinct. The latter is equivalent to $((a-1)^{5}(a+2))^{\frac{q-1}{6}}\notin\{\omega^{\frac{r}{2}},\omega^{r}\}$ and $\omega^{\frac{r}{2}}\neq 1$ . Then the result follows from $2\mid r$ and $\mathrm{ord}(\omega)=3$ . ∎

Theorem 5.3.

Let $q-1=\ell s$ and $m_{1}=(r,s)$ , where $r\geq 1$ , $s\geq 2$ , and $\ell\geq 3$ . Let $f(x)=x^{r}h(x^{s})$ and $g(x)=x^{r_{1}}h(x)^{s_{1}}$ , where $r_{1}=r/m_{1}$ , $s_{1}=s/m_{1}$ , and $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{\ell}$ . Then $f$ is $3$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if one of the following holds:

\edefitn(1)

$m_{1}=1$ , $\ell\equiv 0\pmod{3}$ , and $g$ is $3$ -to- $1$ on $U_{\ell}$ ;
\edefitn(2)

$m_{1}=1$ , $\ell\equiv 1\pmod{3}$ , $s=2$ , and $g$ is $3$ -to- $1$ on $U_{\ell}$ ;
\edefitn(3)

$m_{1}=3$ and $g$ is $1$ -to- $1$ on $U_{\ell}$ .

Proof.

By Theorem 4.3, $f$ is $3$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $m_{1}\mid 3$ , $s(\ell\bmod{m_{2}})<3$ , and $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ , where $m_{2}=3/m_{1}$ . If $m_{1}=1$ , then $m_{2}=3$ . Since $s\geq 2$ , $s(\ell\bmod{3})<3$ is equivalent to $\ell\equiv 0\pmod{3}$ or $\ell\equiv 1\pmod{3}$ and $s=2$ . If $m_{1}=3$ , then $m_{2}=1$ and $s(\ell\bmod{1})=0<3$ . ∎

6 The case $\ell=2,3$

When $U_{\ell}$ has few elements, i.e., $\ell$ is small, it is easy to determine the $m$ -to- $1$ property of $g$ on $U_{\ell}$ . As an example, we consider the case $\ell=2$ , $3$ in this section.

Theorem 6.1.

Let $q$ be odd, $s=(q-1)/2$ , and $m_{1}=(r,s)$ , where $r,s\in\mathbb{N}$ . Let $f(x)=x^{r}h(x^{s})$ and $g(x)=x^{r_{1}}h(x)^{s_{1}}$ , where $r_{1}=r/m_{1}$ , $s_{1}=s/m_{1}$ , and $h\in\mathbb{F}_{q}[x]$ with $h(1)h(-1)\neq 0$ . Then, for $1\leq m\leq 2m_{1}$ , $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if (1) $m=m_{1}$ and $g(1)\neq g(-1)$ , or (2) $m=2m_{1}$ and $g(1)=g(-1)$ .

Applying Theorem 6.1 to $h(x)=x+a$ yields the following result.

Corollary 6.2.

Let $f(x)=x^{r}(x^{\frac{q-1}{2}}+a)$ , where $r\in\mathbb{N}$ , $q$ is odd, and $a\in\mathbb{F}_{q}\setminus\{\pm 1\}$ . Then $f$ is $2$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if (1) $(r,\frac{q-1}{2})=1$ and $(a^{2}-1)^{\frac{q-1}{2}}=(-1)^{r}$ , or (2) $(r,\frac{q-1}{2})=2$ and $((a+1)/(a-1))^{\frac{q-1}{4}}\neq(-1)^{\frac{r}{2}}$ .

This result generalizes [35, Theorem 4.14] in which $q\equiv 3\pmod{4}$ and $(r,\frac{q-1}{2})=1$ .

Theorem 6.3.

Let $s=(q-1)/3$ and $m_{1}=(r,s)$ , where $r,s\in\mathbb{N}$ and $3\mid q-1$ . Let $f(x)=x^{r}h(x^{s})$ and $g(x)=x^{r_{1}}h(x)^{s_{1}}$ , where $r_{1}=r/m_{1}$ , $s_{1}=s/m_{1}$ , and $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{3}$ . Then, for $1\leq m\leq 3m_{1}$ , $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if one of the following holds:

\edefitn(1)

$m=m_{1}$ and $g$ is $1$ -to- $1$ on $U_{3}$ ;
\edefitn(2)

$m=2m_{1}$ , $g$ is $2$ -to- $1$ on $U_{3}$ , and $s\mid r$ ;
\edefitn(3)

$m=3m_{1}$ and $g$ is $3$ -to- $1$ on $U_{3}$ .

Applying Theorem 6.3 to $h(x)=x-a$ yields the following result.

Corollary 6.4.

Let $f(x)=x^{r}(x^{\frac{q-1}{3}}-a)$ and $g(x)=x^{r_{1}}(x-a)^{s_{1}}$ , where $r\in\mathbb{N}$ , $3\mid q-1$ , $a\in\mathbb{F}_{q}\setminus U_{3}$ , $r_{1}=r/(r,\frac{q-1}{3})$ , and $s_{1}=(q-1)/(3r,q-1)$ . Then $f$ is $3$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if (1) $(r,\frac{q-1}{3})=1$ and $g$ is $3$ -to- $1$ on $U_{3}$ , or (2) $(r,\frac{q-1}{3})=3$ and $g$ is $1$ -to- $1$ on $U_{3}$ .

Example 6.1.

Let $f(x)=x^{2}(x^{21}+\xi^{9})$ and $g(x)=x^{2}(x+\xi^{9})^{21}$ , where $\xi$ is a primitive element of $\mathbb{F}_{64}$ such that $\xi^{6}+\xi^{4}+\xi^{3}+\xi+1=0$ . Then $g(1)=g(\omega)=g(\omega^{2})=1$ , where $\omega=\xi^{21}$ . Hence $f$ is $3$ -to- $1$ on $\mathbb{F}_{64}^{*}$ .

7 Monomials

The difficulty in applying Theorem 4.3 is verifying that $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ . While it is easy when $g$ behaves like a monomial on $U_{\ell}$ . The results in this section are conjunctions of Theorem 4.3 and [1, 49, 51].

Theorem 7.1.

Let $q-1=\ell s$ , $m_{1}=(r,s)$ , $r_{1}=r/m_{1}$ , and $s_{1}=s/m_{1}$ , where $\ell,r,s\in\mathbb{N}$ . Let $h\in\mathbb{F}_{q}[x]$ and $h(\alpha)^{s_{1}}=\beta\alpha^{t}$ for any $\alpha\in U_{\ell}$ , a fixed $\beta\in U_{\ell}$ , and a fixed integer $t$ . Then $f(x)\coloneq x^{r}h(x^{s})$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $m_{1}\mid m$ and $(r_{1}+t,\ell)=m/m_{1}$ , where $1\leq m\leq\ell m_{1}$ .

Proof.

For any $x\in U_{\ell}$ , by $h(x)^{s_{1}}=\beta x^{t}$ , we get $x^{r_{1}}h(x)^{s_{1}}=\beta x^{r_{1}+t}$ , which is $m_{2}$ -to- $1$ on $U_{\ell}$ if and only if $(r_{1}+t,\ell)=m_{2}$ . The result follows now from Theorem 4.3. ∎

In Theorem 7.1, $g(x)\coloneq x^{r_{1}}h(x)^{s_{1}}$ behaves like the monomial $\beta x^{r_{1}+t}$ on $U_{\ell}$ . The following results give choices for the parameters satisfying the hypotheses of Theorem 7.1.

Corollary 7.2.

Let $q-1=\ell s$ and $m_{1}=(r,s)$ , where $\ell,r,s\in\mathbb{N}$ . Let $f(x)=x^{r}h(x^{s})^{\ell m_{1}}$ , where $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{\ell}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $m_{1}\mid m$ and $(r,\ell m_{1})=m$ , where $1\leq m\leq\ell m_{1}$ .

Proof.

For $\alpha\in U_{\ell}$ , $h(\alpha)^{\ell m_{1}s_{1}}=h(\alpha)^{q-1}=1$ . Now the result is in the special case $\beta=1$ and $t=0$ of Theorem 7.1. ∎

7.1 $m$ -to- $1$ mappings on $\mathbb{F}_{q^{2}}^{*}$

Now we extend a class of permutations of $\mathbb{F}_{q^{2}}^{*}$ in [51, Theorem 5.1] to $m$ -to- $1$ mappings on $\mathbb{F}_{q^{2}}^{*}$ .

Theorem 7.3.

Suppose $M\in\mathbb{F}_{q^{2}}[x]$ has no roots in $U_{q+1}$ and $\varepsilon x^{t}M(x)^{q}=M(x)$ for any $x\in U_{q+1}$ , where $\varepsilon\in U_{q+1}$ and $\deg(M)\leq t\leq 2\deg(M)$ . Let $f(x)=x^{r}M(x^{q-1})^{km_{1}}$ , where $r,k\in\mathbb{N}$ and $m_{1}=(r,q-1)$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ and $(r_{1}-kt,q+1)=m/m_{1}$ , where $r_{1}=r/m_{1}$ and $1\leq m\leq m_{1}(q+1)$ .

Proof.

Since $0\neq\varepsilon x^{t}M(x)^{q}=M(x)$ for $x\in U_{q+1}$ , we get $M(x)^{q-1}=\varepsilon^{-1}x^{-t}$ , and so $M(x)^{k(q-1)}=\varepsilon^{-k}x^{-kt}$ . Then the result follows from Theorem 7.1. ∎

When $t=\deg(M)$ and $k=m_{1}=m=1$ , Theorem 7.3 is equivalent to [51, Theorem 5.1].

Remark 3.

The polynomial $M$ satisfying $\varepsilon x^{t}M(x)^{q}=M(x)$ for any $x\in U_{q+1}$ can be described explicitly. Indeed, let $M(x)=\sum_{i=0}^{d}a_{i}x^{i}\in\mathbb{F}_{q^{2}}[x]$ , where $d=\deg(M)$ . Then a direct computation gives that

\varepsilon x^{t}M^{q}=M\quad\text{if and only if}\quad M(x)=\sum_{i=t-d}^{\lfloor t/2\rfloor}(a_{i}x^{i}+\varepsilon a_{i}^{q}x^{t-i}),

where $\lfloor t/2\rfloor$ denotes the largest integer $\leq t/2$ .

For simple, take $t=d$ , $a_{0}=-a\in U_{q+1}$ , $\varepsilon=-a$ , and other $a_{i}=0$ . Then $M(x)=x^{d}-a$ , and it has no roots in $U_{q+1}$ if and only if $a\notin(U_{q+1})^{d}$ . Hence we obtain the following result.

Corollary 7.4.

Let $a\in\mathbb{F}_{q^{2}}$ satisfy $a^{q+1}=1$ and $a^{t}\neq 1$ , where $t=(q+1)/(d,q+1)$ with $d\in\mathbb{N}$ . Let $f(x)=x^{r}(x^{d(q-1)}-a)^{km_{1}}$ , where $r,k\in\mathbb{N}$ and $m_{1}=(r,q-1)$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ and $(r_{1}-kd,q+1)=m/m_{1}$ , where $r_{1}=r/m_{1}$ and $1\leq m\leq m_{1}(q+1)$ .

Example 7.1.

Let $q$ be odd such that $3\mid q+1$ and $8\nmid q+1$ . Then $x^{4q-3}+x$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ .

Example 7.2.

Let $q=2^{n}$ and $n$ be odd. Let $a\in\mathbb{F}_{q^{2}}$ satisfy $a^{q+1}=1$ and $a^{(q+1)/3}\neq 1$ . Then $x^{3q+3}+ax^{6}$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ .

Example 7.3.

Let $q$ be odd and $3\mid q+1$ . Let $a\in\mathbb{F}_{q^{2}}$ satisfy $a^{q+1}=1$ and $a^{(q+1)/3}\neq 1$ . Then $x^{3q-2}-ax$ is $2$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ .

7.2 $m$ -to- $1$ mappings on $\mathbb{F}_{q^{n}}^{*}$

Next we extend two classes of permutations of $\mathbb{F}_{q^{n}}^{*}$ in [49] to $m$ -to- $1$ mappings on $\mathbb{F}_{q^{n}}^{*}$ .

Theorem 7.5.

Let $q^{n}-1=\ell s$ , $m_{1}=(r,s)$ , and $\ell m_{1}\mid(q-1,n)$ , where $n$ , $\ell$ , $s$ , $r\in\mathbb{N}$ . Let $f(x)=x^{r}h(x^{s})$ , where $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{\ell}$ . Then $f$ is $m_{1}$ -to- $1$ on $\mathbb{F}_{q^{n}}^{*}$ .

Proof.

Let $r_{1}=r/m_{1}$ and $s_{1}=s/m_{1}$ . Since $q\equiv 1\pmod{\ell m_{1}}$ ,

\frac{q^{\ell m_{1}}-1}{q-1}=\sum^{\ell m_{1}-1}_{i=0}q^{i}\equiv 0\pmod{\ell m_{1}},

and so $q-1$ divides $(q^{\ell m_{1}}-1)/(\ell m_{1})$ , which divides $(q^{n}-1)/(\ell m_{1})$ , i.e., $s_{1}$ . Thus $q-1\mid s_{1}$ . For $\alpha\in U_{\ell}$ , we have $\alpha\in\mathbb{F}_{q}^{*}$ by $\ell\mid q-1$ , and so $h(\alpha)\in\mathbb{F}_{q}^{*}$ . Then $h(\alpha)^{s_{1}}=1$ by $q-1\mid s_{1}$ . Since $\ell\mid q-1$ and $q-1\mid s_{1}$ , we get $\ell\mid s_{1}$ . Then $(r_{1},\ell)=1$ by $(r_{1},s_{1})=1$ . Now the result is in the special case $t=0$ and $m=m_{1}$ of Theorem 7.1. ∎

In the following results we use the notation

h_{d}(x)=x^{d-1}+x^{d-2}+\cdots+x+1.

(7.1)

Theorem 7.6.

Let $q^{n}-1=\ell s$ , $m_{1}=(r,s)$ , and $\ell m_{1}\mid q+1$ , where $n$ is even, $\ell,s,r\in\mathbb{N}$ . Assume $h(x)\coloneq h_{d}(x^{e})^{t}H(h_{k}(x^{e})^{\ell_{0}})$ has no roots in $U_{\ell}$ , where $H\in\mathbb{F}_{q}[x]$ , $d,e,t,k\in\mathbb{N}$ , and $\ell_{0}=\ell/(\ell,k-1)$ . Then, for $1\leq m\leq\ell m_{1}$ , $f(x)\coloneq x^{r}h(x^{s})$ is $m$ -to- $1$ on $\mathbb{F}_{q^{n}}^{*}$ if and only if $m_{1}\mid m$ and

\Big{(}\ell m_{1},r+\frac{(1-d)est}{q-1}\Big{)}=m.

(7.2)

Proof.

Since $n$ is even and $\ell m_{1}\mid q+1$ , we have the divisibility relations

q-1=\frac{q^{2}-1}{q+1}\mid\frac{q^{n}-1}{q+1}\mid\frac{q^{n}-1}{\ell m_{1}}=s_{1},

where $s_{1}=s/m_{1}$ . For $\alpha\in U_{\ell}\setminus\{1\}$ , we get $\alpha^{q}=\alpha^{-1}$ by $\ell\mid q+1$ , and so

h_{k}(\alpha)^{q}=\Big{(}\frac{\alpha^{k}-1}{\alpha-1}\Big{)}^{q}=\frac{\alpha^{-k}-1}{\alpha^{-1}-1}=\frac{h_{k}(\alpha)}{\alpha^{k-1}}.

Then $h_{k}(\alpha)^{\ell_{0}q}=h_{k}(\alpha)^{\ell_{0}}$ , i.e., $h_{k}(\alpha)^{\ell_{0}}\in\mathbb{F}_{q}$ . Clearly, $h_{k}(1)=k\in\mathbb{F}_{q}$ . Since $H\in\mathbb{F}_{q}[x]$ and $H(h_{k}(x^{e})^{\ell_{0}})$ has no roots in $U_{\ell}$ , we have $H(h_{k}(\alpha^{e})^{\ell_{0}})\in\mathbb{F}_{q}^{*}$ for any $\alpha\in U_{\ell}$ . Thus $H(h_{k}(\alpha^{e})^{\ell_{0}})^{s_{1}}=1$ .

For $\alpha\in U_{\ell}$ , if $\alpha^{e}\neq 1$ , then $\alpha^{q}=\alpha^{-1}$ by $\ell\mid q+1$ , and so

h_{d}(\alpha^{e})^{q}=\Big{(}\frac{\alpha^{ed}-1}{\alpha^{e}-1}\Big{)}^{q}=\frac{\alpha^{-ed}-1}{\alpha^{-e}-1}=\frac{h_{d}(\alpha^{e})}{\alpha^{e(d-1)}}.

By hypothesis, $h_{d}(x^{e})$ has no roots in $U_{\ell}$ , and so $h_{d}(\alpha^{e})^{q-1}=\alpha^{e(1-d)}$ . Thus

h_{d}(\alpha^{e})^{s_{1}}=h_{d}(\alpha^{e})^{(q-1)s_{1}/(q-1)}=\alpha^{e(1-d)s_{1}/(q-1)}.

If $\alpha^{e}=1$ , then $h_{d}(\alpha^{e})^{s_{1}}=h_{d}(1)^{s_{1}}=d^{s_{1}}=1$ by $d\in\mathbb{F}_{q}^{*}$ and $q-1\mid s_{1}$ . Thus $h_{d}(\alpha^{e})^{s_{1}}=\alpha^{e(1-d)s_{1}/(q-1)}$ for any $\alpha\in U_{\ell}$ . Then the result follows from Theorem 7.1. ∎

The following lemma characterizes the condition that $h_{d}(x^{e})$ has no roots in $U_{\ell}$ .

Lemma 7.7.

Let $U_{\ell}$ be the cyclic group of all $\ell$ -th roots of unity over $\mathbb{F}_{q^{n}}$ , where $\ell,n\in\mathbb{N}$ and $\ell\mid q^{n}-1$ . Then $h_{d}(x^{e})$ has no roots in $U_{\ell}$ if and only if $(d,q\ell/(e,\ell))=1$ , where $d,e\in\mathbb{N}$ .

Proof.

Evidently, $h_{d}(1)\neq 0$ if and only if $(d,q)=1$ . For $\alpha\in U_{\ell}\setminus\{1\}$ , $h_{d}(\alpha)=(\alpha^{d}-1)/(\alpha-1)$ . Then $h_{d}(\alpha)\neq 0$ if and only if $\alpha^{d}\neq 1$ , which is equivalent to $(d,\ell)=1$ . Hence $h_{d}(x)$ has no roots in $U_{\ell}$ if and only if $(d,q\ell)=1$ . Note that $x^{e}$ is $(e,\ell)$ -to- $1$ from $U_{\ell}$ onto $U_{\ell/(e,\ell)}$ . Thus $h_{d}(x^{e})$ has no roots in $U_{\ell}$ if and only if $h_{d}(x)$ has no roots in $U_{\ell/(e,\ell)}$ , which is equivalent to $(d,q\ell/(e,\ell))=1$ . ∎

Applying Theorem 7.5 to $h(x)=h_{d}(x^{e})^{t}$ and Theorem 7.6 to $H(x)=1$ yields the following results.

Corollary 7.8.

Let $q^{n}-1=\ell s$ , $m_{1}=(r,s)$ , and $\ell m_{1}\mid(q-1,n)$ , where $n,\ell,s,r\in\mathbb{N}$ . Let $f(x)=x^{r}h_{d}(x^{es})^{t}$ , where $d,e,t\in\mathbb{N}$ with $(d,q\ell/(e,\ell))=1$ . Then $f$ is $m_{1}$ -to- $1$ on $\mathbb{F}_{q^{n}}^{*}$ .

Corollary 7.9.

Let $q^{n}-1=\ell s$ , $m_{1}=(r,s)$ , and $\ell m_{1}\mid q+1$ , where $n$ is even, $\ell,s,r\in\mathbb{N}$ . Let $f(x)=x^{r}h_{d}(x^{es})^{t}$ , where $d,e,t\in\mathbb{N}$ with $(d,q\ell/(e,\ell))=1$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{n}}^{*}$ if and only if $m_{1}\mid m$ and Eq. 7.2 holds, where $1\leq m\leq\ell m_{1}$ .

The results in this subsection generalize Theorems 1.2 and 1.3, Corollaries 2.3 and 2.4 in [49] where $m_{1}=1$ and $(e,\ell)=1$ .

8 Rational functions

In this section, we consider the case that $g$ behaves like a rational function on $U_{\ell}$ . Part 1 presents two classes of $m$ -to- $1$ mappings on $\mathbb{F}_{q^{2}}^{*}$ by using known $1$ -to- $1$ rational functions. Parts 2 and 3 give two classes of rational functions that are $3$ -to- $1$ and $5$ -to- $1$ on $U_{q+1}$ respectively, by finding the decompositions of two algebraic curves.

Applying Theorems 4.3 and 4.7 to $\ell=q+1$ and $s=q-1$ yields the next results.

Theorem 8.1.

Let $f(x)=x^{r}h(x^{q-1})$ and $g(x)=x^{r_{1}}h(x)^{s_{1}}$ , where $h\in\mathbb{F}_{q^{2}}[x]$ has no roots in $U_{q+1}$ , $r\geq 1$ , $r_{1}=r/m_{1}$ , $s_{1}=(q-1)/m_{1}$ , and $m_{1}=(r,q-1)$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ , $g$ is $m_{2}$ -to- $1$ on $U_{q+1}$ , and $(q-1)(q+1\bmod{m_{2}})<m$ , where $1\leq m\leq m_{1}(q+1)$ and $m_{2}=m/m_{1}$ .

Theorem 8.2.

Suppose $M\in\mathbb{F}_{q^{2}}[x]$ has no roots in $U_{q+1}$ and $\varepsilon x^{t}M(x)^{q}=M(x)$ for any $x\in U_{q+1}$ , where $\varepsilon\in U_{q+1}$ and $\deg(M)\leq t\leq 2\deg(M)$ . Let $f(x)=x^{r}h(x^{q-1})$ and $F(x)=x^{kt}M(x^{q-1})^{k}f(x)$ , where $r,k\in\mathbb{N}$ satisfy $(r,q-1)=(r+kt,q-1)=1$ and $h\in\mathbb{F}_{q^{2}}[x]$ has no roots in $U_{q+1}$ . Then $F$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ , where $1\leq m\leq q+1$ .

8.1 Known 1-to-1 rational functions

Lemma 8.3 ([16, Lemma 2.2]).

For $n\in\mathbb{N}$ , $x^{4}+x+1$ and $x^{4}+x^{3}+1$ have no roots in $U_{2^{n}+1}$ .

Lemma 8.4 ([47, Lemma 3.2]).

Let $q=2^{n}$ with $n\geq 1$ . Then

G(x)\coloneq\frac{x^{5}+x^{2}+x}{x^{4}+x^{3}+1}

permutes $U_{q+1}$ if and only if $n$ is even.

Theorem 8.5.

Let $q=2^{n}$ with $n$ even. Let $f_{1}(x)=x^{4q+1}+x^{3q+2}+x^{5}$ and $f_{2}(x)=x^{5q}+x^{2q+3}+x^{q+4}$ . Then $f_{1}$ and $f_{2}$ are $(5,q-1)$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ .

Proof.

Put $h_{1}(x)=x^{4}+x^{3}+1$ and $g_{1}(x)=x^{\frac{5}{m_{1}}}h_{1}(x)^{\frac{q-1}{m_{1}}}$ , where $m_{1}=(5,q-1)$ . Then

\displaystyle x^{m_{1}}\circ g_{1}(x)=x^{5}h_{1}(x)^{q-1}=\frac{x^{5}(x^{4}+x^{3}+1)^{q}}{x^{4}+x^{3}+1}=\frac{x^{5}(x^{-4}+x^{-3}+1)}{x^{4}+x^{3}+1}=G(x)

for $x\in U_{q+1}$ . By Lemma 8.4, $G$ is $1$ -to- $1$ on $U_{q+1}$ , and so $g_{1}$ is $1$ -to- $1$ on $U_{q+1}$ . Thus $f_{1}$ is $m_{1}$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ by Lemmas 8.3 and 8.1.

Put $h_{2}(x)=x^{5}+x^{2}+x$ and $g_{2}(x)=x^{\frac{5}{m_{1}}}h_{2}(x)^{\frac{q-1}{m_{1}}}$ , where $m_{1}=(5,q-1)$ . Then $x^{m_{1}}\circ g_{2}(x)=1/G(x)$ for $x\in U_{q+1}$ . By Lemma 8.4, $1/G$ is $1$ -to- $1$ on $U_{q+1}$ , and so $g_{2}$ is $1$ -to- $1$ on $U_{q+1}$ . Thus $f_{2}$ is $m_{1}$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ . ∎

Theorem 8.5 extends [47, Theorems 3.1 and 3.2] in which $n\equiv 2\pmod{4}$ .

8.2 New 3-to-1 rational function

We begin with a different proof of a result in [23, 8, 21].

Lemma 8.6 ([23, 8, 21]).

Let $A_{i}=\{c\in\mathbb{F}_{2^{n}}^{*}\mid\mathrm{Tr}_{2^{n}/2}(1/c)=i\}$ with $i=0$ or $1$ . Then the mapping $a\mapsto a+1/a$ is $2$ -to- $1$ from $\mathbb{F}_{2^{n}}\setminus\{0,1\}$ onto $A_{0}$ and is $2$ -to- $1$ from $U_{2^{n}+1}\setminus\{1\}$ onto $A_{1}$ , where $U_{2^{n}+1}=\{a\in\mathbb{F}_{2^{2n}}\mid a^{2^{n}+1}=1\}$ .

Proof.

For $a\in U_{2^{n}+1}\setminus\{1\}$ , we have $a+1/a\in\mathbb{F}_{2^{n}}^{*}$ and

	$\displaystyle\mathrm{Tr}_{2^{n}/2}((a+1/a)^{-1})$	$\displaystyle=\mathrm{Tr}_{2^{n}/2}(1/(a+1)+1/(a^{2}+1))$
		$\displaystyle=1/(a+1)+1/(a^{2^{n}}+1)$
		$\displaystyle=1,$

i.e., $a+1/a\in A_{1}$ . For any $a$ , $a+b\in U_{2^{n}+1}\setminus\{1\}$ , if $a+1/a=(a+b)+1/(a+b)$ , then $b=0$ or $b=(a^{2}+1)/a\neq 0$ . Thus $a\mapsto a+1/a$ is $2$ -to- $1$ from $U_{2^{n}+1}\setminus\{1\}$ onto $A_{1}$ with cardinality $2^{n-1}$ . Similarly, $a\mapsto a+1/a$ is $2$ -to- $1$ from $\mathbb{F}_{2^{n}}\setminus\{0,1\}$ onto $A_{0}$ with cardinality $2^{n-1}-1$ . ∎

Corollary 8.7.

For any $c\in\mathbb{F}_{2^{n}}^{*}$ , $\mathrm{Tr}_{2^{n}/2}(1/c)=0$ if and only if $c=a+a^{-1}$ for some $a\in\mathbb{F}_{2^{n}}\setminus\{0,1\}$ , and $\mathrm{Tr}_{2^{n}/2}(1/c)=1$ if and only if $c=a+a^{-1}$ for some $a\in U_{2^{n}+1}\setminus\{1\}$ .

We next give a new class of $3$ -to- $1$ rational functions.

Lemma 8.8.

Let $c\in\mathbb{F}_{2^{n}}^{*}$ with $n\geq 1$ and

g(x)=\frac{cx^{3}+x^{2}+1}{x^{3}+x+c}.

If $\mathrm{Tr}_{2^{n}/2}(1+c^{-1})=0$ , then $g$ is $1$ -to- $1$ on $U_{2^{n}+1}$ . If $\mathrm{Tr}_{2^{n}/2}(1+c^{-1})=1$ , then $g$ is $3$ -to- $1$ on $U_{2^{n}+1}$ .

Proof.

Put $q=2^{n}$ . Proposition 3.1 (i) in [4] implies that $x^{3}+x+c$ has no roots in $U_{q+1}$ . Then for any $x$ , $y\in U_{q+1}$ , $g(x)=g(y)$ is equivalent to

(cx^{3}+x^{2}+1)(y^{3}+y+c)=(cy^{3}+y^{2}+1)(x^{3}+x+c).

(8.1)

Proposition 3.2 (ii) in [4] states that Eq. 8.1 factors as

(x+y)H_{1}(x,y)H_{2}(x,y)=0,

(8.2)

where $H_{1}(x,y)=xy+\alpha x+\beta y+1$ , $H_{2}(x,y)=xy+\beta x+\alpha y+1$ , and $\alpha,\beta\in\mathbb{F}_{q^{2}}$ are the roots of $Q(x)\coloneq x^{2}+cx+c^{2}+1$ . Thus $\alpha+\beta=c$ and $\alpha\beta=c^{2}+1$ .

(i) When $\mathrm{Tr}_{2^{n}/2}(1+c^{-1})=0$ , we get $\mathrm{Tr}_{q/2}((c^{2}+1)/c^{2})=0$ and so $\alpha,\beta\in\mathbb{F}_{q}$ . For any $x$ , $y\in U_{q+1}$ ,

	$\displaystyle xyH_{1}(x,y)^{q}$	$\displaystyle=xy(xy+\alpha x+\beta y+1)^{q}$
		$\displaystyle=xy(x^{-1}y^{-1}+\alpha x^{-1}+\beta y^{-1}+1)$
		$\displaystyle=xy+\beta x+\alpha y+1$
		$\displaystyle=H_{2}(x,y)$

and so the roots of $H_{1}$ and $H_{2}$ are the same. For $x$ , $y\in U_{q+1}$ , if $H_{1}(x,y)\neq 0$ , then $H_{2}(x,y)\neq 0$ and so $x=y$ by Eq. 8.2, which implies that $g$ is $1$ -to- $1$ on $U_{2^{n}+1}$ . Thus we need only show that if $H_{1}(x,y)=0$ , then $x=y$ .

If $\beta\in U_{q+1}$ , then $\beta\in\mathbb{F}_{q}\cap U_{q+1}=\{1\}$ , i.e., $\beta=1$ . Since $\alpha+\beta=c$ and $\alpha\beta=c^{2}+1$ , we get $\alpha=c+1=c^{2}+1$ . Hence $c=1$ and so $\alpha=0$ . Then $H_{1}(x,y)=xy+y+1$ . If $H_{1}(x,y)=0$ , then $x\neq 1$ and $y=(x+1)^{-1}$ . By $y^{q}=y^{-1}$ , we get $x^{2}+x=1$ and so $y=(x+1)^{-1}=x$ .

If $\beta\notin U_{q+1}$ , then $x+\beta\neq 0$ for any $x\in U_{q+1}$ . If $H_{1}(x,y)=0$ , then $y=(\alpha x+1)/(x+\beta)$ and so

y^{q}=\Big{(}\frac{\alpha x+1}{x+\beta}\Big{)}^{q}=\frac{\alpha x^{-1}+1}{x^{-1}+\beta}=\frac{\alpha+x}{1+\beta x}.

By $y\in U_{q+1}$ and $\alpha+\beta=c\neq 0$ , we get the following equivalent statements:

	$\displaystyle y^{q}=y^{-1}~{}\Longleftrightarrow$	$\displaystyle~{}~{}\frac{\alpha+x}{1+\beta x}=\frac{x+\beta}{\alpha x+1}$
	$\displaystyle\Longleftrightarrow$	$\displaystyle~{}~{}(\alpha+\beta)x^{2}+(\alpha+\beta)^{2}x+(\alpha+\beta)=0$
	$\displaystyle\Longleftrightarrow$	$\displaystyle~{}~{}x^{2}+(\alpha+\beta)x+1=0$
	$\displaystyle\Longleftrightarrow$	$\displaystyle~{}~{}x=(\alpha x+1)/(x+\beta)=y.$

(ii) When $\mathrm{Tr}_{2^{n}/2}(1+c^{-1})=1$ , we have $\mathrm{Tr}_{q/2}((c^{2}+1)/c^{2})=1$ . Thus $Q$ is irreducible over $\mathbb{F}_{q}$ and so $\alpha,\beta\in\mathbb{F}_{q^{2}}\setminus\mathbb{F}_{q}$ with $\beta=\alpha^{q}$ . Since $\alpha^{q+1}=c^{2}+1$ and $c\neq 0$ , we get $\alpha,\alpha^{q}\notin U_{q+1}$ . Denote

y_{0}=x,\quad y_{1}=(\alpha x+1)/(x+\alpha^{q}),\quad y_{2}=(\alpha^{q}x+1)/(x+\alpha).

(8.3)

Then for any $x\in U_{q+1}$ ,

y_{1}^{q}=\Big{(}\frac{\alpha x+1}{x+\alpha^{q}}\Big{)}^{q}=\frac{x+\alpha^{q}}{\alpha x+1}=\frac{1}{y_{1}}

and $y_{2}^{q}=y_{2}^{-1}$ similarly. Thus $(x,y_{i})\in U_{q+1}\times U_{q+1}$ , $0\leq i\leq 2$ , are solutions of Eq. 8.2. Hence, $g$ is $3$ -to- $1$ on $U_{q+1}$ if and only if $y_{0}$ , $y_{1}$ , $y_{2}$ are distinct for any $x\in U_{q+1}$ except for $(q+1)\bmod{3}$ elements. By Eq. 8.3 and $\alpha+\alpha^{q}=c$ , it is easy to verify that $y_{i}=y_{j}$ for any $i\neq j\in\{0,1,2\}$ if and only if $x^{2}+cx+1=0$ .

If $n$ is odd, then $3\mid q+1$ and $\mathrm{Tr}_{q/2}(1)=1$ . Since $\mathrm{Tr}_{q/2}(1+c^{-1})=1$ , we get $\mathrm{Tr}_{q/2}(1/c)=0$ . By Lemma 8.6, $x^{2}+cx+1$ has two distinct roots $x_{0},x_{0}^{-1}$ in $\mathbb{F}_{q}\setminus\{0,1\}$ . Hence for any $x\in U_{q+1}$ , $x^{2}+cx+1\neq 0$ , and so $y_{0}$ , $y_{1}$ , $y_{2}$ are distinct. Thus $g$ is $3$ -to- $1$ on $U_{q+1}$ .

If $n$ is even, then $q+1\equiv 2\pmod{3}$ and $\mathrm{Tr}_{q/2}(1)=0$ . Since $\mathrm{Tr}_{q/2}(1+c^{-1})=1$ , we get $\mathrm{Tr}_{q/2}(1/c)=1$ . By Lemma 8.6, $x^{2}+cx+1$ has two distinct roots $x_{0},x_{0}^{-1}$ in $U_{q+1}\setminus\{1\}$ . Hence for any $x\in U_{q+1}\setminus\{x_{0},x_{0}^{-1}\}$ , $x^{2}+cx+1\neq 0$ , and so $y_{0}$ , $y_{1}$ , $y_{2}$ are distinct. Thus $g$ is $3$ -to- $1$ on $U_{q+1}$ . ∎

This result generalizes [47, Lemma 4.1] where $c=1$ and [4, Proposition 3.2 (ii)] where $n$ is even and $\mathrm{Tr}_{2^{n}/2}(1/c)=0$ . Moreover, it also implies the following result.

Corollary 8.9.

Let $g_{1}(x)=x(x^{3}+x+c)^{\frac{2^{n}-1}{3}}$ , where $c\in\mathbb{F}_{2^{n}}^{*}$ and $n$ is even. If $\mathrm{Tr}_{2^{n}/2}(1/c)=0$ , then $g_{1}$ is $1$ -to- $1$ on $U_{2^{n}+1}$ . If $\mathrm{Tr}_{2^{n}/2}(1/c)=1$ , then $g_{1}$ is $3$ -to- $1$ on $U_{2^{n}+1}$ .

Proof.

Let $q=2^{n}$ . For any $x\in U_{q+1}$ , $x^{q}=x^{-1}$ and so

\displaystyle x^{3}\circ g_{1}=\frac{x^{3}(x^{3}+x+c)^{q}}{x^{3}+x+c}=\frac{x^{3}(x^{-3}+x^{-1}+c)}{x^{3}+x+c}=\frac{cx^{3}+x^{2}+1}{x^{3}+x+c}.

(8.4)

If $\mathrm{Tr}_{q/2}(1/c)=0$ , then $x^{3}\circ g_{1}$ is $1$ -to- $1$ on $U_{q+1}$ by Lemma 8.8, and so $g_{1}$ is $1$ -to- $1$ on $U_{q+1}$ .

If $\mathrm{Tr}_{q/2}(1/c)=1$ , then $x^{2}+cx+c^{2}+1$ has two roots $\alpha,\alpha^{q}\in\mathbb{F}_{q^{2}}\setminus\mathbb{F}_{q}$ , where $\alpha+\alpha^{q}=c$ and $\alpha^{q+1}=c^{2}+1$ . Thus $\alpha,\alpha^{q}\notin U_{q+1}$ , $\alpha^{q}=\alpha+c$ , $\alpha^{2}=c\alpha+c^{2}+1$ , and $\alpha^{3}=\alpha\alpha^{2}=\alpha+c^{3}+c$ . Denote

y_{0}=x,\quad y_{1}=(\alpha x+1)/(x+\alpha^{q}),\quad y_{2}=(\alpha^{q}x+1)/(x+\alpha).

In the proof of Lemma 8.8, we have already shown that $y_{0},y_{1},y_{2}\in U_{q+1}$ and they are distinct for any $x\in U_{q+1}\setminus\{x_{0},x_{0}^{-1}\}$ , where $x_{0},x_{0}^{-1}\in U_{q+1}$ are the roots of $x^{2}+cx+1$ . To prove that $g_{1}$ is $3$ -to- $1$ on $U_{q+1}$ , we need only show $g_{1}(y_{0})=g_{1}(y_{1})=g_{1}(y_{2})$ for any $x\in U_{q+1}\setminus\{x_{0},x_{0}^{-1}\}$ . Indeed, for any $x\in U_{q+1}$ ,

	$\displaystyle g_{1}(y_{1})$	$\displaystyle=\frac{\alpha x+1}{x+\alpha^{q}}\Big{(}\Big{(}\frac{\alpha x+1}{x+\alpha^{q}}\Big{)}^{3}+\frac{\alpha x+1}{x+\alpha^{q}}+c\Big{)}^{\frac{q-1}{3}}$
		$\displaystyle=\frac{\alpha x+1}{(x+\alpha^{q})^{q}}\big{(}(\alpha x+1)^{3}+(\alpha x+1)(x+\alpha^{q})^{2}+c(x+\alpha^{q})^{3}\big{)}^{\frac{q-1}{3}}$
		$\displaystyle=\frac{\alpha x+1}{x^{q}+(\alpha+c)^{q}}\big{(}(\alpha x+1)^{3}+(\alpha x+1)(x+\alpha+c)^{2}+c(x+\alpha+c)^{3}\big{)}^{\frac{q-1}{3}}$
		$\displaystyle=\frac{\alpha x+1}{x^{-1}+\alpha}\big{(}(\alpha^{3}+\alpha+c)x^{3}+(\alpha^{3}+c\alpha^{2}+(c^{2}+1)\alpha+c^{3})x+c(\alpha+c)^{3}+(\alpha+c)^{2}+1\big{)}^{\frac{q-1}{3}}$
		$\displaystyle=x(c^{3}x^{3}+c^{3}x+c^{4})^{\frac{q-1}{3}}$
		$\displaystyle=x(x^{3}+x+c)^{\frac{q-1}{3}}$
		$\displaystyle=g_{1}(y_{0})$

and $g_{1}(y_{2})=g_{1}(y_{0})$ by a similar argument. ∎

Theorem 8.10.

Let $f(x)=x^{3q}+x^{q+2}+cx^{3}$ or $f(x)=cx^{3q}+x^{2q+1}+x^{3}$ , where $q=2^{n}$ with $n\geq 2$ and $c\in\mathbb{F}_{q}^{*}$ . Then $f$ is $1$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $n$ is odd and $\mathrm{Tr}_{q/2}(1/c)=1$ , and $f$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $\mathrm{Tr}_{q/2}(1/c)=0$ .

Proof.

Since the rational functions corresponding to these two polynomials are reciprocal to each other, we need only consider the first polynomial. Fix $h(x)=x^{3}+x+c$ . Then $f(x)=x^{3}h(x^{q-1})$ . Let $m_{1}=(3,q-1)$ and $g(x)=x^{3/m_{1}}h(x)^{(q-1)/m_{1}}$ . By Theorem 8.1, $f$ is $1$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}=1$ and $x^{3}h(x)^{q-1}$ is $1$ -to- $1$ on $U_{q+1}$ , i.e., $n$ is odd and $\mathrm{Tr}_{q/2}(1/c)=1$ by Eq. 8.4 and Lemma 8.8.

By Theorem 5.3, $f$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if (1) $m_{1}=1$ , $3\mid q+1$ , and $x^{3}h(x)^{q-1}$ is $3$ -to- $1$ on $U_{q+1}$ , or (2) $m_{1}=3$ and $xh(x)^{(q-1)/3}$ is $1$ -to- $1$ on $U_{q+1}$ . If $n$ is odd, then $m_{1}=1$ and $3\mid q+1$ . By Lemma 8.8, $x^{3}h(x)^{q-1}$ is $3$ -to- $1$ on $U_{q+1}$ if and only if $\mathrm{Tr}_{q/2}(1/c)=0$ . Thus $f$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $\mathrm{Tr}_{q/2}(1/c)=0$ . If $n$ is even, then $m_{1}=3$ . By Corollary 8.9, $xh(x)^{(q-1)/3}$ is $1$ -to- $1$ on $U_{q+1}$ if and only if $\mathrm{Tr}_{q/2}(1/c)=0$ . Thus $f$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $\mathrm{Tr}_{q/2}(1/c)=0$ . ∎

Remark 4.

All permutation polynomials of the form $x^{3q}+bx^{q+2}+cx^{3}$ and $cx^{3q}+bx^{2q+1}+x^{3}$ of $\mathbb{F}_{q^{2}}$ are classified in [36, 37], where $q$ is arbitrary and $b,c\in\mathbb{F}_{q}^{*}$ . The $1$ -to- $1$ part of Theorem 8.10 is the special case $b=1$ of [36, 37]. However, the $3$ -to- $1$ part of Theorem 8.10 is new and interesting.

We next use Theorems 8.2 and 8.10 to construct new $3$ -to- $1$ mappings.

Theorem 8.11.

Let $F(x)=x^{k(d-1)}h_{d}(x^{q-1})^{k}f(x)$ , where $k\in\mathbb{N}$ , $d$ is odd and $h_{d}$ is as in Eq. 7.1, $q=2^{n}$ with odd $n\geq 3$ , and $f$ is as in Theorem 8.10. Assume $(d,q+1)=1$ and $(3+k(d-1),q-1)=1$ . Then $F$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $\mathrm{Tr}_{q/2}(1/c)=0$ .

Proof.

Since $(d,q+1)=1$ and $d$ is odd, we get $(d,q(q+1))=1$ and so $h_{d}$ has no roots in $U_{q+1}$ by Lemma 7.7. Assume $t=d-1$ . Then $h_{d}(x)=x^{t}h_{d}(x)^{q}$ for any $x\in U_{q+1}$ . Because $n$ is odd, we have $(3,q-1)=1$ . Then the result follows from Theorems 8.2 and 8.10 ∎

8.3 New 5-to-1 rational function

Lemma 8.12.

Let $q=2^{n}$ with $n\geq 1$ and

g(x)=\frac{x^{4}+x+1}{x^{5}+x^{4}+x}.

If $n\equiv 2\pmod{4}$ , then $g$ is $5$ -to- $1$ on $U_{q+1}$ . If $n\not\equiv 2\pmod{4}$ , then $g$ is $1$ -to- $1$ on $U_{q+1}$ .

Proof.

By Lemma 8.3, $x(x^{4}+x^{3}+1)$ has no roots in $U_{q+1}$ . Hence for any $x$ , $y\in U_{q+1}$ , $g(x)=g(y)$ is equivalent to

(x^{4}+x+1)(y^{5}+y^{4}+y)=(x^{5}+x^{4}+x)(y^{4}+y+1).

(8.5)

[3, Page 8] states that Eq. 8.5 factors as

(x+y)\prod_{i=1}^{4}(xy+\omega^{2^{i-1}}x+\omega^{2^{i+1}}y+1)=0,

(8.6)

where $\omega$ is a primitive element of $\mathbb{F}_{16}$ such that $\omega^{4}+\omega+1=0$ . This factorization can be verified manually or by a computer program. Since $\mathrm{ord}(\omega^{2^{i+1}})=15$ and $q+1\not\equiv 0\pmod{15}$ , we get $\omega^{2^{i+1}}\notin U_{q+1}$ , and so $x+\omega^{2^{i+1}}\neq 0$ for any $x\in U_{q+1}$ , where $1\leq i\leq 4$ . Let

y_{0}=x\quad\text{and}\quad y_{i}=(\omega^{2^{i-1}}x+1)/(x+\omega^{2^{i+1}}),\quad 1\leq i\leq 4.

(8.7)

Then $(x,y_{i})\in U_{q+1}\times K$ , $0\leq i\leq 4$ , are solutions of Eq. 8.6, where $K$ is an extension field of $\mathbb{F}_{q^{2}}$ . Thus $g$ is $1$ -to- $1$ on $U_{q+1}$ if and only if Eq. 8.6 has no roots $(x,y)\in U_{q+1}^{2}$ with $x\neq y$ . When $5\mid q+1$ , $g$ is $5$ -to- $1$ on $U_{q+1}$ if and only if $y_{0}$ , $y_{1}$ , …, $y_{4}$ in $U_{q+1}$ and they are distinct for any $x\in U_{q+1}$ .

For $1\leq i\leq 4$ , a direct computation yields that $y_{i}^{q}=1/y_{i}$ if and only if $\alpha x^{2}+\beta x+\gamma=0$ , where

\alpha=\omega^{2^{i-1}}+\omega^{2^{i+1}q},\quad\beta=\omega^{2^{i-1}}\omega^{2^{i-1}q}+\omega^{2^{i+1}}\omega^{2^{i+1}q},\quad\gamma=\omega^{2^{i-1}q}+\omega^{2^{i+1}}.

Because

\omega^{2^{i-1}}+\omega^{2^{i+1}}=(\omega+\omega^{4})^{2^{i-1}}=1,

(8.8)

we have

	$\displaystyle\beta$	$\displaystyle=\omega^{2^{i-1}}(\omega^{2^{i+1}}+1)^{q}+(\omega^{2^{i-1}}+1)\omega^{2^{i+1}q}=\alpha,$
	$\displaystyle\gamma$	$\displaystyle=(\omega^{2^{i+1}}+1)^{q}+(\omega^{2^{i-1}}+1)=\alpha.$

Thus $y_{i}\in U_{q+1}$ if and only if $\alpha(x^{2}+x+1)=0$ . Since $\omega^{16}=\omega$ , $\alpha=0$ if and only if $n\equiv 2\pmod{4}$ .

If $n\equiv 2\pmod{4}$ , then $\alpha=0$ and so $y_{i}\in U_{q+1}$ for $1\leq i\leq 4$ . HenceEq. 8.6 has five solutions $y_{0}$ , $y_{1}$ , …, $y_{4}$ in $U_{q+1}$ for any $x\in U_{q+1}$ . (i) Assume $y_{i}=y_{0}$ for some $i\in\{1,2,3,4\}$ . By Eqs. 8.7 and 8.8, $y_{i}=y_{0}$ is equivalent to $x^{2}+x+1=0$ . Thus $x^{3}=1$ and $x\neq 1$ , a contradiction to that $U_{q+1}$ has no elements of order $3$ by $(3,q+1)=1$ . (ii) Assume $y_{i}=y_{j}$ for some $i\neq j\in\{1,2,3,4\}$ . By Eq. 8.7, $y_{i}=y_{j}$ is equivalent to

(\omega^{2^{i-1}}+\omega^{2^{j-1}})x^{2}+(\omega^{2^{i-1}}\omega^{2^{j+1}}+\omega^{2^{i+1}}\omega^{2^{j-1}})x+\omega^{2^{i+1}}+\omega^{2^{j+1}}=0,

(8.9)

Since $\mathrm{ord}(\omega)=15$ , $\omega^{2^{i-1}}\neq\omega^{2^{j-1}}$ for any $i\neq j\in\{1,2,3,4\}$ . By Eq. 8.8, $\omega^{2^{i+1}}=\omega^{2^{i-1}}+1$ . Hence Eq. 8.9 is equivalent to $x^{2}+x+1=0$ , a contradiction to that $U_{q+1}$ has no elements of order $3$ . Combining (i) and (ii), we see that $y_{0}$ , $y_{1}$ , …, $y_{4}$ are distinct. Note that $5\mid q+1$ . Therefore, $g$ is $5$ -to- $1$ on $U_{q+1}$ .

If $n\not\equiv 2\pmod{4}$ , then $\alpha\neq 0$ . Hence $y_{i}\in U_{q+1}$ for $i\in\{1,2,3,4\}$ if and only if $x^{2}+x+1=0$ . When $n\equiv 0\pmod{4}$ , we have $(3,q+1)=1$ , and so $U_{q+1}$ has no elements of order $3$ . Thus $y_{i}\notin U_{q+1}$ for any $i\in\{1,2,3,4\}$ , i.e., Eq. 8.6 has no roots $(x,y)\in U_{q+1}^{2}$ with $x\neq y$ . When $n\equiv 1,3\pmod{4}$ , we get $3\mid q+1$ , and so $U_{q+1}$ has two elements of order $3$ . Then $y_{i}\in U_{q+1}$ , i.e., $x^{2}+x+1=0$ , implies that

\omega^{2^{i-1}}x+1=\omega^{2^{i-1}}x+x+x^{2}=x(\omega^{2^{i+1}}+x),

i.e., $y_{i}=x$ for any $i\in\{1,2,3,4\}$ by Eq. 8.7. Hence Eq. 8.6 also has no roots $(x,y)\in U_{q+1}^{2}$ with $x\neq y$ . Therefore, $g$ is $1$ -to- $1$ on $U_{q+1}$ if $n\not\equiv 2\pmod{4}$ . ∎

Lemma 8.12 unifies some results in [16, 27, 24] which only consider the $1$ -to- $1$ property of $g$ under different conditions.

Theorem 8.13.

Let $f(x)=x^{4q-1}+x^{3q}+x^{3}$ , where $q=2^{n}$ with $n\geq 2$ . Then $f$ is $1$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $n$ is odd, and $f$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $n\equiv 0\pmod{4}$ .

Proof.

Fix $h(x)=x^{4}+x^{3}+1$ . Then $h$ has no roots in $U_{q+1}$ by Lemma 8.3 and $f(x)=x^{3}h(x^{q-1})$ . For any $x\in U_{q+1}$ , $x^{q}=x^{-1}$ and so

\displaystyle x^{3}h(x)^{q-1}=\frac{x^{3}(x^{4}+x^{3}+1)^{q}}{x^{4}+x^{3}+1}=\frac{x^{3}(x^{-4}+x^{-3}+1)}{x^{4}+x^{3}+1}=\frac{x^{4}+x+1}{x^{5}+x^{4}+x}.

Let $m_{1}=(3,q-1)$ and $g(x)=x^{3/m_{1}}h(x)^{(q-1)/m_{1}}$ . By Theorem 8.1, $f$ is $1$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}=1$ and $x^{3}h(x)^{q-1}$ is $1$ -to- $1$ on $U_{q+1}$ , i.e., $n$ is odd by Lemma 8.12.

Lemma 8.12 implies $x^{3}h(x)^{q-1}$ is not $3$ -to- $1$ on $U_{q+1}$ . Thus, by Theorem 5.3, $f$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}=3$ and $g_{1}(x)\coloneq xh(x)^{(q-1)/3}$ is $1$ -to- $1$ on $U_{q+1}$ . The condition $m_{1}=3$ is equivalent to $n$ is even. If $n\equiv 0\pmod{4}$ , then $x^{3}\circ g_{1}$ is $1$ -to- $1$ on $U_{q+1}$ by Lemma 8.12, and so $g_{1}$ is $1$ -to- $1$ on $U_{q+1}$ . If $n\equiv 2\pmod{4}$ , then $x^{3}\circ g_{1}$ is $5$ -to- $1$ on $U_{q+1}$ by Lemma 8.12. Since $g_{1}$ induces a map from $U_{q+1}$ to $U_{3(q+1)}$ and $x^{3}$ is a $3$ -to- $1$ map from $U_{3(q+1)}$ to $U_{q+1}$ , we have $g_{1}$ is not $1$ -to- $1$ on $U_{q+1}$ . Hence $f$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $n\equiv 0\pmod{4}$ . ∎

Theorem 8.14.

Let $f(x)=x^{4q+1}+x^{q+4}+x^{5}$ or $f(x)=x^{5q}+x^{4q+1}+x^{q+4}$ , where $q=2^{n}$ with $n\geq 1$ . If $n$ is odd, then $f$ is $1$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ . If $n$ is even, then $f$ is $5$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ .

Proof.

Since the rational functions corresponding to these two polynomials are reciprocal to each other, we need only consider the first polynomial. Fix $h(x)=x^{4}+x+1$ . Then $h$ has no roots in $U_{q+1}$ by Lemma 8.3 and $f(x)=x^{5}h(x^{q-1})$ . For any $x\in U_{q+1}$ , $x^{q}=x^{-1}$ and so

g(x)\coloneq x^{5}h(x)^{q-1}=\frac{x^{5}(x^{4}+x+1)^{q}}{x^{4}+x+1}=\frac{x^{5}(x^{-4}+x^{-1}+1)}{x^{4}+x+1}=\frac{x^{5}+x^{4}+x}{x^{4}+x+1}.

For any $y\in U_{q+1}$ , we get $y^{-1}\in U_{q+1}$ . Thus, by Lemma 8.12, $g$ is $5$ -to- $1$ on $U_{q+1}$ if $n\equiv 2\pmod{4}$ , and $g$ is $1$ -to- $1$ on $U_{q+1}$ if $n\not\equiv 2\pmod{4}$ .

If $n$ is odd, then $(5,q-1)=1$ and $g$ is $1$ -to- $1$ on $U_{q+1}$ . Thus $f$ is $1$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ by Theorem 8.1. If $n\equiv 2\pmod{4}$ , then $(5,q-1)=1$ , $5\mid q+1$ , and $g$ is $5$ -to- $1$ on $U_{q+1}$ . Hence $f$ is $5$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ by Theorem 8.1. If $n\equiv 0\pmod{4}$ , then $(5,q-1)=5$ . Let $g_{1}(x)\coloneq xh(x)^{(q-1)/5}$ . Then $x^{5}\circ g_{1}=g$ . Since $g$ is $1$ -to- $1$ on $U_{q+1}$ , we get $g_{1}$ is $1$ -to- $1$ on $U_{q+1}$ , and so $f$ is $5$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ by Theorem 8.1. ∎

We next use Theorems 8.2 and 8.14 to construct new $5$ -to- $1$ mappings.

Theorem 8.15.

Let $F(x)=x^{k(d-1)}h_{d}(x^{q-1})^{k}f(x)$ , where $k\in\mathbb{N}$ , $d$ is odd and $h_{d}$ is as in Eq. 7.1, $q=2^{n}$ with $n\equiv 2\pmod{4}$ , and $f$ is as in Theorem 8.14. If $(d,q+1)=1$ and $(5+k(d-1),q-1)=1$ , then $F$ is $5$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ .

The proof of this result is the same as that used in Theorem 8.11 and so is omitted. Applying Theorem 8.15 to $k=1$ and $d=3$ yields the following example.

Example 8.1.

Let $q=2^{n}$ with $n\equiv 2,10\pmod{12}$ and $f$ as in Theorem 8.14. Then $(x^{2q}+x^{q+1}+x^{2})f(x)$ is $5$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ .

9 The third problem

By employing Construction 2 again, the following result converts the second problem whether $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ to the third problem whether $\bar{g}$ is $(m_{2}/m_{3})$ -to- $1$ on $S$ .

Theorem 9.1.

Let $q-1=\ell s$ and $m_{1}=(r,s)$ , where $\ell,r,s\in\mathbb{N}$ . Let $f(x)=x^{r}h(x^{s})$ and $g(x)=x^{r_{1}}h(x)^{s_{1}}$ , where $r_{1}=r/m_{1}$ , $s_{1}=s/m_{1}$ , and $h\in\mathbb{F}_{q}[x]$ has no roots in $U_{\ell}$ . Let $S$ , $\bar{S}$ be finite sets and $\lambda\colon U_{\ell}\rightarrow S$ , $\bar{\lambda}\colon U_{\ell m_{1}}\rightarrow\bar{S}$ , $\bar{g}\colon S\rightarrow\bar{S}$ be mappings such that $\lambda$ is surjective and $\bar{\lambda}\circ g=\bar{g}\circ\lambda$ . That is, the following diagrams are commutative:

Suppose $\#\lambda^{-1}(\alpha)=m_{3}\,\#\bar{\lambda}^{-1}(\bar{g}(\alpha))$ and $g$ is $m_{3}$ -to- $1$ on $\lambda^{-1}(\alpha)$ for any $\alpha\in S$ and a fixed $m_{3}\in\mathbb{N}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $m_{1}m_{3}\mid m$ , $s(\ell\bmod{m_{2}})<m$ , $\bar{g}$ is $m/(m_{1}m_{3})$ -to- $1$ on $S$ , and

\sum_{\alpha\in E_{\bar{g}}(S)}\#\lambda^{-1}(\alpha)=\ell\bmod{m_{2}},

(9.1)

where $1\leq m\leq m_{1}m_{3}\,\#S$ , $m_{2}=m/m_{1}$ , and $E_{\bar{g}}(S)$ is the exceptional set of $\bar{g}$ being $m/(m_{1}m_{3})$ -to- $1$ on $S$ .

Proof.

By Theorem 4.3, $f$ is $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if and only if $m_{1}\mid m$ , $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ , and $s(\ell\bmod{m_{2}})<m$ , where $1\leq m\leq\ell m_{1}$ . Thus $f$ is not $m$ -to- $1$ on $\mathbb{F}_{q}^{*}$ if $1\leq m<m_{1}$ , i.e., the result holds when $1\leq m<m_{1}$ . Applying Construction 2 to the lower commutative diagram yields that $g$ is $m_{2}$ -to- $1$ on $U_{\ell}$ if and only if $m_{3}\mid m_{2}$ , $\bar{g}$ is $(m_{2}/m_{3})$ -to- $1$ on $S$ , and Eq. 9.1 holds, where $1\leq m_{2}\leq m_{3}\,\#S$ . Note that $m_{1}m_{3}\mid m$ is equivalent to $m_{1}\mid m$ and $m_{3}\mid m_{2}$ . Since $\lambda$ is surjective, we have

\ell=\#U_{\ell}=\sum_{\alpha\in S}\#\lambda^{-1}(\alpha)=\sum_{\alpha\in S}m_{3}\,\#\bar{\lambda}^{-1}(\bar{g}(\alpha))\geq m_{3}\,\#S.

The conditions $1\leq m\leq\ell m_{1}$ and $1\leq m_{2}\leq m_{3}\,\#S$ imply that $m_{1}\leq m\leq m_{1}m_{3}\,\#S$ . Thus the result holds when $m_{1}\leq m\leq m_{1}m_{3}\,\#S$ . This completes the proof. ∎

To simplify the construction of commutative diagrams, assume $f(x)=x^{r}H(x^{q-1})^{m_{1}}\in\mathbb{F}_{q^{2}}[x]$ , where $m_{1}=(r,q-1)$ . Then $g(x)=x^{r/m_{1}}H(x)^{q-1}$ and it maps $U_{q+1}$ to $U_{q+1}$ . To simplify the third question, we mainly consider the following cases:

\edefnn(1)

$\lambda$ and $\bar{\lambda}$ are $1$ -to- $1$ from $U_{q+1}$ to $U_{q+1}$ and $\bar{g}=x^{n}$ ;
\edefnn(2)

$\lambda$ and $\bar{\lambda}$ are $1$ -to- $1$ from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ and $\bar{g}=x^{n}$ .

9.1 $\lambda$ is $1$ -to- $1$ from $U_{q+1}$ to itself

Theorem 9.2.

Let $L_{1},L_{2},M_{1},M_{2}\in\mathbb{F}_{q^{2}}[x]$ satisfy that $M_{i}$ has no roots in $U_{q+1}$ , $L_{i}=\varepsilon_{i}x^{t_{i}}M_{i}^{q}$ for any $x\in U_{q+1}$ , and $L_{i}/M_{i}$ permutes $U_{q+1}$ , where $\varepsilon_{i}\in U_{q+1}$ and $t_{i}\geq\deg(M_{i})$ . Let

H=M_{1}^{nt_{2}}\big{(}M_{2}\circ x^{n}\circ L_{1}/M_{1}\big{)}\quad\text{and}\quad f=x^{r}H(x^{q-1})^{m_{1}},

where $n,r\in\mathbb{N}$ , $m_{1}=(r,q-1)$ and $r/m_{1}\equiv nt_{1}t_{2}\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ and $(n,q+1)=m/m_{1}$ , where $1\leq m\leq m_{1}(q+1)$ .

Proof.

Since $M_{1}$ and $M_{2}$ have no roots in $U_{q+1}$ and $L_{1}/M_{1}$ permutes $U_{q+1}$ , it follows that $H$ has no roots in $U_{q+1}$ . Let $M_{2}=\textstyle{\sum}\,a_{j}x^{j}\in\mathbb{F}_{q^{2}}[x]$ . Then

H=M_{1}^{nt_{2}}\big{(}\textstyle{\sum}\,a_{j}x^{j}\circ x^{n}\circ L_{1}/M_{1}\big{)}=M_{1}^{nt_{2}}\textstyle{\sum}\,a_{j}(L_{1}/M_{1})^{nj}=\textstyle{\sum}\,a_{j}L_{1}^{nj}M_{1}^{n(t_{2}-j)}.

For $x\in U_{q+1}$ , $L_{i}=\varepsilon_{i}x^{t_{i}}M_{i}^{q}$ implies that $L_{1}^{q}=\varepsilon_{1}^{-1}x^{-t_{1}}M_{1}$ and $\varepsilon_{2}^{-1}L_{2}=x^{t_{2}}M_{2}^{q}=\textstyle{\sum}\,a_{j}^{q}x^{t_{2}-j}$ . Thus

	$\displaystyle H^{q}$	$\displaystyle=\textstyle{\sum}\,a_{j}^{q}(L_{1}^{q})^{nj}(M_{1}^{q})^{n(t_{2}-j)}$
		$\displaystyle=\textstyle{\sum}\,a_{j}^{q}(\varepsilon_{1}^{-1}x^{-t_{1}}M_{1})^{nj}(\varepsilon_{1}^{-1}x^{-t_{1}}L_{1})^{n(t_{2}-j)}$
		$\displaystyle=(\varepsilon_{1}^{-1}x^{-t_{1}})^{nt_{2}}\textstyle{\sum}\,a_{j}^{q}M_{1}^{nj}L_{1}^{n(t_{2}-j)}$
		$\displaystyle=(\varepsilon_{1}^{-1}x^{-t_{1}})^{nt_{2}}M_{1}^{nt_{2}}\textstyle{\sum}\,a_{j}^{q}(L_{1}/M_{1})^{n(t_{2}-j)}$
		$\displaystyle=\varepsilon_{1}^{-nt_{2}}x^{-nt_{1}t_{2}}M_{1}^{nt_{2}}\big{(}\textstyle{\sum}\,a_{j}^{q}x^{t_{2}-j}\circ(L_{1}/M_{1})^{n}\big{)}$
		$\displaystyle=\varepsilon_{1}^{-nt_{2}}x^{-nt_{1}t_{2}}M_{1}^{nt_{2}}\big{(}\varepsilon_{2}^{-1}L_{2}\circ L_{1}^{n}/M_{1}^{n}\big{)}$
		$\displaystyle=x^{-nt_{1}t_{2}}M_{1}^{nt_{2}}\big{(}\beta L_{2}\circ L_{1}^{n}/M_{1}^{n}\big{)},$

where $\beta=\varepsilon_{1}^{-nt_{2}}\varepsilon_{2}^{-1}$ . For $x\in U_{q+1}$ , $x^{r/m_{1}}=x^{nt_{1}t_{2}}$ by $r/m_{1}\equiv nt_{1}t_{2}\pmod{q+1}$ , and so

\displaystyle g(x)\coloneq x^{r/m_{1}}H^{q}/H=\frac{\beta L_{2}\circ L_{1}^{n}/M_{1}^{n}}{M_{2}\circ L_{1}^{n}/M_{1}^{n}}=\beta L_{2}/M_{2}\circ x^{n}\circ L_{1}/M_{1}.

Since $\beta L_{2}/M_{2}$ permutes $U_{q+1}$ , we get

(\beta L_{2}/M_{2})^{-1}\circ g=x^{n}\circ L_{1}/M_{1}.

Note that $f(x)\in U_{\frac{q^{2}-1}{m_{1}}}$ for $x\in\mathbb{F}_{q^{2}}^{*}$ and $g(x)\in U_{q+1}$ for $x\in U_{q+1}$ . Thus the following diagrams are commutative:

Let $\lambda=L_{1}/M_{1}$ and $\bar{\lambda}=(\beta L_{2}/M_{2})^{-1}$ . Since both $\lambda$ and $\bar{\lambda}$ permute $U_{q+1}$ , $\#\lambda^{-1}(\alpha)=\#\bar{\lambda}^{-1}(\alpha^{n})$ and $g$ is $1$ -to- $1$ on $\lambda^{-1}(\alpha)$ for any $\alpha\in U_{q+1}$ . By Theorem 9.1, $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ , $(q-1)((q+1)\bmod{m_{2}})<m$ , and $x^{n}$ is $m_{2}$ -to- $1$ on $U_{q+1}$ , or equivalently $m_{1}\mid m$ and $(n,q+1)=m_{2}$ , where $1\leq m\leq m_{1}(q+1)$ and $m_{2}=m/m_{1}$ . ∎

The conditions in Theorem 9.2 can be satisfied. Indeed, all the desired polynomials $L_{i}$ and $M_{i}$ are completely determined in [51, Lemma 2.1] and [5, Proposition 3.5] when $\deg(L_{i})=\deg(M_{i})=t_{i}\in\{1,2\}$ . The next result is a reformulation of [51, Lemma 2.1].

Lemma 9.3.

Let $\ell(x)\in\overline{\mathbb{F}}_{q}(x)$ be a degree-one rational function, where $\overline{\mathbb{F}}_{q}$ is the algebraic closure of $\mathbb{F}_{q}$ . Then $\ell(x)$ permutes $U_{q+1}$ if and only if $\ell(x)=(\beta^{q}x+\alpha^{q})/(\alpha x+\beta)$ , where $\alpha$ , $\beta\in\mathbb{F}_{q^{2}}$ and $\alpha^{q+1}\neq\beta^{q+1}$ .

Theorem 9.2 reduces to the following form when $L_{2}=\beta^{q}x+\alpha^{q}$ and $M_{2}=\alpha x+\beta$ .

Corollary 9.4.

Let $L$ , $M\in\mathbb{F}_{q^{2}}[x]$ satisfy that $M$ has no roots in $U_{q+1}$ , $L=\varepsilon x^{t}M^{q}$ for any $x\in U_{q+1}$ , and $L/M$ permutes $U_{q+1}$ , where $\varepsilon\in U_{q+1}$ and $t\geq\deg(M)$ . Let

H=\alpha L^{n}+\beta M^{n}\quad\text{and}\quad f(x)=x^{r}H(x^{q-1})^{m_{1}},

where $n\geq 1$ , $\alpha$ , $\beta\in\mathbb{F}_{q^{2}}$ with $\alpha^{q+1}\neq\beta^{q+1}$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv nt\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ and $(n,q+1)=m/m_{1}$ , where $1\leq m\leq m_{1}(q+1)$ .

Proof.

Take $M_{2}=\alpha x+\beta$ , $\varepsilon_{2}=t_{2}=1$ , and $L_{2}=\beta^{q}x+\alpha^{q}$ . Then $M_{2}$ has no roots in $U_{q+1}$ by $\alpha^{q+1}\neq\beta^{q+1}$ , $L_{2}/M_{2}$ permutes $U_{q+1}$ by Lemma 9.3, and $H=M_{1}^{n}(M_{2}\circ L_{1}^{n}/M_{1}^{n})=\alpha L_{1}^{n}+\beta M_{1}^{n}$ . Then the result follows from Theorem 9.2. ∎

Remark 5.

In the case $\deg(L)=\deg(M)=t$ and $m_{1}=m=1$ , Corollary 9.4 is equivalent to [5, Theorem 3.3]. In other cases, Corollary 9.4 generalizes [5, Theorem 3.3]. Moreover, the proof of [5, Theorem 3.3] mainly takes advantage of some properties of “ $\beta$ -associated polynomials”, while Corollary 9.4 is based on the commutative diagrams in the proof of Theorem 9.2.

In Corollary 9.4, take $M=\gamma x+\delta$ , $\varepsilon=t=1$ , and $L=\delta^{q}x+\gamma^{q}$ , where $\gamma^{q+1}\neq\delta^{q+1}$ . Then $L/M$ permutes $U_{q+1}$ by Lemma 9.3, and so we obtain the next result.

Example 9.1.

Let $\alpha$ , $\beta$ , $\gamma$ , $\delta\in\mathbb{F}_{q^{2}}$ satisfy $\alpha^{q+1}\neq\beta^{q+1}$ and $\gamma^{q+1}\neq\delta^{q+1}$ . Let

H(x)=\alpha(\delta^{q}x+\gamma^{q})^{n}+\beta(\gamma x+\delta)^{n}\quad\text{and}\quad f(x)=x^{r}H(x^{q-1})^{m_{1}},

where $n,r\geq 1$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv n\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ and $(n,q+1)=m/m_{1}$ , where $1\leq m\leq m_{1}(q+1)$ .

Remark 6.

In the case $\alpha\beta\gamma\delta\neq 0$ and $m_{1}=m=1$ , Example 9.1 is equivalent to [12, Theorem 1.2], which generalizes some recent results in the literature.

In Corollary 9.4, take $M=x^{4}+x+1$ , $\varepsilon=1$ , $t=5$ , and $L=x^{5}+x^{4}+x$ . If $q=2^{s}$ with $s\not\equiv 2\pmod{4}$ , then $L/M$ permutes $U_{q+1}$ by Lemma 8.12, and so we have the following result.

Example 9.2.

Let $q=2^{s}$ with $s\not\equiv 2\pmod{4}$ and $\alpha$ , $\beta\in\mathbb{F}_{q^{2}}$ with $\alpha^{q+1}\neq\beta^{q+1}$ . Let

H(x)=\alpha(x^{5}+x^{4}+x)^{n}+\beta(x^{4}+x+1)^{n}\quad\text{and}\quad f(x)=x^{r}H(x^{q-1})^{m_{1}},

where $n\geq 1$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv 5n\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ and $(n,q+1)=m/m_{1}$ , where $1\leq m\leq m_{1}(q+1)$ .

Theorem 9.2 reduces to the next result when $L_{2}=cx^{3}+x^{2}+1$ and $M_{2}=x^{3}+x+c$ .

Corollary 9.5.

Let $q$ be even and $L$ , $M\in\mathbb{F}_{q^{2}}[x]$ satisfy that $M$ has no roots in $U_{q+1}$ , $L=\varepsilon x^{t}M^{q}$ for any $x\in U_{q+1}$ , and $L/M$ permutes $U_{q+1}$ , where $\varepsilon\in U_{q+1}$ and $t\geq\deg(M)$ . Let

H=L^{3n}+L^{n}M^{2n}+cM^{3n}\quad\text{and}\quad f(x)=x^{r}H(x^{q-1})^{m_{1}},

where $n\geq 1$ , $c\in\mathbb{F}_{q}^{*}$ with $\mathrm{Tr}_{q/2}(1+c^{-1})=0$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv 3nt\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ and $(n,q+1)=m/m_{1}$ , where $1\leq m\leq m_{1}(q+1)$ .

Proof.

Take $M_{2}=x^{3}+x+c$ , $\varepsilon_{2}=1$ , $t_{2}=3$ , and $L_{2}=cx^{3}+x^{2}+1$ . Then $L_{2}/M_{2}$ permutes $U_{q+1}$ by Lemma 8.8 and $H=M_{1}^{3n}(M_{2}\circ L_{1}^{n}/M_{1}^{n})=L_{1}^{3n}+L_{1}^{n}M_{1}^{2n}+cM_{1}^{3n}$ . Now the result follows from Theorem 9.2. ∎

In Corollary 9.5, taking $L=\beta^{q}x+\alpha^{q}$ and $M=\alpha x+\beta$ yields the next result.

Example 9.3.

Let $q$ be even and $\alpha$ , $\beta\in\mathbb{F}_{q^{2}}$ with $\alpha^{q+1}\neq\beta^{q+1}$ . Let

H(x)=(\beta^{q}x+\alpha^{q})^{3n}+(\beta^{q}x+\alpha^{q})^{n}(\alpha x+\beta)^{2n}+c(\alpha x+\beta)^{3n}

and $f(x)=x^{r}H(x^{q-1})^{m_{1}}$ , where $n\geq 1$ , $c\in\mathbb{F}_{q}^{*}$ with $\mathrm{Tr}_{q/2}(1+c^{-1})=0$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv 3n\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ and $(n,q+1)=m/m_{1}$ , where $1\leq m\leq m_{1}(q+1)$ .

9.2 $\lambda$ is $1$ -to- $1$ from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$

For arbitrary $L$ , $M\in\mathbb{F}_{q^{2}}[x]$ , define $L(c)/M(c)=\infty$ if $L(c)\neq 0$ and $M(c)=0$ for some $c\in\mathbb{F}_{q^{2}}$ . When $L\neq 0$ and $M\neq 0$ , we define

\frac{L(\infty)}{M(\infty)}=\begin{cases}\infty&\text{if $\deg(L)>\deg(M)$,}\\ a/b&\text{if $\deg(L)=\deg(M)$,}\\ 0&\text{if $\deg(L)<\deg(M)$,}\end{cases}

where $a$ and $b$ are the leading coefficients of $L$ and $M$ , respectively. In particular, $\infty^{n}=\infty$ for any $n\in\mathbb{N}$ . For arbitrary $N(x)\coloneq\sum_{i=0}^{u}a_{i}x^{i}\in\mathbb{F}_{q^{2}}[x]$ , define $N^{(q)}(x)=\sum_{i=0}^{u}a_{i}^{q}x^{i}$ .

Theorem 9.6.

Let $L$ , $M\in\mathbb{F}_{q^{2}}[x]$ satisfy that $L=\varepsilon x^{t}L^{q}$ and $M=\varepsilon x^{t}M^{q}$ for any $x\in U_{q+1}$ and that $L/M$ induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ , where $\varepsilon\in U_{q+1}$ and $t\geq\max\{\deg(L),\deg(M)\}$ . Let $N\in\mathbb{F}_{q^{2}}[x]$ satisfy that $N^{(q)}/N$ induces a bijection from $\mathbb{F}_{q}\cup\{\infty\}$ to $U_{q+1}$ . Let

H=M^{nu}\big{(}N\circ x^{n}\circ L/M\big{)}\quad\text{and}\quad f=x^{r}H(x^{q-1})^{m_{1}},

where $n,r\in\mathbb{N}$ , $u=\deg(N)$ , $H$ has no roots in $U_{q+1}$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv ntu\pmod{q+1}$ . Then, for $1\leq m\leq m_{1}(q+1)$ , $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if one of the following holds:

\edefitn(1)

$m=m_{1}$ and $(n,q-1)=1$ ;
\edefitn(2)

$m_{1}\mid m$ , $(n,q-1)=m/m_{1}\geq 3$ , and $2(q-1)<m$ .

Proof.

Put $N=\sum_{i=0}^{u}a_{i}x^{i}\in\mathbb{F}_{q^{2}}[x]$ . Then

H=M^{nu}(\sum a_{i}x^{i}\circ x^{n}\circ L/M)=\sum a_{i}L^{ni}M^{n(u-i)}

and for any $x\in U_{q+1}$ ,

	$\displaystyle H^{q}$	$\displaystyle=\sum a_{i}^{q}L^{qni}M^{qn(u-i)}$
		$\displaystyle=\sum a_{i}^{q}(\varepsilon^{-1}x^{-t}L)^{ni}(\varepsilon^{-1}x^{-t}M)^{n(u-i)}$
		$\displaystyle=(\varepsilon^{-1}x^{-t})^{nu}\sum a_{i}^{q}L^{ni}M^{n(u-i)}.$

Define $g(x)=x^{r/m_{1}}H^{q-1}$ . The condition $r/m_{1}\equiv ntu\pmod{q+1}$ implies $x^{r/m_{1}}=x^{ntu}$ for any $x\in U_{q+1}$ . Recall that $H$ has no roots in $U_{q+1}$ . Thus, for any $x\in U_{q+1}$ ,

g(x)=x^{r/m_{1}}H^{q}/H=\frac{\beta\sum_{i=0}^{u}a_{i}^{q}L^{ni}M^{n(u-i)}}{~{}\sum_{i=0}^{u}a_{i}L^{ni}M^{n(u-i)}},

(9.2)

where $\beta=\varepsilon^{-nu}$ . If $M(x)\neq 0$ for some $x\in U_{q+1}$ , then

\displaystyle g(x)=\frac{\beta\sum a_{i}^{q}(L/M)^{ni}}{~{}\sum a_{i}(L/M)^{ni}}=\frac{\beta N^{(q)}\circ(L/M)^{n}}{N\circ(L/M)^{n}}=\beta N^{(q)}/N\circ x^{n}\circ L/M.

(9.3)

If $M(x_{0})=0$ for some $x_{0}\in U_{q+1}$ , then $x_{0}$ is unique and $L(x_{0})\neq 0$ , since $L/M$ induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ . Hence, by Eq. 9.2,

g(x_{0})=\beta a_{u}^{q}L(x_{0})^{nu}/a_{u}L(x_{0})^{nu}=\beta a_{u}^{q}/a_{u}.

Because $L(x_{0})\neq 0$ and $M(x_{0})=0$ , we get $L(x_{0})/M(x_{0})=\infty$ and $\infty^{n}=\infty$ . Thus

\beta N^{(q)}/N\circ x^{n}\circ L(x_{0})/M(x_{0})=\beta N^{(q)}(\infty)/N(\infty)=\beta a_{u}^{q}/a_{u}.

In summary, Eq. 9.3 holds for any $x\in U_{q+1}$ . Since $\beta N^{(q)}/N$ induces a bijection from $\mathbb{F}_{q}\cup\{\infty\}$ to $U_{q+1}$ ,

(\beta N^{(q)}/N)^{-1}\circ g=x^{n}\circ L/M.

Note that $f(x)\in U_{\frac{q^{2}-1}{m_{1}}}$ for $x\in\mathbb{F}_{q^{2}}^{*}$ and $g(x)\in U_{q+1}$ for $x\in U_{q+1}$ . Thus the following diagrams are commutative:

Let $\lambda=L/M$ and $\bar{\lambda}=(\beta N^{(q)}/N)^{-1}$ . Since both $\lambda$ and $\bar{\lambda}$ are bijective, $\#\lambda^{-1}(\alpha)=\#\bar{\lambda}^{-1}(\alpha^{n})=1$ and $g$ is $1$ -to- $1$ on $\lambda^{-1}(\alpha)$ for any $\alpha\in\mathbb{F}_{q}\cup\{\infty\}$ . By Theorem 9.1, for $1\leq m\leq m_{1}(q+1)$ , $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m_{1}\mid m$ , $(q-1)((q+1)\bmod{m_{2}})<m$ , $x^{n}$ is $m_{2}$ -to- $1$ on $\mathbb{F}_{q}\cup\{\infty\}$ , and

\#E_{x^{n}}(\mathbb{F}_{q}\cup\{\infty\})=(q+1)\bmod{m_{2}},

where $m_{2}=m/m_{1}$ .

Under the condition $m_{1}\mid m$ , if $m_{2}=1$ , then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $(n,q-1)=1$ . If $m_{2}=2$ , then $x^{n}$ only maps 0 to 0 and $\infty$ to $\infty$ . Hence $x^{n}$ is not $2$ -to- $1$ on $\mathbb{F}_{q}\cup\{\infty\}$ , and so $f$ is not $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ . If $m_{2}\geq 3$ , then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $(q-1)((q+1)\bmod{m_{2}})<m$ and $(n,q-1)=m_{2}$ , i.e., $(n,q-1)=m_{2}$ and $2(q-1)<m$ . ∎

Remark 7.

The idea of Theorem 9.6 comes from [5]. In the case $t=\deg(L)=\deg(M)$ and $m_{1}=m=1$ , Theorem 9.6 is similar to [5, Theorem 5.1]. In other cases, Theorem 9.6 generalizes [5, Theorem 5.1].

All degree-one rational functions over $\mathbb{F}_{q^{2}}$ that are bijections from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ are completely determined in [51, Lemma 3.1], which can be reformulated as follows.

Lemma 9.7.

Let $\ell(x)\in\overline{\mathbb{F}}_{q}(x)$ be a degree-one rational function, where $\overline{\mathbb{F}}_{q}$ is the algebraic closure of $\mathbb{F}_{q}$ . Then $\ell(x)$ induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ if and only if $\ell(x)=(\beta x+\beta^{q})/(\alpha x+\alpha^{q})$ , where $\alpha$ , $\beta\in\mathbb{F}_{q^{2}}^{*}$ and $\alpha^{q-1}\neq\beta^{q-1}$ .

Theorem 9.6 reduces to the following form when $N=\alpha x+\beta$ .

Corollary 9.8.

H=\alpha L^{n}+\beta M^{n}\quad\text{and}\quad f=x^{r}H(x^{q-1})^{m_{1}},

where $n\geq 1$ , $\alpha$ , $\beta\in\mathbb{F}_{q^{2}}^{*}$ with $\alpha^{q-1}\neq\beta^{q-1}$ , $H$ has no roots in $U_{q+1}$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv nt\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m=m_{1}$ and $(n,q-1)=1$ , where $1\leq m\leq\min\{2(q-1),m_{1}(q+1)\}$ .

Proof.

Let $\ell(x)=(\beta x+\beta^{q})/(-\alpha x-\alpha^{q})$ . Then it induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ by Lemma 9.7, and its compositional inverse is $\ell^{-1}(x)=-(\alpha^{q}x+\beta^{q})/(\alpha x+\beta)$ , which induces a bijection from $\mathbb{F}_{q}\cup\{\infty\}$ to $U_{q+1}$ . In Theorem 9.6, take $N=\alpha x+\beta$ . Then $N^{(q)}=\alpha^{q}x+\beta^{q}$ and $H=M^{n}(N\circ L^{n}/M^{n})=\alpha L^{n}+\beta M^{n}$ . Now the result follows from Theorem 9.6. ∎

Substituting the rational function in Lemma 9.7 to Corollary 9.8 yields the next result.

Example 9.4.

Let $\alpha$ , $\beta$ , $\gamma$ , $\delta\in\mathbb{F}_{q^{2}}^{*}$ satisfy $\alpha^{q-1}\neq\beta^{q-1}$ and $\gamma^{q-1}\neq\delta^{q-1}$ . Let

H(x)=\alpha(\gamma x+\gamma^{q})^{n}+\beta(\delta x+\delta^{q})^{n}\quad\text{and}\quad f=x^{r}H(x^{q-1})^{m_{1}},

where $n$ , $r\geq 1$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv n\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m=m_{1}$ and $(n,q-1)=1$ , where $1\leq m\leq\min\{2(q-1),m_{1}(q+1)\}$ .

Proof.

Take $L=\gamma x+\gamma^{q}$ and $M=\delta x+\delta^{q}$ . Then $L/M$ induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ by Lemma 9.7, and $\alpha L(x)^{n}+\beta M(x)^{n}$ has no roots in $U_{q+1}$ . Indeed, if $\alpha L(x_{0})^{n}=-\beta M(x_{0})^{n}$ for some $x_{0}\in U_{q+1}$ , then $L(x_{0})\neq 0$ and $M(x_{0})\neq 0$ by $\alpha\beta\neq 0$ and $\gamma^{q-1}\neq\delta^{q-1}$ . Thus $-\beta/\alpha=(L(x_{0})/M(x_{0}))^{n}\in\mathbb{F}_{q}^{*}$ , contrary to $\alpha^{q-1}\neq\beta^{q-1}$ . Then the result follows from Corollary 9.8. ∎

Remark 8.

In the case $m_{1}=m=1$ , Example 9.4 is equivalent to [12, Theorem 1.1] which generalizes some results in the literature. In other cases, Example 9.4 is a generalization of [12, Theorem 1.1].

Remark 9.

Theorems 8.10 and 8.14 are special cases of Examples 9.1 and 9.4 when $(r,q-1)=1$ . We first give another proof of Lemma 8.8 by a compositional decomposition of $g$ . Let $q=2^{k}$ and $g$ as in Lemma 8.8. Let $a\in\mathbb{F}_{q^{2}}$ be a solution of $x^{2}+cx+1=0$ and $\lambda(x)=(x+a)/(ax+1)$ . Then the compositional inverse of $\lambda$ is itself. By $a^{2}=ac+1$ and $a^{3}=a^{2}c+a$ , it is easy to verify that $\lambda\circ g=x^{3}\circ\lambda$ , i.e., $g=\lambda\circ x^{3}\circ\lambda$ . For any $x\in U_{q+1}$ , $g(x)^{q}=g(x)^{-1}$ and so $g$ maps $U_{q+1}$ to itself. Hence the following diagram is commutative:

If $\mathrm{Tr}_{q/2}(1/c)=0$ , then $a\in\mathbb{F}_{q}\setminus\{0,1\}$ by Corollary 8.7, and so $a^{q+1}=a^{2}\neq 1$ . By Lemma 9.3, $\lambda$ permutes $U_{q+1}$ and so $\lambda(U_{q+1})=U_{q+1}$ . When $k$ is odd, $(3,q+1)=3$ and so $x^{3}$ is $3$ -to- $1$ on $U_{q+1}$ . Thus $g$ is $3$ -to- $1$ on $U_{q+1}$ . When $k$ is even, $(3,q+1)=1$ and so $x^{3}$ is $1$ -to- $1$ on $U_{q+1}$ . Thus $g$ is $1$ -to- $1$ on $U_{q+1}$ . If $\mathrm{Tr}_{q/2}(1/c)=1$ , then $a\in U_{q+1}\setminus\{1\}$ by Corollary 8.7, and so $a=e^{q-1}$ for some $e\in\mathbb{F}_{q^{2}}^{*}$ . Then

\lambda(x)=\frac{ex+ea}{eax+e}=\frac{ex+e^{q}}{e^{q}x+e}

and $e^{q(q-1)}\neq e^{q-1}$ . Then by Lemma 9.7, $\lambda$ induces a bijection from $U_{q+1}$ onto $\mathbb{F}_{q}\cup\{\infty\}$ , and so $\lambda(U_{q+1})=\mathbb{F}_{q}\cup\{\infty\}$ . When $k$ is odd, $(3,q-1)=1$ and so $x^{3}$ permutes $\mathbb{F}_{q}\cup\{\infty\}$ . Thus $g$ is $1$ -to- $1$ on $U_{q+1}$ . When $k$ is even, $(3,q-1)=3$ and so $x^{3}$ is $3$ -to- $1$ form $\mathbb{F}_{q}\cup\{\infty\}$ from to itself. Thus $g$ is $3$ -to- $1$ on $U_{q+1}$ . This completes the proof of Lemma 8.8.

In Example 9.1, take $q=2^{k}$ with $k$ odd, $r=n=3$ , $\alpha=\gamma=a$ , and $\beta=\delta=1$ . Then $(r,q-1)=1$ and $H(x)=a^{2}c(x^{3}+x+c)$ . Thus $f(x)=x^{r}H(x^{q-1})$ is $3$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ by $(n,q+1)=3$ . That is, Theorem 8.10 is a special case of Example 9.1 if $(r,q-1)=1$ and $\mathrm{Tr}_{q/2}(1/c)=0$ .

In Example 9.4, take $q=2^{k}$ with $k$ odd, $r=n=3$ , $\alpha=\delta=ea$ , and $\beta=\gamma=e$ . Then $(r,q-1)=1$ and $H(x)=e^{4}a^{2}c(x^{3}+x+c)$ . Thus $f(x)=x^{r}H(x^{q-1})$ is $1$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ by $(n,q-1)=1$ . That is, Theorem 8.10 is a special case of Example 9.4 if $(r,q-1)=1$ and $\mathrm{Tr}_{q/2}(1/c)=1$ .

In the above analysis, taking $c=1$ and replacing $3$ by $5$ yields another proof of Lemma 8.12. Hence Theorem 8.14 is also a special case of Examples 9.1 and 9.4 if $(5,q-1)=1$ .

We next construct a class of rational functions from $\mathbb{F}_{q}\cup\{\infty\}$ to $U_{q+1}$ by the composition of monomials and degree-one rational functions. Take $\alpha$ , $\beta\in\mathbb{F}_{q^{2}}^{*}$ with $\alpha^{q-1}\neq\beta^{q-1}$ and

\ell_{2}(x)=-x\circ\frac{\beta x+\beta^{q}}{\alpha x+\alpha^{q}}\circ-x=\frac{\beta x-\beta^{q}}{-\alpha x+\alpha^{q}}.

By Lemma 9.7, $\ell_{2}$ induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ . Then its compositional inverse is $\ell_{2}^{-1}(x)=(\alpha^{q}x+\beta^{q})/(\alpha x+\beta)$ , which induces a bijection from $\mathbb{F}_{q}\cup\{\infty\}$ to $U_{q+1}$ . Let $k\in\mathbb{N}$ and $(k,q+1)=1$ . Then $x^{k}$ permutes $U_{q+1}$ . Pick $\ell_{1}(x)=(\gamma^{q}x+\delta^{q})/(\delta x+\gamma)$ , where $\gamma,\delta\in\mathbb{F}_{q^{2}}$ with $\gamma^{q+1}\neq\delta^{q+1}$ . Then $\ell_{1}$ permutes $U_{q+1}$ by Lemma 9.3. Let

\displaystyle\lambda_{k}(x)

\displaystyle=\ell_{1}\circ x^{k}\circ\ell_{2}^{-1}=\frac{\gamma^{q}(\alpha^{q}x+\beta^{q})^{k}+\delta^{q}(\alpha x+\beta)^{k}}{\gamma(\alpha x+\beta)^{k}+\delta(\alpha^{q}x+\beta^{q})^{k}},

i.e., the following diagram is commutative:

Then $\lambda_{k}$ induces a bijection from $\mathbb{F}_{q}\cup\{\infty\}$ to $U_{q+1}$ . Applying Theorem 9.6 to $N=\gamma(\alpha x+\beta)^{k}+\delta(\alpha^{q}x+\beta^{q})^{k}$ yields the following result.

Corollary 9.9.

Let $L$ , $M\in\mathbb{F}_{q^{2}}[x]$ satisfy that $L=\varepsilon x^{t}L^{q}$ and $M=\varepsilon x^{t}M^{q}$ for any $x\in U_{q+1}$ , $L/M$ induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ , where $\varepsilon\in U_{q+1}$ and $t\geq\max\{\deg(L),\deg(M)\}$ . Assume $\alpha$ , $\beta\in\mathbb{F}_{q^{2}}^{*}$ , $\gamma$ , $\delta\in\mathbb{F}_{q^{2}}$ , $\alpha^{q-1}\neq\beta^{q-1}$ , and $\gamma^{q+1}\neq\delta^{q+1}$ . Let

H=\gamma(\alpha L^{n}+\beta M^{n})^{k}+\delta(\alpha^{q}L^{n}+\beta^{q}M^{n})^{k}\quad\text{and}\quad f=x^{r}H(x^{q-1})^{m_{1}},

where $n,k,r\geq 1$ , $(k,q+1)=1$ , $H$ has no roots in $U_{q+1}$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv ntk\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m=m_{1}$ and $(n,q-1)=1$ , where $1\leq m\leq\min\{2(q-1),m_{1}(q+1)\}$ .

Substituting the rational function in Lemma 9.7 to Corollary 9.9 yields the next result.

Example 9.5.

Let $\beta$ , $\theta\in\mathbb{F}_{q^{2}}^{*}$ and $\delta\in\mathbb{F}_{q^{2}}$ satisfy $\beta^{q-1}\neq 1$ , $\theta^{q-1}\neq 1$ , and $\delta^{q+1}\neq 1$ . Let

H(x)=((x+1)^{n}+\beta(\theta x+\theta^{q})^{n})^{k}+\delta((x+1)^{n}+\beta^{q}(\theta x+\theta^{q})^{n})^{k}

and $f=x^{r}H(x^{q-1})^{m_{1}}$ , where $n,k,r\geq 1$ , $(k,q+1)=1$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv kn\pmod{q+1}$ . Then $f$ is $m$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $m=m_{1}$ and $(n,q-1)=1$ , where $1\leq m\leq\min\{2(q-1),m_{1}(q+1)\}$ .

Proof.

Let $L(x)=x+1$ and $M(x)=\theta x+\theta^{q}$ . By Lemma 9.7, $L/M$ induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ . By the proof of Example 9.4, $L^{n}+\beta^{q}M^{n}$ has no roots in $U_{q+1}$ . If $H(\bar{x})=0$ for some $\bar{x}\in U_{q+1}$ , then

	$\displaystyle-\delta$	$\displaystyle=(L(\bar{x})^{n}+\beta M(\bar{x})^{n})^{k}/(L(\bar{x})^{n}+\beta^{q}M(\bar{x})^{n})^{k}$
		$\displaystyle=x^{k}\circ(x+\beta)/(x+\beta^{q})\circ x^{n}\circ L/M\circ\bar{x}\in U_{q+1},$

contrary to $\delta^{q+1}\neq 1$ . Thus $H(x)$ has no roots in $U_{q+1}$ . Then the result follows from Corollary 9.9. ∎

Recently, low-degree rational functions that permute $\mathbb{F}_{q}\cup\{\infty\}$ are given in [14, 19, 20, 11] by different methods. By substituting these functions for $x^{n}$ in Theorem 9.6, one can obtain more classes of $m$ -to- $1$ mappings over $\mathbb{F}_{q^{2}}^{*}$ . For instance, we deduce the following result by substituting the rational function in [19, Theorem 3.2] for $x^{n}$ in Theorem 9.6.

Lemma 9.10 ([19, Theorem 3.2]).

Let $q$ be even and $\alpha\in\mathbb{F}_{q^{2}}\setminus\mathbb{F}_{q}$ . Then

f(x)\coloneq x+\frac{1}{x+\alpha}+\frac{1}{x+\alpha^{q}}

permutes $\mathbb{F}_{q}\cup\{\infty\}$ if and only if $\alpha+\alpha^{q}=1$ .

Theorem 9.11.

	$\displaystyle\bar{g}=x+\frac{1}{x+\alpha}+\frac{1}{x+\alpha^{q}},$
	$\displaystyle h_{2}=L^{2}M+(\alpha+\alpha^{q})LM^{2}+\alpha^{q+1}M^{3},$
	$\displaystyle H=h_{2}^{u}(N\circ\bar{g}\circ L/M),$

and $H$ has no roots in $U_{q+1}$ , where $u=\deg(N)$ . Let $f=x^{r}H(x^{q-1})^{m_{1}}$ , where $r\in\mathbb{N}$ , $m_{1}=(r,q-1)$ , and $r/m_{1}\equiv 3tu\pmod{q+1}$ . Then $f$ is $m_{1}$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $\alpha+\alpha^{q}=1$ .

Proof.

Since

\bar{g}(x)=\frac{x^{3}+(\alpha+\alpha^{q})x^{2}+\alpha^{q+1}x+(\alpha+\alpha^{q})}{x^{2}+(\alpha+\alpha^{q})x+\alpha^{q+1}},

we have

	$\displaystyle\bar{g}\circ L/M$	$\displaystyle=\frac{L^{3}/M^{3}+(\alpha+\alpha^{q})(L^{2}/M^{2})+\alpha^{q+1}(L/M)+(\alpha+\alpha^{q})}{(L^{2}/M^{2})+(\alpha+\alpha^{q})(L/M)+\alpha^{q+1}}$
		$\displaystyle=\frac{L^{3}+(\alpha+\alpha^{q})L^{2}M+\alpha^{q+1}LM^{2}+(\alpha+\alpha^{q})M^{3}}{L^{2}M+(\alpha+\alpha^{q})LM^{2}+\alpha^{q+1}M^{3}}\coloneq h_{1}/h_{2}.$

Put $N=\sum_{i=0}^{u}a_{i}x^{i}\in\mathbb{F}_{q^{2}}[x]$ . Then

H=h_{2}^{u}\cdot\sum_{i=0}^{u}a_{i}(h_{1}/h_{2})^{i}=\sum_{i=0}^{u}a_{i}h_{1}^{i}h_{2}^{u-i}.

Since $L=\varepsilon x^{t}L^{q}$ and $M=\varepsilon x^{t}M^{q}$ , we get $h_{i}^{q}=(\varepsilon^{-1}x^{-t})^{3}h_{i}$ for any $x\in U_{q+1}$ , and so

H^{q}=\sum_{i=0}^{u}a_{i}^{q}h_{1}^{qi}h_{2}^{q(u-i)}=(\varepsilon^{-1}x^{-t})^{3u}\sum_{i=0}^{u}a_{i}^{q}h_{1}^{i}h_{2}^{u-i}.

Define $g(x)=x^{r/m_{1}}H^{q-1}$ . The condition $r/m_{1}\equiv 3tu\pmod{q+1}$ implies $x^{r/m_{1}}=x^{3tu}$ for any $x\in U_{q+1}$ . Recall that $H$ has no roots in $U_{q+1}$ . Thus, for any $x\in U_{q+1}$ ,

\displaystyle g(x)=x^{r/m_{1}}H^{q}/H=\frac{\beta\sum_{i=0}^{u}a_{i}^{q}h_{1}^{i}h_{2}^{u-i}}{~{}\sum_{i=0}^{u}a_{i}h_{1}^{i}h_{2}^{u-i}},

(9.4)

where $\beta=\varepsilon^{-3u}$ . If $M(x)\neq 0$ for some $x\in U_{q+1}$ , then

\displaystyle g(x)=\beta N^{(q)}/N\circ h_{1}/h_{2}=\beta N^{(q)}/N\circ\bar{g}\circ L/M.

(9.5)

If $M(x_{0})=0$ for some $x_{0}\in U_{q+1}$ , then $x_{0}$ is unique and $L(x_{0})\neq 0$ , since $L/M$ induces a bijection from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$ . Hence, by Eq. 9.4,

g(x_{0})=\beta a_{u}^{q}L^{3u}(x_{0})/a_{u}L^{3u}(x_{0})=\beta a_{u}^{q}/a_{u}.

Because $L(x_{0})\neq 0$ and $M(x_{0})=0$ , we get $L(x_{0})/M(x_{0})=\infty$ and $\bar{g}(\infty)=\infty$ . Thus

\beta N^{(q)}/N\circ\bar{g}\circ L(x_{0})/M(x_{0})=\beta a_{u}^{q}/a_{u}.

In summary, Eq. 9.5 holds for any $x\in U_{q+1}$ . Since $\beta N^{(q)}/N$ induces a bijection from $\mathbb{F}_{q}\cup\{\infty\}$ to $U_{q+1}$ ,

(\beta N^{(q)}/N)^{-1}\circ g=\bar{g}\circ L/M.

Note that $f(x)\in U_{\frac{q^{2}-1}{m_{1}}}$ for $x\in\mathbb{F}_{q^{2}}^{*}$ and $g(x)\in U_{q+1}$ for $x\in U_{q+1}$ . Thus the following diagrams are commutative:

Let $\lambda=L/M$ and $\bar{\lambda}=(\beta N^{(q)}/N)^{-1}$ . Since both $\lambda$ and $\bar{\lambda}$ are bijective, $\#\lambda^{-1}(e)=\#\bar{\lambda}^{-1}(\bar{g}(e))=1$ and $g$ is $1$ -to- $1$ on $\lambda^{-1}(e)$ for any $e\in\mathbb{F}_{q}\cup\{\infty\}$ . By Theorem 9.1 and [19, Theorem 3.2], $f$ is $m_{1}$ -to- $1$ on $\mathbb{F}_{q^{2}}^{*}$ if and only if $\bar{g}$ is $1$ -to- $1$ on $\mathbb{F}_{q}\cup\{\infty\}$ if and only if $\alpha+\alpha^{q}=1$ . ∎

References

Akbary and Wang [2007] A. Akbary and Q. Wang. On polynomials of the form $x^{r}f(x^{(q-1)/l})$ . Int. J. Math. Math. Sci., 2007:article ID 23408, 7 pages, 2007. doi:10.1155/2007/23408.
Akbary et al. [2011] A. Akbary, D. Ghioca, and Q. Wang. On constructing permutations of finite fields. Finite Fields Appl., 17:51–67, 2011.
Bartoli and Giulietti [2018] D. Bartoli and M. Giulietti. Permutation polynomials, fractional polynomials, and algebraic curves. Finite Fields Appl., 51:1–16, 2018. doi:10.1016/j.ffa.2018.01.001.
Bartoli and Quoos [2018] D. Bartoli and L. Quoos. Permutation polynomials of the type $x^{r}g(x)^{s}$ over $\mathbb{F}_{q^{2n}}$ . Des. Codes Cryptogr., 86:1589–1599, 2018. doi:10.1007/S10623-017-0415-8.
Bartoli et al. [2018] D. Bartoli, A. M. Masuda, and L. Quoos. Permutation polynomials over $\mathbb{F}_{q^{2}}$ from rational functions. https://arxiv.org/abs/1802.05260v1, 2018.
Bartoli et al. [2022] D. Bartoli, M. Giulietti, and M. Timpanella. Two-to-one functions from Galois extensions. Discrete Appl. Math., 309:194–201, 2022. doi:10.1016/j.dam.2021.12.008.
Charpin and Kyureghyan [2009] P. Charpin and G. Kyureghyan. When does ${G}(x)+\gamma\mathrm{Tr}({H}(x))$ permute $\mathbb{F}_{2^{n}}$ ? Finite Fields Appl., 15:615–632, 2009.
Dillon and Dobbertin [2004] J. F. Dillon and H. Dobbertin. New cyclic difference sets with Singer parameters. Finite Fields Appl., 10(3):342–389, 2004. doi:10.1016/j.ffa.2003.09.003.
Ding [2015] C. Ding. Linear codes from some 2-designs. IEEE Trans. Inf. Theory, 61(6):3265–3275, 2015. doi:10.1109/TIT.2015.2420118.
Ding [2016] C. Ding. A construction of binary linear codes from Boolean functions. Discrete Math., 339(9):2288–2303, 2016. doi:10.1016/j.disc.2016.03.029.
Ding and Zieve [2022] Z. Ding and M. E. Zieve. Low-degree permutation rational functions over finite fields. Acta Arith., 202:253–280, 2022. doi:10.4064/aa210521-12-11.
Ding and Zieve [2023] Z. Ding and M. E. Zieve. Constructing permutation polynomials using generalized Rédei functions. https://arxiv.org/abs/2305.06322, 2023.
Ding and Zieve [2024] Z. Ding and M. E. Zieve. On a class of $m$ -to-1 functions. Discrete Appl. Math., 353:208–210, 2024. doi:10.1016/j.dam.2024.04.028.
Ferraguti and Micheli [2020] A. Ferraguti and G. Micheli. Full classification of permutation rational functions and complete rational functions of degree three over finite fields. Des. Codes Cryptogr., 88:867–886, 2020.
Gao et al. [2021] Y. Gao, Y.-F. Yao, and L.-Z. Shen. $m$ -to- $1$ mappings over finite fields $\mathbb{F}_{q}$ . IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E104.A(11):1612–1618, 2021. doi:10.1587/transfun.2021EAP1003.
Gupta and Sharma [2016] R. Gupta and R. K. Sharma. Some new classes of permutation trinomials over finite fields with even characteristic. Finite Fields Appl., 41:89–96, 2016.
Hasan et al. [2021] S. U. Hasan, M. Pal, C. Riera, and P. Stǎnicǎ. On the $c$ -differential uniformity of certain maps over finite fields. Des. Codes Cryptogr., 89:221–239, 2021. doi:10.1007/s10623-020-00812-0.
Hou [2015] X.-D. Hou. Permutation polynomials over finite fields—A survey of recent advances. Finite Fields Appl., 32:82–119, 2015.
Hou [2021a] X.-D. Hou. A power sum formula by Carlitz and its applications to permutation rational functions of finite fields. Cryptogr. Commun., 13:681–694, 2021a. doi:10.1007/s12095-021-00495-x.
Hou [2021b] X.-D. Hou. Rational functions of degree four that permute the projective line over a finite field. Commun. Algebra, 49(9):3798–3809, 2021b. doi:10.1080/00927872.2021.1906887.
Kim and Mesnager [2020] K. H. Kim and S. Mesnager. Solving $x^{2^{k}+1}+x+a=0$ in $\mathbb{F}_{2^{n}}$ with $\gcd(n,k)=1$ . Finite Fields Appl., 63:101630, 2020. doi:10.1016/j.ffa.2019.101630.
Kölsch and Kyureghyan [2024] L. Kölsch and G. Kyureghyan. The classifications of o-monomials and of 2-to-1 binomials are equivalent. Des. Codes Cryptogr., 2024. doi:10.1007/s10623-024-01463-1.
Lachaud and Wolfmann [1990] G. Lachaud and J. Wolfmann. The weights of the orthogonals of the extended quadratic binary Goppa codes. IEEE Trans. Inf. Theory, 36(3):686–692, 1990.
Li et al. [2018] K. Li, L. Qu, C. Li, and S. Fu. New permutation trinomials constructed from fractional polynomials. Acta Arith., 183:101–116, 2018. doi:10.4064/aa8461-11-2017.
Li et al. [2021a] K. Li, C. Li, T. Helleseth, and L. Qu. Binary linear codes with few weights from two-to-one functions. IEEE Trans. Inf. Theory, 67(7):4263–4275, 2021a. doi:10.1109/TIT.2021.3068743.
Li et al. [2021b] K. Li, S. Mesnager, and L. Qu. Further study of $2$ -to- $1$ mappings over $\mathbb{F}_{2^{n}}$ . IEEE Trans. Inf. Theory, 67(6):3486–3496, June 2021b.
Li and Helleseth [2017] N. Li and T. Helleseth. Several classes of permutation trinomials from Niho exponents. Cryptogr. Commun., 9:693–705, 2017. doi:10.1007/s12095-016-0210-9.
Lidl and Niederreiter [1997] R. Lidl and H. Niederreiter. Finite Fields. Cambridge Univ. Press, Cambridge, 1997.
Marcos [2011] J. E. Marcos. Specific permutation polynomials over finite fields. Finite Fields Appl., 17(2):105–112, 2011.
Mesnager and Qu [2019] S. Mesnager and L. Qu. On two-to-one mappings over finite fields. IEEE Trans. Inf. Theory, 65(12):7884–7895, Dec. 2019. doi:10.1109/TIT.2019.2933832.
Mesnager et al. [2023a] S. Mesnager, L. Qian, and X. Cao. Further projective binary linear codes derived from two-to-one functions and their duals. Des. Codes Cryptogr., 91:719–746, 2023a. doi:10.1007/s10623-022-01122-3.
Mesnager et al. [2023b] S. Mesnager, L. Qian, X. Cao, and M. Yuan. Several families of binary minimal linear codes from two-to-one functions. IEEE Trans. Inf. Theory, 69(5):3285–3301, 2023b. doi:10.1109/TIT.2023.3236955.
Mesnager et al. [2023c] S. Mesnager, M. Yuan, and D. Zheng. More about the corpus of involutions from two-to-one mappings and related cryptographic S-boxes. IEEE Trans. Inf. Theory, 69(2):1315–1327, 2023c.
Mullen and Panario [2013] G. L. Mullen and D. Panario. Handbook of Finite Fields. CRC Press, Boca Raton, 2013.
Niu et al. [2023] T. Niu, K. Li, L. Qu, and C. Li. Characterizations and constructions of $n$ -to- $1$ mappings over finite fields. Finite Fields Appl., 85:102126, 2023. doi:10.1016/j.ffa.2022.102126.
Özbudak and Temür [2022] F. Özbudak and B. G. Temür. Classification of permutation polynomials of the form $x^{3}g(x^{q-1})$ of $\mathbb{F}_{q^{2}}$ where $g(x)=x^{3}+bx+c$ and $b,c\in\mathbb{F}_{q}^{*}$ . Des. Codes Cryptogr., 90:1537–1556, 2022.
Özbudak and Temür [2023] F. Özbudak and B. G. Temür. Complete characterization of some permutation polynomials of the form $x^{r}(1+ax^{s_{1}(q-1)}+bx^{s_{2}(q-1)})$ over $\mathbb{F}_{q^{2}}$ . Cryptogr. Commun., 15:775–793, 2023.
Park and Lee [2001] Y. H. Park and J. B. Lee. Permutation polynomials and group permutation polynomials. Bull. Austral. Math. Soc., 63:67–74, 2001.
Wan and Lidl [1991] D. Wan and R. Lidl. Permutation polynomials of the form $x^{r}f(x^{(q-1)/d})$ and their group structure. Monatsh. Math., 112:149–163, 1991.
Wang [2007] Q. Wang. Cyclotomic mapping permutation polynomials over finite fields. In Sequences, Subsequences, and Consequences, volume 4893 of Lecture Notes in Comput. Sci., pages 119–128. Springer, 2007.
Wang [2019] Q. Wang. Polynomials over finite fields: an index approach. In K.-U. Schmidt and A. Winterhof, editors, Combinatorics and Finite Fields: Difference Sets, Polynomials, Pseudorandomness and Applications, pages 319–346, 2019. doi:10.1515/9783110642094-015.
Wang [2024] Q. Wang. A survey of compositional inverses of permutation polynomials over finite fields. Des. Codes Cryptogr., 2024. doi:10.1007/s10623-024-01436-4.
Wu et al. [2021] Y. Wu, N. Li, and X. Zeng. New PcN and APcN functions over finite fields. Des. Codes Cryptogr., 89:2637–2651, 2021. doi:10.1007/s10623-021-00946-9.
Yuan et al. [2021] M. Yuan, D. Zheng, and Y. Wang. Two-to-one mappings and involutions without fixed points over $\mathbb{F}_{2^{n}}$ . Finite Fields Appl., 76:101913, 2021.
Yuan [2024] P. Yuan. Local method for compositional inverses of permutation polynomials. Commun. Algebra, 52(7):3070–3080, 2024. doi:10.1080/00927872.2024.2314113.
Yuan and Ding [2014] P. Yuan and C. Ding. Further results on permutation polynomials over finite fields. Finite Fields Appl., 27:88–103, 2014.
Zha et al. [2017] Z. Zha, L. Hu, and S. Fan. Further results on permutation trinomials over finite fields with even characteristic. Finite Fields Appl., 45:43–52, 2017.
Zheng et al. [2020] Y. Zheng, Q. Wang, and W. Wei. On inverses of permutation polynomials of small degree over finite fields. IEEE Trans. Inf. Theory, 66(2):914–922, Feb. 2020. doi:10.1109/TIT.2019.2939113.
Zieve [2009] M. E. Zieve. On some permutation polynomials over $\mathbb{F}_{q}$ of the form $x^{r}h(x^{(q-1)/d})$ . Proc. Am. Math. Soc., 137(7):2209–2216, 2009.
Zieve [2010] M. E. Zieve. Classes of permutaton polynomials based on cyclotomy and an additive analogue. In Additive Number Theory, pages 355–361. Springer, New York, 2010. doi:10.1007/978-0-387-68361-4_25.
Zieve [2013] M. E. Zieve. Permutation polynomials on $\mathbb{F}_{q}$ induced from Rédei function bijections on subgroups of $\mathbb{F}_{q}^{*}$ . https://arxiv.org/abs/1310.0776v2, 2013.

On many-to-one mappings over finite fields

Abstract

keywords:

MSC:

1 Introdution

1.1 The progress of many-to-one mapping

Definition 1.1.

Definition 1.2.

Example 1.1.

Example 1.2.

Example 1.3.

1.2 The constructions of many-to-one mappings

Theorem 1.1 (The AGW criterion).

Theorem 1.2 (Local criterion [45]).

1.3 The organization of the paper

1.4 Notations

2 Some properties of mm-to-11 mappings

Theorem 2.1.

Proof.

Theorem 2.2.

Proof.

Theorem 2.3.

Proof.

Corollary 2.4.

Corollary 2.5.

Example 2.1.

3 Three constructions for mm-to-11 mappings

Lemma 3.1 (Generalized local criterion).

Proof.

3.1 The first construction

Construction 1.

Proof.

3.2 The second construction

Construction 2.

Proof.

Corollary 3.2.

Corollary 3.3.

Proof.

Corollary 3.4.

3.3 The third construction

Construction 3.

Proof.

Remark 1.

Remark 2.

4 Many-to-one mappings of the form xr​h​(xs)x^{r}h(x^{s})

Theorem 4.1.

Lemma 4.2.

Proof.

Theorem 4.3.

Proof.

Example 4.1.

Corollary 4.4.

Corollary 4.5.

Theorem 4.6.

Proof.

Theorem 4.7.

Proof.

5 The case m=2,3m=2,3

Theorem 5.1.

Proof.

Corollary 5.2.

Proof.

Theorem 5.3.

Proof.

6 The case ℓ=2,3\ell=2,3

Theorem 6.1.

Corollary 6.2.

Theorem 6.3.

Corollary 6.4.

Example 6.1.

7 Monomials

Theorem 7.1.

Proof.

Corollary 7.2.

Proof.

7.1 mm-to-11 mappings on 𝔽q2∗\mathbb{F}_{q^{2}}^{*}

Theorem 7.3.

Proof.

Remark 3.

Corollary 7.4.

2 Some properties of $m$ -to- $1$ mappings

3 Three constructions for $m$ -to- $1$ mappings

4 Many-to-one mappings of the form $x^{r}h(x^{s})$

5 The case $m=2,3$

6 The case $\ell=2,3$

7.1 $m$ -to- $1$ mappings on $\mathbb{F}_{q^{2}}^{*}$

7.2 $m$ -to- $1$ mappings on $\mathbb{F}_{q^{n}}^{*}$

9.1 $\lambda$ is $1$ -to- $1$ from $U_{q+1}$ to itself

9.2 $\lambda$ is $1$ -to- $1$ from $U_{q+1}$ to $\mathbb{F}_{q}\cup\{\infty\}$