Wreath product

In group theory, the wreath product is a special combination of two groups based on the semidirect product. It is formed by the action of one group on many copies of another group, somewhat analogous to exponentiation. Wreath products are used in the classification of permutation groups and also provide a way of constructing interesting examples of groups.

Given two groups $A$ and $H$ (sometimes known as the bottom and top^[1]), there exist two variants of the wreath product: the unrestricted wreath product $A{\text{ Wr }}H$ and the restricted wreath product $A{\text{ wr }}H$ . The general form, denoted by $A{\text{ Wr}}_{\Omega }H$ or $A{\text{ wr}}_{\Omega }H$ respectively, requires that $H$ acts on some set $\Omega$ ; when unspecified, usually $\Omega =H$ (a regular wreath product), though a different $\Omega$ is sometimes implied. The two variants coincide when $A$ , $H$ , and $\Omega$ are all finite. Either variant is also denoted as $A\wr H$ (with \wr for the LaTeX symbol) or A ≀ H (Unicode U+2240).

The notion generalizes to semigroups and, as such, is a central construction in the Krohn–Rhodes structure theory of finite semigroups.

Definition

Let $A$ be a group and let $H$ be a group acting on a set $\Omega$ (on the left). The direct product $A^{\Omega }$ of $A$ with itself indexed by $\Omega$ is the set of sequences ${\overline {a}}=(a_{\omega })_{\omega \in \Omega }$ in $A$ , indexed by $\Omega$ , with a group operation given by pointwise multiplication. The action of $H$ on $\Omega$ can be extended to an action on $A^{\Omega }$ by reindexing, namely by defining

h\cdot (a_{\omega })_{\omega \in \Omega }:=(a_{h^{-1}\cdot \omega })_{\omega \in \Omega }

for all $h\in H$ and all $(a_{\omega })_{\omega \in \Omega }\in A^{\Omega }$ .

Then the unrestricted wreath product $A{\text{ Wr}}_{\Omega }H$ of $A$ by $H$ is the semidirect product $A^{\Omega }\rtimes H$ with the action of $H$ on $A^{\Omega }$ given above. The subgroup $A^{\Omega }$ of $A^{\Omega }\rtimes H$ is called the base of the wreath product.

The restricted wreath product $A{\text{ wr}}_{\Omega }H$ is constructed in the same way as the unrestricted wreath product except that one uses the direct sum as the base of the wreath product. In this case, the base consists of all sequences in $A^{\Omega }$ with finitely many non-identity entries. The two definitions coincide when $\Omega$ is finite.

In the most common case, $\Omega =H$ , and $H$ acts on itself by left multiplication. In this case, the unrestricted and restricted wreath product may be denoted by $A{\text{ Wr }}H$ and $A{\text{ wr }}H$ respectively. This is called the regular wreath product.

Notation and conventions

The structure of the wreath product of A by H depends on the H-set Ωおめが and in case Ωおめが is infinite it also depends on whether one uses the restricted or unrestricted wreath product. However, in literature the notation used may be deficient and one needs to pay attention to the circumstances.

In literature A≀_ΩおめがH may stand for the unrestricted wreath product A Wr_Ωおめが H or the restricted wreath product A wr_Ωおめが H.
Similarly, A≀H may stand for the unrestricted regular wreath product A Wr H or the restricted regular wreath product A wr H.
In literature the H-set Ωおめが may be omitted from the notation even if Ωおめが ≠ H.
In the special case that H = S_n is the symmetric group of degree n it is common in the literature to assume that Ωおめが = {1,...,n} (with the natural action of S_n) and then omit Ωおめが from the notation. That is, A≀S_n commonly denotes A≀_{1,...,n}S_n instead of the regular wreath product A≀_{S_n}S_n. In the first case the base group is the product of n copies of A, in the latter it is the product of n! copies of A.

Properties

Agreement of unrestricted and restricted wreath product on finite Ωおめが

Since the finite direct product is the same as the finite direct sum of groups, it follows that the unrestricted A Wr_Ωおめが H and the restricted wreath product A wr_Ωおめが H agree if Ωおめが is finite. In particular this is true when Ωおめが = H and H is finite.

