Linear recurring sequences over Galois rings (Q1908455): Difference between revisions

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.\)