# Counting Shi regions with a fixed separating wall

Susanna Fishel<fnref n="1" />, Eleni Tzanaki<fnref n="2" /> and Monica Vazirani<fnref n="3" />

**Abstract.** Athanasiadis introduced separating walls for a region in the extended Shi arrangement and used them to generalize the Narayana numbers. In this paper, we fix a hyperplane in the extended Shi arrangement for type A and calculate the number of dominant regions which have the fixed hyperplane as a separating wall; that is, regions where the hyperplane supports a facet of the region and separates the region from the origin.

**Résumé.** Athanasiadis a introduit la notion d'hyperplan de séparation pour une région dans l'arrangement de Shi et l'a utilisée pour généraliser les numéros de Narayana. Dans cet article, nous fixons un hyperplan dans l'arrangement de Shi pour le type A et calculons le nombre de régions dominantes qui ont l'hyperplan fixe pour mur de séparation, c'est-à-dire les régions où l'hyperplan soutient une facette de la région et sépare la région de l'origine.

**Keywords:** Shi arrangement, partitions

## 1 Introduction

A hyperplane arrangement dissects its ambient vector space into regions. The regions have walls – hyperplanes which support facets of the region – and the walls may or may not separate the region from the origin. The regions in the extended Shi arrangement are enumerated by well-known sequences: all regions by the extended parking functions numbers, the dominant regions by the extended Catalan numbers, dominant regions with a given number of separating walls by the Narayana numbers. In this paper we study the extended Shi arrangement by fixing a hyperplane in it and calculating the number of regions for which that hyperplane is a separating wall. For example, suppose we are considering the $m$th extended Shi arrangement in dimension $n-1$, with highest root $\theta$. Let $H_{\theta,m}$ be the $m$th translate of the hyperplane through the origin with $\theta$ as normal. Then we show there are $m^{n-2}$ regions which abut $H_{\theta,m}$ and are separated from the origin by it.

At the heart of this paper is a well-known bijection from certain integer partitions to dominant alcoves (and regions). One particularly nice aspect of our work is that we are able to use the bijection to enumerate regions. We characterize the partitions associated to the regions in question by certain interesting features and easily count those partitions, whereas it would be difficult to count the regions directly.

We rely on work from several sources. Shi (1986) introduced what is now called the Shi arrangement while studying the affine Weyl group of type A, and Stanley (1998) extended it. We also use the work

<footnote n="1">¹School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ, USA</footnote>

<footnote n="2">²Department of Applied Mathematics, University of Crete, Heraklion, Crete, Greece</footnote>

<footnote n="3">³Department of Mathematics, UC Davis, CA, USA</footnote>
on alcoves in Shi (1987). The work in Richards (1996) on decomposition numbers for Hecke algebras has been very useful. The Catalan numbers have been extended and generalized; see Athanasiadis (2005) for the history. Fuss-Catalan numbers is another name for the extended Catalan numbers. The Catalan numbers can be written as a sum of Narayana numbers. Athanasiadis (2005) generalized the Narayana numbers. He showed they enumerated several types of objects; one of them was the number of dominant Shi regions with a fixed number of separating walls. This led us to investigate separating walls. All of our work is for type A.

In Section 2, we introduce notation, define the Shi arrangement, certain partitions, and the bijection between them which we use to count regions. In Section 3, we characterize the partitions assigned to the regions which have $H_{\theta,m}$ as separating wall. Finally, we give a recursion for counting the regions which have other separating walls $H_{\alpha,m}$ in Section 4, by using generating functions.

# 2 Preliminaries

Here we introduce notation and review some constructions.

## 2.1 Root system notation and extended Shi arrangements

Let $\{\epsilon_1, \dots, \epsilon_n\}$ be the standard basis of $\mathbb{R}^n$ and $\langle \cdot | \cdot \rangle$ be the bilinear form for which this is an orthonormal basis. Let $\alpha_i = \epsilon_i - \epsilon_{i+1}$. Then $\Pi = \{\alpha_1, \dots, \alpha_{n-1}\}$ is a basis of

$$V = \{(a_1, \dots, a_n) \in \mathbb{R}^n \mid \sum_{i=1}^{n} a_i = 0\}.$$

We let $\alpha_{ij} = \alpha_i + \dots + \alpha_j$, the highest root $\alpha_{1,n-1} = \theta$, and note that $\alpha_{ii} = \alpha_i$ and $\alpha_{ij} = \epsilon_i - \epsilon_{j+1}$.

The elements of $\Delta = \{\epsilon_i - \epsilon_j \mid i \neq j\}$ are called roots and we say a root $\alpha$ is positive, written $\alpha > 0$, if $\alpha \in \Delta^+ = \{\epsilon_i - \epsilon_j \mid i < j\}$.

A hyperplane arrangement is a set of hyperplanes, possibly affine hyperplanes, in $V$. We are interested in certain sets of hyperplanes of the following form. For each $\alpha \in \Delta^+$, we define its reflecting hyperplane

