Coxeter groups, Salem numbers and the Hilbert metric
Curtis T. McMullen September 17, 2005

Contents
1 2 3 4 5 6 7 Introduction . . . . . . . . . . . . . . . . Translation length in the Hilbert metric Coxeter groups and the Tits cone . . . . Coxeter elements . . . . . . . . . . . . . Bipartite Coxeter diagrams . . . . . . . Minimal hyperbolic diagrams . . . . . . Small Salem numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6 12 16 19 23 29

Research supported in part by the NSF. 2000 Mathematics Subject Classification: Primary 20F55, 11R06; Secondary 53C60.

1

Introduction

The shortest loop traced out by a billiard ball in an acute triangle is the pedal subtriangle, connecting the feet of the altitudes. In this paper we prove a similar result for loops in the fundamental polyhedron of a Coxeter group W , and use it to study the spectral radius λ(w), w ∈ W for the geometric action of W . In particular we prove: Theorem 1.1 Let (W, S) be a Coxeter system and let w ∈ W . Then either λ(w) = 1 or λ(w) ≥ λLehmer ≈ 1.1762808. Here λLehmer denotes Lehmer’s number, a root of the polynomial 1 + x − x3 − x4 − x5 − x6 − x7 + x9 + x10 (1.1)

and the smallest known Salem number. Billiards. Recall that a Coxeter system (W, S) is a group W with a finite generating set S = {s1 , . . . , sn }, subject only to the relations (si sj )mij = 1, where mii = 1 and mij ≥ 2 for i = j. The permuted products sσ1 sσ2 · · · sσn ∈ W, σ ∈ Sn ,

are the Coxeter elements of (W, S). We say w ∈ W is essential if it is not conjugate into any subgroup WI ⊂ W generated by a proper subset I ⊂ S. The Coxeter group W acts naturally by reflections on V ∼ RS , preserv= ing an inner product B(v, v ′ ). Let λ(w) denote the spectral radius of w|V . When λ(w) > 1, it is also an eigenvalue of w. We will show (§4): Theorem 1.2 Let (W, S) be a Coxeter system and let w ∈ W be essential. Then we have λ(w) ≥ inf Sn λ(sσ1 sσ2 · · · sσn ). Here is the relation to billiards. In the case of a hyperbolic Coxeter system (when (V, B) has signature (p, 1)), the orbifold Y = Hp /W is a convex polyhedron bounded by mirrors meeting in acute angles. Closed geodesics on Y can be visualized as loops traced out by billiards in this polyhedron. The hyperbolic length of the geodesic in the homotopy class of w ∈ π1 (Y ) = W is given by log λ(w). Thus the theorem states that the essential billiard loops in Y are no shorter than the shortest Coxeter element. As a special (elementary) case, the shortest billiard loop in the (p, q, r)triangle in H2 is the pedal subtriangle representing w = s1 s2 s3 ; see Figure 1. 1

Figure 1. The shortest billiard loop in the (3, 4, 7)-triangle.

The Hilbert metric on the Tits cone. To prove Theorem 1.2 for higherrank Coxeter groups (signature (p, q), q ≥ 2), we need a generalization of hyperbolic space. A natural geometry in this case is provided by the Hilbert metric on the Tits cone. The Hilbert distance on the interior of a convex cone K is given in terms of the cross-ratio by dK (x, y) = (1/2) inf log[a, x, y, b], where the infimum is over all segments [a, b] in K containing [x, y]; it is a metric when K contains no line. We will show (§2) that the translation length of a linear map T preserving K satisfies
x∈K ◦

inf dK (x, T x) = log λ(T ),

provided λ(T ) = λ(T −1 ). The Tits cone W · F ⊂ V ∗ is the orbit, under the dual action of W , of a simplicial cone F which forms a fundamental domain for W . When (W, S) is hyperbolic or higher-rank, K = W · F contains no line, so dK is a metric. At the same time, log λ(w) is the translation length of w in the Hilbert metric on K, so this geometry can be used to study eigenvalues. We propose (PK ◦ , dK ) as a natural generalization of the Klein model for hyperbolic space to higher-rank Coxeter groups (§3). Once this geometry is in place, the proof of Theorem 1.2 is based on the fact that a loop repre2

senting an essential element w must touch all the faces of the fundamental domain F (§4). The bicolored eigenvalue. Next we give a succinct lower bound for the spectral radius of Coxeter elements. The Coxeter diagram D of (W, S) is the weighted graph whose vertices are the set S, and whose edges of weight mij join si to sj when mij ≥ 3. If D is a tree (such as one of the familiar spherical diagrams An , Bn , Dn or En ), then the Coxeter elements w ∈ W range in a single conjugacy class. When D has cycles, however, many different conjugacy classes (and different values of λ(w)) can arise. When every cycle has even order (so D is bipartite), a special role is played by the bicolored Coxeter elements. These are defined by w = S1 S2 , where S = S1 ⊔ S2 is a two-coloring of the vertices of D. All bicolored Coxeter elements are conjugate. The value of λ(w) they share can be computed directly, as follows. Let α(W, S) be the leading eigenvalue of the adjacency matrix of (W, S), defined by Aij = 2 cos(π/mij ) for i = j and Aii = 0. Let β = β(W, S) ≥ 1 be the largest root of the equation β + β −1 + 2 = α(W, S)2 , provided α(W, S) ≥ 2. Set β(W, S) = 1 if α(W, S) < 2. Then λ(w) = β(W, S) for all bicolored Coxeter elements. The above definition of the bicolored eigenvalue β(W, S) makes sense for any Coxeter system, bipartite or not. We will show in §5: Theorem 1.3 For any Coxeter system (W, S), we have inf λ(sσ1 sσ2 · · · sσn ) ≥ β(W, S).
Sn

In particular the bicolored Coxeter elements, when they exist, minimize λ(sσ1 sσ2 · · · sσn ). In the hyperbolic and higher-rank cases, it is easy to see that β(W, S) > 1; thus every Coxeter element has infinite order. The same conclusion is well-known to hold in the affine case, so we obtain: Corollary 1.4 A Coxeter group W is infinite iff every Coxeter element sσ1 sσ2 · · · sσn ∈ W has infinite order. This Corollary was first established in [How]. Minimal hyperbolic diagrams. There is a natural partial ordering on Coxeter systems that is conveniently visualized in terms of diagrams: we 3

write (W ′ , S ′ ) ≥ (W, S) if the diagram D ′ is obtained from D by adding more vertices and edges and/or increasing their weights. A useful feature of the invariant β(W, S) is that it is a monotone function: we have (W ′ , S ′ ) ≥ (W, S) =⇒ β(W ′ , S ′ ) ≥ β(W, S), by elementary properties of positive matrices. Now suppose w ∈ W ′ satisfies λ(w) > 1. Then (W ′ , S ′ ) has indefinite signature, and therefore it dominates a minimal hyperbolic Coxeter system (W, S). In §6 we will show: Theorem 1.5 There are 38 minimal hyperbolic Coxeter systems, and among these we have inf β(W, S) = λLehmer . By monotonicity of β, we have λ(w) ≥ β(W ′ , S ′ ) ≥ β(W, S) ≥ λLehmer , completing the proof of Theorem 1.1. Small Salem numbers. The results above suggest using β(W, S) as a measure of the complexity of a Coxeter system. We conclude in §7 with a few connections between the simplest Coxeter systems and small Salem and Pisot numbers. Let Ya,b,c denote the Coxeter system whose diagram is a tree with 3 branches of lengths a, b and c, joined at a single node. For example E8 = Y2,3,5 . We will show: • The smallest Salem numbers of degrees 6, 8 and 10 coincide with λ(w) for the Coxeter elements of Y3,3,4 , Y2,4,5 and Y2,3,7 . (These are the hyperbolic versions of the exceptional spherical Coxeter systems E6 , E7 and E8 .) • In particular λLehmer = λ(w) for the Coxeter elements of Y2,3,7 . • The set of all irreducible Coxeter systems with β(W, S) < λPisot consists exactly of Y2,4,5 and Y2,3,n , n ≥ 7. Here λPisot ≈ 1.324717 is the smallest Pisot number; it satisfies x3 = x + 1. • The infimum of β(W, S) over all higher-rank Coxeter systems coincides with λPisot .

4

• There are exactly 6 Salem numbers < 1.3 that arise as eigenvalues in Coxeter groups. Five of these arise from the Coxeter elements of Y2,3,n , 7 ≤ n ≤ 11. (On the other hand, there are in all 47 known Salem numbers less than 1.3.) • The second smallest known Salem number, λ ≈ 1.188368, arises as λ(g) for g ∈ O+ (II17,1 ), but does not arise as λ(w) for any w in the index two Coxeter group W ⊂ O+ (II17,1 ). Here II17,1 denotes the unique even unimodular lattice of signature (17, 1). At the end of §7 we connect the study of β(W, S) to the many known results on the leading eigenvalues of graphs. Notes and references. E. Hironaka showed that Lehmer’s number is the smallest of an infinite family of Salem numbers that arise as roots of Alexander polynomials of certain pretzel knots [Hir]. We observed that these Salem numbers are also the leading eigenvalues of Coxeter elements for the diagrams Yp1 ,...,pn , and were led to formulate Theorem 1.1. It is conjectured that λLehmer is the smallest Salem number, and more generally that it has minimal Mahler measure among all algebraic integers (other than roots of unity). This conjecture is confirmed by Theorem 1.1 for those algebraic integers λ(w) that arise via Coxeter groups. Many Salem numbers can also be realized as eigenvalues of automorphisms of even, unimodular lattices [GM], but it is unknown if λLehmer is a lower bound for the Salem numbers that arise in this way. See [GH] for a recent survey on this topic. Basic references for Coxeter groups include [Bou], [Ha1] and [Hum]. See [A’C], [BLM], [Co] and [How] for related work on eigenvalues of Coxeter elements. Connections between Salem numbers and growth-rates of reflection groups in H2 and H3 are studied in [FP], [Fl], [CW] and [Par]. The pedal triangle is discussed in [RT, §5]. (The existence of billiard loops is an open question for obtuse triangles; see [HH].) For the convenience of the reader, we have included short proofs of key results from the literature and a summary of the needed background on Coxeter groups. I would like to thank D. Allcock, B. Gross and E. Hironaka for many informative and useful discussions.

