%% 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]{FPSAC2024}
\articlenumber{63}
%% 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[backend=bibtex]{biblatex}
\addbibresource{lascoux.bib}

\usepackage{mathrsfs}
\usepackage[all]{xy}
\usepackage{todonotes}
\usepackage{wrapfig}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{statement}[theorem]{Statement}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{designation}[theorem]{Notation}
\newtheorem{claim}[theorem]{Claim}



\newcommand{\cC}{\mathcal{C}}
\newcommand{\cEP}{\mathcal{EP}}
\newcommand{\cL}{\mathscr{L}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}



\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\rk}{rk}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\Ker}{Ker}


\theoremstyle{remark}

\newtheorem{remark}[theorem]{Remark}


\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{construction}[theorem]{Construction}

%\usepackage{showlabels}

%% define your title in the usual way
\title[Lascoux polynomials and Gelfand--Zetlin patterns]{Lascoux polynomials and Gelfand--Zetlin patterns}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Ekaterina Presnova\thanks{\href{epresnova@hse.ru}{epresnova@hse.ru}, \href{ekaterina.presnova@gmail.com}{ekaterina.presnova@gmail.com}}\addressmark{1} \and Evgeny Smirnov\thanks{\href{esmirnov@hse.ru}{esmirnov@hse.ru}, \href{evgeny.smirnov@gmail.com}{evgeny.smirnov@gmail.com}. Evgeny Smirnov was partially supported  by the Russian Science Foundation, grant no.~22-41-02028.}\addressmark{1}\addressmark{2}\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}HSE University, Russia \\ \addressmark{2}Independent University of Moscow, Russia\\
\addressmark{3}Guangdong Technion -- Israel Institute of Technology, China}

%% put the date of submission here
\received{November 15, 2023}

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

%% 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 new combinatorial description for Lascoux polynomials and for symmetric Grothendieck polynomials in terms of cellular decompositions of Gelfand--Zetlin polytopes. This generalizes a similar result on key polynomials by Kiritchenko, Smirnov, and Timorin. }

%% put your French abstract here, or comment this out if you don't have one
%\resume{A paraitre ici}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Lascoux polynomials, key polynomials, Gelfand--Zetlin polytopes}

%% 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{lascoux.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}

In this paper, we provide a new combinatorial description of Lascoux polynomials in terms of subdivisions of Gelfand--Zetlin polytopes and certain collections of their faces. Lascoux polynomials, denoted by $\cL_\alpha^{(\beta)}$, form a basis for $\ZZ[\beta][x_1,x_2,\dots]$, where $\alpha$ runs over the set of weak compositions  (i.e., infinite sequences of nonnegative integers with finitely many positive entries). They simultaneously generalize key polynomials and Grassmannian Grothendieck polynomials; the latter family represents classes of structure sheaves of Schubert varieties in the connective $K$-theory of a Grassmannian, as shown by A.\,Buch~\cite{Buch02}. Both of these families are superfamilies of Schur polynomials.

Lascoux polynomials were defined by A.\,Lascoux~\cite{Lascoux04} in terms of homogeneous divided difference operators; just as many other families of polynomials defined using these operators, they have nonnegative coefficients. Although Lascoux polynomials do not have a description in geometric or representation-theoretic terms, they admit several combinatorial descriptions: for example, T.\,Yu~\cite{Yu21} provides a description of Lascoux polynomials in terms of set-valued tableaux, generalizing simultaneously Buch's description of symmetric Grothendieck polynomials in terms of set-valued Young tableaux and A.\,Lascoux and M.-P.\,Sch\"utzenberger's tableau formula for key polynomials~(\cite{LascouxSchutzenberger90}). 


Lascoux polynomials $\cL_\alpha^{(\beta)}$ specialized at $\beta=0$ are equal to key polynomials. Suppose $w\in S_n$ is a permutation such that $\alpha=(\alpha_1,\dots,\alpha_n)=w(\lambda)$ for a suitable partition $\lambda=(\lambda_1,\dots,\lambda_n)$. The key polynomials $\kappa_\alpha=\kappa_{w,\lambda}$ are defined as the characters of Demazure modules $D_{w,\lambda}$, i.e. $B$-submodules in the irreducible $\GL(n)$-representation $V_\lambda$ with the highest weight $\lambda$. The module $D_{w,\lambda}$ is defined as the smallest $B$-submodule containing the extremal vector $wv_\lambda\in V_\lambda$, where $B\subset \mathrm{GL}(n)$ is a fixed Borel subgroup. A character formula for Demazure modules was stated in \cite{Demazure74} and proved by H.\,H.\,Andersen in~\cite{Andersen85} (the original proof by M.\,Demazure contained a gap). The first combinatorial description of these characters was given in~\cite{LascouxSchutzenberger90}.

In~\cite{KST}, V.\,Kiritchenko, E.\,Smirnov, and V.\,Timorin provide a formula for key polynomials in terms of integer points in Gelfand--Zetlin polytopes. Let $\lambda$ be a strictly dominant weight for $\GL(n)$; then it defines an integer convex polytope $GZ(\lambda)\subset \RR^{n(n-1)/2}$, called the Gelfand--Zetlin polytope. This polytope admits a projection $\pi\colon GZ(\lambda)\to \wt(\lambda)$ into the weight polytope of $V_\lambda$. For each permutation $w\in S_n$, one can construct a collection of faces $F_{w,\lambda}$ of $GZ(\lambda)$, such that $\kappa_{w,\lambda}=\sum \exp(\pi(z))$, where $z$ ranges over the set of integer points in $F_{w,\lambda}$ (see \cite[Corollary~5.2]{KST}).

