Abstract:
In this paper, we research the class $R(n,m)$ of substitutions on $n$-dimensional vector space produced by the binary left-shift registers of the length $n$ with one feedback $f(x_1,\dots,x_n)=x_1\oplus\psi(x_2,\dots,x_n)$ essentially depending on $m$ variables, $3\le m\le n$. We have obtained the following double-ended estimate for the
exponent of the mixing digraphs $\Gamma(g)$ for nonlinear substitutions $g\in R(n,m)$:
$$
n+\left\lceil\frac{n-1}{m-1}\right\rceil-1\le\exp{\Gamma(g)}\le\Delta(D)+n+\left\lfloor\frac{(n-2)^2}2\right\rfloor-1,
$$
where $D(g)=\{i_1,\dots,i_m\}$ is the set of indexes of essential variables of the shift register feedback function $f$, $1=i_1<\dots<i_m\le n$, $m\le n$; $\Delta(D)=\max\{i_2-i_1,\dots,i_m-i_{m-1},n-i_m\}$. We have also obtained some upper-bound estimates for the sum and for the ratio of exponents of mixing digraphs of substitution $g\in R(n,m)$ and its inverse substitution $g^{-1}$:
\begin{gather*}
\exp{\Gamma(g)}+\exp{\Gamma(g^{-1})}\le2\left(\Delta(D)+\left\lfloor\frac{n^2}m\right\rfloor\right)+i_m,\\
\frac{\exp{\Gamma(g)}}{\exp{\Gamma(g^{-1})}}\le\frac{\Delta(D)+n+\left\lfloor\frac{(n-2)^2}2\right\rfloor-1}{n+\left\lceil\frac{n-1}{m-1}\right\rceil-1}.
\end{gather*}
Fulltext:
PDF file (553 kB)