5

2

Translation length in the Hilbert metric

Let V be a finite-dimensional real vector space. Let K ⊂ V be a closed, convex cone, such that the interior K ◦ of K is nonempty and K contains no line. Let T : V → V be a linear automorphism of V with T (K) = K, and let λ(T ) denote the spectral radius of T . In this section we introduce the Hilbert metric dK on K ◦ and study the translation length δ(T, K) = inf ◦ dK (x, T x).
x∈K

We will show: Theorem 2.1 (Hilbert length) The translation length of T in the Hilbert metric satisfies 1 log max (λ+ , λ− , λ+ λ− ) ≤ δ(T, K) ≤ log max (λ+ , λ− ), 2 where λ± = λ(T ±1 ) . Corollary 2.2 The translation length is given by δ(T, K) = log λ(T ) provided λ(T ) = λ(T −1 ). The Hilbert metric. Let K ⊂ V be a closed convex set containing no line. Let [x, y] ⊂ K denote the segment joining x, y ∈ K. The cross-ratio of 4 collinear points is given by [a, x, y, b] = |y − a| |x − b| · |y − b| |x − a|

for any norm | · | on V . The Hilbert metric on K ◦ is defined by dK (x, y) = 1 inf log[a, x, y, b], 2

where the infimum is over all a, b ∈ K such that [x, y] lies in the interior of [a, b] with the same orientation. Compare [H], [Ha2], [Bus, p. 105], [BK, IV.28]. It is easy to see that dK induces the usual topology on K ◦ . Examples. Let K = [A, B] ⊂ V = R; then dK coincides with the Riemannian metric (B − A) |dx| · 2|x − A||x − B| 6

More generally, if K ⊂ Rn is the closed unit ball, then K ◦ coincides with the Klein model for hyperbolic space Hn , and the Hilbert metric agrees with the hyperbolic metric of constant curvature −1. (The factor of 1 in 2 the definition of dK compensates for the transition between the Poincar´ e and Klein models.) Straightness. Since the Hilbert metric restricts to a Riemannian metric on any segment in K ◦ , we have the following crucial straightness property: dK (x, y) + dK (y, z) = dK (x, z) (2.1)

for any y ∈ [x, z]. Contraction principle. Linear maps φ are contracting for the Hilbert metric: that is, if φ : V → V ′ is a linear map that sends K into K ′ , then we have dK ′ (φ(x), φ(y)) ≤ dK (x, y). e In this respect the Hilbert metric behaves like the Poincar´ metric from complex analysis.
d z w a e c p x y b f

Figure 2. The triangle inequality.

Triangle inequality. We sketch a proof that dK is a metric. Since K contains no line, dK (x, y) = 0 iff x = y. The triangle inequality is verified by Figure 2. By convexity, given x, y, z ∈ K ◦ , K contains at least the quadrilateral L whose diagonals are the maximal segments [a, b] and [c, d] containing [x, y] and [y, z]. Let [e, f ] denote the maximal segment through [x, z] in L, and let p be the intersection of the lines through [a, c] and [b, d]. (If these lines are parallel we take p at infinity.) Projection from p sends y to a point w in [x, z]. Since projection between lines preserves cross-ratios, we see that [a, x, y, b] = [e, x, w, f ] and thus dK (x, w) ≤ dL (x, w) = dK (x, y). 7

Similarly dK (w, z) ≤ dK (y, z). Finally from the straightness property we obtain dK (x, z) = dK (x, w) + dK (w, z) ≤ dK (x, y) + dK (y, z). The balanced metric. Here is a variant of the Hilbert metric with useful properties. A segment [x, y] ⊂ K extends by α > 0 if the segment with the same center but (1 + 2α)-times longer, namely [a, b] = [x + α(x − y), y + α(y − x)], is also contained in K. The balanced metric on K ◦ is defined by d∗ (x, y) = inf{log(1 + α−1 ) : [x, y] extends by α.}. K The proof of the triangle inequality is similar to the case of the Hilbert metric (see [BW, Lemma 2]). The balanced metric is simply the Hilbert metric subject to the condition that [a, b] has the same center as [x, y]. Thus it enjoys the same contraction principle. Noting that [−α, 0, 1, 1 + α] = (1 + α−1 )2 we have: 1 ∗ d (x, y) ≤ dK (x, y) ≤ d∗ (x, y). K 2 K One advantage of the balanced metric is the product formula: d∗ 1 ×K2 ((x1 , y1 ), (x2 , y2 )) = max d∗ 1 (x1 , y1 ), d∗ 2 (x2 , y2 ) , K K K which makes it suitable for proofs by induction. For example, a Hilbert ball 2 in K = R+ is a hexagon, while a balanced ball is a square (Figure 3). A disadvantage of the balanced metric is that the straightness property (2.1) fails. Translation length. We now assume, as in the beginning of this section, that K ⊂ V is a closed convex cone containing no line, and K ◦ = ∅. Let T : V → V be a linear map such that T (K) = K. Then T induces an isometry of K ◦ in both the balanced and Hilbert metrics. Let δ∗ (T, K) =
x∈K ◦

(2.2)

inf d∗ (x, T x). K

Concentrating first on the balanced metric, we will show: Theorem 2.3 (Balanced length) The translation length of T in the balanced metric is given by δ∗ (T, K) = log max (λ(T ), λ(T −1 )). 8

p

Figure 3. Balls of radius (log 2)/2 centered at p ∈ R2 in the balanced metric + (inner) and the Hilbert metric (outer).

Eigenvectors in K. As a first step in the proof, we show: Theorem 2.4 Let T : V → V be a linear map satisfying T (K) = K. Then λ(T ) > 0 is an eigenvalue of T , with a corresponding eigenvector v ∈ K. Proof. Since T (K) = K, T is invertible. Using the generalized eigenspace decomposition of T on V ⊗ C, we obtain a T -invariant splitting V = X ⊕ Y such that the spectrum of (T |X) lies on the circle |z| = λ(T ), while λ(T |Y ) < λ(T ). Choose a norm | · | on V . Since K ◦ = ∅, there exists a vector u = (x, y) ∈ K with x = 0. Then we have |T n (x)| ≍ λ(T )n |x| ≫ |T n (y)| as n → ∞. It follows that any accumulation point w of the sequence T n (u)/|T n (u)| lies in K ∩ X. Since K is a cone, the entire ray R+ · w is also contained in K ∩ X. The set of all rays contained in K∩X determines a nonempty, T -invariant subset P(K ∩ X) ⊂ PX. Since K is closed, convex and contains no line, P(K ∩ X) is a compact, convex disk. Therefore T : P(K ∩ X) → P(K ∩ X) has a fixed point [v]. We have T v = αv and |α| = λ(T ) since v ∈ X. Since K contains no line we have α > 0 and thus α = λ. Corollary 2.5 We have δ∗ (T, K) ≥ log max (λ(T ), λ(T −1 )). Proof. Let λ = λ(T ). Let T ∗ : V ∗ → V ∗ be the dual of T , and let K ∗ = {f ∈ V ∗ : f (K) ≥ 0} be the dual cone to K. Since the interior of K is nonempty and K contains no line, the same properties obtain for K ∗ . 9

By the preceding Theorem, there is a nonzero f ∈ K ∗ such that T ∗ (f ) = λf . Then f : V → R satisfies: f (T v) = λf (v) and f (K) ⊂ [0, ∞).

By the contraction principle, δ∗ (T, K) is bounded below by the translation distance δ∗ (T ′ , K ′ ) = | log λ| of T ′ (x) = λx on V ′ = R with K ′ = [0, ∞). Applying the same reasoning to T −1 gives the Corollary. For the reverse inequality it is convenient to prove a slightly more general statement that allows K to contain a line. Lemma 2.6 Let K ⊂ V be a closed convex cone with K ◦ = ∅. Let T : V → V be an automorphism preserving K, and suppose 1 + α−1 > max (λ(T ), λ(T −1 )). Then there exists an x ∈ K ◦ such that [x, T x] extends by α. Proof. The proof will be by induction on dim V . If dim V = 0, the Lemma holds for all values of α > 0 by taking x = 0. Now suppose that dim V > 0 and that the Lemma has been established for all vector spaces with dim V ′ < dim V . Observe that any T -invariant subspace S ⊂ V of positive dimension yields a quotient map f : V → V ′ = V /S, and an automorphism T ′ of V ′ making the diagram V −−→ V −−     f f
T′ T

