## Computing Bruhat Order Covering Relations

To put this in context: I am in the process of developing a package for Macaulay 2 (a commutative algebra software,) called "Permutations", which will add permutations as a type of combinatorial object that M2 will handle, hopefully integrating nicely with the (still in development) Posets package, the (still in development) Graphs package, and various current M2 functions.

One of the first things that I'd wanted to put in was functions which compute the poset of the Bruhat order on $S_n$ and compute when one permutation covers another in the Bruhat order. This was all coded and "working" - but has been producing a poset which is decidedly NOT the desired poset (among other things, the graph of the Hasse diagram isn't regular.) I'd like to ask whether the (probably somewhat naive) algorithm I was using to check covering relations seems reasonable (so the problem is just in the coding of it, not in the theory behind it) or not.

To see if $P\leq R$ in the Bruhat order:

Given a pair of permutations P and R, compute their lengths (the number of simple transpositions in their decomposition, or [as implemented right now] the sum of entries in their inversion vectors.) If length(P)=length(R)+1, then we compute $(P^{-1})*R$.

If R covers P in the Bruhat order, then length$((P^{-1})*R)=1.$

Am I missing some subtlety of the Bruhat order? I thought one permutation covered enough exactly when they differed by a single, simple transposition. This seemed to capture that - but is giving me an incorrect poset.

Coding error or theory error? I'd love to hear it.

-
I'm banking on "coding error" at this point, but before I spent an eternity banging through code, I figured I'd make sure that I wasn't crazy with that as a covering relation check. – Gwyn Whieldon May 13 2010 at 8:12
Great that you're doing this! I'm sure it will be very useful. Patrik's answer looks good to me---the minimal example of the phenonmenon he mentions already happens for $S_3$, where $P=s_1 s_2$ covers $R=s_2$ but $P^{-1} R=s_2 s_1 s_2$ is the longest element. The ordering you are computing is sometimes called "weak Bruhat". – GS May 13 2010 at 9:59
(And it's not left-right symmetric---that is, if you test for when $R P^{-1}$ has length one you get a different order) – GS May 13 2010 at 10:01
Oops---I should have mentioned: $s_1=(12)$ and $s_2=(23)$ are the simple transpositions. You probably are familiar with the notation, but still. – GS May 13 2010 at 10:02

My M2 permutation code is here: http://www.math.cornell.edu/~allenk/permutation.m2 It's got a bunch of specialized stuff about Rothe diagrams and Fulton's essential set, but at the end it's got a BruhatLeq, for strong Bruhat order (so, not what you're computing).

If you want covering relations in strong Bruhat or right weak Bruhat, find the first place F and the last place L that your permutations differ. Weak Bruhat Covering: L=F+1. Strong Bruhat covering: each value w(F+1)...w(L-1) is not in the interval (w(F),w(L)).

If you want all relations in weak Bruhat order, w >= v if l(w) = l(v) + l(v^-1 w).

For all relations in strong Bruhat order, best to compute the corresponding rank matrices, and compare those entrywise. (That's what I do in the above code.)

-
Nice! Do you have anything that works for other Coxeter groups? – GS May 13 2010 at 13:48
This is one of the reasons I posted this on MathOverflow too - I was hoping to get a response with, "Oh, I've already written all of that." With the coveringRelation code fixed, it's now printing out the digraph of the Hasse diagram beautifully (between Posets and Graphs, it will export into Graphviz format - .DOT files - a picture of any poset.) Thank you very much for the advice! – Gwyn Whieldon May 13 2010 at 16:10
I haven't seen it mentioned, perhaps it is not very well known: Fokko du Cloux wrote a console application called "Coxeter" which does all kinds of (spherical or affine) Coxeter group operations, for instance Bruhat order and Kazhdan-Lusztig polynomials. It can do input and output with some other software, and the source code is available if you truly need to add something. The only drawback is that there is not really a document that tells you how to use it, but I could post the basics if anyone is interested. – Sean Rostami May 13 2010 at 16:43
The answers and comments reinforce the importance of being precise about terminology used for orderings of Coxeter groups. Plus the widespread problem of having scattered computer programs that overlap but aren't readily found or used by other people. Such programs tend to grow out of someone's current research enthusiasm and then get put on the shelf or lack documentation or fail to run on some hardware. It's especially important to uniformize access to du Cloux's programs now that he is gone. But no one gets paid or rewarded for doing this extra work, while few are qualified. – Jim Humphreys May 13 2010 at 17:14
A related place where precision is important: which is a Schubert variety, and which is an opposite Schubert variety. Unfortunately some people want them for homological purposes, and some for cohomological, so they disagree on whether l(w) should be the dimension or the codimension. – Allen Knutson May 13 2010 at 17:59

$P^{-1}R$ is not in general of length 1. For example

(12)(23)(34)(45)(56) covers (12)(23)(45)(56) but (12)(23)(45)(56) (56)(45)(34)(23)(12)=

(12)(23)(34)(23)(12)

Your algorithm should work if you instead test if $P^{-1}R$ is a transposition (not just a simple transposition).

-

For Stephen Griffeth and others:

To tell the software what group you want to work with, get yourself to the "type" prompt, either by pressing Enter at the main prompt, or by entering "type" as a command. The names of the groups are:

1. A-I, corresponding to the finite Coxeter groups
2. a-g, corresponding to the affine Coxeter groups
3. X or x, for input from a file
4. Y or y, for interactive input

For (1) (2) and (4) you will next be presented with the "rank" prompt, which refers to the size of the generating set of the Coxeter group, so for example the affine Weyl group of SL(3) should be "a" followed by "3". For (4) you will also be asked for the entries of the Coxeter matrix. For (3) you will be asked for a file.

When you need to enter a group element, you merely type a sequence of integers 1 through rank separated by periods, e.g. 1.2.1. If the rank is at most 9 then you can (must?) omit the periods, e.g. 121. If you need to input the identity element, you simply type nothing and press Enter.

I don't remember how the simple reflections are numbered, but I seem to remember that the affine generator is always the last one. There is a prefix and postfix command to change these naming conventions (so you could call the 1st reflection "s(1)" if you wanted), which is useful when you are doing input from the output of some other program or script.

You can see a list of commands by typing "help", and they should be mostly self-explanatory knowing the above.

-
 There are plans to include an interface to du Cloux's Coxeter package in Sage. Not that this is useful information right now, but it hopefully means that if you're worried that, in a couple of years, you might want to do some Coxeter group calculations using du Cloux's package, and you won't be able to find this question again, well, by then, hopefully you'll be able to do them within Sage. – Hugh Thomas May 16 2010 at 20:32 Great, thanks Sean! Hugh: I am afraid, and look forward to the day Sage has this. – GS Jun 2 2010 at 21:35