$$H_{\alpha,0} = \{v \in V \mid \langle v | \alpha \rangle = 0\} \text{ and for } k \in \mathbb{Z}, H_{\alpha,0} \text{'s } k\text{th translate, } H_{\alpha,k} = \{v \in V \mid \langle v | \alpha \rangle = k\}.$$

Note $H_{-\alpha, -k} = H_{\alpha, k}$ so we usually take $k \in \mathbb{Z}_{\ge 0}$. Then the extended Shi arrangement, here called the *m-Shi arrangement*, is the collection of hyperplanes

$$\mathcal{H}_m = \{H_{\alpha,k} \mid \alpha \in \Delta^+, -m < k \le m\}.$$

This arrangement is defined for crystallograhic root systems of all finite types.

Regions of the *m-Shi arrangement* are the connected components of the hyperplane arrangement complement $V \setminus \bigcup_{H \in \mathcal{H}_m} H$.

We denote the closed half-spaces $\{v \in V \mid \langle v | \alpha \rangle \ge k\}$ and $\{v \in V \mid \langle v | \alpha \rangle \le k\}$ by $H_{\alpha,k}^+$ and $H_{\alpha,k}^-$ respectively. The dominant chamber of $V$ is $V \cap \bigcap_{i=1}^{n-1} H_{\alpha_i, 0}^+$ and is also referred to as the fundamental chamber in the literature. This paper primarily concerns regions and alcoves in the dominant chamber.

A dominant region of the *m-Shi arrangement* is a region that is contained in the dominant chamber. We call the collection of dominant regions in the *m-Shi arrangement* $S_{n,m}$.
Each connected component of

$$V \setminus \bigcup_{\substack{\alpha \in \Delta^+ \\ k \in \mathbb{Z}}} H_{\alpha, k}$$

is called an *alcove* and the *fundamental alcove* is $\mathcal{A}_0$, the interior of $H_{\theta,1}^- \cap \bigcap_{i=1}^{n-1} H_{\alpha_i,0}^+$, where $\theta = \alpha_1 + \dots + \alpha_{n-1} = \varepsilon_1 - \varepsilon_n$. A *dominant alcove* is one contained in the dominant chamber. Denote the set of dominant alcoves by $\mathfrak{A}_n$.

A *wall* of a region is a hyperplane in $\mathcal{H}_m$ which supports a facet of that region or alcove. Two open regions are *separated* by a hyperplane $H$ if they lie in different closed half-spaces relative to $H$. Please see Athanasiadis (2005) for details. We study dominant regions with a fixed separating wall. A *separating wall* for a region $R$ is a wall of $R$ which separates $R$ from $\mathcal{A}_0$.

## 2.2 The affine symmetric group

**Definition 2.1** The affine symmetric group, denoted $\hat{\mathfrak{S}}_n$, is defined as

$$ \hat{\mathfrak{S}}_n = \langle s_1, \dots, s_{n-1}, s_0 \mid s_i^2 = 1, \ s_i s_j = s_j s_i \text{ if } i \neq j \pm 1 \ \text{mod } n, \\ s_i s_j s_i = s_j s_i s_j \text{ if } i \equiv j \pm 1 \ \text{mod } n \rangle $$

$$ \text{for } n > 2, \text{ but } \hat{\mathfrak{S}}_2 = \langle s_1, s_0 \mid s_i^2 = 1 \rangle. $$

The affine symmetric group $\hat{\mathfrak{S}}_n$ acts freely and transitively on the set of alcoves. We thus identify each alcove $\mathcal{A}$ with the unique $w \in \hat{\mathfrak{S}}_n$ such that $\mathcal{A} = w^{-1}\mathcal{A}_0$. Each simple generator $s_i$, $i > 0$, acts by reflection with respect to the simple root $\alpha_i$. In other words, it acts by reflection over the hyperplane $H_{\alpha_i,0}$. The element $s_0$ acts as reflection with respect to the affine hyperplane $H_{\theta,1}$.

## 2.3 Shi coordinates and Shi tableaux.

Every alcove $\mathcal{A}$ can be written as $w^{-1}\mathcal{A}_0$ for a unique $w \in \hat{\mathfrak{S}}_n$ and additionally, for each $\alpha \in \Delta^+$, there is a unique integer $k_\alpha$ such that $k_\alpha < \langle \alpha | x \rangle < k_\alpha + 1$ for all $x \in \mathcal{A}$. Shi characterized the integers $k_\alpha$ which can arise in this way and the next lemma gives the conditions for type $\mathcal{A}$.

**Lemma 2.2 (Shi (1987))** Let $\{k_{\alpha_{ij}}\}_{1 \le i \le j \le n-1}$ be a set of $\binom{n}{2}$ integers. There exists a $w \in \hat{\mathfrak{S}}_n$ such that

$$ k_{\alpha_{ij}} < \langle \alpha_{ij} | x \rangle < k_{\alpha_{ij}} + 1 $$

$$ \text{for all } x \in w^{-1}\mathcal{A}_0 \text{ if and only if} $$

$$ k_{\alpha_{it}} + k_{\alpha_{t+1,j}} \le k_{\alpha_{ij}} \le k_{\alpha_{it}} + k_{\alpha_{t+1,j}} + 1, $$

$$ \text{for all } t \text{ such that } i \le t < j. $$

From now on, we write $k_{ij}$ for $k_{\alpha_{ij}}$. These $\{k_{ij}\}_{1 \le i \le n-1}$ are the *Shi coordinates* of the alcove. We arrange the coordinates for an alcove $\mathcal{A}$ in the Young's diagram (see Section 2.4) of a staircase partition $(n-1, n-2, \dots, 1)$ by putting $k_{ij}$ in the box in row $i$, column $n-j$. See Krattenthaler et al. (2002) for a similar arrangement of sets indexed by positive roots. For alcoves in $\mathfrak{A}_n$, the entries are nonincreasing along rows and columns and are nonnegative.
We can also assign coordinates to regions in the Shi arrangement. In each region of the *m*-Shi hyperplane arrangement, there is exactly one “representative,” or *m*-minimal, alcove closest to the fundamental alcove $\mathcal{A}_0$. See Shi (1986) for $m = 1$ and Athanasiadis (2005) for $m \ge 1$. Let $\mathcal{A}$ be an alcove with Shi coordinates $\{k_{ij}\}_{1\le i\le n-1}$ and suppose it is the *m*-minimal alcove for the region $R$. We define coordinates $\{e_{ij}\}_{1\le i\le j\le n-1}$ for $R$ by $e_{ij} = \min(k_{ij}, m)$.

Again, we arrange the coordinates for a region $R$ in the Young's diagram (see Section 2.4) of a staircase partition $(n-1, n-2, \dots, 1)$ by putting $e_{ij}$ in the box in row $i$, column $n-j$. For dominant regions, the entries are nonincreasing along rows and columns and are nonnegative.

**Example 2.3** For $n = 5$, the coordinates are arranged

<table><tr><td>k<sub>14</sub></td><td>k<sub>13</sub></td><td>k<sub>12</sub></td><td>k<sub>11</sub></td></tr><tr><td>k<sub>24</sub></td><td>k<sub>23</sub></td><td>k<sub>22</sub></td></tr><tr><td>k<sub>34</sub></td><td>k<sub>33</sub></td></tr><tr><td>k<sub>44</sub></td></tr></table>

<table><tr><td>e<sub>14</sub></td><td>e<sub>13</sub></td><td>e<sub>12</sub></td><td>e<sub>11</sub></td></tr><tr><td>e<sub>24</sub></td><td>e<sub>23</sub></td><td>e<sub>22</sub></td></tr><tr><td>e<sub>34</sub></td><td>e<sub>33</sub></td></tr><tr><td>e<sub>44</sub></td></tr></table>

**Example 2.4** The dominant chamber for the 2-Shi arrangement for $n = 3$ is illustrated in Figure 1. The yellow region has coordinates $e_{12} = 2$, $e_{11} = 1$, and $e_{22} = 2$. Its 2-minimal alcove has coordinates $k_{12} = 3$, $k_{11} = 1$, and $k_{22} = 2$.

<figure><img src="image_1.png" /><figcaption>Fig. 1: $S_{3,2}$ consists of 12 regions</figcaption></figure>

Denote the Shi tableau for the alcove $\mathcal{A}$ by $T_{\mathcal{A}}$ and for the region $R$ by $T_{R}$.

Both Richards (1996) and Athanasiadis (2005) characterized the Shi tableaux for dominant *m*-Shi regions.

**Lemma 2.5** Let $T = \{e_{ij}\}_{1\le i\le j\le n-1}$ be a collection of integers such that $0 \le e_{ij} \le m$. Then $T$ is the Shi tableau for a region $R \in S_{n,m}$ if and only if

$$e_{ij} = \begin{cases} e_{it} + e_{t+1,j} & \text{or } e_{it} + e_{t+1,j} + 1 & \text{if } m-1 \ge e_{it} + e_{t+1,j} \text{ for } t = i, \dots, j-1 \\ m & \text{otherwise} \end{cases} \quad (2.1)$$
**Proof:** Proof omitted in abstract.

□

Lemma 3.9 from Athanasiadis (2005) is crucial to our work here. He characterizes the co-filtered chains of ideals for which $H_{\alpha,m}$ is a separating wall. We translate that into our set-up in Lemma 2.6, using entries from the Shi Tableau.

**Lemma 2.6 (Athanasiadis (2005))** A region $R \in S_{n,m}$ has $H_{\alpha_{uv},m}$ as a separating wall if and only if $e_{uv} = m$ and for all $t$ such that $u \le t < v$, $e_{ut} + e_{t+1,v} = m - 1$.

## 2.4 Partitions

A partition is a non-increasing sequence $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_n)$ of nonnegative integers. $\lambda_1, \lambda_2, \dots$ are called the parts of $\lambda$. We identify a partition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_n)$ with its Young diagram, that is the array of boxes with coordinates $\{(i, j) : 1 \le j \le \lambda_i \text{ for all } \lambda_i\}$. The conjugate of $\lambda$ is the partition $\lambda'$ whose diagram is obtained by reflecting $\lambda$'s diagram about the diagonal. The length of a partition $\lambda$, $\ell(\lambda)$, is the number of positive parts of $\lambda$.

