On the \(N\)th linear complexity of automatic sequences (Q1747239)

For a prime power \(q\), a \(q\)-automatic sequence \((u_n)\) over the alphabet \(\mathbb{F}_q\) is the output of a finite automaton whose input is the \(q\)-ary digital expansion of \(n\). By a result of Christol, \((u_n)\) is \(q\)-automatic over \(\mathbb{F}_q\) if and only if the generating function \(G(t)=\sum_{n=0}^\infty u_nt^n\) is algebraic over \(\mathbb{F}_q[t]\). The \(N\)-th linear complexity \(L(u_n, N)\) of \((u_n)\) over \(\mathbb{F}_q\) is the length \(L\) of a shortest linear recurrence over \(\mathbb{F}_q\) satisfied by the first \(N\) elements of \((u_n)\). The linear complexity of \((u_n)\) is \(L(u_n)=\sup_{N\geq 1} L(u_n,N)\). Ultimately periodic sequences are automatic and correspond to rational generating functions. They have finite linear complexity. The authors show, using properties of the the algebraic generating function, that if \((u_n)\) is automatic but not ultimately periodic then the \(N\)-th linear complexity is of order \(N\), the largest possible order of magnitude. They derive explicit values for the linear complexity of a number of examples of automatic sequences and find a connection between the linear complexity profile of a binary sequence and the continued fraction expansion of its generating function. Since automatic sequences are highly predictable, the results confirm that a large linear complexity does not guarantee unpredictability.