Discrete Functions

Mixing properties for some classes of permutations on $\mathbb{F}_2^n$

L. A. Karpova, I. A. Pankratova

Tomsk State University

Abstract: In the class $\mathcal{F}_{n,k}$ of permutations on $\mathbb{F}_2^n$ with coordinate functions essentially depending on exactly $k$ variables, $k<n$, we consider two subclasses $S_{n,k}$ and $P_{n,k}$. The method for constructing a function $F(x_1,\ldots,x_n)=(f_1,\ldots,f_n)\in S_{n,k}$ starts from some function $G(x_1,\ldots,x_k)=(g_1,\ldots, g_k)\in \mathcal{F}_{k,k}$. Then we set $f_i(x_1,\ldots,x_n)=g_i(x_1,\ldots,x_k)$ for $i=1,\ldots,k$ and $f_i(x_1,\ldots,x_n)=x_i\oplus h_i(x_1,\ldots,x_{i-1})$ for $i=k+1,\ldots,n$, where $h_i$ is any function essentially depending on exactly $k-1$ variables from $x_1,\ldots,x_{i-1}$. The method for constructing a function $F\in P_{n,k}$ is used in the case when $k|n$, i.e. $n=sk$ for some $s\in\mathbb{N}$. We construct $s$ functions $G_1,\ldots,G_s\in\mathcal{ F}_{k,k}$, $G_i=\left(g_1^{(i)},\ldots,g_k^{(i)}\right)$, $i=1,\ldots,s$, and set $f_{tk+i}(x_1,\ldots,x_n)=g_i^{(t+1)}(x_{tk+1},\ldots,x_{(t+1)k})$, $t=0,\ldots,s-1$, $i=1,\ldots,k$. Mixing properties of such function are discussed, an algorithm for calculating elementary exponents is given.

Keywords: essential dependence of a function on a variable, mixing properties of the function, elementary exponent.

UDC: 519.7

DOI: 10.17223/2226308X/12/13

Bibliographic databases:

•