Invariance groups of finite functions and orbit equivalence of permutation groups

Eszter K. Horváth; Géza Makay; Reinhard Pöschel; Tamás Waldhauser

Open Mathematics (2015)

  • Volume: 13, Issue: 1, page 83-95, electronic only
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Eszter K. Horváth, et al. "Invariance groups of finite functions and orbit equivalence of permutation groups." Open Mathematics 13.1 (2015): 83-95, electronic only. <http://eudml.org/doc/268733>.

@article{EszterK2015,
abstract = {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.},
author = {Eszter K. Horváth, Géza Makay, Reinhard Pöschel, Tamás Waldhauser},
journal = {Open Mathematics},
keywords = {Invariance groups; Symmetry groups; Galois connections; Orbit equivalence of permutation groups; Symmetric and alternating groups; Functions of several variables; invariance groups; symmetry groups; orbit equivalence of permutation groups; symmetric groups; alternating groups; functions of several variables},
language = {eng},
number = {1},
pages = {83-95, electronic only},
title = {Invariance groups of finite functions and orbit equivalence of permutation groups},
url = {http://eudml.org/doc/268733},
volume = {13},
year = {2015},
}

TY - JOUR
AU - Eszter K. Horváth
AU - Géza Makay
AU - Reinhard Pöschel
AU - Tamás Waldhauser
TI - Invariance groups of finite functions and orbit equivalence of permutation groups
JO - Open Mathematics
PY - 2015
VL - 13
IS - 1
SP - 83
EP - 95, electronic only
AB - 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.
LA - eng
KW - Invariance groups; Symmetry groups; Galois connections; Orbit equivalence of permutation groups; Symmetric and alternating groups; Functions of several variables; invariance groups; symmetry groups; orbit equivalence of permutation groups; symmetric groups; alternating groups; functions of several variables
UR - http://eudml.org/doc/268733
ER -

References

top
  1. [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 Zbl21.0141.01
  2. [2] Clote P., Kranakis E., Boolean functions, invariance groups, and parallel complexity, SIAM J. Comput., 1991, 20, 553-590 Zbl0734.68038
  3. [3] Crama Y., Hammer P.L., Boolean functions. Theory, algorithms, and applications., Encyclopedia of Mathematics and its Applications 142. Cambridge University Press, 2011 Zbl1237.06001
  4. [4] Dixon J. D., Mortimer B., Permutation groups, Graduate Texts in Mathematics, 163, Springer-Verlag, 1996 Zbl0951.20001
  5. [5] Hall M.,The theory of groups, Chelsea Publishing Company, New York, 1976 
  6. [6] Inglis N.F.J., On orbit equivalent permutation groups, Arch. Math., 1984, 43, 297-300 Zbl0545.20001
  7. [7] Kisielewicz A., Symmetry groups of Boolean functions and constructions of permutation groups, J. Algebra, 1998, 199, 379-403 Zbl0897.20001
  8. [8] Klein F., Vorlesungen über die Theorie der elliptischen Modulfunctionen. Ausgearbeitet und vervollständigt von Dr. Robert Fricke, Teubner, Leipzig, 1890 Zbl24.0412.01
  9. [9] Kearnes K., personal communication, 2010 
  10. [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 Zbl1063.08003
  11. [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. [12] Remak R., Über die Darstellung der endlichen Gruppen als Untergruppen direkter Produkte, J. Reine Angew. Math., 1930, 163, 1-44 Zbl56.0129.01
  13. [13] Seress Á., Primitive groups with no regular orbits on the set of subsets, Bull. Lond. Math. Soc., 1997, 29, 697-704 
  14. [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 Zbl1171.20003
  15. [15] Siemons J., Wagner A., On finite permutation groups with the same orbits on unordered sets, Arch. Math. 1985, 45, 492-500 Zbl0582.20001
  16. [16] Wielandt H., Finite permutation groups, Academic Press, New York and London, 1964 Zbl0138.02501
  17. [17] Wielandt H., Permutation groups through invariant relations and invariant functions, Dept. of Mathematics, Ohio State University Columbus, Ohio, 1969 

NotesEmbed ?

top

You must be logged in to post comments.