New York Journal of Mathematics

New York J. Math. 8 (2002) 111–131.

Groups Acting on Products of Trees, Tiling Systems and Analytic K-Theory

Jason S. Kimberley and Guyan Robertson

Abstract. Let T_{1} and T_{2} be homogeneous trees of even degree ≥ 4. A BM group Γ is a torsion-free discrete subgroup of Aut(T_{1}) × Aut(T_{2}) which acts freely and transitively on the vertex set of T_{1} × T_{2}. This article studies dynamical systems associated with BM groups. A higher rank Cuntz-Krieger algebra A(Γ) is associated both with a 2-dimensional tiling system and with a boundary action of a BM group Γ. An explicit expression is given for the K-theory of A(Γ). In particular K_{0} = K_{1}. A complete enumeration of possible BM groups Γ is given for a product homogeneous trees of degree 4, and the K-groups are computed.

Contents

1. Introduction 111 2. Products of trees and their automorphisms 112 3. Groups which act freely and transitively on the vertices of Δ 114 4. A 2-dimensional subshift associated with a BM group 117 5. The boundary action 121 6. Examples 126 7. BM groups with degrees m = n = 4 128 References 131

1. Introduction

The structure of a group which acts freely and cocompactly on a tree is well understood. Any such a group is a finitely generated free group. By way of contrast, a group which acts in a similar manner on a product of trees can have remarkably subtle properties. For example, M. Burger and S. Mozes [BM1, BM2] have proved rigidity and arithmeticity results analogous to the theorems of Margulis for lattices in semisimple Lie groups.

Received February 21, 2002. Mathematics Subject Classification. Primary 20E08, 51E24; secondary 46L80. Key words and phrases. group actions, trees, K-theory, C^{∗}-algebras. This research was funded by the Australian Research Council. The second author is also

grateful for the support of the University of Geneva.

111^{ISSN 1076-9803/02}

This article will consider a discrete subgroup Γ of Aut(T_{1}) × Aut(T_{2}) where T_{1}, T_{2} are homogeneous trees of finite degree. In addition, we require that Γ is torsionfree and acts freely and transitively on the vertex set of T_{1} × T_{2}. For simplicity, refer to such a group as a BM group. BM groups were used in [BM1] to exhibit the first known examples of finitely presented, torsion-free, simple groups.

A product of two trees may be regarded as the 1-skeleton of an affine building whose 2-cells are euclidean squares. A BM group Γ acting freely and transitively on the vertex set of T_{1} × T_{2} defines a 2-dimensional tiling system. Associated to this tiling system there is a C^{∗}-algebra A, which is called a rank-2 Cuntz-Krieger algebra in [RS1]. This algebra is isomorphic to a crossed product C^{∗}-algebra A(Γ) arising from a boundary action of Γ. It follows from the results of [RS1] that A(Γ) is purely infinite, simple, unital and nuclear, and is therefore itself classified by its K-theory. This provides the motivation for us to examine the K-theory of these examples in some detail. In Theorem 5.3 we obtain an explicit expression for the Ktheory of A(Γ) analogous to that of [RS2] for algebras associated with Ã_{2} buildings. In particular K_{0} = K_{1} for this algebra. In Proposition 5.4, the class of the identity in K_{0} is shown to be a torsion element.

In Section 6, these issues are examined for several explicit groups. In Section 7 a complete list is given of all BM groups acting on T_{1} × T_{2}, where T_{1}, T_{2} are homogeneous trees of degree four. The abelianizations and K-groups are also computed.

After this article was submitted, we became aware of the work of Diego Rattaggi [Rat], which undertakes a detailed analysis of BM groups, including extensive computations with explicit presentations. We are grateful to him for several helpful comments on this article.

2. Products of trees and their automorphisms

Given a homogeneous tree T, there is a type map τ defined on the vertices of T and taking values in ℤ/2ℤ. To see this, fix a vertex v_{0} ∈ T and define

τ(v) = d(v_{0}, v) (mod 2),

where d(u, v) denotes the usual graph distance between vertices of the tree. The type map partitions the set of vertices into two classes so that two vertices are in the same class if and only if the distance between them is even. Thus the type map is independent of v_{0}, up to addition of 1 (mod 2). Since any automorphism of the tree preserves distances between vertices this observation proves

Lemma 2.1. For each automorphism g of T there exists i ∈ ℤ/2ℤ such that, for every vertex v, τ(gv) = τ(v) + i

Suppose that Δ is the 2 dimensional cell complex associated with a product T_{1} × T_{2} of homogeneous trees. Then Δ is an affine building of type Ã_{1} × Ã_{1} in a natural way [R]. Write u = (u_{1}, u_{2}) for a generic vertex of Δ. There is a type map τ on the vertices of Δ where

τ(v) = (τ(v_{1}), τ(v_{2})) ∈ ℤ/2ℤ × ℤ/2ℤ.

We say that an automorphism g of Δ is type-rotating if there exists (i_{1}, i_{2}) ∈ ℤ/2ℤ × ℤ/2ℤ such that, for each vertex v,

τ(gv) = (τ(v_{1}) + i_{1}, τ(v_{2}) + i_{2}).

The chambers of Δ are geometric squares and each chamber has exactly one vertex of each type. We denote by Aut_{tr}(Δ) the group of type-rotating automorphisms of Δ.

Lemma 2.2. An automorphism g of Δ is type-rotating if and only if it is a Cartesian product of automorphisms of the two trees.

Proof. If we have

g(u_{1}, u_{2}) = (g_{1}u_{1}, g_{2}u_{2})

for automorphisms g_{i} of T_{i} then it follows from Lemma 2.1 that g is type-rotating. Conversely suppose that g is type-rotating. Let (u_{1}, u_{2}) and (u_{1}, u′_{2}) be neighbouring vertices in Δ. Then g(u_{1}, u_{2}) = (x_{1}, x_{2}) and g(u_{1}, u′_{2}) = (x′_{1}, x′_{2}) are neighbouring vertices in Δ and the type-rotating assumption on g means that τ(x_{1}) = τ(x′_{1}). Since neighbouring vertices in T_{1} have distinct types we must have x_{1} = x′_{1}. By induction on d(u_{2}, u′_{2}), we see that the first coordinate of g(u_{1}, u_{2}) is independent of u_{2} ∈ T_{2}. Similarly, the second coordinate of g(u_{1}, u_{2}) is independent of u_{1} ∈ T_{1}. Thus there exist maps g_{1} of T_{1} and g_{2} of T_{2} such that g(u_{1}, u_{2}) = (g_{1}u_{1}, g_{2}u_{2}). Since g is an automorphism of Δ it follows that each g_{i} is an automorphism of T_{i}. Thus g = g_{1} × g_{2} for some automorphisms g_{i} of T_{i}. □

Corollary 2.3. Aut_{tr}(Δ) = Aut(T_{1}) × Aut(T_{2}).

An apartment in Δ is a subcomplex isomorphic to the plane tessellated by squares. See [R, p. 184] for some comments on this and alternative ways of looking at apartments. Denote by V the vertex set of Δ. Any two vertices u, v ∈ V belong to a common apartment. The convex hull, in the sense of buildings, between two vertices u and v is the subset of an apartment containing u and v depicted in Figure 1. The convex hull of u and v is contained in every apartment of Δ which

u •  v • m = 6  n = 3

Figure 1. Convex hull of two vertices.

contains u and v.

Define the distance, d(u, v), between u and v to be the graph theoretic distance on the one-skeleton of Δ. Any path from u to v of length d(u, v) lies in their convex hull, and the union of the vertices in such paths is exactly the set of vertices in the convex hull.

We define the shape σ(u, v) of the ordered pair of vertices (u, v) ∈ V × V to be the pair (m, n) ∈ ℕ × ℕ as indicated in Figure 1. Note that d(u, v) = m + n. The components of σ(u, v) indicate the relative contributions to d(u, v) from the two factors. If v = (v_{1}, v_{2}) and w = (w_{1}, w_{2}) are vertices of Δ, the shape from v to w is

σ(v, w) = (d(v_{1}, w_{1}), d(v_{2}, w_{2}))

where d denotes the usual graph-theoretic distance on a tree. An edge in Δ connects the vertices v and w if σ(v, w) = (0, 1) or σ(v, w) = (1, 0).

Lemma 2.4. Suppose m_{1}, m_{2}, n_{1}, n_{2} ∈ ℕ and σ(u, w) = (m_{1} + m_{2}, n_{1} + n_{2}) for vertices u, w ∈ V. Then there is a unique vertex v ∈ V such that

