We recall the following notation from the Introduction which is essential throughout this manual, cf. [Tor20]. Let \Omega be a set of cardinality d\in\mathbb{N}_{\ge 3} and let T_{d}=(V,E) denote the d-regular tree, following the graph theory notation in [Ser80]. A labelling l of T_{d} is a map l:E\to\Omega such that for every x\in V the restriction l_{x}:E(x)\to\Omega,\ e\mapsto l(e) is a bijection, and l(e)=l(\overline{e}) for all e\in E. For every k\in\mathbb{N}, fix a tree B_{d,k} which is isomorphic to a ball of radius k around a vertex in T_{d} and carry over the labelling of T_{d} to B_{d,k} via the chosen isomorphism. We denote the center of B_{d,k} by b.
For every x\in V there is a unique, label-respecting isomorphism l_{x}^{k}:B(x,k)\to B_{d,k}. We define the k-local action \sigma_{k}(g,x)\in\mathrm{Aut}(B_{d,k}) of an automorphism g\!\in\!\mathrm{Aut}(T_{d}) at a vertex x\in V via the map
\sigma_{k}:\mathrm{Aut}(T_{d})\times V\to\mathrm{Aut}(B_{d,k}), \sigma_{k}(g,x)\mapsto \sigma_{k}(g,x):=l_{gx}^{k}\circ g\circ (l_{x}^{k})^{-1}.
In this package, local actions F\le\mathrm{Aut}(B_{d,k}) are handled as objects of the category IsLocalAction (2.1-1) and have several attributes and properties introduced throughout this manual. Most importantly, a local action always stores the degree d and the radius k of the ball B_{d,k} that it acts on.
‣ IsLocalAction( F ) | ( filter ) |
Returns: true if F is an object of the category IsLocalAction, and false otherwise.
Local actions F\le\mathrm{Aut}(B_{d,k}) are stored together with their degree (see LocalActionDegree (2.1-4)), radius (see LocalActionRadius (2.1-5)) as well as other attributes and properties in this category. They can be initialised using the creator operation LocalAction (2.1-2).
gap> G:=WreathProduct(SymmetricGroup(2),SymmetricGroup(3)); Group([ (1,2), (3,4), (5,6), (1,3,5)(2,4,6), (1,3)(2,4) ]) gap> IsLocalAction(G); false gap> H:=AutBall(3,2); Group([ (1,2), (3,4), (5,6), (1,3,5)(2,4,6), (1,3)(2,4) ]) gap> IsLocalAction(H); true gap> K:=LocalAction(3,2,G); Group([ (1,2), (3,4), (5,6), (1,3,5)(2,4,6), (1,3)(2,4) ]) gap> IsLocalAction(K); true
‣ LocalAction( d, k, F ) | ( operation ) |
Returns: the regular rooted tree group G as an object of the category IsLocalAction (2.1-1), checking that F is indeed a subgroup of \mathrm{Aut}(B_{d,k}).
The arguments of this method are a degree d \in\mathbb{N}_{\ge 3}, a radius k \in\mathbb{N}_{0} and a group F \le\mathrm{Aut}(B_{d,k}).
gap> G:=WreathProduct(SymmetricGroup(2),SymmetricGroup(3)); Group([ (1,2), (3,4), (5,6), (1,3,5)(2,4,6), (1,3)(2,4) ]) gap> IsLocalAction(G); false gap> G:=LocalAction(3,2,G); Group([ (1,2), (3,4), (5,6), (1,3,5)(2,4,6), (1,3)(2,4) ]) gap> IsLocalAction(G); true
‣ LocalActionNC( d, k, F ) | ( operation ) |
Returns: the regular rooted tree group G as an object of the category IsLocalAction (2.1-1), without checking that F is indeed a subgroup of \mathrm{Aut}(B_{d,k}).
The arguments of this method are a degree d \in\mathbb{N}_{\ge 3}, a radius k \in\mathbb{N}_{0} and a group F \le\mathrm{Aut}(B_{d,k}).
‣ LocalActionDegree( F ) | ( attribute ) |
Returns: the degree d of the ball B_{d,k} that F is acting on.
The argument of this attribute is a local action F \le\mathrm{Aut}(B_{d,k}) (see IsLocalAction (2.1-1)).
gap> A4:=LocalAction(4,1,AlternatingGroup(4)); Alt( [ 1 .. 4 ] ) gap> F:=LocalActionPhi(3,A4); <permutation group with 18 generators> gap> LocalActionDegree(F); 4
‣ LocalActionRadius( F ) | ( attribute ) |
Returns: the radius k of the ball B_{d,k} that F is acting on.
The argument of this attribute is a local action F \le\mathrm{Aut}(B_{d,k}) (see IsLocalAction (2.1-1)).
gap> A4:=LocalAction(4,1,AlternatingGroup(4)); Alt( [ 1 .. 4 ] ) gap> F:=LocalActionPhi(3,A4); <permutation group with 18 generators> gap> LocalActionRadius(F); 3
‣ LocalAction( r, d, k, aut, addr ) | ( operation ) |
Returns: the r-local action \sigma_{r}(aut,addr) of the automorphism aut of B_{d,k} at the vertex represented by the address addr.
The arguments of this method are a radius r, a degree d \in\mathbb{N}_{\ge 3}, a radius k \in\mathbb{N}, an automorphism aut of B_{d,k}, and an address addr.
gap> a:=(1,3,5)(2,4,6);; a in AutBall(3,2); true gap> LocalAction(2,3,2,a,[]); (1,3,5)(2,4,6) gap> LocalAction(1,3,2,a,[]); (1,2,3) gap> LocalAction(1,3,2,a,[1]); (1,2)
gap> mt:=RandomSource(IsMersenneTwister,1);; gap> b:=Random(mt,AutBall(3,4)); (1,18,11,5,23,14,4,20,10,7,22,16)(2,17,12,6,24,13,3,19,9,8,21,15) gap> LocalAction(2,3,4,b,[3,1]); (1,2)(3,6,4,5) gap> LocalAction(3,3,4,b,[3,1]); Error, the sum of input argument r=3 and the length of input argument addr=[ 3, 1 ] must not exceed input argument k=4
‣ Projection( F, r ) | ( operation ) |
Returns: the restriction of the projection map \mathrm{Aut}(B_{d,k})\to\mathrm{Aut}(B_{d,r}) to F.
The arguments of this method are a local action F \le\mathrm{Aut}(B_{d,k}), and a projection radius r \le k.
gap> F:=LocalActionGamma(4,3,SymmetricGroup(3)); Group([ (1,16,19)(2,15,20)(3,13,18)(4,14,17)(5,10,23)(6,9,24)(7,12,22) (8,11,21), (1,9)(2,10)(3,12)(4,11)(5,15)(6,16)(7,13)(8,14)(17,21)(18,22) (19,24)(20,23) ]) gap> pr:=Projection(F,2); <action homomorphism> gap> mt:=RandomSource(IsMersenneTwister,1);; gap> a:=Random(mt,F);; Image(pr,a); (1,2)(3,5)(4,6)
‣ ImageOfProjection( F, r ) | ( function ) |
Returns: the local action \sigma_{r}(F,b)\le\mathrm{Aut}(B_{d,r}).
The arguments of this method are a local action F \le\mathrm{Aut}(B_{d,k}), and a projection radius r \le k. This method uses LocalAction (2.1-6) on generators rather than Projection (2.1-7) on the group to compute the image.
gap> AutBall(3,2); Group([ (1,2), (3,4), (5,6), (1,3,5)(2,4,6), (1,3)(2,4) ]) gap> ImageOfProjection(AutBall(3,2),1); Group([ (), (), (), (1,2,3), (1,2) ])
The automorphism groups of the finite labelled balls B_{d,k} lie at the center of this package. The method AutBall (2.2-1) produces these automorphism groups as iterated wreath products. The result is a permutation group on the set of leaves of B_{d,k}.
‣ AutBall( d, k ) | ( function ) |
Returns: the local action \mathrm{Aut}(B_{d,k}) as a permutation group of the d\cdot (d-1)^{k-1} leaves of B_{d,k}.
The arguments of this method are a degree d \in\mathbb{N}_{\ge 3} and a radius k \in\mathbb{N}_{0}.
gap> G:=AutBall(3,2); Group([ (1,2), (3,4), (5,6), (1,3,5)(2,4,6), (1,3)(2,4) ]) gap> Size(G); 48
The vertices at distance n from the center b of B_{d,k} are addressed as elements of the set
\Omega^{(n)}:=\{(\omega_{1},\ldots,\omega_{n})\in\Omega^{n}\mid \forall l\in\{1,\ldots,n-1\}:\ \omega_{l}\neq\omega_{l+1}\},
i.e. as lists of length n of elements from [1..d] such that no two consecutive entries are equal. They are ordered according to the lexicographic order on \Omega^{(n)}. The center b itself is addressed by the empty list []. Note that the leaves of B_{d,k} correspond to elements of \Omega^{(k)}.
‣ BallAddresses( d, k ) | ( function ) |
Returns: a list of all addresses of vertices in B_{d,k} in ascending order with respect to length, lexicographically ordered within each level. See AddressOfLeaf (2.3-3) and LeafOfAddress (2.3-4) for the correspondence between the leaves of B_{d,k} and addresses of length k.
The arguments of this method are a degree d \in\mathbb{N}_{\ge 3} and a radius k \in\mathbb{N}_{0}.
gap> BallAddresses(3,1); [ [ ], [ 1 ], [ 2 ], [ 3 ] ] gap> BallAddresses(3,2); [ [ ], [ 1 ], [ 2 ], [ 3 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]
‣ LeafAddresses( d, k ) | ( function ) |
Returns: a list of addresses of the leaves of B_{d,k} in lexicographic order.
The arguments of this method are a degree d \in\mathbb{N}_{\ge 3} and a radius k \in\mathbb{N}_{0}.
gap> LeafAddresses(3,2); [ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]
‣ AddressOfLeaf( d, k, lf ) | ( function ) |
Returns: the address of the leaf lf of B_{d,k} with respect to the lexicographic order.
The arguments of this method are a degree d \in\mathbb{N}_{\ge 3}, a radius k \in\mathbb{N}, and a leaf lf of B_{d,k}.
gap> AddressOfLeaf(3,2,1); [ 1, 2 ] gap> AddressOfLeaf(3,3,1); [ 1, 2, 1 ]
‣ LeafOfAddress( d, k, addr ) | ( function ) |
Returns: the smallest leaf (integer) whose address has addr as a prefix.
The arguments of this method are a degree d \in\mathbb{N}_{\ge 3}, a radius k \in\mathbb{N}, and an address addr.
gap> LeafOfAddress(3,2,[1,2]); 1 gap> LeafOfAddress(3,2,[3]); 5 gap> LeafOfAddress(3,2,[]); 1
‣ ImageAddress( d, k, aut, addr ) | ( function ) |
Returns: the address of the image of the vertex represented by the address addr under the automorphism aut of B_{d,k}.
The arguments of this method are a degree d \in\mathbb{N}_{\ge 3}, a radius k \in\mathbb{N}, an automorphism aut of B_{d,k}, and an address addr.
gap> ImageAddress(3,2,(1,2),[1,2]); [ 1, 3 ] gap> ImageAddress(3,2,(1,2),[1]); [ 1 ]
‣ ComposeAddresses( addr1, addr2 ) | ( function ) |
Returns: the concatenation of the addresses addr1 and addr2 with reduction as per [Tor20, Section 3.2].
The arguments of this method are two addresses addr1 and addr2.
gap> ComposeAddresses([1,3],[2,1]); [ 1, 3, 2, 1 ] gap> ComposeAddresses([1,3,2],[2,1]); [ 1, 3, 1 ]
generated by GAPDoc2HTML