# Lorentzian Coxeter groups and Boyd-Maxwell ball packings.

1 Introduction

Apollonian ball packings form a renowed class of infinite ball packings, see for instance [GLM+05, GLM+06]. Boyd-Maxwell ball packings are generated by inversions, generalizing Apollonian ball packings. We name these packings after Boyd, who first studied them in [Boy74], and Maxwell, who related them to Lorentzian Coxeter groups in [Max82]. Here, we revisit Boyd-Maxwell ball packings. This retrospective is motivated by recent studies on limit roots of infinite Coxeter groups.

Limit roots were introduced and studied in [HLR14]. They are the limit directions of the roots in a geometric representation of an infinite Coxeter system. Properties of limit roots of infinite Coxeter groups were investigated in a recent series of papers, see [HLR14, DHR13, HPR13]. In many examples, the Coxeter group acts as a discrete reflection group on Lorentz space, and patterns of fractal ball packings appear, see Figure 1. A description of this fractal structure is conjectured in [HLR14, Section 3.2] and proved in [DHR13, Theorem 4.10].

While investigating limit roots, we observed that patterns appearing in these examples are similar to Boyd-Maxwell ball packings. The main result here relates the set of limit roots to Boyd-Maxwell ball packings. More specifically, Theorem 3.3 states that the set of limit directions of weights of a Lorentzian Coxeter group W is equal to its set of limit roots. This result allows to conclude that for a Lorentzian Coxeter system (W, S) with Maxwell's condition, namely that (W, S) is of level 2, the set of limit roots is the complement of the interiors of all balls in the Boyd-Maxwell packing, see Corollary 3.4. Moreover, even if Maxwell's condition is not satisfied, the statement is generalized to non-packing clusters of balls, see Corollary 3.5. In [CL13], we also study the tangency graphs of Boyd-Maxwell ball packings and enumerate level-2 Coxeter systems.

In Section 2, we recall the notions of geometric representations of Coxeter system, limit root, and review the work of Boyd and Maxwell. In Section 3, we relate limit weights, limit roots and Boyd-Maxwell ball packings and examine a generalization to ball clusters.

2 Coxeter groups, limit roots and Boyd-Maxwell Packings

2.1 Geometric representation of a Coxeter group

