Linear recurring sequences over Galois rings (Q1908455)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Linear recurring sequences over Galois rings
scientific article

    Statements

    Linear recurring sequences over Galois rings (English)
    0 references
    27 March 1996
    0 references
    Let \(R=GR(q^n,p^n)\) be a Galois ring of characteristic \(p^n\) consisting of \(q^n\) elements, \(q=p^r,\) \(p\) a prime. Let \(u=(u(0),u(1),\dots )\) be a linear recurring sequence over \(R\) with a reversible characteristic polynomial \(F(x) \in R[x]\) of degree \(m.\) A set \(K \subset R\) is called a coordinate subset if the natural injection \(\mu : K \rightarrow {\bar R}= R/pR\) is a bijection. Then there exist for each \(i \in {\mathbb N}\) a \(w_j(i) \in K\) with \[ u(i) = \sum_{j=0}^{n-i} w_j(i) p^j. \] The sequences \(w_0,\dots ,w_{n-1}\) are called the coordinate sequences of \(u.\) This paper deals with the length of period \(T(w_{\tau})\) with the characteristic polynomial \(M_{w_{\tau}}(x) \in {\bar R} [x]\) and the rank, i.e. the degree of \(M_{w_{\tau}}(x)\) of the coordinate sequences of \(u\) provided \(u\) is a sequence of maximal period over \(R.\) It is proved for example that \(T(w_0)= q^m-1, \text{rank} w_0=m\) and for \(s \geq 1\) \[ T(w_s)=(q^m-1)p^s, \quad \text{rank} w_s \geq m (p^{s-1}+1). \] In the special case \(R={\mathbb Z}_{p^n}, n>1\) much sharper lower bounds and the non-trivial upper bound \[ \text{rank} w_s \leq m(p^{s-1} +1) + \sum_{k=0}^{p^{s-1}-1}(k+1) \sum_{N=d_0(k)}^{d_1(k)} \left \{ \begin{matrix} m \\ N \end{matrix} \right \} \] are proved. Here \(\left \{ \begin{matrix} m \\ N \end{matrix} \right \} \) denotes the cardinality of the set \[ \{ (k_0, \dots , k_{m-1} ) \in {\mathbb N}^m : k_0+ \dots + k_{m-1} = N; k_0, \dots , k_{m-1} \in \{ 0,\dots , p-1 \} \} \] and \(d_0(k), d_1(k)\) are constants depending only on \(p\) and \(k.\)
    0 references
    Galois ring
    0 references
    linear recurring sequence
    0 references
    0 references
    0 references
    0 references

    Identifiers