Let \Omega be a set of cardinality d\in\mathbb{N}_{\ge 3} and let T_{d}=(V,E) be the d-regular tree. We follow Serre's graph theory notation [Ser80]. Given a subgroup H of the automorphism group \mathrm{Aut}(T_{d}) of T_{d}, and a vertex x\in V, the stabilizer H_{x} of x in H induces a permutation group on the set E(x):=\{e\in E\mid o(e)=x\} of edges issuing from x. We say that H is locally "P" if for every x\in V said permutation group satisfies the property "P", e.g. being transitive, semiprimitive, quasiprimitive or 2-transitive.
In [BM00], Burger-Mozes develop a remarkable structure theory of closed, non-discrete, locally quasiprimitive subgroups of \mathrm{Aut}(T_{d}), which resembles the theory of semisimple Lie groups. They complement this structure theory with a particularly accessible class of subgroups of \mathrm{Aut}(T_{d}) with prescribed local action: Given F\le\mathrm{Sym}(\Omega), their universal group \mathrm{U}(F)\le\mathrm{Aut}(T_{d}) is closed, compactly generated, vertex-transitive and locally permutation isomorphic to F. It is discrete if and only if F is semiregular. When F is transitive, \mathrm{U}(F) is maximal up to conjugation among vertex-transitive subgroups of \mathrm{Aut}(T_{d}) that are locally permutation isomorphic to F, hence universal.
This construction was generalized by the second author in [Tor20]: In the spirit of k-closures of groups acting on trees developed in [BEW15], we generalize the universal group construction by prescribing the local action on balls of a given radius k\in\mathbb{N}, the Burger-Mozes construction corresponding to the case k=1. Fix a tree B_{d,k} which is isomorphic to a ball of radius k in the labelled tree T_{d} and let l_{x}^{k}:B(x,k)\to B_{d,k} (x\in V) be the unique label-respecting isomorphism. Then
\sigma_{k}:\mathrm{Aut}(T_{d})\times V\to\mathrm{Aut}(B_{d,k}),\ (g,x)\to l_{gx}^{k}\circ g\circ (l_{x}^{k})^{-1}
captures the k-local action of g at the vertex x\in V.
With this we can make the following definition: Let F\!\le\!\mathrm{Aut}(B_{d,k}). Define
\mathrm{U}_{k}(F):=\{g\in\mathrm{Aut}(T_{d})\mid \forall x\in V:\ \sigma_{k}(g,x)\in F\}.
While \mathrm{U}_{k}(F) is always closed, vertex-transitive and compactly generated, other properties of \mathrm{U}(F) do not carry over. Foremost, the group \mathrm{U}_{k}(F) need not be locally action isomorphic to F and we say that F\le\mathrm{Aut}(B_{d,k}) satisfies condition (C) if it is. This can be viewed as an interchangeability condition on neighbouring local actions, see Section 3.1. There is also a discreteness condition (D) on F\le\mathrm{Aut}(B_{d,k}) in terms of certain stabilizers in F under which \mathrm{U}_{k}(F) is discrete, see Section 5.1.
UGALY provides methods to create, analyse and find local actions F\le\mathrm{Aut}(B_{d,k}) that satisfy condition (C) and/or (D), including the constructions \Gamma, \Delta, \Phi, \Sigma, and \Pi developed in [Tor20]. This package was developed within the Zero-Dimensional Symmetry Research Group in the School of Mathematical and Physical Sciences at The University of Newcastle as part of a project course taken by the first author, supervised by the second author.
Note: many of the examples in this manual access random elements of various domains via Random(). To ensure reproducibility and testability we initialize the random source mt below each time.
gap> mt:=RandomSource(IsMersenneTwister,1); <RandomSource in IsMersenneTwister>
UGALY serves both a research and an educational purpose. It consolidates a rudimentary codebase that was developed by the second author in the course of research undertaken towards the article [Tor20]. This codebase had been tremendously beneficial in achieving the results of [Tor20] in the first place and so there has always been a desire to make it available to a wider audience.
From a research perspective, UGALY introduces computational methods to the world of locally compact groups. Due to the Cayley-Abels graph construction [KM08], groups acting on trees form a particularly significant class of totally disconnected locally compact groups. Burger-Mozes universal groups [BM00] and their generalisations \mathrm{U}_{k}(F), where F\le\mathrm{Aut}(B_{d,k}) satisfies the compatibility condition (C), are among the most accessible of these groups and form a significant subclass: in fact, due to [Tor20, Corollary 4.32], the locally transitive, generalised universal groups are exactly the closed, locally transitive subgroups of \mathrm{Aut}(T_{d}) that contain an inversion of order 2 and satisfy one of the independence properties (P_{k}) (see [BEW15]) that generalise Tits' independence property (P), see [Tit70]. Subgroups of \mathrm{Aut}(B_{d,k}) are treated as objects of the category IsLocalAction (2.1-1) to the effect that they remember the degree d the radius k of the tree B_{d,k} that they act on as a permutation group on its d\cdot(d-1)^{k-1} leaves. For example, the automorphism group of B_{3,2} can be accessed as follows.
gap> F:=AutBall(3,2); Group([ (1,2), (3,4), (5,6), (1,3,5)(2,4,6), (1,3)(2,4) ]) gap> IsLocalAction(F); true gap> LocalActionDegree(F); 3 gap> LocalActionRadius(F); 2
In general, a subgroup F of the permutation group \mathrm{Aut}(B_{d,k}) can be turned into an object of the category IsLocalAction (2.1-1) by calling the creator operation LocalAction (2.1-2) with the degree d, the radius k and the permutation group F itself. For example, the subgroup A_{3}\le\mathrm{Aut}(B_{3,1})\cong S_{3} can be generated as follows.
gap> A3:=LocalAction(3,1,AlternatingGroup(3)); Alt( [ 1 .. 3 ] ) gap> IsLocalAction(A3); true gap> LocalActionDegree(A3); 3 gap> LocalActionRadius(A3); 1
UGALY provides the means to generate a library of all generalised universal groups \mathrm{U}_{k}(F) in terms of their k-local action F\le\mathrm{Aut}(B_{d,k}) satisfying the compatibility condition (C). We envision to add such a library in a future version of this package. In the case k=1 of classical Burger-Mozes groups, the compatibility condition (C) is void and so the library would coincide with the library of finite transitive permutation groups TransGrp. For example, in the case (d,k)=(3,1) there are only two local actions, corresponding to the two transitive permutation groups of degree 3, namely A_{3} and S_{3}.
gap> A3:=LocalAction(3,1,TransitiveGroup(3,1)); A3 gap> S3:=LocalAction(3,1,TransitiveGroup(3,2)); S3
To create this library for the case (d,k)=(3,2) we organise the subgroups F\le\mathrm{Aut}(B_{3,2}) that satisfy the compatibility condition (C) according to which subgroup of \mathrm{Aut}(B_{3,1}) they project to under the natural projection \mathrm{Aut}(B_{3,2})\to\mathrm{Aut}(B_{3,1}) that restricts automorphisms to B_{3,1}\subseteq B_{3,2}. In other words, we organise the subgroups F\le\mathrm{Aut}(B_{3,2}) satisfying (C) according to \sigma_{1}(F,b)\le\mathrm{Aut}(B_{3,1}). Using ConjugacyClassRepsCompatibleGroupsWithProjection (3.3-5), the following code illustrates that there is one conjugacy class of groups that projects to A_{3} whereas five project to S_{3}.
gap> A3_extn:=ConjugacyClassRepsCompatibleGroupsWithProjection(2,A3); [ Group([ (1,4,5)(2,3,6) ]) ] gap> S3_extn:=ConjugacyClassRepsCompatibleGroupsWithProjection(2,S3); [ Group([ (1,2)(3,5)(4,6), (1,4,5)(2,3,6) ]), Group([ (1,2)(3,4)(5,6), (1,2)(3,5)(4,6), (1,4,5)(2,3,6) ]), Group([ (3,4)(5,6), (1,2)(3,4), (1,4,5)(2,3,6), (3,5,4,6) ]), Group([ (3,4)(5,6), (1,2)(3,4), (1,4,5)(2,3,6), (3,5)(4,6) ]), Group([ (3,4)(5,6), (1,2)(3,4), (1,4,5)(2,3,6), (5,6), (3,5,4,6) ]) ]
All of these groups have been identified to stem from general constructions of groups \widetilde{F}\le\mathrm{Aut}(B_{d,2}) satisfying (C) from a given group F\le\mathrm{Aut}(B_{d,1}), much like some finite transitive groups have been organised into families. Specifically, the constructions \Gamma(F), \Delta(F), \Pi(F,\rho,X) and \Phi(F) introduced in the article [Tor20, Section 3.4] can be accessed via the UGALY functions LocalActionGamma (4.1-2), LocalActionDelta (4.1-3), LocalActionPi (4.4-4) and LocalActionPhi (4.2-1) respectively, see Chapter 4. Below, we use these functions to identify all six groups of the previous output.
gap> LocalActionPhi(A3)=A3_extn[1]; true gap> LocalActionGamma(3,S3)=S3_extn[1]; true gap> LocalActionDelta(3,S3)=S3_extn[2]; false gap> IsConjugate(AutBall(3,2),LocalActionDelta(3,S3),S3_extn[2]); true gap> rho:=SignHomomorphism(S3);; gap> LocalActionPi(2,3,S3,rho,[0,1])=S3_extn[3]; true gap> LocalActionPi(2,3,S3,rho,[1])=S3_extn[4]; true gap> LocalActionPhi(S3)=S3_extn[5]; true
UGALY may also be a useful tool in the context of the Weiss conjecture [Wei78], which in particular states that there are only finitely many conjugacy classes of discrete, vertex-transitive and locally primitive subgroup of \mathrm{Aut}(T_{d}). When such a group contains an inversion of order 2, it can be written as a universal group \mathrm{U}_{k}(F), where F\le\mathrm{Aut}(B_{d,k}) satisfies both the compatibility condition (C) and the discreteness condition (D), due to [Tor20, Corollary 4.38]. Therefore, UGALY can be used to construct explicit examples of groups relevant to the Weiss conjecture. Their structure as well as patterns in their appearance may provide more insight into the conjecture and suggest directions of research. At the very least, UGALY provides lower bounds on their numbers. For example, consider the case d=4. There are exactly two primitive groups of degree 4, namely A_{4} and S_{4}, which we readily turn into objects of the category IsLocalAction (2.1-1).
gap> NrPrimitiveGroups(4); 2 gap> A4:=LocalAction(4,1,PrimitiveGroup(4,1));; gap> S4:=LocalAction(4,1,PrimitiveGroup(4,2));;
Next, we proceed as before to determine how many conjugacy classes of subgroups of \mathrm{Aut}(B_{4,2}) with (C) there are that project onto A_{4} and S_{4} respectively. We then filter the output for subgroups that, in addition, satisfy the discreteness condition (D), see SatisfiesD (5.2-1).
gap> A4_extn:=ConjugacyClassRepsCompatibleGroupsWithProjection(2,A4);; gap> Size(A4_extn); Size(Filtered(A4_extn,SatisfiesD)); 5 2 gap> S4_extn:=ConjugacyClassRepsCompatibleGroupsWithProjection(2,S4);; gap> Size(S4_extn); Size(Filtered(S4_extn,SatisfiesD)); 13 3
For A_{4} there are two, and for S_{4} there are three. We conclude that there are at least 5=2+3 conjugacy classes of discrete, vertex-transitive and locally primitive subgroups of \mathrm{Aut}(T_{4}). More examples, and hence a better lower bound, can be obtained by increasing k.
Every subgroup F\le\mathrm{Aut}(B_{d,k}) which satisfies both (C) and (D) admits an involutive compatibility cocycle (see [Tor20, Section 3.2.2]), i.e. a map z:F\times\{1,\ldots,d\}\to F which satisfies certain properties reflecting the discreteness of the group \mathrm{U}_{k}(F). It is intriguing that some groups F\le\mathrm{Aut}(B_{d,k}) with (C) and (D) stem from groups F'\le\mathrm{Aut}(B_{d,k-1}) that satisfy (C), admit an involutive compatibility cocycle z but do not satisfy (D), in the sense of the construction F=\Gamma_{z}(F') (see [Tor20, Proposition 3.26]), whereas others do not. For example, in the case d=3, five of the seven conjugacy classes of discrete, vertex-transitive and locally primitive subgroups of \mathrm{Aut}(T_{3}) come from generalised universal groups. Of these five, three arise from groups F' as above while the remaining two do not, see [Tor20, Example 4.39]. The three groups are \Gamma(A_{3}) and \Gamma(S_{3}) and \Gamma_{z}(\Pi(S_{3},\mathrm{sgn},\{1\})). The code example below verifies that \Pi(S_{3},\mathrm{sgn},\{1\})\le\mathrm{Aut}(B_{3,2}) indeed satisfies (C), does not satisfy (D) but admits an involutive compatibility cocycle z, which can be obtained using InvolutiveCompatibilityCocycle (5.3-1).
gap> S3:=SymmetricGroup(3);; gap> rho:=SignHomomorphism(S3);; gap> H:=LocalActionPi(2,3,S3,rho,[1]);; gap> [SatisfiesC(H), SatisfiesD(H), not InvolutiveCompatibilityCocycle(H)=fail]; [ true, false, true ]
We then find that there are four conjugacy classes of subgroups of \mathrm{Aut}(B_{3,3}) that satisfy (C) and project onto \Pi(S_{3},\mathrm{sgn},\{1\}) under the natural projection map \mathrm{Aut}(B_{3,3})\to\mathrm{Aut}(B_{3,2}). Of these four groups, two also satisy (D) and one is conjugate to \Gamma_{z}(\Pi(S_{3},\mathrm{sgn},\{1\})), which we construct using LocalActionGamma (4.1-2).
gap> grps:=ConjugacyClassRepsCompatibleGroupsWithProjection(3,H);; Size(grps); 4 gap> Size(Filtered(grps,SatisfiesD)); 2 gap> z:=InvolutiveCompatibilityCocycle(H);; gap> Size(Intersection(LocalActionGamma(H,z)^AutBall(3,3),grps)); 1
The number of different (involutive) compatibility cocycles that a group F\le\mathrm{Aut}(B_{d,k}) may admit is also mysterious, including in the case k=1. For example, consider the case (d,k)=(4,1). We compute the set of all involutive compatibility cocycles of a local action using the function AllInvolutiveCompatibilityCocycles (5.3-2):
gap> grps:=AllTransitiveGroups(NrMovedPoints,4); [ C(4) = 4, E(4) = 2[x]2, D(4), A4, S4 ] gap> Apply(grps,H->Size(AllInvolutiveCompatibilityCocycles(LocalAction(4,1,H))));; gap> grps; [ 1, 1, 8, 28, 256 ]
From an educational point of view, we envision that UGALY could be used to enhance the learning experience of students in the area of groups acting on trees. The class of generalised universal groups forms an ideal framework for this purpose. For example, to internalise the widely used concept of local actions it may be helpful to take a 2-local action in the form of an automorphism of B_{3,2}, decompose it into its 1-local actions, and recover the original autmorphism from them: in the example below, we start with a random automorphism aut of B_{3,2}. We then compute its 1-local actions at the center vertex, represented by the address [], as well as its neighbours [1], [2] and [3] using LocalAction (2.1-6). Finally, we recover aut from the 1-local actions at the center's neighbours using AssembleAutomorphism (3.2-4), which only requires the local actions at the center's neighbours.
gap> mt:=RandomSource(IsMersenneTwister,1);; gap> aut:=Random(mt,AutBall(3,2)); (1,4,5,2,3,6) gap> aut_center:=LocalAction(1,3,2,aut,[]); (1,2,3) gap> aut_1:=LocalAction(1,3,2,aut,[1]); (1,2,3) gap> aut_2:=LocalAction(1,3,2,aut,[2]); (1,2,3) gap> aut_3:=LocalAction(1,3,2,aut,[3]); (1,3) gap> AssembleAutomorphism(3,1,[aut_1,aut_2,aut_3]); (1,4,5,2,3,6)
The computationally inclined student may also benefit from verifying existing theorems using UGALY. For example, one way to phrase a part of Tutte's work [Tut47] [Tut59] is to say that there are only three conjugacy classes of discrete, locally transitive subgroups of \mathrm{Aut}(T_{3}) that contain an inversion of order 2 and are P_{2}-closed. Due to [Tor20, Corollary 4.38], this can be verified by checking that among all locally transitive subgroups of \mathrm{Aut}(B_{3,2}) which satisfy the compatibility condition (C), only three also satisfy the discreteness condition (D). In the code example below, we start this task by turning the two transitive groups of degree 3, namely A_{3} and S_{3}, into objects of the category IsLocalAction (2.1-1). For each of them we proceed to compute the list of subgroups of \mathrm{Aut}(B_{3,2}) that satisfy (C) and project onto the respective group as before. Now we merely have to go through these lists and check whether or not condition (D) is satisfied. Indeed we find exactly three groups.
gap> A3:=LocalAction(3,1,TransitiveGroup(3,1));; gap> S3:=LocalAction(3,1,TransitiveGroup(3,2));; gap> A3_extn:=ConjugacyClassRepsCompatibleGroupsWithProjection(2,A3); [ Group([ (1,4,5)(2,3,6) ]) ] gap> S3_extn:=ConjugacyClassRepsCompatibleGroupsWithProjection(2,S3); [ Group([ (1,2)(3,5)(4,6), (1,4,5)(2,3,6) ]), Group([ (1,2)(3,4)(5,6), (1,2)(3,5)(4,6), (1,4,5)(2,3,6) ]), Group([ (3,4)(5,6), (1,2)(3,4), (1,4,5)(2,3,6), (3,5,4,6) ]), Group([ (3,4)(5,6), (1,2)(3,4), (1,4,5)(2,3,6), (3,5)(4,6) ]), Group([ (3,4)(5,6), (1,2)(3,4), (1,4,5)(2,3,6), (5,6), (3,5,4,6) ]) ] gap> Apply(A3_extn,SatisfiesD); A3_extn; [ true ] gap> Apply(S3_extn,SatisfiesD); S3_extn; [ true, true, false, false, false ]
It may also be instructive to generate involutive compatibility cocycles computationally and check parts of the axioms manually. In the example below, we first generate the group \Pi(S_{3},\mathrm{sgn},\{1\})\le\mathrm{Aut}(B_{3,2}), which we know admits an involutive compatibility cocycle from before. We then check that z is indeed involutive on a random element a \in\Pi(S_{3},\mathrm{sgn},\{1\}) in direction 1 by checking that z(z(a,1),1)=a.
gap> S3:=SymmetricGroup(3);; gap> rho:=SignHomomorphism(S3);; gap> H:=LocalActionPi(2,3,S3,rho,[1]);; gap> z:=InvolutiveCompatibilityCocycle(H);; gap> mt:=RandomSource(IsMersenneTwister,1);; gap> a:=Random(mt,H); Image(z,[Image(z,[a,1]),1]); (1,5,3)(2,6,4) (1,5,3)(2,6,4)
generated by GAPDoc2HTML