%% 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]{FPSAC2021}
\articlenumber{46}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
\usepackage{mathbbol,amsfonts, amscd, mathrsfs,tikz}
%% note that the class file already loads {amsmath, amsthm, amssymb}

%%*****************New Commands*************************************
\newcommand{\RR}{\mathbb{F}}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\bFF}{\mathbb{F}}
\newcommand{\bff}{\mathbb{f}}
\newcommand{\GG}{\mathcal{G}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\bgg}{\mathbb{g}}
\newcommand{\bGG}{\mathbb{G}}
\newcommand{\bmm}{\mathbb{M}}
\newcommand{\obmm}{{\overline{\bmm}}}
\newcommand{\NN}{\normalfont\mathbb{N}}
\newcommand{\ZZ}{\normalfont\mathbb{Z}}
\newcommand{\ZZC}{\normalfont\mathcal{Z}}
\newcommand{\MM}{{\normalfont\mathfrak{M}}}
\newcommand{\PP}{{\normalfont\mathbb{P}}}
\newcommand{\xx}{{\normalfont\mathbf{x}}}
\newcommand{\XX}{{\normalfont\mathbf{X}}}
\newcommand{\bXX}{{\normalfont\mathbb{X}}}
\newcommand{\bYY}{{\normalfont\mathbb{Y}}}
\newcommand{\yy}{\normalfont\mathbf{y}}
\newcommand{\dd}{{\normalfont\mathbf{d}}}
\newcommand{\ara}{{\normalfont\text{ara}}}
\newcommand{\cc}{\normalfont\mathbf{c}}
\newcommand{\mm}{{\normalfont\mathfrak{m}}}
\newcommand{\xy}{(x_0,x_1)}
\newcommand{\SSS}{\widetilde{S}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\pp}{{\normalfont\mathfrak{p}}}
\newcommand{\aaa}{\mathfrak{a}}
\newcommand{\bbb}{\mathfrak{b}}
\newcommand{\qqq}{\normalfont\mathfrak{q}}
\newcommand{\nn}{{\normalfont\mathfrak{N}}}
\newcommand{\bn}{{\normalfont\mathbf{n}}}

