fbpx
Wikipedia

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 and (sometimes known as the bottom and top[1]), there exist two variations of the wreath product: the unrestricted wreath product and the restricted wreath product . The general form, denoted by or respectively, requires that acts on some set ; when unspecified, usually (a regular wreath product), though a different is sometimes implied. The two variations coincide when , , and are all finite. Either variation is also denoted as (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   be a group and let   be a group acting on a set   (on the left). The direct product   of   with itself indexed by   is the set of sequences   in   indexed by  , with a group operation given by pointwise multiplication. The action of   on   can be extended to an action on   by reindexing, namely by defining

 

for all   and all  .

Then the unrestricted wreath product   of   by   is the semidirect product   with the action of   on   given above. The subgroup   of   is called the base of the wreath product.

The restricted wreath product   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   with finitely-many non-identity entries.

In the most common case,  , and   acts on itself by left multiplication. In this case, the unrestricted and restricted wreath product may be denoted by   and   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, AH 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 = Sn is the symmetric group of degree n it is common in the literature to assume that Ω = {1,...,n} (with the natural action of Sn) and then omit Ω from the notation. That is, ASn commonly denotes A{1,...,n}Sn instead of the regular wreath product ASnSn. 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 AH 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
     
  • 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
     

Examples

The base of this wreath product is the n-fold direct product
mn = ℤm × ... × ℤm
of copies of ℤm where the action φ : Sn → Aut(ℤmn) of the symmetric group Sn of degree n is given by
φ(σ)(α1,..., αn) := (ασ(1),..., ασ(n)).[5]
The action of Sn on {1,...,n} is as above. Since the symmetric group S2 of degree 2 is isomorphic to ℤ2 the hyperoctahedral group is a special case of a generalized symmetric group.[6]
  • The smallest non-trivial wreath product is ℤ2≀ℤ2, which is the two-dimensional case of the above hyperoctahedral group. It is the symmetry group of the square, also called Dih4, 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 Spn. Then P is isomorphic to the iterated regular wreath product Wn = ℤp ≀ ℤp≀...≀ℤp of n copies of ℤp. Here W1 := ℤp and Wk := Wk−1≀ℤp for all k ≥ 2.[7][8] For instance, the Sylow 2-subgroup of S4 is the above ℤ2≀ℤ2 group.
  • The Rubik's Cube group is a subgroup of index 12 in the product of wreath products, (ℤ3S8) × (ℤ2S12), 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 (S3S3) ≀ S2, where the factors are the permutation of rows/columns within a 3-row or 3-column band or stack (S3), the permutation of the bands/stacks themselves (S3) and the transposition, which interchanges the bands and stacks (S2). Here, the index sets Ω are the set of bands (resp. stacks) (|Ω| = 3) and the set {bands, stacks} (|Ω| = 2). Accordingly, |S3S3| = |S3|3|S3| = (3!)4 and |(S3S3) ≀ S2| = |S3S3|2|S2| = (3!)8 × 2.
  • Wreath products arise naturally in the symmetry group of complete rooted trees and their graphs. For example, the repeated (iterated) wreath product S2S2...S2 is the automorphism group of a complete binary tree.

References

  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, 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)
  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)

External links

