Editing Wreath product

{{Short description|Topic in group theory}}
{{Group theory sidebar |Basics}}
In [[group theory]], the '''wreath product''' is a special combination of two [[Group (mathematics)|groups]] based on the [[semidirect product]]. It is formed by the [[Action (group theory)|action]] of one group on many copies of another group, somewhat analogous to [[exponentiation]]. Wreath products are used in the classification of [[permutation group]]s and also provide a way of constructing interesting examples of groups.

Given two groups <math>A</math> and <math>H</math> (sometimes known as the ''bottom'' and ''top''<ref>{{Citation|last1=Bhattacharjee|first1=Meenaxi|title=Wreath products|date=1998|url=https://doi.org/10.1007/BFb0092558|work=Notes on Infinite Permutation Groups|pages=67–76|series=Lecture Notes in Mathematics|place=Berlin, Heidelberg|publisher=Springer|language=en|doi=10.1007/bfb0092558|isbn=978-3-540-49813-1|access-date=2021-05-12|last2=Macpherson|first2=Dugald|last3=Möller|first3=Rögnvaldur G.|last4=Neumann|first4=Peter M.|volume=1698 }}</ref>), there exist two variants of the wreath product: the '''unrestricted wreath product''' <math>A \text{ Wr } H</math> and the '''restricted wreath product''' <math>A \text{ wr } H</math>. The general form, denoted by <math>A \text{ Wr}_{\Omega} H</math> or <math>A \text{ wr}_{\Omega} H</math> respectively, requires that <math>H</math> [[Group action (mathematics)|acts]] on some set <math>\Omega</math>; when unspecified, usually <math>\Omega = H</math> (a '''regular wreath product'''), though a different <math>\Omega</math> is sometimes implied. The two variants coincide when <math>A</math>, <math>H</math>, and <math>\Omega</math> are all finite. Either variant is also denoted as <math>A \wr H</math> (with '''\wr''' for the LaTeX symbol) or ''A''&nbsp;≀&nbsp;''H'' ([[Unicode]] U+2240).

The notion generalizes to [[semigroup]]s and, as such, is a central construction in the [[Krohn-Rhodes theory|Krohn–Rhodes structure theory]] of finite semigroups.

== Definition ==

Let <math>A</math> be a group and let <math>H</math> be a group [[Group action (mathematics)|acting]] on a set <math>\Omega</math> (on the left). The [[Direct product of groups|direct product]] <math>A^{\Omega}</math> of <math>A</math> with itself indexed by <math>\Omega</math> is the set of sequences <math>\overline{a} = (a_{\omega})_{\omega \in \Omega}</math> in <math>A</math>, indexed by <math>\Omega</math>, with a group operation given by pointwise multiplication. The action of <math>H</math> on <math>\Omega</math> can be extended to an action on <math>A^{\Omega}</math> by ''reindexing'', namely by defining

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

for all <math>h \in H</math> and all <math>(a_{\omega})_{\omega \in \Omega} \in A^{\Omega}</math>.

Then the '''unrestricted wreath product''' <math>A \text{ Wr}_{\Omega} H</math> of <math>A</math> by <math>H</math> is the [[semidirect product]] <math>A^{\Omega} \rtimes H</math> with the action of <math>H</math> on <math>A^{\Omega}</math> given above. The subgroup <math>A^{\Omega}</math> of <math>A^{\Omega} \rtimes H</math> is called the '''base''' of the wreath product.

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

In the most common case, <math>\Omega = H</math>, and <math>H</math> acts on itself by left multiplication. In this case, the unrestricted and restricted wreath product may be denoted by <math>A \text{ Wr } H</math> and <math>A \text{ wr } H</math> 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''≀<sub>Ω</sub>''H'' may stand for the unrestricted wreath product ''A''&nbsp;Wr<sub>Ω</sub>&nbsp;''H'' or the restricted wreath product ''A''&nbsp;wr<sub>Ω</sub>&nbsp;''H''.
* Similarly, ''A''≀''H'' may stand for the unrestricted regular wreath product ''A''&nbsp;Wr&nbsp;''H'' or the restricted regular wreath product ''A''&nbsp;wr&nbsp;''H''.
* In literature the ''H''-set Ω may be omitted from the notation even if Ω&nbsp;≠&nbsp;''H''.
* In the special case that ''H''&nbsp;=&nbsp;''S''<sub>''n''</sub> is the [[symmetric group]] of degree ''n'' it is common in the literature to assume that Ω&nbsp;=&nbsp;{1,...,''n''} (with the natural action of ''S''<sub>''n''</sub>) and then omit Ω from the notation. That is, ''A''≀''S''<sub>''n''</sub> commonly denotes ''A''≀<sub>{1,...,''n''}</sub>''S''<sub>''n''</sub> instead of the regular wreath product ''A''≀<sub>''S''<sub>''n''</sub></sub>''S''<sub>''n''</sub>. In the first case the base group is the product of ''n'' copies of ''A'', in the latter it is the product of [[Factorial|''n''!]] copies of&nbsp;''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''&nbsp;Wr<sub>Ω</sub>&nbsp;''H'' and the restricted wreath product ''A''&nbsp;wr<sub>Ω</sub>&nbsp;''H'' agree if Ω is finite. In particular this is true when Ω = ''H'' and ''H'' is finite.

=== Subgroup ===
''A''&nbsp;wr<sub>Ω</sub>&nbsp;''H'' is always a [[subgroup]] of ''A''&nbsp;Wr<sub>Ω</sub>&nbsp;''H''.

=== Cardinality ===
If ''A'', ''H'' and Ω are finite, then
:: |''A''≀<sub>Ω</sub>''H''| = |''A''|<sup>|Ω|</sup>|''H''|.<ref>Joseph J. Rotman, An Introduction to the Theory of Groups, p. 172 (1995)</ref>

=== Universal embedding theorem ===
{{Main|Universal embedding theorem}}
''Universal embedding theorem'': If ''G'' is an [[Group extension|extension]] of ''A'' by ''H'', then there exists a subgroup of the unrestricted wreath product ''A''≀''H'' which is isomorphic to ''G''.<ref>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)</ref> This is also known as the ''Krasner–Kaloujnine embedding theorem''. The [[Krohn–Rhodes theorem]] involves what is basically the semigroup equivalent of this.<ref name="Meldrum1995">{{cite book|author=J D P Meldrum|author-link=John D. P. Meldrum|title=Wreath Products of Groups and Semigroups|year=1995|publisher=Longman [UK] / Wiley [US]|isbn=978-0-582-02693-3|page=ix}}</ref>

== 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''&nbsp;Wr<sub>Ω</sub>&nbsp;''H'' (and therefore also ''A''&nbsp;wr<sub>Ω</sub>&nbsp;''H'') can act.

* The '''imprimitive''' wreath product action on Λ&nbsp;×&nbsp;Ω.
*: If {{nowrap|((''a''<sub>''ω''</sub>),''h'') ∈ ''A'' Wr<sub>Ω</sub> ''H''}} and {{nowrap|(''λ'',''ω''&prime;) ∈ Λ × Ω}}, then
*:: <math>((a_\omega), h) \cdot (\lambda,\omega') := (a_{h(\omega')}\lambda, h\omega'). </math>
* The '''primitive''' wreath product action on Λ<sup>Ω</sup>.
*: An element in Λ<sup>Ω</sup> is a sequence (''λ''<sub>''ω''</sub>) indexed by the ''H''-set Ω. Given an element {{nowrap|((''a''<sub>''ω''</sub>), ''h'') ∈ ''A'' Wr<sub>Ω</sub> ''H''}} its operation on (''λ''<sub>''ω''</sub>)&nbsp;∈&nbsp;Λ<sup>Ω</sup> is given by
*:: <math>((a_\omega), h) \cdot (\lambda_\omega) :=  (a_{h^{-1}\omega}\lambda_{h^{-1}\omega}).</math>

== Examples ==

* The [[lamplighter group]] is the restricted wreath product <math>\mathbb{Z}_2 \wr \mathbb{Z}</math>.

* <math>\mathbb{Z}_m \wr S_n</math>(the [[generalized symmetric group]]). The base of this wreath product is the ''n''-fold direct product <math>\mathbb{Z}_m^n = \mathbb{Z}_m ... \mathbb{Z}_m</math>of copies of <math>\mathbb{Z}_m</math> where the action <math>\phi:S_n \to \text{Aut}(\mathbb{Z}_m^n)</math> of the [[symmetric group]] ''S''<sub>''n''</sub> of degree ''n'' is given by ''φ''(''σ'')(α<sub>1</sub>,..., ''α''<sub>''n''</sub>) := (''α''<sub>''σ''(1)</sub>,..., ''α''<sub>''σ''(''n'')</sub>).<ref>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</ref>

* <math>S_2 \wr S_n</math>(the [[hyperoctahedral group]]).
* The action of ''S''<sub>''n''</sub> on {1,...,''n''} is as above. Since the symmetric group ''S''<sub>2</sub> of degree 2 is [[Group isomorphism|isomorphic]] to <math>\mathbb{Z}_2</math> the hyperoctahedral group is a special case of a generalized symmetric group.<ref>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.</ref>

* The smallest non-trivial wreath product is <math>\mathbb{Z}_2 \wr \mathbb{Z}_2</math>, which is the two-dimensional case of the above hyperoctahedral group. It is the symmetry group of the square, also called ''D''<sub>4</sub>, the [[dihedral group]] of order 8.
* Let ''p'' be a [[Prime number|prime]] and let <math>n \geq 1</math>. Let ''P'' be a [[Sylow theorems|Sylow ''p''-subgroup]] of the symmetric group ''S''<sub>''p''<sup>''n''</sup></sub>. Then ''P'' is [[Group isomorphism|isomorphic]] to the iterated regular wreath product <math>W_n = \mathbb{Z}_p \wr ... \wr \mathbb{Z}_p</math> of ''n'' copies of <math>\mathbb{Z}_p</math>. Here <math>W_1:=\mathbb{Z}_p</math> and <math>W_k:=W_{k - 1} \wr \mathbb{Z}_p</math> for all <math>k \geq 2</math>.<ref>Joseph J. Rotman, An Introduction to the Theory of Groups, p. 176 (1995)</ref><ref>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)</ref> For instance, the Sylow 2-subgroup of S<sub>4</sub> is the above <math>\mathbb{Z}_2 \wr \mathbb{Z}_2</math> group.

