Permutation Polynomials, de Bruijn Sequences, and Linear Complexity

The paper establishes a connection between the theory of permutation polynomials and the question of whether a de Bruijn sequence over a general finite field of a given linear complexity exists. The connection is used both to construct span 1 de Bruijn sequences (permutations) of a range of linear complexities and to prove non-existence results for arbitrary spans. Upper and lower bounds for the linear complexity of a de Bruijn sequence of spannover a finite field are established. Constructions are given to show that the upper bound is always tight, and that the lower bound is also tight in many cases.