Polynomial transformations of linear recurrent sequences over the ring $\mathbf Z_{p^2}$

V. L. Kurakin

Diskretnaya Matematika, Tome 11 (1999) no. 2, pp. 40-65.

Résumé

Let $u$ be a linear recurring sequence (LRS) over the ring $R=\mathbf Z_{p^2}$ with absolutely irreducible characteristic polynomial $F(x)\in R[x]$, and $\Phi(x_1,\ldots, x_s)\in R[x_1,\ldots, x_s]$. We give an upper bound for the rank (the degree of a minimal polynomial) of the sequence $$ v(i) = \Phi(u(i), u(i+1),\ldots, u(i+s-1)) $$ over $R$. In the special case, where $\bar u$ is a maximal LRS over the field $\bar R=R/pR=GF(p)$, and $\Phi(x)\in R[x]$ is a polynomial in one variable of degree less than $p$, an exact formula for the rank of the sequence $v(i)=\Phi(u(i))$ over $R$ is obtained. An upper bound for the rank of the sequence $v(i)= \Phi(u_1(i),\ldots,u_s(i))$ over $R$ is also given, where $u_t$ is a LRS over $R$ with absolutely irreducible characteristic polynomial $F_t(x)\in R[x]$, $t=1,\ldots,s$, and $\Phi(x_1,\ldots, x_s)\in R[x_1,\ldots, x_s]$. If $m_1,\ldots,m_s$ are pairwise relatively prime, $\bar u_t$ is a maximal LRS over the field $\bar R$, and the degree of $\Phi(x_1,\ldots, x_s)$ in $x_t$ is less than $\min\{p, m_t, m_t(p-2)/(p-1) + 1\}$, $t=1,\ldots,s$, the exact formula for the rank of the sequence $v$ over $R$ is obtained.