Affine Permutations of Type A

Anders Björner^{1} Department of Mathematics Kungl. Tekniska Högskolan S-100 44 Stockholm, Sweden

Francesco Brenti^{2} Dipartimento di Matematica Universitá degli Studi di Perugia I-06123 Perugia, Italy

Submitted: August 17, 1995; Accepted: September 24, 1995

Dédié à D. Foata à l’occasion de ses soixante bougies

Abstract

We study combinatorial properties, such as inversion table, weak order and Bruhat order, for certain infinite permutations that realize the affine Coxeter group Ã_{n}.

1 Introduction

Denote by S̃_{n} the group (under composition) of all bijections π : Z → Z such that π(x) + n = π(x + n), for all x ∈ Z, and π(1) + π(2) + … + π(n) = (\begin{matrix}n+1 \\ 2 \end{matrix}). With respect to the adjacent transpositions (i, i + 1) (mod n), i = 1, 2, …, n, this gives a realization of the affine Coxeter group Ã_{n−1}. This was pointed out by Lusztig [17] and has also appeared in the work of Shi [19] and of H. and K. Eriksson [9, 10].

1Partially supported by EC grant No. CHRX-CT93-0400

2Part of this work was carried out while the author was a member of the Institute for Advanced Study in Princeton, New Jersey, U.S.A., and was partially supported by NSF grant DMS 9304580 and EC grant No. CHRX-CT93-0400.

In this paper we study combinatorial properties of such “affine permutations”. We define the inversion table of an affine permutation and show that this gives a bijection between S̃_{n} and certain integer sequences. A direct enumerative consequence is Bott’s formula for the length generating function of Ã_{n−1}. Specialized to minimal coset representatives modulo the symmetric group S_{n} we get a bijection between S̃_{n}/S_{n} and the set of integer partitions with at most n − 1 parts.

In the later sections we give combinatorial rules for comparing affine permutations in weak order and in Bruhat order. The former is done in terms of containment of certain inversion multigraphs. These are directed graphs whose indegree sequence is the inversion table. For Bruhat order a somewhat more involved criterion is given, which amounts to the containment of certain associated skew shapes and which specializes to the well known “tableau criterion” for ordinary permutations.

Affine permutations of other types, giving combinatorial models for some of the other affine Coxeter groups, have been studied by H. and K. Eriksson [9, 10].

2 Notation and Preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this work. We let P =^{def} {1, 2, 3, …} , N=^{def}P ∪{0}, Z be the ring of integers, and Q be the field of rational numbers. For a ∈N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅), and given n, m ∈ Z, n ≤ m, we let [n, m] =^{def} {n, n+1, …, m−1, m}. Given a set A we denote its cardinality by |A| and its power set by P(A). For a ∈ Q we let ⌊a⌋ (respectively, ⌈a⌉) denote the largest integer ≤ a (respectively, smallest integer ≥ a), and |a| be the absolute value of a (this should cause no confusion with the notation |A| used when A is a set).

Given a set T we let S(T) be the set of all bijections π : T → T, and S_{n} =^{def} S([n]). If σ ∈ S_{n} then we write σ = σ_{1} … σ_{n} to mean that σ(i) = σ_{i}, for i = 1, …, n. Given σ, τ ∈ S_{n} we let στ =^{def} σ ∘ τ (composition of functions) so that, for example, (1, 2)(2, 3) = (1, 2, 3).

We will follow [20], Chap. 3, for notation and terminology concerning partially ordered sets.

We will follow [15] for general Coxeter groups notation and terminology. In particular, given a Coxeter system (W, S) and σ ∈ W we denote by l(σ) the length of σ in W, with respect to S, and we let

D(σ) =^{def} {s ∈ S : l(σ s) < l(σ)} .

We call D(σ) the descent set of σ. We denote by e the identity of W, and we let T =^{def} {σsσ^{−1} : σ ∈ W, s ∈ S} be the set of reflections of W. Given u ∈ W we let

T_{u} =^{def} {t ∈ T : l(ut) < l(u)} .

We denote by “≤” (respectively “⪯”) the Bruhat order (respectively (left) weak order) on W. Recall (see, e.g., [15], §5.9) that this means that x ≤ y (respectively, x ⪯ y) if and only if there exist r ∈ N and t_{1}, …, t_{r} ∈ T (respectively, ∈ S) such that t_{r} … t_{1} x = y and l(t_{i} … t_{1} x) > l(t_{i−1} … t_{1}x) for i = 1, …, r. For example, the Hasse diagram of the Bruhat order on S_{3} is shown in Figure 1, while that of its (left) weak order is shown in Figure 2. The following result is well known; see [15] for part i) and [1] or [2] for part ii).

Proposition 2.1 Let (W, S) be a Coxeter system and u, v ∈ W. Then:

i) l(u) = |T_{u}|;

ii) u ⪯ v if and only if T_{u} ⊆ T_{v}.

[figure: 123; 321; 213; 312; 132; 231]

Figure 1

[figure: 123; 321; 213; 312; 132; 231]

Figure 2

Given J ⊆ S we let W_{J} be the subgroup of W generated by J and

W^{J} =^{def} {w ∈ W : D(w) ⊆ S \ J}.

We call W_{J} the parabolic subgroup generated by J and W^{J} the set of minimal left coset representatives of W_{J}. We will often consider W_{J} and W^{J} as posets with the partial ordering induced by Bruhat order. Recall (see, e.g., [15], §1.10) that given u ∈ W and J ⊆ S there exist unique elements u_{J} ∈ W_{J} and u^{J} ∈ W^{J} such that

u = u^{J} u_{J}

and l(u) = l(u_{J}) + l(u^{J}). The following result on Bruhat order will be used in section 6.

Theorem 2.2 (Deodhar [5]) Let u, v ∈ W and H ⊆ P(S), ∅ ∉ H, be such that ⋂_{J∈H} J = ∅. Then the following are equivalent:

i) u ≤ v;

ii) u^{J} ≤ v^{J} for all J ∈ H.

3 Affine permutations

For n ∈ P we let S̃_{n} be the group of all bijections π of Z in itself such that

π(x + n) = π(x) + n,  (1)

for all x ∈ Z, and

∑_{x=1}^{n} π(x) = (\begin{matrix}n+1 \\ 2 \end{matrix}) ,  (2)

with composition as group operation. Clearly, such a π is uniquely determined by its values on [n], and we write π = [a_{1}, …, a_{n}] to mean that π(i) = a_{i} for i = 1, …, n, and call this the window notation of π. For example, if n = 5, π = [2, 1, −2, 0, 14], and σ = [15, −3, −2, 4, 1] then πσ = [24, −4, −7, 0, 2]. Note that, for all σ ∈ S̃_{n} and i, j ∈ Z,

σ(i) ≢ σ(j) (mod n)  (3)

if and only if i ≢ j (mod n).

There is an alternative notation for the elements of S̃_{n} which we will sometimes use. Given σ ∈ S̃_{n} write

σ(i) = n r_{i} + k_{i}

where r_{i} ∈ Z, and k_{i} ∈ [n], for i = 1, …, n. Then, by (3), k_{1}, …, k_{n} are a permutation of [n], and, by (2), ∑_{i=1}^{n} r_{i} = 0. We will then write

σ = (r_{1}, …, r_{n}|\overline{σ})

where \overline{σ} ∈ S_{n} is such that \overline{σ}(i) = k_{i} for i = 1, …, n. For example, if σ = [−4, 1, −6, 19] ∈ S̃_{4} then we also write σ = (−2, 0, −2, 4|4, 1, 2, 3) (so \overline{σ} = 4123). Note that if σ = (r_{1}, …, r_{n}|\overline{σ}) and τ = (s_{1}, …, s_{n}|\overline{τ}) then

σ τ = (s_{1} + r_{\overline{τ}(1)}, …, s_{n} + r_{\overline{τ}(n)}|\overline{σ} \overline{τ})

and

σ^{−1} = (−r_{(\overline{σ})^{−1}(1)}, …, −r_{(\overline{σ})^{−1}(n)}|(\overline{σ})^{−1}).

The group S̃_{n} is clearly generated by S =^{def} {s_{1}, s_{2}, …, s_{n}} where s_{i} =^{def} [1, 2, …, i −

1, i + 1, i, i + 2, …, n] for i = 1, …, n − 1 and s_{n} =^{def} [0, 2, 3, …, n − 1, n + 1]. For

σ ∈ S̃_{n} we let

lÃ(σ) =^{def} min{r ∈ N : σ = s_{i_{1}} … s_{i_{r}} for some i_{1}, …, i_{r} ∈ [n]},

