Séminaire Lotharingien de Combinatoire 67 (2012), Article B67e

FLAG WEAK ORDER ON WREATH PRODUCTS

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

Abstract. A generating set for the wreath product ℤ_{r} ≀ S_{n} which leads to a nicely behaved weak order is presented. It is shown that the resulting poset has properties analogous to those of the weak order on the symmetric group: it is a self-dual lattice, ranked by the Foata–Han flag inversion number; any two maximal chains are connected via Tits-type pseudo-Coxeter moves; and its intervals have the desired homotopy types. The associated Möbius function and relevant generating functions are computed.

1. Introduction

The weak order on a Coxeter group is a fundamental tool in the study of the combinatorial structure of this group. A natural problem is to give a “correct definition” of a weak order on the wreath product G(r, n) := ℤ_{r} ≀ S_{n}. The weak order on a Coxeter group is determined via the generating set of simple reflections and the associated length function. In this paper we address the basic question: which generating set for the wreath product is the counterpart of the set of simple reflections? Unfortunately, the natural analogue — the set of complex reflections — does not lead to a nicely behaved partial order. It will be shown that there is a generating set yielding an order on G(r, n) with properties analogous to those of the weak order on S_{n} = G(1, n): the resulting poset is ranked by the Foata–Han flag inversion number; it is a self-dual lattice; it has a Tits-type property; and its intervals have the desired homotopy types. Finally, the associated Möbius function and relevant generating functions will be computed.

The rest of the paper is organized as follows. Necessary preliminaries and notation are given in Section 2. For the sake of clarity, results are first stated and proved for the hyperoctahedral group B_{n} = G(2, n): the generating set and corresponding presentation are described in Section 3, the flag weak order is defined in Section 4, and its properties are studied in Sections 4–6. The corresponding results for general r are discussed in Section 7. Section 8 contains final remarks and open problems.

2. Preliminaries

Let (W, S) be a Coxeter system; thus W is a group with a set of generators S = {s_{0}, s_{1}, …, s_{n}} and a presentation of the form

W = ⟨s_{0}, s_{1}, …, s_{n} | (s_{i}s_{j})^{m_{ij}} = e, 0 ≤ i ≤ j ≤ n⟩,

where m_{ij} = m_{ji} ∈ {2, 3, …} ∪ {∞} and m_{ii} = 1.

The (right) weak order ≤ on W is the reflexive and transitive closure of the relation

w ⋖ ws if and only if w ∈ W, s ∈ S, and ℓ(w) + 1 = ℓ(ws),

Work of the first and third authors was supported in part by an Internal Research Grant from the Office of the Rector, Bar-Ilan University.

where ℓ(·) is the standard length function with respect to the Coxeter generating set S. The left weak order is defined similarly, with sw instead of ws. For combinatorial and other properties of the weak order the reader is referred to [3].

Let S_{n} be the symmetric group on the letters [n] := {1, …, n}. Recall that S_{n} is a Coxeter group with respect to the set of Coxeter generators S := {s_{i} | 1 ≤ i ≤ n − 1}, where s_{i} may be interpreted as the adjacent transposition (i, i + 1).

For π ∈ S_{n} let the inversion set be Inv(π) := {(i, j) : i < j, π(i) > π(j)}, the inversion number be inv(π) := #Inv(π), and the descent set be Des(π) := {i ∈ [n − 1] : π(i) > π(i+1)}. Recall the classical combinatorial interpretations of the Coxeter length function and of the (right) weak order [3, Cor. 1.5.2, Prop. 3.1.3]:

(1) ℓ(π) = inv(π) = inv(π^{−1}),  π ≤ σ if and only if Inv(π^{−1}) ⊆ Inv(σ^{−1}).

Let B_{n} be the group of all bijections σ of the set [±n] := {−n, …, −1, 1, …, n} onto itself such that

σ(−a) = −σ(a), for all a ∈ [±n],

with composition as the group operation. B_{n} is known as the group of “signed permutations” on [n], or as the hyperoctahedral group of rank n. We identify S_{n} as a subgroup of B_{n}, and B_{n} as a subgroup of S_{2n}, in the natural ways.

For σ ∈ B_{n} let Neg(σ) := {i ∈ [n] : σ(i) < 0}, neg(σ) := #Neg(σ) and |σ| = [|σ(1)|, …, |σ(n)|] ∈ S_{n}.

More generally, consider the wreath product = ℤ_{r} ≀ S_{n}, where ℤ_{r} is the (additive) cyclic group of order r:

G(r, n) := {g = ((c_{1}, …, c_{n}), σ) | c_{i} ∈ ℤ_{r} 1 ≤ i ≤ n, σ ∈ S_{n}},

with the group operation

((c_{1}, …, c_{n}), σ) · ((d_{1}, …, d_{n}), τ) := ((c_{τ(1)} + d_{1}, …, c_{τ(n)} + d_{n}), στ).

(This definition is slightly non-standard, and it is chosen for compatibility with the case r = 2; see below.) The elements of ℤ_{r} ≀S_{n} may be interpreted as r-colored permutations, i.e., bijections g of the set ℤ_{r} × [n] onto itself such that

g(c, i) = (d, j) implies g(c + c′, i) = (d + c′, j), for all c, c′, d ∈ ℤ_{r}, i, j ∈ [n].

For example, G(1, n) is naturally isomorphic to the symmetric group S_{n}, and G(2, n) is isomorphic to the hyperoctahedral group B_{n}, where ((c_{1}, …, c_{n}), σ) ∈ G(2, n) corresponds to the element g ∈ B_{n} such that

g(i) = (−1)^{c_{i}}σ(i), for all i ∈ [n].

Thus Neg(g) = {i : c_{i} = 1}, a basic compatibility (for r = 2) that underlies the choice of group operation in G(r, n) above. Informally, this means that the colors (or signs) c_{i} are attached before the permutation σ is applied.

In the special cases r = 1, 2, G(r, n) is of course a Coxeter group.

For an r-colored permutation π = ((c_{1}, …, c_{n}), σ) ∈ G(r, n) let |π| := σ and n(π) :=

∑_{i=1}^{n} c_{i} ∈ ℤ, where elements of ℤ_{r} are interpreted as the corresponding elements of

{0, …, r − 1} ⊆ ℤ. Note that, for r = 2, n(π) = neg(π).

The classical inversion number on permutations has a counterpart for wreath products, the flag inversion number. It was introduced by Foata and Han [8, 9] and further investigated in [7, 6].

Definition 2.1. The flag inversion number of an r-colored permutation π ∈ G(r, n) is defined by

finv(π) := r · inv(|π|) + n(π).

For a positive integer m and an indeterminate q, let us write

[m]_{q} := \frac{1 − q^{m}}{1 − q} .

Proposition 2.2 ([7, Theorem 7.4]). For every r and n, we have

∑_{π∈G(r,n)} q^{finv(π)} = ∏_{i=1}^{n}[ri]_{q}.

3. Generators and Presentations

The alternating subgroup of a reflection group is the kernel of the sign homomorphism which maps all the Coxeter generators (simple reflections) to −1.

Proposition 3.1. The alternating subgroup of the hyperoctahedral group B_{n} = G(2, n) is isomorphic to the abstract group generated by {a_{i} : 1 ≤ i ≤ n − 1} with defining relations

(A1)  a_{i}^{4} = 1, 1 ≤ i ≤ n − 1,
(A2)  a_{i}a_{j} = a_{j}a_{i}, |i − j| > 1,
(A3)  a_{i}a_{i+1}a_{i} = a_{i+1}a_{i}a_{i+1}, 1 ≤ i ≤ n − 1,

and

(A4)  (a_{i}a_{i+1})^{3} = 1, 1 ≤ i ≤ n − 1.

Proof. Denote by B_{n}^{+} the alternating subgroup of B_{n}, and let B̂_{n}^{+} be the abstract group with the above presentation. Define a map ϕ from the free group generated by a_{1}, …, a_{n−1} to B_{n}^{+} by

