Printer Friendly

Affine permutations and rational slope parking functions.

1 Introduction

Parking functions are prevalent in modern combinatorics. There is a natural action of the symmetric group on parking functions, and the orbits are labeled by the non-decreasing parking functions which correspond naturally to Dyck paths. This provides a link between parking functions and various combinatorial objects counted by Catalan numbers. In a series of papers Garsia, Haglund, Haiman, et al. [10, 11], related the combinatorics of Catalan numbers and parking functions to the space of diagonal harmonics. There are also deep connections to the geometry of the Hilbert scheme.

Since the works of Pak and Stanley [16], Athanasiadis and Linusson [4], it became clear that parking functions are tightly related to the combinatorics of the affine symmetric group. In particular, they provided two different bijections between the parking functions and the regions of Shi hyperplane arrangement. It has been remarked in [2, 6, 15] that the inverses of the affine permutations labeling the minimal alcoves in Shi regions belong to a certain simplex [D.sup.n+1.sub.n], which is isometric to the (n + 1)-dilated fundamental alcove. As a result, the alcoves in [D.sup.n+1.sub.n] can be labeled by parking functions in two different ways.

Many of the concepts above have "rational" counterparts corresponding to a coprime pair (m, n), for which the classical case is (n + 1, n). In [8] and [9] the first and the second authors proved that the rational Dyck paths label the affine cells in a certain algebraic variety, the compactified Jacobian of a plane curve singularity with one Puiseaux pair (m, n). This work was generalized by Hikita in [12] who proved that m/n parking functions naturally label the cells in a certain Springer fibre in the affine flag variety for the affine symmetric group [[??].sub.n]. As a consequence of this paper, we can use our construction to prove new formulas for the Poincare polynomials of certain affine Springer fibers relying on the work of [8] and [9].

The present paper is dedicated to the systematic study of the m/n parking functions in terms of the affine symmetric group [[??].sub.n]. We consider the set [[??].sup.m.sub.n] of all affine permutations in [[??].sub.n] with no inversions of height m and two maps A and PS from [[??].sup.m.sub.n] to the set of m/n parking functions P[F.sub.m/n]. When one composes PS with [A.sup.-1], one recovers the zeta map [zeta] of Haglund, which was used to give a combinatorial proof of the weak symmetry property of the q, t-Catalan numbers.


The authors would like to thank the American Institute of Mathematics for their hospitality, and D. Armstrong, F. Bergeron, S. Fishel, I. Pak, R. Stanley, V. Reiner, B. Rhoades, A. Varchenko, G. Warrington and N. Williams for useful discussions and suggestions. E. G. was partially supported by the grants RFBR-13-01-00755, NSh-4850.2012.1. M. V. was partially supported by the grant NSA MSP H98230-12-1-0232.

2 Tools and definitions

We start with a brief review of the definitions and basic results involving parking functions, affine permutations, and hyperplane arrangements, which will play the key role in our constructions.

2.1 Parking Functions

Definition 2.1 A function f: {1, ..., n} [right arrow] [Z.sub.[greater than or equal to]0] is called an m/n-parking function if the Young diagram with row lengths equal to f(1), ..., f(n) put in decreasing order, bottom to top, fits under the diagonal in an n x m rectangle. The set of such functions is denoted by P[F.sub.m/n].

We will often use the notation f = ([absolute value of f(1)f(2) ... f(n)]) for parking functions.

Example 2.2 Consider the function f: {1,2,3,4} [right arrow] [Z.sub.[greater than or equal to]0] given by f(1) = 2, f(2) = 0, f(3) = 4, and f(4) = 0 (i.e. f = ([absolute value of 2040])). The corresponding Young diagram fits under the diagonal in a 4 x 7 rectangle, but does not fit under the diagonal in a 4 x 5 rectangle. Thus, f [member of] P[F.sub.7/4] but f [not member of] P[F.sub.5/4] (see Figure 1).

Equivalently, a function f: {1, ..., n} [right arrow] [Z.sub.[greater than or equal to]0] belongs to P[F.sub.m/n] if and only if it satisfies

[for all]i [member of] {0, ..., n - 1}, #{k [member of] {1, ..., n} | f(k) [less than or equal to] [im/n]} [greater than or equal to] i + 1.

Let P: P[F.sub.m/n] [right arrow] [Y.sub.m,n] denote the natural map from the set of parking functions to the set [Y.sub.m,n] of Young diagrams that fit under diagonal in an n x m rectangle. To recover a parking function f [member of] P[F.sub.m/n] from the corresponding Young diagram P(f) one needs some extra information. Lengths of the rows of P(f) correspond to the values of f, but one needs also to assign the preimages to them. That is, one should label the rows of P(f) by integers 1,2, ..., n. Note that if P(f) has two rows of the same length, then the order of the corresponding labels does not matter. One should choose one of the possible orders. We choose the decreasing order (read from bottom to top).

