The asymptotic normalized linear complexity of multisequences (Q933420)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The asymptotic normalized linear complexity of multisequences
scientific article

    Statements

    The asymptotic normalized linear complexity of multisequences (English)
    0 references
    21 July 2008
    0 references
    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.
    0 references
    linear complexity
    0 references
    multisequence
    0 references
    battery discharge model
    0 references
    isometry
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references