# Orders on Coxeter Groups — with a Problem Set!

So, David, how do weak order and bruhat order work on the permutation group, S_n ? As I understand, Coxeter groups are (finitely generated?) reflection groups and your description of a particular element depends on your choice of presentation. These two orders have to do with the length of the “reduced” word representing a particular element. I still don’t totally get how this works. Also, do they form a distributive lattice under these orders?

That’s a great question, but I have a talk and two papers to work on (and at least one of my coauthors is reading this blog!) So I’ll make it a problem set. If you want to work out the case of weak order on $S_n$ for yourself, read on, then join in in the comments!

There are several different orders people like to consider on Coxeter groups. I will discuss the two most important, called weak order and strong order. Weak order is a lattice, but not a distributive lattice. Strong order is not a lattice. Strong order is also sometimes called “Bruhat order”, and weak order is also sometimes called “weak Bruhat order”.

A Coxeter group is a group generated by a set S. The theory permits S to be infinite, but in the examples of interest it is usually finite. The relations are $s^2 = e$, for each $s \in S$, and $(st)^{m_{st}} = e$, for each $(s,t)\in S^2$, where $m_{st}$ is an integer depending on the pair $(s,t)$. For now, I’ll ignore the questions about the relation to reflection groups.

The most basic Coxeter group is the symmetric group $S_n$, with generators $s_1 = (1 2)$, $s_2 = (2 3)$, …, $s_{n-1} = (n-1 \ n)$. To be completely exlicit, $s_i$ switches $i$ and $i+1$ and leaves the other elements of $\{ 1,2, \ldots, n \}$ fixed.

Given $w$ in $W$, the length $\ell(w)$ of $w$ is the shortest expression for $w$ in terms of the elements of $S$. An expression which achieves this shortest length is called reduced. Exercise: for $w \in W$ and $s \in S$, we always have $\ell(ws)=\ell(w) \pm 1$.

In strong order, $u \leq w$ if there is a reduced word for $u$ which occurs as a subword of a reduced word for $w$. (Equivalently, if any reduced word for $w$ contains a reduced subword with product $u$.)

In weak order, $u \leq w$ if there is a reduced word for $u$ which occurs as a prefix of a reduced word for $w$. This is a more restrictive condition than the one for strong order, so there are few relations in weak order. Exercise: for $w \in W$ and $s \in S$, we must either have $ws < w$ or $w < ws$ in weak order. Weak order relations of the form $u < us$ are called covers; and the covers generate all relations.

Weak order is a lattice, but not distributive. Strong order is not a lattice.

Now that you have the definitions, here’s the problem set!

(1) Write down all the elements of $S_3$, all of the reduced words for each of these elements, and draw weak and strong order on $S_3$.

(2) In the group $S_n$, give a concrete formula for $\ell(w)$. Hint: there is exactly one element of $S_n$ which has length ${0}$, and exactly one which has length $\binom{n}{2}$; all others are in between. Your formula should have this property as well.

(3) For $w \in S_n$ give a criterion for when $\ell(w) = \ell(w s_i)+1$
and when $\ell(w) = \ell(w s_i)-1$.

(4) Describe weak order on $S_n$.

I can’t think how to write a similar problem set for strong order right now, but I’ll try to come up with one later (or just write up the answer, if I fail.)

Of course, collaberation is encouraged. If you know the answers, though, don’t give them away!

## 10 thoughts on “Orders on Coxeter Groups — with a Problem Set!”

1. Pingback: 0xDE ~
2. Jeremy Henty says:

You wrote “w.s = w.s”. I think you meant “w.s <= w or w <= w.s".

3. Jeremy Henty says:

I think HTML ate my post. “w.s = w.s” should have been “w.s <= w or w >= w”.

4. Jeremy Henty says:

Aargh! One last time! Otherwise you’ll have to read my mind!

You wrote “w.s < w or w >= w.s”. I think you meant “w.s <= w or w <= w.s”.

5. Jeremy Henty says:

David,

You still have “ws < w or w > ws” when I’m sure you want “ws < w or w < ws”.

6. Alexander Woo says:

Let me add to David’s problem set for strong Bruhat order…

3′)
a) Describe all $t\in S_n$ such that there exist $v,w\in S_n$ with $\ell(vt)=\ell(w)-1$ and $v.
b) Show that for all $t\in S_n$ found in (a) and all $w\in S_n$, either $wt or $w.
c) For $w\in S_n$ and $t$ as in (a), give a criterion for when $wt, and a criterion for when $\ell(wt)=\ell(w)-1$. (Bonus: Find a formula for $\ell(wt)-\ell(w)$.)

4) Describe Bruhat order on $S_n$.

I fixed some of Alex’s formulas. David