Occurrence indices of elements in linear recurrence sequences over primary residue rings
Даниил Николаевич Былков, Олег Витальевич Камловский · Problems of Information Transmission · 2008
We study distances to the first occurrence (occurrence indices) of a given element in a linear recurrence sequence over a primary residue ring $$ \mathbb{Z}_{p^n } $$ . We give conditions on the characteristic polynomial F(x) of a linear recurrence sequence u which guarantee that all elements of the ring occur in u. For the case where F(x) is a reversible Galois polynomial over $$ \mathbb{Z}_{p^n } $$ , we give upper bounds for occurrence indices of elements in a linear recurrence sequence u. A situation where the characteristic polynomial F(x) of a linear recurrence sequence u is a trinomial of a special form over ℤ4 is considered separately. In this case we give tight upper bounds for occurrence indices of elements of u.