4
$\begingroup$

Given two permutation groups $G,H$ on the same set $M$, and a permutation $\sigma$ on $M$, how to find a factorization $\sigma = gh$ (but not $\sigma = hg$), where $g \in G$ and $h \in H$?

This problem arises from modeling variations of Rubik's Cube with permutation groups. One problem with this approach is that these puzzles often contain indistinguishable stickers. For example, in the $4\times4\times4$ puzzle the four center stickers on each face are indistinguishable, giving a total of $24^6$ potential "solved" configurations. But not all of these are actually possible. Calculations with Mathematica show that for each face, only $12$ permutations of its center stickers are achievable, without disrupting the configuration of other stickers. Therefore in a scrambled state we cannot randomly assign to each center sticker a target position, otherwise the permutation may not be solvable.

$\endgroup$
  • $\begingroup$ This is a coset intersection problem - you are looking for $G\sigma \cap H$. There is a discussion about it here $\endgroup$ – Derek Holt Oct 25 '17 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.