At SPUR this summer I’ll be working on the Kazhdan-Lusztig polynomials, although my mentor and I haven’t quite pinned down what problem I’m working on. I thought I’d take the chance to share some interesting mathematics and also to write up some background for my own benefit. I’ll mostly be following the second half of Humphreys.

A **Coxeter system** is a group together with a generating set and presentation of the form

where , and . (When there is no relation between , we write this as .) The group is a **Coxeter group**, and is usually understood to come with a preferred presentation, so we will often abuse terminology and use “group” and “system” interchangeably. is also referred to as the set of **simple reflections** in , and the **rank.** (We will only consider finitely-generated Coxeter groups.)

Historically, Coxeter groups arose as symmetry groups of regular polytopes and as Weyl groups associated to root systems, which in turn are associated to Lie groups, Lie algebras, and/or algebraic groups; the former are very important in understanding the latter. John Armstrong over at the Unapologetic Mathematician has a series on root systems. In addition, for a non-technical overview of Coxeter groups and -analogues, I recommend John Baez’s week184 through week187. The slogan you should remember is that Weyl groups are “simple algebraic groups over .”

**Coxeter diagrams**

A convenient way of describing a Coxeter system is through the construction of its Coxeter diagram. This is a graph whose vertices are the elements of and where there is an edge between and with label if , although traditionally edges with label are left unlabeled. This is because if and only if and commute. It follows that if the Coxeter diagram of a Coxeter system is disconnected, is the direct product of the Coxeter groups associated to each connected component of the Coxeter diagram. A Coxeter system is called **irreducible** if its Coxeter diagram is connected, and from now on we will only talk about irreducible Coxeter systems.

**Alternating subgroups**

Thanks to the nature of the relations in a Coxeter group, the assignment always gives a homomorphism for any Coxeter group. This is called the **sign** homomorphism, and reflects the fact that the generators are supposed to act as reflections. The kernel of the sign homomorphism is called the **alternating subgroup** of . One might think of it as the “orientation-preserving” elements of .

**Examples**

The only Coxeter group of rank is , so that’s not very interesting.

The irreducible Coxeter groups of rank are precisely the finite and infinite dihedral groups. When is finite, can be thought of as a reflection across, say, the -axis in , and can be thought of as a reflection across the line . When is infinite, can be thought of as a reflection across a line which makes an angle to the -axis which is not a rational multiple of . The sign homomorphism is the determinant of the corresponding linear transformation on , and the alternating subgroup is the subgroup of rotations.

An important class of finite Coxeter groups occurs when and ; their Coxeter diagrams are the path graphs. The resulting Coxeter group of rank is none other than the symmetric group with generators (and this is where the sign homomorphism and the alternating subgroup get their name), and it is the Weyl group associated to the general linear group and its relatives. This relationship is ultimately responsible for the identity

where the LHS counts permutations according to their inversions and the RHS is the -factorial, one interpretation of which is the number of maximal flags of . This relationship generalizes to other Weyl groups, but we won’t pursue this connection here.

Note that is equivalent to the **braid relation** . It is instructive to prove this by writing out permutations in “graphical notation,” as this is the fundamental relation describing the braid group. (One can also associate generalized braid groups to any Coxeter system.)

A particularly interesting class of examples of Coxeter systems are the Coxeter systems of rank , which are (more or less) the triangle groups (and the corresponding alternating subgroups are the von Dyck groups). Given a rank Coxeter system, construct a triangle with angles . (The triangle does not necessarily live in the Euclidean plane; this construction requires the triangle to be curved in general.) Then the reflections across each side of the triangle generate a group isomorphic to the corresponding Coxeter group, essentially because of our earlier discussion about dihedral groups. One can think of these reflections as instructions for patching together copies of the triangle. Eventually, one of three things will happen in this process.

- If the triangle’s angles add up to , the copies of the triangle will form a tessellation of . This only occurs in finitely many cases, which are described in the Wikipedia article.
- If the triangle’s angles add up to greater than , the copies of the triangle will form a tessellation of the sphere. This is related to the McKay correspondence, and again the cases are described in the Wikipedia article.
- If the triangle’s angles add up to less than , the copies of the triangle will form a tessellation of the hyperbolic plane. This is the “generic” case, since it occurs whenever are sufficiently large.

This division between Euclidean, spherical, and hyperbolic geometry is a common theme throughout mathematics; it is particularly fundamental, for example, in the uniformization theorem for surfaces.

Of particular interest outside of the theory of Coxeter groups is the triangle group. By a special case of the Gauss-Bonnet theorem, the area of a hyperbolic triangle is proportional to the amount by which its angle sum is less than . Among the hyperbolic triangles above, the one of maximal angle sum, hence minimal area, has angle measures (exercise!). This observation turns out to imply, at least heuristically, Hurwitz’s theorem on the automorphisms of a Riemann surface of genus greater than . In particular, the automorphism group of a Hurwitz surface is a finite quotient of the alternating subgroup of the triangle group. (On that note, there is a beautiful paper by Noam Elkies, the Klein quartic in number theory, on the most famous Hurwitz surface.)

Also of particular interest is the triangle group , which has the property that one of the vertices of the corresponding hyperbolic triangle is “at infinity” and consequently has hyperbolic angle zero. It is in fact isomorphic to . With relations , the isomorphism is given by

Its alternating subgroup is the infamous modular group, whose action on the hyperbolic plane we’ve discussed before.

**The geometric representation**