The main purpose of this paper is to generalize this result, constructing a combinatorial description of symmetric Grothendieck and Lascoux polynomials in terms of subdivisions of Gelfand--Zetlin polytopes. For this we construct a cellular decomposition $\cC$ of $GZ(\lambda)$ whose 0-cells coincide with the integer points in $GZ(\lambda)$. Now, to each $i$-dimensional cell $C_i$ we assign a monomial $m(C_i)$ in $x_1,\dots,x_n$; for a 0-cell $z\in GZ(\lambda)$ we have $m(C_i)=\exp(\pi(z))$. Some cells correspond to the zero monomial. Our main result is as follows:
\[
\cL_{w,\lambda}^{(\beta)}=\sum_{C_i\in \cC\cap F_{w,\lambda}} \beta^i m(C_i),
\]
where the sum is taken over all cells situated inside the collection of faces $F_{w,\lambda}$.

Informally, the Lascoux polynomial $\cL_{w,\lambda}^{(\beta)}$ can be viewed as a ``weighted Euler characteristic'' of the subdivision $\cC\cap F_{w,\lambda}$ for the collection of faces $F_{w,\lambda}$. Namely, $i$-dimensional cells of this subdivision correspond to monomials of degree $i+\ell(w)$ with coefficient $\beta^i$ in front of them.

It would be very interesting to establish a bijection of our construction of cells indexing monomials in Lascoux polynomials with T.\,Yu's description in terms of set-valued tableaux. In particular, we expect the crystal operations on set-valued tableaux (see~\cite{Yu21}) to have a nice description in terms of Gelfand--Zetlin polynomials. However, we do not address these questions in this paper, leaving them as a subject of subsequent work. 

An extended exposition of the results presented in this note, with all proofs and further discussion, can be found in~\cite{PresnovaSmirnov24}.






\section{Preliminaries}

\subsection{Lascoux polynomials}\label{ssec:lascoux}

To define Lascoux polynomials, we need two families of operators: \emph{divided difference operators} $\partial_i$, with $1\leq i\leq n-1$, acting on the polynomial ring $\ZZ[x_1,\dots,x_n]$ and \emph{Demazure--Lascoux operators} $\pi_i^{(\beta)}$, again with $1\leq i\leq n-1$, acting on the ring $\ZZ[\beta,x_1,\dots,x_n]$ equipped with a formal parameter $\beta$. 


\begin{definition}\label{def:divdiff}
The $i$-th \emph{divided difference operator} $\partial_i$ acts on polynomial $f = f(x_1, x_2, \ldots)$ in the following way:
 $$
 \partial_i (f) = \frac{f - s_if}{x_i - x_{i+1}},
 $$
where $s_if$ is obtained from $f$ by permuting variables $x_i$ and $x_{i+1}$. 
\end{definition}

We consider operators $\pi_i^{(\beta)}$, that are modifications of divided differences operators.

\begin{definition}\label{def:demlascoux}
    \textit{The $i^{th}$ Demazure--Lascoux operator} $\pi_i^{(\beta)}$ acts on $f\in\mathbb{Z}[\beta][x_1, x_2, \ldots]$ in the following way:
$$
 \pi_i^{(\beta)}(f) = \partial_i(x_i f + \beta x_ix_{i+1}f ).
 $$
\end{definition}

 Let $\alpha = (\alpha_1, \alpha_2, \ldots)$ be an infinite sequence of nonnegative integers with finitely many positive entries.
 \begin{definition}\label{def:lascoux} \textit{The Lascoux polynomial $\mathscr{L}_{\alpha}^{(\beta)} \in \mathbb{Z}[\beta][x_1, x_2, \ldots]$ associated with $\alpha$} is defined by:
 \begin{equation*}
\mathscr{L}_{\alpha}^{(\beta)} = 
 \begin{cases}
   x^{\alpha} &\text{if $\alpha$ is a partition: $\alpha_1 \geq \alpha_{2} \geq \ldots$}\\
   \pi_i^{(\beta)} (\mathscr{L}_{s_i \alpha}^{(\beta)})&\text{otherwise, where $\alpha_i < \alpha_{i + 1}$}
 \end{cases}
\end{equation*}
\end{definition}
 Since the Demazure--Lascoux operators satisfy the braid relations, we can associate a Lascoux polynomial to partition $\lambda$ and permutation $w \in S_n$ in the following way:
 $$
 \mathscr{L}_{w, \lambda}^{(\beta)} = \pi_{i_k}^{(\beta)}\ldots\pi_{i_2}^{(\beta)}\pi_{i_1}^{(\beta)}(x^{\lambda}),
 $$
where $(s_{i_k},\ldots, s_{i_1})$ is a reduced word for permutation $w=s_{i_1}\ldots s_{i_k}$.


It is well-known (cf., for instance, \cite{Yu21}) that specializations of Lascoux polynomials provide other nice families of polynomials. Namely, taking $\beta=0$ gives key polynomials $\kappa_{w,\lambda}=\mathscr{L}_{w, \lambda}^{(\beta)}\mid_{\beta = 0}$. If we take the Lascoux polynomial of the longest permutation, we get a symmetric Grothendieck polynomial $G_{\lambda}^{(\beta)} = \mathscr{L}_{w_0, \lambda}^{(\beta)} = \pi_{w_0}^{(\beta)}(x^\lambda)$. Finally, taking these two specializations simultaneously gives us Schur polynomials: $S_{\lambda}=\kappa_{w_0, \lambda} = \pi_{w_0}^{(\beta)}(x^\lambda)|_{\beta = 0}$.

\subsection{Gelfand--Zetlin patterns}

Let $\lambda$ be a partition, i.e. a sequence of nonnegative integers $ \lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$. Consider the space $\RR^d$, where $d = \frac{n (n-1)}{2}$, with coordinates $y_{ij}$ indexed by pairs $(i, j)$ of positive integers satisfying $i + j \leq n$. The following triangular tableau 
\begin{equation}\label{eq:gz-tableau}
	\begin{matrix}
		\lambda_n && \lambda_{n-1}&& \lambda_{n-2}&&\dots &&\lambda_1\\
		& y_{11} && y_{12} && \dots && y_{1,n-1}\\
		&& y_{21}&& \dots && y_{2,n-2}\\
		&&& \ddots & \vdots &\reflectbox{$\ddots$}\\
		&&&&y_{n-1,1}
	\end{matrix}