commute. Since the spectrum of T ′ is contained in that of T , and dim V ′ < dim V , the Lemma provides an x′ in (K ′ )◦ = f (K ◦ ) such that [x′ , T ′ (x′ )] extends by α. Lifting to V , we obtain y, z ∈ K ◦ such that [y, z] extends by α and T (y) = z + s for some s ∈ S. We apply this observation in two ways to complete the proof. First, suppose K ⊂ V contains a line. Let S be the maximal subspace contained in K. Then [y, z] and [y, z + s] extend by the same amount, so [y, T (y)] extends by α and we are done. Second, suppose K ⊂ V contains no line. It is convenient to assume that λ = λ(T ) ≥ λ(T −1 ) (if not, replace T by its inverse); then λ ≥ 1. By 10

−− V ′ −−→ V ′

Theorem 2.4 there is an eigenvector v ∈ K such that T v = λv. (If v were in K ◦ we could finish the proof by taking x = v; but frequently v lies in ∂K.) Let S be the subspace R · v ⊂ V . By the observation above, we have y, z ∈ K ◦ such that [y, z] extends by α and T (y) = z + mv for some m ∈ R. Let x = y + M v where M ≫ 0. Since y lies in K ◦ and R+ · v ⊂ K, we have x ∈ K ◦ . We claim that for M sufficiently large, [x, T x] extends by α. To see this, we compute: x + α(x − T x) = y + α(y − T (y)) + M (v + α(v − T (v))) = y + α(y − z) + (M β − m)v = y + α(y − z) − mv + M (1 + α − αλ)v

where the coefficient β = 1 + α − αλ is positive by our assumption that 1 + α−1 > λ. Therefore we have (M β − m)v ∈ R+ · v ⊂ K when M is large enough. On the other hand, y + α(y − z) lies in K since [y, z] extends by α. Since K + K ⊂ K, we have x + α(x − T x) ∈ K. A similar argument shows T x + α(T x − x) ∈ K. Thus [x, T x] extends by α. Proof of Theorem 2.3 (Balanced length). By Corollary 2.5 we have δ∗ (T, K) ≥ log max (λ(T ), λ(T −1 )). Since d∗ (x, T x) ≤ log(1 + α−1 ) when [x, T x] extends by α, the preceding K Lemma provides the reverse inequality. Proof of Theorem 2.1 (Hilbert length). Using the comparison (2.2) between the Hilbert metric and the balanced metric, the Theorem 2.3 immediately yields 1 log max (λ+ , λ− ) ≤ δ(T, K) ≤ log max (λ+ , λ− ) 2 where λ± = λ(T ±1 ). When λ+ and λ− are both > 1, the lower bound can be strengthened to 1 log λ+ λ− , as follows. Proceeding as in Corollary 2.5, there exist eigen2 vectors f± ∈ K ∗ such that (T ∗ )±1 f± = λ± f± . Define f : V → R2 by

11

f (v) = (f+ (v), f− (v)), and T ′ : R2 → R2 by T ′ (x, y) = (λ+ x, λ−1 y). Then − f ◦ T = T ′ ◦ f , and f (K) = K ′ = R2 . By the contraction principle, we have + δ(T, K) ≥ δ(T ′ , K ′ ) = completing the proof. 1 log(λ+ λ− ), 2

3

Coxeter groups and the Tits cone

This section summarizes geometric properties of Coxeter groups. Basic references for this material are [Bou] and [Hum]; see also [Vin1], [Ha1]. Our main interest will be hyperbolic and higher-rank Coxeter groups. For such groups, we observe that the Hilbert metric on the interior of the Tits cone K ◦ is well-defined and invariant, and passes to the space of rays PK ◦ . Thus (PK ◦ , dK ) serves as a generalization of the Klein model for hyperbolic space to the case of higher-rank Coxeter groups. Coxeter systems. Let W be a group generated by a finite set S, and let m(s, t) denote the order of st ∈ W . Assume m(s, s) = 1 and m(s, t) ≥ 2 for all s = t in S. The pair (W, S) is a Coxeter system if the generators S, together with the relations (st)m(s,t) = 1 for all s, t ∈ S, give a presentation for W . Then W itself is a Coxeter group. Let V = RS be the real vector space with one basis element es for each s ∈ S. Define a symmetric bilinear form B : V × V → R by B(es , et ) = −2 cos(π/m(s, t)). There is a natural geometric action of W on V preserving the form B, given on the generators s ∈ S by s · v = v − B(es , v)es ; that is, by letting s acts via reflection through the hyperplane normal to es . The representation W → O(V, B) is faithful. The quadratic form B(v, v) on V is equivalent over R to one of the standard forms 2 x1 + · · · + x2 − x2 − · · · − x2 p p+1 p+q rad(V ) = {v : B(v, v ′ ) = 0 ∀v ′ ∈ V }; 12

on Rn ; its signature is (p, q). The radical is defined by

Eigenvalues. Let λ(w) denote the spectral radius of w ∈ W acting geometrically on V . Clearly s|rad(V ) = I for all s ∈ S, so the same is true of w. Moreover B descends to a non-degenerate quadratic form on V /rad(V ), preserved by w. It follows that det(λI − w) is a reciprocal polynomial, and in particular that λ(w) = λ(w−1 ). (3.1) The Tits cone. The Coxeter group W also acts naturally on the dual space V ∗ . The dual action is characterized by the equation w · f, w · v = f, v , where f, v denotes the natural pairing between f ∈ V ∗ and v ∈ V . The spectral radii of w|V and w|V ∗ agree. The fundamental chamber F ⊂ V ∗ for (W, S) is defined by: F = {f ∈ V ∗ : f, es ≥ 0 ∀s ∈ S}. Passage to the dual space permits a uniform treatment of the geometric action even in the case where rad(V ) = (0). For example, the chamber F ⊂ V is always a cone on a simplex, while the region {v : B(v, es ) ≥ 0 ∀s ∈ S} ⊂ V need not be. The Tits cone is the full orbit W · F of the fundamental chamber under the action of W . From [Bou, V.4] or [Hum, §5.13] we have: Theorem 3.1 The Tits cone W · F is convex, and w(F ) = F iff w = id. Diagrams. The Coxeter diagram of (W, S) is the weighted graph D whose vertices are S and whose edges of weight m(s, t) join s to t whenever m(s, t) ≥ 3. To make a picture of the diagram D, we draw single lines for edges of weight 3, double lines for edges of weight 4, and lines labeled by n for edges of weight n ≥ 5. A Coxeter system is irreducible if the action of W on V /rad(V ) is irreducible; equivalently, if its Coxeter diagram is connected.

it satisfies dim rad(V ) = n − p − q. Remark: when (st) has infinite order, one drops the relation (st)m(s,t) = 1 and sets B(es , et ) = −2.

13

A general Coxeter system (W, S) reduces naturally into irreducible subsystems (Wi , Si ), such that S = ⊔Si and W = Wi . The geometric action of W on V is the product of the actions of Wi on Vi . Classification by signature. Assume the Coxeter system (W, S) is irreducible. Then (W, S) can be classified into one of 4 types according to the signature of (V, B). Letting n = |S| = dim V , we say (W, S) is: • Spherical if sig(V, B) = (n, 0); • Affine if sig(V, B) = (n − 1, 0); • Hyperbolic if sig(V, B) = (p, 1); and • Higher-rank if sig(V, B) = (p, q), q ≥ 2. This classification is conveniently approached via the adjacency matrix Ast = (2I − B)(es , et ) = 2 cos(π/m(s, t)), 0 s = t, s = t.

Let α = α(W, S) denote the spectral radius of A. Since the smallest eigenvalue of the symmetric matrix B is 2 − α(W, S), we find:  spherical if α(W, S) < 2,  (W, S) is affine if α(W, S) = 2, and   hyperbolic or higher-rank if α(W, S) > 2.

Terminology. The term ‘adjacency matrix’ comes from the case where m(s, t) ≤ 3 for all s, t; then Ast = 1 if s and t are joined by an edge in the Coxeter diagram of (W, S), and = 0 otherwise. The term ‘higher rank’ is meant to remind one that the real Lie group SO(p, q) has real rank ≥ 2 when (p, q) ≥ (2, 2). Note that in [Bou] and [Hum], the term ‘hyperbolic’ is used differently than here; these authors include the additional condition that rad(V ) = (0) and Hp /W has finite volume. Perron-Frobenius. Since the Coxeter diagram of (W, S) is connected, the matrix A is one to which the Perron-Frobenius theory applies. That is, α = α(W, S) is a simple eigenvalue of A, and there is a positive vector v0 = as es , as > 0 such that Av0 = αv0 and Bv0 = (2 − α)v0 . Now assume α = 2 and let f0 ∈ V ∗ be the dual vector satisfying f0 , v = (2 − α)−1 B(v0 , v)

for all v ∈ V . Then clearly f0 belongs to rad(V )⊥ ; that is, f0 , v = 0 for all v ∈ rad(V ). Moreover, we have f0 , es = as > 0, so f ∈ F ◦ . This shows: 14