So far we know nothing about an arbitrary Coxeter group except that its order is at least two. In particular, we we don’t know that actually has order exactly . This will be rectified by constructing a particularly well-behaved linear representation of an arbitrary Coxeter group.

The **geometric representation** of a Coxeter group is defined as follows. Let be the free vector space on the basis . Define a bilinear form on by extending

bilinearly. We are going to represent as a “reflection” across the hyperplane orthogonal to , and in that case the above bilinear form is precisely what the inner product “should be” in order to agree with what we said above about dihedral groups. ( won’t actually act as a reflection in the usual sense unless is positive-definite.) We now define

.

By construction, and for all orthogonal to ; exactly what a reflection would do (again, if were positive-definite). It follows that has order . It’s also not hard to show that preserves the bilinear form, hence so does any element in the group generated by the in . But we don’t know yet whether this group is actually .

**Claim:** .

*Proof.* Restrict to the subspace spanned by . Computation shows that is positive-semidefinite when restricted to , and in particular is positive-definite if and only if (exactly as one would expect from our discussion of dihedral groups above). It also shows that fix . When , we compute that , which implies that is the rotation through radians. When , we compute that

from which it follows that has infinite order as desired.

It follows that there is a unique homomorphism sending to , hence that really does have order for all in . However, we do not yet know whether has trivial kernel. We will show this in the next section.

(Aside: we do know that if is positive-definite, the geometric representation actually maps into the orthogonal group, so the corresponding Coxeter groups (which turn out to be precisely the finite Coxeter groups) act on a sphere. In the rank case, this is precisely the action of the spherical triangle groups described above. In the “simply laced” case where (hence the corresponding Coxeter diagram has only unlabeled edges), it’s not hard to see that where is the adjacency matrix of the Coxeter diagram, hence that is positive-definite if and only if has spectral radius less than . This is the connection which is responsible for the ADE classification showing up both here and in the McKay correspondence, and in fact one can classify the finite Coxeter groups by a process almost exactly like that used in the linked post, except that we must take labels into account. The affine Dynkin diagrams that occur there are associated to the simply laced affine Weyl groups, which are the ones where is positive-semidefinite and has corank (in the simply laced case, the ones where has spectral radius exactly ), which are in turn associated to affine Lie algebras.)

**The length function**

Since all the generators square to the identity, we know that any element of can be written as a word in the generators, without the need for inverses, such that no two consecutive generators are the same. Let the **length** of an element denote the minimal length of such a word. When is a Weyl group, the length of a word corresponds to the dimension of the corresponding cell in the Bruhat decomposition of the corresponding flag variety. (This is merely by way of motivation and has nothing to do with how we will use the length function.)

*Example.* The length function on is the number of inversions.

Below is a list of elementary properties of the length function.

- .
- if and only if .
- (the triangle inequality).
- .
- for all .
- .

It follows that is always either equal to or to . To determine which is the case, we turn to the geometric representation. First, we declare by convention that in order to simplify our notation.

The **root system** of in its geometric representation is the set of all vectors of the form . (This notion of root system is more general than the notion used in Lie theory.) Any root can be written in the form

where, to distinguish them from the other roots, we will refer to the as the **simple roots.** Call a root **positive** if for all , and write . Similarly, call a root **negative** if for all , and write . Let denote the positive and negative roots, respectively.

If , let denote the **parabolic subgroup** of generated by the elements of and let denote the corresponding length function, with . (The name comes from the corresponding notion in the theory of algebraic groups.) Although we have not proven it yet, it will turn out that the restriction of the presentation of to makes a Coxeter group and that . For now, all we know is that .

**Theorem:** If , then . (Consequently, if , then .)

*Proof.* We proceed by induction on the length of . The statement is obvious when . In general, let be a generator that appears as the last letter in a reduced word for ; then and . We want to write as a product of two words in a sufficiently clever way that we can apply the inductive hypothesis. To this end, let and let be the set of all words such that and . Clearly , so is nonempty. Let be an element in of minimal length, and write

.

Since , it follows that , so we will be able to apply the inductive hypothesis to once we know that .

Suppose to the contrary that that . Then we can argue as follows. By the triangle inequality,

.

The hypothesis implies that , whereas the fact that implies that . But this implies

.

It follows that the first inequality must be an equality, hence that . But has minimal length in ; contradiction. Hence , and the inductive hypothesis applies to . By induction, it follows that . The same argument shows that , hence that . It now remains to show that maps to a non-negative linear combination of .

We now claim that . Otherwise, we get

which contradicts the inductive hypothesis. It follows that a reduced expression for in , which can only be an alternating product of , must end in . The rest is computation and casework.

**Case:** . Then , hence , and so forth.

**Case:** . It follows that is a product of less than terms of the form together with possibly an in front. Now, observe that rotates an angle of towards , hence less than such rotations keep us within the cone spanned by . It's also not hard to see (draw a picture!) that the extra reflection caused by a starting also keeps us within this cone.

**Corollary:** Every root is either positive or negative.

**Corollary:** The geometric representation is faithful.

*Proof.* Suppose is not the identity but is in the kernel of . Then there exists such that , hence . But the identity fixes ; contradiction.

on July 25, 2010 at 9:36 am |TsektsemutsHey, great blog. I can’t understand 99% of it, but I like the title. For Coxeter polytopes, there’s a really good program called Jenn3d, not in the Debian repos unfortunately, but easy to compile. The author originally wrote the program in order to play weiqi in three dimensions, but ended up totally rewriting it.