Namespaces
Variants
Actions

Difference between revisions of "Wreath product"

From Encyclopedia of Mathematics
Jump to: navigation, search
(LaTeX part)
m (tex done)
 
Line 1: Line 1:
{{TEX|part}}
+
{{TEX|done}}
 +
 
 
The wreath product of two groups $A$ and $B$ is constructed in the following way. Let $A^B$ be the set of all functions defined on $B$ with values in $A$. With respect to [[pointwise multiplication]], this set is a [[group]] which is the complete direct product of $|B|$ copies of $A$ ($|B|$ denotes the [[cardinality]] of $B$); $B$ acts on $A^B$ as a group of automorphisms in the following way: if $b \in B$, $\phi \in A^B$, then $\phi^b(x) = \phi(xb^{-1})$ for $x \in B$. With respect to this operation, one can form the [[semi-direct product]] $W$ of $B$ and $A^B$, that is, the set of all pairs $(b,\phi)$, where $b \in B$, $\phi \in A^B$, with multiplication operation given by
 
The wreath product of two groups $A$ and $B$ is constructed in the following way. Let $A^B$ be the set of all functions defined on $B$ with values in $A$. With respect to [[pointwise multiplication]], this set is a [[group]] which is the complete direct product of $|B|$ copies of $A$ ($|B|$ denotes the [[cardinality]] of $B$); $B$ acts on $A^B$ as a group of automorphisms in the following way: if $b \in B$, $\phi \in A^B$, then $\phi^b(x) = \phi(xb^{-1})$ for $x \in B$. With respect to this operation, one can form the [[semi-direct product]] $W$ of $B$ and $A^B$, that is, the set of all pairs $(b,\phi)$, where $b \in B$, $\phi \in A^B$, with multiplication operation given by
 
$$
 
$$
Line 17: Line 18:
  
 
====Comments====
 
====Comments====
More generally, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816035.png" /> be a group and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816036.png" /> a [[Permutation group|permutation group]], i.e. a group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816037.png" /> acting on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816038.png" /> (not transitively or faithfully). Consider the set all pairs
+
More generally, let $  G $
 +
be a group and $  H $
 +
a [[Permutation group|permutation group]], i.e. a group $  H $
 +
acting on a set $  X $(
 +
not transitively or faithfully). Consider the set all pairs
 +
 
 +
$$
 +
\{ {( h,\  f \  )} : {f : \  X \rightarrow G ,\  h \in H} \}
 +
.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816039.png" /></td> </tr></table>
 
  
 
A product on this set is defined by
 
A product on this set is defined by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816040.png" /></td> </tr></table>
+
$$
 +
(h _{1} ,\  f _{1} )(h _{2} ,\  f _{2} ) \  = \
 +
( h _{1} h _{2} ,\  f _{1} ^ {\  h _ 2} f _{2} ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816041.png" /> (and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816042.png" />). This defines a group structure and the resulting group is denoted <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816043.png" /> and is called the (complete) wreath product of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816044.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816045.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816046.png" /> is infinite, then by taking only mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816047.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816048.png" />, the unit element in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816049.png" />, for almost-all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816050.png" /> one obtains the (restricted) wreath product.
 
  
In the special case where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816051.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816052.png" /> acting on itself by the right regular permutation representation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816053.png" />, one obtains the wreath products described above. These are often called the standard wreath product or the regular wreath product.
+
where $  f _{1} ^ {\  h _ 2} (x) = f _{1} (h _{2} (x)) $(
 +
and  $  (ff ^ {\  \prime} )(x) = f(x) f ^ {\  \prime} (x) $).  
 +
This defines a group structure and the resulting group is denoted  $  G \  ? \  H $
 +
and is called the (complete) wreath product of  $  G $
 +
with $  H $.  
 +
If  $  X $
 +
is infinite, then by taking only mappings  $  f: \  X \rightarrow G $
 +