Proposition 3.2 Except in the affine case, F ◦ meets rad(V )⊥ . Spherical, affine and hyperbolic groups. The spherical and affine groups are well-understood; for example, their diagrams are classified. In the spherical case the Tits cone is all of V ∗ and W is finite. In the affine case the closure of the Tits cone is a half-space bounded by rad(V )⊥ , and W = W0 ⋉ Zn−1 with |W0 | < ∞. By considering the space of rays in the interior of the Tits cone, one obtains an isometric action of W on the sphere S n or on the Euclidean space Rn−1 . Hyperbolic and higher rank groups. We will use the Hilbert metric on the Tits cone to obtain an isometric action in the hyperbolic and higher-rank cases. Let K = W · F . Theorem 3.3 Let (W, S) be a hyperbolic or higher-rank Coxeter system. Then the closure of the Tits cone K contains no line. Proof. (From [Vin1, Lemma 15].) Let X ⊂ V ∗ be the maximal subspace contained in K. For the sake of contradiction, suppose X = (0). Then X ⊥ ⊂ V is a proper W -invariant subspace. By irreducibility of the action of W on V /rad(V ), we have X ⊥ ⊂ rad(V ), and thus X ⊃ rad(V )⊥ . Since F ◦ meets rad(V )⊥ , there is an f0 ∈ rad(V )⊥ and a neighborhood U of the origin in V ∗ such that f0 + U ⊂ F ◦ ⊂ W · F = K. We also have −f0 ∈ X ⊂ K. Since K is a convex cone, this implies U = (−f0 ) + f0 + U ⊂ K, and thus K = V . Therefore W is finite and (W, S) is spherical, a contradiction.

Since K contains no line, the Hilbert metric dK is well-defined and we have: Corollary 3.4 In the hyperbolic or higher-rank case, the Coxeter group W acts isometrically on K ◦ in its Hilbert metric. Since λ(w) = λ(w−1 ) ((3.1) above), Theorems 2.1 and 2.4 imply:

15

Corollary 3.5 Let w belong to a hyperbolic or higher-rank Coxeter group. Then λ(w) ≥ 1 is an eigenvalue of w, and log λ(w) =
x∈K ◦

inf dK (x, w · x).

Projective models. The Hilbert determines a W -invariant metric on the space of rays PK ◦ ⊂ PV ∗ , because the cross-ratio is projectively invariant. The space PK ◦ is isometric (via projection) to the affine slice (K ◦ ∩ H, dK ), for hyperplane H ⊂ V with H ∩ K ◦ = ∅ and K ∩ H compact. In the case of hyperbolic Coxeter groups, W also acts isometrically on the Klein model for hyperbolic space, Hp = PH ⊂ PV ∗ , where H is the image of the timelike cone B(v, v) < 0 under the map V → V ∗ defined by B. In fact, when the radical is trivial and Hp /W has finite volume, Hp coincides isometrically with (PK ◦ , dK ). Thus we can regard (PK ◦ , dK ) as a generalization of the Klein model for hyperbolic space to the infinite-volume and higher-rank cases.

4

Coxeter elements

In this section we show Coxeter elements minimize translation length among all essential elements in W . Coxeter elements. Let (W, S) be a Coxeter system with S = {s1 , . . . sn }. We say w ∈ W is a Coxeter element if w = sσ1 sσ2 · · · sσn for some permutation σ ∈ Sn . Essential elements. Let WI ⊂ W denote the parabolic subgroup generated by I ⊂ S. Then (WI , I) is also a Coxeter system. An element w ∈ W is peripheral if it is conjugate into a proper parabolic subgroup WI ⊂ W , I = S; otherwise it is essential. We will show: Theorem 4.1 Let (W, S) be a Coxeter system and let w ∈ W be essential. Then we have λ(w) ≥ inf Sn λ(sσ1 sσ2 · · · sσn ). 16

Loops in the fundamental chamber. It is easy to see that Theorem 4.1 for general (W, S) follows from the irreducible case. In the spherical and affine cases, λ(w) = 1 for all w ∈ W and the Theorem is immediate. Now assume (W, S) is hyperbolic or higher-rank. Then W acts isometrically and discretely on K ◦ , with X = F ∩ K ◦ as a fundamental domain. The natural projection map π : K ◦ → X, characterized by x ∈ W · π(x), is a covering map in the sense of orbifolds. By convexity, K ◦ is contractible, and hence the orbifold fundamental group of X is W . Let γ : [0, 1] → K ◦ be a piecewise linear path. Breaking the domain into intervals [ti , ti+1 ] on which γ is linear, and setting xi = γ(ti ), we define its length by L(γ) = dK (xi , xi+1 ). The sum is independent of the choice of subdivision because of the triangle equality (2.1) for collinear points. A loop in X is a piecewise-linear path γ : [0, 1] → X with γ(0) = γ(1). A lift of γ is a path γ : [0, 1] → K ◦ such that π ◦ γ = γ. In this case γ(1) = w · γ(0) for some w ∈ W , and we say γ (or γ) represents w. A given loop has many lifts, and thereby represents many elements in W. General position. The codimension-one faces of F are given by F (s) = {f ∈ F : f (s) = 0}, s ∈ S; the codimension-two faces, by F (s) ∩ F (t), s = t. Let us say a piecewise-linear path γ : [0, 1] → X is in general position if it is disjoint from the codimension-two faces of F and meets the codimensionone faces at most in a finite set. Proposition 4.2 We have log λ(w) = inf L(γ) over all loops γ : [0, 1] → X in general position representing w. Proof. Let γ represent w via the lift γ. By Corollary 3.5, log λ(w) is the minimal translation length of w in the Hilbert metric. Thus we have L(γ) = L(γ) ≥ dK (γ(0), w · γ(0)) ≥ log λ(w). 17

Moreover, there exist xn ∈ K ◦ with dK (xn , w · xn ) → log λ(w). Since the orbits of the codimension-one faces W · F (s) are nowhere dense, we can assume π(xn ) ∈ F ◦ . Let γn denote the straight line from xn to w · xn ; then L(γn ) → log λ(w). Since the orbits W · (F (s) ∩ F (t)) of the codimension-two faces of F do not separate K ◦ , we can modify γn slightly (introducing new bends if necessary but increasing its length by at most 1/n) so that γn = π ◦ γn is in general position. Then L(γn ) → log λ and γn represents w, completing the proof. Let γ be a loop in general position, and let t1 < t2 < . . . < tm be the parameters such that γ(ti ) ∈ ∂F . Then we have γ(ti ) ∈ F (gi ) for a unique gi ∈ S. We say w is a subword of g1 g2 · · · gm if we have w = gi1 gi2 · · · gik for some indices 1 ≤ i1 < i2 < · · · < ik ≤ m. Proposition 4.3 The loop γ represents w iff w is conjugate to a subword of g1 g2 · · · gm . Proof. Define a lift γ of γ by  γ(t)  γ(t) = g1 g2 · · · gk · γ(t)   g1 g2 · · · gm · γ(t)

if t ∈ [0, t1 ], if t ∈ [tk , tk+1 ], and if t ∈ [tm , 1].

Since gk ·γ(tk ) = γ(tk ), the definition is consistent and γ is continuous. Thus γ represents the full word g1 · · · gm . By ignoring a subset of the (ti )’s, we can similarly obtain a lift which represents any subword of g1 · · · gm . Now let γ be a lift with γ(0) ∈ X. Then γ(t) = w(t) · γ(t) for some w(t) ∈ W . The element w(t) can only change when γ(t) touches a face F (gi ), and then only by composition on the right with gi . Thus γ has the form above and therefore γ represents a subword of g1 · · · gm . To complete the proof, observe that γ represents w iff g · γ represents gwg−1 .

18

Proof of Theorem 4.1. As discussed above, the Theorem reduces to the case of a hyperbolic or higher-rank group. Let w ∈ W be an essential element of such a group. For any ǫ > 0 we can find a loop γ : [0, 1] → X in general position such that γ represents w and L(γ) ≤ log λ(w) + ǫ. Let γ(ti ) ∈ F (gi ) be the points of γ that meet ∂F . Then w is conjugate to a subword of g1 · · · gm . Since w is essential, every element of S must occur in the sequence (gi ). Thus g1 · · · gm also contains a Coxeter element w′ as a subword, and therefore γ also represents w′ . We then have λ(w′ ) ≤ L(γ) ≤ log λ(w) + ǫ, and the proof is completed by letting ǫ → 0. Hyperbolic groups. For hyperbolic Coxeter systems, the proof above can also be carried through using hyperbolic space Hp in place of PK ◦ . Question. Are all Coxeter elements essential?

5

Bipartite Coxeter diagrams

Let (W, S) be a Coxeter system. In this section we introduce the bicolored eigenvalue β(W, S) ≥ 1 and prove it controls the eigenvalues of all Coxeter elements. We will show: Theorem 5.1 Any Coxeter system (W, S) satisfies inf λ(sσ1 sσ2 · · · sσn ) ≥ β(W, S).
Sn

Equality holds if the Coxeter diagram of (W, S) is bipartite. Corollary 5.2 We have λ(w) ≥ β(W, S) for all essential w ∈ W . Bicolored Coxeter elements. When the Coxeter diagram D of (W, S) is a tree (or forest), the Coxeter elements range in a single conjugacy class in W [Hum, §3.16]. When D contains cycles, in general several conjugacy classes occur. However, when all the cycles in D are of even order, there is still a special class of Coxeter elements that are unique up to conjugacy. To define these, let us say a partition S = S1 ⊔ S2 of the vertices of D is a two-coloring if all edges of D lead from S1 to S2 . A two-coloring exists 19