\end{equation}
is called a \emph{Gelfand--Zetlin pattern}, if all $y_{ij}$ are integers, and every small triangle in this tableau satisfies inequalities $y_{i-1,j}\leq y_{i,j}\leq y_{i-1,j+1}$. Here we formally set $y_{0j}=\lambda_{n+1-j}$.

Gelfand--Zetlin patterns parametrize elements of the \emph{Gelfand--Zetlin basis} in the $\GL(n)$-module $V(\lambda)$ with highest weight $\lambda$ (see~\cite{GelfandZetlin50}). The number of such patterns for a fixed top row $\lambda$ can be computed using Weyl's dimension formula: 


\begin{figure}
\centering
	\begin{tikzpicture}% [scale = 0.9]
\draw [gray] (1.5, 4.5)  -- (1.5,0.5);
\draw (0,0) -- (0,2) -- (2,2) -- (0,0) -- (1.5,0.5) -- (3.5, 2.5) -- (3.5, 4.5) -- (2,2) -- (3.5,2.5) -- (3.5, 4.5)-- (1.5, 4.5) -- (0,2);
\draw (0,1) node[left]{$\lambda_1-\lambda_2$};
\draw (2.5,4.5) node[above]{$\lambda_1-\lambda_2$};
\draw (0.85, 0.2) node[below]{$\lambda_2-\lambda_3$};
\draw (3.5,3.5) node[right]{$\lambda_2-\lambda_3$};
\end{tikzpicture}
\caption{Gelfand--Zetlin polytope}\label{fig:fig1}
\end{figure}	
\[
\dim V(\lambda)=\prod_{i<j} \frac{\lambda_i-\lambda_j-i+j}{j-i}.
\]

\subsection{Gelfand--Zetlin polytopes}

 Gelfand--Zetlin patterns can be viewed as integer points in $\RR^{\frac{n(n-1)}2}$. The convex hull of these points is called a \emph{Gelfand--Zetlin polytope} and denoted $GZ(\lambda)$. It is easy to see that the set of integer points in $GZ(\lambda)$ gives us exactly the set of Gelfand--Zetlin patterns.


\begin{example} For $n=3$, the Gelfand--Zetlin polytope $GZ(\lambda)$ is defined in $\RR^3$ by the following inequalities: $\lambda_3\leq x\leq \lambda_2$, $\lambda_2\leq y\leq\lambda_1$, $x\leq z\leq y$. If all $\lambda_i$ are distinct, it is three-dimensional, as shown on Fig.~\ref{fig:fig1}.

\end{example}

\section{Enhanced Gelfand--Zetlin patterns}


\subsection{Construction of enhanced Gelfand--Zetlin patterns}\label{ssec:constr} 

In this section we define \emph{enhanced Gelfand--Zetlin patterns}, i.e. Gelfand--Zetlin patterns with some additional data, which we will call \emph{enhancement}. These data are of two kinds: first, some elements in a pattern may be encircled, and second, some pairs of neighbor elements in consecutive rows can be joined by an edge. 

Informally, the pattern without enhancement stands for the ``maximal'' point of the closure of the corresponding cell, i.e. the point with the largest sum of coordinates. 

\begin{definition}\label{def:enhanced} A Gelfand--Zetlin pattern with the top row $(\lambda_n,\dots,\lambda_1)$ with some entries marked by circles and with edges between certain neighboring entries is said to be an \emph{enhanced Gelfand--Zetlin patterns}, if these elements satisfy the following conditions:

\begin{enumerate}
	\item The numbers in the first row are encircled.
	
	\item The two entries joined by an edge must be equal, and the bottom entry should be encircled. The converse does not have to be true: two equal neighboring entries are not necessarily joined by an edge.
	

	\item If two neighboring entries in a row are joined by edges with an entry above them, they must also be joined with the entry below them, and vice versa. Pictorially:
\[
\xymatrixrowsep{1pc}\xymatrixcolsep{1pc}
\scalebox{0.7}{\xymatrix{ & *+[o][F.]{a} \ar@{-}[dl]\ar@{-}[dr]\\ *+[Fo]{a}&& *+[Fo]{a}\\ & *+[o][F.]{b}}}\qquad\text{or}\qquad
\scalebox{0.7}{\xymatrix{ & *+[o][F.]{b} \\  *+[o][F.]{a}&&  *+[o][F.]{a}\\ & *+[o][F]{a}\ar@{-}[ul]\ar@{-}[ur]}}\qquad\Rightarrow\qquad
\scalebox{0.7}{\xymatrix{ &  *+[o][F.]{a} \ar@{-}[dl]\ar@{-}[dr]\\  *+[o][F]{a}&&  *+[Fo]{a}\\ & *+[Fo]{a}\ar@{-}[ul]\ar@{-}[ur]}}.
\]
(a dotted circle around an entry means that it may be either encircled or not).

\item If two entries in the topmost row are equal, then the entry below them (which is equal to both of them) is encircled and connected to both of them by edges.

\item If $a<b$ and the pattern contains the following triangle: $\begin{smallmatrix} a&&b \\ &a
\end{smallmatrix}$, then 
there is an edge between the two $a$'s. 
Pictorially:
\[
\xymatrixrowsep{1pc}\xymatrixcolsep{1pc}
\scalebox{0.7}{\xymatrix{ *+[o][F.]{a} &&  *+[o][F.]{b}\\& *+[o][F.]{a}}}\qquad\Rightarrow\qquad \scalebox{0.7}{\xymatrix{ *+[o][F.]{a} &&  *+[o][F.]{b}\\& *+[Fo]{a}\ar@{-}[ul]}}
\] 

