Closed classes of polynomials modulo $p^2$

D. G. Meshchaninov

Diskretnaya Matematika, Tome 29 (2017) no. 3, pp. 54-69.

Résumé

We consider functions of $p^2$-valued logic ($p$ is prime) that may be implemented by polynomials over the ring ${\mathbb Z}_{p^2}$, and describe all closed classes that contain linear functions. It turns out that the set of these classes is countable. We also construct the lattice of such classes with respect to inclusion.

Détail

Keywords: $k$-valued logic, closed class, clone, polynomials over a ring of residues, lattice of closed classes.

Bibliographie

[1] Yanov Yu. I., Muchnik A. A., “O suschestvovanii $k$-znachnykh zamknutykh klassov, ne imeyuschikh konechnogo bazisa”, Dokl. AN SSSR, 127:1 (1959), 44–46 | Zbl

[2] Post E. L., “The two-valued iterative systems of mathematical logic”, Ann. Math. Stud., 5, Princeton Univ. Press, Princeton–London, 1941 | MR | Zbl

[3] Kempner A. J., “Polynomials and their residue systems”, Trans. Amer. Math. Soc., 22:4 (1921), 240–266 | DOI | MR | Zbl

[4] Redei L., Szele T., “Algebraisch-Zahlentheoretische Betrachtungen über Ringe. II”, Acta Math., 82 (1950), 209–241 | DOI | MR | Zbl

[5] Keller G., Olson F. R., “Counting polynomial functions $\pmod {p^n}$”, Duke Math. J., 35:4 (1968), 835–838 | DOI | MR | Zbl

[6] Aizenberg H. H., Semion I. V., Tsitkin A. I., “Moschnost klassa funktsii $k$-znachnoi logiki ot $n$ peremennykh, predstavimykh polinomami po modulyu $k$”, Mnogoustoichivye elementy i ikh primenenie, Sov. radio, M., 1971, 79–83

[7] Singmaster D., “On polynomial functions $\pmod {m}$”, J. Number Th., 6:5 (1974), 345–352 | DOI | MR | Zbl

[8] Carlitz L., “Functions and polynomials $\pmod {p^n}$”, Acta Arithm., 9 (1964), 66–78 | MR

[9] Aizenberg H. H., Semion I. V., “Nekotorye kriterii predstavimosti funktsii $k$-znachnoi logiki polinomami po modulyu $k$”, Mnogoustoichivye elementy i ikh primenenie, Sov. radio, M., 1971, 84–88

[10] Rosenberg I. G., “Polynomial functions over finite rings”, Glasnik Matematiki, 10:1 (1975), 25–33 | MR | Zbl

[11] Meschaninov D. G., “Nekotorye usloviya predstavimosti funktsii iz $P_k$ polinomami po modulyu $k$”, Dokl. AN SSSR, 299:1 (1988), 50–53

[12] Meshchaninov D. G., “On the second $p$-differences of functions of $p^\alpha$-valued logic”, Discrete Math. Appl., 3:6 (1993), 611–621 | DOI | MR | Zbl

[13] Remizov A. B., “Superstructure of the closed class of polynomials modulo $k$”, Discrete Math. Appl., 1:1 (1991), 9–22 | DOI | MR | Zbl

[14] Meshchaninov D. G., “A method for constructing polynomials of $k$-valued logic functions”, Discrete Math. Appl., 5:4 (1995), 333–346 | DOI | MR | Zbl

[15] Selezneva S. N., “A fast algorithm for the construction of polynomials modulo $k$ for $k$-valued functions for composite $k$”, Discrete Math. Appl., 21:5-6 (2011), 651–674 | DOI | DOI | MR | Zbl

[16] Cherepov A. H., Nadstruktura klassa sokhraneniya otnoshenii sravneniya v $k$-znachnoi logike po vsem modulyam-delitelyam $k$, Avtoref. diss. kand. fiz.-mat. n., M., 1986

[17] Nechaev A. A., “Kriterii polnoty sistem funktsii $p^n$-znachnoi logiki, soderzhaschikh operatsii slozheniya i umnozheniya po modulyu $p^n$”, Metody diskretnogo analiza v reshenii kombinatornykh zadach, 1980, no. 34, 74–89, 4. Novosibirsk

[18] Cherepov A. H., “Opisanie struktury zamknutykh klassov v $P_k$, soderzhaschikh klass polinomov”, Problemy kibernetiki, 1983, no. 40, 5–18 | MR | Zbl

[19] Meshchaninov D. G., “Superstructures of the class of polynomials in $P_k$”, Math. Notes, 44:5 (1988), 950–954 | DOI | MR | Zbl

[20] Gavrilov G. P., “On the superstructure of the class of polynomials in multivalued logics”, Discrete Math. Appl., 6:4 (1996), 405–412 | DOI | DOI | MR | Zbl

[21] Gavrilov G. P., “On the closed classes of multivalued logic containing the polynomial class”, Discrete Math. Appl., 7:3 (1997), 231–242 | DOI | DOI | MR | Zbl

[22] Zaets M. V., “Klassifikatsiya funktsii nad primarnym koltsom vychetov v svyazi s metodom pokoordinatnoi linearizatsii”, Prikl. diskret. matematika. Prilozhenie, 2014, no. 7, 16–19

