Wreath product

Algebraic structure → Group theory Group theory
hide Basic notions Subgroup Normal subgroup Quotient group (Semi-)direct product Group homomorphisms kernel image direct sum wreath product simple finite infinite continuous multiplicative additive cyclic abelian dihedral nilpotent solvable action Glossary of group theory List of group theory topics
show Finite groups Classification of finite simple groups cyclic alternating Lie type sporadic Cauchy's theorem Lagrange's theorem Sylow theorems Hall's theorem p-group Elementary abelian group Frobenius group Schur multiplier Symmetric group Sn Klein four-group V Dihedral group Dn Quaternion group Q Dicyclic group Dicn
show Discrete groups Lattices Integers (${\displaystyle \mathbb {Z} }$) Free group Modular groups PSL(2, ${\displaystyle \mathbb {Z} }$) SL(2, ${\displaystyle \mathbb {Z} }$) Arithmetic group Lattice Hyperbolic group
show Topological and Lie groups Solenoid Circle General linear GL(n) Special linear SL(n) Orthogonal O(n) Euclidean E(n) Special orthogonal SO(n) Unitary U(n) Special unitary SU(n) Symplectic Sp(n) G2 F4 E6 E7 E8 Lorentz Poincaré Conformal Diffeomorphism Loop Infinite dimensional Lie group O(∞) SU(∞) Sp(∞)
show Algebraic groups Linear algebraic group Reductive group Abelian variety Elliptic curve
v t

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 variations of the wreath product: the unrestricted wreath product A Wr H and the restricted wreath product A wr H. The general form, denoted by A Wr_Ω H or A wr_Ω H respectively, uses a set Ω with an H-action; when unspecified, usually Ω = H (a regular wreath product), though a different Ω is sometimes implied. The two variations coincide when A, H, and Ω are all finite. Either variation is also denoted as ${\displaystyle A\wr H}$ (with \wr for the latex symbol) or A ≀ H (Unicode U+2240).

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

Definition[]

Let A and H be groups and Ω a set with H acting on it (from the left). Let K be the direct product

${\displaystyle K=\prod _{\omega \in \Omega }A_{\omega }}$

of copies of A_ω := A indexed by the set Ω. The elements of K can be seen as arbitrary sequences (a_ω) of elements of A indexed by Ω with component-wise multiplication. Then the action of H on Ω extends in a natural way to an action of H on the group K by

${\displaystyle h(a_{\omega }):=(a_{h^{-1}\omega }).}$

Then the unrestricted wreath product A Wr_Ω H of A by H is the semidirect product K ⋊ H. The subgroup K of A Wr_Ω H is called the base of the wreath product.

The restricted wreath product A wr_Ω H is constructed in the same way as the unrestricted wreath product except that one uses the direct sum

${\displaystyle K=\bigoplus _{\omega \in \Omega }A_{\omega }}$

as the base of the wreath product. In this case the elements of K are sequences (a_ω) of elements in A indexed by Ω of which all but finitely many a_ω are the identity element of A.

In the most common case, one takes Ω := H, where H acts in a natural way on itself by left multiplication. In this case, the unrestricted and restricted wreath product may be denoted by A Wr H and A 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≀_SnS_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 the H-set Ω is finite. In particular this is true when Ω = 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

  ${\displaystyle ((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

  ${\displaystyle ((a_{\omega }),h)\cdot (\lambda _{\omega }):=(a_{h^{-1}\omega }\lambda _{h^{-1}\omega }).}$

Examples[]

• The Lamplighter group is the restricted wreath product ℤ₂≀ℤ.
• ℤ_m≀S_n (Generalized symmetric group).

The base of this wreath product is the n-fold direct product

ℤ_mⁿ = ℤ_m × ... × ℤ_m

of copies of ℤ_m where the action φ : S_n → Aut(ℤ_mⁿ) of the symmetric group S_n of degree n is given by

φ(σ)(α₁,..., α_n) := (α_σ(1),..., α_σ(n)).^[5]

• S₂≀S_n (Hyperoctahedral group).

The action of S_n on {1,...,n} is as above. Since the symmetric group S₂ of degree 2 is isomorphic to ℤ₂ the hyperoctahedral group is a special case of a generalized symmetric group.^[6]

• The smallest non-trivial wreath product is ℤ₂≀ℤ₂, which is the two-dimensional case of the above hyperoctahedral group. It is the symmetry group of the square, also called Dih₄, the dihedral group of order 8.
• Let p be a prime and let n≥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 = ℤ_p ≀ ℤ_p≀...≀ℤ_p of n copies of ℤ_p. Here W₁ := ℤ_p and W_k := W_k−1≀ℤ_p for all k ≥ 2.^[7][8] For instance, the Sylow 2-subgroup of S₄ is the above ℤ₂≀ℤ₂ group.

• The Rubik's Cube group is a subgroup of index 12 in the product of wreath products, (ℤ₃≀S₈) × (ℤ₂≀S₁₂), 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 symmetry group 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[]

External links[]

• Wreath product in Encyclopedia of Mathematics.
• Some Applications of the Wreath Product Construction. Archived 21 February 2014 at the Wayback Machine