Transformation completeness properties of SVPC transformation sets

A set T of permutations of a finite set D is said to be transformation complete if the orbits of 〈T〉, the group generated by T, acting on F(D), the power set of D, are exactly the set of subsets of D having the same cardinality, where the orbit of xε{lunate}F(D) is {α(x)|αε{lunate}〈T〉}. This paper studies the transformation completeness properties of suppressed variable permutation and complementation (SVPC) transformations which act on Boolean variables with domain being D = {0, 1}ⁿ. An SVPC transformation with r control variables is an identity on the n-cube except on an (n - r)-subcube where the acting is like a variable permutation and complementation (VPC) transformation on n - r variables, 0≤r<n. Let Pⁿ_r be the set of all SVPC transformations on n variables with r control variables. It is shown that Pⁿ_r is transformation complete for n>r≥1. In particular, it is shown that S_2ⁿ = 〈Pⁿ_n-1〉 = 〈Pⁿ_n-2〉 ⊃ 〈Pⁿ_n-3〉 = 〈Pⁿ_n-4〉 = ⋯ = 〈Pⁿ₁〉 = A_2ⁿ ⊃ 〈Pⁿ₀〉, where S_2ⁿ and A_2ⁿ are the symmetric group and alternating group of degree 2ⁿ, respectively. Pⁿ₀, i.e., the VPC transformation group on n variables, is not transformation complete, however. Thus, one control variable is necessary and sufficient to make Pⁿ_r transformation complete.