A bijection between all Shi regions and core partitions

The $m$-Shi arrangement is a hyperplane arrangement related to a number of areas of study in combinatorics and representation theory, including parking functions and $n$-core partitions. There are multiple bijections between the set of all regions of the arrangement and parking functions ([4], [22]), and the Athanasiadis-Linusson bijection in particular is interesting in part because the natural symmetric group action on parking functions reflects the geometry of the Shi arrangment.

In [11] (resp. [12]), Fishel and Vazirani showed a bijection between the dominant (resp. bounded dominant) chambers of the $m$-Shi arrangement and partitions which are simultaneously $n$-core and $(mn+1)$-core (resp. $(mn-1)$-core). However, this bijection does not extend outside the dominant chamber. The goal of this paper is to extend the results of Fishel-Vazirani by giving a bijection between the set of all chambers of the $m$-Shi arrangement and a certain subset of $n$-core partitions. Moreover, like the original, it adapts in a natural way to a bijection on the bounded chambers of the arrangement. In addition, it has the same $S_{n}$-structure as parking functions in the Athanasiadis-Linusson bijection. Thus we close the loop from the Fishel-Vazirani result to the more classical indexings of Shi regions, and bring the $S_{n}$ action to the partition picture. As part of the proof, we will establish an independently interesting characterization of the minimal chambers that occur in the $S_{n}$-orbit of a minimal chamber of the $m$-Shi arrangement.

We being with a brief survey of known results on the relationship between the $m$-Shi arrangement, $n$-core partitions, and the affine symmetric group. Our notation in this section closely models that of [11], which contains several results which will be important in what follows.

We now summarize some standard facts about partitions - see [17] for example, for details. A partition $\lambda$ of a positive integer $n$ is an infinite sequence $(\lambda_{1},\lambda_{2},\cdots)$ of non-negative integers, written in non-increasing order, that sum to $n$. For example, $(5,4,2,1,0,0,\cdots)$ and $(10,1,1,0,0,\cdots)$ are partitions of 12. We will usually write a partition as a finite list consisting only of the non-zero entries of $\lambda$. We will also typically identify a partition with its Young diagram - a configuration of boxes arranged in a grid, where the first row has $\lambda_{1}$ boxes, the second has $\lambda_{2}$ boxes, etc.

The boxes in $\lambda$ will be referred to by their coordinates, so that box $(i,j)$ is in the $j$th row and $i$th column, counting from the top and left sides of the diagram. We say that a box $b$ in a Young diagram $\lambda$ is removable for $\lambda$ if it is in $\lambda$, but removing it from $\lambda$ still yields a valid Young diagram. We say that a box $b$ is addable for $\lambda$ if it is not in $\lambda$, but adding it to $\lambda$ would still yield a valid Young diagram. Each box in the grid is assigned a content. Specifically, the box in row $j$ and column $i$ has content $i-j$.

Each box in a Young diagram also has associated to it a hook length, defined as the the number of boxes directly to the right of the box in its row plus the number of boxes directly below the box in its column, plus 1.

If a given box $b$ has hook length $s$, then there will be a connected chain of boxes along the lower-right edge of the Young diagram, starting at the end of the row containing $b$, and ending at the bottom of the column containing $b$, that has exactly $s$ boxes.

This chain of boxes is the rim hook associated to $b$. Removing the rim hook associated to a given box will yield a valid Young diagram. If we repeatedly remove rim hooks of length $n$ from a Young diagram $\lambda$ until none remain, the result will be independent of the order in which the rim hooks are removed. In this case, we call the resulting partition $\lambda^{\prime}$ the $n$-core of $\lambda$. If a Young diagram $\lambda$ has no hook lengths equal to $n$, we say that $\lambda$ is $n$-core, since the $n$-core of $\lambda$ is $\lambda$ itself. A partition $\lambda$ is $n$-core if and only if none of its hook lengths are divisible by $n$. We say that a partition $\lambda$ is $(n,t)$-core if it is simultaneously $n$-core and $t$-core.

