
%\newcommand{\Pow}{\textup{\textsf{Pow}}}

%% 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{52}
%% 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{amsfonts}
\usepackage{paralist}
\usepackage{booktabs}
\usepackage{graphicx,epsf}
\usepackage{graphics}
\usepackage{epsfig}
\usepackage{epstopdf}
\usepackage{psfrag}


\usepackage{amsmath,amsfonts,amssymb,latexsym,amsthm}
\usepackage{graphicx,epsf}
\usepackage{amsthm}
\usepackage{multicol}
\usepackage{ytableau}

\usepackage{url}
\usepackage{hyperref} %hyperref wants to be loaded last

\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}


\usepackage[colorinlistoftodos]{todonotes}
\newcommand{\defn}{}
\newcommand{\defna}{}
\newcommand{\defnb}{}
\newcommand{\defng}{}


\newtheorem{theorem}{Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem{claim}[thm]{Claim}
\newtheorem{Def}[thm]{Definition}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{mainlem}[thm]{Main Lemma}
\newtheorem{sublemma}[thm]{Sublemma}
\newtheorem{problem}[thm]{Problem}
\newtheorem{observation}[thm]{Observation}
\newtheorem{Cor}[thm]{Corollary}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{Conjecture}[thm]{Conjecture}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{question}[thm]{Question}
\newtheorem{clm}[thm]{Claim}
\newtheorem{op}[thm]{Open Problem}

\newtheorem{ex}[thm]{Example}



\theoremstyle{plain}
\newtheorem{theo}[thm]{Theorem}
\newtheorem{lem}[thm]{Lemma}



\theoremstyle{definition}

\newtheorem{Example}[thm]{Example}
\newtheorem{eg}[thm]{Example}
\newtheorem{ques}{Question}
\newtheorem{rem}[thm]{Remark}
\newtheorem{definition}[thm]{Definition}

\numberwithin{equation}{section}

\def\bx{{\textbf{\textit{x}}}}
\def\by{{\textbf{\textit{y}}}}
\def\bz{{\textbf{\textit{z}}}}

\newcommand{\la}{\lambda}
\newcommand{\cd}{\mathcal D}
\newcommand{\cb}{\mathcal B}
\newcommand{\cp}{\mathcal P}
\newcommand{\cP}{\mathcal P}
\newcommand{\cf}{\mathcal F}
\newcommand{\cF}{\mathcal F}
\newcommand{\cg}{\mathcal G}
\newcommand{\cjp}{\mathcal{J}}
\newcommand{\nn}{\Bbb N}
\newcommand{\cR}{\mathcal R}
\newcommand{\cS}{\mathcal S}
\newcommand{\cT}{\mathcal T}
\newcommand{\cQ}{\mathcal Q}

\newcommand{\wh}{\widehat}
\newcommand{\bu}{\bullet}
\newcommand{\emp}{\varnothing}
\newcommand{\sq}{\square}
\newcommand{\st}{\star}
\newcommand{\bd}{\blacktriangledown}
\newcommand{\ap}{\approx}
\newcommand{\aA}{\Bbb A}
\newcommand{\zz}{\Bbb Z}

\newcommand{\Gg}{\Bbb G}

\newcommand{\ff}{\Bbb F}
\newcommand{\cc}{\Bbb C}
\newcommand{\rr}{\Bbb R}
\newcommand{\qqq}{\Bbb Q}
\newcommand{\tT}{\Bbb T}
\newcommand{\ee}{\Bbb E}
\newcommand{\sS}{\Bbb S}
\newcommand{\oo}{\Bbb O}
\newcommand{\ooo}{\overline \oo}
\newcommand{\ov}{\overline}
\newcommand{\gG}{\Bbb G}
%\newcommand{\sm}{\setminus}
\newcommand{\pr}{\prime}
\newcommand{\Ga}{\Gamma}
\newcommand{\Om}{\Omega}
\newcommand{\De}{\Delta}
\newcommand{\Si}{\Sigma}

\newcommand{\ga}{\gamma}
\newcommand{\si}{\sigma}
\newcommand{\de}{\delta}
\newcommand{\ep}{\epsilon}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\om}{\omega}
%\newcommand{\k}{\kappa}
\newcommand{\ka}{\kappa}
\newcommand{\ve}{\varepsilon}
\newcommand{\vr}{\text{\rm deg}}
\newcommand{\vp}{\varphi}
\newcommand{\vk}{\varkappa}
\newcommand{\CR}{\mathcal R}
\newcommand{\GG}{\goth G}
\newcommand{\GI}{\goth I}
\newcommand{\CS}{\mathcal S}
\newcommand{\cC}{\mathcal C}
\newcommand{\ca}{\mathcal A}
\newcommand{\CB}{\mathcal B}
\newcommand{\T}{\bold T}
\newcommand{\CT}{\mathcal T}
\newcommand{\BCT}{\text{BCT}}
\newcommand{\CTR}{\mathrm T}
\newcommand{\cN}{\mathcal N}
\newcommand{\BB}{\bold B}
\newcommand{\bP}{\bold P}
\newcommand{\ssu}{\subset}
\newcommand{\sss}{\supset}
\newcommand{\wt}{\widetilde}
\newcommand{\vda}{\vdash}

\newcommand{\La}{\Lambda}
\newcommand{\const}{\text{{\rm const}}}
\newcommand{\rc}{ {\text {\rm rc}  } }
\newcommand{\y}{ {\text {\rm y}  } }
\newcommand{\sy}{ {\text {\rm sy}  } }
\newcommand{\Z}{ {\text {\rm Z} } }
\newcommand{\FF}{ {\text {\rm F} } }
\newcommand{\RR}{ {\text {\rm R} } }
\newcommand{\Tr}{ {\text {\rm Tr} } }
\newcommand{\rk}{\dim}
\newcommand{\srk}{\dim}
\newcommand{\prev}{\prec}
\newcommand{\oa}{\ov \al}
\newcommand{\Ups}{\Upsilon}
\newcommand{\vt}{\vartheta}
\newcommand{\dv}{\divideontimes}
\newcommand{\cw}{\mathcal W}
\newcommand{\U}{{\text {\rm U} } }
\newcommand{\rT}{{\text {\rm T} } }
\newcommand{\CA}{{\text {\rm T} } }
\newcommand{\RC}{{\text {\rm RC} } }