and

invÃ(σ) =^{def} ∑_{1≤i<j≤n} |⌊\frac{σ(j) − σ(i)}{n}⌋| .

For example, if σ = [15, −3, −2, 4, 1] ∈ S̃_{5} then

invÃ(σ) = |⌊\frac{−18}{5}⌋| + |⌊\frac{−17}{5}⌋| + |⌊\frac{−11}{5}⌋| + |⌊\frac{−14}{5}⌋| + |⌊\frac{1}{5}⌋| + |⌊\frac{7}{5}⌋|

+ |⌊\frac{4}{5}⌋| + |⌊\frac{6}{5}⌋| + |⌊\frac{3}{5}⌋| + |⌊\frac{−3}{5}⌋| = 17 .

Proposition 3.1 (Shi [19]) Let n ∈ P. Then

lÃ(σ) = invÃ(σ)  (4)

for all σ ∈ S̃_{n}.

Proof. We prove first that

invÃ(σ) ≤ lÃ(σ)  (5)

for all σ ∈ S̃_{n}. It is easy to see that

invÃ(σs_{i}) = invÃ(σ) + |⌊\frac{σ(i) − σ(i + 1)}{n}⌋| − |⌊\frac{σ(i + 1) − σ(i)}{n}⌋|
= invÃ(σ) − sgn(σ(i) − σ(i + 1)),  (6)

if i ∈ [n − 1], and that

invÃ(σ s_{n}) = invÃ(σ) − ∑_{1≤j≤n−1} (|⌊\frac{σ(j) − σ(1)}{n}⌋| + |⌊\frac{σ(n) − σ(j)}{n}⌋|)
+ ∑_{2≤j≤n−1} (|⌊\frac{σ(j) − σ(n)}{n}⌋ + 1| + |⌊\frac{σ(1) − σ(j)}{n}⌋ + 1|)
+ |⌊\frac{σ(1) − σ(n)}{n} + 2⌋|
= invÃ(σ) + |⌊\frac{σ(1) − σ(n)}{n}⌋ + 2| − |⌊\frac{σ(n) − σ(1)}{n}⌋|  (7)
= invÃ(σ) + sgn (\frac{σ(1) − σ(n)}{n} + 1) .

Since invÃ(e) = lÃ(e) = 0, (6) and (7) prove (5), as claimed.

We now prove (4) by induction on invÃ(σ). If invÃ(σ) = 0 then ⌊\frac{σ(j)−σ(i)}{n}⌋ = 0 for all 1 ≤ i < j ≤ n, and hence σ(1) < σ(2) < … < σ(n) and σ(n) − σ(1) < n. This implies that σ(i) = σ(1) + i − 1 for i = 1, …, n and therefore, by (2), that σ = e, so that (4) holds. So let t ∈ N and σ ∈ S̃_{n} be such that invÃ(σ) = t + 1. Then σ ≠ e and hence there exists s ∈ S such that invÃ(σ s) = t (otherwise (6) and (7) would imply that σ(1) < σ(2) < … < σ(n) < σ(1) + n and hence that σ = e, as noted above). This, by the induction hypothesis, implies that lÃ(σ s) = t and hence that lÃ(σ) ≤ t + 1. Therefore lÃ(σ) ≤ invÃ(σ) and this, by (5), concludes the induction step and hence the proof. □

As a consequence we obtain the following simple combinatorial description of the “descent set” of an element of S̃_{n}.

Proposition 3.2 Let n ∈ P and σ ∈ S̃_{n}. Then

D(σ) = {i ∈ [n] : lÃ(σ s_{i}) < lÃ(σ)} = {i ∈ [n] : σ(i) > σ(i + 1)}.

Proof. By Proposition 3.1 we have that

{i ∈ [n] : lÃ(σ s_{i}) < lÃ(σ)} = {i ∈ [n] : invÃ(σ s_{i}) < invÃ(σ)} ,

and the result follows from (6) and (7). □

Given π ∈ S̃_{n} and a, b ∈ Z we say that a is to the left of b in π if π^{−1}(a) < π^{−1}(b). The preceding two results enable us to give a simple proof of the following fundamental fact. Proposition 3.3 (Lusztig [17]) (S̃_{n}, S) is a Coxeter system of type Ã_{n−1}. Proof. We will show that the pair (S̃_{n}, S) satisfies the Exchange Condition and this will imply, by [15], §1.9, that (S̃_{n}, S) is a Coxeter system. The computation of its type is straightforward. So let i, i_{1}, …, i_{p} ∈ [n] and suppose that

lÃ(s_{i_{1}} … s_{i_{p}}s_{i}) < lÃ(s_{i_{1}} … s_{i_{p}}) .  (8)

We want to show that there exists a j ∈ [p] such that

s_{i_{1}} … s_{i_{p}}s_{i} = s_{i_{1}} … ŝ_{i_{j}} … s_{i_{p}} ,  (9)

(s_{i_{j}} omitted). Let w =^{def} s_{i_{1}} … s_{i_{p}}, b =^{def} w(i), and a =^{def} w(i + 1). By Proposition 3.2 we know that (8) means that b > a. Therefore a is to the left of b in the identity, but is to the right of b in w. Hence there exists j ∈ [p] such that a is to the left of b in s_{i_{1}} … s_{i_{j−1}} but a is to the right of b in s_{i_{1}} … s_{i_{j}}. Hence s_{i_{1}} … ŝ_{i_{j}} … s_{i_{p}} and s_{i_{1}} … s_{i_{p}} are equal except that a + kn and b + kn are interchanged (for each k ∈ Z) and this, by the definitions of w, a, and b, implies (9). □

There are, of course, other ways to prove Proposition 3.3. For example, if we let G be the subgroup of S̃_{n} generated by {s_{1}, …, s_{n−1}} and H be the subgroup generated by {g_{1}, …, g_{n−1}} where

g_{i} =^{def} [1, 2, … i − 1, n + i, i + 1 − n, i + 2, …, n − 1, n]

for i = 1, …, n − 1, then it is not hard to verify that G ≅ S_{n}, that H ≅ Z^{n−1}, that G normalizes H, that G ∪ H generates S̃_{n}, and that G ∩ H = {e}. This shows that S̃_{n} is the semidirect product of G and H with respect to the action of G on H given by conjugation (this is sometimes also called the internal semidirect product). On the other hand, if we let (A_{n−1}, {s̄_{1}, …, s̄_{n−1}}) be a Coxeter system of type A_{n−1}, Φ be its root system, α_{1}, …, α_{n−1} its simple roots, and L the translation group generated by the coroots (in the canonical geometric representation of A_{n−1}, see [15], §5.3), then it is not difficult to show that there are unique group isomorphisms φ : G → A_{n−1} and θ : H → L such that φ(s_{i}) = s̄_{i} and θ(g_{i}) = α_{i}, for i = 1, …, n−1, and θ(s_{i}g_{j}s_{i}) = s̄_{i}(α_{j}) for all i, j ∈ [n − 1]. This shows that the conjugation action of G on H corresponds, under the isomorphisms φ and θ, to the geometric action of A_{n−1} on L, and hence implies, by Proposition 4.2 of [15], that S̃_{n} is isomorphic to a Coxeter system of type Ã_{n−1} (and that s_{1}, …, s_{n} are mapped to the Coxeter generators of Ã_{n−1} under this isomorphism).

We now describe combinatorially the set of reflections of (S̃_{n}, S).

Proposition 3.4 The set of reflections of (S̃_{n}, S) is

{[1, 2, …, i − 1, kn + j, i + 1, …, j − 1, −kn + i, j + 1, …, n] : 1 ≤ i < j ≤ n, k ∈ Z}.

Proof. Let π ∈ S̃_{n}, and i ∈ [n]. Then we have that

πs_{i}π^{−1}(j) = \{ \begin{matrix}j, & if j ≢ π(i), π(i + 1) & (mod n), \\ j − π(i) + π(i + 1), & if j ≡ π(i) & (mod n), \\ j − π(i + 1) + π(i), & if j ≡ π(i + 1) & (mod n), \end{matrix}

for if j ≡ π(i) (mod n) then (πs_{i}π^{−1})(j) = (πs_{i}π^{−1})(j − π(i) + π(i)) = j − π(i) + (πs_{i}π^{−1})(π(i)) = j − π(i) + π(i + 1), and similarly if j ≡ π(i + 1), and the thesis follows. □

For example, if π = [15, −3, −2, 4, 1] then πs_{1}π^{−1} = [1, 20, 3, 4, −13], πs_{2}π^{−1} = [1, 3, 2, 4, 5], πs_{3}π^{−1} = [1, 2, 9, −2, 5], πs_{4}π^{−1} = [4, 2, 3, 1, 5] and πs_{5}π^{−1} = [20, 2, 3, 4, −14].

It is easy to describe combinatorially the maximal parabolic subgroups and their minimal coset representatives in the group (S̃_{n}, S).

Proposition 3.5 Let n ∈ P, i ∈ [n], and J =^{def} S \ {s_{i}}. Then:

i) (S̃_{n})_{J} = {σ ∈ S̃_{n} : σ_{|_{[i+1−n,i]}} ∈ S([i + 1 − n, i])};