\item If $a<b$ and the pattern contains the following triangle: $\begin{smallmatrix}a && b\\ &b
\end{smallmatrix}$ with the bottom entry encircled, then there is an edge between the two $b$'s:
\[
\xymatrixrowsep{1pc}\xymatrixcolsep{1pc}
\scalebox{0.7}{\xymatrix{ *+[o][F.]{a} &&  *+[o][F.]{b}\\& *+[o][F]{b}}}\qquad\Rightarrow\qquad \scalebox{0.7}{\xymatrix{ *+[o][F.]{a} &&  *+[o][F.]{b}\\& *+[o][F]{b}\ar@{-}[ur]}}
\]


\item For a triangle $\begin{smallmatrix}
	a && a\\ &a
\end{smallmatrix}$: if the two top entries can be connected by a path of edges, the bottom entry should be encircled and connected with them.

\item\label{lastcondition} If in a triangle $\begin{smallmatrix}
	a && a\\ &a
\end{smallmatrix}$ the bottom entry is encircled, then it should be connected with at least one of them by an edge.

\end{enumerate}
We denote the set of all enhanced patterns with the first row $\lambda$ by $\cP(\lambda)$.
\end{definition}

\begin{example}\label{ex:dualkogan} The pattern
$\begin{smallmatrix} 0 && 1&& 2\\ &1&& 2\\ &&2\end{smallmatrix}$ has eight enhancements.
\[
\xymatrixrowsep{1pc}\xymatrixcolsep{1pc}
\scalebox{0.7}
{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& 1 &&2 \\
&&2}
}\qquad\qquad
\scalebox{0.7}
{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& *+[o][F]{1}\ar@{-}[ur]  &&2 \\
&&2}
}
\qquad\qquad
\scalebox{0.7}
{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& {1}  &&*+[o][F]{2}\ar@{-}[ur] \\
&&2}
}\qquad\qquad
\scalebox{0.7}
{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& {1}  && 2 \\
&&*+[o][F]{2}\ar@{-}[ur]}
}\]
\[
\xymatrixrowsep{1pc}\xymatrixcolsep{1pc}
\scalebox{0.7}{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& *+[o][F]{1}\ar@{-}[ur]  && *+[o][F]{2}\ar@{-}[ur] \\
&&2}
}\qquad\qquad
\scalebox{0.7}{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
&1 && *+[o][F]{2}\ar@{-}[ur] \\
&&*+[o][F]{2}\ar@{-}[ur]}
}\qquad\qquad
\scalebox{0.7}{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& *+[o][F]{1}\ar@{-}[ur]   && 2 \\
&&*+[o][F]{2}\ar@{-}[ur]}
}\qquad\qquad
\scalebox{0.7}{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& *+[o][F]{1}\ar@{-}[ur]  && *+[o][F]{2}\ar@{-}[ur] \\
&&*+[o][F]{2}\ar@{-}[ur]}
}
\]
\end{example}

\begin{example}\label{ex:nonsimple} The pattern $\begin{smallmatrix}0 &&1 && 2\\ &1&& 1\\ &&1\end{smallmatrix}$ has four enhancements. 
\[
\xymatrixrowsep{1pc}\xymatrixcolsep{1pc}
\scalebox{0.7}{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& 1  && *+[o][F]{1}\ar@{-}[ul] \\
&&1}
}
\qquad\qquad
\scalebox{0.7}{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& 1  && *+[o][F]{1}\ar@{-}[ul] \\
&&*+[o][F]{1}\ar@{-}[ul]}
}
\qquad\qquad
\scalebox{0.7}{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& 1  && *+[o][F]{1}\ar@{-}[ul] \\
&&*+[o][F]{1}\ar@{-}[ur]}
}
\qquad\qquad
\scalebox{0.7}{\xymatrix{
*+[o][F]{0} && *+[o][F]{1} && *+[o][F]{2}\\
& *+[o][F]{1}\ar@{-}[ur]  && *+[o][F]{1}\ar@{-}[ul] \\
&&*+[o][F]{1}\ar@{-}[ur]\ar@{-}[ul]}
}
\]
Note that according to Definition~\ref{def:enhanced}~(4), the last entry in the second row must be encircled and connected to the middle entry in the first row.
\end{example}

An enhanced pattern can be viewed as a graph (with marked vertices). Consider the connected components of this graph. 

\begin{lemma} The connected components of an enhanced Gelfand--Zetlin pattern satisfy the following:
\begin{enumerate}
	\item the entries in the topmost row belong to the same connected component if and only if they are equal;
	\item each connected component either has a unique highest vertex or contains one or more entries from the topmost row;
	\item all vertices in a connected component, possibly except the highest one, are encircled. In particular, the number of connected components is not less than the number of distinct $\lambda_i$'s plus the number of entries without circles.
\end{enumerate}
\end{lemma}

\begin{proof} This follows immediately from Definition~\ref{def:enhanced}.
\end{proof}

\begin{definition}\label{def:rankpattern}
	The \emph{rank} $\rk P$ of an enhanced pattern $P$ is the number of entries without circles.
\end{definition}