[23] Zaets M. V., “O klasse variatsionno-koordinatno-polinomialnykh funktsii nad primarnym koltsom vychetov”, Prikl. diskret. matematika, 2014, no. 3(25), 12–27

[24] Krokhin A. A., Safin K. L., Sukhanov E. V., “On the structure of the lattice of closed classes of polynomials”, Discrete Math. Appl., 7:2 (1997), 131–146 | DOI | DOI | MR | Zbl

[25] Salomaa A. A., “On infinetely generated sets of operations in finite algebra”, Ann. Univ. Turku, Ser. A, I, 1964, no. 74, 1–12 | MR

[26] Bagyinszki J., Demetrovics J., “The lattice of linear classes in prime-valued logics”, Discrete mathematics, 1982, no. 7, 105–123, Banach Center Publ., Warsaw | MR

[27] Szendrei Á., “On closed sets of linear operations over a finite sets of square-free cardinality”, Elektr. Inform. Kybern., 1978, no. 14, 547–559 | MR | Zbl

[28] Szendrei Á., “On closed classes of quasilinear functions”, Czechoslov. Math. J., 1980, no. 80, 498–509 | MR | Zbl

[29] Lau D., “Uber abgeschlossenen Mengen linearen Funktionen in mehrvertigen Logiken”, J. Inf. Proccess. Cybern. EIK, 24:7/8 (1988), 367–381 | MR | Zbl

[30] Lau D., B. Schröder, “On the number of closed subsets of linear functions in 6-valued logic”, Beiträge zur Alg. und Geom., 1990, no. 31, 19–32 | MR

[31] Lau D., “Kongruenzen auf abgeschlossenen Mengen linearen Funktionen in mehrvertigen Logiken”, Rostock Math. Kolloq., 1990, no. 43, 3–16 | MR

[32] Bulatov A. A., “Polynomial reducts of modules, I. Rough classification”, Mult.-Valued Log., 33:2 (1998), 135–154

[33] Lau D., Function algebras on finite sets, Springer-Verlag, 2006, 668 pp. | MR | Zbl

[34] Semigrodskikh A. P., Sukhanov E. B., “On closed classes of polynomials over finite fields”, Discrete Math. Appl., 7:6 (1997), 593–606 | DOI | DOI | MR | Zbl

[35] Darsaliya V. Sh., “Usloviya polnoty dlya polinomov s naturalnymi, tselymi i ratsionalnymi koeffitsientami”, Fund. i prikl. matem., 2:2 (1996), 365–374 | MR | Zbl

[36] Mamontov A. I., “Issledovanie struktury zamknutykh klassov v funktsionalnoi sisteme lineinykh polinomov s tselymi neotritsatelnymi koeffitsientami”, Vestnik MEI, 6 (2006), 83–90

[37] Mamontov A. I., Meshchaninov D. G., “The completeness problem in the function algebra of linear integer-coefficient polynomials”, Discrete Math. Appl., 20:5-6 (2010), 621–641 | DOI | DOI | MR | Zbl

[38] Mamontov A. I., “Problema otnositelnoi polnoty v funktsionalnoi sisteme lineinykh polinomov s ratsionalnymi koeffitsientami”, Vestnik MEI, 2011, no. 6, 133–142

[39] Meschaninov D. G., Nikitin I. V., “Funktsionalno zamknutye klassy polinomov, sokhranyayuschikh nekotorye ekvivalentnosti na chislovykh mnozhestvakh”, Vestnik MEI, 2011, no. 6, 14–23

[40] Meschaninov D. G., Nikitin I. V., “Klassy sokhraneniya porogovykh razbienii v funktsionalnykh sistemakh polinomov”, Vestnik MEI, 2012, no. 6, 132–141

[41] Aleksiadis N. F., “Funktsionalnaya sistema polinomov s naturalnymi koeffitsientami”, Vestnik MEI, 2013, no. 6, 125–140

[42] Meschaninov D. G., Nikitin I. V., “Klassy polinomov, sokhranyayuschikh razbieniya oblasti opredeleniya na promezhutki ravnoi dliny”, Vestnik MEI, 2013, no. 6, 147–153

[43] Mamontov A. I., Meshchaninov D. G., “The algorithm for completeness recognizing in function algebra $L(\mathbb Z)$”, Discrete Math. Appl., 24:1 (2014), 21–28 | DOI | DOI | MR | Zbl

[44] Meschaninov D. G., Nikitin I. V., “Klassy polinomov, sokhranyayuschikh obobschennye tochechnye razbieniya beskonechnoi oblasti opredeleniya”, Mezhdunar. nauchno-issled. zhurnal, 9:3(40) (2015), 75–79

[45] Meschaninov D. G., “O pervykh $d$-raznostyakh funktsii $k$-znachnoi logiki”, Matem. voprosy kibernetiki, 1998, no. 7, 265–280

[46] Meschaninov D. G., “O zamknutykh klassakh $k$-znachnykh funktsii, sokhranyayuschikh pervye $d$-raznosti”, Matem. voprosy kibernetiki, 1999, no. 8, 219–230

[47] Meschaninov D. G., “O zamknutykh klassakh polinomov nad koltsom $Z_k$”, Trudy IX Mezhdunar. konf. "Diskretnye modeli v teorii upravlyayuschikh sistem" (20–22 maya 2015 g.), MAKS-Press, M., 2015, 161–163