In [18], Lascoux described a way for $\widetilde{S}_{n}$ to act on Young diagrams of $n$-core partitions by adding or removing boxes of a given content. Specifically, if $\lambda$ is a partition, then it cannot have both addable and removable boxes with content congruent to $i$ mod $n$. (Due to the importance of this action, in our treatment of $n$-cores, we will always reduce the contents of boxes mod $n$.) Then $s_{i}$ acts on $\lambda$ by

This is the description of this action originally given in [18], although [11] has more of the details worked out. We will refer to this as the level 1 action, to contrast the level $t$ action below.

There are a number of combinatorial indexings of $n$-core partitions that we will move between often in this paper. We will begin by introducing all of these indexings and a description of the necessary actions of $\widetilde{S}_{n}$ on each one.

Balanced $n$-abaci The first combinatorial indexing of partitions which is particularly useful for $n$-cores is the notion of an $n$-abacus ([17] is a standard reference). Imagine the integers arranged in an infinite grid containing $n$ columns, marked with the numbers $0,1,2,\cdots n-1$. We label the rows by integers, so that row 0 contains $0,1,2,\cdots n-1$, row 1 contains $n,n+1,\ldots 2n-1$, row -1 contains $-n,-n+1,\ldots-1$, etc. An abacus diagram is merely a set of integers whose complement is bounded below, which we draw on the infinite grid by circling each number in the set. The columns of this diagram are called the runners of the abacus, and the circled numbers are called beads.

From a partition $\lambda$, we can obtain a particular abacus diagram which we will call the positive $n$-abacus of $\lambda$. The positive $n$-abacus of a partition $\lambda$ is the diagram obtained from this grid by circling each number which is the hook length of a box in the first column of the Young diagram of $\lambda$, as well as all the negative integers. Then a partition is $n$-core if and only its positive $n$-abacus has no positive beads on the 0 runner, and for each $i$ from $1$ to $n-1$, if runner $i$ has any positive beads, they are in positions $i,i+n,i+2n,\ldots i+kn$ for some nonnegative integer $k$. In other words, the beads on the abacus must be pushed as far up the runners as possible, with no positive beads on the 0 runner.

We say that two abacus diagrams are equivalent to each other if one can be obtained from the other by adding a constant to each bead in the diagram. Any abacus diagram that is equivalent to the positive $n$-abacus of $\lambda$ will be referred to as an $n$-abacus for $\lambda$.

We define the balance number of an abacus diagram for an $n$-core $\lambda$ to be the sum over the runners of the diagram of the row number of the first non-circled number on that runner, and say that a diagram is balanced if its balance number is 0.

Then every $n$-core partition has an abacus diagram equivalent to a unique balanced abacus diagram, which we call the balanced $n$-abacus of $\lambda$. This correspondence gives a bijection between balanced $n$-abacus diagrams meeting the “flushness” property described above and $n$-core partitions. (Note the positive part of the 0 runner may no longer be empty in the balanced abacus.) The balanced $n$-abacus is particularly useful because the action of $\widetilde{S}_{n}$ on the set of balanced $n$-abaci is easily described. Given a balanced $n$-abacus $X$ for $\lambda$, we define $w_{i}\cdot X$ to be $X$ with runners $i-1$ and $i$ swapped if $1\leq i\leq n-1$, and $w_{0}\cdot X$ to be the diagram obtained from $X$ by swapping runners $0$ and $n-1$, and then adding one bead to runner 0 and removing the last bead from runner $n-1$. The result will be the balanced abacus of an $n$-core partition, and [5] shows that this action is equivalent to the action on $n$-core partitions described above.

$n$-vectors Because of the “flushness” condition, the balanced $n$-abacus of an $n$-core partition is completely determined by the row number of the first non-circled bead on each runner. We can encode this as a vector with $n$ components, the $i$th entry of which is the row number of the first non-circled number on that runner. This is the ‘$n$-vector’ construction of Garvan, Kim, and Stanton ([14]). Since the abacus diagram is balanced, the entries of the resulting vector will sum to 0. Thus this correspondence gives a bijection between $n$-core partitions and $n$-dimensional vectors with integer entries that sum to zero. In [5] it is shown that this is an $\widetilde{S}_{n}$-equivariant bijection between $n$-core partitions and $Q$.

Moreover, [11] shows that this map induces a bijection between the set of partitions which are $(n,mn+1)$-core and the dominant $m$-minimal alcoves. Specifically, if $\lambda$ is an $(n,mn+1)$-core partition equal to $w^{-1}\cdot\emptyset$, where $w\in\widetilde{S}_{n}/G$, then $wA_{0}$ is an $m$-minimal alcove.

$n$-sets and $n$-windows Consider the $n$-vector $v=(a_{1},\ldots,a_{n})$ of an $n$-core partition $\lambda$, and let $S(\lambda)=\{na_{1},na_{2}+1,\ldots,na_{n}+n-1\}$. Since $v$ encodes the rows of the first non-circled beads on each runner of the abacus, the (unique) element of $S(\lambda)$ that is congruent to $i$ mod $n$ is the label of the first non-circled bead on runner $i$. Also, since $\sum a_{i}=0$, we notice that the sum of the elements of $S(\lambda)$ is $\binom{n}{2}$. The tuple $S(\lambda)$ is called the $n$-set of $\lambda$, and the resulting correspondence is a bijection between transversals of $\mathbb{Z}/n\mathbb{Z}$ with sum equal to $\binom{n}{2}$ and $n$-core partitions. Since $\widetilde{S}_{n}$ acts on $\mathbb{Z}$, it also acts on $n$-sets by acting on each element of the set. It is routine to check that the action on the $n$-set of a partition corresponds to the action on its abacus.

We will use $S(\lambda)_{i}$ to denote the element of $S(\lambda)$ which is congruent to $i$ mod $n$. Finally, we let $X(\lambda)$ be the $n$-tuple consisting of the elements of $S(\lambda)$ sorted in increasing order, which we call the $n$-window for $\lambda$. Similarly to above, we will use $X(\lambda)_{i}$ to denote the $i$th entry of $X(\lambda)$, i.e. the $i$th smallest entry in $S(\lambda)$. Then if $\lambda=w^{-1}\emptyset$ where $w\in\widetilde{S}_{n}/G$, we have that $X(\lambda)$ is the $n$-window of $w^{-1}$. We note that $n$-windows give yet another parametrization for $n$-cores.

We turn now to Fayers’ “level $t$” action of $\widetilde{S}_{n}$ on $\mathbb{Z}$. Specifically, in [9] and [10], for any $t$ relatively prime to $n$ (which we assume throughout), Fayers defined an action which we denote as $\ast_{t}$:

where $n\circ t=\frac{1}{2}(n-1)(t-1)$. We will not use this precise action, but we restate it here to point out why Fayers’ results still apply in our case. Instead, we focus on two variants of this action which are specific to the case $t\equiv\pm 1$ mod $n$, denoted $\cdot_{t}$. First, if $t=mn+1$, we define:

Secondly, if $t=mn-1$, then we define:

We use these particular definitions because in either case, the level $t$ action of $s_{i}$ will swap the $i-1$ and $i$ congruence classes setwise, by shifting by $t$ in the appropriate direction. A similar definition could be given done for any value of $t$ relatively prime to $n$, but the choice of which congruence classes to swap may start to matter, and it is unclear if such an action has a direct application. However, in our case, tailoring the level $mn+1$ and $mn-1$ actions in this way will let us give a consistent description of both of our bijections. (Note that we also have the nice property that the level 1 action is the usual action of $\widetilde{S}_{n}$, which we will denote as $\cdot_{1}$ from now on. )

Now, for $t=mn+1$, the actions $\ast_{t}$ and $\cdot_{t}$ differ only by an index shift by $n\circ t$, an automorphism of $\widetilde{S}_{n}$. Similarly, for $t=mn-1$, the actions differ by shifting the index by $n\circ t$ and negating (mod $n$). Thus, the orbit of any integer or set of integers will be the same under either $\ast_{t}$ or $\cdot_{t}$, meaning several important results from [9] still hold. (We will refer to simply “the orbit of the level $t$ action”, since it is the same regardless of whether we look at $\cdot_{t}$ or $\ast_{t}$. For results specific to $t=mn\pm 1$, we will specify the value of $t$.) The proofs of the other results we need from [9] are virtually unchanged, and we summarize all those results here.

