Wreath product

Last updated May 20, 2024

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}$ , 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.

Related Research Articles

In group theory, a branch of mathematics, given a group $G$ under a binary operation ∗, a subset $H$ of $G$ is called a subgroup of $G$ if $H$ also forms a group under the operation ∗. More precisely, $H$ is a subgroup of $G$ if the restriction of ∗ to $H \times H$ is a group operation on $H$ . This is often denoted $H \leq G$ , read as " $H$ is a subgroup of $G$ ".

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group $defined over a finite set of symbols consists of the permutations that can be performed on the symbols. Since there are such permutation operations, the order of the symmetric group is .$

In the mathematical field of group theory, Lagrange's theorem is a theorem that states that for any finite group $G$ , the order of every subgroup of $G$ divides the order of $G$ . The theorem is named after Joseph-Louis Lagrange. The following variant states that for a subgroup $of a finite group, not only is an integer, but its value is the index, defined as the number of left cosets of in .$

<span class="mw-page-title-main">Generating set of a group</span> Abstract algebra concept

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.

In mathematics, more specifically in the field of group theory, a solvable group or soluble group is a group that can be constructed from abelian groups using extensions. Equivalently, a solvable group is a group whose derived series terminates in the trivial subgroup.

In mathematics, a symplectic matrix is a $matrix with real entries that satisfies the condition$

In mathematics, specifically group theory, the index of a subgroup H in a group G is the number of left cosets of H in G, or equivalently, the number of right cosets of H in G. The index is denoted $or or . Because G is the disjoint union of the left cosets and because each left coset has the same size as H, the index is related to the orders of the two groups by the formula$

In mathematics, a generalized permutation matrix is a matrix with the same nonzero pattern as a permutation matrix, i.e. there is exactly one nonzero entry in each row and each column. Unlike a permutation matrix, where the nonzero entry must be 1, in a generalized permutation matrix the nonzero entry can be any nonzero value. An example of a generalized permutation matrix is

In mathematics, the modular group is the projective special linear group $of 2 × 2 matrices with integer coefficients and determinant 1. The matrices A and −A are identified. The modular group acts on the upper-half of the complex plane by fractional linear transformations, and the name "modular group" comes from the relation to moduli spaces and not from modular arithmetic.$

In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from symmetric function theory to quantum chemistry studies of atoms, molecules and solids.

In group theory, a field of mathematics, a double coset is a collection of group elements which are equivalent under the symmetries coming from two subgroups, generalizing the notion of a single coset.

In mathematics, a Young symmetrizer is an element of the group algebra of the symmetric group, constructed in such a way that, for the homomorphism from the group algebra to the endomorphisms of a vector space $obtained from the action of on by permutation of indices, the image of the endomorphism determined by that element corresponds to an irreducible representation of the symmetric group over the complex numbers. A similar construction works over any field, and the resulting representations are called Specht modules . The Young symmetrizer is named after British mathematician Alfred Young.$

In mathematics, the fundamental theorem of Galois theory is a result that describes the structure of certain types of field extensions in relation to groups. It was proved by Évariste Galois in his development of Galois theory.

In mathematics, D₃ (sometimes alternatively denoted by D₆) is the dihedral group of degree 3 and order 6. It equals the symmetric group S₃. It is also the smallest non-abelian group.

Brauer's theorem on induced characters, often known as Brauer's induction theorem, and named after Richard Brauer, is a basic result in the branch of mathematics known as character theory, within representation theory of a finite group.

In mathematics, the Burnside ring of a finite group is an algebraic construction that encodes the different ways the group can act on finite sets. The ideas were introduced by William Burnside at the end of the nineteenth century. The algebraic ring structure is a more recent development, due to Solomon (1967).

In mathematics, especially in the fields of group theory and Lie theory, a central series is a kind of normal series of subgroups or Lie subalgebras, expressing the idea that the commutator is nearly trivial. For groups, the existence of a central series means it is a nilpotent group; for matrix rings, it means that in some basis the ring consists entirely of upper triangular matrices with constant diagonal.

In mathematics, a hyperoctahedral group is an important type of group that can be realized as the group of symmetries of a hypercube or of a cross-polytope. It was named by Alfred Young in 1930. Groups of this type are identified by a parameter $n$ , the dimension of the hypercube.

In mathematics, the O'Nan–Scott theorem is one of the most influential theorems of permutation group theory; the classification of finite simple groups is what makes it so useful. Originally the theorem was about maximal subgroups of the symmetric group. It appeared as an appendix to a paper by Leonard Scott written for The Santa Cruz Conference on Finite Groups in 1979, with a footnote that Michael O'Nan had independently proved the same result. Michael Aschbacher and Scott later gave a corrected version of the statement of the theorem.

The affine symmetric groups are a family of mathematical structures that describe the symmetries of the number line and the regular triangular tiling of the plane, as well as related higher-dimensional objects. In addition to this geometric description, the affine symmetric groups may be defined in other ways: as collections of permutations (rearrangements) of the integers that are periodic in a certain sense, or in purely algebraic terms as a group with certain generators and relations. They are studied in combinatorics and representation theory.

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 .
Some Applications of the Wreath Product Construction. Archived 21 February 2014 at the Wayback Machine

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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]