Now introduce the notion of a \emph{reduced enhanced pattern}.  Let us index the positions that may contain a NE-SW edge by simple reflections from $S_n$ as shown on Fig.~\ref{fig:dualkogan}. On each NE-SW edge  joining $y_{i,j}$ with $y_{i-1,j+1}$ in our pattern we write the corresponding simple reflection if the entries joined by this edge are equal to $y_{0,i+j}=\lambda_{n+1-i-j}$ (that is, are maximal possible on this diagonal). Then take the word formed by the letters on the edges read from bottom to top, from right to left. If this word is reduced, then the corresponding pattern $P$ is said to be reduced. Then denote the product by $w^-$. Given a reduced pattern $P$, define the permutation corresponding to $P$ as $w(P)=w_0w^-$.
\begin{figure}[h!]
\[
\begin{tikzpicture} [scale = 1.5]
    \filldraw (0,6) circle (1.5 pt);
    \filldraw (1,6) circle (1.5 pt);
    \filldraw (2,6) circle (1.5 pt);
    \filldraw (3,6) circle (1.5 pt);
    \filldraw (0.5,5.5) circle (1.5 pt);
    \filldraw (1.5,5.5) circle (1.5 pt);
    \filldraw (2.5,5.5) circle (1.5 pt);
    \filldraw (1,5) circle (1.5 pt);
    \filldraw (2,5) circle (1.5 pt);
    \filldraw (1.5,4.5) circle (1.5 pt);
    \draw[lightgray] (1.5, 4.5) -- (3,6);
    \draw[lightgray] (1,5) -- (2,6);
    \draw[lightgray] (0.5,5.5) -- (1,6);
    \draw (0.85,5.65) node {$s_3$};
    \draw (1.85,5.65) node {$s_2$};
    \draw (2.85,5.65) node {$s_1$};
    \draw (1.35,5.15) node {$s_3$};
    \draw (2.35,5.15) node {$s_2$};
    \draw (1.85,4.65) node {$s_3$};
\end{tikzpicture}
\]
	\caption{Assigning permutation to an enhanced pattern}
	\label{fig:dualkogan}
\end{figure}

\begin{example}
	All enhanced patterns  from Example~\ref{ex:dualkogan} except the seventh one are reduced. They correspond to the following permutations: $w_0=s_1s_2s_1=s_2s_1s_2$, $s_2s_1$, $s_1s_2$, $s_2s_1$, $s_1$, $s_2$,  $\mathrm{Id}$.
\end{example}

Finally, given a permutation $w\in W$, denote by $\cP(w,\lambda)$ the set of all reduced enhanced patterns $P$ from $\cP(\lambda)$ such that $w(P)\leq w$ in the Bruhat order. We will use this set of patterns later in Theorem~\ref{thm:kst}.


\subsection{Efficient enhanced patterns}

\begin{definition}\label{def:ineffpattern}
	A enhanced pattern $P$ is said to be \emph{inefficient} if it contains a triangle of the form $\begin{smallmatrix}a && a\\ &a
\end{smallmatrix}$ such that its bottom entry is not connected with the right one by an edge, and \emph{efficient} otherwise. The set of all efficient reduced enhanced patterns with the first row $\lambda$ is denoted by $\cP^+(\lambda)$. Like in the previous subsection, for a fixed $w\in S_n$ denote by $\cP^+(w,\lambda)$ the set of all efficient reduced enhanced patterns $P$ satisfying $w(P)\leq w$ in the Bruhat order.
\end{definition}


\begin{prop}\label{prop:zeroefficient} Every enhanced pattern of rank zero is efficient.
\end{prop}

\begin{proof}
Take an inefficient enhanced pattern $P$. This means that it contains a triangle of the form $\begin{smallmatrix}a && a\\ &a\end{smallmatrix}$ such that there is no edge between the bottom and the right entries. Definition~\ref{def:enhanced} implies that these two entries are contained in different connected components, both marked with the same number $a$. This means that at least one of these components contains a vertex without circle, so the rank of $P$ cannot be zero.
\end{proof}


Moreover, it turns out that for an efficient enhanced pattern, the edges provide redundant data. Namely, we have the following lemma.

\begin{lemma}\label{lem:redundant}
	The edges in an efficient enhanced pattern are uniquely determined by positions of encircled vertices.
\end{lemma}

\begin{proof} The conditions listed in Definition~\ref{def:enhanced} imply that positions of edges are defined by positions of encircled vertices in all cases except for case~(\ref{lastcondition}). In the latter case there are two possibilities of joining the bottom vertex in the triangle $\begin{smallmatrix}a&& a\\&a\end{smallmatrix}$ with one of its neighbors in the upper row, and only one of them defines an efficient pattern.
\end{proof}

For a reduced efficient enhanced GZ-pattern $P$, we assign to it a monomial $x^P$ in the following way. Let $S_i(P)$ be the sum of numbers in the $i$-th row of the pattern $P$, with $S_0(P)=\lambda_1+\dots+\lambda_n$, and let $D_i(P)$ stand for the number of entries without circles in the $i$-th row of $P$. Denote $d_{n+1-i}=d_{n+1-i}(P)=S_{i-1}(P)-S_i(P)+D_i(P)$. Then
\[
x^P=\beta^{\rk P}x_1^{d_1}\dots x_n^{d_n}. 
\]

\begin{example}  All enhanced GZ-patterns patterns in Example~\ref{ex:dualkogan} are efficient; the corresponding monomials are
\[
\beta^3x_1^2x_2^2x_3^2,\quad \beta^2 x_1^2x_2^2x_3,\quad \beta^2 x_1^2x_2^2x_3,\quad \beta^2 x_1^2x_2x_3^2,\quad\beta x_1^2x_2^2, \quad\beta x_1^2x_2x_3,\quad\beta x_1^2x_2x_3,\quad x_1^2x_2.
\]
In Example~\ref{ex:nonsimple}, the first two patterns are inefficient, and the second two correspond to $\beta x_1x_2x_3^2$ and $x_1x_2x_3$, respectively.
\end{example}


\section{Main results}



In this section we give the main results of this paper. We start with constructing a cellular decomposition for $GZ(\lambda)$. The cells are indexed by enhanced Gelfand--Zetlin patterns, and the set of $0$-dimensional cells is exactly the set of integer points in $GZ(\lambda)$. The second main result is as follows:  Lascoux polynomial $\cL^{(\beta)}_{w,\lambda}$ is equal to the sum of monomials corresponding to all efficient reduced enhanced patterns $P\in\cP^+(\lambda)$ such that $w(P)\leq w$ in the Bruhat order.


\subsection{Cellular decomposition of Gelfand--Zetlin polytopes}

Let $GZ(\lambda)\subset \RR^{\frac{n(n-1)}2}$ be a Gelfand--Zetlin polytope. In this section we construct its cellular decomposition, with cells indexed by enhanced Gelfand--Zetlin patterns.

\begin{construction}\label{def:cells} Let $P$ be an enhanced pattern with entries $a_{ij}$, and let $y\in GZ(\lambda)$ be a point with coordinates $y_{ij}$. To each coordinate $y_{ij}$ we assign an equality or a double inequality as follows:
\begin{enumerate}
	\item if there is an edge going up from $a_{ij}$ to $a_{i-1,j}$ or $a_{i-1,j+1}$ (or both), then $y_{ij}=y_{i-1,j}$ or $y_{ij}=y_{i-1,j+1}$, respectively;
	\item if there are no edges going up from $a_{ij}$, and this entry is encircled, then $y_{ij}=a_{ij}$;

	\item if there are no edges going up from $a_{ij}$ and this entry is not encircled, we impose a double inequality on $y_{ij}$ as follows:
 \begin{enumerate}
     \item If the entry $a_{i-1,j}$ satisfies $a_{ij}-a_{i-1,j}\geq 2$, then $a_{ij}-1<y_{ij}$; otherwise, $y_{i-1,j}<y_{ij}$;
     \item If $a_{i-1,j+1}$ is equal to $a_{ij}$, we set $y_{ij}<y_{i-1,j+1}$; otherwise, $y_{ij}<a_{ij}$.
 \end{enumerate}
\end{enumerate}
\end{construction}
Denote the set  defined by these equalities and inequalities by $\widehat{C_P}$. This is ``almost'' the required cell corresponding to $P$; however, it does not necessarily lie in $GZ(\lambda)$. To get an actual cell, take the affine span $L$ of $\widehat{C_P}$ and intersect $\widehat{C_P}$ with the relative interior of $GZ(\lambda)\cap L$ in $L$:
\[
C_P=\widehat{C_P}\cap (GZ(\lambda)\cap L)^0.
\]
This set is convex and open in $L$. 

Informally, the relation between an enhanced pattern $P$ and the corresponding set $C_P$ is as follows. For each connected component in $P$ containing only encircled entries with the same numbers, all the corresponding coordinates of points in $C_P$ are equal to this number. On the other hand, if a connected component has a non-encircled vertex, the corresponding coordinate can take values in an interval determined by the condition (4) of~Definition~\ref{def:enhanced}; note that the length of this interval does not exceed $i-1$, where $i$ is the row number. All the remaining coordinates in the same connected component (corresponding to encircled entries) are equal to this coordinate.


The first main result of this paper states that this is indeed a cellular decomposition of $GZ(\lambda)$.

\begin{theorem}\label{thm:celldecomp} For each $P\in\cP(\lambda)$, the set $C_P\subset GZ(\lambda)$ is homeomorphic to an open ball of dimension $\rk P$. These balls $C_P$ form a cellular decomposition of $GZ(\lambda)$ whose zero-dimensional cells coincide with $GZ(\lambda)\cap \ZZ^{\frac{n(n-1)}2}$.	
\end{theorem}

Moreover, this cellular decomposition is compatible with the Bruhat order on $S_n$. Namely, in~\cite{KST} the authors define a collection of special faces (called \emph{dual Kogan faces}) of $GZ(\lambda)$ for each $w\in S_n$. The following result holds. 

\begin{theorem}\label{thm:kst} Let $F_w$ be the set of dual Kogan faces of $GZ(\lambda)$ corresponding to $w$ in the sense of~\cite[Theorem 4.3]{KST}. Then we have
\[
F_w=\bigcup_{P\in\cP(w,\lambda)} \overline C_P.
\]
\end{theorem}

\subsection{Lascoux polynomials as sums over efficient enhanced patterns}

The following is the second main result of this paper.

\begin{theorem}\label{thm:main2}
Let $w \in S_n$ be a permutation and $\lambda$ be a partition. Then the Lascoux polynomial $\cL^{(\beta)}_{w,\lambda}$ is equal to
$$
\mathscr{L}_{w, \lambda}^{(\beta)} = \sum\limits_{P \in \cP^+(w,\lambda)}{x^P}.
$$
\end{theorem} 

The sum is taken over all efficient reduced enhanced patterns $P$ with $w(P)\leq w$.
In the case $w=w_0$ we get an expression for the symmetric Grothendieck polynomial:


\begin{corollary}\label{thm:main1}
Let $\lambda$ be a partition. Then the symmetric Grothendieck polynomial $G_{\lambda}^{(\beta)}(x_1,\dots,x_n)$ is equal to
$$
G_{\lambda}^{(\beta)}(x_1,\dots,x_n) = \mathscr{L}_{w_0, \lambda}^{(\beta)} = \sum\limits_{P \in \cP^+(\lambda)}{x^P}.
$$
\end{corollary}


The specialization of the equality from Theorem~\ref{thm:main2} gives an expression for key polynomials, obtained in~\cite{KST}:

\begin{theorem}[{\cite[Theorem 5.1]{KST}}]
	Let $w \in S_n$ be a permutation and $\lambda$ be a partition. Then the key polynomial $\kappa_{w,\lambda}$ is equal to
$$
\kappa_{w, \lambda} = \sum\limits_{P \in \cP^+(w,\lambda)}{x^P},
$$
where the sum is taken over efficient reduced enhanced patterns $P$ of rank 0.
\end{theorem} 


Another immediate corollary from Theorem~\ref{thm:main2}, to the best of our knowledge, did not appear in the literature before.

\begin{corollary}\label{cor:positive} Let $\lambda$ be a partition and $u,w \in S_n$  be permutations such that $u \leq w$ in the Bruhat order on $S_n$. Then the polynomial $\mathscr{L}_{w, \lambda}^{(\beta)}-\mathscr{L}_{u,\lambda}^{(\beta)}$ has nonnegative coefficients.
\end{corollary}




