Which subgroups of the symmetric group Sn arise as invariance groups of n-variable functions defined on a k-element domain? It appears that the higher the difference n-k, the more difficult it is to answer this question. For k ≤ n, the answer is easy: all subgroups of Sn are invariance groups. We give a complete answer in the cases k = n-1 and k = n-2, and we also give a partial answer in the general case: we describe invariance groups when n is much larger than n-k. The proof utilizes Galois connections and the corresponding closure operators on Sn, which turn out to provide a generalization of orbit equivalence of permutation groups. We also present some computational results, which show that all primitive groups except for the alternating groups arise as invariance groups of functions defined on a three-element domain.
@article{bwmeta1.element.doi-10_1515_math-2015-0010,
author = {Eszter K. Horv\'ath and G\'eza Makay and Reinhard P\"oschel and Tam\'as Waldhauser},
title = {Invariance groups of finite functions and orbit equivalence of permutation groups},
journal = {Open Mathematics},
volume = {13},
year = {2015},
zbl = {1319.06003},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_math-2015-0010}
}
Eszter K. Horváth; Géza Makay; Reinhard Pöschel; Tamás Waldhauser. Invariance groups of finite functions and orbit equivalence of permutation groups. Open Mathematics, Tome 13 (2015) . http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_math-2015-0010/
[1] Bochert A., Ueber die Zahl der verschiedenen Werthe, die eine Function gegebener Buchstaben durch Vertauschung derselben erlangen kann, Math. Ann., 1889, 33, 584-590 | Zbl 21.0141.01
[2] Clote P., Kranakis E., Boolean functions, invariance groups, and parallel complexity, SIAM J. Comput., 1991, 20, 553-590 | Zbl 0734.68038
[3] Crama Y., Hammer P.L., Boolean functions. Theory, algorithms, and applications., Encyclopedia of Mathematics and its Applications 142. Cambridge University Press, 2011 | Zbl 1237.06001
[4] Dixon J. D., Mortimer B., Permutation groups, Graduate Texts in Mathematics, 163, Springer-Verlag, 1996 | Zbl 0951.20001
[5] Hall M.,The theory of groups, Chelsea Publishing Company, New York, 1976
[6] Inglis N.F.J., On orbit equivalent permutation groups, Arch. Math., 1984, 43, 297-300 | Zbl 0545.20001
[7] Kisielewicz A., Symmetry groups of Boolean functions and constructions of permutation groups, J. Algebra, 1998, 199, 379-403 | Zbl 0897.20001
[8] Klein F., Vorlesungen über die Theorie der elliptischen Modulfunctionen. Ausgearbeitet und vervollständigt von Dr. Robert Fricke, Teubner, Leipzig, 1890 | Zbl 24.0412.01
[9] Kearnes K., personal communication, 2010
[10] Pöschel R., Galois connections for operations and relations, In: K. Denecke, M. Erné, and S.L. Wismath (Eds.), Galois connections and applications, Mathematics and its Applications, 565, Kluwer Academic Publishers, Dordrecht, 2004, 231-258 | Zbl 1063.08003
[11] Pöschel R. and Kalužnin L. A., Funktionen- und Relationenalgebren, Deutscher Verlag der Wissenschaften, Berlin, 1979, Birkhäuser Verlag Basel, Math. Reihe Bd. 67, 1979
[12] Remak R., Über die Darstellung der endlichen Gruppen als Untergruppen direkter Produkte, J. Reine Angew. Math., 1930, 163, 1-44 | Zbl 56.0129.01
[13] Seress Á., Primitive groups with no regular orbits on the set of subsets, Bull. Lond. Math. Soc., 1997, 29, 697-704
[14] Seress Á., Yang K., On orbit-equivalent, two-step imprimitive permutation groups, Computational Group Theory and the Theory of Groups, Contemp. Math., 2008, 470, 271-285 | Zbl 1171.20003
[15] Siemons J., Wagner A., On finite permutation groups with the same orbits on unordered sets, Arch. Math. 1985, 45, 492-500 | Zbl 0582.20001
[16] Wielandt H., Finite permutation groups, Academic Press, New York and London, 1964 | Zbl 0138.02501
[17] Wielandt H., Permutation groups through invariant relations and invariant functions, Dept. of Mathematics, Ohio State University Columbus, Ohio, 1969