Geodesic
The number of occurrences of elements from~a~given~subset on~the complication segments of~linear~recurrence sequences
Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 30-39.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{PDM_2023_2_a2,
     author = {A. S. Tissin},
     title = {The number of occurrences of elements from~a~given~subset on~the complication segments of~linear~recurrence sequences},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {30--39},
     publisher = {mathdoc},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2023_2_a2/}
}
TY  - JOUR
AU  - A. S. Tissin
TI  - The number of occurrences of elements from~a~given~subset on~the complication segments of~linear~recurrence sequences
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2023
SP  - 30
EP  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2023_2_a2/
LA  - ru
ID  - PDM_2023_2_a2
ER  - 
%0 Journal Article
%A A. S. Tissin
%T The number of occurrences of elements from~a~given~subset on~the complication segments of~linear~recurrence sequences
%J Prikladnaâ diskretnaâ matematika
%D 2023
%P 30-39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2023_2_a2/
%G ru
%F PDM_2023_2_a2
A. S. Tissin. The number of occurrences of elements from~a~given~subset on~the complication segments of~linear~recurrence sequences. Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 30-39. http://geodesic.mathdoc.fr/item/PDM_2023_2_a2/

[1] Kamlovskiy O. V., “Distribution properties of sequences produced by filtering generators”, Prikladnaya Diskretnaya Matematika, 2013, no. 3(21), 11–25 (in Russian) | Zbl

[2] Korobov N. M., “Distribution of non-decomposable and first-order roots in recurrence series”, Dokl. AS USSR, 88:4 (1953), 603–606 (in Russian) | Zbl

[3] Vinogradov I. M., Fundamentals of Number Theory, Nauka Publ., M., 1972, 168 pp. (in Russian) | MR

[4] Kamlovskiy O. V., “Non-absolute estimates for incomplete trigonometric sums from linear recurrences and their applications”, Matem. Vopr. Kriptogr., 65:3 (2014), 17–34 (in Russian) | DOI

[5] Nechaev V. I. and Stepanova L. L., “Distribution of non-decomposables and first-order roots in recurrence sequences over a field of algebraic numbers”, Uspekhi Matem. Nauk, 20:3 (1965), 197–203 (in Russian) | MR | Zbl

[6] Lidl R. and Niderrayter G., Finite Fields, Mir Publ., M., 1988, 822 pp. (in Russian)

[7] Sidel'nikov V. M., “Estimates for the number of occurrences of signs in recurrence sequence segments over a finite field”, Diskretnaya Matematika, 3:2 (1991), 87–95 (in Russian) | Zbl

[8] Logachev O. A., Fedorov S. N., and Yashchenko V. V., “Boolean functions as points on a hypersphere in Euclidean space”, Diskretnaya Matematika, 30:1 (2018), 39–55 (in Russian) | DOI | MR

[9] Shparlinskiy I. E., “Distribution of non-decomposable and first-order roots in recurrence sequences”, Matem. Zametki, 24:5 (1978), 603–613 (in Russian) | MR | Zbl

[10] Shparlinskiy I. E., “On the distribution of values of recurrent sequences”, Problemy Peredachi Informatsii, 25:2 (1989), 46–53 (in Russian) | MR | Zbl