* The [[Rubik's Cube group]] is a normal subgroup of index 12 in the product of wreath products, <math>(\mathbb{Z}_3 \wr S_8) \times (\mathbb{Z}_2 \wr S_{12})</math>, the factors corresponding to the symmetries of the 8 corners and 12 edges.

* The [[Mathematics of Sudoku#The sudoku symmetry group|Sudoku validity-preserving transformations (VPT) group]] contains the double wreath product (''S''<sub>3</sub> ≀ ''S''<sub>3</sub>) ≀ ''S''<sub>2</sub>, where the factors are the permutation of rows/columns within a 3-row or 3-column ''band'' or ''stack'' (''S''<sub>3</sub>), the permutation of the bands/stacks themselves (''S''<sub>3</sub>) and the transposition, which interchanges the bands and stacks (''S''<sub>2</sub>). Here, the index sets ''Ω'' are the set of bands (resp. stacks) (|''Ω''| = 3) and the set {bands, stacks} (|''Ω''| = 2). Accordingly, |''S''<sub>3</sub> ≀ ''S''<sub>3</sub>| = |''S''<sub>3</sub>|<sup>3</sup>|''S''<sub>3</sub>| = (3!)<sup>4</sup> and |(''S''<sub>3</sub> ≀ ''S''<sub>3</sub>) ≀ ''S''<sub>2</sub>| = |''S''<sub>3</sub> ≀ ''S''<sub>3</sub>|<sup>2</sup>|''S''<sub>2</sub>| = (3!)<sup>8</sup> × 2.

*Wreath products arise naturally in the symmetries of complete rooted [[Tree (data structure)|trees]] and their [[Graph (discrete mathematics)|graphs]]. For example, the repeated (iterated) wreath product ''S''<sub>2</sub> ≀ ''S''<sub>2</sub> ≀ ''...'' ≀ ''S''<sub>2</sub> is the automorphism group of a complete [[binary tree]].

== References ==

{{Reflist}}

== External links ==
* [http://www.encyclopediaofmath.org/index.php?title=Wreath_product&oldid=35297 Wreath product] in ''[[Encyclopedia of Mathematics]]''. 
* Charles Wells, [https://abstractmath.org/Papers/SAWPCWC.pdf "Some applications of the wreath product construction"], revised.

[[Category:Group products]]
[[Category:Permutation groups]]
[[Category:Binary operations]]