2.1 Coefficients in the Klyachko algebra

The q-Klyachko algebra $\mathcal {K}$ is the commutative algebra over $\mathbb {C}(q)$ on the generators $\{u_i\;|\; i\in \mathbb {Z}\}$ subject to the following relations for all $i\in \mathbb {Z}$ :

$$ \begin{align*} (q+1)u_i^2=qu_iu_{i-1}+u_iu_{i+1}. \end{align*} $$

For a finite subset $I\subset \mathbb {Z}$ , let . By [Reference Nadeau and Tewari18, Proposition 3.9], the set $\mathcal {B}$ of such square-free monomials forms a linear basis for $\mathcal {K}$ . Given $c\in \mathcal {W}_r$ , we have

(2.2) $$ \begin{align} A_c(q)=(r)_q!\times\mathrm{ coefficient\ of}\ u_{[r]}\ \mathrm{ in\ the\ expansion\ of }\ u_1^{c_1}\cdots u_r^{c_r} \mathrm{ in }\ \mathcal{B}. \end{align} $$

2.2 Recurrence relation

The remixed Eulerian number $A_c(q)$ for $c=(c_1,\dots ,c_r)\in \mathcal {W}_{r}^{}$ is the unique polynomial satisfying the initial condition $A_{(1^{r})}(q)=(r)_q!$ and the relation

(2.3) $$ \begin{align} (q+1)A_c(q)=q A_{(\dots,c_{i-1}+1,c_{i}-1,\dots)}(q)+A_{(\dots,c_{i}-1,c_{i+1}+1,\dots)}(q)\ \mathrm{ for\ any }\ i\ \mathrm{ satisfying }\ c_i\geq 2. \end{align} $$

On the right-hand side we ignore the ill-defined terms in the case $i=1$ or $i=r$ .

A more efficient recurrence based approach is as follows. The initial condition continues to be $A_{(1^r)}(q)=(r)_q!$ . Otherwise, consider i such that $c_i\geq 2$ . Let $\mathrm {Supp}(c)$ denote the support of c, that is, the set of all indices j such that $c_j>0$ . Let $[a,b]$ be the maximal interval in $\mathrm {Supp}(c)$ containing i. We let $L_i(c)$ (resp. $ R_i(c)$ ) denote the composition obtained by decrementing $c_i$ by $1$ and incrementing $c_{a-1}$ (resp. $c_{b+1}$ ) by $1$ . Then we have

(2.4) $$ \begin{align} (b-a+2)_qA_{c}(q)=q^{i-a+1}(b-i+1)_qA_{L_i(c)}(q)+(i-a+1)_qA_{R_i(c)}(q). \end{align} $$

Again, if $a=1$ (resp. $b=r$ ), then $L_i(c)$ (resp. $R_i(c)$ ) is not well defined, and the corresponding remixed Eulerians are $0$ .

2.3 Probabilistic interpretation

Consider the integer line $\mathbb {Z}$ as a set of sites. A configuration is an $\mathbb {N}$ -vector $c=(c_i)_{i\in \mathbb {Z}}$ with $\sum _ic_i<\infty $ , which we visualize as a finite set of particles with $c_i$ particles stacked at site i. Stable configurations are those for which $c_i\leq 1$ for all i. They are identified with finite subsets of $\mathbb {Z}$ via their support.

Given jump probabilities $q_L,q_R\geq 0$ satisfying $q_L+q_R=1$ , consider the following process with state space the set of configurations. Suppose we are in a configuration c. If c is stable, the process stops. Otherwise, pick any i such that $c_i>1$ and move the top particle at site i to the top of site $i-1$ (resp. $i+1$ ) with probability $q_L$ (resp. $q_R$ ). The process ends in a stable configuration with probability $1$ . Furthermore, it is known that the probability of ending in a particular stable configuration does not depend on the choice of site i at each step.

For a finite subset $I\subset \mathbb {Z}$ , we can then define $\mathbb {P}_c(I)$ to be the probability that the process starting at configuration c ends in the stable configuration given by I. Assume $q_R>0$ and let . By [Reference Nadeau and Tewari18, Proposition 5.1], for $c\in \mathcal {W}_{r}^{}$ we have

(2.5) $$ \begin{align} \mathbb{P}_c([r])=\frac{A_c(q)}{(r)_q!}. \end{align} $$

Note that we have then $q_L=\frac {q}{1+q}$ and $q_R=\frac {1}{1+q}$ .

Remark 2.1. Using this interpretation one has the following ‘cyclic sum rule’ [Reference Nadeau and Tewari18, Proposition 5.3]: Given $c=(c_1,\dots ,c_{r})\in \mathcal {W}_{r}^{}$ , let $\mathsf {Cyc}(c)$ be the set of all $c'\in \mathcal {W}_{r}^{}$ such that $(c',0)$ is a cyclic rotation of $(c,0)$ . Then

(2.6) $$ \begin{align} \sum_{c'\in \mathsf{Cyc}(c)}A_{c'}(q)=(r)_q!. \end{align} $$

There are $\mathrm {Cat}_r$ sets of the form $\mathsf {Cyc}(c)$ so that summing equation (2.6) over all of them proves Theorem 1.3 (8).

We record a slightly different way to think about the previous process as it will be particularly helpful.

Sequential process: Fix any word $\mathbf {i}=(i_1,\ldots ,i_r)\in [r]^r$ . Starting with the empty configuration, drop particles one at a time at sites $i_1,i_{2},\ldots , i_r$ , and stabilize at every step. Each such step involves the particle either landing on an interval of occupied sites in the current stable configuration, and then proceeding to exit either to the left or to the right, or landing on an unoccupied site in which case it stabilizes immediately. We denote by $\mathbb {P}^{\mathbf {i}}(I)$ the probability to end up with the stable set I.

Let $\mathrm {cont}(\mathbf {i})=(c_1,\dots ,c_r)\in \mathcal {W}_{r}^{}$ , where $c_j$ is the the number of instances of j in $\mathbf {i}$ for $j\in [r]$ . Then we have

(2.7) $$ \begin{align}\mathbb{P}^{\mathbf{i}}(I)=\mathbb{P}_{\mathrm{cont}(\mathbf{i})}(I)\end{align} $$

and thus by equation (2.5),

(2.8) $$ \begin{align} \mathbb{P}^{\mathbf{i}}([r])=\frac{A_{\mathrm{cont}(\mathbf{i})}(q)}{(r)_q!}. \end{align} $$

3.1 A recursive formula for $\mathbb {P}^{\mathbf {i}}([a,b])$

Consider $\mathbf {i}=i_1\cdots i_r$ , and let us compute $\mathbb {P}^{\mathbf {i}}([a,b])$ , where we assume that $b-a+1=r$ and $i_j\in [a,b]$ for all j since $\mathbb {P}^{\mathbf {i}}([a,b])=0$ otherwise.

Let us condition on the stable set obtained just before dropping the last particle $i_r$ . This set is necessarily of the form $[a,b]\setminus \{j\}=[a,j-1]\sqcup [j+1,b]$ for $j\in [a,b]$ in order to have $\mathbb {P}^{\mathbf {i}}([a,b])\neq 0$ . We thus get

(3.1) $$ \begin{align} \mathbb{P}^{\mathbf{i}}([a,b])=\sum_{j=a}^b\mathbb{P}^{i_1\cdots i_{r-1}}([a,b]\setminus\{j\})\,\mathbb{P}^{i_r}([a,b],j), \end{align} $$

where $\mathbb {P}^i([a,b],j)$ is the probability to reach the stable set $[a,b]$ from $[a,b]\setminus \{j\}$ after dropping a particle at the site $i\in [a,b]$ and stabilizing.

The probability $\mathbb {P}^{i_1\cdots i_{r-1}}([a,b]\setminus \{j\})$ is clearly zero unless

• (*) there are $j-a$ indices t such that $i_t\in [a,j-1]$ and $b-j$ indices t such that $i_t\in [j+1,b]$ .