Subgroup

A wr_Ωおめが H is always a subgroup of A Wr_Ωおめが H.

Cardinality

If A, H and Ωおめが are finite, then

|A≀_ΩおめがH| = |A|^{|Ωおめが|}|H|.^[2]

Universal embedding theorem

Universal embedding theorem: If G is an extension of A by H, then there exists a subgroup of the unrestricted wreath product A≀H which is isomorphic to G.^[3] This is also known as the Krasner–Kaloujnine embedding theorem. The Krohn–Rhodes theorem involves what is basically the semigroup equivalent of this.^[4]

Canonical actions of wreath products

If the group A acts on a set Λらむだ then there are two canonical ways to construct sets from Ωおめが and Λらむだ on which A Wr_Ωおめが H (and therefore also A wr_Ωおめが H) can act.

The imprimitive wreath product action on Λらむだ × Ωおめが.
If ((a_ωおめが),h) ∈ A Wr_Ωおめが H and (λらむだ,ωおめが′) ∈ Λらむだ × Ωおめが, then
$((a_{\omega }),h)\cdot (\lambda ,\omega '):=(a_{h(\omega ')}\lambda ,h\omega ').$
The primitive wreath product action on Λらむだ^Ωおめが.
An element in Λらむだ^Ωおめが is a sequence (λらむだ_ωおめが) indexed by the H-set Ωおめが. Given an element ((a_ωおめが), h) ∈ A Wr_Ωおめが H its operation on (λらむだ_ωおめが) ∈ Λらむだ^Ωおめが is given by
$((a_{\omega }),h)\cdot (\lambda _{\omega }):=(a_{h^{-1}\omega }\lambda _{h^{-1}\omega }).$

Examples

The lamplighter group is the restricted wreath product $\mathbb {Z} _{2}\wr \mathbb {Z}$ .

$\mathbb {Z} _{m}\wr S_{n}$ (the generalized symmetric group). The base of this wreath product is the n-fold direct product $\mathbb {Z} _{m}^{n}=\mathbb {Z} _{m}...\mathbb {Z} _{m}$ of copies of $\mathbb {Z} _{m}$ where the action $\phi :S_{n}\to {\text{Aut}}(\mathbb {Z} _{m}^{n})$ of the symmetric group S_n of degree n is given by φふぁい(σしぐま)(αあるふぁ₁,..., αあるふぁ_n) := (αあるふぁ_{σしぐま(1)},..., αあるふぁ_{σしぐま(n)}).^[5]

$S_{2}\wr S_{n}$ (the hyperoctahedral group).
The action of S_n on {1,...,n} is as above. Since the symmetric group S₂ of degree 2 is isomorphic to $\mathbb {Z} _{2}$ the hyperoctahedral group is a special case of a generalized symmetric group.^[6]

The smallest non-trivial wreath product is $\mathbb {Z} _{2}\wr \mathbb {Z} _{2}$ , which is the two-dimensional case of the above hyperoctahedral group. It is the symmetry group of the square, also called D₄, the dihedral group of order 8.
Let p be a prime and let $n\geq 1$ . Let P be a Sylow p-subgroup of the symmetric group S_pⁿ. Then P is isomorphic to the iterated regular wreath product $W_{n}=\mathbb {Z} _{p}\wr ...\wr \mathbb {Z} _{p}$ of n copies of $\mathbb {Z} _{p}$ . Here $W_{1}:=\mathbb {Z} _{p}$ and $W_{k}:=W_{k-1}\wr \mathbb {Z} _{p}$ for all $k\geq 2$ .^[7]^[8] For instance, the Sylow 2-subgroup of S₄ is the above $\mathbb {Z} _{2}\wr \mathbb {Z} _{2}$ group.

The Rubik's Cube group is a normal subgroup of index 12 in the product of wreath products, $(\mathbb {Z} _{3}\wr S_{8})\times (\mathbb {Z} _{2}\wr S_{12})$ , the factors corresponding to the symmetries of the 8 corners and 12 edges.

