Symmetry groups of Boolean functions and constructions of permutation groups (Q1378434): Difference between revisions

Let \(n\) and \(k\) be natural numbers, \(n\geq 1\) and \(k\geq 2\). A subgroup \(G\) of the symmetric group \(S_n\) is called \(k\)-representable iff there is a \(k\)-valued boolean function in \(n\) variables \(f\colon\{0,1\}^n\to\{0,1,\ldots,k-1\}\) such that \(G\) coincides with the symmetry group \(S(f)\) defined by \(S(f):=\{\sigma\mid\sigma\in S_n\) and \(f(x_1,\ldots,x_n)=f(x_{\sigma(1)},\ldots,x_{\sigma(n)})\) for all \((x_i)\in\{0,1\}^n\}\). \(G\) is called representable if it is \(k\)-representable for some \(k\geq 2\). In the present paper conditions are investigated for a subgroup \(G\leq S_n\) to be \(k\)-representable or not \(k\)-representable. As a counterexample to an assertion of \textit{P. Clote} and \textit{E. Kranakis} [SIAM J. Comput. 20, No. 3, 553-590 (1991; Zbl 0734.68038)]\ it is shown that there exists a \(3\)-representable permutation group which is not \(2\)-representable. Also several ways to construct non-(\(k\)-)representable groups are introduced and discussed in some detail, in particular intransitive and imprimitive group constructions. It is conjectured that for all \(k\geq 2\) there are \((k+1)\)-representable permutation groups which are not \(k\)-representable.