such that  $  f(x) = e $,
 +
the unit element in  $  G $,  
 +
for almost-all  $  x $
 +
one obtains the (restricted) wreath product.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816054.png" /> is also a permutation group acting on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816055.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816056.png" /> can be seen as a permutation group acting on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816057.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816058.png" /> acting as
+
In the special case where  $  X = H $
 +
with  $  H $
 +
acting on itself by the right regular permutation representation  $  x ^{h} = h(x) = xh ^{-1} $,
 +
one obtains the wreath products described above. These are often called the standard wreath product or the regular wreath product.
 +
 
 +
If  $  G $
 +
is also a permutation group acting on a set $  Y $,  
 +
then $  G \  ? \  H $
 +
can be seen as a permutation group acting on the set $  Y \times X $
 +
with $  (h,\  f \  ) $
 +
acting as
 +
 
 +
$$
 +
(h,\  f \  )(y,\  x) \  = \  ( f(x)(y),\  h(x)) .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816059.png" /></td> </tr></table>
 
  
Many natural subgroups of the symmetric groups, such as centralizers of elements, normalizers of certain subgroups, Sylow subgroups, are direct products of wreath products. For instance, the normalizer of the [[Young subgroup|Young subgroup]], <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816060.png" /> is the wreath product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816061.png" />. The wreath product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816062.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816063.png" /> an arbitrary group has been called the complete monomial group of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816065.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816066.png" />, or the symmetry of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816068.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816069.png" />. The wreath products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816070.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816071.png" /> are sometimes termed generalized symmetric groups and generalized alternating groups; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816072.png" /> is a hyper-octahedral group.
+
Many natural subgroups of the symmetric groups, such as centralizers of elements, normalizers of certain subgroups, Sylow subgroups, are direct products of wreath products. For instance, the normalizer of the [[Young subgroup|Young subgroup]], $  S _{m} \times \dots \times S _{m} \subset S _{nm} $
 +
is the wreath product $  S _{m} \  ? \  S _{n} $.  
 +
The wreath product $  G \  ? \  S _{n} $
 +
for $  G $
 +
an arbitrary group has been called the complete monomial group of degree $  n $
 +
of $  G $,  
 +
or the symmetry of degree $  n $
 +
of $  G $.  
 +
The wreath products $  \mathbf Z / (m) \  ? \  S _{n} $
 +
and $  \mathbf Z / (m) \  ? \  A _{n} $
 +
are sometimes termed generalized symmetric groups and generalized alternating groups; $  \mathbf Z / (2) \  ? \  S _{n} $
 +
is a hyper-octahedral group.
  
A more general standard product is the twisted wreath product, which incorporates an action of a subgroup <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816073.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816074.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816075.png" />, cf. [[#References|[a4]]].
+
A more general standard product is the twisted wreath product, which incorporates an action of a subgroup $  H _{1} $
 +
of $  H $
 +
on $  G $,  
 +
