 SubgroupLattice - Maple Help

Home : Support : Online Help : Mathematics : Group Theory : SubgroupLattice

GroupTheory

 SubgroupLattice
 construct the lattice of subgroups of a group Calling Sequence SubgroupLattice(G) convert(L, out) SubgroupLattice(G, output = out) Parameters

 G - a group data structure L - the result returned by the SubgroupLattice command out - one of the keywords list, maximalsubgroups, conjugacyclasses, layers, or graph (possibly with indices described below) Description

 • The subgroups of a group form a lattice under inclusion. The SubgroupLattice command computes this lattice and returns a data structure that can be interrogated about some of its properties.
 • The subgroup lattice displays the group G that was its input, the number of conjugacy classes of subgroups (since the subgroups arise from the computation in conjugacy classes), and the total number of subgroups.
 • All of the ways to access the information contained in the subgroup lattice L use the convert command as $\mathrm{convert}\left(L,\mathrm{out}\right)$, for various values of out. (These are special conversions that are only valid for subgroup lattice data structures, not for general Maple objects.)  Alternatively, if you need only one of the types of output, you can bypass using the convert command by using the corresponding output = out option.
 – convert(L, 'list') : return a list of subgroups
 This returns a list of all subgroups. All subgroups have G as their supergroup.
 – convert(L, 'maximalsubgroups') : return a list of maximal subgroups
 This is similar to convert(L, 'list'), but it returns only those subgroups that are maximal subgroups.
 – convert(L, 'conjugacyclasses') : return a list of subgroups, grouped by conjugacy class
 This returns a list of lists of subgroups. The subgroups occur in the same order as above, but they are grouped by conjugacy class.
 – convert(L, 'layers') : return a list of conjugacy classes, grouped by layer
 The lattice of subgroups is organized naturally in a number of layers, with the trivial subgroup at the bottom and G at the top: the layers are characterized by the number of (not necessarily distinct) prime factors in the order of its subgroups. This calling sequence returns a list of lists of lists of subgroups; the subgroups are first grouped into conjugacy classes, and then the conjugacy classes are grouped into layers.
 The conjugacy classes occur in the same order as above. Within a layer, the conjugacy classes are sorted by the order of the subgroup: conjugacy classes of smaller subgroups before conjugacy classes of larger subgroups. For conjugacy classes of equally big subgroups, conjugacy classes with more subgroups in them come before smaller conjugacy classes. Remaining ties are broken arbitrarily.
 – convert(L, 'list[zuppos]'), convert(L, 'list[group, zuppos]'), convert(L, 'layer[zuppos]'), convert(L, 'maximalsubgroups[group]'), etc : return alternative or additional information for each subgroup
 The algorithm for generating the subgroup lattice uses special generating sets for the subgroups, consisting of particular representatives for all cyclic subgroups of G of prime power order, or zuppos (the German-language acronym used for such subgroups). These generating sets can be used to test inclusion relations quickly: ${H}_{1}$ is a subgroup of ${H}_{2}$ if and only if the set of zuppo representatives in ${H}_{1}$ is a subset of the set of zuppo representatives in ${H}_{2}$.
 Using the indexed forms of the conversions above allows you to access this additional information. This can be used with conversions to list, maximalsubgroups, conjugacyclasses, and layers. You can supply the index zuppos to obtain the set of zuppo representatives of $H$ instead of each subgroup $H$. You can also supply both of the indices group and zuppos to obtain a list of both $H$ itself and the set of zuppo representatives in $H$. Supplying no indices is equivalent to supplying just the index group.
 Grouping of the resulting information is as before:
 • 'list[...]' and 'maximalsubgroups[...]' will return a list where each element is the requested information for a single subgroup;
 • 'conjugacyclasses[...]' will return a list of lists corresponding to conjugacy classes, where each element of a sublist is the requested information for a single subgroup;
 • 'layers[...]' will return a list of lists of lists corresponding to layers, where each element of the sub-sublist is the requested information for a single subgroup.
 For instance, convert(L, 'layers[group, zuppos]') will return a list of layers; each layer is represented by a list of conjugacy classes; each conjugacy class is represented by a list of subgroups; and each subgroup is represented by a two-element list of the subgroup data structure itself and its set of zuppo generators.
 – convert(L, 'graph') : convert to a GraphTheory graph data structure
 This converts the subgroup lattice to a graph data structure as used by the GraphTheory package. The vertices are the numbers $1$ through $n$, where $n$ is the number of subgroups of G; the number $i$ corresponds to the $i$th subgroup occurring in convert(L, 'list'). The vertices are drawn in horizontal layers corresponding to the layer structure described above and there is an edge from each vertex to each of its covering vertices (that is, its immediate parents in the lattice). Furthermore, in each layer, conjugacy classes of subgroups have their vertices closer together than for subgroups that are not conjugate.
 – convert(L, 'graph[weighted]') : convert to a GraphTheory weighted graph data structure
 This results in a data structure very similar to convert(L, 'graph'), but the edge from subgroup H to subgroup K will have as its associated weight the index K : H - that is, the number of cosets of H in K, or the ratio of the group orders of K to H.
 – convert(L, 'graph[directed]') or convert(L, 'graph[weighted, directed]') : convert to a GraphTheory directed graph data structure
 This results in a data structure very similar to convert(L, 'graph'), but the graph is directed. Each arc runs from a smaller subgroup to the bigger subgroup - that is, to a higher layer.
 • The algorithm used does not find any perfect subgroups of G, other than potentially G itself, its soluble residual, and the trivial group. If the soluble residual of G is of size at least 360, then it may contain other nontrivial perfect subgroups. These will not be found by the algorithm. Examples

 > $\mathrm{with}\left(\mathrm{GroupTheory}\right):$