σ(u, v) = (m_{1}, n_{1}) and σ(v, w) = (m_{2}, n_{2}).

Proof. Such a v ∈ V satisfies d(u, w) = d(u, v)+d(v, w) so it must lie in the convex hull of u and w. Inside the convex hull existence and uniqueness of v are clear. □

It is a direct consequence of the definitions that every type-rotating automorphism g ∈ Aut(Δ) preserves shape in the sense that σ(gu, gv) = σ(u, v) for all u, v ∈ V.

3. Groups which act freely and transitively on the vertices of Δ

Suppose that Γ ≤ Aut_{tr}(Δ) acts freely and transitively on the vertex set V. Fix any vertex v_{0} ∈ V and let

N = {a ∈ Γ ; d(v_{0}, av_{0}) = 1}.

The Cayley graph of Γ constructed via right multiplication with respect to the set N has Γ itself as its vertex set and has {(c, ca) ; c ∈ Γ, a ∈ N} as its edge set. There is a natural action of Γ on its Cayley graph via left multiplication. Using the convention that an undirected edge between vertices u and v in a graph represents the pair of directed edges (u, v) and (v, u), it is immediate that the Γ-map c ↦ cv_{0} from Γ to Δ is an isomorphism between the Cayley graph of Γ and the one-skeleton of Δ. In this way we identify Γ with the vertex set V of Δ. Connectivity of Δ implies that N is a generating set for Γ.

It is traditional to label the directed edge (c, ca) with the generator a ∈ N. More generally, to the pair (c, d) ∈ Γ × Γ we assign the label c^{−1}d. Equivalently, to the pair (c, cd) we assign the label d ∈ Γ. Suppose this label is written as a product of generators; d = a_{1} … a_{j}. Then there is a path (c, ca_{1}, ca_{1}a_{2}, …, cd) from c to cd whose successive edges are labelled a_{1}, …, a_{j}. The left translate of (c, cd) by b ∈ Γ is (bc, bcd) and also carries the label d. Conversely, any pair (c′, c′d) which carries the label d is the left translate by b = c′c^{−1} of (c, cd). Thus two pairs carry the same label if and only if one is the left translate of the other.

We define a shape function on Γ by

σ(b) = σ(v_{0}, bv_{0})

for b ∈ Γ. The pair (c, cb) has label b and its shape, defined via the identification of the Cayley graph and the one-skeleton of Δ, is

σ(c, cb) = σ(cv_{0}, cbv_{0}) = σ(v_{0}, bv_{0}) = σ(b).

A different choice of v_{0} leads to a shape function on Γ which differs from the first by an inner automorphism of Γ.

Definition 3.1. [RRS] Suppose that the group Γ ≤ Aut_{tr}(Δ) acts freely and transitively on V. Then Γ is called an Ã_{1} × Ã_{1} group.

Consider an Ã_{1} × Ã_{1} group Γ. Fix a vertex v_{0} = (v_{1}, v_{2}) ∈ V and suppose that g = g_{1} × g_{2} ∈ Γ. Recall that

σ(g) = σ(v_{0}, gv_{0}) = (d(v_{1}, g_{1}v_{1}), d(v_{2}, g_{2}v_{2})) .

Consider the generating set

N = {g ∈ Γ ; d(v_{0}, gv_{0}) = 1}

of Γ. Let

A = {a ∈ Γ ; σ(a) = (1, 0)} and B = {b ∈ Γ ; σ(b) = (0, 1)}. (3.1)

Lemma 3.2. Each element g ∈ Γ has a unique reduced expression of the form

g = a_{1} … a_{m}b_{1} … b_{n}

and of the form

g = b′_{1} … b′_{n}a′_{1} … a′_{m}

for some a_{i}, a′_{i} ∈ A and b_{i}, b′_{i} ∈ B. Moreover σ(g) = (m, n).

Proof. This follows immediately from Lemma 2.4. □

In [BM1, Section 1], M. Burger and S. Mozes constructed a class of groups which act freely and transitively on the vertices of a product of trees. It is convenient to refer to these groups as BM groups. Our aim now is to show that the class of BM groups coincides with the class of torsion-free Ã_{1} × Ã_{1} groups.

Definition 3.3. [BM1, Section 1] A BM group is defined as follows. Choose sets A, B, with |A| = m, |B| = n where m, n ≥ 4 are even integers. Choose fixed point free involutions a ↦ a^{−1}, b ↦ b^{−1} on A, B respectively and a subset R ⊂ A × B × B × A with the following properties:

(i) If (a, b, b′, a′) ∈ R then each of (a^{−1}, b′, b, a′^{−1}), (a′^{−1}, b′^{−1}, b^{−1}, a^{−1}), and (a′, b^{−1}, b′^{−1}, a) belong to R.

(ii) All four 4-tuples in (i) are distinct. Equivalently (a, b, b^{−1}, a^{−1}) ∉ R for

a ∈ A, b ∈ B. (iii) Each of the four projections of R to a subproduct of the form A × B or B × A

is bijective. Equivalently at least one such projection is bijective. A BM square is defined to be a set of four distinct tuples as in (ii), that is four element subsets of A × B × B × A of the form

{(a, b, b′, a′), (a^{−1}, b′, b, a′^{−1}), (a′^{−1}, b′^{−1}, b^{−1}, a^{−1}), (a′, b^{−1}, b′^{−1}, a)}.

If (a, b, b′, a′) ∈ R then write ab□b′a′.

A BM group Γ has presentation

(3.2) Γ = ⟨A ∪ B ; ab = b′a′ whenever ab□b′a′⟩

In a subsequent article [BM2], a set of objects (A, B, a ↦ a^{−1}, b ↦ b^{−1}, R) satisfying the above conditions is called a VH-datum.

b_{′}  b a a′  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}

Figure 2. A geometric square.

Theorem 3.4. A group Γ is a BM group if and only if it is a torsion-free Ã_{1} × Ã_{1} group.

Proof. Suppose that Γ is a torsion-free Ã_{1} × Ã_{1} group with generating set N = A ∪ B, where A and B are described by equations (3.1). The map c ↦ c^{−1} on N is fixed point free since Γ is torsion-free. Define R to be the set of 4-tuples (a, b, b′, a′) ∈ A × B × B × A such that ab = b′a′. Condition (i) for a BM group is clearly satisfied. To verify Condition (ii) note that if (a, b, b^{−1}, a^{−1}) ∈ R then (ab)^{2} = 1, contradicting the assumption that Γ is torsion-free. Condition (iii) follows immediately from Lemma 3.2.

We now prove the converse. Given a BM group Γ we may construct as in [BM1] a cell complex Y whose fundamental group is Γ. The complex Y has one vertex v and the cells are geometric squares as in Figure 2. There are |A||B|/4 such cells whose four edges form a bouquet of four loops meeting at v. The boundary labels of the directed edges are elements of A ∪ B and edges with the same label are identified in the complex. Definition 3.3(ii) says that none of the cells of Y is a projective plane.

By definition, the link of the vertex v in Y is the graph Lk(v, Y) whose vertices are in 1-1 correspondence with the half-edges incident with v and whose edges are in 1-1 correspondence with the corners incident at v. In our setup the link Lk(v, Y) is a complete bipartite graph with vertex set A ∪ B and an edge between each element of A and each element of B. Intuitively, completeness of this bipartite graph means that there are no “missing corners”. It follows from [BW, Theorem 10.2] that the universal cover of Y is a product of homogeneous trees Δ = T_{1} × T_{2}, where T_{1} has valency |A| and T_{2} has valency |B|. (In the terminology of [BW], Y is said to be a complete VH complex.) Elements of Γ correspond to edge paths in Y. By [BW, Lemma 4.3] each g ∈ Γ can be expressed uniquely in each of the normal forms g = a_{1} … a_{m}b_{1} … b_{n} = b′_{1} … b′_{n}a′_{1} … a′_{m}, for some a_{i}, a′_{i} ∈ A and b_{i}, b′_{i} ∈ B. The 1-skeleton of the universal covering space T_{1} × T_{2} may therefore be identified with the Cayley graph of Γ with respect to the generating set A ∪ B. Thus Γ ⊂ Aut_{tr}(Δ) = AutT_{1} × AutT_{2}, and Y = Γ\Δ.

