GroupTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : GroupTheory/Simplify

GroupTheory

  

Simplify

  

simplify the presentation for a group

 

Calling Sequence

Parameters

Description

Examples

Compatibility

Calling Sequence

Simplify( G )

Simplify( G, tryhard )

Parameters

G

-

a finitely presented group

Description

• 

The Simplify( G ) command attempts to simplify the presentation associated to the finitely presented group G. First, simplifications try to reduce the numbers of generators and relators, but this may cause an increase in the total relator length.

• 

Use the tryhard option to force the Simplify command to employ more expensive simplifications that aim to reduce the total relator length.

• 

You can use the PresentationComplexity command to measure the result of simplification.

• 

The Simplify( G ) command employs several Tietze transformations, composed in a series of "rounds", to try to produce a "smaller" presentation for the input group G.  In the current implementation, each round consists of the following steps:

Step

Description

cyclic reduction

all relators are cyclically reduced

redundant relator removal

any relators that are trivially redundant are removed

elimination of trivial generators

any trivial generators detected are removed

elimination by "short" relators

relators of length 2 are used to eliminate generators

power-relator consolidation

multiple power relators for the same generator are resolved to a single relator

elimination by "long" relators

relators of length greater than 2 are used to eliminate generators

common subword reduction (tryhard)

with the tryhard option, or for very small presentations, an attempt is made to reduce the total relator length

• 

The first several simplifications listed are relatively inexpensive, and do not increase the total relator length, but may reduce the number of generators and relators.

• 

Elimination by "long" relators is moderately expensive, and decreases the number of generators and relators, at the expense of an increase in the total relator length.

• 

Common subword reduction is very expensive, and is only performed for presentations with few relators, or at the request of the user by the inclusion of the tryhard option.

• 

Because the implementation of this command involves heuristics that employ a trade-off between the level of simplification that can be achieved as well as time- and space-performance, the implementation is expected to evolve.  As a result, it cannot be expected that the exact simplifications performed on any given finite presentation will be compatible between Maple releases.

Examples

withGroupTheory:

Ga,b,c,d|a2,b2,c2,d2,a·b=c,b·c=d,d·a=b

Ga,b,c,da2,b2,c2,d2,a-1d-1b,b-1a-1c,c-1b-1d

(1)

SimplifyG

aa2

(2)

Ga,b,c|a2,b3,c5,a·b·c=1

Ga,b,ca2,abc,b3,c5

(3)

PresentationComplexityG

3,4,13

(4)

GSimplifyG

Ga,ba2,b3,b-1a-1b-1a-1b-1a-1b-1a-1b-1a-1

(5)

Note that while the number of generators and relators have each been reduced by one, the total relator length has increased by two.

PresentationComplexityG

2,3,15

(6)

GSmallGroup32,5,form=fpgroup

Ga1,a2,a3,a4,a5a22,a32,a52,a12a4-1,a42a5-1,a3-1a1-1a3a1,a3-1a2-1a3a2,a4-1a1-1a4a1,a4-1a2-1a4a2,a4-1a3-1a4a3,a5-1a1-1a5a1,a5-1a2-1a5a2,a5-1a3-1a5a3,a5-1a4-1a5a4,a2-1a1-1a2a1a3-1

(7)

PresentationComplexityG

5,15,53

(8)

GSimplifyG

Ga1,a2a22,a1-2a2-1a12a2,a18,a1-1a2-1a1a2-1a1-1a2a1a2,a2-1a1a2a1-1a2-1a1-1a2a1,a2-1a1-1a2a1a2-1a1-1a2a1,a1-4a2-1a14a2,a1-2a2-1a1a2a12a2-1a1-1a2,a1-4a2-1a1a2a14a2-1a1-1a2

(9)

As in the previous example, the total relator length is increased, though the number of generators and relators have both been reduced.

PresentationComplexityG

2,9,74

(10)

Using the tryhard option, more expensive simplifications are attempted which, in this case, successfully reduce the total relator length.

GSimplifyG,tryhard

Ga1,a2a22,a1-1a2a12a2-1a1-1,a18,a1-1a2-1a1a2-1a1-1a2a1a2,a2-1a1a2a1-1a2-1a1-1a2a1

(11)

PresentationComplexityG

2,5,32

(12)

The next example does not result in the elimination of any generators, but the number and total length of the relators is reduced.

Ga,b|a10·b·a·b=1,a11·b·a2·b·a11·b=1:

PresentationComplexityG

2,2,40

(13)

HSimplifyG

Ha,bab-1ab2aba-1b,a10bab

(14)

PresentationComplexityH

2,2,22

(15)

The Simplify command is typically used on the output of a Reidemeister-Schreier process for producing a presentation of a subgroup of a finitely presented group.

Ga,b,c|a3,b7,c13,a·b2,b·c2,c·a2,a·b·c2=1:

HSubgroupc,a·b,G:

PresentationComplexityH

2,60,25340

(16)

HSimplifyH:

PresentationComplexityH

2,28,10795

(17)

HSimplifyH,tryhard:

PresentationComplexityH

2,4,23

(18)

Compatibility

• 

The GroupTheory[Simplify] command was introduced in Maple 18.

• 

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

See Also

GroupTheory

GroupTheory[FPGroup]

GroupTheory[PresentationComplexity]