ϕ(a_{i}) := [1, …, −(i + 1), i, …, n], 1 ≤ i ≤ n − 1.

Since ϕ(a_{i}) = (i, i + 1)(i, −i) is a product of two reflections in B_{n}, it indeed belongs to B_{n}^{+}. It is easy to check that relations (A1)–(A4) are satisfied when each a_{i} is replaced by ϕ(a_{i}). Therefore, this defines a group homomorphism, which we again denote by ϕ, from B̂_{n}^{+} to B_{n}^{+}. We shall show that it is actually an isomorphism.

Now, B_{n}^{+} is generated by the set {(i, i + 1)(1, −1) : 1 ≤ i ≤ n − 1}; see, e.g., [10, §5.1, Exercise 1]. Since ϕ(a_{i})^{2} = (i + 1, −(i + 1))(i, −i), it follows that

ϕ(a_{i})ϕ(a_{i−1})^{2}ϕ(a_{i−2})^{2} ⋯ ϕ(a_{1})^{2} = (i, i + 1)(1, −1)

for 1 ≤ i ≤ n − 1, and therefore ϕ : B̂_{n}^{+} → B_{n}^{+} is surjective.

It remains to show that ϕ is injective. Since it is surjective and #B_{n}^{+} = 2^{n−1}n!, it suffices to show that #B̂_{n}^{+} ≤ 2^{n−1}n!.

Let N̂_{n}^{+} be the subgroup of B̂_{n}^{+} generated by a_{1}^{2}, …, a_{n−1}^{2}. We shall show that N̂_{n}^{+} is a commutative normal subgroup of B̂_{n}^{+}. Indeed, (A4) can be written as

a_{i}a_{i+1}a_{i}a_{i+1}a_{i}a_{i+1} = 1,

or, using (A3), as

a_{i}a_{i+1}a_{i}a_{i}a_{i+1}a_{i} = 1.

Rearrangement gives

a_{i}^{2}a_{i+1} = a_{i+1}^{−1}a_{i}^{−2},

or

(2)  a_{i+1}^{−1}a_{i}^{2}a_{i+1} = a_{i+1}^{−2}a_{i}^{−2} ∈ N̂_{n}^{+}.

Similarly, (A4) and (A3) for i − 1 imply

a_{i−1}^{−1}a_{i}^{2}a_{i−1} = a_{i−1}^{−2}a_{i}^{−2} ∈ N̂_{n}^{+}.

Finally, by (A2),

a_{j}^{−1}a_{i}a_{j} = a_{i}, |i − j| > 1,

so that

a_{j}^{−1}a_{i}^{2}a_{j} = a_{i}^{2} ∈ N̂_{n}^{+}, |i − j| > 1.

Thus N̂_{n}^{+} is a normal subgroup of B̂_{n}^{+}.

Commutativity of N̂_{n}^{+} is also easy: (2) and (A1) imply that

a_{i+1}^{−1}a_{i}^{2}a_{i+1} = a_{i+1}^{−2}a_{i}^{2},

or

a_{i+1}a_{i}^{2}a_{i+1} = a_{i}^{2},

so that also

a_{i+1}^{2}a_{i}^{2}a_{i+1}^{2} = a_{i+1}(a_{i+1}a_{i}^{2}a_{i+1})a_{i+1} = a_{i+1}a_{i}^{2}a_{i+1} = a_{i}^{2}.

Thus, again by (A1),

a_{i}^{2}a_{i+1}^{2} = a_{i+1}^{−2}a_{i}^{2} = a_{i+1}^{2}a_{i}^{2},

i.e., a_{i}^{2} and a_{i+1}^{2} commute. This is certainly also the case for a_{i}^{2} and a_{j}^{2} when |i − j| > 1, so N̂_{n}^{+} is commutative.

We can now wrap up the proof: N̂_{n}^{+} is a commutative group generated by the involutions a_{1}^{2}, …, a_{n−1}^{2}. Thus each element of N̂_{n}^{+} can be written as a product a_{i_{1}}^{2} ⋯ a_{i_{k}}^{2} for some k ≥ 0 and 1 ≤ i_{1} < ⋯ < i_{k} ≤ n − 1. In particular, #N̂_{n}^{+} ≤ 2^{n−1}. Also, N̂_{n}^{+} is a normal subgroup of B̂_{n}^{+}. The quotient B̂_{n}^{+}/N̂_{n}^{+} is generated by ā_{i}, the cosets corresponding to the generators a_{i} of B̂_{n}^{+}, 1 ≤ i ≤ n − 1. The ā_{i} satisfy the same relations (A2)–(A4) as the a_{i}, with (A1) replaced by

ā_{i}^{2} = 1, 1 ≤ i ≤ n − 1.

These are exactly the Coxeter relations defining the symmetric group S_{n} (actually, (A3) is now equivalent to (A4)), so that B̂_{n}^{+}/N̂_{n}^{+} is a homomorphic image of S_{n}, and in particular #(B̂_{n}^{+}/N̂_{n}^{+}) ≤ n!. Everything put together, we obtain #B̂_{n}^{+} ≤ 2^{n−1}n!, as required. □

The above presentation may be extended to the whole group B_{n} = G(2, n).

Proposition 3.2. The hyperoctahedral group B_{n} = G(2, n) is isomorphic to the abstract group generated by S_{2,n} := {a_{i} : 1 ≤ i ≤ n−1}∪{b_{i} : 1 ≤ i ≤ n} with defining relations

(B1)  b_{i}^{2} = 1, 1 ≤ i ≤ n,
(B2)  b_{i}b_{j} = b_{j}b_{i}, 1 ≤ i < j ≤ n,
(B3)  a_{i}^{2} = b_{i}b_{i+1}, 1 ≤ i ≤ n − 1,
(B4)  a_{i}a_{j} = a_{j}a_{i}, |i − j| > 1,
(B5)  a_{i}a_{i+1}a_{i} = a_{i+1}a_{i}a_{i+1}, 1 ≤ i ≤ n − 1,
(B6)  a_{i}b_{j} = b_{j}a_{i}, j ≠ i, i + 1,
(B7)  a_{i}b_{i} = b_{i+1}a_{i}, 1 ≤ i ≤ n − 1,

and

(B8)  a_{i}b_{i+1} = b_{i}a_{i}, 1 ≤ i ≤ n − 1.

Remark 3.3. Note that relations (A1)–(A4) in Proposition 3.1 follow from relations (B1)–(B8) in Proposition 3.2. Relation (A1) follows from relations (B1), (B2) and (B3). Relations (A2)–(A3) are relations (B4)–(B5). Finally, relation (A4) follows from relations (B1), (B3), (B5)–(B8) as follows:

(a_{i}a_{i+1})^{3} = (a_{i}a_{i+1}a_{i})(a_{i+1}a_{i}a_{i+1}) = (a_{i}a_{i+1}a_{i})(a_{i}a_{i+1}a_{i})
= a_{i}a_{i+1}b_{i}b_{i+1}a_{i+1}a_{i}  = b_{i+1}a_{i}a_{i+1}a_{i+1}a_{i}b_{i+2}
= b_{i+1}a_{i}b_{i+1}b_{i+2}a_{i}b_{i+2} = b_{i+1}b_{i}a_{i}a_{i}b_{i+2}b_{i+2}
= b_{i+1}b_{i}b_{i}b_{i+1}b_{i+2}b_{i+2} = 1.

Proof. This is similar to the proof of Proposition 3.1 (and somewhat simpler).

Let B̂_{n} be the abstract group with the presentation described in Proposition 3.2. Define a map ϕ from the free group generated by a_{1}, …, a_{n−1}, b_{1}, …, b_{n} to B_{n} by

ϕ(a_{i}) := [1, …, −(i + 1), i, …, n], 1 ≤ i ≤ n − 1,

