Invariance groups of finite functions and orbit equivalence of permutation groups. (English) Zbl 1319.06003
Summary: Which subgroups of the symmetric group \(S_n\) 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\leq n\), the answer is easy: all subgroups of \(S_n\) 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 \(S_n\), 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.
MSC:
| 06A07 | Combinatorics of partially ordered sets |
| 06A15 | Galois correspondences, closure operators (in relation to ordered sets) |
| 08A40 | Operations and polynomials in algebraic structures, primal algebras |
| 06E30 | Boolean functions |
| 20B35 | Subgroups of symmetric groups |
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
Keywords:
invariance groups; symmetry groups; Galois connections; orbit equivalence of permutation groups; symmetric groups; alternating groups; functions of several variablesSoftware:
JBoolReferences:
| [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; · JFM 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; · Zbl 0354.20001 |
| [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; · JFM 22.0455.02 |
| [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; · Zbl 0421.03049 |
| [12] | Remak R., Über die Darstellung der endlichen Gruppen als Untergruppen direkter Produkte, J. Reine Angew. Math., 1930, 163, 1-44; · JFM 56.0129.01 |
| [13] | Seress Á., Primitive groups with no regular orbits on the set of subsets, Bull. Lond. Math. Soc., 1997, 29, 697-704; · Zbl 0892.20002 |
| [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; |
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.
