Permutation polynomials, projective polynomials, and bijections between μ q n − 1 q − 1 \mu_{\frac{q^{n}-1}{q-1}} and PG ​ ( n − 1 , q ) \text{PG}(n-1,q)

Tong Lin, Qiang Wang · 2025

Read Permutation polynomials, projective polynomials, and bijections between μ q n − 1 q − 1 \mu_{\frac{q^{n}-1}{q-1}} and PG ​ ( n − 1 , q ) \text{PG}(n-1,q) by Tong Lin, Qiang Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-11775.txt.

Introduction

Lin and Wang build in twenty twenty-five two-way bridges between a projective geometry space and a special set of roots of unity inside a finite field. Finite fields power coding and cryptography, and tidy maps between their structures are valuable. Starting from any basis of the larger field over the smaller, they define a family of fractional-style maps that pair the two sets exactly.

They introduce a class of polynomials tied to the maps and use their traits to write down the maps' inverses. Studying those polynomials' roots yields a three-way matching between splits of three related sets. Through the bridges they then construct permutation polynomials of a set index over the field. The work enriches the toolkit linking geometry and field arithmetic.

Catalog record

CREATORTong Lin, Qiang Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11775

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Permutation polynomials, projective polynomials, and bijections between μ q n − 1 q − 1 \mu_{\frac{q^{n}-1}{q-1}} and PG ​ ( n − 1 , q ) \text{PG}(n-1,q) Tong Lin, Qiang Wang Abstract Using arbitrary bases for the finite field 𝔽 q n \mathbb{F}_{{q}^{n}} over 𝔽 q \mathbb{F}_{q} , we obtain the generalized Möbius transformations (GMTs), which are a class of bijections between the projective geometry PG ​ ( n − 1 , q ) \text{PG}(n-1,q) and the set of roots of unity μ q n − 1 q − 1 ⊆ 𝔽 q n \mu_{\frac{q^{n}-1}{q-1}}\subseteq\mathbb{F}_{{q}^{n}} , where n ≥ 2 n\geq 2 is any integer. We also introduce a class of projective polynomials, using the properties of which we determine the inverses of the GMTs. Moreover, we study the roots of those projective polynomials, which lead to a three-way correspondence between partitions of 𝔽 q n ∗ , μ q n − 1 q − 1 \mathbb{F}_{{q}^{n}}^{\ast},\mu_{\frac{q^{n}-1}{q-1}} and PG ​ ( n − 1 , q ) \text{PG}(n-1,q) . Through this correspondence and the GMTs, we construct permutation polynomials of index q n − 1 q − 1 \frac{q^{n}-1}{q-1} over 𝔽 q n \mathbb{F}_{{q}^{n}} . 1 Introduction Throughout this paper, let \mathbb{F}_{{q}^{n}} be the finite field with q^{n} elements, where q is a prime power and n\geq 2 . A polynomial f\in\mathbb{F}_{{q}^{n}}[x] permutes \mathbb{F}_{{q}^{n}} if it is a bijection over \mathbb{F}_{{q}^{n}} . Permutation polynomials over finite fields have long been a fundamental subject of great interest since they find their applications in a diversity of areas such as cryptography [ 23 , 26 , 31 , 37 ] , coding theory [ 12 , 25 ] , combinatorial designs [ 13 ] and block ciphers [ 9 ] . Over the years, a vast number of classes of permutation polynomials have been researched; see, for example, [ 2 , 3 , 4 , 16 , 19 , 27 , 32 , 34 , 35 , 36 , 43 , 44 , 45 , 46 , 47 ] and the references therein. Among them, the study of permutation polynomials of the form x^{r}h\left(x^{s}\right) has been popularized by numerous researchers using different techniques, many of which involve the multiplicative case of the AGW-Criterion, which is the following lemma. Lemma 1.1 ( [ 2 , 35 , 40 , 42 , 48 ] ) . Let r\in\mathbb{N} . Let \ell,s\in\mathbb{N} be such that q^{n}-1=\ell s . The polynomial f(x)=x^{r}h\left(x^{s}\right) permutes \mathbb{F}_{{q}^{n}} if and only if \gcd(r,s)=1 and g(x)=x^{r}h(x)^{s} permutes \mu_{\ell} , the set of all \ell -th roots of unity. In fact, every polynomial f\in\mathbb{F}_{{q}^{n}}[x] such that f(0)=0 can be uniquely written as x^{r}h\left(x^{s}\right) , where r\geq 0 is the vanishing order and \ell=(q^{n}-1)/s is the index of f . The notion of index was introduced in [ 3 ] . Let r be any positive integer coprime to q-1 . In this paper, we focus on constructing permutation polynomials of vanishing order r and index \frac{q^{n}-1}{q-1} over \mathbb{F}_{{q}^{n}} . That is, we find polynomials h\in\mathbb{F}_{{q}^{n}}[x] such that f(x)=x^{r}h\left(x^{q-1}\right) permutes \mathbb{F}_{{q}^{n}} . Since f(0)=0 for each such f , it suffices to construct h for which the corresponding f permutes \mathbb{F}_{{q}^{n}}^{\ast} . For this purpose, we apply Lemma 1.1 . Through the mapping x^{q-1} , we project \mathbb{F}_{{q}^{n}}^{\ast} onto \mu_{\frac{q^{n}-1}{q-1}} , which is of smaller cardinality, and find h such that g(x)=x^{r}h(x)^{q-1} permutes \mu_{\frac{q^{n}-1}{q-1}} . To study the permutational behavior of g , we may follow the same ideas as above and project \mu_{\frac{q^{n}-1}{q-1}} onto a set S via properly chosen bijections from \mu_{\frac{q^{n}-1}{q-1}} to S . For example, S can be the projective geometry \text{PG}(n-1,q)=\bigl(\mathbb{F}_{q}^{n}\setminus\bigl\{\vec{0}\bigr\}\bigr)/\penalty\sim, which is the quotient set of \mathbb{F}_{q}^{n}\setminus\bigl\{\vec{0}\bigr\} by the equivalence relation \sim , under which \vec{x}\sim\vec{y} when \vec{x}=\lambda\vec{y} for some \lambda\in\mathbb{F}_{q}^{\ast} . Counting the number of equivalence classes yields that \bigl|\text{PG}(n-1,q)\bigr|=\frac{q^{n}-1}{q-1}=\Bigl|\mu_{\frac{q^{n}-1}{q-1}}\Bigr| . We denote the equivalence class in \text{PG}(n-1,q) represented by a vector \vec{x}=(x_{0},\dots,x_{n-1})\in\mathbb{F}_{q}^{n}\setminus\bigl\{\vec{0}\bigr\} by (x_{0}:\dots:x_{n-1}) . {\lx@inpgf@ignorespaces{\mathbb{F}_{{q}^{n}}^{\ast}}} {\lx@inpgf@ignorespaces{\mathbb{F}_{{q}^{n}}^{\ast}}} {\lx@inpgf@ignorespaces{\mu_{\frac{q^{n}-1}{q-1}}}} {\lx@inpgf@ignorespaces{\mu_{\frac{q^{n}-1}{q-1}}}} {\lx@inpgf@ignorespaces{\text{PG}(n-1,q)}} {\lx@inpgf@ignorespaces{\text{PG}(n-1,q)}} \scriptstyle{\lx@inpgf@ignorespaces f(x)=x^{r}h\left(x^{q-1}\right)} \scriptstyle{\lx@inpgf@ignorespaces x^{q-1}} \scriptstyle{\lx@inpgf@ignorespaces x^{q-1}} \scriptstyle{\lx@inpgf@ignorespaces g(x)=x^{r}h(x)^{q-1}} \scriptstyle{\lx@inpgf@ignorespaces\eta_{1}^{-1}} \scriptstyle{\lx@inpgf@ignorespaces\overline{g}} \scriptstyle{\lx@inpgf@ignorespaces\eta_{2}} Figure 1: The multiplicative AGW criterion with generic bijections \eta_{1} and \eta_{2} As Fig. 1 shows, for each bijection \overline{g} over \text{PG}(n-1,q) and each pair of bijections \eta_{1},\eta_{2} from \text{PG}(n-1,q) to \mu_{\frac{q^{n}-1}{q-1}} , the mapping \eta_{2}\circ\overline{g}\circ\eta_{1}^{-1} is a bijection over \mu_{\frac{q^{n}-1}{q-1}} . If there exists an h\in\mathbb{F}_{{q}^{n}}[x] such that x^{r}h(x)^{q-1}=\eta_{2}\circ\overline{g}\circ\eta_{1}^{-1}, (1) then the polynomial f(x)=x^{r}h\left(x^{q-1}\right) permutes \mathbb{F}_{{q}^{n}} as per Lemma 1.1 . Therefore, our main goal in this paper becomes finding polynomials h\in\mathbb{F}_{{q}^{n}}[x] which satisfy Eq. 1 for bijections \overline{g} over \text{PG}(n-1,q) and some bijections \eta_{1},\eta_{2} from \text{PG}(n-1,q) to \mu_{\frac{q^{n}-1}{q-1}} . When n=2 , a common choice for \eta_{1},\eta_{2} is the so-called Möbius transformation. More precisely, for i=1,2 , we pick u_{i}\in\mu_{q+1}\setminus\mathbb{F}_{q} , and let \eta_{i}(x)=\frac{x+u_{i}^{q}}{x+u_{i}}, Since \gcd(r,q-1)=1 , f(x)=x^{r}h\left(x^{q-1}\right) permutes \mathbb{F}_{{q}^{2}} if and only if \eta_{2}^{-1}\circ x^{r}h(x)^{q-1}\circ\eta_{1} permutes \text{PG}(1,q)\cong\mathbb{F}_{q}\sqcup\{\infty\} , where \infty denotes a ‘point at infinity’ adjoined to the ‘line’ \mathbb{F}_{q} . Examples of this technique can be found in [ 16 , 20 , 28 , 34 , 38 , 39 ] . Similarly, when n=3 , Fig. 1 shows that one can construct h\in\mathbb{F}_{{q}^{3}}[x] for which f(x)=x^{r}h\left(x^{q-1}\right) permutes \mathbb{F}_{{q}^{3}} by projecting \mu_{q^{2}+q+1} onto \text{PG}(2,q) . In this case, instead of using the usual Möbius transformations, Qu and Li [ 36 ] introduced the following mappings. Let W=\Bigl\{\omega,\omega^{q},\omega^{q^{2}}\Bigr\} be a basis \mathbb{F}_{{q}^{3}} over \mathbb{F}_{q} for some \omega\in\mathbb{F}_{{q}^{3}}^{\ast} , and define \psi_{W}:\text{PG}(2,q)\to\mu_{q^{2}+q+1} , where \psi_{W}(x_{0}:x_{1}:x_{2})=\frac{x_{0}\omega^{q}+x_{1}\omega^{q^{2}}+x_{2}\omega}{x_{0}\omega+x_{1}\omega^{q}+x_{2}\omega^{q^{2}}}. (2) Let \alpha=\omega^{q+1}-\omega^{2q^{2}} and define, for i=0,1,2 , T_{W,i}(x)=\alpha^{q^{i+1}}+\alpha^{q^{i+2}}x+\alpha^{q^{i}}x^{q+1}, (3) Then for each x\in\mu_{q^{2}+q+1} , \psi_{W}^{-1}(x)=\begin{cases}(1:0:0)&\text{if }x=\omega^{q-1};\\ \biggl(\frac{T_{W,0}(x)}{T_{W,1}(x)}:1:0\biggr)&\text{if }T_{W,1}(x)\neq 0\text{ and }T_{W,2}(x)=0;\\ \biggl(\frac{T_{W,0}(x)}{T_{W,2}(x)}:\frac{T_{W,1}(x)}{T_{W,2}(x)}:1\biggr)&\text{if }T_{W,2}(x)\neq 0.\end{cases} (4) In this paper, we generalize Qu and Li’s ideas in order to deal with the case where n\geq 2 is an arbitrary integer. We summarize our first main result into the following theorem. Theorem I . Let W=\{\omega_{j}:0\leq j\leq n-1\} be any basis for \mathbb{F}_{{q}^{n}} over \mathbb{F}_{q} . Define \psi_{W}:\text{PG}(n-1,q)\to\mu_{\frac{q^{n}-1}{q-1}} , where \psi_{W}(x_{0}:\dots:x_{n-1})=\Biggl(\sum_{j=0}^{n-1}x_{j}\omega_{j}\Biggr)^{q-1}=\frac{\displaystyle{\sum_{j=0}^{n-1}x_{j}\omega_{j}^{q}}}{\displaystyle{\sum_{j=0}^{n-1}x_{j}\omega_{j}}}. Then \psi_{W} is a bijection. Moreover, for 0\leq i\leq n-1 , define T_{W,i}(x)=\sum_{k=0}^{n-1}(-1)^{k(n-1)}c_{i}^{q^{k}}x^{\frac{q^{k}-1}{q-1}}, in which the constant term c_{i}=T_{W,i}(0) is the (i,0) -cofactor of the matrix M_{W}=\begin{bmatrix}\omega_{0}&\omega_{0}^{q}&\dots&\omega_{0}^{q^{n-1}}\\ \omega_{1}&\omega_{1}^{q}&\dots&\omega_{1}^{q^{n-1}}\\ \vdots&\vdots&\ddots&\vdots\\ \omega_{n-1}&\omega_{n-1}^{q}&\dots&\omega_{n-1}^{q^{n-1}}\\ \end{bmatrix}. Then \psi_{W}^{-1}(x)=\begin{cases}(1:0:\dots:0)&\text{ if }x=\omega_{0}^{q-1};\\ \displaystyle{\biggl(\frac{T_{W,0}(x)}{T_{W,1}(x)}:1:0:\dots:0\biggr)}&\text{ if }x=(x_{0}\omega_{0}+\omega_{1})^{q-1}\text{ for some }x_{0}\in\mathbb{F}_{q};\\ \vdots&\ \vdots\\ \displaystyle{\biggl(\frac{T_{W,0}(x)}{T_{W,n-1}(x)}:\dots:\frac{T_{W,n-2}(x)}{T_{W,n-1}(x)}:1\biggr)}&\begin{array}[]{l}\text{if }x=(x_{0}\omega_{0}+\dots+x_{n-2}\omega_{n-2}+\omega_{n-1})^{q-1}\\ \text{for some }x_{0},\dots,x_{n-2}\in\mathbb{F}_{q}.\end{array}\end{cases} {\lx@inpgf@ignorespaces{\mathbb{F}_{{q}^{n}}^{\ast}}} {\lx@inpgf@ignorespaces{\mathbb{F}_{{q}^{n}}^{\ast}}} {\lx@inpgf@ignorespaces{\mu_{\frac{q^{n}-1}{q-1}}}} {\lx@inpgf@ignorespaces{\mu_{\frac{q^{n}-1}{q-1}}}} {\lx@inpgf@ignorespaces{\text{PG}(n-1,q)}} {\lx@inpgf@ignorespaces{\text{PG}(n-1,q)}} \scriptstyle{\lx@inpgf@ignorespaces f(x)=x^{r}h\left(x^{q-1}\right)} \scriptstyle{\lx@inpgf@ignorespaces x^{q-1}} \scriptstyle{\lx@inpgf@ignorespaces x^{q-1}} \scriptstyle{\lx@inpgf@ignorespaces g(x)=x^{r}h(x)^{q-1}} \scriptstyle{\lx@inpgf@ignorespaces\psi_{W}^{-1}} \scriptstyle{\lx@inpgf@ignorespaces\overline{g}} \scriptstyle{\lx@inpgf@ignorespaces\psi_{Y}} Figure 2: The multiplicative AGW criterion with generalized Möbius transformations As Fig. 2 shows, if W,Y are any bases for \mathbb{F}_{{q}^{n}} over \mathbb{F}_{q} , the GMT \psi_{W} , the inverse of the GMT \psi_{Y} together with any bijection \overline{g} over \text{PG}(n-1,q) allow us to construct bijections over \mu_{\frac{q^{n}-1}{q-1}} , which then induce permutations over \mathbb{F}_{{q}^{n}} via Lemma 1.1 . When n=2 , and W=\{1,u\} , where u\in\mu_{q+1}\setminus\{\pm 1\} , it is easy to check that a usual Möbius transformation and its inverse satisfy the formulas given in Theorem I . When n=3 and W=\left\{\omega,\omega^{q},\omega^{q^{2}}\right\} for some \omega\in\mathbb{F}_{{q}^{3}}^{\ast} , Theorem I recovers Qu and Li’s results in [ 36 ] . The polynomials T_{W,i}\ (0\leq i\leq n-1) are examples of projective polynomials , which are of the form \displaystyle{\sum_{k=0}^{n-1}c_{k}x^{\frac{q^{k}-1}{q-1}}} . They were introduced by Abhyankar [ 1 ] . As a side note, our scope of understanding of projective polynomials is rather limited. Many known results about projective polynomials concern those with very

Read the complete text