ii) S̃_{n}^{J} = {σ ∈ S̃_{n} : σ(1) < … < σ(i), σ(i + 1) < … < σ(n + 1)}. □

In other words, the preceding result says that, given σ ∈ S̃_{n} and J = S \ {s_{i}} (i ∈ [n]), then σ ∈ (S̃_{n})_{J} (respectively, σ ∈ S̃_{n}^{J}) if and only if σ, when restricted to [i+1−n, i], is a permutation of [i+1−n, i] (respectively, if and only if σ(i+1−n) < σ(i + 2 − n) < … < σ(i − 1) < σ(i)).

In the following we shall pay a lot of attention to the special case I = S\{s_{n}}, and the symbol “I” will be reserved for this particular set. Thus (S̃_{n})_{I} is the subgroup of S̃_{n} that permutes the set [n], so (S̃_{n})_{I} ≅ S_{n} gives a naturally embedded copy of the symmetric group, and S̃_{n}^{I} consists of those elements σ = [a_{1}, …, a_{n}] whose window is increasing: a_{1} < … < a_{n}.

Due to the symmetry of Ã_{n−1}’s Coxeter diagram all maximal parabolic subgroups are isomorphic, and in fact even conjugate. Thus there is no lack of generality in confining attention to the special maximal parabolic (S̃_{n})_{I} ≅ S_{n}.

4 Affine Inversion Tables

It is a well known fact that a permutation is uniquely determined by its inversion table (see, e.g., [20], p. 21). In this section we show that this result extends naturally to affine permutations.

Given σ ∈ S̃_{n} and j ∈ Z we let

Inv_{j}(σ) =^{def} |{i ∈ P : j < i, σ(j) > σ(i)}|,  (10)

and

Inv(σ) =^{def} (Inv_{1}(σ), …, Inv_{n}(σ)).

We call Inv(σ) the affine inversion table of σ. For example, if σ = [5, 3, −2] ∈ S̃_{3} then Inv(σ) = (4, 2, 0). Note that (10) implies that

Inv_{j}(σ) = Inv_{j+n}(σ)

for all j ∈ Z, and that if σ ∈ S_{n} (considered as a subgroup of S̃_{n} as above) then Inv(σ) coincides with the usual inversion table.

The following two results give some elementary properties of Inv(σ).

Proposition 4.1 Let σ ∈ S̃_{n}. Then:

i) Inv_{i}(σ) = ∑_{j=1}^{i−1} ⌊\frac{max(σ(i)−σ(j),0)}{n}⌋ + ∑_{j=i+1}^{n} ⌊ \frac{max(σ(i)−σ(j)+n,0)}{n}⌋;

ii) lÃ(σ) = ∑_{i=1}^{n}Inv_{i}(σ);

iii) σ(i) > σ(i + 1) if and only if Inv_{i}(σ) > Inv_{i+1}(σ), for i ∈ [n];

iv) there exists i ∈ [n] such that Inv_{i}(σ) = 0.

Proof. From (10) we have that

Inv_{i}(σ) = |{j ∈ [n] : j > i, σ(j) < σ(i)}| + ∑_{j=1}^{n} |{a ∈ P : σ(j + an) < σ(i)}|

and i) follows. Now ii) follows directly from i) and Proposition 3.1. To prove iii) note that if σ(i) < σ(i + 1) then, by the definition (10), Inv_{i}(σ) ≤ Inv_{i+1}(σ), while if σ(i) > σ(i + 1) then it is clear that Inv_{i}(σ) ≥ Inv_{i+1}(σ) + 1. Finally, choosing i ∈ [n] such that σ(i) = min{σ(1), …, σ(n)} proves iv). □

Given σ ∈ S_{n} and j ∈ [n] we will find it convenient to let

inv_{j}(σ) =^{def} |{k ∈ [n] : k < j, σ(k) > σ(j)}| .  (11)

Lemma 4.2 Let i ∈ [n], and σ = (r_{1}, …, r_{n}|\overline{σ}) ∈ S̃_{n}^{I}. Then:

i) Inv_{i}(σ) = 0 if and only if σ(i) < σ(1) + n;

ii) Inv_{i}(σ) = i r_{i} + ∑_{j=i+1}^{n}r_{j} − inv_{i}(\overline{σ}).

In particular, Inv_{n}(σ) = σ(n) − n.

Proof. We prove i) first. We may clearly assume that i ≥ 2. Suppose first that Inv_{i}(σ) = 0. Then from i) of Proposition 4.1 we deduce in particular that

⌊\frac{max(σ(i) − σ(1), 0)}{n}⌋ = 0

and the result follows since σ(1) < σ(i) by hypothesis. Conversely, suppose that σ(i) < σ(1) + n. Then since σ ∈ S̃_{n}^{J} we deduce from Proposition 3.5 that

σ(1) ≤ σ(j) < σ(i) < σ(1) + n

for all j ∈ [i − 1], and σ(i) < σ(j) for all j ∈ [i + 1, n]. Hence we have from i) of Proposition 4.1 that

Inv_{i}(σ) = ∑_{j=1}^{i−1} ⌊\frac{max(σ(i) − σ(j), 0)}{n}⌋ + ∑_{j=i+1}^{n} ⌊\frac{max(σ(i) − σ(j) + n, 0)}{n}⌋ = 0.

To prove ii) note that from i) of Proposition 4.1 we conclude that

Inv_{i}(σ) = ∑_{j=1}^{i−1} ⌊\frac{σ(i) − σ(j)}{n}⌋
= ∑_{j=1}^{i−1} ((r_{i} − r_{j}) + ⌊\frac{\overline{σ}(i) − \overline{σ}(j)}{n}⌋)
= (i − 1)r_{i} − ∑_{j=1}^{i−1} r_{j} − inv_{i}(\overline{σ})
= i r_{i} + ∑_{j=i+1}^{n} r_{j} − inv_{i}(\overline{σ}),

as desired. □

We now introduce the basic operators that are the “building blocks” of our bijection between affine permutations and affine inversion tables. Let [a_{1}, …, a_{n}] ∈ S̃_{n}^{I} and i ∈ [2, n] be such that

{r ∈ [n − 1] : r + a_{i} ∉ {a_{i+1}, …, a_{n}} (mod n), r + a_{i} < a_{i+1}} ≠ ∅.

We then define

E_{i}([a_{1}, …, a_{n}]) =^{def} [a_{1}, …, a_{j−1}, a_{j} − k, a_{j+1}, …, a_{i−1}, a_{i} + k, a_{i+1}, …, a_{n}] (12)

where

k =^{def} min{r ∈ [n − 1] : r + a_{i} ∉ {a_{i+1}, …, a_{n}}(mod n), r + a_{i} < a_{i+1}}  (13)

and j is the unique element of [i − 1] such that a_{j} ≡ a_{i} + k (mod n).

There is a combinatorially appealing way of describing the operators E_{i}, which we now explain. We may clearly identify every element σ of S̃_{n}^{I} with a subset A of Z, of size n, such that any two elements of A are not congruent modulo n (just take A =^{def} {σ(1), …, σ(n)}). Let us call (and think of) the elements of A as “chips”. Then the subset of Z corresponding to E_{i}(σ) is obtained simply by moving the i-th (from left to right, i.e. i-th smallest) element of A as few steps as possible to the right so that it occupies a position that is not congruent to any of the elements of A that are to its right, and then moving the only chip to its left that occupies a position congruent to the one where the i-th chip has been moved to, a corresponding number of steps to the left. Figure 3 illustrates this process for n = 4, σ = [−3, 2, 3, 8] and i = 3.

The next result gives the fundamental property of the operators E_{i}.

Proposition 4.3 Let σ = [a_{1}, …, a_{n}] ∈ S̃_{n}^{I} and i ∈ [n] be such that Inv_{j}(σ) = 0 for all j ∈ [i − 1] and either Inv_{i}(σ) < Inv_{i+1}(σ) or i = n. Then:

