matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2024.4.35-50matatecs-62Research ArticleСТАТЬИНекоторые свойства почти всех n-квазигруппSome properties of almost all n-quasigroupsГалатенкоА. В.GalatenkoA. V.

Алексей Владимирович Галатенко

Ленинские горы, д. 1, г. Москва, 119991

Alexei Vladimirovich Galatenko

1 Leninskie Gory, Moscow 119991

agalat@msu.ruГалатенкоВ. В.GalatenkoV. V.

Владимир Владимирович Галатенко

Ленинские горы, д. 1, г. Москва, 119991

Vladimir Vladimirovich Galatenko

1 Leninskie Gory, Moscow 119991

vgalat@msu.ruПанкратьевА. Е.PankratievA. E.

Антон Евгеньевич Панкратьев

Ленинские горы, д. 1, г. Москва, 119991

Anton Evgevievich Pankratiev

1 Leninskie Gory, Moscow 119991

apankrat@intsys.msu.ruМГУ имени М.В.Ломоносова, механико-математический факультетРоссияMoscow State University, Faculty of Mechanics and MathematicsRussian Federation202424012025243550Copyright © Галатенко А.В., Галатенко В.В., Панкратьев А.Е., 20252025Галатенко А.В., Галатенко В.В., Панкратьев А.Е.Galatenko A.V., Galatenko V.V., Pankratiev A.E.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/62

Изучается “типичность” свойств простоты, неаффинности и полиномиальной полноты конечных n-квазигрупп. Показано, что при фиксированном n почти все n-квазигруппы сильно неаффинны, т.е. не изотопны аффинным. Найдено точное значение числа простых, аффинных и одновременно простых и аффинных n-квазигрупп порядка 4. Как следствие, показано, что почти все n-квазигруппы порядка 4 полиномиально полны и сильно неаффинны.

We study the generic nature of simplicity, non-affinity and polynomial completeness of finite n-quasigroups. It is shown that for fixed n almost all n-quasigroups are strongly non-affine, i.e., not isotopic to affine n-quasigroups. Exact number of simple, affine and simultaneously simple and affine n-quasigroups of the order 4 is established. As a corollary, it is proven that almost all n-quasigroups of the order 4 are polynomially complete and strongly non-affine.

