Local permutation polynomials and their companions

DOI10.1016/J.FFA.2025.102717MaRDI QIDQ6924370zbMATH OpenFDO

Publication date 29 September 2025

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.FFA.2025.102717

finite fields Latin squares local permutation polynomials permutation polynomials

Polynomials over finite fields (11T06) Arithmetic theory of polynomial rings over finite fields (11T55) Finite fields (field-theoretic aspects) (12E20)

Review text

Let \(n\) be a positive integer, \(p\) a prime, \(q\) a power of \(p\), \(\mathbb{F}_q\) the finite field with \(q\) elements, \(\mathbb{F}_q^n\) the Cartesian product of \(n\) copies of \(\mathbb{F}_q\), and \(\mathbb{F}_q[X_1, \ldots,X_n]\) the ring of polynomials in \(n\) variables \(X_1, \ldots, X_n\) over \(\mathbb{F}_q\). It is well-know that any map from \(\mathbb{F}_q^n\) to \(\mathbb{F}_q\) can be uniquely represented by a polynomial \(f(X_1,X_2,\ldots,X_n) \in \mathbb{F}_q[X_1,X_2,\ldots,X_n]\) such that \(\text{deg}_{X_i}(f)<q\) for all \(i\in \{1,2,\ldots,n\}\), where \(\text{deg}_{X_i}(f)\) denotes the degree of \(f\) in the \(i\)-th variable \(X_i\). A polynomial \(f\in \mathbb{F}_q[X_1,X_2,\ldots,X_n]\) is called a permutation polynomial (PP) if the equation \(f(X_1,X_2,\ldots,X_n)=a\) has exactly \(q^{n-1}\) solutions in \(\mathbb{F}_q^{n}\) for each \(a\in \mathbb{F}_q\). For \(n=1\), the above definition coincides with the classical notion of the permutation polynomial in one variable. The classification of permutation polynomials in several variables is generally a difficult problem. In 1970, Niederreiter classified the permutation polynomials of several variables over \(\mathbb{F}_q\) of degree at most two. However, the classification of permutation polynomials in several variables of degree \(\geq 3\) remains an open problem.\N\NA polynomial \(f(X_1,X_2,\ldots,X_n) \in \mathbb{F}_q[X_1,X_2,\ldots,X_n]\) is called a local permutation polynomial (LPP) if for each \( i \in \{1, \ldots, n\}\), the equation \(f(a_1,\ldots,a_{i-1},X_i,a_{i+1},\ldots,a_n)=a\) has at most one solution for all \(a \in \mathbb{F}_q\) and \(\overline{a}_i\in \mathbb{F}_q^{n-1}\), where \(\overline{a}_i:=(a_1,\ldots,a_{i-1},a_{i+1},\ldots,a_n)\). In other words, \(f(a_1,a_2,\ldots,a_{i-1},X_i,a_{i+1},\ldots,a_n)\in \mathbb{F}_q[X_i]\) is a permutation polynomial over \(\mathbb{F}_q\) for each \(\overline{a}_i\in \mathbb{F}_q^{n-1}\), where \( i \in \{1,\ldots, n\}\). It is easy to observe that an LPP is always a permutation polynomial; however, the converse may not be true in general. For instances, \(f(X_1,X_2)=X_1^2+X_2\) is a permutation polynomial, but it is not an LPP over \(\mathbb{F}_q\) when \(q\) is a power of an odd prime.\N\N\textit{G. L. Mullen} gave necessary and sufficient conditions for polynomials in two and three variables to be local permutations polynomials over a prime field \(\mathbb{F}_p\) in [Fibonacci Q. 18, 104--108 (1980; Zbl 0427.12017); Fibonacci Q. 18, 208--214 (1980; Zbl 0438.12009)], respectively. Those conditions were expressed in terms of the coefficients of the polynomial. \N\NFor two variables, it was shown in [\textit{W. S. Diestelkamp} et al., J. Comb. Math. Comb. Comput. 50, 129--140 (2004; Zbl 1052.05020)] that the degree of an LLP in \(\mathbb{F}_q[x,y]\) is bounded above by \(2(q-2)\). In [Finite Fields Appl. 91, Article ID 102261, 22 p. (2023; Zbl 1541.11103)], \textit{J. Gutierrez} and \textit{J. Jiménez Urroz} showed that the result is true for several variables.\N\NAnbar, Kaşıkcı and Topuzoğlu generalized the notion of LPPs and defined what is known as vectorial local permutations. A map \(F: \mathbb{F}_q^n \rightarrow \mathbb{F}_q^n\) given by\N\[\NF(X_1,\ldots,X_n) = (f_1(X_1,\ldots,X_n), \ldots,f_n(X_1,\ldots,X_n))\N\]\Nis called a vectorial local permutation if all the polynomials \(f_i(X_1,\ldots,X_n)\in \mathbb{F}_q[X_1,X_2,\ldots,X_n]\), where \(i \in \{1, \ldots, n\}\), are LPPs over \(\mathbb{F}_q\), and \(F\) is called a vectorial permutation if it induces a permutation of \(\mathbb{F}_q^n\). If \(F\) is a vectorial permutation, then by using the absolute irreducibility of certain curve over \(\mathbb{F}_q\) and the number of rational points on it, the authors showed that the degrees of the components \(f_1, f_2, \ldots, f_n \in \mathbb{F}_q[X_1, \ldots, X_n]\) are at least two when \(2 \leq \text{deg}(F )=d < \sqrt{q}\) and \(d\mid (q-1)\), where \(\text{deg}(F ):=\max \{\text{deg} (f_i) \mid i=1, \ldots, n\}\).\N\NA Latin square of order \(n\) is an \(n \times n\) matrix with entries from a set \(S\) of size \(n\), such that every element of \(S\) appears exactly once in each row and each column. Two Latin squares are said to be orthogonal if, when superimposed, they produce all the ordered pairs of \(S \times S\). A set of Latin squares of order \(n\) that are pairwise orthogonal is referred to as Mutually Orthogonal Latin Squares (MOLS). A set of MOLS of order \(n\) is called a complete set if it contains \(n-1\) Latin squares. It is a well-known fact that there is a one-to-one correspondence between the set of Latin squares of order a prime power \(q\) and the set of bivariate LPPs over the finite fields of order \(q\). Likewise, an orthogonal Latin square of the Latin square associated with a particular bivariate LPP corresponds to an orthogonal LPP, also referred to as a companion, associated with that LPP. Consequently, constructing an LPP (or a companion) is essentially the same as constructing a Latin square (or an orthogonal Latin square). \N\NRecently, \textit{J. Gutierrez} and \textit{J. Jiménez Urroz} [Finite Fields Appl. 91, Article ID 102261, 22 p. (2023; Zbl 1541.11103)] established a one-to-one correspondence between bivariate LPPs and a specific type of \(q\)-tuples of permutation polynomials in one variable over the finite fields with \(q\) elements. They then used this correspondence to construct a family of bivariate LPPs based on a class of symmetric subgroups without fixed points, known as \(e\)-Klenian groups. We refer to the LPPs in this family as e- Klenian polynomials. In the paper under review, motivated by the work of Gutierrez and Urroz, the authors construct three new families of bivariate LPPs based on certain subgroups of the symmetric group of permutations on \(q\) symbols. In [loc. cit.], \textit{J. Gutierrez} and \textit{J. Jiménez Urroz} showed the existence of a companion for the \(e\)-Klenian polynomials over finite fields of odd characteristic. For even characteristic, the authors presented some computational results regarding the companions of the \(e\)- Klenian polynomials. In the paper under review, the authors prove the existence of a companion for the \(e\)-Klenian polynomials over finite fields of even characteristic for all \(e \geq 1\). However, for \(e=0\), the authors show that \(e\)-Klenian polynomials over finite fields of even characteristic do not have any companion. They also provide an explicit expression of a companion for each of their families of LPPs.

Cites work

This page was built for publication: Local permutation polynomials and their companions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6924370)