i) {r ∈ [n − 1] : r + a_{i} < a_{i+1}, r + a_{i} ∉ {a_{i+1}, …, a_{n}} (mod n) } ≠ ∅, if i < n;

ii) E_{i}(σ) ∈ S̃_{n}^{I}; iii)

Inv_{t}(E_{i}(σ)) = \{ \begin{matrix}Inv_{t}(σ), & if t ∈ [n] \ \{i\}, \\ Inv_{t}(σ) + 1, & if t = i. \end{matrix}

Proof. Let

h =^{def} min{g ∈ Z : a_{i} < g < a_{i+1} and σ^{−1}(g) > 0}

(h certainly exists since Inv_{i}(σ) < Inv_{i+1}(σ)). Since a_{1} < … < a_{n} this implies that σ^{−1}(h) > n and that h ≡ a_{j} (mod n) for some j ≤ i. Choosing r =^{def} h − a_{i} then proves i). Now let k ∈ P and j ∈ [n] be defined as in (12) and (13) (k exists by i)). Then a_{i} + k ≡ a_{j} (mod n), and a_{i} + r ∈ {a_{i+1}, …, a_{n}} (mod n) for all r ∈ [k − 1]. Hence a_{j} −r ∈ {a_{i}, …, a_{n}} (mod n) for all r ∈ [k] and therefore a_{j−1} ∉ [a_{j} −k, a_{j} −1], which proves ii). To prove iii) let r_{0} ∈ N be such that

a_{i} + k = a_{j} + r_{0}n.  (14)

Since a_{j−1} < a_{j} − k (by ii)) we conclude from i) of Proposition 4.1 that, if t ≥ i + 1, then

Inv_{t}(E_{i}(σ)) − Inv_{t}(σ) = ⌊\frac{a_{t} − (a_{i} + k)}{n}⌋ + ⌊\frac{a_{t} − (a_{j} − k)}{n}⌋ − ⌊\frac{a_{t} − a_{i}}{n} ⌋ − ⌊\frac{a_{t} − a_{j}}{n} ⌋
= ⌊\frac{a_{t} − a_{j} − r_{0}n}{n}⌋ + ⌊\frac{a_{t} − a_{i} + r_{0}n}{n}⌋ − ⌊\frac{a_{t} − a_{0}}{n} ⌋ − ⌊\frac{a_{t} − a_{j}}{n} ⌋
= 0.  (15)

Now let t ∈ [i − 1]. Then Inv_{t}(σ) = 0 and this by Lemma 4.2 implies that σ(t) < σ(1) + n. Now if j ≠ 1 then E_{i}(σ)(t) ≤ σ(t) < σ(1) + n = E_{i}(σ)(1) + n, and hence Inv_{t}(E_{i}(σ)) = 0 by Lemma 4.2. If j = 1 then we claim that σ(t) < σ(1) − k + n. In fact, if σ(t) = σ(1) + n − r for some r ∈ [k] then a_{t} ≡ a_{1} − r ≡ a_{i} + k − r (mod n) by (14) and this, by the definition (13) of k, implies that a_{t} ∈ {a_{i}, a_{i+1}, …, a_{n}} (mod n), which is a contradiction. Hence E_{i}(σ)(t) = σ(t) < σ(1) − k + n = E_{i}(σ)(1) + n and this again implies that Inv_{t}(E_{i}(σ)) = 0 by Lemma 4.2. Also, if m ∈ [i − 1] \ {j} and d ∈ Z is such that

a_{i} < a_{m} + d n

then

a_{i} < a_{m} + d n − k

(for if r ∈ [k] is such that a_{i} = a_{m} + dn − r then a_{m} ≡ a_{i} + r (mod n) and this, by the definition (13) of k, implies that a_{m} ∈ {a_{j}} ∪ {a_{i+1}, …, a_{n}} (mod n), which is a contradiction). Therefore

⌊\frac{a_{i} − a_{m} + k}{n} ⌋ = ⌊\frac{a_{i} − a_{m}}{n} ⌋  (16)

for m ∈ [i − 1] \ {j}. Finally, note that

⌊\frac{(a_{i} + k) − (a_{j} − k)}{n}⌋ = ⌊\frac{r_{0}n + k}{n} ⌋ = r_{0} = ⌊\frac{r_{0}n − k}{n} ⌋ + 1 = ⌊\frac{a_{i} − a_{j}}{n} ⌋ + 1 . (17)

Hence,

Inv_{i}(E_{i}(σ)) = ∑_{m=1}^{i−1} ⌊\frac{max(E_{i}(σ)(i) − E_{i}(σ)(m), 0)}{n}⌋
= ⌊\frac{σ(i) + k − (σ(j) − k)}{n}⌋ + ∑_{m∈[i−1]\\{j\}} ⌊\frac{σ(i) + k − σ(m)}{n}⌋
= ⌊\frac{σ(i) − σ(j)}{n}⌋ + 1 + ∑_{m∈[i−1]\\{j\}} ⌊\frac{σ(i) − σ(m)}{n}⌋
= Inv_{i}(σ) + 1

by (16), (17), and i) of Proposition 4.1. □

We are now ready to prove the first main result of this section.

Theorem 4.4 We have that

Inv : S̃_{n}^{I} → P_{n−1}

is a bijection, where P_{n−1} is the set of all partitions of length ≤ n − 1.

Proof. Note first that if σ ∈ S̃_{n}^{I} then, by Proposition 3.5, σ(1) < … < σ(n) and hence , by iii) and iv) of Proposition 4.1, 0 = Inv_{1}(σ) ≤ Inv_{2}(σ) ≤ … ≤ Inv_{n}(σ), so that Inv(σ) ∈ P_{n−1}.

Now let 0 = λ_{1} ≤ λ_{2} ≤ … ≤ λ_{n} be an element of P_{n−1}. We define

C(λ_{1}, …, λ_{n}) =^{def} E_{2}^{λ_{2}} … E_{n−1}^{λ_{n−1}}E_{n}^{λ_{n}}([1, 2, …, n]).

It is then clear from Proposition 4.3 that C is well defined and that

Inv(C(λ_{1}, …, λ_{n})) = (λ_{1}, …, λ_{n})

for all (λ_{1}, …, λ_{n}) ∈ P_{n−1}. To complete the proof we therefore have to show that Inv: S̃_{n}^{I} → P_{n−1} is an injective map.

So let σ, τ ∈ S̃_{n}^{I} and suppose that Inv(σ) = Inv(τ). Let σ = (r_{1}, …, r_{n}|\overline{σ}) and τ = (s_{1}, …, s_{n}|\overline{τ}). Then, by ii) of Lemma 4.2 (with i = n), we have that

n r_{n} − inv_{n}(\overline{σ}) = n s_{n} − inv_{n}(\overline{τ})

and hence (since inv_{n}(\overline{σ}), inv_{n}(\overline{τ}) ∈ [0, n−1]) we conclude that r_{n} = s_{n} and inv_{n}(\overline{σ}) = inv_{n}(\overline{τ}). Now from ii) of Lemma 4.2 (with i = n − 1) we conclude that

(n − 1)r_{n−1} − inv_{n−1}(\overline{σ}) = Inv_{n−1}(σ) − r_{n}
= Inv_{n−1}(τ) − s_{n}
= (n − 1)s_{n−1} − inv_{n−1}(\overline{τ})

and hence (since inv_{n−1}(\overline{σ}), inv_{n−1}(\overline{τ}) ∈ [0, n−2]) that r_{n−1} = s_{n−1} and inv_{n−1}(\overline{σ}) = inv_{n−1}(\overline{τ}). Continuing in this way we conclude that r_{i} = s_{i} and inv_{i}(\overline{σ}) = inv_{i}(\overline{τ}) for all i = 1, …, n. Therefore, by the invertibility of the ordinary inversion table for permutations ([20], p. 21), \overline{σ} = \overline{τ} and hence σ = τ. □

We illustrate the preceding theorem with an example. Let n = 4 and λ = (1, 2, 4) ∈ P_{3}. Then we have from our definitions that

C(1, 2, 4) = E_{2}E_{3}^{2}E_{4}^{4}([1, 2, 3, 4])
= E_{2}E_{3}^{2}E_{4}^{3}([0, 2, 3, 5])
= E_{2}E_{3}^{2}E_{4}^{2}([0, 1, 3, 6])
= E_{2}E_{3}^{2}E_{4}([0, 1, 2, 7])
= E_{2}E_{3}^{2}([−1, 1, 2, 8])
= E_{2}E_{3}([−2, 1, 3, 8])
= E_{2}([−2, −1, 5, 8])
= [−5, 2, 5, 8].