Consider a group of order 48.

 > $\mathrm{g1}≔\mathrm{SmallGroup}\left(48,8\right)$
 ${\mathrm{g1}}{≔}{\mathrm{< a permutation group on 48 letters with 5 generators >}}$ (1)
 > $\mathrm{sgl1}≔\mathrm{SubgroupLattice}\left(\mathrm{g1}\right)$
 ${\mathrm{sgl1}}{≔}\left[\begin{array}{c}{\mathrm{subgroup lattice}}\\ {18}{\mathrm{conjugacy classes}}\\ {36}{\mathrm{subgroups}}\end{array}\right]$ (2)
 > $\mathrm{graph1}≔\mathrm{convert}\left(\mathrm{sgl1},'\mathrm{graph}'\right)$
 ${\mathrm{graph1}}{≔}{\mathrm{Graph 1: an undirected graph with 36 vertices and 83 edge\left(s\right)}}$ (3)
 > $\mathrm{GraphTheory}:-\mathrm{DrawGraph}\left(\mathrm{graph1}\right)$ The bottom layer is only the trivial subgroup. The layer above that (which contains all subgroups of prime order) contains only two subgroups. Since there must be elements of order 2 and of order 3 in a group of order 48 by Sylow's theorems, there is only a single subgroup of order 2 (with a single element of order 2) and a single subgroup of order 3 (with two elements of order 3). These subgroups correspond to groups 2 and 3 in the list below.

 > $\mathrm{subgroups1}≔\mathrm{convert}\left(\mathrm{sgl1},'\mathrm{list}'\right):$
 > ${\mathrm{subgroups1}}_{2}$
 $⟨\left({1}{,}{8}\right)\left({2}{,}{3}\right)\left({4}{,}{22}\right)\left({5}{,}{21}\right)\left({6}{,}{7}\right)\left({9}{,}{31}\right)\left({10}{,}{32}\right)\left({11}{,}{17}\right)\left({12}{,}{18}\right)\left({13}{,}{14}\right)\left({15}{,}{19}\right)\left({16}{,}{20}\right)\left({23}{,}{47}\right)\left({24}{,}{48}\right)\left({25}{,}{45}\right)\left({26}{,}{46}\right)\left({27}{,}{29}\right)\left({28}{,}{30}\right)\left({33}{,}{41}\right)\left({34}{,}{42}\right)\left({35}{,}{43}\right)\left({36}{,}{44}\right)\left({37}{,}{39}\right)\left({38}{,}{40}\right)⟩$ (4)
 > ${\mathrm{subgroups1}}_{3}$
 $⟨\left({1}{,}{9}{,}{10}\right)\left({2}{,}{15}{,}{16}\right)\left({3}{,}{19}{,}{20}\right)\left({4}{,}{23}{,}{24}\right)\left({5}{,}{25}{,}{26}\right)\left({6}{,}{27}{,}{28}\right)\left({7}{,}{29}{,}{30}\right)\left({8}{,}{31}{,}{32}\right)\left({11}{,}{33}{,}{34}\right)\left({12}{,}{35}{,}{36}\right)\left({13}{,}{37}{,}{38}\right)\left({14}{,}{39}{,}{40}\right)\left({17}{,}{41}{,}{42}\right)\left({18}{,}{43}{,}{44}\right)\left({21}{,}{45}{,}{46}\right)\left({22}{,}{47}{,}{48}\right)⟩$ (5)