iff all cycles in D are of even order. In the terminology of graph-theory, the diagram D is bipartite. Let D admit a two-coloring S = S1 ⊔ S2 . Since there are no edges between elements s, t ∈ Si , we have (st)2 = 1. Thus Si generates an abelian subgroup of W , isomorphic to (Z/2)|Si | . The product σi of the elements of 2 Si is independent of the choice of ordering and satisfies σi = 1. We refer to w = σ1 σ2 as a bicolored Coxeter element. Its conjugacy class is independent of the choice of two-coloring. In fact, if (W, S) is irreducible then its bicolored Coxeter element is unique up to w → w−1 , since the two-coloring of a connected diagram is unique up to (S1 , S2 ) → (S2 , S1 ). As noted in [A’C] and [BLM], the spectrum of the bicolored Coxeter elements is determined by the spectrum of Ast . In particular we have: Proposition 5.3 Let w be a bicolored Coxeter element for (W, S). Then the spectrum of w is contained in S 1 ∪R+ , and the eigenvalue(s) maximizing Re λ satisfy (5.1) 2 + λ + λ−1 = α(W, S)2 . Proof. It is easy to check that the adjacency matrix determines an operator A : V → V satisfying A = σ1 + σ2 , where w = σ1 σ2 . Thus A2 = 2 + σ1 σ2 + σ2 σ1 = 2 + w + w−1 . The spectrum of w is therefore the preimage of the spectrum of A2 under λ → 2 + λ + λ−1 . Since A is symmetric, the spectrum of A2 lies in the interval [0, α(W, S)2 ], and the Proposition follows. The bicolored eigenvalue. Motivated by equation (5.1), we define the bicolored eigenvalue β(W, S) as the unique root β ≥ 1 of the equation 2 + β + β −1 = α(W, S)2 , provided α(W, S) ≥ 2. For α(W, S) < 2 we set β(W, S) = 1. In the first case, (W, S) has a hyperbolic or higher-rank component; in the second, all components are affine or spherical. In the first case λ(w) is an eigenvalue of w, showing: Corollary 5.4 We have λ(w) = β(W, S) for all bicolored Coxeter elements. Proof of Theorem 5.1. Assume (W, S) is hyperbolic or of higher-rank; the Theorem easily reduces to this case. Let α = α(W, S) > 2. 20

Let w = s1 · · · sn be a Coxeter element in W . We will write vectors ′ v ∈ V as v = vi ei , ei = esi , and write v ≥ v ′ to mean vi ≥ vi for all i. Since sk · v = v − B(v, ek )ek , and B = 2I − A, we have: (sk · v)i = (A · v)i − vi vi if k = i, otherwise. (5.2)

Note that (A · v)i only depends on vj , j = i Let v > 0 be a Perron-Frobenius eigenvector for A; it satisfies Av = αv. To prove the Theorem, it suffices to show (w + w−1 )(v) ≥ (α2 − 2)v, since this equation implies λ(w) + λ(w)−1 ≥ λ(w + w−1 ) ≥ α2 − 2 and thus λ(w) ≥ β(W, S). To prove (5.3) first note that v ′ ≥ v implies Av ′ ≥ Av. Since α − 1 ≥ 1, we have (sn · v)n = (α − 1)vn ≥ vn , and thus sn · v ≥ v. By induction, we have the inequalities (sk sk+1 · · · sn · v)k ≥ (A · v)k − vk = (α − 1)vk for all k. Since sk only changes the kth coordinate of v, we have (sk+1 · · · sn · v)i (sk+1 · · · sn · v)i ≥ (α − 1)vi , i > k, i ≤ k. sk sk+1 · · · sn · v ≥ v, (5.3)

=

vi ,

Applying the same reasoning to w−1 = sn · · · s1 , we find u = (sk+1 · · · sn · v) + (sk−1 · · · s1 · v) satisfies ui ≥ αvi , i = k, and uk = 2vk . On the other hand, we have ((w + w−1 ) · v)k = (sk · u)k , using again the fact that only sk changes the kth coordinate. Therefore we have ((w + w−1 ) · v)k = (A · u)k − uk establishing (5.3) and completing the proof. ≥ (A · (αv))k − 2vk = (α2 − 2)vk ,

21

Corollary 5.5 The bicolored Coxeter elements, if they exist, minimize λ(w) among all Coxeter elements. Geometric interpretation. Suppose (W, S) admits a two-coloring S = S1 ⊔S2 with corresponding Coxeter element w = σ1 σ2 . Then Fi = s∈Si F (s) is a facet of F with a finite stabilizer in W ; hence it meets K ◦ . Let [x, y] ⊂ X be a line segment joining F1 to F2 in (rad(V ))⊥ and perpendicular to both. A loop γ that traces [x, y] twice, once in each direction, gives a geodesic representing w; thus log λ(w) = 2L([x, y]). In terms of the Hilbert metric on the quotient orbifold X, Theorem 4.1 implies: Corollary 5.6 The loop γ for a bicolored Coxeter element has minimal length among all loops that touch all the faces of X.

Figure 4. The geodesic stabilized by the Coxeter element for the (2, 3, ∞) triangle group.

Example. Let (W, S) = a, b, c : a2 = b2 = c2 = (ac)2 = (ab)3 be the (2, 3, ∞) triangle group. Its Coxeter diagram is a b
∞

c.

22

The Coxeter element w = (ac)b is bicolored, and the corresponding segment [x, y] joins the right angle x = F (a) ∩ F (c) of X to the opposite side F (b). The hyperbolic length of [x, y] is given by the log of the golden mean, and therefore √ 3+ 5 λ(w) = = 2.61803 . . . 2 is the golden mean squared. The corresponding tiling of H2 in the Poincar´ model, and the geodesic e stabilized by w (which has [x, y] as a subsegment), are shown in Figure 4. As is well-known, W contains PSL2 (Z) as a subgroup of index two, and w2 = ( 2 1 ) when suitably normalized. 11 Finite covers of Coxeter diagrams. Here is another perspective on the bicolored eigenvalue. Let (W, S) be a Coxeter system with connected diagram D. Regarding D as a topological 1-complex with weights on its edges, consider the 2d -fold covering space D′ → D determined by the map π1 (D) → H1 (D, Z/2). All cycles in D′ have even length, so the associated Coxeter system (W ′ , S ′ ) admits a bicolored Coxeter element w′ ∈ W ′ . Clearly α(W, S) = α(W ′ , S ′ ), so we can alternatively define the bicolored eigenvalue of (W, S) by β(W, S) = λ(w′ ). In other words, every Coxeter system admits a bicolored ‘virtual’ Coxeter element, whose leading eigenvalue is β(W, S). Indiscrete groups. The proof of Theorem 5.1 uses only the fact that the adjacency matrix Ast is non-negative and symmetric, so it can easily be generalized beyond Coxeter groups. A corresponding result applies, for example, to the (possibly indiscrete) group generated by reflections through the sides of any simplex in hyperbolic space with interior dihedral angles ≤ π/2.

6

Minimal hyperbolic diagrams

In this section we use the classification of minimal hyperbolic diagrams to prove a universal lower bound for eigenvalues in Coxeter groups. Let (W, S) be a Coxeter system and let λ(W, S) = inf{λ(w) : w ∈ W and λ(w) > 1}. 23

We set λ(W, S) = 1 if all elements of W have spectral radius one. Note that when (W, S) is hyperbolic, log λ(W ) is the length of the shortest closed geodesic on the hyperbolic orbifold Hp /W . We will show: Theorem 6.1 Either λ(W, S) = 1 or λ(W, S) ≥ λLehmer . Recall λLehmer = 1.17628 . . . is the largest real root of Lehmer’s polynomial (1.1). Minimal Coxeter elements. We first show λ(W, S) can be computed by examining a finite number of elements w ∈ W . Given a Coxeter system (W, S), let λCox (W, S) = inf λ(sσ1 sσ2 · · · sσn ).
Sn

The infimum is realized by the minimal Coxeter elements in W . Theorem 6.2 For any Coxeter system with λ(W, S) > 1, we have λ(W, S) = inf{λCox (WI , I) : (WI , I) is hyperbolic or higher-rank.} Proof. Any element w ∈ W is conjugate to an essential element of (WJ , J) for some J ⊂ S. If λ(w) > 1 then (WJ , J) has a hyperbolic or higher-rank component (WI , I) with the same minimal Coxeter eigenvalue as (WJ , J). By Theorem 4.1 we have λ(w) ≥ λCox (WJ , J) = λCox (WI , I), and the proof is completed by taking the infimum over all w ∈ W with λ(w) > 1. Monotonicity. Coxeter systems admit a natural partial order, defined by (W, S) ≤ (W ′ , S ′ ) if there is an injective map ι : S → S ′ such that m(s, t) ≤ m(ι(s), ι(t)) for all s, t ∈ S. We write (W, S) ∼ (W ′ , S ′ ) if ι = ′ ; otherwise (W, S) < (W ′ , S ′ ). extends to an isomorphism between W and W Since m(s, t) ∈ {1, 2, 3, . . . , ∞}, this ordering satisfies the descending chain condition: any strictly decreasing sequence of Coxeter systems is finite. The inequality on m(s, t) is equivalent to the inequality Ast ≤ A′ ι(s)ι(t) between adjacency matrices. Now the spectral radius of Ast ≥ 0 increases as its entries do, since λ(A) = lim An 1/n . The same is therefore true of the bicolored eigenvalue; we have: 24