and

ϕ(b_{i}) := [1, …, −i, …, n], 1 ≤ i ≤ n.

Thus ϕ(a_{i}) = (i, i+1)(i, −i) and ϕ(b_{i}) = (i, −i). It is easy to check that relations (B1)– (B8) are satisfied when each a_{i} (b_{i}) is replaced by ϕ(a_{i}) (ϕ(b_{i}), respectively). Therefore this defines a group homomorphism, which we again denote by ϕ, from B̂_{n} to B_{n}. We shall show that it is actually an isomorphism.

Clearly, {ϕ(a_{i})ϕ(b_{i}) : 1 ≤ i ≤ n−1} is the set of Coxeter generators for the symmetric group S_{n}, embedded naturally into B_{n}. A similar assertion holds for {ϕ(b_{i}) : 1 ≤ i ≤ n} and ℤ_{2}^{n}. Since B_{n} = ℤ_{2}^{n} ⋊ S_{n}, it follows that {ϕ(a_{i}) : 1 ≤ i ≤ n − 1} ∪ {ϕ(b_{i}) : 1 ≤ i ≤ n}) generates B_{n}. Thus ϕ is surjective and, in particular,

#B̂_{n} ≥ #B_{n}.

It remains to show that ϕ is injective. Since it is surjective and #B_{n} = 2^{n}n!, it suffices to show that #B̂_{n} ≤ 2^{n}n!.

Let N̂_{n} be the subgroup of B̂_{n} generated by b_{1}, …, b_{n}. We shall show that N̂_{n} is a commutative normal subgroup of B̂_{n}. Commutativity follows from (B2), while normality follows from (B6)–(B8), which may be written as

a_{i}^{−1}b_{j}a_{i} = b_{j}, j ≠ i, i + 1,
a_{i}^{−1}b_{i+1}a_{i} = b_{i}, 1 ≤ i ≤ n − 1,

and

a_{i}^{−1}b_{i}a_{i} = b_{i+1}, 1 ≤ i ≤ n − 1.

We can now wrap up the proof: N̂_{n} is a commutative group generated by the involutions b_{1}, …, b_{n}. Thus each element of N̂_{n} can be written as a product b_{i_{1}} ⋯ b_{i_{k}} for some k ≥ 0 and 1 ≤ i_{1} < ⋯ < i_{k} ≤ n. In particular, #N̂_{n} ≤ 2^{n}. Also, N̂_{n} is a normal subgroup of B̂_{n}. The quotient B̂_{n}/N̂_{n} is generated by ā_{i}, the cosets corresponding to the generators a_{i} of B̂_{n}, 1 ≤ i ≤ n − 1. The ā_{i} satisfy relations (B4)–(B5), with (B3) replaced by

ā_{i}^{2} = 1, 1 ≤ i ≤ n − 1.

These are exactly the Coxeter relations defining the symmetric group S_{n}, so that B̂_{n}/N̂_{n} is a homomorphic image of S_{n}, and in particular #(B̂_{n}/N̂_{n}) ≤ n!. Everything put together, we obtain #B̂_{n} ≤ 2^{n}n!, as required. □

4. Flag Weak Order

From now on we identify the abstract generating set of B_{n},

S_{2,n} = {a_{i} : 1 ≤ i < n} ∪ {b_{i} : 1 ≤ i ≤ n},

with the choice

a_{i} := [1, …, i − 1, −(i + 1), i, i + 2, …, n]

and

b_{i} := [1, …, i − 1, −i, i + 1, …, n],

used in the proof of Proposition 3.2.

Following Foata and Han [8, 9], let the flag inversion number of π ∈ B_{n} be

finv(π) := 2 · inv(|π|) + neg(π).

Definition 4.1. The flag (right) weak order ⪯ on B_{n} is the reflexive and transitive closure of the relation

π ⋖ πs if and only if π ∈ G(2, n), s ∈ S_{2,n} and finv(π) < finv(πs).

Note that this order is not isomorphic to the classical weak order on B_{n}.

Proposition 4.2. The poset (B_{n}, ⪯) is (i) ranked (by flag inversion number); (ii) self-dual (by π ↦ πμ_{0}, where μ_{0} := [n̄, …, ¯1] is the unique maximal element in

this order); (iii) rank-symmetric and unimodal.

¯2¯1 ¯21 2¯1 21 ¯1¯2 1¯2 ¯12 12

Figure 1. The Hasse diagram of the flag weak order on B_{2}. Edges are drawn in dotted lines for a_{i}’s and as solid lines for b_{i}’s.

¯3¯2¯1 ¯3¯21 ¯32¯1 3¯2¯1 ¯321 ¯3¯1¯2 3¯21 ¯2¯3¯1 32¯1 ¯3¯12 ¯31¯2 3¯1¯2 321 2¯3¯1 ¯23¯1 ¯2¯31 ¯1¯3¯2 ¯312 3¯12 31¯2 ¯231 2¯31 23¯1 ¯2¯1¯3 1¯3¯2 ¯13¯2 ¯1¯32 312 2¯1¯3 ¯21¯3 ¯2¯13 231 13¯2 1¯32 ¯132 ¯1¯2¯3 21¯3 2¯13 ¯213 132 1¯2¯3 ¯12¯3 ¯1¯23 213 12¯3 1¯23 ¯123 123

Figure 2. The Hasse diagram of the flag weak order on B_{3}. Edges are drawn as dotted lines for a_{i}’s and as solid lines for b_{i}’s.

Proof. (i) In order to show that all maximal chains between two elements have the same length (the difference between their finv values), it suffices to show that, if σ = πs, with s ∈ S_{2,n} and finv(π) < finv(σ), then there exists π ≺ w ⪯ σ with finv(w) = finv(π) + 1. If s ∈ {b_{1}, …, b_{n}}, then

finv(πs) − finv(π) = 2 · (inv(|πs|) − inv(|π|)) + (neg(πs) − neg(π)) = 2 · 0 ± 1 = 1

(positive by the assumption finv(π) < finv(πs)). In this case we can take w := πs = σ. Otherwise, s ∈ {a_{1}, …, a_{n−1}}. Then

finv(πs) − finv(π) = 2 · (inv(|πs|) − inv(|π|)) + (neg(πs) − neg(π)) = 2 · (±1) ± 1.

Being positive by assumption, this number is either 1 or 3. In the first case, which occurs if s = a_{i}, 1 ≤ i ≤ n, |π(i)| < |π(i + 1)| and π(i + 1) < 0, we can again take w := πs. In the second case, which occurs if s = a_{i}, |π(i)| < |π(i + 1)| and π(i + 1) > 0, we have, by relations (B1) and (B7) in Proposition 3.2, σ = πb_{i+1}a_{i}b_{i}, with finv(π) + 3 = finv(πb_{i+1}) + 2 = finv(πb_{i+1}a_{i}) + 1 = finv(σ), and we can take w := πb_{i+1}.

(ii) Let μ_{0} := [n̄, …, ¯1]. Then, for every π ∈ B_{n},

finv(πμ_{0}) = 2 · inv (|πμ_{0}|) + neg(πμ_{0})

= 2 [\binom{n}{2} − inv (|π|)] + [n − neg(π)]

= finv(μ_{0}) − finv(π).

If σ = πs with s ∈ S_{2,n} and finv(π) < finv(σ), then

finv(πμ_{0}) − finv(σμ_{0}) = finv(σ) − finv(π) > 0.

Moreover, we have πμ_{0} = σμ_{0}s̃, where

s̃ = μ_{0}^{−1}s^{−1}μ_{0} = \begin{cases}b_{n+1−i}, & if s = b_{i}; \\ a_{n−i}, & if s = a_{i}. \end{cases}

It follows, by Definition 4.1, that π ⪯ σ if and only if σμ_{0} ⪯ πμ_{0}, and, since right multiplication by μ_{0} is a bijection on B_{n}, this proves self-duality.