Let (W, S) be a finitely generated Coxeter system, where S = {[s.sub.1], [s.sub.2], ..., [s.sub.n]} is a finite set of generators and the Coxeter group W is generated by the relations [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with [m.sub.ii] = 1 and [m.sub.ij] [greater than or equal to] 2 or = to if i [not equal to] j. The cardinality [absolute value of S] = n is the rank of the Coxeter system (W, S). Let V be a real vector space of dimension n, equipped with a basis [DELTA] = {[[alpha].sub.1], [[alpha].sub.2], ..., [[alpha].sub.n]}. Given a Coxeter system (W, S), we define a bilinear form B as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [c.sub.ij] are chosen arbitrarily with [c.sub.ij] = [c.sub.ji] [greater than or equal to] 1. For a non-isotropic vector [alpha] [member of] V, we define the reflection [[sigma].sub.[alpha]]

[[sigma].sub.[alpha]](x): = x - 2 [B(x, [alpha])/B([alpha], [alpha])] [alpha] a for all x [member of] V. (1)

Then the homomorphism [rho]: W [right arrow] GL(V) that sends [s.sub.i] to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a faithful geometric representation of the Coxeter group W as a discrete subgroup of the orthogonal group [O.sub.B](V), i.e., the group of linear transformations of V preserving the bilinear form B. The group W acts on (V, B) by w(x) = [rho](w)(x). We refer the readers to [Hum92, Chapter 5] and [HLR14, Section 1] for more details.

If the bilinear form B is of signature (n - 1,1), the pair (V, B) is called a n-dimensional Lorentz space and the Coxeter system (W, S) with W acting on (V, B) is said to be Lorentzian. By abuse of language, we also say that W is a Lorentizian Coxeter group.

Remark 2.1 Being Lorentzian is an extrinsic property of the Coxeter system (W, S) since it depends on the choice of the bilinear form B associated to the vector space V on which W acts. In the present investigation, we are mainly concerned with Coxeter groups acting on Lorentz space, therefore we call them Lorentzian. In the literature, the term hyperbolic is used, but with different meanings, see for instance [Bou68, Vin71, Max78, Max82, Hum92, DHR13].

In a Lorentz space, a vector x is space-like (resp. time-like, light-like) if B(x, x) is positive (resp. negative, zero). The set of light-like vectors Q = {x [member of] V | B(x, x) = 0} form a cone called the light cone.

Let [PHI] = W([DELTA]) be the orbit of [DELTA] under the action of W. Then the pair ([PHI], [DELTA]) is a based root system. The vectors in [DELTA] are called simple roots, and the vectors in [PHI] are called roots. Let [V.sup.*] be the dual vector space of V with dual basis [[DELTA].sup.*]. If the bilinear form B is non-singular, which is the case for Lorentz spaces, [V.sup.*] can be identified with V, and [[DELTA].sup.*] = {[[omega].sub.1], [[omega].sub.2], ..., [[omega].sub.n]} can be identified with a set of vectors in V such that

B([[alpha].sub.i], [[omega].sub.j]) [[delta].sub.ij], (2)

where [[delta].sub.ij] is the Kronecker delta function. Vectors in [[DELTA].sup.*] are called fundamental weights, and vectors in the orbit

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

are called weights. We refer the readers to [Bou68, Chapter VI, Section 1.10] for more details.

2.2 Limit roots

To study the asymptotic directions of the roots, we pass to the projective space PV, i.e., the topological space of 1-dimensional subspaces of V. For a non-zero vector x [member of] V \ {0}, let [??] [member of] PV denote the line passing through x and the origin. The group action of W on V by reflection induces a projective action of W on PV:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For a set X [subset] V, we define the corresponding projective set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In this sense, we have projective roots [??], projective weights [??] and the projective light cone [??].

Let h(x) denote the sum of the coordinates of x in the basis [DELTA], and call it the height of the vector x. We say that x is future-directed (resp. past-directed) if h(x) is positive (resp. negative). The hyperplane {x [member of] V | h(x) = 1} is the affine subspace aff ([DELTA]) spanned by the simple roots. It is useful to identify the projective space PV with the affine subspace aff ([DELTA]) with a projective hyperplane added at infinity. For a vector x [member of] V, if h(x) [not equal to] 0, [??] is identified with the projective vector

x/h(x) [member of] aff([DELTA]).

Otherwise, if h(x) = 0, the direction x is identified to a point on the projective hyperplane at infinity. In fact, if h(x) = 0, x is identified with the intersection of aff ([DELTA]) with the straight line passing through x and the origin. In this sense, the projective roots [??], projective weights [??] and projective light cone [??] are respectively identified with the intersection of aff ([DELTA]) with the 1-subspaces spanned by the roots [PHI], weights [OMEGA] and light-like vectors. The projective light cone [??] is projectively equivalent to a sphere. In Figure 2, simple roots, fundamental weights and some positive roots are represented in aff ([DELTA]).

Definition 2.2 (Hohlweg-Labbe-Ripoll [HLR14, Definition 2.12]) The set E([PHI]) of limit roots is the set of accumulation points of [??], in other words,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 2.7 of [HLR14] asserts that

E([PHI]) [subset or equal to] [??] [intersection] cone([DELTA]).

Consequently, there is no limit root in the set [??] cone([DELTA]). If the set [??] \ cone([DELTA]) consists of open spherical caps, it was conjectured that E([PHI]) is equal to the complement of the W-orbit of these caps, see [HLR14, Conjecture 3.9]. This conjecture is proved in [DHR13, Theorem 4.10], and presented here in Theorem 2.3. The aim here is to relate this result to the one of Maxwell, see Theorem 2.4.

Theorem 2.3 ([DHR13, Theorem 4.10], [HMN13, Theorem 1.2]) Let [(W, S).sub.B] be an irreducible Lorentzian Coxeter system. Then

E([PHI]) = [??] \ (W x ([??] \ conv([DELTA]))).

In particular, if [??] [subset] conv([DELTA]), then E([PHI]) = [??].

2.3 Boyd-Maxwell packing

In a metric space, a ball packing is a set of balls with disjoint interiors. A famous example is the Apollonian ball packing, see for instance [Boy73, BdPP94, [GLM.sup.+]05, [GLM.sup.+]06, Che13]. The residual set of a ball packing is the complement of the interiors of all balls in the packing. An Apollonian packing can be generated by inversions. In [Boy74], Boyd presents a new class of infinite ball packings generalizing this construction process. Moreover, he notices a connection to reflection groups. In [Max82], Maxwell revisits these packings, and interprets them using Lorentzian Coxeter groups.

Given a space-like vector x in the Lorentz space (V, B), the normalized vector x of x is given by

[bar.x] = x/[square root of B(x, x)]

The normalized vector x lies on the one-sheet hyperboloid H = {x [member of] V |B(x, x) = 1}. For n > 2, there is a classical correspondence between (n-2)-dimensional balls and space-like directions in n-dimensional Lorentz space, see for example [Max82, Section 2], [Cec08, Section 2.2] or [HJ03, Section 1.1]. Given a space-like vector x, let [H.sub.x] be the orthogonal hyperplane [H.sub.x] = {x' [member of] V | B(x, x') = 0}. The intersection of [??] with the projective half-space [[??].sup.-.sub.x] = {x' [member of] PV | B(x, x') [less than or equal to] 0} is a closed ball (spherical cap) on [??]. We denote this ball by Ball(x). After a stereographic projection, Ball(x) becomes a ball in an (n - 2)-dimensional Euclidean space. For two space-like vectors x and x', if they are not both future-directed, we have

