Linear complexity of polylinear sequences

V. L. Kurakin

Diskretnaya Matematika, Tome 13 (2001) no. 1, pp. 3-55.

Résumé

A number of definitions of a linear complexity (rank) of a polylinear recurring sequence over a ring or over a module is introduced. The equivalence of these definitions and properties of linear complexity for sequences over various classes of rings (fields, division rings, commutative and commutative Artinian rings, left Ore domains, Bezout domains) are studied. It is proved that for sequences over a commutative Bezout domain, in the same way as for sequences over a field, all introduced definitions are equivalent.

Bibliographie

[1] Atya M., Makdonald I., Vvedenie v kommutativnuyu algebru, Mir, Moskva, 1972 | MR

[2] Van der Varden B. L., Algebra, Nauka, Moskva, 1979 | MR

[3] Elizarov V. P., Konechnye koltsa, M., 1993

[4] Kash F., Moduli i koltsa, Mir, Moskva, 1981 | MR

[5] Kon P., Svobodnye koltsa i ikh svyazi, Mir, Moskva, 1975 | MR

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

[7] Kurakin V. L., “Binomialnoe predstavlenie lineinykh rekurrentnykh posledovatelnostei”, Fundamentalnaya i prikladnaya matematika, 1:2 (1995), 553–556 | MR | Zbl

[8] Kurakin V. L., “Algoritm Berlekempa–Messi nad konechnymi koltsami, modulyami i bimodulyami”, Diskretnaya matematika, 10:4 (1998), 3–34 | MR | Zbl

[9] Kurakin V. L., “Polinomialnye preobrazovaniya lineinykh rekurrentnykh posledovatelnostei nad konechnymi kommutativnymi koltsami”, Diskretnaya matematika, 12:3 (2000), 3–36 | MR | Zbl

[10] Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad kvazifrobeniusovymi modulyami”, Uspekhi matem. nauk, 48:3 (1993), 197–198 | MR | Zbl

[11] Nechaev A. A., “Konechnye kvazifrobeniusovy moduli, prilozheniya k kodam i lineinym rekurrentam”, Fundamentalnaya i prikladnaya matematika, 1:1 (1995), 229–254 | MR | Zbl

[12] Kherstein I., Nekommutativnye koltsa, Mir, Moskva, 1972 | MR

[13] Shafarevich I. R., Osnovnye ponyatiya algebry. Sovremennye problemy matematiki. Fundamentalnye napravleniya. Itogi nauki i tekhniki, 11, VINITI, Moskva, 1986 | MR

[14] Herlestam T., “On the complexity of functions of linear shift register sequences”, Int. Symp. Inform. Theory, Les Arc, France, 1982

[15] Key E. L., “An analysis of the structure and complexity of nonlinear binary sequence generators”, IEEE Trans. Inform. Theory, 22, no. 6, 1976, 732–736 | Zbl

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

[17] V. L. Kurakin, A. V. Mikhalev, A. A. Nechaev, V. N. Tsypyschev, Linear and polylinear recurring sequences over abelian groups and modules, 102:6 (2000), 4598–4626 | MR | Zbl

[18] McCoy N. H., Rings and ideals, Math. Assoc. Amer., Menasha, 1962 | Zbl

[19] Peterson B., Taft E. Y., “The Hopf algebra of lineary recursive sequences”, Aequat. Math., 20 (1980), 1–17 | DOI | MR | Zbl

[20] Rueppel R. A., Staffelbach O. J., “Products of linear recurring sequences with maximum complexity”, IEEE Trans. Inform. Theory, 33, no. 1, 1987, 126–131

[21] Sakata S.,, “Synthesis of two-dimensional linear feedback shift-registers and Groebner bases”, Lect. Notes Comput. Sci., 356, 1989, 394–407 | MR | Zbl

[22] Sakata S., “Extension of the Berlekamp–Massey algorithm to $N$ dimensions”, Inform. and Comput., 84:2 (1990), 207–239 | DOI | MR | Zbl

[23] Sakata S., “Two-dimensional shift register synthesis and Groebner bases for polynomial ideals over an integer residue ring”, Discr. Appl. Math., 33:1–3 (1991), 191–203 | DOI | MR | Zbl

[24] Zierler N., Mills W. H., “Products of linear recurring sequences”, J. Algebra, 27:1 (1973), 147–157 | DOI | MR | Zbl