Working with Finitely Presented Groups - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : GroupTheory/tutorials/WorkingWithFPGroups

Working with Finitely Presented Groups

 

Introduction

Creating a Finitely Presented Group

Subgroups of Finitely Presented Groups

Operations on Finitely Presented Groups

Compatibility

Introduction

A finitely presented group is a group defined by a finite number of generators and defining relations or relators. Unlike permutation groups or Cayley table groups, where there are many operations that can be decided (even if only by an expensive algorithm), most interesting questions about finitely presented groups are algorithmically undecidable. This is not just a matter of nobody having yet been clever enough to devise an algorithm to answer the question. For most such questions it can be proved that no general algorithm can, in fact, exist. Nevertheless, you can attempt to answer questions about special classes of finitely presented groups, and there are procedures such as the Todd-Coxeter algorithm that, while non-terminating in general, will (eventually) terminate for finite finitely presented groups, given sufficient time and memory.

The following sections discuss some of the operations on finitely presented groups that are available in Maple.

Creating a Finitely Presented Group

with( GroupTheory ):

To begin working with finitely presented groups in Maple, the first thing that you need to do is to create such a group. A finitely presented group can be entered directly using notation very close to that used in textbooks. For example, the statement

G := < a, b | a^2, b^3, (a.b)^5 = 1 >;

Ga&comma;ba2&comma;b3&comma;ababababab

(1)

creates the alternating group of degree 5 as a finitely presented group.

There is one idiosyncrasy that you must be aware of: there must be at least one relation (in the form of an equation) among the relators for the input to be recognized as a finite presentation. Otherwise, Maple will interpret the syntax as a Vector.

To retrieve the set of generators of G, use the Generators command:

Generators( G );

a&comma;b

(2)

Note that the generators are represented as words [a] and [b], rather than just the symbols a and b. This is because, in general, a finitely presented group can be produced as the subgroup of another finitely presented group generated by some words on the original generators. You can obtain the relators (again, as a set of words), by using the Relators command:

Relators( G );

a&comma;a&comma;b&comma;b&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b

(3)

Another way to obtain finitely presented groups is to use one of the group constructors that return groups in this class by using the form = "fpgroup" option. For instance, all groups in the small groups database can be obtained in this way.

SmallGroup( 12, 3, 'form' = "fpgroup" );

a1&comma;a2&comma;a3a22&comma;a32&comma;a13&comma;a3-1a2-1a3a2&comma;a3-1a1-1a3a1a2-1&comma;a2-1a1-1a2a1a3-1a2-1

(4)

Many other constructors can produce a group in the form of a finitely presented group.

CyclicGroup( 6, 'form' = "fpgroup" );

gg6

(5)

DihedralGroup( 5, 'form' = "fpgroup" );

D5

(6)

Symm( 5, 'form' = "fpgroup" );

S5

(7)

Subgroups of Finitely Presented Groups

Use the Subgroup command to create a subgroup of a finitely presented group. The first argument is the set of generators, and the second argument is the finitely presented group of which it is a subgroup.

G := < a, b | [a,b] = 1 >;

Ga&comma;ba-1b-1ab

(8)

H := Subgroup( { a^4, (a.b)^9 }, G );

H_G&comma;_G0_G_G0_G-1_G0-1

(9)

Notice that Maple has produced a presentation for the subgroup H on a new set {_G, _G0} of generators.

To verify that H is indeed a subgroup of G, use the IsSubgroup command.

IsSubgroup( H, G );

true

(10)

You can obtain the parent group G from H by using the Supergroup command.

Supergroup( H );

a&comma;ba-1b-1ab

(11)

Each subgroup of a finitely presented group comes equipped with an embedding morphism.

eta := Embedding( H );

η<a group morphism>

(12)

eta( [_G,_G,_G0,_G0,_G0] );

a&comma;a&comma;a&comma;a&comma;a&comma;a&comma;a&comma;a&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b&comma;a&comma;b

(13)

You can apply the embedding eta to a word on the generators of H.

Operations on Finitely Presented Groups

To compute the order of a finitely presented group, use the GroupOrder command. In general, the order of a finitely presented group cannot be determined, but the command attempts to handle certain cases in which the order can be determined. In particular, if the group is finite then, given sufficient time and space, the order can eventually be determined.

