On the $N$th linear complexity of automatic sequences

Abstract

The $N$th linear complexity of a sequence is a measure of predictability. Any unpredictable sequence must have large $N$th linear complexity. However, in this paper we show that for $q$-automatic sequences over ${\mathbb{F}}_q$ the converse is not true. We prove that any (not ultimately periodic) $q$-automatic sequence over ${\mathbb{F}}_q$ has $N$th linear complexity of order of magnitude $N$. For some famous sequences including the Thue--Morse and Rudin--Shapiro sequence we determine the exact values of their $N$th linear complexities. These are non-trivial examples of predictable sequences with $N$th linear complexity of largest possible order of magnitude.