How does GAP calculate 2-closure?

Question

GAP software has a method for calculating the two closure of a (permutation) group? how does it do that calculation?

Answer 1

You can find the actual code in the file lib/stbcbckt.gi in the GAP distribution. The algorithm performs a backtrack search through the symmetric group, searching for permutations that preserve the orbits of $G$. The crucial (but very technical) bit is to only test one element in each coset of the subgroup found so far, and to avoid testing elements that one can deduce a priori will not satisfy the condition. (Example: if $a$ satisfies but $b$ does not, the $ab$ cannot satisfy either.)

This clearly does not scale well with the degree, as the run time might be exponential or worse.

Addendum (prompted by comment): When calculating the 2-closure of $U$, the process maintains a subgroup $S$, consisting of the part of the 2-closure found already. This subgroup is initialized initially with $U$ and is changed whenever new elements are found. Now if testing one element $a$ for being in the 2-closure, the same result will hold for all elements in the coset $Sa$ (and even in the double coset $SaS$). Thus it is sufficient to test one element in each coset only. In practice this is done by discardiong elements that are known cheaply to not be lexicographically minimal in their coset.