Counting functions and expected values for the lattice profile at \(n\) (Q2566959)

Let \(\eta= (\eta_1,\eta_2,\dots)\) be a sequence over the finite field \(\mathbb F_q\). We say that \(\eta\) passes the \(S\)-dimensional \(n\)-lattice test \((n\geq 2)\) if the vectors \(\{\eta_j- \eta_1\mid 2\leq j\leq n- S+ 1\}\text{\,span\,}\mathbb F^S_q\), where \(\eta_j= (\eta_j, \eta_{j+1},\dots, \eta_{j+S-1})\), \(1\leq j\leq n-S+ 1\). For \(n\geq 2\), let \(S_n(\eta)\) be the greatest \(S\) such that \(\eta\) passes the \(S\)-dimensional \(n\)-lattice test, and call it the \(n\)th lattice level of \(\eta\) (or the lattice profile of \(\eta\) at \(n\)). We also define \(S_0(\eta)= S_1(\eta)= 0\). Basing on the earlier works by the first and the third author [Appl. Algebra Eng. Commun. Comput. 13, No. 6, 499--508 (2003 Zbl 1026.11064); Lect. Notes Comput. Sci. 2948, 69--78 (2004; Zbl 1058.65009)], the authors determine the number of sequences \(\eta\) over \(\mathbb F_q\) of length \(n\) with \(S_n(\eta)= S\) (\(n\geq 1\), \(S\geq 0\)), and give the exact formulas for the expected value and the variance of the \(n\)th lattice level of an arbitrary sequence \(\eta\) over \(\mathbb F_q\). Further, they also determine the number of finite sequences over \(\mathbb F_q\) with length \(n\), linear complexity \(L\) and the \(n\)th lattice level \(S\). Moreover, in the binary case, they show that the infinite sequence \(\eta\) has maximal possible \(n\)th lattice level for all \(n= 0,1,\dots\) (i.e. \(S_n(\eta)= \lfloor n/2\rfloor\) for all \(n\geq 0\)) if and only if \(\eta_i+ \eta_{2i}= 1\) for \(i= 1,2,\dots\).