* Ball(x) and Ball(x') are disjoint if B([bar.x], [bar.x]') < -1;

* Ball(x) is tangent to Ball(x') if B([bar.x], [bar.x]') = -1;

* The boundary of Ball(x) and Ball(x') intersect transversally if B([bar.x], [bar.x]') > -1;

Therefore, if a set of space-like vectors represents a ball packing, we must have B([bar.x], [bar.x]') < -1 for any two vectors. The packing corresponding to a pair of opposite vectors {x, -x} is said to be trivial.

To encode both the Coxeter system (W, S) and the bilinear form B, we adopt Vinberg's convention for Coxeter graphs. Namely, if [c.sub.ij] > 1 the edge ij is dotted and labeled by -[c.sub.ij]. A graph G is said to be of level 0 if it represents a finite or affine Coxeter system (W, S). The list of level-0 Coxeter graphs can be found in [Hum92, Chapter 2]. A graph G is of level [less than or equal to] r if every induced subgraph of G on n - r vertices is of level 0. A graph G is of level r if it is of level [less than or equal to] r but not of level [less than or equal to] r - 1. Correspondingly, a Coxeter system (W, S) with a Coxeter graph of level r is said to be of level r.

For a Lorentzian Coxeter system (W, S), let [[OMEGA].sub.r] be the set of space-like weights. Maxwell proved that Coxeter groups of level 2 are Lorentzian [Max82, Proposition 1.6] and the following theorem.

Theorem 2.4 (Maxwell [Max82, Theorem 3.2]) Let (W, S) be a Lorentzian Coxeter system and [[OMEGA].sub.r] its set of space-like weights. The set {Ball([omega]) | [omega] [member of] [[OMEGA].sub.r]} is a ball packing if and only if W is of level 2.

We call the ball packing in Theorem 2.4 the Boyd-Maxwell ball packing generated by the Coxeter system (W, S), and denote it by P (W, S). Maxwell manually enumerated the Coxeter graphs representing irreducible Coxeter groups of level 2, and suggested a computer verification. This is done in [CL13, Section 5].

3 Relation between limit roots, limit weights and Boyd-Maxwell Packings

From now on, we assume that (W, S) is a Coxeter system with W acting on a non-singular space (V, B). We define the set of limit weights E([OMEGA]) analogously to limit roots.

Definition 3.1 The set of limit weights E([OMEGA]) is the set of accumulation points of the projective weights [??]. That is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

As we know, limit roots lie in the isotropic cone Q. Here is an analogous result for limit weights.

Theorem 3.2 Consider an injective sequence of weights [([w.sub.k]).sub.k [member of] N] and suppose that [([[??].sub.k]).sub.k [member of] N] converges to a limit f. Then

(i) h([[omega].sub.k]) tends to -[infinity],

(ii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

When (V, B) is a Lorentz space, even more is true.

Theorem 3.3 The set of limit weights of a Lorentzian Coxeter system (W, S) is equal to its set of limit roots. That is, E([OMEGA]) = E([PHI]).

Figure 3 illustrates the result of the previous theorem.

We denote the set of space-like weights by [[OMEGA].sub.r]. It is the union of the orbits of space-like fundamental weights. Space-like weights in [[OMEGA].sub.r] correspond to balls in the Boyd-Maxwell ball packing P(W, S). From this correspondence, we get the following corollary of Theorem 3.2.

Corollary 3.4 The set E (\$) of limit roots of an irreducible Lorentzian Coxeter system (W, S) of level 2 is equal to the residual set of the Boyd-Maxwell ball packing P(W, S).

Let us now explain the relation between ball packings studied by Boyd and Maxwell and ball packings observed in the study of limit roots. In the point of view of [HLR14] and [DHR13], (W, S) is of level 2 if and only if [??] \ conv([DELTA]) is not empty and consists of a union of disjoint spherical caps. We notice from Equation (2) that

aff([DELTA] \{[alpha]}) = aff([DELTA]) [intersection] [H.sub.[omega]], [for all][alpha] [member of] [DELTA],

where [omega] is the fundamental weights corresponding to the simple root [alpha]. In other words, the supporting hyperplane aff([DELTA] \ {[alpha]}) of the simplex conv([DELTA]) is exactly the intersection of aff([DELTA]) and the orthogonal hyperplane for the fundamental weight w. Therefore, the spherical caps obtained by the space-like fundamental weights are exactly the spherical caps in [??] conv([DELTA]). Consequently, if the Coxeter system is Lorentzian of level 2, the fractal structure described in Theorem 2.3 is the residual set of the Boyd-Maxwell ball packing described in Theorem 2.4.

For a Lorentzian Coxeter system of level [less than or equal to] 1, every facet of conv([DELTA]) is disjoint from, or tangent to Q. In this case, as observed in [HPR13, DHR13], E([PHI]) = [??], so no pattern of ball packing or ball cluster appears. In the framework of Maxwell, it can be explained by the absence of space-like weights. For a Lorentzian Coxeter system of level higher than 2, the space-like weights still represent (n - 2)-dimensional balls, but some balls will intersect each other. We name this configuration Boyd-Maxwell ball cluster generated by the Coxeter group, see Figure 1(b) for an example. The notion of residual set naturally extends to ball clusters. To generalize Corollary 3.4 to Boyd-Maxwell ball clusters, most of the arguments and discussions in the previous part applies. However, slight modifications are necessary. Finally, we obtain the following corollary, which completes the connection between Theorem 2.3 and 2.4.

Corollary 3.5 The set E([PHI]) of limit roots of an irreducible Lorentzian Coxeter system (W, S) is equal to the residual set of the Boyd-Maxwell ball cluster generated by (W, S).

References

[BdPP94] M. Borkovec, W. de Paris, and R. Peikert. The fractal dimension of the Apollonian sphere packing. Fractals, 2(4):521-526, 1994.

[Bou68] Nicolas Bourbaki. Groupes et algebres de Lie. Chapitre 4-6. Paris: Hermann, 1968.

[Boy73] David W. Boyd. The osculatory packing of a three dimensional sphere. Canad. J. Math., 25:303-322, 1973.

[Boy74] David W. Boyd. A new class of infinite sphere packings. Pacific J. Math., 50:383-398, 1974.

[Cec08] Thomas E. Cecil. Lie Sphere Geometry. Universitext. Springer, New York, 2 edition, 2008.

[Che13] Hao Chen. Apollonian ball packings and stacked polytopes. preprint, arXiv:1306.2515, page 20 pp., 2013.

[CL13] Hao Chen and Jean-Philippe Labbe. Lorentzian Coxeter groups and Boyd-Maxwell Packings. preprint, arXiv:1310.8608v2, page28 pp., 2013.

[DHR13] Matthew Dyer, Christophe Hohlweg, and Vivien Ripoll. Imaginary cones and limit roots of infinite coxeter groups. preprint, arXiv:1303.6710, page 63 pp, 2013.

[GLM+05] Ronald L. Graham, Jeffrey C. Lagarias, Colin L. Mallows, Allan R. Wilks, and Catherine H. Yan. Apollonian circle packings: geometry and group theory. I. The Apollonian group. Discrete Comput. Geom., 34(4):547-585, 2005.

[GLM+06] Ronald L. Graham, Jeffrey C. Lagarias, Colin L. Mallows, Allan R. Wilks, and Catherine H.

Yan. Apollonian circle packings: geometry and group theory. III. Higher dimensions. Discrete Comput. Geom., 35(1):37-72, 2006.

[HJ03] Udo Hertrich-Jeromin. Introduction to Mobius Differential Geometry, volume 300 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2003.

[HLR14] Christophe Hohlweg, Jean-Philippe Labbe, and Vivien Ripoll. Asymptotical behaviour of roots of infinite Coxeter groups. Canad. J. Math., 66(2):323-353, 2014.

[HMN13] Akihiro Higashitani, Ryosuke Mineyama, and Norihiro Nakashima. An analysis of infinite Coxeter groups: the case of type (n-1,1) Coxeter matrices. preprint, arXiv:1212.6617, page 18 pp, September 2013.

[HPR13] Christophe Hohlweg, Jean-Philippe Preaux, and Vivien Ripoll. On the limit set of root systems of Coxeter groups and Kleinian groups. preprint, arXiv:1305.0052, page 24 pp, 2013.

[Hum92] James E. Humphreys. Reflection groups and Coxeter groups. Cambridge Studies in Advanced Mathematics. 29 (Cambridge University Press), 1992.

[Max78] George Maxwell. Hyperbolic trees. J. Algebra, 54(1):46-49, 1978.

[Max82] George Maxwell. Sphere packings and hyperbolic reflection groups. J. Algebra, 79(1):78-97, 1982.

[Vin71] Ernest B. Vinberg. Discrete linear groups that are generated by reflections. Izv. Akad. Nauk SSSR. Ser Mat., 35:1072-1112, 1971.

Hao Chen * and Jean-Philippe Labbe ([dagger])Hao Chen * and Jean-Philippe Labbe ([dagger])

Freie Universitat Berlin, Institut fur Mathematik, Arnimallee 2, 14195 Berlin, Germany

* supported by the Deutsche Forschungsgemeinschaft within the Research Training Group "Methods for Discrete Structures" (GRK 1408). haochen@math.fu-berlin.de

([dagger]) supported by a the SFB Transregio "Discretization in Geometry and Dynamics" (TRR 109). labbe@math.fu- berlin.de