Definition 2.3 Let [[??].sub.m,n] denote the set of couples (D,[tau]) of a Young diagram D [member of] [Y.sub.m,n] and a (finite) permutation [tau] [member of] [S.sub.n], such that if kth and (k + 1)th rows of D have the same length, then [tau](k + 1) < [tau](k). We will refer to [tau] as the row-labeling of D.

Note that [tau] [member of] [S.sub.n] is the permutation of maximal length such that f [omicron] [tau] is non- increasing.

Example 2.4 In Example 2.2, one has [tau] = [3,1,4,2], so f [omicron] [tau] = ([absolute value of 2040]) [omicron] [3,1,4,2] = ([absolute value of 4200]).

We get the following lemma:

Lemma 2.5 The set of m/n-parking functions P[F.sub.m/n] is in bijection with the set of labeled Young diagrams [[??].sub.m,n].

Remark 2.6 Note that for m = n + 1 the set P[F.sub.m/n] is exactly the set of classical parking functions PF, and for m = kn + 1 it is the set of k-parking functions P[F.sub.k] (e.g. [10]).

From now on we will assume that m and n are coprime, so there are no lattice points on the diagonal of n x m rectangle. By abuse of notation, we will call a non-decreasing parking function increasing. The number of increasing parking functions equals the generalized Catalan number [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The number of all parking functions #P[F.sub.m/n] equals [m.sup.n-1]. (See [4].)

2.2 Affine Permutations

Definition 2.7 The affine symmetric group [[??].sub.n] is generated by [s.sub.1], ..., [s.sub.n-1], [s.sub.0] subject to the relations




and let [H.sup.k.sub.ij] be the hyperplane {[bar.x] [member of] V|[x.sub.i] - [x.sub.j] = k} [subset] V. The hyperplane arrangement [[??].sub.n] = {[H.sup.k.sub.ij]: 0 < i < j [less than or equal to] n, k [member of] Z} is called the affine braid arrangement. The connected components of the complement to the affine braid arrangement are called alcoves. The group [[??].sub.n] acts on V with the generator [s.sub.i] acting by reflection in the hyperplane [H.sup.0.sub.i,i+1] for i > 0, and [s.sub.0] acting by reflection in the hyperplane [H.sup.1.sub.1,n]. The action is free and transitive on the set of alcoves, so that the map [omega] [??] [omega]([A.sub.0]), where [A.sub.0] := {[bar.x] [member of] V|[x.sub.1] > [x.sub.2] > ... > [x.sub.n] > [x.sub.1] - 1} is the fundamental alcove, gives a bijection between the group [[??].sub.n] and the set of alcoves.

Observe [H.sup.k.sub.i,j] = [H.sup.-k.sub.j,i], so we may always take i < j. It is convenient to extend our notation to allow subscripts in Z via [H.sup.k.sub.i+tn,j+tn] = [H.sup.k.sub.i,j] and [H.sup.k.sub.i,j] = [H.sup.k-1.sub.i,j-n]. In this way, we can uniquely write each hyperplane in [[??].sub.n] as [H.sup.0.sub.i,l] with 1 [less than or equal to] i [less than or equal to] n, i < l, l [member of] Z. Then we can define the height of the hyperplane [H.sup.0.sub.i,l] to be l - i. Observe, in this manner, the reflecting hyperplane of [s.sub.0] is [H.sup.1.sub.1,n] = [H.sup.0.sub.1,0] = [H.sup.0.sub.0,1] of height 1. Note that with this notation, the action of the group [[??].sub.n] on the hyperplanes [H.sup.k.sub.i,j] is given by [omega]([H.sup.k.sub.i,j]) = [H.sup.k.sub.[omega](i),[omega](j)].

There is another way to think about the affine symmetric group:

Definition 2.8 A bijection [omega]: Z [right arrow] Z is called an affine [S.sub.n]-permutation, if [omega](x + n) = [omega](x) + n for all x, and [[summation].sup.n.sub.i=1] [omega](i) = [n(n + 1)/2].

In this presentation the operation is composition and the generators [s.sub.1], ..., [s.sub.n-1], [s.sub.0] are given by


It is convenient to use list or window notation for [omega] [member of] [[??].sub.n] as the list [[omega](1), [omega](2), ..., [omega](n)]. Since [omega](x + n) = [omega](x) + n, this determines [omega]. The bijection between [[??].sub.n] and the set of alcoves can be made more explicit in the following way.

Lemma 2.9 Every alcove A contains exactly one point [([x.sub.1], ..., [x.sub.n]).sup.T] [member of] A in its interior such that the numbers [n + 1/2] - n[x.sub.1], ..., [n + 1/2] - n[x.sub.n] are all integers. Moreover, if [bar.x] [member of] [omega]([A.sub.0]) is such a point, then in the window notation one has

[[omega].sup.-1] = [[n + 1/2] - n[x.sub.1], ..., [n + 1/2] - n[x.sub.n]]. (1)

These points are called centroids of alcoves.

The minimal length left coset representatives [omega] [member of] [[??].sub.n]/[S.sub.n], also known as affine Grassmannian permutations, satisfy [omega](1) < [omega](2) < ... < [omega](n), so that their window notation is an increasing list of integers (summing to [n(n + 1)/2] and with distinct remainders mod n). Their inverses [[omega].sup.-1] are the minimal length right coset representatives and satisfy that the centroids of the alcoves [[omega].sup.-1] ([A.sub.0]) are precisely those whose coordinates are decreasing. That is to say, [[omega].sup.-1]([A.sub.0]) is in the dominant chamber {[bar.x] [member of] V|[x.sub.1] > [x.sub.2] > ... > [x.sub.n]}.

By a slight abuse of notation, we will refer to the set of minimal length left (right) coset representatives as [[??].sub.n]/[S.sub.n] (respectively [S.sub.n]\[[??].sub.n]).

2.3 Sommers region

Definition 2.10 Let w be an affine permutation. The set of its inversions is defined as

Inv([omega]) := {(i, j) [member of] Z x Z|1 [less than or equal to] i [less than or equal to] n, i < j, [omega](i) > [omega](j)}.

The length of a permutation w is then defined as l([omega]) = #Inv([omega]). This coincides with Coxeter length. We shall say the height of an inversion (i,j) is j - i. We will also use the notation [bar.Inv]([omega]) := {(i,j) [member of] Z x Z| i < j, [omega](i) > [omega](j)} for unnormalized inversions.

Geometrically, [omega] has an inversion of height m if and only if the alcove [[omega].sup.-1]([A.sub.0]) is separated from [A.sub.0] by a (corresponding) hyperplane of height m. More precisely, that hyperplane is [H.sup.0.sub.i,i+m] if the inversion is (i, i + m). The following definition will play the key role in our constructions:

Definition 2.11 An affine permutation [omega] [member of] [[??].sub.n] is called m-stable if for all x the inequality [omega](x + m) > [omega](x) holds, i.e. [omega] has no inversions of height m. The set of all m-stable affine permutations is denoted by [[??].sup.m.sub.n].

Definition 2.12 An affine permutation [omega] [member of] [[??].sub.n] is called m-restricted if [[omega].sup.-1] [member of] [[??].sup.m.sub.n]. We will denote the set of m-restricted permutations by [sup.m][[??].sub.n]. Note [omega] [member of] [sup.m][[??].sub.n] if and only if for all i < j, [omega](i) - [omega](j) [not equal to] m.

Lemma 2.9 implies an important corollary for the set [[??].sup.m.sub.n]:

Lemma 2.13 Let m = kn + r, where 0 < r < n. The set of alcoves {[omega]([A.sub.0]): [omega] [member of] [sup.m][[??].sub.n]} coincides with the set of alcoves that fit inside the region [D.sup.m.sub.n] [subset] V defined by the inequalities:

1. [x.sub.i] - [x.sub.i+r] [greater than or equal to] -k for 1 [less than or equal to] i [less than or equal to] n - r,

2. [x.sub.i+r-n] - [x.sub.i] [less than or equal to] k + 1 for n - r + 1 [less than or equal to] i [less than or equal to] n.

The simplex [D.sup.m.sub.n] was first defined in [5, 15] and so we call it the Sommers region. [D.sup.m.sub.n] plays the central role in our study. It is worth mentioning that the combinatorial structure of [D.sup.m.sub.n] has been recently investigated in [17], where the alcoves in it were labeled by certain sequences of numbers (but not parking functions). We plan to investigate the connections of our work to [17] in the future. It is known that [D.sup.m.sub.n] is isometric to the mth dilation of the fundamental alcove. This was proven for all types by Fan [5, Lemma 2.2] and Sommers [15, Theorem 5.7], based on an earlier unpublished observation of Lusztig.

3 Main Constructions

3.1 Bijection A: [[??].sup.m.sub.n] [right arrow] P[F.sub.m/n]

We define the map A: [[??].sup.m.sub.n] [right arrow] P[F.sub.m/n] by the following procedure. Given [omega] [member of] [[??].sup.m.sub.n], consider the set [[DELTA].sub.[omega]] := {i [member of] Z: [omega](i) > 0} [subset] Z and let [M.sub.[omega]] be its minimal element. Note that the set [[DELTA].sub.[omega]] is invariant under addition of m and n.

Consider the integer lattice [(Z).sup.2]. We prefer to think about it as of the set of square boxes, rather than the set of integer points. Consider the rectangle [R.sub.m,n] := {(x, y) [member of] [(Z).sup.2]|0 [less than or equal to] x < m, 0 [less than or equal to] y < n}. Let us label the boxes of the lattice according to the linear function

l(x, y) := (mn - m - n) + [M.sub.[omega]] - nx - my.

The function l(x,y) is chosen in such a way that a box is labeled by [M.sub.[omega]] if and only if its NE corner touches the line containing the NW-SE diagonal of the rectangle [R.sub.m,n], so l(x, y) [greater than or equal to] [M.sub.[omega]] if and only if the box (x, y) is below this line. The Young diagram [D.sub.[omega]] defined by

[D.sub.[omega]] := {(x, y) [member of] [R.sub.m,n]|l(x, y) [member of] [[DELTA].sub.[omega]]}.

satisfies [D.sub.w] [member of] [Y.sub.m,n].

The row-labeling [[tau].sub.[omega]] is given by [[tau].sub.[omega]](i) = [omega]([a.sub.i]), where [a.sub.i] is the label on the rightmost box of the ith row of [D.sub.[omega]] (if a row has length 0 we take the label on the box (-1, i - 1), just outside the rectangle in the same row). Note that if ith and (i + 1)th rows have the same length, then [a.sub.i+1] = [a.sub.i] - m and

[[tau].sub.[omega]] (i + 1) = [omega]([a.sub.i+1]) = [omega]([a.sub.i] - m) < [omega]([a.sub.i]) = [[tau].sub.[omega]](i).

Therefore, ([D.sub.[omega]], [[tau].sub.[omega]]) [member of] [[??].sub.m,n]. We define A([omega]) [member of] P[F.sub.m/n] to be the parking function corresponding to ([D.sub.[omega]], [[tau].sub.[omega]]).

Example 3.1 Let n = 4, m = 7. Consider the affine permutation [omega] = [0,6,3,1] = [s.sub.1][s.sub.0][s.sub.2][s.sub.3][s.sub.2]:


The inversion set is Inv([omega]) = {(2,3), (2,4), (2,5), (2,8), (3,4)}. Note that there are no inversions of height 7, so [omega] is 7-stable. Equivalently, [[omega].sup.-1] = [4, -2, 3, 5] is 7-restricted. The set [[DELTA].sub.[omega]] = {-2, 2, 3, 4, ...} is invariant under the addition of 4 and 7, and [M.sub.[omega]] = -2. The diagram [D.sub.[omega]] is shown in Figure 2. Note that the labels 3,4,5, and -2 on the rightmost boxes of the rows of [D.sub.[omega]] are the 4-generators of the set [[DELTA].sub.[omega]], i.e. they are the smallest numbers in [[DELTA].sub.[omega]] in the corresponding congruence classes mod4. It follows then that the corresponding values [omega](3), [omega](4), [omega](5), and [omega](-2) are a permutation of 1,2,3,4. Indeed, read bottom to top, ([omega](3), [omega](4), [omega](5), [omega](-2)) = (3,1,4,2). This defines the row-labeling [[tau].sub.[omega]] := [3,1,4,2]. Note that the last (top) two rows of the diagram have the same length 0. Therefore, the difference between the corresponding labels is 5 - (-2) = 7. The 7-stability condition then implies that [tau](3) = [omega](5) > [omega](-2) = [tau](4), which is exactly the required monotonicity condition on the labeling. Using the bijection from Lemma 2.5, one obtains the parking function [A.sub.[omega]] = ([absolute value of 2040]).

Alternatively, one can define the map A in a more compact, but less pictorial way:

Definition 3.2 Let [omega] [member of] [[??].sup.m.sub.n]. We define the corresponding parking function [A.sub.[omega]] as follows. Let [M.sub.[omega]] := min{i [member of] Z: [omega](i) > 0}. Given [alpha] [member of] {1, ..., n}, there is a unique way to express [[omega].sup.-1]([alpha]) - [M.sub.[omega]] as a linear combination rm - kn with the condition r [member of] {0, ..., n - 1}. Note that one automatically gets k [greater than or equal to] 0. Indeed, otherwise [alpha] = [omega]([M.sub.[omega]] + rm - kn) [greater than or equal to] [omega]([M.sub.[omega]]) - kn [greater than or equal to] -kn [greater than or equal to] n, which contradicts the assumption [alpha] [member of] {1, ..., n}. We set [A.sub.[omega]]([alpha]) := k.

Lemma 3.3 The two above definitions of the map A are equivalent.

Theorem 3.4 The map A: [[??].sup.m.sub.n] [right arrow] P[F.sub.m/n] is a bijection.

We call A the Anderson map, since if we restrict the domain to minimal length right coset representatives (which correspond to partitions called (m, n)-cores), and then project to increasing parking functions by sorting, the map agrees with one constructed by Anderson [1].

3.2 Map PS: [[??].sup.m.sub.n] [right arrow] P[F.sub.m/n]

Definition 3.5 Let [omega] [member of] [[??].sup.m.sub.n]. Then the map P[S.sub.[omega]]: {1, ..., n} [right arrow] Z is given by:

P[S.sub.[omega]]([alpha]) := #{[beta]|[beta] > [alpha], 0 < [[omega].sup.-1]([alpha]) - [[omega].sup.-1]([beta]) < m} = #{i|[omega](i) > [alpha], [[omega].sup.-1]([alpha]) - m < i < [[omega].sup.-1]([alpha])}.

In other words, P[S.sub.[omega]]([alpha]) is equal to the number of inversions (i,j) [member of] Inv([omega]) of height less than m and such that [omega](j) [equivalent to] [alpha] mod n.

Definition 3.6 Let SP: [sup.m][[??].sub.n] [right arrow] P[F.sub.m/n] be defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Observe S[P.sub.u](i) = #{j > i|0 < u(i) - u(j) < m}.

Example 3.7 Using [omega] = [0,6,3,1] as in Example 3.1, one gets P[S.sub.[omega]] = ([absolute value of 3011]).

Theorem 3.8 For any m-stable affine permutation [omega], the function P[S.sub.[omega]] is an mIn-parking function. Thus one gets a map PS: [[??].sup.m.sub.n] [right arrow] P[F.sub.m/n].

Conjecture 3.9 The map PS: [omega] [??] P[S.sub.[omega]] is a bijection between [[??].sup.m.sub.n] and P[F.sub.m/n].

In the special cases m = kn [+ or -] 1, we can prove that PS is a bijection.

It is convenient to extend the domains of the functions P[S.sub.[omega]] and S[P.sub.[omega]] to all integers by using exactly the same formula. Note that in this case P[S.sub.[omega]]([alpha] + n) = P[S.sub.[omega]]([alpha]). We have the following results, which should be considered as steps towards Conjecture 3.9:

Proposition 3.10 Let [omega] [member of] [sup.m][[??].sub.n] and let 1 [less than or equal to] i [less than or equal to] n, i < j.

1. [omega](i) < [omega](i + 1) [??] S[P.sub.[omega]](i) [less than or equal to] S[P.sub.[omega]](i + 1)

2. (i,j) [member of] Inv([omega]) [??] S[P.sub.[omega]] (i) > S[P.sub.[omega]](j)

Proposition 3.11 Let [omega] [member of] [sup.m][[??].sub.n].



As a corollary to this proposition, we see that SP is injective on {[omega] [member of] [sup.m][[??].sub.n]|(i, j) [member of] Inv([omega]) [??] [omega](i) - [omega](j) < m}. Another interpretation of Proposition 3.10 is that SP not only respects descents but also respects (weakly) increasing subsequences.

4 The cases m = kn [+ or -] 1 and the Extended Shi Arrangements

4.1 Extended Shi Arrangements and Pak-Stanley Labeling

Recall the set of k-parking functions P[F.sub.k] := P[F.sub.(kn+1)/n]. Recall the hyperplanes [H.sup.k.sub.ij] = {[bar.x] [member of] V|[x.sub.i] - [x.sub.j] = k} and the affine braid arrangement [[??].sub.n] = {[H.sup.k.sub.ij]|1 [less than or equal to] i, j [less than or equal to] n, k [member of] Z}. The extended Shi arrangement, or k-Shi arrangement [14, 16], is defined as a subarrangement of the affine braid arrangement:

Definition 4.1 The hyperplane arrangement


is called the k-Shi arrangement. The connected components of the complement to [Sh.sup.k.sub.n] are called k-Shi regions. The set of k-Shi regions is denoted [Reg.sup.k.sub.n] .

The hyperplane [H.sup.l.sub.ij] divides V into two half-spaces. Let [H.sup.l,[??].sub.ij] denote the half-space that contains [A.sub.0] and [H.sup.l,[??].sub.ij] denote the complementary half-space. Note that [H.sup.l.sub.ij] separates [omega]([A.sub.0]) from [A.sub.0] iff [omega]([A.sub.0]) [subset or equal to] [H.sup.l,[??].sub.ij] iff (i, j - ln) or (j, i + ln) [member of] Inv([[omega].sup.-1]) (when taking the convention i, j [member of] {1, ..., n}).

Definition 4.2 The Pak-Stanley labeling is the map [lambda]: [Reg.sup.k.sub.n] [right arrow] P[F.sub.k], R [??] [[lambda].sub.R] defined by the formula


In other words, one labels the fundamental alcove [A.sub.0] by the parking function f = ([absolute value of 0 ... 0]), and then as one crosses the hyperplane [H.sup.l.sub.ij] in the positive direction (i.e. getting further away from [A.sub.0]), one adds 1 to f(j) if l [less than or equal to] 0 and adds 1 to f(i) if l > 0.

Remark 4.3 One can rewrite this definition as follows:

[[lambda].sub.R](a) = #{[H.sup.0.sub.ij] [member of] [Sh.sup.k.sub.n]|R [subset or equal to] [H.sup.0,[??].sub.ij], a = i < j} = #{[H.sup.0.sub.aa+t]|R [subset or equal to] [H.sup.0,[??].sub.aa+t], 0 < t < kn, t [??] 0 mod n}.

We illustrate the Pak-Stanley labeling for n = 3, k = 1 (m = 4) in Figure 3.

Theorem 4.4 ([16]) The map [lambda]: [Reg.sup.k.sub.n] [right arrow] P[F.sub.k] is a bijection.

4.2 Relation Between Sommers Regions and Extended Shi Arrangements for m = kn [+ or -] 1

Consider the case m = kn + 1. One can show that each region of an extended Shi arrangement contains a unique minimal alcove (i.e. an alcove with the least number of hyperplanes [H.sup.k.sub.ij] separating it from the fundamental alcove [A.sub.0]).

Theorem 4.5 ([6]) An alcove [omega]([A.sub.0]) is the minimal alcove of a k-Shi region if and only if [[omega].sup.-1] ([A.sub.0]) [subset] [].

See Figure 4. Theorem 4.5 and Lemma 2.13 imply a bijection alc: [[??]] [right arrow] [Reg.sup.k.sub.n].

Theorem 4.6 One has [lambda] [omicron] alc = PS in this case. In particular, PS is a bijection for m = kn + 1.

The case m = kn-1 is treated similarly. The main difference is that instead of the set of all k-Shi regions [Reg.sup.k.sub.n] one should consider the set of bounded k-Shi regions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. One can show that every bounded k-Shi region contains exactly one maximal alcove.

Theorem 4.7 ([7]) An alcove [omega]([A.sub.0]) is the maximal alcove of a bounded k-Shi region if and only if [[omega].sup.-1]([A.sub.0]) [subset] [].

As above, we use Lemma 2.13 and Theorem 4.7 to obtain the bijection [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We prove the following theorem:

Theorem 4.8 The image of the subset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is exactly P[F.sub.(kn-1)/n] [subset] P[F.sub.(kn+1)/n] under the Pak-Stanley labeling. Furthermore, one gets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in this case. In particular, PS is a bijection for m = kn - 1.

5 Minimal Length Representatives and the Zeta Map

Definition 5.1 Let [Mod.sub.m,n] be the set of subsets [DELTA] [subset] [Z.sub.[greater than or equal to]0], such that [DELTA] + m [subset] [DELTA], [DELTA] + n [subset] [DELTA], and min([DELTA]) = 0. A number a is called an n-generator of [DELTA], if a [member of] [DELTA] and a - n [not member of] [DELTA]. Every [DELTA] [member of] [Mod.sub.m,n] has exactly n distinct n-generators.

In [8, 9] such subsets were called 0-normalized semimodules over the semigroup generated by m and n. We will simply call them m, n-invariant subsets.

There is a natural map R: [[??].sup.m.sub.n] [right arrow] [Mod.sub.m,n] given by [omega] [??] [[DELTA].sub.[omega]] - min([[DELTA].sub.[omega]]) (here, as before, [[DELTA].sub.[omega]] = {i [member of] Z: [omega](i) > 0}). Let [[OMEGA].sup.m.sub.n] be the set of m-stable minimal length right coset representatives of [S.sub.n]\[[??].sub.n]. In other words,

[[OMEGA].sup.m.sub.n] := {[omega] [member of] [[??].sup.m.sub.n]|[[omega].sup.-1](1) < ... < [[omega].sup.-1](n)}. (2)

One can check that the restriction [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a bijection. The integers [[omega].sup.-1](1), ..., [[omega].sup.-1](n) are the n-generators of [[DELTA].sub.[omega]], and since [omega] [member of] [[OMEGA].sup.m.sub.n] we have [[omega].sup.-1](1) < ... < [[omega].sup.-1](n), so one can uniquely recover [omega] from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the restriction.

Recall that [Y.sub.m,n] is the set of Young diagrams that fit under diagonal in an n x m rectangle and P: P[F.sub.m/n] [right arrow] [Y.sub.m,n] is the natural map. In [8, 9] the first two named authors constructed two maps D: [Mod.sub.m,n] [right arrow] [Y.sub.m,n] and G: [Mod.sub.m,n] [right arrow] [Y.sub.m,n], proved that D is a bijection, and related the two maps to the theory of q, t-Catalan numbers in the following way. In the case m = n + 1 one gets


where [delta] = [n(n-1)/2] and [c.sub.n](q,t) is the Garsia-Haiman q,t-Catalan polynomial. It is known that these polynomials are symmetric [c.sub.n](q, t) = [c.sub.n](t, q), although the proof is highly non-combinatorial and uses the machinery of Hilbert schemes, developed by Haiman. Finding a combinatorial proof of the symmetry of the q, t-Catalan polynomials remains an open problem.

The above consideration motivates the rational slope generalization of the q, t-Catalan numbers:


where [delta] = [(m-1)(n-1)/2] is the total number of boxes below the diagonal in an n x m rectangle. The symmetry of these polynomials remains an open problem beyond the classical case m = n + 1 and the cases min(m, n) [less than or equal to] 4 (see [9] for min(m,n) [less than or equal to] 3 and [13] for min(m,n) = 4). It was also shown in [8] that the composition G [omicron] [D.sup.-1]: [Y.sub.m,n] [right arrow] [Y.sub.m,n] generalizes Haglund's zeta map exchanging the pairs of statistics (area, dinv) and (bounce, area) on Dyck paths. It was conjectured that the map G, and therefore, the generalized Haglund's zeta, are also bijections. This would imply a weaker symmetry property [c.sub.m,n](q, 1) = [c.sub.m,n](1, q). In [9] the bijectivity of G was proved for m = kn [+ or -] 1. For more details on this work we refer the reader to [8, 9].

Let * denote the involution on [[??].sub.n]: [[omega].sup.*](x) = 1 - [omega](1 - x).

Lemma 5.2 The map * preserves the set [[??].sup.m.sub.n] and the set [[OMEGA].sup.m.sub.n] The map [bar.*]: (i,j) [right arrow] (1 - j, 1 - i) provides a height preserving bijection from {(i,j) | i < j, [omega](i) > [omega](j)} to {(i,j) | i < j, [[omega].sup.*](i) > [[omega].sup.*](j)}.

The following Theorem shows that our constructions are direct generalizations of those of [8, 9]:

Theorem 5.3 One has the following identities:

1. P [omicron] A [omicron] [[??].sup.-1] = D,

2. P [omicron] PS [omicron] * [omicron] [[??].sup.-1] = G.

The involution * could have been avoided in Theorem 5.3 by adjusting the definition of the map PS. However, in that case one would have to use * to match the map PS for m = kn + 1 with the Pak-Stanley labeling (see Section 4).

The composition PS [omicron] [A.sup.-1]: [PF.sub.m/n] [right arrow] [PF.sub.m/n] should be thought of as a rational slope parking function generalization of the Haglund zeta map [zeta]. Note that its bijectivity remains conjectural beyond cases m = kn [+ or -] 1, which follows immediately from Theorems 4.6 and 4.8.

6 Some examples for m [not equal to]] kn [+ or -] 1

In this section we discuss some examples for which m [not equal to] kn [+ or -] 1.

Example 6.1 There are 81 = [3.sup.4] 3/5-parking functions. The [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] increasing parking functions are {[absolute value of 00000]), ([absolute value of 00001]), ([absolute value of 00002]), ([absolute value of 00011]), ([absolute value of 00012]), ([absolute value of 00111]), ([absolute value of 00112)]. Grouping them into the [S.sub.5]-orbits {f [omicron] w | [omega] [member of] [S.sub.5]} yields 81 = 1 + 5 + 5 + 10 + 20 + 10 + 30. There are 7 vectors in [Z.sup.5] [intersection] V [intersection] [D.sup.3.sub.5]. Their transposes are:

(0,0,0,0,0), (1,0,0,0,-1), (0,1,0,0,-1), (1,0,0,-1,0), (0,0,1,-1,0), (0,1,-1,0,0), (1,-1,0,1,-1)

The 30 parking functions in the [S.sub.5]-orbit of ([absolute value of 00112]) correspond under the map A to the 30 permutations in [S.sub.5] [intersection] [sup.3][[??].sub.5] which are those in the support of the shuffle 14 [??] 25 [??] 3 (that is to say, the intersection of the Sommers region with the orbit of the identity permutation).

On the other hand, the parking function ([absolute value of 00000]) = A([[omega].sub.m]) corresponds under A to the affine permutation [[omega].sub.m] = [-3,0,3,6,9] [member of] [sup.3][[??].sub.5]. Anything else in its right [S.sub.5]-orbit lies outside the Sommers region.

Despite the fact many of the above theorems and constructions use [[??].sup.m.sub.n], it is more uniform to study the set {u[A.sub.0] | [omega] [member of] [sup.m][[??].sub.n]} and SP than {[omega][A.sub.0] | [omega] [member of] [[??].sup.m.sub.n]} and PS. One reason is that while the Sommers region can always be defined for gcd(m, n) = 1, a hyperplane arrangement that is the correct analogue of the Shi arrangement cannot. Consider the following example.

Example 6.2. In the case (n, m) = (5, 3) it is impossible to find a set of hyperplanes that separate the alcoves {[omega][A.sub.0] | [omega] [member of] [[??].sup.m.sub.n]} and has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] dominant regions, i.e. that there are exactly 7 dominant regions with a unique [omega][A.sub.0] in each. In other words, the notion of [Reg.sup.k.sub.n] does not extend well when m [not equal to] kn [+ or -] 1.

Indeed, there are 7 dominant regions corresponding to the 3-restricted affine permutations [omega] [member of] [sup.3][[??].sub.5] [intersection] [[??].sub.5]/[S.sub.5]. The hyperplanes [H.sup.0.sub.4,6], [H.sup.0.sub.5,6] and [H.sup.0.sub.5,7] separate [02346] from other 3-restricted permutations. To separate [-21457] from [-11258], one must add either [H.sup.0.sub.3,6] or [H.sup.0.sub.5,8] to the arrangement, but this would leave either of the non-3-restricted permutations [-22456] or [01248] in a region with no 3-restricted permutations. Therefore any extension of the classical braid arrangement for [S.sub.5] would either have a region with two 3-restricted permutations or a region with none of them.


[1] J. Anderson. Partitions which are simultaneously [t.sub.1]- and [t.sub.2]-core. Discrete Math. 248 (2002), no. 1-3, 237-243.

[2] D. Armstrong. Hyperplane arrangements and diagonal harmonics. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 39-50, Discrete Math. Theor. Comput. Sci. Proc., AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011.

[3] D. Armstrong, B. Rhoades. The Shi arrangement and the Ish arrangement. Trans. Amer. Math. Soc. 364 (2012), no. 3, 1509-1528.

[4] C. Athanasiadis, S. Linusson. A simple bijection for the regions of the Shi arrangement of hyperplanes. Discrete Math. 204 (1999), no. 1-3, 27-39.

[5] C. K. Fan. Euler characteristic of certain affine flag varieties. Transform. Groups 1 (1996), no. 1-2, 35-39.

[6] S. Fishel, M. Vazirani. A bijection between dominant Shi regions and core partitions. European J. Combin. 31 (2010), no. 8, 2087-2101.

[7] S. Fishel, M. Vazirani. A bijection between (bounded) dominant Shi regions and core partitions, DMTCS Proceedings, 283-294, 2010.

[8] E. Gorsky, M. Mazin. Compactified Jacobians and q, t-Catalan Numbers, I. Journal of Combinatorial Theory, Series A, 120 (2013) 49-63.

[9] E. Gorsky, M. Mazin. Compactified Jacobians and q, t-Catalan Numbers, II. Journal of Algebraic Combinatorics, 39 (2014), no. 1, 153-186.

[10] J. Haglund. The q, t-Catalan Numbers and the Space of Diagonal Harmonics: With an Appendix on the Combinatorics of Macdonald Polynomials. AMS University lecture series, 2008.

[11] J. Haglund, M. Haiman, N. Loehr, J. Remmel, A. Ulyanov. A combinatorial formula for the character of the diagonal coinvariants. Duke Math. J., 126 (2005), 195-232.

[12] T. Hikita. Affine Springer fibers of type A and combinatorics of diagonal coinvariants. arXiv:1203.5878

[13] K. Lee, L. Li, N. Loehr. Combinatorics of certain higher q, t-Catalan polynomials: chains, joint symmetry, and the Garsia-Haiman formula. arXiv:1211.2191

[14] J.-Y. Shi. The Kazhdan-Lusztig cells in certain affine Weyl groups. Lecture Notes in Mathematics, no. 1179, Springer-Verlag, Berlin/Heidelberg/New York (1986).

[15] E. Sommers. B-stable ideals in the nilradical of a Borel subalgebra. Canad. Math. Bull., 48(3):460-472, 2005.

[16] R. P. Stanley. Hyperplane arrangements, parking functions and tree inversions. Mathematical essays in honor of Gian-Carlo Rota (Cambridge, MA, 1996), 359-375, Progr. Math., 161, Birkhauser Boston, Boston, MA, 1998.

[17] H. Thomas, N. Williams. Cyclic symmetry of the scaled simplex. J. Algebraic Combin. 39 (2014), no. 2, 225-246.

Eugene Gorsky (1) Mikhail Mazin (2) Monica Vazirani (3)

(1) Columbia University, New York, New York, USA

(2) Kansas State University, Manhattan, Kansas, USA

(3) University of California at Davis, Davis, California, USA
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Gorsky, Eugene; Mazin, Mikhail; Vazirani, Monica
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2014
Previous Article:A Chevalley-Monk and Giambelli's formula for Peterson varieties of all Lie types.
Next Article:Honeycombs from Hermitian matrix pairs, with interpretations of path operators and S [L.sub.n] crystals.

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters