On the distribution of de Bruijn sequences of low complexity (Q1069308)

The paper deals with a problem of complexity of de Bruijn sequences of order n, i.e. binary sequences \(s=s_ 0,\ldots,s_{2^ n-1}\) satisfying a recurrence equation of the following type: \(f(s_ i,\ldots,s_{i+n-1})+s_{i+n}=0\) (for \(0\leq i\leq 2^ n-1\) and with the other coefficients taken modulo \(2^ n)\) where n is the smallest number for which such a recurrence holds. Because of numerous applications, since a long time the problem of synthesis of de Bruijn sequences has been considered, but the complexity problem has been clearly formulated not so long ago. In the last years there appeared papers dealing with the so called linear complexity of de Bruijn sequences meant as the smallest number m such that \(\sum^{m}_{j=1}a_ js_{i+m-j}+s_{i+m}=0\), in GF(2), for some binary digits \(a_ 1,\ldots,a_ m\). It is known that \(2^{n-1}+n\leq m\leq 2^ n-1\). There exist many open problems for such a notion of complexity. This paper solves some of them for the sequences whose complexity is between \(2^{n-1}+n\) and \(2^{n-1}+2^{n-2}\). The application of an interesting technique allows to evaluate the number of such sequences and to give a recursive method to generate sequences of complexity \(2^{n-1}+2^{n-2}\).