(iii) Rank-symmetry follows from (ii) (and (i)). Unimodality follows from (i) together with Proposition 2.2. □

The proof of Proposition 4.2 implies the following statement.

Corollary 4.3. σ covers π in (B_{n}, ⪯) if and only if either (i) there exists an integer i with 1 ≤ i ≤ n such that

i ∉ Neg(π) and σ = πb_{i};

or (ii) there exists 1 ≤ i ≤ n − 1 such that

i + 1 ∈ Neg(π), |π(i)| < |π(i + 1)| and σ = πa_{i}.

5. Properties of the Flag Weak Order

5.1. Lattice Structure. For a set of pairs A ⊆ {(i, j) : 1 ≤ i < j ≤ n} let M(A) := {j : (i, j) ∈ A}. For example, M({(1, 6), (1, 4), (2, 3), (4, 6)}) = {3, 4, 6}.

Proposition 5.1. For every π, σ ∈ B_{n},

(3) π ⪯ σ if and only if Inv(|π^{−1}|) ⊆ Inv(|σ^{−1}|) and
Neg(π^{−1}) \ Neg(σ^{−1}) ⊆ M [Inv(|σ^{−1}|) \ Inv(|π^{−1}|)] .

Proof. ⟹ : It suffices to show that the right-hand side of (3) holds whenever σ covers π in (B_{n}, ⪯). By Corollary 4.3, there are two cases to check:

(i) There exists an integer i with 1 ≤ i ≤ n such that i ∉ Neg(π) and σ = πb_{i}. Then clearly Inv(|π^{−1}|) = Inv(|σ^{−1}|) and Neg(π^{−1}) \ Neg(σ^{−1}) = ∅.

(ii) There exists an integer i with 1 ≤ i ≤ n − 1 such that i + 1 ∈ Neg(π), |π(i)| < |π(i + 1)| and σ = πa_{i}. Defining p := |π(i)| and q := |π(i + 1)|, we have

p < q,  σ(i + 1) = π(i) = ±p,  σ(i) = −π(i + 1) = q.

Thus Inv(|σ^{−1}|) = Inv(|π^{−1}|) ∪ {(p, q)} and Neg(π^{−1}) \ Neg(σ^{−1}) = {q}. ⟸ : Assume that the right-hand side of (3) holds. There are two cases to consider:

(i) Inv(|π^{−1}|) = Inv(|σ^{−1}|). Then |π^{−1}| = |σ^{−1}| and Neg(π^{−1}) \ Neg(σ^{−1}) = ∅, i.e., Neg(π^{−1}) ⊆ Neg(σ^{−1}). It is clear that one can get from π to σ by a sequence of right multiplications by various b_{i}, each step increasing finv(·) by 1. Thus π ⪯ σ.

(ii) Inv(|π^{−1}|) is strictly contained in Inv(|σ^{−1}|). Thus |π| is strictly smaller than |σ| in the right weak order on S_{n}, and one can get from |π| to |σ| by a sequence of right multiplications by various Coxeter generators s_{i} of S_{n}, each step increasing the cardinality of the inversion set by 1. Let s_{i_{1}}, …, s_{i_{k}} be such a sequence, so that |σ| = |π|s_{i_{1}} ⋯ s_{i_{k}}. Let a_{i_{1}}, …, a_{i_{k}} be the corresponding sequence of generators of B_{n}. Define π_{0} := π and, recursively,

π_{j} := π_{j−1}ã_{j}, 1 ≤ j ≤ k,

where

ã_{j} := \begin{cases}a_{i_{j}}, & if i_{j} + 1 ∈ Neg(π_{j−1}); \\ b_{i_{j}+1}a_{i_{j}}, & otherwise. \end{cases}

It is easy to see that

π = π_{0} ⪯ π_{1} ⪯ ⋯ ⪯ π_{k},

with finv(π_{j}) − finv(π_{j−1}) ∈ {1, 2}, j = 2, …, k. We shall show that π_{k} ⪯ σ, implying π ⪯ σ.

Indeed |π_{k}| = |σ|, and in particular Inv(|π_{k}^{−1}|) = Inv(|σ^{−1}|). Moreover, for each 1 ≤ j ≤ k, we have

Neg(π_{j}^{−1}) = \begin{cases}Neg(π_{j−1}^{−1}) \ \{|π_{j−1}(i_{j} + 1)|\}, & if i_{j} + 1 ∈ Neg(π_{j−1}); \\ Neg(π_{j−1}^{−1}), & otherwise. \end{cases}

Since M [Inv(|π_{j}^{−1}|) \ Inv(|π_{j−1}^{−1}|)] = {|π_{j−1}(i_{j} + 1)|} we conclude that, in both cases,

Neg(π_{j}^{−1}) = Neg(π_{j−1}^{−1}) \ M [Inv(|π_{j}^{−1}|) \ Inv(|π_{j−1}^{−1}|)] .

Thus

Neg(π_{k}^{−1}) = Neg(π_{0}^{−1}) \ ⋃_{j=1}^{k} M [Inv(|π_{j}^{−1}|) \ Inv(|π_{j−1}^{−1}|)]
= Neg(π_{0}^{−1}) \ M [Inv(|π_{k}^{−1}|) \ Inv(|π_{0}^{−1}|)] ,

where we have used the property ⋃_{j} M[A_{j}] = M[ ⋃_{j} A_{j}] and the fact that Inv(|π_{j−1}^{−1}|) ⊆ Inv(|π_{j}^{−1}|). Since π_{0} = π and Inv(|π_{k}^{−1}|) = Inv(|σ^{−1}|), we conclude that

Neg(π_{k}^{−1}) = Neg(π^{−1}) \ M [Inv(|σ^{−1}|) \ Inv(|π^{−1}|)] .

Our assumption

Neg(π^{−1}) \ Neg(σ^{−1}) ⊆ M [Inv(|σ^{−1}|) \ Inv(|π^{−1}|)]

is equivalent to

Neg(σ^{−1}) ⊇ Neg(π^{−1}) \ M [Inv(|σ^{−1}|) \ Inv(|π^{−1}|)] ,

namely to

Neg(σ^{−1}) ⊇ Neg(π_{k}^{−1}).

Together with Inv(|π_{k}^{−1}|) = Inv(|σ^{−1}|), this implies, by case (i) above, that π_{k} ⪯ σ. □

Proposition 5.2. The poset (B_{n}, ⪯) is a lattice.

Proof. For simplicity of notation, let

(4)  M(|π|, |σ|) := M [Inv(|σ^{−1}|) \ Inv(|π^{−1}|)] , π, σ ∈ B_{n}.

Proposition 5.1 can be stated as:

π ⪯ σ if and only if

Inv(|π^{−1}|) ⊆ Inv(|σ^{−1}|) and Neg(π^{−1}) ⊆ Neg(σ^{−1}) ∪ M(|π|, |σ|).

Let σ_{1}, σ_{2} be two elements of B_{n}. It follows that, for any π ∈ B_{n},

(5) π ⪯ σ_{1} and π ⪯ σ_{2} if and only if Inv(|π^{−1}|) ⊆ Inv(|σ_{1}^{−1}|) ∩ Inv(|σ_{2}^{−1}|) and Neg(π^{−1}) ⊆ (Neg(σ_{1}^{−1}) ∪ M(|π|, |σ_{1}|)) ∩ (Neg(σ_{2}^{−1}) ∪ M(|π|, |σ_{2}|)) .

We shall now define a candidate for the meet (in B_{n}) of σ_{1} and σ_{2}, and prove that it has the required properties. First note that the intersection of inversion sets (of permutations in S_{n}) is not necessarily an inversion set. Nevertheless, since S_{n} under right weak order is a lattice, there exists a meet

τ = |σ_{1}| ∧_{S_{n}} |σ_{2}| ∈ S_{n}

which satisfies, by (1),