Let Γ be a BM group with presentation (3.2). In view of the preceding discussion we need only show that Γ is torsion-free. The argument for this is well known [Br, VI.5, p. 161, Theorem], and it was shown to us by Donald Cartwright, in the context of Ã_{2} groups. Suppose that 1 ≠ x ∈ Γ with x^{n} = 1 for some integer n > 0. Let C(x) denote the cyclic group generated by x. Fix a vertex v_{0} of the 1 skeleton of Δ = T_{1} × T_{2}. Then Γv_{0} is the set of vertices of Δ. Now the set C(x)v_{0} is a bounded C(x)-stable subset of Δ. Since the complete metric space Δ satisfies the negative curvature condition of [Br, VI.3b], it follows from the Bruhat-Tits Fixed Point Theorem that there is a C(x)-fixed point p ∈ Δ. Since the action of Γ is free on the vertices of Δ, p cannot be a vertex. Thus p lies in the interior of an edge E or a square S in Δ, and either E or S is invariant under C(x). By considering g^{−1}xg for suitable g ∈ Γ, we may suppose that one vertex of E (respectively S) is v_{0}.

Case 1. E is invariant under C(x). It follows that E has endpoints v_{0},xv_{0} and that x ∈ A ∪ B satisfies x^{2} = 1, contradicting the definition of a BM group. We therefore reduce to:

Case 2. S is invariant under C(x), where S is the square illustrated in Figure 3. Then xv_{0} ≠ v_{0} (since the action is free) and so xv_{0} is one of the other three vertices of S. Thus x = a or x = b′ or x = ab, where a ∈ A,b, b′ ∈ B. If x = a then xav_{0} = a^{2}v_{0} is a vertex of S, which is impossible. Similarly x ≠ b′. Thus x = ab. Again x^{2}v_{0} = ababv_{0} is a vertex of S. According to Lemma 3.2, the only way this can happen is if abab = 1. However this contradicts Condition (ii) in Definition 3.3. This completes the proof of Theorem 3.4. □

b_{′}  b a a′  • • • •  av_{0} b′v_{0} v_{0}  abv_{0}

Figure 3. The square S.

Remark 3.5. The fact that BM groups are torsion-free is an immediate consequence of [BH, Theorem 4.13(2) p. 201]. That much more general result applies to fundamental groups of spaces of non-positive curvature. They are always torsionfree.

4. A 2-dimensional subshift associated with a BM group

Identify elements of Γ with vertices of Δ. The set R may be identified with the set of Γ-equivalence classes of oriented basepointed squares (chambers) in Δ. We refer to such an equivalence class of squares as a tile. We now construct a 2-dimensional shift system associated with Γ.

The transition matrices are defined as follows. If r = (a, b, b′, a′), s = (c, d, d′, c′) ∈ R then define horizontal and vertical transition matrices M_{1}, M_{2} as indicated in Figure 4: that is M_{j}(s, r) = 1 if r and s represent the labels of tiles in Δ which lie as shown in Figure 4, and M_{j}(s, r) = 0 otherwise. The mn × mn matrices M_{1}, M_{2} are nonzero {0, 1}-matrices .

It follows that M_{1}(s, r) = 1 if and only if b = d′ and c ≠ a^{−1}. (The condition c′ ≠ a′^{−1} is redundant, because two adjacent sides of a square uniquely determine it.) See Figure 5. It follows that each row or column of M_{1} has precisely m − 1 nonzero

M_{1}(s, r) = 1  M_{2}(s, r) = 1 r  s  rs

Figure 4. Definition of the transition matrices.

entries. A diagram similar to Figure 5 applies to vertical transition matrices, with the result that each row or column of M_{2} has precisely n − 1 nonzero entries.

r  s_{a}  _{c}^{a′}  ^{c′}^{b}  ^{d}^{b′}  ^{d′}

Figure 5. Definition M_{1}.

We now use R as an alphabet and M_{1}, M_{2} as transition matrices to build up two dimensional words as in [RS1]. Let [m, n] denote {m, m + 1, …, n}, where m ≤ n are integers. If m, n ∈ ℤ^{2}, say that m ≤ n if m_{j} ≤ n_{j} for j = 1, 2, and when m ≤ n, let [m, n] = [m_{1}, n_{1}]×[m_{2}, n_{2}]. In ℤ^{2}, let 0 denote the zero vector and let e_{j} denote the j^{th} standard unit basis vector. If m ∈ ℤ_{+}^{2} = {m ∈ ℤ^{2}; m ≥ 0}, let

W_{m} = {w : [0, m] → R; M_{j}(w(l + e_{j}), w(l)) = 1 whenever l, l + e_{j} ∈ [0, m]}

and call the elements of W_{m} words. Let W = ⋃_{m∈ℤ_{+}^{2}} W_{m}. We say that a word w ∈ W_{m} has shape σ(w) = m, and we identify W_{0} with R in the natural way via the map w ↦ w(0). Define the initial and final maps o : W_{m} → R and t : W_{m} → R by o(w) = w(0) and t(w) = w(m). In order to apply the theory of [RS1] we need to show that the matrices M_{1}, M_{2} satisfy the following conditions: (H0) Each M_{i} is a nonzero {0, 1}-matrix . (H1a) M_{1}M_{2} = M_{2}M_{1}. (H1b) M_{1}M_{2} is a {0, 1}-matrix . (H2) The directed graph with vertices r ∈ R and directed edges (r, s) whenever

M_{i}(s, r) = 1 for some i, is irreducible. (H3) For any nonzero p ∈ ℤ^{2}, there exists a word w ∈ W which is not p-periodic,

i.e., there exists l so that w(l) and w(l + p) are both defined but not equal.

Lemma 4.1. The matrices M_{1}, M_{2} satisfy Conditions (H0), (H1a), (H1b) and (H3).

Proof. (H0): By definition M_{1} and M_{2} are {0, 1}-matrices and they are clearly nonzero.

(H1a,b): Consider the configuration of Figure 6 consisting of chambers lying in some apartment of the building. Given the tiles r_{o}, r_{1}, and r, there is exactly one tile r_{2} which completes the picture. Therefore if (M_{2}M_{1})(r, r_{o}) > 0 then (M_{1}M_{2})(r, r_{o}) = 1. Likewise, if (M_{1}M_{2})(r, r_{o}) > 0, then (M_{2}M_{1})(r, r_{o}) = 1. Conditions (H1a) and (H1b) follow.

r_{o} r_{1} r_{2}  r

Figure 6. A word of shape (1, 1).

(H3): Fix any nonzero p ∈ ℤ^{2}. Choose m ∈ ℤ_{+}^{2} large enough that the rectangle [0, m] contains a point l and its p-translate l + p. We can construct w ∈ W_{m} which is not p-periodic, as follows.

Let w(l) ∈ R be chosen arbitrarily. Now for j = 1, 2 there are at least two choices of r ∈ R such that M_{j}(r, w(l)) = 1 (respectively M_{j}(w(l), r) = 1). Thus one can begin to extend the domain of definition of w in any one of four directions so that there are at least two choices of w(l ± e_{j}), j = 1, 2. By induction, one can extend w in many ways to an element of W_{m}, at each step choosing a particular direction for the extension. In order to do this, first choose arbitrarily a shortest path from l to l + p, and then extend step by step along the path. It is important to note that at each step, w extends uniquely to be defined on a complete rectangle in ℤ^{2}, as illustrated in Figure 7. In that Figure, we assume that w is defined on the rectangle [l, m], and then define w(m + e_{2}) = r, where M_{2}(r, w(m)) = 1. By Conditions (H1a) and (H1b), there is a unique choice of w(m − e_{1} + e_{2}) which is compatible with the values of w(m + e_{2}) and w(m − e_{1}). Continue the process inductively until w is defined uniquely on the whole rectangle [l, m + e_{2}].

[l, m]  ^{m}_{l}  ^{m+e_{2}}^{m−e_{1}}^{m−e_{1}+e_{2}} • • • • •

Figure 7. w(m + e_{2}) determines w on the rectangle [l, m + e_{2}].

Figure 8 illustrates how w is defined on [l, l + p] (where p = (5, 3)), by moving along a certain path from l to l + p. The values of w on this path are given by a sequence of tiles. The values of w up to a certain point on the path determine the values on a rectangle which contains the corresponding initial segment of the path. At the end of the process, the values of w on the path have completely determined the values on [l, l + p]. The final extension from [l, l + p] to the complete rectangle [0, m] is done similarly.

w(l)  w(p)

Figure 8. Definition of w on the rectangle [l, l + p].

At each step, there are at least two different choices for the extension in any direction for which w is not already defined. In particular, one can ensure that w(l + p) ≠ w(l). Therefore w is not p-periodic. □

