# A q-deformation of an algebra of Klyachko and Macdonald's reduced word formula

Philippe Nadeau, Vasu Tewari

► To cite this version:

Philippe Nadeau, Vasu Tewari. A q-deformation of an algebra of Klyachko and Macdonald's reduced word formula. Transactions of the American Mathematical Society, 2025, 378, pp.8821-8870. 10.1090/tran/9481. hal-03373386

HAL Id: hal-03373386

https://hal.science/hal-03373386v1

Submitted on 24 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A $q$-DEFORMATION OF AN ALGEBRA OF KLYACHKO, AND MACDONALD'S REDUCED WORD FORMULA

PHILIPPE NADEAU AND VASU TEWARI

**ABSTRACT.** There is a striking similarity between Macdonald's reduced word formula and the image of the Schubert class in the cohomology ring of the permutahedral variety $\text{Perm}_n$ as computed by Klyachko. Toward understanding this better, we undertake an in-depth study of a $q$-deformation of the $S_n$-invariant part of the rational cohomology ring of $\text{Perm}_n$, which we call the $q$-Klyachko algebra. We uncover intimate links between expansions in the basis of squarefree monomials in this algebra and various notions in algebraic combinatorics, thereby connecting seemingly unrelated results by finding a common ground to study them. Our main results are as follows.

* A $q$-analog of divided symmetrization ($q$-DS) using Yang-Baxter elements in the Hecke algebra. It is a linear form that picks up coefficients in the squarefree basis.

* A relation between $q$-DS and the ideal of quasisymmetric polynomials involving work of Aval-Bergeron-Bergeron.

* A family of polynomials in $q$ with nonnegative integral coefficients that specialize to Postnikov's mixed Eulerian numbers when $q = 1$. We refer to these new polynomials as remixed Eulerian numbers. For $q > 0$, their normalized versions occur as probabilities in the internal diffusion limited aggregation (IDLA) stochastic process.

* A lift of Macdonald's reduced word identity in the $q$-Klyachko algebra.

* The Schubert expansion of the Chow class of the standard split Deligne-Lusztig variety in type A, when $q$ is a prime power.

## CONTENTS

<table><tr><td>1. Introduction</td><td>2</td></tr><tr><td>2. Notation</td><td>7</td></tr><tr><td>3. The Klyachko algebra K</td><td>9</td></tr><tr><td>4. q-divided symmetrization</td><td>13</td></tr><tr><td>5. Remixed Eulerian numbers</td><td>20</td></tr><tr><td>6. Specializations of quasisymmetric polynomials</td><td>25</td></tr><tr><td>7. Klyachko-Macdonald identity and Chow class of a Deligne-Lusztig variety</td><td>29</td></tr><tr><td>8. The interval property</td><td>36</td></tr><tr><td>9. A q-analogue of the volume polynomial</td><td>41</td></tr><tr><td>Appendix A. Proof of Proposition 4.3</td><td>42</td></tr><tr><td>Appendix B. Proof of Theorem 4.15</td><td>44</td></tr><tr><td>Appendix C. Proof of Theorem 7.2</td><td>45</td></tr><tr><td>References</td><td>46</td></tr></table>
# 1. INTRODUCTION

The permutahedral variety in type A has garnered a lot of attention recently, especially since the study of its cohomology ring plays a key role in the dramatic recent resolutions of various questions concerning log-concavity of various polynomials arising in combinatorics; see for instance [5, 22].

Let $\mathrm{Flag}(n)$ denote the (type A) complete flag variety. Denote by $\mathrm{Perm}_n \subset \mathrm{Flag}(n)$ the closure of a torus orbit of a general point in $\mathrm{Flag}(n)$. Equivalently, $\mathrm{Perm}_n$ can be described as the smooth projective toric variety described by the braid fan. It is the *permutahedral variety of type A*. The inclusion $\mathrm{Perm}_n \subset \mathrm{Flag}(n)$ induces a pullback $i^* : \mathrm{H}^*(\mathrm{Flag}(n), \mathbb{Q}) \to \mathrm{H}^*(\mathrm{Perm}_n, \mathbb{Q})$ between cohomology rings. In fact the image of $i^*$ coincides with the algebra of invariants $\mathrm{H}^*(\mathrm{Perm}_n, \mathbb{Q})^{\mathbb{S}_n}$.

It is this $\mathbb{S}_n$-invariant subring of the cohomology ring, which is also isomorphic to the cohomology ring of the Peterson variety [1], that was first studied by Klyachko [24]. In particular he obtained a presentation for this ring of invariants, and this presentation has subsequently been rederived in [16, 21]. This ring of invariants has dimension $2^r$ where $r = n - 1$ as shown by Klyachko [24] and later by Stembridge [43, §3]. The dimension hints at the existence of a nice combinatorial linear basis for this space, and indeed, Klyachko constructs a basis indexed by subsets of $\{1, \dots, r\}$. We note that Klyachko's results work in all Lie types and we have emphasized the type A picture here.

Recall that the cohomology ring $\mathrm{H}^*(\mathrm{Flag}(n), \mathbb{Q})$ has a basis given by Schubert classes $\sigma_w$ as $w$ ranges over elements in $\mathbb{S}_n$, which brings us to our point of departure. It is natural to inquire about the image of $\sigma_w$ under $i^*$. Klyachko expresses $i^*(\sigma_w)$ as a sum of monomials indexed by reduced words of $w$; see [34, §8] where we reproduce his proof<fnref n="1" /> with mild modifications. Particularly remarkable is the fact that Klyachko's expression bears an unmistakable resemblance to Macdonald's reduced word formula [30], which we now recall. Let $\mathrm{Red}(w)$ denote the set of reduced words for a permutation $w \in \mathbb{S}_n$. Macdonald [30] established that for $w$ with length $\ell$ we have

$$ (1.1) \qquad \mathfrak{S}_w(1, \dots, 1) = \frac{1}{\ell!} \sum_{a_1 \dots a_\ell \in \mathrm{Red}(w)} a_1 \cdots a_\ell, $$

where $\mathfrak{S}_w$ denotes the Schubert polynomial indexed by $w$. These polynomials are certain distinguished representatives of Schubert classes and were introduced by Lascoux and Schützenberger. Note that the left-hand side counts the number of reduced pipe dreams for $w$. We note here that Macdonald's reduced word identity has already been given several proofs [6, 17, 20], each shedding new light. More importantly for us, a $q$-analogue (conjectured by Macdonald) was first proved by Fomin and Stanley [15] by working in the NilCoxeter algebra; see also [31].

To make matters more intriguing, we note that Klyachko did not have access to the combinatorial formula for Schubert polynomials established by Billey–Jockusch–Stanley [7] and Fomin–Stanley [15] as it came later. Furthermore, from the perspective of Klyachko's work, there is a priori nothing that suggests that a particular representative of a Schubert class may be more important than others, whereas Macdonald's identity clearly deals with a specific representative.

This article stems from our desire to explain this resemblance between Klyachko's result and Macdonald's reduced word identity, as this appears to have been overlooked in literature as far as we can tell. With the benefit of hindsight, we see that Klyachko's result foreshadows Macdonald's result. In fact, given that Macdonald's result permits a $q$-analogue, we are able to generalize Klyachko's result by working a parameter $q$ into the setup.

<footnote n="1">¹The original is in Russian.</footnote>
Let $\mathbf{k}$ be a field of characteristic zero, and $q \in \mathbf{k}$ not equal to a nontrivial root of unity. We introduce an algebra $\mathcal{K}$, called the *Klyachko algebra* henceforth, by considering a natural $q$-deformation of Klyachko's presentation [24]. More precisely $\mathcal{K}$ is the commutative algebra over $\mathbf{k}$ on the generators $\{u_i | i \in \mathbb{Z}\}$ subject to the following relations for $i \in \mathbb{Z}$:

$$ (1.2) \qquad (q+1)u_i^2 = qu_i u_{i-1} + u_i u_{i+1}. $$

The algebra that results on setting $u_i = 0$ for $i \ge n$ and $i < 0$, will be called $\mathcal{K}_n$. In this case, when we additionally set $q = 1$, the relations in (1.2) descend to Klyachko's presentation of $H^*(\mathrm{Perm}_n, \mathbb{Q})^{\mathbb{S}_n}$ [24]. We will be particularly interested in the 'positive half' $\mathcal{K}_+$ of $\mathcal{K}$ obtained by setting $u_i = 0$ for all $i \le 0$.

**1.1. Discussion of main results.** The first half of the article focuses on the interplay between an algebraic operation that we call $q$-divided symmetrization, and the coefficients when considering expansions in the distinguished basis $\{u_i\}$ of $\mathcal{K}$ comprising squarefree monomials indexed by finite subsets $I$ of $\mathbb{Z}$. The algebras $\mathcal{K}_+$ and $\mathcal{K}_-$ inherit bases of squarefree monomials by omitting terms involving $u_i$ where $i \notin \mathbb{Z}_+$ or $i \notin \{1, \dots, n-1\}$ respectively. The $q$-divided symmetrization operator is a linear operator that takes a polynomial $f \in \mathbf{k}[x_1, \dots, x_n]$ of degree $n-1$ as input and outputs $\langle f \rangle_n^q \in \mathbf{k}$; see §4 for the precise definition. When $q = 1$, $q$-divided symmetrization specializes to Postnikov's divided symmetrization [38, §3], and our lift naturally involves substituting Hecke operators $T_i$ acting on rational functions in $x_1, \dots, x_n$ as opposed to ordinary transpositions $s_i$ in Postnikov's symmetrization.

Fix $r \ge 1$. Our first main result is the following:

**Theorem 1.1.** Let $f$ be a polynomial in $\mathbf{k}[x_{r+1}]$ with $\deg(f) = r$. Consider the expansion of $f(u_1, u_2 - u_1, \dots, u_r - u_{r-1}, -u_r)$ in the squarefree basis of $\mathcal{K}_{r+1}$, and let $\mathrm{Top}_{r+1}(f)$ be the top coefficient in this expansion, namely that of $u_1 \cdots u_r$. Then

$$ \langle f \rangle_{r+1}^q = (r)_q! \times \mathrm{Top}_{r+1}(f). $$

We are in fact able to extend Theorem 1.1 to a statement involving coefficients of arbitrary square-free monomials occuring in expansions in the full Klyachko algebra $\mathcal{K}$; see Theorem 4.15. We proceed to describe our results borne out of this interplay between the Klyachko algebra and $q$-divided symmetrization, with a particular focus on combinatorially pertinent families of polynomials.

Our second main result concerns a family of polynomials that we call remixed Eulerian numbers. While our original definition describes them as $q$-divided symmetrizations of certain special polynomials, the link to the Klyachko algebra in Theorem 1.1 permits an alternative characterization that we present next. To state it we need some notation. For a fixed positive integer $r$, let $W_r^q$ be the set of sequences of nonnegative integers $(c_1, \dots, c_r)$ whose parts sum to $r$. We let $(r)_q!$ denote the usual $q$-factorial of $r$.

**Theorem 1.2.** There exists a unique family of polynomials $\{A_c(q)\}_{c \in W_r^q}$ with $A_{(1^r)}(q) = (r)_q!$ that satisfies the following relations: for any $i = 1, \dots, r$ such that $c_i \ge 2$,

$$ (q+1)A_{(c_1, \dots, c_r)}(q) = qA_{(c_1, \dots, c_{i-1}+1, c_{i-1}, \dots, c_r)}(q) + A_{(c_1, \dots, c_{i-1}, c_{i+1}+1, \dots, c_r)}(q). $$

If $i = 1$ (resp. $i = r$), then the first (resp. second) term on the right hand side is to be omitted.

It follows easily from [34, 37] that $A_c(1) = A_c$ where the latter are the mixed Eulerian numbers introduced by Postnikov [38]. Furthermore, for $c \in W_r^q$, the following properties hold:
(1) $A_c(q) \in \mathbb{N}[q]$.

(2) $A_c(q)$ is the probability to end in the configuration $(1^r)$ starting from the configuration $c$ in the process described in §5.

(3) Given $c \in W_r^r$, define $\tilde{c} := (c, 0)$. Let $\text{Cyc}(c)$ be the set of all $c'$ such that $(c', 0)$ is a cyclic rotation of $\tilde{c}$. We have the following cyclic sum rule:

$$ \sum_{c' \in \text{Cyc}(c)} A_{c'}(q) = (r)_q!. $$

We further study these polynomials in a separate article [35], and proceed to make several remarks. It is worth noting that the nonnegativity of the coefficients of $A_c(q)$ does not immediately follow from the unique characterization above. One needs to derive a better recursion, which in turn implies a nontrivial divisibility property; see §§5.2. If one considers $A_c(q)$ where the $c$ are drawn from $\text{Cyc}((r, 0^{r-1}))$, then one obtains a familiar family of polynomials: they are the MacMahon–Carlitz $q$-Eulerians, i.e. the $q$ tracks the major index of permutations on $r$ letters with a fixed number of descents. Note furthermore that there are $\text{Cat}_r := \frac{1}{r+1} \binom{2r}{r}$ cyclic classes determined by compositions in $W_r^r$, and we get a Mahonian distribution for each class.

Let $\text{QSym}$ denote the ring of quasisymmetric functions in $x_1, x_2, \dots$. We may truncate quasisymmetric functions to obtain quasisymmetric polynomials by declaring $x_i = 0$ for $i > m$ for some choice of positive integer $m$. We denote by $\text{QSym}_m^+$ the ideal in $\mathbb{Q}[x_1, \dots, x_m]$ generated by positive degree quasisymmetric polynomials. Of particular interest to is the quotient $\mathbb{Q}[x_1, \dots, x_m]/\text{QSym}_m^+$, studied in the work of Aval–Bergeron–Bergeron [4]. These authors established that this quotient has dimension $\text{Cat}_m$ and possesses a monomial basis (henceforth the ABB basis) naturally indexed by lattice paths subject to certain constraints. Since we care particularly about degree $m-1$ polynomials in the context of $q$-divided symmetrization, we note here that in the top degree of $\mathbb{Q}[x_1, \dots, x_m]/\text{QSym}_m^+$, the ABB monomial basis is identified with Dyck paths from $(0,0)$ to $(m-1, m-1)$, as the exponent vectors of these monomials give ‘prototypical’ Catalan objects.

Principal specializations of truncations of quasisymmetric functions are important in combinatorics especially in the context of the study of P-partitions. Our third main result demonstrates that $q$-divided symmetrization, computations in $\mathcal{K}$, and the ABB basis fit nicely in this context.

**Theorem 1.3.** Let $f$ be a quasisymmetric function of degree $r > 0$.

(1) We have

$$ (1.3) \qquad \sum_{j \ge 1} f(1, q, \dots, q^{j-1}) t^j = \frac{\sum_m \langle f(x_1, \dots, x_m) \rangle_{r+1}^q t^m}{(t; q)_{r+1}}. $$

(2) The expression $f(u_1, u_2 - u_1, \dots, u_r - u_{r-1}, -u_r)$ vanishes in $\mathcal{K}_{r+1}$.

(3) $\langle \cdot \rangle_{r+1}^q$ vanishes on the space of degree $r$ polynomials in $\text{QSym}_{r+1}^+$.

If $f = g + h$ where $h \in \text{QSym}_{r+1}^+$ and $g$ is expressed in the basis of ABB monomials, then

$$ \langle f \rangle_{r+1}^q = g(1, q, q^2, \dots, q^r). $$

In particular for $\mathbf{x}^c$ an ABB monomial of degree $r$ we have

$$ \langle \mathbf{x}^c \rangle_{r+1}^q = q^{\text{coarea}(\text{Dyck}(c))}. $$
Here Dyck(c) is the Dyck path corresponding to c, and coarea refers to the well-known complementary area statistic.

Let $\mathrm{Sym}_n^+$ denote the ideal in $\mathbb{Q}[x_1, \dots, x_n]$ generated by positive degree symmetric polynomials in $x_1, \dots, x_n$. The quotient $\mathbb{Q}[x_1, \dots, x_n]/\mathrm{Sym}_n^+$ is the well-known coinvariant algebra, which is known to be isomorphic to $H^*(\mathrm{Flag}(n), \mathbb{Q})$ by Borel's isomorphism under which the Schubert classes can be regarded as Schubert polynomials. Clearly $\mathrm{Sym}_n^+ \subset \mathrm{QSym}_n^+$. By Theorem 1.3 we have that $\langle \cdot \rangle_n^q$ vanishes on degree $n-1$ polynomials in $\mathrm{Sym}_n^+$.

It is thus natural to inquire if anything substantial can be said about the $q$-divided symmetrization of Schubert polynomials of the appropriate degree. It turns out that the $\langle \mathfrak{S}_w \rangle_n^q$ for $w \in S_n$ of length $n-1$ possess a geometric meaning in the setting of Deligne-Lusztig varieties, thanks to the work of D. Kim [23]. Given the link between $q$-divided symmetrization and $K$ in Theorem 1.1, we are thus led to consider expansions for Schubert polynomials in $K$. Fortuitously, our initial motivation to unify Klyachko's identity and Macdonald's identity aligns with this new endeavour.

This brings us to our fourth main result. We will need some notions attached to reduced words. Suppose $w \in S_n$ has length $\ell$. Let $\mathbf{a} = a_1 \cdots a_\ell \in \mathrm{Red}(w)$. We define $\mathrm{comaj}(\mathbf{a})$ to be the sum of all $i \in \{1, \dots, \ell-1\}$ such that $a_i < a_{i+1}$.

**Theorem 1.4.** (q-Klyachko-Macdonald identity) Let $w \in S_n$ of length $\ell$. The following equality holds in $K_+$.

$$ \mathfrak{S}_w(u_1, u_2 - u_1, \dots) = \frac{1}{(\ell)_q!} \sum_{\mathbf{a} \in \mathrm{Red}(w)} q^{\mathrm{comaj}(\mathbf{a})} u_{a_1} u_{a_2} \cdots u_{a_\ell}. $$

Theorem 1.4 is a generalization of Klyachko's result for $q=1$ in the quotient $K_n$. The reader is invited to compare our proof in §7 with Klyachko's proof presented in [34, §8]. It should become apparent that the latter proof does not modify so as to incorporate the $q$. Instead we adapt the argument in [15] to $K_+ \otimes NC_n$ and employ a 'Yang-Baxter' relation that works particularly well with the relations in $K_+$. Here $NC_n$ refers to the (type A) NilCoxeter algebra.

We define the content of $\mathbf{a}$, denoted by $\mathrm{cont}(\mathbf{a})$, to be the sequence of nonnegative integers whose $i$th entry counts the number of $i$s in $\mathbf{a}$ for all $i \ge 1$. The following two equalities are immediate consequences of Theorem 1.4.

$$ \begin{aligned} \mathfrak{S}_w(1, q, q^2, \dots) &= \frac{1}{(\ell)_q!} \sum_{\mathbf{a} \in \mathrm{Red}(w)} q^{\mathrm{comaj}(\mathbf{a})} (a_1)_q (a_2)_q \cdots (a_\ell)_q, \\ \langle \mathfrak{S}_w \rangle_{\ell+1}^q &= \frac{1}{(\ell)_q!} \sum_{\mathbf{a} \in \mathrm{Red}(w)} q^{\mathrm{comaj}(\mathbf{a})} A_{\mathrm{cont}(\mathbf{a})}(q). \end{aligned} $$

The first one is the $q$-Macdonald reduced word identity [15] and is obtained by specialization, while the second formula is a consequence of Theorem 1.1.

We turn our attention to $a_w(q) := \langle \mathfrak{S}_w \rangle_{\ell+1}^q$ in this latter formula, from which it is not obvious that $a_w(q) \in \mathbb{N}[q]$. That this is indeed true follows from work of Kim [23], which has the feature that whilst it implies the nonnegativity and integrality of the coefficients of $a_w(q)$, the resulting explicit expression unfortunately involves generalized Littlewood-Richardson coefficients. These are in general hard to compute, and finding a combinatorial rule to describe them is a wide open problem. We approach understanding $a_w(q)$ from our explicit formula above and uncover some
curious properties of these polynomials, extending previous work of the authors [34] in the case $q = 1$. We briefly describe some developments next, referring the reader to §§7.2, §§7.3, and §§7.4

We obtain a *cyclic sum rule* which generalizes [34, Theorem 1.5] nicely. Informally our rule says that $S'_n$ can be decomposed into $Cat_{n-1}$ cyclic classes, in such a way that the sum of the $a_w(q)$ as $w$ ranges over a fixed class tracks the distribution of comaj over the set of reduced words for any choice of representative from that class.

This summary rule suggests that an approach to describing the $a_w(q)$ combinatorially might involve decomposing the set of reduced words of $w$ in some hitherto undetermined manner. Nevertheless, in §§7.4, we are able to deal with special cases, namely, $w$ being a Łukasiewicz permutation or a Grassmannian permutation.

Additionally, for the class of permutations we call quasiindecomposable permutations, we show that the corresponding $a_w(q)$ 'encode' the generating function tracking principal specializations of certain Schubert polynomials. Specifically, for $v$ an indecomposable permutation in $S_{p+1}$ of length $\ell$, we show in Theorem 7.9 that

$$ (1.4) \qquad \sum_{j \ge 0} t^j \mathfrak{S}_{1j \times v}(1, q, q^2, \dots) = \frac{\sum_{m=0}^{\ell-p} a_{1^{m} \times v \times 1^{\ell-p-m}}(q) t^m}{(t; q)_{\ell+1}}. $$

See §§7.3 for details on undefined notation. A remark of independent interest is that we do not know an alternative proof for the fact that the rational function expressing the left-hand side of (1.4) has a numerator which is a polynomial in $N[q, t]$.

This brings us to our final stop. The reader may have observed that two of our highlighted results — equation 1.3 and equation (1.4)— are equalities that involve the specialization $x_i \mapsto q^{i-1}$ on one side and $q$-divided symmetrization of either Schubert polynomials or quasisymmetric polynomials on the other side. *What do these two families have in common?* Motivated by this we introduce a property of polynomials that we refer to as the interval property. In fact this property is shared by numerous expansions in this work. Broadly speaking, we say that a polynomial possesses the said property if its image in $K$ (or $K_+$) expands in the squarefree basis of $K$ in terms of monomials $u_I$ where $I$ is a finite interval in $\mathbb{Z}$. As we demonstrate in §8, this has interesting consequences for principal specializations of the sort considered here.

**Outline of the article:** We briefly introduce relevant notation in §2. The core of this work consists of §3 and §4. Our central object — the Klyachko algebra $K$ — is introduced in §3. We show that squarefree monomials form a basis of $K$, as well as the important quotients $K_+$ and $K_n$, and introduce the principal specialization sp. The operation of $q$-divided symmetrization (qDS) is introduced in §4. After some preliminary results, we introduce remixed Eulerian numbers $A_c^q$ in §§4.3, and Theorem 1.1 is established in §§4.4.

The next three sections give different illustrations of these concepts. In §5 we shed further light on the remixed Eulerian numbers by giving a probabilistic interpretation for $q > 0$ as well as establishing the non-negativity of their coefficients as polynomials in $q$. §6 contains the interplay with quasisymmetric functions and the proof of Theorem 1.3. Our motivating result Theorem 1.4 is established at the beginning of §7. We then explain the geometric significance of the $a_w(q)$ when $q$ is a prime power, and proceed to establish several of their properties.
§8 introduces the so-called interval property, which is a satisfying unifying explanation to several identities of this work. Finally §9 ties several qDS evaluations from this work, by introducing a q-deformation of the volume polynomial of the permutahedron.

## 2. NOTATION

For any undefined terminology relating to various combinatorial objects arising in this work, we refer the reader to [30, 42].

We denote the set of nonnegative integers by $\mathbb{N}$, and the set of positive integers by $\mathbb{Z}_+$. Given integers $a \le b$, on occasion we denote the interval $\{a, a+1, \dots, b\}$ by $[a, b]$. If $a = 1$, instead of writing $[1, b]$ we occasionally write $[b]$. We interpret $[1, b] + k$ to mean the interval $[1 + k, b + k]$.