Indeed, Inv([−5, 2, 5, 8]) = (0, 1, 2, 4). It is instructive to model the computation of C(1, 2, 4) by successively moving chips on Z, as explained above.

To prove our main result we now need one last technical fact. For i ∈ [n − 1] and (b_{1}, …, b_{n}) ∈ N^{n} \ P^{n} let

D_{i}(b_{1}, …, b_{n}) =^{def} \{ \begin{matrix}(b_{1}, …, b_{i−1}, b_{i+1}, b_{i} − 1, b_{i+2}, …, b_{n}), & if b_{i} > b_{i+1}, \\ (b_{1}, …, b_{i−1}, b_{i+1} + 1, b_{i}, b_{i+2}, …, b_{n}), & if b_{i} ≤ b_{i+1}. \end{matrix}

Note that D_{i}(b_{1}, …, b_{n}) ∈ N^{n} \ P^{n} and that D_{i}^{2} = Id for every i ∈ [n − 1].

Lemma 4.5 Let σ ∈ S̃_{n} and i ∈ [n − 1]. Then

Inv(σs_{i}) = D_{i}(Inv(σ)).

Proof. If Inv_{i}(σ) ≤ Inv_{i+1}(σ) then (by iii) of Proposition 4.1) σ(i) < σ(i + 1) and hence

Inv_{j}(σ s_{i}) = \{ \begin{matrix}Inv_{i}(σ), & if j = i + 1, \\ Inv_{i+1}(σ) + 1, & if j = i, \\ Inv_{j}(σ), & if j ≠ i, i + 1. \end{matrix}

Similarly, if Inv_{i}(σ) > Inv_{i+1}(σ) then σ(i) > σ(i + 1) and hence

Inv_{j}(σ s_{i}) = \{ \begin{matrix}Inv_{i}(σ) − 1, & if j = i + 1, \\ Inv_{i+1}(σ), & if j = i, \\ Inv_{j}(σ), & if j ≠ i, i + 1. \end{matrix}

The result follows. □

We can now prove the main result of this section.

Theorem 4.6 The map Inv: S̃_{n} → N^{n} \ P^{n} is a bijection.

Proof. Let (b_{1}, …, b_{n}) ∈ N^{n} \ P^{n}. It is then easy to see (e.g., by induction on ∑_{i=1}^{n} b_{i}) that there exist i_{1}, …, i_{k} ∈ [n − 1] such that

D_{i_{k}} … D_{i_{1}}(b_{1}, …, b_{n})

is nondecreasing. By Theorem 4.4 there exists σ ∈ S̃_{n}^{I} such that Inv(σ) = D_{i_{k}} … D_{i_{1}}(b_{1}, …, b_{n}). Hence, by Lemma 4.5,

Inv(σs_{i_{k}} … s_{i_{1}}) = D_{i_{1}} … D_{i_{k}}D_{i_{k}} … D_{i_{1}}(b_{1}, …, b_{n}) = (b_{1}, …, b_{n}),

and this proves surjectivity.

To prove injectivity let σ, τ ∈ S̃_{n} be such that Inv(σ) = Inv(τ) = (b_{1}, …, b_{n}). Then, as noted above, there exist i_{1}, …, i_{k} ∈ [n − 1] such that

D_{i_{k}} … D_{i_{1}}(b_{1}, …, b_{n})

is nondecreasing. But by Lemma 4.5 we have that

Inv(σs_{i_{1}} … s_{i_{k}}) = D_{i_{k}} … D_{i_{1}}(b_{1}, …, b_{n}) = Inv(τs_{i_{1}} … s_{i_{k}}).

Since D_{i_{k}} … D_{i_{1}}(b_{1}, …, b_{n}) is nondecreasing we conclude by Proposition 4.1 and Theorem 4.4 that σs_{i_{1}} … s_{i_{k}} = τs_{i_{1}} … s_{i_{k}}, and the result follows. □

We illustrate the preceding theorem with an example. Let n = 4, and (1, 0, 4, 1) ∈ N^{4} \ P^{4}. Then

D_{1}D_{3}(1, 0, 4, 1) = D_{1}(1, 0, 1, 3) = (0, 0, 1, 3),

and since

C(0, 0, 1, 3) = E_{2}^{0}E_{3}^{1}E_{4}^{3}([1, 2, 3, 4]) = [−2, 1, 4, 7],

we conclude that

(1, 0, 4, 1) = D_{3}D_{1}(0, 0, 1, 3)
= D_{3}D_{1}(Inv([−2, 1, 4, 7]))
= Inv([−2, 1, 4, 7]s_{1}s_{3})
= Inv([1, −2, 7, 4]).

As an immediate consequence of Theorem 4.6 we obtain the following expression for the length-generating function of Ã_{n−1}, which is the type A specialization of a formula by Bott [3], (see also [15], §8.9).

Corollary 4.7 Let n ∈ P. Then

∑_{w∈S̃_{n}} x^{l(w)} = \frac{1 + x + x^{2} + … + x^{n−1}}{(1 − x)^{n−1}} = ∏_{i=1}^{n−1} \frac{1 + x + … + x^{i}}{1 − x^{i}}

Proof. By Theorem 4.6 and ii) of Proposition 4.1 we have that

∑_{w∈S̃_{n}} x^{l(w)} = ∑_{α∈N^{n}\P^{n}} x^{|α|} = ∑_{α∈N^{n}} x^{|α|} − ∑_{α∈P^{n}} x^{|α|} = \frac{1}{(1 − x)^{n}} − \frac{x^{n}}{(1 − x)^{n}} ,

and the first equality follows. The second one is elementary. □

Another combinatorial proof of Corollary 4.7 appears in [7].

5 Weak order and the Young lattice

With an ordinary permutation π ∈ S_{n} is associated its inversion graph G_{π}. This is the graph on vertex set [n] having edges (i, j) where i < j and π(i) > π(j). Such graphs are characterized by the property that both G_{π} and the complementary graph \overline{G_{π}} are transitive (when all edges are oriented toward the greater of the adjacent nodes). Furthermore, π ⪯ σ in left weak order if and only if G_{π} ⊆ G_{σ}. See [21] for these facts. The last one is a special case of ii) of Proposition 2.1.

In this section we define a directed inversion multigraph I_{π} for affine permutations π ∈ S̃_{n}, and we show that these graphs determine left weak order by inclusion. The problem of finding a graph-theoretic characterization of affine inversion multigraphs is left open.

For π ∈ S̃_{n} we let I_{π} have [n] as its set of vertices, and we put an edge of weight (or multiplicity) |⌊\frac{π(j)−π(i)}{n}⌋| between i and j directed toward the node with highest π-value, for all 1 ≤ i < j ≤ n. Edges of multiplicity zero are deleted. For instance, the inversion multigraph of [−11, −2, 15, 11, 2] is shown in Figure 4.

Figure 4

There is an obvious connection with the inversion tables used in Section 4.

Lemma 5.1 Let π ∈ S̃_{n}. Then Inv_{i}(π) is the indegree (number of in-directed edges, counted with multiplicities) of node i in the graph I_{π}. □ Thus, Inv(π) is in graph-theoretic terms the indegree sequence of I_{π}. Theorem 4.6 therefore implies the following. Corollary 5.2 An affine permutation π is uniquely determined by its inversion graph I_{π}. □ Now, define inclusion I_{π} ⊆ I_{σ} of inversion graphs to mean that each directed multiedge in I_{π} occurs with the same direction and greater or equal multiplicity in I_{σ}. Theorem 5.3 Let π, σ ∈ S̃_{n}. Then π ⪯ σ in left weak order if and only if I_{π} ⊆ I_{σ}. Proof. This is merely a combinatorial restatement of part ii) of Proposition 2.1. To see this we must determine the set T_{π} of reflections associated to π. These are of the following two kinds. For 1 ≤ i < j ≤ n let m(i, j) = |⌊\frac{π(j)−π(i)}{n}⌋|.

1. If π(i) < π(j) and m(i, j) > 0 then the reflections t ∈ T such that πt = […, π(j) − kn, …, π(i) + kn, …], 1 ≤ k ≤ m(i, j), belong to T_{π}.

2. If π(i) > π(j) then the reflections t ∈ T such that π t = […, π(j)+kn, …, π(i)− kn, …], 0 ≤ k ≤ m(i, j) − 1, belong to T_{π}.

We leave to the reader the easy verification (using Proposition 3.1) that these are the only possible t ∈ T for which l(π t) < l(π), and that T_{π} ⊆ T_{σ} if and only if I_{π} ⊆ I_{σ}. □