Inv(τ^{−1}) ⊆ Inv(|σ_{1}^{−1}|) ∩ Inv(|σ_{2}^{−1}|)

and (6) Inv(γ^{−1}) ⊆ Inv(|σ_{1}^{−1}|) ∩ Inv(|σ_{2}^{−1}|) implies Inv(γ^{−1}) ⊆ Inv(τ^{−1}), for all γ ∈ S_{n}).

Define σ_{∧} ∈ B_{n} by

(7)  |σ_{∧}| := |σ_{1}| ∧_{S_{n}} |σ_{2}| (= τ)

and

(8)  Neg(σ_{∧}^{−1}) := (Neg(σ_{1}^{−1}) ∪ M(τ, |σ_{1}|)) ∩ (Neg(σ_{2}^{−1}) ∪ M(τ, |σ_{2}|)) .

Then clearly σ_{∧} ⪯ σ_{1} and σ_{∧} ⪯ σ_{2}. It remains to show that π ⪯ σ_{1} and π ⪯ σ_{2} implies π ⪯ σ_{∧}. This is straightforward if Inv(|π^{−1}|) = Inv(|σ_{∧}^{−1}|), but more intricate otherwise.

Assume that π ⪯ σ_{1} and π ⪯ σ_{2}. Then

Inv(|π^{−1}|) ⊆ Inv(|σ_{1}^{−1}|) ∩ Inv(|σ_{2}^{−1}|),

so that, by (6),

Inv(|π^{−1}|) ⊆ Inv(τ^{−1}) = Inv(|σ_{∧}^{−1}|).

From

Inv(|π^{−1}|) ⊆ Inv(|σ_{∧}^{−1}|) ⊆ Inv(|σ_{1}^{−1}|)

it now follows that

Inv(|σ_{1}^{−1}|) \ Inv(|π^{−1}|) = (Inv(|σ_{1}^{−1}|) \ Inv(|σ_{∧}^{−1}|)) ∪ (Inv(|σ_{∧}^{−1}|) \ Inv(|π^{−1}|)) ,

and therefore

M(|π|, |σ_{1}|) = M(|π|, |σ_{∧}|) ∪ M(|σ_{∧}|, |σ_{1}|).

A similar assertion holds for σ_{2}. From (5) it thus follows that

Neg(π^{−1}) ⊆ (Neg(σ_{1}^{−1}) ∪ M(|π|, |σ_{1}|)) ∩ (Neg(σ_{2}^{−1}) ∪ M(|π|, |σ_{2}|))
= (Neg(σ_{1}^{−1}) ∪ M(|π|, |σ_{∧}|) ∪ M(|σ_{∧}|, |σ_{1}|))
∩ (Neg(σ_{2}^{−1}) ∪ M(|π|, |σ_{∧}|) ∪ M(|σ_{∧}|, |σ_{2}|))
= M(|π|, |σ_{∧}|)

∪ [(Neg(σ_{1}^{−1}) ∪ M(|σ_{∧}|, |σ_{1}|)) ∩ (Neg(σ_{2}^{−1}) ∪ M(|σ_{∧}|, |σ_{2}|))]

= M(|π|, |σ_{∧}|) ∪ Neg(σ_{∧}^{−1}),

using definition (8) of Neg(σ_{∧}^{−1}). In other words, π ⪯ σ_{∧}, as required.

We have shown the existence of meets in (B_{n}, ⪯). The existence of joins follows by self-duality (Proposition 4.2(ii)):

σ_{1} ∨ σ_{2} = (σ_{1}μ_{0} ∧ σ_{2}μ_{0})μ_{0}.
□

Note that (7)–(8) in the proof of Proposition 5.2 provide an explicit description of the meet of two elements. One can generalize this description to any number of elements, using the notation M(|π|, |σ|) from (4). For the corresponding description of the join it is convenient to use also the notation Pos(σ) := [n] \ Neg(σ) for σ ∈ B_{n}.

Lemma 5.3. Let A be an arbitrary subset of B_{n}.

(i) The meet A_{∧} of A in (B_{n}, ⪯) is determined by

|A_{∧}| := ⋀_{σ∈A} |σ|,

where the meet is taken with respect to the (right) weak order on S_{n}, and by

Neg(A_{∧}^{−1}) := ⋂_{σ∈A} (Neg(σ^{−1}) ∪ M(|A_{∧}|, |σ|)) .

(ii) The join A_{∨} of A in (B_{n}, ⪯) is determined by

|A_{∨}| := ⋁_{σ∈A} |σ|

and by

Pos(A_{∨}^{−1}) := ⋂_{σ∈A} (Pos(σ^{−1}) ∪ M(|σ|, |A_{∨}|)) .

Remark 5.4. For n ≥ 3, the lattice (B_{n}, ⪯) is not semi-modular. To verify this, notice that π = 2¯1¯3 and σ = ¯13¯2 cover their meet π ∧ σ = ¯1¯2¯3 but are not covered by their join π ∨ σ = 32¯1. Moreover, for n ≥ 2, the lattice (B_{n}, ⪯) is not complemented, since 1¯2 has no complement in (B_{2}, ⪯).

5.2. Homotopy Type and Möbius Function. The following results generalize wellknown properties of the classical weak order on a Coxeter group. Recall that an atom in an interval [π, σ] is an element τ ∈ [π, σ] covering π. Recall also the notation A_{∨} from Lemma 5.3(ii).

Lemma 5.5. Suppose that π ≺ σ in B_{n}. Then, for any two sets A and B of atoms in the interval [π, σ], we have

A ≠ B ⟹ A_{∨} ≠ B_{∨}.

Proof. For a set A of atoms in the interval [π, σ], define

A_{1} := A ∩ {πa_{i} : 1 ≤ i ≤ n − 1}

and

A_{2} := A ∩ {πb_{i} : 1 ≤ i ≤ n}.

Assume now that A and B are sets of atoms in [π, σ] such that A_{∨} = B_{∨}. We shall prove that A = B.

Since |πb_{i}| = |π| for all i, it follows from Lemma 5.3(ii) that

|A_{∨}| = ⋁_{τ∈A} |τ| = ⋁_{τ∈A_{1}} |τ|,

where joins are taken in S_{n}. Consequently, we have

A_{∨} = B_{∨} implies |A_{∨}| = |B_{∨}|, and the latter implies A_{1} = B_{1}.

The last implication holds since joins of sets of atoms uniquely determine the sets in any interval in the usual weak order on S_{n}; see, e.g., [3, Lemma 3.2.4(i)].

We still need to show that A_{2} = B_{2}. If σ = πa_{i} covers π then, by definition, Pos(σ^{−1}) is the (disjoint) union of Pos(π^{−1}) and {|π(i + 1)|}, while M(|π|, |A_{∨}|) is the (not necessarily disjoint) union of M(|σ|, |A_{∨}|) and {|π(i+1)|}. Hence, for every σ ∈ A_{1}, we have

Pos(σ^{−1}) ∪ M(|σ|, |A_{∨}|) = Pos(π^{−1}) ∪ M(|π|, |A_{∨}|).

On the other hand, if σ = πb_{i} ∈ A_{2}, then

Pos(σ^{−1}) ∪ M(|σ|, |A_{∨}|) = (Pos(π^{−1}) \ {π(i)}) ∪ M(|π|, |A_{∨}|).

Thus, by Lemma 5.3(ii), we obtain

Pos(A_{∨}^{−1}) = ⋂_{σ∈A_{1}∪A_{2}} (Pos(σ^{−1}) ∪ M(|σ|, |A_{∨}|))

= (Pos(π^{−1}) ∪ M(|π|, |A_{∨}|)) ∩ ⋂_{σ∈A_{2}} (Pos(σ^{−1}) ∪ M(|σ|, |A_{∨}|))

= (Pos(π^{−1}) ∪ M(|π|, |A_{∨}|)) ∩ ⋂_{πb_{i}∈A_{2}} ((Pos(π^{−1}) \ {π(i)}) ∪ M(|π|, |A_{∨}|))