G := < a, b, c, d, e | a.b = c, b.c = d, c.d = e, d.e = a, e.a = b >;

Ga&comma;b&comma;c&comma;d&comma;ea-1e-1b&comma;b-1a-1c&comma;c-1b-1d&comma;d-1c-1e&comma;e-1d-1a

(14)

GroupOrder( G );

11

(15)

G := < a, b | a^2 = b^3 >;

Ga&comma;ba-2b3

(16)

GroupOrder( G );

(17)

It is often of use to know the structure of the abelianization of a finitely presented group. Use the AbelianInvariants command to obtain the canonical invariants of the abelianization of a finitely presented group.

AbelianInvariants( G );

1&comma;

(18)

The list returned has the form [r,[d[1], d[2], ..., d[k]]], where r is the rank of the torsion-free part, and the d[i] are the invariant factors, with d[i] a divisor of d[i+1]. Thus, the abelianization of this group G is infinite cyclic.

Now, consider the following subgroup H of G.

H := Subgroup( { a, [b,a,1/b], [1/b,a,b,a,1/b,1/a,b],[1/b,a,1/b,a,b,a,1/b,1/a,b,1/a,b], [1/b,a,1/b,a,1/b,a,b,1/a,b,1/a,b,1/a,b] }, G );

H_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1

(19)

This is a subgroup of finite index in G. You can determine the index by using the Index command.

Index( H, G );

10

(20)

Often, computing a subgroup of a finitely presented group will produce an unwieldy presentation. You can try to reduce the overall "size" of the presentation by using the Simplify command.

H2 := Simplify( H );

H2_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G3-2_G12&comma;_G4-2_G32&comma;_G5_G2-2_G52&comma;_G5-3_G42

(21)

To measure the effect of whatever simplifications were achieved, use the PresentationComplexity command.

PresentationComplexity( H );

5,7,39

(22)

PresentationComplexity( H2 );

5,7,30

(23)

This indicates that, while the numbers of generators (5) and relators (7) were not reduced, the total length of the relators was reduced from 39 to 30.

For a finite index subgroup H of a finitely presented group G, you can obtain the set of (left or right) cosets as shown in the following example.

cosets := RightCosets( H, G );

cosets_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b-1&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b-1a&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b-1ab&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b-1abab-2&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b-1abab-2a&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b-1abab-2ab&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b-1abab-2abab-2&comma;_G1&comma;_G2&comma;_G3&comma;_G4&comma;_G5_G12_G2-2&comma;_G3_G2-2_G3&comma;_G4_G2-2_G4&comma;_G5_G2-2_G52&comma;_G3_G2-2_G3-1_G12&comma;_G4_G2-2_G4-1_G3_G22_G3-1&comma;_G5_G2-2_G5-1_G4_G22_G4-1·b-1abab-2abab-2a

(24)

Each coset has the form Hg, for some element g of G. This element g is called a representative of the coset Hg. To obtain a representative for a coset, use the Representative method.

map( Representative, cosets );

1&comma;b&comma;b-1&comma;b-1a&comma;b-1ab&comma;b-1abab-2&comma;b-1abab-2a&comma;b-1abab-2ab&comma;b-1abab-2abab-2&comma;b-1abab-2abab-2a

(25)

As explained above, most questions about finitely presented groups cannot be answered in general.

IsAbelian( G );

Error, (in IsAbelian) cannot determine whether a general finitely presented group is Abelian.  If you know that your group is finite, try converting it to a permutation group by using the `PermutationGroup' command with your finitely presented group as input.

However, if you have a finite finitely presented group, you can often get an answer by first converting it to a permutation group using the PermutationGroup constructor.

G := < a, b | a^2, b^4, (a.b)^2 = 1 >;

Ga&comma;ba2&comma;abab&comma;b4

(26)

IsFinite( G );

true

(27)

IsAbelian( PermutationGroup( G ) );

false

(28)

The same is true of many other computations that cannot be complete for finitely presented groups in general.

IsNilpotent( PermutationGroup( G ) );

true

(29)

Compatibility

• 

The Working with Finitely Presented Groups tutorial was introduced in Maple 2015.

• 

For more information on Maple 2015 changes, see Updates in Maple 2015.