### 2.4.1 Core partitions

The $(k, l)$-hook of any partition $\lambda$ consists of the $(k, l)$-box of $\lambda$, all the boxes to the right of it in row $k$ together with all the nodes below it and in column $l$. The hook length $h_{kl}^{\lambda}$ of the box $(k, l)$ is the number of boxes in the $(k, l)$-hook. Let $n$ be a positive integer. An $n$-core is a partition $\lambda$ such that $n \nmid h_{(k,l)}^{\lambda}$ for all $(k, l) \in \lambda$. We let $C_n$ denote the set of partitions which are $n$-cores.

## 2.5 Abacus diagrams

In Section 3, we use a bijection, called $\Phi$, to describe certain regions. We will need abacus diagrams to define $\Phi$. We associate to each partition $\lambda$ its abacus diagram. When $\lambda$ is an $n$-core, its abacus has a particularly nice form.

The $\beta$-numbers for a partition $\lambda = (\lambda_1, \dots, \lambda_r)$ are the hook lengths from the boxes in its first column:

$$ \beta_k = h_{(k,1)}^{\lambda}. $$

Each partition is determined by its $\beta$-numbers and $\beta_1 > \beta_2 > \dots > \beta_{\ell(\lambda)} > 0$.

An abacus diagram is a diagram, with integer entries arranged in $n$ columns labeled 0, 1, ..., $n-1$, called runners. The horizontal cross-sections or rows will be called levels and runner $k$ contains the integer entry $qn + r$ on level $q$ where $-\infty < q < \infty$. We draw the abacus so that each runner is vertical, oriented with $-\infty$ at the top and $\infty$ at the bottom, and we always put runner 0 in the leftmost position, increasing to runner $n-1$ in the rightmost position. Entries in the abacus diagram may be circled; such circled elements are called beads. The level of a bead labelled by $qn + r$ is $q$ and its runner is $r$. Entries which are not circled will be called gaps. Two abacus diagrams are equivalent if one can be obtained by adding a constant to each entry of the other.

