Reconstruction of a~linear recurrence of maximal period over a~Galois ring from its highest coordinate sequence

A. S. Kuzmin ; A. A. Nechaev

Diskretnaya Matematika, Tome 23 (2011) no. 2, pp. 3-31

Résumé

Let $R=GR(q^n,q^n)$ be a Galois ring of cardinality $q^n$ and characteristic $p^n$, $q=p^r$, $p$ be a prime. We call a subset $K\subset R$ a coordinate set if $0\in K$ and for any $a\in R$ there exists a unique $\varkappa(a)\in K$ such that $a\equiv\varkappa(a)\pmod{pR}$. Let $u$ be a linear recurring sequence of maximal period (MP LRS) over a ring $R$. Then any its term $u(i)$ admits a unique representation in the form $$ u(i)=w_0(i)+pw_1(i)+\dots+p^{n-1}w_{n-1}(i),\qquad w_t(i)\in K,\quad t\in\{0,\dots,n-1\}. $$ We pose the following conjecture: the sequence $u$ can be uniquely reconstructed from the sequence $w_{n-1}$ for any choice of the coordinate set $K$. It is proved that such a reconstruction is possible under some conditions on $K$. In particular, it is possible for any $K$ if $R=\mathbf Z_{p^n}$ and for any Galois ring $R$ if $K$ is a $p$-adic (Teichmüller) coordinate set.