Linear complexity profile of binary sequences with small correlation measure (Q2466313): Difference between revisions

The linear complexity profile \(L(s_n,N)\) of a sequence \((s_n), n=0,1\dots\) over the field \(\mathbb F_2\) is the function which for every integer \(N \geq 2\) is defined as the shortest length \(L\) of a recurrence relation over \(\mathbb F_2\) the first \(N\) terms of the sequence satisfy. For a \(T\)-periodic binary sequence \((s_n)\), \textit{C. Mauduit} and \textit{A. Sárközy} [Acta Arith. 82, 365--377 (1997; Zbl 0886.11048)] introduced the correlation measure \(C_k(s_n)\) of order \(k \geq 1\) defined by \[ C_k(s_n) = \max_{M,D}\left| \sum_{n=0}^{M-1}(-1)^{s_{n+d_1}+s_{n+d_2}+\cdots+s_{n+d_k}}\right| ,\tag{1} \] where the maximum is taken over all \(D = (d_1,d_2,\dots,d_k)\) with nonnegative integers \(d_1 < d_2 < \dots < d_k\) and \(M\) such that \(M-1+d_k \leq T-1\). The authors discover a relation between these two complexity measures, namely \[ L(s_n,N) \geq N - \max_{1\leq k\leq L(s_n,N)+1}C_k(s_n), \] for \(2 \leq N \leq T-1\) (Theorem 1). Then they apply this relation to known results on the pseudorandomness measure (1) to obtain results on the linear complexity profile of the discrete logarithm threshold sequence (cf. \textit{A. Sárközy} [Studia Sci. Math. Hung. 38, 377--384 (2001; Zbl 0997.11062)]), the Legendre sequence and the two-prime generator. Finally the authors estimate \(C_k(e_n)\) for the binary Sidel'nikov sequence \((e_n)\), and present the resulting estimation for \(L(e_n,N)\).