John Mangual asks:

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 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 , for each , and , for each , where is an integer depending on the pair . For now, I’ll ignore the questions about the relation to reflection groups.

The most basic Coxeter group is the symmetric group , with generators , , …, . To be completely exlicit, switches and and leaves the other elements of fixed.

Given in , the length of is the shortest expression for in terms of the elements of . An expression which achieves this shortest length is called **reduced**. **Exercise:** for and , we always have .

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

In **weak order**, if there is a reduced word for which occurs as a **prefix** of a reduced word for . This is a more restrictive condition than the one for strong order, so there are few relations in weak order. **Exercise**: for and , we must either have or in weak order. Weak order relations of the form 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 , all of the reduced words for each of these elements, and draw weak and strong order on .

(2) In the group , give a concrete formula for . Hint: there is exactly one element of which has length , and exactly one which has length ; all others are in between. Your formula should have this property as well.

(3) For give a criterion for when

and when .

(4) Describe weak order on .

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!

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

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

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”.

Thanks for the correction!

David,

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

OK, think I got it now.

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

3′)

a) Describe all such that there exist with and .

b) Show that for all found in (a) and all , either or .

c) For and as in (a), give a criterion for when , and a criterion for when . (Bonus: Find a formula for .)

4) Describe Bruhat order on .

I fixed some of Alex’s formulas. DavidAlex: that’s a nice approach!