\documentclass[finalversion]{FPSAC2024}
\articlenumber{11}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{question}[theorem]{Question}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lettertheorem}{Theorem}
\renewcommand{\thelettertheorem}{\Alph{lettertheorem}}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{warning}[theorem]{Warning}
\newtheorem*{notation}{Notation}


\renewcommand{\tilde}{\widetilde}
\renewcommand{\bar}{\overline}
\newcommand{\bbC}{\mathbb{C}}
\newcommand{\bbD}{\mathbb{D}}
\newcommand{\bbH}{\mathbb{H}}
\newcommand{\bbK}{\mathbb{K}}
\newcommand{\bbN}{\mathbb{N}}
\newcommand{\bbP}{\mathbb{P}}
\newcommand{\bbQ}{\mathbb{Q}}
\newcommand{\bbR}{\mathbb{R}}
\newcommand{\bbZ}{\mathbb{Z}}
\newcommand{\bbLL}{\mathbb{LL}}
\newcommand{\ILL}{\mathrm{ILL}}

\newcommand{\Raw}{\Rightarrow}
\newcommand{\raw}{\rightarrow}
\newcommand{\daw}{\downarrow}
\newcommand{\upaw}{\uparrow}
\newcommand{\Lra}[1]{\xrightarrow[L]{#1}}
\newcommand{\Rra}[1]{\xrightarrow[R]{#1}}
\newcommand{\xra}{\xrightarrow}
\newcommand{\cug}{\subseteq}
\newcommand{\sug}{\supseteq}
\newcommand{\into}{\longmapsto}



\newcommand{\undx}{{\underline{x}}}
\newcommand{\undy}{{\underline{y}}}
\newcommand{\undz}{{\underline{z}}}
\newcommand{\undw}{{\underline{w}}}
\newcommand{\undtheta}{\underline{\theta}}
\newcommand{\undH}{{\underline{\mathbf{H}}}}

\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calD}{\mathcal{D}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calH}{\mathcal{H}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\calL}{\Omega}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calU}{\mathcal{U}}
\newcommand{\calV}{\mathcal{V}}
\newcommand{\calX}{\mathcal{X}}

\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfM}{\mathbf{M}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfU}{\mathbf{U}}
\newcommand{\bfV}{\mathbf{V}}
\newcommand{\bfN}{\mathbf{N}}


\newcommand{\frh}{\mathfrak{h}}
\newcommand{\frD}{\mathfrak{D}}
\newcommand{\frP}{\mathfrak{P}}
\newcommand{\frQ}{\mathfrak{Q}}
\newcommand{\frR}{\mathfrak{R}}
\newcommand{\frgl}{\mathfrak{gl}}
\newcommand{\frsl}{\mathfrak{sl}}
\newcommand{\frg}{\mathfrak{g}}
\newcommand{\frb}{\mathfrak{b}}

\newcommand{\FA}{A_{\text{id}}}

\newcommand{\sbim}{{\mathbb{S}Bim}}
\newcommand{\bsbim}{\mathbb{BS}Bim}


%colored letters
\newcommand{\cols}{{\color{red} s}}
\newcommand{\colt}{{\color{blue} t}}
\newcommand{\colu}{{\color{green} u}}

\hyphenation{Co-xe-ter}

%from HL
\newcommand{\lra}{\longrightarrow}
\newcommand*{\longhookrightarrow}{\ensuremath{\lhook\joinrel\relbar\joinrel\rightarrow}}



\DeclareMathOperator{\cha}{ch}
\DeclareMathOperator{\chara}{char}
\DeclareMathOperator{\coeff}{coeff}
\DeclareMathOperator{\defect}{def}
\DeclareMathOperator{\Downs}{Downs}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\for}{For}
\DeclareMathOperator{\gr}{gr}
\DeclareMathOperator{\Grad}{Gr}
\DeclareMathOperator{\grdim}{grdim}
\DeclareMathOperator{\grrk}{grrk}
\DeclareMathOperator{\hgt}{ht}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\Iden}{Id}
\DeclareMathOperator{\ima}{Im}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\rank}{rk}
\DeclareMathOperator{\Rep}{Rep}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\spa}{span}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\Trace}{Tr}
\DeclareMathOperator{\Peaks}{Peaks}
\DeclareMathOperator{\adm}{Adm}
\DeclareMathOperator{\Conf}{Conf}
\DeclareMathOperator{\rex}{rex}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\conv}{Conv}
\DeclareMathOperator{\vol}{Vol}
\DeclareMathOperator{\relvol}{relVol}





\numberwithin{equation}{section}


%\usepackage[T1]{fontenc}
%\usepackage[latin1]{inputenc}
%\usepackage{amsmath,amsfonts}
%\usepackage{amsthm}
%\usepackage{amssymb}
%\usepackage{authblk}
%\usepackage[USenglish]{babel}
%\usepackage{enumitem}
%\usepackage{enumerate}
%\usepackage{cite}
%\usepackage{xcolor}
%\usepackage{todonotes}
%\usepackage[final, pdftex, pdfpagelabels, pdfstartview = {FitH}, bookmarks, plainpages = false, linktoc=all,linkcolor=black, citecolor=blue, urlcolor=blue,
%filecolor=black]{hyperref}
%\usepackage{cleveref}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{dynkin-diagrams}
\usepackage{titlesec}

\setlength{\headheight}{16pt}

\title[On the size of Bruhat intervals]{On the size of Bruhat intervals}

