Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles
type: Item
instance of: scholarly article
title: Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles
zbMATH Open document ID: 0934.94013
author: Harald Niederreiter
author: Michael Vielhaber
published in: Journal of Complexity
publication date: 2000-04-24T00:00:00Z
review text: 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\)).
Mathematics Subject Classification ID: 94A55
zbMATH DE Number: 1319717
zbMATH Keywords: pseudorandom sequences
zbMATH Keywords: linear complexity profiles
zbMATH Keywords: Hausdorff dimension
reviewed by: Ian Blake
MaRDI profile type: Publication
full work available at URL: jcom.1997.0451
OpenAlex ID: W2034856607
DOI: 10.1006/JCOM.1997.0451
description: scientific article; zbMATH DE number 1319717