We will need $q$-integers. For $n \in \mathbb{N}$ and $0 \le k \le n$, set

$$ (2.1) \qquad (n)_q := \frac{q^n - 1}{q-1} = 1 + q + \cdots + q^{n-1}; \quad (n)_q! := \prod_{1 \le i \le n} (i)_q; \quad \binom{n}{k}_q := \frac{(n)_q!}{(k)_q!(n-k)_q!}. $$

These are respectively called the $q$-integers, $q$-factorials and $q$-binomial coefficients. These are all polynomials in $q$ with nonnegative integer coefficients. As a consequence, if $q$ is an element of any $\mathbb{Z}$-algebra, then $(n)_q, (n)_q!$ and $\binom{n}{k}_q$ are well-defined elements therein.

For an indeterminate $t$ and $n$ a nonnegative integer, define the $q$-Pochhammer symbol

$$ (2.2) \qquad (t; q)_n := \prod_{1 \le i \le n} (1 - tq^{i-1}). $$

Finally, we record Cauchy's $q$-binomial theorems that state

$$ (2.3) \qquad (t; q)_n = \sum_{0 \le n \le k} (-1)^k \binom{j}{k} t^k, $$

$$ (2.4) \qquad \frac{1}{(t; q)_n} = \sum_{j \ge 0} \binom{n+j-1}{j} t^j. $$

### 2.1. N-vectors and compositions.
We call a sequence $c = (c_i)_{i \in \mathbb{Z}} \in \mathbb{N}^\mathbb{Z}$ an $\mathbb{N}$-vector if its support is finite. Recall that the support of $c$, denoted by $\text{Supp}(c)$, is the set of indices $i \in \mathbb{Z}$ such that $c_i > 0$. Let $\mathcal{W}$ be the set of $\mathbb{N}$-vectors. For $c \in \mathcal{W}$, define its weight $|c|$ to equal $\sum_i c_i$, and let $\mathcal{W}^k$ be the set of $\mathbb{N}$-vectors with $|c| = k$. We also define $e(c) = |c| - |\text{Supp}(c)|$. Note that $e(c)$ is nonnegative, and is equal to 0 precisely when $c_i \in \{0, 1\}$ for all $i$. Such vectors are naturally identified with finite subsets of $\mathbb{Z}$ via their support.

We will also refer to finite sequences $(c_1, \dots, c_N)$ of nonnegative integers as $\mathbb{N}$-vectors, or simply vectors. They are naturally embedded in $\mathcal{W}$ by setting $c_i = 0$ for all $i \in \mathbb{Z} \setminus [N]$. We write $\mathcal{W}_N$ for these finite sequences, and $\mathcal{W}_N^k$ for those with $|c| = k$. Let $\text{rev}(c)$ denote the reverse of the vector $c$: if $c = (c_1, \dots, c_N)$, then $\text{rev}(c)$ is by definition $(c_N, \dots, c_1)$. Given an $\mathbb{N}$-vector $c = (c_1, \dots, c_n)$, we define $N(c) = \sum_{1 \le i \le n} (i-1)c_i$.

A composition $\alpha$ of $r$ is an $\mathbb{N}$-vector $(\alpha_1, \dots, \alpha_N)$ with positive entries such that $\alpha_1 + \alpha_2 + \dots + \alpha_N = r$. This is denoted $\alpha \vdash r$. Let $\text{Set}(\alpha)$ denote the subset of $[r-1]$ associated to $\alpha$ under the folklore one-to-one correspondence $\alpha \mapsto \{\alpha_1, \alpha_1 + \alpha_2, \dots, \alpha_1 + \alpha_2 + \dots + \alpha_{N-1}\}$.
2.2. **Symmetric and quasisymmetric polynomials/functions.** Throughout, let $\mathbf{x} = \{x_i\}_{i \in \mathbb{Z}}$, $\mathbf{x}_+ = \{x_i\}_{i \in \mathbb{Z}_{>0}}$ and $\mathbf{x}_n = \{x_i \mid i \in [n]\}$ for $n$ a positive integer.

A polynomial $f \in \mathbb{Q}[\mathbf{x}_n]$ is called quasisymmetric if for any strong composition $(\alpha_1, \dots, \alpha_k)$ the coefficient of $x_{i_1}^{\alpha_1} \cdots x_{i_k}^{\alpha_k}$ equals that of $x_1^{\alpha_1} \cdots x_k^{\alpha_k}$ whenever $1 \le i_1 < \cdots < i_k \le n$. We denote the ring of quasisymmetric polynomials in $x_1, \dots, x_n$ by QSym$_n$. A linear basis for the degree $d$ homogeneous component of QSym$_n$ is given by the fundamental quasisymmetric polynomials $F_\alpha(x_1, \dots, x_n)$ indexed by compositions $\alpha \vdash d$. To define this, recall the correspondence sending $\alpha \vdash d$ to Set($\alpha$) $\subseteq [d-1]$ from the last section. We have

$$ (2.5) \qquad F_{\alpha}(x_1, \dots, x_n) = \sum_{\substack{1 \le i_1 \le \dots \le i_d \le n \\ i_j < i_{j+1} \text{ if } j \in \text{Set}(\alpha)}} x_{i_1} \cdots x_{i_d}. $$

We note here that $F_\alpha(x_1, \dots, x_n) = 0$ if $\ell(\alpha) > n$.

Let QSym denote the ring of quasisymmetric functions. Elements of QSym can be defined as bounded-degree formal power series $f \in \mathbb{Q}[\mathbf{x}_+]$ such that for any strong composition $(\alpha_1, \dots, \alpha_k)$ the coefficient of $x_{i_1}^{\alpha_1} \cdots x_{i_k}^{\alpha_k}$ equals that of $x_1^{\alpha_1} \cdots x_k^{\alpha_k}$ for positive integers $i_1 < \cdots < i_k$. The fundamental quasisymmetric functions $F_\alpha$ for $\alpha$ a strong composition are then naturally defined by removing the condition $i_d \le n$ in the sum (2.5).

2.3. **Reduced words of permutations, and Schubert polynomials.** We denote the set of permutations on $n$ letters by $\mathbb{S}_n$. An inversion in $w \in \mathbb{S}_n$ is an ordered pair $(i, j)$ such that $i < j$ and $w_i > w_j$. The number of inversions will be denoted by $\text{inv}(w)$. This quantity is also otherwise known as the length of $w$ and denoted by $\ell(w)$. Of particular importance is the subset $\mathbb{S}_n'$ of $\mathbb{S}_n$ comprising permutations of length $n-1$. A descent in $w \in \mathbb{S}_n$ is an index $i \in [n-1]$ such that $w_i > w_{i+1}$. The set of descents in $w$ will be denoted by $\text{Des}(w)$. The sum of entries in $\text{Des}(w)$ is referred to as the major index of $w$ and denoted by $\text{maj}(w)$.

A reduced expression of a permutation $w$ is any minimal length factorization $w = s_{i_1} \dots s_{i_{\ell(w)}}$ where each $s_{ij}$ is a simple transposition. We refer to the word $i_1 \dots i_{\ell(w)}$ as a reduced word. The set of reduced words for $w$ is denoted by $\text{Red}(w)$. Given $\mathbf{a} \in \text{Red}(w)$, its content $\text{cont}(\mathbf{a})$ is the $\mathbb{N}$-vector whose $j$th entry counts occurrences of $j$ in $\mathbf{a}$ for all $j$. We define the statistic comaj($\mathbf{a}$) to be the sum of all $j$ such that $a_j < a_{j+1}$. For instance given the reduced word $\mathbf{a} = 7534232$ for $w = 16423587 \in \mathbb{S}_8$, we have $\text{cont}(\mathbf{a}) = (0, 2, 2, 1, 1, 0, 1)$ and $\text{comaj}(\mathbf{a}) = 3 + 5 = 8$.

2.4. **Schubert polynomials.** Let $\text{Sym}_n \subseteq \text{QSym}_n \subseteq \mathbb{Q}[\mathbf{x}_n]$ be the subring of symmetric polynomials in $x_1, \dots, x_n$, and $\text{Sym}_n^+$ be the ideal of $\mathbb{Q}[\mathbf{x}_n]$ generated by elements $f \in \text{Sym}_n$ such that $f(0) = 0$. The quotient ring $R_n = \mathbb{Q}[\mathbf{x}_n]/\text{Sym}_n^+$ is the coinvariant ring.

Let $\partial_i$ be the divided difference operator on $\mathbb{Q}[\mathbf{x}_n]$, given by

$$ (2.6) \qquad \partial_i(f) = \frac{f - s_i \cdot f}{x_i - x_{i+1}}. $$

Define the Schubert polynomials for $w \in \mathbb{S}_n$ as follows: $\mathfrak{S}_{w_0} = x_1^{n-1} x_2^{n-2} \cdots x_{n-1}$, while if $i$ is a descent of $w$, let $\mathfrak{S}_{w_i} = \partial_i \mathfrak{S}_w$. Here $w_0$ is the longest word in $\mathbb{S}_n$. For $w \in \mathbb{S}_n$, the Schubert polynomial $\mathfrak{S}_w$ is a homogeneous polynomial of degree $\ell(w)$ in $\mathbb{Q}[\mathbf{x}_n]$. In fact Schubert polynomials are well defined for $w \in \mathbb{S}_\infty$. Moreover, when $w \in \mathbb{S}_\infty$ runs through all permutations whose largest descent is at most $n$, the Schubert polynomials $\mathfrak{S}_w$ form a basis for $\mathbb{Q}[\mathbf{x}_n]$.
### 3. THE KLYACHKO ALGEBRA $\mathcal{K}$

Let $\mathbf{k}$ be a field of characteristic zero, and $q \in \mathbf{k}$. We assume that $q$ is not a nontrivial root of unity in $\mathbf{k}$. In particular $q$ can be 1 but necessarily $q \neq -1$. This condition ensures that $(n)_q \neq 0$ for $n \ge 1$, so that we can safely divide by $q$-integers and $q$-factorials.

We will mostly be interested in the ‘generic’ case where $q$ is an indeterminate and $\mathbf{k} = \mathbb{Q}(q)$ or $\mathbb{C}(q)$ say. However important applications occur when:

* $\mathbf{k} = \mathbb{R}$ and $q > 0$, cf. §5.

* $q$ is a prime power, cf. §7;

The case $q = 1$ is the starting point of this work, since certain results presented here will give new proofs of certain results of the authors in [33, 34].

**3.1. The algebra $\mathcal{K}$**. The central object of our study is the following $\mathbf{k}$-algebra depending on the parameter $q$.

**Definition 3.1** (Klyachko algebra $\mathcal{K}$). Let $\mathcal{K} = \mathcal{K}^q$ be the commutative algebra over $\mathbf{k}$ on the generators $\{u_i | i \in \mathbb{Z}\}$ subject to the following relations for all $i \in \mathbb{Z}$:

$$ (3.1) \qquad (q+1)u_i^2 = qu_i u_{i-1} + u_i u_{i+1}. $$

It is a quadratic algebra, i.e. its defining relations have degree two. Let $z = (z_i)_{i \in \mathbb{Z}}$ be indeterminates; we will also need $z_+ = (z_i)_{i \in \mathbb{Z}_+}$ and $z_r = (z_i)_{i=1, \dots, r}$ for $r > 0$. We let

$$ \pi : \mathbf{k}[z] \to \mathcal{K}, z_i \mapsto u_i $$

be the defining projection. If we let $\mathrm{IK}$ be the ideal of $\mathbf{k}[z]$ generated by the elements $(q+1)z_i^2 - qz_iz_{i-1} - z_iz_{i+1}$ for $i \in \mathbb{Z}$, then $\mathcal{K}$ is by definition isomorphic to $\mathbf{k}[z]/\mathrm{IK}$.

*Shift and homotheties.* Consider the shift $\tau: i \mapsto i+1$ on $\mathbb{Z}$. This induces an automorphism on $\mathbf{k}[z]$ via $z_i \mapsto z_{i+1}$, which we continue to denote by $\tau$. The relations of $\mathcal{K}$ are invariant under $\tau$, so that $u_i \mapsto u_{i+1}$ defines an automorphism of $\mathcal{K}$ still denoted by $\tau$ and named shift.

We also note that for any $\lambda \in \mathbf{k}^*$, $u_i \mapsto \lambda u_i$ extend to an automorphism of $\mathcal{K}$ since the relations (3.1) are homogeneous.

**Remark 3.2.** There is a more homogeneous version of the relations of $\mathcal{K}$, namely:

$$ (q_1 + q_2)u_i^2 = q_1 u_i u_{i-1} + q_2 u_i u_{i+1}. $$

for some $q_1, q_2 \in \mathbf{k}$. If $q_2 \neq 0$ this becomes the relation for $\mathcal{K}^q$ with $q = q_1/q_2$ so there is no loss of generality in keeping just one parameter, as we opted to do in our definition.

The homogeneous version has the advantage of exhibiting more symmetry. In particular the relation is invariant under $u_j \mapsto u_{-j}$ and $q_1 \leftrightarrow q_2$, which shows that $\mathcal{K}^q \simeq \mathcal{K}^{1/q}$ for nonzero $q$.

*Quotients.* Given any subset $I$ of $\mathbb{Z}$, we let $\mathcal{K}_I$ be the algebra generated by $u_i \in I$ subject to the relations (3.1) with $u_i = 0$ for $i \notin I$. That is, $\mathcal{K}_I$ is the quotient of $\mathcal{K}$ by the ideal generated by the $u_i$ for $i \notin I$. The most important quotients are for $I$ semi-infinite and for $I$ an interval:

**Definition 3.3.** Let $\mathcal{K}_+ := \mathcal{K}_{\mathbb{Z}_+}$ and $\mathcal{K}_n := \mathcal{K}_{\{1, \dots, n-1\}}$.

We define $\pi_+ : \mathbf{k}[z_+] \to \mathcal{K}_+$ to be the natural projection sending $z_i$ to $u_i$, whose kernel $\mathrm{IK}_+$ is generated by the elements $(q+1)z_i^2 - qz_iz_{i-1} - z_iz_{i+1}$ for $i > 1$ together with $(q+1)z_1^2 - z_1z_2$.
Analogously, define $\pi_n : \mathbf{k}[\mathbb{z}_{n-1}] \to \mathcal{K}_n$ with kernel $\mathbf{I}\mathcal{K}_n$ generated by the elements $(q+1)z_1^2 - z_1z_2$, $(q+1)z_{n-1}^2 - qz_{n-1}z_{n-2}$ and $(q+1)z_i^2 - qz_iz_{i-1} - z_iz_{i+1}$ for $1 < i < n-1$.

Note that we have kept the notation $u_i$ for the generators $u_i$ in different algebras $\mathcal{K}_I$, in order to avoid too much notation. When a computation holds in a quotient but not in the full algebra $\mathcal{K}$, we will always make sure to specify it clearly.

Remark 3.4. The presentation of $\mathcal{K}_n$ for $q = 1$ coincides with $H^*(\text{Perm}_n, \mathbb{Q})^{\mathbb{S}_n}$ as proved in [24, 25] and used by the authors in [34].

## 3.2. Basic identities.

**Definition 3.5.** For any finite subset $I \subset \mathbb{Z}$, define $u_I := \prod_{i \in I} u_i \in \mathcal{K}$.

Given the defining relations of $\mathcal{K}$, it is natural to expect that these squarefree monomials form a linear basis of $\mathcal{K}$, which is the content of Proposition 3.9. Toward establishing this we prove some basic identities that hold in $\mathcal{K}$. The next lemma lays the groundwork for many of the computations in this article.

**Lemma 3.6.** Consider integers $a \le b$ and $i \in [a, b]$. In $\mathcal{K}$, we have

$$ (3.2) \qquad (b-a+2)_q u_i u_{[a,b]} = q^{i-a+1} (b-i+1)_q u_{[a-1,b]} + (i-a+1)_q u_{[a,b+1]} $$

Moreover, (3.2) is a consequence of the relations (3.1) for $i = a, \dots, b$.

The second claim shows a *local* property of the relation, which is useful in order to compare computation in various quotients $\mathcal{K}_I$.

*Proof.* Let $L = u_{[a-1,b]}$ and $R = u_{[a,b+1]}$, which are the two elements of $\mathcal{K}$ occurring on the right hand side of (3.2). Then the relations (3.1) gives that the elements $f_i := u_i u_{\{a,\dots,b\}}$ satisfy

$$ (1+q)f_i = qf_{i-1} + f_{i+1} \quad \text{for } a < i < b; $$

$$ (1+q)f_a = qL + f_{a+1}; $$

$$ (1+q)f_b = qf_{b-1} + R. $$

Let $n = b - a + 1$. Let $F$ be the $n \times 1$ vector with entries $f_i$; $M$ the $n \times n$ tridiagonal Toeplitz matrix with diagonal $1+q$, superdiagonal $-1$ and subdiagonal $-q$; and $C$ the $n \times 1$ vector with $C_1 = qL, C_n = R$ and all other entries zero. Then the above system of equations can be succinctly written $MF = C$. For $a=1, b=4$ we get

$$ \underbrace{\begin{pmatrix} 1+q & -1 & 0 & 0 \\ -q & 1+q & -1 & 0 \\ 0 & -q & 1+q & -1 \\ 0 & 0 & -q & 1+q \end{pmatrix}}_{M} \underbrace{\begin{pmatrix} u_1 u_{[1,4]} \\ u_2 u_{[1,4]} \\ u_3 u_{[1,4]} \\ u_4 u_{[1,4]} \end{pmatrix}}_{F} = \underbrace{\begin{pmatrix} q u_{[0,4]} \\ 0 \\ 0 \\ u_{[1,5]} \end{pmatrix}}_{C} $$

The determinant of $M$ can be computed to be $(b-a+2)_q$, which is nonzero by our assumption on $q$. The inverse $M^{-1}$ is easily checked to be given by

$$ (M^{-1})_{ij} = \frac{1}{(b-a+2)_q} \times \begin{cases} q^{j-i} (n+1-i)_q (j)_q & \text{for } i \ge j; \\ (n+1-j)_q (i)_q & \text{for } i < j. \end{cases} $$
Then the rows of the identity $F = M^{-1}C$ give the relations (3.2). The second claim in Lemma 3.6 follows immediately from the previous proof. $\square$

We note a corollary which follows from elementary computations:

**Corollary 3.7.** Let $i \in \mathbb{Z}$ and assume the interval $[a, b]$ contains $i-1$ or $i$; that is $[a, b] \cap \{i-1, i\} \neq \emptyset$. Then we have

$$ (3.3) \qquad (b-a+2)_q(u_i-u_{i-1})u_{[a,b]} = q^{i-a} (u_{[a,b+1]} - u_{[a-1,b]}). $$

Now we give an important relation allowing us to expand any element as a linear combination of the elements $u_I$.

