Invariance groups of functions and related Galois connections
- PDF / 447,376 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 220 Views
Invariance groups of functions and related Galois connections Eszter K. Horváth1
· Reinhard Pöschel2
· Sven Reichard3
Received: 28 February 2020 / Accepted: 3 August 2020 © The Author(s) 2020
Abstract Invariance groups of sets of Boolean functions can be characterized as Galois closures of a suitable Galois connection. We consider such groups in a much more general context using group actions of an abstract group and arbitrary functions instead of Boolean ones. We characterize the Galois closures for both sides of the corresponding Galois connection and apply the results to known group actions. Keywords Invariance group · Group action · Galois connection · Boolean function · Permutation group Mathematics Subject Classification 20B25 · 20B35 · 06A15 · 05E18
1 Introduction An n-ary Boolean function f is invariant under a permutation σ ∈ Sn (notation σ f ) iff permuting the variables of f according to σ does not change the function value: f (xσ (1) , . . . , xσ (n) ) = f (x1 , . . . , xn ). The invariance group of f consists of all permutations σ with σ f .
This research of the first author was supported by NFSR of Hungary (OTKA), grant number K 115518, and by grant TUDFO/47138-1/2019-ITM of the Ministry for Innovation and Technology, Hungary.
B
Reinhard Pöschel [email protected] Eszter K. Horváth [email protected] http://www.math.u-szeged.hu/∼horvath Sven Reichard [email protected]
1
Bolyai Institute, University of Szeged, Szeged, Hungary
2
Technische Universität Dresden, Dresden, Germany
3
Dresden International University, Dresden, Germany
123
Beitr Algebra Geom
Invariance groups of Boolean functions are important objects of study in computer science (see Clote and Kranakis (1991) and the references therein). Algebraic investigations were started by Kisielewicz (1998) who called such groups symmetry groups. In Kisielewicz (1998) also k-valued Boolean functions and their symmetry groups are considered, which coincides with invariance groups of sets of ordinary Boolean functions (just taking the intersection of all invariance groups of functions in the given set). This led to the question how one can determine or characterize the invariance groups of sets of Boolean functions. There are several contributions to this problem, e.g., Grech (2010), Grech and Kisielewicz (2014) (giving a full answer for subgroups of direct sums of regular permutation groups), Horváth et al. (2015) (considering a finer classification using functions on a k-element set instead of Boolean functions), Xiao (2005) (generalization by considering the linear group GL(n, 2) instead of Sn ). The above relation induces a Galois connection between permutations and Boolean functions, such that the invariance groups (of sets of Boolean functions) are just the Galois closed sets of permutations. In the present paper we consider this Galois connection in a much more general n context, namely instead of Boolean functions f ∈ 22 (throughout the paper 2 mostly will stand for the two-element set {0, 1}) w
Data Loading...
