Perfect linear complexity profile and apwenian sequences (Q1994979): Difference between revisions

A measure of the randomness of a binary sequence is its linear complexity profile. Certain sequences are said to have prefect linear complexity profile. These are the sequences with most random behaviour for this measure. If \((s_m)_{m \ge 1}\) has perfect complexity profile, all partial quotients of the simple continued fraction expansion of the formal power series \(\sum_{i \ge 1} s_i T^{-i}\) over the field of two elements have degree \(1\). The converse is also true, classifying such sequences in terms of continued fractions. In an entirely different direction of research, the notion of an apwenian sequence recently occurred. These are binary sequences \((c_n)_{n \ge 0}\) for which all Hankel determinants are odd. In the present paper, it is observed that the two types of sequences are in fact the same up to a shift of index by \(1\). The automaticity of such sequences is studied, and a number of questions and problems arising from combining the two viewpoints are described.