Theoretical Backgrounds of Applied Discrete Mathematics
$2$-Transitivity degree for one class of substitutions over finite fields
D. H. Hernández Piloto Certification Research Center, Moscow, Russia
Abstract:
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.
Keywords:
transitivity, degree of $2$-transitivity, digit function, regular group, substitution.
UDC:
621.391:519.7+621.391.1:004.7
DOI:
10.17223/20710410/46/2