Lemma 4.2. Consider the directed graph which has a vertex for each r ∈ R and a directed edge from r to s for each i such that M_{i}(s, r) = 1. This graph is irreducible. i.e., Condition (H2) holds.

Proof. Given r_{o}, r_{t} ∈ R we need to find a directed path starting at r_{o} and ending at r_{t}.

There are m − 1 letters r_{1} ∈ R such that M_{1}(r_{1}, r_{o}) = 1. For each such r_{1} there are n − 1 letters r ∈ R such that M_{2}(r, r_{1}) = 1. Since M_{2}M_{1} is a {0, 1}-matrix (equivalently the paths r_{o} → r_{1} → r are distinct) it follows that the set

S_{+}(r_{o}) = {r ∈ R ; w(0, 0) = r_{o} and w(1, 1) = r for some w ∈ W_{(1,1)}}

contains (m − 1)(n − 1) elements. See Figure 6. Similarly the set

S_{−}(r_{t}) = {r ∈ R ; w(0, 0) = r and w(1, 1) = r_{t} for some w ∈ W_{(1,1)}}

contains (m − 1)(n − 1) elements. Since m, n ≥ 4, we have |R| = mn < 2(m − 1)(n − 1) and so there exists r ∈ S_{+}(r_{o}) ∩ S_{−}(r_{t}). It follows that there is a directed path from r_{o} (to r) to r_{t}, as required. □

Associated with the 2-dimensional shift system constructed above there is a finitely generated abelian group defined as follows. The block mn × 2mn matrix (I − M_{1}, I − M_{2}) defines a homomorphism ℤ^{R} ⊕ ℤ^{R} → ℤ^{R}. Define C = coker ^{(I−M_{1},} ^{I−M_{2})} . Thus C can be defined as an abelian group, in terms of generators and relations:

C = C(Γ) = ⟨r ∈ R; r = ∑_{s} M_{j}(s, r)s, j = 1, 2⟩ .

As we shall see, this group plays an important role in classifying the C^{∗}-algebra A(Γ) which is studied in the next section. The next observation will be needed there.

Lemma 4.3. There exists a permutation matrix P : ℤ^{R} → ℤ^{R} such that P^{2} = I and

P M_{j}P = M_{j}^{t}, j = 1, 2.

In particular coker ^{(I−M_{1},} ^{I−M_{2})} = coker ^{(I−M_{1}^{t},} ^{I−M_{2}^{t})} .

Proof. Define p : R → R by p((a, b, b′, a′)) = (a′^{−1}, b′^{−1}, b^{−1}, a^{−1}). (This corresponds to a rotation of the square in Figure 2 through the angle π.) Then M_{j}(s, r) = 1 if and only if M_{j}(p(r), p(s)) = 1. That is M_{j}(s, r) = M_{j}(p(r), p(s)). Let P : ℤ^{R} → ℤ^{R} be the corresponding permutation matrix defined by P e_{p(r)} = e_{r}, where {e_{r} ; r ∈ R} is the standard basis of ℤ^{R}. □

5. The boundary action

A sector in Δ is a \frac{π}{2} -angled sector in some apartment. Two sectors are equivalent (or parallel) if their intersection contains a sector. See Figure 9, where the equivalent sectors with base vertices x, x′ do not necessarily lie in a common apartment, but the shaded subsector is contained in them both.

x x′  ^{.}^{.}^{.} ^{.}^{.}^{.}^{.} ^{.}^{.}^{.} ^{.}^{.}^{.}^{.} ^{.}^{.}^{.} ^{.}^{.}^{.}^{.} ^{.}^{.}^{.} ^{.}^{.}^{.}^{.} ^{.}^{.}^{.} ^{.}^{.}^{.}^{.} ^{.}^{.}^{.} ^{.}^{.}^{.}^{.} ^{.}^{.}^{.} ^{.}^{.}^{.}^{.}

Figure 9. Equivalent sectors containing a common subsector.

The boundary Ω of Δ is defined to be the set of equivalence classes of sectors in Δ. Fix a vertex x. For any ω ∈ Ω there is a unique sector [x, ω) in the class ω having base vertex x, as illustrated in Figure 10 [R, Theorem 9.6].

• x  [x, ω)

Figure 10. A representative sector [x, ω).

Ω is a totally disconnected compact Hausdorff space with a basis for the topology given by sets of the form

Ω(v) = {ω ∈ Ω : [x, ω) contains v}

where v is any fixed vertex of Δ. It is easy to see that Ω is (non canonically) homeomorphic to ∂T_{1} × ∂T_{2}.

Recall from Section 4 that the alphabet R is identified with the set of Γequivalence classes of basepointed chambers in Δ. We refer to such an equivalence class as a tile. Each tile has a unique representative labelled square based at a fixed vertex of Δ, where each edge label is a generator of Γ.

For each vertex y ∈ Δ the convex hull conv(x, y) is a rectangle R in some apartment. Associated with the rectangle R there is therefore a unique word w ∈ W defined by the labellings of the constituent squares of R. Conversely, by construction of the BM group, every word w ∈ W arises in this way. There is thus a natural bijection between the set of rectangles R in Δ based at x and the set of words w ∈ W. Denote by 𝔣(w) the basepointed final chamber (square) in the rectangle R. Thus 𝔣(w) has edge labelling corresponding to t(w) ∈ R. The square 𝔣(w) is oriented, with basepoint chosen to be the vertex closest to the origin x. It is worth recalling that the terminology has been set up so that R = W_{(0,0)}. That is, tiles are words of shape (0, 0).

If w ∈ W, denote by Ω(w) the set of all ω ∈ Ω such that the sector [x, ω) contains the rectangle in Δ based at x, corresponding to the word w. Denote by 1_{Ω(w)} the indicator function of this set. It is clear from the definition of the topology on Ω that 1_{Ω(w)} ∈ C(Ω).

y_{x}  [x, ω)^{𝔣(w)}

Figure 11. The rectangle R = conv(x, y) associated to a word w ∈ W_{(4,1)}, and the sector [x, ω) representing a boundary point ω ∈ Ω(w).

The group Γ acts on Ω and hence on C(Ω) via γ ↦ α_{γ}, where α_{γ}f(ω) = f(γ^{−1}ω), for f ∈ C(Ω), γ ∈ Γ. The algebraic crossed product relative to this action is the ∗- algebra k(Γ, C(Ω)) of functions ϕ : Γ → C(Ω) of finite support, with multiplication and involution given by

ϕ ∗ ψ(γ_{0}) = ∑_{γ∈Γ} ϕ(γ)α_{γ}(ψ(γ^{−1}γ_{0})) and ϕ^{∗}(γ) = α_{γ}(ϕ(γ^{−1})^{∗}).

The full crossed product algebra C(Ω) ⋊ Γ is the completion of the algebraic crossed product in an appropriate norm. There is a natural embedding of C(Ω) into C(Ω)⋊Γ which maps f ∈ C(Ω) to the function taking the value f at the identity of Γ and 0 elsewhere. The identity element 1 of C(Ω) ⋊ Γ is then identified with the constant function 1(ω) = 1, ω ∈ Ω. There is a natural unitary representation π : Γ → C(Ω)⋊Γ, where π(γ) is the function taking the value 1 at γ and 0 otherwise. It is convenient to denote π(γ) simply by γ. Thus a typical element of the dense ∗-algebra k(Γ, C(Ω)) can be written as a finite sum ∑_{γ} f_{γ}γ, where f_{γ} ∈ C(Ω), γ ∈ Γ. The definition of the multiplication implies the covariance relation

α_{γ}(f) = γfγ^{−1} for f ∈ C(Ω), γ ∈ Γ. (5.1)

Theorem 5.1. Let A(Γ) = C(Ω) ⋊ Γ. Then A(Γ) is isomorphic to the rank-2 Cuntz-Krieger algebra A associated with the alphabet R and transition matrices M_{1}, M_{2}, as described in [RS1].

The proof of this result is essentially the same as that given in [RS1, Section 7], in the case of a group of automorphisms of a building of type Ã_{2}.

Here is how the isomorphism is defined. The C^{∗}-algebra A is defined as the universal C^{∗}-algebra generated by a family of partial isometries {s_{u,v}; u, v ∈ W and t(u) = t(v)} satisfying the relations