cf. [[#References|[a4]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B. Huppert,  "Endliche Gruppen" , '''1''' , Springer  (1967)  pp. §15</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Hall jr.,  "The theory of groups" , Macmillan  (1959)  pp. 81ff</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Kerber,  "Representations of permutation groups" , '''I-II''' , Springer  (1971–1975)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M. Suzuki,  "Group theory" , '''1''' , Springer  (1982)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B. Huppert,  "Endliche Gruppen" , '''1''' , Springer  (1967)  pp. §15</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Hall jr.,  "The theory of groups" , Macmillan  (1959)  pp. 81ff</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Kerber,  "Representations of permutation groups" , '''I-II''' , Springer  (1971–1975)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M. Suzuki,  "Group theory" , '''1''' , Springer  (1982)</TD></TR></table>
  
The wreath product of semi-groups is a construction assigning to two semi-groups a third in the following way: The wreath product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816076.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816077.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816078.png" /> has as underlying set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816079.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816080.png" /> is the [[Semi-group|semi-group]] of all mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816081.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816082.png" /> under [[pointwise multiplication]], and the operation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816083.png" /> is given by the formula: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816084.png" />, where the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816085.png" /> is defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816086.png" />. The wreath product of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816087.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816088.png" /> is written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816089.png" />. This is the standard wreath product; for other definitions and generalizations of the wreath product see [[#References|[1]]], [[#References|[2]]], [[#References|[4]]]–[[#References|[7]]].
+
The wreath product of semi-groups is a construction assigning to two semi-groups a third in the following way: The wreath product $  W $
 +
of $  A $
 +
and $  B $
 +
has as underlying set $  F ( B ,\  A ) \times B $,  
 +
where $  F ( B ,\  A ) $
 +
is the [[Semi-group|semi-group]] of all mappings from $  B $
 +
into $  A $
 +
under [[pointwise multiplication]], and the operation on $  W $
 +
is given by the formula: $  ( f ,\  b ) ( g ,\  c ) = ( f ^ {\  b _ g} ,\  b c ) $,  
 +
where the mapping $  b _{g} $
 +
is defined by $  b _{g} (y) = g ( y b ) $.  
 +
The wreath product of $  A $
 +
and $  B $
 +
is written as $  A \  \mathop{\rm wr}\nolimits \  B $.  
 +
This is the standard wreath product; for other definitions and generalizations of the wreath product see [[#References|[1]]], [[#References|[2]]], [[#References|[4]]]–[[#References|[7]]].
  
The wreath product of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816091.png" /> contains the [[Direct product|direct product]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816092.png" /> as a sub-semi-group. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816093.png" /> has an identity, then any ideal extension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816094.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816095.png" /> can be imbedded in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816096.png" /> (see [[#References|[3]]]).
+
The wreath product of $  A $
 +
and $  B $
 +
contains the [[Direct product|direct product]] $  A \times B $
 +
as a sub-semi-group. If $  A $
 +
has an identity, then any ideal extension of $  A $
 +
by $  B $
 +
can be imbedded in $  A \  \mathop{\rm wr}\nolimits \  B $(
 +
see [[#References|[3]]]).
  
The question of when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816097.png" /> inherits various properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816098.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w09816099.png" /> has been investigated mainly for various types of simplicity (see [[Simple semi-group|Simple semi-group]]). Some examples follow. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160100.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160101.png" /> are ideally-simple semi-groups and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160102.png" /> is a semi-group with right cancellation, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160103.png" /> is an ideally-simple semi-group. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160104.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160105.png" /> are completely-simple semi-groups and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160106.png" /> is left-simple, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160107.png" /> is completely simple [[#References|[3]]]. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160108.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160109.png" /> are semi-groups with completely-simple kernels (see [[Kernel of a semi-group|Kernel of a semi-group]]), then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160110.png" /> has a completely-simple kernel [[#References|[4]]], and, moreover, the kernel of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160111.png" /> is equal to the square of the wreath product of the kernels [[#References|[7]]]. If one of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160112.png" /> is regular and the other is left-simple, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160113.png" /> is regular [[#References|[6]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160114.png" />; then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160115.png" /> is an inverse semi-group (cf. [[Inversion semi-group|Inversion semi-group]]) (or [[Right group|right group]]) if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160116.png" /> is an inverse semi-group (or right group, respectively) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160117.png" /> is a group [[#References|[6]]].
+
The question of when $  A \  \mathop{\rm wr}\nolimits \  B $
 +
inherits various properties of $  A $
 +
and $  B $
 +
has been investigated mainly for various types of simplicity (see [[Simple semi-group|Simple semi-group]]). Some examples follow. If $  A $
 +
and $  B $
 +
are ideally-simple semi-groups and $  B $
 +
is a semi-group with right cancellation, then $  A \  \mathop{\rm wr}\nolimits \  B $
 +
is an ideally-simple semi-group. If $  A $
 +
and $  B $
 +
are completely-simple semi-groups and $  A $
 +
is left-simple, then $  A \  \mathop{\rm wr}\nolimits \  B $
 +
is completely simple [[#References|[3]]]. If $  A $
 +
and $  B $
 +
are semi-groups with completely-simple kernels (see [[Kernel of a semi-group|Kernel of a semi-group]]), then $  A \  \mathop{\rm wr}\nolimits \  B $
 +
has a completely-simple kernel [[#References|[4]]], and, moreover, the kernel of $  A \  \mathop{\rm wr}\nolimits \  B $
 +
is equal to the square of the wreath product of the kernels [[#References|[7]]]. If one of $  A ,\  B $
 +
is regular and the other is left-simple, then $  A \  \mathop{\rm wr}\nolimits \  B $
 +
is regular [[#References|[6]]]. Let $  | A | > 1 $;  
 +
then $  A \  \mathop{\rm wr}\nolimits \  B $
 +
is an inverse semi-group (cf. [[Inversion semi-group|Inversion semi-group]]) (or [[Right group|right group]]) if and only if $  A $
 +
is an inverse semi-group (or right group, respectively) and $  B $
 +
is a group [[#References|[6]]].
  
Wreath products can be used to give a compact proof of Evan's theorem that every countable semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160118.png" /> can be imbedded in a semi-group with two generators [[#References|[1]]], and in the case when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w098/w098160/w098160119.png" /> is finitely generated and periodic it can be imbedded in a periodic semi-group with two generators.
+
Wreath products can be used to give a compact proof of Evan's theorem that every countable semi-group $  S $
 +
can be imbedded in a semi-group with two generators [[#References|[1]]], and in the case when $  S $
 +
is finitely generated and periodic it can be imbedded in a periodic semi-group with two generators.
  
 
The wreath product and its generalizations play an important role in the algebraic theory of automata. For example, they can be used to prove the theorem on the decomposition of every finite semi-group automaton into a step-by-step combination of flip-flops and simple group automata ([[#References|[2]]], see also [[#References|[5]]]), the so-called Krohn–Rhodes theorem.
 
The wreath product and its generalizations play an important role in the algebraic theory of automata. For example, they can be used to prove the theorem on the decomposition of every finite semi-group automaton into a step-by-step combination of flip-flops and simple group automata ([[#References|[2]]], see also [[#References|[5]]]), the so-called Krohn–Rhodes theorem.

Latest revision as of 22:29, 27 January 2020


The wreath product of two groups $A$ and $B$ is constructed in the following way. Let $A^B$ be the set of all functions defined on $B$ with values in $A$. With respect to pointwise multiplication, this set is a group which is the complete direct product of $|B|$ copies of $A$ ($|B|$ denotes the cardinality of $B$); $B$ acts on $A^B$ as a group of automorphisms in the following way: if $b \in B$, $\phi \in A^B$, then $\phi^b(x) = \phi(xb^{-1})$ for $x \in B$. With respect to this operation, one can form the semi-direct product $W$ of $B$ and $A^B$, that is, the set of all pairs $(b,\phi)$, where $b \in B$, $\phi \in A^B$, with multiplication operation given by $$ (b,\phi) (c,\psi) = (bc, \phi^c \psi) \ . $$

The resulting group $W$ is called the Cartesian (or complete) wreath product of $A$ and $B$, and is denoted by $A \mathop{Wr} B$ (or $A \bar{\wr} B$, a denotation of Ph. Hall). If instead of $A^B$ one takes the smaller group $A^{(B)}$ consisting of all functions with finite support, that is, functions taking only non-identity values on a finite set of points, then one obtains a subgroup of $W$ called the wreath product (direct wreath product, discrete wreath product) of $A$ and $B$; it is denoted by $A \mathop{wr} B$ (or $A \wr B$). Both wreath products are widely used for constructing various examples of groups.

References

[1] H. Neumann, "Varieties of groups" , Springer (1967)
[2a] M. Krasner, L. Kaloujnine, "Produit complet des groupes de permutations et problème d'extension de groupes I" Acta Sci. Math. Szeged , 13 (1950) pp. 208–230
[2b] M. Krasner, L. Kaloujnine, "Produit complet des groupes de permutations et problème d'extension de groupes II" Acta Sci. Math. Szeged , 14 (1951) pp. 39–66; 69–82


Comments

More generally, let $ G $ be a group and $ H $ a permutation group, i.e. a group $ H $ acting on a set $ X $( not transitively or faithfully). Consider the set all pairs

$$ \{ {( h,\ f \ )} : {f : \ X \rightarrow G ,\ h \in H} \} . $$


A product on this set is defined by

$$ (h _{1} ,\ f _{1} )(h _{2} ,\ f _{2} ) \ = \ ( h _{1} h _{2} ,\ f _{1} ^ {\ h _ 2} f _{2} ) , $$


where $ f _{1} ^ {\ h _ 2} (x) = f _{1} (h _{2} (x)) $( and $ (ff ^ {\ \prime} )(x) = f(x) f ^ {\ \prime} (x) $). This defines a group structure and the resulting group is denoted $ G \ ? \ H $ and is called the (complete) wreath product of $ G $ with $ H $. If $ X $ is infinite, then by taking only mappings $ f: \ X \rightarrow G $ such that $ f(x) = e $, the unit element in $ G $, for almost-all $ x $ one obtains the (restricted) wreath product.

In the special case where $ X = H $ with $ H $ acting on itself by the right regular permutation representation $ x ^{h} = h(x) = xh ^{-1} $, one obtains the wreath products described above. These are often called the standard wreath product or the regular wreath product.

If $ G $ is also a permutation group acting on a set $ Y $, then $ G \ ? \ H $ can be seen as a permutation group acting on the set $ Y \times X $ with $ (h,\ f \ ) $ acting as

$$ (h,\ f \ )(y,\ x) \ = \ ( f(x)(y),\ h(x)) . $$


Many natural subgroups of the symmetric groups, such as centralizers of elements, normalizers of certain subgroups, Sylow subgroups, are direct products of wreath products. For instance, the normalizer of the Young subgroup, $ S _{m} \times \dots \times S _{m} \subset S _{nm} $ is the wreath product $ S _{m} \ ? \ S _{n} $. The wreath product $ G \ ? \ S _{n} $ for $ G $ an arbitrary group has been called the complete monomial group of degree $ n $ of $ G $, or the symmetry of degree $ n $ of $ G $. The wreath products $ \mathbf Z / (m) \ ? \ S _{n} $ and $ \mathbf Z / (m) \ ? \ A _{n} $ are sometimes termed generalized symmetric groups and generalized alternating groups; $ \mathbf Z / (2) \ ? \ S _{n} $ is a hyper-octahedral group.

A more general standard product is the twisted wreath product, which incorporates an action of a subgroup $ H _{1} $ of $ H $ on $ G $, cf. [a4].

References

[a1] B. Huppert, "Endliche Gruppen" , 1 , Springer (1967) pp. §15
[a2] M. Hall jr., "The theory of groups" , Macmillan (1959) pp. 81ff
[a3] A. Kerber, "Representations of permutation groups" , I-II , Springer (1971–1975)
[a4] M. Suzuki, "Group theory" , 1 , Springer (1982)

The wreath product of semi-groups is a construction assigning to two semi-groups a third in the following way: The wreath product $ W $ of $ A $ and $ B $ has as underlying set $ F ( B ,\ A ) \times B $, where $ F ( B ,\ A ) $ is the semi-group of all mappings from $ B $ into $ A $ under pointwise multiplication, and the operation on $ W $ is given by the formula: $ ( f ,\ b ) ( g ,\ c ) = ( f ^ {\ b _ g} ,\ b c ) $, where the mapping $ b _{g} $ is defined by $ b _{g} (y) = g ( y b ) $. The wreath product of $ A $ and $ B $ is written as $ A \ \mathop{\rm wr}\nolimits \ B $. This is the standard wreath product; for other definitions and generalizations of the wreath product see [1], [2], [4][7].

The wreath product of $ A $ and $ B $ contains the direct product $ A \times B $ as a sub-semi-group. If $ A $ has an identity, then any ideal extension of $ A $ by $ B $ can be imbedded in $ A \ \mathop{\rm wr}\nolimits \ B $( see [3]).

The question of when $ A \ \mathop{\rm wr}\nolimits \ B $ inherits various properties of $ A $ and $ B $ has been investigated mainly for various types of simplicity (see Simple semi-group). Some examples follow. If $ A $ and $ B $ are ideally-simple semi-groups and $ B $ is a semi-group with right cancellation, then $ A \ \mathop{\rm wr}\nolimits \ B $ is an ideally-simple semi-group. If $ A $ and $ B $ are completely-simple semi-groups and $ A $ is left-simple, then $ A \ \mathop{\rm wr}\nolimits \ B $ is completely simple [3]. If $ A $ and $ B $ are semi-groups with completely-simple kernels (see Kernel of a semi-group), then $ A \ \mathop{\rm wr}\nolimits \ B $ has a completely-simple kernel [4], and, moreover, the kernel of $ A \ \mathop{\rm wr}\nolimits \ B $ is equal to the square of the wreath product of the kernels [7]. If one of $ A ,\ B $ is regular and the other is left-simple, then $ A \ \mathop{\rm wr}\nolimits \ B $ is regular [6]. Let $ | A | > 1 $; then $ A \ \mathop{\rm wr}\nolimits \ B $ is an inverse semi-group (cf. Inversion semi-group) (or right group) if and only if $ A $ is an inverse semi-group (or right group, respectively) and $ B $ is a group [6].

Wreath products can be used to give a compact proof of Evan's theorem that every countable semi-group $ S $ can be imbedded in a semi-group with two generators [1], and in the case when $ S $ is finitely generated and periodic it can be imbedded in a periodic semi-group with two generators.

The wreath product and its generalizations play an important role in the algebraic theory of automata. For example, they can be used to prove the theorem on the decomposition of every finite semi-group automaton into a step-by-step combination of flip-flops and simple group automata ([2], see also [5]), the so-called Krohn–Rhodes theorem.

References

[1] B.H. Neumann, "Embedding theorems for semigroups" J. London Math. Soc. , 35 : 138 (1960) pp. 184–192
[2] K. Krohn, J. Rhodes, "Algebraic theory of machines. I Prime decomposition theorem for finite semigroups and machines" Trans. Amer. Math. Soc. , 116 (1965) pp. 450–464
[3] R.P. Hunter, "Some results on wreath products of semigroups" Bull. Soc. Math. Belgique , 18 : 1 (1966) pp. 3–16
[4] J.D., jr. McKnight, E. Sadowski, "The kernel of the wreath product of semigroups" Semigroup Forum , 4 (1972) pp. 232–236
[5] M.A. Arbib (ed.) , Algebraic theory of machines, languages and semigroups , Acad. Press (1968)
[6] Yu.G. Koshelev, "Wreath products and equations in semigroups" Semigroup Forum , 11 : 1 (1975) pp. 1–13 (In Russian) ((English abstract.))
[7] S. Nakajima, "On the kernel of the wreath product of completely simple semigroups II" , Proc. First Symp. Semigroups (Shimane Univ. Matsue, 1977) , Shimane Univ. Matsue (1977) pp. 84–88

E.A. GolubovL.N. Shevrin

How to Cite This Entry:
Wreath product. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Wreath_product&oldid=35297
This article was adapted from an original article by A.L. Shmel'kin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article