Permutation polynomials, de Bruijn sequences, and linear complexity (Q1924236)

A periodic sequence \(s\) over the finite field \(F=GF(p^n)\) is called a span \(n\) de Bruijn sequence if each \(n\)-tuple of elements of \(F\) appears exactly once as a window of \(n\) consecutive terms in a period of the sequence. De Bruijn sequences have been widely studied because of their equivalence with Hamiltonian cycles in the de Bruijn graph. The degree of the shortest linear recurrence which generates the sequence \(s\) is called the linear complexity of \(s\). For \(p=2\), the linear complexity has been thoroughly investigated. The present paper extends this investigation to general finite fields, where both results and techniques vary considerably from those in the binary case. The basic goal of the paper is to determine as much as possible about the range of values of the linear complexity \(c\) of span \(n\) de Bruijn sequences. Both nonexistence results and families of examples are given. A sharp upper bound on \(c\) is obtained and significant evidence is obtained to show that a certain lower bound may be sharp. Many of the results are obtained with the help of a connection established between the theory of permutation polynomials and de Bruijn sequences of a given linear complexity.