Let $c$ be an $\mathbb{N}$-vector and let $J = \text{Supp}(c)$. Assume there exists an index $i$ such that $c_i \ge 2$, and fix such an $i$. Let $I = [a, b]$ be the maximal interval in $J$ containing $i$, so that $a-1, b+1 \notin J$ and thus $c_{a-1} = c_{b+1} = 0$. Let $L_i(c)$ (resp. $R_i(c)$) be the $\mathbb{N}$-vector $c'$ defined by $c'_k = c_k$ if $k \neq a-1, i$ (resp. $k \neq i, b+1$), $c'_i = c_i - 1$, and $c'_{a-1} = 1$ (resp. $c'_{b+1} = 1$). In words, these are obtained from $c$ by decrementing $c_i$ by 1 and incrementing $c_{a-1}$ (resp. $c_{b+1}$) by 1.

For an $\mathbb{N}$-vector $c$, let

$$ u^c = \prod_{i \in \mathbb{Z}} u_i^{c_i}. $$

**Corollary 3.8.** With $c, i, a, b$ as above and assuming $c_i \ge 2$, we have in $K$

$$ (3.4) \qquad (b-a+2)_q u^c = q^{i-a+1} (b-i+1)_q u^{L_i(c)} + (i-a+1)_q u^{R_i(c)}. $$

*Proof.* By definition the generators $u_j$ for $j = a, \dots, b$ occur in $u^c$, and since $c_i \ge 2$ we can apply (3.2). Since $a-1, b+1 \notin J$ we have the desired result. $\square$

### 3.3. The squarefree basis.

**Proposition 3.9.** Let $J \subset \mathbb{Z}$. The $u_I$ for $I$ finite subset of $J$ form a $\mathbf{k}$-basis of the algebra $K_J$.

We denote the basis of squarefree monomials for $K_I$ by $B_I$. In the important cases $K, K_+$, and $K_n$, we denote the corresponding bases by $B, B_+$, and $B_n$ respectively.

*Proof.* From (3.4), by induction on $e(c) = |c| - |\text{Supp}(c)|$, one can reduce any monomial in $u_i$ to a linear combination of squarefree monomials. Indeed $e(L_i(c)) = e(R_i(c)) = e(c) - 1$ when $c_i \ge 2$, and recall that $e(c) = 0$ precisely when $u^c$ is squarefree. It follows immediately that the $u_I$ span $K$; by passing to the quotient, the same holds for any $K_J$.

We now want to show linear independence of these elements. First, it is enough to prove this for the algebras $K_n$ for $n \ge 1$. Indeed any relation between squarefree monomials in an algebra $K_J$ must hold in an algebra $K_{J'}$ for $J'$ a finite interval: this is a consequence of the second part of Lemma 3.6. By the shift invariance of the relations, we can assume $J' = [1, n-1]$ for a certain $n$.

We will use standard notions of commutative algebra in the proof, for which we refer to [41, §I.5] for instance. Recall that $K_n$ is defined as the quotient of $\mathbf{k}[z_{n-1}]$ by $\mathbb{I}K_n$, an ideal generated by $n-1$ quadratic polynomials. Now we have just shown that squarefree monomials span $K_n$, which is therefore finite-dimensional over $\mathbf{k}$. It follows that the generators of $\mathbb{I}K_n$ form a homogeneous system of parameters for $\mathbf{k}[z_{n-1}]$, as a module over itself.
Since $\mathbf{k}[\mathbf{z}_{n-1}]$ is Cohen-Macaulay, these generators form necessarily a regular sequence. Hence we get the following identity between Hilbert series<fnref n="2" />:

$$ \mathrm{Hilb}(\mathbf{k}[\mathbf{z}_{n-1}], t) = \frac{1}{(1-t^2)^{n-1}} \mathrm{Hilb}(\mathcal{K}_n, t). $$

Since $\mathrm{Hilb}(\mathbf{k}[\mathbf{z}_{n-1}], t) = \frac{1}{(1-t)^{n-1}}$, we obtain $\mathrm{Hilb}(\mathcal{K}_n, t) = (1+t)^{n-1}$. So $\mathcal{K}_n$ has $\mathbf{k}$-dimension $2^{n-1}$, which is exactly the number of squarefree monomials it contains. Since we have shown that these span $\mathcal{K}_n$, they necessarily form a basis. $\square$

**Corollary 3.10.** Let $P \in \mathbf{k}[\mathbf{z}_+]$, and suppose that there exists $N > 0$ such that $P(u_1, u_2, \dots) = 0$ in $\mathcal{K}_n$ for all $n \ge N$. Then $P(u_1, u_2, \dots) = 0$ in $\mathcal{K}_+$.

*Proof.* $P(u_1, u_2, \dots)$ vanishes in $\mathcal{K}_+$ if all its coefficients on the basis $u_I, I \subset \mathbb{Z}_+$ are zero. Now let $d$ be the degree of $P$ and $a$ be the maximal index of an indeterminate $z_i$ occurring in $P$. It follows from the second part of Lemma 3.6 that, in order to reduce $P$ in the basis $u_I, I \subset \mathbb{Z}_+$, one only needs relations involving generators $u_i$ with $i < a + d$. These relations occur in any $\mathcal{K}_n$ for $n$ large enough, and so by hypothesis we have $P(u_1, u_2, \dots) = 0$ in $\mathcal{K}_+$. $\square$

As we will see in §5, coefficients of general monomials expressed in the basis $\mathcal{B}$ have a probabilistic interpretation due to Diaconis and Fulton [11]. In this seminal work, the algebras $\mathcal{K}_I$ actually occur as special cases of a wide class of algebras, and Proposition 3.9 is proved in greater generality. We included our own proof as to be self contained; our arguments are also of a different nature.

3.4. **Specializations.** The following specialization will be instrumental in this work to go from computations in $\mathcal{K}$ to numerical formulas.

**Proposition 3.11.** *The assignment*

$$ u_i \mapsto \begin{cases} (i)_q & \text{for } i > 0; \\ 0 & \text{for } i \le 0, \end{cases} $$

* extends to a unique algebra morphism $\mathrm{sp} : \mathcal{K} \to \mathbf{k}$.

*Proof.* One has $(q+1)(i)_q^2 = q(i)_q(i-1)_q + (i)_q(i+1)_q$ for $i > 1$ and $(q+1)(1)_q^2 = 0 \times (1)_q + (1)_q(2)_q$, and the relations are trivially verified for $i \le 0$ so the map extends to an algebra morphism. It is unique since the $u_i$ generate $\mathcal{K}$ as an algebra. $\square$

The specialization obviously factors through $\mathcal{K}_+$, and we keep the same notation sp:

$$ \mathrm{sp} : \mathcal{K}_+ \to \mathbf{k} $$

$$ u_i \mapsto (i)_q $$

Now consider an interval $I = [a+1, b]$ with $a \ge 0$ so that $u_I \in \mathcal{K}_+$. Then we get

$$ (3.5) \qquad \mathrm{sp} \left( \frac{u_{[a+1, b]}}{(b-a)q!} \right) = \binom{b}{a} q. $$

This evaluation will allow us to go from identities in $\mathcal{K}_+$ to numerical formulas.

<footnote n="2">²Recall that the Hilbert series $\mathrm{Hilb}(\oplus_{i \ge 0} V_i, t)$ of a graded vector space with finite-dimensional homogeneous components is the generating series $\sum_{i \ge 0} (\mathrm{dim} V_i t^i)$.</footnote>
*Other specializations.* It is natural to consider specializations, i.e. characters of $\mathcal{K}$. Can we characterize the algebra morphisms $\mathcal{K} \to \mathbf{k}$? Given the presentation (3.1), the problem is equivalent to characterizing all sequences $(a_i)_{i \in \mathbb{Z}}$ in $\mathbf{k}$ that satisfy $(1+q)a_i^2 = qa_ia_{i-1} + a_ia_{i+1}$ for all $i$. The corresponding specialization is then given by $u_i \mapsto a_i$.

◦ A first family of specializations is given by

$$a_i = \alpha + \beta q^i \text{ for all } i$$

with $\alpha, \beta \in \mathbf{k}$ two parameters. This family contains in particular all solutions $(a_i)_{i \in \mathbb{Z}}$ that do not vanish.

◦ A second family of specializations, depending on two integer parameters $m \le M$ and two parameters $\alpha, \beta \in \mathbf{k}$, can be given by

$$\begin{cases} a_i = 0 & \text{for } i \in [m, M]; \\ a_{M+k} = \alpha(k)_q & \text{for } k > 0; \\ a_{m-k} = \beta(k)_{1/q} & \text{for } k > 0. \end{cases}$$

It is then an easy exercise to show that every specialization belongs to one of the two families.

It follows immediately that the specializations of $\mathcal{K}_+$ are precisely the maps $\alpha \cdot \text{sp} \circ \tau^{-m}$ for $\alpha \in \mathbf{k}$ and $m \ge 0$, where $\tau$ is the shift map introduced at the beginning of this section. The only specialization from $\mathcal{K}_n$ is the augmentation $u_i \mapsto 0$ sending elements of positive degree to zero.

### 4. $q$-DIVIDED SYMMETRIZATION

In this section we introduce $q$-divided symmetrization, which is a natural $q$-deformation of the divided symmetrization operator introduced by Postnikov [38] and further studied in [2, 33, 37]. We state a few properties of this operator before showing its direct connection with the algebra $\mathcal{K}$ in Theorems 4.11 and 4.15. The connection goes through an interesting family of numbers, the *remixed Eulerian numbers* $A_q^q$, further studied in §5.

**4.1. Definition and first properties.** Consider the natural action of $\mathbb{S}_n$ on $\mathbf{k}[x_1, \dots, x_n]$ obtained by letting the generator $s_i$ for $1 \le i \le n-1$ act by swapping $x_i$ and $x_{i+1}$. The divided difference operator $\partial_i$ is then given by $\frac{1-s_i}{x_i - x_{i+1}}$. Following [12, §2], define operators $\square_i$ for $1 \le i \le n-1$ acting on functions in $x_1, \dots, x_n$ as$^3$

$$\square_i = \partial_i(qx_i - x_{i+1})$$

These operators can be described via Demazure-Lusztig operators $T_i$ that act on polynomials as

$$T_i = (q-1)\partial_i x_i + s_i.$$

Indeed, one can check that $\square_i = T_i + 1$. Since the $T_i$ satisfy Hecke relations,$^4$ one obtains a well-defined operator $T_w$ for $w \in \mathbb{S}_n$ by picking a reduced word. For $w_o$ the longest word in $\mathbb{S}_n$, consider the operator $\square_{w_o}$ [12, Theorem 3.1] expressed as follows:

$$(4.1) \qquad \square_{w_o} = \partial_{w_o} \prod_{1 \le i < j \le n} (qx_i - x_j).$$

<footnote>$^3$We note here that the authors of [12] act on the left, whereas we act on the right.</footnote>

<footnote>$^4$In fact $s_i$, $\partial_i$, and $T_i$ are all special cases of a five parameter family [29] that satisfy Hecke relations.</footnote>
Recall that $\partial_{w_o}$ simply performs antisymmetrization followed by division by the Vandermonde determinant. In fact, $\square_{w_o}$ is the maximal Yang-Baxter element as defined in [10], up to a power of $q$; see also [27, §7]. By [12, Theorem 3.1], the operator $\square_{w_o}$ affords the expansion

$$ (4.2) \qquad \square_{w_o} = \sum_{\sigma \in S_n} T_{\sigma}. $$

**Definition 4.1.** Define the $q$-divided symmetrization (abbreviated to $qDS$ on occasion) of $f \in k[x_1, \dots, x_n]$ to be

$$ \langle f \rangle_n^q := \square_{w_o} \frac{f}{\prod_{1 \le i \le n-1} (qx_i - x_{i+1})} = \sum_{w \in S_n} T_w \left( \frac{f}{\prod_{1 \le i \le n-1} (qx_i - x_{i+1})} \right) $$

When $q = 1$, the Hecke operator $T_w$ reduces to the permutation $w$ acting on polynomials. Definition 4.1 thus specializes to Postnikov's divided symmetrization [38, §3], which was the starting point for our definition. We will describe several properties of $qDS$ that extend known properties of the case $q = 1$. Thanks to (4.1) we have $\langle f \rangle_n^q = \partial_{w_o} (f \prod_{1 \le i < j \le n-1} (qx_i - x_j))$ and so $\langle f \rangle_n^q$ is a symmetric polynomial in $x_1, \dots, x_n$.

It follows that if $\deg(f) < n-1$, then $\langle f \rangle_n^q$ is 0. So the 'first' instance where $qDS$ becomes interesting is when $\deg(f) = n-1$, in which case $f \mapsto \langle f \rangle_n^q$ is a linear form on $k[x_1, \dots, x_n]$. For the purposes of this article we restrict ourselves to this setting, as it turns out that this is the case of interest in conjunction with the algebra $K$.

It is clear that the definition just mentioned make $qDS$ appear rather arduous to compute. The next result, extending a formula of Petrov [37, Eq. (1)], goes a long way in simplifying that task.

**Lemma 4.2.** If $f \in k[x_1, \dots, x_n]$ of degree $n-1$ factors as $g(x_1, \dots, x_i)(qx_i - x_{i+1})h(x_{i+1}, \dots, x_n)$, then

$$ \langle f \rangle_n^q = \binom{n}{i}_q \langle g \rangle_i^q \langle h \rangle_{n-i}^q. $$

*Proof.* Let $C(i, n-i)$ be the set of minimal length coset representatives for $S_n/(S_i \times S_{n-i})$. We may factor $\square_{w_o}$ as

$$ (4.3) \qquad \square_{w_o} = \sum_{w \in S_n} T_w = \sum_{v \in C(i, n-i)} T_v \left( \sum_{w' \in S_i} T_{w'} \right) \left( \sum_{w'' \in S_{n-i}} T_{w''} \right) $$

Given the special form that $f$ possesses, from the above factorization we infer that

$$ (4.4) \qquad \langle f \rangle_n^q = \langle g \rangle_i^q \langle h \rangle_{n-i}^q \sum_{v \in C(i, n-i)} T_v(1). $$

Since $T_i(1) = q$ for any $i$, from (4.4) we obtain

$$ (4.5) \qquad \langle f \rangle_n^q = \langle g \rangle_i^q \langle h \rangle_{n-i}^q \sum_{v \in C(i, n-i)} q^{\ell(v)}. $$

The claim follows because the length generating function over minimal length coset representatives is given by $q$-binomial coefficients. $\square$
<figure><img src="image_2.png" /><figcaption>FIGURE 1. $\mathcal{P}_c$ when $c = (0, 3, 0, 0, 0, 1, 3, 0)$ with $S_c = \{1, 4, 5, 6\}$.</figcaption></figure>

4.2. **qDS of monomials.** We represent $\mathbb{N}$-vectors $(c_1, \dots, c_n)$ as *Lukasiewicz paths* starting at (0,0) by interpreting each $c_i$ as a vector step $(1, c_i - 1)$. We refer to the path corresponding to $c$ as $\mathcal{P}_c$. For instance, Figure 1 depicts $\mathcal{P}_c$ for $c = (0, 3, 0, 0, 0, 1, 3, 0)$ The lattice point on $\mathcal{P}_c$ with x-coordinate $i$ has y-coordinate given by $h_i = h_i(c) := (\sum_{k=1}^i c_k) - i$. In particular $h_0 = 0$ and $h_n = \sum_i c_i - n$. We define a statistic by

$$h(c) = \sum_{1 \le i \le n-1} h_i.$$

We are now ready to state the $q$-analogue of [38, Proposition 3.5]. The authors do not know of a proof in the spirit of Postnikov’s argument which relies on constant term extraction. Instead, our proof, presented in the appendix, is based on the repeated use of Lemma 4.2.

**Proposition 4.3.** Let $c = (c_1, \dots, c_n)$ be an $\mathbb{N}$-vector with $\sum_i c_i = n-1$. Let $S$ be the set of $i \in \{1, \dots, n-1\}$ such that $h_i(c) < 0$. Let $X_S$ be the set of permutations in $S_n$ with descent set $S$. Then

$$(4.6) \qquad \langle x_1^{c_1} \dots x_n^{c_n} \rangle_n^q = (-1)^{|S|} \sum_{\sigma \in X_S} q^{\binom{n-1}{2} - \mathrm{inv}(\sigma) - h(c)}$$

**Example 4.4.** Consider the monomial corresponding to $c = (1, 0, 1)$. Then $S = \{2\}$, and therefore $X_S = \{132, 231\}$. Also, we have $h(c) = (1-1) + (1-2) = -1$. Proposition 4.3 tells us that

$$\langle x_1 x_3 \rangle_3^q = -(q^{\binom{3-1}{2}} - \mathrm{inv}(132)+1) + q^{\binom{3-1}{2}} - \mathrm{inv}(231)+1) = -(q+1).$$

4.3. **Remixed Eulerian numbers.** For an $\mathbb{N}$-vector $c = (c_1, \dots, c_r)$, let

$$y_c = x_1^{c_1} (x_1 + x_2)^{c_2} \dots (x_1 + \dots + x_r)^{c_r},$$

a polynomial of degree $|c|$.

**Definition 4.5 (Remixed Eulerian numbers)** $A_c^q$. Let $c \in W_r^r$, so that $c = (c_1, \dots, c_r)$ with $|c| = r$. We define the *remixed Eulerian number* $A_c^q \in \mathbf{k}$ by

$$(4.7) \qquad A_c^q = \langle y_c \rangle_{r+1}^q.$$

Note that $A_c^q$ indeed belongs to the base field $\mathbf{k}$ since $y_c$ has degree $r$ and we apply qDS with respect to $r+1$ variables, see remarks following Definition 4.1. For $q=1$, we get back the *mixed Eulerian numbers* $A_c = A_c^1$ introduced by Postnikov [38, §16]; see also [34, §4].

**Remark 4.6.** It follows from the definition of qDS that $A_c^q \in \mathbb{Z}[q] \subset \mathbf{k}$. If $q$ is transcendental over $\mathbb{Q} \subset \mathbf{k}$, then $A_c^q$ is a polynomial in $q$ that does not depend on $\mathbf{k}$. This explains why we can, and will, safely talk about remixed Eulerian numbers independently of $\mathbf{k}$, as polynomials in $q$.
**Remark 4.7.** Notice that we divide-symmetrize with respect to $x_1, \dots, x_{r+1}$, while $y_c$ for $c = (c_1, \dots, c_r)$ only depends on variables among $x_1, \dots, x_r$. As the $T_i$ admit symmetric polynomials as scalars, we have $\langle y_{(c_1, \dots, c_{r+1})} \rangle_{r+1}^q = 0$ whenever $c_{r+1} > 0$, so there is no loss of generality in restricting to sequences with $c_{r+1} = 0$.

**Theorem 4.8.** For a fixed positive integer $r$, the family $(A_c^q)_{c \in W_r^c}$ is uniquely determined by the following conditions:

(a) $A_{(1^r)}^q = (r)_q!$.

(b) for any $i = 1, \dots, r$ such that $c_i \ge 2$,

$$ (4.8) \qquad (q+1)A_{(c_1, \dots, c_r)}^q = qA_{(c_1, \dots, c_{i-1}+1, c_{i-1}, \dots, c_r)}^q + A_{(c_1, \dots, c_{i-1}, c_{i+1}+1, \dots, c_r)}^q. $$

If $i=1$ (resp. $i=r$), then the first (resp. second) term on the right hand side is to be omitted.

**Example 4.9.** Here are all remixed Eulerian numbers $A_c^q$ indexed by $c = (c_1, c_2, c_3)$ such that $|c| = 3$. We suppress commas and parentheses in writing our compositions for clarity.

$$ \begin{aligned} A_{111}^q &= (1+q)(1+q+q^2) & A_{120}^q &= (1+q)^2 & A_{201}^q &= (1+q)^2 & A_{210}^q &= (1+q)^2 & A_{300}^q &= 1 \\ A_{102}^q &= q(1+q+q^2) & A_{012}^q &= q^2(1+q) & A_{021}^q &= q(1+q)^2 & A_{030}^q &= 2q(1+q) & A_{003}^q &= q^3 \end{aligned} $$

The careful reader will have observed that all $A_c^q$ listed here are polynomials in $q$ with nonnegative integral coefficients. This is not immediate from Theorem 4.8, nor from Definition 4.5. We establish this in §5 by working with a variant of equation (4.13).

**Proof of Theorem 4.8.** Let us first show that the numbers $A_c^q$ satisfy (a) and (b). First, expanding $y_{(1^r)} = x_1(x_1+x_2)\dots(x_1+\dots+x_r)$ gives the sum of all $r!$ monomials $x_{i_1}\dots x_{i_r}$ with $1 \le i_j \le j$. Write such monomials as $\mathbf{x}_i$ with $\mathbf{i} = (i_1, \dots, i_r)$. We apply Proposition 4.3 with $n=r+1$ to each of those monomials: let $m(\mathbf{i}) = (m_1, \dots, m_r, m_{r+1})$ where $m_j$ is the number of occurrences of $j$ in $m(\mathbf{i})$. Then the descent set $S$ attached to any vector $m(\mathbf{i})$ is empty, and thus (4.6) simplifies to $\langle \mathbf{x}_i \rangle_{r+1}^q = q^{\binom{r}{2}-h(m(\mathbf{i}))}$. Using $\sum_j j m_j = \sum_j i_j$, one computes easily $h(m(\mathbf{i})) = \binom{r}{2} - \sum_{j=1}^r i_j$. It follows that

$$ A_{(1^r)}^q = \sum_{\mathbf{i}} \langle \mathbf{x}_{\mathbf{i}} \rangle_{r+1}^q = \sum_{\mathbf{i}} q^{\sum_{j=1}^r i_j} $$

which is readily seen to be the desired $q$-factorial, proving (a).

We now focus on (b). To establish it we need to check that

$$ (4.9) \qquad \left\langle (q+1)y_{(c_1, \dots, c_r)} - qy_{(c_1, \dots, c_{i-1}+1, c_{i-1}, \dots, c_r)} - y_{(c_1, \dots, c_{i-1}, c_{i+1}+1, \dots, c_r)} \right\rangle_{r+1}^q = 0, $$

which by the definition of $y_c$ is equivalent to

$$ (4.10) \qquad \left\langle y_{(c_1, \dots, c_{i-1}, c_{i-1}, c_{i+1}, \dots, c_r)} (qx_i - x_{i+1}) \right\rangle_{r+1}^q = 0. $$

By expressing $x_1 + \dots + x_m$ as $(x_1 + \dots + x_i) + (x_{i+1} + \dots + x_m)$ for $m > i$, we may expand $y_{(c_1, \dots, c_{i-1}, c_{i-1}, c_{i+1}, \dots, c_r)}$ as

$$ (4.11) \qquad y_{(c_1, \dots, c_{i-1}, c_{i-1}, c_{i+1}, \dots, c_r)} = \sum_{k \ge 0} y_{(c_1, \dots, c_{i-1}, c_{i-1}+k)} f_k(x_{i+1}, \dots, x_r) $$
where only finitely many polynomials $f_k$ are nonzero. We can then apply Lemma 4.2 to obtain

$$ (4.12) \qquad \langle y_{(c_1, \dots, c_{i-1}, c_i-1, \dots, c_r)}(qx_i - x_{i+1}) \rangle_{r+1}^q = \binom{r+1}{i} \sum_{q \mid k \ge 0} \langle y_{(c_1, \dots, c_{i-1}, c_i-1+k)} \rangle_i^q \langle f_k \rangle_{r+1-i}^q $$

We claim that the right hand side vanishes. Indeed if $\deg(f_k) < r - i$, this is already true. So let us suppose that $\deg(f_k) \ge r - i$. If so, then we must have $\deg(y_{(c_1, \dots, c_{i-1}, c_i-1+k)}) \le i - 1$. Since $c_i \ge 2$, we know that $c_i - 1 + k \ge 1$, and thus $\langle y_{(c_1, \dots, c_{i-1}, c_i-1+k)} \rangle_i^q = 0$ because of the presence of the symmetric factor $x_1 + \dots + x_i$. Thus, the equality in (4.10) follows. The preceding argument is technically only valid for $i \ne 1, r$, and we leave it to the reader to check those two cases separately.

Now let us show that the $A_c^q$ are the only numbers satisfying these relations. The issue is that property (b) in Theorem 4.8 does not immediately determine these numbers by induction. However, one can easily deduce the new relations (4.13) below. These relations together with the initial condition (a) show that such a family of numbers is unique if it exists, by induction on $e(c) = |c| - |\text{Supp}(c)|$.

Let $i$ be such that $c_i \ge 2$. Let $I = [a, b] \subset [1, r]$ be the maximal interval of the support of $c$ containing $i$. Define $L_i(c), R_i(c)$ as in Lemma 3.6. A slight modification is in order: that if $a = 1$ (resp. $b = r$) then $L_i(c)$ (resp. $R_i(c)$) has support outside of $[1, r]$. In this case the corresponding mixed Eulerians are not defined, we set them to 0. Then we have

$$ (4.13) \qquad (b-a+2)_q A_c^q = q^{i-a+1} (b-i+1)_q A_{L_i(c)}^q + (i-a+1)_q A_{R_i(c)}^q. $$

The proof is entirely identical to Lemma 3.6, since the system of equations to solve is the same. This completes the proof of Theorem 4.8. $\square$

We reiterate that the relation in property (b) in Theorem 4.8 is of a different character than that in equation (4.13). Indeed the former implies, for instance, that

$$ (4.14) \qquad A_{012}^q = (1+q)A_{021}^q, $$

whereas the latter says that

$$ (4.15) \qquad (3)_q A_{012}^q = q^2 (1)_q A_{111}^q. $$

The second immediately implies that $A_{012} = q^2(1+q)$ given the initial condition $A_{111}^q = (3)_q!$. On the other hand, the first relation does not yield the same return right away.

### 4.4. qDS as top coefficient in $\mathcal{K}$.
Given the similarity in the second property in Theorem 4.8 and the defining relations of the Klyachko algebra $\mathcal{K}$, one senses that there is an intimate relation between qDS and computations in $\mathcal{K}$. This relation in the case $q = 1$ is implicit in [34], in which case this connection has a geometric explanation; cf. Remark 4.13 below.

We make the relation precise here, allowing for general $q$. We need to introduce certain elementary morphims first.

**Definition 4.10** ($\Delta, \Delta_+, \Delta_n$ and $\rho, \rho_+, \rho_n$). We define the morphism of algebras from $k[x]$ to $k[z]$ by

$$ \Delta : x_i \mapsto z_i - z_{i-1}. $$
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Commutative diagram grouping various algebra morphisms relevant to us. The morphisms from the bottom row are introduced in §4.4. The right hand side is dealt with in §6.3, cf. Corollary 6.6.</figcaption></figure>

We define also $\Delta_+$ from $k[x_+]$ to $k[z_+],$ and $\Delta_n$ from $k[x_n]$ to $k[z_{n-1}]$ by restriction where $z_i$ is set to 0 if it is not part of the image. Explicitly, $\Delta_+(x_i) = z_i - z_{i-1}$ for $i > 1$ and $\Delta_+(x_1) = z_1$; and $\Delta_n(x_i) = z_i - z_{i-1}$ for $1 < i < n$, $\Delta_n(x_1) = z_1$, $\Delta_n(x_n) = -z_{n-1}$.

Finally, we define $\rho := \pi \circ \Delta$, $\rho_+ := \pi \circ \Delta_+$, and $\rho_n := \pi \circ \Delta_n$.

Note in particular that $\Delta_+(x_1 + \cdots + x_i) = z_i$ so that $\Delta_+(y_c) = z^c$. These morphisms are illustrated in Figure 2.

**Theorem 4.11.** Let $f$ be a polynomial in $k[x_n]$ with $\deg(f) = n - 1$. Consider the expansion of $\rho_n(f) = f(u_1, u_2 - u_1, \dots, u_{n-1} - u_{n-2}, -u_{n-1})$ in the basis $B_n$, and let $\text{Top}_n(f)$ be the top coefficient in this expansion, namely that of $u_1 \cdots u_{n-1}$. Then

$$ (4.16) \qquad \langle f \rangle_n^q = (n-1)_q! \times \text{Top}_n(f). $$

*Proof.* Observe that polynomials $y_{(c_1, \dots, c_n)} = x_1^{c_1} (x_1 + x_2)^{c_2} \dots (x_1 + \dots + x_n)^{c_n}$ with $c = (c_1, \dots, c_n)$ satisfying $|c| = n-1$ comprise a basis of the degree $n-1$ homogeneous component of $k[x_n]$. By linearity, it suffices to check (4.16) on these basis elements.

When $c_n > 0$, then $\rho_n(y_c)$ vanishes and therefore $\text{Top}_n(y_c) = 0$. On the other hand, as mentioned in Remark 4.7, we have $\langle y_c \rangle_n^q = 0$ as well. Hence we now assume $c_n = 0$, and define $r = n-1$. We also redefine $c = (c_1, \dots, c_r)$ to keep notations simple. Now $\rho_n(y_c) = u^c$, so the right hand side of (4.16) for $f = y_c$ is $(r)_q!$ times the coefficient of $u_{[r]}$ in $u^c$; let $A'_c$ be this value. Since $\langle y_c \rangle_n^q = A_c^q$, we now need to show that the numbers $A'_c$ satisfy the two conditions of Theorem 4.8.

If $c = (1^r)$ then $u^c = u_{[r]}$ so $A'_c = (r)_q!$ as Property (a) in Theorem 4.8. Now if we have any $c_i \ge 2$, consider the relation (3.1), multiply both sides by $(r)_q!u^d$ for $d = (c_1, \dots, c_{i-1}, c_i - 2, c_{i+1}, \dots, c_r)$
and extract the coefficient of $u_{[r]}$. The resulting relation is Property (b) in Theorem 4.8 for $A'_c$, which finally shows that $A'_c = A_c$ and completes the proof. $\square$

**Example 4.12.** We revisit the monomials in Example 4.4. We set $n = 3$. If $f = x_1^2$, then $\rho_n(f) = u_1^2$, which in view of the relation $(1+q)u_1^2 = u_1u_2$ implies that the coefficient of $u_1u_2$ in $\rho_n(f)$ is $1/(1+q)$. Theorem 4.11 then says $\langle x_1^2 \rangle_3^q = 1$.

On the other hand, if we pick $f = x_1x_3$, then $\rho_n(f) = -u_1u_2$. This time, the coefficient that needs to be scaled by $(2)_q!$ is $-1$, and therefore $\langle x_1x_3 \rangle_3^q = -(1+q)$.

**Remark 4.13.** For $q = 1$, Theorem 4.11 follows from a geometric viewpoint, and the statement was exploited by the authors in [34]. The reasoning is as follows: we pick $f$ to be the Schubert polynomial $\mathfrak{S}_w$ for a permutation $w \in S_n$ of length $n-1$. It can be shown that it suffices to check the equality in Theorem 4.11 for such $f$.<fnref n="5" /> Now on the one hand, $\langle \mathfrak{S}_w \rangle_n^1$ computes certain intersection numbers $a_w$ for the permutahedral variety, as explained in [34], following [3, 23]. On the other hand, work of Klyachko [24, 25] mentioned in the introduction shows that these same numbers $a_w$ can be computed in the ring $\mathcal{K}_n^1 \simeq H^*(\mathrm{Perm}_n, \mathbb{Q})^{\mathbb{S}_n}$ by the formula $(n-1)! \times \mathrm{Top}_n(\mathfrak{S}_w)$. This completes the argument. In §7.2, we will see how these calculations turn out to also have a geometric content when $q$ is a prime power.

**4.5. Extension to all coefficients in $\mathcal{B}$**. Theorem 4.11 shows that a certain coefficient in the basis $\mathcal{B}$ of squarefree monomials can be interpreted in terms of qDS. It is therefore natural to inquire about the coefficients of other squarefree monomials. In this subsection we show that they can also be expressed in terms of qDS.

Let $I$ be a finite subset of $\mathbb{Z}$, and write it uniquely as a union of maximal intervals:

$$I = I_1 \cup I_2 \cup \dots \cup I_k$$

with $I_j = [a_j, b_j]$ and $a_{j+1} - b_j \ge 2$ for $1 \le j < k$. Given $f$ in $\mathbf{k}[z]$, define

$$f^I(\mathbf{x}) = f(z) \left| \begin{array}{l} z_i = 0 \text{ if } i \notin I; \\ z_i = x_{a_j} + \dots + x_i \text{ if } i \in I_j. \end{array} \right. .$$

Note that $f \mapsto f^I$ is an algebra morphism from $\mathbf{k}[z]$ to $\mathbf{k}[x_i, i \in I]$. Define

$$(4.17) \qquad Q_I(\mathbf{x}) := \prod_{j=1}^{k-1} (qx_{b_j+1} - x_{b_j+2}) \times \dots \times (qx_{a_{j+1}-1} - x_{a_{j+1}}).$$

**Example 4.14.** Consider $I = \{1, 3, 4, 5, 9, 10\}$. Then we have $I_1 = \{1\}$, $I_2 = \{3, 4, 5\}$, and $I_3 = \{9, 10\}$. For $f$ any polynomial in the $z$ variables, we obtain $f^I(\mathbf{x})$ by setting $z_1 = x_1$, $z_3 = x_3$, $z_4 = x_3 + x_4$, $z_5 = x_3 + x_4 + x_5$, $z_9 = x_9$, and $z_{10} = x_9 + x_{10}$. Furthermore we have

$$Q_I(\mathbf{x}) = (qx_2 - x_3) \cdot (qx_6 - x_7)(qx_7 - x_8)(qx_8 - x_9).$$

If $I = \{1, \dots, r\}$ and $f = z_1^{c_1} \cdots z_r^{c_r}$, then

$$f^I(\mathbf{x}) = x_1^{c_1} (x_1 + x_2)^{c_2} \cdots (x_1 + \cdots + x_r)^{c_r} = y_{(c_1, \dots, c_r)}.$$

In this case $Q_I(\mathbf{x})$ is the empty product, and so equals 1.

<footnote n="5">⁵The reason is that these Schubert polynomials span a vector space inside all polynomials in $\mathbf{k}[x_n]$ with $\mathrm{deg}(f) = n-1$, which possesses a complementary subspace on which both sides of (4.16) vanish.</footnote>
We are now ready to state the generalization of Theorem 4.11. For this we define $\langle \cdot \rangle_I^q$ to mean the qDS of the argument over the variables $x_i$ for $i \in I$.

**Theorem 4.15.** Let $f$ be a homogeneous degree $d$ polynomial in $z = (z_i)_{i \in \mathbb{Z}}$. Then the coefficient $u_I^*(f)$ of $u_I$ in the expansion

$$ \pi(f) = \sum_{I \subset \mathbb{Z}, |I|=d} u_I^*(f)u_I $$

is given by

$$ (4.18) \qquad u_I^*(f) = \frac{1}{(b_k - a_1 + 1)q!} \langle Q_I(\mathbf{x}) \times f^I(\mathbf{x}) \rangle_{\{a_1, a_1+1, \dots, b_k+1\}}^q $$

We recover qDS in the sense of §4 when $a_1 = 1$ and $b_k = n - 1$. We postpone the proof to the Appendix B, and discuss an important special case.

Consider $f = z_1^{c_1} \cdots z_k^{c_k}$ where $c_i > 0$ for $i \in [k]$. Suppose $|c| = r$. We can naturally think of $c$ as an $N$-vector in $W_r^r$. From equation (4.18), one infers that $u_I^*(f) = 0$ for all $I \subset \mathbb{Z}$ with cardinality $r$ unless $I$ is an interval containing $[k]$. So to express $\pi(f)$ in the basis $\mathcal{B}$ we only need to compute $u_{I_j}^*(f)$ for the $r-k+1$ intervals $I_j := [j, j+r-1]$ for $k+1-r \le j \le 1$. For such intervals, $Q_{I_j}$ equals 1, and

$$ f^{I_j}(\mathbf{x}) = \prod_{1 \le i \le k} (x_j + x_{j+1} + \cdots + x_i)^{c_i}. $$

Now, $u_{I_j}^*(f)$ is obtained by applying qDS to this expression, and we can reindex to get

$$ u_{I_j}^*(f) = \frac{1}{(r)q!} \langle \prod_{0 \le j \le r-k} (x_1 + \cdots + x_{j+1})^{c_1} \cdots (x_1 + \cdots + x_{j+k})^{c_k} \rangle_{[1,n]}, $$

and the right-hand side is readily recognized as $A_{(0^j, c, 0^{r-j-k})}(q) \times \frac{1}{(r)q!}$.

To summarize this discussion, we have that if $c$ is a strong composition of $r$, there holds in $\mathcal{K}$

$$ (4.19) \qquad u_1^{c_1} \cdots u_k^{c_k} = \frac{1}{(r)q!} \sum_{0 \le j \le r-k} A_{(0^j, c, 0^{r-j-k})}(q) u_{[1-j, r-j]} $$

*Remark 4.16.* We have stated this result here to illustrate 4.15, but it can be proved without it. It is indeed a consequence of the interpretation of $A_c(q)$ via Theorem 4.11 together with the shift-invariance of the relations of $\mathcal{K}$.

## 5. REMIXED EULERIAN NUMBERS

In this section we give certain properties of positivity of the numbers $A_c^q$. First we show that when $q$ is a positive real number, these give certain probabilities in a certain diffusion process on $\mathbb{Z}$. We then show that as polynomials in $q$, $A_c^q$ has nonnegative integer coefficients.

A much more in-depth study of these polynomials is given by the authors in [35].
**5.1. A probabilistic process after Diaconis-Fulton.** 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_i c_i < \infty$ as before, which we now visualize as a finite set of particles, where there are $c_i$ particles stacked at site $i$. The configuration $c = (\dots, 0, 3, 0, c_0 = 1, 1, 2, 0, 2, 0, \dots)$ is represented below. Stable configurations are those for which $c_i \le 1$ for all $i$, and are naturally identified with finite subsets of $\mathbb{Z}$ via their support.

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

Given jump probabilities $q_L, q_R \ge 0$ satisfying $q_L + q_R = 1$, we 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 resulting configurations are $L_i(c)$ and $R_i(c)$ respectively, as seen already in this work.

Let us assume here that we perform such a jump every unit of time while the process hasn't stabilized. To specify the process completely, one needs to give a rule (deterministic or probabilistic) on how to pick the site $i$ in case there are several sites with more than one particle. It turns out that for our purposes it will not matter, as we now explain.

Note first that whichever rule is chosen, it is easy to show that the process will end up in a stable configuration with probability 1. We can then define $\mathbb{P}_c(I)$ to be the probability that the process, according to the chosen rules and starting at configuration $c$, ends up in the stable configuration given by the finite subset $I$ of $\mathbb{Z}$. Diaconis and Fulton [11] showed a strong abelian property of this model, namely that $\mathbb{P}_c(I)$ is independent of the chosen rules for picking the jumping particle.

Assume $q_R > 0$ and let $q := q_L/q_R$, so that $q_L = \frac{q}{1+q}$ and $q_R = \frac{1}{1+q}$. We have then the following result:

**Proposition 5.1.** Fix an $\mathbb{N}$-vector $c$. Then we have the following expansion in $\mathcal{K}$ in the basis $\mathcal{B}$:

$$u^c = \sum_{\text{finite } I \subset \mathbb{Z}} \mathbb{P}_c(I) u_I.$$

In particular, if $c \in W_r^r$, then

$$\mathbb{P}_c([r]) = \frac{A_c^q}{(r)_q!}.$$

In this probabilistic interpretation, we recognize Lemma 3.6 as the *gambler's ruin*. Namely, the coefficients on the right hand side compute the left and right exit probabilities of an asymmetric random walker on the integer segment $[a, b]$, starting from $i$.

**Proof of Lemma 5.1.** If $c$ is already stable, there is nothing to show as $u^c = u_{\text{Supp}(c)} \in \mathcal{B}$, and $\mathbb{P}_c(J) = \delta_{J,\text{Supp}(c)}$ for any finite $J \subset \mathbb{Z}$. Otherwise suppose $c_i > 2$ for some $i \in \mathbb{Z}$. We are allowed to pick $i$ to hop because of the abelian property, and then obtain immediately the following transition equation

$$(5.1) \qquad \mathbb{P}_c(I) = q_L \mathbb{P}_{L_i(c)}(I) + q_R \mathbb{P}_{R_i(c)}(I).$$
Now we see that the coefficient $A_c^I$ of $u_I$ in the $\mathcal{B}$-expansion of $u^c$ satisfies the same relation. For a fixed $I$, these relations characterize $A_c^I$ following the proof for remixed Eulerian numbers in the case $I = [r]$, and the proof is complete. $\square$

The obvious parallel between the transition moves in this particle jumping process and the relations defining $\mathcal{K}$ eliminates the element of surprise from our preceding result. Nevertheless, on viewing the result in isolation, it is intriguing that this simple probabilistic process computes $q$-analogues of a discrete-geometric notion — mixed Eulerian numbers in this case. Our next remark frames this particle process in the appropriate context which is the work of Diaconis-Fulton [11].

**Remark 5.2.** The above process is an instance of Diaconis-Fulton's *growth game* [11]. For the case where finitely many particles are dropped on the origin beginning with the origin being the only inhabited site, one obtains $q$-analogues of classical Eulerian numbers (suitably normalized), and this case is also discussed in [32].

A property of remixed Eulerian numbers that will come handy in the sequel is a cyclic sum rule satisfied by remixed Eulerian numbers. In the case $q = 1$, this was established by Postnikov [38] by a geometric argument. It was later reproven by Petrov [37] by a probabilistic argument which we essentially follow here.

To state the rule, we need some notation. For $c = (c_1, \dots, c_r) \in W_r^r$, set $\tilde{c} = (c_1, \dots, c_r, 0)$. Write $c \sim c'$ if $\tilde{c}'$ can be obtained as a cyclic rotation of $\tilde{c}$. This is an equivalence relation on $W_r^r$, and we define $\text{Cyc}(c)$ to be the equivalence class of $c$. For $c = (2, 0, 1)$, $\text{Cyc}(c)$ contains $c$ and $c' = (1, 0, 2)$ since $\tilde{c} = (2, 0, 1, 0) \sim (1, 0, 2, 0) = \tilde{c}'$.

**Proposition 5.3.** For $c \in W_r^r$, we have

$$ \sum_{c' \in \text{Cyc}(c)} A_{c'}(q) = (r)_q!. $$

*Proof.* As this is a polynomial relation, it is enough to prove it when $q$ is a nonnegative real. Consider the same dynamic as above, but on a circular set of sites labeled 1 through $r+1$ clockwise. Fix $c \in W_r^r$ and start the process with the configuration of $c_i$ particles at site $i$ for $1 \le i \le r$, and 0 at site $r+1$. The process stabilizes with probability one and has the abelian property, as it is still an instance of the processes considered in [11].

In a stable configuration, exactly one of the $r+1$ sites will be unoccupied. By rotational symmetry, the probability $P_j$ of ending at the stable configuration supported on $[r+1] \setminus \{j\}$ is equal to the probability of reaching the stable configuration supported on $[r]$ but starting from the configuration $c$ rotated counterclockwise $j$ times. Clearly $P_j$ is 0 if $c_j > 0$. If not, the rotated configuration has support in $[r]$ and so corresponds naturally to an element $c'$ in $\text{Cyc}(c)$. The probability $P_j$ in this case is given by $\mathbb{P}_{c'}([r])$ introduced above, since the process behaves exactly as on $\mathbb{Z}$.