The level $t$ action is important for us in the way that it acts on $n$-windows, $n$-cores, and their $n$-sets. In [9], Fayers described $\ast_{t}$ acting on $n$-cores, which operates in terms of adding or removing rim hooks of legnth $t$ with a particular pattern of contents - a direct generalization of Lascoux’s $\widetilde{S}_{n}$ action. On the level of $n$-sets, the level $t$ action on $\mathbb{Z}$ can be applied directly to sets of integers as well. Fayers ([9]) shows that if $\lambda$ is an $n$-core, then for any $w\in\widetilde{S}_{n}$, $w\ast_{t}S(\lambda)$ is the $n$-set of another $n$-core partition. Now, as in [10] we let $C_{n}$ be the set of all $n$-cores, and define $C_{n}^{(N)}$ to be the set of all $n$-cores $\lambda$ satisfying $|x-y|<nN$ for all $x,y\in S(\lambda)$. Fayers ([10], Lemma 3.16) shows that each $(s,t)$ core is an element of $C_{n}^{(t)}$. We also give an equivalence relation $\equiv_{N}$ on $n$-cores where $\lambda_{1}\equiv_{N}\lambda_{2}$ if there is a bijection $\phi:S(\lambda_{1})\rightarrow S(\lambda_{2})$ with $\phi(x)\equiv x$ mod $nN$ for all $x\in S(\lambda_{1})$.

We should note here that $C_{n}^{(mn+1)}$ has essentially already appeared as an indexing set for chambers of the Shi arrangement. The group $\mathbb{Z}^{n}_{n+1}$ of $n$-tuples of integers mod $n+1$ has a subgroup $H$ of order $n+1$ generated by $(1,1,\ldots,1)$, so the quotient $\mathbb{Z}^{n}_{n+1}/H$ has $(n+1)^{n-1}$ elements. (This set appears in [2], [4], and [23], among many others.) But each coset has a unique representative with a 0 in the first entry, and $(0,a_{1},\ldots a_{n-1})$ can be associated to the positive abacus with $a_{i}$ (flush) beads on the runner labeled $i$. If all the $a_{i}$ are less than $n+1$, then that abacus represents a partition in $C_{n}^{(n+1)}$. These cosets also each contain a single representative that describes a parking function, and the Athanasiadis-Linusson bijection (though not the Pak-Stanley) from regions to parking functions is $S_{n}$-equivariant with the normal permutation action on $\mathbb{Z}^{n}_{n+1}/H$. Interestingly, while the partition indexing of dominant Shi regions feels very natural because of the affine symmetric group action, the abaci associated to the partitions do not match up well to the obvious $S_{n}$ action on $\mathbb{Z}^{n}_{n+1}/H$. As we will see, our level $t$ action on $C_{n}^{(mn+1)}$ is an appropriate substitute.

For the level $t$ action, we have:

These lemmata together mean in particular that the level $mn\pm 1$ actions are well-defined on the sets $C_{n}^{(mn\pm 1)}$, which have size $(mn\pm 1)^{n-1}$. These are precisely the number of regions and bounded regions in the $m$-Shi arrangement. Our next goal is to understand the orbits of this action.

Proof. We claim that $s_{0}$ acts on $C_{n}^{(t)}$ in the same way as $s_{\theta}$ does. Since the action of $\widetilde{S}_{n}$ on $\mathbb{Z}$ is completely determined by its action on a set of congruence class representatives mod $n$, we look at the set $Y=\{0,t,2t,\ldots(n-1)t\}$ if $t=mn+1$ and $Y=\{0,-t,-2t,\ldots-(n-1)t\}$ for $t=mn-1$. Then for $1\leq i\leq n-1$, the action of $s_{i}$ switches the entries of $Y$ congruent to $i-1$ and $i$ mod $n$, and leaves the other elements of $Y$ fixed, so that the action of $s_{\theta}$ on $Y$ switches the elements congruent to 0 and $(n-1)$ mod $n$, and leaves the other elements fixed. But by the same token, for $t=mn+1$, $s_{0}\cdot_{t}0=-t\equiv(n-1)t$ mod $nt$, and $s_{0}\cdot_{t}(n-1)t=nt\equiv 0$ mod $nt$, while $s_{0}$ fixes the other elements of $Y$. Similar statements hold for $t=mn-1$, so that, mod $nt$, $s_{0}$ and $s_{\theta}$ have the same level $t$ action on $\mathbb{Z}$, so they act the same way on the equivalence classes under $\sim_{nt}$. $\square$