It is now an easy computation to check, for example, that [−2, −3, 11] ⪯̸ [14, −8, 0]. The two inversion graphs are shown in Figure 5.

On the other hand, by Proposition 6.6 one has that [−2, −3, 11] ≤ [14, −8, 0] in Bruhat order.

If all ascents π(i) < π(j), i < j, are large enough then the graph I_{π} is complete, which has the following consequence.

Corollary 5.4 If π, σ ∈ S̃_{n} and no pair 1 ≤ i < j ≤ n satisfies 0 < π(j) − π(i) < n, then π ⪯ σ in left weak order implies that π and σ have the same overall ascent/descent pattern (i.e., π(j) − π(i) and σ(j) − σ(i) have the same sign for all 1 ≤ i < j ≤ n). □

There is a natural partial order on the set P_{n−1} of partitions with at most n − 1 parts, called the Young lattice, obtained by inclusion of their diagrams. This means that

λ ≤ μ ⇔ λ_{1} ≤ μ_{1}, …, λ_{n−1} ≤ μ_{n−1}

for partitions λ, μ ∈ P_{n−1}, 0 ≤ λ_{1} ≤ … ≤ λ_{n−1}, 0 ≤ μ_{1} ≤ … ≤ μ_{n−1}. Because of the bijection Inv: S̃_{n}^{I} → P_{n−1} (Theorem 4.4) we can pull the Young lattice back to S̃_{n}^{I} and obtain a third partial order, in addition to weak order and Bruhat order. Alternatively, we may, via the Inv bijection, talk about weak order and Bruhat order on the set P_{n−1} of length-restricted partitions. Either way, the three partial orders are related as follows, with strict inclusions.

Theorem 5.5 Weak order ⊆ Young lattice ⊆ Bruhat order.

Proof. Let π, σ ∈ S̃_{n}^{I}. If π ⪯ σ in weak order then I_{π} ⊆ I_{σ}, so by our definitions and Lemma 5.1, Inv(π) ≤ Inv(σ) in Young lattice order.

Now, assume that Inv(π) < Inv(σ) is a covering in the Young lattice. Then the entries of Inv(π) = (b_{1}, b_{2}, …, b_{n}) and of Inv(σ) = (c_{1}, c_{2}, …, c_{n}) are identical in all positions except one, where b_{i} + 1 = c_{i}. In this situation σ = π t for some reflection t. This is most easily seen using the map Inv^{−1} = C : P_{n−1} → S̃_{n}^{I} defined in the proof of Theorem 4.4 and the combinatorial interpretation of C(b_{1}, b_{2}, …, b_{n}) = E_{2}^{b_{2}} … E_{n}^{b_{n}}([1, 2, …, n]) in terms of moving chips on the integer line Z, explained in Section 4. In fact, let for brevity α =^{def} C(0, …, 0, b_{i}, …, b_{n}), and

k =^{def} min{r ∈ [n−1] : r+α(i) ∉ {α(i+1), …, α(n)} (mod n), r+α(i) < α(i+1)}.

Then it’s not hard to verify (we leave the details to the reader) that, for any a ∈ [2, i] and b ∈ [0, c_{a−1}], the chip positions of C(0, …, 0, b, b_{a}, …, b_{n}) and C(0, …, 0, b, c_{a}, …, c_{n}) are equal except that the i-th (from the left) chip of C(0, …, 0, b, b_{a}, …, b_{n}) lies k steps to the left of the i-th chip of C(0, …, 0, b, c_{a}, …, c_{n}), while the j-th chip of C(0, …, 0, b, b_{a}, …, b_{n}) lies k steps to the right of the j-th chip of C(0, …, 0, b, c_{a}, …, c_{n}) (for some j ∈ [i − 1]).

Since l(σ) = ∑ c_{i} = ∑ b_{i} + 1 = l(π) + 1 and σ = πt this shows that π < σ in Bruhat order. By transitivity this implies that all Young lattice relations are also Bruhat relations. □

[figure: [1,2,3]; [0,2,4]; [0,1,5]; [-1,3,4]; [-1,1,6]; [-2,3,5]; [-1,0,7]; [-2,2,6]; [-3,4,5]; [-2,0,8]; [-3,2,7]; [-4,4,6]]

Figure 6

Figure 6 illustrates left weak order on S̃_{3}^{I} with the extra relations of the Young lattice added as dotted lines. For the corresponding picture of Bruhat order see Figure 9. Enumerative properties of the weak order on S̃_{3}^{I} (under the name “Hex”) have been investigated by Propp [18], Section 2, and Fomin [14], Example 2.7.1. Its dual (in the sense of Fomin) turns out to be Bruhat order on S̃_{3}^{I} (with certain positive integral multiplicities). The higher posets S̃_{n}^{I} (n > 3) have to our knowledge not been investigated from this point of view.

Let L_{n,k} be the set of partitions with at most k parts of size at most n − k. In other words, the partitions that fit into a k×(n−k) rectangle. There is a well-known bijection

S_{n}^{J} → L_{n,k},

where S_{n}^{J} = S_{n}/(S_{k} × S_{n−k}) is the set of minimal coset representatives of S_{n} modulo the maximal parabolic subgroup S_{k} × S_{n−k}. Thus, one can talk about left weak order, Young lattice (containment of shapes) and Bruhat order also for S_{n}^{J}. The same inclusions hold, however in this situation they are not strict. In fact, they all coincide, as was remarked in [1], §4.9.

6 Bruhat order

The Bruhat ordering of S̃_{n} will be characterized in terms of a certain encoding of group elements π ∈ S̃_{n} as monotone functions φ_{π} : Z → Z. We begin by discussing the basic properties of this encoding.

The following notation will be used in this section, for given n ∈ P:

\begin{aligned}[a]^{+} & = & \{a + kn : k ∈ N\} \\ [a]_{<j}^{+} & = & [a]^{+} ∩ \{m ∈ Z : m < j\}. \end{aligned}

For an arbitrary finite set S ⊆ Z and j ∈ Z define

φ_{S}(j) = ∑_{a∈S} |[a]_{<j}^{+}| = ∑_{a∈S} max (0, ⌈\frac{j − a}{n}⌉) .

Hence, φ_{S}(j) counts the total number of integers less than j that belong to some right half congruence class of some element of S. If π ∈ S̃_{n} then we will write φ_{π} to mean φ_{{π(1),...,π(n)}}. The following property is immediate.

Lemma 6.1 Let π ∈ S̃_{n}. Then φ_{π} is a unit increase monotone function on Z, by which we mean that 0 ≤ φ_{π}(j + 1) − φ_{π}(j) ≤ 1 for all j ∈ Z. □

We will now for a while assume that π ∈ S̃_{n}^{I}, i.e., that the window is increasing.

Lemma 6.2 Let π ∈ S̃_{n}^{I}. Then:

i) φ_{π}(j) = \{ \begin{matrix}0, & if j ≤ π(1), \\ j − 1, & if j > π(n) − n; \end{matrix}

ii) φ_{π}(j) > \{ \begin{matrix}0, & if π(1) < j ≤ 1, \\ j − 1, & if 1 ≤ j ≤ π(n) − n. \end{matrix}

iii) π is uniquely determined by φ_{π}’s restriction to any interval [x, y] such that φ_{π}(x) = 0 and φ_{π}(y) = y − 1.

Proof. We begin by observing that

φ_{e}(j) = \{ \begin{matrix}0, & if j ≤ 1, \\ j − 1, & if j ≥ 1, \end{matrix}

for the identity element e = [1, 2, …, n]. Let e = π_{0} ⊲ π_{1} ⊲ … ⊲ π_{s} = π be a maximal chain in Bruhat order of S̃_{n}^{I}. Then, by Proposition 3.4, each covering π_{i} ⊲ π_{i+1} is of the form π_{i} = [π_{i}(1), …, π_{i}(a), …, , π_{i}(b), …, π_{i}(n)] ⊲ [π_{i}(1), …, π_{i}(a) − s, …, π_{i}(b) + s, …, π_{i}(n)] = π_{i+1}, for some 1 ≤ a < b ≤ n, s ≥ 1, such that π_{i}(a) − s ≡ π_{i}(b) (mod n). Thus, φ_{π_{i+1}} ≥ φ_{π_{i}} and φ_{π_{i+1}}(j) = φ_{π_{i}}(j) for all j ≤ π_{i}(a)−s and j > π_{i}(b)+s−n. From this part i) follows and also part ii) with nonstrict inequalities “≥ 0”. For the strict inequality one checks that φ_{π}(π(n)−n) = π(n)−n and uses the monotone unit increase property (Lemma 6.1).