Proposition 6.3 If (W, S) ≥ (W ′ , S ′ ) then β(W, S) ≥ β(W ′ , S ′ ). Minimal hyperbolic diagrams. A hyperbolic Coxeter system (W, S) is minimal if (W ′ , S ′ ) has only spherical and affine components whenever (W ′ , S ′ ) < (W, S). Proposition 6.4 If (W0 , S0 ) is hyperbolic or higher rank, then there is a minimal hyperbolic Coxeter system with (W, S) ≤ (W0 , S0 ). Proof. We will write the signature of a Coxeter system as (p(W, S), q(W, S)). Consider the set of all Coxeter systems with (Wα , Sα ) ≤ (W0 , S0 ) and q(Wα , Sα ) ≥ 1. By the descending chain condition, this set has at least one minimal element (W, S). The minimal system (W, S) must be irreducible — otherwise one of its hyperbolic or higher-rank components would be strictly smaller. By minimality, q(W ′ , S ′ ) = 0 if (W ′ , S ′ ) < (W, S), and thus any strictly smaller system has only spherical and affine components. To see (W, S) is hyperbolic, pick s ∈ S and let I = S − {s}; then (WI , I) < (W, S) so q(WI , I) = 0. Adding s back in increases the signature by at most 1, so q(W, S) = 1. Therefore (W, S) is a minimal hyperbolic Coxeter system. By Theorem 6.2 we have: Proposition 6.5 If (W, S) is a minimal hyperbolic Coxeter system, then λ(W, S) = λCox (W, S). Theorem 6.6 Up to isomorphism, there are 38 minimal hyperbolic Coxeter systems. Their diagrams are shown in Table 5. Proof. Since the affine and spherical diagrams are known, the enumeration of minimal hyperbolic Coxeter systems is a straightforward combinatorial problem, albeit with many cases. As an alternative argument, we note that if (W, S) is a minimal hyperbolic Coxeter system, then (W, S) is irreducible and rad(V ) = (0). (Indeed, rad(V ) = (0) implies RI + rad(V ) = RS for some proper subset I ⊂ S, and then (WI , I) < (W, S) is still hyperbolic, contradicting minimality.) Moreover, the condition that all proper parabolic subgroups of W are affine or spherical implies that the vertices of the simplex PF ⊂ PV ∗ lie inside or on the boundary of hyperbolic space Hn−1 . Therefore Hn−1 /W has finite volume. 25

Coxeter system Ah4 Ah5 Ah6 Ah7 Ah8 Bh5 Bh6 Bh7 Bh8 Bh9 Dh6 Dh7 Dh8 Dh9 Dh10

λ(W, S) 2.36921 (2.26844) 2.08102 1.98779 (1.96355) 1.88320 1.83488 (1.82515) 1.72208 1.58235 1.50614 1.45799 1.42501 1.72208 1.58235 1.50614 1.45799 1.42501

det(xI − w) 1 − x − 3x2 − x3 + x4 (1 + x)(1 − x − 2x2 − x3 + x4 ) 1 − 2x2 − 3x3 − 2x4 + x6 (1 + x)(1 + x + x2 )(1 − 2x + x2 − 2x3 + x4 ) 1 − x2 − 2x3 − 3x4 − 2x5 − x6 + x8 (1 + x)(1 − x − x2 − x3 + x4 ) 1 − x2 − 2x3 − x4 + x6 (1 + x)(1 − x − x3 − x5 + x6 ) 1 − x2 − x3 − x5 − x6 + x8 (1 + x)(1 − x − x3 + x4 − x5 − x7 + x8 ) (1 + x)2 (1 − x − x2 − x3 + x4 ) (1 + x)(1 − x2 − 2x3 − x4 + x6 ) (1 + x)2 (1 − x − x3 − x5 + x6 ) (1 + x)(1 − x2 − x3 − x5 − x6 + x8 ) (1 + x)2 (1 − x − x3 + x4 − x5 − x7 + x8 ) (1 + x + x2 )(1 − x2 − x3 − x4 + x6 ) (1 + x)(1 − x3 − x4 − x5 + x8 ) 1 + x − x3 − x4 − x5 − x6 − x7 + x9 + x10

Eh8 Eh9 Eh10

1.40127 1.28064 1.17628

Table 5. The 38 minimal hyperbolic Coxeter diagrams. (Continued on next page.)

26

Coxeter system K343 K3433 K44 K53 K533 L33433 L34333 L353 L4343 L443 L5333 L534 L54 L633 L73 Q3 Q4 Q5
5 5
5

λ(W, S) 2.08102 1.88320 2.61803 2.15372 1.91650 1.58235 1.40127 1.84960 1.88320 2.08102 1.36000 1.91650 2.15372 1.72208 1.63557 3.09066 (2.89005) 2.57747 2.43750 (2.3963) 2.61803

det(xI − w) (1 + x)(1 − x − 2x2 − x3 + x4 ) (1 + x)2 (1 − 2x + x2 − 2x3 + x4 ) (1 + x)2 (1 − 3x + x2 ) (1 + x)2 (2 − 3x − (1 + x)(2 − x − √ √ 5x + 2x2 ) √ 5x3 + 2x4 )

5

5x − x3 −

1 − x2 − 2x3 − x4 + x6 1 − x2 − x3 − x4 + x6 2+x− √ √ √ 5x − 2 5x2 + x3 − 5x3 + 2x4

(1 + x)(1 − 2x + x2 − 2x3 + x4 ) 1 − x − 2x2 − x3 + x4 (1 + x)(2 − x − 2−x− √ √ 5x + 2x2 − x3 − √ 5x3 + 2x4 √ 3 5x + 2x4 )

5

5x − x3 − √

5

(1 + x)(2 − 3x −

5x + 2x2 )

6

1 − x − x2 − x3 + x4 (1 + x)(1 + x + x2 − 4x cos2 π/7) (1 + x)(1 − 2x − √ 2x + x2 )

7

√ 1 − x − x2 − 2 2x2 − x3 + x4 (1 + x)(1 − 2x + x2 − (1 + x)3 (1 − 3x + x2 ) (1 + x)4 (1 − 3x + x2 ) √ 2x2 − 2x3 + x4 )

X5

X6

2.61803

Table 5. (Continued.)

27

The hyperbolic Coxeter systems of finite covolume with trivial radical are known and appear, for example, in [Hum, §6.8].1 There are 72 such Coxeter systems with |S| ≥ 4. For |S| ≤ 3 there are infinitely many, namely the (p, q, r) triangle groups with 1/p + 1/q + 1/r < 1. However among these, only the (3, 3, 4), (2, 4, 5) and (2, 3, 7) groups are minimal. Thus we obtain a list of 75 Coxeter systems containing all the minimal ones. Removing the non-minimal elements from this list of 75, we are left with the 38 diagrams shown in Table 5. Guide to Table 5. The first column in Table 5 gives the notation for the Coxeter system (W, S); the second, its diagram. The third column gives the approximate value of λ(W, S) = λCox (W, S). Note that λ(W, S) = β(W, S) for bipartite diagrams, so it is easily computed from the adjacency matrix. For the 5 diagrams which cannot be two-colored, β(W, S) is shown in parentheses. The last column gives the characteristic polynomial p(x) = det(xI − w) of a minimal Coxeter element. By Proposition 6.5, λ(W, S) is a zero of p(x). Our notation for Coxeter systems is based in part on the standard notation An , Bn , Dn , En spherical diagrams. To each of these spherical diagrams one can adjoin an extending node to obtain an affine diagram. Attaching one more hyperbolic node to the extending node by a single edge, we obtain the hyperbolic diagrams Ahn+2 , Bhn+2 , Dhn+2 and Ehn+2 . Note that λLehmer = λ(Eh10 ). The notation L4343 indicates a linear graph with four edges, whose weights are 4, 3, 4, and 3. Similarly K343 indicates a linear graph with edge weights 3, 4 and 3, but with an additional edge of weight 3 attached to the penultimate node. We denote by Qn a loop of n edges, one of which is doubled, and by X5 and X6 a pair of star-shaped diagrams in no particular series. Proof of Theorem 6.1. Suppose λ(W, S) > 1. By the preceding results and the bicolored bound (Theorem 5.1), there is a hyperbolic or higher-rank subsystem (WI , I), I ⊂ S, and a minimal hyperbolic diagram (W ′ , S ′ ) ≤ (WI , I) such that λ(W, S) = λCox (WI , I) ≥ β(WI , I) ≥ β(W ′ , S ′ ). Inspection of Table 5 shows β(W ′ , S ′ ) ≥ λLehmer for all minimal hyperbolic Coxeter systems, completing the proof.
1

In the first printing of this book, X5 is missing a weight on one of its edges.

28

7

Small Salem numbers

In this section we conclude by detailing some connections between the simplest Coxeter systems and small Salem and Pisot numbers. Salem and Pisot numbers. An algebraic integer λ > 1 is a Pisot number if its conjugates (other than λ itself) satisfy |λ′ | < 1. Similarly, an algebraic integer λ > 1 is a Salem number if its conjugates satisfy |λ′ | ≤ 1 and include 1/λ. (We allow quadratic Salem numbers.) It is known that the Pisot numbers form a closed subset P ⊂ R, homeomorphic to the ordinal ω ω , and that every Pisot number is a limit of Salem numbers (see e.g. [Sa]). The smallest Pisot number, λPisot ≈ 1.324717, is a root of x3 = x + 1, while the smallest accumulation point in P is the golden mean, √ 1+ 5 ≈ 1.61803, λGolden = 2 a root of x2 = x + 1. All Pisot numbers λ < λGolden + ǫ are known [DP]. The Salem numbers are less well-understood. It is conjectured that λLehmer ≈ 1.17628, a root of the 10th degree polynomial discovered by Lehmer and given in (1.1), is the smallest Salem number [Leh], [GH]. The catalog of 39 Salem numbers given in [B1] includes all Salem numbers λ < 1.3 of degree ≤ 20 over Q [B3]; it will be sufficient for the applications below. At present there are 47 known Salem numbers λ < 1.3, and the list of such is known to be complete through degree 40; see [B2], [Mos] and [FGR]. Salem numbers from Coxeter groups. A Coxeter system (W, S) is crystallographic if W preserves a lattice V (Z) ⊂ V . A Coxeter system is crystallographic iff every cycle in its diagram contains an even number of edges with weight 4 and an even number with weight 6, and no edge weights other than 3, 4, 6 and ∞ occur in the diagram [Hum, §5.13]. Proposition 7.1 Let (W, S) be a hyperbolic crystallographic Coxeter system, and suppose w ∈ W satisfies λ(w) > 1. Then λ(w) is a Salem number of degree at most |S| over Q.

