On the minimum linear complexity of de Bruijn sequences over non-prime finite fields (Q1284473)

It is known that the maximum possible linear complexity of a span \(n\) de Bruijn sequence over the finite field \({\mathbb F}_{p^m}\) is \(p^{mn}-1\) and such a sequence may be constructed in a straightforward manner. The situation regarding the minimum linear complexity has proved more complex. \textit{S. R. Blackburn, T. Etzion} and \textit{K. G. Paterson} [J. Comb. Theory, Ser. A 76, No. 1, 55-82 (1996; Zbl 0871.11089)] showed that the linear complexity was never less than \(p^{mn-1}+n\) and for \(m\geq 2\) the lower bound is realized for some \(n\) including \(n=2\). They conjectured that for \(m\geq 2\) this lower bound is always realized. This conjecture is proved completely in the paper under reviewing. The proof is constructive. It seems that the better minimum for an odd prime field (i.e. \(m=1\)) is yet to be found. Some partial solution for this case was also given in the paper mentioned above.