\newcommand{\Q}{{\text {\rm Q} } }
\newcommand{\mix}{{\text {\rm mix} } }
\newcommand{\inv}{{\text {\rm inv} } }
\newcommand{\maj}{{\text {\rm maj} } }
\newcommand{\sign}{{\text {\rm sign} } }
\newcommand{\PSL}{{\text {\rm PSL} } }
\newcommand{\SL}{{\text {\rm SL} } }
\newcommand{\Sch}{{\mathfrak{S}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ch}{\mathrm{ch}}
\newcommand{\Mgn}{\overline{M}_{g,n}}
\newcommand{\Hilbn}{\mathrm{Hilb}_n}

\newcommand{\NN}{{\mathbb N}}
\newcommand{\HH}{{\mathbb H}}
\newcommand{\A}{{\mathbb A}}
\newcommand{\PP }{{\mathbb P}}
\newcommand{\QQ }{{\mathbb Q}}
\newcommand{\bstar}{\divideontimes}
\newcommand{\rp}{ {\text {\rm P}  } }

\def\perm{\mathrm{perm}}
\def\per{\mathrm{per}}
\def\sgn{\mathrm{sgn}}
\def\sk{{\textrm{sk}}}

\def\.{\hskip.06cm}
\def\ts{\hskip.03cm}

%\def\bs{\mathbf{z}}
\def\bt{\mathbf{u}}
\def\cor{\mathcal{C}}
\def\dor{\mathcal{D}}
\def\syt{ {\text {\rm SYT}  } }
\def\SYT{ {\text {\rm SYT}  } }
\def\SSYT{ {\text {\rm SSYT}  } }
\def\LR{ {\text {\rm LR}  } }
\def\GL{ {\text {\rm GL}  } }
\def\rg{\overline{g}}


\def\P{{{\rm{\textsf{P}} }}}
\def\R{{{\rm{\textsf{RP}}}}}
\def\ParP{{\rm{\textsf{$\oplus$P}}}}
\def\FP{{\rm{\textsf{FP}}}}
\def\PH{{\rm{\textsf{PH}}}}
\def\BPP{{\rm{\textsf{BPP}}}}
\def\SP{{{\rm{\textsf{\#P}}}}}
\def\SPr{{{{\sf \#P}}}}

\newcommand{\ComCla}[1]{\textup{\textsf{#1}} }

\def\GapP{{{\rm{\textsf{GapP}} }}}
\newcommand{\CeqP}{\ComCla{C$_=$P}}
\def\FP{{{}\rm{\textsf{FP}} }}
\def\NP{{{\rm{\textsf{NP}} }}}
\def\coNP{{{\rm{\textsf{coNP}} }}}

\def\VP{{{\rm{\textsf{VP}} }}}
\def\VNP{{{\rm{\textsf{VNP}} }}}
\def\EXP{{{\rm{\textsf{EXP}}}}}
\def\NEXP{{{\rm{\textsf{NEXP}}}}}
\def\SEXP{{{\rm{\textsf{\#EXP}}}}}
\def\EEXP{{{\rm{\textsf{EXPSPACE}}}}}
\def\EE{{\rm{\textsf{EE}}}}
\def\PAR{{\rm{\textsf{$\oplus$EXP}}}}
\def\DTIME{{\rm{\textsf{DTIME}}}}

\def\rB{ {\text {\rm B} } }
\def\Sh{ {\mathfrak{S} } }

\def\FPRAS{{\rm{\textrm{FPRAS} }}}
\def\FPTAS{{\rm{\textrm{FPTAS} }}}
\def\vol{{\text {\rm vol}}}

\def\TT{{\mathcal T}}
\def\TTab{\mathcal{T}(\mathbf a, \mathbf b)}

\def\rTT{{\text{\rm T}}}
\def\rTab{{\text{\rm T}}(\mathbf a, \mathbf b)}

\def\BTT{{\mathcal T}'}
\def\BTTab{\mathcal{T}'(\mathbf a, \mathbf b)}

\def\rBTT{{\text{\rm T}'}}
\def\rBTab{{\text{\rm T}'}(\mathbf a, \mathbf b)}


\def\Mi{{\mathcal M}}
\newcommand{\VK}{\psi}

\def\bba{{\text{\bf a}}}
\def\bbb{{\text{\bf b}}}
\def\bbc{{\text{\bf c}}}
\def\bbd{{\text{\bf d}}}

\def\bbv{{\text{\bf v}}}


\def\bbx{{\text{\bf x}}}
\def\bby{{\text{\bf y}}}
\def\bbz{{\text{\bf z}}}
\def\cX{\mathcal X}


\def\N{\mathbb{N}}
\def\Z{\mathxbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\IC{{\mathbb{C}}}


\newcommand{\nin}{\noindent}
\newcommand{\sm}{\smallskip}
\newcommand{\ms}{\medskip}
\newcommand{\bs}{\bigskip}

\newcommand{\corn}{{{\text{\rm $v$}}}}
\def\lan{ {\text {\rm la} } }
\def\lc{ {\text {\rm lc} } }
\def\area{ {\text {\rm area} } }

\def\hba{\hslash}


\def\Pt{P^{t}}
\def\Qt{Q^{t}}

\def\St{{\text {\rm St} } }
\def\bT{{\text{\bf T}}}
\def\bSi{{\mathbf \Si}}


\def\co{c_1}
\def\ct{c_2}

\def\rD{\text{{\rm \textbf{D}}}}
\def\rC{\text{{\rm \textbf{C}}}}
\def\rF{\text{{\rm \textsf{F}}}}
\def\rM{\textup{{\rm {M}}}}

%\def\VNP{\mathsf{VNP}}
%\def\VP{\mathsf{VP}}
\def\VPs{\mathsf{VP}_{\mathrm{ws}}}
\def\dc{\mathsf{dc}}
\def\powc{\mathsf{pc}}
\def\Pow{\mathsf{Pow}}

\def\<{\langle}
\def\>{\rangle}

\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}

\def\det{\mathrm{det}}
\def\per{\mathrm{per}}
\def\sgn{\mathrm{sgn}}
\def\GL{\mathrm{GL}}
\def\SL{\mathrm{SL}}

\def\wt{\mathrm{weight}}
\def\rank{\mathrm{rank}}
\newcommand{\chara}{{\mathrm{char}}}
\def\Sym{\mathsf{Sym}}
\newcommand{\Det}{\Omega} 
\newcommand{\ol}[1]{\overline{#1}}
\def\e{\epsilon}
\def\la{\lambda}
\def\pleth{\mathrm{pleth}}
\def\mdet{\mathrm{multdet}}
\def\mult{\mathrm{mult}}
\def\ot{\otimes} 
\def\sP{\#\mathrm{P}}
\def\stab{\mathrm{stab}}
\def\id{\mathrm{id}}
\def\diag{\mathrm{diag}}
\def\ocp{Z}
\newcommand{\kron}{k}
\newcommand{\gctm}{K}
\newcommand{\plethc}{a}

\newcommand{\out}{d}
\newcommand{\inn}{n}
\newcommand{\imm}{m}
\newcommand{\cM}{\mathcal{M}}




\newcommand{\IA}{\ensuremath{\mathbb{A}}}
\newcommand{\IN}{\ensuremath{\mathbb{N}}}
\newcommand{\IZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\IQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\IR}{\ensuremath{\mathbb{R}}}
\newcommand{\IIF}{\ensuremath{\mathbb{F}}}
\newcommand{\IP}{\ensuremath{\mathbb{P}}}
\newcommand{\aG}{\ensuremath{\mathfrak{G}}}
\newcommand{\aE}{\ensuremath{\mathsf{E}}}
\newcommand{\sF}{\ensuremath{\mathscr{F}}}
\newcommand{\sV}{\ensuremath{\mathscr{V}}}
\newcommand{\sW}{\ensuremath{\mathscr{W}}}
%\DeclareMathOperator{\diag}{diag}
\newcommand{\pl}[3]{p_{#1}({#2[#3]})}
\newcommand{\Weyl}[1]{\{{#1}\}}
\newcommand{\Specht}[1]{[{#1}]}
\newcommand{\tensor}{\smash{\textstyle\bigotimes}}
\newcommand{\HWV}{\mathsf{HWV}}
\newcommand{\Id}{\mathrm{Id}}
\DeclareMathOperator{\rowstab}{rowstab}
\DeclareMathOperator{\colstab}{colstab}
\newcommand{\transpose}[1]{{{^t\!}{#1}}}
\newcommand{\leftindex}[2]{\!\!{{^{{\color{white}#2}#1}_{{\color{white}#1}#2}\!}}}
\newcommand{\tinyotimes}{\scalebox{0.9}{$\otimes$}}
\newcommand{\tinycdots}{\scalebox{0.9}{$\cdot\!\!\cdot\!\!\cdot$}}

\newcommand{\Ch}{\textup{\textsf{Ch}}}
\allowdisplaybreaks
%% define your title in the usual way
\title[The Newton polytope of the Kronecker product]{The Newton polytope of the Kronecker product}




%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Greta Panova\thanks{\href{mailto:gpanova@usc.edu}{gpanova@usc.edu}. The author was partially supported  by the NSF.}\addressmark{1} \and Chenchen Zhao\thanks{\href{mailto:zhao109@usc.edu}{zhao109@usc.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Southern California, Los Angeles, CA 90089}


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

\abstract{We study the Kronecker product of two Schur functions $s_\lambda\ast s_\mu$, whose Schur expansion is given by the Kronecker coefficients $g(\lambda,\mu,\nu)$ of the symmetric group. We prove special cases of a conjecture of Monical--Tokcan--Yong that its monomial expansion has a saturated Newton polytope. Our proofs employ the Horn inequalities for positivity of Littlewood--Richardson coefficients and imply necessary conditions for the positivity of Kronecker coefficients. }

\keywords{Kronecker coefficients, saturated Newton polytope, Symmetric group representations}

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


\section{Introduction}

The Kronecker coefficients $g(\la,\mu,\nu)$ of the symmetric group present an 85 year old mystery in Algebraic Combinatorics and Representation Theory. They are defined as the multiplicities of an irreducible $S_n$-module $\mathbb{S}_\nu$ in the tensor product of two other irreducibles: $\mathbb{S}_\la \otimes \mathbb{S}_\mu$.  Originally introduced by Murnaghan in 1938~\cite{Mur38,Mur56}, the question for their computation has been reiterated many times since the 1980s. Stanley's 10th open problem in Algebraic Combinatorics~\cite{Sta00} is to find a manifestly positive combinatorial interpretation for the Kronecker coefficients. Yet, over the years, very little progress has been made and only for special cases, see~\cite{Pan22} for an overview. Their importance has been reinforced by their role in Geometric Complexity Theory, a program aimed at establishing computational lower bounds and ultimately separating complexity classes like $\P$ vs $\NP$, see~\cite{Pan23} and references therein. While no positive combinatorial formula exists, we also lack understanding for when such coefficients would be positive. The possibility of answering these questions in a ``nice'' way is explored using computational complexity theory, see ~\cite{Pak22,Pan23}. 

In a different direction, \cite{Yong} initiated the study of the Newton polytopes of important polynomials in Algebraic Combinatorics. It has since been established that some of the main polynomials of interest have the \emph{saturated Newton polytope} (SNP) property. 

\begin{Def} A multivariate polynomial with nonnegative coefficients $f(x_1,\ldots,x_k)=\sum_{\al} c_\al x^\al$ has a saturated Newton polytope (SNP) if the set of points $M_k(f):=\{(\al_1,\cdots,\al_k): c_\al>0\}$ coincides with its convex hull in $\mathbb{Z}^k$. 
\end{Def}
Given a symmetric function $f$, let $f(x_1,\dots, x_k)$ denote the specialization of $f$ to the variables $x_1,\dots,x_k$ that sets $x_m = 0 $ for all $ m \ge k+1.$
\begin{Def}\label{def:snp_sym_fun} A symmetric function $f$ has a saturated Newton polytope (SNP) if $f(x_1,\dots, x_k)$ has a SNP for all $k \ge 1.$\end{Def}

\subsection{SNP for the Kronecker product}
The \defn{Kronecker coefficients} of $S_n$, denoted by $g(\la,\mu,\nu)$, give the multiplicities of one Specht module in the tensor product of the other two, namely
$$\mathbb{S}_\la \otimes \mathbb{S}_\mu = \oplus_{\nu \vdash n} \mathbb{S}_\nu^{\oplus g(\la,\mu,\nu)}.$$ The Kronecker product $\ast$ of symmetric functions is defined on the Schur basis as 
$$s_\la \ast s_\mu:= \sum_\nu g(\la,\mu,\nu) s_\nu,$$ 
and extended by linearity. It is equivalent to the inner product of $S_n$ characters under the characteristic map. 

\begin{conj}[\cite{Yong}]\label{conj:snp}
The Kronecker product $s_\la*s_\mu$ has a saturated Newton polytope.
\end{conj}

We prove this conjecture for partitions of lengths 2 and 3 and various truncations.
\begin{thm}\label{thm:2row}
Let $\la,\mu \vdash n$ with $\ell(\la)\leq 2, \ell(\mu)\leq 3$, and $\mu_1 \geq \la_1$ then
$s_\la*s_\mu(x_1,\ldots,x_k)$ has a saturated Newton polytope for every $k \in \mathbb{N}$.
\end{thm}

This theorem follows from the Kronecker product containing a term \(s_\nu\), where \(\nu\) dominates all other partitions in the product. As a result, the degree vectors of the monomials are the integer points \((a_1, \ldots, a_k)\) that, when sorted, satisfy \( \text{sort}(a_1, \ldots, a_k) \preceq \nu \) in the dominance order, ensuring the polytope is saturated. However, it is not always the case that there is a unique maximal term with respect to the dominance order. The first instance where no such dominant partition exists is covered in the following theorem.

\begin{thm}\label{thm:main}
Let $\la,\mu \vdash n$ with $\ell(\la)\leq 3$ and $\ell(\mu)\leq 2$. Then 
$s_\la * s_\mu(x_1,x_2,x_3)$ has a saturated Newton polytope. 
\end{thm}

The difficulty with this problem in the general case is the lack of any criterion for the positivity of the Kronecker coefficients. We express the Kronecker product in the monomial basis as sums of products of multi-Littlewood--Richardson coefficients. Using the Horn inequalities, which determine when a Littlewood--Richardson coefficient is nonzero, we construct a polytope $\mathcal{P}(\la,\mu; \mathbf{a})$ parametrized by $\la,\mu$ and $\mathbf{a}=(a_1,\ldots,a_k)$ for the  monomial of interest $x_1^{a_1}x_2^{a_2}\cdots x_k^{a_k}$. 
A monomial appears in $s_\la \ast s_\mu$ if and only if $\mathcal{P}(\la,\mu;\mathbf{a})$ has an integer point, and we can infer the  following.

\begin{prop}\label{cor:int_point_snp}
   Let $\mu,\la \vdash n$. The Kronecker product $s_\la \ast s_\mu (x_1,\ldots,x_k)$ has a saturated Newton polytope if and only if for every $\bba\in \mathbb{Z}^k$ the polytope $\mathcal{P}(\la,\mu;\bba)$ is either empty or has an integer point. 
\end{prop}

It is not hard to see that $\mathcal{P}(\la,\la;\mathbf{a})$ is always nonempty and has an integer point. However, it is far from clear how to characterize when $\mathcal{P}(\la,\mu;\bba) \neq \emptyset$ once $\mu \neq \la$ and the number of variables $k$ grows, and further to determine if there is an integer point. It is also not apparent whether these polytopes have an integer vertex as the relevant inequalities result in many non-integral vertices.

The  limiting version of Conjecture~\ref{conj:snp} holds in general. 
\begin{thm}\label{thm:limit}
Let $\la,\mu$ be partitions of the same size and $k \in \mathbb{N}$. Then the set of points 
$$\bigcup_{p=1}^\infty \frac{1}{p} M_k(s_{p\la}\ast s_{p\mu})$$ is a convex subset of $\mathbb{Q}^k$. 
\end{thm}
This is not surprising since the set of triples $\frac{1}{|\la|}(\la,\mu,\nu)$ for which there is a $p$, such that $g(p\la,p\mu,p\nu)>0$, forms a polytope known as the Moment polytope, see~\cite{vergne2017inequalities,burgisser2017membership}.  

\subsection{Positivity implications}

Suppose that  $g(\la,\mu,\al) >0$ and $g(\la,\mu,\be)>0$ for some partitions $\al,\be$. Then the monomials with powers $\al$ and $\be$ appear in $s_{\la}*s_\mu$. Suppose that $\gamma = t\al+(1-t)*\be \in \mathbb{Z}^k$ for some $t=\frac{p}{q} \in \mathbb{Q}$ with $p<q$. The SNP property would imply that $\gamma$ appears as a monomial, and thus there is a partition $\theta \succ \gamma$, such that $g(\la,\mu,\theta)>0$. 
By the semigroup property we have that $g(p \la, p\mu, p \al)>0$, $g( (q-p) \la, (q-p)\mu, (q-p)\be) >0$ and thus $g(q\la, q\mu, q\ga)>0$. However, the Kronecker coefficients do not, in general, possess the saturation property, so we cannot expect $g(\la,\mu,\ga)>0$ and in fact this is not always true\footnote{ Let $\lambda = (8,8)$ and $\mu = (5,3,1,1,1,1,1,1,1,1)$. Let $\alpha = (7,3,2,2,2)$, $\beta = (5,5,2,2,2)$ and $\nu=(6, 4, 2, 2, 2).$ We have that $g(\lambda,\mu, \alpha) =g(\lambda,\mu, \beta)=1$, but $g(\lambda,\mu, \frac{\alpha+\beta}{2}) = 0$, and $s_\la \ast s_\mu$ does not have a unique dominant term.}. We can generalize the above reasoning into the following.

\begin{prop}\label{cor:snp_positivity}
Suppose that $s_\la * s_\mu$ has a saturated Newton polytope. Then for every collection of partitions $\al^1,\al^2,\ldots$, s.t. $g(\la,\mu,\al^i)>0$ and $\sum_i t_i \al^i $ has integer parts for some $t_i \in  [0,1]$ with $t_1+t_2+\cdots=1$, there exists a partition $\theta \succeq \sum_i t_i \al^i$ in the dominance order, such that $g(\la,\mu,\theta)>0$. 
\end{prop}

Our methods and the Horn inequalities also give some necessary conditions for a Kronecker coefficient to be positive. We cannot expect easy necessary and sufficient criteria for positivity since this decision problem is $\NP$-hard by~\cite{IMW}. The general statement is Theorem~\ref{prop:kron_pos_gen} stated in Section~\ref{s:pos} in terms of the so-called LR-consistent triples. We illustrate the criteria with a simplified version below in the case of one two-row partition. 

\begin{prop}
    Suppose that $g(\la,\mu,\nu)>0$ and $\ell(\mu)=2$, $k=\ell(\la)$. Then there exist nonnegative integers $y_i \in [0, \lfloor \la_i/2 \rfloor ]$ for $i\in[k]$, such that
    \begin{align}
    \sum_{i\in A \cup C} \la_i +\sum_{i \in B }  y_i -\sum_{i\in C} y_i  \leq   \min\{\sum_{j \in J} \mu_j, \sum_{j \in J} \nu_j\}
\end{align}
for all triples of mutually disjoint sets $A \sqcup B \sqcup C \subset[k]$ and $J=\{1,\ldots,r,r+2,\ldots,r+b+1\}$ or $J= \{1,\ldots,r+b-1,r+2b\}$, where $r=2|A|+|C|$ and $b=|B|$.
\end{prop}


The details of the above results, along with full proofs, computations, and additional discussions will appear in the full version of this abstract, available in~\cite{PZ}.



\section{Definitions and tools}\label{s:def}

\subsection{Basic notions from algebraic combinatorics}
We use standard notation from~\cite{Mac} and~\cite[$\S$7]{S1}
throughout the paper.


\ytableausetup{boxsize=2ex}


The irreducible representations of the \emph{symmetric group} $S_n$ are the \defn{Specht modules} $\mathbb{S}_\la$ and are indexed by partitions $\la \vdash n$. The irreducible polynomial representations of  $GL_N(\mathbb{C})$ are the \emph{Weyl modules} $V_\la$ and are indexed by all partitions with $\ell(\la) \leq N$. Their characters are  the Schur functions $s_\la(x_1,\ldots,x_N)$, where $x_1,\ldots,x_N$ are the eigenvalues of $g \in GL_N(\mathbb{C})$.

We will use the standard bases for the ring of symmetric functions $\Lambda$: the \defn{monomial} symmetric functions
$$m_\al(x_1,x_2,\ldots,x_k) = \sum_{\sigma} x_{\sigma_1}^{\al_1}x_{\sigma_2}^{\al_2}\cdots ,$$ where the sum goes over all  permutations $\sigma$ giving different monomials. 

The \defn{Schur functions} $s_\la(x_1,\ldots)$ can be defined as the generating functions for SSYTs of shape $\la$, i.e., $s_\la =\sum_\al K_{\la \al}m_\al.$
We will also use the \defn{homogeneous} symmetric functions $h_\la$ defined as 
$h_k := s_{(k)}=\sum_{i_1 \leq \cdots \leq i_k} x_{i_1}\cdots x_{i_k}$ and $h_\la:= h_{\la_1} h_{\la_2}\cdots$. 

The \defn{Littlewood--Richardson} coefficients $c^{\la}_{\mu\nu}$ are defined as structure constants in $\Lambda$ for the Schur basis, and also as the multiplicities in the $GL$-module decomposition $V_\mu \otimes V_\nu = \oplus_\la V_\la^{c^{\la}_{\mu\nu}}$. We have
$$s_\mu s_\nu = \sum_\la c^{\la}_{\mu\nu} s_\la.$$

They can be evaluated by the \defn{Littlewood--Richardson rule} as a positive sum of skew SSYT of shape $\la/\mu$ and type (weight)~$\nu$ whose reverse reading word is a ballot sequence. Their positivity can be decided in polynomial time as $c^{\la}_{\mu\nu} >0$ if and only if its corresponding polytope is nonempty (see~\cite{KT,MNS}). 
The \defn{multi-LR coefficients} can be defined recursively as
$$c^\la_{\nu^1,\nu^2,\ldots,\nu^k} := \langle s_\la, s_{\nu^1}s_{\nu^2}\cdots s_{\nu^k}\rangle = \sum_{\tau^1,\tau^2,\ldots,\tau^k} c^{\la}_{\nu^1 \tau^1} c^{\tau^1}_{\nu^2 \tau ^2} \cdots c^{\tau^{k-1}}_{\nu^k \tau ^k}.$$


\subsection{The Kronecker product}
The Kronecker product, denoted by $*$, of symmetric functions can be defined on the basis of the Schur functions and extended by linearity:
$s_\la * s_\mu = \sum_\nu g(\la,\mu,\nu) s_\nu.$

It is also ${\rm ch}(\chi^\la \chi^\mu)$, where $\chi$ are the $S_n$ characters and ${\rm ch}$ is the Frobenius characteristic map.
The Kronecker coefficients can be equivalently defined as the coefficients in the expansion
\begin{equation}\label{eq:kron_pleth}
s_\la[x\cdot y] = \sum_{\mu,\nu} g(\la,\mu,\nu) s_\mu(x) s_\nu(y),
\end{equation}
where $[x\cdot y]:= (x_1y_1,x_1y_2,\ldots,x_2y_1,\ldots)$ denote all pairwise products of the two sets of variables.


Via Schur--Weyl duality the Kronecker coefficients can be interpreted as the dimensions of $GL$ highest weight spaces, which then makes the following \defn{semigroup property}, see~\cite{CHM}, apparent:

\emph{If $\al^1, \be^1, \ga^1 \vdash n$ and $\al^2,\be^2,\ga^2 \vdash m$ satisfy $g(\al^i,\be^i,\ga^i)>0$ for $i=1,2$, then $g(\al^1+\al^2, \be^1+\be^2, \ga^1+\ga^2) \geq \max\{ g(\al^1,\be^1,\ga^1), g(\al^2,\be^2,\ga^2)\}$.}

Here we will be concerned with the monomial expansion. Since the homogeneous and monomial bases are orthogonal to each other, i.e. $\langle h_\la ,m_\mu \rangle = \delta_{\la,\mu}$ we have that \begin{align}\label{eq:kron_mon}
s_\la \ast s_\mu = \sum_\nu g(\la,\mu,\nu) s_\nu = \sum_{\nu,\al} g(\la,\mu,\nu) K_{\nu \al} m_\al = \sum_{\al \vdash n} \langle s_\la \ast s_\mu, h_\al\rangle m_\al.
\end{align}

In Section~\ref{s:LRs} we will see further ways of finding the monomial expansion.


\subsection{Newton polytopes}

Let $f(x_1,\ldots,x_k) = \sum_\al c_\al x^\al$ be a polynomial with nonnegative coefficients, where $x^\al := x_1^{\al_1}\cdots x_k^{\al_k}$ and $\al \in \mathbb{Z}_{\geq 0}^k$ is the degree vector. We denote by 
$M_k(f) := \{ \al \in \mathbb{Z}_{\geq 0}^k \, : \; c_\al >0\}$ the set of vectors, for which the corresponding monomial appears in $f(x_1,\ldots,x_k)$. For brevity we will say ``monomial $\al$ appears in $f$''. We denote by $N_k(f):= Conv(M_k(f))$ the convex hull of $M_k(f)$, this is the \defn{Newton polytope} of $f(x_1,\ldots,x_k)$. Thus,  
a polynomial $f$ has a \defn{saturated Newton polytope} if and only if $M_k(f) = N_k(f)$.
In particular, a polynomial $f$ has an SNP if and only if the following condition holds: 
\begin{align} 
\label{eq:snp}\tag{snp}
 \text{For every $k+1$-tuple of compositions $(\al^1,\ldots,\al^{k+1})$, such that $c_{\alpha^i}>0$, and } \\ \notag
 \text{ weights $t_i \in[0,1]$, such that $t_1+\cdots+t_{k+1}=1$ and $\gamma := \sum_{i=1}^{k+1} t_i \alpha^i \in \mathbb{Z}^k$, we have $c_\gamma >0$.}
\end{align}
Note that it is enough to check the convex combination of $k+1$ points in $k$-dimensional space by Caratheodory's theorem. 


As noted in~\cite{Yong} many of the important symmetric polynomials have SNP.
Since Kostka coefficients $K_{\la\mu}$ are positive if and only if $\la \succ \mu$ in the dominance order, we get an immediate characterization of $M_k(s_\la)$ and the following important statement. 

\begin{prop}[\cite{Yong}]\label{prop:schur_polytope}
The Schur polynomial $s_\la(x_1,\ldots,x_k)$ has a saturated Newton polytope and
$M_k(f) = conv\{ (\la_{\sigma_1},\ldots,\la_{\sigma_k} ) \text{ for all } \sigma\in S_k\}.$
\end{prop}



\section{Two and three-row partitions}\label{s:2-3-row}
In this section, we deduce the SNP property for certain cases from existing formulas. In the cases treated here we will see that 
there will be a unique partition $\nu$, s.t. $g(\la,\mu,\nu)>0$ and if $g(\la,\mu,\al)>0$ then $\nu \succ \al$ and so $s_\la \ast s_\mu$ will contain all monomials $\al \prec \nu$, as observed in~\cite{Yong}.



First, let $\ell(\la), \ell(\mu) =2$ and the number of variables be arbitrary. In~\cite{rosas}, Rosas computed the Kronecker product of two two-row partitions. In particular, \cite[Corollary 5]{rosas} gives a formula for Kronecker coefficients indexed by 3 two-row partitions. We could then show that 
$N(s_\la*s_\mu; k) = N(s_\nu;k)$ for a certain partition $\nu$. 




\begin{lemma}\label{lem:maximal-two-row} Let $\lambda = (\lambda_1, \lambda_2)$, $\mu = (\mu_1,\mu_2)$, and $\nu = (\nu_1,\nu_2)$ be two-row partitions of $n$. Without loss of generality, suppose that $\la_2 \ge \mu_2$. Then $\langle s_{\la}\ast s_{\mu}, h_{\nu}\rangle > 0$ if and only if $\nu_2 \ge \la_2-\mu_2 .$
\end{lemma}
By equation~\eqref{eq:kron_mon} this means that $m_\nu$ appears with a nonzero coefficient in that Kronecker product. 

We now move to a more general case and invoke the full Theorem from~\cite{rosas}.
Specifically, \cite[Theorem 5]{rosas} gives a formula for Kronecker products of 2 two-row partitions, allowing us to show that there is a unique maximal term in dominance order in the Kronecker product $s_\la \ast s_\mu$ in the following case.

\begin{prop}[Theorem \ref{thm:2row}]\label{prop:2-3-row1}
Let $\la$ and $\mu$ be partitions of $n$, where $\la = (\la_1,\la_2)$ and $\mu = (\mu_1,\mu_2,\mu_3)$, such that $\mu_1 \ge \la_1$. Then the Kronecker product $s_\la \ast s_\mu(x_1,\dots,x_k)$ has a saturated Newton polytope for every $k$.
\end{prop}

\begin{rem}
We cannot expect to have unique maximal terms in general. For instance, $s_{(6,6)}\ast s_{(8,2,1,1)} = s_{(4, 4, 2, 1,1)} + s_{(4, 4, 3, 1)} + s_{(5, 3, 1, 1, 1, 1)} + s_{(5, 3, 2, 1, 1)} + s_{(5, 3, 2, 2)} + s_{(5, 3, 3, 1)} + 2s_{(5, 4, 1, 1, 1)}\\ + 3s_{(5, 4, 2, 1)} + s_{(5, 4, 3)} + s_{(5, 5, 1, 1)} + 2s_{(5, 5, 2)} + s_{(6, 2, 2, 1, 1)} + 2s_{(6, 3, 1, 1, 1)} + 3s_{(6, 3, 2, 1)} + s_{(6, 3, 3)} +\\ 4s_{(6, 4, 1, 1)} + 2s_{(6, 4, 2)} + 2s_{(6, 5, 1)} + s_{(7, 2, 1, 1, 1)} + s_{(7, 2, 2, 1)} + 2s_{(7, 3, 1, 1)} + 2s_{(7, 3, 2)} + 2s_{(7, 4, 1)} + s_{(7, 5)} + s_{(8, 2, 1, 1)} + s_{(8, 3, 1)}.$ In this product, $(7,5)$ and $(8,3,1)$ are incomparable maximal.
\end{rem}

\section{Multi-LR coefficients and Horn inequalities}\label{s:LRs}

\subsection{Monomial expansion via multi-LR coefficients}
As we observed, the Kronecker product does not necessarily have a unique dominating term $s_\nu$. Moreover, there are no positive formulas for many other cases we could use. We thus move directly towards the monomial expansion. The coefficient at $\bbx^\bba$, where $\bba =(a_1,a_2,\ldots)$ in $s_\la \ast s_\mu$ can be expressed as
\begin{equation}\label{eq:mon_LR}
\langle s_\la(y) \ast s_\mu (z) , h_\bba[yz] \rangle =  \langle s_\la(y) \ast s_\mu (z), \prod_i \sum_{\al^i \vdash a_i} s_{\al^i}(y) s_{\al^i}(z) \rangle
= \sum_{ \al^i \vdash a_i, i=1,...} c^{\la}_{\al^1\al^2\cdots} c^{\mu}_{\al^1\al^2 \cdots}
\end{equation}


We now define the following set of points given by the concatenation of the vectors $\al^1,\al^2,\ldots,\al^k$:
\begin{align}\label{eq:p_mu_a}
P(\mu; \bba):= \{ (\al^1, \al^2,\cdots,\al^k) \in \mathbb{Z}_{\geq 0}^{\ell(\mu)k} :  c^{\mu}_{\al^1\al^2\cdots}>0 \text{ and } |a^i|=a_i \text{ for all }i=1,\ldots,k\}.
\end{align}
Observe that $P(\mu;\bba) \neq \emptyset$ for all $\mu, \bba$ of the same size. This can be seen either by a greedy algorithm to construct $\al^1,\ldots$ a nonzero multi-LR coefficient, or by observing that $s_\mu \ast s_\mu = s_{(n)} + \cdots$ and contains every monomial of degree $n$, so for every $\bba$ there are some $\al^i \vdash a_i$ with $c^{\mu}_{\al^1\cdots} >0$. The monomials appearing in $s_\la \ast s_\mu$  correspond to $\bba$, for which there exist $\al^1,\cdots$ with $c^\la_{\al^1\cdots}>0$ and $c^{\mu}_{\al^1\cdots}>0$. Thus
\begin{prop}\label{prop:kron_monomials}
The set of monomial degrees $\bba=(a_1,\ldots,a_k)$ appearing in $s_\la \ast s_\mu$ is given as
$$M_k(s_\la \ast s_\mu) = \{ \bba \in \mathbb{Z}^k_{\geq 0}: P(\la;\bba) \cap P(\mu;\bba) \neq \emptyset\}.$$ 
\end{prop}
We turn towards understanding the above set of points, and in particular, whether they would be the set of lattice points of a convex polytope. 


\subsection{Horn inequalities for multi-LR's}


We first reduce our multi-LR positivity problem from~\eqref{eq:mon_LR} and~\eqref{eq:p_mu_a} to the case of regular LR coefficients.
Let again $c^{\mu}_{\alpha^1,\alpha^2,\ldots} = \langle s_{\alpha^1} s_{\alpha^2} \cdots, s_\mu \rangle$ be  the multi-LR coefficients.


\begin{thm}[\cite{vanleeuwen1999littlewoodrichardson}]\label{thm:vlee}
Let $\lambda,\mu,\nu$ be partitions such that $|\lambda| = |\mu| + |\nu|$.
Then $c^{\lambda}_{\mu,\nu} = \langle s_\lambda, s_{\mu\diamond \nu}\rangle$,
where $\mu \diamond \nu$ denotes the skew shape $(\nu_1^{\ell(\mu)}+\mu,\nu)/\nu$.
\end{thm}

We can thus generalize Theorem \ref{thm:vlee} as follows.

\begin{lemma}\label{lem:multiLR-ordinary}
Let $\la \vdash n$. For a $k$-tuple of partitions $\al^1,\cdots, \al^k$ with $\ell(\al^i) \leq \ell$, such that $|\al^1|+\cdots+|\al^k|=n$ we have that
$c^{\la}_{\al^1\cdots \al^k} = \langle s_\la, s_{\al^1 \diamond \al^2 \diamond \cdots \diamond \al^k} \rangle = c^{\omega(\al)}_{\la, \, \delta_k(n,\ell)}$,
where $\al^1 \diamond \al^2 \diamond \al^3 \cdots = \al^1 \diamond (\al^2 \cdots)$ recursively,
$ \omega(\al) := ( (n(k-1))^{\ell} + \al^1, (n(k-2))^\ell + \al^2, \cdots ,\al^k ),$
and $\delta_k(n,\ell) :=  \left( (n(k-1))^{\ell} , (n(k-2))^\ell , \cdots ,n^\ell \right).$
\end{lemma}


We next turn to LR positivity as described by the Horn inequalities. 
For a subset $I = \{i_1< i_2 < \dots < i_s\} \subset [r]$, let $\rho(I)$ denote the partition $\rho(I) := (i_s-s,\dots,i_2-2,i_1-1).$ We say a triple of subsets $I, J, K \subset [r]$ is \defn{LR-consistent} if they have the same cardinality $s$ and $c^{\rho(I)}_{\rho(J),\rho(K)} =1.$

\begin{thm}[\cite{zelevinsky1997littlewoodrichardson,klyachko,KT}]\label{thm:horn}
    Let $\lambda,\mu,\nu \in \mathbb{N}^r$ with weakly decreasing component. Then $c^\lambda_{\mu,\nu} >0$ if and only if $|\lambda| = |\mu| + |\nu|$ and $\sum_{i\in I}\lambda_i \le \sum_{j\in J}\mu_j+\sum_{k\in K}\nu_k$ for all $LR$-consistent triples $I,J,K \subset [r]$.
\end{thm}

For a set $I \subset \{1,\ldots, \ell k\}$ construct the set $D(I):= \{ (i,j) \in [k]\times[\ell], \text{ such that } \ell(i-1)+j \in I\}$, that is the set of pairs $( \lceil \frac{x}{\ell} \rceil , x\% \ell),$ where $x \in I$ and $x \% \ell$ is its remainder by division by $\ell$, adjusted to be in the range from $1$ to $\ell$.
Applying Theorem~\ref{thm:horn} with $\la = \omega(\al)$, $\mu$ and $\nu = \delta_k(n,\ell)$ from Lemma~\ref{lem:multiLR-ordinary}, and observing that
if $m=\ell(i-1) + j$ then $\omega(\al)_m = n(k-i) +\al^i_j$ and $(\delta_k(n,\ell))_m = n(k-i)$ we get the following.

\begin{Cor}\label{cor:polytope_horn}
Let $\ell(\mu)=\ell$ and $\bba=(a_1,\ldots,a_k)$. Then $P(\mu;\bba)$ is the set of points $(\al^1,\ldots,\al^k) \in \mathbb{Z}_{\geq 0}^{\ell k}$ satisfying the following linear conditions. 
\begin{align}
    \sum_j \al^i_j &\quad = \quad a_i, \qquad \text{ for }i\in[k];\\
    \al^i_j &\quad \geq \quad \al^i_{j+1},  \qquad \text{ for }j\in[\ell-1], \, i\in[k]; \\
    \sum_{ (i,j) \in D(I) } \left( n(k-i) +\al^i_j \right) &\quad \leq \quad \sum_{j \in J} \mu_j + \sum_{ (d,r) \in D(K)}  n(k-d) ,  \label{eq:all inequalities}
\end{align}
where the last inequalities hold for all LR-consistent triples $I,J,K \in[\ell k]$.
\end{Cor}


\subsection{The case for \texorpdfstring{$k=3$}.}
As we know the values of LR coefficients for the triples of partitions $\rho(I), \rho(J), \rho(K)$ when $|I|\leq 6$, we can write all the linear inequalities defining the set of $(\la,\mu,\nu)$ with $\ell(\la),\ell(\mu),\ell(\nu)\leq 6$ and see that they are the integer points in a convex polytope. In general this polytope is quite complicated and it is not known whether it has any integral nonzero vertices. We will approach the first cases beyond Section~\ref{s:2-3-row}. 

We will restrict ourselves to the Kronecker product of a two-row and a three-row partition and monomials $x_1^{a_1}x_2^{a_2}x_3^{a_3}$. Let $\ell(\la) =2$ and $\ell(\mu)=3$.
Our goal is to describe $P(\la;a_1,a_2,a_3) \cap P(\mu;a_1,a_2,a_3)$. 
Applying Corollary~\ref{cor:polytope_horn} to $\la$, $(a_1,a_2,a_3)$ and $\mu,(a_1,a_2,a_3)$, we have
\begin{align}\label{eq:c_nu_mu_pos_2}
c^\mu_{\alpha^1,\alpha^2,\alpha^3}c^\la_{\al^1,\al^2,\al^3}>0 \text{ if and only if}\qquad \qquad \qquad \qquad\qquad & \\
\notag  \max \{\alpha^1_1,\alpha^2_1,\alpha^3_1, \alpha^1_2+\alpha^2_2, \alpha^1_2+\alpha^3_2,\alpha^2_2+\alpha^3_2\} &\le  \mu_1\\
    \notag \max \{\alpha^1_2,\alpha^2_2,\alpha^3_2\}  &\le \mu_2 \\
    \notag \alpha^1_2+\alpha^2_2+\alpha^3_2 &\le  \la_2 \\
  \notag   \max \{\alpha^1_1+\alpha^2_2+\alpha^3_2,\alpha^1_2+\alpha^2_1+\alpha^3_2,\alpha^1_2+\alpha^2_2+\alpha^3_1 \} &\le \min\{ \mu_1+\mu_3, \la_1\} \\
    \notag \max \{\alpha^1_1+\alpha^2_1+\alpha^3_2,\alpha^1_2+\alpha^2_1+\alpha^3_1,\alpha^1_1+\alpha^2_2+\alpha^3_1 \} &\le  \mu_1+ \mu_2\\
    \notag \max \{\alpha^1_1+\alpha^1_2+\alpha^2_2+\alpha^3_2,\alpha^1_2+\alpha^2_1+\alpha^2_2+\alpha^3_2,\alpha^1_2+\alpha^2_2+\alpha^3_1 +\alpha^3_2\} &\le \mu_1+\mu_2.
\end{align}



\subsection{The set \texorpdfstring{$P(\la;\bba) \cap P(\mu;\bba)$}{}}

The linear inequalities~\eqref{eq:c_nu_mu_pos_2} describe a polytope in $\mathbb{R}^6$ for the variables $(\al^1_1,\al^1_2,\ldots)$. By Section~\ref{s:LRs} a monomial $\bbx^\bba$ occurs in $s_\la \ast s_\mu$ if and only if the set $P(\la;\bba) \cap P(\mu;\bba)$ has a nonzero integer point. This set corresponds to the set of lattice points of the section of the polytope in~\eqref{eq:c_nu_mu_pos_2} with $\al^i_1+\al^i_2=a_i$ for $i=1,2,3$, as well as $\al^i_1 \geq \al^i_2$, which comes from  $\al^i$s being partitions. Let $x:=\al^1_1, y:=\al^2_1, z:=\al^3_1$. Define $\mathcal{P}(\la,\mu,\bba)$ to be that polytope, substituting the new constraints in~\eqref{eq:c_nu_mu_pos_2}, it is defined by the following inequalities
\begin{align}
\notag \mathcal{P}(\la,\mu,\bba): =\Bigg\{(x,y,z) \in \mathbb{R}^3 \text{ s.t. } \, a_1 - \min(\mu_2, \la_2, \frac{a_1}{2}) &\le x \le \min(a_1,\mu_1)\label{eqn1}
\tag{1}\\
a_2-\min(\mu_2, \la_2, \frac{a_2}{2}) &\le y \le \min(a_2,\mu_1) \label{eqn2}
\tag{2}\\
a_3- \min(\mu_2, \la_2,\frac{a_3}{2}) &\le z \le \min(a_3,\mu_1) \label{eqn3}
\tag{3} \\
\max(\mu_3, a_1+a_2-\mu_1) &\le x+y \label{eqn4}
\tag{4}\\
\max(\mu_3, a_1+a_3-\mu_1) &\le x+z \label{eqn5}
\tag{5}\\
\max(\mu_3, a_2+a_3-\mu_1) &\le y+z  \label{eqn6}
\tag{6}\\
\la_1 &\le x+y+z \label{eqn7}
\tag{7}\\
\max(\mu_2,\la_2) -a_1 &\le -x+y+z \le \mu_1+\mu_2-a_1\label{eqn8}
\tag{8}\\
\max(\mu_2,\la_2) -a_2 &\le x-y+z \le \mu_1+\mu_2-a_2 \label{eqn9}
\tag{9}\\
\. \max(\mu_2,\la_2) -a_3 &\le x+y-z \le \mu_1+\mu_2-a_3 \Bigg\} \label{eqn10}
\tag{10}
\end{align}

We can summarize these descriptions and derivations in the following. 

\begin{prop}\label{prop:2-3row2}
The monomial $\bbx^\bba$ occurs in $s_\la\ast s_\mu$ if and only if $P(\la;\bba) \cap P(\mu;\bba) \neq \emptyset$. When $\ell(\la)=2, \ell(\mu)=3$ and $\mu_1<\la_1$ this is equivalent to $\mathcal{P}(\la,\mu,\bba) \cap \mathbb{Z}^3 \neq \emptyset$.
\end{prop}


\section{Integer points in \texorpdfstring{ $\mathcal{P}(\la,\mu,\bba)$}{}}\label{s:int_points}

We are now ready to prove the counterpart of Proposition~\ref{prop:2-3-row1} by analyzing the polytope $\mathcal{P}(\la,\mu,\bba)$. By considering $\mathcal{P}(\la,\mu, \bbc)$ as a fiber of a linear projection from a polyhedral cone, we have the following proposition.

\begin{prop}\label{prop:average_polytope}
Suppose that $\mathcal{P}(\la,\mu, \bba^i) \neq \emptyset$  for some vectors $\bba^i$, $i=1,\ldots,4$ and $\bbc =\sum_i t_i \bba^i$ for some $t_i\in[0,1]$ with $t_1+t_2+t_3+t_4=1$. Then  $\mathcal{P}(\la,\mu, \bbc)\neq \emptyset$.
\end{prop}

\begin{proof}[Proof sketch]
The inequalities defining $\mathcal{P}(\la,\mu,\bba)$ can be written in the form $A [x,y,z]^T \leq \bbv$ for a $3 \times 3$ matrix $A$ with entries $\{0,1,-1\}$ and vector $\bbv = B_1 [\la_1,\la_2]^T + B_2 [\mu_1,\mu_2,\mu_3]^T + B_3 [a_1, a_2,a_3]^T$. Assuming $\mathcal{P}(\la,\mu,\bba^i) \neq \emptyset$ for all $i$, we can show that $p:=\sum_i t_i p_i$ where $p_i \in \mathcal{P}(\la,\mu,\bba^i)$ satisfies the inequalities for $\mathcal{P}(\la,\mu,\bbc)$ and this polytope is hence nonempty. \end{proof}   
We will now show this polytope is nonempty if and only if it has an integer point. 
\begin{thm}\label{thm:int_point}
If $\mathcal{P}(\la,\mu,\bba) \neq \emptyset$ then it has an integer point, i.e. $\mathcal{P}(\la,\mu,\bba)\cap \mathbb{Z}^3 \neq \emptyset$.
\end{thm}

\begin{proof}[Proof sketch]
We first show that if a polytope $\mathcal{P}=\mathcal{P}(\la,\mu,\bba)$ is nonempty, it contains a half-integer point by discussing cases for different types of matrices defining the polytope and proving that, in each case, there exists a half-integer point near a vertex of $\mathcal{P}$. We then extend this result by showing that if $\mathcal{P}$ contains a half-integer point, it must contain an integer point.  Our proof considers perturbations of a given half-integer point, showing that small adjustments lead to integer points within $\mathcal{P}$. Exploiting the integer bounds of the inequalities is key to bridge the gap between half-integer and integer points.
\end{proof}



\begin{proof}[Proof of Theorem~\ref{thm:main}]
Let $x_1^{a^i_1}x_2^{a^i_2}x_3^{a^i_3}$ be monomials appearing in $s_\la \ast s_\mu (x_1,x_2,x_3)$ with non zero coefficients. By Proposition~\ref{prop:2-3row2} we have that $\mathcal{P}(\la,\mu;\bba^i) \cap \mathbb{Z}^3 \neq \emptyset$. Suppose that $(c_1,c_2,c_3)$ is in the convex hull of $\{ \bba^i \}_i$, so $\bbc = \sum_i t_i \bba^i$ for some $t_i \in [0,1]$ with $t_1+t_2+\cdots=1$. By Proposition~\ref{prop:average_polytope} we have that $\mathcal{P}(\la,\mu,\bbc) \neq \emptyset$. Then if $c_i \in \mathbb{Z}$ by Theorem~\ref{thm:int_point} we have $\mathcal{P}(\la,\mu;\bbc) \cap \mathbb{Z}^3 \neq \emptyset$ and thus ${\bf x}^\bbc$ appears as a monomial in $s_\la \ast s_\mu$. By the characterization \eqref{eq:snp}, the polynomial $s_\la \ast s_\mu(x_1,x_2,x_3)$ has a saturated Newton polytope. 
\end{proof}

\section{Positivity of Kronecker coefficients}\label{s:pos}

First, we will discuss the limiting case of the SNP property. 

\begin{proof}[Proof sketch of Theorem~\ref{thm:limit}]
By Caratheodory's theorem, it suffices to show that if every point is a convex combination of $k+1$ points from our set and is contained in the set, then the set is convex. Consider points $\al^1, \al^2, \cdots, \al^{k+1} \in \bigcup_{p=1}^\infty \frac{1}{p} M_k({p\la}, {p\mu})$ where $M_k(p\la,p\mu):=M_k(s_{p\la}\ast s_{p\mu})$. For each \(\alpha^i\), choose \(p_i\) such that \(\alpha^i \in \frac{1}{p_i} M_k(p_i \lambda, p_i \mu)\). Let $p = lcm(p_1,\ldots,p_k)$. Employing the semigroup property, establish that \(\alpha^i \in \frac{1}{p} M_k(p\lambda, p\mu)\) for all \(i\). Suppose \(\theta\) is a rational convex combination of \(\alpha^1, \alpha^2, \ldots, \alpha^{k+1}\). Apply the semigroup property to show that \(\theta\) is in \(\frac{1}{qp} M_k(qp\lambda, qp\mu)\) for some carefully chosen $q \in \mathbb{Z}$, implying convexity of the set by Caratheodory's theorem.
\end{proof}


We next consider positivity criteria for Kronecker coefficients. Suppose that $g(\la,\mu,\nu)>0$, then $s_\nu$ appears in $s_\la \ast s_\mu$, and so its leading monomial $m_\nu$ also appears, so $\mathcal{P}(\la,\mu,\nu)\cap \mathbb{Z}^{r} \neq \emptyset$, where $r = \min\{ \ell(\la),\ell(\mu) \} \ell(\nu)$. Then from Section~\ref{s:LRs} we must have that $P(\la;\nu) \cap P(\mu;\nu)$ has an integer point. We can then apply Corollary~\ref{cor:polytope_horn} and its inequalities to infer that the polytope $\mathcal{P}(\la,\mu,\nu)$ has an integer point. 

We define an mLR-consistent triple $(I,J,K)$ of subsets of $[1,\ldots,\ell k]$ as an LR-consistent triple satisfying the condition that $|I \cap [ \ell(j-1)+1,\ldots, \ell j]|=|K \cap [\ell(j-1),\ldots, \ell j]|$ for every $j=1,\ldots,k$.
\begin{thm}\label{prop:kron_pos_gen}
    Suppose that $g(\la,\mu,\nu)>0$ and let $\ell=\min\{\ell(\mu),\ell(\nu)\}$ Then there exist nonnegative integers $\{\al^i_j\}_{i\in[k],j\in[\ell]}$ satisfying
     \begin{align}
    \sum_j \al^i_j & =   \la_i, & \text{ for }i\in[k];\\
    \al^i_j & \geq   \al^i_{j+1},  & \text{ for }j\in[\ell-1], \, i\in[k]; \\
    \sum_{ (i,j) \in D(I)} \al^i_j & \leq   \min\{\sum_{j \in J} \mu_j, \sum_{j \in J} \nu_j\}, & \text{ for every mLR-consistent } (I,J,K). 
\end{align}
\end{thm}

\begin{proof}[Proof sketch of Theorem \ref{prop:kron_pos_gen}]
    For $I,J,K$ to be an LR-consistent triple,  we must have $\rho(K) \subset \rho(I)$, which implies that if $I = \{i_1 < i_2 < \cdots <i_s\}$ and $K=\{ k_1 < \cdots <k_s\}$ then $k_j \leq i_j$ for all $j$. Thus in~\eqref{eq:all inequalities} we have
$\sum_{ (d,r) \in D(K) } n(k-d) \geq \sum_{(i,j) \in D(I)} n(k-i),$
with a difference of at least $n$ if the two sums are not equal. If they are not equal then the inequalities are trivially satisfied. Thus we assume that we have equality. Thus $I= \cup I_p $ and $K= \cup K_p$, where $I_j, K_j \subset [\ell(j-1)+1,\ldots,\ell j]$ and $|I_j|=|K_j|$ and for all such sets, and a set $J$ with $|J| = |I|$ and $c^{\rho(I)}_{\rho(J)\rho(K)}=1$ , which is the definition of mLR-consistent. 
\end{proof}

\acknowledgements{We are grateful to Christian Ikenmeyer, Allen Knutson, Igor Pak, Anne Schilling and Alexander Yong for helpful discussions on the topics.  }

\printbibliography
\end{document}