Geodesic
Frequency characteristics of linear recurrence sequences over Galois rings
Sbornik. Mathematics, Tome 200 (2009) no. 4, pp. 499-519 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The frequencies of occurrences of elements in linear recurrence sequences of vectors over Galois rings are studied. The study of these frequencies is reduced to the study of the corresponding trigonometric sums over Galois rings. Based on estimates for trigonometric sums, nontrivial estimates for the frequencies of occurrence of elements in linear recurrence sequences are obtained, which generalize some known results for sequences over a finite field. These estimates are asymptotically best possible. Bibliography: 25 titles.
Keywords: linear recurrence sequences, Galois rings, trigonometric sums, distribution of elements of pseudorandom sequences, estimates for trigonometric sums. 
@article{SM_2009_200_4_a1,
     author = {O. V. Kamlovskii},
     title = {Frequency characteristics of linear recurrence sequences over {Galois} rings},
     journal = {Sbornik. Mathematics},
     pages = {499--519},
     year = {2009},
     volume = {200},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2009_200_4_a1/}
}
TY  - JOUR
AU  - O. V. Kamlovskii
TI  - Frequency characteristics of linear recurrence sequences over Galois rings
JO  - Sbornik. Mathematics
PY  - 2009
SP  - 499
EP  - 519
VL  - 200
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/SM_2009_200_4_a1/
LA  - en
ID  - SM_2009_200_4_a1
ER  - 
%0 Journal Article
%A O. V. Kamlovskii
%T Frequency characteristics of linear recurrence sequences over Galois rings
%J Sbornik. Mathematics
%D 2009
%P 499-519
%V 200
%N 4
%U http://geodesic.mathdoc.fr/item/SM_2009_200_4_a1/
%G en
%F SM_2009_200_4_a1
O. V. Kamlovskii. Frequency characteristics of linear recurrence sequences over Galois rings. Sbornik. Mathematics, Tome 200 (2009) no. 4, pp. 499-519. http://geodesic.mathdoc.fr/item/SM_2009_200_4_a1/

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

[2] N. M. Korobov, “Raspredelenie nevychetov i pervoobraznykh kornei v rekurrentnykh ryadakh”, Dokl. AN SSSR, 88:4 (1953), 603–606 | MR | Zbl

[3] V. I. Nechaev, “Distribution of signs in a sequence of rectangular matrices over a finite field”, Proc. Steklov Inst. Math., 218:3 (1997), 332–339 | MR | Zbl

[4] H. Niederreiter, “Distribution properties of feedback shift register sequences”, Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform., 15:1 (1986), 19–34 | MR | Zbl

[5] I. E. Shparlinskij, “On distribution of values of recurrence sequences”, Problems Inform. Transmission, 25:2 (1989), 120–125 | MR | Zbl

[6] V. M. Sidel'nikov, “Estimates for the number of appearances of signs on a segment of a recurrence sequence over a finite field”, Discrete Math. Appl., 2:5 (1992), 473–481 | MR | Zbl | Zbl

[7] O. V. Kamlovskii, “Otsenki chastot poyavleniya nulei v lineinykh rekurrentnykh posledovatelnostyakh vektorov”, Chebyshevskii sbornik, 6:1 (2005), 135–145 | MR | Zbl

[8] P. V. Kumar, T. Helleseth, A. R. Calderbank, “An upper bound for Weil exponential sums over Galois rings and applications”, IEEE Trans. Inform. Theory, 41:2 (1995), 456–468 | DOI | MR | Zbl

[9] A. Weil, “On some exponential sums”, Proc. Nat. Acad. Sci. U.S.A., 34:5 (1948), 204–207 | DOI | MR | Zbl

[10] L. Carlitz, S. Uchiyama, “Bounds for exponential sums”, Duke Math. J., 24:1 (1957), 37–41 | DOI | MR | Zbl

[11] O. V. Kamlovskii, A. S. Kuzmin, “Otsenki chastot poyavleniya elementov v lineinykh rekurrentnykh posledovatelnostyakh nad koltsami Galua”, Fundament. i prikl. matem., 6:4 (2000), 1083–1094 | MR | Zbl

[12] A. G. Shanbhag, P. V. Kumar, T. Helleseth, “Upper bound for a hybrid sum over Galois rings with applications to aperiodic correlation of some $q$-ary sequences sequences”, IEEE Trans. Inform. Theory, 42:1 (1996), 250–254 | DOI | MR | Zbl

[13] P. Solé, D. Zinoviev, “The most significant bit of maximum-length sequences over $\mathbb Z_{2^l}$: autocorrelation and imbalance”, IEEE Trans. Inf. Theory, 50:8 (2006), 1844–1846 | DOI | MR

[14] S. Fan, W. Han, “Random properties of the highest level sequences of primitive sequences over $\mathbb Z_{2^l}$”, IEEE Trans. Inf. Theory, 49:6 (2003), 1553–1557 | DOI | MR | Zbl

[15] H. Hu, D. Feng, W. Wu, “Incomplete exponential sums over galois rings with applications to some binary sequences derived from $\mathbb Z_{2^l}$”, IEEE Trans. Inf. Theory, 52:5 (2006), 2260–2265 | DOI | MR

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

[17] B. R. McDonald, Finite rings with identity, Pure and Applied Mathematics, 28, Dekker, New York, 1974 | MR | Zbl

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

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

[20] N. M. Korobov, Teoretiko-chislovye metody v priblizhennom analize, MTsNMO, M., 2004 | MR | Zbl

[21] R. Lidl, H. Niederreiter, Finite fields, Encyclopedia Math. Appl., 20, Addison-Wesley, Reading, MA; Cambridge Univ. Press, Cambridge, 1983 | MR | MR | Zbl | Zbl

[22] V. N. Tsypyshev, “Matrichnyi lineinyi kongruentnyi generator nad koltsom Galua nechetnoi kharakteristiki”, Tezisy dokladov V mezhdunarodnoi konferentsii “Algebra i teoriya chisel: Sovremennye problemy i prilozheniya” (Tula, 2003), Izd-vo Tul. GPU, Tula, 2003, 233–237 | MR

[23] S. Boztas, R. Hammous, P. V. Kumar, “$4$-phase sequences with near-optimum correlation properties”, IEEE Trans. Inform. Theory, 38:3 (1992), 1101–1113 | DOI | Zbl

[24] A. S. Kuz'min, “The distribution of elements on cycles of linear recurrents over rings of residues”, Russian Math. Surveys, 47:6 (1992), 219–221 | DOI | MR | Zbl

[25] A. Kuzmin, A. Nechaev, “Complete weight enumerators of generalized Kerdock code and related linear codes over Galois ring”, Discrete Appl. Math., 111:1–2 (2001), 117–137 | DOI | MR | Zbl