Theoretical Backgrounds of Applied Discrete Mathematics
The number of occurrences of elements from a given subset on the complication segments of linear recurrence sequences
A. S. Tissin Certification Research Center, LLC, Moscow, Russia
Abstract:
Let
$v$ be a sequence constructed by the rule
$v(i) = f(u_1(i),\ldots, u_k(i))$,
$i \geq 0$, where
$u_1,\ldots,u_k$ are linear recurrence sequences over the field
$P$ with characteristic polynomial
$F(x)$. We study the value
$N_l(H,v)$, which is equal to the number of occurrences of elements from the subset
$H\subset P$ among the elements
$v(0),v(1),\ldots,v(l-1)$. We have obtained non-trivial estimates for the value
$N_l(H,v)$ and considered special cases when the set
$H$ is a subgroup of the group
$P^*$,
$H$ is the set of all primitive elements of the field
$P$. Results are generalized to the case of
$r$-tuples for the value $N_l(H,\vec{s},v) = \left|\{i \in \{0,\ldots, l-1\}: v(i + s_1) \in H, \ldots, v(i + s_r) \in H \}\right|$, where
$\vec{s} = \left(s_1,\ldots,s_r\right) $ is a set of non-negative integers.
Keywords:
finite fields, filter generators, discrete function curvature, linear recurrence sequences, characters of abelian group.
UDC:
519.4
DOI:
10.17223/20710410/60/3