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

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