(5.2a)  s_{u,v}^{∗} = s_{v,u}
(5.2b)  s_{u,v}s_{v,w} = s_{u,w}
(5.2c)  s_{u,v} = ∑_{\begin{matrix}w∈W;σ(w)=e_{j}, \\ o(w)=t(u)=t(v) \end{matrix}} s_{uw,vw}, for 1 ≤ j ≤ r

(5.2d)  s_{u,u}s_{v,v} = 0, for u, v ∈ W_{0}, u ≠ v.

We refer to [RS1, Section 1] for details, in particular for the meaning of the product of words used in (5.2c).

The isomorphism ϕ : A → C(Ω) ⋊ Γ is defined as follows.

If u, v ∈ W with t(u) = t(v) ∈ R, let γ ∈ Γ be the unique element such that γ𝔣(v) = 𝔣(u). The condition t(u) = t(v) means that 𝔣(u), 𝔣(v) lie in the same Γ-orbit, so that γ exists. Moreover γ is unique, since Γ acts freely on Δ. Now define

ϕ(s_{u,v}) = γ1_{Ω(v)} = 1_{Ω(u)}γ. (5.3)

The proof of that ϕ is an isomorphism is exactly the same as the corresponding result for Ã_{2} groups given in [RS1, Section 7]. Here are the essential details.

Equation (5.3) does define a ∗-homomorphism of A because the operators of the form ϕ(s_{u,v}) are easily seen to satisfy the relations (5.2). Since the algebra A is simple [RS1, Theorem 5.9], ϕ is injective. Now observe that 1_{Ω(w)} = ϕ(s_{w,w}). It follows that the range of ϕ contains C(Ω). For the sets Ω(w), w ∈ W, form a basis for the topology of Ω, and so the linear span of {1_{Ω(w)}; w ∈ W } is dense in C(Ω). To show that ϕ is surjective, it therefore suffices to show that the range of ϕ contains Γ. It is clearly enough to show that ϕ(A) contains the generating set A ∪ B for Γ.

Suppose that a ∈ A. Then

a = a.1 = ∑_{w∈W_{(1,0)}} a1_{Ω(w)} ∈ ϕ(A).

Similarly B ⊂ ϕ(A). □

In view of Lemmas 4.1, 4.2, the following is an immediate consequence of [RS1, Proposition 5.11, Theorem 5.9, Corollary 6.4 and Remark 6.5].

Theorem 5.2. The C^{∗}-algebra A(Γ) is purely infinite, simple and nuclear. Moreover it satisfies the Universal Coefficient Theorem.

It also follows from [RS1] that A(Γ) satisfies the U.C.T., hence it is classified by its K-theory, together with the class [1] of its identity element in K_{0}. It is therefore of interest to determine the K-theory of A(Γ). The matrices (I − M_{1}, I − M_{2}) and (I − M_{1}^{t}, I − M_{2}^{t}) define homomorphisms ℤ^{R} ⊕ ℤ^{R} → ℤ^{R}. The K-theory of A(Γ) can be expressed as follows [RS2], where G^{tors} denote the torsion part of a finitely generated abelian group G, and rank(G) denotes the rank of G:

rank(K_{0}(A(Γ))) = rank(K_{1}(A(Γ)))
= rank(coker ^{(I−M_{1},} ^{I−M_{2})} ) + rank(coker ^{(I−M_{1}^{t},} ^{I−M_{2}^{t})} )
K_{0}(A(Γ))^{tors} ≅ coker ^{(I−M_{1},} ^{I−M_{2})}^{tors}
K_{1}(A(Γ)^{tors} ≅ coker ^{(I−M_{1}^{t},} ^{I−M_{2}^{t})}^{tors}.

Recall that we defined C = C(Γ) = coker ^{(I−M_{1},} ^{I−M_{2})} . The next result therefore follows from Lemma 4.3.

Theorem 5.3. If Γ is a BM group then

K_{0}(A(Γ)) = K_{1}(A(Γ)) = C ⊕ ℤ^{rank(C)}. (5.4)

The identity element in A(Γ) is denoted by 1. As is the case for similar algebras [RS2, Proposition 5.4], [Ro2], the class [1] has torsion in K_{0}(A(Γ)). In the present setup we can be much more precise. For notational convenience, let α = \frac{m}{2}, β = \frac{n}{2} and let ρ = gcd(α − 1, β − 1).

Proposition 5.4. Let [1] be the class in K_{0}(A(Γ)) of the identity element of A(Γ), where Γ is a BM group. Then ρ · [1] = 0.

(a) If ρ is odd, then the order of [1] is precisely ρ.

(b) If ρ is even, then the order of [1] is either ρ or \frac{ρ}{2}.

The proof of this result depends upon an examination of explicit projections in A(Γ).

If c is an oriented basepointed square in Δ with base vertex v_{0}, let Ω(c) denote the clopen subset of Ω consisting of all boundary points with representative sector having initial square c and initial vertex v_{0}. The indicator function p_{c} of the set Ω(c) is continuous and so lies in C(Ω) ⊂ C(Ω) ⋊ Γ. See Figure 12. The covariance relation (5.1) implies that the class of p_{c} in K_{0}(A(Γ)) depends only on the Γequivalence class of the oriented basepointed square c. Recall that we identify such a Γ-equivalence class with a tile r ∈ R. It is therefore appropriate to denote the class of p_{c} in K_{0}(A(Γ)) by [r].

Similarly, to each a ∈ A and b ∈ B we can associate elements [a], [b] ∈ K_{0}(A(Γ)). For example, if a ∈ A, fix a directed edge labelled by the element a ∈ A and consider the set of all boundary points ω with representative sector having initial square c containing that edge, as in Figure 12. As above, the class in K_{0}(A(Γ)) of the characteristic function of this set depends only on the label a, and may be denoted by [a]. The class [b] ∈ K_{0}(A(Γ)) for b ∈ B is defined similarly.

Recall now the following result:

Lemma 5.5. [R, Lemma 9.4] Given any chamber c ∈ Δ and any sector S in Δ, there exists a sector S_{1} ⊂ S such that S_{1} and c lie in a common apartment.

._{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}•  [v_{0}, ω)_{a}_{b} c_{v_{0}}

Figure 12. A sector representing ω ∈ Ω(c).

It follows by considering parallel sectors in an appropriate apartment that if e = [v_{0}, v_{1}] is a directed edge in Δ and if ω ∈ Ω, then ω has a representative sector S that lies relative to e in one of the two positions in Figure 13, in some apartment containing them both.

•  S = [v_{0}, ω)_{e}_{v_{0}}  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}  •  S = [v_{1}, ω)_{e}_{v_{1}}  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}

Figure 13. Relative positions of a directed edge and a representative sector.

Let p_{e} denote the characteristic function of the set of points ω ∈ Ω such that e is contained in [v_{0}, ω), as in the left hand diagram. Let \overline{p}_{e} denote the characteristic function of the set of points ω ∈ Ω such that e is contained in [v_{1}, ω), as in the right hand diagram. It follows that p_{e}, \overline{p}_{e} are idempotents in A(Γ) and 1 = p_{e} +\overline{p}_{e}. If the edge e has label a ∈ A (respectively b ∈ B) then in K_{0}(A(Γ)), [p_{e}] = [a] and [\overline{p}_{e}] = [a^{−1}] (respectively [p_{e}] = [b] and [\overline{p}_{e}] = [b^{−1}]).

We therefore obtain

\begin{aligned}[1] & = [a] + [a^{−1}],  a ∈ A \\ & = [b] + [b^{−1}],  b ∈ B. \end{aligned} (5.5)

The relations (5.5) imply that

\begin{aligned}α[1] & = ∑_{a∈A}[a], \\ β[1] & = ∑_{a∈B}[b]. \end{aligned}

Also, each boundary point ω has a unique representative sector based at a fixed vertex v_{0} with initial edges as in Figure 12. It follows that

[1] = ∑_{a∈A}[a] = ∑_{b∈B}[b].

Therefore

[1] = α[1] = β[1],

from which it follows that ρ · [1] = 0, thus proving the first assertion in Proposition 5.4.

In order to obtain a lower bound for the order of the class [1] in K_{0}(A(Γ)) we need to use the fact (proved in [RS2]) that the map r ↦ [r] is a monomorphism from the abstract group

C = ⟨r ∈ R; r = ∑_{s} M_{j}(s, r)s, j = 1, 2⟩

onto a direct summand of K_{0}(A(Γ)). The class [1] is the image of the element e = ∑_{r∈R} r under this map. Moreover each column of the matrix M_{1} (respectively

M_{2}) has (m − 1) (respectively (n − 1)) nonzero terms. (See Section 4.)

