Operations on the Set of Elements

Subsections

• Order Functions
• Set Operations
• Membership and Equality

Order Functions

Order(G) : GrpAtc -> RngIntElt

# G : GrpAtc -> RngIntElt

The order of the group G as an integer. If the order of G is known to be infinite Infinity is returned.

IsFinite(G) : GrpAtc -> BoolElt, RngIntElt

Given a confluent group G return true if G has finite order and false otherwise. If G does have finite order also return the order of G.

Example GrpAtc_Order (H31E5)

(1)

We construct the group Z wreath C_2 and compute its order. The result of Infinity indicates that the group has infinite order.

> F<a,b,t> := FreeGroup(3);
> Q := quo< F | t^2=1, b*a=a*b, t*a*t=b>;
> G := AutomaticGroup(Q);
Running Knuth-Bendix with the following parameter values
MaxRelations  = 200
MaxStates     = 0
TidyInt       = 20
MaxWdiffs     = 512
HaltingFactor = 100
MinTime       = 5
#System is confluent.
#Halting with 14 equations.
#First word-difference machine with 14 states computed.
#Second word-difference machine with 14 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 6 states computed.
#General multiplier with 27 states computed.
#Validity test on general multiplier succeeded.
#Checking inverse and short relations.
#Axiom checking succeeded.
> print Order(G);
Infinity

(2)

We construct a three fold cover of A_6 and check whether it has finite order.

> FG<a,b> := FreeGroup(2);
> Q := quo< FG | a^3=1, b^3=1, (a*b)^4=1, (a*b^-1)^5=1>;
> G := AutomaticGroup(Q : GeneratorOrder := [a,b,a^-1,b^-1]);
Running Knuth-Bendix with the following parameter values
MaxRelations  = 200
MaxStates     = 0
TidyInt       = 20
MaxWdiffs     = 512
HaltingFactor = 100
MinTime       = 5
#System is confluent.
#Halting with 183 equations.
#First word-difference machine with 289 states computed.
#Second word-difference machine with 360 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 314 states computed.
#General multiplier with 1638 states computed.
#Multiplier incorrect with generator number 4.
#General multiplier with 1958 states computed.
#Multiplier incorrect with generator number 2.
#General multiplier with 2020 states computed.
#Multiplier incorrect with generator number 1.
#General multiplier with 2038 states computed.
#Validity test on general multiplier succeeded.
#General length-2 multiplier with 4252 states computed.
#Checking inverse and short relations.
#Checking relation:  _1*_2*_1*_2 = _4*_3*_4*_3
#Checking relation:  _1*_4*_1*_4*_1 = _2*_3*_2*_3*_2
#Axiom checking succeeded.
> print IsFinite(G);
true 1080
> isf, ord := IsFinite(G);
> print isf, ord;
true 1080

Set Operations

Random(G, n) : GrpAtc, RngIntElt -> GrpAtcElt

A random word of length at most n in the generators of G.

Random(G) : GrpAtc -> GrpAtcElt

A random word (of length at most the order of G) in the generators of G.

Representative(G) : GrpAtc -> GrpAtcElt

Rep(G) : GrpAtc -> GrpAtcElt

An element chosen from G.

Set(G, a, b) : GrpAtc, RngIntElt, RngIntElt -> SetEnum

    Search: MonStgElt                   Default: "DFS"

Create the set of words, w, in G with a <= length(w) <= b. If Search is set to "DFS" (depth-first search) then words are enumerated in lexicographical order. If Search is set to "BFS" (breadth-first-search) then words are enumerated in lexicographical order for each individual length (i.e. in short-lex order). Depth-first-search is marginally quicker. Since the result is a set the words may not appear in the resultant set in the search order specified (although internally they will be enumerated in this order).

Set(G) : GrpAtc -> SetEnum

    Search: MonStgElt                   Default: "DFS"

Create the set of words that is the carrier set of G. If Search is set to "DFS" (depth-first search) then words are enumerated in lexicographical order. If Search is set to "BFS" (breadth-first-search) then words are enumerated in lexicographical order for each individual length (i.e. in short-lex order). Depth-first-search is marginally quicker. Since the result is a set the words may not appear in the resultant set in the search order specified (although internally they will be enumerated in this order).

Seq(G, a, b) : GrpAtc, RngIntElt, RngIntElt -> SeqEnum

    Search: MonStgElt                   Default: "DFS"

Create the sequence S of words, w, in G with a <= length(w) <= b. If Search is set to "DFS" (depth-first search) then words will appear in S in lexicographical order. If Search is set to "BFS" (breadth-first-search) then words will appear in S in lexicographical order for each individual length (i.e. in short-lex order). Depth-first-search is marginally quicker.

Seq(G) : GrpAtc -> SeqEnum

    Search: MonStgElt                   Default: "DFS"

Create a sequence S of words from the carrier set of G. If Search is set to "DFS" (depth-first search) then words will appear in S in lexicographical order. If Search is set to "BFS" (breadth-first-search) then words will appear in S in lexicographical order for each individual length (i.e. in short-lex order). Depth-first-search is marginally quicker.

Example GrpAtc_Set (H31E6)

> FG<a,b,c,d,e,f> := FreeGroup(6);
> Q := quo< FG | a*c^-1*a^-1*d=1, b*f*b^-1*e^-1=1,
>                c*e*c^-1*d^-1=1, d*f^-1*d^-1*a=1,
>                e*b*e^-1*a^-1=1, f*c^-1*f^-1*b^-1=1 >;
> G<a,b,c,d,e,f> := AutomaticGroup(Q);
Running Knuth-Bendix with the following parameter values
MaxRelations  = 200
MaxStates     = 0
TidyInt       = 20
MaxWdiffs     = 512
HaltingFactor = 100
MinTime       = 5
#System is confluent.
#Halting with 41 equations.
#First word-difference machine with 16 states computed.
#Second word-difference machine with 17 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 6 states computed.
#General multiplier with 58 states computed.
#Validity test on general multiplier succeeded.
#Checking inverse and short relations.
#Axiom checking succeeded.
> print Representative(G);
Id(G)
> print Random(G);
a*c;
> print Random(G, 5);
a * b
> Set(G);
{ a * d * b, a * b, a * b * e, a * c, a * d, d * b, b * e,
  a * b * a, a * b * d, b * a, a * c * e, Id(G), b * d, c * e,
  e, f, a, a * e, b, c, a * f, d }
> Seq(G : Search := "BFS");
[ Id(G), a, b, c, d, e, f, a * b, a * c, a * d, a * e, a * f,
  b * a, b * d, b * e, c * e, d * b, a * b * a, a * b * d,
  a * b * e, a * c * e, a * d * b ]

Membership and Equality

w in G : GrpAtcElt, GrpAtc -> BoolElt

Given a word w and an automatic group G, return true if w is an element of G, false otherwise.

w notin G : GrpAtcElt, GrpAtc -> BoolElt

Given a word w and an automatic group G, return true if w is not an element of G, false otherwise.

S subset G : { GrpAtcElt }, GrpAtc -> BoolElt

Given an automatic group G and a set (or sequence) S of words return true if every member of S is an element of G, false otherwise.

S notsubset G : { GrpAtcElt }, GrpAtc -> BoolElt

Given an automatic group G and a set (or sequence) S of words return true if any member of S is not an element of G, false otherwise.