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