5
$\begingroup$

I know that if two permutations share only 1 point that is moved by both of them, then the commutator of those permutations is a 3-cycle [1]. This is helpful for puzzles like Rubik's cube, where if two moves overlap by just 1 piece, the commutator will result in a 3-cycle with the remaining pieces fixed.

Can anything be said about the number of moved points of the commutator if the permutations overlap by more than 1 point? I think the max number of moved points would be 3n, where n is the number of shared moved points. But it could be fewer if the shared points move to other shared points.

In other words, is there an easy way to tell how many points will be moved by the commutator [g,h] given the points that are moved by both g and h (and other information about shared points moving to shared points)?

$\endgroup$

1 Answer 1

8
$\begingroup$

This answer uses the convention that $[g,h] = g^{-1}h^{-1}gh$. If $g$ is a permutation, the support of $g$, denoted $\mathrm{supp}(g)$, is the set of points that $g$ moves.

Proposition. Let $g$ and $h$ be permutations, and let $S=\mathrm{supp}(g)\cap \mathrm{supp}(h)$. Then $$ \mathrm{supp}\bigl([g,h]\bigr) \subseteq S\cup g^{-1}(S)\cup h^{-1}(S). $$

Proof: Suppose to the contrary that $p\in \mathrm{supp}\bigl([g,h]\bigr)$ but $p\notin S\cup g^{-1}(S)\cup h^{-1}(S)$. Since $p\notin S$, either $g$ or $h$ must fix $p$.

If $g(p)=p$, then $h$ must move $p$ since otherwise $[g,h]$ would fix $p$. Note then that $h$ moves $h(p)$ as well. Since $p\notin h^{-1}(S)$, we know that $h(p)\notin S$ and therefore $g$ must fix $h(p)$. Then $gh(p)=h(p)$, so $ g^{-1}h^{-1}gh(p)=g^{-1}h^{-1}h(p) = g^{-1}(p)=p $, a contradiction.

If $h(p)=p$, then $g$ must move $p$ since otherwise $[g,h]$ would fix $p$. Note then that $g$ moves $g(p)$ as well. But since $p\notin g^{-1}(S)$ we know that $g(p)\notin S$ and therefore $h$ must fix $g(p)$. Then $h^{-1}$ fixes $g(p)$ as well, so $h^{-1}gh(p) = h^{-1}g(p)=g(p)$ and hence $g^{-1}h^{-1}gh(p) = g^{-1}g(p)=p$, a contradiction.$\quad \square$

Corollary. If $g$ and $h$ are permutations and $|\mathrm{supp}(g)\cap \mathrm{supp}(h)| = n$, then $\bigl|\mathrm{supp}\bigl([g,h]\bigr)\bigr|\leq 3n$.

This leaves open the question of which pairs $(n,k)$ are possible, where $$ n=|\mathrm{supp}(g)\cap \mathrm{supp}(h)|\qquad\text{and}\qquad k=\bigl|\mathrm{supp}\bigl([g,h]\bigr)\bigr|. $$ The proposition above shows that $k\leq 3n$, and for $n=1$ we know that $(1,3)$ is the only possibility. Here are some other observations:

  • $k=1$ is never possible, since a nontrivial permutation must move at least two points.

  • $k=2$ is never possible since $[g,h]$ is always an even permutation, and the only permutations that move exactly two points are transpositions.

  • For $n\geq 2$, the pair $(n,0)$ is possible. For example, $g$ could be an $n$-cycle and $h$ could be the same as $g$ (or the inverse of $g$, if you want $g$ and $h$ to be distinct).

  • The pair $(2,3)$ is possible, e.g. $\bigl[(1\;\;2),(1\;\;2\;\;3)\bigr] = (1\;\;3\;\;2)$.

  • The pair $(2,4)$ is possible, e.g. $\bigl[(1\;\;2\;\;3),(1\;\;2\;\;4)\bigr] = (1\;\;2)(3\;\;4)$.

  • The pair $(2,5)$ is possible, e.g. $\bigl[(1\;\;2\;\;3),(1\;\;4)(2\;\;5)\bigr] = (1\;\;4\;\;5\;\;3\;\;2)$.

  • The pair $(3,4)$ is possible, e.g. $\bigl[(1\;\;2\;\;3),(1\;\;2)(3\;\;4)\bigr] = (1\;\;3)(2\;\;4)$.

  • The pair $(3,5)$ is possible, e.g. $\bigl[(1\;\;2\;\;3),(1\;\;2\;\;5)(3\;\;4)\bigr] = (1\;\;3\;\;5\;\;4\;\;2)$.

  • If $(n,k)$ is possible and $(n',k')$ is possible, then $(n+n',k+k')$ is possible. Specifically, if $f$ and $g$ realize $(n,k)$ and $f'$ and $g'$ realize $(n',k')$, where $\mathrm{supp}(f')\cup \mathrm{supp}(g')$ is disjoint from $\mathrm{supp}(f)\cup \mathrm{supp}(g)$, then $ff'$ and $gg'$ realize $(n+n',k+k')$.

It follows from these obervations that all pairs $(n,k)$ are possible for $n\geq 2$ and $0\leq k\leq 3n$ as long as $k\ne 1,2$.

$\endgroup$
2
  • $\begingroup$ Thank you for the insightful and detailed answer! $\endgroup$ Commented Oct 2, 2021 at 4:37
  • $\begingroup$ Hi @Jim Belk Are there sharper bounds? For example, trivially if $g=f$, then $S=supp(f)=supp(g)$ which could be as large as we want, but $| supp([f,f]) | =0$. So can we say more about $| supp([f,g]) |$ in terms of just $|supp(f)|$ and $|supp(g)|$ ? At least statistically, if not in absolute terms. $\endgroup$
    – BharatRam
    Commented Feb 6, 2022 at 14:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .