\documentclass[12pt]{article}
\usepackage{e-jc}

%\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
%%%%%%%%%%%%%%% dodalem JW
\usepackage{color}
%%%%%%%%%%%%
\usepackage[centertags]{amsmath}
% \usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{caption}
\usepackage{newlfont}
\usepackage{verbatim}
\usepackage{amscd}
\usepackage{amsgen}
\usepackage{comment}
%\usepackage{youngtab}
\usepackage{xspace}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{amssymb,amsmath}
\usepackage{amscd}
\usepackage{enumitem}
\usepackage{color}
\usepackage{xy}
\usepackage{graphicx}

% THEOREMS ---------------------------------------------------------------
\theoremstyle{plain}
\newtheorem{thm}{Theorem}%[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{lema}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{obs}[thm]{Observation}
\newtheorem{comp}[thm]{Computation}
%\newtheorem*{ques}{Question}
\newtheorem{ques}[thm]{Question}
%\newtheorem*{tthm}{Theorem}
%\newtheorem{pr}{Program}
%\newtheorem{pro}{Problem}
\theoremstyle{definition}
\newtheorem{df}[thm]{Definition}
\newtheorem{exm}[thm]{Example}
%\newtheorem*{exmm}{Example}
\newtheorem{rem}[thm]{Remark}
\newtheorem{tab}{table}[section]
\newtheorem{fact}[thm]{Fact}

\newtheorem{pr}{Algorithm}
% \newtheorem{constr}{Construction}[section]

%\numberwithin{equation}{section}
%\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\renewcommand{\baselinestretch}{1.2} %%% ----------------------------------------------------------------------
\def\p{\mathbb{P}}
\def\P{\mathbb{P}}
\def\RR{\mathbb{R}}
\def\z{\mathbb{Z}}
\def\n{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\N{\mathbb{N}}
\def\c{\mathbb{C}}
\def\C{\mathbb{C}}
\def\o{\mathcal{O}}
\def\Id{Id}
\def\Eval{Eval}
\DeclareMathOperator{\inte}{int} \DeclareMathOperator{\rk}{Rk}\DeclareMathOperator{\Proj}{Proj}
\DeclareMathOperator{\diag}{diag}\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\sing}{Sing} \DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Sing}{Sing} \DeclareMathOperator{\divi}{div}
\DeclareMathOperator{\Pic}{Pic}\DeclareMathOperator{\rad}{Rad}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\codim}{codim} \DeclareMathOperator{\h}{ht}
\DeclareMathOperator{\Spec}{Spec}
\def\p{\mathbb{P}}
\def\a{\mathbb{A}}
\def\ob{\begin{obs}}
\def\kob{\end{obs}}
\def\dow{\begin{proof}}
\def\kdow{\end{proof}}
\def\kwadrat{\hfill$\square$}
\def\tw{\begin{thm}}
\def\ktw{\end{thm}}
\def\hip{\begin{con}}
\def\khip{\end{con}}
\def\lem{\begin{lema}}
\def\klem{\end{lema}}
\def\ex{\begin{exm}}
\def\prog{\begin{pr}}
\def\kprog{\end{pr}}
\def\wn{\begin{cor}}
\def\kwn{\end{cor}}
\def\uwa{\begin{rem}}
\def\kuwa{\end{rem}}
\def\kex{\end{exm}}
\def\dfi{\begin{df}}
\def\kdfi{\end{df}}
\def\W{\mathcal W}
\setcounter{section}{0}
\def\cA{{\mathcal A}}
\def\cT{{\mathcal T}}
\def\flo{{\mathcal G}}
\def\soc{{\mathcal S}}
\def\g{g}
\def\n{n^-}
\def\pp{p}
\def\b{b}
\definecolor{zielony}{rgb}{0.5, 0.9, 0.1}
\definecolor{czerwony}{rgb}{0.9, 0.2, 0.1}
\definecolor{niebieski}{rgb}{0.3, 0.1, 0.9}
\newcommand{\red}[1]{\color{czerwony} #1 \color{black}}
\newcommand{\green}[1]{\color{zielony} #1 \color{black}}
\newcommand{\blue}[1]{\color{niebieski} #1 \color{black}}
\newcommand{\barvinok}{\textsc{barvinok}\xspace}
\newcommand{\iscc}{\textsc{iscc}\xspace}
\newcommand{\isl}{\textsc{isl}\xspace}
\xyoption{line}
\def\fa{\begin{fact}}
\def\kfa{\end{fact}}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\vol}{Vol}

\usepackage{url}
\usepackage{hyperref}
\definecolor{darkblue}{RGB}{0,0,160}
\hypersetup{
colorlinks,%
citecolor=black,%
filecolor=black,%
linkcolor=darkblue,%
urlcolor=darkblue
}

\renewcommand{\comment}[1]{{$\star$\sf\textbf{#1}$\star$}}

\title{Obstructions to combinatorial formulas for plethysm}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Thomas Kahle\\
\small Fakult\"at f\"ur Mathematik\\[-0.8ex]
\small Otto-von-Guericke Universit\"at\\[-0.8ex] 
\small 39106 Magdeburg, Germany\\
\small\tt thomas.kahle@ovgu.de\\
\and
Mateusz Micha\l ek \\
\small Max Planck Institut for Mathematics in the Sciences\\[-0.8ex]
\small Leipzig, Germany\\[-0.8ex]
\small and\\[-0.8ex]
\small Mathematical Institute of the Polish Academy of Sciences\\[-0.8ex]
\small Warsaw, Poland\\
\small\tt wajcha2@poczta.onet.pl
}

\date{\dateline{??}{??}
\small Mathematics Subject Classifications: Primary: 20G05, 11P21; Secondary: 11H06, 05A16,
52B20, 52B55}
% Primary:
% 	20G05   	Representation theory
%  	11P21   	Lattice points in specified regions
% Secondary:
%  	11H06   	Lattices and convex bodies
%       05A16   	Asymptotic enumeration
% 	52B20   	Lattice polytopes
%       52B55   	Computational aspects related to convexity
%  	20C15   	Ordinary representations and characters

\begin{document}
\maketitle

\begin{abstract}
Motivated by questions of Mulmuley and Stanley we investigate
quasi-poly\-no\-mials arising in formulas for plethysm.  We
demonstrate, on the examples of $S^3(S^k)$ and $S^k(S^3)$, that these
need not be counting functions of inhomogeneous polytopes of dimension
equal to the degree of the quasi-polynomial. It follows that these
functions are not, in general, counting functions of lattice points in
any scaled convex bodies, even when restricted to single rays. Our
results also apply to special rectangular Kronecker coefficients.
\end{abstract}


Many problems in representation theory have combinatorial solutions.
A~well-known, important example is the Littlewood--Richardson rule
which gives the multiplicities of isotypic components in the tensor
product of two irreducible $GL(n)$ representations
\cite{fulton91:_repres_theor}.  The solution is combinatorial in the
sense that the answer is given by the number of lattice points in
explicit rational convex polyhedra, i.e.~the multiplicities are equal
to values of an Ehrhart quasi-polynomial.  Berenstein and Zelevinsky
provided another interpretation of the Littlewood--Richardson
rule~\cite{BZ}, isomorphic, however, on the level of polytopes
\cite{pak2005combinatorics}.  The study of different polyhedral
structures turned out to be very useful.  Knutson and Tao
\cite{knutson1999honeycomb} showed that the honeycomb polytopes (in
spirit similar to \cite{BZ}) are nonempty if and only if they contain
a lattice point.  This was the crucial last step in the solution to
the Horn problem~\cite{horn1962eigenvalues} which goes back to Weyl's
work on eigenvalues of partial differential
equations~\cite{weyl1912asymptotische}.

In this paper we study the more complicated plethysm coefficients
$m^{d,k}_\lambda$ defined~by
\[
S^d(S^k W)=\bigoplus_{\lambda} m^{d,k}_\lambda S^\lambda W,
\]
where the sum is over partitions $\lambda$ of~$dk$.

The computation of the multiplicity functions in plethysms can be seen
as an operation on Schur polynomials~\cite{macdonald1998symmetric}.
Viewed like this, it is surprising that when the plethysm is written
in terms of other Schur polynomials, the coefficients are always
nonnegative.  Of course this must be true, because the coefficients
are multiplicities of irreducible representations, but it would be
desirable to have a combinatorial explanation for nonnegativity.
%
In \cite[Problem~9]{Stanley} Richard Stanley asked for a
\emph{positive} combinatorial method to compute plethysm coefficients.
A connection between plethysm and lattice point counting was shown at
least
in~\cite{KMplethysm,colmenarejo2015stability,christandl2012computing}.
These connections are not direct in the sense that plethysm
coefficients are not seen to equal counts, but always involve some
opaque arithmetics.

The functions $f(s)=m^{d,sk}_{s\lambda}$ and
$g(s)=m^{sd,k}_{s\lambda}$ share many properties with Ehrhart
functions of rational polytopes:
\begin{itemize}
\item Both $f$ and $g$ are nonnegative and $f(0)=g(0)=1$.
\item Both $f$ and $g$ are quasi-polynomials.  This deep fact follows
from~\cite[Corollary~2.12]{meinrenken1999singular}.
See~\cite[Remark~3.12]{KMplethysm}.
\item For regular $\lambda$, the leading term of $f$ is proportional
to the Ehrhart function of a rational polytope corresponding to the
Littlewood--Richardson rule~\cite[Section~4]{KMplethysm}.
\end{itemize}
\begin{rem}
The scaling factor between the leading coefficient of $f$ and the
Ehrhart function in the third bullet is the Plancherel measure on
Young diagrams.  It is conjectured that the same is true for
any~$\lambda$, however we are not aware of a proof.
\end{rem}

\begin{exm}
The multiplicity of $\lambda=s\cdot(2k-1,1)$ inside $S^2(S^{sk})$
equals $0$ when $s$ is odd and $1$ when $s$ even.  In particular, it
is equal to the number of integral points in the (zero-dimensional)
polytope $\{s/2\}$.  The multiplicity of $s\cdot(2k,k)$ inside
$S^3(S^{sk})$ is equal to the number of integral points in the
(one-dimensional) polytope $s\cdot[1/3,1/2]$ or $s\cdot [1/2,2/3]$.
\end{exm}

Ketan Mulmuley posed several conjectures concerning the behavior of
plethysm and Kronecker coefficients in relation to geometric
complexity theory \cite{mulmuley2001geometric,mulmuleyGCT6long}.
\begin{ques}\label{q:combinatorial}
Fix positive integers $k,d$, and $\lambda$ a partition of $kd$.  Are
the quasi-polynomials $s\mapsto m^{d,sk}_{s\lambda}$ and
$s\mapsto m^{sd,k}_{s\lambda}$ Ehrhart functions of rational
polytopes?
\end{ques}
The question about $m^{sd,k}_{s\lambda}$ comes directly from
\cite[Hypothesis~1.6.4]{mulmuleyGCT6long}.  We give a negative answer
for both functions in Remark~\ref{r:ehrhart-proof}.  Our main goal,
however, is a generalized version of these questions for which we need
some additional terminology.  Following
\cite[Section~5.1]{mulmuleyGCT6short} we define a \emph{shifted} or
\emph{inhomogeneous rational polytope} as a system of inequalities
\[
P (A,b,c) = \{x\in\mathbb{Q}^m : Ax \le b+c\},
\]
where $b,c$ are arbitrary rational vectors and $A$ is a rational
matrix.  Splitting the right hand side as $b + c$ is motivated by the
definition of the dilations of $P$ as
\[
P(A,sb,c) = \{x\in\mathbb{Q}^m : Ax \le sb + c\}.
\]
An \emph{asymptotic Ehrhart quasi-polynomial} is a counting function
of the form
\[
s\mapsto \#(P(A,sb,c)\cap\Z^m).
\]
The \emph{dimension} of a shifted rational polytope $P$ is by
definition the dimension of $P(A,sb,c)$ for large~$s$ (for small $s$ the
polytope can be empty).  Contrary to the case of Ehrhart
quasi-polynomials, an asymptotic Ehrhart quasi-polynomial does not
need to be a quasi-polynomial, although it is for large arguments.
Moreover, a quasi-polynomial may be an asymptotic Ehrhart
quasi-polynomial but not an Ehrhart quasi-polynomial.  Asymptotic
Ehrhart quasi-polynomials do not have to satisfy Ehrhart reciprocity.
% See the discussion at the end of this paper for an example.
Further, the dimension of a shifted rational polytope can be strictly
greater than the degree of the associated asymptotic Ehrhart
quasi-polynomial.  See~\cite{stanley1982linear}
and~\cite[Chapter~I]{stanley96:_combin_commut_algeb} for structure
theory of asymptotic Ehrhart quasi-polynomials and the relation to
linear diophantine equations.

In \cite[Hypothesis~5.3]{mulmuleyGCT6short} it is conjectured that the
multiplicity of $s\cdot\pi$ in $S^{s\cdot\lambda}(S^\mu)$ is an asymptotic
Ehrhart quasi-polynomial with additional complexity-theoretic
properties.  The asymptotic part of the conjecture is motivated by the
failure of Ehrhart type explanations already for Kronecker
coefficients~\cite{briand2009reduced,King} which are often considered
less complicated than plethysm coefficients.  In the present paper we
make progress towards a negative answer of the following simplified
version.
% , motivated by the results of~\cite{King}.
% which discards all the complexity theory.
% of~\cite[Hypothesis~5.3]{mulmuleyGCT6short}.
\begin{ques}\label{q:mulmuley2}
Is $m^{sd,k}_{s\lambda}$ an asymptotic Ehrhart quasi-polynomial?
\end{ques}

Our main result, Theorem~\ref{t:main}, implies a negative answer to
both cases in Question~\ref{q:combinatorial} and strong restrictions
on a positive solution to Question~\ref{q:mulmuley2}.  We show that
$m^{sd,k}_{s\lambda}$ need not be an asymptotic Ehrhart
quasi-polynomial of a polytope of dimension equal to the degree of its
growth.  At the moment we are not able either to exclude or confirm
that $m^{sd,k}_{s\lambda}$ is an asymptotic Ehrhart quasi-polynomial
for an inhomogeneous polytope of dimension strictly larger than its
degree.

% As the main result of our
% work, we show that both of the above mentioned multiplicity functions
% for plethysm do not have to come from any shifted rational polytope of
% dimension equal to the degree of the quasi-polynomial. As for
% (homogeneous) rational polytopes the degree of the quasi-polynomial
% equals the dimension of the polytope, this is a stronger statement
% than the one presented in Question \ref{q:combinatorial}. Still, 

In previous work the authors gave a formula for plethysm coefficients,
which is a sum of Ehrhart functions of various polytopes with
(positive and negative) coefficients~\cite{KMplethysm}.  This allows
to gather experimental data on the questions for many rays.
A-posteriori, the specific plethysm in Theorem~\ref{t:main} can also
be confirmed using well-known formulas for $S^3(S^k)$.  General
formulas for $S^k(S^3)$ are unknown, though.  Our methods are inspired
by \cite{King, briand2009reduced}.
\begin{thm}\label{t:main}
The multiplicity functions of $S^{s\cdot(7,5,0)}$ in $S^3(S^{4s})$ and
$S^{4s}(S^3)$ equal
\begin{align*}
  \phi: s & \mapsto \frac{s+r(s)}{3}
%
%
% It also equals (s+1)/3 rounded up or down depending on the parity of s.
% 
% 	    
%  
% 		    \frac{1}{3} \left( s + 6 \left\lfloor \frac{s}{2}
% 		    \right\rfloor + 2 +
% 		    \left\lfloor \frac{s}{3} \right\rfloor -
% 		    \left\lfloor \frac{s-1}{3} \right\rfloor -
% 		    \left\lfloor \frac{s-2}{3} \right\rfloor +
% 		    \left\lfloor \frac{s-3}{3} \right\rfloor \right) \\
%    &\,\, =  \frac{1}{3} s + 2 \left\lfloor \frac{s}{2}
%       \right\rfloor + \frac{2}{3} +
%       \begin{cases}
%       1/3 & \text { if $s\equiv 0 \mod 3$ }\\
%       0 & \text { if $s\equiv 1 \mod 3$ }\\
%       -1/3 & \text { if $s\equiv 2 \mod 3$ }\\
%       \end{cases}
\end{align*}
where $r(s)$ has period $6$ and takes the values $3,-1,1,0,2,-2$ on
respectively the integers $0,\dots,5$.  There do not exist rational
vectors $a,b,c \in\mathbb{Q}^n$ (of arbitrary length $n$) such that
$\phi$ equals the counting function of a one-dimensional inhomogeneous
polytope $P(a,b,c)$.
% \[
% \{x\in\mathbb{Q} : ax \le b + c\}.
% \]
%
In particular, $\phi$ is not an Ehrhart function of any rational
polyhedron.
% No
% positive combination of Ehrhart functions of rational polyhedra
% equals~$\phi$.
\end{thm}
\begin{rem}\label{r:ehrhart-proof}
Before giving a general proof, it is easy to see that $\phi$ cannot
be an Ehrhart function: it violates Ehrhart--Macdonald
reciprocity~\cite{ehrhart1967I,macdonald1971polynomials}.  The value
$f(-s)$ of an Ehrhart quasi-polynomial $f$ of a rational polytope $P$
at a negative integer argument counts (up to a global sign) the number
of interior lattice points in~$s\cdot P$.  In particular,
$|f(-s)|\leq f(s)$.  However,
\[
-\phi(-1)=1>0=\phi(1).
\]
% The first 7 values of the function $\phi$ in the theorem are
% $1,0,1,1,2,1,3$.  One can without much trouble observe that this can
% not be an Ehrhart function using the jump down from $1$ to $0$ and
% then the $2,1,3$ pattern.
Interestingly, the jumps in values that make Ehrhart reciprocity fail
are also the crucial ingredient for our proof of non-representability
by a one-dimensional inhomogeneous polytope.
%This statement gives a counterexample to Mulmuley's original question
%from the arXiv version [... exact reference from referee reply].
\end{rem}
% There are also several ways to exclude $\phi$ from being an Ehrhart
% function.  The easiest is to note that the polytope would have to be
% of dimension $1$ and volume~$4/3$.  Since $\phi(6)=9$, six times the
% polytope is a lattice polytope.  This reduces the problem to
% checking a finite number of intervals as candidates for the
% polytope, none of which has $\phi$ as its Ehrhart function.
\begin{proof}
The equality of the multiplicities of the given ray in both plethysms
is a consequence of Hermite reciprocity \cite{hermite1854},
\cite[Exercise~6.18]{fulton91:_repres_theor}.  There are now various
ways to determine the formula from the interpretation as a
multiplicity in $S^3(S^{4s})$.  One is to simply evaluate the explicit
formula from~\cite{KMplethysm} along a ray.  Another way is to observe
that the function must exhibit linear growth and that its period is at
most six~\cite{CGR83, manivel2014secants}.  With this information and
some values the function can be interpolated.

Let $P$ be an inhomogeneous line segment as in the statement.  Then
the $s$-th dilation of $P$ can be written as
\[
P (s) = \{x\in\Q: \max_i (sb_i + c_i) \le x \le \min_i (sb'_i + c'_i)\}.
\]
Asymptotically, $P(s)$ becomes an interval of length~$\frac{s}{3}$.
This means that there exists an $s_0$ such that for all $s > s_0$
\begin{equation}\label{eq:main_bound}
P(s) = \{x\in\Q: s b + c \le x \le s(b+\textstyle\frac{1}{3}) + c')\} =: Q(s),
\end{equation}
for some $b,c,c'\in\Q$.  Making $s_0$ even larger it can be assumed
that $s_0b$ are integers and that $s_0$ is divisible by~6 (the period
of~$\phi$).  Since $\#Q(s)$ and $\#P(s)$ have the same linear term and
constants that are $s_0$-periodic (by the divisibility assumptions)
they agree for all~$s$.

The proof of nonexistence of the family $Q(s)$ such that
$\phi(s) = \#Q(s)$ is by examination of constraints on $b$, coming
from the known values of the counting function~$\phi$.  Without loss
of generality we have
\begin{equation}
\label{eq:shiftP2} 0 \le b < 1.  % By shifting $d$ by integers
\end{equation}
Indeed, changing $b$ by an integer also only shifts $Q$ by an integral
value.

As $\phi(5)+2=\phi(6)$ there must be at least two integers $x$ such
that $5(b+\frac{1}{3})+c'<x\leq 6(b+\frac{1}{3})+c'$. Hence,
$b+\frac{1}{3}>1$.  In particular, for any $s$ there is always at
least one integer $x$ satisfying
$s(b+\frac{1}{3})+c'<x\leq (s+1)(b+\frac{1}{3})+c'$ (an interval of
length $>1$ must contain an integer). On the other hand, by
\eqref{eq:shiftP2} there is at most one integer $x$ satisfying
$sb+c'<x\leq (s+1)b+c'$ (an interval of length $<1$ may contain at
most one integer).  The above two intervals are the difference between
$P(s)$ and $P(s+1)$.  It follows that $\phi(s)$ is nondecreasing. This
contradicts $\phi(0)=1>0=\phi(1)$.
\end{proof}

\begin{rem}
We have confirmed that all examples with two rows and fewer boxes are
in fact Ehrhart functions.  In this sense, our counter-example is
minimal.
\end{rem}

\begin{rem}
A different way to describe an inhomogeneous polytope is by linear
integral equations and nonnegativity.  In this setting Stanley gave a
general reciprocity theorem which relates the Hilbert series (expanded
at $\infty$) of the module of positive integral solutions of linear
Diophantine equations to the Hilbert series of negative solutions to
the same equations.  In \cite[Theorem~4.2]{stanley1982linear} there
are, however, combinatorially defined correction terms.
\end{rem}

% In the remainder of this note we discuss some ramifications of the
% theorem.
% 

\begin{rem}
While this is not visible from the representation
in~\cite{KMplethysm}, a general theorem of Meinrenken and Sjamaar
\cite{meinrenken1999singular} implies that the chambers of plethysm
quasi-polynomials are polyhedral cones (see
\cite[Remark~3.12]{KMplethysm}, \cite{paradan2015witten}).  One may
thus ask the stronger question if they are Ehrhart quasi-polynomials
in general.  Of course, Theorem~\ref{t:main} gives a negative answer
to this much stronger property too.
\end{rem}


Lattice point counting in polytopes and Ehrhart functions are arguably
the most natural combinatorial explanations one may hope for here, but
they are not the only ones. Our theorem also excludes other
possibilities.
\begin{cor}
The plethysm coefficients are not positive combinations of counting
functions of lattice points in integral scalings of any convex
regions.
\end{cor}
\begin{proof}
One-dimensional convex sets are polyhedra and the counting function in
Theorem~\ref{t:main} would need to specialize to a positive
combination of Ehrhart functions.
\end{proof}
% One could ask next if the plethysm quasi-polynomials are counting
% functions of any other, necessarily nonconvex, shapes.  In principle
% there could be a nonconvex cone that projects to the weight space and
% the counting function of lattice points in the fibers coincide with
% the plethysm multiplicities.
%
The plethysm counting function in Theorem~\ref{t:main} cannot be
written as a positive combination of Ehrhart quasi-polynomials as
these also have to satisfy Ehrhart reciprocity.  However, it can be
written as a sum of an asymptotic Ehrhart quasi-polynomial and an
honest Ehrhart quasi-polynomial as in the following proposition (which
is very easy to confirm).
\begin{prop}\label{p:sum}
Fix a small rational $\varepsilon > 0$. Let
$P(s) =  [\varepsilon,s\cdot\frac{1}{3}+\varepsilon]$ and
$Q(s) = s\cdot \{\frac{1}{2}\}$.  Then
$\phi(s) = \#(P(s)\cap\Z) + \#(Q(s) \cap \Z)$.
\end{prop}

\begin{rem}
An interesting open question is the following. Suppose we are given a
piecewise quasi-polynomial whose chambers are cones.  Is there a
finite computational test if the quasi-polynomial is an (asymptotic)
Ehrhart function?  Assume it is not an Ehrhart function globally, but
is an Ehrhart function on each individual ray.  Is there a finite
number of rays such that finding polytopes for each of the finitely
many rays proves the Ehrhart nature for all rays?  Is it some
multi-dimensional generalization of Ap\'ery sets known from numerical
semigroups?
\end{rem}

\begin{rem}
According to \cite[Remark~3.8]{KMplethysm} the function $\phi$ in
Theorem~\ref{t:main} also counts, for example, the multiplicity of
$\lambda = s\cdot (7+2t,5+2t,2t)$ in $S^3(S^{s\cdot (5+2t)})$ for any
positive~$t$.  Therefore counterexamples also exist for strictly
interior rays.
\end{rem}

Recently, there has been a lot of interest in \emph{Kronecker
coefficients}~\cite{manivel2014asymptotics2,
briand2009reduced,sam2015stembridge,baldoni2015multiplicity}.  These
are different from plethysm, but also hard to compute and important in
geometric complexity theory.  It is known that on rays they are given
by quasi-polynomials \cite[Theorem 1]{manivel2014asymptotics} that do
not have to be Ehrhart functions~\cite{King}.  However, the problem is
open for specific rays that are important in GCT.  Emmanuel Briand
pointed us towards following observation.  Two row partitions are
useful because Hermite reciprocity applies to them.  Further, by the
work of Vallejo \cite{Vallejo}, cf.~\cite{macdonald1998symmetric}, the
plethysm coefficients in Theorem~\ref{t:main} are equal to special
Kronecker coefficients:
\[
\phi(s)=K(3^{4s},3^{3s},(7s,5s))=K((4s,4s,4s),(4s,4s,4s),(7s,5s)),
\]
where $K$ depends on three partitions and is the Kronecker
coefficient.  Indeed, let $p_n(a,b)$ denote the number of Young
diagrams with $n$ boxes contained inside an $a\times b$ rectangle.
Both the multiplicity of $\lambda$ with two rows in the plethysm
$S^a(S^b)$ and the Kronecker coefficient $K(a^{b},a^{b},\lambda)$ can
be expressed as the difference
\[
p_{\lambda_2}(a,b)-p_{\lambda_2-1}(a,b).
\]
For example by transposition, this immediately implies Hermite
reciprocity.
\begin{exm}
The multiplicity of $(7,5)$ inside $S^4(S^3)$ equals zero. Here we
have $4$ diagrams with $5$ boxes inside a $4\times 3$ rectangle:
$(4,1),(3,2),(3,1,1),(2,2,1)$. We also have $4$ such diagrams with $4$
boxes: $(4,0),(3,1),(2,2),(2,1,1)$, hence the difference is indeed
zero.
\end{exm}
The rectangular Kronecker coefficients $K(a^b,a^b,\lambda)$ are of
particular interest in GCT (see e.g.~\cite{ChristianandGretta}).
Moreover, they exactly govern unimodality of $q$-binomial
coefficients, observed already in 1878 by Sylvester (see
\cite[p.~2]{PakPanova}).

In a different direction, the following interesting question was
recently brought to our attention by Mich\`ele Vergne.
\begin{ques}
Are the plethysm coefficients Ehrhart polynomials after rescaling?
Specifically, are $\tilde f(s):=f(ks)$ or $\tilde g(s):=g(ks)$ Ehrhart
polynomials for some $k$?
\end{ques}
One can prove that the answer is positive when $f$ or $g$ are of
degree one, thus to find a counterexample one needs to consider
partitions with more than one row.

\subsection*{Acknowledgment}
The project was started at the Simons Institute at UC Berkeley during
the ``Algorithms and Complexity in Algebraic Geometry'' semester.
Micha{\l}ek was realizing the project as a part of the PRIME DAAD
program.  Micha{\l}ek would like to thank Klaus Altmann and Bernd
Sturmfels for the great working environment.  Kahle was supported by
the research focus dynamical systems of the state Saxony Anhalt.

% \bibliographystyle{amsalpha}
% \bibliography{plethysm}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{CDW12}

\bibitem[BOR09]{briand2009reduced}
Emmanuel Briand, Rosa Orellana, and Mercedes Rosas, \emph{Reduced {K}ronecker
  coefficients and counter--examples to {M}ulmuley’s strong saturation
  conjecture {SH}}, Computational Complexity \textbf{18} (2009), no.~4,
  577--600.

\bibitem[BV15]{baldoni2015multiplicity}
Velleda Baldoni and Mich\`ele Vergne, \emph{Multiplicity of compact group
  representations and applications to {K}ronecker coefficients}, preprint,
  arXiv:1506.02472 (2015).

\bibitem[BZ92]{BZ}
Arkady~D Berenstein and Andrei~V Zelevinsky, \emph{Triple multiplicities for
  {$sl(r+1)$} and the spectrum of the exterior algebra of the adjoint
  representation}, Journal of Algebraic Combinatorics \textbf{1} (1992), no.~1,
  7--22.

\bibitem[CDW12]{christandl2012computing}
Matthias Christandl, Brent Doran, and Michael Walter, \emph{Computing
  multiplicities of {L}ie group representations}, IEEE 53rd Annual Symposium on
  Foundations of Computer Science (FOCS), IEEE, 2012, pp.~639--648.

\bibitem[CGR84]{CGR83}
Y.~M. Chen, A.~M. Garsia, and J.~Remmel, \emph{Algorithms for plethysm},
  Combinatorics and algebra ({B}oulder, {C}olo., 1983), Contemp. Math.,
  vol.~34, AMS, Providence, RI, 1984, pp.~109--153.

\bibitem[Col17]{colmenarejo2015stability}
Laura Colmenarejo, \emph{Stability properties of the plethysm: A combinatorial
  approach}, Discrete Mathematics \textbf{340} (2017), no.~8, 2020--2032.

\bibitem[Ehr67]{ehrhart1967I}
Eug{\`e}ne Ehrhart, \emph{Sur un probl{\`e}me de g{\'e}om{\'e}trie
  diophantienne lin{\'e}aire {I}}, J. reine angew. Math \textbf{226} (1967),
  1--29.

\bibitem[FH91]{fulton91:_repres_theor}
William Fulton and Joe Harris, \emph{Representation theory. {A} first course},
  Springer, Berlin, 1991.

\bibitem[Her54]{hermite1854}
Charles Hermite, \emph{Sur la theorie des fonctions homog{\`e}nes \`a deux
  ind\'etermin\'ees}, Cambridge and Dublin Mathematical Journal \textbf{9}
  (1854), 172--217.

\bibitem[Hor62]{horn1962eigenvalues}
Alfred Horn, \emph{Eigenvalues of sums of {H}ermitian matrices}, Pacific
  Journal of Mathematics \textbf{12} (1962), no.~1, 225--241.

\bibitem[IP17]{ChristianandGretta}
Christian Ikenmeyer and Greta Panova, \emph{Rectangular {K}ronecker
  coefficients and plethysms in geometric complexity theory}, Advances in
  Mathematics \textbf{319} (2017), 40--66.

\bibitem[KM16]{KMplethysm}
Thomas Kahle and Mateusz Micha\l{}ek, \emph{Plethysm and lattice point
  counting}, J. Found. Comp. Math \textbf{16} (2016), no.~5, 1241--1261.

\bibitem[KT99]{knutson1999honeycomb}
Allen Knutson and Terence Tao, \emph{The honeycomb model of
  {$GL_n(\mathbb{C})$} tensor products {I}: Proof of the saturation
  conjecture}, Journal of the AMS \textbf{12} (1999), no.~4, 1055--1090.

\bibitem[KW09]{King}
Ronald King and Trevor Welsh, \emph{Some remarks on characters of symmetric
  groups, {S}chur functions, {L}ittlewood--{R}ichardson and {K}ronecker
  coefficients}, work in progress
  \url{http://congreso.us.es/enredo2009/Workshop_files/Sevilla_King.pdf}
  (2009).

\bibitem[Mac71]{macdonald1971polynomials}
Ian~G Macdonald, \emph{Polynomials associated with finite cell-complexes},
  Journal of the LMS \textbf{2} (1971), no.~1, 181--192.

\bibitem[Mac98]{macdonald1998symmetric}
Ian~Grant Macdonald, \emph{Symmetric functions and {H}all polynomials}, Oxford
  University Press, 1998.

\bibitem[Man15]{manivel2014asymptotics}
Laurent Manivel, \emph{On the asymptotics of {K}ronecker coefficients}, Journal
  of Algebraic Combinatorics \textbf{42} (2015), no.~4, 999--1025.

\bibitem[Man16]{manivel2014asymptotics2}
\bysame, \emph{On the asymptotics of {K}ronecker coefficients, 2},
  S{\'e}minaire Lotharingien de Combinatoire \textbf{75} (2016), B75d, 13p.

\bibitem[MM15]{manivel2014secants}
Laurent Manivel and Mateusz Micha{\l}ek, \emph{Secants of minuscule and
  cominuscule minimal orbits}, Linear Algebra and its Applications \textbf{481}
  (2015), 288--312.

\bibitem[MS99]{meinrenken1999singular}
Eckhard Meinrenken and Reyer Sjamaar, \emph{Singular reduction and
  quantization}, Topology \textbf{38} (1999), no.~4, 699--762.

\bibitem[MS01]{mulmuley2001geometric}
Ketan~D Mulmuley and Milind Sohoni, \emph{Geometric complexity theory {I}: An
  approach to the {P} vs. {NP} and related problems}, SIAM Journal on Computing
  \textbf{31} (2001), no.~2, 496--526.

\bibitem[Mul09]{mulmuleyGCT6long}
Ketan~D Mulmuley, \emph{Geometric complexity theory {VI}: the flip via
  saturated and positive integer programming in representation theory and
  algebraic geometry}, preprint, arXiv:0704.0229 (2009).

\bibitem[Mul11]{mulmuleyGCT6short}
Ketan Mulmuley, \emph{Geometric complexity theory {VI}: The flip via
  positivity}, \url{http://gct.cs.uchicago.edu/gct6.pdf}, 2011, Online;
  accessed 14 December 2015.

\bibitem[PP14]{PakPanova}
Igor Pak and Greta Panova, \emph{Bounds on {K}ronecker and $q$-binomial
  coefficients}, preprint, arXiv:1410.7087 (2014).

\bibitem[PV05]{pak2005combinatorics}
Igor Pak and Ernesto Vallejo, \emph{Combinatorics and geometry of
  {L}ittlewood--{R}ichardson cones}, European Journal of Combinatorics
  \textbf{26} (2005), no.~6, 995--1008.

\bibitem[PV15]{paradan2015witten}
Paul-Emile Paradan and Mich\`ele Vergne, \emph{Witten non abelian localization
  for equivariant {K}-theory, and the {$[Q, R]= 0$} theorem}, preprint,
  arXiv:1504.07502 (2015).

\bibitem[SS16]{sam2015stembridge}
Steven~V Sam and Andrew Snowden, \emph{Proof of {S}tembridge’s conjecture on
  stability of {K}ronecker coefficients}, Journal of Algebraic Combinatorics
  \textbf{43} (2016), no.~1, 1--10.

\bibitem[Sta82]{stanley1982linear}
Richard~P Stanley, \emph{Linear {D}iophantine equations and local cohomology},
  Inventiones mathematicae \textbf{68} (1982), no.~2, 175--193.

\bibitem[Sta96]{stanley96:_combin_commut_algeb}
Richard~P. Stanley, \emph{Combinatorics and commutative algebra}, 2nd ed.,
  Birkh{\"a}user, 1996.

\bibitem[Sta00]{Stanley}
Richard~P. Stanley, \emph{Positivity problems and conjectures in algebraic
  combinatorics}, Mathematics: Frontiers and Perspectives, AMS, Providence, RI,
  2000, pp.~295--319.

\bibitem[Val14]{Vallejo}
Ernesto Vallejo, \emph{A diagrammatic approach to {K}ronecker squares}, J.
  Combin. Theory Ser. A \textbf{127} (2014), 243--285.

\bibitem[Wey12]{weyl1912asymptotische}
Hermann Weyl, \emph{Das asymptotische {V}erteilungsgesetz der {E}igenwerte
  linearer partieller {D}ifferentialgleichungen (mit einer {A}nwendung auf die
  {T}heorie der {H}ohlraumstrahlung)}, Mathematische Annalen \textbf{71}
  (1912), no.~4, 441--479.

\end{thebibliography}

\end{document}