\subsection{Example: $GZ(3,2,0)$}\label{ssec:ex320}  Let $\lambda=(3,2,0)$. The Gelfand--Zetlin polytope $GZ(\lambda)$ with its cellular decomposition defined in Theorem~\ref{thm:celldecomp} is shown in Figure~\ref{fig:cell3dim} below. All cells except the two purple ones (one one-dimensional and one two-dimensional) are efficient.

Now let us establish the correspondence between permutations from $S_3$ and combinations of faces of this polytope. The identity permutation $\id$ corresponds to the vertex with the highest sum of coordinates (it is marked by a larger black dot in~Figure~\ref{fig:cell3dim}). The simple transpositions $s_1$ and $s_2$ correspond to the vertical and horizontal edges adjacent to this vertex, respectively. The cellular decompositions of these edges are shown in~Figure~\ref{fig:example1}.

 The permutation $s_1s_2$ corresponds to the back trapezoid face (shown by blue color in Figure~\ref{fig:example2}), while the permutation $s_2s_1$ corresponds to two faces, a triangular and a rectangular one, highlighted in green. Now, for each of these sets of faces, we need to take its cellular decomposition and compute the sum of all the monomials corresponding to the cells occurring in it; this would give us the Lascoux polynomials. The figures are self-explanatory;  the picture for the symmetric Grothendieck polynomial $\mathscr{L}_{s_1s_2s_1,\lambda}$ is too bulky, so we do not provide it here.

\begin{figure}[h]
%\hrule
  \begin{minipage}[b]{.35\textwidth}
\centering
 \begin{tikzpicture}[scale=0.7] 
\filldraw[magenta!15] (2,2) -- (2, 4) -- (4,4);


\draw (0,0) -- (0,4) -- (4, 4) -- (0,0) -- (1.5,0.5) --  (5.5,4.5) -- (5.5,6.5) -- (4, 4);
\draw (3.5,6.5) -- (3.5,2.5) -- (2,2) -- (2,4) -- (3.5,6.5) -- (5.5,6.5);
\draw (1.5,6.5) -- (1.5,0.5);
\draw (2, 4) -- (3.5, 4.5) -- (1.5, 4.5) -- (0, 4) -- (1.5, 6.5) -- (3.5, 6.5);
\draw (4, 4) -- (5.5, 4.5);
\draw (0, 2) -- (1.5, 2.5);

\draw [magenta, very thick] (2,2) -- (4, 4);

\filldraw [gray] (0,0) circle (3pt);
\filldraw [gray] (0,2) circle (3pt);
\filldraw [gray] (0,4) circle (3pt);
\filldraw [gray] (2,2) circle (3pt);
\filldraw [gray] (2,4) circle (3pt);
\filldraw [gray] (4,4) circle (3pt);
\filldraw [gray] (1.5,0.5) circle (3pt);
\filldraw [gray] (3.5,2.5) circle (3pt);
\filldraw [gray] (5.5,4.5) circle (3pt);
\filldraw [black] (5.5,6.5) circle (4pt);
\filldraw [gray] (3.5,6.5) circle (3pt);
\filldraw [gray] (1.5,6.5) circle (3pt);
\filldraw [gray] (1.5,4.5) circle (3pt);
\filldraw [gray] (1.5,2.5) circle (3pt);
\filldraw [gray] (3.5,4.5) circle (3pt);
\end{tikzpicture}
    \caption{Cellular decomposition of $GZ(3,2,0)$}
    \label{fig:cell3dim}
  \end{minipage}\hfil
\begin{minipage}[b]{.65\textwidth}
\centering
 	\begin{tikzpicture} [scale = 0.8]

\filldraw [black] (0,0) circle (3pt);
\draw (0,0) node [above]{$ x_1^3 x_2^2$};
\draw (0, -2) node {\text{$\mathscr{L}_{\id, \lambda}x$}};


\draw (3,-1) -- (3,1);
\filldraw [gray] (3,-1) circle (3pt);
\filldraw [black] (3,1) circle (3pt);
\draw (3,-1) node [right]{$ x_1^2 x_2^3$};
\draw (3,1) node [right]{$ x_1^3 x_2^2$};
\draw (3,0) node [right]{$ \beta x_1^3 x_2^3$};
\draw (3, -2) node {\text{$\mathscr{L}_{s_1, \lambda}$}};


\draw (6,0) node[above] {$ x_1^3 x_3^2$}-- node[below] {$ \beta x_1^3 x_2 x_3^2$}(8,0) node[above] {$ x_1^3 x_2 x_3$}-- node[below] {$\beta x_1^3 x_2^2x_3$}(10, 0)node[above] {$ x_1^3 x_2^2$};
\filldraw [gray] (6,0) circle (3pt);
\filldraw [gray] (8,0) circle (3pt);
\filldraw [black] (10,0) circle (3pt);
\draw (8, -2) node {\text{$\mathscr{L}_{s_2, \lambda}$}};

\end{tikzpicture}
\caption{Lascoux polynomials for $\id$, $s_1$, and $s_2$}\label{fig:example1}
\vspace{1.4cm}
\end{minipage}
\end{figure}


\begin{figure}[h!]
	
\begin{tikzpicture}[scale=0.9]

\filldraw [blue!5] (10.75, 5.25) -- (10.75, 8.25) -- (12.75, 8.25) -- (12.75, 7.25);
\filldraw [teal!10] (10.75, 8.25) -- (10,7) -- (10.75, 7);

\filldraw [teal!95!blue!15](10.75, 8.25) -- (10.75, 7) -- (12,7) -- (12.75, 7.25)  -- (12.75, 8.25);

\draw [NavyBlue!50!,  dashed] (11.75, 6.25) -- (11.75, 8.25) ;
\draw [NavyBlue!50!,  dashed] (10.75, 7.25) -- (11.75, 7.25);
\draw [PineGreen,dotted, very thick] (11.75, 8.25) -- (11, 7);

