Easy way to find the generators of the centralizer of a permutation $\sigma \in S_n$ Like if I want to find the generator of the centralizer of $(1,2)(3,4) \in S_4$, what is the fastest way to find the generators of the centralizer?
There must be an algorithm that doesn't involve trying every element to get the centralizer and then trying various combinations of the elements in the centralizer to get the generators.
 A: The centralizer of $(12)(34)$ is generated by $(12),(34),$ and any permutation which swaps $\{1,2\}$ and $\{3,4\}$, for instance $(13)(24)$.
For a permutation $\pi$ of $[n]=\{1,\cdots,n\}$, we have an action of the cyclic subgroup $\langle \pi\rangle$ on $[n]$, which has a block system that cannot be refined further (without being trivial) consisting of the cycles of $\pi$. So for instance, the permutation $(123)(456)$ has block system $\{\{1,2,3\},\{4,5,6\}\}$. Call the blocks, cycle-blocks. The permutation $\pi$ not only fixes the block system as a whole, but fixes each individual block.
Lemma. If permutations $\pi$ and $\tau$ commute, then they permute each other's cycle-blocks.
Note that $\tau\pi\tau^{-1}$ has the same cycle notation as $\pi$, but with $\tau$ applied to all the numbers present in it. See if you can use this to prove the lemma!
Blocks with different sizes cannot be permuted among each other, obviously. Thus, if $\pi=\pi_1\pi_2\cdots$ where each $\pi_k$ is a product of $k$-cycles, a permutation $\tau$ centralizing $\pi$ must permute the $1$-cycle-blocks among each other, the $2$-cycle blocks among each other, etc. Therefore, we can write $\tau=\tau_1\tau_2\cdots$ where each $\tau_k$ centralizes $\pi_k$ and fixes numbers not in the $k$-cycle-blocks of $\pi$.
That is, if we set $\Pi_k$ to be the support of $\pi_k$ (the set of elements it actually moves, i.e. its non-fixed-points, i.e. the numbers that appear in the $k$-cycles of $\pi$) then we have an internal direct product
$$ C_{S_n}(\pi)=C_{S_{\Pi_1}}(\pi_{\large 1})\times C_{S_{\Pi_{\large 2}}}(\pi_2)\times\cdots $$
To find a generating set for the whole centralizer, we just need to find generating sets for the smaller ones.
Suppose $\pi_k=\sigma_1\sigma_2\cdots \sigma_m$ is a product of $k$-cyclces $\sigma_i$. Obviously $C_{S_{\Pi_{\large k}}}(\pi_k)$ contains the internal direct product $\langle\sigma_1\rangle\times\langle\sigma_2\rangle\cdots\times\langle\sigma_m\rangle$ (isomorphic to $\mathbb{Z}_k^m$) but it actually contains more than this, since some centralizing elements may permute the cycle-blocks of $\pi_k$. However, you can prove any centralizing permutation which fixes each individual cycle-block must be in this internal direct product.
Write the cycles $\sigma_1,\sigma_2,\cdots,\sigma_m$ as rows of numbers in a table. A permutation $\tau$ which cycles the numbers in an individual row centralizes $\pi_k$ (these are the elements of $\langle\sigma_i\rangle$s). But also any permutation $\tau$ which permutes the rows themselves (while keeping the numbers in them in the same order) also centralizes $\pi_k$! This is a copy of $S_m$ within $S_{\Pi_k}$. You can pick any generating set for $S_m$ (e.g. adjacent transpositions) and turn it into a generating set for this copy $\overline{S_m}$.
Now, we must have $C_{S_{\Pi_{\large k}}}(\pi_k)=\langle\sigma_1,\cdots,\sigma_m\rangle\rtimes\overline{S_m}$. For, given any $\tau$ in this centralizer, we can pick a $\rho$ which permutes the rows of our table the same way $\tau$ does (in the aforementioned way), then $\rho^{-1}\tau$ is a centralizing element which fixes the cycle-blocks of $\pi_k$ hence must be in the internal direct product of $\langle\sigma_i\rangle$s, so we conclude an arbitrary $\tau$ is in this semidirect product.
(The semidirect product is a copy of the wreath product $\mathbb{Z}_k\wr S_m$.)
For instance, on the set $\{a,b,x,y,1,2,3,4,5,6,7,8,9\}$ consider
$$ \pi=(ab)(xy)(123)(456)(789). $$
Write the following table
$$ \begin{array}{ccc} 
a & b & \\
 x & y & \\
 1 & 2 & 3 \\
 4 & 5 & 6 \\
 7 & 8 & 9 
\end{array} $$
Our generating set should include the cycles of $\pi$. For $\pi_2=(ab)(xy)$, we have a $\overline{S_2}$, whose adjacent transposition corresponds to $(ax)(by)$. For $\pi_3$, we have a $\overline{S_3}$ with two adjacent transpositions corresponding to $(14)(25)(36)$ and $(47)(58)(69)$. Therefore,
$$ \{(ab),(xy),(ax)(by),(123),(456),(789),(14)(25)(36),(47)(58)(69)\} $$
is a generating set.