The preceding argument together with Proposition 5.1 gives

$$ (5.2) \qquad \sum_{c' \in \text{Cyc}(c)} \frac{A_{c'}(q)}{(r)_q!} = 1, $$

which is what we set out to prove. $\square$
Continuing our example above, we get the following relation which can be checked from the data in Example 4.9

$$A_{(2,0,1)}(q) + A_{(1,0,2)}(q) = (3)_q!$$

A particularly interesting case of Proposition 5.3 is when $Supp(c)$ is an interval. Indeed, the cyclic rotations do not matter and the sum in question only runs over linear shifts of $c$, and only those sequences contribute to the sum whose support lies in $[r]$. We have already encountered this in the discussion right after Theorem 4.15, and we address this further in §§5.3 particularly as it has ramifications when we discuss Schubert polynomials.

## 5.2. Positivity of coefficients.
In the rest of this section we consider $A_c(q)$ as a polynomial.

Definition 4.5 implies immediately that $A_c(q) \in \mathbb{Z}[q]$. We know also that for $q = 1$, we have $A_c := A_c(1)$ is the mixed Eulerian number [38]. It is positive, for instance by its original interpretation as a mixed volume. More generally, for $q > 0$ we now know that $A_c(q) > 0$ because of the probabilistic interpretation from Proposition 5.1.

What is not obvious from its definition, or even from the relations (4.13), is that the coefficients of $A_c(q) \in \mathbb{Z}[q]$ are actually nonnegative; indeed the presence of the factor $(b-a+2)_q$ prevents us from concluding so immediately.

**Proposition 5.4.** For any $c = (c_1, \dots, c_r)$ such that $|c| = r$, we have $A_c(q) \in \mathbb{N}[q]$.

*Proof.* Let $I_1 \sqcup I_2 \sqcup \dots \sqcup I_k$ denote the maximal interval decomposition of $Supp(c)$, and suppose that $m_j := |I_j|$ for $1 \le j \le k$. Define

$$\tilde{A}_c(q) := A_c(q) / \prod_i (m_i)_q!$$

We will prove the stronger claim that $\tilde{A}_c(q) \in \mathbb{N}[q]$, which of course implies the proposition since the $q$-factorials have nonnegative coefficients. Suppose first that $c_i \le 1$ for all $i$. The only possibility is $c = (1^r)$ in which case $\tilde{A}_c(q) = A_c(q)/(r)_q! = 1$ by Theorem 4.8.

Now consider $i$ such that $c_i \ge 2$, and suppose it belongs to the maximal interval $I_j = [a, b]$. Note that $m_j + 1 = b - a + 2$. Now note that (4.13) says

$$(5.3) \qquad (m_j + 1)_q A_c(q) = q^{i-a+1} (b-i+1)_q A_{L_i(c)}(q) + (i-a+1)_q A_{R_i(c)}(q),$$

where $L_i(c)$ and $R_i(c)$ are defined as in the proof of Theorem 4.8. By dividing both sides of this equation by $(m_j + 1)_q \prod_{1 \le p \le k} (m_p)_q!$, we obtain

$$(5.4) \qquad \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).$$

Here $b_L$ and $b_R$ are determined by how $Supp(L_i(c))$, $Supp(R_i(c))$ and $Supp(c)$ are related, and we perform this analysis next.

If $a = 1$, then $L_i(c)$ is not defined and the corresponding term is omitted. If $a = 2$ or $c_{a-2} = 0$, then the maximal interval decomposition of $Supp(L_i(c))$ is obtained by replacing $I_j$ by $\{a-1\} \cup I_j$. Note that the cardinality of the latter is $m_j + 1$, and therefore we infer that $b_L = 1$. If we are not in either of the preceding two scenarios, then we have $I_{j-1} = [f, a-2]$ for some $f \ge 1$, so that $[f, b]$ is a maximal interval in the support of $L_i(c)$. In this case, we have $b_L = \binom{b-f+1}{b-a+2}_q$.

Symmetrically, if $b = 1$, then $R_i(c)$ is not defined and the corresponding term is omitted. If $b = r-1$ or $c_{b+2} = 0$, then $b_R = 1$. Otherwise we have $I_{j+1} = [b+2, g]$ for some $g \le r$, so that $[a, g]$ is a maximal interval in $Supp(R_i(c))$. In this case, we have $b_R = \binom{g-a+1}{b-a+2}_q$.
Thus equation (5.4) gives a recurrence for $\tilde{A}_c(q)$ which clearly shows that it has nonnegative coefficients. $\square$

The cyclic sum rule for remixed Eulerians descends to one for the reduced analogues.

**Corollary 5.5.** Fix $c \in W_r^r$. Suppose $\text{Supp}(c)$ decomposes as a disjoint union of (inclusion) maximal intervals as $I_1 \sqcup \cdots \sqcup I_k$. Set $m_j = |I_j|$.

$$ \sum_{c' \in \text{Cyc}(c)} \tilde{A}_{c'}(q) = \frac{(n-1)q!}{\prod_{1 \le j \le k} (m_j)_{q}!} $$

**5.3. Connected remixed Eulerian numbers.** We now return to the case where $c$ is an $\mathbb{N}$-vector such that $\text{Supp}(c)$ is an interval in $\mathbb{Z}$. Our result here is an alternative encoding of the coefficients in the expansion in equation (4.19). In fact, what we obtain is a $q$-analogue of a recent result of Berget-Spink-Tseng [5, Theorem A.1] in their investigation of log-concavity of matroid $h$-vectors.

**Proposition 5.6.** Let $c = (c_1, \dots, c_k) \models r$. We have

$$ (5.5) \qquad \sum_{m \ge 0} t^m \prod_{i=1}^k (m+i)_{q}^{c_i} = \frac{\sum_{i=0}^{r-k} A_{0^i c_0^{r-k-i}}(q) t^i}{(t;q)_{r+1}}. $$

*Proof.* Fix $m \ge 0$. Using the shift invariance of the relations defining $\mathcal{K}$, we can expand $u_{m+1}^{c_1} \cdots u_{m+k}^{c_k} = \tau^m(u_1^{c_1} \cdots u_k^{c_k})$ in the basis $\mathcal{B}$ of $\mathcal{K}$ by shifting indices on the right-hand side in equation (4.19). We thus obtain

$$ (5.6) \qquad (r)_q! u_{m+1}^{c_1} \cdots u_{m+k}^{c_k} = \sum_{j=0}^{r-k} A_{0^j c_0^{r-j-k}}(q) u_{[1,r]+(m-j)}. $$

Via the specialization $\text{sp}: u_i \mapsto (i)_q$ for $i > 0$, see 3.11, we obtain the polynomial identity

$$ (m+1)_q^{c_1} \cdots (m+k)_q^{c_k} = \sum_{j=0}^{\min(m,r-k)} A_{0^j c_0^{r-k-j}}(q) \binom{r+m-j}{m-j}_q. $$

By Cauchy's $q$-binomial theorem (2.4), the right-hand side is the coefficient of $t^m$ in $\frac{\sum_{i=0}^{r-k} A_{0^i c_0^{r-k-i}}(q) t^i}{(t;q)_n}$, which completes the proof. $\square$

We briefly touch upon various instances of connected remixed Eulerian numbers in disguise in literature. As elaborated in [19, §3], given positive integers $p_1$ through $p_m$, MacMahon considered the maj-des distribution over the set of permutations $M_{(p_1, \dots, p_m)}$ of the multiset $\{1^{p_1}, \dots, m^{p_m}\}$. Suppose $r = p_1 + \cdots + p_m$. MacMahon showed [19, Eq. (3.3)] that

$$ (5.7) \qquad \sum_{n \ge 0} t^n \prod_{1 \le i \le m} \binom{n+p_i}{p_i}_q = \frac{\sum_{\pi \in M_{(p_1, \dots, p_m)}} t^{\text{des}(\pi)} q^{\text{maj}(\pi)}}{(t;q)_{r+1}}. $$
By setting $c_i := |\{j | p_j \ge i\}|$ and $k := \max\{p_1, \dots, p_m\}$, one can rewrite this as

$$ (5.8) \qquad \sum_{n \ge 0} t^n \prod_{1 \le i \le k} (n+i)_q^{c_i} = \frac{\prod_{1 \le i \le m} (p_i)_q! \left( \sum_{\pi \in M_{(p_1, \dots, p_m)}} t^{\mathrm{des}(\pi)} q^{\mathrm{maj}(\pi)} \right)}{(t; q)_{r+1}} $$

Note that we must have $c_1 \ge c_2 \ge \dots \ge c_k > 0$. Also given any such partition $(c_1, \dots, c_k)$, one can always associate a corresponding $(p_1, \dots, p_m)$. Thus we see that for partitions $c = (c_1, \dots, c_k)$, the polynomial $A_{0^i c_0 r^{k-i}}(q)$ tracks the distribution of major index over $\pi \in M_{(p_1, \dots, p_m)}$ where $\mathrm{des}(\pi) = i$, up to scaling by $\prod_{1 \le i \le m} (p_i)_q!$. The case where $p_i = 1$ for all $1 \le i \le m$ is particularly well known. In this case $c = (r)$ and one obtains

$$ (5.9) \qquad A_{(0^i, r, 0^{r-k-i})}(q) = \sum_{\substack{\pi \in S_r \\ \mathrm{des}(\pi)=i}} q^{\mathrm{maj}(\pi)}, $$

and the right-hand side gives the $q$-Eulerian number of Carlitz [8].