The Sudoku validity-preserving transformations (VPT) group contains the double wreath product (S₃ ≀ S₃) ≀ S₂, where the factors are the permutation of rows/columns within a 3-row or 3-column band or stack (S₃), the permutation of the bands/stacks themselves (S₃) and the transposition, which interchanges the bands and stacks (S₂). Here, the index sets Ωおめが are the set of bands (resp. stacks) (|Ωおめが| = 3) and the set {bands, stacks} (|Ωおめが| = 2). Accordingly, |S₃ ≀ S₃| = |S₃|³|S₃| = (3!)⁴ and |(S₃ ≀ S₃) ≀ S₂| = |S₃ ≀ S₃|²|S₂| = (3!)⁸ × 2.

Wreath products arise naturally in the symmetries of complete rooted trees and their graphs. For example, the repeated (iterated) wreath product S₂ ≀ S₂ ≀ ... ≀ S₂ is the automorphism group of a complete binary tree.

References

^ Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1998), "Wreath products", Notes on Infinite Permutation Groups, Lecture Notes in Mathematics, vol. 1698, Berlin, Heidelberg: Springer, pp. 67–76, doi:10.1007/bfb0092558, ISBN 978-3-540-49813-1, retrieved 2021-05-12
^ Joseph J. Rotman, An Introduction to the Theory of Groups, p. 172 (1995)
^ M. Krasner and L. Kaloujnine, "Produit complet des groupes de permutations et le problème d'extension de groupes III", Acta Sci. Math. 14, pp. 69–82 (1951)
^ J D P Meldrum (1995). Wreath Products of Groups and Semigroups. Longman [UK] / Wiley [US]. p. ix. ISBN 978-0-582-02693-3.
^ J. W. Davies and A. O. Morris, "The Schur Multiplier of the Generalized Symmetric Group", J. London Math. Soc. (2), 8, (1974), pp. 615–620
^ P. Graczyk, G. Letac and H. Massam, "The Hyperoctahedral Group, Symmetric Group Representations and the Moments of the Real Wishart Distribution", J. Theoret. Probab. 18 (2005), no. 1, 1–42.
^ Joseph J. Rotman, An Introduction to the Theory of Groups, p. 176 (1995)
^ L. Kaloujnine, "La structure des p-groupes de Sylow des groupes symétriques finis", Annales Scientifiques de l'École Normale Supérieure. Troisième Série 65, pp. 239–276 (1948)

External links

Wreath product in Encyclopedia of Mathematics.
Charles Wells, "Some applications of the wreath product construction", revised. Archived 21 February 2014 at the Wayback Machine

[1] Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1998), "Wreath products", Notes on Infinite Permutation Groups, Lecture Notes in Mathematics, vol. 1698, Berlin, Heidelberg: Springer, pp. 67–76, doi:10.1007/bfb0092558, ISBN 978-3-540-49813-1, retrieved 2021-05-12

[2] Joseph J. Rotman, An Introduction to the Theory of Groups, p. 172 (1995)

[3] M. Krasner and L. Kaloujnine, "Produit complet des groupes de permutations et le problème d'extension de groupes III", Acta Sci. Math. 14, pp. 69–82 (1951)

[Meldrum1995-4] J D P Meldrum (1995). Wreath Products of Groups and Semigroups. Longman [UK] / Wiley [US]. p. ix. ISBN 978-0-582-02693-3.

[5] J. W. Davies and A. O. Morris, "The Schur Multiplier of the Generalized Symmetric Group", J. London Math. Soc. (2), 8, (1974), pp. 615–620

[6] P. Graczyk, G. Letac and H. Massam, "The Hyperoctahedral Group, Symmetric Group Representations and the Moments of the Real Wishart Distribution", J. Theoret. Probab. 18 (2005), no. 1, 1–42.

[7] Joseph J. Rotman, An Introduction to the Theory of Groups, p. 176 (1995)

[8] L. Kaloujnine, "La structure des p-groupes de Sylow des groupes symétriques finis", Annales Scientifiques de l'École Normale Supérieure. Troisième Série 65, pp. 239–276 (1948)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]