= (Pos(π^{−1}) \ {π(i) : πb_{i} ∈ A_{2}}) ∪ M(|π|, |A_{∨}|).

(The intermediate steps, though not the end result, should be slightly rewritten if A_{1} = ∅.) If we show that

(9)  πb_{i} ∈ A_{2} implies π(i) ∉ M(|π|, |A_{∨}|),

it will then follow that, assuming |A_{∨}| = |B_{∨}|,

(10)  Pos(A_{∨}^{−1}) = Pos(B_{∨}^{−1}) if and only if A_{2} = B_{2}.

Indeed,

πb_{i} ∈ A_{2} implies π(i) > 0, and the latter implies πa_{i−1} ∉ A_{1}.

An examination of |A_{∨}| as a join of atoms in an interval of S_{n} shows that

M(|π|, |A_{∨}|) ⊆ {|π(i)| : πa_{i−1} ∈ A_{1}},

which implies (9) and (10) and completes the proof. □

Lemma 5.5 leads to an easy way to determine the homotopy type and Möbius function for open intervals in (B_{n}, ⪯), generalizing [3, Theorem 3.2.7 and Corollary 3.2.8].

Proposition 5.6. Suppose that π ≺ σ in B_{n} and finv(σ)−finv(π) ≥ 2. Then the order complex of the open interval (π, σ) is homotopy equivalent to the sphere S^{k−2} if σ is the join of k atoms in the interval [π, μ_{0}], and is contractible otherwise.

Corollary 5.7. For every π, σ ∈ B_{n},

μ(π, σ) = \begin{cases}(−1)^{k}, & if σ is the join of k atoms in [π, μ_{0}]; \\ 0, & otherwise. \end{cases}

The proofs of Proposition 5.6 and Corollary 5.7 are along the lines of the analogous proofs for the symmetric group [3, Theorem 3.2.7 and Corollary 3.2.8], and are left to the reader.

5.3. Tits Property. In this subsection, it will be shown that maximal chains in (B_{n}, ⪯ ) exhibit a Tits-type connectivity property.

Let π, σ ∈ B_{n} such that π ⪯ σ. Each maximal chain in the interval [π, σ] of (B_{n}, ⪯) corresponds to a unique word w = s_{i_{1}} ⋯ s_{i_{d}} of length d = finv(σ) − finv(π) with letters s_{i_{j}} in the alphabet S_{2,n}, such that finv(πs_{i_{1}} ⋯ s_{i_{j}}) − finv(π) = j for all 1 ≤ j ≤ d.

Proposition 5.8 (Tits Property). Any two maximal chains in any interval [π, σ] of (B_{n}, ⪯) are connected via the following pseudo-Coxeter moves on the corresponding words:

b_{i}b_{j} ⟷ b_{j}b_{i}, 1 ≤ i < j ≤ n, (T 1) a_{i}b_{j} ⟷ b_{j}a_{i}, j ≠ i, i + 1, (T 2) a_{i}b_{i+1} ⟷ b_{i}a_{i}, 1 ≤ i ≤ n − 1, (T 3) a_{i}a_{j} ⟷ a_{j}a_{i}, |i − j| > 1, (T 4)

and

(T 5)  a_{i}a_{i+1}b_{i+1}a_{i} ⟷ a_{i+1}b_{i+1}a_{i}a_{i+1}, 1 ≤ i ≤ n − 1.

In order to prove this proposition, we first classify maximal chains in certain special intervals.

Lemma 5.9. Let π ∈ B_{n}, s, s′ ∈ S_{2,n}, s ≠ s′, such that both πs and πs′ cover π. Then the following assertions hold true:

(i) The interval [π, πs ∨ πs′] contains exactly two maximal chains, one described by a word starting with s, and one by a word starting with s′.

(ii) The above words are independent of π, as long as both πs and πs′ cover π.

Denote by α(s, s′) the word corresponding to the chain starting with s. (iii) The complete list of words corresponding to maximal chains in intervals of the

form [π, πs ∨ πs′] in (B_{n}, ⪯) is:

α(b_{i}, b_{j}) = b_{i}b_{j}, i ≠ j;
α(a_{i}, b_{j}) = a_{i}b_{j}, α(b_{j}, a_{i}) = b_{j}a_{i}, j ≠ i, i + 1;
α(a_{i}, b_{i}) = a_{i}b_{i+1}, α(b_{i}, a_{i}) = b_{i}a_{i}, 1 ≤ i ≤ n − 1;
α(a_{i}, a_{j}) = a_{i}a_{j}, |i − j| > 1;

and

α(a_{i}, a_{i+1}) = a_{i}a_{i+1}b_{i+1}a_{i}, α(a_{i+1}, a_{i}) = a_{i+1}b_{i+1}a_{i}a_{i+1}, 1 ≤ i ≤ n − 2.

The words α(a_{i}, b_{i+1}) and α(b_{i+1}, a_{i}) do not exist, since πa_{i} and πb_{i+1} cannot cover π simultaneously.

Proof of Lemma 5.9. First of all, πa_{i} and πb_{i+1} cannot cover π simultaneously since, by Corollary 4.3,

πa_{i} covers π implies π(i + 1) < 0, and the latter implies πb_{i+1} ≺ π.

We shall deal with the other cases one by one.

If i ≠ j then, by Corollary 4.3, πb_{i} and πb_{j} cover π if and only if π(i) > 0 and π(j) > 0. Then πb_{i} ∨ πb_{j} = πb_{i}b_{j}, and indeed α(b_{i}, b_{j}) = b_{i}b_{j} is unique and independent of π.

If j ≠ i, i + 1 then, by Corollary 4.3, πa_{i} and πb_{j} cover π if and only if π(i + 1) < 0, |π(i)| < |π(i+1)| and π(j) > 0. Then πa_{i} ∨πb_{j} = πa_{i}b_{j} = πb_{j}a_{i}, so that α(a_{i}, b_{j}) = a_{i}b_{j} and α(b_{j}, a_{i}) = b_{j}a_{i} are clearly unique and independent of π.

If πa_{i} and πb_{i} cover π (for some 1 ≤ i ≤ n − 1) then, by Corollary 4.3, π(i) > 0, π(i + 1) < 0 and |π(i)| < |π(i + 1)|. Then πa_{i} ∨ πb_{i} = πb_{i}a_{i} = πa_{i}b_{i+1}, and again α(a_{i}, b_{i}) = a_{i}b_{j+1} and α(b_{i}, a_{i}) = b_{i}a_{i} are unique and independent of π.

Similarly, if |i − j| > 1 then πa_{i} and πa_{j} cover π if and only if π(i + 1) < 0, |π(i)| < |π(i + 1)|, π(j + 1) < 0 and |π(j)| < |π(j + 1)|. Then πa_{i} ∨ πa_{j} = πa_{i}a_{j}, so that α(a_{i}, a_{j}) = a_{i}a_{j} is clearly unique and independent of π.

In all of the above cases, the interval [π, πs ∨ πs′] is of length 2. It is easy to identify which generators a_{k} appear in a maximal chain, and the rest readily follows.

Let us now turn to the last case, and assume that πa_{i} and πa_{i+1} cover π, for some 1 ≤ i ≤ n − 2. By Corollary 4.3, π(i + 1) < 0, π(i + 2) < 0 and |π(i)| < |π(i + 1)| < |π(i + 2)|. By Lemma 5.3(ii), σ := πa_{i} ∨ πa_{i+1} satisfies |σ| = |π|s_{i}s_{i+1}s_{i} and Pos(σ^{−1}) = Pos(π^{−1}) ∪ {|π(i + 1)|, |π(i + 2)|}. Thus finv(σ) − finv(π) = 2 · 3 − 2 = 4. The only maximal chains in S_{n} from |π| to |σ| correspond to s_{i}s_{i+1}s_{i} and s_{i+1}s_{i}s_{i+1}, and thus each maximal chain from π to σ must correspond to either a_{i}a_{i+1}a_{i} or a_{i+1}a_{i}a_{i+1}, with one additional letter of type b_{k}. It is easy to see that the only possibilities are α(a_{i}, a_{i+1}) = a_{i}a_{i+1}b_{i+1}a_{i} and α(a_{i+1}, a_{i}) = a_{i+1}b_{i+1}a_{i}a_{i+1}. □