From how $\mathrm{sgl1}$ prints, we can already see the number of subgroups and conjugacy classes, but here is how we can obtain them programmatically.

 > $\mathrm{numelems}\left(\mathrm{subgroups1}\right)$
 ${36}$ (6)
 > $\mathrm{conjugacy_classes1}≔\mathrm{convert}\left(\mathrm{sgl1},'\mathrm{conjugacyclasses}'\right):$
 > $\mathrm{numelems}\left(\mathrm{conjugacy_classes1}\right)$
 ${18}$ (7)

To obtain the maximum amount of information, use the command below.

 > $\mathrm{layers1}≔\mathrm{convert}\left(\mathrm{sgl1},'{\mathrm{layers}}_{\mathrm{group},\mathrm{zuppos}}'\right):$
 > $\mathrm{numelems}\left(\mathrm{layers1}\right)$
 ${6}$ (8)

The following corresponds to the first group in the first conjugacy class in the third layer - subgroup 4 in the diagram above:

 > $\mathrm{sg4}≔{{{\mathrm{layers1}}_{3}}_{1}}_{1}$
 ${\mathrm{sg4}}{≔}\left[⟨\left({1}{,}{11}{,}{8}{,}{17}\right)\left({2}{,}{22}{,}{3}{,}{4}\right)\left({5}{,}{14}{,}{21}{,}{13}\right)\left({6}{,}{18}{,}{7}{,}{12}\right)\left({9}{,}{34}{,}{31}{,}{42}\right)\left({10}{,}{33}{,}{32}{,}{41}\right)\left({15}{,}{48}{,}{19}{,}{24}\right)\left({16}{,}{47}{,}{20}{,}{23}\right)\left({25}{,}{40}{,}{45}{,}{38}\right)\left({26}{,}{39}{,}{46}{,}{37}\right)\left({27}{,}{44}{,}{29}{,}{36}\right)\left({28}{,}{43}{,}{30}{,}{35}\right)⟩{,}\left\{\left({1}{,}{11}{,}{8}{,}{17}\right)\left({2}{,}{22}{,}{3}{,}{4}\right)\left({5}{,}{14}{,}{21}{,}{13}\right)\left({6}{,}{18}{,}{7}{,}{12}\right)\left({9}{,}{34}{,}{31}{,}{42}\right)\left({10}{,}{33}{,}{32}{,}{41}\right)\left({15}{,}{48}{,}{19}{,}{24}\right)\left({16}{,}{47}{,}{20}{,}{23}\right)\left({25}{,}{40}{,}{45}{,}{38}\right)\left({26}{,}{39}{,}{46}{,}{37}\right)\left({27}{,}{44}{,}{29}{,}{36}\right)\left({28}{,}{43}{,}{30}{,}{35}\right){,}\left({1}{,}{8}\right)\left({2}{,}{3}\right)\left({4}{,}{22}\right)\left({5}{,}{21}\right)\left({6}{,}{7}\right)\left({9}{,}{31}\right)\left({10}{,}{32}\right)\left({11}{,}{17}\right)\left({12}{,}{18}\right)\left({13}{,}{14}\right)\left({15}{,}{19}\right)\left({16}{,}{20}\right)\left({23}{,}{47}\right)\left({24}{,}{48}\right)\left({25}{,}{45}\right)\left({26}{,}{46}\right)\left({27}{,}{29}\right)\left({28}{,}{30}\right)\left({33}{,}{41}\right)\left({34}{,}{42}\right)\left({35}{,}{43}\right)\left({36}{,}{44}\right)\left({37}{,}{39}\right)\left({38}{,}{40}\right)\right\}\right]$ (9)

