This chapter is intended for advanced users. It explains the provided search methods and the interface to the search graph structure LinsGraph.
All search methods in LINS return a LinsGraph encoding a partial normal subgroup lattice of a finitely presented group \(G\). A LinsGraph is a graph, where each node is a LinsNode that contains a normal subgroup \(H\) of \(G\) and pointers to the minimal \(G\)-normal super/sub-groups of \(H\), i.e. its neighbours in the graph. The directed edges of the graph are therefore encoded directly into the nodes.
‣ List( gr ) | ( method ) |
Returns a list of all LinsNodes in the graph gr.
The nodes are sorted by index in increasing order, e.g. the root node is at the first position. In order to get a list containing only the normal subgroups that the search graph attempted to find, use ComputedNormalSubgroups (2.1-2).
‣ ComputedNormalSubgroups( gr ) | ( attribute ) |
Returns the normal subgroups that the search graph attempted to find.
If the ComputedNormalSubgroups component of the graph is not set, this defaults to a call of List (2.1-1).
‣ LinsRoot( gr ) | ( attribute ) |
Returns the root node of the graph.
If the search was started in the finitely presented group \(G\), this will return the LinsNode that contains \(G\).
‣ IndexBound( gr ) | ( attribute ) |
Returns the index bound for the search in gr.
‣ LinsOptions( gr ) | ( attribute ) |
Returns the search options of the graph gr.
‣ IsomorphismFpGroup( gr ) | ( attribute ) |
Returns the isomorphism from the original group of the search onto the fp-group contained in the root.
A LinsNode is a part of the search graph structure LinsGraph (see 2.1). As such, all methods are with respect to the search graph, where the node is contained in.
‣ Grp( rH ) | ( method ) |
Returns the group contained in the node.
‣ Index( rH ) | ( method ) |
Let \(G\) be the group contained in the root node and \(H\) be the \(G\)-normal subgroup contained in rH.
Returns the index \([G : H]\).
‣ LinsNodeMinimalSupergroups( rH ) | ( attribute ) |
Let \(G\) be the group contained in the root node and \(H\) be the \(G\)-normal subgroup contained in rH.
Returns a list of all LinsNodes containing minimal \(G\)-normal supergroups of \(H\).
‣ LinsNodeMinimalSubgroups( rH ) | ( attribute ) |
Let \(G\) be the group contained in the root node and \(H\) be the \(G\)-normal subgroup contained in rH.
Returns a list of all LinsNodes containing minimal \(G\)-normal subgroups of \(H\).
‣ LinsNodeSupergroups( rH ) | ( operation ) |
Let \(G\) be the group contained in the root node and \(H\) be the \(G\)-normal subgroup contained in rH.
Returns a list of all LinsNodes containing \(G\)-normal supergroups of \(H\).
‣ LinsNodeSubgroups( rH ) | ( operation ) |
Let \(G\) be the group contained in the root node and \(H\) be the \(G\)-normal subgroup contained in rH.
Returns a list of all LinsNodes containing \(G\)-normal subgroups of \(H\).
‣ LowIndexNormalSubgroupsSearch( G, n[, opts] ) | ( function ) |
Given a finitely presented group G and some index bound n, this will start a search in the normal subgroup lattice of G up to index n.
The optional argument opts must be a record containing valid search options (see 3.1).
If the optional argument opts is not given, the search will be started with the default options, i.e. it will terminate once all normal subgroups of G with index at most n are found.
It is possible to call the function with a group G that is not an fp-group. The group will be automatically replaced with an fp-group (see IsomorphismFpGroup (2.1-6)).
Returns: LinsGraph encoding a partial normal subgroup lattice of G
‣ LowIndexNormalSubgroupsSearchForAll( G, n ) | ( function ) |
Given a finitely presented group G and some index bound n, this will compute all normal subgroups of G with index at most n.
This is a synonym for calling LowIndexNormalSubgroupsSearch (2.3-1) without any options.
It is possible to call the function with a group G that is not an fp-group. The group will be automatically replaced with an fp-group (see IsomorphismFpGroup (2.1-6)).
Returns: LinsGraph encoding a partial normal subgroup lattice of G
‣ LowIndexNormalSubgroupsSearchForIndex( G, n, l ) | ( function ) |
Given a finitely presented group G, some index n and l being a positive integer or infinity, this will attempt to find l normal subgroups of G with index n.
In particular, if l is infinity, all normal subgroups of G with index n will be computed.
Furthermore, if l is a positive integer and the ComputedNormalSubgroups of the graph has less than l nodes, then all normal subgroups of G with index n were computed.
It is possible to call the function with a group G that is not an fp-group. The group will be automatically replaced with an fp-group (see IsomorphismFpGroup (2.1-6)).
Returns: LinsGraph encoding a partial normal subgroup lattice of G
In this section we present example sessions which demonstrate how to use the advanced search methods provided by LINS. For this we revise the examples from the introduction as well as include new ones.
We compute all normal subgroups in \(D_{50}\), the dihedral group of size \(50\).
gap> G := DihedralGroup(50); <pc group of size 50 with 3 generators>
The search algorithm automatically translates the group into a finitely presented group via a call to IsomorphismFpGroup.
The isomorphism is stored inside the lins graph.
gap> gr := LowIndexNormalSubgroupsSearchForAll(G, 50); <lins graph contains 4 normal subgroups up to index 50> gap> r := LinsRoot(gr); <lins node of index 1> gap> H := Grp(r); <fp group of size 50 on the generators [ F1, F2, F3 ]> gap> Iso := IsomorphismFpGroup(gr); [ f1, f2, f3 ] -> [ F1, F2, F3 ] gap> Source(Iso) = G; true gap> Range(Iso) = H; true
In order to get all nodes from the search graph, we need to use List. As expected, the algorithm finds \(D_{50}, C_{25}, C_5\) and the trivial group.
gap> L := List(gr); [ <lins node of index 1>, <lins node of index 2>, <lins node of index 10>, <lins node of index 50> ] gap> IsoTypes := List(L, node -> StructureDescription(Grp(node))); [ "D50", "C25", "C5", "1" ]
We compute all normal subgroups of index \(5^2 = 25\) in \(C_5^4\), the direct product of \(4\) copies of the cyclic group of order \(5\):
gap> G := ElementaryAbelianGroup(5^4); <pc group of size 625 with 4 generators>
Again, the search algorithm automatically translates the group into a finitely presented group via a call to IsomorphismFpGroup.
gap> gr := LowIndexNormalSubgroupsSearchForIndex(G, 5 ^ 2, infinity); <lins graph contains 963 normal subgroups up to index 25>
Now we are not interested in all normal subgroups that the search graph considered, but only in those of index \(25\). Thus we need to use ComputedNormalSubgroups. For a prime \(p\), and integers \(d, s \in \mathbb{N}\), the number of subgroups of order \(p^s\) of an elementary abelian \(p\)-group of order \(p^d\) is exactly
\[ ( (p^d - 1)(p^d - p) \cdots (p^d - p^{(s-1)}) ) / ( (p^s - 1)(p^s - p) \cdots (p^s - p^{(s-1)}) ) . \]
Thus we expect to find \(( (5^4-1) \cdot (5^4-5) ) / ( (5^2 - 1) \cdot (5^2 - 5) ) = 806\) normal subgroups of index \(25\).
Furthermore, all subgroups need to be of the isomorphism type \(C_5^2\).
gap> L := ComputedNormalSubgroups(gr);; gap> IsoTypes := Collected(List(L, node -> StructureDescription(Grp(node)))); [ [ "C5 x C5", 806 ] ]
We compute a normal subgroup of index \(3 \cdot 5 = 15\) in \(C_3 \times C_3 \times C_4 \times C_5\), a direct product of cyclic groups:
gap> G := AbelianGroup([3, 3, 4, 5]); <pc group of size 180 with 4 generators> gap> gr := LowIndexNormalSubgroupsSearchForIndex(G, 15, 1); <lins graph contains 7 normal subgroups up to index 15>
We use ComputedNormalSubgroups in order to get the normal subgroup of index \(15\). As expected, the algorithm finds a group of the isomorphism type \(C_{12} = C_3 \times C_4\).
gap> L := ComputedNormalSubgroups(gr); [ <lins node of index 15> ] gap> IsoTypes := List(L, node -> StructureDescription(Grp(node))); [ "C12" ]
generated by GAPDoc2HTML