\newcommand{\bx}{{\normalfont\mathbf{x}}}
\newcommand{\bz}{{\normalfont\mathbf{z}}}
\newcommand{\bk}{{\normalfont\mathbf{k}}}
\newcommand{\bm}{{\normalfont\mathbf{m}}}
\newcommand{\ttt}{{\normalfont\mathbf{t}}}
\newcommand{\nnn}{{\normalfont\mathfrak{n}}}
\newcommand{\fP}{{\mathfrak{P}}}
\newcommand{\fJ}{{\mathfrak{J}}}
\newcommand{\fL}{{\mathfrak{L}}}
\newcommand{\fI}{{\mathfrak{I}}}
\newcommand{\fK}{{\mathfrak{K}}}
\newcommand{\fS}{{\mathfrak{S}}}
\newcommand{\fT}{{\mathfrak{T}}}
\newcommand{\rank}{\normalfont\text{rank}}
\newcommand{\reg}{\normalfont\text{reg}}
\newcommand{\sat}{{\normalfont\text{sat}}}
%\newcommand{\ht}{{\normalfont\text{height}}}
\newcommand{\depth}{\normalfont\text{depth}}
\newcommand{\grade}{\normalfont\text{grade}}
\newcommand{\spn}{\normalfont\text{Span}}
\newcommand{\codim}{\normalfont\text{codim}}
\newcommand{\conv}{\normalfont\text{conv}}
\newcommand{\Tor}{{\normalfont\text{Tor}}}
\newcommand{\sdim}{{\normalfont\text{sdim}}}
\newcommand{\Ext}{\normalfont\text{Ext}}
\newcommand{\pd}{\normalfont\text{pd}}
\newcommand{\Ker}{\normalfont\text{Ker}}
\newcommand{\Coker}{\normalfont\text{Coker}}
\newcommand{\Quot}{\normalfont\text{Quot}}
\newcommand{\IM}{\normalfont\text{Im}}
\newcommand{\HT}{\normalfont\text{ht}}
\newcommand{\Syz}{\normalfont\text{Syz}}
\newcommand{\II}{\normalfont\hat{I}}
\newcommand{\Ann}{\normalfont\text{Ann}}
\newcommand{\Supp}{\normalfont\text{Supp}}
\newcommand{\Ass}{{\normalfont\text{Ass}}}
\newcommand{\sym}{{\normalfont\text{Sym}}}
\newcommand{\Min}{{\normalfont\text{Min}}}
\newcommand{\Sym}{\normalfont\text{Sym}}
\newcommand{\Rees}{\mathcal{R}}
\newcommand{\extRees}{\widetilde{\Rees}}
\newcommand{\ee}{{\normalfont\mathbf{e}}}
\newcommand{\Hom}{\normalfont\text{Hom}}
\newcommand{\grHom}{{}^*\Hom}
\newcommand{\Fitt}{\normalfont\text{Fitt}}
\newcommand{\sF}{\widetilde{\mathfrak{F}}}
\newcommand{\EEQ}{\mathcal{K}}
\newcommand{\JJ}{\mathcal{J}}
\newcommand{\REQ}{\mathcal{I}}
\newcommand{\BB}{\mathfrak{B}}
\newcommand{\bbA}{\mathbb{A}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\DD}{\mathbb{D}}
\newcommand{\bbH}{\mathbb{H}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\mO}{\mathscr{O}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\LL}{\mathbb{L}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\SE}{\mathcal{S}}
\newcommand{\Cc}{\mathcal{C}}
\newcommand{\FF}{\normalfont\mathcal{F}}
\newcommand{\HL}{\normalfont\text{H}_{\mm}}
\newcommand{\HH}{\normalfont\text{H}}
\newcommand{\bBB}{\normalfont\text{B}}
\newcommand{\zZZ}{\normalfont\text{Z}}
\newcommand{\cCC}{\normalfont\text{C}}
\newcommand{\Hdr}{\normalfont\text{H}_{\text{dR}}}
\newcommand{\gr}{{\normalfont\text{gr}}}
\newcommand{\Sol}{\normalfont\text{Sol}}
\newcommand{\TwistSol}{{\Sol(L_1,L_2;S)}_{\Fou}}
\newcommand{\AAA}{\mathfrak{A}}
\newcommand{\iniTerm}{\normalfont\text{in}}
\newcommand{\indeg}{\normalfont\text{indeg}}
\newcommand{\bideg}{\normalfont\text{bideg}}
\newcommand{\Proj}{\normalfont\text{Proj}}
\newcommand{\Hilb}{{\normalfont\text{Hilb}}}
\newcommand{\Spec}{\normalfont\text{Spec}}
\newcommand{\Diff}{{\normalfont\text{Diff}}}
\newcommand{\DiffR}{\Diff_{R/A}}
\newcommand{\Diag}{\Delta_{R/A}}
\newcommand{\Princ}{P_{R/A}}
\newcommand{\MaxSpec}{\normalfont\text{MaxSpec}}
\newcommand{\multProj}{\normalfont\text{MultiProj}}
\newcommand{\msupp}{\normalfont\text{MSupp}}
\newcommand{\biProj}{{\normalfont\text{BiProj}}}
\newcommand{\Rat}{\mathfrak{R}}
\newcommand{\gldim}{{\normalfont\text{gldim}}}
\newcommand{\LCAT}{\M_U^l(\T)}
\newcommand{\RCAT}{\M_U^r(\T)}
\newcommand{\xvars}[1]{x_{#1,0}, x_{#1,1},\ldots,x_{#1,r_{#1}}}
\newcommand{\Sylv}{{\mathcal{S}\textit{ylv}}_{(x_0,x_1)}(\varphi)}
\newcommand{\fib}{\mathfrak{F}}
\newcommand{\sfib}{\widetilde{\mathfrak{F}_R(I)}}
\newcommand{\fX}{\mathfrak{X}}
%\newcommand{\sfib}[1]{\widetilde{\mathfrak{F}_{#1}}}
%-- double arrows
\newcommand{\rightarrowdbl}{\rightarrow\mathrel{\mkern-14mu}\rightarrow}
\newcommand{\xrightarrowdbl}[2][]{%
	\xrightarrow[#1]{#2}\mathrel{\mkern-14mu}\rightarrow
}
%%***********************************************************************




\def\fu{\mathbf{u}}
\def\f0{\mathbf{0}}
\def\fone{\mathbf{1}}
\def\fe{\mathbf{e}}
\def\fw{\mathbf{w}}
\def\fv{\mathbf{v}}
\def\fx{\mathbf{x}}
\def\fs{\mathbf{s}}
\def\fb{\mathbf{b}}
\def\fc{\mathbf{c}}
\def\fp{\mathbf{p}}
\def\fq{\mathbf{q}}
\def\fa{\mathbf{a}}
\def\fe{\mathbf{e}}
\def\fal{\mathbf{\alpha}}
\def\fn{\mathbf{n}}

\def\ls{\leqslant}
\def\gs{\geqslant}
\def\lra{\longrightarrow}
\def\ll{\lambda}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{proposition}[theorem]{Proposition}


%%***********************************************************************


%% define your title in the usual way
\title[Multidegrees]{When are multidegrees positive?}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Federico Castillo\thanks{\href{mailto:castillo@mis.mpg.de}{castillo@mis.mpg.de}.}\addressmark{1}, Yairon Cid-Ruiz\thanks{\href{mailto:cidruiz@mis.mpg.de}{cidruiz@mis.mpg.de}.}\addressmark{2},
Binglin Li\thanks{\href{mailto:binglinligeometry@uga.edu}{binglinligeometry@uga.edu}.}\addressmark{3},
Jonathan Monta\~no\thanks{\href{mailto:jmon@nmsu.edu}{jmon@nmsu.edu} The fourth author is supported by NSF Grant DMS \#2001645..}\addressmark{4}, \and
Naizhen Zhang\thanks{\href{mailto:naizhen.zhang@math.uni-hannover.de}{naizhen.zhang@math.uni-hannover.de}.}\addressmark{5}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Max Planck Institute for Mathematics in the Sciences \\
\addressmark{2}Ghent University, Algebra Research Group. \\
\addressmark{3}Department of Statistics, University of Georgia\\
\addressmark{4}Department of Mathematical Sciences, New Mexico State University\\
\addressmark{5}Institut f\"ur Differentialgeometrie, Leibniz Universit\"at Hannover,\\
}

%% 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{Let $\mathbf{k}$ be an arbitrary field, $\mathbb{P} = \mathbb{P}_\kk^{m_1} \times_\kk \cdots \times_\kk \mathbb{P}_\kk^{m_p}$ be a multiprojective space over $\kk$, and $X \subseteq \mathbb{P}$ be a closed subscheme of $\mathbb{P}$.
	We provide necessary and sufficient conditions for the positivity of the multidegrees of $X$.  
	As a consequence of our methods, we show that when $X$ is irreducible, the support of multidegrees forms a discrete algebraic polymatroid. 
	In  algebraic terms, we characterize the positivity of the mixed multiplicities of  a standard multigraded algebra over an Artinian local ring, and we apply this  to the positivity of  mixed multiplicities of ideals. 
	Furthermore, we  use our results to recover several results in the literature in the context of combinatorial algebraic geometry. }

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{positivity, multidegrees, mixed multiplicities, multiprojective scheme, projections, polymatroids, Hilbert polynomial}

%% 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, ie. [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{46Castillo.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}

Let $\kk$ be an arbitrary field, $\PP = \PP_\kk^{m_1} \times_\kk \cdots \times_\kk \PP_\kk^{m_p}$ be a multiprojective space over $\kk$, and $X \subseteq \PP$ be a closed subscheme of $\PP$.
The \emph{multidegrees} of $X$ are fundamental invariants that describe %many 
algebraic and geometric properties of $X$.
For each $\bn=(n_1,\ldots,n_p) \in \NN^p$ with $n_1+\cdots+n_p=\dim(X)$  one can define the \textit{multidegree of $X$ of type $\bn$ with respect to $\PP$}, denoted by $\deg_\PP^\bn(X)$, in different ways. In classical geometrical terms, when $\kk$ is algebraically closed, $\deg_\PP^\bn(X)$ equals the number of points (counting multiplicity) in the intersection of $X$ with the product $L_1 \times_\kk \cdots \times_\kk L_p  \subset \PP$, where $L_i \subset \PP_\kk^{m_i}$ is a general linear subspace of dimension $m_i-n_i$ for each $1 \le i \le p$.

\medskip

The study of multidegrees goes back to pioneering work by van~der~Waerden \cite{VAN_DER_WAERDEN}.
From a more algebraic point of view, multidegrees receive the name of \emph{mixed multiplicities}. 
More recent papers where the notion of multidegree (or mixed multiplicity) is studied are, e.g.,  \cite{Bhattacharya,VERMA_BIGRAD,HERMANN_MULTIGRAD,TRUNG_POSITIVE,MIXED_MULT, EXPONENTIAL_VARIETIES,KNUTSON_MILLER, michalek2020maximum, CONCA_DENEGRI_GORLA}. 

\medskip

The main goal of this paper is to answer the following fundamental question considered by Trung \cite{TRUNG_POSITIVE} and by Huh \cite{Huh12} in the case $p=2$.
\begin{itemize}
	\item \emph{For $\bn \in \NN^p$ with $n_1+\cdots+n_p=\dim(X)$, when do we have that $\deg_\PP^\bn(X) >0$?}
\end{itemize}
Our main result says that the positivity of $\deg_\PP^\bn(X)$ is determined by the dimensions of the images of the natural projections from $\PP$ restricted to the irreducible components of $X$.
First, we set a basic notation: for each $\fJ = \{j_1,\ldots,j_k\} \subseteq \{1,\ldots,p\}$, let $\Pi_\fJ$ be the natural projection 
$$
\Pi_\fJ: \PP = \PP_\kk^{m_1} \times_\kk \cdots \times_\kk \PP_\kk^{m_p} \;\rightarrow\; \PP_\kk^{m_{j_1}} \times_\kk \cdots \times_\kk \PP_\kk^{m_{j_k}}.
$$
The following is the main theorem of this article. Here, we give necessary and sufficient conditions for the positivity of multidegrees. 


\begin{theorem}
	\label{thmA}
	Let $\kk$ be an arbitrary field, $\PP = \PP_\kk^{m_1} \times_\kk \cdots \times_\kk \PP_\kk^{m_p}$ be a multiprojective space over $\kk$, and $X \subseteq \PP$ be a closed subscheme of $\PP$.
	Let $\bn=(n_1,\ldots,n_p) \in \NN^p$ be such that $n_1+\cdots+n_p=\dim(X)$.
	Then, $\deg_\PP^\bn(X) > 0$ if and only if there is an irreducible component $Y \subseteq X$ of $X$ that satisfies the following two conditions:
	\begin{enumerate}
		\item $\dim(Y) = \dim(X)$.
		\item For each $\fJ = \{j_1,\ldots,j_k\} \subseteq \{1,\ldots,p\}$ the inequality 
		$$
		n_{j_1} + \cdots + n_{j_k} \le \dim\big(\Pi_\fJ(Y)\big)
		$$
		holds.
	\end{enumerate} 
\end{theorem}


When $\kk$ is the field of complex numbers this theorem is essentially covered by the geometric results in \cite[Theorems 2.14, 2.19]{KAVEH_KHOVANSKII},
however their methods do not extend to arbitrary fields. Here we follow an algebraic approach that allows us to prove the result for all fields, and hence a general version for algebras over Artinian local rings. 
The main idea in the proof of Theorem \ref{thmA} is the study of the dimensions of the images of the natural projections after cutting by a general hyperplane.

\medskip

We note  that if $p=2$ and $X$ is arithmetically Cohen--Macaulay,  the conclusion of \autoref{thmA} in the irreducible case also holds for $X$ (see \cite[Corollary 2.8]{TRUNG_POSITIVE}). 
We show that this is not necessarily true for $p>2$.


\medskip
If $X$ is irreducible, then the function $r:2^{\{1,\ldots,p\}}\rightarrow \ZZ$ defined by $r(\fJ):=\dim\big(\Pi_\fJ(X)\big)$ is a submodular function, i.e., $r(\fJ_1\cap \fJ_2)+r(\fJ_1\cup \fJ_2)\leq r(\fJ_1)+r(\fJ_2)$ for any two subsets $\fJ_1,\fJ_2\subseteq \{1,\ldots,p\}$. 
By the Submodular Theorem (see, e.g., \cite[Theorem 3.11]{NESTED} or \cite[Appendix B]{YU})  and the inequalities of Theorem \ref{thmA}, the points $\bn\in \NN^p$ for which $\deg_\PP^\bn(X) > 0$ are the lattice points of a \textit{generalized permutohedron}. 
Defined by A.~Postnikov in \cite{POSTNIKOV} generalized permutohedra are polytopes obtained by deforming usual permutohedra. 
In recent years this family of polytopes has been studied in relation to other fields such as probability, combinatorics, and  representation theory (see \cite{YU,YONG,FACES}).  





\medskip


In a more algebraic flavor, we state the translation of Theorem \ref{thmA} to the mixed multiplicities  of a standard multigraded algebra over an Artinian local ring.

Let $A$ be an Artinian local ring and $R$ be a finitely generated standard $\NN^p$-graded $A$-algebra and let $P_R(\ttt)=P_R(t_1,\ldots,t_p) \in \QQ[\ttt]=\QQ[t_1,\ldots,t_p]$ be the \emph{Hilbert polynomial} of $R$ (see, e.g., \cite[Theorem 4.1]{HERMANN_MULTIGRAD}, \cite[Theorem 3.4]{MIXED_MULT}).
Then, the degree of $P_R$ is equal to the dimension of $R$ and
$$
P_R(\nu) = \dim_\kk\left([R]_\nu\right) 
$$
for all $\nu \in \NN^p$ such that $\nu \gg \mathbf{0}$.
Furthermore, if we write 
\begin{equation}
\label{eq_Hilb_poly}
P_{R}(\ttt) = \sum_{n_1,\ldots,n_p \ge 0} e(n_1,\ldots,n_p)\binom{t_1+n_1}{n_1}\cdots \binom{t_p+n_p}{n_p},
\end{equation}
then $0 \le e(n_1,\ldots,n_r) \in \ZZ$ for all $n_1+\cdots+n_p = r$.

Let $\bn = (n_1,\ldots,n_p) \in \NN^p$ with $\lvert\bn\rvert=r$.
Then $e(\bn,R) := e(n_1,\ldots,n_p)$ is the \textit{mixed multiplicity} of R of type $\mathbf{n}$.



\begin{theorem}
	\label{corB}
	Let $A$ be an Artinian local ring and $R$ be a finitely generated standard $\NN^p$-graded $A$-algebra.
	For each $1 \le j \le p$, let  $\mm_j \subset R$ be the ideal generated by the elements of degree $\ee_j$, where $\ee_j \in \NN^p$ denotes the $j$-th elementary vector.
	Let $\nn = \mm_1 \cap \cdots \cap \mm_p \subset R$.
	Let $\bn=(n_1,\ldots,n_p) \in \NN^p$ be such that $n_1+\cdots+n_p=\dim\left(R/\left(0:_R\nn^\infty\right)\right)-p$.
	Then, $e(\bn;R) > 0$ if and only if there is a minimal prime ideal $\fP \in \Min\left(0:_R\nn^\infty\right)$ of $\left(0:_R\nn^\infty\right)$ that satisfies the following two conditions:
	\begin{enumerate}
		\item $\dim\left(R/\fP\right)  = \dim\left(R/\left(0:_R\nn^\infty\right)\right)$.
		\item For each $\fJ = \{j_1,\ldots,j_k\} \subseteq \{1,\ldots,p\}$ the inequality 
		$$
		n_{j_1} + \cdots + n_{j_k} \le \dim\left(\frac{R}{\fP+\sum_{j \not\in \fJ} \mm_j}\right) - k
		$$
		holds. 
	\end{enumerate} 
\end{theorem}

For a given finite set of  ideals in a Noetherian local ring, such that  one of   them is  zero-dimensional, we can define their mixed multiplicities by considering a certain associated standard multigraded algebra (see \cite{TRUNG_VERMA_MIXED_VOL} for more information). 
These multiplicities have a long history of interconnecting problems from commutative algebra, algebraic geometry, and combinatorics, with applications to the topics of Milnor numbers, mixed volumes, and integral dependence (see, e.g., \cite{Huh12,huneke2006integral,TRUNG_VERMA_MIXED_VOL,teissier1973cycles}). 
As a direct consequence of Theorem \ref{corB} we are able to give a characterization for the positivity of mixed multiplicities of ideals. In another related result, we focus on homogeneous ideals generated in one degree; this case is of particular importance due to its relation with rational maps between projective varieties. 
In this setting, we provide more explicit  conditions for positivity in terms of the analytic spread of products of these ideals.


\medskip


Going back to the setting of Theorem \ref{thmA}, we switch our attention to the following discrete set 
$$
\msupp_\PP(X) \,=\, \big\{\bn\in \NN^p \;\mid\; \deg_\PP^\bn(X)>0\big\},
$$	
which we call the \textit{support of $X$ with respect to $\PP$}.  
When $X$ is irreducible,  we show that $\msupp_\PP(X)$ is  a \textit{(discrete) polymatroid}. An alternative proof is given by  Br{\"a}nd{\'e}n and Huh in \cite[Corollary 4.7]{LORENTZ} using the theory of Lorentzian polynomials.   An advantage of our approach is that we can describe the corresponding rank submodular functions of the polymatroids, a fact that we exploit in the applications.
Additionally, our results are valid when $X$ is just irreducible and not necessarily geometrically irreducible over $\kk$ (i.e., we do not need to assume that $X \times_\kk \overline{\kk}$ is irreducible for an algebraic closure $\overline{\kk}$ of $\kk$); it should be noticed that this generality is not covered by the statements in \cite{LORENTZ} and \cite{KAVEH_KHOVANSKII}.

\medskip


Discrete polymatroids \cite{HERZOG_HIBI_MONOMIALS} have also been studied  under the  name of M-convex sets \cite{MUROTA}. Polymatroids can also be described as the  integer points in a generalized permutohedron \cite{POSTNIKOV}, so  they are closely related to submodular functions, which are well studied in optimization, see \cite{LOVASZ} and \cite[Part IV]{SCHRIJVER} for comprehensive surveys on submodular functions, their applications, and their history.
There are  two distinguishable types of  polymatroids, linear and algebraic polymatroids, whose main properties are inherited by  their representation  in terms of other algebraic structures. 
Theorem \ref{thmA} allows us to define another type of polymatroids, that we call \emph{Chow polymatroids}, and which interestingly lies in between the other two.
In the following theorem we summarize our main results in this direction.


%We also show that this set of points forms a discrete polymatroid  belongs to a special class  known in the literature as {polymatroids polytopes}. 



\begin{theorem}
	Over an arbitrary field $\kk$, we have the following inclusions of families of polymatroids	
	$$
	\Big(\texttt{Linear polymatroids}\Big) \;\subseteq\; \Big(\texttt{Chow polymatroids}\Big) \;\subseteq\; \Big(\texttt{Algebraic polymatroids}\Big).
	$$	
	Moreover, when $\kk$ is a field of characteristic zero, the three families coincide.
\end{theorem}
If $\kk$ has positive characteristic, then these types of polymatroids do not agree. In fact, there exist examples of polymatroids which are algebraic over any field of positive characteristic but never linear. 

\smallskip

Theorem \ref{thmA} can be applied to particular examples of varieties coming from combinatorial algebraic geometry. 
In Section \ref{subsect_Schubert} we do so to matrix Schubert varieties; in this case the multidegrees are the coefficients of Schubert polynomials, thus our results allow us to give an alternative proof to a recent conjecture regarding the support of these polynomials. 
In Sections \ref{sec_flag} and \ref{sec_M0} we study certain embeddings of flag varieties and of the moduli space $\overline{M}_{0,p+3}$, respectively. In Section \ref{sec_mixed} we recover a well-known characterization for the positivity of mixed volumes of convex bodies.

\section{Applications}\label{sec_comb} 

In this section  we  relate our results to several objects from combinatorial algebraic geometry.


\subsection{Schubert polynomials}
\label{subsect_Schubert}

Let $\fS_p$ be the symmetric group on the set $[p]$. For every $i\in[p-1]$ we have the transposition $s_i:=(i,i+1)\in \fS_p$. Recall that the set $S=\{ s_i~:~1\leq i< p \}$ generates $\fS_p$. The \emph{length} $l(\pi)$ of a permutation $\pi$ is the least amount of elements in $S$ needed to obtain $\pi$. Alternatively, the length is equal to the number of \emph{inversions}, i.e., $l(\pi)=\{(i,j)\in[p]\times[p]:i<j,\; \pi(i)>\pi(j)\}$. 
The permutation $\pi_0=(p,p-1,\cdots,2,1)$ (in one line notation) is the longest permutation, it has length $\frac{p(p-1)}{2}$.
\begin{definition}
	The \textit{Schubert polynomials} $\fS_\pi\in\ZZ[t_1,\ldots,t_p]$ are defined recursively  in the following  way. 
	First we define $\fS_{\pi_0}:=\prod_{i} t_i^{p-i}$, and for any permutation $\pi$ and transposition $s_i$ with $l(s_i\pi)<l(\pi)$ we let
	\[
	\fS_{s_i\pi} = \dfrac{\fS_{\pi}-s_i\fS_{\pi}}{t_i-t_{i+1}},
	\]
	where $\fS_{p}$ acts on $\ZZ[t_1,\ldots,t_p]$ by permutation of variables. For more information see \cite[Chapter 10]{FULTON_TABLEAUX}. 
\end{definition}



Next we define \textit{matrix Schubert varieties} following \cite[Chapter 15]{MILLER_STURMFELS}. Let $\kk$ be an algebraic closed field and  $M_p(\kk)$ be the $\kk$-vector space of $p\times p$ matrices with entries in $\kk$. As an affine variety we define its coordinate ring as $R_p:=\kk[x_{ij}:(i,j)\in[p]\times[p]]$. Furthermore we consider an $\NN^p$-grading on $R_p$ by letting $\deg(x_{ij}) = \ee_i$.

\begin{definition} 
	Let $\pi$ be a permutation matrix. The matrix Schubert variety $\overline{X_\pi}\subset M_p(\kk)$ is the subvariety
	\[
	\overline{X_\pi}=\{Z\in M_p(\kk)\mid \rank(Z_{m\times n})\leq \rank(\pi_{m\times n}) \; \text{ for all }\; m,n\},
	\]
	where $Z_{m\times n}$ is the restriction to the first $m$ rows and $n$ columns. This is an irreducible variety
	and the prime ideal $I\left(\overline{X_\pi}\right)$ is multihomogeneous \cite[Theorem 15.31]{MILLER_STURMFELS}. By  \cite[Theorem 15.40]{MILLER_STURMFELS}, the Schubert polynomial $\fS_\pi$  equals the multidegree polynomial of the variety corresponding to the ideal $I\left(\overline{X_\pi}\right)$.
\end{definition}

Following \cite{YONG} we say a polynomial $f=\sum_{\bn}c_{\bn}\ttt^\bn\in \ZZ[t_1,\cdots,t_p]$ have the Saturated Newton Polytope property (SNP for short) if $\text{supp}(f):=\{\bn\in\NN^p\mid c_\bn>0\}=\text{ConvexHull}\{\bn\in\NN^p\mid c_\bn>0\}\cap\NN^p$, in other words, if the support of $f$ consist of the integer points of a polytope.
In \cite[Conjecture 5.5]{YONG} it was conjectured that the Schubert polynomials have SNP property and they even conjectured a set of defining inequalities for the Newton polytope in \cite[Conjecture 5.13]{YONG}. 
A.~Fink, K.~M\'ez\'aros, and A.~St.~Dizier confirmed the full conjecture in \cite{FINK}.  %As noted by the authors of \cite{huh2019logarithmic} the combination of \autoref{prop_poly} (they use the equivalent \cite[Corollary 10.2]{LORENTZ}) and \cite[Theorem 15.40]{MILLER_STURMFELS} (which is also included in \cite[Theorem 6]{huh2019logarithmic}) is enough to give an alternative proof to  \cite[Conjecture 5.5]{YONG}.


\begin{theorem}\label{thm_Schubert}
	For any permutation $\pi$, the Schubert polynomial $\fS_\pi$ has SNP and its Newton polytope is a polymatroid polytope.
\end{theorem}

The Newton polytope of a polynomial $f$ is by definition the convex hull of the exponents in the support of $f$, however in by our convention $\msupp$ consists of the complementary exponents. This does not change the conclusion that the resulting polytope is a polymatroid polytope.

\medskip

{\bf Codimensions of projections.} 
We now use Theorem {thmA} to give a combinatorial interpretation for the codimensions of the natural projections of matrix Schubert varieties. First we need some terminology.

A \textit{ diagram} $D$ is a subset of a $p\times p$ grid whose boxes are indexed by  the set $[p]\times [p]$.  % whose boxes are indexed by the pairs  $(i,j)\in [p]\times [p]$. %We thnk %, to be thought of as a square grid. 
The authors of \cite{YONG} define a function $\theta_D:2^{[p]}\mapsto \ZZ$ as follows: for a subset $\fJ\subseteq [p]$ and   $c\in [p]$ ,  we construct a word $W_D^c(\fJ)$ by reading the column $c$ of $[p]\times [p]$ from top to bottom  and recording
\begin{itemize}
	\item $($ if $(r,c)\notin D$ and $r\in \fJ$,
	\item $)$ if $(r,c)\in D$ and $r\notin \fJ$,
	\item $\star$ if $(r,c)\in D$ and $r\in \fJ$;
\end{itemize}
let $\theta_D^c(\fJ)=\#\textrm{ paired ``()" in }W_D^c(\fJ)+\#\star\textrm{ in } W_D^c(\fJ)$, and finally $\theta_D(\fJ)=\sum_{i=1}^p \theta_D^i(\fJ)$.\\
\medskip
\textbf{Example}
	For example, let $D$ be the diagram depicted in  Figure \ref{fig:diagram} and $\fJ=\{2,3\}$, then $\theta_D(\fJ)=3$. %Intuitively the definition counts the number of boxes in the rows indexed by $\fJ$ with an extra rule that allows to count boxes from below just once.
	
	
	\begin{figure}[ht]
		\centering
		\scalebox{.5}{
			\begin{tikzpicture}
			
			
			
			
			\draw[dotted] (0,0)--(5,0)--(5,5)--(0,5)--(0,0);
			\draw[dotted] (1,0)--(1,5);
			\draw[dotted] (2,0)--(2,5);
			\draw[dotted] (3,0)--(3,5);
			\draw[dotted] (4,0)--(4,5);
			\draw[dotted] (0,1)--(5,1);
			\draw[dotted] (0,2)--(5,2);
			\draw[dotted] (0,3)--(5,3);
			\draw[dotted] (0,4)--(5,4);
			\draw[fill=red!10] (0,5)--(1,5)--(1,4)--(0,4)--cycle;
			\draw[fill=red!10] (1,5)--(2,5)--(2,4)--(1,4)--cycle;
			\draw[fill=red!10](2,5)--(3,5)--(3,4)--(2,4)--cycle;
			\draw[fill=red!10](0,4)--(1,4)--(1,3)--(0,3)--cycle;
			\draw[fill=red!10](0,2)--(0,1)--(1,1)--(1,2)--cycle;
			\draw[fill=red!10] (2,3)--(2,2)--(3,2)--(3,3)--cycle;\
			\end{tikzpicture} }
		\caption{Example of a diagram in $[5]\times[5]$}
		\label{fig:diagram} 
	\end{figure}


For any $\pi\in\fS_p$ we can define its \textit{Rothe diagram} as  $$D_\pi:=\{(i,j)\mid 1\leq i,j\leq n, \pi(i)>j\text{ and }\pi^{-1}(j)>i\}\subset[p]\times[p].$$ For example when $\pi=42531$ then $D_\pi$ is the diagram of \autoref{fig:diagram}.

\begin{theorem} \label{thm_projections_schubert}
	Let $\pi\in\fS_p$, then 
	for any $\fJ\subseteq [p]$ the projection $\Pi_\fJ\left(\overline{X_\pi}\right)$ onto the rows indexed by $\fJ$ has codimension $\theta_{D_\pi}([p])-\theta_{D_\pi}(\fJ')$, where $\fJ'=[p]\backslash\fJ$ is the complement of $\fJ$.
\end{theorem}



	Notice that $\theta_{D_\pi}([p])$ counts the total number of boxes in $D_\pi$, which is equal to the length of $\pi$ (see \cite[Definition 15.13]{MILLER_STURMFELS}). So the case $\fJ=[p]$ of Theorem \ref{thm_projections_schubert} above is equivalent to the well-known fact that the codimesion of  a matrix Schubert variety is equal to the length of the permutation (see \cite[Theorem 15.31]{MILLER_STURMFELS}).


\subsection{Flag varieties} \label{sec_flag}
We now focus on a multiprojective embedding of flag varieties. 
We first review some terminology. 
For more information the reader is referred to \cite{FULTON_TABLEAUX} or \cite{BRION}.

In this subsection we work over an algebraically closed field $\kk$. Consider the \emph{complete flag variety} $Fl(V)$ of a $\kk$-vector space $V$ of dimension $p+1$. This variety parametrizes complete flags, i.e., sequences $V_\bullet := (V_0,\cdots,V_{p+1})$ such that $\{0\}=V_0\subset V_1 \subset V_2 \subset \cdots \subset V_{p} \subset V_{p+1}=V,$
and each $V_i$ is a linear subspace of $V$ of dimension $i$. 
One can embed this variety in a product of Grassmannians $Fl(V) \hookrightarrow \textrm{Gr}(1,V)\times \textrm{Gr}(2,V) \times \cdots\times \textrm{Gr}(p,V)$ as the subvariety cut out by incidence relations. 

Furthermore, each Grassmannian can be embedded in a projective space via the Pl\"ucker embedding $\iota_i:\textrm{Gr}(i,V) \rightarrow\PP_\kk^{m_i}$ for $1\leq i\leq p$. 
By considering the product of these maps, we obtain a multiprojective embedding of $\iota: Fl(V)\hookrightarrow \PP_\kk^{m_1}\times_\kk\cdots \times_\kk\PP_\kk^{m_p}$. 
For convenience we also call $\iota$ the \textit{Pl\"ucker embedding}.
The proposition below computes the corresponding multidegree support.

\begin{proposition}\label{prop_sottile}
	Let $V$ be a $\kk$-vector space of dimension $p+1$ and let $X$ be the image of the Pl\"ucker embedding $\iota: Fl(V)\hookrightarrow \PP = \PP_\kk^{m_1}\times_\kk\cdots\times_\kk\PP_\kk^{m_{p}}$, then
	\begin{equation}\label{eq:flag_simple}
	\msupp_\PP(X)=\left\{\bn\in\NN^{p} \;\mid\; 1\leq n_k\leq \sum_{j=1}^{k}(p-j)-\sum_{i=1}^{k-1} n_i, \;\; \forall k\in [p],\;\; \sum_{j=1}^p n_j = \binom{p+1}{2} \right\};
	\end{equation}
	
\end{proposition}


The pullbacks of the classes $H_i$ from $\PP_\kk^{m_1}\times_\kk\cdots\times_\kk\PP_\kk^{m_p}$ to $Fl(V)$ are called the Schubert divisors, so Proposition \autoref{prop_sottile} amounts to a criterion for which powers of these classes intersect. These intersections are called Grassmannian Schubert problems in \cite{PURBHOO_SOTTILE}. In \cite[Theorem 1.2]{PURBHOO_SOTTILE} K.~Purbhoo and F.~Sottile give a stronger statement by providing an explicit combinatorial formula using \emph{filtered tableau} to compute the exact intersection numbers. 




\subsection{A multiprojective embedding of $\overline{M}_{0,p+3}$}\label{sec_M0}

The moduli space $\overline{M}_{0,p+3}$ parametrizes rational stable curves with $p+3$ marked points. 
Here we apply our methods to an embedding considered in \cite{MONKS}. 
The starting point is the closed embedding $\Psi_p: \overline{M}_{0,p+3}\longrightarrow \overline{M}_{0,p+2}\times_\kk \PP_\kk^p$ constructed by S.~Keel and J.~Tevelev in \cite[Corollary 2.7]{KEEL_TEVELEV}. 
By iterating this construction we obtain an embedding $\overline{M}_{0,p+3}\hookrightarrow \PP_\kk^1\times_\kk\PP_\kk^2\times_\kk\cdots\times_\kk\PP_\kk^p$ (see \cite[Corollary 3.2]{MONKS}). 
In \cite{MONKS}, R.~Cavalieri, M.~Gillespie, and L.~Monin computed the corresponding multidegree which turns out to be related to parking functions. 
As an easy consequence of our \autoref{thmA}, we can compute its support.

\begin{proposition}\label{prop_parking}
	Let $X$ be the image of  $\overline{M}_{0,p+3}\hookrightarrow \PP =  \PP_\kk^1\times_\kk\PP_\kk^2\times_\kk\cdots\times_\kk\PP_\kk^p$, then 
	\begin{equation}\label{eq:M0n}
	\msupp_\PP(X)=\left\{\bn\in\NN^p\;\mid\; \sum_{i=1}^k n_i\leq k,\; \forall 1\leq k\leq p-1,\; \sum_{i=1}^p n_i=p\right\}.
	\end{equation}
	
	
	%	\begin{align*}
	%	0&\leq \bn_1\\
	%	\bn_1 &\leq 1\\
	%	\bn_2+\bn_1&\leq 2 \\
	%	\bn_3+\bn_2+\bn_1&\leq 3\\
	%	&\vdots\\
	%	\bn_{n-1}+\cdots+\bn_3+\bn_2+\bn_1&\leq n-1\\
	%	\bn_{n-1}+\cdots+\bn_3+\bn_2+\bn_1&= n.
	%	\end{align*}
\end{proposition}


The cardinality of $\msupp_\PP(X)$ is equal to the Catalan number $C_n$ (see \cite[Exercise 86]{CATALAN}). For a comprehensible survey on Catalan numbers see \cite{CATALAN}.





\subsection{Mixed Volumes}\label{sec_mixed}
In this subsection we assume $\kk$ is an algebraically closed field. We begin by  reviewing the definition of mixed volumes of convex bodies, as a general reference see \cite[Chapter IV]{EWALD}.
Let $\textbf{K}=(K_1,\ldots,K_p)$ be a $p$-tuple of convex bodies in $\mathbb{R}^d$.  The volume polynomial $v(\textbf{K})\in \ZZ[w_1,\ldots,w_p]$ is defined as
\[
v(K_1,\ldots,K_p) :=  \text{Vol}_d(w_1K_1+\cdots+w_pK_p).
\]
This is a homogeneous polynomial of degree $d$. If the coefficients of $v(\textbf{K})$  are written as $\binom{d}{\bn}V(\textbf{K};\bn)w^\bn$, then the numbers $V(\textbf{K};\bn)$ are called the \textit{mixed volumes of} $\textbf{K}$. A natural question to ask is: when are mixed volumes positive? The relation between mixed volumes and toric varieties (see  \autoref{eq_mixed-intersection} below) together with \autoref{thmA} allows us to give another proof of a classical theorem  formulated on the non-vanishing of mixed volumes \cite[Theorem 5.1.8]{SCHNEIDER}. 

\begin{theorem}
	\label{thm_mixed}
	Let $\textnormal{\textbf{K}}=(K_1,\ldots,K_p)$ be a $p$-tuple of convex bodies in $\mathbb{R}^d$. 
	Then, $V(\textnormal{\textbf{K}};\bn)>0$ if and only if $\sum_{i=1}^p n_i=d$ and $\sum_{i\in \fJ} n_i\leq \dim\left(\sum_{i\in \fJ} K_i\right)$ for every subset $\fJ \subseteq [p]$.
\end{theorem}

The proof can be reduced to the case of polyopes, where we can use basic results about toric varieties and lattice polytopes.
As an initial step we recall some facts about basepoint free divisors; a general reference is \cite[Section 6]{COX_TORIC}. Let $\Sigma$ be  a fan and  let $P$ be a lattice polytope  whose normal fan coarsens $\Sigma$.  
Then,  $P$ induces a basepoint free divisor $D_P$ in the toric variety $Y_{\Sigma}$ \cite[Proposition 6.2.5]{COX_TORIC}. Here, being basepoint free means that the complete linear series $|D_P|$ induces a morphism $\phi_{P}:Y_{\Sigma}\rightarrow \PP_{\kk}^{m_i}$ for some $m_i\in\NN$ such that $\phi^*(H)=D_P\in A^*(Y_{\Sigma})$, where $H$ is the class of a hyperplane in the projective space $\PP_{\kk}^{m_i}$.

\begin{lemma}\label{lem_toric-aux-1}	
	Let $K_1,\ldots,K_p$ be lattice polytopes and let $K:=K_1+\cdots+K_p$ be their Minkowski sum . Let  $Y$  be the toric variety associated to $\Sigma$, the normal fan of $K$, then  for each $\fJ\subseteq[p]$ we have a map $\phi_{\fJ}: Y\rightarrow \prod_{j\in\fJ} \PP_{\kk}^{m_j}$ such that $\dim\left(\phi_{\fJ}(Y)\right)=\dim\left(\sum_{i\in\fJ}K_i\right)$.
\end{lemma}

\begin{lemma} \label{lem_toric-aux-2}	
	In the setup of Lemma \ref{lem_toric-aux-1}, if $\fJ=[p]$ then after scaling each polytope if necessary, $\phi = \phi_{\fJ}$ is an embedding.
\end{lemma}



\begin{proof}[Proof of \autoref{thm_mixed}]
	We can assume that each $K_i$ is a polytope. 
	Additionally, we can reduce to the case where each $K_i$ is a lattice polytope since any polytope can be approximated by lattice polytopes (see \cite[Page 120]{FULTON}). 
	Let $K=K_1+\cdots+K_p$ and let $Y$ be the  toric projective variety associated to the normal fan of $K$. Each lattice polytope $K_i$ induces a basepoint free divisor $D_i$ on $Y$. As explained in \cite[Eq. (2), Page 116]{FULTON}, the fundamental connection between mixed volumes and intersection products is  given by the following equation
	\begin{equation}\label{eq_mixed-intersection}
	V(\textbf{K};\bn)=\left(D_1^{n_1}\cdots D_p^{n_p}\right)/d!,
	\end{equation}	
	where the numerator is the intersection product of the divisors in $Y$. Notice that positivity of mixed volumes  is unchanged by scaling so whenever needed we can scale each polytope.
	
	
	By \autoref{lem_toric-aux-2} we have an embedding $\phi: Y\rightarrow \prod_{i=1}^p \PP_{\kk}^{m_i}$ such that the pullback of each $H_i\in A^*\left(\prod_{i=1}^p \PP_{\kk}^{m_i}\right)$ is $D_i$. 
	By using the projection formula \cite[Proposition 2.5(c)]{FULTON_INTERSECTION_THEORY}, we can consider the product $\left(H_1^{n_1}\cdots H_p^{n_p}\right)/d!$ instead of the one in \autoref{eq_mixed-intersection}.
	From the fact that $Y$ is irreducible we are now in the setup to apply Theorem \ref{thmA} and Lemma \ref{lem_toric-aux-1} computes the appropriate dimensions.
\end{proof}


\acknowledgements{We thank the reviewer for his/her suggestions for the improvement of this work.
	We would like to thank  Chris Eur, Maria Gillespie, June Huh, David Speyer, and Mauricio Velasco for
	useful conversations. We are also grateful with Frank Sottile for useful comments on an earlier version (in particular for the simplification of the statement of Proposition \ref{prop_sottile}). Special thanks to  Brian Osserman for many insightful conversations and encouragements. 
	The computer algebra system \texttt{Macaulay2} \cite{MACAULAY2} was of great help to compute several examples in the preparation of this paper.
}

%% 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}