Proof of Proposition 5.8. The proof is similar to the analogous proof for the symmetric group [3, Theorem 3.3.1]. It proceeds by induction on the difference between the ranks of the top and bottom elements.

If the difference is zero then the statement obviously holds.

Assume that the difference is k > 0. Consider two maximal chains in the interval [π, σ], corresponding to the words ss_{2} ⋯ s_{k} and s′s′_{2} ⋯ s′_{k}, all letters being in S_{2,n}. Thus

σ = πss_{2} ⋯ s_{k} = πs′s′_{2} ⋯ s′_{k}.

If s = s′ then the statement holds by the induction hypothesis for the interval [πs, σ]. If s ≠ s′ then πs ⪯ σ and πs′ ⪯ σ. By the lattice property, πs ∨ πs′ ⪯ σ. By

Lemma 5.9 there exists a maximal chain in the interval [π, πs ∨ πs′] corresponding to the word α(s, s′) starting with s. It can be extended to a maximal chain in [π, σ] corresponding to the word α(s, s′)β, where β corresponds to some maximal chain in [πs ∨ πs′, σ]. Both words ss_{2} ⋯ s_{k} and α(s, s′)β start with s. By the induction hypothesis for [πs, σ], it is possible to transform ss_{2} ⋯ s_{k} into α(s, s′)β using the moves (T 1)–(T 5). By the same argument applied to s′, it is possible to transform α(s′, s)β into s′s′_{2} ⋯ s′_{k} using the moves (T 1)–(T 5). Finally, by Lemma 5.9, it is possible to transform α(s, s′)β into α(s′, s)β using one of the moves (T 1)–(T 5), thus completing the proof. □

6. Bivariate Distribution

Let

E_{n}(t) := ∑_{π∈S_{n}} t^{des(π)}

be the Eulerian Polynomial. More generally, let

S_{n}(q, t) := ∑_{π∈S_{n}} q^{inv(π)}t^{des(π)}.

Recall that (B_{n}, ⪯) is graded by finv.

Definition 6.1. For every π ∈ B_{n} let wdes(π) be the number of elements in B_{n} which are covered by π in the poset (B_{n}, ⪯).

Lemma 6.2. For every π ∈ B_{n}, we have

wdes(π) = # (Des(|π|) ∪ Neg(π)) .

Proof. By Corollary 4.3 (with π and σ interchanged), σ is covered by π in (B_{n}, ⪯) if and only if

(i) there exists 1 ≤ i ≤ n, such that

i ∈ Neg(π)  and  σ = πb_{i};

or (ii) there exists 1 ≤ i ≤ n − 1, such that

i ∉ Neg(π), |π(i)| > |π(i + 1)|  and  σ = πa_{i}^{−1}.

Hence, the set of elements which are covered by π in (B_{n}, ⪯) is

{πb_{i} : i ∈ Neg(π)} ∪ {πa_{i}^{−1} : i ∈ Des(|π|) \ Neg(π)},

a disjoint union.

It follows that

wdes(π) = #Neg(π) + #(Des(|π|) \ Neg(π)) = #(Des(|π|) ∪ Neg(π)).
□

Proposition 6.3. For every n, we have

∑_{π∈B_{n}} t^{wdes(π)} = (1 + t)^{n} · E_{n} (\frac{2t}{1 + t})

and

∑_{π∈B_{n}} q^{finv(π)}t^{wdes(π)} = (1 + qt)^{n} · S_{n} (q^{2}, \frac{(1 + q)t}{1 + qt}) .

Remark 6.4. By a well known result of Stanley [12], S_{n}(q, t) has an elegant q-exponential generating function; for details and generalizations see [3, §7.2]. It follows that the same is true when the pair (finv, wdes) is used instead of (inv, des).

Proof of Proposition 6.3. ℤ_{2}^{n} and S_{n} can be viewed as subgroups of B_{n}, restricting elements π ∈ B_{n} to have |π| = id or π(i) > 0, i = 1, …, n, respectively. Moreover, every π ∈ B_{n} can be written in the form π = vu for some u ∈ ℤ_{2}^{n} and v = |π| ∈ S_{n}. Hence,

∑_{π∈B_{n}} t^{wdes(π)} = ∑_{u∈ℤ_{2}^{n}} ∑_{v∈S_{n}} t^{wdes(vu)}.

FLAG WEAK ORDER ON WREATH PRODUCTS 17

By Lemma 6.2, the right-hand side is equal to

