Abstract:
Let $u$ be a linear recurring sequence (LRS) over a finite commutative
local ring $R$ with identity, and let $\Phi(x)\in R[x]$. We find a
characteristic polynomial $H(x)$ and prove an upper estimate for
the rank (linear complexity) over $R$ of the sequence $v=\Phi(u)$.
If $\bar u$ is an $m$-sequence over the residue field
$\bar R=R/J(R)=GF(q)$ of the ring $R$ and $\deg\Phi(x)\le q-1$,
then this estimate is attained and $H(x)$ is a minimal polynomial of $v$.
Analogous results are obtained for the sequence
$v=\Phi(u_1, \ldots, u_K)$ which is a polynomial transform of
$K$ linear recurrences $u_1, \ldots, u_K$ over $R$.