\author[F. Castillo, D. de la Fuente, N. Libedinsky and D. Plaza]{Federico Castillo\thanks{\href{federico.castillo@mat.uc.cl}{federico.castillo@mat.uc.cl}. Partially supported by FONDECYT-ANID grant 1221133.}\addressmark{1},  Damian de la Fuente\thanks{\href{damiandlfa@gmail.com}{damiandlfa@gmail.com}.  }\addressmark{2},  Nicolas Libedinsky\thanks{\href{nlibedinsky@gmail.com}{nlibedinsky@gmail.com}. Partially supported by FONDECYT-ANID grant 1230247. }\addressmark{3}, \and David Plaza\thanks{\href{davidricardoplaza@gmail.com}{davidricardoplaza@gmail.com}. Partially supported by FONDECYT-ANID grant 1200341. }\addressmark{4}}


\address{\addressmark{1}Pontificia Universidad Católica, Santiago, Chile\\ \addressmark{2}LAMFA, Universit\'e de Picardie Jules Verne, Amiens, France\\  \addressmark{3}Universidad de Chile, Santiago, Chile \\  \addressmark{4}Universidad de Talca, Talca, Chile}
\received{March 31, 2024}


%\revised{}

\abstract{For affine Weyl groups and elements associated to dominant coweights, we present a  convex geometry formula for the size of the corresponding lower Bruhat intervals. Extensive computer calculations for these groups have led us to believe that a similar formula exists for all lower Bruhat intervals.}


%% put your keywords here, or comment this out if you don't have them yet
\keywords{Bruhat order, Affine Weyl groups, Polytopes, Lattice points}


\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
\begin{document}

\maketitle


\section{Introduction}

In this extended abstract of the article \cite{GeoFor2023}, we study, for any affine Weyl group, the lower Bruhat interval for the element  $\theta(\lambda)$ (see Definition \ref{def: theta}) associated to a dominant coweight $\lambda$.
These elements are intimately related to representation theory (character formulas for Lie groups, geometric Satake equivalence, quantum groups, among others).
While calculating with indecomposable Soergel bimodules \cite{LP} and Kazhdan-Lusztig polynomials \cite{batistelli2023kazhdan, PreCanonical}, it became apparent that finding formulas for the cardinalities of lower Bruhat intervals played a crucial role. 
Surprisingly, little is known apart from length $2$ (general) intervals \cite[Lemma 2.7.3]{BB}, lower intervals for smooth elements in Weyl groups \cite{OhPostnikovYoo, MSY} and related results for affine Weyl groups \cite{RS, BE}. 

Our two main results relate the lower interval $\leq\theta(\lambda)\coloneqq[\mathrm{id}, \theta(\lambda)]$, i.e. the elements below $\theta(\lambda)$ in the (strong) Bruhat order, with a certain convex polytope $\mathsf{P}(\lambda)$.
We give a construction of $\leq\theta(\lambda)$ in terms of lattice points in $\mathsf{P}(\lambda)$. 
By using this construction, we then derive a formula which computes the cardinality of $\leq\theta(\lambda)$ as a linear combination of the volumes of the faces of $\mathsf{P}(\lambda)$.
For the sake of clarity, we will first explain these results in a small example.

Let us consider $W$ the affine Weyl group of type $\tilde{A}_2$, and the usual identification between elements in $W$ and triangles (alcoves) in the tessellation of the plane by equilateral triangles. If $x$ is an element of $W$, when we write $x\subset \mathbb{R}^2$, we mean the set of points in the closure of the alcove corresponding to $x$ (the closed triangle).  
In Figure \ref{fig1} we have the simple roots $\alpha_1$ and $\alpha_2$ in red and in blue, and the fundamental weights $\varpi_1$ and $\varpi_2$.
The $\textbf{id}$-triangle is the fundamental alcove.
For a dominant weight $\lambda \in X^+ 
:=\mathbb{Z}_{\geq0}\varpi_1+\mathbb{Z}_{\geq0}\varpi_2$ (depicted by a white dot in
Figure \ref{fig1}),
let $\theta(\lambda)\in W$ denote the $\lambda$-translate of
the opposite of the fundamental alcove: those are the grey
triangles.

Let also $P(\lambda)$ denote $\mathrm{Conv}(W_f\cdot
\lambda)$, the convex hull of the orbit of $\lambda$ under the finite
Weyl group $W_f$. 
For $\lambda = 2\varpi_1+\varpi_2$, it is the yellow
hexagon in Figure \ref{fig2}. The faces of $P(\lambda)$ containing $\lambda$ are
$$F_J := P(\lambda)\cap ( \lambda + \sum_{i \in J} \mathbb{R}\alpha_i), \quad J
\subset \{1,2\}.$$
%\vspace{0.5cm}


\begin{figure}[ht]
    \centering
    \begin{minipage}{0.45\textwidth}
        \centering
        \includegraphics[width=0.9\textwidth]{FPSAC1.png} % first figure itself
        \caption{}
        \label{fig1}
    \end{minipage}\hfill
    \begin{minipage}{0.45\textwidth}
        \centering
        \includegraphics[width=0.9\textwidth]{FPSAC2.png} % second figure itself
        \caption{}
        \label{fig2}
    \end{minipage}
\end{figure}

Consider the lattice $\mathcal{L}\coloneqq\lambda+\bbZ\alpha_1+\bbZ\alpha_2$.
Let $\lambda= 2\varpi_1+\varpi_2$, as before.
In Figure \ref{fig3} the interval $\leq \theta(\lambda)\coloneqq\{w\in W\mid w\leq \theta(\lambda)\}$ is colored in grey, and the green dots are the set $X_\lambda\coloneqq P(\lambda)\cap\mathcal{L}$.
Let $\mu\in X_\lambda$ and notice that there are six (grey) triangles adjacent to $\mu$.
Since the subgroup $W_f$ of $W$ corresponds to the six triangles adjacent to the origin (where the three thick lines meet), the triangles adjacent to $\mu$ are precisely the $\mu$-translate of $W_f$.
In fact, this describes all the grey triangles:
\begin{equation}\label{eq: LF peque1}
    \leq\theta(\lambda)=\bigsqcup_{\mu\in X_\lambda}W_f+\mu.
\end{equation}
In particular we get the following equation, which we call the \textit{Lattice Formula}
\begin{equation}\label{eq: LF peque2}
    |\leq\theta(\lambda)|=6\,|P(\lambda)\cap\mathcal{L}|.
\end{equation}
% \vspace{0.5cm}

\begin{figure}[ht]
    \centering
    \begin{minipage}{0.45\textwidth}
        \centering
        \includegraphics[width=0.9\textwidth]{FPSAC3.png} % first figure itself
        \caption{Lattice Formula}
        \label{fig3}
    \end{minipage}\hfill
    \begin{minipage}{0.45\textwidth}
        \centering
        \includegraphics[width=0.9\textwidth]{FPSAC4.png} % second figure itself
        \caption{Geometric Formula}
        \label{fig4}
    \end{minipage}
\end{figure}

\vspace{0.5cm}

On the other hand, take the area of each colored part in Figure \ref{fig4}.
By adding these areas and dividing by the area of any triangle, we get  
\begin{equation}\label{babypick}
    \vert \leq \theta(\lambda) \vert = 
\mu_{1,2}\mathrm{Area}(F_{1,2})+\mu_{1}\mathrm{Length}(F_{1})+\mu_{2}\mathrm{Length}(F_{2})+\mu_{\emptyset}\mathrm{Card}(F_{\emptyset}),\end{equation}
for some real numbers $\mu_{J}$.
That is, $\mu_{1,2}\mathrm{Area}(F_{1,2})$ is the number of triangles in the yellow part, $\mu_{1}\mathrm{Length}(F_{1})$ corresponds to the red part, $\mu_{2}\mathrm{Length}(F_{3})$ to the blue part and the last term corresponds to the 6 turquoise triangles.

It is obvious that for a given $\lambda$, there are some $\mu$'s satisfying Equation \eqref{babypick}.
However it turns out that the coefficients $\mu$'s corresponding to the partition of Figure \ref{fig4} do not depend on the choice of $\lambda$ and that they are unique in this sense.
We call this formula the \textit{Geometric Formula}.

\begin{remark}
   The reader may notice that the formula presented here bears strong similarities to Pick's theorem. For the proof of Theorem \ref{geofor}, a generalization of the formula \eqref{babypick} applicable to any root system, we use a generalized version of Pick's theorem developed by Berline and Vergne. For more details see Section \ref{sec: lattice points}.
\end{remark}

For any irreducible root system $\Phi$ one has an associated affine Weyl group $W$ and one can define similar  concepts as in the $\tilde{A_2}$ case.
For example, $\theta(\lambda)$ corresponds to the alcove touching $\lambda$ in the direction of $\rho$ (the sum of the fundamental weights). The following theorem, a generalization of Equation \eqref{eq: LF peque2}, builds the bridge between Coxeter combinatorics and convex geometry.


\begin{lettertheorem}[Lattice Formula] \label{flf} For every dominant coweight $\lambda$, we have  $$\vert\leq\theta(\lambda)|=|W_f| \ |\mathrm{Conv}(W_f\cdot \lambda)\cap (\lambda+\mathbb{Z}\Phi^\vee)|.$$
\end{lettertheorem}
This formula is a key step to prove our main theorem below but it is also interesting in its own right, as we now explain. 
In \cite{postnikov2009permutohedra} Postnikov studied permutohedra of general types.
Among them, one of the most remarkable is the regular permutohedron of type $A_n$.
The number of integer points of that polytope can be interpreted \cite[\S 3]{stanley1980decompositions} as the number of forests on $\{1,2,\ldots, n\}$.
There are other interpretations for the integer points of the regular permutohedron of type $A_n$, for instance, \cite[Proposition 4.1.3]{backman2019geometric} gives one as certain orientations of the complete graph. 
We remark that these interpretations are only for the regular permutohedron of type $A_n.$
For non-regular permutohedra of any type, before the present paper, there was no interpretation of the integer points.  Theorem \ref{flf} gives a first interpretation of this sort, and it is also of a different nature than the pre-existent ones in that it is not related to graph theory but to Coxeter theory. 



This theorem also gives an interesting new insight. For a generic permutohedron (i.e. $\mathrm{Conv}(W_f\cdot \lambda)$ for some $\lambda \in \bbZ_{>0}\varpi_1+\bbZ_{>0}\varpi_2$), the set of vertices is in bijection with the finite Weyl group $W_f=\{w\leq_R w_0\}$ where $\leq_R$ is the right weak Bruhat order on $W_f$ and $w_0$ is the longest element.
The Hasse diagram of $\leq_R$ on $\{w\leq_R w_0\}$ corresponds to the graph of the polytope.

Theorem \ref{flf} (or more precisely Proposition \ref{prop: to prove LF}, a generalization of Equation \eqref{eq: LF peque1}) says that if we consider the strong Bruhat order, the set $\leq \theta(\lambda)$  can be obtained from the lattice points inside the polytope.  Heuristically, the weak Bruhat order gives the vertices of the polytope and the strong Bruhat order gives the lattice points inside the polytope.

Now we can present our main result.
For $J\subseteq \{1,2,\ldots, n\},$  one can define the face $F_J=\mathrm{Conv}(W_J\cdot \lambda)$ of $\mathrm{Conv}(W_f\cdot \lambda)$. 
See section \ref{sec: faces and vols} for more details. 

\begin{lettertheorem}[Geometric Formula]\label{geofor}
 For every rank 
$n$ irreducible root system $\Phi$, there are unique ${\mu_J^{\Phi}\in\mathbb{R}}$ such that for any dominant coweight $\lambda$,
$$|\leq\theta(\lambda)|=\sum_{J\subset \{1,\ldots,n\}}\mu_J^{\Phi}\mathrm{Vol}(F_J),
$$
\end{lettertheorem}

\begin{remark}
This Theorem generalizes Equation \eqref{babypick}.
One should be careful with the intuition coming from type $\tilde{A_2}$.
In that small example, recall that the coefficients were determined by the partition in Figure \ref{fig4}.
For a given $\lambda$ one can always construct a partition $\mathcal{P}$ of (the alcoves of) $\leq\theta(\lambda)$ according to $\mathrm{Conv}(W_f\cdot \lambda)$, and then derive some coefficients $\mu$'s.
It is fortuitous that in the $\tilde{A_2}$ case, these coefficients coincide with the ones in the Geometric Formula.
Already in $\tilde{A_4}$ it is not true that $\mathrm{Conv}(W_f\cdot \lambda)\subset\leq\theta(\lambda)$, and in $\tilde{A_{24}}$ there is a negative $\mu_J$ coefficient, so $\mu_J\mathrm{Vol}(F_J)$ is not the number of alcoves in some $p\in\mathcal{P}$.
\end{remark}


Theorem \ref{geofor} is proved by combining Theorem \ref{flf} with a particular formula for computing the number of lattice points developed by Berline-Vergne \cite{berline2007local} and Pommersheim-Thomas \cite{pommersheim2004cycles}.
The construction we use is part of a bigger family of formulae relating the number of lattice points of a polytope with the volumes of its faces, see \cite[\S 6]{barvinok1999algorithmic}.

 
In  \cite{postnikov2009permutohedra}, Postnikov gives several formulas for the volumes $\mathrm{Vol}(F_J)$ for any $\Phi$. 
When $\Phi$ is the root system of type $A_n$, in Section \ref{sec: coefs} we give some geometric coefficients $\mu_J^{A_n}$.

The volumes are polynomials in the coordinates $m_1, \dots, m_n$ of $\lambda$ in the coweight basis.
As a consequence of Theorem \ref{geofor} we obtain that the size of the lower Bruhat intervals generated by $\theta(\lambda)$ is a polynomial function on the coordinates of $\lambda$.

\vspace{0.2cm}

\section{Lattice Formula }

We refer the reader to \cite{humphreys1992reflection,Bour46} for more details about Weyl groups.

For the rest of this extended abstract, we fix an irreducible (reduced, crystallographic) root system $\Phi$ of rank $n$, and we denote by $V$ be the ambient (real) Euclidean space spanned by $\Phi$, with inner product ${(-,-)}: V \times V \to \mathbb{R} $.

Let $\alpha_1,\cdots,\alpha_n\in\Phi$ be a choice of simple roots.
The \textit{fundamental coweights} ${\varpi_i^\vee}$ are defined by the equations ${(\varpi_i^\vee,\alpha_j)=\delta_{ij}}$. 
They form a basis of $V$. 
A \textit{coweight} is an integral linear combination of the fundamental coweights, and a \textit{dominant coweight }is a coweight whose coordinates in this basis are non-negative.
The set of coweights will be denoted by $\Lambda^\vee$.

For a root $\alpha\in\Phi$ and an integer $k\in\mathbb{Z}$, consider the hyperplane
\begin{equation*}
    H_{\alpha,k}=\{\lambda\in V\mid (\lambda,\alpha)=k\},
\end{equation*}
and the affine reflection $s_{\alpha,k}$ through this hyperplane.
We write $s_i\coloneqq s_{\alpha_i,0}$, for $1\leq i\leq n$, and $s_0\coloneqq s_{\tilde{\alpha},-1}$, where $\tilde{\alpha}$ is the highest root.
The \textit{affine Weyl group} $W$ is the group generated by $S\coloneqq\{s_0,s_1,\ldots,s_n\}$.
We have that $(W,S)$ is a Coxeter system.
We denote by $\leq$ the (strong) Bruhat order on $W$: $u\leq w$ if $u$ can be obtained by deleting some letters of a reduced word for $w$.
For $J\subset S$, the \textit{parabolic subgroup} $W_J$ is the subgroup of $W$ generated by $J$.
The \textit{finite Weyl group} $W_f$ is the parabolic subgroup of $W$ generated by $S_f\coloneqq\{s_1,\ldots,s_n\}$.
It has a maximal element $w_0$ with respect to $\leq$.

An alcove is a connected component of $V\setminus\cup_{\alpha,k}H_{\alpha,k}$.
The closure of an alcove is a fundamental domain for the action of $W$ on $V$.
The \textit{fundamental alcove} is the simplex
\begin{equation*}
    A_\text{id}\coloneqq\{\lambda\in V\mid -1<(\lambda,\alpha)<0, \ \forall\alpha=\alpha_1,\ldots,\alpha_n,\tilde{\alpha}\}.
\end{equation*}
We have a bijection $w\mapsto A_w\coloneqq wA_\text{id}$ between $W$ and the set of alcoves.
% A vertex of $A_w$ will mean a vertex of its closure.

The \textit{coroot} $\alpha^\vee$ corresponding to a root $\alpha\in\Phi$ is $\alpha^\vee\coloneqq2\alpha/(\alpha,\alpha)$.
The lattice $\Lambda^\vee$ contains $\bbZ\Phi^\vee$ as a subgroup of finite index. 
Consider the group $\Omega\coloneqq\Lambda^\vee/\bbZ\Phi^\vee$.
Define $v_i=-\varpi_i^\vee$ for $1\leq i\leq n$ and let $v_0$ be the zero vector. 
Define $M\coloneqq\{i\mid(\varpi_i^\vee,\tilde{\alpha})=1\}$.
The set $\{v_0,v_i\mid i\in M\}$ is a complete system of representatives of $\Omega$.
This group classifies all parabolic subgroups of $W$ that are isomorphic to $W_f$.
We will denote by $W_\sigma$ the parabolic subgroup corresponding to $\sigma\in\Omega$.
It is the subgroup generated by $S\setminus\{s_i\}$, where $\sigma=v_i$ in $\Omega$.
From now on, we will identify $\Omega$ with the representatives $\{v_0,v_i\mid i\in M\}$.

\begin{definition} \label{def: theta}
Let $\lambda$ be a dominant coweight. 
Since ${A_{w_0}+\lambda}$ is an alcove, there exists a unique element ${\theta(\lambda)\in W}$ such that ${A_{\theta(\lambda)}=A_{w_0}+\lambda}$. 
See Figure \ref{fig1} for an example.  
\end{definition}

For any $X\subset W$, let $A(X)$ be the union of alcoves corresponding to $X$. That is, $A(X)=\sqcup_{x\in X}A_x$.
The following Lemma captures the geometric intuition needed to prove Theorem \ref{flf}.

\begin{lemma}\label{lemmafirstlat}
Let $\lambda$ be a dominant coweight and let ${\sigma\in\Omega}$ such that $\lambda\in\sigma+\bbZ\Phi^\vee$.
Then,
\begin{enumerate}
    \item \label{uno}${A(W_\sigma)=A(W_f)+\sigma}$.
    \item \label{dos}  ${A(\theta(\lambda)W_\sigma)=A(W_f)+\lambda}$.
    \item \label{cinq}  $\theta(\lambda)$ is maximal with respect to the Bruhat order in its double coset $W_f\theta(\lambda) W_{\sigma}$.
    \item The maximal elements of the double cosets in $\bigsqcup_{\sigma\in\Omega}W_f\backslash W/ W_{\sigma}$, are precisely the $\theta$-elements.
\end{enumerate}
\end{lemma}

\begin{definition}\label{def: orbit pol}
    For any $\lambda\in V$, we define the \textit{orbit polytope} $\mathsf{P}^\Phi(\lambda)$ as the convex polytope whose vertex set is the $W_f$-orbit of $\lambda$. See Figure \ref{fig2} for an example.
\end{definition}

As long as $\lambda$ is not the zero vector, the orbit polytope is always full dimensional.

Using Lemma \ref{lemmafirstlat}, we can derive the following Proposition, which describes the alcoves corresponding to $\leq\theta(\lambda)$ in terms of lattice points in $\mathsf{P}^\Phi(\lambda)$.

\begin{prop} \label{prop: to prove LF}
  For every dominant coweight $\lambda$, we have 
  \begin{equation}\label{leqthetaalcoves}
    A\bigg(\leq\theta(\lambda)\bigg)=\bigsqcup_{\mu\in X_\lambda}A(W_f)+\mu,
\end{equation}
where $X_\lambda=\mathsf{P}^\Phi(\lambda)\cap(\lambda+\mathbb{Z}\Phi^\vee)$.
\end{prop}

Then, by counting alcoves in Equation \eqref{leqthetaalcoves}, we get the Lattice Formula.

\begin{theorem}[Lattice Formula]\label{thm:first-lattice-formula}
For every dominant coweight $\lambda$, we have 
\begin{equation}\label{firstlatdef}
    |\leq\theta(\lambda)|=|W_f| \ |\mathsf{P}^\Phi(\lambda)\cap (\lambda+\mathbb{Z}\Phi^\vee)|.
\end{equation}
\end{theorem}

\section{Geometric Formula}

\subsection{Faces of the orbit polytope and their volumes}\label{sec: faces and vols}

For any $X\subset V$ we denote by $\mathsf{Conv}(X)$ the convex hull of $X$.
Let $\lambda$ be a dominant coweight.
The faces of the orbit polytope $\mathsf{P}^\Phi(\lambda)$ are given by
\begin{equation*}
    \mathsf{F}(w,J)=w\mathsf{Conv}(W_J\cdot\lambda),
\end{equation*}
where $J\subset S_f$ and $w$ ranges over any representatives of $W/W_J$.
In particular, the facets of $\mathsf{P}^\Phi(\lambda)$ containing $\lambda$, are precisely $\mathsf{F}(\text{id},S_f\setminus\{s_i\})$ for $1\leq i\leq n$.

\begin{definition}\label{def: vol}
    For a subset $J\subset S_f$, we define $V_J^\Phi(\lambda)$ as the $|J|$-dimensional volume of the face $\mathsf{F}(\text{id},J)$ of $\mathsf{P}^\Phi(\lambda)$.
\end{definition}

It will turn out that the volumes $V_J^\Phi(\lambda)$ can be seen as polynomials, as we now explain.
For simplicity, suppose $J=S_f$ and that $\lambda$ is \textit{generic}\footnote{In the literature, a coweight is \textit{regular} if it is not orthogonal to any root.
Thus, a dominant coweight is generic if and only if it is regular.}, i.e. its coordinates (in the fundamental coweight basis) are strictly positive.
We can decompose $\mathsf{P}^\Phi(\lambda)$ into pyramids having the facets of $\mathsf{P}^\Phi(\lambda)$ as their bases, and the zero vector as their apex.
Thus we can compute the $n$-dimensional volume of $\mathsf{P}^\Phi(\lambda)$, i.e. $V_{S_f}^\Phi(\lambda)$, by adding up the volumes of these pyramids.
After considering symmetries, we get the following equation.

\begin{equation}\label{eqpyrfor}
    V_{S_f}^\Phi(\lambda)=\dfrac{1}{n}\sum_{j=1}^n \left[W:W_{S_f\setminus\{s_j\}}\right]\,\dfrac{(\lambda,\varpi_j^\vee)}{\Vert\varpi_j^\vee\Vert} \ V_{S_f\setminus\{s_j\}}^\Phi(\lambda).
\end{equation}

Now let $\mathbf{m}=(m_1,\ldots,m_n)$ be a $n$-tuple of positive integers.
Define $V_{S_f}^\Phi(\mathbf{m})\coloneqq V_{S_f}^\Phi(m_1\varpi^\vee_1+\ldots+m_n\varpi^\vee_n)$.
It is clear that the term $(\lambda,\varpi_j^\vee)$ (coming from the height of the pyramids) is a polynomial in $m_1,\ldots,m_n$.
Since $V_\emptyset^\Phi(\lambda)=1$, Equation \eqref{eqpyrfor} implies that $V_{S_f}^\Phi(\mathbf{m})$ is a homogeneous polynomial of degree $n$ in $m_1,\ldots,m_n$, by induction.

For any $J\subset S_f$ and dominant coweight $\lambda$, a similar formula to Equation \eqref{eqpyrfor} allows us to see the volumes $V_J^\Phi(\lambda)$ as polynomials.
Furthermore, we can deduce their linear independence.
We collect this in the following Lemma (for more details, see \cite[\S 4]{GeoFor2023}).

\begin{lemma}\label{lem: vols as pols} Let $\mathbf{m}=(m_1,\ldots,m_n)$ be a $n$-tuple of non-negative integers.
For $J\subset S_f$, define $V_J^\Phi(\mathbf{m})\coloneqq V_J^\Phi(m_1\varpi^\vee_1+\ldots+m_n\varpi^\vee_n)$.
\begin{itemize}

    \item $V_J^\Phi(\mathbf{m})$ is a homogeneous polynomial of degree $|J|$ in the variables $m_j$, for $j\in J$ (identifying $J$ with a subset of $\{1,2,\ldots,n\}$).

    \item The polynomials $V_J^\Phi(\mathbf{m})$ with $J\subset S_f$ are linearly independent.
    
\end{itemize}
\end{lemma}

\begin{remark}
    To compare our results to Potnikov's formulas for the volumes, suppose $\Phi$ has type $A_n$.
    In this case, $\mathsf{P}^\Phi(\lambda)$ is a permutohedron.
    Our variables $m_1,\ldots,m_n$ correspond to the variables $u_1,\ldots,u_n$ in \cite[\S 16]{postnikov2009permutohedra}.
    There is a missing scalar factor of $\sqrt{n+1}$, which is the Euclidean volume of the fundamental parallelepiped spanned by the simple roots, but his formulas are scaled so that its volume is $1$.
\end{remark}

\subsection{Counting lattice points}\label{sec: lattice points}

For any (possibly non-pointed) cone $\mathsf{C}$ that includes the origin, we define its \emph{polar} as
\[
\mathsf{C}^\circ = \{v\in V~:~( v,w ) \leq 0, \forall w\in \mathsf{C}\}.
\]

Let $\Gamma \subset V$ be a lattice.
\begin{definition}
\label{def:conos}
Let $ \mathsf{P} $ be a full dimensional lattice polytope, that is, a convex polytope whose vertices lie in $\Gamma$.
For a face $ \mathsf{F} \subset \mathsf{P} $ let $ H $ be its affine span, $ L $ the corresponding linear subspace and $\pi:V\rightarrow L^\perp$ the orthogonal projection.
We define four cones:

\begin{itemize}

    \item The \textbf{normal cone} $ \mathsf{n}( \mathsf{F} , \mathsf{P} ) = \cone \{ u_\mathsf{G}~:~\mathsf{G}\text{ is a facet such that } \mathsf{F}\subset \mathsf{G}\}$, where $u_\mathsf{G}$ is an outer normal for the facet $\mathsf{G}\subset\mathsf{P}$.

    \item The \textbf{feasible cone} $\mathsf{f}(\mathsf{F},\mathsf{P})$ is the polar of the normal cone $\mathsf{n}( \mathsf{F} , \mathsf{P} )$.

    \item The \textbf{supporting cone} $\mathsf{s}(\mathsf{F},\mathsf{P}) := H + \mathsf{f}(\mathsf{F},\mathsf{P})$. It is a translation of the feasible cone.
    
    \item The \textbf{transverse cone} $ \mathsf{t}( \mathsf{F} , \mathsf{P} ) = \pi(\mathsf{s}(\mathsf{F},\mathsf{P})) $.
    
\end{itemize}

\end{definition}

We say that a pointed cone $\mathsf{C}$ is rational if its vertex is a lattice point and every ray (1-dimensional face) contains a lattice point.
The following is the \emph{Euler-Maclaurin formula} developed by Berline and Vergne \cite{berline2007local} (see also \cite[Chapters 19-20]{barvinok2008integer} for an exposition).
There exists a function $\nu$ on pointed rational cones such that the following is true for all lattice polytopes $ \mathsf{P}. $
\begin{equation}\label{eq:local-formula}
|\mathsf{P}\cap \Gamma| = \sum_{\mathsf{F}\subseteq \mathsf{P}} \nu\left( \mathsf{t}( \mathsf{F} , \mathsf{P}) \right)\text{relVol} (\mathsf{F}),
\end{equation}
where the sum is indexed over all nonempty faces of $\mathsf{P}$. 
The relative volume $\mathrm{relVol}(\mathsf{F})$ of a face is the volume on its affine span $H$ normalized with respect to the lattice $\Gamma\cap L$, where $L$ is the linear subspace parallel to $H$. More precisely,
\begin{equation}
\label{eq:rel_vol}
\relvol(\mathsf{F}) = \frac{\vol(\mathsf{F})}{\det(\Gamma\cap L)}.
\end{equation}

\begin{remark}
To be more precise, Berline and Vergne's main construction in \cite{berline2007local} is a function $\mu$ that maps pointed rational cones to meromorphic functions \cite[\S 4]{berline2007local}.
In this paper we only use the function $\nu$ which is $\mu$ evaluated at zero \cite[Definition 25]{berline2007local}, and then Equation \eqref{eq:local-formula} is equivalent to \cite[Theorem 26]{berline2007local} when the function $h$ is the constant function equal to $1$. 
\end{remark}

We remark that for a single polytope $\mathsf{P}$, it is obvious that there will be a formula resembling Equation \eqref{eq:local-formula}.
The interesting part of Berline-Vergne's  theorem is that the $\nu$ function satisfies Equation \eqref{eq:local-formula} for all lattice polytopes simultaneously and has certain local properties.
Namely, the following operations do not change the $\nu$ value of a transverse cone.
\begin{itemize}
    \item [i] Applying a lattice-preserving orthogonal transformation.
    \item [ii] Translating by a lattice element.
\end{itemize}

We use these tools to prove Theorem \ref{geofor}, which we restate for the reader's convenience.
\begin{theorem}[Geometric Formula]\label{thm:geometric-formula}
For every irreducible root system $\Phi$, there are unique ${\mu_J^{\Phi}\in\mathbb{R}}$ such that for any dominant coweight $\lambda$,
\begin{equation}\label{geofordef}
    |\leq\theta(\lambda)|=\sum_{J\subset S_f}\mu_J^{\Phi}V_J^{\Phi}(\lambda).
\end{equation}
\end{theorem}

The sketch of the proof is as follows.
We focus on proving the existence of the coefficients, since Lemma \ref{lem: vols as pols} implies uniqueness.

Let $\lambda$ be a dominant coweight. The polytope $ \mathsf{Q}^\Phi(\lambda)\coloneqq \mathsf{P}^\Phi(\lambda) - \lambda$ is a lattice polytope with respect to the lattice $ \mathbb{Z}\Phi^\vee $.
Note that the Lattice Formula, Theorem \ref{thm:first-lattice-formula}, yields
\begin{equation}
\label{eq:complete_lattic_formula}
|\leq\theta(\lambda)|=|W_f| \ |\mathsf{P}^\Phi(\lambda)\cap (\lambda+\mathbb{Z}\Phi^\vee)|=|W_f| \ | \mathsf{Q}^\Phi(\lambda) \cap \mathbb{Z}\Phi^\vee|.
\end{equation}

Applying Berline-Vergne formula \eqref{eq:local-formula}, we get

\begin{equation}\label{eq: geofor sketch}
|\leq\theta(\lambda)|= |W_f|\sum_{\mathsf{F} \subseteq\mathsf{Q}^\Phi(\lambda)} \nu\left( \mathsf{t}( \mathsf{F} , \mathsf{Q}^\Phi(\lambda))\right) \text{relVol} (\mathsf{F}).
\end{equation}

The faces of the lattice polytope $\mathsf{Q}^\Phi(\lambda)$ are $\mathsf{G}_J(w,\lambda) := \mathsf{F}_J(w,\lambda)-\lambda$ for all pairs $w\in W_f$ and $J\subset S_f$.
We define $\mathsf{G}_J(\lambda):=\mathsf{G}_J(\mathrm{id},\lambda)$.
Recall that a generic dominant coweight is a positive integer linear combination of the fundamental coweights.

\begin{lemma}
\label{lem:orbit_nu}
Let $ \lambda $ be a \textbf{generic} dominant coweight and $J\subset S_f$.
Then
\begin{enumerate}
    \item The $\nu$ value of the transverse cone of $\mathsf{G}_J(\lambda)$ in $\mathsf{Q}^\Phi(\lambda)$  is independent of $\lambda$. 

    \item The $\nu$ value of the transverse cones of  $\mathsf{G}_J(\lambda)$ and $\mathsf{G}_J(\lambda,w)$ are equal for all $w\in W_f$. 
    
    \item For $w\in W_f$ we have that $\vol(\mathsf{G}_J(\lambda))=\vol(\mathsf{G}_J(\lambda,w))$. Furthermore, $\relvol(\mathsf{G}_J(\lambda))=\relvol(\mathsf{G}_J(\lambda,w))$.
\end{enumerate}
\end{lemma}

Combining Lemma \ref{lem:orbit_nu} and Equation \eqref{eq: geofor sketch}, we get the existence in the generic case.

\begin{prop}[Existence in the generic case]\label{prop:geometric-formula-generic}
For every irreducible root system $\Phi$, there exists ${\mu_J^{\Phi}\in\mathbb{R}}$ such that for any \textbf{generic} dominant coweight $\lambda$,
\begin{equation}\label{eq: geofor final}
|\leq\theta(\lambda)|=\sum_{J\subset S_f}\mu_J^{\Phi}V_J^{\Phi}(\lambda).
\end{equation}
\end{prop}

On the other hand, we can express $\mathsf{Q}^\Phi(\lambda)$ as a Minkowski sum $m_1\mathsf{Q}^\Phi(\varpi_1^\vee)+\cdots+m_n\mathsf{Q}^\Phi(\varpi_n^\vee)$, where $\lambda=m_1\varpi_1^\vee+\cdots+m_n\varpi_n^\vee$. 
Using Equation \eqref{eq:complete_lattic_formula}, we get the quasi-polynomiality of $|\leq\theta(\lambda)|$ (see \cite[Theorem 7]{mcmullen1978lattice}).

\begin{prop}[Quasi-polynomiality]
\label{prop:quasi-polynomiality}
For every dominant coweight $\lambda = \sum_i m_i\varpi_i^\vee$ (generic or not), we have that $|\leq \theta(\lambda)|$ is a quasi-polynomial in $m_1,\dots,m_n$.
\end{prop}


We now prove the Geometric Formula.

\begin{proof}[Proof of Theorem \ref{thm:geometric-formula}]
Proposition \ref{prop:geometric-formula-generic} together with the fact that $V^\Phi_J$ are polynomials (by Lemma \ref{lem: vols as pols}) imply that $|\leq\theta(\lambda)|=\sum\mu_J^{\Phi}V_J^{\Phi}(\lambda)$ is a polynomial in the coordinates $m_1,\ldots,m_n$ of $\lambda$ (in the fundamental coweight basis) when they are positive integers. 
By Proposition \ref{prop:quasi-polynomiality} we know that $|\leq\theta(\lambda)|$ is in general a quasi-polynomial in the $m_i$'s.
Put $\mathbf{m}=(m_1,\ldots,m_n)$.
We have a polynomial $\sum\mu_J^{\Phi}V_J^{\Phi}(\mathbf{m})$ agreeing with the quasi-polynomial $|\leq\theta(\mathbf{m})|$ on the set $\bbZ_{>0}^n$.
Thus, they must agree on $\bbZ_{\geq0}^n$.
Therefore, formula \eqref{eq: geofor final} holds for every dominant coweight $\lambda$, generic or not, giving the existence in every case.

Finally, by Lemma \ref{lem: vols as pols}, the volume polynomials are linearly independent hence the coefficients $\mu_J^{\Phi}$ are unique.
\end{proof}

A direct consequence of the Geometric Formula \ref{thm:geometric-formula}, is that if $\Phi$ has rank $n$ and ${\lambda=(m_1,\ldots,m_n)}$ in the fundamental coweight basis, then ${|\leq\theta(\lambda)|}$ is a polynomial of degree $n$ in the ${m_1,\ldots,m_n}$. Taking the sum over a fixed rank ${|J|=d}$ gives the degree $d$ part of the polynomial. We call the coefficients $\mu_J^\Phi$ the \textit{geometric coefficients}.


\section{On the geometric coefficients \texorpdfstring{$\mu_J^\Phi$}{}}\label{sec: coefs}

We finish by giving some values of the geometric coefficients.
The coefficient corresponding to the empty set is easily determined. 
Using the Geometric Formula \eqref{geofordef}, we get
\begin{equation*}
    \mu_\emptyset^\Phi=\sum_{J\subseteq S_f}\mu_J^\Phi V_J^\Phi(\mathbf{0})=|\leq\theta(\mathbf{0})|
    =|\leq w_0|
    =|W_f|.
\end{equation*}

The coefficient corresponding to the set $S_f$ also has a nice expression.

\begin{lemma}\label{lem: biggeocoef}
    Let $\text{Vol}(A_\text{id})$ be the $n$-dimensional volume of the fundamental alcove. Then
\begin{equation*}
    \mu_{S_f}^\Phi=\dfrac{1}{\text{Vol}(A_\text{id})}.
\end{equation*}
\end{lemma}

In Table \ref{table1}, we show the values of $\mu_{S_f}^{\Phi}$, which were computed using \cite[Plates I,\ldots,VI]{Bour46}.

\begin{table}[ht]
\footnotesize
    \centering
\begin{tabular}{||c | c| c| c | c| c| c | c| c| c  ||} 
 \hline
 \mbox{Type} & $A_n$ & $B_n$ & $C_n$ & $D_n$  &  $E_6$  &  $E_7$ & $E_{8}$ & $F_4$ & $G_2$ \\ [0.5ex] 
 \hline\hline
$\mu_{S_f}^{\Phi}$ & $\displaystyle\frac{(n+1)!}{\sqrt{n+1}}$ & $n!2^{n-1}$ &$n!2^{n} $&$n!2^{n-4}$  & $ 24\sqrt{3} \cdot 6!  $ & $288\sqrt{2} \cdot 7!$ & $17280\cdot 8! $ & $576$ & $12\sqrt{3}$  \\
\hline
\end{tabular}
    \caption{Values of the geometric coefficient $\mu_{S_f}^{\Phi}$.}
    \label{table1}
    \normalsize
\end{table}

Now let $\Phi$ be the root system of type $A_n$ and let $D$ be the corresponding Dynkin diagram.
We say that $J\subseteq S_f$ is connected if the subgraph of $D$ corresponding to $J$ is connected.
For example, $\{s_1,s_2,\ldots,s_l\}\subset S_f$ is connected for every $1\leq l \leq n$.

In \cite[\S 6.2]{GeoFor2023}, we compute the geometric coefficients $\mu_J^{A_n}$ for connected subsets $J\subseteq S_f$.
To achieve this, we use the following Lemma.

\begin{lemma}\label{lem: simplex} For all $m\in\mathbb{Z}_{\geq0}$, and for all $1\leq k\leq n$,
\begin{equation}\label{eq: simplex}
    |\leq\theta(m\varpi_k)|=(n+1)! \, E_{k,n+1}(m),
\end{equation}
where $E_{k,n+1}$ is the Ehrhart polynomial of the hypersimplex 
\begin{equation*}
    \Delta_{k,n+1}=\left\{ x\in [0,1]^{n+1} \mid x_1+\cdots+x_{n+1}=k\right\}.
\end{equation*}
\end{lemma}

In \cite{Ferroni}, the author gave a polynomial expansion of $E_{k,d}(m)$.
On the other hand, the polynomial expansion of $|\leq\theta(m\varpi_k)|\in\bbR[m]$ via the Geometric Formula \ref{thm:geometric-formula}, depends on the polynomials $V_J^{A_n}(m\varpi_k)$.
They are of the form $V_J^{A_n}(m\varpi_k)=c_{k,J}m^{|J|}$, for some number $c_{k,J}$ (depending on the Eulerian numbers \cite[\text{A008292}]{oeis}).
The connectedness of $J$ is necessary (but not sufficient) to assure that $c_{k,J}\neq 0$.
After comparing coefficients in Equation \eqref{eq: simplex}, we get a system of linear equations which, upon solving, gives all the geometric coefficients of connected sets.

For example, for every $1\leq l\leq n$,
\begin{equation} 
     \mu_{\{s_1,s_2,\ldots,s_l\}}^{A_n} =\frac{l!}{\sqrt{l+1}}(n+1)\left[
\begin{matrix}
n+1 \\
l+1 \\
\end{matrix}
\right],   
\end{equation}
where the brackets denote the (unsigned) Stirling numbers of the first kind \cite[A008275]{oeis}.

\printbibliography

\end{document}
