Rank matrices for type $D$ Bruhat order

Question

Roughly, this question asks how the Bruhat (strong) order in type $D$ can be understood like the Bruhat orders in types A and B=C. I'll review how types A and B work before asking my question. As a side note, I tried to ask this question earlier today, then deleted it with the intention of fixing some errors and reasking it, but I can't find the deleted question.

Notation: I write $[n]$ for $\{1,2,\ldots, n \}$.

Type A The Bruhat order of type $A_{n-1}$ is a partial order on the group of permutation of $[n]$. It can be described in the two following manners:

("Tableaux criterion") Put a partial order on the set of $k$ element subsets of $[n]$ as follows: For $I$, $J$ two such subsets, sort $I = \{ i_1 < i_2 < \cdots < i_k \}$ and $J = \{ j_1 < j_2 < \cdots < j_k \}$, and define $I \leq J$ if $i_1 \leq j_1$, $i_2 \leq j_2$, ..., $i_k \leq j_k$. Then, for permutations $u$ and $v$, we have $u \leq v$ if and only if $u[k] \leq v[k]$ for $1 \leq k \leq n-1$.

("Rank matrix criterion") We have $u \leq v$ if and only if, for all $1 \leq k, \ell \leq n-1$, we have $\#(u[k] \cap [\ell]) \leq \#(v[k] \cap [\ell])$.

The numbers $r_{k \ell} = \#(u[k] \cap [\ell])$ are called the rank matrix of $u$. It is often useful to formally define $r_{0k}=r_{k0} = 0$ and $r_{kn}=r_{nk}=k$. With those boundary definitions, rank matrices are characterized by $0 \leq r_{(k+1)\ell} - r_{k \ell},\ r_{k(\ell+1)} - r_{k \ell} \leq 1$ and, if $r_{(k+1)\ell} = r_{k(\ell+1)} = r_{k\ell}+1$ then $r_{(k+1)(\ell+1)} = r_{k\ell}+2$.

Type B Let $\sigma : [2n] \to [2n]$ be the involution $\sigma(k) = 2n+1-k$. Then the Coxeter group of type $B$ is the centralizer of $\sigma$ in $S_{2n}$. Bruhat order in type $B$ is the induced order from $S_{2n}$, and thus can be described as by either the Tableaux Criterion or the Rank Matrix Criterion. In either case, we may cut roughly in half the number of cases which need to be checked, because $u[k]$ determines $u[2n-k]$, so we only need check the conditions for $1 \leq k \leq n$.

Type D The Coxeter group of type $D_n$ is the index two subgroup of $B_n$ consisting of permutations for which $\#(u [n] \cap [n]) \equiv n \bmod 2$. The Bruhat order is no longer induced from $B_n$. It seems to follow from other things I will say below that there is a quick definition of it as an induced order though, so that will be my first question:

Let $\tau$ be the permutation $(n \ n+1)$ in $B_n$; this permutation is not in $D_n$ but normalizes $D_n$. Embed $D_n$ into $B_n \times B_n$ by $u \mapsto (u, \tau u \tau^{-1})$. Is the Bruhat order on $D_n$ simply the $B_n \times B_n$ Bruhat order restricted to the image?

In any case, what I can find in sources is that something like the tableaux criterion holds. Namely, in any Coxeter group, there is a collection of subgroups called the maximal parabolics, and there are partial orders on the quotients by the maximal parabolics such that $u \leq v$ if and only if their cosets in by each maximal parabolic $P$ obey $u P \leq v P$. To make this sound more like the tableaux criterion, note that the maximal parabolics in type $D_n$ are the stabilizers of $[1]$, $[2]$, ..., $[n-2]$, $[n]$ and $[n]':=\tau([n])$. So we can identify cosets of maximal parabolics with $D_n$ orbits of these sets. So we can detect whether $u \leq v$ by comparing $uX$ and $vX$ for some poset relation, with $X$ in the list $[1]$, $[2]$, ..., $[n-2]$, $[n]$ and $[n]':=\tau([n])$. But I haven't found a source which spells out how to order the $D_n X$'s.

What, explicitly, is the order on the $D_n X$'s?

I tried to work this out myself, and I believe I got the following: Let $Y$ and $Z \in D_n X$ for $X$ as above. Then the poset relation is that we have both $Y \leq Z$ and $\tau(Y) \leq \tau(Z)$, in our order on subsets of $[2n]$.

Is this right? Is there a source for this?

It seems to me I can also encode this in a rank matrix style. Namely, for $X$ and $Y$ one of $[1]$, $[2]$, ..., $[n-2]$, $[n]$, $[n]'$, $[n+2]$, ..., $[2n-2]$, $[2n-1]$ and $u$ in the $D_n$ Coxeter group, let $r_{XY}(u) = \#(uX \cap Y)$.

