Finitely Generated Subgroups of Free Groups

A number of functions are available that apply specifically to finitely 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 [Sim94, 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.

Rewrite(H, x): GrpFP, GrpFPElt -> BoolElt, GrpFPElt

If \(x\) is an element of \(H\), return true and the corresponding word in the generators of \(H\); otherwise return false.

SubgroupElements(G, H, n): GrpFP, GrpFP, RngIntElt -> SetEnum

Given a subgroup \(H\) of a finitely presented group \(G\), form the coset table for \(H\) in \(G\), and use it to return the words in the generators of \(G\) of length at most \(n\) that represent elements of \(H\).

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: Subgroups of a Free Group (ex-f8ece0)

Run in calculator (opens in a new tab)Copy input

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

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

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

Run in calculator (opens in a new tab)Copy input