The number of occurrences of elements from~a~given~subset on~the complication segments of~linear~recurrence sequences

A. S. Tissin

Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 30-39

Résumé

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.

Détail

Keywords: finite fields, filter generators, discrete function curvature, linear recurrence sequences, characters of abelian group.