Geodesic
Bounds on the discrepancy of linear recurring sequences over Galois rings
Diskretnaya Matematika, Tome 31 (2019) no. 3, pp. 17-25.

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

We study the discrepancy of linear recurring sequences over Galois rings. By means of an estimate of an exponential sum some nontrivial bounds on the discrepancy are derived. It is shown that these bounds are asymptotically not worse than known estimates for maximal period linear recurring sequences over prime fields.
Keywords: linear recurring sequences, Galois ring, distribution of elements in a sequence, discrepancy, exponential sum. 
@article{DM_2019_31_3_a1,
     author = {A. R. Vasin},
     title = {Bounds on the discrepancy of linear recurring sequences over {Galois} rings},
     journal = {Diskretnaya Matematika},
     pages = {17--25},
     publisher = {mathdoc},
     volume = {31},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2019_31_3_a1/}
}
TY  - JOUR
AU  - A. R. Vasin
TI  - Bounds on the discrepancy of linear recurring sequences over Galois rings
JO  - Diskretnaya Matematika
PY  - 2019
SP  - 17
EP  - 25
VL  - 31
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2019_31_3_a1/
LA  - ru
ID  - DM_2019_31_3_a1
ER  - 
%0 Journal Article
%A A. R. Vasin
%T Bounds on the discrepancy of linear recurring sequences over Galois rings
%J Diskretnaya Matematika
%D 2019
%P 17-25
%V 31
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2019_31_3_a1/
%G ru
%F DM_2019_31_3_a1
A. R. Vasin. Bounds on the discrepancy of linear recurring sequences over Galois rings. Diskretnaya Matematika, Tome 31 (2019) no. 3, pp. 17-25. http://geodesic.mathdoc.fr/item/DM_2019_31_3_a1/

[1] V.L. Kurakin, A.S. Kuzmin, A.V. Mikhalev, A.A. Nechaev, “Linear recurrent sequences over rings and modules”, J. Math. Sci., 76:6 (1995), 2793–2915 | DOI | MR | Zbl

[2] A.S. Kuzmin, V.L. Kurakin, A.A. Nechaev, “Psevdosluchainye i polilineinye posledovatelnosti”, Trudy po diskretnoi matematike, v. 1, Izd-vo TVP, M., 1997, 139–202

[3] H. Niederreiter, “On the distribution of pseudo-random numbers generated by the linear congruential method. III”, Math. Comput., 30 (1976), 571–597 | DOI | MR | Zbl

[4] H. Niederreiter, “Statistical tests for linear congruential pseudo-random numbers”, Proc. Comput. Statist. (Leiden), Compstat 1978, 1978, 398–404 | MR

[5] H. Niederreiter, “Statistical independence properties of Tausworthe pseudo-random numbers”, Proc. 3rd Caribbean Conf. on Combinatorics and Computing (Cave Hill, Barbados), 1981, 163–168 | Zbl

[6] H. Niederreiter, “Statistical tests for Tausworthe pseudo-random numbers”, Probability and Statistical Inference, D.Reidel Publ. Co., 1982, 265–274 | DOI | MR

[7] H. Niederreiter, “The performance of $k$-step pseudorandom number generators under the uniformity test”, SIAM J. Sci. Statist. Computing, 5 (1984), 798–810 | DOI | MR | Zbl

[8] H. Niederreiter, “The serial test for digital $k$-step pseudorandom numbers”, Math. J. Okayama Univ., 30 (1988), 93–119 | MR | Zbl

[9] H. Niederreiter, “A statistical analysis of generalized feedback shift register pseudorandom number generators”, SIAM J. Sci. Statist. Computing, 8 (1987), 1035–1051 | DOI | MR | Zbl

[10] H. Niederreiter, “Point sets and sequences with small discrepancy”, Monatsh. Math., 104 (1987), 273–337 | DOI | MR | Zbl

[11] H. Niederreiter, “Pseudorandom numbers generated from shift register sequences”, Lect. Notes Math., 1452, Springer, Berlin, Heidelberg, 1990, 165–177 | DOI | MR

[12] L. Keipers, G. Niderreiter, Ravnomernoe raspredelenie posledovatelnostei, Nauka. Gl. red. fiz.-mat. lit., M., 1985

[13] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992 | MR | Zbl

[14] H. Niederreiter, A. Winterhof, Applied number theory, Springer International Publishing, 2015 | MR | Zbl

[15] P. Sole, D. Zinoviev, “Inversive congruential pseudorandom numbers over Galois rings”, Eur. J. Comb., 30:2 (2009), 458–467 | DOI | MR | Zbl

[16] E.V. Vernigora, “Inversnyi kongruentnyi generator nad koltsom Galua kharakteristiki $p^l$”, Ukr. matem. vest., 8:4 (2011), 607–618

[17] A. A. Nechaev, “Kerdock code in a cyclic form”, Discrete Math. Appl., 1:4 (1991), 365–384 | DOI | MR | Zbl | Zbl

[18] B.R. McDonald, Finite rings with identity, Pure Appl. Math., 28, Dekker, New York, 1974 | MR | Zbl

[19] A. A. Nechaev, “Cycle types of linear substitutions over finite commutative rings”, Russian Acad. Sci. Sb. Math., 78:2 (1994), 283–311 | MR | Zbl

[20] K.L. Chung, “An estimate concerning the Kolmogoroff limit distribution”, Trans. Amer. Math. Soc., 67 (1949), 36–50 | MR | Zbl

[21] T. Cochrane, “On a trigonometric inequality of Vinogradov”, J. Number Theory, 27:1 (1987), 9–16 | DOI | MR | Zbl

[22] V. Sison, Bases of the Galois ring $GR(p^r,m)$ over the integer ring $\mathbb{Z}_{p^r}$, 2016, arXiv: 1410.0289 | Zbl

[23] A.R. Vasin, “Otsenki chastot poyavlenii elementov na otrezkakh lineinykh rekurrentnykh posledovatelnostei nad koltsami Galua”, Diskretnaya matematika, 31:2 (2019), 57–68 | DOI

[24] Kamlovskii O.V., “Frequency characteristics of coordinate sequences of linear recurrences over Galois rings”, Izv. Math., 77:6 (2013), 1130–1154 | DOI | DOI | MR | Zbl