Let k = 2ρ = gcd(m − 2, n − 2), and define a map ϕ : C → ℤ/kℤ by ϕ(r) = 1 + ℤ/kℤ. The map ϕ is well defined since each relation in the presentation of C expresses a generator r as a sum of (m − 1) or (n − 1) other generators. Also ϕ(e) = mn+ℤ/kℤ = 4+ℤ/kℤ, since (m−2)(n−2) = mn−2(m−2)−2(n−2)−4. There are now two cases to consider:

(a) Suppose that ρ is odd. Then ϕ(e) has order ρ in ℤ/kℤ. Therefore the order of e in C is divisible by ρ and hence equal to ρ.

(b) Suppose that ρ is even. Then ϕ(e) has order \frac{ρ}{2} in ℤ/kℤ. Therefore the order of e in C is divisible by \frac{ρ}{2}. □

Remark 5.6. It is tempting to conjecture that the order of the class [1] is always precisely ρ. As we shall see below, there is some supporting evidence for this. There is also computational evidence that rank(C) = rank(H_{2}(Γ)), that is rank(K_{0}(A(Γ))) = 2 rank(H_{2}(Γ)).

Remark 5.7. Recall from Theorem 5.2 that A(Γ) is a p.i.s.u.n. C^{∗}-algebra satisfying the UCT. Furthermore, by Theorem 5.3,

K_{0}(A(Γ)) = K_{1}(A(Γ)) = ℤ^{2n} ⊕ T

where T is a finite abelian group. It follows from [Ro1, Proposition 7.3] that A(Γ) is stably isomorphic to A_{1} ⊗ A_{2}, where A_{1}, A_{2} are simple rank one Cuntz-Krieger algebras and K_{0}(A_{2}) = K_{1}(A_{2}) = ℤ.

6. Examples

In this section we consider some examples of BM groups Γ and the results of the computations for the group C = C(Γ). It is useful to relate our results to the Euler-Poincaré characteristic χ(Γ), which is the alternating sum of the ranks of the groups H_{i}(Γ). The finite cell complex Γ\Δ is a K(Γ, 1) space and Γ has homological dimension at most two, so that H_{2}(Γ) is free abelian and H_{i}(Γ) = 0 for i > 2 . It follows that χ(Γ) coincides with the usual Euler-Poincaré characteristic of the cell complex Y = Γ\Δ. Explicitly, χ(Γ) = (α − 1)(β − 1), where m = 2α and n = 2β.

Example 6.1. Suppose that Γ is a direct product of free groups of ranks α and β, acting on a product Δ of homogeneous trees of degrees m = 2α and n = 2β respectively. Then direct computation shows that

K_{0}(A(Γ)) = ℤ^{2αβ} ⊕ (ℤ/(β − 1)ℤ)^{α} ⊕ (ℤ/(α − 1)ℤ)^{β} ⊕ ℤ/ρℤ

where ρ = gcd(α−1, β−1) is the order of the class [1]. For this group, H_{2}(Γ) = ℤ^{αβ}, and the conjectures of Remark 5.6 are verified.

In this example A(Γ) is actually isomorphic in a natural way to a tensor product of Cuntz-Krieger algebras. In fact, by a result of J. Spielberg [Ro1, Section 1], the action of a free group 𝔽_{α} on the boundary of its Cayley graph gives rise a Cuntz-Krieger algebra A(𝔽_{α}). It is easy to check that A(Γ) ≅ A(𝔽_{α}) ⊗ A(𝔽_{β}). (Cf. Remark 5.7.) The formula for K_{0}(A(Γ)) can thus also be verified using the Künneth Theorem for tensor products.

Example 6.2. Consider some specific examples studied in [M, Section 3]. If p, l ≡ 1 (mod 4) are two distinct primes, Mozes constructs a lattice subgroup Γ_{p,l} of G = PGL_{2}(ℚ_{p})×PGL_{2}(ℚ_{l}). The building Δ of G is a product of two homogeneous trees T_{1}, T_{2} of degrees (p + 1) and (l + 1) respectively. The group Γ_{p,l} is a BM group which acts freely and transitively on the vertex set of Δ, but Γ_{p,l} is not a product of free groups. In fact Γ_{p,l} is an irreducible lattice in G.

Here is how Γ_{p,l} is constructed [M]. Let ℍ(ℤ) = {α = a_{0}+a_{1}i+a_{2}j+a_{3}k; a_{j} ∈ ℤ}, the ring of integer quaternions. Let i_{p} be a square root of −1 in ℚ_{p} and define

ψ : ℍ(ℤ) → PGL_{2}(ℚ_{p}) × PGL_{2}(ℚ_{l})

by

ψ(a_{0} + a_{1}i + a_{2}j + a_{3}k) = ([\begin{matrix}a_{0} + a_{1}i_{p} & a_{2} + a_{3}i_{p} \\ −a_{2} + a_{3}i_{p} & a_{0} − a_{1}i_{p} \end{matrix}] , [\begin{matrix}a_{0} + a_{1}i_{l} & a_{2} + a_{3}i_{l} \\ −a_{2} + a_{3}i_{l} & a_{0} − a_{1}i_{l} \end{matrix}]) .

Let Γ̃_{p,l} = {α = a_{0}+a_{1}i+a_{2}j+a_{3}k ∈ ℍ(ℤ); a_{0} ≡ 1 (mod 2), a_{j} ≡ 0 (mod 2), j = 1, 2, 3, |α|^{2} = p^{r}l^{s}}. Then Γ_{p,l} = ψ(Γ̃_{p,l}) is a torsion-free cocompact lattice in G. Let

A = {a = a_{0} + a_{1}i + a_{2}j + a_{3}k ∈ Γ̃_{p,l}; a_{0} > 0, |a|^{2} = p} ,
B = {b = b_{0} + b_{1}i + b_{2}j + b_{3}k ∈ Γ̃_{p,l}; b_{0} > 0, |b|^{2} = l} .

Then A contains p + 1 elements and B contains l + 1 elements. The images \underline{A}, \underline{B} of A, B in Γ_{p,l} generate free groups Γ_{p}, Γ_{l} of orders \frac{p+1}{2}, \frac{l+1}{2} respectively and Γ_{p,l} itself is generated by \underline{A} ∪ \underline{B}. The product T_{1} × T_{2} is the Cayley graph of Γ_{p,l} relative to this set of generators.

The group Γ_{p,l} is a BM group and ρ = \frac{1}{2} gcd(p − 1, l − 1) is even. Explicit computations, using the formula (5.4) and the MAGMA computer algebra package, show that the order of [1] is ρ in each of the 28 groups Γ_{p,l} where p, l ≡ 1 (mod 4) are two distinct primes ≤ 61.

The normal subgroup theorem [BM2, Theorem 4.1] can be applied to Γ_{p,l}, if the Legendre symbol ( \begin{matrix}p \\ l \end{matrix}) = 1. For, using the notation of [BM2, Section 2.4] and [BM3, Remarks following Proposition 1.8.1], the group H_{p}^{∞} = PSL_{2}(ℚ_{p}) has finite index in H_{p} = \overline{pr_{p}(Γ_{p,l})}. Moreover H_{p} is locally ∞ transitive. Thus the hypotheses of [BM2, Theorem 4.1] are satisfied.

Applying [BM2, Theorem 4.1] to the commutator subgroup [Γ_{p,l}, Γ_{p,l}] of Γ_{p,l} shows that the abelianization H_{1}(Γ_{p,l}) = Γ_{p,l}/[Γ_{p,l}, Γ_{p,l}] is finite.

The Euler-Poincaré characteristic of Γ_{p,l} is χ = χ(Γ_{p,l}) = \frac{(p−1)(l−1)}{4}. Thus χ(Γ_{p,l}) = rank H_{0}(Γ_{p,l})+rank H_{2}(Γ_{p,l}) and so H_{2}(Γ_{p,l}) = ℤ^{χ−1}. Explicit computations for the same range of values of p, l as above shows that the second conjecture of Remark 5.6 is also verified in these cases.

Another experimental observation is the following. Checking through a large number of values of the pairs of primes (p, l) congruent to 1 mod 4, one sees that the abelianization of Γ_{p,l} seems to depend only the greatest common divisor r = gcd((p − 1)/4, (l − 1)/4, 6). In fact we conjecture that

