RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2023 Number 60, Pages 30–39 (Mi pdm800)

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



© Steklov Math. Inst. of RAS, 2024