As a result of this lemma, from this point on, we can focus on the level $t$ action of $G$ on $C_{n}^{(t)}$. To make notation easier, we let $w_{i}=s_{i}$ for $1\leq i\leq n-1$, and let $w_{0}=s_{\theta}$. Now, following the proof of ([10], Lemma 3.10), we describe the stabilizer of the $G$-action on $C_{n}^{(mn+1)}$.

Proof. We prove the case $t=mn+1$ - the other case is similar. If $S(\lambda)_{i}-S(\lambda)_{i-1}=t$, then $w_{i}\cdot_{t}S(\lambda)_{i}=S(\lambda)_{i-1}$ and $w_{i}\cdot_{t}S(\lambda)_{i-1}=S(\lambda)_{i}$, but $w_{i}$ fixes the other elements of $S(\lambda)$, so that $w_{i}\cdot_{t}\lambda=\lambda$.

Now, let $w\in G$ and assume that $w\cdot_{t}\lambda=\lambda$. Since $\lambda$ is a $t$-core, if the abacus for $\lambda$ contains circled beads at $a$ and $a+kt$ for some positive $k$, then the beads $a+t,a+2t,\ldots,a+(k-1)t$ are also circled. The same must be true of the balanced abacus for $\lambda$, so that if $a$ and $a+kt$ are elements of $S(\lambda)$, then so are $a+t,a+2t,\ldots,a+(k-1)t$. Since $t\equiv 1$ mod $n$, we may assume the elements of $S(\lambda)$ lying in a single mod $t$ congruence class are exactly $S(\lambda)_{i}=a$ through $S(\lambda)_{i+k}=a+(k-1)t$. To fix $S(\lambda)$ setwise, the level $t$ action of $w$ must permute the set $\{S(\lambda)_{i},S(\lambda)_{i+1},\ldots,S(\lambda)_{i+k}\}$. But the permutations of this set are generated by $w_{i+1},w_{i+2},\ldots,w_{i+k}$. Since the different mod $t$ congruence classes correspond to disjoint cycles in $S_{n}$, the result follows. ∎

Of course, the orbit of an $(s,t)$-core $\lambda$ in $C_{n}^{(mn\pm 1)}$ is in bijection with the cosets of its stablizer. This (along with Lemma 9 below) completes the information we need about the partition side of our main bijection.

While $n$-sets contain all the information we need about $n$-core partitions, $n$-windows corresponding to alcoves will also be important for us since the ordering of the elements of the window captures the data about the labels of the floors and ceilings of an alcove, as well as the actual hyperplanes that contain those floors and ceilings. For a minimal length coset representative $w$, the permutation $\sigma=f_{n}(w)$ contains the necessary information that links all this data.

To understand the significance of $\sigma$, let $\lambda=w^{-1}\emptyset$. We let $\sigma$ act on $X(\lambda)$ by letting each $w_{i}$ swap the positions of the entries of the tuple that are congruent to $i-1$ and $i$ mod $n$, which, reduced mod $n$, is the same as the level one action of $s_{i}$. Since $w^{-1}\cdot_{1}(0,1,\ldots,n-1)=X(\lambda)$, the action of $\sigma$ sorts $X(\lambda)$ back in congruence class order $(0,1,2,\ldots)$. As a result, $X(\lambda)_{\sigma(i)}=S(\lambda)_{i-1}.$ (The index shifts by 1 since the “first” element of $S(\lambda)$ is $S(\lambda)_{0}$.)

Proof. For $1\leq i\leq n-1$, $s_{i}$ acts linearly on $Q$ and fixes $\delta$. For $s_{0}$, we note that for any $\alpha^{\prime}$, $s_{0}(\alpha^{\prime}+k\delta)=\alpha^{\prime}+k\delta-\langle\alpha^{\prime}+k\delta,\alpha_{0}\rangle\alpha_{0}=\alpha^{\prime}-\langle\alpha^{\prime},-\theta\rangle(-\theta)+j\delta$, for some $j$, while $s_{\theta}(\alpha^{\prime})=\alpha^{\prime}-\langle\alpha^{\prime},\theta\rangle\theta$. Thus the real parts of the actions match. ∎