\draw (10,5) -- (10, 7) -- (12,7) -- (10,5) -- (10.75, 5.25) -- (12.75, 7.25) -- (12,7) -- (12.75, 7.25) -- (12.75, 8.25) -- (10.75, 8.25)  -- (10.75, 5.25) -- (10,5) -- (10, 7) -- (10.75, 8.25) -- (12.75, 8.25)-- (12,7);

\filldraw[black] (12.75, 8.25) circle (2pt);


\scriptsize

\filldraw [blue!5] (0,0) -- (0,6) -- (4,6) -- (4,4);

\draw[dashed, gray, ->] (0, 7) node [above][black] {$\beta^2 x_1^3 x_2^2 x_3^2$} -- (1, 5);
\draw[dashed, gray, ->] (4, 7) node [above][black] {$\beta^2 x_1^3 x_2^3 x_3$} -- (3, 5);
\draw[dashed, gray, ->] (3, 0) node [right][black] {$\beta^2 x_1^2 x_2^3 x_3^2$} -- (1, 2);

\draw (0,6) node [left = 2pt] {$x_1^3x_3^2$}--node [left  = 2pt] {$\beta x_1^3x_2x_3^2$}
    (0,4) node [left  = 2pt] {$x_1^2x_2x_3^2$}--node [left  = 2pt] {$\beta x_1^2x_2^2x_3^2$}
    (0,2) node [left  = 2pt] {$x_1x_2^2x_3^2$}--node [left = 2pt] {$\beta x_1x_2^3x_3^2$}
    (0,0) node [left  = 2pt] {$x_2^3x_3^2$};

\draw (2,6) node [above] {$x_1^3x_2x_3$}--node [above, sloped] {$\beta x_1^3x_2^2x_3$}
    (2,4) node [right = 2pt] {$x_1^2x_2^2x_3$}--node[above, sloped]{$\beta x_1^2x_2^3x_3$}
    (2,2) node [below = 2pt, rotate = 45] {$x_1x_2^3x_3$};

\draw (4,6) node [right = 2pt, NavyBlue] {$x_1^3x_2^2$}--node [right = 2pt] {$\beta x_1^3x_2^3$}
    (4,4) node [right = 2pt] {$x_1^2x_2^3$};

\draw (0, 0) -- node[below, sloped]{$\beta x_1x_2^3x_3^2$} (2, 2) -- node[below, sloped]{$\beta x_1^2x_2^3x_3$} (4, 4);

\draw (0, 4) -- node [below] {$\beta x_1^2x_2^2x_3^2$} (2, 4);

\draw (4, 6) -- node [below = 2pt] {$\beta x_1^3x_2^2x_3$} 
      (2, 6) -- node [below = 2pt] {$\beta x_1^3x_2x_3^2$}
      (0,6);

    


\filldraw [NavyBlue](4,6)  circle (3pt);
\filldraw [gray] (4,4) circle (3pt);
\filldraw [NavyBlue](2,6) circle (3pt);
\filldraw [gray] (2,4) circle (3pt);
\filldraw [gray] (2,2) circle (3pt);
\filldraw [NavyBlue] (0,6) circle (3pt);
\filldraw [gray] (0,2) circle (3pt);
\filldraw [gray] (0,4) circle (3pt);
\filldraw [gray] (0,0) circle (3pt);
\draw [NavyBlue][very thick] (0,6) -- (4,6);




\filldraw [teal!10] (7,0) -- (9,2) -- (13,2) -- (13, 0);
\draw[dashed, gray, ->] (9, 3.5) node [above][black] {$\beta^2 x_1^3 x_2^2x_3^2$} -- (11, 1);
\draw[dashed, gray, ->] (12, 3.5) node [above][black] {$\beta^2 x_1^3 x_2^3 x_3$} -- (12.5, 1);
\draw[dashed, gray, ->] (6.5,2) node [left][black] {$\beta^2 x_1^3 x_2 x_3^3$} -- (9, 1);

\draw (13, 0) node [below] {$x_1^2x_2^3$} -- node [above] {$\beta x_1^2x_2^3x_3$} 
      (11, 0) node [below] {$x_1^2x_2^2x_3$} -- node [above] {$\beta x_1^2x_2^2x_3^2$}
      (9, 0) node [below] {$x_1^2x_2x_3^2$} -- node [above] {$\beta x_1^2x_2x_3^3$} 
      (7, 0) node [below] {$x_1^2x_3^3$};

\draw (13, 2) node [above = 2pt, PineGreen] {$x_1^3x_2^2$} -- node [below] {$\beta x_1^3x_2^2x_3$} 
      (11, 2) node [above = 2pt ]  {$x_1^3x_2x_3$} -- node [below] {$\beta x_1^3x_2x_3^2$}
      (9, 2) node [above = 2pt ] {$x_1^3x_3^2$};

\draw (13, 2) -- node [above, sloped, pos=0.6] {$\beta x_1^3x_2^2x_3$} (11, 0);
\draw (11, 2) -- node [above, sloped, pos=0.6] {$\beta x_1^3x_2x_3^2$} (9, 0);
\draw (9, 2) -- node [above, sloped, pos=0.6] {$\beta x_1^3x_3^3$} (7, 0);
\draw (13, 2) -- node [right]{$\beta x_1^3x_2^3$}(13, 0);

\filldraw [PineGreen] (13,0) circle (3pt);
\filldraw [gray] (9,0) circle (3pt);
\filldraw [gray] (11,0) circle (3pt);
\filldraw [PineGreen] (13,2) circle (3pt);
\filldraw [gray] (9,2) circle (3pt);
\filldraw [gray] (11,2) circle (3pt);
\filldraw [gray] (7,0) circle (3pt);
\draw [PineGreen] [very thick] (13,0) -- (13, 2);

\normalsize

\end{tikzpicture}

\caption{Lascoux polynomials for $s_1s_2$ and $s_2s_1$}\label{fig:example2}
\end{figure}

\acknowledgements{We are grateful to Valentina Kiritchenko for useful discussions.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way


\printbibliography



\end{document}