See Example 2.8 below.

Given a partition $\lambda$ its abacus is any abacus diagram equivalent to the one with beads at entries $\beta_k = h_{(k,1)}^{\lambda}$ and all entries $j \in \mathbb{Z}_{<0}$.

Given the abacus for the partition $\lambda$ with beads at $\{\beta_k\}_{1 \le k \le \ell(\lambda)}$, let $b_i$ be one more than the largest level number of a bead on runner $i$; that is, the level of the first gap. Then $(b_0, \dots, b_{n-1})$ is the vector of level numbers for $\lambda$.
**Remark 2.7** It is well-known that $\lambda$ is an $n$-core if and only if its abacus is flush, that is to say whenever there is a bead at entry $j$ there is also a bead at $j-n$. Additionally, if $(b_0, \dots, b_{n-1})$ is the vector of level numbers for $\lambda$, then $b_0 = 0$, $\sum_{i=0}^{n-1} b_i = \ell(\lambda)$, and since there are no gaps, $(b_0, \dots, b_{n-1})$ describes $\lambda$ completely.

**Example 2.8** The abacus below in Figure 2 represents the 4-core $\lambda = (5, 2, 1, 1, 1)$. The levels are indicated to the left of the abacus and below each runner is the largest level number of a bead in that runner. The boxes of the Young diagram of $\lambda$ have been filled with their hooklengths. The vector of level numbers for $\lambda$ is $(0, 3, 1, 1)$.

<figure><img src="image_2.png" /><figcaption>Fig. 2: The abacus represents the 4-core $\lambda$.</figcaption></figure>

## 2.6 Bijection

We describe here a bijection $\Phi$ from the set of $n$-cores to dominant alcoves. It is a slightly modified version of the bijection given in Richards (1996). Given an $n$-core $\lambda$, let $(b_0 = 0, b_1, \dots, b_{n-1})$ be the level numbers for its abacus. Now let $\tilde{p}_i = b_{i-1}n + i - 1$, which is the entry of the first gap on runner $i$, for $i$ from 1 to $n$, and then let $p_1 = 0 < p_2 < \dots < p_n$ be the $\{\tilde{p}_i\}$ written in ascending order. Finally we define $\Phi(\lambda)$ to be the alcove whose Shi coordinates are given by

$$k_{ij} = \lfloor \frac{p_{j+1} - p_i}{n} \rfloor$$

for $1 \le i \le j \le n-1$.

**Example 2.9** We continue Example 2.8. We have $n = 4$, $\lambda = (5, 2, 1, 1, 1)$, and $(b_0, b_1, b_2, b_3) = (0, 3, 1, 1)$. Then $\tilde{p}_1 = 0$, $\tilde{p}_2 = 13$, $\tilde{p}_3 = 6$, and $\tilde{p}_4 = 7$ and $p_1 = 0$, $p_2 = 6$, $p_3 = 7$, and $p_4 = 13$. Thus $\Phi(\lambda)$ is the alcove with coordinates $k_{13} = 3$, $k_{12} = 1$, $k_{11} = 1$, $k_{23} = 1$, $k_{22} = 0$, and $k_{33} = 1$.

**Proposition 2.10** The map $\Phi$ from $n$-cores to dominant alcoves is a bijection.

**Proof:** We first show that we indeed produce an alcove by the process above. By Lemma 2.2, it is enough to show that $k_{it} + k_{t+1,j} \le k_{ij} \le k_{it} + k_{t+1,j} + 1$ for all $t$ such that $1 \le t < j$. Write $p_i = nq_i + r_i$ for $1 \le i \le n$. Then

$$k_{it} = \begin{cases} q_{t+1} - q_i & \text{if } r_{t+1} > r_i, \\ q_{t+1} - q_i - 1 & \text{if } r_{t+1} < r_i, \end{cases} \quad k_{t+1,j} = \begin{cases} q_{j+1} - q_{t+1} & \text{if } r_{j+1} > r_{t+1} \\ q_{j+1} - q_{t+1} - 1 & \text{if } r_{j+1} < r_{t+1}. \end{cases}$$
and

$$k_{ij} = \begin{cases} q_{j+1} - q_i & \text{if } r_{j+1} > r_i \\ q_{j+1} - q_i - 1 & \text{if } r_{j+1} < r_i. \end{cases} \qquad (2.2)$$

Therefore

$$k_{ij} = \begin{cases} k_{it} + k_{t+1,j} & \text{if } r_i < r_{t+1} < r_{j+1} \text{ or } r_{j+1} < r_i < r_{t+1} \text{ or } r_{t+1} < r_{j+1} < r_i \\ k_{it} + k_{t+1,j} + 1 & \text{if } r_i < r_{j+1} < r_{t+1} \text{ or } r_{t+1} < r_i < r_{j+1} \text{ or } r_{j+1} < r_{t+1} < r_i \end{cases},$$

so that the conditions in Lemma 2.2 are satisfied and we have the Shi coordinates of an alcove. Since each $k_{ij} \ge 0$, it is an alcove in the dominant chamber.

Now we reverse the process described above to show that $\Phi$ is a bijection. Let $\{k_{ij}\}_{1\le i\le j\le n-1}$ be the Shi coordinates of a dominant alcove. Again, write $p_i = nq_i + r_i$ for the intermediate values $\{p_i\}$, which we first calculate. Then $p_1 = q_1 = r_1 = 0$ and $q_i = k_{1,i-1}$. We must now determine $r_2, \dots, r_n$, a permutation of $1, \dots, n-1$. However, by (2.2) we can determine the inversion table for this permutation, using $k_{ij}$ for $2 \le i \le j \le n-1$ and $q_1, \dots, q_n$, so we can compute $r_2, \dots, r_n$ and therefore $p_1, p_2, \dots, p_n$. We can now sort the $\{p_i\}$ according to their residue mod $n$, giving us $\tilde{p}_1, \dots, \tilde{p}_n$; from this, $(b_0, \dots, b_{n-1})$. Note that $(b_0, \dots, b_{n-1})$ is a permutation of $q_1, \dots, q_n$. $\square$

**Example 2.11** We continue Examples 2.8 and 2.9 here. Suppose we are given that $n = 4$ and the alcove coordinates $k_{13} = 3, k_{12} = 1, k_{11} = 1, k_{23} = 1, k_{22} = 0$, and $k_{33} = 1$. We demonstrate $\Phi^{-1}$ and calculate $(b_0, b_1, b_2, b_3)$ and thereby the 4-core $\lambda$. We have $q_1 = 0, q_2 = 1, q_3 = 1$, and $q_4 = 3$, and $r_1 = 0$, from $k_{13}, k_{12}$, and $k_{11}$. We must determine $r_2, r_3, r_4$, a permutation of $1, 2, 3$.

$$k_{23} = 1 = q_4 - q_2 - 1 \quad \text{so } r_4 < r_2$$

$$k_{22} = 0 = q_3 - q_2 \quad \text{so } r_3 > r_2$$

$$k_{33} = 1 = q_4 - q_3 - 1 \quad \text{so } r_4 < r_3$$

