Некоторые свойства почти всех n-квазигрупп
https://doi.org/10.26907/2949-3919.2024.4.35-50
Аннотация
Изучается “типичность” свойств простоты, неаффинности и полиномиальной полноты конечных n-квазигрупп. Показано, что при фиксированном n почти все n-квазигруппы сильно неаффинны, т.е. не изотопны аффинным. Найдено точное значение числа простых, аффинных и одновременно простых и аффинных n-квазигрупп порядка 4. Как следствие, показано, что почти все n-квазигруппы порядка 4 полиномиально полны и сильно неаффинны.
Об авторах
А. В. Галатенко
МГУ имени М.В.Ломоносова, механико-математический факультет
Россия
Россия
Алексей Владимирович Галатенко
Ленинские горы, д. 1, г. Москва, 119991
В. В. Галатенко
МГУ имени М.В.Ломоносова, механико-математический факультет
Россия
Россия
Владимир Владимирович Галатенко
Ленинские горы, д. 1, г. Москва, 119991
А. Е. Панкратьев
МГУ имени М.В.Ломоносова, механико-математический факультет
Россия
Россия
Антон Евгеньевич Панкратьев
Ленинские горы, д. 1, г. Москва, 119991
Список литературы
1. V.A. Shcherbacov, Quasigroups in cryptology, Comput. Sci. J. Mold. 17 (2), 193–228 (2009).
2. 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.1721615
3. A. 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.09
4. V. Dimitrova, S. Markovski, Classification of quasigroups by image patterns, Proceedings of the Fifth International Conference for Informatics and Information Technology, 152–160 (2007).
5. 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).
6. 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.028
7. V.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
8. В.Л. Мурский, Конечная базируемость тождеств и другие свойства “почти всех” алгебр, Проблемы кибернетики 30, 43–56 (1975).
9. 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-P
10. A. Salomaa, Some completeness criteria for sets of functions over a finite domain II, Annales Universitatis Turkuensis. Series AI 63, 19 pp. (1963).
11. А.В. Галатенко, В.В. Галатенко, А.Е. Панкратьев, О сильной полиномиальной полноте почти всех квазигрупп, Матем. заметки 111 (1), 8–14 (2022). DOI: https://doi.org/10.4213/mzm13229
12. B. 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/S0218196706003116
13. D.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/070697331
14. C.F. Laywine, G.L. Mullen, Discrete mathematics using Latin squares, Wiley, New York, 1998.
15. В.Н. Потапов, Д.С. Кротов, Асимптотика числа n-квазигрупп порядка 4, Сиб. матем. журн. 47 (4), 873–887 (2006). URL: https://www.mathnet.ru/rus/smj902
16. 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).
17. В.Н. Потапов, Д.С. Кротов, О числе n-арных квазигрупп конечного порядка, Дискрет. матем. 24 (1), 60–69 (2012). DOI: https://doi.org/10.4213/dm1172
18. N. 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-8
19. V.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
20. А.В. Галатенко, А.Е. Панкратьев, В.М. Староверов, Алгоритмы проверки некоторых свойств n-квазигрупп, Программирование (1), 40–53 (2022). DOI: https://doi.org/10.31857/s0132347422010046
21. D. 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-9
22. G.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
Рецензия
Для цитирования:
Галатенко А.В., Галатенко В.В., Панкратьев А.Е. Некоторые свойства почти всех n-квазигрупп. Математика и теоретические компьютерные науки. 2024;2(4):35-50. https://doi.org/10.26907/2949-3919.2024.4.35-50
For citation:
Galatenko A.V., Galatenko V.V., Pankratiev A.E. Some properties of almost all n-quasigroups. Mathematics and Theoretical Computer Science. 2024;2(4):35-50. (In Russ.) https://doi.org/10.26907/2949-3919.2024.4.35-50
Просмотров:
65
Послать статью по эл. почте 