# 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 '10 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 '10 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 '10 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 '10 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 '10 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 '10 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 '10 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 '10 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 '10 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 '10 at 20:32
Great, thanks Sean! Hugh: I am afraid, and look forward to the day Sage has this. –  GS Jun 2 '10 at 21:35
I only remembered this recently (yesterday), but I have my own MAGMA functions that interface with the Coxeter3 program and I wanted to record it somewhere on the internet. Feel free to email me if you need such a thing. You can call these functions within your MAGMA script and they will instruct the locally-installed Coxeter3 to perform a certain task. Essentially all input/output processing and intermediate steps are performed internally, so you can use it profitably without knowing anything about Coxeter3. It should be no trouble to transfer the MAGMA code to Sage, but I did not do this. –  Sean Rostami Jul 8 at 0:26
This really is necessary for doing certain things. I'm not very knowledgeable about Sage, but MAGMA definitely has some gaps. For example, MAGMA knows about affine Weyl groups, but many basic functions regarding affine Weyl groups are unavailable. Coxeter3 can do such things. I also have several functions that fill other gaps in MAGMA, like the near-total inability of MAGMA to handle extended affine Weyl groups--MAGMA knows about weights and it knows about Coxeter groups, but there is no code linking the two (example: find a reduced expression for the affine Weyl component of a translation). –  Sean Rostami Jul 8 at 0:30
I also have a "user's manual", written a few years ago, for du Cloux's program Coxeter3. I am happy to send it to you or even expand it if there is interest. Email me if you need such a thing. But probably there isn't (and shouldn't be) because of functions, either my own or something that is now in Sage, that interface with Coxeter3. –  Sean Rostami Jul 8 at 0:33