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 (x<sub>1</sub>,...,x<sub>n</sub>) = x<sub>1</sub> ф ^(x<sub>2</sub>,...,x<sub>n</sub>) 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)<sup>2</sup> n - 1 m1 1 n + where D = {i<sub>1</sub>,...,i<sub>m</sub>} is the set of indexes of essential variables of the shift register feedback function f, 1 = i<sub>1</sub> <... < i<sub>m</sub> ^ n, m ^ n; A(D) = max{i<sub>2</sub> - i<sub>1</sub>,..., i<sub>m</sub> - i<sub>m-1</sub>, n - i<sub>m</sub>}. 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<sup>-1</sup>: <sub>n</sub>2 m A(D) + n + (n - - 2)<sup>2 </sup>2 _ -1 n+ n - 1" -1 m - 1 exp r(g) + exp r(g<sup>-1</sup>) ^ 2 ^A(D) + + im <sup>ex</sup>p <sup>r(</sup>g<sup>) ex</sup>p<sup>r(</sup>g<sup>-1)</sup>