Young subgroups for reversible computers
We consider the symmetric group S-n in the special case where n is composite: n = pq (both p and q being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of S-pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup S-p(q), whereas the second one is an element of the dual Young subgroup S-p(q). This leads to synthesis methods for arbitrary reversible logic circuits of logic width w. These circuits form a group isomorphic to S(2)w. A particularly efficient synthesis is found by choosing p = 2 and thus q = 2(w-1). The approach illustrates a direct link between combinatorics, group theory, and reversible computing.
young subgroup reversible computing double coset enumeration