I am considering the following two binary operations on permutation groups:
- the direct product, and
- the wreath product.
It turns out that there is an efficient algorithm to factor a given permutation group $G$ with respect to the direct product: Chang, Mun See; Jefferson, Christopher, Disjoint direct product decompositions of permutation groups, ZBL07379067.
I am wondering whether there is also an algorithm to factor with respect to the wreath product, in the following sense.
A group is called directly indecomposable, if it cannot be written as the direct product of two non-trivial groups. The number of such groups (up to conjugacy) is https://oeis.org/A005226.
Let us call a group wreath primitive, if is directly indecomposable and cannot be written a the wreath product of two non-trivial groups. The number of such groups (up to conjugacy) is https://oeis.org/A005227.
It is known that every directly indecomposable permutation group, other than the trivial group, can be written in a unique way as the wreath product of a wreath primitive group and a permutation group.
Problem: I would like an efficient algorithm that yields this factorisation.
Motivation:
I am actually considering permutation groups as molecular combinatorial species. In this context, the direct product of permutation groups corresponds to the ordinary product of species. Thus, a directly indecomposably group corresponds to an atomic species. Moreover, the wreath product corresponds to the substitution of molecular species.
As mentioned above in terms of permutation groups, it is known (Bouchard, Pierre; Ouellette, Mario, Mario Ouellette’s arborescent decomposition for species of structures, Sémin. Lothar. Comb. 21, B21m, 13 p. (1989). ZBL1186.05020., cf. also Prop. 3.3.3 in the thesis of Kathleen Pineau, https://lacim.uqam.ca/les-parutions/LACIM-Publications-Volume-21.pdf) that any atomic species, other than the singleton species $X$, can be written in a unique way as a substitution $P(M)$, where $M$ is molecular and $P$ is a species corresponding to a wreath primitive permutation group. Note that, in particular, the degree of $P(M)$ is the product of the degrees of $P$ and $M$.
I am not sure whether one might be able to distill an algorithm from the article by Bouchard and Ouellette.