Reading the values φ_{π}(j), for j = x, x + 1, …, y, we record the j where the function increases for the first time for each congruence class modulo n. These positions (minus one) give the successive values π(1), π(2), …, π(n), hence they determine π. □

We now come to the Bruhat order criterion for S̃_{n}^{I}, which is the basic stepping stone to the general criterion.

Theorem 6.3 Let π, σ ∈ S̃_{n}^{I}. Then the following conditions are equivalent:

i) π ≤ σ in Bruhat order;

ii) φ_{π} ≤ φ_{σ};

iii) φ_{π}(j) ≤ φ_{σ}(j), for all j such that π(1) < j ≤ π(n) − n and j ∈ ⋃_{i=1}^{n}([π(i)]^{+} ∪ [σ(i)]^{+}).

Proof.

i) ⇒ ii). It suffices to check the inequality for the case when π ⊲ σ is a covering, and this was already done in the proof of Lemma 6.2. ii) ⇒ i). Let Φ(π, σ) = ∑_{j∈Z}(φ_{σ}(j) − φ_{π}(j)). This is a finite quantity (by Lemma 6.2), and under hypothesis ii) we have that Φ(π, σ) ≥ 0. The proof will be by induction on Φ(π, σ).

If Φ(π, σ) = 0 then φ_{π} = φ_{σ} and hence π = σ by (iii) of Lemma 6.2.

Assume that Φ(π, σ) > 0. The plan is to find a reflection t ∈ T such that π < π t ∈ S̃_{n}^{I}, φ_{π t} ≤ φ_{σ}, and Φ(π t, σ) < Φ(π, σ). Then by induction π t < σ, and we will be done.

Let k ≥ 1 be minimal such that π(k) ≠ σ(k). Then σ(k) < π(k), since φ_{π} ≤ φ_{σ}. Notice that k < n, since π(n) = (\begin{matrix}n+1 \\ 2 \end{matrix}) − π(1) − … − π(n − 1). Let

c =^{def} max{i ∈ [σ(k)]^{+} : i < π(k)}.

Thus, σ(k) ≤ c < π(k) ≤ c + n. Let D = {z ∈ Z|c ≤ z < π(k) and z ≢ π(i) (mod n) for all 1 ≤ i ≤ k − 1}. Note that D ≠ ∅ since c ∈ D. Let

u =^{def} min{i ∈ P : π(p) − in ∈ D for some p > k},  (18)

and

q =^{def} max{p ∈ [k + 1, n] : π(p) − un ∈ D}.

Notice that this implies that

c ≤ π(k + 1) − un < … < π(q − 1) − un < π(q) − un < π(k) ≤ c + n. (19)

Finally, let t be the reflection such that

π t = [π(1), …, π(q) − u n, …, π(k) + u n, …, π(n)],

with changes in the window of π occurring only in the positions k and q. The window of π t is increasing (since π(q + 1) − un ∉ D and hence π(q + 1) − un ≥ π(k)) and l(πt) > l(π) (in fact: l(π t) = l(π) + 1). Furthermore one sees that

φ_{π t}(j) = \{ \begin{matrix}φ_{π}(j) + 1, & if j ∈ G, \\ φ_{π}(j), & otherwise, \end{matrix}  (20)

where

G =^{def} ⋃_{j=1}^{u}[π(q) − jn + 1, π(k) + (u − j) n].

Hence, Φ(π t, σ) = Φ(π, σ) − |G| = Φ(π, σ) − u(π(k) + u n − π(q)) < Φ(π, σ). So, to complete the argument it remains only to show that φ_{π t} ≤ φ_{σ}, which in view of (20) will follow from

(φ_{π})_{|_{G}} < (φ_{σ})_{|_{G}}.  (21)

Fix v ∈ [n], and let c_{v} = c + (u − v)n and a_{v} = π(k) + (u − v)n. Note that, by (19),

c_{v} ≤ π(k + 1) − vn < … < π(q − 1) − vn < π(q) − vn < a_{v} ≤ c_{v} + n.

From this we deduce that

φ_{π}(c_{v} + 1) < φ_{σ}(c_{v} + 1),  (22)

since φ_{π}(c_{v}) ≤ φ_{σ}(c_{v}) and φ_{σ}(c_{v} + 1) counts the new element c_{v} ∈ [σ(k)]^{+}, which is not counted by φ_{π}(c_{v} + 1). Furthermore, for j ∈ [c_{v} + 1, a_{v} − 1], we have that

φ_{σ}(j + 1) − φ_{σ}(j) = \{ \begin{matrix}1, & if j ∈ \{σ(1), …, σ(k − 1)\} (mod n), \\ ≥ 0, & otherwise, \end{matrix}  (23)

whereas

φ_{π}(j + 1) − φ_{π}(j) = \{ \begin{matrix}1, & if j ∈ \{π(1), …, π(k − 1)\} (mod n), \\ 0, & otherwise, \end{matrix}  (24)

with the “= 0” part implied by the minimality of u. But π(i) = σ(i) for all i ∈ [k−1], so (22), (23) and (24) imply that

φ_{π}(j) < φ_{σ}(j),

for all j ∈ [c_{v} + 1, a_{v}], which contains the inequalities (21). ii) ⇔ iii). The forward implication is clear. For the converse, observe that φ_{π}(j) = 0 ≤ φ_{σ}(j) for j ≤ π(1), and φ_{π}(j) = j − 1 ≤ φ_{σ}(j) for j > π(n) − n by Lemma 6.2, and that φ_{π}(j + 1) − φ_{π}(j) = 0 = φ_{σ}(j + 1) − φ_{σ}(j) unless j ∈ [π(i)]^{+} ∪ [σ(i)]^{+} for some 1 ≤ i ≤ n. □

The π ↔ φ_{π} encoding of elements of S̃_{n}^{I} can be interpreted as associating a skew Ferrers diagram F (π) with each π ∈ S̃_{n}^{I}. Namely, let F (π) be the set of boxes between the two graphs y = φ_{π}(⌈x⌉) and y = φ_{e}(⌈x⌉) in the xy-plane. For example, if σ = [−4, 4, 6] then y = φ_{σ}(⌈x⌉) has the graph shown in Figure 7, and F (σ) is shown in Figure 8.

-5 -4 -3 -2 -1 1 2 3 4

Figure 7

Figure 8

Theorem 6.3 can now be interpreted as saying that Bruhat order on S̃_{n}^{I} is the same as the order by containment of associated shapes:

π ≤ σ ⇔ F (π) ⊆ F (σ).

There are simpler rules for Bruhat order on S̃_{n}^{I} for n ≤ 3. The n = 2 case is trivial: S̃_{2}^{I} is a one-way infinite chain isomorphic to (N, ≤), and π < σ in S̃_{2}^{I} (and in S̃_{2}) if and only if l(π) < l(σ). The n = 3 case takes the following form.

Proposition 6.4 Let π, σ ∈ S̃_{3}^{I}. Then π ≤ σ if and only if π(1) ≥ σ(1) and π(3) ≤ σ(3).

Proof. This is of course a specialization of Theorem 6.3. However, it is not so easy to see that the inequalities here imply those in part ii) of Theorem 6.3. A better alternative is to check that if σ(1) ≤ π(1) and π(3) ≤ σ(3) for π ≠ σ, then some move is possible in the chip game position corresponding to π (see section 4) leading to a new position π_{1} with σ(1) ≤ π_{1}(1) ≤ π(1) and π(3) ≤ π_{1}(3) ≤ σ(3). Repeating this until equalities are achieved leads to a Bruhat order chain π ⊲ π_{1} ⊲ … ⊲ π_{k} = σ. □

This simple rule is illustrated in Figure 9 showing Bruhat order of S̃_{3}^{I} up to length 5.

[figure: [1,2,3]; [0,2,4]; [0,1,5]; [-1,3,4]; [-1,1,6]; [-2,3,5]; [-1,0,7]; [-2,2,6]; [-3,4,5]; [-2,0,8]; [-3,2,7]; [-4,4,6]]

Figure 9

We are now ready to prove the general result for Bruhat order.

Theorem 6.5 Let π, σ ∈ S̃_{n}. Then the following are equivalent:

i) π ≤ σ in Bruhat order;

ii) φ_{{π(k+1),...,π(k+n)}} ≤ φ_{{σ(k+1),...,σ(k+n)}} for all k ∈ [0, n − 1];

iii) φ_{{π(k+1),...,π(k+n)}}(j) ≤ φ_{{σ(k+1),...,σ(k+n)}}(j) for all k ∈ [0, n − 1] and all j ∈ [min_{1≤i≤n}{π(i)}, max_{1≤i≤n}{π(i)}].

