Some properties of almost all n-quasigroups
https://doi.org/10.26907/2949-3919.2024.4.35-50
Abstract
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.
About the Authors
A. V. Galatenko
Moscow State University, Faculty of Mechanics and Mathematics
Russian Federation
Russian Federation
Alexei Vladimirovich Galatenko
1 Leninskie Gory, Moscow 119991
V. V. Galatenko
Moscow State University, Faculty of Mechanics and Mathematics
Russian Federation
Russian Federation
Vladimir Vladimirovich Galatenko
1 Leninskie Gory, Moscow 119991
A. E. Pankratiev
Moscow State University, Faculty of Mechanics and Mathematics
Russian Federation
Russian Federation
Anton Evgevievich Pankratiev
1 Leninskie Gory, Moscow 119991
References
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. V.L. Murskiy, Finite basis of identities and other properties of “almost all” algebras, Problemy kibernetiki 30, 43–56 (1975) [in Russian].
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. A.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/S0001434622010023
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. V.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-9
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. V.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.035
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. A.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/s0361768822010042
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
Review
For citations:
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
Views:
63
Email this article 