H_{1}(Γ_{p,l}) = \begin{cases}ℤ/2ℤ ⊕ (ℤ/4ℤ)^{3} & if r = 1, \\ (ℤ/2ℤ)^{3} ⊕ (ℤ/8ℤ)^{2} & if r = 2, \\ ℤ/2ℤ ⊕ ℤ/3ℤ ⊕ (ℤ/4ℤ)^{3} & if r = 3, \\ (ℤ/2ℤ)^{3} ⊕ ℤ/3ℤ ⊕ (ℤ/8ℤ)^{2} & if r = 6. \end{cases}

The validity of this formula was checked for all values of the pair (p, l) up to (73, 97), and for several other values.

7. BM groups with degrees m = n = 4

A BM group acts on a product of homogeneous trees T_{1} × T_{2}, where T_{1} has degree m = 2α ≥ 4 and T_{2} has degree n = 2β ≥ 4. We now examine the simplest case m = n = 4.

Recall that a BM square is a set of four distinct tuples

{(a, b, b′, a′), (a^{−1}, b′, b, a′^{−1}), (a′^{−1}, b′^{−1}, b^{−1}, a^{−1}), (a′, b^{−1}, b′^{−1}, a)}.

contained in A × B × B × A, as in Definition 3.3(i),(ii). In the presentation (3.2), a BM group has 4αβ generators and a set of relations which we call a set of BM relations. Possible sets of BM relations correspond to those unions of αβ BM squares whose images under a projection chosen from Definition 3.3(iii) are disjoint.

Choose once and for all such a projection, say (a, b, b′, a′) ↦ (a, b). Consider the graph 𝔊 whose vertices are the BM squares and whose edges join BM squares having disjoint images under the chosen projection. Possible sets of BM relations correspond to cliques (complete subgraphs) of size αβ in the graph 𝔊. The computer algebra package MAGMA contains a dynamic programming algorithm due to [MPW] for finding all cliques of a given size.

For α = β = 2 there are 541 cliques in 𝔊 of size 4. Say that two of the corresponding presentations are equivalent if one may be obtained from the other by permuting the generators. There are precisely 52 equivalence classes of presentations. In the tables below we list 52 representative presentations, together with the structure of the groups H_{1}(Γ) and C(Γ). For BM groups Γ with semi-degrees α = β = 2, we have χ(Γ) = 1. Thus rank H_{1}(Γ) = rank H_{2}(Γ). Therefore the tables show that the conjectures of Remark 5.6 are verified for all such groups.

In the tables, each of the 52 groups arising from these presentations is assigned a name Γ = 2 × 2.j. Using an algorithm due to C. C. Sims [S], which is implemented in the MAGMA package, we have found the indices and lengths of all conjugacy classes of subgroups with index at most 8 in each of these 52 groups. From these data we have checked that the only possible isomorphisms between 2 × 2.j and 2 × 2.k occur if both j and k lie in one of the following sets:

{1, 17}, {3, 19}, {4, 30}, {5, 10}, {7, 21}, {26, 46}, {27, 29, 45}, {28, 43, 47}, {42, 44}.

Thus, amongst the 52 groups 2 × 2.j, there are at least 41 non-isomorphic groups.

The quotient complexes Y = (T_{1} ×T_{2})/Γ corresponding to the groups Γ = 2×2.j with j in any of these sets are not homeomorphic, as can be seen by considering the fundamental groups of one point deletion subspaces of Y. One therefore obtains 52 pairwise non-homeomorphic complexes Y. Of course, this does not imply that the groups Γ are non-isomorphic. In fact, we have discovered Tietze transformations showing that, if {j, k} is contained in any one of the listed sets, except for {4, 30} or {5, 10}, then the corresponding groups are isomorphic. There are thus at most 43 non-isomorphic groups. We do not know whether the groups 2 × 2.j and 2 × 2.k are isomorphic in the two cases {j, k} = {4, 30} and {j, k} = {5, 10}. Note that the shift system group C(Γ) depends only on Γ and not on the presentation of Γ.

The following notation is used in the tables. The group Γ is generated by A ∪ B where A = {1, −1, 2, −2} and B = {3, −3, 4, −4}. The fixed point free involution on each of these sets is given by x ↦ −x. Thus x^{−1} is denoted −x. Moreover the relations are written in the form abb′a′ = 1 rather than the form ab = b′a′ used in Definition 3.3. For example, the first relation for the presentation of group 2 × 2.01 is (1)(3)(1)(3)^{−1} = 1. The tables are simplified by use of the abbreviations:

m [a, b, ...] means ℤ^{m} ⊕ ℤ/aℤ ⊕ ℤ/bℤ ⊕ …;

(j)a means a, a, ..., a with j repetitions.
Group Presentation  H_{1} (Γ)  C (Γ)
2x2.01 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & +2 & −3 & +2 & +4 & +2 & −4 \end{matrix} 2[(2) 2]  2[(2) 4]
2x2.02 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & +2 & −3 & +2 & +4 & −2 & +4 \end{matrix} 1[(3) 2]  1[(3) 4]
2x2.03 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & +2 & −3 & +2 & +4 & −2 & −4 \end{matrix} 2[(2) 2]  2[(2) 4]
2x2.04 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & +2 & +4 & +2 & −3 & +2 & −4 \end{matrix} 1[2, 4]  1[2, 4, 8]
2x2.05 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & −2 & +3 & +2 & +4 & −2 & +4 \end{matrix} 1[(3) 2]  1[(3) 4]
2x2.06 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & −2 & +3 & +2 & +4 & −2 & −4 \end{matrix} 2[(2) 2]  2[(2) 4]
2x2.07 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & −2 & −3 & +2 & +4 & −2 & −4 \end{matrix} 3[2]  3[4]
2x2.08 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & +3 \end{matrix} 2[2]  2[2, 4]
2x2.09 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +1 & −4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & −3 \end{matrix} 1[(2) 2]  1[(2) 2, 4]
2x2.10 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & +4 \\ +2 & +3 & +2 & −3 & +2 & +4 & −2 & −4 \end{matrix} 1[(3) 2]  1[(3) 4]
2x2.11 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & +4 \\ +2 & +3 & +2 & +4 & +2 & −3 & +2 & −4 \end{matrix} 0[(2) 2, 4] 0[(2) 4, 8]
2x2.12 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & +4 \\ +2 & +3 & −2 & +3 & +2 & +4 & +2 & −4 \end{matrix} 0[(4) 2]  0[(2) 2, (3) 4]
2x2.13 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & +4 \\ +2 & +3 & −2 & +3 & +2 & +4 & −2 & −4 \end{matrix} 1[(3) 2]  1[(3) 4]
2x2.14 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & +4 \\ +2 & +3 & −2 & −3 & +2 & +4 & −2 & −4 \end{matrix} 2[(2) 2]  2[(2) 4]
2x2.15 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & +4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & +3 \end{matrix} 1[(2) 2]  1[(2) 4]
2x2.16 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & +4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & −3 \end{matrix} 1[(2) 2]  1[(2) 4]

130 Jason S. Kimberley and Guyan Robertson