Proof. By Deodhar’s criterion (Theorem 2.2) we have that π ≤ σ if and only if π^{(i)} ≤ σ^{(i)} for all 1 ≤ i ≤ n, where π^{(i)} denotes the minimal coset representative of π modulo (S̃_{n})_{S\{s_{i}}}. For i = n this gives a reduction to the situation in Theorem 6.3. Namely, π^{(n)} is the increasing rearrangement of the standard window [π(1), π(2), …, π(n)] and similarly for σ^{(n)}, so what must be checked (according to Theorem 6.3) is condition ii) for k = 0.

For i ≠ n we get a reduction to a situation equivalent to that in Theorem 6.3. Now π^{(i)} is the increasing rearrangement of the window [π(i+1), π(i+2), …, π(i+n)], and Theorem 6.3 leads to condition ii) for k = i. □

Let us exemplify this rule for π = [5, −3, 4] and σ = [−8, 11, 3]. It must be checked that

φ_{{5,−3,4}}(j) ≤ φ_{{−8,11,3}}(j)
φ_{{8,−3,4}}(j) ≤ φ_{{−5,11,3}}(j)
φ_{{8,0,4}}(j) ≤ φ_{{−5,14,3}}(j)

for all −3 ≤ j ≤ 5. All these inequalities hold, so π ≤ σ. This can also be interpreted as containment for three pairs of skew shapes, as explained in connection with Figure 8. Of course, for n = 3 there is a quicker algorithm. Namely, sort the 6 sets into increasing order and check pairwise “containment” as in Proposition 6.4. In this case we get

[−3, 4, 5] ≤ [−8, 3, 11]
[−3, 4, 8] ≤ [−5, 3, 11]
[0, 4, 8] ≤ [−5, 3, 14].

This procedure can be formalized as follows.

Proposition 6.6 Let π, σ ∈ S̃_{3}. Then π ≤ σ in Bruhat order if and only if min{π(i), π(i + 1), π(i + 2)} ≥ min{σ(i), σ(i + 1), σ(i + 2)} and max{π(i), π(i + 1), π(i + 2)} ≤ max{σ(i), σ(i + 1), σ(i + 2)} for i = 1, 2, 3. □

Theorem 6.5 gives a numerical algorithm for comparing elements of S̃_{n} in Bruhat order. If we disregard the time needed to compute the values

φ_{π}(j) = ∑_{i=1}^{n} |[π(i)]_{<j}^{+}| = ∑_{i=1}^{n} max (0, ⌈\frac{j − π(i)}{n}⌉) ,

this algorithm requires

n max_{1≤i,j≤n}{π(i) − π(j)}

comparisons of such values to determine “π ≤ σ?”. Specialized to elements of the symmetric group S_{n} ⊆ S̃_{n} this gives a O(n^{2}) algorithm for deciding Bruhat order. This algorithm is in fact equivalent to the well-known “tableau criterion”, due to Ehresmann [8], Lehmann [16] and (in the abstract form of Theorem 2.2) Deodhar [5]. The tableau criterion, in the version that arises as a special case of Theorem 6.5, says that π ≤ σ (for two ordinary permutations π and σ) if and only if, for all k, the increasing rearrangement of π(k + 1), …, π(n) is entry by entry greater than or equal to the increasing rearrangement of σ(k + 1), …, σ(n). Equivalently, for all k, the increasing rearrangement of π(1), …, π(k) is entry by entry less than or equal to the increasing rearrangement of σ(1), …, σ(k), which is the usual form of the tableau criterion for S_{n}.

7 Final Comments

We have seen that affine permutations have a combinatorial theory that in many ways is parallel to the classical theory for ordinary permutations. In fact, the resemblance is likely to go further than what has been shown here. A few open questions that we find interesting are:

(7.1) Can permutation statistics, such as excedance, major index, left-to-right minima, etc. (see [20]) be defined for affine permutations so that interesting identities arise, similar to the classical results of P. A. MacMahon, D. Foata, M. P.

Schützenberger and others (see, e.g., [11], [12], [13], and [20])? In particular, is there a natural notion of “major index” for affine permutations which is equidistributed with length on S̃_{n}? Note that the obvious choice of defining

maj(σ) =^{def} ∑_{i∈D(σ)} i

for σ ∈ S̃_{n} does not have this property since, for example, |{σ ∈ S̃_{n} : maj(σ) = 1\}| = +∞ and maj(σ) ≤ (\begin{matrix}n+1 \\ 2 \end{matrix}) for all σ ∈ S̃_{n}. Also, it would be interesting to investigate the cycle structure of affine permutations.

(7.2) Can affine inversion multigraphs be combinatorially characterized? Note that if I_{π} is the directed inversion multigraph of an affine permutation π ∈ S̃_{n} then I_{π} has no antiparallel edges and if I_{π} has directed edges from i to j and from j to k, with 1 ≤ i < j < k ≤ n, then I_{π} has a directed edge from i to k and

m(i, j) + m(j, k) ≤ m(i, k) ≤ m(i, j) + m(j, k) + 1,

where m(a, b) denotes the multiplicity of the directed edge (a, b) for a, b ∈ [n], a < b.

(7.3) In [6] Dyer defines and studies the concept of a “reflection order” for a Coxeter system. It would be interesting to translate Dyer’s definition into the present permutation description of Ã_{n}, thus obtaining a combinatorial characterization of this concept for Ã_{n}. Since reflection orderings play a fundamental role in the computation of both the R-polynomials and the Kazhdan-Lusztig polynomials of a Coxeter system (see [6], Corollary 3.4, and [4], Theorem 4.5), this combinatorial characterization could then yield simpler rules for the computation of these polynomials for Ã_{n}.

References

[1] A. Björner, Orderings of Coxeter groups, in “Combinatorics and Algebra”, (ed. C. Greene), Contemporary Math. Series, Vol. 34, Amer. Math. Soc., 1984, pp. 175-195.

[2] A. Björner and M. Wachs, Generalized quotients in Coxeter groups, Trans. Amer. Math. Soc. 308 (1988), 1-37.

[3] R. Bott, An application of the Morse theory to the topology of Lie groups, Bull. Soc. Math. France 84 (1956), 251-281.

[4] F. Brenti, Combinatorial expansions of Kazhdan-Lusztig polynomials, J. London Math. Soc., to appear.

[5] V. V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function, Invent. Math. 39 (1977), 187-198.

[6] M. Dyer, Hecke algebras and shellings of Bruhat intervals, Comp. Math. 89 (1993), 91-115.

[7] R. Ehrenborg and M. Readdy, Juggling and applications to q-analogues, Discrete Math., special issue on Algebraic Combinatorics, to appear.

[8] C. Ehresmann, Sur la topologie de certains espaces homogènes, Ann. Math. 35 (1934), 396-443.

[9] H. Eriksson, Computational and combinatorial aspects of Coxeter groups, Ph. D. Thesis, KTH, Stockholm, 1994.

[10] H. Eriksson and K. Eriksson, Affine Coxeter groups as infinite permutations (extended abstract), in “Proceedings of FPSAC’ 95 conference”, Paris, 1995.

[11] D. Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236-240.

[12] D. Foata, Distributions Eulériennes et Mahoniennes sur le groupe des permutations, in Higher Combinatorics (M. Aigner, ed.), Reidel, Dordrecht/Boston, 1977.

[13] D. Foata and M.-P. Schützenberger, Théorie géométrique des polynômes Eulériens, Lecture Notes in Math., Vol. 138, Springer, Berlin, 1970.

[14] S. Fomin, Duality of graded graphs, J. Algebraic Combinatorics 3 (1994), 357-404.

[15] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, No.29, Cambridge Univ. Press, Cambridge, 1990.

[16] E. L. Lehmann, Some concepts of dependence, Ann. Math. Statist. 37 (1966), 1137-1153.

[17] G. Lusztig, Some examples of square integrable representations of semisimple p-adic groups, Trans. Amer. Math. Soc. 277 (1983), 623-653.

[18] J. Propp, Some variants of Ferrers diagrams, J. Combin. Theory, Ser. A 52 (1989), 98-128.

[19] J. Shi, The Kazhdan-Lusztig cells in certain affine Weyl groups, Lecture Notes in Math., Vol 1179, Springer, Berlin, 1986.

[20] R. P. Stanley, Enumerative Combinatorics , Vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[21] T. Yanagimoto and M. Okamoto, Partial orderings of permutations and monotonicity of a rank correlation statistic, Ann. Inst. Statist. Math. 21 (1969), 489-506.