Canonical representation for sets in a group.

86 Views Asked by At

Let $G$ be a permutation group acting on a set $X$ of elements.

Is there a known group theory operation "$\mathrm{Canon}$" such that, for each pair $A, B \subseteq X$ of elements subsets, $\mathrm{Canon}(A) = \mathrm{Canon}(B)$ if and only if $A$ is in the orbit of $B$?

If yes, what is it called? Is it available in GAP?

Note 1 about orbits of sets: The orbit of a set of elements $A$ under $G$ is the following set of sets: $\{\{\sigma(x) : x \in A\}: \sigma \in G\}$. It describes how that set of elements, as a whole, may vary under $G$.

Note 2 about orbits of sets: The relation [$A$ is in the orbit of $B$] is symmetric. Furthermore, it is an equivalence relation. The power set $2^X$ is partitioned by it.

1

There are 1 best solutions below

1
On BEST ANSWER

If your group is a group of permutations, acting naturally on sets of integers, the GRAPE package for GAP includes a function SmallestImageSet that produces the smallest image in the orbit of a set under a group. The algorithm is described in:

Linton, Steve Finding the smallest image of a set. (English) Zbl 1134.05302 Gutierrez, Jaime (ed.), ISSAC 2004. Proceedings of the 2004 international symposium on symbolic and algebraic computation, Santander, Spain, July 4–7, 2004. New York, NY: ACM Press (ISBN 1-58113-827-X/pbk). 229-234