The asymptotic normalized linear complexity of multisequences (Q933420): Difference between revisions

Let \(q\) be a prime power and \({\mathbb F}_q\) the finite field of order \(q\). Let \(M \in {\mathbb N}\). For all multisequences \(a = (a_{m,t}) \in {\mathbb F}_q^{M\times{\mathbb N}}\) and all \(m \in [M] := \{1, \dots , M\}\) the authors denote by \(G_m\) the formal power series \[ G_m := \sum_{t=1}^{\infty}a_{m,t}x^{-t} \in {\mathbb F}_q[x^{-1}]. \] The linear complexity \(L_a\) of a multisequence \(a \in {\mathbb F}_q^{M\times{\mathbb N}}\) is defined through \[ L_a(n) := \min\{ \deg{v} \mid v \in {\mathbb F}_q[x] ,\quad \forall m \in [M] \quad \exists u_m \in {\mathbb F}_q[x]:\;G_m = \frac{u_m(x)}{v(x)} + o(x^{-n})\}. \] for all \(n \in {\mathbb N}\). The asymptotic lower bound for the normalized linear complexity of a multisequence \(a \in {\mathbb F}_q^{M\times{\mathbb N}}\) is then defined by \[ I := \liminf_{n \to \infty} \frac{L_a(n)}{n}. \] The asymptotic upper bound for the normalized linear complexity of a multisequence \(a \in {\mathbb F}_q^{M\times{\mathbb N}}\) is defined similarly as \[ S := \limsup_{n \to \infty} \frac{L_a(n)}{n}. \] It is shown that if for all \(m \in [M]\) the sequence \((a_{m,t})_{t \in {\mathbb N}}\) has nonzero discrepancy infinitely often (here the definition of discrepancy is taken from [\textit{Z. Dai, X. Feng} and \textit{J. Yang}, SETA 2004, Lect. Notes Comput. Sci. 3486, 339--354 (2005; Zbl 1145.94413)], where it is defined for \(q=2\)), then it holds that \[ \frac{M}{M+1} \leq S \leq 1 \quad\text{and}\quad M(1-S) \leq I \leq 1-\frac{S}{M}. \] This answers an Open Problem posed in [\textit{Z. Dai, K. Imamura} and \textit{J. Yang}, SETA 2004, Lect. Notes Comput. Sci. 3486, 129--142 (2005; Zbl 1145.94414)]. Furthermore it is shown that for all \((I,S)\) there are \(\left| {\mathbb F}_q^{M\times{\mathbb N}} \right|\) multisequences having \(I,S\) as respective bounds.