More generally, the connected remixed Eulerian numbers appear in the work of Garsia–Remmel [18] as $q$-hit polynomials. Indeed, Equations I.11 and I.12 in loc. cit. together imply that the $A_{0^i c_0 r^{k-i}}(q)$ are $q$-hit polynomials (up to a power of $q$) of certain Ferrers boards determined by $c$. Informally, this is how the correspondence goes. Consider any Dyck path from $(0,0)$ to $(r, r)$ such that its area sequence has $c_i$ instances of $i$ for $i \in [r]$. Then it must be the case that $\mathrm{Supp}(c)$ is an interval in $[r]$. Such a Dyck path in turn determines a Ferrers diagram $\lambda(c)$, and computing the $q$-hit polynomial as a weighted sum over all nonattacking placements in the $r \times r$ board where $i$ rooks land inside $\lambda(c)$ gives $A_{0^i c_0 r^{k-i}}(q)$. We address this connection in more detail in [35].

## 6. SPECIALIZATIONS OF QUASISYMMETRIC POLYNOMIALS

We now aim to give the expansion of $\rho_+(P) = P(u_1, u_2 - u_1, u_3 - u_2, \dots)$ in the basis $B_+$ for any quasisymmetric polynomial $P(x_1, \dots, x_m)$. Amongst other things, this will shed a new light on the main results of the authors in [33] for $q = 1$. It helps to consider the case of monomials first.

**6.1. Expansion of monomials in $u_i - u_{i-1}$**. Consider the expansion of $\rho(\mathbf{x}^c) = \prod_i (u_i - u_{i-1})^{c_i}$ for $c$ any $\mathbb{N}$-vector:

$$ (6.1) \qquad \prod_i (u_i - u_{i-1})^{c_i} = \sum_I \psi_I^c u_I. $$

We use Theorem 4.15 to find a formula for the coefficients $\psi_I^c$. Assume $|I| = |c|$, otherwise $\psi_I^c = 0$ for degree reasons. Let $I_1 \sqcup I_2 \sqcup \dots \sqcup I_k$ be the maximal interval decomposition of $I$, with $I_j = [a_j, b_j]$. We then introduce $\tilde{I} := \tilde{I}_1 \sqcup \tilde{I}_2 \sqcup \dots \sqcup \tilde{I}_k$ where $\tilde{I}_j = [a_j, b_j + 1]$ for all $j$.

Arguing as in the proof of Theorem 4.15, we have that $\psi_I^c = 0$ unless $\mathrm{Supp}(c) \subseteq \tilde{I}$.

**Proposition 6.1.** Let $c, I$ satisfy $\mathrm{Supp}(c) \subseteq \tilde{I}$ and $\sum_{i \in \tilde{I}_j} c_i = |I_j|$ for $j = 1, \dots, k$. Then

$$ (6.2) \qquad \psi_I^c = \prod_{1 \le j \le k} \frac{1}{(|I_j|)_q!} \langle x_{a_j}^{c_{a_j}} x_{a_{j+1}}^{c_{a_{j+1}}} \cdots x_{b_j}^{c_{b_j}} x_{b_{j+1}}^{c_{b_{j+1}}} \rangle^{q} \{a_j, \dots, b_j+1\}. $$
Note that all terms in the product can be calculated by Proposition 4.3. If $\sum_{i \in \tilde{I}_j} c_i = |I_j|$ fails for a certain $j$, then $\psi_I^c = 0$.

We now restrict to the case where $\text{Supp}(c)$ is an interval. The reason for this will become clear soon. Without loss of generality we may assume that $\text{Supp}(c) = [k]$ for some positive integer $k$, and suppose $|c| = r$.

By the analysis above, the only nonzero coefficients $\psi_I^c$ occur when $\tilde{I}$ is an interval containing $[k]$. A direct analysis reveals the following two scenarios are the only possible ones:

(1) $\tilde{I} = \tilde{I}_1$ is an interval of length $r+1$ containing $[k]$. Write $I = [1, r] - a$ for some $0 \le a \le r - k + 1$. Then we immediately get from (6.2) that

$$ (6.3) \qquad (r)_q! \psi_I^c = \langle \mathbf{x}^c \rangle_{[1,1+r]-a}^q $$

(2) $\tilde{I} = \tilde{I}_1 \sqcup \tilde{I}_2$ with $\tilde{I}_1 = [i - L_i, i]$ and $\tilde{I}_2 = [i + 1, i + 1 + R_i]$ for a certain $i \in [1, k-1]$, where $L_i = \sum_{j \le i} c_j$ and $R_i = \sum_{j > i} c_j$. Now (6.2) says

$$ (6.4) \qquad (r)_q! \psi_I^c = \binom{r+1}{L_i+1}_q \langle x_1^{c_1} \cdots x_i^{c_i} \rangle_{[i-L_i,i]}^q \langle x_{i+1}^{c_{i+1}} \cdots x_k^{c_k} \rangle_{[i+1,i+1+R_i]}^q $$

which can be easily evaluated.

**6.2. qDS of fundamental quasisymmetric polynomials.** In this section we will determine $\langle F_\alpha(x_1, \dots, x_m) \rangle_n^q$ for $\alpha$ a strong composition of $r$ and $m \le n$. The case $q=1$ was one of the main results of [33]; see Remark 6.4 below.

Recall that $N(\alpha) = \sum_{1 \le i \le \ell(\alpha)} (i-1)\alpha_i$.

**Theorem 6.2.** Let $\alpha \vdash r$, and let $m \ge \ell(\alpha)$. We have that in $K_+$,

$$ (6.5) \qquad \rho_+(F_\alpha(x_1, \dots, x_m)) = \frac{q^{N(\alpha)}}{(r)_q!} u_{[1,r]+m-\ell(\alpha)}. $$

In words, the expansion of $F_\alpha(u_1, u_2 - u_1, \dots, u_m - u_1)$ in the basis $B_+$ of $K_+$ consists of the single term $\frac{q^{N(\alpha)}}{(r)_q!} u_{[1,r]+m-\ell(\alpha)}$. Let us point out that the complete expansion in $K$ has many more terms in general. It can be described explicitly, but we will not need it here.

*Proof.* Let $k := \ell(\alpha)$. We will prove the claim by induction on $m-k$.

If $m=k$, then $F_\alpha(x_1, \dots, x_k)$ is the monomial $x^\alpha$. As $\alpha$ is a strong composition, $\text{Supp}(\alpha)$ is connected and so the expansion of $\rho(x^\alpha) = (u_1 - u_0)^{\alpha_1} \dots (u_r - u_{r-1})^{\alpha_k}$ in the $B$ basis is given by (6.3) and (6.4). To get the expansion for $\rho_+(x^\alpha)$, we retain the basis elements in $B_+$. Only $u_{[r]}$ survives, corresponding to the case $a=0$ in (6.3), so that it comes with the coefficient $\psi_{[r]}^\alpha = \langle \mathbf{x}^c \rangle_{r+1}^q / (r)_q!$. Now $\langle \mathbf{x}^c \rangle_{r+1}^q$ equals $q^{N(\alpha)}$ by Proposition 4.3 as wanted. The claim is true for $m=k$.

So we turn our attention to the case $m > k$. Observe the following well-known recursion:

$$ F_{\alpha}(x_1, \dots, x_m) = \begin{cases} F_{(\alpha_1, \dots, \alpha_k)}(x_1, \dots, x_{m-1}) + x_m F_{(\alpha_1, \dots, \alpha_{k-1}, \alpha_k)}(x_1, \dots, x_m) & \alpha_k > 1, \\ F_{(\alpha_1, \dots, \alpha_k)}(x_1, \dots, x_{m-1}) + x_m F_{(\alpha_1, \dots, \alpha_{k-1})}(x_1, \dots, x_{m-1}) & \alpha_k = 1. \end{cases} $$

We induct on $m+|\alpha|$. Let $\alpha'$ denote the composition $(\alpha_1, \dots, \alpha_k - 1)$ when $\alpha_k > 1$ and $(\alpha_1, \dots, \alpha_{k-1})$ if $\alpha_k = 1$. In either case, applying $\rho_+$ to the recursion above, and using the inductive hypothesis
gives

