Paper BOAT Bruhat Order and Alcovic Tilings Federico Castillo, Damian de la Fuente, Nicolas Libedinsky, David Plaza Abstract We derive a formula for computing the size of lower Bruhat intervals for elements in the dominant cone of an affine Weyl group of type A A . This enumeration problem is reduced to counting lattice points in certain polyhedra. Our main tool is a decomposition—or tiling—of each interval into smaller, combinatorially tractable pieces, which we call paper boats. We also conjecture a generalization of this formula to all affine Weyl groups, restricted to elements in the lowest two-sided Kazhdan–Lusztig cell, which contains almost all of the elements. A note on the title The title of this paper reflects two aspects of this work, though the connection between them emerged unexpectedly. Initially, we referred to the sets that we introduce as “paper boats” due to their visual resemblance in certain cases to actual paper boats (see the green objects in Figure 1(a) ). Subsequently, we observed that this name could also serve as an acronym for “Bruhat Order and Alcovic Tilings”, which is the central theme of the paper (see Figures 1(a) and 1(b) ). 1  Introduction In [ 7 ] , we initiated the study of the sizes of lower Bruhat intervals in affine Weyl groups and uncovered intriguing connections with convex geometry. In that work, we derived formulas for a set of elements, denoted by \mathord{\text{\textgoth{A}}} in this introduction, which plays a significant role in representation theory. (a) Tiling the dominant part of a lower interval by paper boats. (b) Tiling the dominant part of a lower interval by paper boats. (c) Polyhedra associated to the tilings and lattice points. Figure 1 : Some examples of tilings of lower Bruhat intervals Let \mathfrak{B} denote the dominant elements, i.e. , those whose alcoves belong to the dominant chamber, and let \mathfrak{C} represent the lowest two-sided Kazhdan-Lusztig cell. These sets satisfy the inclusion \mathord{\text{\textgoth{A}}}\subset\mathfrak{B}\subset\mathfrak{C} and are depicted in Figure 2(a) for the affine Weyl group of type A_{2} . The set \mathord{\text{\textgoth{A}}} corresponds to the green triangles, \mathfrak{B} corresponds to the green and orange triangles, and \mathfrak{C} corresponds to the green, orange and gray triangles. The red triangle corresponds to the identity element. It does not belong to any of the sets \mathord{\text{\textgoth{A}}} , \mathfrak{B} and \mathfrak{C} . (a) Illustration of the sets \mathord{\text{\textgoth{A}}} , \mathfrak{B} and \mathfrak{C} for the affine Weyl group of type A_{2} . (b) Tiling the dominant region by translations of the fundamental parallelepiped. Figure 2 : In this paper, we propose a conjectural formula (see Equation ( 2.37 )) for the size of lower Bruhat intervals associated with elements in \mathfrak{C} and prove it in type A for elements in \mathfrak{B} . To illustrate the relative sizes of these sets in type A_{n} , consider selecting a “random” element from the affine Weyl group. The probability of such an element belonging to \mathord{\text{\textgoth{A}}} , \mathfrak{B} , and \mathfrak{C} is \frac{1}{n!(n+1)!},\quad\frac{1}{(n+1)!}\quad\mbox{and}\qquad 1, respectively. Thus, our conjecture effectively provides an answer for almost the entirety of the affine Weyl group, and our proof for \mathfrak{B} extends our prior results [ 7 ] to encompass a set that is n! times larger in type A_{n} . Another interesting aspect of this work is the conjecture (partially established in this paper) that the resulting formulas, when restricted to some specific sets, are polynomials. This is a scenario that exceeds expectations in both simplicity and elegance. To elaborate briefly, let \Pi^{+} denote the fundamental parallelepiped spanned by the fundamental coweights. In ( 2.15 ), we prove that \mathfrak{B} can be tiled using the set \{\Pi^{+}+\lambda\mid\lambda\in(\Lambda^{\vee})^{+}\} , where (\Lambda^{\vee})^{+} is the set of dominant coweights. This tessellation is illustrated in Figure 2(b) , where \Pi^{+} is highlighted in light blue and the points corresponds to the elements in (\Lambda^{\vee})^{+} . The aforementioned polynomiality phenomenon asserts that, for a fixed alcove x\subset\Pi^{+} , the size of the Bruhat interval [\text{id},x+\lambda] is a polynomial in the coordinates of \lambda\in(\Lambda^{\vee})^{+} expressed in the basis of fundamental coweights. Three observations are worth highlighting. First, within each tile \Pi^{+}+\lambda there is exactly one element of \mathord{\text{\textgoth{A}}} , so this polynomiality phenomenon extends that of [ 7 ] . Second, the emergence of polynomiality from this tiling provides yet another instance of the deep connection between alcove geometry (via the Bruhat order) and Euclidean geometry. Finally, and in alignment with the previous observation, we have verified computationally—quite unexpectedly—that all polynomials that arise in this context, even when extended to the full cell \mathfrak{C} , are geometric polynomials . That is, they are linear combinations (with coefficients that do not depend on \lambda ) of the volumes of the faces of the permutohedron \mathsf{P}(\lambda) , which is defined as the convex hull of the W_{\mathrm{f}} -orbit of \lambda . This was proven for \mathord{\text{\textgoth{A}}} in [ 7 ] , and this observation strongly suggests that the tessellation using \Pi^{+} introduced here is the natural and correct framework for this study. Let us briefly explain the main contributions of this paper. Bruhat order criterion in alcovic terms Elements in \mathord{\text{\textgoth{A}}} have nice algebraic properties that arbitrary elements do not share; see Lemma 2.5 . As a consequence [ 7 , Eq. (3.3)] , their lower Bruhat intervals can essentially be reduced to ideals in the dominance order. The latter is significantly more accessible than the former, which simplifies matters considerably. To extend our results beyond \mathord{\text{\textgoth{A}}} , we require a criterion for determining whether x\leq y , not merely as abstract elements of the affine Weyl group, but specifically as alcoves. We establish a criterion for the dominant region in type A : comparing alcoves reduces to comparing their corresponding vertices with respect to the dominance order. More precisely we have the following proposition. Proposition 1.1 . Let W_{\mathrm{aff}} be an affine Weyl group of type A , V the set of vertices of the fundamental alcove, and x,y\in\mathfrak{B} . Then, x\leq y\qquad\mbox{if and only if}\qquad x(v)\leq y(v),\ \forall\ v\in V, where the left-hand relation denotes the (strong) Bruhat order and the right-hand relation denotes the dominance order. This is the content of Proposition 3.1 . The criterion for the entire group was originally mentioned by Schremmer in [ 19 , §3] . We warmly thank him for sharing a sketch of the proof, which we have expanded into the detailed version presented in Section 6 . Tiling lower intervals To describe our next result, we first introduce some notation. For w\in W_{\mathrm{aff}} , where W_{\mathrm{aff}} is an affine Weyl group, we denote by \mathcal{A}_{w} the corresponding alcove. Let (\Lambda^{\vee})^{+} denote the set of dominant coweights. We define \mathcal{F}=\{a\in W_{\mathrm{aff}}\mid\mathcal{A}_{a}\subset-\Pi^{+}\}, and for \lambda\in(\Lambda^{\vee})^{+} and a\in\mathcal{F} , we let \theta_{a}(\lambda) be the unique element in W_{\mathrm{aff}} satisfying \mathcal{A}_{\theta_{a}(\lambda)}=\mathcal{A}_{aw_{0}}+\lambda . The region \mathfrak{B} (resp. \mathord{\text{\textgoth{A}}} ) consists of elements in W_{\mathrm{aff}} of the form \theta_{a}(\lambda) (resp. \theta_{\mathrm{id}}(\lambda) ). Consider the Bruhat intervals of the form \mathcal{I}_{a}(\lambda):=[\mathrm{id},\theta_{a}(\lambda)]=\{x\in W_{\mathrm{aff}}\mid x\leq\theta_{a}(\lambda)\}. The following definition introduces the central combinatorial object of this paper. Definition 1.2 . The Paper Boat associated with \lambda\in(\Lambda^{\vee})^{+} and a\in\mathcal{F} is defined as PB_{a}(\lambda):=\mathcal{I}_{a}(\lambda)\setminus\bigcup_{\mu\lessdot\lambda}\mathcal{I}_{a}(\mu), (1.1) where \mu\lessdot\lambda denotes a covering relation in the poset (\Lambda^{\vee})^{+} ordered by dominance. A key observation is that lower intervals for elements in \mathfrak{B} are invariant under the left action of W_{\mathrm{f}} . This allows us to focus on their dominant part. The fundamental building blocks of our tiling are the Paper Boats. This structure is illustrated in Figures 1(a) and 1(b) . The next theorem establishes that Paper Boats provide a tessellation of lower Bruhat intervals for elements in \mathfrak{B} . For the rest of the Introduction, all results stated will be for the affine Weyl group W_{\mathrm{aff}} of type A_{n} . Theorem A . Let \lambda be a dominant coweight, and let a\in\mathcal{F} . Then we have the following decomposition: \mathcal{I}_{a}(\lambda)=\bigsqcup_{\mu\leq\lambda}PB_{a}(\mu), (1.2) where the union runs over all \mu\in(\Lambda^{\vee})^{+} satisfying \mu\leq\lambda in the dominance order. In our previous work, we established a tiling [ 7 , Theorem A] for lower Bruhat intervals \mathcal{I}_{\mathrm{id}}(\lambda) ( i.e. for elements in \mathord{\text{\textgoth{A}}} ). This tiling led to a formula for the size of these intervals due to two key properties. First, among all intervals there is only one type of tile, consisting of the alcoves of the finite Weyl group W_{\mathrm{f}} . Second, for a given \mathcal{I}_{\mathrm{id}}(\lambda) , the number of tiles in the corresponding tiling corresponds to the number of lattice points in the permutohedron \mathsf{P}(\lambda) . The tiling presented in Theorem A , this time for general elements in \mathfrak{B} , retains similar properties. The first difference is that now there is more than one type of tile. In Definition 3.11 we introduce a finite partition \mathcal{Z} of the dominant coweights. The following theorem shows that, among all possible tilings, this new tiling features a finite number of distinct types of tiles. Theorem B . Let a\in\mathcal{F} and Z\in\mathcal{Z} . If \lambda,\mu\in Z , then the dominant alcoves in PB_{a}(\lambda) are a translation of the dominant alcoves in PB_{a}(\mu) . In particular, |PB_{a}(\lambda)|=|PB_{a}(\mu)|. It is worth noting that the definition of Paper Boats can be generalized to all affine Weyl groups and to all elements of \mathfrak{C} . We conjecture that there is a tiling as in Theorem A with a property as in Theorem B , at this level of generality (see Conjectures 2.12 and 2.13 ). Formulas for sizes of intervals. Combining Theorem A and Theorem B , we derive the following theorem and our main counting formula. For a dominant coweight \lambda , let \mathcal{L}_{\lambda} be the component of \Lambda^{\vee} (modulo the coroot lattice) containing \lambda . We let \mathfrak{I}_{\lambda} be the dominant lattice points (within \mathcal{L}_{\lambda} ) in the permutohedron \mathsf{P}(\lambda) , see Equation 2.33 . Theorem C . Let \lambda\in(\Lambda^{\vee})^{+} and let a\in\mathcal{F} . Then |\mathcal{I}_{a}(\lambda)|=\sum_{Z\in\mathcal{Z}}c_{a}(Z)|\mathfrak{I}_{\lambda}\cap Z|, where c_{a}(Z) is |PB_{a}(\mu)| for any \mu\in Z . As we mentioned above, the first difference between our previous tiling for elements in \mathord{\text{\textgoth{A}}} [ 7 ] and our new tiling for elements in \mathfrak{B} ( 1.2 ), is that we now have to deal with the sizes of Paper Boats c_{a}(Z) . For example in Figure 1(a) (resp. Figure 1(b) ), the blue tile at the bottom, for instance, has size five (resp. three). The second difference is that, after a reinterpretation of this formula as a weighted lattice point count (see ( 5.4 )), the number of tiles, of the same type, is equal to the number of lattice points in slices of permutohedra; whereas in [ 7 ] the relevant polytopes where always permutohedra. Sizes of Paper Boats: This is an intriguing problem even in type \widetilde{A}_{n} . In Proposition 4.1 we obtain a closed formula for the size of Paper Boats c_{a}(Z) , when Z is sufficiently deep inside the dominant chamber; their size is equal to (n+1)!^{2} , which does not depend on a . This is particularly striking given that the shapes of Paper Boats can vary dramatically. See the green regions highlighted in both Figures 1(a) and 1(b) for type \widetilde{A}_{2} and Figure 3 for \widetilde{A}_{3} . More generally, we conjecture that, for any type, the size of Paper Boats associated with coweights sufficiently deep inside the dominant chamber equals |W_{\mathrm{f}}|^{2} . Counting lattice points: In Section 5 , we see each \mathfrak{I}_{\lambda}\cap Z as the lattice points in convex polytopes. These lattice points are depicted in Figure 1(c) , where each color represents a different zone Z\in\mathcal{Z} . One technical difficulty is that we have to consider polytopes whose vertices are not lattice points ( Lemma 5.7 ) but rather rational points. Using general results about counting lattice points in polyhedra [ 1 ] , we prove that the number of lattice points in a rational polytope agrees with a quasi-polynomial, leading to the following theorem. Theorem D . Let \lambda\in(\Lambda^{\vee})^{+} and (\lambda_{1},\ldots,\lambda_{n}) its coordinates in the basis of fundamental coweights. For a fixed a\in\mathcal{F} the function q_{a}:\mathbb{N}^{n}\to\mathbb{N} defined as (\lambda_{1},\dots,\lambda_{n})\mapsto|\mathcal{I}_{a}(\lambda)| , agrees with a quasi-polynomial of degree n on the subset \mathbb{N}_{\geq 2}^{n} where each coordinate is at least two. Moreover, the top homogeneous component is a polynomial and it is independent of a . A quasi-polynomial on \mathbb{Z}^{n} of degree d is a function that agrees with a polynomial function of degree d on cosets of a subgroup H of \mathbb{Z}^{n} of finite index, see Definition 5.9 . The most basic example is the floor function \lfloor n/2\rfloor . The quasi-polynomial q_{a} is obtained as a linear combination of quasi-polynomials, and the coefficients in this combination are the sizes of different Paper Boats. But Theorem D is not the end of the story. After extensive computations, we have consistently found that q_{a} is actually a polynomial. This is quite unexpected as the quasi-polynomials composing q_{a} are definitely not polynomials in general. It suggests the presence of algebraic relations between the sizes c_{a}(Z) to be discovered. Furthermore, in every case our computations show that the polynomial is also geometric. To be more precise, the polynomials are rational combinations of volume polynomials from faces of permutohedra. Conjecture 1.3 . For any affine Weyl group the map q_{a} is a geometric polynomial. We remark that the polinomiality and the geometricity parts of this conjecture are both difficult. Heuristically the polinomiality part suggests that q_{a} is as simple as one could reasonably expect, while the geometricity part indicates that, among the full set of polynomials, these are exceptionally well-behaved and hint to a deeper connection with convex geometry. In Theorem 4.8 , we verify this conjecture for type \widetilde{A}_{3} , and we also show it in type \widetilde{A}_{n} for the top homogeneous part of q_{a} in Theorem 5.13 . We further conjecture an extension of Conjecture 1.3 to lower intervals coming from elements in \mathfrak{C} (rather than \mathfrak{B} ). See Conjecture 4.10 for more details. In this general form, it holds for types \widetilde{A}_{1} (trivially), \widetilde{A}_{2} (see [ 13 ] ) and \widetilde{B}_{2} (see [ 2 ] ). We have not found a counterexample in types \widetilde{A}_{3} and \widetilde{B}_{3} . Structure of the paper. Section 2 contains a recollection of important facts about affine Weyl groups. We also introduce a parametrization of the lowest two-sided Kazhdan-Lusztig cell and define the Paper Boat, our main object of study. In Section 3 we present the proof of Theorems A , B and C for type \widetilde{A}_{n} . Section 4 is devoted to the study the sizes of Paper Boats (also for type \widetilde{A}_{n} ). We compute the size of the most “common” Paper Boat, we give a recursive formula for the size of a Paper Boat in terms of lower Bruhat intervals and we give a criterion to test wether a given function matches the size of a lower interval. We then use this criterion to establish Conjecture 1.3 for type \widetilde{A}_{3} . In Section 5 we reinterpret Theorem C as a weighted lattice point count and invoke results from Ehrhart theory to obtain Theorem D . Finally, Section 6 contains the proof of Proposition 1.1 , which is heavily used from Section 3 onward. Acknowledgments. We would like to thank Gaston Burrull and Felix Schremer for their helpful comments. FC was partially supported by FONDECYT-ANID grant 1221133. NL was partially supported by FONDECYT-ANID grant 1230247. DP was partially supported by FONDECYT-ANID grant 1240199. We thank the support of the MATH-AmSud program (Grant 24-MATH-01). 2  The Paper Boat In this section, we introduce the Paper Boat associated with any element in the lowest two-sided Kazhdan-Lusztig cell, which is the central object of study in this paper. To achieve this, we begin by recalling key facts about affine Weyl groups. Additionally, we present a parametrization for the elements within the lowest two-sided Kazhdan-Lusztig cell and some of its properties. 2.1 Affine Weyl groups Let \Phi be an irreducible root system of rank n , and let E be the Euclidean space spanned by \Phi , with inner product \langle-,-\rangle:E\times E\to\mathbb{R} . We denote by \mathbf{0} the origin of E . Let {\Phi^{+}} be a choice of positive roots and \Delta\subset\Phi^{+} the simple root basis. We denote by \rho the half-sum of the positive roots. Let {\alpha^{\vee}=2\alpha/\langle\alpha,\alpha\rangle} be the coroot corresponding to a root {\alpha\in\Phi} . The set \Phi^{\vee}=\{\alpha^{\vee}\mid\alpha\in\Phi\} is also a root system. The fundamental weights \varpi_{\alpha} and fundamental coweights \varpi_{\alpha}^{\vee} are defined by the equations {\langle\varpi_{\alpha},\beta^{\vee}\rangle=\langle\varpi_{\alpha}^{\vee},\beta\rangle}=\delta_{\alpha\beta} , for \alpha,\beta\in\Delta . Both sets form a basis of E . We denote by \displaystyle\Lambda^{\vee}=\bigoplus_{\alpha\in\Delta}\mathbb{Z}\varpi_{\alpha}^{\vee} the set of coweights. We define C^{+}=\{x\in E\mid\langle x,\alpha\rangle\geq 0,\,\mbox{ for all }\alpha\in\Delta\}. We refer to {(\Lambda^{\vee})^{+}}\coloneqq\Lambda^{\vee}\cap C^{+} as the set of dominant coweights. We denote by \leq the dominance order on \Lambda^{\vee} , that is, {\mu\leq\lambda} if the coordinates of {\lambda-\mu} in the simple coroot basis \{\alpha^{\vee}\}_{\alpha\in\Delta} are non-negative. Remark 2.1 . In this paper we use the symbol \leq for different orders: for the standard ordering on real numbers, the Bruhat order on elements of the affine Weyl group, and for the dominance order on elements of the (co)weight lattice. Since they are all on different objects, from context it should be clear which one we are using. For \alpha\in\Phi and k\in\mathbb{Z} we define the hyperplane H_{\alpha,k}=\{\lambda\in E\mid\langle\lambda,\alpha\rangle=k\}. We denote by s_{\alpha,k} the affine reflection along the hyperplane H_{\alpha,k} . We write H_{\alpha}=H_{\alpha,0} and s_{\alpha}=s_{\alpha,0} . The affine Weyl group W_{\mathrm{aff}} of \Phi is the group of affine transformations of E generated by s_{\alpha,k} , for \alpha\in\Phi and k\in\mathbb{Z} . An alcove is a connected component of the space E-\bigcup_{\alpha\in\Phi,k\in\mathbb{Z}}H_{\alpha,k}. Let \mathcal{A} be the set of all alcoves. We define the fundamental alcove \mathcal{A_{\text{id}}}\in\mathcal{A} by \mathcal{A}_{\mathrm{id}}=\{x\in E\mid-1<\langle x,\alpha\rangle<0,\ \forall\alpha\in\Phi^{+}\}. The walls of \mathcal{A}_{\mathrm{id}} are the hyperplanes \{H_{\alpha}\mid\alpha\in\Delta\} , together with H_{\widetilde{\alpha},-1} , where \widetilde{\alpha}\in\Phi is the highest root. We set {s_{0}=s_{\widetilde{\alpha},-1}} and {S=\{s_{0},s_{\alpha}\mid\alpha\in\Delta\}} . Then the pair {(W_{\mathrm{aff}},S)} is a Coxeter system, with length function \ell and Bruhat order \leq . The action of W_{\mathrm{aff}} on E gives a simply transitive action on \mathcal{A} . Thus, we have a bijection W_{\mathrm{aff}}\rightarrow\mathcal{A} given by w\mapsto\mathcal{A}_{w}=w(\mathcal{A}_{\mathrm{id}}) . We define the vertices of an alcove \mathcal{A}_{w} to be the vertices of its closure \overline{\mathcal{A}_{w}} , and denote this set by V(w) . For X\subset W_{\mathrm{aff}} , we write \mathcal{A}(X)=\bigcup_{x\in X}\overline{\mathcal{A}_{x}}. (2.1) If Y\subset E is such that Y=\mathcal{A}(X) , we write \mathcal{A}^{-1}(Y)=X . We have a geometric interpretation of the length function. Concretely, \ell(w)=\#\{H=H_{\alpha,k}\mid H\mbox{ separates }\mathcal{A}_{\mathrm{id}}\mbox{ and }\mathcal{A}_{w}\}. (2.2) The (finite) Weyl group W_{\mathrm{f}} is the parabolic subgroup of W_{\mathrm{aff}} generated by the set S_{\mathrm{f}}=\{s_{\alpha}\mid\alpha\in\Delta\} . We denote by w_{0} the longest element of W_{\mathrm{f}} . The affine Weyl group can also be realized as a semi-direct product: {W_{\mathrm{aff}}\cong\mathbb{Z}\Phi^{\vee}\rtimes W_{\mathrm{f}}} , where the elements of \mathbb{Z}\Phi^{\vee} act on E as translations. We define W_{\mathrm{aff}}^{+}=\mathcal{A}^{-1}(C^{+}) and W_{\mathrm{aff}}^{-}=\mathcal{A}^{-1}(C^{-}) , where C^{-}=-C^{+} . We have W_{\mathrm{aff}}=\bigsqcup_{w\in W_{\mathrm{f}}}wW_{\mathrm{aff}}^{+}. (2.3) Consider the extended affine Weyl group W_{\mathrm{e}}=\Lambda^{\vee}\rtimes W_{\mathrm{f}} and the subgroup \Omega=\{\sigma\in W_{\mathrm{e}}\mid\sigma(\mathcal{A}_{\mathrm{id}})=\mathcal{A}_{\mathrm{id}}\}. (2.4) For \sigma\in\Omega and w\in W_{\mathrm{aff}} we write w_{\sigma}\coloneqq\sigma w\sigma^{-1} . We have \sigma(\mathcal{A}_{w})=\mathcal{A}_{w_{\sigma}} . For X\subset W_{\mathrm{aff}} we write X_{\sigma}=\sigma X\sigma^{-1}\subset W_{\mathrm{aff}} . Each \sigma\in\Omega permutes the walls of \mathcal{A}_{\mathrm{id}} and thus conjugation by \sigma permutes the simple reflections S of W_{\mathrm{aff}} , i.e. , S_{\sigma}=S . Note that (W_{\mathrm{f}})_{\sigma}\cong W_{\mathrm{f}} is the maximal parabolic subgroup of W_{\mathrm{aff}} corresponding to (S_{\mathrm{f}})_{\sigma}=S\setminus\{(s_{0})_{\sigma}\} , whose longest element is (w_{0})_{\sigma} . In fact, all maximal parabolic subgroups of W_{\mathrm{aff}} arise in this way. It is well-known [ 4 , Prop VI.2.3.6] that the set \{-\sigma(\mathbf{0})\mid\sigma\in\Omega\} forms a complete system of representatives of \Lambda^{\vee}/\mathbb{Z}\Phi^{\vee} . Hence, for \lambda\in\Lambda^{\vee} , there is a unique \sigma_{\lambda}\in\Omega such that \lambda\equiv-\sigma_{\lambda}(\mathbf{0})\hskip-5.69046pt\pmod{\mathbb{Z}\Phi^{\vee}}. (2.5) Note that if \lambda\in\mathbb{Z}\Phi^{\vee} , then \sigma_{\lambda}=\mathrm{id} . Remark 2.2 . The group \Omega can be seen as a subgroup of the automorphism group of the Dynkin diagram of W_{\mathrm{aff}} . Indeed, if \sigma\in\Omega , by definition \sigma is an isometry satisfying \sigma(\mathcal{A}_{\mathrm{id}})=\mathcal{A}_{\mathrm{id}} . Therefore, it permutes the generators S of the Coxeter system (W_{\mathrm{aff}},S) while respecting its defining relations. Definition 2.3 . Given I,J\subset S , we define \displaystyle\begin{split}{}_{I}\mathcal{D}_{J}&=\{w\in W_{\mathrm{aff}}\mid wsw\mbox{ and }w>wt\ \mbox{ for all }s\in I\mbox{ and }t\in J\}. (2.7) It is immediate that ({}_{I}\mathcal{D}_{J})^{-1}={}_{J}\mathcal{D}_{I} and ({}^{I}\mathcal{D}^{J})^{-1}={}^{J}\mathcal{D}^{I} . When either of the two sets is empty (resp. S_{\mathrm{f}} ) we will just leave a blank space (resp. put \mathrm{f} ) instead. For instance, \mathcal{D}_{\mathrm{f}}={}_{\emptyset}\mathcal{D}_{S_{\mathrm{f}}} (and similarly for the other cases). It is a fact [ 23 , Proposition 2.1] that {}_{I}\mathcal{D}_{J} (resp. {}^{I}\mathcal{D}^{J} ) forms a complete system of representatives of W_{I}\backslash W_{\mathrm{aff}}/W_{J} , of minimal (resp. maximal) length. For this reason, its elements are called the minimal (resp. maximal) double coset representatives. Using this notation we can rewrite W_{\mathrm{aff}}^{-} and W_{\mathrm{aff}}^{+} . 1 1 1 The rewriting ( 2.8 ) is due to our choice of fundamental alcove. In the usual conventions (e.g. [ 10 , 4 ] ) one would have {}_{\mathrm{f}}\mathcal{D}=W_{\mathrm{aff}}^{+} and {}^{\mathrm{f}}\mathcal{D}=W_{\mathrm{aff}}^{-} . In formulas, we have {}_{\mathrm{f}}\mathcal{D}=W_{\mathrm{aff}}^{-}\qquad\mbox{and}\qquad{}^{\mathrm{f}}\mathcal{D}=W_{\mathrm{aff}}^{+}. (2.8) For \sigma\in\Omega , we write \mathcal{D}^{\sigma}=\mathcal{D}^{(S_{\mathrm{f}})_{\sigma}} . It is easy to check that \mathcal{D}^{\sigma}=(\mathcal{D}^{\mathrm{f}})_{\sigma}=\sigma\mathcal{D}^{\mathrm{f}}\sigma^{-1} . The analogous equality holds for \mathcal{D}_{\sigma},{}_{\sigma}\mathcal{D},{}^{\sigma}\mathcal{D} (defined similarly). With this notation we have that \mathcal{D}^{\mathrm{f}}=\mathcal{D}^{\mathrm{id}} , however we will always prefer \mathcal{D}^{\mathrm{f}} to avoid confusion. 2.2 The lowest two-sided cell In this section we collect some facts about the lowest two-sided cell \mathfrak{C} of W_{\mathrm{aff}} . The results preceding Definition 2.4 can be found in [ 20 , 21 ] , while the subsequent content is original. For x,y\in W_{\mathrm{aff}} , if \ell(xy)=\ell(x)+\ell(y) , we write x\cdot y to denote both the element xy\in W_{\mathrm{aff}} and the statement that its length is the sum of the lengths of x and y . We have \mathfrak{C}=\{x\cdot(w_{0})_{\sigma}\cdot y\in W_{\mathrm{aff}}\mid x,y\in W_{\mathrm{aff}}\text{ and }\sigma\in\Omega\}. (2.9) Shi gave an alternative alcovic description of \mathfrak{C} in terms of a certain hyperplane arrangement known as the Shi arrangement. He showed that \mathcal{A}(\mathfrak{C})=\{\lambda\in E\mid 0\leq\langle\lambda,\alpha\rangle\mbox{ or }\langle\lambda,\alpha\rangle\leq-1\mbox{ for all }\alpha\in\Phi^{+}\}. (2.10) Let \Pi^{+} be the parallelepiped spanned by the fundamental coweights. More precisely, \Pi^{+}=\{\lambda\in E\mid 0\leq\langle\lambda,\alpha\rangle\leq 1,\mbox{ for all }\alpha\in\Delta\}. (2.11) We also define \Pi^{-}=w_{0}(\Pi^{+}) , which is the parallelepiped spanned by the negative fundamental coweights. Both \Pi^{+} and \Pi^{-} are alcoved polytopes (as defined in [ 11 , 12 ] ), meaning they are unions of several alcoves. Specifically, each consists of |W_{\mathrm{f}}|/|\Omega| alcoves, as shown in [ 12 , §4] . We define \mathcal{F}=\mathcal{A}^{-1}(\Pi^{-}) . Note that for all a\in\mathcal{F} we have \ell(w_{0}a)=\ell(w_{0})+\ell(a) , since w_{0}\in W_{\mathrm{f}} and a\in{}_{\mathrm{f}}\mathcal{D} (see [ 3 , Equation (2.12)] ). Therefore, we have w_{0}\cdot a and a^{-1}\cdot w_{0} . A direct computation yields \mathcal{A}^{-1}(\Pi^{+})=\{w_{0}\cdot a\mid a\in\mathcal{F}\}. (2.12) For a\in\mathcal{F} , consider the set \mathfrak{C}(a)=\{a^{-1}\cdot w_{0}\cdot z\mid z\in W_{\mathrm{aff}}\}. (2.13) Note that \mathfrak{C}(\mathrm{id})=W_{\mathrm{aff}}^{+} . A third description of the lowest two-sided cell is in [ 21 , Corollary 1.2] : \mathfrak{C}=\bigsqcup_{\begin{subarray}{c}a\in\mathcal{F}\\ \sigma\in\Omega\end{subarray}}\mathfrak{C}(a)_{\sigma}. (2.14) It is not hard to prove 2 2 2 Here, we slightly abuse notation, as the unions in ( 2.15 ) and ( 2.16 ) are not strictly disjoint. They become disjoint only when considering the interiors of the corresponding sets. that one can tesselate C^{+} using the parallelepiped \Pi^{+} : C^{+}=\mathcal{A}(\mathfrak{C}(\mathrm{id}))=\bigsqcup_{\lambda\in(\Lambda^{\vee})^{+}}\Pi^{+}+\lambda. (2.15) Using ( 2.14 ), we get an alcovic parametrization of \mathfrak{C} : \mathcal{A}(\mathfrak{C})=\bigsqcup_{\begin{subarray}{c}a\in\mathcal{F}\\ \sigma\in\Omega\\ \lambda\in(\Lambda^{\vee})^{+}\end{subarray}}\,\sigma a^{-1}(\Pi^{+}+\lambda). (2.16) We will use this formula to derive an algebraic parametrization of \mathfrak{C} . Recall that for \lambda a dominant coweight, the translation of any alcove by \lambda is still an alcove. Definition 2.4 . For \lambda\in(\Lambda^{\vee})^{+} and a\in\mathcal{F} , we define the element \theta_{a}(\lambda)\in W_{\mathrm{aff}}^{+} as the unique element in W_{\mathrm{aff}} such that \mathcal{A}_{\theta_{a}(\lambda)}=\mathcal{A}_{w_{0}a}+\lambda. (2.17) We remark that the element \theta_{\mathrm{id}}(\lambda) coincides with the element \theta(\lambda) introduced in [ 7 , 14 ] . The elements \theta_{\mathrm{id}}(\lambda) posses the following property, see [ 7 , Lemma 2.4] . Lemma 2.5 . Let \lambda be a dominant coweight and let \tau=\sigma_{\lambda}\in\Omega as in ( 2.5 ). Then \theta_{\mathrm{id}}(\lambda)\in{}^{\mathrm{f}}\mathcal{D}^{\tau} . Furthermore, \{\theta_{\mathrm{id}}(\lambda)\mid\lambda\in(\Lambda^{\vee})^{+}\}=\bigsqcup_{\sigma\in\Omega}{}^{\mathrm{f}}\mathcal{D}^{\sigma}. (2.18) The following lemma gives an equivalent algebraic definition of the elements \theta_{a}(\lambda) . Lemma 2.6 . For \lambda\in(\Lambda^{\vee})^{+} and a\in\mathcal{F} , let \sigma_{\lambda} be as in Equation ( 2.5 ). Then \theta_{a}(\lambda)=t_{\lambda}\,w_{0}\,a\,\sigma_{\lambda}^{-1}, (2.19) where t_{\lambda}\in W_{\mathrm{e}} is the translation by \lambda . Proof. For notational simplicity, we put \sigma=\sigma_{\lambda} . In [ 14 , §2.1] it is shown that t_{\lambda}w_{0}\sigma^{-1}\in W_{\mathrm{aff}} (in that paper this element is called \theta(\lambda) ). This implies that (t_{\lambda}w_{0}\sigma^{-1})(\sigma a\sigma^{-1})\in W_{\mathrm{aff}} . In other words, x:=t_{\lambda}w_{0}a\sigma^{-1}\in W_{\mathrm{aff}} and \mathcal{A}_{x}=x(\mathcal{A}_{\mathrm{id}})=\mathcal{A}_{w_{0}a}+\lambda, (2.20) since \sigma^{-1} fixes the fundamental alcove. Therefore, x=\theta_{a}(\lambda) . ∎ We stress that, for a\in\mathcal{F} and \lambda,\mu\in\Lambda^{\vee} with \lambda,\lambda-\mu\in(\Lambda^{\vee})^{+} , V(\theta_{a}(\lambda-\mu))=V(\theta_{a}(\lambda))-\mu. (2.21) Let \lambda\in(\Lambda^{\vee})^{+} . Note that by Equation ( 2.12 ) and Definition 2.4 , we get \mathcal{A}^{-1}(\Pi^{+}+\lambda)=\{\theta_{a}(\lambda)\mid a\in\mathcal{F}\}. (2.22) Hence, Equation ( 2.16 ) gives an algebraic parametrization of \mathfrak{C} : \mathfrak{C}=\bigsqcup_{\begin{subarray}{c}a\in\mathcal{F}\\ \sigma\in\Omega\\ \lambda\in(\Lambda^{\vee})^{+}\end{subarray}}\,\mathcal{A}^{-1}(\sigma a^{-1}(\Pi^{+}+\lambda))=\bigsqcup_{\begin{subarray}{c}a\in\mathcal{F}\\ \sigma\in\Omega\\ \lambda\in(\Lambda^{\vee})^{+}\end{subarray}}\,\{(a^{-1}\theta_{b}(\lambda))_{\sigma}\mid b\in\mathcal{F}\}. (2.23) That is, there is a bijection \Theta:\mathcal{F}\times(\Lambda^{\vee})^{+}\times\mathcal{F}\times\Omega\xlongrightarrow{\sim}\mathfrak{C} (2.24) given by \Theta(a,\lambda,b,\sigma)=(a^{-1}\theta_{b}(\lambda))_{\sigma}=\sigma a^{-1}\theta_{b}(\lambda)\sigma^{-1} . We can say more about this bijection, but first we need to establish the following lemma. For X,Y\subset W_{\mathrm{aff}} , we write X\cdot Y to denote the set XY and to state that x\cdot y (i.e. \ell(xy)=\ell(x)+\ell(y) ) for every x\in X and y\in Y . Lemma 2.7 . For all \sigma\in\Omega , we have \mathcal{D}_{\sigma}\cdot{}^{\sigma}\mathcal{D} and \mathcal{D}^{\sigma}\cdot{}_{\sigma}\mathcal{D} . Proof. Suppose \mathcal{D}^{\mathrm{f}}\cdot{}_{\mathrm{f}}\mathcal{D} holds. Then (\mathcal{D}^{\mathrm{f}}\cdot{}_{\mathrm{f}}\mathcal{D})^{-1}=({}_{\mathrm{f}}\mathcal{D})^{-1}\cdot(\mathcal{D}^{\mathrm{f}})^{-1}=\mathcal{D}_{\mathrm{f}}\cdot{}^{\mathrm{f}}\mathcal{D} , hence simply conjugating by \sigma yields the desired result. So it suffices to prove \mathcal{D}^{\mathrm{f}}\cdot{}_{\mathrm{f}}\mathcal{D} . Let x\in\mathcal{D}^{\mathrm{f}} and y\in{}_{\mathrm{f}}\mathcal{D} . We prove \ell(x)+\ell(y)\leq\ell(xy) , as the reverse inequality always holds. For u,w\in W_{\mathrm{aff}} , let \mathcal{H}(u,w) be the set of hyperplanes H_{\alpha,k} that separate \mathcal{A}_{u} and \mathcal{A}_{w} . We claim the following: 1. x\mathcal{H}(\mathrm{id},y)=\{xH\mid H\in\mathcal{H}(\mathrm{id},y)\}\subset\mathcal{H}(\mathrm{id},xy) , 2. \mathcal{H}(\mathrm{id},x)\subset\mathcal{H}(\mathrm{id},xy) . Assume the claims and let H\in\mathcal{H}(\mathrm{id},x)\cap\mathcal{H}(x,xy) . Then \mathcal{A}_{\mathrm{id}} and \mathcal{A}_{xy} both lie on the same side of H , but this contradicts Item 2 . Hence the intersection \mathcal{H}(\mathrm{id},x)\cap\mathcal{H}(x,xy) is empty. On the other hand, it is clear that x\mathcal{H}(\mathrm{id},y)\subset\mathcal{H}(x,xy) . Therefore, using Item 1 , we have \left(\mathcal{H}(\mathrm{id},x)\sqcup x\mathcal{H}(\mathrm{id},y)\right)\subset\mathcal{H}(\mathrm{id},xy), (2.25) which implies \ell(x)+\ell(y)\leq\ell(xy) . So it remains to prove the claims. The proof is as follows. 1. Let H\in\mathcal{H}(\mathrm{id},y) . Note that x^{-1}\in{}^{\mathrm{f}}\mathcal{D}=W_{\mathrm{aff}}^{+} and y\in{}_{\mathrm{f}}\mathcal{D}=W_{\mathrm{aff}}^{-} , so we must have that H\in\mathcal{H}(x^{-1},y) . Therefore xH\in\mathcal{H}(\mathrm{id},xy) , as we wanted to show. 2. Let H\in\mathcal{H}(\mathrm{id},x) . Then x^{-1}H\in\mathcal{H}(x^{-1},\mathrm{id}) . Once again, since x^{-1}\in W_{\mathrm{aff}}^{+} and y\in W_{\mathrm{aff}}^{-} , we must have x^{-1}H\in\mathcal{H}(x^{-1},y) and hence H\in\mathcal{H}(\mathrm{id},xy) . This concludes the proof of the lemma. ∎ Now we are in position to describe the length of any element in \mathfrak{C} . Corollary 2.8 . Let \lambda\in(\Lambda^{\vee})^{+} and a,b\in\mathcal{F} . Let \tau=\sigma_{\lambda}\in\Omega as in ( 2.5 ). Then a^{-1}\cdot\theta_{\mathrm{id}}(\lambda)\cdot\tau b\tau^{-1} . Consequently, for any \sigma\in\Omega we have \ell(\Theta(a,\lambda,b,\sigma))=\ell(a)+\ell(b)+\ell(w_{0})+2\langle\lambda,\rho\rangle. (2.26) Proof. On the one hand, since b\in\mathcal{F}\subset W_{\mathrm{aff}}^{-}={}_{\mathrm{f}}\mathcal{D} , then \tau b\tau^{-1}\in({}_{\mathrm{f}}\mathcal{D})_{\tau}={}_{\tau}\mathcal{D} . Also, we know that \theta_{\mathrm{id}}(\lambda)\in{}^{\mathrm{f}}\mathcal{D}^{\tau}\subset\mathcal{D}^{\tau} , by Lemma 2.5 . Hence, Lemma 2.7 implies that \theta_{\mathrm{id}}(\lambda)\cdot\tau b\tau^{-1} . On the other hand, a\in{}_{\mathrm{f}}\mathcal{D} implies that a^{-1}\in\mathcal{D}_{\mathrm{f}} and we know that \theta_{b}(\lambda)\in W_{\mathrm{aff}}^{+}={}^{\mathrm{f}}\mathcal{D} . Applying Lemma 2.7 for ( \sigma=\mathrm{id} ) and using Lemma 2.6 , we deduce that a^{-1}\cdot\theta_{b}(\lambda)=a^{-1}\cdot\theta_{\mathrm{id}}(\lambda)\cdot\tau b\tau^{-1}. (2.27) Finally, ( 2.26 ) follows from Remark 2.2 and the equality \ell(\theta_{\mathrm{id}}(\lambda))=\ell(w_{0})+2\langle\lambda,\rho\rangle (see [ 14 , §2.1] ). ∎ A remarkable property of the parametrization ( 2.24 ) is that it intertwines the dominance order with the Bruhat order, as the following lemma shows. Lemma 2.9 . Fix a,b\in\mathcal{F} and \sigma\in\Omega . Let \lambda,\mu\in(\Lambda^{\vee})^{+} such that \lambda\equiv\mu\mod\mathbb{Z}\Phi^{\vee} . Then \mu\leq\lambda\qquad\mbox{if and only if}\qquad\Theta(a,\mu,b,\sigma)\leq\Theta(a,\lambda,b,\sigma). Proof. It suffices to consider \sigma=\mathrm{id} because if x,y\in W_{\mathrm{aff}} and \sigma\in\Omega one can prove that x\leq y\iff x_{\sigma}\leq y_{\sigma} (see Remark 2.2 ). Let \tau=\sigma_{\lambda}=\sigma_{\mu}\in\Omega as in ( 2.5 ). In the following, we use the fact that for all x,y\in W_{\mathrm{aff}}, if z\in W_{\mathrm{aff}} satisfies that z\cdot x and z\cdot y then x\leq y\iff z\cdot x\leq z\cdot y (2.28) There is a similar equivalence if one multiplies by z on the right. Both equivalences are proved by induction on \ell(z) using the Lifting Property for Coxeter Systems. We have \displaystyle\mu\leq\lambda \displaystyle\iff\theta_{\mathrm{id}}(\mu)\leq\theta_{\mathrm{id}}(\lambda), ( [ 14 , §2.1] ) \displaystyle\iff a^{-1}\cdot\theta_{\mathrm{id}}(\mu)\cdot\tau b\tau^{-1}\leq a^{-1}\cdot\theta_{\mathrm{id}}(\lambda)\cdot\tau b\tau^{-1}, ( Corollary 2.8 and ( 2.28 )) \displaystyle\iff a^{-1}\cdot\theta_{b}(\mu)\leq a^{-1}\cdot\theta_{b}(\lambda), ( Lemma 2.6 ) \displaystyle\iff\Theta(a,\mu,b,\mathrm{id})\leq\Theta(a,\lambda,b,\mathrm{id}), finishing the proof. ∎ For (a,\lambda,b,\sigma)\in\mathcal{F}\times(\Lambda^{\vee})^{+}\times\mathcal{F}\times\Omega , we denote by \mathcal{I}(a,\lambda,b,\sigma) the lower Bruhat interval of \Theta(a,\lambda,b,\sigma)\in\mathfrak{C} . In formulas, \mathcal{I}(a,\lambda,b,\sigma)=\{w\in W_{\mathrm{aff}}\mid w\leq\Theta(a,\lambda,b,\sigma)\}. (2.29) 2.3 The Paper Boat Consider the subposet ((\Lambda^{\vee})^{+},\leq) of the poset of coweights with the dominance order. For \lambda,\mu\in(\Lambda^{\vee})^{+} we write \mu\lessdot\lambda if \lambda covers \mu in ((\Lambda^{\vee})^{+},\leq) . In [ 22 ] , the author gives a complete description of this covering relation. In particular, he shows that \lambda-\mu\in(\Phi^{\vee})^{+} whenever \mu\lessdot\lambda . For \lambda\in(\Lambda^{\vee})^{+} , we define (\Phi^{\vee})^{+}(\lambda)=\{\lambda-\mu\mid\mu\in(\Lambda^{\vee})^{+}\mbox{ and }\mu\lessdot\lambda\}=\{\alpha\in(\Phi^{\vee})^{+}\mid\lambda-\alpha\in(\Lambda^{\vee})^{+}\mbox{ and }\lambda-\alpha\lessdot\lambda\}. (2.30) Remark 2.10 . We emphasize that the symbol \lessdot is reserved for coverings in the subposet of dominant coweights. For example consider type A_{2} , which is self-dual so there is no distinction between roots and coroots and between weights and coweights. We have \mathbf{0}\lessdot\varpi_{1}+\varpi_{2} . This relationship does not hold when considering the full set of weights. Indeed, note that \mathbf{0}<-\varpi_{1}+2\varpi_{2}<\varpi_{1}+\varpi_{2} , which means that \varpi_{1}+\varpi_{2} does not cover \mathbf{0} in the weight poset \Lambda . Definition 2.11 . We define the Paper Boat associated to (a,\lambda,b,\sigma)\in\mathcal{F}\times(\Lambda^{\vee})^{+}\times\mathcal{F}\times\Omega , denoted by PB(a,\lambda,b,\sigma) , as \displaystyle PB(a,\lambda,b,\sigma) \displaystyle=\mathcal{I}(a,\lambda,b,\sigma)\setminus\bigcup_{\alpha\in(\Phi^{\vee})^{+}(\lambda)}\mathcal{I}(a,\lambda-\alpha,b,\sigma) (2.31) \displaystyle=\mathcal{I}(a,\lambda,b,\sigma)\setminus\bigcup_{\mu\lessdot\lambda}\mathcal{I}(a,\mu,b,\sigma). (2.32) For \lambda\in(\Lambda^{\vee})^{+} , we denote by \mathfrak{I}_{\lambda} the ideal generated by \lambda in the subposet of dominant coweights. This ideal can be equivalently described as \mathfrak{I}_{\lambda}=\mathsf{P}(\lambda)\cap C^{+}\cap(\lambda+\mathbb{Z}\Phi^{\vee}), (2.33) where \mathsf{P}(\lambda)=\mathrm{Conv}(W_{\mathrm{f}}\cdot\lambda), (2.34) see [ 7 , Proof of Theorem 3.2] . We have two central conjectures. The first one asserts that each lower Bruhat interval generated by an element in the lowest two-sided cell, is a disjoint union of Paper Boats. Conjecture 2.12 . Let (a,\lambda,b,\sigma)\in\mathcal{F}\times(\Lambda^{\vee})^{+}\times\mathcal{F}\times\Omega . Then \mathcal{I}(a,\lambda,b,\sigma)=\bigsqcup_{\mu\in\mathfrak{I}_{\lambda}}PB(a,\mu,b,\sigma). (2.35) The non-trivial part of Conjecture 2.12 is that the union is actually disjoint. It would imply that if one manages to compute the cardinalities of Paper Boats, then one would be able to compute the sizes of all lower intervals in the lowest two-sided cell. However, a priori, there are infinitely many Paper Boats to compute. Our second conjecture would solve this. Conjecture 2.13 . For all affine Weyl groups there is a partition \mathcal{Z} of (\Lambda^{\vee})^{+} with at most 3^{n} parts satisfying the following property. Fix a,b\in\mathcal{F} , \sigma\in\Omega and Z\in\mathcal{Z} . Then, |PB(a,\lambda,b,\sigma)|=|PB(a,\mu,b,\sigma)|\qquad\mbox{ for all }\lambda,\mu\in Z. (2.36) Suppose \mathcal{Z} is such a partition. As mentioned above, Conjecture 2.12 and Conjecture 2.13 would imply that |\mathcal{I}(a,\lambda,b,\sigma)|=\sum_{Z\in\mathcal{Z}}|\mathfrak{I}_{\lambda}\cap Z|\,|PB(a,Z,b,\sigma)|, (2.37) where |PB(a,Z,b,\sigma)| is the cardinality of |PB(a,\mu,b,\sigma)| for any \mu\in Z . 3  The Paper Boat in the dominant cone of type \widetilde{A} In this section, we prove Conjecture 2.12 and Conjecture 2.13 for affine type A and for all elements in W_{\mathrm{aff}}^{+}=\mathfrak{C}(\mathrm{id}) . Since type A is self-dual, we make no distinction between roots and coroots and between weights and coweights. We use the following realization of the root system. Consider the Euclidean space \mathbb{R}^{n+1} with canonical basis \varepsilon_{1},\ldots,\varepsilon_{n+1} and dot product \langle-,-\rangle . Let E be the hyperplane of vectors whose coordinate sum is zero. The root system of type A_{n} is \Phi=\{\varepsilon_{i}-\varepsilon_{j}\in E\mid 1\leq i,j\leq n+1,\,i\neq j\}. The simple roots are \Delta=\{\alpha_{i}=\varepsilon_{i}-\varepsilon_{i+1}\mid 1\leq i\leq n\} . We stress that in type A the vertices of the fundamental alcove are V(\mathrm{id})=\{\mathbf{0},-\varpi_{1},\ldots,-\varpi_{n}\}. For convenience, we write \varpi_{0}=\mathbf{0} . The main tool we use to establish our results in this section is the following criterion, which allows us to compare elements in the Bruhat order within W_{\mathrm{aff}}^{+} . As mentioned in the introduction, this criterion states that we can compare two elements in the Bruhat order by comparing the vertices of their corresponding alcoves in the dominance order. For the sake of readability, we defer its proof to Section 6 . Proposition 3.1 . Let x,y\in W_{\mathrm{aff}}^{+} . Then x\leq y (in the Bruhat order), if and only if x(-\varpi_{i})\leq y(-\varpi_{i}) for all i\in\{0,1,\ldots,n\} (in the dominance order). Equivalently, x\leq y in the Bruhat order if and only if \nu\leq\mu in the dominance order for all (\nu,\mu)\in V(x)\times V(y) satisfying \nu\equiv\mu\mod\mathbb{Z}\Phi . Recall the parametrization in ( 2.24 ). By definition, we have \Theta(\mathrm{id},\lambda,a,\mathrm{id})=\theta_{a}(\lambda) . The restriction of ( 2.24 ) to W_{\mathrm{aff}}^{+} , gives W_{\mathrm{aff}}^{+}=\mathfrak{C}(\mathrm{id})=\{\theta_{a}(\lambda)\mid a\in\mathcal{F},\lambda\in\Lambda^{+}\}. (3.1) Thus, for simplicity, for \lambda\in\Lambda^{+} and a\in\mathcal{F} we introduce the notation \displaystyle\mathcal{I}_{a}(\lambda) \displaystyle=\mathcal{I}(\mathrm{id},\lambda,a,\mathrm{id})=\{w\in W_{\mathrm{aff}}\mid w\leq\theta_{a}(\lambda)\}, (3.2) \displaystyle PB_{a}(\lambda) \displaystyle=PB(\mathrm{id},\lambda,a,\mathrm{id})=\mathcal{I}_{a}(\lambda)\setminus\bigcup_{\alpha\in\Phi^{+}(\lambda)}\mathcal{I}_{a}(\lambda-\alpha), (3.3) where the set \Phi^{+}(\lambda)=\{\alpha\in\Phi^{+}\mid\lambda-\alpha\in\Lambda^{+}\mbox{ and }\lambda-\alpha\lessdot\lambda\} was introduced in ( 2.30 ). That set was described for arbitrary root systems in [ 22 ] . In type A , the following explicit description is given. If \lambda\in\Lambda^{+} , then \alpha\in\Phi^{+}(\lambda) if and only if one of the following conditions hold. 1. \alpha\in\Delta and \langle\lambda,\alpha\rangle\geq 2 . 2. \alpha=\alpha_{i,j}=\alpha_{i}+\alpha_{i+1}+\ldots+\alpha_{j} , \langle\lambda,\alpha_{i}\rangle=\langle\lambda,\alpha_{j}\rangle=1 and \langle\lambda,\alpha_{k}\rangle=0 for all i-\eta_{\alpha,v} for some \alpha\in\Delta_{v} . Let 0\leq i\leq n and note that \langle\gamma+v_{i},\varpi_{\alpha}\rangle>-\eta_{\alpha,v}+\langle v_{i},\varpi_{\alpha}\rangle\geq-\eta_{\alpha,v}+\eta_{\alpha,v}=0. (4.10) It follows that \langle\gamma-\alpha+v_{i},\varpi_{\alpha}\rangle\geq 0 . This is the same inequality as the one obtained in ( 4.8 ). Therefore, we reach the same contradiction and this proves Item 2 . We have proved that \gamma=\kappa_{v} . Therefore, \phi is bijective as we wanted to show. ∎ Example 4.2 . In Figure 4 , we graphically illustrate the bijection \phi occurring in the proof of Proposition 4.1 for type \widetilde{A}_{2} . Let a=s_{0} . In Figure 4(a) (resp. Figure 4(b) ), the green triangles represent the set PB_{a}^{+}(2\varpi_{1}+2\varpi_{2}) (resp. PB_{a}^{+}(3\varpi_{1}+2\varpi_{2}) ) and the corresponding element \theta_{a}(2\varpi_{1}+2\varpi_{2}) (resp. \theta_{a}(3\varpi_{1}+2\varpi_{2}) ) is represented by the green triangle marked with (resp. ). (a) \lambda=2\varpi_{1}+2\varpi_{2} . (b) \lambda=3\varpi_{1}+2\varpi_{2} . Figure 4 : The bijection \phi:W_{\mathrm{f}}\longrightarrow PB_{a}^{+}(\lambda) , for \lambda\in Z(2,\ldots,2) . The set PB_{a}^{+}(\lambda) is illustrated in green. The elements of W_{\mathrm{f}} are labeled as follows: \hbox to6.06pt{\vbox to6.06pt{\pgfpicture\makeatletter\hbox{\hskip 3.02861pt\lower-3.02861pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 3.91 0 C 3.91 2.16 2.16 3.91 0 3.91 C -2.16 3.91 -3.91 2.16 -3.91 0 C -3.91 -2.16 -2.16 -3.91 0 -3.91 C 2.16 -3.91 3.91 -2.16 3.91 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 0 0)} \pgfsys@hbox{58}\lxSVG@closescope }}} \lxSVG@closescope }}} } \lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}=e,\qquad\hbox to6.06pt{\vbox to6.06pt{\pgfpicture\makeatletter\hbox{\hskip 3.02861pt\lower-3.02861pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 3.91 0 C 3.91 2.16 2.16 3.91 0 3.91 C -2.16 3.91 -3.91 2.16 -3.91 0 C -3.91 -2.16 -2.16 -3.91 0 -3.91 C 2.16 -3.91 3.91 -2.16 3.91 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 0 0)} \pgfsys@hbox{58}\lxSVG@closescope }}} \lxSVG@closescope }}} } \lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}=s_{1},\qquad\hbox to6.06pt{\vbox to6.06pt{\pgfpicture\makeatletter\hbox{\hskip 3.02861pt\lower-3.02861pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 3.91 0 C 3.91 2.16 2.16 3.91 0 3.91 C -2.16 3.91 -3.91 2.16 -3.91 0 C -3.91 -2.16 -2.16 -3.91 0 -3.91 C 2.16 -3.91 3.91 -2.16 3.91 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 0 0)} \pgfsys@hbox{58}\lxSVG@closescope }}} \lxSVG@closescope }}} } \lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}=s_{2},\qquad\hbox to6.06pt{\vbox to6.06pt{\pgfpicture\makeatletter\hbox{\hskip 3.02861pt\lower-3.02861pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 3.91 0 C 3.91 2.16 2.16 3.91 0 3.91 C -2.16 3.91 -3.91 2.16 -3.91 0 C -3.91 -2.16 -2.16 -3.91 0 -3.91 C 2.16 -3.91 3.91 -2.16 3.91 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 0 0)} \pgfsys@hbox{58}\lxSVG@closescope }}} \lxSVG@closescope }}} } \lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}=s_{1}s_{2},\qquad\hbox to6.06pt{\vbox to6.06pt{\pgfpicture\makeatletter\hbox{\hskip 3.02861pt\lower-3.02861pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 3.91 0 C 3.91 2.16 2.16 3.91 0 3.91 C -2.16 3.91 -3.91 2.16 -3.91 0 C -3.91 -2.16 -2.16 -3.91 0 -3.91 C 2.16 -3.91 3.91 -2.16 3.91 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 0 0)} \pgfsys@hbox{58}\lxSVG@closescope }}} \lxSVG@closescope }}} } \lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}=s_{2}s_{1},\qquad\hbox to6.06pt{\vbox to6.06pt{\pgfpicture\makeatletter\hbox{\hskip 3.02861pt\lower-3.02861pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \lxSVG@begingroup@{_scopebegin=1} \lxSVG@closescope \hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 3.91 0 C 3.91 2.16 2.16 3.91 0 3.91 C -2.16 3.91 -3.91 2.16 -3.91 0 C -3.91 -2.16 -2.16 -3.91 0 -3.91 C 2.16 -3.91 3.91 -2.16 3.91 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 0 0)} \pgfsys@hbox{58}\lxSVG@closescope }}} \lxSVG@closescope }}} } \lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}=s_{1}s_{2}s_{1}. The bijection in the proof of Proposition 4.1 goes as follows. For v\in W_{\mathrm{f}} we first translate the corresponding alcove by \mu=3\varpi_{1}+3\varpi_{2} . Then we translate by -\kappa_{v} to obtain the green triangle in PB_{a}^{+}(\lambda) . 4.2 Paper boats in terms of lower intervals In this section we use the principle of inclusion-exclusion to obtain a formula for the size of a Paper Boat in terms of lower Bruhat intervals. Recall the weight poset \Lambda and its join ( 3.7 ) and meet ( 3.6 ) operators. For J\subset\Phi , we define \displaystyle\vee_{J}=\bigvee_{\alpha\in J}\alpha . Proposition 4.3 . Let a\in\mathcal{F} and \lambda\in\Lambda^{+} . Then c_{a}(\lambda)=\sum_{J\subset\Phi^{+}(\lambda)}(-1)^{|J|}\,\left|\,\mathcal{I}_{a}(\lambda-\vee_{J})\,\right|. (4.11) In the proof of Proposition 4.3 , we will make use of the following lemma. Lemma 4.4 . Let \lambda\in\Lambda^{+} , a\in\mathcal{F} and \emptyset\neq J\subset\Phi^{+}(\lambda) . Then, \bigcap_{\alpha\in J}\mathcal{I}_{a}(\lambda-\alpha)=\mathcal{I}_{a}\left({\bigwedge_{\alpha\in J}}(\lambda-\alpha)\right)=\mathcal{I}_{a}(\lambda-\vee_{J}). (4.12) Proof. We note that by Equations ( 3.7 ), ( 3.6 ) and the fact that \wedge^{+} is the restriction of \wedge to the dominant weights, we have {\bigwedge_{\alpha\in J}}^{+}\left(\lambda-\alpha\right)=\bigwedge_{\alpha\in J}\left(\lambda-\alpha\right)=\lambda-\vee_{J}. (4.13) Therefore, \bigwedge_{\alpha\in J}\left(\lambda-\alpha\right)=\lambda-\vee_{J} is a dominant weight, so that ( 4.12 ) makes sense. The first equality in Equation 4.12 is a direct application of Lemma 3.7 , whereas the second equality follows from ( 4.13 ). ∎ Proof of Proposition 4.3 . Note that \displaystyle-\left|\bigcup_{\alpha\in\Phi^{+}(\lambda)}\mathcal{I}_{a}(\lambda-\alpha)\right|\displaystyle=\sum_{\emptyset\neq J\subset\Phi^{+}(\lambda)}(-1)^{|J|}\left|\bigcap_{\alpha\in J}\mathcal{I}_{a}(\lambda-\alpha)\right|\displaystyle=\sum_{\emptyset\neq J\subset\Phi^{+}(\lambda)}(-1)^{|J|}\left|\mathcal{I}_{a}(\lambda-\vee_{J})\right|, (4.14) where the first equality follows from the inclusion-exclusion principle and the second one is implied by Lemma 4.4 . By the definition of c_{a}(\lambda) , ( 4.14 ) implies ( 4.11 ). ∎ Example 4.5 . Using Proposition 4.3 , we compute c_{a}(\lambda) for all \lambda\in\Lambda^{+} in the case of the affine Weyl group of type A_{3} . Since the set \mathcal{Z} ( Definition 3.11 ) is a partition of \Lambda^{+} and the values c_{a}(\lambda) remain constant within each zone Z\in\mathcal{Z} ( Theorem 3.13 ), it suffices to compute c_{a}(\lambda) for a single representative \lambda_{Z} per zone Z . By definition of c_{a}(\lambda) , we must also compute the set \Phi^{+}(\lambda) . As before, it is sufficient to determine \Phi^{+}(\lambda_{Z}) for each Z\in\mathcal{Z} , since the sets \Phi^{+}(\lambda) are constant within zones ( Remark 3.12 ). For the zone Z=Z(i_{1},i_{2},i_{3}) , we set \lambda_{Z}=(i_{1},i_{2},i_{3})=i_{1}\varpi_{1}+i_{2}\varpi_{2}+i_{3}\varpi_{3} . The sets \Phi^{+}(\lambda) are presented in the columns of Table 1 , while the values c_{a}^{+}(\lambda) are displayed in Table 2 . Finally, we emphasize that the values of c_{a}(\lambda) are obtained by multiplying c_{a}^{+}(\lambda) by |W_{\mathrm{f}}|=24 ( Corollary 3.6 ). i_{1} 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 i_{2} 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 i_{3} 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 \alpha_{1} \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \alpha_{2} \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \alpha_{3} \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet \alpha_{12} \bullet \bullet \bullet \alpha_{23} \bullet \bullet \bullet \alpha_{13} \bullet Table 1 : The sets \Phi^{+}(i_{1},i_{2},i_{3}) . i_{1} 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 i_{2} 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 i_{3} 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 a_{1} 1 4 4 6 12 12 6 12 12 4 12 12 12 24 24 12 24 24 4 12 12 12 24 24 12 24 24 a_{2} 2 7 6 10 17 16 8 15 14 7 18 16 17 30 28 15 28 26 6 16 14 16 28 26 14 26 24 a_{3} 3 10 9 13 22 22 9 18 18 9 22 21 18 33 33 15 30 30 6 16 15 15 27 27 12 24 24 a_{4} 3 9 6 13 18 15 9 15 12 10 22 16 22 33 27 18 30 24 9 21 15 22 33 27 18 30 24 a_{5} 5 14 10 18 24 22 9 16 14 14 29 24 24 37 34 16 29 26 10 24 20 22 34 32 14 26 24 a_{6} 8 20 12 26 31 26 14 23 18 20 36 26 31 44 36 23 38 30 12 26 18 26 36 30 18 30 24 Table 2 : Values of c_{a}^{+}(i_{1},i_{2},i_{3}) . We obtain the following corollary. Corollary 4.6 . Let a\in\mathcal{F} and F_{a}:\Lambda^{+}\rightarrow\mathbb{R} be a function. Suppose that for all \lambda\in\Lambda^{+} , c_{a}(\lambda)=\sum_{J\subset\Phi^{+}(\lambda)}(-1)^{|J|}F_{a}(\lambda-\vee_{J}). (4.15) Then, F_{a}(\lambda)=|\mathcal{I}_{a}(\lambda)| for all \lambda\in\Lambda^{+} . Proof. We proceed by induction on the dominance order on \Lambda^{+} . The minimal elements in this order are \varpi_{0},\varpi_{1},\dots,\varpi_{n} . For these elements, we have \Phi^{+}(\varpi_{i})=\emptyset . Therefore, by the definition of the Paper Boat, we obtain PB_{a}(\varpi_{i})=\mathcal{I}_{a}(\varpi_{i}) . This implies that c_{a}(\varpi_{i})=|\mathcal{I}_{a}(\varpi_{i})| . On the other hand, by ( 4.15 ), we also have c_{a}(\varpi_{i})=F_{a}(\varpi_{i}) . Thus, we conclude that F_{a}(\varpi_{i})=|\mathcal{I}_{a}(\varpi_{i})| , which proves the result for the minimal elements in the dominance order. Now, let \lambda\in\Lambda^{+} and assume that F_{a}(\mu)=|\mathcal{I}_{a}(\mu)| for all \mu\in\Lambda^{+} such that \mu<\lambda . By combining Proposition 4.3 , our inductive hypothesis and ( 4.15 ), we get \begin{array}[]{rl}|\mathcal{I}_{a}(\lambda)|&\displaystyle=c_{a}(\lambda)-\sum_{\emptyset\neq J\subset\Phi^{+}(\lambda)}(-1)^{|J|}|\mathcal{I}_{a}(\lambda-\vee_{J})|\\ &\displaystyle=c_{a}(\lambda)-\sum_{\emptyset\neq J\subset\Phi^{+}(\lambda)}(-1)^{|J|}F_{a}(\lambda-\vee_{J})\\ &=F_{a}(\lambda).\end{array} (4.16) This completes the proof by induction. ∎ 4.3 Geometric formula in \widetilde{A_{3}} We end this section by applying Corollary 4.6 to prove that, for a fixed a\in\mathcal{F} , the function |\mathcal{I}_{a}(\lambda)| is a polynomial in \lambda for the affine Weyl group of type A_{3} . These polynomials are explicitly given in Theorem 4.8 and are in fact geometric polynomials. For the rest of this section we work in type A_{3} . We begin by noticing that \mathcal{F}=\{\mathrm{id},s_{0},s_{0}s_{1},s_{0}s_{3},s_{0}s_{1}s_{3},s_{0}s_{1}s_{3}s_{2}\}. (4.17) For a=\mathrm{id} , we proved in [ 7 , Theorem B] that |\mathcal{I}_{a}(\lambda)| is a linear combination of the volumes of the faces of the orbit polytope \mathsf{P}(\lambda) ( 2.34 ). In this paper we use the usual Euclidean volume, for more details we refer to [ 7 , §2.3] . Definition 4.7 . Recall that (W_{\mathrm{f}},S_{\mathrm{f}}) is a Coxeter system. For J\subset S_{\mathrm{f}} , let W_{J} be the parabolic subgroup generated by J . The faces of P(\lambda) are given by F_{J}(\lambda)=\text{Conv}(W_{J}\cdot\lambda) . We write V_{J}(\lambda):=\text{Vol}(F_{J}(\lambda)). With this definition [ 7 , Theorem B] establishes that there exist unique \mu_{J}\in\mathbb{R} such that |\mathcal{I}_{\mathrm{id}}(\lambda)|=\sum_{J\subset S_{\mathrm{f}}}\mu_{J}V_{J}(\lambda), (4.18) for all \lambda\in\Lambda^{+} . We stress that the numbers \mu_{J} do not depend on \lambda . This is called the Geometric Formula in [ 7 ] and it holds for arbitrary affine Weyl groups. It is a fact [ 7 , Remark 4.6] that there is a polynomial p_{J}\in\mathbb{R}[x,y,z] such that V_{J}(x\varpi_{1}+y\varpi_{2}+z\varpi_{3})=p_{J}(x,y,z),\quad\mbox{for all }x,y,z\in\mathbb{Z}_{\geq 0}. Let us write (x,y,z):=x\varpi_{1}+y\varpi_{2}+z\varpi_{3} . With this notation, ( 4.18 ) becomes |\mathcal{I}_{\mathrm{id}}(x,y,z)|=\sum_{J\subset S_{\mathrm{f}}}\mu_{J}V_{J}(x,y,z), (4.19) and we see that |\mathcal{I}_{\mathrm{id}}(x,y,z)| is a polynomial in \mathbb{R}[x,y,z] . The following theorem, a generalization of ( 4.19 ) to all elements of \mathcal{F} , establishes the polynomiality for the cardinality of all lower Bruhat intervals for dominant elements. It precisely answers the question of counting the sets \{u\in W_{\mathrm{aff}}\mid u\leq w\} , for all w\in W_{\mathrm{aff}}^{+} . We use the identification S_{\mathrm{f}}=\{s_{1},s_{2},s_{3}\} with the set \{1,2,3\} , and we enumerate \mathcal{F} as a_{1}=\mathrm{id},\quad a_{2}=s_{0},\quad a_{3}=s_{0}s_{1},\quad a_{4}=s_{0}s_{3},\quad a_{5}=s_{0}s_{1}s_{3},\quad a_{6}=s_{0}s_{1}s_{3}s_{2}. (4.20) Theorem 4.8 . Fix any a\in\mathcal{F} . Then for all J\subset S_{\mathrm{f}} , there exist unique coefficients \mu_{J,a}\in\mathbb{R} such that |\mathcal{I}_{a}(x,y,z)|=\sum_{J\subset S_{\mathrm{f}}}\mu_{J,a}V_{J}(x,y,z). (4.21) Explicitly, the coefficients \mu_{J,a} are given in Table 3 , and the polynomials V_{J}(x,y,z) are given in Equation 4.22 : \mu_{\emptyset,a} \mu_{\{1\},a} \mu_{\{2\},a} \mu_{\{3\},a} \mu_{\{1,2\},a} \mu_{\{1,3\},a} \mu_{\{2,3\},a} \mu_{\{1,2,3\},a} a_{1} 24 22\,\sqrt{2} 28\,\sqrt{2} 22\,\sqrt{2} 16\,\sqrt{3} 36 16\,\sqrt{3} 12 a_{2} 48 40\,\sqrt{2} 52\,\sqrt{2} 40\,\sqrt{2} 24\,\sqrt{3} 60 24\,\sqrt{3} 12 a_{3} 72 52\,\sqrt{2} 70\,\sqrt{2} 58\,\sqrt{2} 24\,\sqrt{3} 72 32\,\sqrt{3} 12 a_{4} 72 58\,\sqrt{2} 70\,\sqrt{2} 52\,\sqrt{2} 32\,\sqrt{3} 72 24\,\sqrt{3} 12 a_{5} 120 82\,\sqrt{2} 100\,\sqrt{2} 82\,\sqrt{2} 32\,\sqrt{3} 96 32\,\sqrt{3} 12 a_{6} 192 112\,\sqrt{2} 148\,\sqrt{2} 112\,\sqrt{2} 40\,\sqrt{3} 108 40\,\sqrt{3} 12 Table 3 : \begin{array}[]{l}V_{\emptyset}(x,y,z)=1,\hskip 60.00009ptV_{\{1\}}(x,y,z)=\sqrt{2}x,\hskip 60.00009ptV_{\{2\}}(x,y,z)=\sqrt{2}y,\\[10.00002pt] V_{\{3\}}(x,y,z)=\sqrt{2}z,\hskip 100.00015ptV_{\{1,2\}}(x,y,z)=\tfrac{\sqrt{3}}{2}x^{2}+2\sqrt{3}xy+\tfrac{\sqrt{3}}{2}y^{2},\\[10.00002pt] V_{\{1,3\}}(x,y,z)=2xz,\hskip 97.0001ptV_{\{2,3\}}(x,y,z)=\tfrac{\sqrt{3}}{2}y^{2}+2\sqrt{3}yz+\tfrac{\sqrt{3}}{2}z^{2},\\[10.00002pt] V_{\{1,2,3\}}(x,y,z)=\tfrac{1}{3}x^{3}+2x^{2}y+4xy^{2}+\tfrac{4}{3}y^{3}+3x^{2}z+12xyz+4y^{2}z+3xz^{2}+2yz^{2}+\tfrac{1}{3}z^{3}.\end{array} (4.22) Proof. For a fixed element a\in\mathcal{F} , we define the function F_{a}:\Lambda^{+}\rightarrow\mathbb{R} by F_{a}(\lambda)=\sum_{J\subset\Phi^{+}(\lambda)}\mu_{J,a}V_{J}(x,y,z). (4.23) Our goal is to verify that F_{a} satisfies ( 4.15 ) for all \lambda\in\Lambda^{+} . Since the set of zones \mathcal{Z} ( Definition 3.11 ) partitions \Lambda^{+} , it suffices to verify ( 4.15 ) within each individual zone Z\in\mathcal{Z} . By Theorem 3.13 and Remark 3.12 , the coefficients c_{a}(\lambda) and the sets \Phi^{+}(\lambda) remain constant for all \mu in a given zone Z . Consequently, for each zone Z(i_{1},i_{2},i_{3})\in\mathcal{Z} , we must confirm the validity of the condition c_{a}(i_{1},i_{2},i_{3})=\sum_{J\subset\Phi^{+}(i_{1},i_{2},i_{3})}(-1)^{|J|}F_{a}((x,y,z)-\vee_{J}), (4.24) for all \lambda\in Z(i_{1},i_{2},i_{3}) , where \lambda=(x,y,z)=x\varpi_{1}+y\varpi_{2}+z\varpi_{3} . We perform these verifications using SageMath together with Tables 1 and 2 . Below, we provide illustrative computations for three zones: 1. Zone \mathbf{Z(2,2,2)} : • Using Table 1 , we find that \Phi^{+}(2,2,2)=\{\alpha_{1},\alpha_{2},\alpha_{3}\} . • From Table 2 , we obtain c_{a}(2,2,2)=24\cdot c_{a}^{+}(2,2,2)=24^{2}=576 , which does not depend on the choice of a\in\mathcal{F} (as predicted by Proposition 4.1 ). • Substituting into ( 4.24 ), we get \begin{array}[]{ll}576=&F(x,y,z)\\ &-F_{a}(x-2,y+1,z)-F_{a}(x+1,y-2,z+1)-F_{a}(x,y+1,z-2)\\ &+F_{a}(x-1,y-1,z+1)+F_{a}(x-2,y+2,z-2)+F_{a}(x+1,y-1,z-1)\\ &-F_{a}(x-1,y,z-1).\end{array} (4.25) Each term in the right-hand side of ( 4.25 ) is obtained computing the join of a subset of \Phi^{+}(2,2,2) . For instance, if J=\{\alpha_{1},\alpha_{2}\} we have \vee_{J}=\alpha_{1}+\alpha_{2}=(1,1,-1) , leading to (-1)^{|J|}F_{a}((x,y,z)-\vee_{J})=F_{a}(x-1,y-1,z+1). (4.26) The other terms are computed in a similar fashion. We have that ( 4.25 ) simplifies to 576=48\mu_{\{1,2,3\},a}, and consulting Table 3 , the equality holds for all a\in\mathcal{F} . 2. Zone \mathbf{Z(1,1,2)} : • Here, \Phi^{+}(1,1,2)=\{\alpha_{3},\alpha_{12}\} . • For a=a_{5}=s_{0}s_{1}s_{3} , we compute c_{a_{5}}(1,1,2)=24\cdot c_{a_{5}}^{+}(1,1,2)=24\cdot 34=816 . • Substituting into ( 4.24 ), we obtain the relation 816=F_{a_{5}}(1,1,z)-F_{a_{5}}(1,2,z-2)-F_{a_{5}}(0,0,z+1)+F_{a_{5}}(0,1,z-1), (4.27) which simplifies to 816=-3\sqrt{3}\mu_{\{1,2\},a_{5}}+4\mu_{\{1,3\},a_{5}}+3\sqrt{3}\mu_{\{2,3\},a_{5}}+36\mu_{\{1,2,3\},a_{5}}. (4.28) Using Table 3 , we confirm this identity. 3. Zone \mathbf{Z(1,1,1)} : • We find \Phi^{+}(1,1,1)=\{\alpha_{12},\alpha_{23}\} . We note that J=\Phi^{+}(1,1,1) gives \vee_{J}=\alpha_{13}=(1,0,1) , which is different from \alpha_{12}+\alpha_{23} . • With a=a_{2}=s_{0} , the condition to verify is 720=F_{a_{2}}(1,1,1)-F_{a_{2}}(0,0,2)-F_{a_{2}}(2,0,0)+F_{a_{2}}(0,1,0). (4.29) After simplifying, we get the equivalent condition \displaystyle\begin{split}720=&-\sqrt{2}\mu_{\{1\},a_{2}}+\tfrac{3}{2}\sqrt{3}\mu_{\{1,2\},a_{2}}+2\sqrt{2}\mu_{\{2\},a_{2}}+\tfrac{3}{2}\sqrt{3}\mu_{\{2,3\},a_{2}}\\ &-\sqrt{2}\mu_{\{3\},a_{2}}+28\mu_{\{1,2,3\},a_{2}}+2\mu_{\{1,3\},a_{5}}.\end{split} (4.30) Substituting values from Table 3 , the equality is verified. By repeating similar calculations for each zone Z\in\mathcal{Z} , we confirm that F_{a} satisfies ( 4.24 ) for all \lambda\in\Lambda^{+} . Thus, by Corollary 4.6 , we conclude that F_{a}(\lambda)=|\mathcal{I}_{a}(\lambda)| for all \lambda\in\Lambda^{+} . ∎ Remark 4.9 . We stress that, for a\in\mathcal{F} , Theorem 4.8 implies that the cardinality of \mathcal{I}_{a}(x,y,z) is a polynomial in \mathbb{R}[x,y,z] of degree 3 . Furthermore, Table 3 shows that that the homogeneous part of degree 3 of this polynomial, is \mu_{\{1,2,3\},a}\cdot V_{\{1,2,3\}}(x,y,z)=12\cdot V_{\{1,2,3\}}(x,y,z), which does not depend on a . Heuristically, we view this phenomenon as the permutohedron \mathsf{P}(\lambda) serving as an approximation of the lower intervals \mathcal{I}_{a}(\lambda) . In Theorem 5.13 we will prove this for type \widetilde{A}_{n} in general. After extensive computations in types \widetilde{A_{3}} and \widetilde{B_{3}} , we conjecture a generalization of Theorem 4.8 to all affine Weyl groups and to the whole lowest two-sided cell \mathfrak{C} . Conjecture 4.10 . Let \Phi be any irreducible root system, and recall the parametrization \Theta:\mathcal{F}\times(\Lambda^{\vee})^{+}\times\mathcal{F}\times\Omega\xlongrightarrow{\sim}\mathfrak{C}. (4.31) Fix a,b\in\mathcal{F} and \sigma\in\Omega . Then there exist unique coefficients \mu_{J,a,b,\sigma}\in\mathbb{R} such that |\mathcal{I}(a,\lambda,b,\sigma)|=\sum_{J\subset S_{\mathrm{f}}}\mu_{J,a,b,\sigma}V_{J}(\lambda), (4.32) for all \lambda\in(\Lambda^{\vee})^{+} . By Remark 2.2 the choice of \sigma is superfluous, i.e., if the conjecture holds for \sigma=\mathrm{id} then it holds for all \sigma . In this case we would have \mu_{J,a,b,\sigma}=\mu_{J,a,b,\mathrm{id}} . 5  Lattice points in polyhedra In this section we work entirely in type \widetilde{A}_{n} . As before we use the standard label of the simple roots \Delta=\{\alpha_{1},\dots,\alpha_{n}\} with fundamental weigths \{\varpi_{1},\dots,\varpi_{n}\} . For notation we denote the set \{1,\dots,k\}=[k] for any natural number k . We begin by rewriting the formula from Corollary 3.14 in terms of discrete geometry. Recall the definition of \mathsf{P}(\lambda) in ( 2.34 ). We had previously defined certain discrete zones in Definition 3.11 , and now we define a continuous version. For \boldsymbol{i}\in\{0,1,2\}^{n} we define Z_{\mathbb{R}}(\boldsymbol{i})=\{x\in C^{+}\mid\langle x,\alpha_{j}\rangle=i_{j}\mbox{ if }i_{j}=0,1,\mbox{ and }\langle x,\alpha_{j}\rangle\geq 2\mbox{ if }\ i_{j}=2\}. (5.1) Definition 5.1 . Let \lambda\in C^{+} be an element in the dominant chamber. We define the following polyhedra related to \mathsf{P}(\lambda) . \displaystyle\mathsf{P}^{+}(\lambda) \displaystyle=\mathsf{P}(\lambda)\cap C^{+}, (5.2) \displaystyle\mathsf{P}_{\boldsymbol{i}}^{+}(\lambda) \displaystyle=\mathsf{P}^{+}(\lambda)\cap Z_{\mathbb{R}}(\boldsymbol{i}),\,\forall\boldsymbol{i}\in\left\{0,1,2\right\}^{n}. (5.3) With these definitions we can combine ( 2.33 ) and ( 3.17 ) to obtain |\mathcal{I}_{a}(\lambda)|=\sum_{\boldsymbol{i}\in\left\{0,1,2\right\}^{n}}c_{a}(\boldsymbol{i})|\mathsf{P}_{\boldsymbol{i}}^{+}(\lambda)\cap\left(\mathbb{Z}\Phi+\lambda\right)|, (5.4) for a\in\mathcal{F} and \lambda\in\Lambda^{+} a dominant weight. Equation 5.4 is the key connection between the Bruhat order and polyhedral combinatorics. Counting lattice points in polyhedra is a classic problem and it is well known that such problem exhibits a polynomial behavior [ 1 ] . There are however some technical details that we must address to properly use the available results. 5.1 Vertices of \mathsf{P}^{+}(\lambda) We begin by describing how the vertices of \mathsf{P}^{+}(\lambda) depends on \lambda . Proposition 5.2 . Let \lambda\in C^{+} be any element in the dominant region. The point \mathbf{0} is a vertex of \mathsf{P}^{+}(\lambda) . For every other vertex \sum_{i=1}^{n}a_{i}\varpi_{i} we have that each a_{i} is a \mathbb{Z}\left[\frac{1}{(n+1)!}\right] -linear combination of \lambda_{1},\dots,\lambda_{n} , where \lambda=\sum_{i=1}^{n}\lambda_{i}\varpi_{i} . Proof. The inequality description of \mathsf{P}^{+}(\lambda) has the following form \left\{x\in E\,\middle|\begin{array}[]{rll}\langle\varpi_{i},x\rangle&\leq\langle\varpi_{i},\lambda\rangle,&i\in[n],\\ \langle\alpha_{i},x\rangle&\geq 0,&i\in[n],\\ \end{array}\right\}. (5.5) Every vertex is the unique solution to a linear subsystem of \begin{array}[]{rll}\langle\varpi_{i},x\rangle&=\langle\varpi_{i},\lambda\rangle,&i\in[n],\\ \langle\alpha_{i},x\rangle&=0,&i\in[n],\\ \end{array} (5.6) consisting of of n equations such that the set of normal 3 3 3 For a linear equality of the form \langle\mathbf{a},x\rangle=b , we call the vector \mathbf{a} the normal vector. vectors are linearly independent, see [ 1 , Lemma 4.9] . For example, the point \mathbf{0} is the unique solution to the subsystem consisting of the simple roots. Since \mathbf{0}\in\mathsf{P}^{+}(\lambda) , then it is a vertex. In general, writing x=\sum_{i}x_{i}\varpi_{i} we transform the system ( 5.6 ) into a matrix equation of the form \mathbf{C}x=b(\lambda) , where b(\lambda) is a column vector such that each entry is a \mathbb{Z}[\frac{1}{n+1}] -linear in \lambda_{1},\dots,\lambda_{n} , since (n+1)\langle\varpi_{i},\varpi_{j}\rangle\in\mathbb{Z} for every pair i,j . The matrix \mathbf{C} has to be invertible and by Cramer’s rule we have that the entries of the unique solution are a \mathbb{Z}[\frac{1}{D}] -linear combination of the entries of b(\lambda) , where D:=\det(\mathbf{C}) . By Lemma 5.3 the factor \frac{1}{n+1} cancels and we get that each coordinate is indeed a \mathbb{Z}\left[\frac{1}{(n+1)!}\right] -linear combination of \lambda_{1},\dots,\lambda_{n} . ∎ Lemma 5.3 . Consider the 2n\times n matrix \mathbf{M}_{n} obtained by concatenating vertically the inverse of the Cartan matrix and the and the identity matrix \mathbf{I}_{n} . Then every maximal minor of \mathbf{M}_{n} is either 0 or k/(n+1) where k divides (n+1)! . Proof. The set of maximal minors of \mathbf{M}_{n} coincides with the set of all minors of the inverse of the Cartan matrix \mathbf{A}_{n}^{-1} . The Jacobi’s complementary minor formula [ 6 , Lemma A.1] states that \det\mathbf{N}[I,J]=|(\det(\mathbf{N}))(\det\mathbf{N}^{-1}[I^{c},J^{c}])|, (5.7) where \mathbf{N}[I,J] is the submatrix of \mathbf{N} obtained by restricting to rows indexed by I and columns indexed by J . Applying ( 5.7 ) to the inverse Cartan matrix we obtain that the set of all (absolute values of) minors are the same as those of the Cartan matrix multiplied by 1/(n+1) , since it is well-known that \det(\mathbf{A}_{n})=n+1 . The conclusion follows from Proposition 5.4 . ∎ Proposition 5.4 . Let \mathbf{A}_{n} be the Cartan matrix of type A_{n} and let \mathbf{B} be a submatrix of \mathbf{A}_{n} obtained by eliminating some rows and the same number of columns. Then, either \det(\mathbf{B})=0 or there exists a partition \mu=(\mu_{1},\ldots,\mu_{\ell}) of 0\leq m\leq n with \ell\leq n+1-m parts such that |\det(\mathbf{B})|=(\mu_{1}+1)(\mu_{2}+1)\cdots(\mu_{\ell}+1). (5.8) In particular, it divides (n+1)! . Proof. Let k be the size of the square matrix \mathbf{B} . We proceed by induction on k . If k=1 then |\det(\mathbf{B})|=0,1, or 2 . If |\det(\mathbf{B})|=1 we take \mu as the empty partition of 0 . Similarly, if |\det(\mathbf{B})|=2 we take \mu=(1) . This proves the base case. We now fix 2\leq k\leq n and suppose that ( 5.8 ) holds for matrices of size less than k . We first suppose that the set of rows and columns eliminated from \mathbf{A}_{n} to obtain \mathbf{B} is the same. It follows that \mathbf{B} is a diagonal block matrix, where each block is a Cartan matrix of type \mathbf{A}_{j} for some j\leq k . Let \mu=(\mu_{1},\ldots,\mu_{\ell}) be the sizes of each block ordered in decreasing order (here we admit repetitions). Since the determinant of a Cartan matrix of type \mathbf{A}_{j} is j+1 we have that \mu satisfies ( 5.8 ). This proves the proposition in this case. Now let i_{1}r separately. ∎ We can now evaluate y[i,i^{\prime}] in the abovementioned elements. \begin{array}[]{rl}y[i,i^{\prime}]&=\displaystyle\sum_{m=1}^{n+1}\#\{b\in\mathbb{Z}\mid b(n+1)+m\leq q(n+1)+r\mbox{ and }q^{\prime}(n+1)+r^{\prime}\leq(b+\mu_{m})(n+1)+w(m)\}\\ &\\ &\displaystyle=\sum_{m=1}^{n+1}\#\{b\in\mathbb{Z}\mid bl, so that \nu_{i} is defined for i\in\mathbb{Z}_{>0}. We denote by \nu^{\prime} the conjugate of \nu and we put |\nu|=\sum_{i=1}^{l}\nu_{i} . For all Q\in\mathbb{Z}_{<0} one has the equality (see Figure 6 ) \mu^{\prime}_{1}+\cdots+\mu^{\prime}_{-Q}+|\mu|_{Q}=|\mu|=|\lambda|=\lambda^{\prime}_{1}+\cdots+\lambda^{\prime}_{-Q}+|\lambda|_{Q}, (6.12) where \mu^{\prime}=(\mu_{1}^{\prime},\mu_{2}^{\prime},\ldots) and \lambda^{\prime}=(\lambda_{1}^{\prime},\lambda_{2}^{\prime},\ldots) . \lambda= |\lambda|_{Q} -Q Figure 6 : Using Young diagrams to illustrate Equation 6.12 . So we conclude that for all Q\in\mathbb{Z}_{<0}, \mu^{\prime}_{1}+\cdots+\mu^{\prime}_{-Q}\geq\lambda^{\prime}_{1}+\cdots+\lambda^{\prime}_{-Q}\iff|\mu|_{Q}\leq|\lambda|_{Q}. (6.13) Using the well-known equivalence \mu\preceq\lambda\iff\mu^{\prime}\succeq\lambda^{\prime}, as well as Equation 6.13 we obtain that \mu\preceq\lambda\iff|\mu|_{Q}\leq|\lambda|_{Q}. (6.14) for all Q\in\mathbb{Z}_{<0} . On the other hand, for all Q\in\mathbb{Z}_{\geq 0} we have |\lambda|_{Q}=Q(n+1)+|\lambda|=Q(n+1)+|\mu|=|\mu|_{Q}. (6.15) By combining ( 6.14 ) and ( 6.15 ) we obtain ( 6.9 ). ∎ It is clear that if \nu\in\mathbb{Z}^{n+1} and Q\in\mathbb{Z} one has |\nu|_{Q}=|\nu_{\mathrm{dom}}|_{Q} . Thus, by applying Lemma 6.7 , we conclude that condition ( 6.8 ) is equivalent to: \forall r,r^{\prime}\in\{1,\ldots,n+1\}:(y^{(r,r^{\prime})}_{1})_{\mathrm{dom}}\preceq(y^{(r,r^{\prime})}_{2})_{\mathrm{dom}}, or in other words, \forall r,r^{\prime}\in\{1,\ldots,n+1\}:(\mu_{1}+\varpi^{\prime}_{r}-w_{1}^{-1}(\varpi^{\prime}_{r^{\prime}-1}))_{\mathrm{dom}}\preceq(\mu_{2}+\varpi^{\prime}_{r}-w_{2}^{-1}(\varpi^{\prime}_{r^{\prime}-1}))_{\mathrm{dom}}. (6.16) This ends the proof of Theorem 6.4 . ∎ In the next corollary, we will identify S_{n+1} and W_{\mathrm{f}} through the map h . This simplification is intended to avoid further complicating the notation in the proof. Corollary 6.8 . Let x_{1}=(w_{1},\nu_{1}) , x_{2}=(w_{2},\nu_{2})\in(W_{\mathrm{f}}\ltimes\mathbb{Z}\Phi)^{\bullet} , then the following are equivalent. (a) We have x_{1}\leq x_{2} in the Bruhat order. (b) For all i,j\in\{0,1\ldots,n\} , we have (\nu_{1}+\varpi_{i}-w_{1}^{-1}\varpi_{j})_{\mathrm{dom}}\leq(\nu_{2}+\varpi_{i}-w_{2}^{-1}\varpi_{j})_{\mathrm{dom}}. Proof. Recall the bijection g_{\mathrm{res}}:\mathbb{Z}\Phi^{\prime}\rightarrow\mathbb{Z}\Phi , defined as the restriction of the map g in Lemma 6.1 . Using the isomorphism g_{1} , we see that x_{1}\leq x_{2} in the Bruhat order if and only if w_{1}\varepsilon^{g_{\mathrm{res}}^{-1}(\nu_{1})}=g_{1}^{-1}(x_{1})\leq w_{1}\varepsilon^{g_{\mathrm{res}}^{-1}(\nu_{1})}=g_{1}^{-1}(x_{2}). (6.17) With this notation, and using the equivalence of Theorem 6.4 , ( 6.17 ) is equivalent to \forall i,j\in\{1,\ldots,n+1\}:(g_{\mathrm{res}}^{-1}(\nu_{1})+\varpi^{\prime}_{i}-w_{1}^{-1}(\varpi^{\prime}_{j-1}))_{\mathrm{dom}}\preceq(g_{\mathrm{res}}^{-1}(\nu_{2})+\varpi^{\prime}_{i}-w_{2}^{-1}(\varpi^{\prime}_{j-1}))_{\mathrm{dom}}. (6.18) Applying the map g to both sides of the inequality, using Lemma 6.1 part ( 5 ), and then using Corollary 6.2 , we obtain that 6.18 is equivalent to \forall i,j\in\{1,\ldots,n+1\}:g(g_{\mathrm{res}}^{-1}(\nu_{1})+\varpi^{\prime}_{i}-w_{1}^{-1}(\varpi^{\prime}_{j-1}))_{\mathrm{dom}}\leq g(g_{\mathrm{res}}^{-1}(\nu_{2})+\varpi^{\prime}_{i}-w_{2}^{-1}(\varpi^{\prime}_{j-1}))_{\mathrm{dom}}. (6.19) As g(\varpi^{\prime}_{n+1})=\varpi_{0} , by applying again Lemma 6.1 , we obtain that ( 6.19 ) is equivalent to \forall i,j\in\{0,\ldots,n\}:(\nu_{1}+\varpi_{i}-w_{1}^{-1}(\varpi_{j}))_{\mathrm{dom}}\leq(\nu_{2}+\varpi_{i}-w_{2}^{-1}(\varpi_{j}))_{\mathrm{dom}}. ∎ 6.2 Specializing the criterion for C^{+} and in our conventions We prove Proposition 3.1 , which we restate for the reader’s convenience. Proposition 6.9 . Let x,y\in W_{\mathrm{aff}}^{+} . Then x\leq y (in the Bruhat order), if and only if x(-\varpi_{i})\leq y(-\varpi_{i}) for all i\in\{0,1,\ldots,n\} (in the dominance order). Equivalently, x\leq y in the Bruhat order if and only if \nu\leq\mu in the dominance order for all (\nu,\mu)\in V(x)\times V(y) satisfying \nu\equiv\mu\mod\mathbb{Z}\Phi . The proof of Proposition 6.9 is a translation of Corollary 6.8 to our conventions. To do this we first need the following lemma. Lemma 6.10 . Let \lambda,\mu\in\Lambda . Then \mu\leq\lambda\iff w_{0}(\lambda)\leq w_{0}(\mu). Proof. It suffices to show that 0\leq\lambda\implies w_{0}(\lambda)\leq 0 . It is well known that w_{0} maps the set of fundamental weights to the set of the negative fundamental weights. Let \tau be the permutation of \{1,\ldots,n\} defined by w_{0}(\varpi_{i})=-\varpi_{\tau(i)} . Note that since \mathbf{0}\leq\lambda , for all 1\leq i\leq n , we have 0\leq\langle\lambda,\varpi_{i}\rangle=\langle w_{0}(\lambda),-\varpi_{\tau(i)}\rangle. This implies that \langle w_{0}(\lambda),\varpi_{i}\rangle\leq 0 for all i\in\{1,\ldots,n\} . In other words, w_{0}(\lambda)\leq\mathbf{0} . ∎ Proof of Proposition 6.9 . We will prove only the first equivalence, as the second follows directly from it. We denote by (\mathbb{Z}\Phi\rtimes W_{\mathrm{f}})_{\bullet} the affine Weyl group defined as in Section 2 . Recall also that (\mathbb{Z}\Phi\rtimes W_{\mathrm{f}})^{\bullet} is the affine Weyl used in Section 6.1.2 . To apply the criterion in Corollary 6.8 , we will need the following group isomorphisms: \begin{array}[]{ccccc}(\mathbb{Z}\Phi\rtimes W_{\mathrm{f}})_{\bullet}&\xlongrightarrow{\sim}&(\mathbb{Z}\Phi\rtimes W_{\mathrm{f}})^{\bullet}&\xlongrightarrow{\sim}&(W_{\mathrm{f}}\ltimes\mathbb{Z}\Phi)^{\bullet}\\ (\lambda,w)&\longmapsto&(-\lambda,w)&\longmapsto&(w,-w^{-1}(\lambda))\end{array} (6.20) Let x=(\lambda,w) and y=(\mu,u) in (\mathbb{Z}\Phi\rtimes W_{\mathrm{f}})_{\bullet} . Using ( 6.20 ) we see that x\leq y (in the Bruhat order) if and only if (w,-w^{-1}(\lambda))\leq(u,-u^{-1}(\mu))\ \mbox{ in }(W_{\mathrm{f}}\ltimes\mathbb{Z}\Phi)^{\bullet}. (6.21) Applying Corollary 6.8 , we get that ( 6.21 ) is equivalent to the statement that for all i,j\in\{0,\ldots,n\} , we have (-w^{-1}(\lambda)+\varpi_{i}-w^{-1}(\varpi_{j}))_{\mathrm{dom}}\leq(-u^{-1}(\mu)+\varpi_{i}-u^{-1}(\varpi_{j}))_{\mathrm{dom}}, (6.22) in the dominance order. By definition, for any v\in\Lambda and z\in W_{\mathrm{f}} we have v_{\mathrm{dom}}=(z\cdot v)_{\mathrm{dom}} . Hence, ( 6.22 ) becomes (-\lambda+w(\varpi_{i})-\varpi_{j})_{\mathrm{dom}}\leq(-\mu+u(\varpi_{i})-\varpi_{j})_{\mathrm{dom}}. In turn, this last inequality is equivalent to (-x(-\varpi_{i})-\varpi_{j})_{\mathrm{dom}}\leq(-y(-\varpi_{i})-\varpi_{j})_{\mathrm{dom}}. (6.23) Since x\in W_{\mathrm{aff}}^{+} we have that x(-\varpi_{i})+\varpi_{j}\in C^{+} , so that -x(-\varpi_{i})-\varpi_{j}\in C^{-} , where C^{-}=-C^{+} . On the other hand, by [ 4 , Corollary VI.1.6.3] we have w_{0}(C^{-})=C^{+} . It follows that (-x(-\varpi_{i})-\varpi_{j})_{\mathrm{dom}}=w_{0}(-x(-\varpi_{i})-\varpi_{j})=-w_{0}x(\varpi_{i})-w_{0}(\varpi_{j}), (6.24) and the same holds for y . By ( 6.24 ), we obtain that ( 6.23 ) is equivalent to \forall i\in\{0,\ldots,n\}:w_{0}x(-\varpi_{i})\geq w_{0}y(-\varpi_{i}). Finally, multiplying by w_{0} and applying Lemma 6.10 , we get x(-\varpi_{i})\leq y(-\varpi_{i}) for all i\in\{0,1,\ldots,n\} . ∎