De Bruijn sequences, irreducible codes and cyclotomy (Q1126191)

A de Bruijn sequence of order \(n\) is a binary sequence with period \(2^n\) which contains all binary \(n\)-tuples. They are defined by nonlinear feedback functions. The most of the algorithms for generating de Bruijn sequences are variants of the cycle join algorithms (CJA). Each of these algorithms finds a spanning tree in the undirected graph (\textit{adjacency graph}) defined by a feedback function (\textit{starting function}). In this paper, the adjacency graphs of linear feedback functions whose characteristic polynomials are irreducible, are analysed. For such functions a lower bound for the number of de Bruijn sequences that can be obtained, is given. This generalizes the class of the sequences corresponding to the feedback function of which the characteristic polynomials are primitive.