$2$-Transitivity degree for one class of~substitutions over finite fields

D. H. Hernández Piloto

Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 19-26.

Résumé

The paper deals with the class of substitutions proposed by A. V. Abornev, constructed using digit functions $\gamma_1$ over the ring $\mathbb{Z}_{p^2}$ of the form $h(\vec{x})=\vec{z}$, where $\vec{z}=\vec{z}_1+p\vec{z}_2 $, $(\vec{z}_1 | \vec{z}_2)=\gamma_1(\vec{x}K)$ and $K$ is a matrix of dimensions $m\times2m$. We consider a generalization of this class of substitutions using arbitrary functions $F:P^{m}\rightarrow P^{m}$ over finite field $P$ in the place of the digit functions $\gamma_1$. A set $\Sigma$ is called $2$-transitive if for any pairs $\alpha=(a_1,a_2)$, $\beta=(b_1,b_2)$ in $\Sigma$ there exists a substitution $g$, such that $g(a_i)=b_i$, $i \in \{1,2\}$. We are interested in the degree of $2$-transitivity of a group $\Sigma$, denoted by $d_2(\Sigma)$, which is equal to the smallest natural value $k$, such that $(\Sigma)^k$ is a $2$-transitive group. The main goal is to find groups of substitutions with the minimum of this parameter. Using our construction, it is demonstrated that the degree of $2$-transitivity is lower bounded by $4$. When $F(x+a)-F(x)$ is a substitution for any $a\in P^m \backslash \{\mathbf{0}\}$, the degree of $2$-transitivity of the composition $\Sigma h$ is equal to $4$. In other papers these functions were called planar. Notice that in a field with characteristic $2$ planar functions do not exist. If the characteristic is not $2$, then these functions exist. Indeed, if $Q$ is an extension of degree $m$ of $P$, $\hat F(x)=x^2$ for all $x\in Q$, and $\alpha_1,\ldots,\alpha_m$ is the base of the vector space $Q_P$, then the function $F(x_1,\ldots, x_m)=\hat F(\alpha_1x_1+\ldots+\alpha_mx_m)$, $x_1,\ldots,x_m\in P$, is planar.

Détail

Keywords: transitivity, degree of $2$-transitivity, digit function, regular group
Mots-clés : substitution.

Bibliographie

[1] Abornev A. V., “Substitutions induced by digit-injective transformations of a module over a Galois ring”, Prikladnaya Diskretnaya Matematika, 2013, no. 4, 5–15 (in Russian)

[2] Glukhov M. M., “On 2-transitivity of the composition of regular substitution groups”, Trudy po Diskretnoy Matematike, Fizmatlit Publ., M., 2000, 37–52 (in Russian)

[3] Glukhov M. M., “On the approximation of discrete functions by linear functions”, Matematicheskie Voprosy Kriptografii, 7:4 (2016), 29–50 (in Russian) | DOI | MR