$$ (6.6) \qquad \rho_+((r)_q!F_\alpha(x_1, \dots, x_m)) = q^{N(\alpha)}u_{[1,r]+m-k-1} + q^{N(\alpha')}(r)_q x_m u_{[1,r-1]+m-k}, $$

which by Corollary 3.7 becomes

$$ (6.7) \qquad \rho_+((r)_q!F_\alpha(x_1, \dots, x_m)) = q^{N(\alpha)}u_{[1,r]+m-k-1} + q^{N(\alpha')}q^{k-1}(u_{[1,r]+m-k} - u_{[1,r]+m-k-1}). $$

The inductive step is completed by noting that $q^{k-1}q^{N(\alpha')} = q^{N(\alpha)}$.

□

We obtain the following consequence generalizing [33, Theorem 1.1] which is the case $q = 1$.

**Corollary 6.3.** Let $\alpha \models n - 1$, and let $\ell(\alpha) \le m \le n$. Then we have

$$ \langle F_{\alpha}(x_1, \dots, x_m) \rangle_n^q = \begin{cases} q^{N(\alpha)} & \text{if } m = \ell(\alpha); \\ 0 & \text{otherwise.} \end{cases} $$

In particular, for $f$ any quasisymmetric function of degree $n-1$, we have

$$ (6.8) \qquad \sum_{j \ge 1} f(1, q, \dots, q^{j-1}) t^j = \frac{\sum_m t^m \langle f(x_1, \dots, x_m) \rangle_n^q}{(t; q)_n}. $$

*Proof.* By Theorem 4.11, we know that $\langle F_\alpha(x_1, \dots, x_m) \rangle_n^q$ equals $(r)_q!$ times the coefficient of $u_{[r]}$ in $\rho_+(F_\alpha(x_1, \dots, x_m))$. The first claim of Corollary 6.3 then follows immediately from Theorem 6.2. Now let $f = F_\alpha$ and pick $j \ge \ell(\alpha)$. The specialization sp : $i \mapsto (i)_q$ in Theorem 6.2 gives immediately

$$ (6.9) \qquad F_{\alpha}(1, q, \dots, q^{j-1}) = q^{N(\alpha)} \binom{j - \ell(\alpha) + r}{r}_{q}. $$

Multiplying by $t^j$ and summing over all $j$, and then appealing to (2.3), we get

$$ (6.10) \qquad \sum_{j \ge 1} F_{\alpha}(1, q, \dots, q^{j-1}) t^j = \frac{t^{\ell(\alpha)} q^{N(\alpha)}}{(t; q)_n}. $$

This last formula is well-known in the theory of quasisymmetric functions and $(P, \omega)$-partitions, cf. [19, Eq. (2.1)] of which it is a special case. The right-hand side is clearly $\frac{t^{\ell(\alpha)} \langle F_\alpha(x_1, \dots, x_{\ell(\alpha)}) \rangle_n^q}{(t; q)_n}$. Linearity implies the claim for general $f$. □

**Remark 6.4.** The reader should compare our proof of Corollary 6.3 with the proof in the case $q = 1$ [33, Proposition 4.1]. The latter relies upon the (slightly involved) exact computation of the divided symmetrization of monomial quasisymmetric polynomials. It turns out that the qDS of monomial quasisymmetric polynomials is not as nice or easy. We do not currently know of ways to arrive at Corollary 6.3 outside of the one that we employ — identify (and subsequently leverage) the link between qDS and coefficient extraction in the Klyachko algebra.

**Remark 6.5.** For a large class of quasisymmetric functions arising ‘naturally’ as quasisymmetric functions of posets in the theory of P-partitions, our previous result allows us to assign a combinatorial meaning to their qDS generalizing that in [33, §4.3].
6.3. **The work of Aval–Bergeron–Bergeron.** Recall that $\mathrm{QSym}_n^+ \subset \mathbf{k}[\mathbf{x}_n]$ is the ideal generated by quasisymmetric polynomials without constant term. We claim that $\langle f \rangle_n^q$ is equal to 0 if $f \in \mathrm{QSym}_n^+$ has degree $n-1$. In fact we have the following stronger statement.

**Corollary 6.6.** For any polynomial $f$ in $\mathrm{QSym}_n^+$, we have

$$ \rho_n(f) = 0. $$

In particular, if $f$ has degree $n-1$ then $\langle f \rangle_n^q = 0$.

*Proof.* Since $\rho_n$ is an algebra morphism, it suffices to verify this for a quasisymmetric polynomial $f$, and even for $f = F_\alpha(x_1, \dots, x_n)$ for some nonempty strong composition $\alpha$. Setting $m = n$ in the statement of Theorem 6.2 immediately implies the first claim. The second claim then follows immediately from Theorem 4.11. $\square$

Since $\rho_n$ vanishes on $\mathrm{QSym}_n^+$, one is naturally led to consider the quotient $\mathbb{Q}[\mathbf{x}_n]/\mathrm{QSym}_n^+$. A monomial basis for this quotient was computed in Aval–Bergeron–Bergeron [4, Theorem 4.1] and fortunately it fits nicely in our context.

Consider the set

$$ \mathcal{A}_n = \{(c_1, \dots, c_n) \mid \sum_{i \le j \le n} c_j \le n - i \text{ for all } 1 \le i \le n\}. $$

Let $L_n = \mathrm{Vect}(\mathbf{x}^c | c \in \mathcal{A}_n)$ be the linear span of the corresponding monomials. For instance, if $n=3$, then $\mathcal{A}_3 = \{(0,0,0), (1,0,0), (0,1,0), (1,1,0), (2,0,0)\}$ and therefore $\{1, x_1, x_2, x_1x_2, x_1^2\}$ is a basis for $L_3$. The results in [4] imply the vector space decomposition

$$ (6.11) \qquad \mathbb{Q}[\mathbf{x}_n] = L_n \oplus \mathrm{QSym}_n^+. $$

**Theorem 6.7.** If $f \in \mathbf{k}[\mathbf{x}_n]$, homogeneous of degree $n-1$, is written $f = g + h$ with $g \in L_n$ and $h \in \mathrm{QSym}_n^+$, then

$$ \langle f \rangle_n^q = g(1, q, q^2, \dots, q^{n-1}). $$

*Proof.* Let $g$ and $h$ be as in the statement of the theorem. We have that $\langle h \rangle_n^q = 0$ by Corollary 6.6. So we consider $\langle g \rangle_n^q$. By linearity it suffices to consider $\langle \mathbf{x}^c \rangle_n^q$ for $c \in \mathcal{A}_n$ satisfying $|c| = n-1$. We use Proposition 4.3. Note that $\sum_{1 \le j \le n} c_i \ge i$ for $i \in [n]$, which means that the Lukasiewicz path $P_c$ drops below the $x$-axis only in its final step, and thus the descent set $S_c$ is empty. It follows that

$$ (6.12) \qquad \langle \mathbf{x}^c \rangle_n^q = q^{N(c)} = q^{\sum_{1 \le i \le n} (i-1)c_i}. $$

The claim now follows. $\square$

In words, qDS on the degree $n-1$ component of $\mathbf{k}[x_1, \dots, x_n]$ may be obtained by first projecting to the first factor in (6.11) and then computing the principal specialization (sending $x_i$ to $q^{i-1}$) of the resulting polynomial.

**Example 6.8.** From Example 4.4, we know $\langle x_1x_3 \rangle_3^q = -(1+q)$. We can arrive at the same result differently by noting that

$$ x_1x_3 = x_1(x_1 + x_2 + x_3) - (x_1^2 + x_1x_2). $$

Since $x_1x_2 + x_1^2 \in L_3$ and $x_1(x_1+x_2+x_3) \in \mathrm{QSym}_3^+$ Theorem 6.7 tells us that $\langle x_1x_3 \rangle_3^q = g(1, q, q^2)$ where $g = -x_1x_2 - x_1^2$.
We close this subsection by recording a corollary that naturally leads us to looking at the coinvariant algebra closely.

**Corollary 6.9.** The map $\rho$ induces a morphism from the coinvariant algebra $k[\mathbf{x}_n]/\mathrm{Sym}_n^+$ to $\mathcal{K}_n$.

*Proof.* Since $\mathrm{Sym}_n^+ \subset \mathrm{QSym}_n^+$, and $\rho_n$ vanishes on $\mathrm{QSym}_n^+$ by Corollary 6.6, the claim follows. $\square$

This morphism for $q = 1$ coincides with the pullback homomorphism $t^*$ between the cohomology ring of the flag variety and the $\mathbb{S}_n$-invariant part of the cohomology ring of the permutahedral variety, as detailed in the introduction. A geometric interpretation for generic $q$, or any other value of $q$, is not known to the authors.

## 7. KLYACHKO–MACDONALD IDENTITY AND CHOW CLASS OF A DELIGNE–LUSZTIG VARIETY

We are now ready to return to our primary motivation mentioned in the introduction, which was to understand the relationship between the two following formulas for $w \in \mathbb{S}_n$ of length $\ell$, and $\mathcal{S}_w$ is the corresponding Schubert polynomial (cf. §§2.4).

$$ (7.1) \qquad \mathcal{S}_w(u_1, u_2 - u_1, \dots, u_\ell) = \frac{1}{\ell!} \sum_{a \in \mathrm{Red}(w)} u_{a_1} u_{a_2} \cdots u_{a_\ell} \quad \text{in } \mathcal{K}_n^1 \simeq H^*(\mathrm{Perm}_n, \mathbb{Q})^{\mathcal{S}_n}. $$

$$ (7.2) \qquad \mathcal{S}_w(1, \dots, 1) = \frac{1}{\ell!} \sum_{a \in \mathrm{Red}(w)} a_1 a_2 \cdots a_\ell. $$

The first identity is Klyachko's identity (for type A) first stated in [24] and proved in [25]; since the latter is in Russian, the authors included a slightly simplified version of the proof in [34, §8]. The second identity is Macdonald's reduced word identity [30].

Before we deal with the $q$-version and prove Theorem 1.4 which encompasses both identities, let us explain that it is possible to deduce (7.2) from (7.1). It is not as straightforward as specializing $u_i \mapsto 1$ in (7.1), since the identity holds in $\mathcal{K}_n^1$ and not in $\mathcal{K}^1$ or $\mathcal{K}_+^1$, cf. §3.4. In fact both sides in (7.1) vanish for $\ell \ge n$ since the top graded dimension of $\mathcal{K}_n^1$ is $n-1$. It should not come as a surprise since Klyachko's identity actually holds for any representative of the Schubert classes. Now Schubert polynomials have the important stability property under the inclusions $\mathbb{S}_n \subseteq \mathbb{S}_{n+1}$, and are thus defined for $w \in \mathbb{S}_\infty$. So pick $w \in \mathbb{S}_\infty$, and let $n_0$ be such that $w \in \mathbb{S}_{n_0}$. Then (7.1) is valid for all $n \ge n_0$, and thus holds in $\mathcal{K}_+^1$. The specialization $u_i \mapsto 1$ is now possible and thus we obtain (7.2).

The methodology of proof of (7.1) cannot be simply extended to the $q$-case: it is based on the theory of root systems, and it is not clear how the parameter $q$ fits into this story. Also the inductive nature of this proof does not mix well with the comaj statistic. We will instead prove Theorem 1.4 using the Fomin–Stanley approach to the $q$-Macdonald identity. The subsequent remainder of this section involves applications to certain coefficients $a_w(q)$ related to a particular Deligne–Lusztig variety.

### 7.1. A $q$-Klyachko–Macdonald identity.
We define the *NilCoxeter algebra* $\mathcal{NC}_n$ as the free associative algebra over $\mathbb{C}$ generated by $v_1, \dots, v_{n-1}$ subject to $v_i^2 = 0$, $v_iv_j = v_jv_i$ for $|i-j| \ge 2$ and $v_iv_{i+1}v_i = v_{i+1}v_iv_{i+1}$ for $1 \le i \le n-2$. Given these relations, it follows that $\mathcal{NC}_n$ has a linear basis consisting of elements $v_w$ indexed by $w \in \mathbb{S}_n$. The *NilCoxeter algebra* plays a crucial role in Fomin and Stanley's proof of the $q$-analogue of Macdonald's reduced word identity [15]. As we
demonstrate next, we are able to adapt their proof<fnref n="6" /> to incorporate the Klyachko algebra in the setup.

Let $\mathfrak{S}_w(x_1, \dots, x_{n-1})$ be the Schubert polynomial associated with $w \in S_n$. Let $\mathfrak{S}_n$ be defined by

$$ \mathfrak{S}_n(x_1, \dots, x_{n-1}) = \sum_{w \in S_n} \mathfrak{S}_w v_w \quad \in \mathbb{Q}[x_1, \dots, x_{n-1}] \otimes NC_n. $$

For $i = 1, \dots, n-1$, define $h_i(x) = 1 + xv_i$ where $x$ is any parameter. Following [15, §2], we have the equality

$$ (7.3) \qquad \mathfrak{S}_n(x_1, \dots, x_{n-1}) = \prod_{i=1}^{n-1} \prod_{j=n-1}^{i} h_j(x_i), $$

which is in fact equivalent to the Billey–Jockusch–Stanley formula [7]. Since the $v_i$ do not commute, we emphasize how to interpret the product on the right hand side. The inner product is multiplied from left to right, whereas the order is immaterial as far as the outer product is concerned. For instance, here is $\mathfrak{S}_3(x_1, x_2)$.

$$ \mathfrak{S}_3(x_1, x_2) = (h_2(x_1)h_1(x_1)) \cdot h_2(x_2) = (1 + x_1v_2)(1 + x_1v_1) \cdot (1 + x_2v_2) $$

Using the fact that $h_i(x)h_j(y) = h_j(y)h_i(x)$ for $j - i \ge 2$ [15, Lemma 3.1 (i)], we may rewrite (7.3) as

$$ (7.4) \qquad \mathfrak{S}_n(x_1, \dots, x_{n-1}) = \mathfrak{S}_{n-1}(x_1, \dots, x_{n-2})|_{v_j \mapsto v_{j+1}} \prod_{i=1}^{n-1} h_i(x_i), $$

where the terms in the product on the right-hand side are multiplied from left to right. So, for instance

$$ \mathfrak{S}_4(x_1, x_2, x_3) = \mathfrak{S}_3(x_1, x_2)|_{v_j \mapsto v_{j+1}} h_1(x_1)h_2(x_2)h_3(x_3). $$

The result in Theorem 7.2 is central to this section. The reader should compare it to [15, Lemma 5.3] as it foreshadows our application of principal specialization to the statement below. To establish this result, we will need the following lemma:

**Lemma 7.1** (‘Yang-Baxter relation’). Let $\mathcal{A}$ be a commutative algebra and $a, b, c$ three elements in $\mathcal{A}$ that satisfy $c(a + c - b) = 0$. Then for any $i = 1, \dots, n-2$, we have in $\mathcal{A} \otimes NC_n$

$$ (7.5) \qquad h_i(a)h_{i+1}(b)h_i(c) = h_{i+1}(c)h_i(a+c)h_{i+1}(b-c). $$

*Proof.* We can pick $i=1$ without loss of generality. By expanding the expressions on both sides, we must compare the coefficients of $v_w$ for all 6 elements of $S_3$. These are easily checked to coincide in all cases, using the assumed relation $c(a + c - b) = 0$. $\square$

If $\mathcal{A}$ is an integral domain, then either $c = 0$ in which case (7.5) is trivial, or $c = a + b$ and then this becomes precisely the case used in [15].

<footnote n="6">⁶As a warning to the reader, Fomin and Stanley use $u$-variables to denote the generators for the NilCoxeter algebra. We use $v$ instead since the $u$-variables are the generators for $\mathcal{K}$.</footnote>
**Theorem 7.2.** In $K_+ \otimes NC_n$, there holds:

$$ (7.6) \qquad \mathfrak{S}_n(u_1, u_2 - u_1, \dots, u_{n-1} - u_{n-2}) = \prod_{k=\infty}^{1} \prod_{j=n-1}^{1} h_j (q^{k-1}(1-q)u_j). $$

For any $w \in S_n$ one has the identity in $K_+$

$$ (7.7) \qquad \mathfrak{S}_w(u_1, u_2 - u_1, u_3 - u_2, \dots) = \frac{1}{(\ell)_q!} \sum_{\mathbf{a} \in \mathrm{Red}(w)} q^{\mathrm{comaj}(\mathbf{a})} u_{a_1} u_{a_2} \cdots u_{a_\ell}, $$

where $\ell$ is the length of $w$.

These identities do not hold in $K$. Consider $\mathfrak{S}_{231} = x_1x_2$. The left hand side has a term $-u_{\{0,2\}}$ while the right hand side does not.

Applying the specialization sp to (7.7) gives the $q$-Macdonald reduced word identity:

**Corollary 7.3.**

$$ (7.8) \qquad \mathfrak{S}_w(1, q, q^2, \dots) = \frac{1}{(\ell)_q!} \sum_{\mathbf{a} \in \mathrm{Red}(w)} q^{\mathrm{comaj}(\mathbf{a})} (a_1)_q (a_2)_q \cdots (a_\ell)_q. $$

**7.2. Chow classes of Deligne–Lusztig varieties.** We just saw that Theorem 7.2 lifts the $q$-Macdonald reduced word identity to the algebra $K$.

Here we will see another application of Theorem 7.2: when $q$ is a prime power, it gives a positive formula for the coefficients in Schubert cycle expansion of the class of a certain Deligne–Lusztig variety. This is a positive characteristic analogue of one of the key observations of [34].

Deligne–Lusztig varieties were introduced by the eponymous authors in the seminal article [9]. These are fundamental subvarieties of the generalized flag varieties over a finite field, introduced to describe the representation theory of finite groups of Lie type; see [13]. In [23], Kim studies classes of Deligne–Lusztig varieties in the Chow ring of the flag variety, namely the coinvariant ring $R_n = \mathbb{Q}[\mathbf{x}_n]/\mathrm{Sym}_n^+$.

Here we only focus on type A, in the split case. Let us briefly explain Deligne–Lusztig varieties in this case for completeness. Let $q$ be a prime power, $\mathbb{F}_q$ denotes the finite field with $q$ elements and $\overline{\mathbb{F}}_q$ an algebraic closure of it. Denote by Frob: $x \mapsto x^q$ the Frobenius map on $\overline{\mathbb{F}}_q$, whose fixed points form $\mathbb{F}_q$. Consider the general linear group $G = GL_n(\overline{\mathbb{F}}_q)$. Now Frob acts on $G$ by $(a_{ij}) \mapsto (a_{ij}^q)$ so that it has as fixed points $G^F = GL_n(\mathbb{F}_q)$. Let $B \subset G$ be the subgroup of upper triangular matrices and $G/B$ be the flag variety, identified as the set of complete flags $(F_i)_{i=0}^n$ in $\mathbb{F}_q^n$. Let $\sigma \in S_n$. The Deligne–Lusztig variety $X(\sigma)$ is defined as the set of flags $\mathcal{F} = (F_i)_i$ such that $\mathcal{F}$ and Frob($\mathcal{F}$) are in relative position $\sigma$. One way to express this last condition is that there exists a basis $(e_i)_i$ of $\mathbb{F}_q^n$ adapted to the flag $\mathcal{F}$ (that is, $(e_1, \dots, e_k)$ is a basis of $F_k$ for any $k$) such that $(e_{\sigma(i)})_i$ is adapted to Frob($\mathcal{F}$). Note that $X(\sigma)$ has a natural structure of smooth projective variety.

In the article [23], D. Kim gives an expression for the Chow class of any Deligne–Lusztig variety (in any type) in terms of Schubert intersection numbers. Let us state the result of interest here, which concerns the standard Deligne–Lusztig variety $\mathrm{Cox}_n = X(\sigma_n)$ with $\sigma_n = s_1s_2\dots s_{n-1}$ the long cycle $(1, 2, \dots, n)$. The variety $\mathrm{Cox}_n$ is sometimes called the *Coxeter variety* [13, §6]. We decompose its Chow class $[\mathrm{Cox}_n]$ as an element of $R_n$:

$$ [\mathrm{Cox}_n] = \sum_w a_w(q) \mathfrak{S}_{w_0w} \mod \mathrm{Sym}_n^+, $$
where $w$ runs through all permutations of $S_n$ of length $n-1$.

Then [23, Proposition 6.2], in the special case of $\sigma_n$, can be rewritten in the form

$$ (7.9) \qquad a_w(q) = \langle \mathfrak{S}_w \rangle_{r+1}^q, $$

for any $w \in S'_{r+1}$, the set of permutations in $S_{r+1}$ with length $r$.

By Theorem 4.11, we know that $a_w(q)$ is $(r)_q!$ times the coefficient of $u_{[1,r]}$ in the squarefree basis expansion of $\mathfrak{S}_w(u_1, u_2 - u_1, u_3 - u_2, \dots)$. Together with the identity (7.7), this gives us the formula

$$ (7.10) \qquad a_w(q) = \frac{1}{(r)_q!} \sum_{\mathbf{a} \in \mathrm{Red}(w)} q^{\mathrm{comaj}(\mathbf{a})} A_{\mathrm{cont}(\mathbf{a})}(q), $$

where $\mathrm{cont}(\mathbf{a})$ is the sequence of nonnegative integers whose $i$th entry counts the number of $i$s in $\mathbf{a}$ for all $i \ge 1$. Setting $q=1$ in (7.10) gives us the quantity $a_w := a_w(1)$ which is exactly what is computed in [34, Theorem 1.1].

**Example 7.4.** Consider $w = 32415 \in S'_5$. It has three reduced words: 2123, 1213, and 1231. The corresponding contents are: (1, 2, 1, 0), (2, 1, 1, 0), and (2, 1, 1, 0). We have $A_{(1,2,1,0)} = (1+q)^2(1+q+q^2)$ and $A_{(2,1,1,0)} = (1+q)(1+q+q^2)$. By (7.10) we get

$$ a_w(q) = \frac{1}{(4)_q!} (q^5(1+q)^2(1+q+q^2) + (q^3+q^4)(1+q)(1+q+q^2)) = q^3. $$

The statement of [34, Theorem 1.1] mentions certain symmetries afforded by the $a_w$. It is natural to inquire whether they lift in the presence of the $q$ parameter. Consider conjugation by the longest word. From the definition of qDS we have

$$ \langle f \rangle_{r+1}^q = (-1)^r q^{\binom{r}{2}} \langle \omega f \rangle_{r+1}^{q^{-1}}, $$

where $\omega$ is the involution on $\mathbb{Q}[x_n]$ mapping $x_i \to x_{n+1-i}$ for $i \in [n]$. Since $\mathfrak{S}_w(x_1, \dots, x_n) = \mathfrak{S}_{w_0ww_0}(-x_n, \dots, -x_1)$ modulo $\mathrm{Sym}_n^+$, we infer the following

**Proposition 7.5.** For any $w \in S'_{r+1}$,

$$ a_{w_0ww_0}(q) = q^{\binom{r}{2}} a_w(q^{-1}). $$

This relation can also be easily derived from (7.10). The symmetry $a_w = a_{w^{-1}}$ no longer lifts to something obvious in the presence of the $q$. For instance, check that $a_{153264}(q) = q^7 + 2q^6 + 3q^5 + q^4 + q^3$ and $a_{143625}(q) = q^8 + 2q^7 + 2q^6 + 2q^5 + q^4$.

In the two subsections that follow we give $q$-analogues for certain results that hold for $a_w$; see [34, §5.2 and §6]. The techniques employed in loc. cit. are robust enough to allow for incorporating the $q$ parameter easily, and so our exposition will be brief and we refer the reader to [34] for further details and any undefined terminology.

### 7.3. Properties of $a_w(q)$.
In this section we establish two summatory properties of the numbers $a_w$, based on the notion of factorization of a permutation. We borrow notation from [34, §], and refer the reader to loc. cit. for details in the interest of brevity.

We can factor $w$ in $S_n$ uniquely into indecomposable permutations as

$$ (7.11) \qquad w = w_1 \times w_2 \times \dots \times w_k, $$
where each $w_i$ is an indecomposable permutation in $S_{m_i}$ for some $m_i > 0$. We say that $w$ is quasiindecomposable if exactly one $w_i$ is different from 1, i.e. $w = 1^i \times u \times 1^j$ for $u$ indecomposable $\neq 1$ and integers $i, j \ge 0$. Given this decomposition, the cyclic shifts $w^{(1)}, \dots, w^{(k)}$ of $w$ are given by

$$ (7.12) \qquad w^{(i)} = (w_i \times w_{i+1} \times \dots \times w_k) \times (w_1 \times \dots \times w_{i-1}). $$

These notions are very natural in terms of reduced words: Let the support of $w \in S_n$ be the set of letters in $[n-1]$ that occur in any reduced word for $w$. Then $w$ is indecomposable if and only if it has full support $[n-1]$. It is quasiindecomposable if its support is an interval in $\mathbb{Z}_{>0}$.

**Theorem 7.6 (Cyclic Sum Rule).** Let $w \in S'_n$, and consider its cyclic shifts $w^{(1)}, \dots, w^{(k)}$ defined by way of (7.11) and (7.12). We have that

$$ (7.13) \qquad \sum_{i=1}^{k} a_{w^{(i)}}(q) = \sum_{\mathbf{a} \in \mathrm{Red}(w)} q^{\mathrm{comaj}(\mathbf{a})}. $$

*Proof.* The proof presented in [34, Theorem 5.6] works virtually unchanged. Instead of appealing to the cyclic sum rule for (ordinary) mixed Eulerian numbers, we invoke Proposition 5.3. $\square$

*Remark 7.7.* In his seminal paper on reduced word enumeration, Stanley [40] introduced a family of symmetric functions $(F_w)_{w \in S_\infty}$ that have come to be called *Stanley symmetric functions*. By work of Edelman-Greene [14] and Lascoux-Schützenberger [28] we have the Schur-positive expansion $F_w = \sum_\lambda a_{w_\lambda} s_\lambda$, where the $a_{w_\lambda}$ may be computed using the *Lascoux-Schützenberger tree*. From the Edelman-Greene correspondence one can then show

$$ \sum_{\mathbf{a} \in \mathrm{Red}(w)} q^{\mathrm{comaj}(\mathbf{a})} = \sum_{\lambda} a_{w_\lambda} \sum_{T \in \mathrm{SYT}(\lambda)} q^{\mathrm{maj}(T)}, $$

which implies the right-hand side in Theorem 7.6 may be computed using the major index statistic on tableaux. In the case of $w$ vexillary, we have exactly one nonzero $a_{w_\lambda}$ so the right-hand side simplifies enormously.

**Example 7.8.** Let $w = 53124768 \in S'_8$. We have $w = 53124 \times 21 \times 1$, and hence its three cyclic shifts are $w^{(1)} = 53124 \times 21 \times 1 = 53124768$, $w^{(2)} = 21 \times 1 \times 53124 = 21386457$, and $w^{(3)} = 1 \times 53125 \times 21 = 16423587$. One computes that

$$ \begin{align*} a_{w^{(1)}}(q) &= q^7 + q^6 + q^5 + q^4 + q^3 + q^2, \\ a_{w^{(2)}}(q) &= q^{14} + 2q^{13} + 3q^{12} + 3q^{11} + 3q^{10} + 3q^9 + 3q^8 + 2q^7 + q^6, \\ a_{w^{(3)}}(q) &= q^{12} + 2q^{11} + 4q^{10} + 5q^9 + 6q^8 + 5q^7 + 5q^6 + 4q^5 + 3q^4 + q^3. \end{align*} $$

One may now check that $a_{w^{(1)}}(q) + a_{w^{(2)}}(q) + a_{w^{(3)}}(q)$ indeed tracks comaj over $\mathrm{Red}(w)$. Finally we also note that the Stanley symmetric function $F_w$ in this case expands as $F_w = s_{421} + s_{43} + s_{52}$. One can sum the major index generating function over tableaux of shape 421, 43, and 52 to obtain $a_{w^{(1)}}(q) + a_{w^{(2)}}(q) + a_{w^{(3)}}(q)$ again.

Our next result considers $a_w(q)$ when $w$ is quasiindecomposable and provides a simple way to compute them in terms of specializations of Schubert polynomials. For a permutation $v$ of length $\ell$ and $m \ge 0$, consider

$$ (7.14) \qquad \nu_v(m) := \nu_{1^m \times v} = \mathfrak{S}_{1^m \times v}(1, q, q^2, \dots). $$
**Theorem 7.9.** Assume that $v \in \mathbb{S}_{p+1}$ is indecomposable of length $n-1$. Define quasiindecomposable permutations $v^{[m]} \in \mathbb{S}'_n$ for $m=0, \dots, n-p-1$ by $v^{[m]} := 1^m \times v \times 1^{n-p-1-m}$. Then one has

$$ (7.15) \qquad \sum_{j \ge 0} \nu_v(j) t^j = \frac{\sum_{m=0}^{n-p-1} a_{v^{[m]}}(q) t^m}{(t; q)_n}. $$

*Proof.* One only needs to follow the script of [34, Theorem 5.8] making necessary changes along the way, taking into account the fact that the map sending $i_1 \cdots i_{n-1} \mapsto (i_1 + m) \cdots (i_{n-1} + m)$ is a comaj-preserving bijection between $\text{Red}(v)$ and $\text{Red}(v^{[m]})$ for $m=0, \dots, n-p-1$. $\square$

**Example 7.10.** Consider $n=7$ and $v=4321 \in \mathbb{S}_4$ an indecomposable permutation of length 6. We have that $v^{[0]} = 4321567$, $v^{[1]} = 1543267$, $v^{[2]} = 1265437$, and $v^{[3]} = 1237654$. One may check that

$$ \sum_{j \ge 0} \nu_u(j) t^j = \frac{q^4 + (q^8 + 2q^7 + 2q^6 + 2q^5)t + (2q^{10} + 2q^9 + 2q^8 + q^7)t^2 + q^{11}t^3}{(t; q)_7}. $$

Take particular note of the fact that coefficients in the numerator on the right hand side are all positive, which is a priori not immediate. Theorem 7.9 then tells us that $a_{v^{[0]}} = q^4$, $a_{v^{[1]}} = q^8 + 2q^7 + 2q^6 + 2q^5$, $a_{v^{[2]}} = 2q^{10} + 2q^9 + 2q^8 + q^7$, and $a_{v^{[3]}} = q^{11}$.

**7.4. Combinatorial interpretation for $a_w(q)$ in special cases.** We discuss two nice classes of permutations— Łukasiewicz permutations and Grassmannian permutations — beginning with the former.

**7.4.1. Łukasiewicz permutations.** In [34, Definition 6.1] we define a Łukasiewicz composition to be a vector $(c_1, \dots, c_n)$ with weight $n-1$ such that $c_1 + \cdots + c_k \ge k$ for all $1 \le k \le n-1$. A Łukasiewicz permutation in $\mathbb{S}_n$ is simply one whose code is a Łukasiewicz composition. We recall that the code of $w \in \mathbb{S}_n$ is the vector $(c_1, \dots, c_n)$ where $c_i$ is the number of $j > i$ such that $w_i > w_j$.

**Proposition 7.11.** For $w$ a Łukasiewicz permutation in $\mathbb{S}'_n$, we have

$$ a_w(q) = \mathfrak{S}_w(1, q, \dots, q^{n-1}). $$

*Proof.* The proof is similar to that presented in [34, Theorem 6.5], except that one eventually employs the equality $\langle x_1^{c_1} \cdots x_n^{c_n} \rangle = q^{\sum_{1 \le i \le n} (i-1)c_i}$ for $c$ a Łukasiewicz composition to conclude. $\square$

**Remark 7.12.** Two classes of permutations in $\mathbb{S}'_n$ that are Łukasiewicz are dominant permutations and Coxeter elements. A permutation is dominant if it is 132-avoiding, which in turn implies that its code can naturally be interpreted as a partition of $n-1$. For dominant $w$, the Schubert polynomial $\mathfrak{S}_w(x_1, \dots, x_n)$ is a single monomial. If we let code($w$) = $(\lambda, 0^{n-\ell(\lambda)})$, then $a_w(q) = q^{N(\lambda)}$. Equation (7.10) then implies the equality that $\sum_{\mathbf{a} \in \text{Red}(w)} q^{\text{comaj}(\mathbf{a})} A_{\text{cont}(\mathbf{a})} = q^{N(\lambda)}(n-1)_q!$, which is reminiscent of the cyclic sum rule in Proposition 5.3.

A Coxeter element in $\mathbb{S}'_n$ is a permutation $w$ such that any reduced word for $w$ contains one instance each of $s_1$ through $s_{n-1}$. As described in §6.3, we associate $I_w \subset [n-2]$ with any Coxeter element $w$ including $i \in [n-2]$ in $I_w$ if $s_i$ appears before $s_{i+1}$ in any reduced word for $w$. We then have the analogue of [34, Proposition 6.13]:

$$ a_w(q) = \sum_{\substack{\sigma \in \mathbb{S}_{n-1} \\ \text{Des}(\sigma) = I_w}} q^{\text{maj}(\sigma^{-1})} $$
An alternative description involves the major index distribution over all Young tableaux of the ribbon shape associated with $I_w$.

### 7.4.2. Grassmannian permutations.
A permutation is said to be *Grassmannian* if it has a unique descent. If this descent is in position $m$, we say that the permutation is *m-Grassmannian*. The partition $\lambda(w)$ obtained by sorting the entries of the code of $w$ in nonincreasing order (and omitting 0s) is called the *shape* of $w$. For instance, $w = 146235$ is 3-Grassmannian. Since the code $w$ is $(0, 2, 3, 0, 0, 0)$, we have $\lambda(w) = (3, 2)$. Note that together with the position of the first descent, the shape allows us to reconstruct a unique Grassmannian permutation interpreted as an element of $S_\infty$.

Given a partition $\lambda$, we let $\text{SYT}(\lambda)$ denote the set of standard Young tableaux of shape $\lambda$. Recall that a positive integer $i$ is a descent of $T \in \text{SYT}(\lambda)$ if $i + 1$ occupies some row strictly below that occupied by $i$. Let $\text{SYT}(\lambda, d)$ be the subset of $\text{SYT}(\lambda)$ comprising tableaux with exactly $d$ descents.

**Proposition 7.13.** Let $w \in S'_n$ be a $m$-Grassmannian permutation. Then we have

$$a_w(q) = \sum_{T \in \text{SYT}(\lambda(w), m-1)} q^{\text{maj}(T)}.$$

*Proof.* We follow the approach in [34, Proposition] using our results from §6. Set $\lambda := \lambda(w)$. We infer that

$$(7.16) \qquad a_w(q) = \sum_{T \in \text{SYT}(\lambda, m-1)} q^{(m-1)(n-1) - \text{maj}(T)}.$$

Recall now that Schützenberger’s evacuation map applied to $T$ results in a tableau $\text{evac}(T)$ of the same shape and with the same number of descents. More importantly, if $i$ is a descent in $T$, then $n-1-i$ is a descent in $\text{evac}(T)$. It follows that $\text{maj}(T) + \text{maj}(\text{evac}(T)) = (m-1)(n-1)$ for all $T \in \text{SYT}(\lambda, m-1)$. As evacuation is an involution on $\text{SYT}(\lambda, m-1)$, the claim follows. $\square$

Incidentally the proof just presented tells us that $a_w(q)$ is a ‘palindromic’ polynomial in $q$ because of the relation $q^{(m-1)(n-1)}a_w(q^{-1}) = a_w(q)$.

**Example 7.14.** Consider the 3-Grassmannian permutation $w = 146235$ with $\lambda(w) = (3, 2)$. Then

$$a_w(q) = q^4 + q^5 + q^6$$

from the following three tableaux:

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

We close by using the alternative expression for $a_w(q)$ in (7.10) and the preceding proposition to arrive at an evaluation for a class of remixed Eulerian numbers.

**Corollary 7.15.** Let $w \in S'_{r+1}$ be $m$-Grassmannian of shape $\lambda$. For $1 \le i \le r$, let $c_i$ be the number of cells in $\lambda$ that have content $i - m$. Then we have

$$A_{(c_1, \dots, c_r)}(q) = q^{-N(\lambda)} \left( \sum_{T \in \text{SYT}(\lambda, m-1)} q^{\text{maj}(T)} \right) \prod_{(i,j) \in \lambda} (h(i, j))_q,$$

where $h(i, j) = \lambda_i + \lambda'_j - i - j + 1$ is the hook-length of the cell $(i, j)$ in $\lambda$.
*Proof.* The proof follows from the approach in [34, Corollary 6.18]. □

**Example 7.16.** We consider the same 3-Grassmannian permutation as in Example 7.14. We get that $(c_1, \dots, c_5) = (0, 1, 2, 1, 1)$, and Corollary 7.15 says

$$A_{012110}(q) = q^{-2}(q^4 + q^5 + q^6)(4)_q(3)_q(2)_q = q^2(1+q)^2(1+q+q^2)^2(1+q^2).$$

*Remark 7.17.* In [34, §7], the authors consider the case of *w* a vexillary permutation. We gave a combinatorial interpretation for $a_w(1)$ in terms of certain special descents in tableaux, and one is led to believe that there should be a way to modify the arguments so that the *q* can be incorporated. Given the intricacy of the original argument, we do not pursue this matter further in this article as that would lead us astray.

## 8. THE INTERVAL PROPERTY

We now turn our attention to gaining a better understanding of a curious phenomenon encountered by the authors in [33, 34], which continues to manifest itself in the presence of the additional *q* parameter. The careful reader may have noticed a common underlying trait of equations (7.15), (6.8) and (5.5). Broadly speaking, each equation has a generating function tracking principal specializations on the left-hand side, and the right-hand side rewrites this as a rational function wherein the numerator records the qDS of ‘shifts’ of the appropriate family of polynomials. This resemblance acquires further mystery given that the objects involved — monomials whose exponent vector is a N-vector with interval support, quasisymmetric polynomials, and Schubert polynomials indexed by quasiindecomposable permutations— do not appear to possess obvious commonalities. As we demonstrate below, this ‘coincidence’ is explained by a characteristic possessed by the expansions in the basis $\mathcal{B}$ (or $\mathcal{B}_+$) when one takes the images of these polynomials under $\pi$. In doing so, we also give a satisfying answer to a problem raised by the authors in [34, §8.4].

**Definition 8.1.** (Interval property) A polynomial $f \in \mathbf{k}[\mathbb{z}]$ (resp. $\mathbf{k}[\mathbb{z}_+]$) is said to possess the strong (resp. weak) interval property if the expansion $\sum_{I \subset \mathbb{Z}} c_I u_I$ of $\pi(f)$ (resp. $\pi_+(f)$) in the basis $\mathcal{B}$ (resp. $\mathcal{B}_+$) satisfies

$$c_I \neq 0 \Rightarrow I \text{ is an interval in } \mathbb{Z}.$$

Note that this is really a property of elements of $\mathcal{K}$, resp. $\mathcal{K}_+$; we will only use it for polynomials though, since in this section we use the Klyachko algebras as intermediate steps towards understanding certain formulas involving principal specializations of polynomials.

For instance, $z_1^2 z_3$ does not possess the strong interval property as $\pi(f) = u_1^3 u_3$ expands as $\frac{1}{q+1}(u_{1,2,3} + q u_{0,1,3})$ and $\{0, 1, 3\}$ is not an interval. On the other hand if we work in $\mathcal{K}_+$, we see that $u_1^2 u_3 = \frac{1}{q+1} u_1 u_2 u_3$. Therefore, $z_1^2 z_3$ possesses the weak interval property.

For brevity, we say that a polynomial is SIP (resp. WIP) if it possesses the strong (resp. weak) interval property. Polynomials that are SIP (resp. WIP) form a vector space which we denote by $\mathcal{C}$ (resp. $\mathcal{C}_+$): in fact, using the defining ideals of $\mathcal{K}$ and $\mathcal{K}_+$, we have

$$\mathcal{C} = \bigoplus_{I \text{ interval } \subset \mathbb{Z}} \mathbf{k} z_I \oplus \mathbf{I}\mathcal{K}, \quad \mathcal{C}_+ = \bigoplus_{I \text{ interval } \subset \mathbb{Z}_+} \mathbf{k} z_I \oplus \mathbf{I}\mathcal{K}_+.$$

We now discuss the families of polynomials that concern us. For starters note that the discussion after Theorem 4.15 already gives us an important family of polynomials in $\mathbf{k}[\mathbb{z}]$, whose merit can
be measured by the fact that it explains the three motivating examples at the beginning of this section.

**Corollary 8.2.** Let $c$ be an $\mathbb{N}$-vector with interval support. Then $z^c$ is SIP.

There are families of polynomials in $k[z_+]$ that are WIP which are also relevant as we aim to demonstrate next. It will help us to introduce a property of $\mathbb{N}$-vectors that generalizes slightly what was referred to as the Lukasiewicz property in [34].

**Definition 8.3.** Let $c = (c_1, c_2, \dots)$ be a nonzero $\mathbb{N}$-vector with support in $\mathbb{Z}_+$. Let

$$m_c := \min\{j \ge 1 \mid c_j > 0 \text{ and } c_{j+1} = 0\} \text{ and } M_c := \max\{j \ge 1 \mid c_j > 0\}.$$

We call $c$ quasi Lukasiewicz if

$$(8.1) \qquad \sum_{i=1}^{j} c_i \ge j \text{ for } j = m_c, \dots, M_c.$$

*Remark 8.4.* Write $\text{Supp}(c)$ as a union of maximal intervals $I_j = [a_j, b_j]$, $j = 1, \dots, k$ with $b_j$ increasing. Note that $m_c = b_1$ while $M_c = b_k$. Then to verify that $c$ is Lukasiewicz it is easily checked that it suffices to verify Property (8.1) for $j = b_1, a_2 - 1, b_2, a_3 - 1, b_3, \dots, a_k - 1, b_k$. It follows that, for a given support, this property only depends on the sum of $c$ restricted to each maximal interval in this support.

This family is a quite natural common generalization of two important special cases:

* If $c$ is quasi Lukasiewicz with $c_1 > 0$, then $(c_1, \dots, c_{|c|+1})$ is a Lukasiewicz composition in the sense of [34], that is the inequality 8.1 holds for $j = 1, \dots, |c|$.

* Any $c$ with interval support that satisfies $c_i = 0$ for $i > |c|$ is quasi Lukasiewicz.

We transport this notion to permutations:

**Definition 8.5.** A permutation $w$ is (quasi) Lukasiewicz if for all its reduced words $a$ (equivalently, any of them$^7$), the content $\text{cont}(a)$ is (quasi) Lukasiewicz.

For instance, one can check that the permutation $32154 \in S_5$ is Lukasiewicz, say by picking the reduced word $a = 4121$ in which case $\text{cont}(a) = (2, 1, 0, 1)$. On the other hand, note that the permutation $1 \times 32154 = 143265$ is not quasi Lukasiewicz, as the reduced word $a = 5232$ has $\text{cont}(a) = (0, 2, 1, 0, 1)$, which does not satisfy the criteria of being quasi Lukasiewicz.

*Remark 8.6.* In [34] and in §7, we called a permutation Lukasiewicz if its code is Lukasiewicz. This is not different from the current definition. Indeed, for $w \in S_n$, consider the reduced word read from its *bottom pipe dream*. From [34, Appendix A] we have that $\text{cont}(a)$ being Lukasiewicz is equivalent to the code of $w$ being Lukasiewicz.

**Theorem 8.7.** The following families of polynomials in $k[z_+]$ are WIP:

(1) $z^c$ for $c$ quasi Lukasiewicz.

(2) $\Delta_+(P)$ for $P(x_1, \dots, x_m)$ a quasisymmetric polynomial in $x_1, \dots, x_m$.

(3) $\Delta_+(\mathfrak{S}_w)$ for $w$ a quasi Lukasiewicz permutation.

<footnote>$^7$By Matsumoto’s property, any two reduced words are related by a sequence of braid/commutation moves. It is easy to see, using for instance Remark 8.4, that if $\text{cont}(a)$ is quasi Lukasiewicz, then it remains so after applying a braid/commutation move.</footnote>
**Proof.** For (1), one possibility is to use the recurrence (3.4). Let us give a proof using the probabilistic interpretation from Proposition 5.1 instead. Let $q > 0$. Then one must show that when $I \subset \mathbb{Z}_+$ is not an interval, the probability $P_c(I)$ is zero; equivalently, let us prove that if $I$ is not an interval and $P_c(I) > 0$, then $I$ contains nonpositive integers. In this case, there exists $j > 0$ with $j \notin I$ such that $I$ has both elements smaller and larger than $j$. Because $P_c(I) > 0$, which means that it is possible for $c$ to stabilize at $I$, one has $c_j = 0$ and $|I| = |c|$. Now by (8.1), $\sum_{i=1}^{j-1} c_i = \sum_{i=1}^{j} c_i \ge j$. So there are at least $j$ particles in the sites 1 to $j-1$, and by the hypothesis it is possible for all of them to stabilize strictly left of $j$. Therefore some must end up at nonpositive sites, which is what we wanted to prove.

For (2), we appeal to Theorem 6.2 from which it follows immediately. As to (3), it follows from the identity (7.7): if $w$ is quasi Lukasiewicz, then each summand on the right-hand side is WIP, as implied by (1), and therefore so is the entire sum. $\square$

**Proposition 8.8.** Consider a homogeneous degree $d$ polynomial $f \in \mathbf{k}[\mathbf{z}_+]$ that is WIP, so that

$$ \pi_+(f) = \sum_{a \ge 1} f_a u_{[a,a+d-1]} $$

for some $f_a$ in $\mathbf{k}$. Then we have

$$ f_a = \langle f(\underbrace{0, \dots, 0}_{a-1}, x_1, x_1 + x_2, \dots, x_1 + \dots + x_d, 0, \dots) \rangle_{d+1}^q $$

and

$$ f((1)_q, (2)_q, \dots) = \sum_{a \ge 1} f_a \binom{a+d-1}{d}_q $$

Moreover, if $f = \Delta_+(g)$ for $g \in \mathbf{k}[\mathbf{x}_+]$, then

$$ f_a = \langle g(\underbrace{0, \dots, 0}_{a-1}, x_1, x_2, \dots, x_{d+1}, 0, \dots) \rangle_{d+1}^q $$

and

$$ g(1, q, q^2, \dots) = \sum_{a \ge 1} f_a \binom{a+d-1}{d}_q $$

**Proof.** The first equality follows from restricting Theorem 4.15 to $\mathcal{K}_+$. Indeed we simply have to compute $u_I^*(f)$ for $I = [a, a+d-1]$. The details are very similar to those in the discussion immediately after Theorem 4.15, and we omit them. The second equality then follows from applying the specialization sp (cf. §§3.4) sending $u_i \to (i)_q$.

For the second expression, it follows

$$ g(u_1, u_2 - u_1, \dots, ) = \sum_{a=1}^{\infty} \langle g(\underbrace{0, \dots, 0}_{a-1}, x_1, x_2, \dots, x_d, -(x_1 + \dots + x_d), 0, 0, \dots) \rangle_{d+1} \frac{u_{[a,a+d-1]}}{(d)_q!} $$

Here we can replace $-(x_1 + \dots + x_d)$ by $x_{d+1}$, since $x_1 + \dots + x_{d+1}$ is symmetric in $x_1, \dots, x_{d+1}$. The second equality follows by the same specialization sp. $\square$
Proposition 8.8 can thus be applied to any of three examples of Theorem 8.7. Note however that the identities that we have obtained for each of these families turned out to be summation formulas over specializations of multiple ‘compatible’ members of these families, as mentioned at the beginning of this section: cf. (5.5), (6.8), (7.15). We now proceed to give a common setting to explain such formulas.

Let $f$ be a formal power series in $(x_i)_{i \in \mathbb{Z}}$, homogeneous of degree $d \ge 1$, and such that the support of $f$ is bounded above, i.e. there exists an $M$ such that the variables $x_i$ for $i > M$ do not appear in $f$. Let $\psi_+(f)$ be the element in $\mathbf{k}[\mathbf{x}_+]$ obtained by setting $x_i = 0$ for all $i \le 0$.<fnref n="8" /> We continue to denote the shift map sending $x_i \to x_{i+1}$ by $\tau$. For $i \ge 0$, consider the sequence of polynomials in $\mathbf{x}_+$:

$$ (8.2) \qquad f^{(i)} := \psi_+(\tau^i(f)) = f(\dots, 0, x_1, x_2, \dots, x_i; x_{i+1}, x_{i+2}, \dots), $$

where the semicolon separates positive and nonpositive indices in $f = f((x_i)_{i \in \mathbb{Z}})$. Note that the $f^{(i)}$ have automatically the following compatibility property for any $i \ge 0$:

$$ (8.3) \qquad f^{(i)}(x_1, x_2, \dots) = f^{(i+1)}(0, x_1, x_2, \dots). $$

We now consider three properties such that such a series can possess:

(1) $f^{(0)} \neq 0$ and $x_1$ divides $f^{(0)}$.

(2) $\Delta_+(f^{(i)})$ is WIP for all $i \ge 0$.

(3) $f^{(i)}(x_1, \dots, x_{d+1}, 0, \dots) \in \mathrm{QSym}_{d+1}^+$ for all $i \ge d+1$.

Note these are really properties of the polynomials $f^{(i)}$. In fact we could have started directly with such a family of polynomials satisfying the compatibility relations (8.3). The series $f$ serves as a nice device to encode such a family, inspired by the back stable Schubert polynomials $\mathfrak{S}_w$ [26], see below. Note that the $\mathfrak{S}_w$ are back stable in a symmetric sense, while the authors extended this notion naturally to back stable quasisymmetric [36]. Condition (3) hints at a further extension of such notions.

Assume $f$ satisfies all three properties. Condition (2) says that $\Delta_+(f^{(i)})$ is WIP for all $i \ge 0$ and so by Proposition 8.8 we get

$$ (8.4) \qquad f^{(i)}(1, q, q^2, \dots) = \sum_{a \ge 1} \langle f^{(i)}(\underbrace{0, \dots, 0}_{a-1}, x_1, x_2, \dots, x_{d+1}, 0, \dots) \rangle_{d+1}^q \binom{a+d-1}{d} \cdot $$

Condition (1) immediately implies $f^{(0)}(0, x_1, x_2, \dots) = 0$, and more generally

$$ (8.5) \qquad f^{(i)}(\underbrace{0, \dots, 0}_{i+1}, x_1, x_2, \dots) = 0. $$

Thus (8.4) can be rewritten as

$$ (8.6) \qquad f^{(i)}(1, q, q^2, \dots) = \sum_{1 \le a \le i+1} \langle f^{(i-a+1)}(x_1, x_2, \dots, x_{d+1}, 0, \dots) \rangle_{d+1}^q \binom{a+d-1}{d} \cdot $$

<footnote n="8">⁸This map is denoted $\pi_+$ in [26], which unfortunately conflicts with our meaning of $\pi_+$.</footnote>
By condition (3) we have $\langle f^{(i-a+1)}(x_1, x_2, \dots, x_{d+1}, 0, \dots) \rangle_{d+1}^q = 0$ for $i-a+1 \ge d+1$ as the argument lands inside $\mathrm{QSym}_{d+1}^+$, using Corollary 6.6. Reindexing by setting $j = i-a+1$ we get

$$ (8.7) \qquad f^{(i)}(1, q, q^2, \dots) = \sum_{j=0}^{\min(i,d)} \langle f^{(j)} \rangle_{d+1}^q \binom{i+d-j}{d} q^j. $$

If we now multiply both sides of by $t^i$ and sum over all $i \ge 0$, by appealing to Cauchy's $q$-binomial theorem (2.4) we obtain:

**Proposition 8.9.** Suppose $f$ is a power series in $(x_i)_{i \in \mathbb{Z}}$ with support bounded above and homogeneous of degree $d \ge 1$. Assume further that $f$ meets conditions (1) through (3). Then we have

$$ \sum_{i \ge 0} f^{(i)}(1, q, q^2, \dots) t^i = \frac{\sum_{0 \le j \le d} \langle f^{(j)} \rangle_{d+1}^q t^j}{(t; q)_{d+1}}. $$

In light of Proposition 8.9 we revisit three important families considered earlier.

**The connected $y_c$.** Given a strong composition $c = (c_1, \dots, c_k) \models d$, consider

$$ (8.8) \qquad \overleftarrow{y}_c = \prod_{1 \le i \le k} (\cdots + x_{-1} + x_0 + x_1 + \cdots + x_i)^{c_i}. $$

Since $\overleftarrow{y}_c^{(0)} = x_1^{c_1} (x_1+x_2)^{c_2} \cdots (x_1+\cdots+x_k)^{c_k} = y_c$, condition (1) is met since $c_1 > 0$. Condition (3) follows because for $i \ge d+1$, we have $\overleftarrow{y}_c^{(i)}(x_1, \dots, x_{d+1}, 0, \dots) = (x_1 + \cdots + x_{d+1})^d$ which is symmetric in $x_1, \dots, x_{d+1}$. Finally, condition (2) follows from Corollary 8.2.

Proposition 5.6 now follows immediately from Proposition 8.9.

**Fundamental quasisymmetric functions.** Let $\tilde{f}$ be a quasisymmetric function in the variables $(x_i)_{i \le 0}$. Define $f = \tau^j(\tilde{f})$ where $j$ is the smallest positive integer so that the resulting $f$ meets condition (1).<fnref n="9" /> Thus $f$ is a quasisymmetric function in $(x_i)_{i \le j}$ satisfying Condition (1). Condition (2) follows from Theorem 8.7. Finally condition (3) is clear since the $f^{(i)}(x_1, \dots, x_{d+1}, 0, \dots)$ belong to $\mathrm{QSym}_{d+1}$. We may now infer Equation (6.8) as a consequence of Proposition 8.9.

As an explicit instance, say $\tilde{f} = F_\alpha(\mathbf{x}_-)$ for $\alpha = (\alpha_1, \dots, \alpha_k) \models d$. Then $f = \tau^k(F_\alpha(\mathbf{x}_-))$. In particular $f^{(0)} = x_1^{\alpha_1} \cdots x_k^{\alpha_k}$, and more generally $f^{(i)} = F_\alpha(x_1, \dots, x_{k+i})$. The reader can now check that the equality in Proposition 8.9 is that in equation (6.8) after both sides are divided by $t^k$.

**$\mathfrak{S}_w$ for $w$ quasiindecomposable.** We now discuss Theorem 7.9. To this end, we rely on beautiful recent work of Lam-Lee-Shimozono [26]. To keep the exposition brief, we borrow terminology from loc. cit. without definition. Assume $w \in \mathfrak{S}_{p+1}$ is indecomposable of length $d$. We interpret $w$ as a permutation in $\mathfrak{S}_\mathbb{Z}$ by declaring $w(i) = i$ for all $i \in \mathbb{Z} \setminus [p+1]$. In [26, Theorem 3.2], Lam et al introduce the back stable Schubert polynomial $\overleftarrow{\mathfrak{S}}_w$, which is a formal power series analogue of the ordinary Schubert polynomial $\mathfrak{S}_w$. One of its properties is that $\psi_+(\overleftarrow{\mathfrak{S}}_w) = \mathfrak{S}_w$.

<footnote n="9">⁹It is not hard to check that such a $j$ always exists. Indeed say $\tilde{f} = \sum_{\alpha \vdash d} c_\alpha F_\alpha(\mathbf{x}_-)$, then $j = \ell(\alpha)$ for $\alpha$ a composition of shortest length such that $c_\alpha > 0$.</footnote>
We take $f = \overleftarrow{\mathcal{S}}_w$. By [26, Proposition 3.7] and after taking images under $\psi_+$, we get

$$ (8.9) \qquad f^{(i)} = \mathcal{S}_{1^{i} \times w}. $$

We now verify conditions (1) through (3) under the assumption that $w$ is indecomposable.

We have $f^{(0)} = \mathcal{S}_w \neq 0$; $w$ is indecomposable, so in particular $w(1) > 1$, which in turn implies the $x_1$ divides $f^{(0)}$; say by the Billey–Jockusch–Stanley formula [7]. This verifies condition (1). Condition (2) follows from Theorem 8.7. As to (3), $\mathcal{S}_{1^{i} \times w}$ is well known to be symmetric in the variables $x_1, \dots, x_i$ [30]. Thus for $i \ge d+1$, $\mathcal{S}_{1^{i} \times w}(x_1, \dots, x_{d+1}, 0, \dots)$ is a symmetric polynomial in its variables, and thus naturally lands in $\mathrm{QSym}_{d+1}^+$. We have thus verified all criteria needed for Proposition 8.9, and Theorem 7.9 follows.

It would be interesting to find more families and identities that fit within this framework.

## 9. A q-ANALOGUE OF THE VOLUME POLYNOMIAL

We now return to what was Postnikov’s original motivation to discuss divided symmetrization and discuss how the parameter $q$ fits into this context. Given $\lambda = (\lambda_1, \dots, \lambda_n) \in \mathbb{R}^n$, the *permutahedron* $P_\lambda$ is defined to be the convex hull of all points of the form $w \cdot \lambda$ as $w$ ranges over $\mathcal{S}_n$. Postnikov [38, §3] establishes that if $\lambda_1 \ge \dots \ge \lambda_n$, the volume $V(\lambda_1, \dots, \lambda_n)$ of $P_\lambda$ is given by $\frac{1}{(n-1)!} \langle (\lambda_1 x_1 + \dots + \lambda_n x_n)^{n-1} \rangle_n^{q=1}$. It follows in particular that $V(\lambda)$ is a polynomial in the $\lambda_i$’s.

In light of this, it is reasonable to define the *q-volume* of $P_\lambda$ as

$$ (9.1) \qquad V^q(\lambda_1, \dots, \lambda_n) := \frac{1}{(n-1)!} \langle (\lambda_1 x_1 + \dots + \lambda_n x_n)^{n-1} \rangle_n^q. $$

We refer to $V^q(\lambda)$ as the *q-volume polynomial* of $P_\lambda$ given that it recovers Postnikov’s volume polynomial when $q=1$. The choice of nomenclature is justified further by the expansions that we consider next, which lift Postnikov’s results nicely and also serve to unify some of the qDS evaluations from this work.

By appealing to Proposition 4.3, we can expand in monomials of the form $\lambda_1^{c_1} \cdots \lambda_n^{c_n}$ as follows:

$$ (9.2) \qquad V^q(\lambda_1, \dots, \lambda_n) = \sum_{\substack{c=(c_1, \dots, c_n) \\ |c|=n-1}} \langle \mathbf{x}^c \rangle_n^q \frac{\lambda_1^{c_1} \cdots \lambda_n^{c_n}}{c_1! \cdots c_n!}. $$

Thus we obtain a generalization to [38, Theorem 3.2].

We can also generalize Postnikov’s expression [38, Section 16] for the volume polynomial in terms of mixed Eulerian numbers in a straightforward manner. Set $\mu_i = \lambda_i - \lambda_{i+1}$ for $1 \le i \le n-1$. In view of Theorem 4.11, we may then express $V^q(\lambda)$ alternatively as:

$$ (9.3) \qquad V^q(\lambda_1, \dots, \lambda_n) = \hat{V}^q(\mu_1, \dots, \mu_{n-1}) := \frac{(n-1)_q!}{(n-1)!} \times \mathrm{Top}_n((\mu_1 u_1 + \dots + \mu_{n-1} u_{n-1})^{n-1}). $$

Here the coefficient extraction on the right-hand side takes place in $\mathcal{K}_n$ with the ground field $\mathbf{k}$ containing $\mathbb{Q}(q)[\mu_1, \dots, \mu_{n-1}]$. Once again we may expand $(\mu_1 u_1 + \dots + \mu_{n-1} u_{n-1})^{n-1}$ in terms of
monomials of the form $\mu_1^{c_1} \cdots \mu_{n-1}^{c_{n-1}}$. From equation (9.3) it then follows that

$$ (9.4) \qquad V^q(\lambda_1, \dots, \lambda_n) = \sum_{\substack{c=(c_1, \dots, c_{n-1}) \\ |c|=n-1}} A_c(q) \frac{\mu_1^{c_1} \cdots \mu_{n-1}^{c_{n-1}}}{c_1! \cdots c_{n-1}!} $$

We now proceed to describe how qDS of Schubert polynomials appears in the context of $q$-volumes. We note that the analogous expression when $q = 1$ is not present in [38]. We will need the notion of (type A) degree polynomials introduced in [39] and which we refer to for their combinatorial definition in terms of chains in the Bruhat order. Given permutations $v$ and $w$ in $S_n$, the degree polynomial $D_{v,w}(y_1, \dots, y_n) \in \mathbb{Q}[y_1, \dots, y_n]$ can be defined by the fact that its evaluation at $(\Lambda_1 > \cdots > \Lambda_n) \in \mathbb{Z}^n$ is the degree of the Schubert variety $X^w$ in its projective embedding given by the line bundle indexed by $\Lambda$; see [39, Section 4].

By using [39, Equation 4.2] (essentially due to Chevalley) we have the following equality<fnref n="10" />

$$ (9.5) \qquad \frac{(\lambda_1 x_1 + \dots + \lambda_n x_n)^{n-1}}{(n-1)!} = \sum_{w \in S'_n} \mathfrak{S}_w(x_1, \dots, x_n) D_w(\lambda_1, \dots, \lambda_n) \mod \mathrm{Sym}_n^+. $$

Since qDS vanishes on degree $n-1$ homogeneous polynomials belonging to $\mathrm{Sym}_n^+$, we have

$$ (9.6) \qquad V^q(\lambda_1, \dots, \lambda_n) = \sum_{w \in S'_n} a_w(q) D_w(\lambda_1, \dots, \lambda_n). $$

Thus the $a_w(q)$ arise as coefficients when one expresses the $q$-volume in terms of degree polynomials.

Our results in this section have been largely obtained by algebraic manipulations, and it makes sense to inquire about an interpretation for $q$-volumes that is of a geometric flavor. We give one in [35], interpreting the exponents of $q$ as statistics on an interesting polyhedral decomposition of the permutahedron.

## APPENDIX A. PROOF OF PROPOSITION 4.3

Given $c \in W_n^{n-1}$, we need to show

$$ (A.1) \qquad \langle x_1^{c_1} \dots x_n^{c_n} \rangle_n^q = (-1)^{|S|} \sum_{\sigma \in X_S} q^{\binom{n-1}{2} - \mathrm{inv}(\sigma) - h(c)} $$

where $h_i(c) = (\sum_{k \le i} c_k) - i$ for $i = 1, \dots, n$, $h(c) = \sum_{i=1}^{n-1} h_i(c)$, $S$ is the set of $i \in \{1, \dots, n-1\}$ such that $h_i < 0$, and finally $X_S$ is the set of permutations of $S_n$ with descent set $S$.

Assume first that there exists an index $k \in [n-1]$ such that $h_k < -1$, and pick $k$ to be the largest such index. Since $h_n(c) = -1$, this implies that $h_{k+1} \ge h_k + 1$, that is $c_{k+1} \ge 2$. Consider the move sending $c$ to $d := (c_1, \dots, c_k+1, c_{k+1}-1, \dots, c_n) \in W_n^{n-1}$. We have $h_i(d) = h_i$ for $i \ne k$ and $h_k(d) = h_k + 1$. Thus we have $S_c = S_d$ and $h(d) = h(c) + 1$.

We show that $\langle \mathbf{x}^c \rangle_n = q \langle \mathbf{x}^d \rangle_n$. Indeed

$$ (A.2) \qquad \langle q\mathbf{x}^d - \mathbf{x}^c \rangle_n = \langle x_1^{c_1} \cdots x_k^{c_k} (qx_k - x_{k+1}) x_{k+1}^{c_{k+1}-1} \cdots x_n^{c_n} \rangle_n. $$

<footnote n="10">¹⁰An equality of this sort holds for any pair of dual bases where the duality pairing is as described in [39, Section 5]. Indeed, degree polynomials are duals to Schubert polynomials under that pairing.</footnote>
By our hypothesis that $h_k < -1$, we know that $\deg(x_1^{c_1} \cdots x_k^{c_k}) < k-1$. Lemma 4.2 implies that the right hand side of (A.2) equals 0, which in turn implies that $\langle \mathbf{x}^c \rangle_n = q \langle \mathbf{x}^d \rangle_n$.

Now assume that there exists an index $k \in [n-1]$ such that $h_k(c') > 0$, and pick $k$ to be the smallest such index. Since $h_0(c') = 0$, this implies that $h_{k-1}(c') + 1 \le h_k(c')$, that is $c'_k \ge 2$. Consider the move sending $c'$ to a sequence $d' := (c'_1, \dots, c'_k - 1, c'_{k+1} + 1, \dots, c'_n) \in W_n^{n-1}$. We have $h_i(d) = h_i(c')$ for $i \ne k$ and $h_k(d') = h_k(c') - 1 \ge 0$. Thus we have $S_{c'} = S_{d'}$ and $h(d') = h(c') - 1$. Arguing like before allows us to conclude that $\langle \mathbf{x}^{c'} \rangle_n = q^{-1} \langle \mathbf{x}^{d'} \rangle_n$. Repeating this transformation turns $c'$ to a composition $c''$ which satisfies $h_i(c'') \in \{0, -1\}$ for all $i \in [n]$, and we have

$$ (A.3) \qquad \langle \mathbf{x}^c \rangle_n = q^{b-a} \langle \mathbf{x}^{c''} \rangle_n $$

The upshot of the preceding discussion is that to compute $\langle \mathbf{x}^c \rangle_n$ it suffices to consider vectors $c$ such that $h_i(c) \in \{0, -1\}$ for all $i \in [n]$. The map $c \mapsto S_c$ restricted to these sequences is a 1-1 correspondence with subsets $S \subseteq [n-1]$. We write $S \mapsto c(S)$ for the inverse map, and set $\mathbf{x}(S) := \mathbf{x}^{c(S)}$.

For $S \subseteq [n-1]$, consider the family of polynomials

$$ (A.4) \qquad \beta_n(S) = q^{|S|+1-n} \sum_{\substack{\sigma \in S_n \\ \text{Des}(\sigma) = S}} q^{\binom{n}{2} - \text{inv}(\sigma)} $$

Our goal now is to prove that

$$ (A.5) \qquad \langle \mathbf{x}(S) \rangle_n = (-1)^{|S|} \beta_n(S) $$

To this end, we proceed by induction on $n$. When $n=1$, we have $S = \emptyset$. In this case, we have $\mathbf{x}(S) = 1$, and both sides of the equality in (A.5) equal 1. Let $n \ge 2$ henceforth. Assume further that $S \ne [n-1]$, and let $i \notin S$. Define $S_i = S \cap [i]$ and $S^i = \{j \in [n-i] \mid j+i \in S\}$. Then Lemma 4.2 gives

$$ (A.6) \qquad q \langle \mathbf{x}(S) \rangle_n - \langle \mathbf{x}(S \cup \{i\}) \rangle_n = \binom{n}{i} q \langle \mathbf{x}(S_i) \rangle_i \langle \mathbf{x}(S^i) \rangle_{n-i}. $$

The numbers $(-1)^{|S|} \beta_n(S)$ also satisfy this identity, because:

$$ (A.7) \qquad q\beta_n(S) + \beta_n(S \cup \{i\}) = \binom{n}{i} q \beta_i(S_i) \beta_{n-i} (S^i). $$

This has a simple combinatorial proof: given a permutation corresponding to the left hand side, split its 1-line notation after position $i$, and standardize both halves so that they become permutations on $[1, i]$ and $[1, n-i]$ respectively. The factor of $\binom{n}{i}q$ comes from inversions that have their left endpoint in $[1, i]$ and the right end point in $[i+1, n]$. Counting these inversions is the same as counting inversions in binary words in $\{0, 1\}$ with $i$ 0s and $n-i$ 1s. The factor $q$ comes from the factor $q^{|S|+1-n}$ ultimately.

To conclude, note that (A.6) determines all values $\langle \mathbf{x}(S) \rangle_n$ by induction in terms of the single value $\langle \mathbf{x}([n-1]) \rangle_n$. Now $\mathbf{x}([n-1]) = x_2 \cdots x_n$, so by the following lemma $\langle \mathbf{x}([n-1]) \rangle_n = (-1)^{n-1}$. This coincides with $(-1)^{n-1} \beta_n(S)$ so (A.5) holds in this case also and the proof is complete.
**Lemma A.1.** For $1 \le i \le n$, we have

$$ (A.8) \qquad \text{If } X_i := \prod_{\substack{1 \le j \le n \\ j \ne i}} x_j, \text{ then } \langle X_i \rangle_n = (-1)^{n-i} q^{\binom{i-1}{2}} \binom{n-1}{i-1} \qquad . $$

*Proof of the lemma.* We use induction on $n$. The claim is clearly true when $n = 1$, where the empty product is to be interpreted as 1. Assume $n \ge 2$ henceforth. For $i = 1, \dots, n-1$, we have

$$ \begin{aligned} \langle qX_{i+1} - X_i \rangle_n &= \langle (x_1 \dots x_{i-1})(qx_i - x_{i+1})(x_{i+2} \dots x_n) \rangle_n \\ &= \binom{n}{i} \langle x_1 \dots x_{i-1} \rangle_i \langle x_2 \dots x_{n-i} \rangle_{n-i}. \end{aligned} $$

By the inductive hypothesis, we have $\langle x_1 \dots x_{i-1} \rangle_i = q^{\binom{i-1}{2}}$ and $\langle x_2 \dots x_{n-i} \rangle_{n-i} = (-1)^{n-i-1}$. Therefore

$$ (A.9) \qquad \langle X_{i+1} \rangle_n - \langle X_i \rangle_n = (-1)^{n-i-1} q^{\binom{i-1}{2}} \binom{n}{i} \qquad . $$

By summation, this gives (A.8) up to a common additive constant. The proof of the lemma is then complete using $\sum_{i=1}^n \langle X_i \rangle_n = \langle \sum_{i=1}^n X_i \rangle_n = 0$ since $\sum_{i=1}^n X_i$ is symmetric in $x_1, \dots, x_n$, and $\sum_{i=1}^n (-1)^{n-i} q^{\binom{i-1}{2}} \binom{n-1}{i-1} \qquad \square$

## APPENDIX B. PROOF OF THEOREM 4.15

Notice that the expression on the RHS of (4.18) is linear in $f$, and thus it is enough to consider $f = z^c$ for $c$ an $\mathbb{N}$-vector with $|c| = d$.

Given $I$ with $|I| = d$, consider $p_c^I := u_I^*(z^c)$. Decompose $I$ as $I_1 \sqcup \dots \sqcup I_k$ where $I_j = [a_j, b_j]$ where $b_j \le a_{j+1} - 2$. It is easily seen that $p_c^I = 0$ unless $\text{Supp}(c) \subset I$ and $|I_j| = \sum_{i \in I_j} c_i$ for all $j$. Therefore, assume these conditions hold.

Let $c^{I_j}$ be the $\mathbb{N}$-vector which agrees with $c$ on the indices determined by the interval $I_j$ and is 0 everywhere else. From the relations defining $\mathcal{K}$ it follows that

$$ (B.1) \qquad p_c^I = \prod_{1 \le j \le k} p_{c^{I_j}}^{I_j} = \prod_{1 \le j \le k} \frac{A_{c^{I_j}}}{(|I_j|)_q!}, $$

where, in arriving at the second equality, we have used (a shifted version of) Theorem 4.11 to conclude that the coefficient of $u_{I_j}$ in $u^{I_j}$ is given by $\frac{A_{c^{I_j}}}{(|I_j|)_q!}$.

To establish the claim we need to show that

$$ (B.2) \quad p_c^I = \langle Q_I(\mathbf{x}) \prod_{j=1}^k x_{a_j}^{c_{a_j}} (x_{a_j} + x_{a_j+1})^{c_{a_j+1}} \cdots (x_{a_j} + \cdots + x_{b_j})^{c_{b_j}} \rangle_{\{a_1, \dots, b_k+1\}}^q \times \frac{1}{(b_k - a_1 + 1)_q!}. $$

It is immediate that the RHS vanishes if $\text{Supp}(c) \not\subset I$ as the degree of the argument is too small. So assume that $\text{Supp}(c) \subset I$. By applying Lemma 4.2 repeatedly, one may rewrite the RHS as

$$ (B.3) \qquad \prod_{1 \le j \le k} \left( \langle x_{a_j}^{c_{a_j}} \cdots (x_{a_j} + \cdots + x_{b_j})^{c_{b_j}} \rangle_{\{a_j, \dots, b_j+1\}}^q \times \frac{1}{(|I_j|)_q!} \right). $$
Note that $(c_{a_j}, \dots, c_{b_j})$ is nothing but $c^{I_j}$. Again we see that the right hand sides vanish if there exists $1 \le j \le k$ such that $|I_j| \ne |c^{I_j}|$ for degree reasons. Therefore, assuming that this is not the case, and recalling the definition of $A_{c^{I_j}}$, we see that the right hand in (B.2) coincides with the expression for $p_c^I$ from (B.1). This concludes our proof.

## APPENDIX C. PROOF OF THEOREM 7.2

Let us deal with the second part first. The identity (7.7) follows from extracting coefficients to the right-hand side of (7.6), using [15, Lemma 5.4]. More specifically we need to set $t_j = v_j$ and $z_j = (1-q)u_j$ in [15, Lemma 5.4].

So we just need to prove (7.6), and for this we follow the steps of [15]. The key difference is that we will need to appeal to the new Lemma 7.1.

It is clearly enough to prove that for any $k \ge 0$, we have

$$ (C.1) \qquad \mathfrak{S}_n(q^k u_1, q^k(u_2 - u_1), \dots, q^k(u_{n-1} - u_{n-2})) = \\ \qquad \mathfrak{S}_n(q^{k+1}u_1, q^{k+1}(u_2 - u_1), \dots, q^{k+1}(u_{n-1} - u_{n-2})) \prod_{j=n-1}^{1} h_j(q^k(1-q)u_j). $$

So we focus on proving (C.1). In fact, it is enough to do the case $k=0$ because the relations among the $u_i$ are homogeneous and are thus verified by the rescaled $q^k u_i$.

The case $n=2$ amounts to checking that $\mathfrak{S}_2(u_1) = 1 + u_1 v_1$ equals $\mathfrak{S}_2(qu_1)h_1((1-q)u_1) = (1+qu_1v_1)(1+(1-q)u_1v_1)$. This is true as $v_1^2 = 0$.

The case $n=3$ can also be checked directly, and this time we need the relations in $K_+$. The left-hand side, by using the relation $(1+q)u_1^2 = u_1 u_2$, expands as

$$ (C.2) \qquad \mathfrak{S}_3(u_1, u_2 - u_1) = 1 + u_1 v_1 + u_2 v_2 + u_1^2 v_2 v_1 + q u_1^2 v_1 v_2 + q u_1^3 v_2 v_1 v_2. $$

We need to that this equals $\mathfrak{S}_3(qu_1, q(u_2 - u_1))h_2((1-q)u_2)h_1((1-q)u_1)$, which in turn may be rewritten as

$$ h_2(qu_1)h_1(qu_1)\underline{h_2(qu_2 - qu_1)h_2(u_2 - qu_2)h_1((1-q)u_1)}. $$

The underlined terms give $h_2(u_2 - qu_1)$, say by [15, Lemma 3.1 (ii)]. A routine but tedious computation repeatedly employing the relation $u_1^2 = u_1(u_2 - qu_1)$ in $K_+$ shows that the resulting expression collapses to the right-hand side in (C.2).

Let $n \ge 4$. Let $R_n$ denote the right-hand side of (C.1) for $k=0$. We want to show that $R_n$ equals $\mathfrak{S}_n(u_1, u_2 - u_1, \dots, u_{n-1} - u_{n-2})$. Declare $u_0 = 0$. By using (7.4), we have

$$ (C.3) \qquad R_n = \mathfrak{S}_{n-1}(qu_1, \dots, q(u_{n-2} - u_{n-3}))|_{v_i \to v_{i+1}} \underbrace{\prod_{i=1}^{n-1} h_i(q(u_i - u_{i-1})) \prod_{j=n-1}^{1} h_j((1-q)u_j)}_{S:=S(u_1, \dots, u_{n-1})}. $$

For $i \ge 1$, we furthermore declare

$$ \tilde{h}_i := h_i(qu_i - qu_{i-1}); \qquad \tilde{h}'_i := h_i((1-q)u_i). $$
We use [15, Lemma 3.1 (i)] again to rewrite S as follows:

$$
\begin{align*}
S &= \tilde{h}_1 \cdots \tilde{h}_{n-2} \cdot \tilde{h}_{n-1} \tilde{h}'_{n-1} \cdot \tilde{h}'_{n-2} \cdots \tilde{h}'_1 \\
&= \tilde{h}_1 \cdots \tilde{h}_{n-2} \cdot h_{n-1}(u_{n-1} - q u_{n-2}) \cdot \tilde{h}'_{n-2} \cdots \tilde{h}'_1 \\
(C.4) \qquad &= \tilde{h}_1 \cdots \tilde{h}_{n-3} \cdot \tilde{h}_{n-2} h_{n-1}(u_{n-1} - q u_{n-2}) \tilde{h}'_{n-2} \cdot \tilde{h}'_{n-3} \cdots \tilde{h}'_1.
\end{align*}
$$

For $j \ge 1$ one can verify that $a = qu_j - qu_{j-1}$, $b = u_{j+1} - qu_j$ and $c = (1-q)u_j$ satisfy the assumption of Lemma 7.1. Using this Yang-Baxter relation in the underlined factor in the right-hand side of (C.4), with $j = n-2$ and these values of $a, b, c$, gives

$$
\begin{align}
S &= \tilde{h}_1 \cdots \tilde{h}_{n-3} \cdot h_{n-1}((1-q)u_{n-2})h_{n-2}(u_{n-2} - qu_{n-3})h_{n-1}(u_{n-1} - u_{n-2}) \cdot \tilde{h}'_{n-3} \cdots \tilde{h}'_1 \nonumber \\
(C.5) \qquad &= h_{n-1}((1-q)u_{n-2})\tilde{h}_1 \cdots \tilde{h}_{n-3} \cdot \overline{h_{n-2}(u_{n-2} - qu_{n-3})} \cdot \tilde{h}'_{n-3} \cdots \tilde{h}'_1 h_{n-1}(u_{n-1} - u_{n-2}). \nonumber
\end{align}
$$

Now note that $h_{n-2}(u_{n-2} - qu_{n-3}) = \tilde{h}_{n-2}\tilde{h}'_{n-2}$, and so excluding the rightmost and leftmost factors in (C.5), there remains $S(u_1, \dots, u_{n-2})$. Applying this argument repeatedly allows us to conclude by induction that

$$
(C.6) \qquad S(u_1, \dots, u_{n-1}) = \prod_{j=n-1}^{2} h_j((1-q)u_j) \prod_{i=1}^{n-1} h_i(u_i - u_{i-1}).
$$

We return to the expression for $R_n$ in (C.3). On substituting the expression for $S(u_1, \dots, u_{n-1})$ obtained in (C.6), we get

$$
(C.7) \quad R_n = \mathfrak{S}_{n-1}(qu_1, \dots, q(u_{n-2} - u_{n-3}))|_{v_i \mapsto v_{i+1}} \prod_{j=n-1}^{2} h_j((1-q)u_j) \prod_{i=1}^{n-1} h_i(u_i - u_{i-1}).
$$

Applying the inductive hypothesis to the first two factors, we may rewrite this equality as

$$
(C.8) \qquad R_n = \mathfrak{S}_{n-1}(u_1, u_2 - u_1, \dots, u_{n-2} - u_{n-3})|_{v_i \to v_{i+1}} \prod_{i=1}^{n-1} h_i(u_i - u_{i-1}).
$$

A comparison with (7.4) implies the claim, and we are done.

REFERENCES

[1] H. Abe, M. Harada, T. Horiguchi, and M. Masuda. The cohomology rings of regular nilpotent Hessenberg varieties in Lie type A. *Int. Math. Res. Not.* IMRN, (17):5316–5388, 2019.

[2] T. Amdeberhan. Explicit computations with the divided symmetrization operator. *Proc. Amer. Math. Soc.*, 144(7):2799–2810, 2016.

[3] D. Anderson and J. Tymoczko. Schubert polynomials and classes of Hessenberg varieties. *J. Algebra*, 323(10):2605–2623, 2010.

[4] J.-C. Aval, F. Bergeron, and N. Bergeron. Ideals of quasi-symmetric functions and super-covariant polynomials for $S_n$. *Adv. Math.*, 181(2):353–367, 2004.

[5] A. Berget, H. Spink, and D. Tseng. Log-concavity of matroid h-vectors and mixed Eulerian numbers. *Duke Math. J.*, 172(18):3475–3520, 2023.

[6] S. C. Billey, A. E. Holroyd, and B. J. Young. A bijective proof of Macdonald's reduced word formula. *Algebr. Comb.*, 2(2):217–248, 2019.

[7] S. C. Billey, W. Jockusch, and R. P. Stanley. Some combinatorial properties of Schubert polynomials. *J. Algebraic Combin.*, 2(4):345–374, 1993.

[8] L. Carlitz. A combinatorial property of q-Eulerian numbers. *Amer. Math. Monthly*, 82:51–54, 1975.
[9] P. Deligne and G. Lusztig. Representations of reductive groups over finite fields. Ann. of Math. (2), 103(1):103-161, 1976.

[10] F. Descouens and A. Lascoux. Non-symmetric Hall-Littlewood polynomials. Sém. Lothar. Combin., 54A:Art. B54Ar, 14, 2005/07.

[11] P. Diaconis and W. Fulton. A growth model, a game, an algebra, Lagrange inversion, and characteristic classes. Rend. Sem. Mat. Univ. Politec. Torino, 49(1):95-119 (1993), 1991. Commutative algebra and algebraic geometry, II (Italian) (Turin, 1990).

[12] G. Duchamp, D. Krob, A. Lascoux, B. Leclerc, T. Scharf, and J.-Y. Thibon. Euler-Poincaré characteristic and polynomial representations of Iwahori-Hecke algebras. Publ. Res. Inst. Math. Sci., 31(2):179-201, 1995.

[13] O. Dudas. Lectures on modular Deligne-Lusztig theory. In Local representation theory and simple groups, EMS Ser. Lect. Math., pages 107-177. Eur. Math. Soc., Zürich, 2018.

[14] P. Edelman and C. Greene. Balanced tableaux. Adv. in Math., 63(1):42-99, 1987.

[15] S. Fomin and R. P. Stanley. Schubert polynomials and the nil-Coxeter algebra. Adv. Math., 103(2):196-207, 1994.

[16] Y. Fukukawa, M. Harada, and M. Masuda. The equivariant cohomology rings of Peterson varieties. J. Math. Soc. Japan, 67(3):1147-1159, 2015.

[17] C. Gaetz and K. Tung. The Sperner property for 132-avoiding intervals in the weak order. Bull. Lond. Math. Soc., 53(2):442-457, 2021.

[18] A. M. Garsia and J. B. Remmel. $Q$-counting rook configurations and a formula of Frobenius. J. Combin. Theory Ser. A, 41(2):246-275, 1986.

[19] I. M. Gessel. A historical survey of $P$-partitions. In The mathematical legacy of Richard P. Stanley, pages 169-188. Amer. Math. Soc., Providence, RI, 2016.

[20] Z. Hamaker, O. Pechenik, D. E Speyer, and A. Weigandt. Derivatives of Schubert polynomials and proof of a determinant conjecture of Stanley. Algebraic Combinatorics, 3(2):301-307, 2020.

[21] M. Harada, T. Horiguchi, and M. Masuda. The equivariant cohomology rings of Peterson varieties in all Lie types. Canad. Math. Bull., 58(1):80-90, 2015.

[22] J. Huh and E. Katz. Log-concavity of characteristic polynomials and the Bergman fan of matroids. Math. Ann., 354(3):1103-1116, 2012.

[23] D. Kim. Homology Class of a Deligne-Lusztig Variety and Its Analogs. Int. Math. Res. Not. IMRN, 2020(4):1246-1280, 2020.

[24] A. A. Klyachko. Orbits of a maximal torus on a flag space. Funktsional. Anal. i Prilozhен., 19(1):77-78, 1985.

[25] A. A. Klyachko. Toric varieties and flag spaces. Trudy Mat. Inst. Steklov., 208:139-162, 1995.

[26] T. Lam, S. J. Lee, and M. Shimozono. Back stable Schubert calculus. Compos. Math., 157(5):883-962, 2021.

[27] A. Lascoux, B. Leclerc, and J.-Y. Thibon. Flag varieties and the Yang-Baxter equation. Lett. Math. Phys., 40(1):75-90, 1997.

[28] A. Lascoux and M.-P. Schützenberger. Schubert polynomials and the Littlewood-Richardson rule. Lett. Math. Phys., 10(2-3):111-124, 1985.

[29] A. Lascoux and M.-P. Schützenberger. Symmetrization operators in polynomial rings. Funktsional. Anal. i Prilozhен., 21(4):77-78, 1987. Translated from the English by A. V. Zelevinski.

[30] I. G. Macdonald. Notes on Schubert polynomials. Publications du LaCIM, 1991.

[31] E. Marberg and B. Pawlowski. Principal specializations of Schubert polynomials in classical types. Algebr. Comb., 4(2):273-287, 2021.

[32] K. Mittelstaedt. A stochastic approach to Eulerian numbers. Amer. Math. Monthly, 127(7):618-628, 2020.

[33] P. Nadeau and V. Tewari. Divided symmetrization and quasisymmetric functions. Selecta Math. (N.S.), 27(4):Paper No. 76, 24pp, 2021.

[34] P. Nadeau and V. Tewari. The permutahedral variety, mixed Eulerian numbers, and principal specializations of Schubert polynomials. Int. Math. Res. Not. IMRN, pages rnab337, 56p., 2022.

[35] P. Nadeau and V. Tewari. Remixed Eulerian numbers. Forum Math. Sigma, 11:Paper No. e65, 26, 2023.

[36] P. Nadeau and V. Tewari. $P$-partitions with flags and back stable quasisymmetric functions. Comb. Theory, 4(2):Paper No. 4, 22, 2024.

[37] F. Petrov. Combinatorial and probabilistic formulae for divided symmetrization. Discrete Math., 341(2):336-340, 2018.
[38] A. Postnikov. Permutohedra, associahedra, and beyond. *Int. Math. Res. Not.* IMRN, (6):1026–1106, 2009.

[39] A. Postnikov and R. P. Stanley. Chains in the Bruhat order. *J. Algebraic Combin.*, 29(2):133–174, 2009.

[40] R. P. Stanley. On the number of reduced decompositions of elements of Coxeter groups. *European J. Combin.*, 5(4):359–372, 1984.

[41] R. P. Stanley. *Combinatorics and commutative algebra*, volume 41 of *Progress in Mathematics*. Birkhäuser Boston, Inc., Boston, MA, second edition, 1996.

[42] R. P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

[43] J. R. Stembridge. Some permutation representations of Weyl groups associated with the cohomology of toric varieties. *Adv. Math.*, 106(2):244–301, 1994.

UNIV LYON, UNIVERSITÉ CLAUDE BERNARD LYON 1, CNRS UMR 5208, INSTITUT CAMILLE JORDAN, 43 BLVD. DU 11 NOVEMBRE 1918, F-69622 VILLEURBANNE CEDEX, FRANCE

Email address: nadeau@math.univ-lyon1.fr

DEPARTMENT OF MATHEMATICAL AND COMPUTATIONAL SCIENCES, UNIVERSITY OF TORONTO MISSISSAUGA, MISSISSAUGA, ON L5L 1C6, CANADA

Email address: vasu.tewari@utoronto.ca