Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles (Q1296526)

The linear complexity of a sequence of finite length over a finite field \({\mathbb F}_q\) is the shortest length of a linear feedback shift register generating the sequence. The linear complexity profile (l.c.p.) of an arbitrary sequence \(\underline{a} = (a_i)_{i=1}^{\infty}\) from \({\mathbb F}_q^{\infty}\) is the sequence \((L_{\underline{a}} (t))_{t=1}^{\infty}\). A \(d\) perfect sequence \(\underline{a}\) has the property \[ |2 \cdot L_{\underline{a}} (t) -t |\leq d \] for every length \(t \in {\mathbb N}\). The case of \(d=1\) corresponds to a perfect l.c.p. in the previous literature. For any \(d \in {\mathbb N}\) the set of all \(d\)-perfect sequences over \({\mathbb F}_q\) has uncountably many elements. On the other hand this set has measure zero in the space \(({\mathbb F}_q^{\infty} , {\mu}^{\infty})\) where \(\mu\) is the equidistribution measure on \({\mathbb F}_q\) i.e. \(\mu (k) = 1/q ~ \forall k \in {\mathbb F}_q\). The set of interest can be distinguished further by their Hausdorff dimension. Thus the Hausdorff dimension of 1-perfect sequences is 0.5 and the \(d\)-perfect sequences over any \({\mathbb F}_q\) have higher Hausdorff dimension although less than unity. In addition the number of \(d\)-sequences of length \(t\), for all \(d\) and \(t\), is given for all finite fields \({\mathbb F}_q\). The second part considers the case when the condition is relaxed to \( |2 \cdot L_{\underline{a}} (t) -t |\leq d(t)\) where \(d(t)\) is a non-decreasing function on the positive integers. It is shown that \(d(t) = 1 +(1+\varepsilon) \cdot {\log}_q (t)\) gives the threshold between sequences of measure zero (\(\varepsilon =0\)) and positive measure (\(\varepsilon >0\)).