We see that $\mathrm{sg4}$ is a list of two elements: a group and a set of elements. These elements are the zuppo representatives that were chosen for the lattice construction. We now take all subgroups in the layer above it:

 > $\mathrm{layer4}≔\mathrm{map}\left(\mathrm{op},{\mathrm{layers1}}_{4}\right):$

and find which ones contain all zuppo representatives of $\mathrm{sg4}$:

 > $\mathrm{map}\left(i→i+17,\mathrm{select}\left(i→{\mathrm{sg4}}_{2}⊆{{\mathrm{layer4}}_{i}}_{2},\left[\mathrm{seq}\left(1..\mathrm{numelems}\left(\mathrm{layer4}\right)\right)\right]\right)\right)$
 $\left[{18}{,}{27}\right]$ (10)

These correspond exactly to the neighbors of subgroup 4 in the fourth layer of the diagram above, once we add the offset 17 for the number of subgroups in the lower three layers.

We can get the same type of information for a Cayley table group:

 > $\mathrm{g2}≔\mathrm{SmallGroup}\left(24,1\right)$
 ${\mathrm{g2}}{≔}{\mathrm{< a permutation group on 24 letters with 4 generators >}}$ (11)
 > $\mathrm{g2}≔\mathrm{Group}\left(\mathrm{CayleyTable}\left(\mathrm{g2}\right)\right)$
 ${\mathrm{g2}}{≔}{\mathrm{< a Cayley table group with 24 elements >}}$ (12)
 > $\mathrm{graph2}≔\mathrm{SubgroupLattice}\left(\mathrm{g2},'\mathrm{output}={\mathrm{graph}}_{\mathrm{weighted}}'\right)$
 ${\mathrm{graph2}}{≔}{\mathrm{Graph 2: an undirected weighted graph with 10 vertices and 14 edge\left(s\right)}}$ (13)
 > $\mathrm{GraphTheory}:-\mathrm{DrawGraph}\left(\mathrm{graph2}\right)$ For many groups, the maximal subgroups are exactly the ones in the layer just below the topmost one. For the following group, this is not the case.

 > $\mathrm{g3}≔\mathrm{SmallGroup}\left(24,3\right)$
 ${\mathrm{g3}}{≔}{\mathrm{< a permutation group on 24 letters with 4 generators >}}$ (14)
 > $\mathrm{sgl3}≔\mathrm{SubgroupLattice}\left(\mathrm{g3}\right)$
 ${\mathrm{sgl3}}{≔}\left[\begin{array}{c}{\mathrm{subgroup lattice}}\\ {7}{\mathrm{conjugacy classes}}\\ {15}{\mathrm{subgroups}}\end{array}\right]$ (15)
 > $\mathrm{GraphTheory}:-\mathrm{DrawGraph}\left(\mathrm{convert}\left(\mathrm{sgl3},'\mathrm{graph}'\right)\right)$ > $\mathrm{convert}\left(\mathrm{sgl3},'\mathrm{maximalsubgroups}'\right)$
 $\left[⟨\left({1}{,}{2}{,}{3}\right)\left({4}{,}{11}{,}{19}\right)\left({5}{,}{12}{,}{22}\right)\left({6}{,}{23}{,}{14}\right)\left({7}{,}{24}{,}{15}\right)\left({8}{,}{13}{,}{18}\right)\left({9}{,}{16}{,}{20}\right)\left({10}{,}{17}{,}{21}\right){,}\left({1}{,}{8}\right)\left({2}{,}{13}\right)\left({3}{,}{18}\right)\left({4}{,}{5}\right)\left({6}{,}{7}\right)\left({9}{,}{10}\right)\left({11}{,}{12}\right)\left({14}{,}{15}\right)\left({16}{,}{17}\right)\left({19}{,}{22}\right)\left({20}{,}{21}\right)\left({23}{,}{24}\right)⟩{,}⟨\left({1}{,}{11}{,}{15}\right)\left({2}{,}{16}{,}{5}\right)\left({3}{,}{6}{,}{10}\right)\left({4}{,}{13}{,}{17}\right)\left({7}{,}{9}{,}{18}\right)\left({8}{,}{12}{,}{14}\right)\left({19}{,}{20}{,}{23}\right)\left({21}{,}{24}{,}{22}\right){,}\left({1}{,}{8}\right)\left({2}{,}{13}\right)\left({3}{,}{18}\right)\left({4}{,}{5}\right)\left({6}{,}{7}\right)\left({9}{,}{10}\right)\left({11}{,}{12}\right)\left({14}{,}{15}\right)\left({16}{,}{17}\right)\left({19}{,}{22}\right)\left({20}{,}{21}\right)\left({23}{,}{24}\right)⟩{,}⟨\left({1}{,}{23}{,}{17}\right)\left({2}{,}{19}{,}{7}\right)\left({3}{,}{20}{,}{12}\right)\left({4}{,}{9}{,}{14}\right)\left({5}{,}{10}{,}{15}\right)\left({6}{,}{13}{,}{22}\right)\left({8}{,}{24}{,}{16}\right)\left({11}{,}{18}{,}{21}\right){,}\left({1}{,}{8}\right)\left({2}{,}{13}\right)\left({3}{,}{18}\right)\left({4}{,}{5}\right)\left({6}{,}{7}\right)\left({9}{,}{10}\right)\left({11}{,}{12}\right)\left({14}{,}{15}\right)\left({16}{,}{17}\right)\left({19}{,}{22}\right)\left({20}{,}{21}\right)\left({23}{,}{24}\right)⟩{,}⟨\left({1}{,}{9}{,}{22}\right)\left({2}{,}{14}{,}{21}\right)\left({3}{,}{4}{,}{24}\right)\left({5}{,}{23}{,}{18}\right)\left({6}{,}{11}{,}{16}\right)\left({7}{,}{12}{,}{17}\right)\left({8}{,}{10}{,}{19}\right)\left({13}{,}{15}{,}{20}\right){,}\left({1}{,}{8}\right)\left({2}{,}{13}\right)\left({3}{,}{18}\right)\left({4}{,}{5}\right)\left({6}{,}{7}\right)\left({9}{,}{10}\right)\left({11}{,}{12}\right)\left({14}{,}{15}\right)\left({16}{,}{17}\right)\left({19}{,}{22}\right)\left({20}{,}{21}\right)\left({23}{,}{24}\right)⟩{,}⟨\left({1}{,}{21}{,}{8}{,}{20}\right)\left({2}{,}{24}{,}{13}{,}{23}\right)\left({3}{,}{22}{,}{18}{,}{19}\right)\left({4}{,}{6}{,}{5}{,}{7}\right)\left({9}{,}{11}{,}{10}{,}{12}\right)\left({14}{,}{16}{,}{15}{,}{17}\right){,}\left({1}{,}{8}\right)\left({2}{,}{13}\right)\left({3}{,}{18}\right)\left({4}{,}{5}\right)\left({6}{,}{7}\right)\left({9}{,}{10}\right)\left({11}{,}{12}\right)\left({14}{,}{15}\right)\left({16}{,}{17}\right)\left({19}{,}{22}\right)\left({20}{,}{21}\right)\left({23}{,}{24}\right){,}\left({1}{,}{5}{,}{8}{,}{4}\right)\left({2}{,}{10}{,}{13}{,}{9}\right)\left({3}{,}{15}{,}{18}{,}{14}\right)\left({6}{,}{20}{,}{7}{,}{21}\right)\left({11}{,}{23}{,}{12}{,}{24}\right)\left({16}{,}{19}{,}{17}{,}{22}\right)⟩\right]$ (16)

The alternating group on 6 letters is the smallest group for which the algorithm does not find all subgroups. (Missing are two conjugacy classes of 6 perfect subgroups each, all isomorphic to the alternating group on 5 letters.)

 > $\mathrm{SubgroupLattice}\left(\mathrm{AlternatingGroup}\left(6\right)\right)$
 $\left[\begin{array}{c}{\mathrm{subgroup lattice of}}{{\mathbf{A}}}_{{6}}\\ {20}{\mathrm{conjugacy classes}}\\ {489}{\mathrm{subgroups}}\end{array}\right]$ (17) Compatibility

 • The GroupTheory[SubgroupLattice] command was introduced in Maple 17.