Consider a Permutation Group $G$ acting on some set $X$. Since it is well known that the orbits created by $G$ acting on $X$ partition $X$, I was wondering whether there might be some efficient deterministic approach to determining if two elements $x_1, x_2 \in X$ are equivalent under the equivalence relation associated with this partition (i.e. if there is in general a smarter way to determine this than enumerating elements of the orbit $G \cdot x_1$ until we find $x_2$ or exhaust the orbit).

This is essentially the same problem as testing whether there is some $g \in G$ for which $x_1^g = x_2$ right? I know that there are backtrack methods for iterating through all group elements which can be efficient if search tree pruning is applied but I'm not sure if that's relevant here.

My understanding of group theory is a bit rudimentary so if this question has a trivial answer I'd appreciate it if someone could nevertheless suggest some keywords which might point me in the right direction.

  • $\begingroup$ How is the data given? $\endgroup$ – Kenny Lau Jun 18 '18 at 16:46
  • $\begingroup$ $G$ would ideally be represented by a base and strong generating set and $X$ would be some set of numbers. $\endgroup$ – Peter Jun 18 '18 at 16:56

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.