Therefore we have $r_3 = 3, r_2 = 2$, and $r_4 = 1$, which means $b_1 = q_4 = 3, b_2 = q_2 = 1$, and $b_3 = q_3 = 1$.

**Remark 2.12** There is a well-known action of $\hat{\mathfrak{S}}_n$ on $n$-cores; please see Misra and Miwa (1990), Las-coux (2001), Lapointe and Morse (2005), for more details and history. This leads to a bijection $\Psi$ from $n$-cores to dominant alcoves, where $w\emptyset \mapsto w^{-1}\mathcal{A}_0$. We mention that $\Phi = \Psi$, a fact which we will neither use nor prove here. We also remark that the column (or row) sums of the Shi tableau of an alcove give us a partition whose conjugate is $(n-1)$-bounded, as in the bijections of Lapointe and Morse (2005) or Björner and Brenti (1996)

## 3 Separating wall $H_{\theta,m}$

Separating walls were defined in Section 2.1 as a wall of a region which separates the region from $\mathcal{A}_0$. Equivalently for alcoves, $H_{\alpha,k}$ is a separating wall for the alcove $w^{-1}\mathcal{A}_0$ if there is a simple reflection $s_i$, where $0 \le i < n$, such that $w^{-1}\mathcal{A}_0 \subseteq H_{\alpha,k}^+$ and $(s_i w)^{-1}\mathcal{A}_0 \subseteq H_{\alpha,k}^-$. We want to count the regions which have $H_{\alpha,m}$ as a separating wall, for any $\alpha \in \Delta^+$. We do this by induction and the base case will be $\alpha = \theta$. Our main result in this section characterizes the regions which have $H_{\theta,m}$ as a separating wall by describing the $n$-core partitions associated to them under the bijection $\Phi$ described in Section 2.6.
**Theorem 3.1** Let $\Phi: C_n \to \mathfrak{A}_n$ be the bijection described in Section 2.6, let $R \in S_{n,m}$ have $m$-minimal alcove $\mathcal{A}$, and let $\lambda$ be the $n$-core such that $\Phi(\lambda) = \mathcal{A}$. Then $H_{\theta,m}$ is a separating wall for the region $R$ if and only if the Shi coordinates of the region $R$ are the same as the Shi coordinates of its $m$-minimal alcove $\mathcal{A}$ and $h_{11}^{\lambda} = n(m-1)+1$.

**Proof:** Proof omitted in abstract.

<figure><img src="image_3.png" /></figure>

We have the following corollary to Theorem 3.1.

**Corollary 3.2** There are $m^{n-2}$ regions in $S_{n,m}$ which have $H_{\alpha_1 n-1, m}$ as a separating wall.

**Proof:** Let $\vec{b}(\lambda) = (b_0, b_1, \dots, b_{n-1})$ be the vector of level numbers for the $n$-core $\lambda$. Note that $h_{11} = n(m-1)+1$ if and only if $b_1 = m$ and $b_i < m$ for $1 < i \le n-1$. There are $m^{n-2}$ vectors of level numbers $(b_0, b_1, \dots, b_{n-1})$ such that $b_0 = 0$, $b_1 = m$, and $0 \le b_i \le m-1$ for $2 \le i \le n-1$. $\square$

# 4 Arbitrary separating wall

We use $\mathfrak{h}_{\alpha k}^n$ to denote the set of regions in $S_{n,m}$ which have $H_{\alpha,k}$ as a separating wall. See Figure 3. In the language of Athanasiadis (2005), these are the regions whose corresponding co-filtered chain of ideals have $\alpha$ as an indecomposable element of rank $k$.

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** There are three regions in $\mathfrak{h}_{\alpha_1 2}^3$</figcaption></figure>

In this section, we present a generating function for regions in $\mathfrak{h}_{\alpha k}^n$. We use two statistics $r()$ and $c()$ on regions in the extended Shi arrangement. Let $R \in S_{n,m}$ and define

$$r(R) = |\{(j, k) : R \in \mathfrak{h}_{\alpha_1 j k}^n \text{ and } 1 \le k \le m\}| \text{ and } c(R) = |\{(i, k) : R \in \mathfrak{h}_{\alpha_i n-1 k}^n \text{ and } 1 \le k \le m\}|.$$

$r(R)$ counts the number of translates of $H_{\alpha_1 j, 0}$ which separate $R$ from $\mathcal{A}_0$, for $1 \le j \le n-1$. Similarly for $c(R)$ and translates of $H_{\alpha_i, n-1, 0}$.

The generating function is

$$f_{\alpha_{ij}m}^{n}(p, q) = \sum_{R \in \mathfrak{h}_{\alpha_{ij}m}^{n}} p^{c(R)} q^{r(R)}.$$
**Example 4.1** $f_{\alpha_1 2}^3(p, q) = p^4 q^2 + p^4 q^3 + p^4 q^4$.