Proof. Since w acts by an automorphism of V (Z) ∼ Z|S| , λ = λ(w) is an = algebraic integer of degree at most |S|. Since V is hyperbolic, w has exactly two eigenvalues outside the unit circle, namely λ±1 . All the other conjugates λ′ of λ also occur as eigenvalues of w, so they satisfy |λ′ | ≤ 1. Finally 1/λ must be a conjugate of λ, because the product of all conjugates of λ is an integer dividing det(w) = ±1. 29

Corollary 7.2 If (W, S) is hyperbolic, crystallographic, and bipartite, then β(W, S) is a Salem number. Note. The Coxeter system Ah2n is hyperbolic, crystallographic but not bipartite, and in fact β(Ah2n ) fails to be a Salem number for n ≥ 5 (it has 2 conjugates outside the unit circle). Since Coxeter elements minimize λ(w), they provide a geometric source of small Salem numbers. For example, from Table 5 one can verify: Proposition 7.3 The smallest Salem numbers of degrees 6, 8 and 10 coincide with the eigenvalues of Coxeter elements for Eh8 , Eh9 and Eh10 . In particular, β(Eh10 ) = λLehmer . Note these 3 diagrams are the hyperbolic versions of the exceptional spherical diagrams E6 , E7 and E8 . Pisot numbers as limits. A sequence of Coxeter systems can give a geometric form to a sequence of Salem numbers converging to a Pisot number. To give examples of this phenomenon, let Ya,b,c denote the Coxeter system whose diagram is a tree with 3 branches of lengths a, b and c, joined at a single node. For example, Eh8 = Y3,3,4 , Eh9 = Y2,4,5 and Eh10 = Y2,3,7 . Theorem 7.4 As n → ∞, we have β(Bhn ) → β(Ahn ) → λGolden from above, λPisot λPisot λPisot from above, from above, and from below.

β(Y2,3,n ) →

β(Dhn ) →

The values of β above, excluding the subsequence β(Ah2n ), are all Salem numbers. Proof. The sequences of Coxeter systems above are all hyperbolic, crystallographic and (excluding Ah2n ) bipartite, so β(Wn , Sn ) ranges through Salem numbers. The limiting behavior of the β(Wn , Sn ) is calculated in [Hof] for the case of Ahn ; the other cases are similar. Infinite diagrams. We remark that the diagrams for Bhn , Dhn and Y2,3,n all converge to the infinite diagram Y2,3,∞ if we use the triple-point as a basepoint. Similarly, Ahn converges to Y2,∞,∞. Suitably interpreted, we have β(Y2,3,∞ ) = λPisot and β(Y2,∞,∞ ) = λGolden . See [MRS] for more on Pisot numbers and infinite graphs. 30

Proposition 7.5 If an irreducible Coxeter system satisfies 1 < β(W, S) ≤ λGolden then its diagram is a tree. Proof. If the diagram is not a tree then (W, S) ≥ Ahn or (W, S) ≥ Qn for some n. In the first case we have β(W, S) ≥ β(Ahn ) > λGolden . In the second case we have β(W, S) ≥ β(Qn ), and one can check that β(Qn ) > 2 for all n. Small Coxeter systems. Using Theorem 7.4 we can enumerate the Coxeter systems (W, S) that are sufficiently close to spherical, in the sense that β(W, S) is sufficiently close to 1. Theorem 7.6 The only irreducible Coxeter systems with 1 < β(W, S) < λPisot are Y2,4,5 and Y2,3,n , n ≥ 7. Proof. Suppose 1 < β(W, S) < λPisot . By Proposition 7.5, the diagram D of (W, S) is a tree. We claim D has at least one vertex of degree 3 or more. Indeed, there exists a minimal hyperbolic Coxeter system with (W ′ , S ′ ) ≤ (W, S) and hence β(W ′ , S ′ ) < λPisot . Referring to Table 5, we find (W, S) ≥ Eh9 = Y2,4,5 or (W, S) ≥ Eh10 = Y2,3,7 . In particular, D contains a copy of the Y2,3,5 diagram, possibly with higher weights. Next we claim all the edges of D have weight 3. Indeed, an edge of weight 4 or more implies (W, S) ≥ Bhn for some n, which is impossible because β(W, S) < λPisot . In fact the tree D consists of 3 branches joined at a single node; otherwise (W, S) ≥ Dhn for some n, which is impossible because λ(Dhn ) > λPisot . Thus (W, S) = Ya,b,c for some a ≤ b ≤ c. We have (W, S) = Y2,4,5 if (W, S) ≥ Y2,4,5 , since otherwise we would have Similarly, (W, S) = Y2,3,n , n ≥ 7, if (W, S) ≥ Y2,3,7 , since otherwise we would have β(W, S) ≥ min (β(Y3,3,7 ), β(Y2,4,7 )) ≥ 1.40 > λPisot . β(W, S) ≥ min (β(Y3,4,5 ), β(Y2,5,5 ), β(Y2,4,6 )) > 1.36 > λPisot .

To see these Coxeter systems qualify, just note that β(Y2,3,n ) < λPisot for all n by Theorem 7.4, and β(Y2,4,5 ) < λPisot by Table 5.

31

Corollary 7.7 We have λPisot = inf{β(W, S) : (W, S) has higher rank}. Proof. Since Y2,4,5 and Y2,3,n , n ≥ 7 are hyperbolic Coxeter systems, we have β(W, S) ≥ λPisot if (W, S) has higher rank. To show this bound is best possible, let Y2,3,n ∨ Y2,3,n be the diagram obtained from two copies of Y2,3,n by identifying the nodes at the ends of the branches of length n. Let (Wn , Sn ) be the associated Coxeter system (the ‘double’ of Y2,3,n ). Then it is straightforward to check that β(Wn , Sn ) → λPisot and sig(Wn , Sn ) = (pn , 2) for all n ≫ 0. Thus λPisot is a limit of β(W, S) for higher-rank Coxeter systems. Corollary 7.8 Let (W, S) be a Coxeter system, and suppose w ∈ W satisfies 1 < λ(w) < λPisot . Then λ(w) is a Salem number. Proof. We may assume (W, S) is irreducible and w is essential; then 1 < β(W, S) ≤ λ(w) < λPisot , so (W, S) is either Y2,4,5 or Y2,3,n , n ≥ 7. All these Coxeter systems are hyperbolic and crystallographic, so λ(w) is a Salem number. Realizing small Salem numbers. As remarked above, there are 47 known Salem numbers < 1.3. By the preceding Corollary, λ(w) is also a Salem number whenever 1 < λ(w) < 1.3 < λPisot . Using the catalog of small Salem numbers, we can identify which ones occur. Theorem 7.9 Let (W, S) be a Coxeter system, and suppose 1 < λ(w) < 1.3, w ∈ W . Then λ(w) coincides with one of the 6 Salem numbers given in Table 6, and these all arise. Guide to Table 6. The first column in Table 6 gives the approximate value of the Salem number λ; the second, the irreducible Salem polynomial S(x) it satisfies; and the third, one or two ways in which λ arises in Coxeter groups as λ(w). For example, λ ≈ 1.26123 arises as λ(w) = β(Y2,3,9 ) for any Coxeter element w in Y2,3,9 , and as λ(w′ ) for a suitable (non-Coxeter) element w′ in Y2,3,7 . Automorphisms of lattices. To aid in the realization of Salem numbers via Coxeter groups, we quote a result from [GM]. 32

λ 1.17628 1.21639 1.23039 1.26123 1.28064 1.29349

Salem polynomial 1 + x − x3 − x4 − x5 − x6 − x7 + x9 + x10 1 − x4 − x5 − x6 + x10 1 − x3 − x5 − x7 + x10 1 − x2 − x5 − x8 + x10 1 − x3 − x4 − x5 + x8 1 − x2 − x3 + x5 − x7 − x8 + x10

Coxeter data β(Y2,3,7 ) Y2,3,7 β(Y2,3,8 ) β(Y2,3,9 ), β(Y2,3,10 ), β(Y2,3,11 ), Y2,3,7 β(Y2,4,5 ) Y2,3,7

Table 6. The 6 Salem numbers < 1.3 that can arise as λ(w).