Is it true that $u \leq v$ if and only if $r_{XY}(u) \leq r_{XY}(v)$ for all such $X$, $Y$? Is there a source for this?

Finally, one could ask for a simple local characterization of the $r_{XY}$'s, similar to the characterization I gave above for type $A$ rank matrices.

Is such a characterization known?

Answer 1

Here are some more thoughts about how the Type D Bruhat order is more complicated than the Type A and Type B/C orders. These ideas might even suggest that giving a "rank matrix"-like description of the partial order is "impossible" in Type D.

There is a certain property of posets called "clivage" (by Lascoux and Schützenberger) or "dissective" (by Reading). Lascoux and Schützenberger (cited below) showed that the Type A and Type B Bruhat orders are dissective. Meanwhile, Geck and Kim (cited below) showed that Type D Bruhat order is not dissective (they address the exceptional types as well). Also, it is known that a finite poset $P$ is dissective if and only if the MacNeille completion of $P$ is distributive (see Theorem 7 of the paper of Reading cited below).

(As an aside, the MacNeille completion of the Bruhat order of Type A is the distributive lattice of Monotone Triangles (a.k.a. Alternating Sign Matrices) with componentwise order. See the paper of Brualdi and Schroeder cited below for more on this lattice.)

So, Type D Bruhat order lacks a nice property ("dissective") which Type A and B have. But what does this have to do with the possibility of a "rank matrix"-like description of the partial order in Type D? Well, intuitively at least, if you have a partial order defined by componentwise order on some arrays of numbers satisfying certain inequalities, then to formally extend your partial order to be a lattice, what you'll end up doing is taking $\min$'s and $\max$'s of the entries until you get enough new arrays so that everyone has a meet and join. And if so, the result will be distributive because $\min$'s and $\max$'s distribute over one another. But we know Type D Bruhat order does not have a distributive lattice as its completion, so it "can't" have a partial order given by comparing arrays of numbers in this way.

Brualdi, Richard A.; Schroeder, Michael W., Alternating sign matrices and their Bruhat order, Discrete Math. 340, No. 8, 1996-2019 (2017). ZBL1366.15024.

Geck, Meinolf; Kim, Sungsoon, Bases for the Bruhat-Chevalley order on all finite Coxeter groups, J. Algebra 197, No. 1, 278-310 (1997). ZBL0977.20033.

Lascoux, Alain; Schützenberger, Marcel-Paul, Lattices and bases of Coxeter groups, Electron. J. Comb. 3, No. 2, Research paper R27, 35 p. (1996); printed version J. Comb. 3, No. 2, 633-667 (1996). ZBL0885.05111..

Reading, Nathan, Order dimension, strong Bruhat order and lattice properties for posets, Order 19, No. 1, 73-100 (2002). ZBL1007.05097.

Answer 2

The answer to my questions is that I was wrong. I'll switch to the more standard notation of having $D_n$ act on $\{ -n, -n+1, \ldots, -2, -1, 1, 2, \ldots, n-1, n \}$ in order to match the reference of Proctor.

Here is the simplest example to demonstrate my error. Take $n \geq 4$ and look at $D_n \cdot [2]$. Then my belief above was that we should have $(2,1) > (1,-2)$, since $(2,1) > (1,-2)$ and $(2,-1) > (-1,-2)$ are both valid inequalities in type $B$. But this is wrong; any type $D$ transposition which lowers $(2,1)$ takes it below $(1,-2)$. In terms of weights, we are taking about $e_2+e_1$ and $-e_2+e_1$. They differ by $2 e_2 = (e_2+e_1) + (e_2-e_1)$, which is a sum of positive roots. However, subtracting either $e_2+e_1$ or $e_2-e_1$ from $e_2+e_1$ gives $0$ and $2 e_1$ respectively, neither of which are in the $D_n$ orbit of $e_2+e_1$.

The paper of Proctor which Sam Hopkins pointed me to gives the correct criterion in Theorem 5D: Let $I=\{ i_1 < i_2 < \cdots < i_k \}$ and $J=\{ j_1 < j_2 < \cdots < j_k \}$ be two $k$-element subsets of $\{ \pm 1, \pm 2, \ldots, \pm n \}$, both of which have the property of not containing both $a$ and $-a$. Then $I \leq J$ if and only if two conditions hold:

• $i_r \leq j_r$ and

• If there is a set of indices $p, p+1, \ldots, q$ such that $\{ |i_p|, |i_{p+1}|, \ldots, |i_q| \}$ and $\{ |j_p|, |j_{p+1}|, \ldots, |j_q| \}$ are each permutations of $\{ 1,2,\ldots, q-p+1 \}$, then the number of negative elements among $(i_p, i_{p+1}, \ldots, i_q)$ and $(j_p, j_{p+1}, \ldots, j_q)$ must have the same parity.

At the moment, I don't see how to make this second condition sound like a rank matrix condition.