General theory of permutation commutativity

The symmetric groups $S_3$, $S_4$, $S_5$, and so on provide interesting first cases in the study of commuting graphs. The next step after considering the smallest symmetric groups separately, is to develop a general theory of commutativity in permutation groups. As is the case with transformations, permutations, and any kind of computation lattice theory will play a key role in this. The natural link between permutations and lattice theory comes from the orbit of the permutation which is a member of the lattice $Part(A)$. We will show that commuting permutations have orbits that form common unary congruences of each other.

Theorem. it is a necessary condition for any finite permutations $p,q$ to commute with one another for $orbit(p)$ to form a unary congruence of $q$ and for $orbit(q)$ must be a unary congruence of $p$.

Proof. We will start by showing that $orbit(q)$ is a unary congruence of $P$. We have for all $x$ that $p(q(x)) = q(p(x))$. We have that $q(x)$ is invariant under $orbit(q)$ so it follows that $p(q(x)) = p(x) [Q]$. This means that action of $p$ keeps $x$ and the application of $q$ to $x$ in the same $q$ orbit. To get that $[Q]$ forms a unary congruence of $p$ now let $x,y$ be two elements that are in the same $q]$ orbit so that $x = y [Q]$. Then as $x$ and $y$ are in the same orbit of a finite permutation there exists some $n$ such that $y = q^n(x)$ by repeated application of $q$. As $p(q(x)) = p(x) [Q]$ simple induction shows that $p(q^n(x)) = p(x) [Q]$. By simple substitution this means $p(x) = p(y) [Q]$ which shows that $orbit(q)$ is a unary congruence of $p$. Dually, for $q$ with respect to $p$. $\square$

This shows that permutations effect different pieces of information represented as partitions. In certain cases, we will show that commutativity is simply a special case of independence in lattice theory. Actions that operate independently of each other and don't effect each other with respect to the lattice of partitions $Part(A)$ commute with one another. Although this is a necessary condition for commutativity, it is not sufficient. In order to complete our understanding of permutations it is necessary to consider two special cases:

1. Repeated actions
2. Independent actions

If we have a permutation $p$ then a commuting permutation $q$ acts on its orbits. Case (1) occurs when $q$ fixes an orbit of $p$ under its quotient action then they both act on the same orbit. In that case, the action of $q$ must be a repeated version of the cycle it acts on. Iterations of a cycle commute and together form a cyclic group. Case (2) occurs when there are no non-trivial cases when the permutation fixes an orbit of the other permutation. Then the permutations truly act independently of one another. Repeated actions are responsible for the cyclic component and independent actions are responsible for the symmetric component in the wreath product presentation of the centralizer.

Independent actions have more interesting properties. Perhaps the simplest example of independent action is the commuting pair of permutations (0,1)(2,3) and (0,2)(1,3). Consider that you can represent 0,1,2,3 as 00,01,10,11 in binary. Then (0,1)(2,3) is a flip of the least significant bit and (0,2)(1,3) is a flip of the next most significant bit. The commutativity of (0,1)(2,3) and (0,2)(1,3) is stating that flipping independent bits commutes. This is in fact the simplest case, but it can clearly be generalized to any operations on independent elements, even if they contain millions of bits. As long as the operations operate completely independently of one another they will commute.

The partitions {{0,1},{2,3}} and {{0,2},{1,3}} even form a direct product in the lattice of partitions $Part(A)$ separating the elements into two separate bits of information. Likewise, ((0,2,4),(1,3,5)) and ((0,3),(1,4),(2,5)) produce {{0,2,4},{1,3,5}} and {{0,3},{1,4},{2,5}} which are direct products of one another. They independently flip a bit of information and cycle through the remaining bits of information and so they commute. The fact that they are unary congruences of one another's orbit means that they operate independently of one another.

Centralizer of the symmetric group: we can now form the centralizer of a permutation in the symmetric group by $\vee C_i \wr S_j$ which is the subgroup join of the wreath product for each regular component of the permutation. The repeated actions are responsible for $C_n$ and the independent actions are responsible for $S_n$ in the wreath product.