Let O(IIp,1 ) denote the orthogonal group of the unique even, unimodular lattice of signature (p, 1), and let O+ (IIp,1 ) be the subgroup of index two preserving one sheet of the hyperboloid v·v = −1. It is known that O+ (II9,1 ) is isomorphic with the Coxeter group Y2,3,7 in its geometric representation [Vin2], [CS, Ch. 27]. A Salem polynomial is unramified if |S(−1)S(1)| = 1. Theorem 7.10 Let S(x) be an unramified Salem polynomial of degree 8n + 2. Then S(x) = det(xI − g) for some g ∈ O+ (II8n+1,1 ). Proof of Theorem 7.9. Let (W, S) be a Coxeter system with 1 < λ(w) < 1.3, w ∈ W . As remarked above, λ = λ(w) is a Salem number. We may assume w is essential; then 1 < β(W, S) < λ. Since β(Y2,3,n ) ≥ β(Y2,3,12 ) ≈ 1.30227 for n ≥ 12, Theorem 7.6 implies (W, S) is isomorphic to Y2,4,5 or to Y2,3,n , 7 ≤ n ≤ 11. Let d be the degree of λ over Q. Since λ is a Salem number, d is even; and we have d ≤ |S| by Proposition 7.1. Suppose (W, S) is isomorphic to Y2,4,5 . Then the condition d ≤ |S| = 9 leaves only one possibility for λ, namely the degree 8 Salem number given in Table 6. In fact, in the catalog of Salem numbers in the range [1, 1.3] given in [B1] (known to be complete through degree 20), every other number has degree 10 or more.

33

Now suppose (W, S) is isomorphic to Y2,3,n , 7 ≤ n ≤ 11, and d > 8. Then |S| = n + 3, so d = 10, 12 or 14. If d = 12 then we have λ ∈ [β(Y2,3,9 ), 1.3], and if d = 14 then λ ∈ [β(Y2,3,11 ), 1.3]. Referring to the catalog again, we find there are no Salem numbers of the required degrees in these ranges. Thus d = 10. There are 5 Salem numbers of degree 10 in the range [1, 1.3], and these complete the list of 6 numbers given in Table 6. To conclude, we check that all 6 Salem numbers arise via Coxeter groups. Five of them can be recognized as the Coxeter eigenvalues β(Y2,3,n ), 7 ≤ n ≤ 11. (The degree 8 number also arises as β(Y2,4,5 ).) Four of the degree 10 numbers in Table 6 are unramified; by Theorem 7.10, these arise as λ(g) for g ∈ O+ (II9,1 ), and hence as λ(w) for w in Y2,3,7 . All 6 numbers in the table are covered by at least once by these constructions, completing the proof.

Figure 7. The Coxeter diagram for W ⊂ O+ (II17,1 ). The second smallest Salem number. After Lehmer’s number, the second smallest known Salem number is λ ≈ 1.188368, with unramified minimal polynomial S(x) = 1 − x + x2 − x3 − x6 + x7 − x8 + x9 −

x10 + x11 − x12 − x15 + x16 − x17 + x18 .

It is known that reflections in the roots of II17,1 generate a Coxeter subgroup W of index two in O+ (II17,1 ) [Vin2], [CS, Ch. 27]; its diagram is shown in Figure 7. Combining Theorems 7.9 and Theorem 7.10 we obtain: Corollary 7.11 The Salem number λ ≈ 1.188368 arises as λ(g) for g ∈ O+ (II17,1 ), but not as λ(w) for any w in the Coxeter subgroup W ⊂ O+ (II17,1 ). In fact one can take g = g1 g2 , where g1 comes from the order 2 symmetry of the Coxeter diagram of W , and g2 is the bicolored Coxeter element of a Y2,3,7 subdiagram. Graph theory. We remark that the study of Coxeter systems via the values of β(W, S) contains, as a special case, the study of graphs G via the leading eigenvalues α(G) of their adjacency matrices. 34

For example, Shearer has shown the values of α(G) (even when restricted √ to trees) are dense in the interval [ 2 + 5, ∞) [Sh]. It follows that the values of β(W, S) are dense in [λGolden , ∞). On the other hand, graphs with √ α(G) < 2 + 5 have been classified, and it seems likely that a similar classification can be completed for Coxeter systems with β(W, S) < λGolden . A survey of work on the leading eigenvalues of graphs can be found in [CR].

References
[A’C] [BW] N. A’Campo. Sur les valeurs propres de la transformation de Coxeter. Invent. math. 33(1976), 61–67. H. S. Bear and M. L. Weiss. An intrinsic metric for parts. Proc. Amer. Math. Soc. 18(1967), 812–17.

[BLM] S. Berman, Y. S. Lee, and R. V. Moody. The spectrum of a Coxeter transformation, affine Coxeter transformations, and the defect map. J. Algebra 121(1989), 339–357. [Bou] N. Bourbaki. Groupes et alg`bres de Lie, Ch. IV–VI. Hermann, e 1968; Masson, 1981. [B1] [B2] [B3] [Bus] [BK] [CW] [Co] D. Boyd. Small Salem numbers. Duke Math. J. 44(1977), 315–328. D. Boyd. Pisot and Salem numbers in intervals of the real line. Math. Comp. 32(1978), 1244–1260. D. Boyd. Reciprocal polynomials having small measure. II. Math. Comp. 53(1989), 355–357. H. Busemann. The Geometry of Geodesics. Academic Press, 1955. H. Busemann and P. J. Kelly. Projective Geometry and Projective Metrics. Academic Press, 1953. J. W. Cannon and Ph. Wagreich. Growth functions of surface groups. Math. Ann. 293(1992), 239–257. A. J. Coleman. Killing and the Coxeter transformation of KacMoody algebras. Invent. math. 95(1989), 447–477.

35

[CS] [CR] [DP]

J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups. Springer-Verlag, 1999. D. Cvetkovi´ and P. Rowlinson. The largest eigenvalue of a graph: c a survey. Linear and Multilinear Algebra 28(1990), 3–33. J. Dufresnoy and Ch. Pisot. Etude de certaines fonctions m´romorphes born´es sur le cercle unit´. Application ` un ensemble e e e a ´ ferm´ d’entiers alg´briques. Ann. Sci. Ecole Norm. Sup. 72(1955), e e 69–92.

[FGR] V. Flammang, M. Grandcolas, and G. Rhin. Small Salem numbers. In Number Theory in Progress, Vol. I, pages 165–168. de Gruyter, 1999. [Fl] [FP] [GH] [GM] W. J. Floyd. Growth of planar Coxeter groups, P.V. numbers, and Salem numbers. Math. Ann. 293(1992), 475–483. W. J. Floyd and S. P. Plotnick. Growth functions on Fuchsian groups and the Euler characteristic. Invent. math. 88(1987), 1–29. E. Ghate and E. Hironaka. The arithmetic and geometry of Salem numbers. Bull. Amer. Math. Soc. 38(2001), 293–314. B. Gross and C. McMullen. Automorphisms of even unimodular lattices and unramified Salem numbers. J. Algebra 257(2002), 265– 290. L. Halbeisen and N. Hungerb¨hler. On periodic billiard trajectories u in obtuse triangles. SIAM Rev. 42(2000), 657–670. P. de la Harpe. An invitation to Coxeter groups. In Group Theory from a Geometrical Viewpoint (Trieste, 1990), pages 193–253. World Sci. Publishing, 1991. P. de la Harpe. On Hilbert’s metric for simplices. In Geometric Group Theory, Vol. 1 (Sussex, 1991), pages 97–119. Cambridge University Press, 1993. ¨ D. Hilbert. Uber die gerade Linie als k¨rzeste Verbindung zweier u Punkte. Math. Ann. 46(1895), 91–96. E. Hironaka. The Lehmer polynomial and pretzel links. Canad. Math. Bull. 44(2001), 440–451. 36

[HH] [Ha1]

[Ha2]

[H] [Hir]

[Hof]

A. J. Hoffman. On limit points of spectral radii of non-negative symmetric integral matrices. In Graph Theory and Applications, volume 303 of Lecture Notes in Mathematics, pages 165–172. SpringerVerlag, 1972.

[How] R. B. Howlett. Coxeter groups and M -matrices. Bull. London Math. Soc. 14(1982), 137–141. [Hum] J. E. Humphreys. Reflection Groups and Coxeter Groups. Cambridge University Press, 1990. [Leh] D. H. Lehmer. Factorization of certain cyclotomic functions. Ann. of Math. 34(1933), 461–479.

[MRS] J. F. McKee, P. Rowlinson, and C. J. Smyth. Pisot numbers from stars. In Number Theory in Progress, Vol. I, pages 309–319. de Gruyter, 1999. [Mos] M. J. Mossinghoff. Polynomials with small Mahler measure. Math. Comp. 67(1998), 1697–1705. [Par] [RT] [Sa] [Sh] W. Parry. Growth series of Coxeter groups and Salem numbers. J. Algebra 154(1993), 406–415. H. Rademacher and O. Toeplitz. The Enjoyment of Mathematics. Dover, 1990. R. Salem. Algebraic Numbers and Fourier Analysis. Wadsworth, 1983. J. B. Shearer. On the distribution of the maximum eigenvalue of graphs. Linear Algebra Appl. 114/115(1989), 17–20.

` [Vin1] E. B. Vinberg. Discrete groups that are generated by reflections. Math. USSR Izv. 5(1971), 1083–1119. ` [Vin2] E. B. Vinberg. Some arithmetical discrete groups in Lobaˇevski˘ c ı spaces. In Discrete subgroups of Lie groups and applications to moduli (Bombay, 1973), pages 323–348. Oxford Univ. Press, 1975. Mathematics Department Harvard University 1 Oxford St Cambridge, MA 02138-2901 37