Group Presentation  H_{1} (Γ)  C (Γ)
2x2.17 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & +2 & −3 & +2 & +4 & −2 & −4 \end{matrix} 2[(2) 2]  2[(2) 4]
2x2.18 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & +2 & +4 & +2 & −3 & +2 & −4 \end{matrix} 1[2, 4]  1[2, 4, 8]
2x2.19 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & −2 & −3 & +2 & +4 & +2 & −4 \end{matrix} 2[(2) 2]  2[(2) 4]
2x2.20 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & −2 & −3 & +2 & +4 & −2 & +4 \end{matrix} 2[(2) 2]  2[(2) 4]
2x2.21 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & −2 & −3 & +2 & +4 & −2 & −4 \end{matrix} 3[2]  3[4]
2x2.22 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & +3 \end{matrix} 2[2]  2[2, 4]
2x2.23 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & −3 \end{matrix} 1[(2) 2]  1[(2) 2, 4]
2x2.24 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +2 & +4 \\ +1 & −4 & +2 & −4 & +2 & +3 & +2 & −3 \end{matrix} 1[2, 4]  1[(2) 2, 8]
2x2.25 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +2 & +4 \\ +1 & −4 & +2 & −4 & +2 & +3 & −2 & −3 \end{matrix} 1[2, 4]  1[(2) 2, 8]
2x2.26 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +2 & −4 \\ +1 & −4 & +2 & +4 & +2 & +3 & +2 & −3 \end{matrix} 2[2]  2[(2) 2]
2x2.27 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +2 & −4 \\ +1 & −4 & +2 & +4 & +2 & +3 & −2 & −3 \end{matrix} 2[2]  2[(2) 2]
2x2.28 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +2 & −4 \\ +1 & −4 & −2 & +4 & +2 & +3 & +2 & −3 \end{matrix} 2[2]  2[(2) 2]
2x2.29 \begin{matrix}+1 & +3 & +1 & −3 & +1 & +4 & +2 & −4 \\ +1 & −4 & −2 & +4 & +2 & +3 & −2 & −3 \end{matrix} 2[2]  2[(2) 2]
2x2.30 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +1 & −4 \\ +2 & +3 & +2 & +4 & +2 & −3 & +2 & −4 \end{matrix} 1[2, 4]  1[2, 4, 8]
2x2.31 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +1 & −4 \\ +2 & +3 & +2 & −4 & +2 & −3 & +2 & +4 \end{matrix} 0[2, (2) 4]  0[(2) 2, (2) 8]
2x2.32 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +1 & −4 \\ +2 & +3 & −2 & −3 & +2 & +4 & −2 & −4 \end{matrix} 2[4]  2[2, 8]
2x2.33 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +1 & −4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & +3 \end{matrix} 2[2]  2[2, 4]
2x2.34 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +1 & −4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & −3 \end{matrix} 1[(2) 2]  1[(2) 2, 4]
2x2.35 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +1 & −4 \\ +2 & +3 & −2 & −4 & +2 & +4 & −2 & −3 \end{matrix} 1[2, 4]  1[(2) 2, 8]
2x2.36 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +2 & −3 \\ +1 & −4 & +2 & −4 & +2 & +3 & +2 & +4 \end{matrix} 0[4, 8]  0[(2) 2, 4, 8]
2x2.37 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +2 & −3 \\ +1 & −4 & −2 & −4 & +2 & +3 & +2 & −4 \end{matrix} 0[(2) 2, (2) 3] 0[(2) 4, (2) 3]
2x2.38 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +2 & −4 \\ +1 & −4 & +2 & −3 & +2 & +3 & +2 & +4 \end{matrix} 1[8]  1[(2) 2, 8]
2x2.39 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +2 & −4 \\ +1 & −4 & −2 & −3 & +2 & +3 & −2 & +4 \end{matrix} 1[2]  1[(3) 2]
2x2.40 \begin{matrix}+1 & +3 & +1 & +4 & +1 & −3 & +2 & −4 \\ +1 & −4 & −2 & −3 & +2 & +3 & −2 & −4 \end{matrix} 0[(2) 2, 3]  0[(2) 2, 4, 3]
2x2.41 \begin{matrix}+1 & +3 & −1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & −2 & −3 & +2 & +4 & −2 & −4 \end{matrix} 4[]  4[]
2x2.42 \begin{matrix}+1 & +3 & −1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & +3 \end{matrix} 3[]  3[2]
2x2.43 \begin{matrix}+1 & +3 & −1 & −3 & +1 & +4 & −1 & −4 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & −3 \end{matrix} 2[2]  2[(2) 2]
2x2.44 \begin{matrix}+1 & +3 & −1 & +4 & +1 & +4 & −1 & +3 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & +3 \end{matrix} 3[]  3[2]
2x2.45 \begin{matrix}+1 & +3 & −1 & +4 & +1 & +4 & −1 & +3 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & −3 \end{matrix} 2[2]  2[(2) 2]
2x2.46 \begin{matrix}+1 & +3 & −1 & +4 & +1 & +4 & −1 & +3 \\ +2 & +3 & −2 & −4 & +2 & +4 & −2 & −3 \end{matrix} 2[2]  2[(2) 2]
2x2.47 \begin{matrix}+1 & +3 & −1 & +4 & +1 & +4 & −1 & −3 \\ +2 & +3 & −2 & +4 & +2 & +4 & −2 & −3 \end{matrix} 2[2]  2[(2) 2]
2x2.48 \begin{matrix}+1 & +3 & −1 & +4 & +1 & +4 & +2 & +3 \\ +1 & −4 & +2 & −3 & +2 & +4 & −2 & +3 \end{matrix} 2[]  2[(2) 2]
2x2.49 \begin{matrix}+1 & +3 & −1 & +4 & +1 & +4 & +2 & +3 \\ +1 & −4 & +2 & −3 & +2 & +4 & −2 & −3 \end{matrix} 1[2]  1[2, 4]
2x2.50 \begin{matrix}+1 & +3 & −1 & +4 & +1 & +4 & +2 & −3 \\ +1 & −4 & +2 & +3 & +2 & +4 & −2 & +3 \end{matrix} 1[4]  1[(2) 2, 4]
2x2.51 \begin{matrix}+1 & +3 & +2 & +4 & +1 & −3 & +2 & −4 \\ +1 & +4 & +2 & +3 & +1 & −4 & +2 & −3 \end{matrix} 2[2]  2[2, 4]
2x2.52 \begin{matrix}+1 & +3 & +2 & +4 & +1 & −3 & +2 & −4 \\ +1 & +4 & +2 & −3 & +1 & −4 & +2 & +3 \end{matrix} 1[(2) 2]  1[(2) 2, 4]

Groups Acting on Products of Trees 131

References

[BM1] M. Burger and S. Mozes, Finitely presented groups and products of trees, C.R. Acad. Sci. Paris, Sér. 1, 324 (1997), 747–752, MR 98g:20041, Zbl 0966.20013.

[BM2] M. Burger and S. Mozes, Lattices in product of trees, Inst. Hautes Études Sci. Publ. Math., 92 (2001), 151–194, MR 2002i:20042.

[BM3] M. Burger and S. Mozes, Groups acting on trees: from local to global structure, Inst. Hautes Études Sci. Publ. Math., 92 (2001), 113–150, MR 2002i:20041.

[BH] M. R. Bridson and A. Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften, 319, Springer-Verlag, Berlin, 1999, MR 2000k:53038.

[BW] M. R. Bridson and D. T. Wise, VH complexes, towers and subgroups of F × F, Math. Proc. Camb. Phil. Soc., 126 (1999), 481–497, MR 2000c:20050, Zbl 0942.20009.

[Br] K. Brown, Buildings, Springer-Verlag, New York 1989, MR 90e:20001, Zbl 0922.20034.

[M] S. Mozes, Actions of Cartan subgroups, Israel J. Math., 90 (1995), 253–294, MR 97b:22022, Zbl 0851.22020.

[MPW] W. Myrvold, T. Prsa and N. Walker, A dynamic programming approach for timing and designing clique algorithms, Algorithms and Experiments (ALEX ’98): Building Bridges Between Theory and Applications, 1998, 88–95, http://www.csr.uvic.ca/∼wendym/pubs.html.

[Rat] D. Rattaggi, Examples of square complexes, preprint, ETH Zürich, 2002.

[R] M. Ronan, Lectures on Buildings, Academic Press, San Diego, 1989, MR 90j:20001, Zbl 0694.51001.

[Ro1] G. Robertson, Boundary actions for affine buildings and higher rank Cuntz-Krieger algebras. C^{∗}-algebras: Proceedings of the SFB Workshop on C^{∗}-algebras (Münster, March 8–12, 1999), 182–202, Springer-Verlag, 2000, MR 2001j:46082.

[Ro2] G. Robertson, Torsion in K-theory for boundary actions on affine buildings of type Ã_{n}, K-theory, 22 (2001), 251–269, CMP 1 837 234.

[RRS] J. Ramagge, G. Robertson and T. Steger, A Haagerup inequality for Ã_{1} × Ã_{1} and Ã_{2} buildings, Geometric and Funct. Anal., 8 (1998), 702–731, MR 99j:20046, Zbl 0906.43009.

[RS1] G. Robertson and T. Steger, Affine buildings, tiling systems and higher rank Cuntz-Krieger algebras, J. Reine Angew. Math., 513 (1999), 115–144, MR 2000j:46109.

[RS2] G. Robertson and T. Steger, Asymptotic K-theory for groups acting on Ã_{2} buildings, Canadian Math. J., 53 (2001), 809–833, MR 2002f:46141.

[S] C.C. Sims, Computation with Finitely Presented Groups, Encyclopaedia of Mathematics and its Applications 48, Cambridge University Press, 1994, MR 95f:20053, Zbl 0828.20001.

Mathematics Department, University of Newcastle, Callaghan, NSW 2308, Australia

guyan@maths.newcastle.edu.au http://www.maths.newcastle.edu.au/∼guyan/ jascki@iprimus.com.au

This paper is available via http://nyjm.albany.edu:8000/j/2002/8-7.html.