On mixing digraphs of nonlinear substitutions for binary shift registers
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 (x1,...,xn) = x1 ф ^(x2,...,xn) essentially depending on m variables, 3 ^ m ^ n. We have obtained the following double-ended estimate for the exponent of the mixing digraphs r(g) for nonlinear substitutions g £ R(n, m): - 1 ^ exp r(g) ^ A(D) + n + (n - 2)2 n - 1 m1 1 n + where D = {i1,...,im} is the set of indexes of essential variables of the shift register feedback function f, 1 = i1 m ^ n, m ^ n; A(D) = max{i2 - i1,..., im - im-1, n - im}. We have also obtained some upper-bound estimates for the sum and for the ratio of exponents of mixing digraphs of substitution g £ R(n,m) and its inverse substitution g-1: n2 m A(D) + n + (n - - 2)2 2 _ -1 n+ n - 1" -1 m - 1 exp r(g) + exp r(g-1) ^ 2 ^A(D) + + im exp r(g) expr(g-1)