3
$\begingroup$

If $G$ is a group and $H$ is a subgroup of $S_n$ we can form their wreath product $G \wr H = \{(g_1, ..., g_n; \pi): g_i \in G$ and $\pi \in H\}$. I'm wondering whether the following is correct:

  1. $<(e, ..., g_i, ..., e; e)> = \{(g_1, ..., g_n; e)\}$

  2. $\{(g_1, ..., g_n; e)\} \circ \{(e, ..., e; \pi)\} = G \wr H$

Additionally, will all elements of $G \wr H$ be generated distinctly? Or in other words is it possible to do this more efficiently?

Edit: For $(g_1, ..., g_n; \pi), (a_1, ..., a_n; \phi) \in G \wr H, \circ$ is defined by $(a_1, ..., a_n; \phi) \circ (g_1, ..., g_n; \pi) = (a_{\pi(1)}*g_1, ..., a_{\pi(n)}*g_n; \phi\circ\pi)$ where $*$ is the operation for $G$, although for my purposes my $G$ can be thought of as $S_n$.

You also have $(g_1, ..., g_n; \pi)^{-1} = (g^{-1}_{\pi^{-1}(1)}, ...; \pi^{-1})$

By distinct I mean for distinct $(g_1, ..., g_n; e), (a_1, ..., a_n; e), (e, ..., e; \pi), (e, ..., e; \phi)$ we don't have $(g_1, ..., g_n; e) \circ (e, ..., e; \pi) = (a_1, ..., a_n; e) \circ (e, ..., e; \pi)$ or $(g_1, ..., g_n; e) \circ (e, ..., e; \pi) = (g_1, ..., g_n; e) \circ (e, ..., e; \phi)$.

I'm not so sure about that for the first part with generating $\{(g_1, ..., g_n; e)\}$, but by efficiency I mean I want to generate an object much like a wreath product algorithmically so I don't want to do more work than necessary when generating it.

Improve this question
$\endgroup$
4
  • $\begingroup$ What do "distinctly" and "efficiently" mean? The group is not free. Also what is $\circ$? $\endgroup$
    – user6976
    Commented Aug 30, 2011 at 3:59
  • $\begingroup$ @Nick: About 1. and 2. - these are standard properties of semidirect products, see Wiki. I still do not understand what "efficiently" means (and I am not sure you understand it either). $\endgroup$
    – user6976
    Commented Aug 30, 2011 at 4:44
  • $\begingroup$ @Mark: I'm probably abusing the word "efficiency" sorry, I'm trying to write functions for the equivalence ((simple), ordinal or cardinal) of normal form games for a library I have, one way I can think of is to iterate through the set of bijections (which are a lot like a wreath product) to test whether they meet the conditions for an isomorphism, so I'm trying to generate the set of bijections without doing more work than needed. Semi direct products do appear to be what I really want, I'll play around with that and see where I get, thanks! $\endgroup$
    – user17474
    Commented Aug 30, 2011 at 4:53
  • $\begingroup$ Oh, and I'm generating $bij(A, B)$ from $bij(A,B) = g \circ bij(A, A)$ for any $g \in bij(A, B)$. $\endgroup$
    – user17474
    Commented Aug 30, 2011 at 4:55

1 Answer 1

Reset to default
3
$\begingroup$

Note that the wreath product is a semidirect product with normal subgroup $G^n$ and complement $H$. A group theory book that defines wreath product will cover this fact.

Part 1. seems to ask whether the normal $G^n$ is generated by elements of the form $(e, \ldots, g_i, \ldots,e)$, i.e. those which are the identity except in one coordinate. This is true by definition of multiplication in the direct product $G^n$.

Part 2. I interpret to ask whether $G \wr H = G^n H$--this is true because, as noted, the wreath product is a semidirect product of these two groups.

The "distinctness" seems to follow from the existence of inverses. For example, if $(g_1, \ldots, g_n; e) \circ (e, \ldots, e; \pi) = (a_1, \ldots, a_n, ; e) \circ (e, \ldots, e; \pi)$, we may multiply on the right by $(e, \ldots, e; \pi)^{-1}$ and conclude that $(g_1, \ldots, g_n; e) = (a_1, \ldots, a_n; e)$.

There could be an algorithmic question in the original post about generating a wreath product, but it requires a more careful statement.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What do you mean by a more careful statement? My intention is to algorithmically generate a set much like this for testing equivalence of normal form games. $\endgroup$
    – user17474
    Commented Aug 30, 2011 at 5:00
  • 1
    $\begingroup$ By "more careful statement", I mean something mathematically definable to replace "more work than necessary" in the orginal post. For example, we could ask for the smallest possible set of generators of the wreath product. But this might not be what you want--maybe you'll later need to enumerate every element of the group. If that were true the minimality of a generating set might be a liability. $\endgroup$
    – Dikran Karagueuzian
    Commented Aug 31, 2011 at 3:49
  • 1
    $\begingroup$ It might also be that you have extra information about $G$ and $H$ that is useful. As a simple example, if you were interested in the minimality of the generating set and if $H$ were transitive, you could take a set of generators for $G \times 1 \times \cdots \times 1$ and use $H$ to get a set of generators for $G \times \cdots \times G$. $\endgroup$
    – Dikran Karagueuzian
    Commented Aug 31, 2011 at 3:49

You must log in to answer this question.