We let $[k]_{p,q} = \sum_{j=0}^{k-1} p^j q^{k-1-j}$ and $[k]_q = [k]_{1,q}$. We will also need to truncate polynomials and the notation we use for that is

$$ \left( \sum_{j=0}^{j=n} a_j q^j \right)_{\le q^N} = \sum_{j=0}^{j=N} a_j q^j. $$

The statistics are related to the *n*-core partition assigned to the *m*-minimal alcove for the region.

**Claim 4.2** Let $\lambda$ be an *n*-core with vector of level numbers $(b_0, \dots, b_{n-1})$ and suppose $\Phi(\lambda) = R$ and $R \in \mathfrak{h}_{\theta_m}^n$. Then $r(R) = m + \sum_{i=2}^{n-1} b_i$ and $c(R) = m + \sum_{i=2}^{n-1} (m-1-b_i)$.

**Proof:** Proof omitted in abstract.

<figure><img src="image_5.png" /></figure>

We thus obtain another corollary to Theorem 3.1.

**Corollary 4.3**

$$ f_{\theta,m}^n(p,q) = p^m q^m (p^{m-1} + p^{m-2}q + \dots + pq^{m-1} + q^{m-1})^{n-2} = p^m q^m [m]_{p,q}^{n-2}. $$

Corollary 4.3 follows from Claim 4.2 and the abacus representation of *n*-cores which have the prescribed hook length.

Corollary 3.2 can be derived from Corollary 4.3 by evaluating at $p = q = 1$.

Given a Shi tableau $T_R = \{e_{ij}\}_{1 \le i \le j \le n-1}$, where $R \in S_{n,m}$, let $\tilde{T}_R = \{\tilde{e}_{ij}\}_{1 \le i \le j \le n-2}$ denote the tableau where $\tilde{e}_{ij}$ is given by $e_{ij}$. That is, $\tilde{T}_R$ is $T_R$ with the first column removed.

**Example 4.4** Suppose $R \in S_{5,m}$ and

$$ T_R = \left[ \begin{array}{c|c|c|c} e_{14} & e_{13} & e_{12} & e_{11} \\ \hline e_{24} & e_{23} & e_{22} \end{array} \right] . \text{ Then } \tilde{T}_R = \left[ \begin{array}{c|c|c} e_{13} & e_{12} & e_{11} \\ \hline e_{23} & e_{22} \end{array} \right] $$

The next lemma tells us that $\tilde{T}_R$ is always the Shi tableau for a region in one less dimension.

**Lemma 4.5** If $T_R$ is the tableau of a region $R \in S_{n,m}$ and $1 \le u \le v \le n-1$, then $\tilde{T}_R = T_{\tilde{R}}$ for some $\tilde{R} \in S_{n-1,m}$.

**Proof:** This follows from Lemma 2.5.

<figure><img src="image_6.png" /></figure>

**Lemma 4.6** Let $T_R$ be the Shi tableau for the region $R \in S_{n,m}$ and let $\tilde{R}$ be defined by $T_{\tilde{R}} = \tilde{T}_R$, where $\tilde{R} \in S_{n-1,m}$ by Lemma 4.5. Then $R \in \mathfrak{h}_{\alpha_{i,n-2}m}^n$ if and only if $\tilde{R} \in \mathfrak{h}_{\alpha_{i,n-2}m}^{n-1}$.

**Proof:** This follows from Lemma 2.6.

<figure><img src="image_7.png" /></figure>
The next proposition will provide a method for determining whether or not $H_{\alpha_{1n-j},m}$ is a separating wall for $R$. Given a Shi tableau $T = \{b_{ij}\}_{1\le i\le j\le n-1}$ for a region in $S_{n,m}$, let $T'$ be its conjugate given by $T' = \{b'_{ij}\}_{1\le i\le j\le n-1}$, where $b'_{ij} = b_{n-j,n-i}$.

**Example 4.9**

By Lemma 2.5, $T'$ will also be Shi tableau of a region in $S_{n,m}$. Additionally, by Lemma 2.6, we have the following proposition.

**Proposition 4.10** Suppose the regions $R$ and $R'$ are related by

$$ (T_R)' = T_{R'}. $$

Then $R \in \mathfrak{h}_{\alpha_{ij}m}^n$ if and only if $R \in \mathfrak{h}_{\alpha_{n-j,n-i}m}^n$.

In terms of generating functions, this becomes the following:

$$ f_{\alpha_{ij}m}^{n}(p, q) = f_{\alpha_{n-j,n-i}m}^{n}(q, p). \qquad (4.4) $$

We will now combine Theorem 3.1, Proposition 4.6, and Proposition 4.10 to produce an expression for the generating function for regions with a given separating wall.

Given a polynomial $f(p, q)$ in two variables, let $\phi_{km}(f)$ be the polynomial

$$ (p^m[m(k-2) + 1]_q f(p, q))_{\le q^{(k-1)m}} $$