Most importantly, though, $\sigma$ links the labels and the walls of an alcove of $A_{n}$.

Proof. By Lemma 1, if $H_{\alpha,k}$ is a floor of $wA_{0}$ with label $i$, then $w(\alpha_{i})=\alpha-k\delta$, so that $\sigma(\alpha_{i})=\alpha$. If $H_{\alpha,k}$ is a ceiling of $wA_{0}$, then $ws_{i}(\alpha_{i})=\alpha-k\delta$, so that $\sigma(-\alpha_{i})=\alpha$. Either way, $(\sigma s_{i}\sigma^{-1})\cdot\alpha=-\alpha$, so it is a reflection that inverts $\alpha$, and must equal $s_{\alpha}$. ∎

So we see that $\sigma$ links $n$-sets with $n$-windows, but also walls of alcoves with their labels. Combining these observations, we have the following lemma about how the partition associated to an $m$-minimal dominant alcove encodes its floors.

Proof. Part i is intrinsic in [13]. In their notation, the alcove $wA_{0}$ has $k_{\alpha}=k$. The numbers $p_{i}$ constructed in section 2.7 of [13] are the $n$-window for $w^{-1}$, shifted by a constant. Thus the difference between entries remain the same and so $\lfloor\frac{X_{j}-X_{i}}{n}\rfloor=k$. $X_{j}-X_{i}$ cannot equal $kn$ since $X_{i}$ and $X_{j}$ are not congruent mod $n$.

For the other parts, we note that if $H_{\alpha,k}$ is a wall of $wA_{0}$ with label $r$, then for $\sigma=f_{n}(w)$, we have $\sigma s_{r}\sigma^{-1}=s_{\alpha}$. This means $\sigma$ sends $r$ and $r+1$ to $i$ and $j$ in some order. Thus $X_{j}$ and $X_{i}$ are equal to $S(\lambda)_{r-1}$ and $S(\lambda)_{r}$ in some order. But these differ by $1$ mod $n$ so that $X_{j}-X_{i}=nk+1$ or $n(k+1)-1$. But if $H_{\alpha,k}$ is a wall of $wA_{0}$, then $ws_{r}A_{0}$ is on the other side of $H_{\alpha,k}$, which can only happen if $(s_{r}X)_{j}-(s_{r}X)_{i}<kn$. But since $s_{r}$ only changes the elements of $X$ by a total of 2, this must mean that $X_{j}-X_{i}=kn+1$ and $(s_{r}X)_{j}-(s_{r}X)_{i}=kn-1$. A similar argument proves iii. ∎

The conditions ii. and iii. essentially identify floors and ceilings of $wA_{0}$, although not exactly. Hyperplanes of the form $H_{\alpha,0}$ are the only exception since they are technically never floors or ceilings. And condition iv. completes Lemma 6, showing that it is the labels of the walls of an alcove that index its stabilizer. (Note that it has occurred before that the labels on floors of an alcove index the stabilizer of an object indexing the regions of $\mathcal{S}_{n,m}$. See, for example, Lemma 4.1 in [3].)

In what follows, we will want $S_{n}$ to act on $n$-windows of $n$-core partitions, but with the goal of swapping the congruence classes in certain positions of the window. To swap, say, positions $i$ and $i+1$ of an $n$-window, we must “twist” the action of $w_{i}$ by exactly $\sigma$. More precisely, we have the following:

Proof. Note that the congruence classes of the $i$th and $i+1$st entries of $X$ are $\sigma(i)$ and $\sigma(i+1)$. But $(\sigma w_{i}\sigma^{-1})\cdot_{t}\sigma(i)$ is in the congruence class of $\sigma(i+1)$ and vice versa. ∎

Notice that, for different choices of $w\in\widetilde{S}_{n}/G$, corresponding to different $(n,mn\pm 1)$-core partitions, the twisting may act differently. So this action is not globally consistent in some sense, but it is well-defined within each orbit of the level $t$ action of $G$ on $C_{n}^{(t)}$.

We are finally in a position to state our main results.