[MathJax on]

2 LINS Interface

This chapter is intended for advanced users. It explains the provided search methods and the interface to the search graph structure LinsGraph.

2.1 LINS Graph

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.

2.1-1 List

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

2.1-2 ComputedNormalSubgroups

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

2.1-3 LinsRoot

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.

2.1-4 IndexBound

Returns the index bound for the search in gr.

2.1-5 LinsOptions

Returns the search options of the graph gr.

2.1-6 IsomorphismFpGroup

Returns the isomorphism from the original group of the search onto the fp-group contained in the root.

2.2 LINS Node

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.

2.2-1 Grp

Returns the group contained in the node.

2.2-2 Index

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].

2.2-3 LinsNodeMinimalSupergroups

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.

2.2-4 LinsNodeMinimalSubgroups

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.

2.2-5 LinsNodeSupergroups

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.

2.2-6 LinsNodeSubgroups

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.

2.3 LINS Search Functions

2.3-1 LowIndexNormalSubgroupsSearch

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

2.3-2 LowIndexNormalSubgroupsSearchForAll

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

2.3-3 LowIndexNormalSubgroupsSearchForIndex

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

2.4 Examples

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.

2.4-1 Revised Example : all normal subgroups up to index n

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" ]

2.4-2 Revised Example : all normal subgroups of index n

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 ∈ 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) ⋯ (p^d - p^(s-1)) ) / ( (p^s - 1)(p^s - p) ⋯ (p^s - p^(s-1)) ) .

Thus we expect to find ( (5^4-1) ⋅ (5^4-5) ) / ( (5^2 - 1) ⋅ (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 ] ]

2.4-3 Example : a normal subgroup of index n

We compute a normal subgroup of index 3 ⋅ 5 = 15 in C_3 × C_3 × C_4 × 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 × C_4.

gap> L := ComputedNormalSubgroups(gr);
[ <lins node of index 15> ]
gap> IsoTypes := List(L, node -> StructureDescription(Grp(node)));
[ "C12" ]

generated by GAPDoc2HTML