Symmetry Groups of Boolean Functions and Constructions of Permutation Groups

✍ Scribed by Andrzej Kisielewicz

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 273 KB
• Volume: 199
• Category: Article
• ISSN: 0021-8693
• DOI: 10.1006/jabr.1997.7198

✦ Synopsis

In this paper we deal with the symmetry group S f of a boolean function f on n-variables, that is, the set of all permutations on n elements which leave f invariant. The main problem is that of concrete representation: which permutation Ž . groups on n elements can be represented as G s S f for some n-ary boolean w x function f. Following P. Clote and E. Kranakis 6 we consider, more generally, Ž groups represented in such a way by k-valued boolean functions i.e., functions on . a two-element set with k possible values and call such permutation groups Ž . k -representable k G 2 . The starting point of this paper is a false statement in one w x of the theorems of 6 that every k-representable permutation group is 2-representable for all k G 2. We show that there exists a 3-representable permutation group that is not 2-representable. A natural question arises whether there are other examples like this. This question turns out to be not easy and leads us to considering general constructions of permutation groups and investigating their properties. The main result of the present paper may be summarized as follows: using known groups and ''standard'' constructions no other example like that above can be constructed. Nevertheless, we conjecture that there are k q 1-representable permutation groups that are not k-representable for all k G 2. If this is true, then this would open an interesting avenue toward investigating and classifying finite permutation groups.