квазигруппаn-квазигруппапростотааффинностьполиномиальная полнотаquasigroupn-quasigroupsimplicityaffinitypolynomial completenessReferencesV.A. Shcherbacov, Quasigroups in cryptology, Comput. Sci. J. Mold. 17 (2), 193–228 (2009).V.A. Shcherbacov, Quasigroups in cryptology, Comput. Sci. J. Mold. 17 (2), 193–228 (2009).D. Chauhan, I. Gupta, R. Verma, Quasigroups and their applications in cryptography, Cryptologia 45 (3), 227–265 (2021). DOI: https://doi.org/10.1080/01611194.2020.1721615D. Chauhan, I. Gupta, R. Verma, Quasigroups and their applications in cryptography, Cryptologia 45 (3), 227–265 (2021). DOI: https://doi.org/10.1080/01611194.2020.1721615A. Mileva, S. Markovski, Shapeless quasigroups qerived by Feistel orthomorphisms, Glas. Mat. Ser. III 47 (2), 333–349 (2012). DOI: http://dx.doi.org/10.3336/gm.47.2.09A. Mileva, S. Markovski, Shapeless quasigroups qerived by Feistel orthomorphisms, Glas. Mat. Ser. III 47 (2), 333–349 (2012). DOI: http://dx.doi.org/10.3336/gm.47.2.09V. Dimitrova, S. Markovski, Classification of quasigroups by image patterns, Proceedings of the Fifth International Conference for Informatics and Information Technology, 152–160 (2007).V. Dimitrova, S. Markovski, Classification of quasigroups by image patterns, Proceedings of the Fifth International Conference for Informatics and Information Technology, 152–160 (2007).V.A. Artamonov, S. Chakrabarti, S. Gangopadhyay, S.K. Pal, On Latin squares of polynomially complete quasigroups and quasigroups generated by shifts, Quasigroups Relat. Syst. 21 (2), 117–130 (2013).V.A. Artamonov, S. Chakrabarti, S. Gangopadhyay, S.K. Pal, On Latin squares of polynomially complete quasigroups and quasigroups generated by shifts, Quasigroups Relat. Syst. 21 (2), 117–130 (2013).G. Horváth, C.L. Nehaniv, Cs. Szabó, An assertion concerning functionally complete algebras and NP-completeness, Theoret. Comput. Sci. 407 (1–3), 591–595 (2008). DOI: https://doi.org/10.1016/j.tcs.2008.08.028G. Horváth, C.L. Nehaniv, Cs. Szabó, An assertion concerning functionally complete algebras and NP-completeness, Theoret. Comput. Sci. 407 (1–3), 591–595 (2008). DOI: https://doi.org/10.1016/j.tcs.2008.08.028V.A. Artamonov, S. Chakrabarti, S.K. Pal, Characterization of polynomially complete quasigroups based on Latin squares for cryptographic transformations, Discrete Appl. Math. 200, 5–17 (2016). DOI: https://doi.org/10.1016/j.dam.2015.06.033V.A. Artamonov, S. Chakrabarti, S.K. Pal, Characterization of polynomially complete quasigroups based on Latin squares for cryptographic transformations, Discrete Appl. Math. 200, 5–17 (2016). DOI: https://doi.org/10.1016/j.dam.2015.06.033В.Л. Мурский, Конечная базируемость тождеств и другие свойства “почти всех” алгебр, Проблемы кибернетики 30, 43–56 (1975).V.L. Murskiy, Finite basis of identities and other properties of “almost all” algebras, Problemy kibernetiki 30, 43–56 (1975) [in Russian].P.J. Cameron, Almost all quasigroups have rank 2, Discrete Math. 106–107, 111–115 (1992). DOI: https://doi.org/10.1016/0012-365X(92)90537-PP.J. Cameron, Almost all quasigroups have rank 2, Discrete Math. 106–107, 111–115 (1992). DOI: https://doi.org/10.1016/0012-365X(92)90537-PA. Salomaa, Some completeness criteria for sets of functions over a finite domain II, Annales Universitatis Turkuensis. Series AI 63, 19 pp. (1963).A. Salomaa, Some completeness criteria for sets of functions over a finite domain II, Annales Universitatis Turkuensis. Series AI 63, 19 pp. (1963).А.В. Галатенко, В.В. Галатенко, А.Е. Панкратьев, О сильной полиномиальной полноте почти всех квазигрупп, Матем. заметки 111 (1), 8–14 (2022). DOI: https://doi.org/10.4213/mzm13229A.V. Galatenko, V.V. Galatenko, A.E. Pankrat’ev, Strong polynomial completeness of almost all quasigroups, Math. Notes 111 (1), 7–12 (2022). DOI: https://doi.org/10.1134/S0001434622010023B. Larose, L.Zádori, Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras, Int. J. Algebra Comput. 16 (3), 563–581 (2006). DOI: https://doi.org/10.1142/S0218196706003116B. Larose, L. Zádori, Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras, Int. J. Algebra Comput. 16 (3), 563–581 (2006). DOI: https://doi.org/10.1142/S0218196706003116D.S. Krotov, V.N. Potapov, n-ary quasigroups of order 4, SIAM J. Discrete Math. 23 (2), 561–570 (2009). DOI: https://doi.org/10.1137/070697331D.S. Krotov, V.N. Potapov, n-ary quasigroups of order 4, SIAM J. Discrete Math. 23 (2), 561–570 (2009). DOI: https://doi.org/10.1137/070697331C.F. Laywine, G.L. Mullen, Discrete mathematics using Latin squares, Wiley, New York, 1998.C.F. Laywine, G.L. Mullen, Discrete mathematics using Latin squares, Wiley, New York, 1998.В.Н. Потапов, Д.С. Кротов, Асимптотика числа n-квазигрупп порядка 4, Сиб. матем. журн. 47 (4), 873–887 (2006). URL: https://www.mathnet.ru/rus/smj902V.N. Potapov, D.S. Krotov, Asymptotics for the number of n-quasigroups of order 4, Siberian Math. J. 47 (4), 720–731 (2006). DOI: https://doi.org/10.1007/s11202-006-0083-9D.S. Krotov, V.N. Potapov, P.V. Sokolova, On reconstructing reducible n-ary quasigroups and switching subquasigroups, Quasigr. Relat. Syst. 16 (1), 55–67 (2008).D.S. Krotov, V.N. Potapov, P.V. Sokolova, On reconstructing reducible n-ary quasigroups and switching subquasigroups, Quasigr. Relat. Syst. 16 (1), 55–67 (2008).В.Н. Потапов, Д.С. Кротов, О числе n-арных квазигрупп конечного порядка, Дискрет. матем. 24 (1), 60–69 (2012). DOI: https://doi.org/10.4213/dm1172V.N. Potapov, D.S. Krotov, On the number of n-ary quasigroups of finite order, Discrete Math. Appl. 21 (5–6), 575–585 (2011). DOI: https://doi.org/10.1515/dma.2011.035N. Linial, Z. Luria, An upper bound on the number of high-dimensional permutations, Combinatorica 34 (4), 471–486 (2014). DOI: https://doi.org/10.1007/s00493-011-2842-8N. Linial, Z. Luria, An upper bound on the number of high-dimensional permutations, Combinatorica 34 (4), 471–486 (2014). DOI: https://doi.org/10.1007/s00493-011-2842-8V.N. Potapov, On the number of SQSs, latin hypercubes and MDS codes, J. Combin. Des. 26 (5), 237–248 (2018). DOI: https://doi.org/10.1002/jcd.21603V.N. Potapov, On the number of SQSs, latin hypercubes and MDS codes, J. Combin. Des. 26 (5), 237–248 (2018). DOI: https://doi.org/10.1002/jcd.21603А.В. Галатенко, А.Е. Панкратьев, В.М. Староверов, Алгоритмы проверки некоторых свойств n-квазигрупп, Программирование (1), 40–53 (2022). DOI: https://doi.org/10.31857/s0132347422010046A.V. Galatenko, A.E. Pankratiev, V.M. Staroverov, Algorithms for checking some properties of n-quasigroups, Program. Comput. Softw. 48 (1), 36–48 (2022). DOI: http://doi.org/10.1134/s0361768822010042D. Lau, Function algebras on finite sets: a basic course on many-valued logic and clone theory, Springer-Verlag, Berlin, 2006. DOI: https://doi.org/10.1007/3-540-36023-9D. Lau, Function algebras on finite sets: a basic course on many-valued logic and clone theory, Springer-Verlag, Berlin, 2006. DOI: https://doi.org/10.1007/3-540-36023-9G.H. Hardy, S. Ramanujan, Asymptotic formulae in combinatory analysis, Proc. London Math. Soc. 17, 75–115 (1918). DOI: https://doi.org/10.1112/plms/s2-17.1.75G.H. Hardy, S. Ramanujan, Asymptotic formulae in combinatory analysis, Proc. London Math. Soc. 17, 75–115 (1918). DOI: https://doi.org/10.1112/plms/s2-17.1.75

The authors declare that there are no conflicts of interest present.