wreath, product, group, theory, wreath, product, special, combination, groups, based, semidirect, product, formed, action, group, many, copies, another, group, somewhat, analogous, exponentiation, used, classification, permutation, groups, also, provide, const. 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 displaystyle A and H displaystyle H sometimes known as the bottom and top 1 there exist two variations of the wreath product the unrestricted wreath product A Wr H displaystyle A text Wr H and the restricted wreath product A wr H displaystyle A text wr H The general form denoted by A Wr W H displaystyle A text Wr Omega H or A wr W H displaystyle A text wr Omega H respectively requires that H displaystyle H acts on some set W displaystyle Omega when unspecified usually W H displaystyle Omega H a regular wreath product though a different W displaystyle Omega is sometimes implied The two variations coincide when A displaystyle A H displaystyle H and W displaystyle Omega are all finite Either variation is also denoted as A H 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 Contents 1 Definition 2 Notation and conventions 3 Properties 3 1 Agreement of unrestricted and restricted wreath product on finite W 3 2 Subgroup 3 3 Cardinality 3 4 Universal embedding theorem 4 Canonical actions of wreath products 5 Examples 6 References 7 External linksDefinition EditLet A displaystyle A be a group and let H displaystyle H be a group acting on a set W displaystyle Omega on the left The direct product A W displaystyle A Omega of A displaystyle A with itself indexed by W displaystyle Omega is the set of sequences a a w w W displaystyle overline a a omega omega in Omega in A displaystyle A indexed by W displaystyle Omega with a group operation given by pointwise multiplication The action of H displaystyle H on W displaystyle Omega can be extended to an action on A W displaystyle A Omega by reindexing namely by defining h a w w W a h 1 w w W displaystyle h cdot a omega omega in Omega a h 1 cdot omega omega in Omega for all h H displaystyle h in H and all a w w W A W displaystyle a omega omega in Omega in A Omega Then the unrestricted wreath product A Wr W H displaystyle A text Wr Omega H of A displaystyle A by H displaystyle H is the semidirect product A W H displaystyle A Omega rtimes H with the action of H displaystyle H on A W displaystyle A Omega given above The subgroup A W displaystyle A Omega of A W H displaystyle A Omega rtimes H is called the base of the wreath product The restricted wreath product A wr W H displaystyle 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 displaystyle A with finitely many non identity entries In the most common case W H displaystyle Omega H and H displaystyle H acts on itself by left multiplication In this case the unrestricted and restricted wreath product may be denoted by A Wr H displaystyle A text Wr H and A wr H displaystyle A text wr H respectively This is called the regular wreath product Notation and conventions EditThe structure of the wreath product of A by H depends on the H set W and in case W 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 WH may stand for the unrestricted wreath product A WrW H or the restricted wreath product A wrW 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 W may be omitted from the notation even if W H In the special case that H Sn is the symmetric group of degree n it is common in the literature to assume that W 1 n with the natural action of Sn and then omit W from the notation That is A Sn commonly denotes A 1 n Sn instead of the regular wreath product A SnSn 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 EditAgreement of unrestricted and restricted wreath product on finite W Edit Since the finite direct product is the same as the finite direct sum of groups it follows that the unrestricted A WrW H and the restricted wreath product A wrW H agree if the H set W is finite In particular this is true when W H is finite Subgroup Edit A wrW H is always a subgroup of A WrW H Cardinality Edit If A H and W are finite then A WH A W H 2 dd Universal embedding theorem Edit Main article 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 EditIf the group A acts on a set L then there are two canonical ways to construct sets from W and L on which A WrW H and therefore also A wrW H can act The imprimitive wreath product action on L W If aw h A WrW H and l w L W then a w h l w a h w l h w displaystyle a omega h cdot lambda omega a h omega lambda h omega dd The primitive wreath product action on LW An element in LW is a sequence lw indexed by the H set W Given an element aw h A WrW H its operation on lw LW is given by a w h l w a h 1 w l h 1 w displaystyle a omega h cdot lambda omega a h 1 omega lambda h 1 omega dd Examples EditThe Lamplighter group is the restricted wreath product ℤ2 ℤ ℤm Sn Generalized symmetric group The base of this wreath product is the n fold direct productℤmn ℤm ℤm dd of copies of ℤm where the action f Sn Aut ℤmn of the symmetric group Sn of degree n is given byf s a1 an as 1 as n 5 dd S2 Sn Hyperoctahedral group The action of Sn on 1 n is as above Since the symmetric group S2 of degree 2 is isomorphic to ℤ2 the hyperoctahedral group is a special case of a generalized symmetric group 6 The smallest non trivial wreath product is ℤ2 ℤ2 which is the two dimensional case of the above hyperoctahedral group It is the symmetry group of the square also called Dih4 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 Spn Then P is isomorphic to the iterated regular wreath product Wn ℤp ℤp ℤp of n copies of ℤp Here W1 ℤp and Wk Wk 1 ℤp for all k 2 7 8 For instance the Sylow 2 subgroup of S4 is the above ℤ2 ℤ2 group The Rubik s Cube group is a subgroup of index 12 in the product of wreath products ℤ3 S8 ℤ2 S12 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 S3 S3 S2 where the factors are the permutation of rows columns within a 3 row or 3 column band or stack S3 the permutation of the bands stacks themselves S3 and the transposition which interchanges the bands and stacks S2 Here the index sets W are the set of bands resp stacks W 3 and the set bands stacks W 2 Accordingly S3 S3 S3 3 S3 3 4 and S3 S3 S2 S3 S3 2 S2 3 8 2 Wreath products arise naturally in the symmetry group of complete rooted trees and their graphs For example the repeated iterated wreath product S2 S2 S2 is the automorphism group of a complete binary tree References Edit Bhattacharjee Meenaxi Macpherson Dugald Moller Rognvaldur G Neumann Peter M 1998 Wreath products Notes on Infinite Permutation Groups Lecture Notes in Mathematics 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 probleme 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 symetriques finis Annales Scientifiques de l Ecole Normale Superieure Troisieme Serie 65 pp 239 276 1948 External links EditWreath product in Encyclopedia of Mathematics Some Applications of the Wreath Product Construction Archived 21 February 2014 at the Wayback Machine Retrieved from https en wikipedia org w index php title Wreath product amp oldid 1119501730, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.