We prove that every permutation of a Cartesian product of two finite sets can be written as a composition of three permutations, the first of which only modifies the left projection, the second only the right projection, and the third again only the left projection, and three alternations is indeed the optimal number. We show that for two countably infinite sets, the corresponding optimal number of alternations, called the alternation diameter, is four. The notion of alternation diameter can be defined in any category. In the category of finite-dimensional vector spaces, the diameter is also three. For the category of topological spaces, we exhibit a single self-homeomorphism of the plane which is not generated by finitely many alternations of homeomorphisms that only change one coordinate. The results on finite sets and vector spaces were previously known in the context of memoryless computation.
The case of finite sets, which started this paper, is inspired by @cite_1 , where it is shown that any permutation of @math , for three sets @math with @math , can be written as a composition of finitely many permutations where alternately only @math or @math is permuted. Our notion of alternation diameter in the category of finite sets is related to this definition, as it also means refers to alternately permuting a product on the left and right''. The difference is that there is no communication coordinate (making it harder), but we allow the permutation to depend on the value on the right when permuting the value on the left, and vice versa (making it easier).
@cite_1
2339438075
Abstract We say that a reversible boolean function on n bits has alternation depth d if it can be written as the sequential composition of d reversible boolean functions, each of which acts only on the top n − 1 bits or on the bottom n − 1 bits. Moreover, if the functions on n − 1 bits are even, we speak of even alternation depth. We show that every even reversible boolean function of n ⩾ 4 bits has alternation depth at most 9 and even alternation depth at most 13.