7
$\begingroup$

Let $(G, X)$ be a permutation group with domain $X$. Let $O=\{o_1,\dots,o_m\}$ be the set of orbits of $G$. I am interested in generating sets $S$ with the following property:

Let $g\in S$ be a generator. Write $g$ as $\prod_{i=1}^m g_i$ such that $g_i$ moves only points in $o_i$, that is, $g_i$ coincides with $g$ on $o_i$ and is the identity elsewhere. Then there is no non-empty subset of non-identity elements in $\{g_1,\dots,g_m\}$ whose product is not $g$ and is in $G$.

For example, the two generating sets \begin{align*} &(1,2,3)(4,5,6)(7,8,9)(10,11),\; (1,2,3)(4,5,6)(7,9,8)\quad\text{and}\\ &(1,2,3)(4,5,6),\; (7,8,9),\;(10,11) \end{align*} generate the same group $G$, with orbits $o_1=\{1,2,3\}$, $o_2=\{4,5,6\}$, $o_3=\{7,8,9\}$ and $o_4=\{10,11\}$. The first of the two generating sets does not have the desired property, because $(1,2,3)(4,5,6)$ is in $G$ (or also $(10,11)$), whereas the second does.

  • Does this property, or a generating set with this property, have a name?
  • Is there a fast way to produce such a generating set (other than testing all subsets)?
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ It is not obvious to me what you mean by "is a generator". I also don't guess the intended meaning of the set $\{g_1\dots g_m:g_i\neq 1\}$ since the $g_j$ seemed to had been fixed beforehand. (Also, is $m$, the number of orbits, the same as the $m$ in $g_1\dots g_m$?) $\endgroup$
    – YCor
    Commented Jul 3 at 9:39
  • $\begingroup$ "is a generator" refers to the given generating set. The set $\{g_1,\dots,g_m\mid g_i\neq 1\}$ is obtained by restricting $g$ to each of the orbits $o_1,\dots,o_m$ and discard identity elements. Does this make it clearer? $\endgroup$
    – Martin Rubey
    Commented Jul 3 at 9:43
  • 3
    $\begingroup$ I'm afraid not. "The given generating set": no generating set has been introduced. "Is obtained by" is a bit vague. Do you mean the following: "Let $g\in G$, and let $g_i$ coincide with $g$ on $o_i$ and be identity elsewhere, so that $g=\prod g_i$. Still I have no idea what is meant by $\{g_1,\dots,g_m|g_i\neq 1\}$, in the absence of quantifiers indicating what is fixed and what is not fixed (especially $g$, $i$), and what ranges over what. $\endgroup$
    – YCor
    Commented Jul 3 at 9:49
  • $\begingroup$ I edited the question, is it clearer now? (Briefly: yes, your interpretation of what the $g_i$ are is what I intended. I rearranged the subset property in the question. Thank you so much for helping to improve the question! $\endgroup$
    – Martin Rubey
    Commented Jul 3 at 9:59
  • $\begingroup$ Do you have an example where such group elements exist but they don't generate the full group? I believe that needs at least three orbits. $\endgroup$
    – Brendan McKay
    Commented Jul 6 at 3:47

1 Answer 1

Reset to default
2
$\begingroup$

Chang, Mun See; Jefferson, Christopher, Disjoint direct product decompositions of permutation groups, ZBL07379067. solves the problem.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Don't forget to accept your own answer if it resolves the question. $\endgroup$
    – LSpice
    Commented Jul 9 at 14:51
  • $\begingroup$ this might even be already implemented in GAP $\endgroup$
    – Dima Pasechnik
    Commented Jul 10 at 9:18
  • $\begingroup$ Indeed, there is an implementation: github.com/peal/DisjointDirectProdDecomposition $\endgroup$
    – Martin Rubey
    Commented Jul 10 at 10:22
  • $\begingroup$ There is now an alternative implementation in upcoming sagemath 10.5. $\endgroup$
    – Martin Rubey
    Commented Aug 29 at 13:52

You must log in to answer this question.

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