and let $\rho(f)$ be the original polynomial with $p$ and $q$ reversed: $f(q, p)$. Then (4.2) is

$$ f_{\alpha_{ij}m}^{n}(p, q) = \phi_{nm}(f_{\alpha_{ij}m}^{n-1}(p, q)) \text{ and } (4.4) \text{ is } f_{im}^{n}(j, p)q = \rho(f_{\alpha_{n-j,n-i}m}^{n}(p, q)). $$

Finally, the full recursion is

**Theorem 4.11**

$$ f_{\alpha_{uv}m}^{n}(p, q) = \phi_{n}(\phi_{n-1}(\dots\phi_{v+2}(\rho(\phi_{v+1}(\dots(\phi_{v-u+3}(p^{m}q^{m}[m]_{p,q}^{v-u})\dots)). $$

The idea behind the theorem is that, given a root $\alpha_{uv}$ in dimension $n-1$, we remove columns using Lemma 4.7 until we are in dimension $(v+1)-1$, then we conjugate, then remove columns again until our root is $\alpha_{1,v-u+1}$ and we are in dimension $(v-u+2)-1$.

**Example 4.12** We would like to know how many elements there are in $\mathfrak{h}_{\alpha_{24}2}^7$; that is, how many dominant regions in the 2-Shi arrangement for $n=7$ have $H_{\alpha_{24},2}$ as a separating wall.

$$ \begin{aligned} f_{\alpha_{24}2}^{7}(p, q) &= (p^2[13]_q f_{\alpha_{24}2}^{6}(p, q))_{\le q^{12}} \\ &= (p^2[13]_q (p^2[11]_q f_{\alpha_{24}2}^{5}(p, q))_{\le q^{10}})_{\le q^{12}} \\ &= (p^2[13]_q (p^2[11]_q f_{\alpha_{13}2}^{5}(q, p))_{\le q^{10}})_{\le q^{12}} \\ &= (p^2[13]_q (p^2[11]_q (q^2[9]_p f_{\alpha_{13}2}^{4}(q, p))_{\le p^8})_{\le q^{10}})_{\le q^{12}} \\ &= (p^2[13]_q (p^2[11]_q (q^2[9]_p (p^2q^2[2]_{p,q}^2))_{\le p^8})_{\le q^{10}})_{\le q^{12}} \end{aligned} $$
After expanding this polynomial and evaluating at $p = q = 1$, we see there are 781 such regions.

## Acknowledgements

We thank Matthew Fayers for telling us of Richards (1996) and explaining its relationship to Fishel and Vazirani (2010).

## References

C. A. Athanasiadis. On a refinement of the generalized Catalan numbers for Weyl groups. *Trans. Amer. Math. Soc.*, 357(1):179–196 (electronic), 2005. ISSN 0002-9947.

A. Björner and F. Brenti. Affine permutations of type A. *Electron. J. Combin.*, 3(2):Research Paper 18, approx. 35 pp. (electronic), 1996. The Foata Festschrift.

S. Fishel and M. Vazirani. A bijection between dominant Shi regions and core partitions. *European J. Combin.*, 31(8):2087–2101, 2010. ISSN 0195-6698.

C. Krattenthaler, L. Orsina, and P. Papi. Enumeration of ad-nilpotent b-ideals for simple Lie algebras. *Adv. in Appl. Math.*, 28(3-4):478–522, 2002. Special issue in memory of Rodica Simion.

L. Lapointe and J. Morse. Tableaux on $k+1$-cores, reduced words for affine permutations, and $k$-Schur expansions. *J. Combin. Theory Ser. A*, 112(1):44–81, 2005. ISSN 0097-3165.

A. Lascoux. Ordering the affine symmetric group. In *Algebraic combinatorics and applications* (Gößweinstein, 1999), pages 219–231. Springer, Berlin, 2001.

K. Misra and T. Miwa. Crystal base for the basic representation of $U_q(sl(n))$. *Comm. Math. Phys.*, 134 (1):79–88, 1990. ISSN 0010-3616.

M. J. Richards. Some decomposition numbers for Hecke algebras of general linear groups. *Math. Proc. Cambridge Philos. Soc.*, 119(3):383–402, 1996. ISSN 0305-0041. doi: 10.1017/S0305004100074296.

J. Y. Shi. *The Kazhdan–Lusztig cells in certain affine Weyl groups*, volume 1179 of *Lecture Notes in Mathematics*. Springer-Verlag, Berlin, 1986. ISBN 3-540-16439-1.

J. Y. Shi. Alcoves corresponding to an affine Weyl group. *J. London Math. Soc.* (2), 35(1):42–55, 1987. ISSN 0024-6107.

R. P. Stanley. Hyperplane arrangements, parking functions and tree inversions. In *Mathematical essays in honor of Gian-Carlo Rota* (Cambridge, MA, 1996), volume 161 of *Progr. Math.*, pages 359–375. Birkhäuser Boston, Boston, MA, 1998.