Worst-case approximability of functions on finite groups by endomorphisms and affine maps. (English) Zbl 1508.20029

Summary: We study the maximum Hamming distance (or rather, the complementary notion of “minimum approximability”) of a general function on a finite group \(G\) to either of the sets \(\operatorname{End} (G)\) and \(\operatorname{Aff} (G)\), of group endomorphisms of \(G\) and affine maps on \(G\), respectively, the latter being a certain generalization of endomorphisms. We give general bounds on these two quantities and discuss an infinite class of extremal examples (where each of the two Hamming distances can be made as large as generally possible). Finally, we compute the precise values of the two quantities for all finite groups \(G\) with \(|G|\leq 15\).


20D60 Arithmetic and combinatorial problems involving abstract finite groups
20F69 Asymptotic properties of groups


GAP; SmallGrp
Full Text: DOI arXiv


[1] Bors, A., Classification of finite group automorphisms with a large cycle, Commun. Algebra44(11) (2016) 4823-4843. · Zbl 1355.20018
[2] Bors, A., Finite groups with an automorphism inverting, squaring or cubing a non-negligible fraction of elements, J. Algebra Appl.18(3) (2019) 30 pp. · Zbl 1481.20081
[3] Caranti, A., A simple construction for a class of \(p\)-groups with all of their automorphisms central, Rend. Semin. Mat. Univ. Padova135 (2016) 251-258. · Zbl 1348.20026
[4] Carlet, C. and Tarannikov, Y., Covering sequences of Boolean functions and their cryptographic significance, Des. Codes Cryptogr.25(3) (2002) 263-279. · Zbl 1035.94009
[5] B. Eick, H. U. Besche and E. O’Brien, SmallGrp - The GAP Small Groups Library, version 1.3 (9 April 2018), https://www.gap-system.org/Manuals/pkg/SmallGrp-1.3/doc/chap0.html.
[6] Fan, Y. and Xu, B., Fourier transforms and bent functions on finite groups, Des. Codes Cryptogr.86(9) (2018) 2091-2113. · Zbl 1393.43003
[7] GAP Group, GAP - Groups, Algorithms, and Programming, version 4.10.2 (2019), http://www.gap-system.org.
[8] Jonah, D. and Schreiber, B. M., Transitive affine transformations on groups, Pac. J. Math.58(2) (1975) 483-509. · Zbl 0283.20029
[9] Kitture, R. D. and Yadav, M. K., Finite groups with abelian automorphism groups: A survey, in Group Theory and Computation, (Springer-Verlag, Singapore, 2018), pp. 119-140.
[10] Larsen, M. and Shalev, A., Fibers of word maps and some applications, J. Algebra354 (2012) 36-48. · Zbl 1258.20011
[11] Poinsot, L., Bent functions on a finite nonabelian group, J. Discrete Math. Sci. Cryptogr.9(2) (2006) 349-364. · Zbl 1105.43002
[12] Poinsot, L., Non Abelian bent functions, Cryptogr. Commun.4 (2012) 1-23. · Zbl 1282.11165
[13] Poinsot, L. and Pott, A., Non-Boolean almost perfect nonlinear functions on non-Abelian groups, Int. J. Found. Comput. Sci.22(6) (2011) 1351-1367. · Zbl 1236.94064
[14] Robinson, D. J. S., A Course in the Theory of Groups, 2nd edn., , Vol. 80 (Springer-Verlag, New York, 1996).
[15] T. Tao, 254A, Notes 0a: Stirling’s formula, online notes, https://terrytao.wordpress.com/2010/01/02/254a-notes-0a-stirlings-formula/.
[16] Winter, D. L., The automorphism group of an extraspecial \(p\)-group, Rocky Mt. J. Math.2(2) (1972) 159-168. · Zbl 0242.20023
[17] Xu, B., Bentness and nonlinearity of functions on finite groups, Des. Codes Cryptogr.76(3) (2015) 409-430. · Zbl 1359.11092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.