Finitely Generated Subgroups of Free Groups#

generated subgroups of free groups which, by the Nielsen–Schreier theorem, are themselves free. For example, it is possible to determine the index of one such subgroup in another, which may be infinite, and computation of intersections and normalisers of subgroups, and conjugacy testing are all possible. The relevant algorithms are described in [Sims, 1994, Chapter 4], for example.

Supergroup(F): GrpFP -> GrpFP#: The largest (with respect to containment) free group of which \(F\) is known to be a subgroup. The remaining functions will fail and exit with errors if their arguments do not have a common supergroup.

x in H: GrpFP, GrpFPElt -> BoolElt#: Returns true in \(x \in H\), where \(x\) is required to be an element of Supergroup(F).

IsSubgroup(H, K): GrpFP, GrpFP -> BoolElt#: Given groups \(H\) and \(K\), subgroups of some common overgroup, return true if \(H\) is a subgroup of \(K\), and false otherwise.

H eq K: GrpFP, GrpFP -> BoolElt#: Determines whether the (free) subgroups \(H\) and \(K\) of a common free group are equal.

Index(F, H): GrpFP, GrpFP -> RngIntElt#: The index, which may be \(\infty\), in the free group \(F\) of subgroup \(H\). An error will occur if \(H\) is not a subgroup of \(F\).

HasFiniteIndex(F, H): GrpFP, GrpFP -> BoolElt#: Returns true if the index in the free group \(F\) of subgroup \(H\) is finite. An error will occur if \(H\) is not a subgroup of \(F\).

FreeGenerators(H): GrpFP -> SeqEnum, GrpFP#: Returns a sequence of free generators of free group H and also the same group H defined on those generators.

H meet K: GrpFP, GrpFP -> GrpFP#: Computes the intersection of free groups \(H\) and \(K\).

Centraliser(F, x): GrpFP, GrpFPElt -> GrpFP#
Centralizer(F, x): GrpFP, GrpFPElt -> GrpFP#: Computes the centralizer in free group \(F\) of element \(x\). An error will occur if \(x\) is not in \(F\).

IsConjugate(F, x, y): GrpFP, GrpFPElt, GrpFPElt -> BoolElt, GrpFPElt#: Determines whether elements \(x\) and \(y\) of free group \(F\) are conjugate in \(F\) and if so returns a conjugating element. An error will occur if either \(x\) or \(y\) is not in \(F\).

Centraliser(F, H): GrpFP, GrpFP -> GrpFP#
Centralizer(F, H): GrpFP, GrpFP -> GrpFP#: Computes the centralizer in free group \(F\) of subgroup \(H\). An error will occur if \(H\) is not a subgroup of \(F\).

Normaliser(F, H): GrpFP, GrpFP -> GrpFP#
Normalizer(F, H): GrpFP, GrpFP -> GrpFP#: Computes the normalizer in free group \(F\) of subgroup \(H\). An error will occur if \(H\) is not a subgroup of \(F\).

IsConjugate(F, H, K): GrpFP, GrpFP, GrpFP -> BoolElt, GrpFPElt#: Determines whether subgroups \(H\) and \(K\) of free group \(F\) are conjugate in \(F\) and if so returns a conjugating element. An error will occur if either \(H\) or \(K\) is not a subgroup of \(F\).

Example: Free Subgroups (ex-f8ece0)#

Starting with the free group of rank \(3\) some subgroup calculations will be demonstrated.

> F<a,b,c> := FreeGroup(3);
> F;
Finitely presented group F on 3 generators (free)

> H<x, y> := sub< F | a, b>;
> H;
Finitely presented group H on 2 generators
Generators as words in group F
    x = a
    y = b
> Index(F, H);
0

Run in calculator

The next step is to produce a more interesting subgroup of \(F\). To get one, the subgroup \(H\) will be conjugated by an element of \(F\).

> K := H^(a*b*c);
> K;
Finitely presented group K on 2 generators
Generators as words in group F
    K.1 = c^-1 * b^-1 * a * b * c
    K.2 = c^-1 * b^-1 * a^-1 * b * a * b * c
> H eq K;
false
> H meet K;
Finitely presented group on 1 generator
Generators as words in group F
    $.1 = Id(F)

> N := Normalizer(F, K);
> N;
Finitely presented group N on 2 generators
Generators as words in group F
    N.1 = a^c
    N.2 = b^c
> K eq N;
true

Run in calculator

The normaliser \(N\) of \(K\) has nice generators but it is equal to \(K\) so \(K\) is self-normalising.