Indeed, the site j is empty at all times before the last step, so the particles that are dropped on either side of it stay on that side during the process. Assuming (*) is satisfied, let $\mathbf {i'},\mathbf {i"}$ be the two subsequences of $\mathbf {i}$ consisting of $i_t<j$ and $i_t>j$ , respectively. Then we have

(3.2) $$ \begin{align} \mathbb{P}^{i_1\cdots i_{r-1}}([a,b]\setminus\{j\})=\mathbb{P}^{\mathbf{i'}}([a,j-1])\;\mathbb{P}^{\mathbf{i"}}([j+1,b]). \end{align} $$

The other factor $\mathbb {P}^{i_r}([a,b],j)$ in equation (3.1) is also straightforward to compute: If $i_r>j$ , then the particle must exit to the left of the interval $[j+1,b]$ while if $i_r\leq j$ , it must exit to the right of the interval $[a,j-1]$ . These are the well-known exit probabilities of a biased discrete random walk on an interval [Reference Feller4]. We thus obtain explicitly $\mathbb {P}^{i_r}([a,b],j)=\mathrm {wt}_q([a,b],j,i_r)$ , where for any $i\in [a,b]$ ,

(3.3) $$ \begin{align} \mathrm{wt}_q([a,b],j,i)=\left\lbrace \begin{array}{ll}\frac{(b-i+1)_q}{(b-j+1)_q}q^{(i-j)} & i> j, \\ \frac{(i-a+1)_q}{(j-a+1)_q} & i \leq j. \end{array} \right. \end{align} $$

The reader may recognize these as q-deformations of the weights $\mathrm {wt}(i,j)$ in [Reference Postnikov21, Equation 17.1], which can therefore be interpreted as exit probabilities in the symmetric case $q=1$ .

Substituting equations (3.2) and (3.3) in equation (3.1) gives a recursive way to compute $\mathbb {P}^{\mathbf {i}}([a,b])$ :

(3.4) $$ \begin{align} \mathbb{P}^{\mathbf{i}}([a,b])=\sum_{j\mathrm{ satisfying} {(\ast)}}\mathbb{P}^{\mathbf{i'}}([a,j-1])\,\mathbb{P}^{\mathbf{i"}}([j+1,b])\,\mathrm{wt}_q([a,b],j,i_r). \end{align} $$

The initial condition is simply $\mathbb {P}^{\epsilon }(\emptyset )=1$ , where $\epsilon $ is the empty word.

3.2 Postnikov trees

Given a binary tree T, we let $\mathrm {Nodes}(T)$ denote its set of nodes. A standard labeling of a binary tree T with r nodes is a bijective labeling of $\mathrm {Nodes}(T)$ with integers drawn from $[r]$ . The binary search labeling of T is the standard labeling given recursively by traversing the left subtree first, then the root, then the right subtree, and assigning a node the label $i\in [r]$ if it is the ith node encountered in this traversal. This is illustrated in Figure 1 by the labels inside the nodes. Let the bs-label of a node be this label .

Figure 1 With $\mathbf {i}=34717843$ , a Postnikov tree is represented on the left: The binary search labeling is pictured inside the nodes, while the unique decreasing labeling is between brackets in blue. The associated history of the sequential process is illustrated in the second and third panels, reading each panel from top to bottom.

Given a node v in T, let $[l_v,r_v]$ refer to the set of bs-labels of its descendants in T (itself included). A coloring $f:\mathrm {Nodes}(T)\to \mathbb {Z}$ is compatible if for all v, we have $f(v)\in [l_v,r_v]$ . In particular, if v has no children, then $f(v)$ is necessarily the bs-label of v. The weight $\mathrm {wt}(T,f)$ is then defined as

$$\begin{align*}\mathrm{wt}(T,f)=\prod_{v\in T}\mathrm{wt}_q([l_v, r_v],v,f(v)).\end{align*}$$

We call a labeled tree decreasing if it has a standard labeling such that the label of a node is larger than the labels of all its descendants. On the leftmost panel in Figure 1, the exterior labels (in blue) give a decreasing labeling of the underlying tree.

The decreasing labeling is necessarily unique if it exists. Indeed, suppose T is $\mathbf {i}$ -compatible, and let $\mathrm {dec}$ be as in the definition. The root receives the greatest label. Let the bs-label of the root be j. By the definition of compatibility, if t is the $\mathrm {dec}$ -label of a node in the left (resp. right) subtree, then $i_t<j$ (resp. $i_t>j$ ). Thus, the sets of $\mathrm {dec}$ -labels in both subtrees are determined by $\mathbf {i}$ . One can then conclude by induction that the whole $\mathrm {dec}$ -labeling of T is determined by $\mathbf {i}$ .

For instance, the tree T in Figure 1 is $\mathbf {i}$ -compatible, where $\mathbf {i}=34717843$ . Furthermore, we have

$$\begin{align*}\mathrm{wt}(T,\mathbf{i})=\frac{(1)_q }{(1)_q}\cdot \frac{(1)_q }{(1)_q} \cdot \frac{(1)_q }{(1)_q}\cdot \frac{(1)_q }{(1)_q}\cdot \frac{(1)_q }{(2)_q}\cdot q^2\frac{(1)_q }{(3)_q}\cdot q^2\frac{(1)_q }{(3)_q}\cdot\frac{(3)_q }{(5)_q}=\frac{q^4}{(2)_q(3)_q(5)_q}. \end{align*}$$

The order of the terms on the right-hand side is obtained by considering the weights of nodes v encountered according to the decreasing labeling.

Let $\mathcal {P}(\mathbf {i})$ be the set of $\mathbf {i}$ -compatible trees. These are referred to as Postnikov trees in the introduction, with content $\mathrm {cont}(\mathbf {i})$ determined by the multiplicity of each letter in $\mathbf {i}$ .

Theorem 3.3. For any $\mathbf {i}\in [r]^r$ , we have

$$ \begin{align*} \mathbb{P}^{\mathbf{i}}([r])=\sum_{T\in\mathcal{P}(\mathbf{i})}\mathrm{wt}(T,\mathbf{i}). \end{align*} $$

Proof. This follows from the recurrence (3.4). Let us specify that recurrence to the case $a=1,b=r$ and simply write $\mathbb {P}^{\mathbf {i}}$ instead of $\mathbb {P}^{\mathbf {i}}([r])$ . Write also $\mathbf {i^2}$ for the word $\mathbf {i"}$ , where all letters are decreased by j, so that they are between $1$ and $r-j$ . We obtain the recurrence

$$\begin{align*}\mathbb{P}^{\mathbf{i}}=\sum_{j\mathrm{ satisfying}{(\ast)}}\mathbb{P}^{\mathbf{i'}}\,\mathbb{P}^{\mathbf{i^2}}\,\mathrm{wt}_q([r],j,i_r). \end{align*}$$

We need to show that also satisfies such a recurrence. Given a tree in $\mathcal {P}(\mathbf {i})$ , let $j-1$ and $r-j$ be the sizes of its left and right subtrees, respectively. The root has necessarily label $i_r$ and thus weight $\mathrm {wt}_q([r],j,i_r)$ . The compatibility condition imposes that all labels of the left subtree $T'$ are between $1$ and $j-1$ , while all labels on the right subtree $T"$ are between $j+1$ and r. This corresponds precisely to the condition (*) that has to be satisfied, and we let $\mathbf {i'},\mathbf {i"}$ be the subsequences of $\mathbf {i}$ corresponding to $T'$ and $T"$ . Then $T'$ is in $\mathcal {P}(\mathbf {i'})$ , while $T"$ is in $\mathcal {P}(\mathbf {i"})$ . By subtracting j from all labels in $T"$ , we obtain a tree $T^2$ in $\mathcal {P}(\mathbf {i^2})$ , and the recurrence

$$\begin{align*}S(\mathbf{i})=\sum_{j\mathrm{ satisfying}{(\ast)}}S(\mathbf{i'})\,S(\mathbf{i^2})\,\mathrm{wt}_q([r],j,i_r). \end{align*}$$

This is precisely the recurrence satisfied by the $\mathbb {P}^{\mathbf {i}}$ , and we obtain the desired result since the initial conditions match: for $i\in \mathbb {Z}$ , $\mathbb {P}^{i}=S(i)=1$ if $i=1$ and $0$ otherwise.

A direct byproduct of the proof is that trees in $\mathcal {P}(\mathbf {i})$ correspond precisely to a ‘history’ of the sequential process started with $\mathbf {i}$ . The decreasing tree encodes the filling order in which sites get occupied along the process: The kth site to be occupied is $j=bs(v)$ , where v is the node with $\mathrm {dec}(v)=k$ . This is nothing but the standard bijection between decreasing trees and permutations, which we recall at the beginning of Section 6.2. Such a filling order is possible with $\mathbf {i}$ as initial word precisely when the corresponding decreasing tree is $\mathbf {i}$ -compatible. In that case, the weight of the tree is the probability of that ordering.

Equation (2.8) now immediately yields the following q-analogue of [Reference Postnikov21, Theorem 17.7].

Theorem 3.5. For any $c\in \mathcal {W}_{r}^{}$ and any $\mathbf {i}\in [r]^r$ such that $\mathrm {cont}(\mathbf {i})=c$ , we have

$$ \begin{align*} A_{c}(q)=\sum_{T\in\mathcal{P}(\mathbf{i})} (r)_q!\,\mathrm{wt}(T,\mathbf{i}). \end{align*} $$

Example 3.6. Consider $\mathbf {i}=2244$ . Then $\mathrm {cont}(\mathbf {i})=(0,2,0,2)$ . Figure 2 shows the relevant Postnikov trees.

Figure 2 The two Postnikov trees for $\mathbf {i}=2244$ .

Theorem 3.5 now tells us that

$$\begin{align*}A_{(0,2,0,2)}(q)=(4)_q!\cdot\frac{1}{(2)_q}\cdot q^3\frac{(1)_q}{(4)_q}+ (4)_q!\cdot q\frac{1}{(2)_q}\cdot q\frac{(1)_q}{(2)_q}=q^2(1+q+q^2)^2. \end{align*}$$

4.1 An extension of q-binomial coefficients

Remark that both items (8) and (9) of Theorem 1.3 are in this subfamily $EB_r$ . The following explicit product formula proves and generalizes them.

Proposition 4.2. For any $c\in EB_r$ with k as in Definition 4.1, we have

(4.1) $$ \begin{align} A_{c}(q)=q^{d_c}\genfrac(){0pt}{}{r}{k}_q\;\prod_{i=1}^k (i)_q^{c_i}\; \prod_{i=1}^{r-k} (i)_q^{c_{r+1-i}}, \end{align} $$

where $d_c=\displaystyle \sum _{j=1}^{r-k}\sum _{i=1}^j(c_{r+1-i}-1)$ .

Note that by equation (4.1), $d_c$ is the smallest exponent of q occurring in $A_c(q)$ . We give a formula for this exponent in equation (5.3) that is valid for any $c\in \mathcal {W}_{r}^{}$ , and specializes to the expression above when $c\in EB_r$ .

Proof. We use the probabilistic interpretation of $A_c(q)$ in Section 2.3 in its sequential version. We choose the word

$$\begin{align*}\mathbf{i}=1^{c_1}2^{c_2}\cdots k^{c_k} \;r^{c_r} (r-1)^{c_{r-1}}\cdots (k+1)^{c_{k+1}}.\end{align*}$$

It corresponds to the following dropping order of particles: Start with all $c_1$ particles at site $1$ , then all $c_2$ particles at site $2$ , and so on until we drop $c_k$ particles at site k. Then, drop all particles at site r, then at site $r-1$ , and so on down to $k+1$ .

The first part of the definition of $EB_r$ implies that in order to end with the stable configuration $\{1,\ldots ,r\}$ , the following must hold: For $i\leq k-1$ , the intermediate stable configuration after the ith step is the interval $\{1,\ldots ,i\}$ , and the $(i+1)$ -st particle either drops at site $i+1$ or drops on the previous interval and exits to the right. The probability of this happening is $\frac {1}{(k)_q!}\displaystyle \prod _{i=1}^k(i)_q^{c_i}$ by equation (3.3).

For the remaining particles, the situation is symmetric of the first part, since the stable interval $\{1,\ldots ,k\}$ does not interfere with the analysis. The probability of success in this second half is worked out to be $\frac {q^{d_c}}{(r-k)_q!}\displaystyle \prod _{i=1}^{r-k} (i)_q^{c_{r+1-i}}$ by equation (3.3) again.

Now, by equation (2.5), we obtain $A_c(q)$ by multiplying these two expressions together with $(r)_q!$ , thus giving the desired expression.

In terms of the tree interpretation from Section 3, we have in fact shown that for words $\mathbf {i}$ considered in the preceding proof, there is a unique compatible tree. We further note that Proposition 4.2 is the q-analogue of [Reference Liu15, Theorem 4.4]. Finally, the expression for $A_c(q)$ for $c\in EB_r$ motivates understanding the valuation $d_c$ in general; we return to this in Section 5.

Example 4.3. Consider $c=(2,0,1,0,2,1)\in EB_6$ . Then the k in Definition 4.1 equals $3$ . We have $d_c=c_6-1+c_6+c_5-2+c_6+c_5+c_4-3=1$ . The reader may verify that

$$\begin{align*}A_c(q)=q^{1}\genfrac(){0pt}{}{6}{3}_q(1)_q^2(3)_q\,(2)_q^2(1)_q. \end{align*}$$

4.2 Interval support and q-hit numbers

We now focus on the case where $\mathrm {Supp}(c)$ is an interval. That is, c can be written as $c=0^i\beta 0^{r-k-i}$ where $\beta \vDash r$ is a (strong) composition with . Thus, the first i and the last $r-k-i$ entries in c are all $0$ .

By [Reference Nadeau and Tewari18, Proposition 5.6], we have

(4.2) $$ \begin{align} \sum_{j\geq 0}t^j\prod_{i=1}^k(j+i)_q^{\beta_i}=\frac{\displaystyle\sum_{i=0}^{r-k}A_{0^i\beta 0^{r-k-i}}(q) t^i}{(t;q)_{r+1}}. \end{align} $$

Here, .

Remark 4.4. If $\beta $ has a single part, so $\beta =(r)$ , we get

(4.3) $$ \begin{align} \sum_{j\geq 0}(j+1)_q^{r}t^j=\frac{\displaystyle\sum_{i=0}^{r-k}A_{0^i,r, 0^{r-k-i}}(q) t^i}{(t;q)_{r+1}}. \end{align} $$

This shows Theorem 1.3 (3), since the left-hand side was already considered by Carlitz [Reference Carlitz1] and this shows by comparison that $A_{0^i,r, 0^{r-k-i}}(q)$ counts permutations in $\mathbb {S}_r$ with i descents with q-weight given by the major index. An alternative proof of this is given in [Reference Mittelstaedt17].

As briefly touched upon in [Reference Nadeau and Tewari18, Section 5.3], the family of remixed Eulerian numbers $A_{0^i\beta 0^{r-k-i}}(q)$ coincides with polynomials enumerating q-hit numbers appearing in the work of Garsia–Remmel [Reference Garsia and Remmel5]. This observation is also instrumental in order to relate these numbers to recent work around chromatic symmetric functions; see [Reference Nadeau and Tewari19]. We now justify this claim.

Fix r and consider $\lambda =(\lambda _1,\lambda _2,\ldots ,\lambda _r)$ with $\lambda _i$ integers satisfying $r\geq \lambda _1\geq \cdots \geq \lambda _r\geq 0$ . So $\lambda $ can be seen as a Young diagram in an $r\times r$ square; see Figure 3 with $r=6$ and $\lambda =(5,5,3,3,3,0)$ . Following [Reference Garsia and Remmel5], the q-hit numbers $H_j(\lambda ,q)$ can be defined by:

(4.4) $$ \begin{align} \sum_{j\geq 0}t^j\prod_{i=1}^{r}(i-\lambda_{r+1-i}+j)_q=\frac{\displaystyle\sum_{j=0}^r H_j(\lambda,q)t^j}{(t;q)_{r+1}}. \end{align} $$

Figure 3 Partition in a square (left), superimposition with the graph of a permutation.

We will now compare the left-hand sides of equations (4.2) and (4.4). We will show that every nonzero q-hit polynomial is a remixed Eulerian number $A_c(q)$ where c has interval support and vice versa.

For $i=1,2,\dots , r$ , the values $i-\lambda _{r+1-i}$ occurring in equation (4.4) go from $1-\lambda _r\leq 1$ to $r-\lambda _1\geq 0$ with successive differences in $\{1,0,-1,-2,\dots \}$ . Geometrically, these values express the algebraic distance in each row between $\lambda $ and the staircase , computed from bottom to top. In our running example, we have the sequence of values $1,-1,0,1,0,1$ , as Figure 3 reveals.

A moment’s thought shows that these values must thus form an interval, say $[a,a+k-1]$ with $k\geq 1$ , that necessarily contains $0$ or $1$ . Define $\beta _i(=\beta _i(\lambda ))$ to be the number of times that the values $a+i-1$ is obtained so that is a composition of length k. The coefficient $C_j$ of $t^j$ on the left-hand side of equation (4.4) can be rewritten as

$$\begin{align*}\prod_{i=1}^k(j+a+i-1)_q^{\beta_i}. \end{align*}$$

If $a=1$ , we recognize this as the coefficient of $t^j$ on the left-hand side of equation (4.2) with $\beta =B(\lambda )$ . We thus have $H_j(\lambda ,q)=A_{0^j\beta 0^{r-k-j}}(q)$ for $j=0,\ldots ,r-k$ and is zero otherwise.

If $a\neq 1$ , one has $a\leq 0$ to ensure that $0$ or $1$ belong to $[a,a+k-1]$ , which also implies $k\geq 1-a$ . Thus $C_j=0$ for $j=0,\ldots ,-a$ and $C_{j-a+1}= \displaystyle \prod _{i=1}^k(j+i)_q^{\beta _i}$ . The left-hand side of equation (4.4) is then $t^{1-a}$ times the left-hand side of equation (4.2). It follows that $H_j(\lambda ,q)=A_{0^{j-1+a}\beta 0^{r-k+1-a-j}}(q)$ for $j=1-a,\ldots ,r-k+1-a$ and is zero otherwise.

We have shown that every nonzero q-hit polynomial is a remixed Eulerian number $A_c(q)$ , where c has interval support. Conversely, given a composition $\beta =(\beta _1,\ldots ,\beta _k)$ , it is always possible to construct $\lambda $ such that $B(\lambda )=\beta $ , and thus, $H_j(\lambda ,q)=A_{0^j\beta 0^{r-k-j}}(q)$ as above.

Indeed, let $l^r(\beta )=(l_1,\ldots ,l_r)$ be obtained by concatenating $\beta _k$ occurrences of k, $\beta _{k-1}$ occurrences of $k-1$ and so on until $\beta _1$ occurrences of $1$ . If one defines with componentwise subtraction, then $\lambda $ corresponds to a Young diagram inside an $r\times r$ square that satisfies $B(\lambda )=\beta $ .

5.1 Degree and valuation

The following simple relation was recorded as Theorem 1.3 (2) in the introduction. For any finite sequence $a=(a_1,a_2,\ldots ,a_k)$ , define $\mathrm {rev}(a)=(a_k,a_{k-1},\ldots ,a_1)$ .

Lemma 5.1. Let $c=(c_1,\dots ,c_{r})\in \mathcal {W}_{r}^{}$ . Then we have

$$\begin{align*}A_c(q)=q^{\binom{r}{2}}A_{\mathrm{rev}(c)}(q^{-1}). \end{align*}$$

Given $c\in \mathcal {W}_{r}^{}$ , we let $D_c$ denote the degree of $A_c(q)$ . We also define $d_c$ as the valuation of $A_c(q)$ , that is, the smallest exponent of q with a nonzero coefficient.

It turns out that $A_c(q)$ is symmetric with respect to the interval $[d_c,D_c]$ , as we shall show in Theorem 5.6. To this end, we collect some notation that helps describe $D_c$ and $d_c$ combinatorially. For $t\in \mathbb {R}$ , we use

The following pictorial perspective for $c\in \mathcal {W}_{r}^{}$ is occasionally useful. Recall that a Łukasiewicz path is a (finite) lattice path beginning at the origin that takes steps corresponding to translations by $(1,k)$ for $k\geq -1$ . Attach a Łukasiewicz path $P_c$ with $c=(c_1,\dots ,c_r)$ by starting at the origin and translating by $(1,c_i-1)$ as c is read from left to right. See Figure 4. For $i\in [r]$ , we define $h_i(c)$ to be the ordinate on $P_c$ after the ith step. More precisely, $h_i(c)=\displaystyle\sum _{1\leq j\leq i}(c_j-1)$ . Note that $h_r(c)$ is necessarily $0$ . We let

(5.1)

(5.2)

Figure 4 $P_{c}$ when ${c}=(0,3,0,0,0,1,3)$ .

Theorem 5.3. Let $c=(c_1,\dots ,c_{r})\in \mathcal {W}_{r}^{}$ . The following equalities hold:

(5.3) $$ \begin{align}d_c&=H^{-}(c),\end{align} $$

(5.4) $$ \begin{align}D_c&=\binom{r}{2}-\sum_{1\leq i\leq r-1} (h_i(c))^+.\end{align} $$

The reader will note that equation (5.3) generalizes the result of Remark 5.2, as well as the power of q in Proposition 4.2.

Proof. First, we establish equation (5.3). The claim is true when $c=(1^{r})$ . In this case, $A_c(q)=(r)_q!$ and we have $d_c=0=H^{-}(c)$ . We proceed by (downward) induction on the number of parts in c that equal $1$ .

Consider $i\in [r]$ such that $c_i\geq 2$ . Let $[a,b]$ be the maximal interval in $\mathrm {Supp}(c)$ containing i. We have by equation (2.4) that

(5.5) $$ \begin{align} (b-a+2)_qA_{c}(q)=q^{i-a+1}(b-i+1)_qA_{L_i(c)}(q)+(i-a+1)_qA_{R_i(c)}(q). \end{align} $$

It follows that the following relation holds

(5.6) $$ \begin{align} d_c=\min(i-a+1+d_{L_i(c)}, d_{R_i(c)}). \end{align} $$

We want to check that $H^-(c)$ satisfies the same recurrence. Consider the boundary cases first. If $a=1$ , only $R_i(c)$ is defined, and it is easily checked that $H^{-}(c)=H^{-}(R_i(c))$ . If $b=r$ , only $L_i(c)$ is defined and we need to check that $H^{-}(c)=i-a+1+H^{-}(L_i(c))$ . Note that we have $c_{j}>0$ for all $j\in [a,r]$ and $c_{a-1}=0$ . From this, and the fact that $h_{r}(c)=0$ , it follows that $h_j(c)\leq 0$ for all $j\in [a-1,r]$ . Furthermore since $c_i\geq 2$ we are in fact guaranteed that $h_{j}(c)<0$ for $j\in [a-1,i-1]$ . Now, $h(L_i(c))$ is obtained from $h(c)$ by adding $1$ to all entries $h_j(c)$ for $j\in [a-1,i-1]$ and leaving the rest unchanged. Since $h_j(c)<0$ for such j, we still have $h_j(L_i(c))\leq 0$ . It follows that $H^{-}(c)=i-a+1+H^{-}(L_i(c))$ in this case.

We now consider the generic situation where $1<a\leq b<r$ . The arguments are similar to those just presented, and we keep the exposition terse. We set $h_0(c)=0$ . Now, note that the hypotheses on $a,b,i$ are equivalent to

$$\begin{align*}h_{a-2}>h_{a-1}\leq h_{a}\leq \dots \leq h_{b-1}\leq h_b>h_{b+1}\end{align*}$$

and $h_{i-1}<h_{i}$ . Then $h(L_i(c))$ is obtained by adding from $h(c)$ by adding $1$ to $h_{a-1},\ldots ,h_{i-1}$ , while $h(R_i(c))$ is obtained from $h(c)$ by subtracting $1$ from $h_{i},\ldots ,h_{b}$ .

It is clear from this description that $H^-(c) \leq i-a+1+H^-({L_i(c)})$ and $H^-(c)\leq H^-({R_i(c)})$ . To show that it is equal to one of them, consider the sign of $h_i$ . If $h_i>0$ , then $h_i,\ldots ,h_b>0$ from which it follows $H^-(c)=H^-(R_i(c))$ . If $h_i\leq 0$ , then $h_{a-1},\ldots ,h_{i-1}< 0$ , and so these $i-a+1$ values imply $H^-(c)=i-a+1+H^-({L_i(c)})$ .

We finally establish equation (5.4). It follows from Lemma 5.1 that

$$\begin{align*}d_{\mathrm{rev}(c)}+D_c=\binom{r}{2}. \end{align*}$$

Now, $h_i(\mathrm {rev}(c))=-h_{r-i}(c)$ for $i\in [0,r]$ by a direct computation. Using equation (5.3), the claim follows.

In terms of the path $P_c$ , we have that $d_c$ equals the sum of the absolute values of the heights of all lattice points that lie strictly below the x-axis, and $D_c$ equals $\binom {r}{2}-$ sum of the heights of all lattice points that are strictly above the x-axis.

Example 5.4. For $c=(0,3,0,0,0,1,3)$ , the Łukasiewicz path in Figure 4 tells us that

$$ \begin{align*} d_c&=1+1+2+2=6\\ D_c&=\binom{7}{2}-1=20. \end{align*} $$

As a matter of fact, the full polynomial $A_{c}(q)$ is given by

$$\begin{align*}2 q^{20} + 6 q^{19} + 11 q^{18} + 18 q^{17} + 27 q^{16} + 35 q^{15} + 40 q^{14} &+ 42 q^{13} + 40 q^{12} + 35 q^{11}\\ &+ 27 q^{10} + 18 q^{9} + 11 q^{8} + 6 q^{7} + 2 q^{6}. \end{align*}$$

We remark that we have a symmetric polynomial above. This is quite surprising, as no symmetry is apparent in c. It turns out to be a general fact, valid for all polynomials $A_c(q)$ , that we will now prove together with unimodality.

5.2 Symmetry and unimodality

Let us say that a polynomial $P(q)$ is $\mathrm {psu}(N)$ if it has positive coefficients and is unimodal and symmetric with respect to $N/2$ . Note that N is then the sum of the degree and valuation of P. We have the following classical properties; see [Reference Haglund7] for instance.

We introduce the reduced remixed Eulerian numbers [Reference Nadeau and Tewari18]

(5.7)

where $m_1,\dots ,m_p$ are the cardinalities of the maximal intervals $I_1,\dots ,I_p$ in $\mathrm {Supp}(c)$ , ordered from left to right. Using the notations $i,a,b,L_i(c),R_i(c)$ in the recurrence relations (2.4) for ${A}_{c}(q)$ , the $\tilde {A}_{c}(q)$ satisfy the modified recurrence relation ([Reference Nadeau and Tewari18, Proof of Prop. 5.4])

(5.8) $$ \begin{align} \tilde{A}_{c}(q)=b_L\;q^{i-a+1}(b-i+1)_q\;\tilde{A}_{L_i(c)}(q)+b_R\;(i-a+1)_q\;\tilde{A}_{R_i(c)}(q), \end{align} $$

where $b_L,b_R$ are defined as follows. Let j be the index such that $I_j=[a,b]$ .

• • If $j>1$ and $I_{j-1}=[f,a-2]$ for a certain f, then $b_L=\genfrac (){0pt}{}{b-f+1}{b-a+2}_q$ . Otherwise, $b_L=1$ .

• • If $j<p$ and $I_{j+1}=[b+2,g]$ for some $g\leq r$ , then $b_R=\genfrac (){0pt}{}{g-a+1}{b-a+2}_q$ . Otherwise, $b_R=1$ .

In any case, note that both $b_R$ and $b_L$ are $\mathrm {psu}(N)$ for some N (in general distinct): Indeed, the Gaussian binomial coefficient $\genfrac (){0pt}{}{n}{k}_q$ is known to be $\mathrm {psu}(k(n-k))$ .

Proof. We establish some notation for convenience. Suppose the lengths of the maximal intervals in $\mathrm {Supp}(c)$ are $m_1$ through $m_p$ . We let

(5.9)

We have $A_{c}=\tilde {A}_{c}\prod _j (m_j)_q!$ , and each $(m_j)_q!$ is $\mathrm {psu}(\binom {m_j}{2})$ . By Lemma 5.5, the result for $A_c$ thus follows from the one for $\tilde {A}_{c}$ . We proceed to prove the latter by induction on .

The base case corresponds to $c=(1^r)$ , for which $\tilde {A}_{c}(q)=1$ and the claim is clearly true. Now, assume $e(c)>0$ , and consider the recurrence (5.8) for a fixed i with $c_i\geq 2$ : we retain the notations $a,b,L_i(c),R_i(c)$ . Note first that $d_c+D_c=\binom {r}{2}-H(c)$ by summing the expressions in equations (5.3) and (5.4). It then follows from the description of $h(L_i(c))$ and $h(R_i(c))$ given in the proof of equation (5.3) that $d_{L_i(c)}+D_{L_i(c)}=d_c+D_c-(i-a+1)$ and $d_{R_i(c)}+D_{R_i(c)}=d_c+D_c+(b-i+1)$ .

Since $e(L_i(c))=e(R_i(c))=e(c)-1$ , we can apply induction to conclude that $\tilde {A}_{L_i(c)}(q)$ and $\tilde {A}_{R_i(c)}(q)$ are $\mathrm {psu}\left (\binom {r}{2}-H(L_i(c))-n(L_i(c))\right )$ and $\mathrm {psu}\left (\binom {r}{2}-H(R_i(c))-n(R_i(c))\right )$ , respectively. Let $B_i$ and $C_i$ denote the left and right summands on the right-hand side of equation (5.8). It will suffice to show that $B_i$ and $C_i$ are both $\mathrm {psu}\left (\binom {r}{2}-H(c)-n(c)\right )$ ; by Lemma 5.5 so is their sum $\tilde {A}_c$ which then completes the proof.

We focus on $B_i$ , the proof for $C_i$ being entirely similar. Assume first that $b_L=1$ . Then

(5.10) $$ \begin{align} \deg(B_i)+\mathrm{val}(B_i)&=2(i-a+1)+b-i+\binom{r}{2}-H(L_i(c))-n(L_i(c))\nonumber\\ &=b+i-2a+2+\binom{r}{2}-H(L_i(c))-n(L_i(c)). \end{align} $$

Note that $H(L_i(c))-H(c)=i-a+1$ . Since $b_L=1$ , we know that $n(L_i(c))-n(c)=b-a+1$ . Thus, we may rewrite equation (5.10) as

(5.11) $$ \begin{align} \deg(B_i)+\mathrm{val}(B_i)=\binom{r}{2}-H(c)-n(c), \end{align} $$

which disposes off the case $b_L=1$ .

To finish this proof, we finally consider the case where $b_L=\genfrac (){0pt}{}{b-f+1}{b-a+2}_q$ . This time we get

(5.12) $$ \begin{align} \deg(B_i)+\mathrm{val}(B_i)&=b+i-2a+2+(a-f-1)(b-a+2)+\binom{r}{2}-H(L_i(c))-n(L_i(c))\nonumber\\ &=i-a+(a-f)(b-a+2)+\binom{r}{2}-H(L_i(c))-n(L_i(c)). \end{align} $$

Like before, the equality $H(L_i(c))-H(c)=i-a+1$ holds. Unlike before, we have

(5.13) $$ \begin{align} n(L_i(c))-n(c)&=\binom{b-f+1}{2}-\binom{a-f-1}{2}-\binom{b-a+1}{2}\\ &=(a-f)(b-a+2)-1. \nonumber \end{align} $$

We leave it to the reader to put the pieces together and conclude that equation (5.11) holds.

6.1 The polytopes $\mathbf {C}_\lambda (u)$

Fix $\lambda \in \mathbb {R}^{r+1}=(\lambda _1,\lambda _2,\dots ,\lambda _{r+1})$ such that $\lambda _i\geq \lambda _{i+1}$ for $i=1,\ldots ,r$ . For the next definition, we embed $\mathbb {S}_{r}$ into $\mathbb {S}_{r+1}$ as usual by treating $r+1$ as a fixed point. Recall that $s_i$ for $1\leq i\leq r$ is the simple transposition that swaps i and $i+1$ . Recall further from the introduction that given $v\in \mathbb {S}_{r+1}$ , we let .

We multiply permutations from right to left, so if $u=u_1,\ldots ,u_r,r+1$ in one-line notation, then $s_1s_2\cdots s_{r}u=u_1+1,\ldots ,u_r+1,1$ .

Example 6.2. For $r=1$ , we have $u=1$ which $I_1=[12,21]=\{12,21\}\subseteq \mathbb {S}_2$ .

For $r=2$ , we get $I_{12}=[123,231]=\{123,213,132,231\}$ and $I_{21}=[213,321]=\{213,231,312,321\}$ .

For $r=3$ and $\lambda =(3,2,1,0)$ , the six polytopes $\mathbf {C}_\lambda (u)$ for $u\in \mathbb {S}_r$ are illustrated at the bottom left of Figure 5. They are all Bruhat interval polytopes introduced by Tsukerman–Williams [Reference Tsukerman and Williams25].

Figure 5 Slicing of the three dimensional permutahedron (top), its full dissection into cubes (bottom left) and the associated cubical complex (bottom right).

This description of $\mathbf {C}_{\lambda }(u)$ , while possessing the virtue of brevity, is not entirely convenient in practice as it requires listing elements of $I_u$ . We now proceed to give another perspective on $I_u$ which is more enlightening.

Recall that the code $\mathrm {code}(w)$ of a permutation $w\in \mathbb {S}_{r+1}$ is the weak composition $(c_1,\dots ,c_{r+1})$ where $c_i=|\{j>i\;|\; w_i>w_j\}|$ . For instance, $\mathrm {code}(23514)=(1,1,2,0,0)$ . It sends $\mathbb {S}_{r+1}$ bijectively to the sequences $(c_1,\dots ,c_{r+1})$ such that $0\leq c_i\leq r+1-i$ for all i.

Proof. Denote the bottom and top element of $I_u$ , respectively, by $u_-=u_1,\dots ,u_r,r+1$ and $u_+=u_1+1,\dots ,u_r+1,1$ in one-line notation.

Given $S\subset [r]$ , let $\mathbf {e}_S\in \mathbb {R}^{r+1}$ denote the indicator vector of S, that is, $\mathbf {e}_S$ equals the sum of the standard basis vectors $e_i$ (in $\mathbb {R}^{r+1}$ ) for $i\in S$ . Define

We claim that $v\in I_u$ (i.e., $u_-\leq v\leq u_+$ in Bruhat order) if and only $\mathrm {code}(v)\in J_u$ , and that this gives a poset isomorphism (the order on weak compositions is componentwise). Note that this proves the lemma since $J_u$ is clearly order isomorphic to $\mathbb {B}_r$ .

We have $\mathrm {code}(u_+)=\mathrm {code}(u_-)+\mathbf {e}_{[r]}$ as is checked immediately. Therefore, $J_u$ consists of all weak compositions c such that $\mathrm {code}(u_-)\leq c \leq \mathrm {code}(u_+)$ .

We leave it to the reader to check that the full claim follows from invoking the following well-known tableau criterion: $u\leq v$ in Bruhat order if for any i, the weakly increasing rearrangement of $u_1\ldots u_i$ is smaller, componentwise, than the weakly increasing rearrangement of $v_1\ldots v_i$ . In view of this, the condition $u_-\leq v\leq u_+$ translates to exactly two choices for each $v_i$ as i goes from $1$ through r.

6.2 The cube decomposition

We recall the classical bijection $u\mapsto \mathrm {T}(u)$ between $\mathbb {S}_{r}$ and decreasing binary trees. $\mathrm {T}(u)$ is defined more generally for u a word with distinct letters in $\mathbb {Z}_{>0}$ . Assume $u=u_LMu_R$ , where M is the maximal integer in u. Then $\mathrm {T}(u)$ is constructed recursively as the binary tree with root label M whose left (resp. right) subtree is $\mathrm {T}(u_L)$ (resp. $\mathrm {T}(u_R)$ ). For instance, the tree in Figure 6 corresponds to the permutation $u=47128635$ .

Figure 6 Decreasing tree $\mathrm {T}(u)$ for $u=47128635$ .

Given $u\in \mathbb {S}_{r}$ and $i\in [r]$ , let and , where $f_i,g_i\geq 0$ are maximal such that $u_j<u_i$ for $j\in L(u,i)\cup R(u,i)$ . These are the labels of the descendants of the node i in $\mathrm {T}(u)$ : More precisely, $L(u,i)$ (resp. $R(u,i)$ ) is the set of labels of the left (resp. right) subtree of that node.

We now assume $\lambda _i>\lambda _{i+1}$ for $i=1,\ldots ,r$ . Although the next theorem can be adapted for cases with identical values, we do not need it since we will be interested in the volume of $\mathrm {Perm}(\lambda )$ , for which we will obtain polynomial formulas in the $\lambda _i$ that will still be valid in the general case.

Theorem 6.5. The $r!$ polytopes $\{\mathbf {C}_\lambda (u)\}_{u\in \mathbb {S}_{r}}$ are combinatorial cubes that are the maximal faces of a polyhedral subdivision of $\mathrm {Perm}(\lambda )$ .

The facet description of $\mathbf {C}_\lambda (u)$ is given by

(6.1) $$ \begin{align} \hspace{-11pt}\mathrm{(left)} \hspace{5mm} t_{u_i}+\sum_{j\in L(u,i)}t_{u_j}&\leq \lambda_{i-f_i}+\dots+\lambda_i; \end{align} $$

(6.2) $$ \begin{align} \mathrm{(right)}\hspace{5mm} t_{u_i}+\sum_{j\in R(u,i)}t_{u_j}&\geq \lambda_{i+1}+\dots+\lambda_{i+g_i+1}, \end{align} $$

for $i=1,\ldots ,r$ .

Proof. Recall that we assume $\lambda _i>\lambda _{i+1}$ for $i=1,\ldots ,r$ . We have that $\mathrm {Perm}(\lambda )$ is contained between the hyperplanes $x_1=\lambda _1$ and $x_1=\lambda _{r+1}$ .

Now, fix i satisfying $1\leq i\leq r$ , and consider the slice . The sections of $P_i$ for $\lambda _i\geq t\geq \lambda _{i+1}$ are explicitly described in Liu’s work [Reference Liu15, Proposition 3.7]:

$$\begin{align*}S_t=\{t\}\times\mathrm{Perm}(\lambda_1,\dots,\lambda_{i-1},\lambda_i+\lambda_{i+1}-t,\lambda_{i+2},\ldots,\lambda_{r+1}). \end{align*}$$

Note that $\lambda _{i-1}>\lambda _{i}+\lambda _{i+1}-t>\lambda _{i+2}$ for $\lambda _i\geq t\geq \lambda _{i+1}$ . It follows from that result that the slice $P_i$ is in particular combinatorially equivalent to the product of $[0,1]$ with a permutahedron of dimension one less. Proceeding inductively, one can decompose into cubes the two permutahedra that appear as intersections with the hyperplanes $x_1=\lambda _i$ and $x_1=\lambda _{i+1}$ . By taking the direct product with $[0,1]$ , we obtain the decomposition of $\mathrm {Perm}(\lambda )$ into cubes.

It is then easily checked inductively that these cubes are precisely the cubes $\mathbf {C}_{\lambda }(u)$ and that the facet description is as described in equations (6.1) and (6.2).

See Figure 5 for an illustration of the decomposition in the case of the three-dimensional standard permutahedron. We analyze the cube $\mathbf {C}_{\lambda }(213)$ to illustrate the preceding theorem. The table next displays all the relevant information along with the facet-defining inequalities. Each vertex of the cube is obtained by forcing exactly one of the two inequalities in any column to be an equality. Forcing all left (resp. right) inequalities to be equalities produce the vertex $\lambda _{u_-}$ (resp. $\lambda _{u_+}$ ) in the notation of Lemma 6.4.

6.3 q-volume

We now recall the notion of q-volume of the permutahedron introduced by the authors [Reference Nadeau and Tewari18, Section 9]. Given $\lambda $ , we define the q-volume of $\mathrm {Perm}(\lambda )$ as

(6.3) $$ \begin{align} V^q(\lambda)=\frac{1}{(r)_q!} \big\langle {(\lambda_1x_1+\cdots +\lambda_{r+1}x_{r+1})^{r}}\big\rangle_{r+1}^q. \end{align} $$

The remixed Eulerians arise as follows:

(6.4) $$ \begin{align} V^q(\lambda)&= \sum_{c\in \mathcal{W}_{r}^{}}A_{c}(q)\;\frac{(\lambda_1-\lambda_2)^{c_1}}{c_1!}\cdots \frac{(\lambda_{r}-\lambda_{r+1})^{c_{r}}}{c_r!}. \end{align} $$

At $q=1$ , this recovers $V^{1}(\lambda )=\mathrm {vol}(\mathrm {Perm}(\lambda ))$ [Reference Postnikov21]. From the subdivision of $\mathrm {Perm}(\lambda )$ into cubes $(\mathbf {C}_{\lambda }(u))_{u\in \mathbb {S}_r}$ it follows that

(6.5) $$ \begin{align} V^{1}(\lambda)=\mathrm{vol}(\mathrm{Perm}(\lambda))=\sum_{u\in \mathbb{S}_r} \mathrm{vol}(\mathbf{C}_{\lambda}(u)). \end{align} $$

Theorem 6.8 below is a q-deformation of this equality by weighing each summand by $q^{\ell (u)}$ . To prove it, we will need some results from [Reference Harada, Horiguchi, Masuda and Park8, Section 6].

To each $u\in \mathbb {S}_r$ , one can associate a Richardson variety

(6.6) $$ \begin{align} R(u)=X_{1\times w_o^{r}u}\cap X^{u} \end{align} $$

in the variety of complete flags of $\mathbb {C}^{r+1}$ . Its cohomology class can be represented by the product of Schubert polynomials $\mathfrak {S}_{u}\mathfrak {S}_{1\times w_o^{r}u}$ , and its volume polynomial is then given by:

(6.7) $$ \begin{align} \mathrm{Vol}_{\lambda}(R(u))=\frac{1}{(r)_q!}\;\partial_{w_o}\left(\left(\sum_i\lambda_ix_i\right)^r\mathfrak{S}_{u}\mathfrak{S}_{1\times w_o^{r}u}\right). \end{align} $$

It is shown in [Reference Harada, Horiguchi, Masuda and Park8, Remark 6.5] that $R(u)$ is a toric variety and that $\mathrm {Vol}_{\lambda }(R(u))=\mathrm {vol}(\mathbf {C}_\lambda (u))$ . We emphasize here that $w_o$ is the longest element in $\mathbb {S}_{r+1}$ while $w_o^r$ is the longest element in $\mathbb {S}_r$ .

Theorem 6.8. For any $\lambda $ , we have

(6.8) $$ \begin{align} V^q(\lambda)=\sum_{u\in \mathbb{S}_r}q^{\ell(u)} \,\mathrm{vol}(\mathbf{C}_\lambda(u)). \end{align} $$

Proof. Throughout this proof, set and . By definition of q-divided symmetrization (1.3), we have

(6.9) $$ \begin{align} V^q(\lambda)=\frac{1}{(r)_q!}\;\partial_{w_o}\left(L^rP_r\right). \end{align} $$

We now link $P_r$ to double Schubert polynomials. Letting $w_o^r$ denote the longest element in $\mathbb {S}_r$ interpreted as a permutation in $\mathbb {S}_{r+1}$ by affixing $r+1$ as a fixed point, we have the following equality for the dominant double Schubert polynomial

(6.10) $$ \begin{align} \mathfrak{S}_{w_o^{r}}(x_1,\ldots,x_{r+1};y_1,\ldots,y_{r+1})=\prod_{i+j\leq r}(x_i-y_j). \end{align} $$

This by comparison yields

(6.11) $$ \begin{align} P_r=\mathfrak{S}_{w_o^{r}}(qx_1,\ldots,qx_{r+1};x_{r+1},\ldots,x_{1}). \end{align} $$

Now, by Cauchy’s formula [Reference Manivel16, Proposition 2.4.7], for any permutation $w\in \mathbb {S}_{r+1}$ , one has

(6.12) $$ \begin{align} \mathfrak{S}_{w}(x_1,\dots,x_{r+1};y_1,\dots,y_{r+1})&=\sum_{\substack{u,v\in\mathbb{S}_{r+1}\\ v^{-1}u=w\\ \ell(v)+\ell(u)=\ell(w)}}\mathfrak{S}_{u}(x_1,\ldots,x_{r+1})\mathfrak{S}_{v}(-y_1,\ldots,-y_{r+1})\nonumber\\ &= \sum_{\substack{u,v\in\mathbb{S}_{r+1}\\ v^{-1}u=w\\ \ell(v)+\ell(u)=\ell(w)}}\mathfrak{S}_{u}(x_1,\ldots,x_{r+1})\mathfrak{S}_{w_ovw_o}(y_{r+1},\ldots,y_{1}), \end{align} $$

where the second equality is modulo the ideal $I_{r+1}$ in $\mathbb {Q}[x_1,\dots ,x_{r+1}]$ generated by symmetric polynomials with zero constant term. Indeed, $\mathfrak {S}_{v}(-y_1,\dots ,-y_{r+1})=\mathfrak {S}_{w_ovw_o}(y_{r+1},\dots ,y_1)\ \mod I_{r+1}$ .

Now, on setting $w=w_0^r$ in (6.12) and combining with equation (6.11), we get:

(6.13) $$ \begin{align} P_r=\sum_{\substack{u,v\in\mathbb{S}_{r+1}\\ v^{-1}u=w_o^r\\ \ell(v)+\ell(u)=\ell(w_o^r)}}q^{\ell(u)}\mathfrak{S}_{u}(x_1,\ldots,x_{r+1})\mathfrak{S}_{w_ovw_o}(x_1,\ldots,x_{r+1})\ \mod I_{r+1}. \end{align} $$

As explained in [Reference Nadeau and Tewari20, Section 9.5], the indexing set in equation (6.13) may be simplified to give

(6.14) $$ \begin{align} P_r=\sum_{u\in \mathbb{S}_r} q^{\ell(u)}\mathfrak{S}_{u}\mathfrak{S}_{1\times w_o^ru}\quad \mod I_{r+1}. \end{align} $$

Now, note that we may replace $P_r$ in equation (6.9) by any homogeneous polynomial of the same degree equivalent modulo $I_{r+1}$ . Substituting in equation (6.9), we get

(6.15) $$ \begin{align}V^q(\lambda)=\sum_{u\in \mathbb{S}_r}q^{\ell(u)} \frac{1}{(r)_q!}\;\partial_{w_o}\left(L^r\mathfrak{S}_{u}\mathfrak{S}_{1\times w_o^{r}u}\right)=\sum_uq^{\ell(u)}\mathrm{Vol}_\lambda(R(u)), \end{align} $$

where we used equation (6.7) in the last equality. We can then conclude since $\mathrm {Vol}_\lambda (R(u))=\mathrm {vol}(\mathbf {C}_\lambda (u))$ as recalled before the theorem.

Theorem 6.8 further justifies dubbing $V^q(\lambda )$ a q-volume. Based on this result and the expansion (1.1), we give a combinatorial interpretation of remixed Eulerian numbers in Section 7. We end this section with some remarks.

Remark 6.10. It would be nice to have a more direct proof of the previous result, avoiding the use of the Richardson variety $R(u)$ . A possibility would be to show by a direct computation that

$$\begin{align*}v_q(\mu)=\sum_{i=1}^{r}q^{i-1}\int_{0}^{\mu_i}v_q(\mu_1,\dots,\mu_{i-2},\mu_{i-1}+\mu_i-t,t+\mu_{i+1},\mu_{i+2},\dots,\mu_r) \,\mathrm{d}t, \end{align*}$$

where $v_q(\mu )$ is the expression of $V^q(\lambda )$ in terms of $\mu _i=\lambda _{i}-\lambda _{i+1}$ .Footnote ³ Indeed, this recurrence relation is satisfied by the right-hand side in Theorem 6.8 by slicing the permutahedron as in the proof of Theorem 6.5. This is in fact the q-deformation of [Reference Liu15, Proposition 3.9]; we come back to this in Section 7.2.

Remark 6.12. In view of the preceding remark, we may compactify the $V^q(\lambda )$ as a sum over $\mathcal {T}_{r}$ :

(6.16) $$ \begin{align} V^q(\lambda)=\sum_{u\in \mathbb{S}_{r}} q^{\ell(u)}\mathrm{vol}(\mathbf{C}_{\lambda}(u))=\sum_{T\in \mathcal{T}_{r}} \mathrm{vol}(\mathbf{C}_{\lambda}(T))\sum_{u\in \mathcal{S}_T}q^{\ell(u)}. \end{align} $$

Appealing to the q-hook length formula for binary trees we get

(6.17) $$ \begin{align} V^q(\lambda)=\sum_{T\in \mathcal{T}_{r}} \mathrm{vol}(\mathbf{C}_{\lambda}(T))\times q^{\mathrm{stat}(T)}\frac{(r)_q!}{\prod_{v\in T}(h_v)_q!}, \end{align} $$

where $\mathrm {stat}(T)$ is the sum over all internal nodes of the number of right edges in the unique path from root to node, though this precise description is not relevant for the discussion at hand. Given the expression for q-volume in equation (6.17) as a sum over binary trees involving the hook length formula, it is natural to compare it with [Reference Postnikov21, Theorem 17.1] that expresses the ordinary volume of the permutahedron as a sum over binary trees as well. When we set $q=1$ and specialize to the case of the standard permutahedron, it can be checked that $\mathrm {vol}(\mathbf {C}_{\lambda }(T))$ does not become the product on the right-hand expression in loc. cit.. In particular, our expansion does not yield Postnikov’s hook length formula [Reference Postnikov21, Corollary 17.3] despite the similarity.

7.1 Gelfand–Tsetlin polytope, face diagrams and shifted tableaux

The Gelfand–Tsetlin polytope $\mathrm {GT}(\lambda ) \subset \mathbb {R}^{\binom {n}{2}}$ contains all points $(x_{ij})_{1\leq i\leq j\leq n}$ , where

(7.1) $$ \begin{align} x_{i,j-1}\geq x_{i,j} \geq x_{i+1,j} \end{align} $$

holds for all $1\leq i<j\leq n$ . Here, we assume that $x_{ii}=\lambda _i$ for all $i\in [n]$ . Points in $\mathrm {GT}(\lambda )$ can be interpreted as fillings of a triangular array as shown in Figure 7 subject to conditions in equation (7.1).

Figure 7 Gelfand–Tsetlin pattern.

The authors of [Reference Harada, Horiguchi, Masuda and Park8] take inspiration from work of Kogan [Reference Kogan13], Kiritchenko [Reference Kiritchenko11], Kiritchenko–Smirnov–Timorin [Reference Kirichenko, Smirnov and Timorin10], and use a combinatorial gadget called face diagrams to emphasize equalities defining faces of $\mathrm {GT}(\lambda )$ .

Consider a graph on a set of $\binom {n+1}{2}$ vertices, each placed at the centre of the boxes in Figure 7. We address the vertex in row i from the top and column j from the left by $(i,j)$ . Faces of $\mathrm {GT}(\lambda )$ of interest to us are determined by declaring at most one inequality among $x_{i,j} \leq x_{i,j+1}\leq x_{i+1,j+1}$ to be an equality. Pictorially, we emphasize this equality by drawing an edge between the appropriate vertices. The resulting graphs are called face diagrams.

The face diagrams we are interested in are indexed by permutations. Pick $u\in \mathbb {S}_{r}$ , and let $(d_1,\dots ,d_r)$ be such that $\mathrm {code}(u^{-1})=(d_1-1,\dots ,d_{r}-1)$ . Consider the face $\mathsf {F}(u)$ of $\mathrm {GT}(\lambda )$ (and face diagram $\mathrm {FD}(u)$ ) defined by the equalities

(7.2) $$ \begin{align} x_{i,i+j}=x_{i,i+j-1}\ \mathrm{for}\ 1\leq i<d_j; x_{i,i+j}=x_{i+1,i+j}\ \mathrm{for}\ d_j<i\leq r+1-j. \end{align} $$

Then $\mathsf {F}(u)$ is r dimensional. We now observe that the association $\mathrm {FD}(u)\leftrightarrow u$ is essentially the folklore bijection between decreasing binary trees and permutations described in Section 6.2.

Indeed, note the following aspect of $\mathrm {FD}(u)$ . For a fixed $j\in [r]$ , there exists a unique $i\in [r+1-j]$ such that the vertex $(i,i+j)$ is neither connected to the vertex immediately below nor connected to the vertex immediately to the left. Indeed this vertex is given by $(d_j,d_j+j)$ . We enrich $\mathrm {FD}(u)$ by introducing edges joining $(d_j,d_j+j)$ to $(d_j+1,d_j+j)$ and $(d_j,d_j+j-1)$ for each $j\in [r]$ . Additionally, we label the vertices $(d_j,d_j+j)$ by j. The resulting graph is connected and has $\binom {n+1}{2}-1$ edges and hence must be a tree (in a planar representation). One can treat it as a rooted binary tree with root given by the vertex $(1,n)$ . See Figure 8 (middle) for the enriched face diagram for $u=2647351 \in \mathbb {S}_7$ .

Figure 8 $\mathrm {FD}(u)$ for $u=2647351 \in \mathbb {S}_7$ (left) and the corresponding $(T,\mathrm {dec})$ (right).

Shrinking all paths present in the original $\mathrm {FD}(u)$ to length $0$ , we get a complete binary tree with r labeled internal nodes and $r+1$ unlabeled leaves. Ignoring leaves, one obtains the decreasing tree $(T,\mathrm {dec})$ attached to u.Footnote ⁴ Here, T records the unlabeled underlying tree and $\mathrm {dec}$ the decreasing labeling. See the decreasing tree on the right in Figure 8.

To give a combinatorial interpretation to $A_c(q)$ , we endow a decreasing tree (completed with unlabeled leaves) with an additional labeling $\mathrm {lr}$ of the nodes and leaves with distinct positive integers drawn from $\{1,\dots ,2r+1\}$ such that the label of any node is larger (resp. smaller) than that of its left (resp. right) child. Furthermore, the labels on the leaves increase when read from left to right. We call the triple $(T,\mathrm {dec},\mathrm {lr})$ a bilabeled tree. If the sequence of labels read off the leaves is $(1=\ell _1<\cdots < \ell _{r+1}=2r+1)$ , we define the content of the bilabeled tree by setting $c_i=\ell _{i+1}-\ell _i-1$ for $i\in [r]$ .

Theorem 7.1. For $c\in \mathcal {W}_{r}^{}$ , let $B(c)$ be the set of bilabeled trees with content c. We have

$$\begin{align*}A_c(q)=\sum_{(T,\mathrm{dec},\mathrm{lr})\in B(c)}q^{\ell(u)}, \end{align*}$$

where $u\in \mathbb {S}_r$ is the permutation determined by $(T,\mathrm {dec})$ .

Proof. It is shown in [Reference Harada, Horiguchi, Masuda and Park8] that, under a simple transformation, the faces $\mathsf {F}(u)$ of $\mathrm {GT}(\lambda )$ are the $\mathbf {C}_{\lambda }(u)$ ; see [Reference Harada, Horiguchi, Masuda and Park8, Theorem 5.4] and results in Section 6 in loc. cit. Therefore, $\mathrm {vol}(\mathsf {F}(u))=\mathrm {vol}(\mathbf {C}_{\lambda }(u))$ . The former quantity can be described in terms of shifted tableaux, which we then recast.

A shifted Young tableau P associated with $\mathsf {F}(u)$ is a filling of the cells in Figure 7 with entries from $\{1,\dots ,2r+1\}$ so that they increase weakly from left to right and top to bottom, and neighboring entries are equal if and only if the corresponding vertices are connected by an edge in $\mathrm {FD}(u )$ . The diagonal vector of P is the sequence of entries in the cells $(i,i)$ as i ranges from $1$ through $r+1$ .

By [Reference Harada, Horiguchi, Masuda and Park8, Proposition 3.1]

(7.3) $$ \begin{align} \mathrm{vol}(\mathsf{F}(u))=\sum_{c\in \mathcal{W}_{r}^{}}\sum_{P\in \mathrm{ShT}(u,c)} \frac{(\lambda_1-\lambda_2)^{c_1}}{c_1!}\cdots\frac{(\lambda_r-\lambda_{r+1})^{c_r}}{c_r!}, \end{align} $$

where $\mathrm {ShT}(u,c)$ is the set of shifted tableaux associated to $\mathsf {F}(u)$ with prescribed diagonal vector $(1,c_1+2,c_1+c_2+3,\dots ,c_1+\dots +c_r+r+1)$ . Theorem 6.8 then becomes

(7.4) $$ \begin{align} V^q(\lambda)=\sum_{u\in \mathbb{S}_r}q^{\ell(u)} \sum_{c\in \mathcal{W}_{r}^{}}\sum_{P\in \mathrm{ShT}(u,c)} \frac{(\lambda_1-\lambda_2)^{c_1}}{c_1!}\cdots\frac{(\lambda_r-\lambda_{r+1})^{c_r}}{c_r!}. \end{align} $$

Comparing with equation (6.4) yields the following interpretation:

(7.5) $$ \begin{align} A_c(q)=\sum_{u\in \mathbb{S}_r}\sum_{P\in\mathrm{ShT}(u,c)} q^{\ell(u)}. \end{align} $$

Mimicking how we went from $\mathrm {FD}(u)$ to $(T,\mathrm {dec})$ , we can translate shifted tableaux to bilabeled trees— the inequalities defining the former translate into the ‘local binary search’ condition on the labeling $\mathrm {lr}$ while the diagonal vector gives the leaf labeling.

Example 7.2. Consider $c=(2,0,1)\in \mathcal {W}_{3}^{} $ . Figure 9 shows all bilabeled trees with content c. The blue labels on the outside record the $\mathrm {lr}$ labeling whereas the interior labels record the decreasing labeling. We get

$$ \begin{align*} A_{201}(q)=q^{\ell(123)}+q^{\ell(132)}+q^{\ell(231)}=1+q+q^2. \end{align*} $$

Figure 9 All bilabeled trees with content $(2,0,1)$ .

7.2 Connection with Liu’s work

We now demonstrate how the bilabeled tree construction is related to work of Liu [Reference Liu15].

Given a bilabeled tree $(T,\mathrm {dec},\mathrm {lr})$ with content c, consider the node $v_1$ labeled $1$ in the decreasing labeling; its children are leaves, say with labels $\ell _i<\ell _{i+1}$ in the labeling $\mathrm {lr}$ . Then we must have $c_i=\ell _{i+1}-\ell _i-1$ . Let j be the $\mathrm {lr}$ -label of $v_1$ . The local binary search condition tells us that $\ell _i<j<\ell _{i+1}$ .

If $i=1$ , then necessarily $j=2$ since $v_1$ is the only possible node with this label; similarly, if $i=r$ , then $j=2r$ . We obtain a bilabeled tree $(T',\mathrm {dec}',\mathrm {lr}')$ as follows:

• • $T'$ is obtained by replacing the node $v_1$ , and its two attached leaves by a single new leaf $leaf$ .

• • $\mathrm {dec}'$ is obtained by decreasing $\mathrm {dec}$ by one on the remaining nodes in $T'$ .

• • $\mathrm {lr}'$ is obtained by labeling the new leaf $leaf$ by j, and then relabeling via the unique increasing bijection $\{1,\dots ,2r+1\}\setminus \{\ell _i,\ell _{i+1}\}\to \{1,\dots ,2r-1\}$ .

Figure 10 shows an example of this procedure.

Figure 10 An example of $(T,\mathrm {dec},\mathrm {lr})\to (T',\mathrm {dec}',\mathrm {lr}') $ .

Note that the content of $(T',\mathrm {dec}',\mathrm {lr}')$ is $(c_1,\dots ,c_{i-2},c_{i-1}+(j-l_{i}-1),c_{i+1}+(l_{i+1}-j-1),c_{i+2},\dots ,c_r)$ . Also, all bilabeled trees with this content are obtained in the manner described above. We thus get

(7.6) $$ \begin{align} A_c=A_{(c_1+c_2-1,c_3,\dots,c_r)}+A_{(c_1,\dots,c_{r-2},c_{r-1}+c_r-1)} +\sum_{i=2}^{r-1}\sum_{t=0}^{c_i-1}A_{(c_1,\dots,c_{i-2},c_{i-1}+t,c_{i+1}+c_i-1-t,c_{i+2}\dots,c_r)}, \end{align} $$

where $A_c=A_c(1)$ now. This is precisely Liu’s recurrence [Reference Liu15, p. 8] (where $A_c=A_c(1)$ ). Using the same approach, one can in fact obtain a bijection between bilabeled trees with content c and Liu’s C-permutations.