∑_{u∈ℤ_{2}^{n}} ∑_{v∈S_{n}} t^{#(Des(v)∪Neg(u))} = ∑_{v∈S_{n}} ∑_{u∈ℤ_{2}^{n}} t^{#Des(v)}t^{#(Neg(u)\Des(v))}

= ∑_{v∈S_{n}} t^{#Des(v)} ∑_{u∈ℤ_{2}^{n}} t^{#(Neg(u)\Des(v))}

= ∑_{v∈S_{n}} t^{#Des(v)}2^{#Des(v)}(1 + t)^{n−#Des(v)}

= (1 + t)^{n} ∑_{v∈S_{n}} (\frac{2t}{1 + t})^{#Des(v)}

= (1 + t)^{n} · E_{n} (\frac{2t}{1 + t}) .

The proof of the second identity is similar:

∑_{π∈B_{n}} q^{finv(π)}t^{wdes(π)} = ∑_{u∈ℤ_{2}^{n}} ∑_{v∈S_{n}} q^{finv(vu)}t^{wdes(vu)}

= ∑_{u∈ℤ_{2}^{n}} ∑_{v∈S_{n}} q^{2·inv(v)+#Neg(u)}t^{#(Des(v)∪Neg(u))}

= ∑_{v∈S_{n}} q^{2·inv(v)}t^{#Des(v)} ∑_{u∈ℤ_{2}^{n}} q^{#Neg(u)}t^{#(Neg(u)\Des(v))}

= ∑_{v∈S_{n}} q^{2·inv(v)}t^{#Des(v)}(1 + q)^{#Des(v)}(1 + qt)^{n−#Des(v)}

= (1 + qt)^{n} ∑_{v∈S_{n}} q^{2·inv(v)} (\frac{(1 + q)t}{1 + qt})^{#Des(v)}

= (1 + qt)^{n} · S_{n} (q^{2}, \frac{(1 + q)t}{1 + qt}) .

□

7. Wreath Products

The above results generalize to the group G(r, n) := ℤ_{r} ≀S_{n}, for every positive integer r. The proofs are similar and will be left to the reader.

For 1 ≤ i ≤ n define the vector d_{i} := (δ_{i1}, …, δ_{in}) ∈ ℤ_{r}^{n}, where

δ_{ij} = \begin{cases}1, & if i = j; \\ 0, & otherwise. \end{cases}

Let

a_{i} := (d_{i}, s_{i}), 1 ≤ i ≤ n − 1,

and

b_{i} := (d_{i}, id), 1 ≤ i ≤ n.

Proposition 7.1. The wreath product G(r, n) = ℤ_{r} ≀ S_{n} is generated by the set S_{r,n} := {a_{i} : 1 ≤ i ≤ n − 1} ∪ {b_{i} : 1 ≤ i ≤ n} with defining relations (B1)–(B8) of Proposition 3.2, except that relation (B1) is replaced by

(B1_{r})  b_{i}^{r} = 1, 1 ≤ i ≤ n,

Recall Definition 2.1 of the flag inversion number.

Definition 7.2. The flag (right) weak order on G(r, n), ⪯, is the reflexive and transitive closure of the relation

π ⋖ πs implies π ∈ G(r, n), s ∈ S_{r,n} and finv(π) < finv(πs).

Proposition 7.3. The poset (G(r, n), ⪯) is (i) ranked (by flag inversion number); (ii) self-dual (by π ↦ π̄μ_{0}, where μ_{0} = ((r − 1, …, r − 1), [n, …, 1]) is the unique

maximal element in this order and π̄ = ((−c_{1}, …, −c_{n}), τ) when π = ((c_{1}, …, c_{n}), τ)); and

(iii) rank-symmetric and unimodal.

Proposition 7.4. σ covers π in (G(r, n), ⪯) if and only if either (i) there exists 1 ≤ i ≤ n such that

c_{i}(π) ≠ r − 1  and  σ = πb_{i};

or (ii) there exists 1 ≤ i ≤ n − 1 such that

c_{i+1}(π) = r − 1, |π(i)| < |π(i + 1)|  and  σ = πa_{i}.

In the following statement, elements −c_{j}(π^{−1}) = c_{|π^{−1}(j)|}(π) ∈ ℤ_{r} are compared using the natural linear order 0 < 1 < ⋯ < r − 1 on ℤ_{r}.

Proposition 7.5. For every π, σ ∈ G(r, n), we have

π ⪯ σ if and only if Inv(|π^{−1}|) ⊆ Inv(|σ^{−1}|) and

{j : −c_{j}(π^{−1}) > −c_{j}(σ^{−1})} ⊆ M [Inv(|σ^{−1}|) \ Inv(|π^{−1}|)] .

It follows that all the results of Section 5 can be generalized to G(r, n). In particular, the following assertions hold true.

Proposition 7.6. The poset (G(r, n), ⪯) is a lattice.

Lemma 7.7. Let A be an arbitrary subset of G(r, n).

(i) The meet A_{∧} of A in (G(r, n), ⪯) is determined by

|A_{∧}| := ⋀_{σ∈A} |σ|,

where the meet is taken with respect to the (right) weak order on S_{n}, and by

−c_{j}(A_{∧}^{−1}) := min{−c_{j}(σ^{−1}) : σ ∈ A, j ∉ M(|A_{∧}|, |σ|)}, 1 ≤ j ≤ n,

where M(|π|, |σ|) := M [Inv(|σ^{−1}|) \ Inv(|π^{−1}|)], and the minimum is taken with respect to the linear order 0 < 1 < ⋯ < r − 1 on ℤ_{r}, using the convention min ∅ := max ℤ_{r} = r − 1.

(ii) The join A_{∨} of A in (G(r, n), ⪯) is determined by

|A_{∨}| := ⋁_{σ∈A} |σ|

and by

−c_{j}(A_{∨}^{−1}) := max{−c_{j}(σ^{−1}) : σ ∈ A, j ∉ M(|σ|, |A_{∨}|)}, 1 ≤ j ≤ n,

using the convention max ∅ := min ℤ_{r} = 0.

Proposition 7.8. Suppose that π ≺ σ in G(r, n) and finv(σ) − finv(π) ≥ 2. Then the order complex of the open interval (π, σ) is homotopy equivalent to the sphere S^{k−2} if σ is the join of k atoms in the interval [π, μ_{0}], and is contractible otherwise.

Corollary 7.9. For every π, σ ∈ G(r, n), we have

μ(π, σ) = \begin{cases}(−1)^{k}, & if σ is a join of k atoms in [π, μ_{0}]; \\ 0, & otherwise. \end{cases}

Definition 7.10. For every π ∈ G(r, n), we write wdes(π) for the number of elements in G(r, n) which are covered by π in the poset (G(r, n), ⪯).

Clearly, for r = 1, wdes is the standard descent number. For r = 2 it coincides with Definition 6.1.

Proposition 7.11. For every n and r, we have

∑_{π∈G(r,n)} t^{wdes(π)} = (1 + (r − 1)t)^{n} · E_{n} (\frac{rt}{1 + (r − 1)t})

and

∑_{π∈G(r,n)} q^{finv(π)}t^{wdes(π)} = (1 + [r − 1]_{q}qt)^{n} · S_{n} (q^{r}, \frac{[r]_{q}t}{1 + [r − 1]_{q}qt}) .

8. Final Remarks and Open Problems

Recall the pseudo-Coxeter moves (T 1)–(T 5) from Proposition 5.8. Consider the graph Γ_{n}, whose vertices are all maximal chains in the flag weak order on B_{n} and whose edges correspond to these moves. By Proposition 5.8, Γ_{n} is connected.

Problem 8.1. Find the diameter of Γ_{n}.

For a solution of an analogous problem for the classical weak orders of types A and B see [11].

Following comments of an anonymous referee, it should be noted that progress toward a solution of Problem 8.1 may be obtained by explicit calculation of various poset parameters such as order dimension and width. Another approach is a search for symmetries induced by group actions, as well as recursive poset properties such as supersolvability. Such methods were found useful in similar contexts; see, e.g., [1, 11].

It is now natural to look for a definition of a nicely-behaved weak order on other complex reflection groups. A key tool may be the discovery of convenient presentations for kernels of one-dimensional characters.

Finally, a challenging problem is to find a “correct” definition of strong (Bruhat) order on wreath products and other complex reflection groups, having desired properties (such as a nice interval structure and a subword property) which, hopefully, demonstrate an interplay with the flag weak order. Such an order may be useful in developing an appropriate Kazhdan–Lusztig theory.

Acknowledgements. The authors thank the anonymous referees for many helpful comments.

References

[1] R. M. Adin, M. Firer and Y. Roichman, Triangle-free triangulations, Adv. Appl. Math. 45 (2010), 77–95.

[2] R. M. Adin, Y. Cherniavsky and Y. Roichman, Strong order on colored rook monoids and (q, t)- Stirling numbers, in preparation.

[3] A. Björner and F. Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005.

[4] N. Bourbaki, Lie Groups and Lie Algebras, English translation by Andrew Pressley, Springer, New York, 2002.

[5] F. Brenti, V. Reiner and Y. Roichman, Alternating subgroups of Coxeter groups, J. Combin. Theory Ser. A 115 (2008), 845–877.

[6] H. L. M. Faliharimalala and A. Randrianarivony, Flag-major index and flag-inversion number on colored words and wreath product, Sém. Lothar. Combin. 62 (2010), Art. B62c, 10 pp. (electronic).

[7] M. Fire, Statistics on wreath products, preprint; arχiv:math/0409421.

[8] D. Foata and G. -N. Han, Signed words and permutations, I. A fundamental transformation, Proc. Amer. Math. Soc. 135 (2007), 31–40.

[9] D. Foata and G.-N. Han, Statistical Distributions on Words and q-Calculus on Permutations,

Strasbourg, 2007; available at http://www-irma.u-strasbg.fr/~foata/paper/pub109.html.

[10] J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, 29, Cambridge University Press, Cambridge, 1990.

[11] V. Reiner and Y. Roichman, Diameter of reduced words, Trans. Amer. Math. Soc. (to appear);

arχiv:0906.4768.

[12] R. P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combin. Theory Ser. A 20 (1976), 336–356.

[13] A. Vershik and M. Vsemirnov, The local stationary presentation of the alternating groups and the normal form, J. Algebra 319 (2008), 4222–4229.

Department of Mathematics, Bar-Ilan University, 52900 Ramat-Gan, Israel

E-mail address: radin@math.biu.ac.il

Dipartimento di Matematica, Universitá di Roma “Tor Vergata”, Via della Ricerca Scientifica, 00133 Roma, Italy

E-mail address: brenti@mat.uniroma2.it

Department of Mathematics, Bar-Ilan University, 52900 Ramat-Gan, Israel

E-mail address: yuvalr@math.biu.ac.il