%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2023}
\articlenumber{33}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{mathtools}

\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
%\theoremstyle{definition}
\newtheorem{defi}[thm]{Definition}
\newtheorem{exa}[thm]{Example}

\newcommand{\red}{\mathrm{Red}}
\newcommand{\sh}{\mathrm{sh}}
\newcommand{\wfclass}{\mathsf{C}}
\newcommand{\stan}{\mathrm{stan}}
\newcommand{\perm}{\mathrm{Perm}}
\newcommand{\schub}{\mathfrak{S}}
\newcommand{\qsym}{\mathrm{QSym}}
\newcommand{\sym}{\mathrm{Sym}}
\newcommand{\vvt}[1]{\textcolor{blue}{#1}}
\newcommand{\ppn}[1]{\textcolor{red}{#1}}
\newcommand{\flags}[1]{\mathrm{Fl}_{#1}}
\newcommand{\sgrp}{\mathbb{S}}
\newcommand{\alpxn}{\mathbf{x}_{n}}
\newcommand{\alpx}{\mathbf{x}}
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\ds}[2]{\langle {#1} \rangle_{#2}}
\newcommand{\suchthat}{\;|\;}
\newcommand{\cat}{\mathrm{Cat}}
\newcommand{\nvects}{\mathrm{Codes}}
\newcommand{\forest}{\mathfrak{p}}
\newcommand{\supp}{\mathrm{Supp}}
\newcommand{\lsupp}{\mathrm{LSupp}}
\newcommand{\slide}{\mathfrak{F}}
\newcommand{\funda}{\mathsf{L}}%fundamental quasiy
\newcommand{\psymb}{\mathsf{P}} % P symbol for the CS congruence
\newcommand{\qsymb}{\mathsf{Q}} % Q symbol for the CS congruence
\newcommand{\Zaug}{\overline{\bZ}}
\newcommand{\Paug}{\overline{\bP}}
%\newcommand{\lf}[2]{#1^{[#2]}}         %lf for labeled flag
% The CS correspondence business
\newcommand{\wf}{\operatorname{WF}}
\newcommand{\wfpark}{\operatorname{WFPark}}
\newcommand{\congwf}{\underset{\wf}{\equiv}}
\newcommand{\simwf}{\underset{\wf}{\sim}}


\newcommand{\injwords}[1]{\mathrm{Inj}(#1)}%injective words
%{\mc{#1}^*_{\mathrm{inj}}}
\newcommand{\pairofforests}{\mc{P\!\!F}} % no idea why I have chosen this name
\newcommand{\coxsyl}{\operatorname{CS}}
\newcommand{\cspark}{\operatorname{CSPark}}
\newcommand{\rootlist}{\mathsf{rl}}
\newcommand{\lf}[2]{#1^{[#2]}}
\newcommand{\bfc}{{\bf c}}
\newcommand{\cont}{\mathrm{cont}} % for content
\newcommand{\wfc}{\mc{W\!\!F}} %word forest correspondence

%% define your title in the usual way
\title[{$[\perm_n]$ via $\qsym_n^+$}]{$[\perm_n]$ via $\qsym_n^+$}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Philippe Nadeau\thanks{\href{nadeau@math.univ-lyon1.fr}{nadeau@math.univ-lyon1.fr}. P.N. was supported by the project ANR19-CE48-011-01 (COMBIN\'E).}\addressmark{1} \and Vasu Tewari\thanks{\href{mailto:vvtewari@math.hawaii.edu}{vvtewari@math.hawaii.edu}. V.T. was supported by Simons Grant \#855592.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Univ Lyon, Universit\'e Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille Jordan, 43 blvd.
du 11 novembre 1918, F-69622 Villeurbanne cedex, France \\ \addressmark{2}Department of Mathematics, University of Hawaii at Manoa, Honolulu, HI 96822, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use~\cite, and instead write out your citation as something like (author year)
\abstract{We give a combinatorial interpretation for the expansion of the cohomology class of the permutahedral variety $Perm_n$ in Schubert classes. This requires understanding Schubert polynomials modulo the ideal $\mathrm{QSym}_n^+$ of positive degree quasisymmetric polynomials. We introduce a new basis for the polynomial ring that we call forest polynomials, together with a bijective correspondence. Both constructions are of independent interest.
}

%% put your French abstract here, or comment this out if you don't have one
\resume{
Nous donnons une interprétation combinatoire au développement de la classe de cohomologie de la variété permutaédrale $Perm_n$ sur les classes de Schubert. Pour cela, il faut comprendre la réduction des polynômes de Schubert modulo l'idéal $\mathrm{QSym}_n^+$ des polynômes quasi-symétriques de degré positif. Nous introduisons une nouvelle base pour l'anneau de polynômes que nous appelons polynômes forestiers, ainsi qu'une correspondance bijective, toutes deux ayant un intérêt pour elles-mêmes. %Nous montrons que cette base décompose non négativement le polynôme de Schubert et permet une réduction directe modulo $\mathrm{QSym}_n^+$.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{permutahedral variety, quasisymmetric polynomials, binary trees, linear extensions.}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

Schubert calculus is the study of certain enumerative problems in algebraic geometry. These can be often phrased as finding  intersection numbers of subvarieties subject to certain conditions.
Littlewood--Richardson numbers arise for instance as generic triple intersection numbers of Schubert classes in the Grassmannian, and are known to count various families of objects.
The same intersection problem in the flag variety has been the study of intensive research for at least the past forty years.

Here we study a particular problem in the flag variety, namely the intersection of the so-called permutahedral (sub)variety $Perm_n$ with a generic Schubert variety $X^w$. If $w\in\sgrp_n$ has length $n-1$, the cardinality $a_w=|Perm_n\cap X^w|$ of intersection points is a well-defined nonnegative integer. Several properties of these numbers were obtained by the authors in~\cite{NT20}, as well as their evaluation in special cases, all of which point to rich combinatorics.

In this work we complete these results with a combinatorial interpretation for $a_w$.
Recall that $i_1i_2\ldots i_k$ is a \emph{reduced word} for a permutation $w$ if $w=s_{i_1}s_{i_2}\ldots s_{i_k}$ where $s_i$ is the transposition $(i\leftrightarrow i+1)$, and $k$ is minimal, given by the length $\ell(w)$.
We denote the set of reduced words for $w$ by $\red(w)$.
We also need a particular parking procedure in order to state our main result.

{\em WF-parking procedure:} Consider parking spots indexed by $\bZ$, initially all empty.
Cars $1,2,\dots$ arrive successively, with car $i$ having preferred spot $v_i$, and want to park at (empty) spots.
Assume inductively that $i-1$ cars have already parked.
If spot $v_i$ is empty, then car $i$ parks there.
Otherwise, $v_i\in [a,b]$ an interval of occupied spots with spots $a-1$ and $b+1$ being free.\footnote{Recall that in the classical parking algorithm, car $i$ simply parks in spot $b+1$.}
Define $v_j$ to be the preferred spot of the car that parked last in  $[a,b]$; that is, $j<i$ is maximal such that $v_j\in [a,b]$. Then, car $i$ parks in $b+1$ if $v_i\geq v_j$, while  it parks in $a-1$ if $v_i<v_j$.

After $k$ cars have parked they occupy a $k$-subset $I(v_1\cdots v_k)\subset \bZ$. A preference word $v_1\cdots v_k$ is called a \emph{WF-parking word} if $I(v_1\cdots v_k)=\{1,\ldots,k\}$.

\begin{thm}
\label{th:aw_as_parking}
If $w\in \sgrp_n$ has length $n-1$, then $a_w$ is the number of reduced words of $w^{-1}$ that are also WF-parking words.
\end{thm}


\begin{exa}
\label{exa:running}
Consider $w=21543\in \sgrp_5$ with $\ell(w)=4$. To compute $a_w$, we need to compute WF-parking words in $\red(w^{-1})=\red(w)$.
These are given explicitly in~\eqref{eq:red(21543)}, and only the first four of them are WF-parking words. It follows $a_{21543}=4$.
\end{exa}

We will explain the main steps of the proof leading to this result, and stress in particular the rôle played by the \emph{forest polynomials} that we introduce in \cref{sec:forest}. Let us first recall the geometrical context and previous results.


We will be brief on the geometry and refer to~\cite{NT20} for more information. The  \emph{complete flag variety} $\flags{n}$ is  the set of complete flags $V_\bullet=(V_0\subseteq V_1\subseteq V_2 \subseteq \cdots \subseteq V_n)$ where each $V_i$ is a linear subspace of $\bC^n$ of dimension $i$.
It is a smooth projective variety of dimension $\binom{n}{2}$ over $\bC$.
Inside $\flags{n}$ we have first and foremost the \emph{Schubert varieties} $X^w$ indexed by $w\in\sgrp_n$, whose cohomology classes $\sigma_w\coloneqq [X^w]$  form a linear basis of the cohomology ring $H^*(\flags{n},\mathbb{Q})$. In this work we consider the \emph{permutahedral variety} $\mathrm{Perm}_n$. It is an ubiquitous toric variety, encoded by the normal fan of the standard permutahedron, and occurs in $\flags{n}$ as a generic torus orbit or a regular semisimple Hessenberg variety.


Now by standard cohomology theory, the intersection numbers $a_w$ defined above are known to be given by the coefficients in the expansion of the class $[\mathrm{Perm}_n]$ in terms of Schubert classes.
Using a result of Anderson--Tymoczko~\cite{And10}, the authors were led in~\cite{NT20} to an algebraic expression for $a_w$ that we now recall.

Henceforth, set $\bQ[\alpxn]= \bQ[x_1,\dots,x_n]$. Let \emph{divided symmetrization} (DS), introduced under that name by Postnikov~\cite[Section 3]{Pos09}, be the linear form that takes a homogeneous polynomial $f(x_1,\dots,x_n)\in \bQ[\alpxn]$ of degree $n-1$ as input and outputs $\ds{f}{n}\in \bQ$ as:
\begin{align}
\label{eq:def_ds}
  \ds{f}{n}\coloneqq \sum_{w\in \sgrp_n}w\cdot\left(\frac{f(x_1,\dots,x_n)}{\prod_{1\leq i\leq n-1}(x_i-x_{i+1})}\right).
\end{align}
For $w\in \sgrp_n$ with length $n-1$, we have \cite[Theorem 3.2.1]{NT20}
\begin{equation}
\label{eq:aw_as_ds}
a_w=\ds{\schub_{w}}{n}.
\end{equation}

Here $\schub_{w}$ is a Schubert polynomial, see~\eqref{eq:def_schubert} for a definition. Before we explain how to go from the expression~\eqref{eq:aw_as_ds} to \cref{th:aw_as_parking}, note that the authors had previously obtained results on $a_w$ using the algebra of $\sgrp_n$-invariants of the cohomology ring $H^*(\perm_n,\bQ)$. This was based on work of Klyachko~\cite{Kly85} in a crucial way. The main result was an explicit formula for $a_w$ as a positive \emph{rational} linear combination of \emph{mixed Eulerian numbers}  \cite[Theorem 5.1.2]{NT20}.
The formula is reminiscent of Macdonald's famous reduced word identity and this aspect is explored in~\cite{NTc}.

A rational expression, even if positive, is unsatisfying since we know $a_w\in\bN$.
\cref{th:aw_as_parking} thus provides a pleasant answer in that respect.
Surprisingly the road to the interpretation therein goes through the quotient $\bQ[\alpxn]/\qsym_n^+$, first studied by Aval--Bergeron--Bergeron~\cite{ABB04}. We quickly introduce the relevant notions (see \cref{sec:preliminaries} for $\qsym_n^+$).
Let $\mc{C}_n$ denote the set of weak compositions $(c_1,\dots,c_n)$ such that for all $1\leq j\leq n$ we have $c_{j}+\cdots+c_n\leq n-j.$
We call its elements \emph{ABB compositions}. We refer to the monomials $\alpx^c\coloneqq x_1^{c_1}\cdots x_n^{c_n}$ where $c=(c_1,\dots,c_n)\in \mc{C}_n$ as \emph{ABB monomials}.
Aval--Bergeron--Bergeron showed the direct sum decomposition:
\begin{align}
\label{eq:abb_dec}
\bQ[\alpxn]={\bQ\{\alpx^c\suchthat c\in \mc{C}_n\}}\oplus {\qsym_n^+},
\end{align}
from which they inferred  that
$\dim(\bQ[\alpxn]/\qsym_n^+)=\cat_n\coloneqq \frac{1}{n+1}\binom{2n}{n}$.
The following result connects the ABB decomposition with DS.
\begin{thm}[{\cite[Theorem 1.3]{NTa}}]
\label{th:ds_via_qsym}
Express a degree $n-1$ homogeneous polynomial $f$ as $f={g}+{h}$ where ${g\in\bQ\{\alpx^c\suchthat c\in \mc{C}_n\}}$ and ${h\in \qsym_n^+}$. Then $\ds{f}{n}={g(1,1,\dots,1)}.$
\end{thm}

%Implicit in the ABB decomposition is that if $f\in \bZ[\alpxn]$, then the summand $g$ is a $\bZ$-combination of ABB monomials \implying that $\ds{f}{n}\in \bZ$.  If we further have that $g$ is a $\bN$-combination of ABB monomials then  $\ds{f}{n}\in \bN$.
Given Formula~\eqref{eq:aw_as_ds}, we are led to consider the decomposition of $\schub_{w}$ as in \cref{th:ds_via_qsym}. The corresponding polynomial $g$ will turn out to be a $\bN$-combination of ABB monomials, thus showing $a_w\in \bN$.\smallskip

We define an $\bN$-vector to be a sequence of nonnegative integers $(c_i)_{i\in \bZ_{\geq 1}}$ where all but finitely many $c_i$ are $0$. The \emph{support} of an $\bN$-vector $c$ is the set of indices $i\in \bZ_{>0}$ such that $c_i>0$.
We denote the set of $\bN$-vectors by $\nvects$.
Occasionally we truncate an $\bN$-vector to a finite sequence $(c_1,\dots,c_n)$ for some positive integer $n$. It is then understood that $c_i=0$ for all $i>n$.

We propose a family of polynomials $\{\forest_{c}\}_{c\in \nvects}$ which we call \emph{forest polynomials}; the reason will become clear in the sequel. They turn out to enjoy several nice combinatorial properties, and form a $\bZ$-basis of the space of all polynomials.
Our interest in them stems from the following theorem; its first part relies on the \emph{Word-Forest Correspondence} that we introduce in \cref{sec:word_forest}.
\begin{thm}
\label{th:forest_properties}
The following hold.
\begin{enumerate}[label=\emph{(\roman*)},noitemsep,nolistsep]
%\item \label{it1} The set of forest polynomials $\{\forest_c\}$ forms a basis for $\bZ[x_1,x_2,\dots]$.
\item \label{it1} Every Schubert polynomial is a nonnegative integral combination of forest polynomials.%, and this expansion can be determined by the Word-Forest Correspondence.
\item \label{it2} Let us restrict our attention to forest polynomials that only use variables $x_1$ through $x_n$. We then have $\forest_c$ modulo $\qsym_n^+\neq 0$ if and only if $c\in \mc{C}_n$. In the latter case, $\forest_c$ is a nonnegative integral combination of ABB monomials.%, and thus needs no reduction.
%\textup{(}indeed being a Catalan object $c$ uniquely determines a binary tree\textup{)}.
\end{enumerate}
\end{thm}


These two results, given in \cref{sec:word_forest,sec:forest} respectively,  will help give a manifestly nonnegative integral expression for $a_w$ that can eventually be interpreted as in \cref{th:aw_as_parking}; see \cref{sec:proof}. We close by mentioning some other applications in a final section.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Combinatorial preliminaries}
\label{sec:preliminaries}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent \textbf{Quasisymmetric polynomials.}
A \emph{strong composition} $\alpha\coloneqq (\alpha_1,\dots,\alpha_k)$ is a sequence of positive integers. We use $\ell(\alpha)\coloneqq k$ to denote the number of \emph{parts} in $\alpha$.
A polynomial $f\in \bQ[\alpxn]$ is \emph{quasisymmetric} if for every strong composition $\alpha$ the coefficient of $x_1^{\alpha_1}\cdots x_k^{\alpha_k}$ equals that of $x_{i_1}^{\alpha_1}\cdots x_{i_k}^{\alpha_k}$ for every $1\leq i_1<\cdots < i_k\leq n$. Clearly every  polynomial symmetric in  $x_1$ through $x_n$ is also quasisymmetric. A linear basis for the ring of quasisymmetric polynomials in $x_1$ through $x_n$ is given by the \emph{fundamental quasisymmetric polynomials} $\funda_{\alpha}(x_1,\dots,x_n)$ with $\ell(\alpha)\leq n$.
We are interested in the ideal $\qsym_n^+$ generated by positive degree quasisymmetric polynomials in $\bQ[\alpxn]$.
Equivalently, it is the ideal generated by all $\funda_{\alpha}(x_1,\dots,x_n)$ for $\ell(\alpha)>0$.

\smallskip

\noindent\textbf{Schubert polynomials.}
Given $\mathbf{i}=i_1\dots i_k\in \bZ^*$, let $\mathrm{Comp}(\mathbf{i})$ denote the set of sequences $(a_1\geq \dots \geq a_k)$ satisfying $1\leq a_j\leq i_j$ for all $j=1,\ldots, k$ and $a_j>a_{j+1}$ if $i_j>i_{j+1}$ for $j=1,\ldots, k-1$. Define $\slide({\mathbf{i}})$ by
\[
\slide({\mathbf{i}})=\sum_{(a_1,\dots,a_k)\in \mathrm{Comp}(\mathbf{i})}x_{a_1}\cdots x_{a_k}.
\]
If the sum on the right is empty, then $\slide(\mathbf{i})=0$.
Otherwise $\slide(\mathbf{i})$ can always be written as a \emph{slide polynomial} $\slide_{c}$~\cite{AS}.\footnote{Assaf--Searles index slides by $\bN$-vectors, and the latter can be read off from the exponent vector of the revlex leading monomial.} As an example,  $\slide(423)=x_2^2x_4+x_2^2x_3+x_1x_2x_4+x_1x_2x_3+x_1^2x_4+x_1^2x_3+x_1^2x_2$, which by the convention in~\cite{AS} is $\slide_{(0,2,0,1)}$.

Now given $w\in \sgrp_n$, let $\red(w)$ denote the set of \emph{reduced words} of $w$. We then have the following celebrated description of $\schub_w$ due to Billey--Jockusch--Stanley~\cite{BJS}:
\begin{equation}
\label{eq:def_schubert}
\schub_w=\sum_{\mathbf{i}\in \red(w^{-1})}\slide(\mathbf{i}).
\end{equation}
For example consider $w=14253\in \sgrp_5$. Then $\red(w^{-1})=\{243,423\}$.
We just computed $\slide({423})$ above, and $\slide({243})=x_1x_2^2=\slide_{(1,2)}$. Thus $\schub_{14253}=\slide({243})+\slide({423})$ is given by
\begin{equation}
\label{eq:ex_schubert}
\schub_{14253}=x_{1} x_{2}^2 + x_{1}^2 x_{2} + x_{1}^{2} x_{3} + x_{1} x_{2} x_{3} + x_{2}^{2} x_{3} + x_{1}^{2} x_{4} + x_{1} x_{2} x_{4} + x_{2}^{2} x_{4}.
\end{equation}

\smallskip

\noindent\textbf{Indexed forests.}
An \emph{indexed forest} $F$ is a set of complete binary trees, each with leaves labeled from left to right by an interval in $\bZ_{>0}$.
These intervals must moreover partition $\bZ_{>0}$, and all but a finite number of them are singletons, i.e. the corresponding tree is a leaf.
See \cref{fig:indexed_forest} (ignoring red labels for now), where we identify leaves with $\bZ_{> 0}$.

\begin{figure}[!ht]
\centering
\includegraphics[width=0.8\linewidth]{Indexed_Forest}
\caption{An indexed forest $F_0$ with size $6$}
\label{fig:indexed_forest}
\end{figure}

Let $\operatorname{IN}(F)$ be the set of internal nodes of $F$, and let $|F|$ be its size.
We call a node $v\in \mathrm{IN}(F)$ \emph{terminal} if both its children are leaves. Let $\mathrm{Term}(F)$ denote the set of terminal nodes in $F$.
The  \emph{support} $\supp(F)$ of $F$ is the set of labels of leaves attached to nontrivial trees.
The  \emph{left support} $\lsupp(F)$ of $F$ is the set of labels of left leaves attached to nontrivial trees.
The indexed forest in \cref{fig:indexed_forest} has size $6$, $\supp(F)=\{2,3,4,5,7,8,11,12,13\}$, and $\lsupp(F)=\{2,4,7,11\}$. Furthermore, it has 4 terminal nodes.


Define $\rho_F$ on $\operatorname{IN}(F)$  by $\rho_F(v)\coloneqq $ the leaf label reached by following left edges down from $v$; see red labels in \cref{fig:indexed_forest}.
Define $c_i$ to be the number of nodes labeled  $i$ by $\rho_F$ to get a vector $c(F)=(c_1,c_2,\ldots)\in \nvects$.
\begin{lem}
\label{lem:forests_and_codes}
$F\mapsto c(F)$ is a bijection between indexed forests and $\nvects$.
\end{lem}
 For $F$ in \cref{fig:indexed_forest} we get $c(F)=(0,\textcolor{magenta}{2,0,1,0},0,\textcolor{magenta}{1,0},0,0,\textcolor{magenta}{2,0,0},0,0,\ldots)$.
\smallskip

\noindent\textbf{Words.}
Given any alphabet $\mc{A}$, we denote the set of words in $\mc{A}$ by $\mc{A}^*$.
We denote the \emph{length} of any word $w\in \mc{A}^*$ by $\ell(w)$.
We let $\epsilon$ denote the \emph{empty word}.
The set of \emph{injective words} in $\mc{A}^*$ consists of words comprising solely distinct letters.
We denote this set by $\injwords{A}$.
Our ordered alphabet of interest  is obtained by ``augmenting'' $\bZ$: we define the alphabet $\Zaug$ of letters $\lf{i}{j}$ where $i\in \bZ$ and $j\in \bZ_{>0}$. These letters extend the linear order on $\bZ$ by $i<\lf{i}{1}<\lf{i}{2}<\lf{i}{3}<\cdots<i+1$ for all $i$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Forest polynomials}
\label{sec:forest}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We are ready to introduce forest polynomials.
Given the bijection $F\mapsto c(F)$, we can index them by either $\bN$-vectors  or by indexed forests.
We will do this without prior warning, omitting parentheses, commas, and trailing zeros in writing $c$.
\begin{defi}\label{def:forest} The \emph{forest polynomial} $\forest_F\in\bZ[x_1,x_2,\ldots]$  is defined as
\[\forest_F=\sum_{\kappa} \prod_{v\in \operatorname{IN}(F)}x_{\kappa(v)}\]
where the sum is over all labelings $\kappa:\operatorname{IN}(F)\to\bZ_{>0}$ that are bounded above by $\rho_F$, weakly increasing down left edges and strictly increasing down right edges.
\end{defi}


\begin{figure}[!ht]
\centering
\includegraphics[width=0.4\linewidth]{forest_example_0201.pdf}
\caption{An indexed tree $T_0$ with $c(T_0)=(0,2,0,1,0,\dots)$}
\label{fig:forest_0201}
\end{figure}


\begin{exa}
\label{exa:pT0}
Consider the indexed tree $T_0$ in \cref{fig:forest_0201}. Then \begin{align}
\label{eq:running_example}
\forest_{T_0}=\sum_{\substack{{2}\geq a\geq b\\{4}\geq c>b}}x_ax_bx_c&=
x_{2}^{2} x_{4} + x_{1} x_{2} x_{4} + x_{1}^{2} x_{4} + x_{2}^{2} x_{3} + x_{1} x_{2} x_{3} + x_{1}^{2} x_{3}  + x_{1}^{2} x_{2}+ x_{1} x_{2}^{2}.
\end{align}
which coincides with the Schubert polynomial $\schub_{14253}$, cf. \eqref{eq:ex_schubert}. % Note that $\alpx^{(0,2,0,1)}=x_2^2x_4$ is the revlex leading term in $\forest_F=\forest_{0201}$.
 Note that in general $\forest_F$ is the product of $\forest_T$ over all indexed trees $T$ composing $F$. Thus for $F_0$ in \cref{fig:indexed_forest}, we get $\forest_{F_0}=\forest_{T_0}(\sum_{i=1}^7x_i)(\sum_{1\leq i\leq j\leq 11}x_ix_j$).
\end{exa}


%To further emphasize the breadth of our definition, we demonstrate how all fundamental quasisymmetric polynomials arise as forest polynomials.
\begin{exa}\emph{(Fundamental quasisymmetric polynomials $\funda_\alpha$ are forest polynomials})
Let $F$ be an indexed forest with $\lsupp=[a,b]$ for some $a\leq b$.
A moment's thought should convince the reader that such an $F$ must in fact be a ``linear tree''. In fact this condition is equivalent to $\supp(c(F))$ being an interval in $\bZ_{> 0}$. \cref{fig:linear} shows two instances. The one on the left gives $\forest_F=\funda_{121}(x_1,\dots,x_4)$ and that on the right  $\forest_F=\funda_2(x_1,x_2)$.  In general, let $c(F)=(c_1,c_2,\ldots)$. Then $\forest_F=\funda_{\alpha}(x_1,\dots,x_b)$ with $\alpha=(c_b,\ldots,c_a)$.
%$\forest_F=\funda_{\alpha}(x_1,\dots,x_b)$ for some strong composition $\alpha\vDash |\supp(F)|-1$ with $\ell(\alpha)=|\lsupp(F)|$.
\end{exa}
\begin{figure}[!ht]
\centering
	\includegraphics[width=0.5\linewidth]{linear_trees.pdf}
\caption{Two indexed forests with left support an interval}
\label{fig:linear}
\end{figure}

The next proposition  is a consequence of the observation that the revlex leading term in $\forest_F$ is $\alpx^{c(F)}$.
It is interesting to compare it with the fact that Schubert polynomials indexed by permutations with last descent in position at most $n$ (respectively, in $\sgrp_{n}$) form a basis of $\bZ[\alpxn]$ (respectively, of ${\bQ\{\alpx^c\suchthat c_i\leq n-i\}}$).

\begin{prop}
\label{prop:forest_basis}
Given $n\in \bZ_{>0}$, the set
$
\{\forest_F\suchthat \lsupp(F)\subseteq [n]\}
$
is a basis of $\bZ[\alpxn]$, while the set
$
\{\forest_F\suchthat \supp(F)\subseteq [n]\}
$
is a basis of ${\bQ\{\alpx^c\suchthat c\in \mc{C}_n\}}$.
%In particular $\{\forest_F \}_F$ is a basis of $\bZ[\alpx]$.
\end{prop}


\cref{def:forest} essentially describes forest polynomials as a generating function for certain \emph{flagged $(P,\omega,\rho)$-partitions} in the sense of Assaf--Bergeron~\cite{AssBerg}. Let $\mathrm{Dec}(F)$ denote the set of \emph{decreasing forests} with shape $F$, that is bijections $\operatorname{IN}(F)\to \{1,\dots, |F|\}$ decreasing down branches. For a fixed $F$, one can identify $L\in \mathrm{Dec}(F)$ with a word $\rho_F(v_1)\cdots\rho_F(v_{|F|})$ where $v_i$ is the node with label $L(v_i)=i$. The next expansion is a special case of results in \emph{loc. cit.}
\begin{equation}
\label{eq:forest_to_slide}
\forest_F=\sum_{L\in \mathrm{Dec}(F)}\slide(L).
\end{equation}
 Thus any forest polynomial is a sum of slide polynomials. For $T_0$ in \cref{exa:pT0} and \cref{fig:forest_0201}, the expansion in~\eqref{eq:forest_to_slide} specializes to
 $\slide(242)+\slide(422)=\slide_{(1,2)}+\slide_{(0,2,0,1)}$, which as expected coincides with the one defining $\schub_{14253}(=\forest_{T_0})$.
\medskip

\noindent{\bf Reduction modulo $\qsym_n^+$.} Henceforth, given $f\in \bQ[\alpxn]$, we take $f\!\!\mod \qsym_n^+$ to mean the unique $g$ satisfying $f=g+h$ with $h\in \qsym_n^+$ and $g\in \bQ\{\alpx^c\suchthat c\in \mc{C}_n\}$.
Our aim is to give a straightforward description for $\forest_F\!\mod\qsym_n^+$; see \cref{th:red_mod_qsym}.
Despite the simplicity of the statement, the proof is technical (and omitted in this abstract). It relies on the recurrence in \cref{lem:leaf_indexed}.


We discuss two operations on indexed forests that will allow us to describe this recurrence. The first is the \emph{shift} map $\tau$ which, given an indexed forest $F$, simply shifts $\supp(F)$ one unit to the right.
We abuse notation and define $\tau^{i}(\forest_F)=\forest_{\tau^{i}(F)}$ for $i\in \bZ$, making note that if $\supp(\tau^{i}(F))\nsubseteq \bZ_{>0}$, then $\forest_{\tau^{i}(F)}$ equals $0$.

The second operation is \emph{trimming}, which corresponds to removing a terminal node. Explicitly, consider $v\in \mathrm{Term}(F)$.
 %and let $i, i+1\in \supp(F)$ be its children.  Note that this means $\rho_F(v)=i$.
It lies in one of the indexed trees $T$ composing $F$, say with support $[a,b]$.
%Set $T_j'= T_{j}\setminus \{v\}$ and declare $\supp(T_j')=I_j'\coloneqq[a,b-1]$.
We obtain $\mathrm{trim}_v(F)$ from $F$ by replacing $T$ with $T'= T\setminus \{v\}$ with new support $[a,b-1]$, and leaving the other trees unaltered. If $a=b-1$, then $T'$ has no internal nodes (i.e it is trivial), and we omit it.


\begin{figure}[!ht]
\centering
\includegraphics[width=0.7\linewidth]{forest_trim.pdf}
\caption{The two indexed forests resulting from trimming $T_0$ in \cref{fig:forest_0201}}
\label{fig:forest_trim}
\end{figure}

\begin{lem}
\label{lem:leaf_indexed}
Given an indexed forest $F$ we have
\begin{equation}
\label{eq:leaf_indexed}
\forest_F=\forest_{\tau^{-1}(F)}+\sum_{v\in \mathrm{Term}(F)}x_{\rho_F(v)}\,\forest_{\mathrm{trim}_v(F)}.
\end{equation}
\end{lem}
One can rewrite this recurrence by indexing forest polynomials by  $\bN$-vectors.
For the tree $T_0$ in \cref{fig:forest_0201}, using \cref{lem:leaf_indexed} we get:
$
\forest_{0201}=\forest_{201}+x_2\,\forest_{011}+x_4\,\forest_{02}.
$
Now, $\forest_{201}=x_1^2x_2+x_1^2x_3$, $\forest_{011}=e_2(x_1,x_2,x_3)$, and $\forest_{02}=h_2(x_1,x_2)$, and substituting these gives the same expansion as in~\eqref{eq:running_example}.

\cref{lem:leaf_indexed} has several consequences; we record two that concern us most.
First, we have a nice interpretation for the sum of coefficients of $\forest_F$ in a special case.

\begin{prop}
\label{pro:all_1s_tree}
If $T$ is an indexed tree with support $\{1,\ldots,|T|\}$, we have
\begin{equation}
\label{eq:all_1s_tree}
\forest_T(1,\dots,1)=|\mathrm{Dec}(T)|.
\end{equation}
\end{prop}


One can extend this to a result for all $\forest_F$ but we will not need it here.
 The second consequence of \cref{lem:leaf_indexed} is \cref{th:forest_properties}\ref{it2} which we reformulate here.
\begin{thm}
\label{th:red_mod_qsym}
Let $F$ be an indexed forest satisfying $\lsupp(F)\subseteq [n]$.
Then
\[
\forest_F \!\!\mod \qsym_n^+=\left\lbrace\begin{array}{ll}0 & \text{if}\;\;\supp(F)\nsubseteq [n] \;(\text{equivalently},\; c(F)\notin \mc{C}_n)\\ \forest_F & \text{if}\;\;\supp(F)\subseteq [n] \;(\text{equivalently},\; c(F)\in \mc{C}_n).\end{array}\right.
\]
\end{thm}
%An alternative phrasing replaces the condition on $F$ with one on $c(F)$.  \cref{th:red_mod_qsym} then says that $\forest_{F}\in \qsym_n^+$ if $c(F)\notin \mc{C}_n$. Otherwise $\forest_F\in \bQ\{\alpx^c\suchthat c\in \mc{C}_n\}$.

As an example, note that \cref{th:red_mod_qsym} says that the forest polynomial $\forest_{0201}$ in~\eqref{eq:running_example} is in $\qsym_4^+$ as $\supp(T_0)\nsubseteq [4]$.
We invite the reader to check that \begin{align*}
\forest_{0201}=\funda_{(2,1)}(x_1,\dots,x_4)+\funda_{(1,2)}(x_1,\dots,x_4)-(x_3+x_4)\funda_{(1,1)}(x_1,\dots,x_4)
\end{align*}
and thus clearly belongs in $\qsym_4^+$. On the other hand, $\tau^{-1}(T_0)$ has support exactly $[4]$, and $\forest_{2010}=x_1^2x_2+x_1^2x_3$; each monomial here is an ABB monomial.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Word-Forest correspondence}
\label{sec:word_forest}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We now proceed to describe the main insertion algorithm in this work, the  \emph{Word-Forest correspondence}.
We will need labeled versions of indexed forests. A \emph{labeling} of $F$ is a map from $\operatorname{IN}(F)$ to some alphabet $\mc{A}$.
\emph{Furthermore, we allow our indexed forests to be supported on $\bZ$ and not just $\bZ_{>0}$. When we consider forest polynomials subsequently, only those that are supported on $\bZ_{>0}$ shall matter.
}


The input is an injective word $W\in\injwords{\Zaug}$, while the output is a pair $\wfc(W)=(\psymb,\qsymb)$ of labeled indexed forests where the underlying unlabeled forests are the same. Following conventions, we call $\psymb$ (respectively $\qsymb$) the \emph{insertion forest} (respectively \emph{recording forest}).
We define $\wfc(W)$ inductively via an insertion procedure.\smallskip

 A convenient bookkeeping device while executing our algorithm is the \emph{root list} $\rootlist(W)$ for $W$. It is a totally ordered subset of $\bZ\sqcup \Zaug$ that records the list of root labels in $\psymb$: trivial trees are encoded by their index in $\bZ$, other root labels are certain letters in $W$. %Indeed, if there are no letters to insert, the set of leaves (which is $\bZ$) coincides with the set of roots. Our output in this case is the pair where both coordinates equal the trivial forest.If $W$ is nonempty, then $\rootlist(W)$ will be a subset of $\bZ\sqcup \Zaug$.
\smallskip

\noindent{\bf The WF-correspondence.}
Let $W\in\injwords{\Zaug}$. If $W$ is empty, $\psymb$ and $\qsymb$ are trivial forests. We thus set $\rootlist(\epsilon)=\bZ$. Now suppose $W=W'b$ and $\wfc(W')=(\psymb',\qsymb')$ by induction. Then $\wfc(W)$ is determined as follows.
\begin{enumerate}[noitemsep,nolistsep]
  \item Let $a$ (respectively $c$) be the greatest (respectively least) elements in $\rootlist(W')$ such that $a<b<c$.\footnote{Recall that our inputs are injective words}
  \item Merge the two trees in $\psymb'$ with roots labeled  by $a$ and $c$ into a single tree by adding a new root with label $b$ as their parent. This gives us $\psymb(W)$.
  The new root list is then $\rootlist(W)=\left(\rootlist(W')\setminus \{a,c\}\right)\cup\{b\}$.
  \item $\qsymb(W)$ records this merging procedure by performing a corresponding merge in $\qsymb'$ and having $|W|$ as the new root label.% That is we take the two corresponding trees in $\qsymb'$ and merge into a single tree by declaring $|W|$ to be their parent. This gives us $\qsymb$.
\smallskip

\end{enumerate}
See \cref{fig:wfc_example} for the $\psymb$ and $\qsymb$ that result when one applies the preceding procedure.
Note that internal nodes in $\psymb$ are labeled by letters in $W$ whereas those in $\qsymb$ are labeled by $\{1,\dots,|W|\}$. One can say more\textemdash{}
  $\psymb$ is a \emph{local binary search forest}, i.e. the label of any node is strictly greater (lesser) than the label of its left (respectively right) child, while $\qsymb$ is a \emph{decreasing forest} as already defined.
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{wfc_example_fpsac.pdf}
\caption{The insertion and recording forest for $W=\lf{1}{1}\lf{3}{1}\lf{4}{1}\lf{3}{2}$}
\label{fig:wfc_example}
\end{figure}

Fix a finite set $B\subseteq \Zaug$.
Denote by $\sgrp_B$ the set of all permutations of $B$ (in one-line notation). Clearly $|\sgrp_B|=|B|!$ and $\sgrp_B\subset\injwords{\Zaug}$.
Denote by $\pairofforests(B)$ the set of all ordered pairs $(\psymb,\qsymb)$ where $\psymb$,$\qsymb$ have the same underlying complete indexed forest and additionally
\begin{itemize}[noitemsep,nolistsep]
\item internal nodes in $\psymb$  are bijectively labeled by letters in $B$ so that the result is a local binary search forest;
\item internal nodes in $\qsymb$ are bijectively labeled by letters in $\{1,\dots,|B|\}$ so that the result is a decreasing forest.
\end{itemize}

We are ready for our main procedure that governs the combinatorics.
\begin{thm}
%[Coxeter--Sylvester correspondence]
[Word-Forest correspondence]
The map $\wfc: \sgrp_B \to \pairofforests(B)$ is a bijection.
%\begin{enumerate}
%\item Injective words $W$ with letters $B\subset \Zaug$ (here I mean the $|W|$ distinct letters actually occurring in $W$, so there are $|B|!$ such words;
%\item  Pairs  $(\psymb,\qsymb)$ where $\psymb$ is a "local binary search forest" with internal nodes bijectively labelled by $B$\footnote{We work with complete business, $\bZ$ labeling the leaves} and $\qsymb$ a decreasing labeling of the same indexed forest.
%\end{enumerate}
\end{thm}
\begin{proof}[Proof (sketch).]
The forward direction produces an element in $\pairofforests(B)$ as discussed earlier. The inverse correspondence simply consists in reading the labels of $\psymb$ according to the order determined by $\qsymb$, and this is injective as well. The claim follows.
\end{proof}

%Note that while it is immediate that $\sgrp_B$ has cardinality $|B|!$, the same cannot be said of $\pairofforests(B)$. Having established this, we dive deeper into the combinatorics of this correspondence.\medskip
The WF-correspondence specializes to the ``Sylvester correspondence'' when $B$ has the form $\{\lf{1}{1},\lf{2}{1},\ldots,\lf{n}{1}\}$, but does not reduce to it in general. Our main use for this correspondence will be to group together all words that have the same labeled forest $\psymb$. \medskip

\noindent{ \bf The WF-equivalence.} We say that words $W_1,W_2\in \injwords{\Zaug}$ are \emph{$\wf$-equivalent} if $\psymb(W_1)=\psymb(W_2)$. We denote this by $W_1\congwf W_2$.
%This implies necessarily that $W_1,W_2$ comprise the same letters.
For instance the reader can check that $\lf{3}{1}\lf{1}{1}\lf{4}{1}\lf{3}{2}$ and $\lf{1}{1}\lf{3}{1}\lf{4}{1}\lf{3}{2}$ produce the same $\psymb$ (shown in \cref{fig:wfc_example}), and thus $\lf{3}{1}\lf{1}{1}\lf{4}{1}\lf{3}{2}\congwf \lf{1}{1}\lf{3}{1}\lf{4}{1}\lf{3}{2}$.
It is helpful to compare the $\qsymb$ symbol for these two words as well. Observe that two \emph{incomparable} nodes swap their labels. We can actually  give a `local' description to WF-equivalence which generates $\congwf$ as its transitive closure.
We say that $W_1\simwf W_2$ if we can write $W_1=UabV$, $W_2=UbaV$ and there are at least two elements $c,d$ of in the rootlist  $\rootlist(U)$ such that
\begin{align}
\label{ineq:cs_similarity}
\min(a,b)<c,d<\max(a,b).
\end{align}
Note that this entails that $W_1$ and $W_2$ are in the same \emph{commutation class}: if we denote $a=\lf{i}{\cdot},b=\lf{j}{\cdot}$, then necessarily  $|j-i|\geq 2$.
\begin{lem}
\label{lem:blah}
$\congwf$ is the equivalence relation generated by $\simwf$.
\end{lem}

%WF-equivalence classes will play an important role in what follows.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{$a_w$ by expanding Schuberts into forests}
\label{sec:proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 We now discuss the decomposition of Schubert polynomials into forest polynomials. To this end we will need to apply the WF-correspondence to reduced words. We thus need to transform words in $\bZ^*$ as as elements in $\injwords{\Zaug}$.

  For $w\in\bZ^*$, define the word $\stan(w)$ in $\Zaug^*$ by labeling the occurrences of the letter $i$ in $w$ from left to right by $\lf{i}{1},\lf{i}{2},\dots$, for any $i\in \bZ$. For instance $\stan(1221625)=\lf{1}{1}\lf{2}{1}\lf{2}{2}\lf{1}{2}\lf{6}{1}\lf{2}{3}\lf{5}{1}$. It is clear $w\mapsto \stan(w)$ embeds $\bZ^* \in \injwords{\Zaug}$. We will implicitly apply constructions of the previous section to words via these standardized versions.

\begin{defi}
Given a WF-equivalence class $\wfclass$, we define its \emph{shape} $\sh(\wfclass)$ to be the underlying unlabeled indexed forest $F$ of $\psymb(W)$ for any element in $W\in\wfclass$. We define $\supp(\wfclass)$ to be equal to $\supp(F)$.% We also define $\sh(W)=\sh(C)$ for any $W\in C$.
\end{defi}

Recall that $\red(w)$ is the set of reduced words for a permutation $w$. For instance, if $w=21543$ in one-line notation, then
\begin{align}
\label{eq:red(21543)}
\red(w)=\{\textcolor{blue}{1343},\textcolor{blue}{3143},\textcolor{blue}{3413},\textcolor{red}{3431},1434,4134,4314,4341\}.
\end{align}
Those with the same color form an equivalence class under $\congwf$. The corresponding shapes from left to right are shown in \cref{fig:wf_classes}.
In particular we note that $\red(21543)$ is closed under $\congwf$. This is in fact true for any set $\red(w)$: more generally, commutation classes are always closed under $\congwf$ by \cref{lem:blah} and the remark before it.

\begin{figure}[!ht]
\centering
\includegraphics[width=0.8\linewidth]{wf_classes.pdf}
\caption{Shapes of equivalence classes for $\red(21543)$}
\label{fig:wf_classes}
\end{figure}

We are ready to make \cref{th:forest_properties}\emph{\ref{it1}} explicit.
\begin{thm}
\label{th:schub_into_forest}
Fix a permutation $w$. Let $\red(w^{-1})/_{\congwf}$ denote the set of WF-equivalence classes decomposing $\red(w^{-1})$, and let $\wfclass_1$ through $\wfclass_k$ be those satisfying $\supp(\wfclass_i)\subset \bZ_{>0}$.
Then
\begin{equation}
\label{eq:schub_into_forest}
\schub_w=\sum_{1\leq i\leq k}\forest_{\sh(\wfclass_i)}.
\end{equation}
\end{thm}


\begin{proof}[Proof (sketch)]
By definition of $\schub_w$, it equals the sum over $\wfclass\in\red(w^{-1})/_{\congwf}$ of the polynomials $\forest(\wfclass)\coloneqq\sum_{W\in\wfclass}\slide(W)$.  It is easy to show that all terms $\slide(W)$ vanish in $\forest(\wfclass)$ when $\supp(\wfclass)\nsubseteq \bZ_{>0}$. Then a key lemma is to show that one always has $\forest(\wfclass)=\forest_{\sh(\wfclass)}$, which we omit in this abstract.
\end{proof}

%When $w$ is a Grassmannian permutation, the above theorem can be shown to specialize to the well-known expansion of Schur polynomials $s_\lambda$ into fundamental quasisymmetric polynomials $\funda_\alpha$.\medskip

We now return to our motivating question\textemdash{} describing $a_w$ combinatorially via \cref{th:aw_as_parking}.
 We call a WF-equivalence class $\wfclass$ a \emph{tree class} if $\sh(\wfclass)$ is an indexed tree $T$ supported on an initial interval $[n]$ for some $n$.
  Going back to \cref{fig:wf_classes}, we see that $\{\textcolor{blue}{1343},\textcolor{blue}{3143},\textcolor{blue}{3413}\}$ and $\{\textcolor{red}{3431}\}$ are tree classes, whereas $\{1434,4134,4314,4341\}$ is not.

\begin{proof}[Proof of \cref{th:aw_as_parking}]
\cref{th:schub_into_forest} gives us the expansion for $\schub_w$ into forest polynomials. Here $w$ is a permutation in $\sgrp_n$ of length $n-1$, which implies that any forest polynomial $\forest_F$ that appears in \eqref{eq:schub_into_forest} necessarily satisfies $|F|=n-1$ and $\lsupp(F)\subseteq [n]$. It follows from \cref{th:red_mod_qsym} that only forest polynomials indexed by trees with support $[n]$ survive when reducing modulo $\qsym_n^+$. We thus obtain
\[
\schub_w\!\mod \qsym_n^+=\sum_\wfclass\forest_{\sh(\wfclass)},
\]
where $\wfclass$ runs through tree classes in $\red(w^{-1})/_{\congwf}$. Now by \cref{th:ds_via_qsym} we know that
\[
a_w=\sum_\wfclass\forest_{\sh(\wfclass)}(1,\ldots,1).
\]

\cref{pro:all_1s_tree} says that each summand $\forest_{\sh(\wfclass)}(1,\ldots,1)$ equals $|\wfclass|$, so we have that $a_w$ is the number of words in $\red(w^{-1})$ belonging to a tree class.

To conclude, one needs to compare the recursive descriptions of the WF-parking procedure and the WF-correspondence. A careful analysis shows that the former is but a ``shadow'' of the latter, and the set $I(v_1\cdots v_k)$ at the end of the WF-parking procedure is exactly the common support of $\psymb(v_1\cdots v_k)$ and $\qsymb(v_1\cdots v_k)$.

In particular a word in $\bZ^*$ belongs to a tree class if and only if it is a WF-parking word, which completes the proof.
\end{proof}

\section{Other applications}

We have defined several notions in this work in order to solve a particular problem, but these notions are of independent interest. We close with a non-exhaustive list of some notable properties.
\begin{itemize}[noitemsep,nolistsep]
\item The strategy developed to determine $a_w$ can be used to compute the DS of other polynomials. It can for instance give automatically a combinatorial interpretation for the remixed Eulerian numbers introduced in~\cite{NTc}.
\item  Forest polynomials enjoy a positive multiplication rule which can be determined combinatorially via the WF-correspondence.
\item The WF-correspondence and WF-parking deserve further study.
For instance, while the combinatorial interpretation in \cref{th:aw_as_parking} implies several of the results from~\cite{NT20}, it is not obvious to the authors why $a_w=a_{w^{-1}}$ , though this is indeed known to hold ~[\emph{loc. cit.}, Proposition 5.1.1].
\end{itemize}


\printbibliography



\end{document}
