\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsthm,amsmath,amssymb,graphicx}
\renewcommand{\baselinestretch}{1.1}
%
%------    GENERAL MACROS    -----
%
% Standard rings and fields, affine and projective space
%
\def\NZQ{\mathbb}               % the font for N,Z,Q,R,C
\def\NN{{\NZQ N}}
\def\QQ{{\NZQ Q}}
\def\ZZ{{\NZQ Z}}
\def\RR{{\NZQ R}}
\def\CC{{\NZQ C}}
\def\AA{{\NZQ A}}
\def\BB{{\NZQ B}}
\def\PP{{\NZQ P}}
\def\FF{{\NZQ F}}
\def\GG{{\NZQ G}}
\def\HH{{\NZQ H}}
%
%
\def\ab{\mathbf{a}}
\def\hb{\mathbf{h}}
\def\eb{\mathbf{e}}
\def\tb{\mathbf{t}}
\def\xb{\mathbf{x}}
\def\yb{\mathbf{y}}
\def\eb{\mathbf{e}}
%---------------------------------------------------
%
\def\opn#1#2{\def#1{\operatorname{#2}}} % to make operators
%------------------------------------------------
% Numerical invariants of rings, ideals, and modules
%
\opn\aff{aff} \opn\con{conv} \opn\relint{relint} \opn\st{st}
\opn\lk{lk} \opn\cn{cn} \opn\core{core} \opn\vol{vol}
\opn\link{link} \opn\star{star}
%------------------------------------------------
\def\Ac{{\mathcal A}}
\def\Bc{{\mathcal B}}
\def\Hc{{\mathcal H}}
\def\Sc{{\mathcal S}}
\def\Cc{{\mathcal C}}
\def\Gc{{\mathcal G}}
\def\Fc{{\mathcal F}}
\def\Pc{{\mathcal P}}
\def\Nc{{\mathcal N}}
\def\Ec{{\mathcal E}}
\def\Qc{{\mathcal Q}}
%
%
%
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Problem}[Theorem]{Problem}
\newtheorem{Conjecture}[Theorem]{Conjecture}
\newtheorem{Question}[Theorem]{Question}
\theoremstyle{definition}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Remarks}[Theorem]{Remarks}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Examples}[Theorem]{Examples}
\newtheorem{Definition}[Theorem]{Definition}


\pagestyle{plain}

\title{\bf Integer decomposition property of dilated polytopes}
\author{David A. Cox \\
\small Department of Mathematics and Science \\ [-0.8ex]
\small Amherst College, USA \\ [-0.8ex]
\small\tt dacox@amherst.edu \\ [-0.8ex]
\and 
Christian Haase \\
\small Institut f\"ur Mathematik, \\ [-0.8ex]
\small Freie Universit\"at Berlin, Germany \\ [-0.8ex]
\small\tt haase@math.fu-berlin.de \\ [-0.8ex]
\and 
Takayuki Hibi \\
\small Department of Pure and Applied Mathematics, \\ [-0.8ex]
\small Osaka University, Japan \\ [-0.8ex]
\small\tt hibi@math.sci.osaka-u.ac.jp \\ [-0.8ex]
\and 
Akihiro Higashitani\\
\small Department of Mathematics, \\ [-0.8ex]
\small Kyoto University, Japan. \\ [-0.8ex]
\small\tt ahigashi@math.kyoto-u.ac.jp
}

\date{\dateline{Mar 18, 2014}{Oct 19, 2014}\\
\small Mathematics Subject Classifications: Primary 52B20; Secondary 14Q15, 14M25.}


\begin{document}

\maketitle

\begin{abstract} 
An integral convex polytope $\Pc \subset \RR^N$ possesses the integer
decomposition property if, for any integer $k > 0$ and for
any $\alpha \in k \Pc \cap \ZZ^{N}$, there exist $\alpha_{1}, \ldots,
\alpha_k \in \Pc \cap \ZZ^N$ such that $\alpha = \alpha_{1}
+ \cdots + \alpha_k$.  A fundamental question is to determine the
integers $k > 0$ for which the dilated polytope $k\Pc$ possesses the
integer decomposition property.  In the present paper, combinatorial
invariants related to the integer decomposition property of dilated
polytopes will be proposed and studied.
\end{abstract}




\section*{Introduction}
Integral convex polytopes have been studied from the viewpoints of
commutative algebra and algebraic geometry together with enumerative
combinatorics, combinatorial optimization and statistics.  Recall that
an {\em integral} convex polytope $\Pc \subset \RR^N$ is a convex polytope all of
whose vertices have integer coordinates.

There is an entire network \cite[p.2313]{MFO07} of combinatorial and
algebraic properties that involve integral convex polytopes and their
positive integer multiples \cite{BGcover,BGT,KKMS}.  In particular,
some properties may fail for given polytope but hold for a large positive
integer multiple $k \Pc$.  We call $k \Pc = \{ k \alpha : \alpha \in
\Pc \} \subset \RR^{N}$ a {\em dilated polytope}.

The surprise is that the threshold where a given property starts to
hold can differ from one property to the next.  The goal of the
present paper is to explore these thresholds and relate them to other
interesting invariants of integer points in polytopes.

We begin with four aspects of an integral convex polytope $\Pc$ that
will lead to six invariants.  After defining the invariants, we will
say more about what they mean.


\medskip

\noindent {\bf (0.1) Integer Decomposition Property.}
$\Pc \subset \RR^N$ possesses the {\em integer decomposition property} or (IDP) for short
if, for every integer $k = 1, 2, \ldots$ and for all $\alpha \in k \Pc
\cap \ZZ^{N}$, there exist $\alpha_{1}, \ldots, \alpha_k$ belonging to
$\Pc \cap \ZZ^N$ such that $\alpha = \alpha_{1} + \cdots + \alpha_k$.
The (IDP) is important in the theory and application of integer
programming (\cite[\S22.10]{Sch}).  It also arises naturally in the
study of toric varieties (\cite{BGT} and \cite[Ch.\ 2]{CLS}).

Not every integral polytope possesses (IDP), but sufficiently large
dilations do.  The threshold where this first occurs leads to two
numerical invariants of $\Pc$:
\begin{align}
\label{midpdef}
&\text{$\mu_\text{midp}(\Pc) =$ the smallest integer $k > 0$ for which 
$k\Pc$ has (IDP)}. \\
\label{idpdef}
&\text{$\mu_\text{idp}(\Pc) =$  the smallest integer $k > 0$ for which 
$n\Pc$ has (IDP) for all $n \ge k$}.
\end{align}
The reason for two invariants is that even if $k\Pc$ has (IDP), the
same need not be true for $(k+1)\Pc$.  We will give examples of this
phenomenon in Example~\ref{rei}.

If we weaken (IDP) by replacing ``for every integer'' with ``for every
sufficiently large integer'', we get the notion of {\em very ample}.
Thus $\Pc$ is very ample if, for every sufficiently large integer $k
\gg 0$ and for any $\alpha \in k\Pc \cap \ZZ^N$, there exist
$\alpha_1, \ldots, \alpha_k$ belonging to $\Pc \cap \ZZ^N$ such that
$\alpha = \alpha_1 + \cdots + \alpha_k$.  In particular, if $\Pc$
possesses (IDP), then $\Pc$ is very ample.  The term ``very ample''
arises from toric geometry.  By \cite[Proposition 2.1]{BDG}, the
definition of very ample polytope given here is equivalent to the
toric version given in \cite[Definition 2.2.17]{CLS}.

Not every integral polytope is very ample, but sufficiently large
dilations are.  Hence we get the following invariant:
\begin{equation}
\label{vadef}
\text{$\mu_\text{va}(\Pc) =$ the smallest integer $k > 0$ for which 
$k\Pc$ is very ample}.
\end{equation}
Note that if $k\Pc$ is very ample, then so is $(k+1)\Pc$. 

\smallskip

\noindent {\bf (0.2) The Hilbert Basis.}  $\Pc \subset \RR^{N}$ gives
the rational polyhedral cone $\Cc(\Pc) \subset \RR^{N+1}$ generated by
the vertices of $\widetilde{\Pc} = \Pc\times\{1\} \subset \RR^{N+1}$.
A finite set of integer vectors $\{ \hb_{1}, \ldots, \hb_{s} \}
\subset \ZZ^{N+1}$ is a {\em Hilbert basis} of $\Cc(\Pc)$ if every
point of $\Cc(\Pc) \cap \ZZ^{N+1}$ is a nonnegative integer
combination of $\hb_{1}, \ldots, \hb_{s}$.  A Hilbert basis
exists~\cite{Gordan} and a minimal Hilbert basis is
unique~\cite{vanDerCorput}.  Let $\Hc(\Cc(\Pc))$ denote the minimal
Hilbert basis of $\Cc(\Pc)$.

The {\em degree} of $(\alpha,n) \in \Cc(\Pc) \cap \ZZ^{N+1}$ is $\deg
(\alpha,n) = n$.  Applied to the minimal Hilbert basis, we get
the following invariant:
\begin{equation}
\label{Hilbdef}
\text{$\mu_\text{Hilb}(\Pc) =$ the maximal degree of elements belonging to 
$\Hc(\Cc(\Pc))$}.
\end{equation}

\smallskip

\noindent {\bf (0.3) The \boldmath{$\delta$}-Vector.}
The number of integer points in the dilations of $\Pc$ gives the
generating function 
\[
\sum_{k \ge 0} |k\Pc \cap \ZZ^N|\hskip1pt t^k = \frac{\delta_0 + \delta_1 t +
  \cdots + \delta_d t^d}{(1-t)^{d+1}},\quad d = \dim \Pc.
\]
We call $\delta(\Pc) = (\delta_{0}, \delta_{1}, \ldots, \delta_{d})$
the {\em $\delta$-vector} of $\Pc$ \cite[Chapter XI]{HibiRedBook}.
It is also known that $\delta_0 = 1$ and $\delta_i \ge 0$ for all $i$.
We note that the $\delta$-vector is sometimes called the $h^*$-vector or the Ehrhart $h$-vector. 

The largest index where $\delta_i > 0$ gives the following invariant:
\begin{equation}
\label{Ehrdef}
\text{$\mu_\text{Ehr}(\Pc) =$ the maximal integer $i$ for which
  $\delta_i > 0$}.
\end{equation}
The above generating function is determined by the Ehrhart polynomial
of $\Pc$, which explains the name of the invariant.

For later purposes, we note that $(d+1)-\mu_\text{Ehr}(\Pc)$ is the
least integer $k$ for which $k(\Pc \setminus \partial \Pc) \cap
\ZZ^{N} \neq \emptyset$ \cite[Theorem 4.5]{BR}.  Thus knowing
$\mu_\text{Ehr}(\Pc)$ is equivalent to knowing the smallest dilation
of $\Pc$ with an interior integer point.

\medskip

\noindent {\bf (0.4) Boxes and Holes.}
A simplex $\Sc \subset \RR^{N}$ is {\em empty} if $\Sc \cap \ZZ^{N}$
is the set of vertices of $\Sc$.  Given an empty simplex $\Sc \subset
\RR^N$, we define the finite subset $\text{Box}(\Sc) \subset \Cc(\Sc)$
as follows:
\[
\text{Box}(\Sc)
= \bigg\{\sum_{v_i \in \Sc \cap \ZZ^N} r_i (v_i,1) \in \ZZ^{N+1} \, : \,
0 \leq r_i < 1 \bigg\}.
\] 
It is well known that $\Hc(\Cc(\Sc)) \subset \text{Box}(\Sc) \cup
(\widetilde{\Sc} \cap \ZZ^{N+1})$.

If $\Pc \subset \RR^N$ has dimension $d$, then define
$\text{Box}(\Pc)$ to be
\[
\text{Box}(\Pc)=\bigcup_{\Sc} \text{Box}(\Sc) \setminus \ZZ_{\geq
  0}(\widetilde{\Pc} \cap \ZZ^{N+1}), 
\]
where the union is over all empty simplices $\Sc \subset \Pc$ of
dimension $d$.  Note that $\Hc(\Cc(\Pc)) \subset \bigcup_{\Sc}
\Hc(\Cc(\Sc)) \subset \text{Box}(\Pc) \cup (\widetilde{\Pc} \cap
\ZZ^{N+1})$.

Each element of $\text{Box}(\Pc)$ is called a {\em
hole} of $\Pc$.   This leads to our final invariant:
\begin{equation}
\label{holedef}
\text{$\mu_\text{hole}(\Pc) =$ the maximal degree of elements belonging to 
$\text{Box}(\Pc)$},
\end{equation}
with the convention that $\mu_\text{hole}(\Pc) = 1$ if
$\text{Box}(\Pc) = \emptyset$. 

\medskip

An integral convex polytope $\Pc$ of dimension $d$ thus has the six
invariants
\[
\mu_\text{midp}(\Pc),\ \mu_\text{idp}(\Pc),\ \mu_\text{va}(\Pc),\ 
\mu_\text{Hilb}(\Pc),\ \mu_\text{Ehr}(\Pc),\ \mu_\text{hole}(\Pc)
\]
defined in \eqref{midpdef}--\eqref{holedef}.  The goal of this paper
is to study the relations among these invariants.  

These invariants have different flavors that involve geometry,
algebra, and lattice points.  Here are some brief comments:
\begin{itemize}
\item In \emph{toric geometry}, $\Pc$ determines a line bundle on the
  toric variety of the normal fan of $\Pc$.  Then $\mu_\text{va}(\Pc)$
  is the smallest multiple of this line bundle that is very ample in
  the sense of algebraic geometry.
\item (IDP) and very ample are related to the \emph{lattice structure}
  of the polytope.  More precisely, they describe two notions of what
  it means for $\Pc$ to have ``enough'' integer points:\ for (IDP),
  the integer points of $\Pc$ generate all integer points in its
  dilations, while for very ample, the integer points of $\Pc$ give
  the same toric variety as the normal fan of $\Pc$, as explained in
  \cite[Chapter 2]{CLS}.  Thus $\mu_\text{midp}(\Pc)$ and
  $\mu_\text{va}(\Pc)$ give the smallest dilations of $\Pc$ with
  ``enough'' integer points in these two senses.  Furthermore,
  $\mu_\text{idp}(\Pc)$ gives the smallest dilation where it and all
  further dilations have (IDP).
\item Another invariant of the lattice structure is
  $\mu_\text{Ehr}(\Pc)$, since it is determined by counting integer
  points in dilations.
\item In contrast, $\mu_\text{Hilb}(\Pc)$ is an invariant of the \emph{algebraic
  structure} of the semigroup $\Cc(\Pc)\cap\ZZ^{N+1}$ since it is
  determined by the semigroup's Hilbert basis.  
\item Finally, $\mu_\text{hole}(\Pc)$ is a mixture of the lattice
  structure (integer points in boxes) and the algebraic structure
  (removing the semigroup $\ZZ_{\ge0}(\widetilde{\Pc}\cap\ZZ^{N+1})$).
\end{itemize}

\begin{Remark}
In the book \cite{BG}, two notions closely related to (IDP) are
described.  Let $\Pc \subset \RR^N$ be an integral convex polytope of
dimension $d$.  The authors of \cite{BG} define $\Pc$ to be {\em
  integrally closed} if $\Pc$ satisfies
$$\ZZ_{\geq 0}(\widetilde{\Pc}\cap \ZZ^{N+1})=\Cc(\Pc) \cap \ZZ^{N+1}$$ 
and {\em normal} if $\Pc$ satisfies 
$$\ZZ_{\geq 0}(\widetilde{\Pc}\cap \ZZ^{N+1})=\Cc(\Pc) \cap \ZZ(\widetilde{\Pc} \cap \ZZ^{N+1}).$$ 
Then $\Pc$ satisfying (IDP) is equivalent $\Pc$ being integrally closed, 
but not necessarily equivalent to $\Pc$ being normal.

To complicate matters, the books \cite{CLS} and \cite{MS} use the term
``normal'' for a polytope that is integrally closed in the sense of
\cite{BG}.  Because of this inconsistency, we use the term ``(IDP)''
for this concept.  Besides avoiding confusion, (IDP) has the advantage
of being more descriptive, in that lattice points in dilations of a
polytope with (IDP) have ``integer decompositions'' as sums of
integers points of the polytope.  As noted earlier, the term ``(IDP)''
is widely used in integer programming.
\end{Remark}

We now discuss the contents of the paper.  In Section $1$, we give
basic inequalities which the invariants satisfy.  More precisely,
Theorem \ref{invariant} says that
\begin{equation}
\label{introdiagram}
\begin{array}{c}
\begin{picture}(300,52)
\put(5,20){$1 \le \mu_\text{va}(\Pc) $}
\put(64.5,29){\rotatebox{25}{$\le$}}
\put(82,8){\rotatebox{-20}{$\le$}}
\put(83,39){$\mu_\text{midp}(\Pc) \le \mu_\text{idp}(\Pc)$}
\put(264,39){$\mu_\text{Ehr}(\Pc) \le d$}
\put(118,2){$\mu_\text{Hilb}(\Pc)$} 
\put(264,2){$d-1$}
\put(202,20){$\mu_\text{hole}(\Pc)$}
\put(175,6){\rotatebox{25}{$\le$}}
\put(246,12){\rotatebox{-30}{$\le$}}
\put(184,33){\rotatebox{-30}{$\le$}}
\put(246,29){\rotatebox{25}{$\le$}}
\end{picture}
\end{array}
\end{equation}

Various examples, some new and some old, will be supplied in Section
$2$.  In Theorem \ref{Berkeley}, we construct, given integers $d \geq
3$ and $2 \leq j \leq d - 1$, an empty simplex $\Pc$ of dimension $d$
with all six invariants equal to $j$.  At the other extreme, we give
examples of integral convex polytopes $\Pc$, $\Pc'$ and $\Pc''$ with
\begin{itemize}
\item
$\mu_\text{va}(\Pc) < \mu_\text{midp}(\Pc), \, \,  
\mu_\text{va}(\Pc) < \mu_\text{Hilb}(\Pc)$;
\item
$\mu_\text{midp}(\Pc') < \mu_\text{idp}(\Pc')
< \mu_\text{hole}(\Pc'), \, \, 
\mu_\text{Hilb}(\Pc') < \mu_\text{hole}(\Pc')$;
\item
$\mu_\text{hole}(\Pc'') < \mu_\text{Ehr}(\Pc'')$,
\end{itemize}
showing that the inequalities in \eqref{introdiagram} can be strict.
In Theorem \ref{Boston}, we construct, given an integer $d \geq 4$, an
integral convex polytope $\Pc$ of dimension $d$ such that
\[
\mu_\text{midp}(\Pc) = \mu_\text{idp}(\Pc) = d - 2 < d - 1 =
\mu_\text{Hilb}(\Pc).
\]  
We also give an example where $\mu_\text{Hilb}(\Pc) <
\mu_\text{midp}(\Pc)$.  These last two inequalities show that there is no
general comparison between $\mu_\text{midp}(\Pc)$ and
$\mu_\text{Hilb}(\Pc)$. This explains the middle of
\eqref{introdiagram}.


Moreover, in Section $3$, more detailed relations between 
$\mu_\text{midp}(\Pc)$ and $\mu_\text{idp}(\Pc)$ will be discussed
(Theorem \ref{teiri}).
Finally, we compute in Section $4$ the invariants of edge polytopes
arising from finite graphs. 
 

\section{Invariants related to dilated polytopes}

In this section, we discuss the six invariants 
of an integral convex polytopes $\Pc$ of dimension $d$ related to (IDP). 
More precisely, we prove the following. 



\begin{Theorem}\label{invariant}
For the invariants appearing in the introduction 
of an integral convex polytope $\Pc \subset \RR^N$ of dimension $d \ge 2$, 
the following inequalities hold: 
\begin{equation}\label{diagram}
\begin{array}{c}
\begin{picture}(300,52)
\put(5,20){$1 \le \mu_\text{{\em va}}(\Pc) $}
\put(64.5,29){\rotatebox{25}{$\le$}}
\put(82,8){\rotatebox{-20}{$\le$}}
\put(83,39){$\mu_\text{{\em midp}}(\Pc) \le \mu_\text{{\em idp}}(\Pc)$}
\put(264,39){$\mu_\text{{\em Ehr}}(\Pc) \le d$}
\put(118,2){$\mu_\text{{\em Hilb}}(\Pc)$} 
\put(264,2){$d-1$}
\put(202,20){$\mu_\text{{\em hole}}(\Pc)$}
\put(175,6){\rotatebox{25}{$\le$}}
\put(246,12){\rotatebox{-30}{$\le$}}
\put(184,33){\rotatebox{-30}{$\le$}}
\put(246,29){\rotatebox{25}{$\le$}}
\end{picture}
\end{array}
\end{equation}
\end{Theorem}
\begin{proof}
The inequalities 
$1 \leq \mu_\text{va}(\Pc) \leq \mu_\text{midp}(\Pc) \leq \mu_\text{idp}(\Pc)$ and $\mu_\text{Ehr}(\Pc) \leq d$ 
are clear from their definitions. 
On the other hand, since the assertions are obvious if $\Pc$ has (IDP), 
we assume that $\text{Box}(\Pc)$ is not empty. \\
$\bullet$ \underline{$\mu_\text{idp}(\Pc) \leq \mu_\text{hole}(\Pc)$:}
This inequality is proved, though not stated, in
\cite{LiuTrotterZiegler}. We give the proof for the sake of completeness.

It follows from Gordan's Lemma \cite[Theorem 16.4]{Sch} and
Carath\'eodory's Theorem \cite[Corollary 7.1i]{Sch} that $\Cc(\Pc)
\cap \ZZ^{N+1}$ consists of the elements of
$$\{ \alpha  + x \ : \ \alpha \in \text{Box}(\Pc) \cup \{0\}, \ x \in \ZZ_{\geq
  0}(\widetilde{\Pc} \cap \ZZ^{N+1})\}.$$
Thus for $n \geq \mu_\text{hole}(\Pc)$ and an element $\alpha \in (\ell n)\Pc \cap \ZZ^N$, we can write $(\alpha,\ell n) \in \Cc(\Pc) \cap
\ZZ^{N+1}$ as
$
(\alpha_0,n_0) + (\alpha_1,1) + \ldots + (\alpha_r,1)
$
with $n_0 \le n$ for some $(\alpha_0,n_0) \in \Cc(\Pc) \cap \ZZ^{N+1}$ and $(\alpha_i,1) \in \Cc(\Pc) \cap \ZZ^{N+1}$ 
for each $1 \leq i \leq r$. These summands can now be grouped into $\ell$
elements of $n\widetilde{\Pc} \cap \ZZ^{N+1}$. \\
$\bullet$ \underline{$\mu_\text{hole}(\Pc) \leq \mu_\text{Ehr}(\Pc)$:}
Let $(\alpha,\mu_\text{hole}(\Pc)) \in \text{Box}(\Pc)$ attain
$\mu_\text{hole}(\Pc)$. Then, by definition of $\text{Box}(\Pc)$, we
can describe $(\alpha,\mu_\text{hole}(\Pc))$ as a linear combination
of $(d+1)$ linearly independent lattice vectors in $\widetilde{\Pc}$.
Say, $(\alpha,\mu_\text{hole}(\Pc)) = \sum_{i=0}^{d} r_i (v_i,1)$ with
$0 \le r_i <1$. Let $\beta=\sum_{i=0}^{d} (1-r_i) v_i \in \ZZ^N$. 
Since $1-r_i > 0$ and $\sum_{i=0}^{d} (1-r_i) = d+1-\mu_\text{hole}(\Pc)$, 
one has $\beta \in (d+1-\mu_\text{hole}(\Pc))(\Pc \setminus \partial \Pc) \cap \ZZ^N$,
certifying $d+1-\mu_\text{Ehr}(\Pc) \leq d+1-\mu_\text{hole}(\Pc)$.
\\
$\bullet$ \underline{$\mu_\text{va}(\Pc) \leq \mu_\text{Hilb}(\Pc)$:}
Let $\alpha$ be a vertex of $\Pc$, and let $\beta$ be an integer point
in the cone generated by $\Pc-\alpha$. Then, for a sufficiently large integer $k$, 
we have $(\beta+k\alpha,k) \in \Cc(\Pc) \cap
\ZZ^{N+1}$. This point can be written as a nonnegative integral linear
combination of $\Hc(\Cc(\Pc))$: $(\beta+k\alpha,k) =
\sum_{h \in \Hc(\Cc(\Pc))} w_h h$ with $w_h \in \ZZ_{\geq 0}$. This
implies that
$$(\beta,0) \ = \ \sum_{h \in \Hc(\Cc(\Pc))} w_h \bigl[ (h+
  (\mu_\text{Hilb}(\Pc)-\deg(h)) (\alpha,1)) \ - \
  \mu_\text{Hilb}(\Pc) (\alpha,1) \bigr]$$
is a nonnegative integral linear combination of integer points in
$\mu_\text{Hilb}(\Pc) (\Pc-\alpha) \times \{0\}$, showing that
$\mu_\text{Hilb}(\Pc)\Pc$ is very ample.
\\
$\bullet$ \underline{$\mu_\text{Hilb}(\Pc) \leq
  \mu_\text{hole}(\Pc)$:} 
This follows from $\Hc(\Cc(\Pc)) \subset \text{Box}(\Pc) \cup (\widetilde{\Pc} \cap \ZZ^{N+1})$.
\\
$\bullet$ \underline{$\mu_\text{hole}(\Pc) \leq d-1$:}
Here is the argument from \cite{LiuTrotterZiegler}.
Let $\Sc \subset \RR^N$ be an empty simplex of dimension $d$ and let
$v_0,v_1,\ldots,v_d$ be its vertices.
Given $v \in \text{Box}(\Sc)$ there are $r_0,r_1,\ldots,r_d$ with
$0 \leq r_i < 1$ such that $v=\sum_{i=0}^d r_i(v_i,1)$. Since $r_i
<1$, one has $\deg(v)=\sum_{i=0}^d r_i < d+1$.
Suppose that $\deg(v)=d$. Then all $r_i$ must be positive. 
Moreover, we have $\sum_{i=0}^d(1-r_i)=1$ and $0 < 1-r_i <1$. 
Thus the integer point $\sum_{i=0}^d (1-r_i) v_i$ belongs to the
interior of $\Sc$, 
a contradiction. Hence $\deg(v) \leq d-1$.
\end{proof}

\section{Proper inequalities of \eqref{diagram}}

In this section, we present a series of examples of integral convex polytopes.  Each example satisfies a proper inequality in \eqref{diagram}. 

Before giving them, we prove that there exists an integral convex polytope $\Pc$ attaining 
$\mu_\text{va}(\Pc)=\mu_\text{midp}(\Pc)=\mu_\text{idp}(\Pc)=\mu_\text{Hilb}(\Pc)=\mu_\text{hole}(\Pc)=\mu_\text{Ehr}(\Pc)$. 

\begin{Theorem}\label{Berkeley}
Given integers $d \geq 3$ and $2 \leq j \leq d - 1$, 
there exists an empty simplex $\Pc$ of dimension $d$ with 
$\mu_\text{{\em va}}(\Pc)=\mu_\text{{\em midp}}(\Pc)=\mu_\text{{\em idp}}(\Pc)
=\mu_\text{{\em Hilb}}(\Pc)=\mu_\text{{\em hole}}(\Pc)=\mu_\text{{\em Ehr}}(\Pc)=j$. 
\end{Theorem}
%
%
%
%
\begin{proof}
Fix positive integers $d$ and $j$ with $d \geq 3$ and $2 \leq j \leq d-1$ 
and let $\eb_1,\ldots,\eb_d$ be the standard basis of $\RR^d$.  Then we define $\Pc \subset \RR^{d}$ to be the convex hull of $\{ v_0, v_1,\ldots,v_d \} \subset \ZZ^d$, where $v_0={\bf 0}=(0,\ldots,0)$, $v_i = \eb_i$ for $i = 1,\ldots,d-1$ and 
\[
v_d = (\underbrace{1,\ldots,1}_{j},0,\ldots,0,j).
\]
Let $(\delta_0,\delta_1,\ldots,\delta_d)$ be the $\delta$-vector of $\Pc$.
We will prove that $\Pc$ enjoys the required properties. 

Since the determinant of the matrix with columns $v_1,\dots,v_d$ is $j$, the normalized volume of $\Pc$ is $j$. Moreover,  
\begin{equation}\label{hilb}
\frac{q}{j}(v_0,1)+\frac{q}{j}\sum_{i=1}^j(v_i,1)+\frac{j-q}{j}(v_d,1)=(\eb_1+\cdots+\eb_j+(j-q)\eb_d,q+1), 
\end{equation}
where $q=1,\ldots,j-1$. 
Thus $\delta_q \geq 1$ for $q=2,\ldots,j$ (\cite[Proposition 27.7]{HibiRedBook}). 
Since $\sum_{i=0}^d \delta_i =j$ and each $\delta_i$ is nonnegative, one has 
$$(\delta_0,\delta_1,\ldots,\delta_d)=(1,0,\underbrace{1,1,\ldots,1}_{j-1},0,\ldots,0).$$ 
In particular, $\mu_\text{Ehr}(\Pc)=j$. 
Moreover, from $\delta_1=0$, $\Pc$ is an empty simplex. 
Thus, once we show $\mu_\text{va}(\Pc) \geq j$, we conclude that 
$\Pc$ has the desired properties by \eqref{diagram} in Theorem \ref{invariant}. 

Using \eqref{hilb}, one can show without difficulty that the Hilbert basis $\Hc(\Cc(\Pc))$ is 
\[(\widetilde{\Pc} \cap \ZZ^{d+1}) \cup \{(\eb_1+\cdots+\eb_j+(j-q+1)\eb_d,q) : q =2,\ldots,j\}.\]
Now, we show that $k \Pc$ cannot be very ample for $1 \leq k < j$. 
Let $k$ be an integer with $1 \leq k <j$ 
and $m$ the least common multiple of $k$ and $j$.
Write $m=kg$ with $g \geq 2$. Let 
\[
\alpha=(\alpha_0, m+\ell k), \; 
\alpha_0=(m-j+\ell k +1)\eb_1 + \eb_2+\cdots+\eb_j+\eb_d, 
\]
where $\ell$ is an arbitrary nonnegative integer. Since 
\[\alpha=(m-j+\ell k)(v_1,1)+(\eb_1+\cdots+\eb_j+\eb_d,j), \]
it follows that $\alpha$ belongs to $\Cc(\Pc) \cap \ZZ^{d+1}$. 
This implies, first, that $\alpha \not\in \ZZ_{\geq 0} (\widetilde{\Pc} \cap \ZZ^{d+1})$ 
and, second, that $$\alpha_0 \in (m+\ell k)\Pc \cap \ZZ^N = (g+\ell)(k \Pc) \cap \ZZ^N.$$ 
If $k\Pc$ was very ample, then for sufficiently large $\ell$, we could write 
$\alpha_0=\alpha_1+\cdots+\alpha_{g+\ell}$, 
where $\alpha_1,\ldots,\alpha_{g+\ell} \in k \Pc \cap \ZZ^N$. 
Then the $d$th coordinate of each of $\alpha_1,\ldots,\alpha_{g+\ell}$ must be 0 or 1. 
Consider $(\alpha_i,k) \in \Cc(\Pc) \cap \ZZ^{d+1}$ for $1 \leq i \leq g+\ell$. 
Since each $h \in \Hc(\Cc(\Pc))$ with $2 \leq \deg h \leq k$ is of the form 
$$h = (\eb_1+\cdots+\eb_j+(j-i+1)\eb_d,i), $$
where $i=2,\ldots,k$, none of $\alpha_1,\ldots,\alpha_{g+\ell}$ can be expressed 
by using such elements. Thus each of $(\alpha_1,k),\ldots,(\alpha_{g+\ell},k)$ must 
be written as the sum of $k$ elements belonging to $\widetilde{\Pc} \cap \ZZ^{d+1}$. 
It then follows that $\alpha=(\alpha_0,m+\ell k)$ can be written as the sum of $(m+\ell k)$ elements 
belonging to $\widetilde{\Pc} \cap \ZZ^{d+1}$. 
This contradicts $\alpha \not\in \ZZ_{\geq 0}(\widetilde{\Pc} \cap \ZZ^{d+1})$. 
Consequently, $k\Pc$ cannot be very ample, as required. 
\end{proof}




The following three examples (Example \ref{Higashitani}, \ref{rei} and \ref{Ehr}) 
show the existence of integral convex polytopes 
attaining each of the proper inequalities of \eqref{diagram}. 

\begin{Example}[$\mu_\text{va}(\Pc) < \mu_\text{midp}(\Pc)$ and
  $\mu_\text{va}(\Pc) < \mu_\text{Hilb}(\Pc)$]\label{Higashitani}
The existence of a very ample integral convex polytope not having (IDP) is easy to see. 
In fact, for any $d \geq 3$, we may take the product of 
the very ample polytope not having (IDP) of dimension 3 and the the unit cube of dimension $d-3$. 
Such a polytope of dimension 3 is described, e.g., in \cite[Exercise 2.24]{BG}. 
\end{Example}

\begin{Example}[$\mu_\text{midp}(\Pc) < \mu_\text{idp}(\Pc) <
  \mu_\text{hole}(\Pc)$ and $\mu_\text{Hilb}(\Pc) <
  \mu_\text{hole}(\Pc)$]
\label{rei}
Let $d=2m-1$ with $m \geq 4$ and $\Pc$ be the integral simplex whose
vertex set is
$\{{\bf 0}, \eb_1, \ldots,\eb_{d-1},
(m-1)\eb_1+\cdots+(m-1)\eb_{d-1}+m \eb_d\}$.
Then it is immediate to see that one has  
$$\text{Box}(\Pc)=\{(j,\ldots,j,2j) : j=1,\ldots,m-1\}.$$ 
Thus, for $j=2,\ldots,m-1$, we can write
$(j,\ldots,j,2j)=j(1,\ldots,1,2)$.
This implies that $\{x \in \Hc(\Cc(\Pc)) : \text{deg}(x) \geq 2\}=\{(1,\ldots,1,2)\}$.
Hence $\mu_\text{Hilb}(\Pc)=2$, while $\mu_\text{hole}(\Pc)=2m-2=d-1$.


Moreover, we also know that
\begin{equation}\label{tousiki}
\begin{aligned}
&\Cc(\Pc) \cap \ZZ^{d+1} = \ZZ_{\geq 0}(\widetilde{\Pc} \cap
\ZZ^{d+1})\ \cup  \\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad
\{(j,\ldots,j,2j)+ x : 1 \leq j \leq m-1, x \in \ZZ_{\geq
  0}(\widetilde{\Pc} \cap \ZZ^{d+1})\}. 
\end{aligned} 
\end{equation}
It then follows from \eqref{tousiki} that for every element $\alpha$
in $2k \Pc \cap \ZZ^d$
with $k \geq 1$, we can write $\alpha=\alpha_1+\cdots+\alpha_\ell$, 
where $k \leq \ell \leq 2k$ and $\alpha_i \in \Pc \cap \ZZ^d$ or
$\alpha_i=(1,\ldots,1) \in 2 \Pc \cap \ZZ^d$.
By rewriting appropriately, we can express $\alpha=\alpha_1'+\cdots+\alpha_k'$, 
where $\alpha_i' \in 2 \Pc \cap \ZZ^d$. This means that $\mu_\text{midp}(\Pc)=2$. 


On the other hand, we have $(3,\ldots,3) \in 2(3 \Pc) \cap \ZZ^d$ but 
$(3,\ldots,3) \not\in \{\alpha + \beta : \alpha, \beta \in 3\Pc \cap \ZZ^d\}$ 
because of $3 \leq m-1$ and \eqref{tousiki}. Similarly, $k \Pc$ does not possess 
(IDP) when $k$ is odd and $k \leq m-1$. 
However, if $k \geq m$, then $\Qc=k \Pc$ has (IDP). 
In fact, for $\alpha \in \ell \Qc \cap \ZZ^d$ with $\ell \geq 2$, 
since $\ell k \geq 2k \geq 2m$ and $\text{Box}(\Pc)$ has at most 
degree $2m-2$ elements, we can express $\alpha$ as 
$\alpha=(j,\ldots,j) + \alpha'$, 
where $1 \leq j \leq m-1$ and $\alpha' \in \{\alpha_1'+\cdots + \alpha_q' : 
\alpha_i \in \Pc \cap \ZZ^d, q \geq 2\}$. 
Thanks to $q \geq 2$, $\alpha$ can be described as a sum of $\ell$
elements belonging to $\Qc \cap \ZZ^d$. Hence we obtain 
\begin{eqnarray*}
\mu_\text{idp}(\Pc)=
\begin{cases}
m-1 \;&\text{ if $m$ is odd}, \\
m  &\text{ if $m$ is even}. 
\end{cases}
\end{eqnarray*}

Therefore, in summary, 
$$2=\mu_\text{Hilb}(\Pc)=\mu_\text{midp}(\Pc)<
\mu_\text{idp}(\Pc)=2 \left\lfloor \frac{m}{2} \right\rfloor < \mu_\text{hole}(\Pc)=2m-2.$$ 
\end{Example}

\begin{Example}[$\mu_\text{hole}(\Pc) <
  \mu_\text{Ehr}(\Pc)$]\label{Ehr}
When $\Pc$ is an integral convex polytope of dimension $d$ 
which contains an integer point in its interior, 
one has $\mu_\text{Ehr}(\Pc)=d$ but $\mu_\text{hole}(\Pc) \leq d-1$. 
For example, let us consider the integral simplex $\Pc$ of dimension $d \geq 3$ 
whose vertices are {\bf 0} and the row vectors of $d \times d$ matrix 
\begin{eqnarray*}
\begin{pmatrix}
1      &0      &\cdots &\cdots &0 \\
0      &1      &\ddots &       &\vdots \\
\vdots &\ddots &\ddots &\ddots &\vdots \\
0      &\cdots &0      &1      &0 \\
d+1    &\cdots &\cdots &d+1    &d+2
\end{pmatrix}. 
\end{eqnarray*}
Let $v_0={\bf 0}$ and let $v_i$ denote the $i$th row vector. Then the integer point 
$$\frac{2}{d+2}v_0+\frac{1}{d+2}(v_1+\cdots+v_d)=(1,\ldots,1)$$ 
is contained in the interior of $\Pc$, implying $\mu_\text{Ehr}(\Pc)=d$. On the other hand, 
it is easy to see that 
$$\text{Box}(\Pc)=\left\{\left(\left\lfloor\frac{d+1}{2}\right\rfloor+1,\ldots,\left\lfloor\frac{d+1}{2}\right\rfloor+1, 
\left\lfloor\frac{d+1}{2}\right\rfloor \right) \right\},$$ 
implying $\mu_\text{hole}(\Pc)=\left\lfloor\frac{d+1}{2}\right\rfloor$. 
\end{Example}

Next, we consider possible relations between $\mu_\text{Hilb}(\Pc)$ and $\mu_\text{midp}(\Pc)$ 
and also between $\mu_\text{Hilb}(\Pc)$ and $\mu_\text{idp}(\Pc)$. 
As is shown below, there are no relations between them. 
\begin{Example}[$\mu_\text{Hilb}(\Pc)<\mu_\text{midp}(\Pc)$]\label{rei3}
The following integral simplex $\Pc$ of dimension 13 has
$\mu_\text{Hilb}(\Pc)=3$ but $\mu_\text{midp}(\Pc) = 4$:
Let $\Pc$ be a convex hull of {\bf 0} and the row vectors of the matrix 
$\begin{pmatrix}
A &0 \\
0 &B
\end{pmatrix}$, where $A$ (resp.\ $B$) is a $7 \times 7$ (resp.\ $6 \times 6$) matrix such that 
\begin{eqnarray*}
\begin{pmatrix}
1      &0      &\cdots &\cdots &0 \\
0      &1      &\ddots &       &\vdots \\
\vdots &\ddots &\ddots &\ddots &\vdots \\
0      &\cdots &0      &1      &0 \\
3      &\cdots &\cdots &3      &4
\end{pmatrix} \text{ (resp.\ }
\begin{pmatrix}
1      &0      &\cdots &\cdots &0 \\
0      &1      &\ddots &       &\vdots \\
\vdots &\ddots &\ddots &\ddots &\vdots \\
0      &\cdots &0      &1      &0 \\
1      &\cdots &\cdots &1      &2
\end{pmatrix}). 
\end{eqnarray*}
Notice that $A$ corresponds to the polytope in Example \ref{rei} in the case of $m=4$. 
It can be verified that 
$$\Hc(\Cc(\Pc))=(\widetilde{\Pc} \cap \ZZ^{d+1}) \cup 
\{(\underbrace{1,\ldots,1}_7,\underbrace{0,\ldots,0}_6,2), 
(\underbrace{0,\ldots,0}_7,\underbrace{1,\ldots,1}_6,3)\}.$$ 
Thus $\mu_\text{Hilb}(\Pc)=3$. On the other hand, neither $2\Pc$ nor $3\Pc$ possesses (IDP). 
(In fact, $(0,\ldots,0,1,\ldots,1,4) \in \Cc(2\Pc) \cap \ZZ^{d+1} \setminus \ZZ_{\geq 0}(\widetilde{2\Pc} \cap \ZZ^{d+1})$ 
and $(3,\ldots,3,0,\ldots,0,6) \in \Cc(3\Pc) \cap \ZZ^{d+1} \setminus \ZZ_{\geq 0}(\widetilde{3\Pc} \cap \ZZ^{d+1})$.) 
Hence $\mu_\text{midp}(\Pc) \geq 4$. In fact, one can show that $\mu_\text{midp}(\Pc)=4$. 
\end{Example}







Note that an example attaining $\mu_\text{Hilb}(\Pc)<\mu_\text{idp}(\Pc)$ 
has been already given in Example \ref{rei}. 
The following theorem gives an example attaining 
both $\mu_\text{Hilb}(\Pc)>\mu_\text{midp}(\Pc)$ and $\mu_\text{Hilb}(\Pc)>\mu_\text{idp}(\Pc)$. 

\begin{Theorem}\label{Boston}
Given an integer $d \geq 4$, 
there exists an integral convex polytope $\Pc$ of dimension $d$ 
such that $\mu_\text{{\em Hilb}}(\Pc) = d - 1$ and $\mu_\text{{\em midp}}(\Pc)=\mu_\text{{\em idp}}(\Pc)=d-2$. 
\end{Theorem}

Let $d \geq 4$ be an integer and let $M=d(d-2)+1$. 
We define $v_{j} \in \ZZ^{d}$, $1 \leq i \leq d$, as follows:
\begin{eqnarray*}
v_j=
\begin{cases}
{\bf 0}, &j=0, \\
\eb_j, &j=1,\ldots,d-1, \\
\eb_1+\cdots+\eb_{d-1}+M\eb_d, &j=d.
\end{cases}
\end{eqnarray*}
Let $v_j'=v_j+\eb_d$ for $j=0,1,\ldots,d$. We write $\Pc \subset \RR^d$ for the 
integral convex polytope of dimension $d$ 
with the vertices $v_0, v_{1}, \ldots, v_{d}$ and $v'_0, v'_{1}, \ldots, v'_{d}$.
Such a convex polytope appears in \cite[Theorem 2]{EwaldWessels}. 


The following Lemmas \ref{lem1} and \ref{lem2} prove Theorem
\ref{Boston}, that is, they show that $\Pc$ enjoys the required
properties in Theorem \ref{Boston}.  Let 
$$u_s^{(k)}=\eb_1+\cdots+\eb_{d-1}+((k-1)d+s)\eb_d \text{ for }k=1,\ldots,d-2 \text{ and } s=1,\ldots,d$$
and $$u=u_d^{(1)}=\eb_1+\cdots+\eb_{d-1}+d \eb_d.$$ 

\begin{Lemma}\label{lem1}
Let $\Pc$ be as above. Then the Hilbert basis $\Hc(\Cc(\Pc))$ is equal to 
\begin{align}\label{hilbert}
(\widetilde{\Pc} \cap \ZZ^{d+1}) \cup 
\{(u_s^{(k)},d-k)  : k=2,\ldots,d-2, s=1,\ldots,d\} \cup \{(u,d-1)\}. 
\end{align}
Thus, in particular, $\mu_\text{{\em Hilb}}(\Pc)=d-1$. 
\end{Lemma}
\begin{proof}
\noindent
If $q \in \{1,\ldots,M-1\}$, then there exist unique integers 
$k$ and $s$ with $1 \leq k \leq d-2$ and $1 \leq s \leq d$ such that $q=(k-1)d+s$.
Since 
\begin{align*}
&\frac{(d-2)s-k+1}{M}(v_0,1)+\frac{M-q}{M}\sum_{j=1}^{d-1}(v_j,1)+\frac{q}{M}(v_d,1) \\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 
=(\eb_1+\cdots+\eb_{d-1}+q\eb_d, d-k) =(u_s^{(k)},d-k) \in \ZZ^{d+1}, 
\end{align*}
it follows that $(u_s^{(k)},d-k)=(\eb_1+\cdots+\eb_{d-1}+q\eb_d, d-k) \in \Cc(\Pc) \cap \ZZ^{d+1}$. 
When $k=1$ and $s=1,\ldots,d-1$, one has $q=s$ and 
\[
(\eb_1+\cdots+\eb_{d-1}+q\eb_d, d-1)=\sum_{j=1}^s (v_j',1) + \sum_{j=s+1}^{d-1} (v_j,1). 
\]
Hence $(\eb_1+\cdots+\eb_{d-1}+q\eb_d, d-1)$ 
cannot belong to $\Hc(\Cc(\Pc))$ for $q \leq d-1$.
Now, it is routine work to show that, by considering the facets of the cone $\Cc(\Pc)$, 
the Hilbert basis $\Hc(\Cc(\Pc))$ coincides with \eqref{hilbert}. 
\end{proof}

\begin{Lemma}\label{lem2}
We have $\mu_\text{{\em midp}}(\Pc)=\mu_\text{{\em idp}}(\Pc)=d-2$. 
\end{Lemma}
\begin{proof}
\noindent
One can easily see the identities 
\begin{itemize}
\item[] $(u,d-1)+(v_i,1)=(v_i',1)+\sum_{j=1}^{d-1}(v_j', 1) \;\;\text{for}\;\;i=0,1,\ldots,d,$ 
\item[] $(u,d-1)+(v_i',1)=(v_0,1)+(v_i,1)+(u_1^{(2)},d-2) \;\;\text{for}\;\;i=0,1,\ldots,d,$ 
\item[] $(u,d-1)+(u_s^{(d-2)},2)=(v_0,1)+(v_d,1)+\sum_{j=1}^{s-1}(v_j',1)+\sum_{j=s}^{d-1}(v_j,1),$ 
\item[] $(u,d-1)+(u_s^{(k)},d-k)=(u_s^{(k+1)},d-k-1)+\sum_{j=0}^{d-1}(v_j,1)$ for $k=2,\ldots,d-3,$
\item[] $(u,d-1)+(u,d-1)=(u_d^{(2)},d-2)+\sum_{j=0}^{d-1}(v_j,1).$ 
\end{itemize}
It then follows that
\[(\Cc(\Pc) \cap \ZZ^{d+1}) \setminus \{(u,d-1)\} = \ZZ_{\geq 0} (\Hc(\Cc(\Pc)) \setminus \{(u,d-1)\}).\]
Moreover, if $k+k' \geq d$, then
\begin{align*}
&(u_s^{(k)},d-k)+(u_{s'}^{(k')},d-k')=\\
&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;
\begin{cases}
(v_d,1)+(u_{s+s'-1}^{(k+k'-d+1)}, 2d-k-k'-1),
&\;\;\text{if}\;\;s+s'\leq d+1, \\
(v_0,1)+(v_d,1)+(u_{s+s'-1-d}^{(k+k'-d+2)}, 2d-k-k'-2),
&\;\;\text{if}\;\;s+s'\geq d+2. 
\end{cases}\end{align*}
If $k+k' \leq d-1$, then 
\begin{align*}
&(u_s^{(k)},d-k)+(u_{s'}^{(k')},d-k')=\\
&\;\;\;\;\;\;\;\;
\begin{cases}
(u_s^{(k+k'-1)},d-k-k'+1)+\sum_{j=1}^{s'}(v_j',1)+\sum_{j=s'+1}^{d-1}(v_j,1), 
&\;\;\text{if}\;\;s'\leq d-1, \\
(u_s^{(k+k')},d-k-k')+\sum_{j=0}^{d-1}(v_j,1), 
&\;\;\text{if}\;\;s'= d. 
\end{cases}\end{align*}
Consequently, when we write $\alpha \in \Cc(\Pc) \cap \ZZ^{d+1}$ 
by using at least two $u_s^{(k)}$'s, we can reduce one $u_s^{(k)}$.
Hence $\alpha$ can be expressed by using at most one $u_s^{(k)}$ belonging to $\Hc(\Cc(\Pc))$. 

Let $\Pc'=(d-2)\Pc$ and $\alpha \in n \Pc' \cap \ZZ^d$.
Since $d \geq 4$, one has $n(d-2) \neq d-1$. Thus $(\alpha,n(d-2)) \not=(u,d-1)$. 
By the above discussions, there exists an expression of $\alpha$ of the form 
\[
(\alpha, n(d-2)) = v' + \sum_{j=1}^{n(d-2)-\deg(v')}(v_j'',1), 
\]
where $v' \in \{(u_s^{(k)},d-k) : k=2,\ldots,d-2, s=1,\ldots,d\}$ and each $v_j'' \in \Pc \cap \ZZ^d$. 
Since the degree of $v'$ is at most $d-2$, there exists an expression of $\alpha$ of the form
\[
\alpha=\alpha_1+\cdots+\alpha_n
\] 
with each $\alpha_i \in \Pc' \cap \ZZ^d$. Hence $\Pc'$ possesses (IDP). 
By $\mu_\text{idp}(\Pc) \leq d-1$, $k\Pc$ possesses (IDP) for $k \geq d-1$. 
Thus, we obtain $\mu_\text{idp}(\Pc) \leq d-2$. 

Now it is easy to see that for $r < d-2$, $r \Pc$ never possesses (IDP). 
Therefore, we conclude that $\mu_\text{midp}(\Pc)=\mu_\text{idp}(\Pc)=d-2$. 
\end{proof}






\section{Restrictions on invariants}

In this section, we discuss more restrictions on the invariants. 
We consider the following question. 

\begin{Question}\label{toi}{\em 
Let $d, a_1, a_2, a_3, a_4, a_5, a_6$ be positive integers satisfying 
\begin{align*}
a_1 \leq a_2 \leq a_3 \leq a_5 \leq a_6 \leq d \;\text{ and }\;  a_1 \leq a_4 \leq a_5 \leq d-1. 
\end{align*}
Then does there exist an integral convex polytope $\Pc$ of dimension $d$ such that 
\begin{eqnarray*}
&\mu_\text{va}(\Pc)=a_1,\ \mu_\text{midp}(\Pc)=a_2,\ \mu_\text{idp}(\Pc)=a_3, \
\mu_\text{Hilb}(\Pc)=a_4,\ \mu_\text{hole}(\Pc)=a_5 \\
&\text{ and } \mu_\text{Ehr}(\Pc)=a_6\text{?}
\end{eqnarray*}
}\end{Question}

{}From some easy observations, we cannot assign these positive integers freely. 
In fact, it is obvious that 
\begin{itemize}
\item if either $\mu_\text{midp}(\Pc)$ or $\mu_\text{Hilb}(\Pc)$ is 1, 
then $\mu_\text{va}(\Pc)=\mu_\text{midp}(\Pc)=\mu_\text{idp}(\Pc)=\mu_\text{Hilb}(\Pc)
=\mu_\text{hole}(\Pc)=1$; 
\item if $\mu_\text{midp}(\Pc)<\mu_\text{idp}(\Pc)$, 
then $\mu_\text{idp}(\Pc) \geq \mu_\text{midp}(\Pc) +2$. 
\end{itemize}
Moreover, we also see non-trivial restrictions. 
\begin{Theorem}\label{teiri} The following assertions hold: 
\begin{itemize}
\item[(1)] if $\mu_\text{{\em midp}}(\Pc) \geq (d-1)/2$, 
then $\mu_\text{{\em idp}}(\Pc)=\mu_\text{{\em midp}}(\Pc)$; 
\item[(2)] if $\mu_\text{{\em midp}}(\Pc) \leq (d-1)/2$, 
then $\mu_\text{{\em idp}}(\Pc) \leq (d-3)/2+\mu_\text{{\em midp}}(\Pc)$. 
\end{itemize}
\end{Theorem}




Before proving these, we recall the following lemma. 
\begin{Lemma}[cf. {\cite[Theorem 2.2.12]{CLS}}]\label{hodai}
Let $\Pc \subset \RR^N$ be an integral convex polytope of dimension $d$. 
Given $\alpha \in n \Pc \cap \ZZ^N$ for $n \geq d-1$, $\alpha$ can be written like 
$$\alpha=\alpha'+\alpha_1+\cdots+\alpha_{n-d+1},$$ 
where $\alpha' \in (d-1) \Pc \cap \ZZ^N$ and $\alpha_1,\ldots,\alpha_{n-d+1} \in \Pc \cap \ZZ^N$. 
\end{Lemma}
A proof of this lemma appears in the proof of \cite[Theorem 2.2.12]{CLS}. 




\begin{proof}[Proof of Theorem \ref{teiri}]
(1) It suffices to show that for an integral convex polytope $\Pc \subset \RR^N$ of dimension $d$ 
with $\mu_\text{midp}(\Pc) \geq (d-1)/2$, $n\Pc$ possesses (IDP) for every $n \geq \mu_\text{midp}(\Pc)$. 

Let $k=\mu_\text{midp}(\Pc)$. 
Let $n \geq k$ and let $\alpha \in m(n\Pc) \cap \ZZ^N$ for $m \geq 2$. 
Since $mn \geq 2n \geq 2k \geq d-1$, 
thanks to Lemma \ref{hodai}, we obtain 
$$\alpha=\alpha'+\alpha_1+\cdots+\alpha_{mn-d+1},$$ 
where $\alpha' \in (d-1)\Pc \cap \ZZ^N$ and 
$\alpha_1,\ldots,\alpha_{mn-d+1} \in \Pc \cap \ZZ^N$. 
Moreove, since $k\Pc$ has (IDP), 
there are $\alpha_1'$ and $\alpha_2'$ in $k\Pc \cap \ZZ^N$ such that 
$$\alpha_1'+\alpha_2'=\alpha'+\alpha_{mn-2k+1}+\cdots+\alpha_{mn-d+1} \in 2k \Pc \cap \ZZ^N.$$ 
Therefore, 
$$\alpha=\underbrace{\alpha_1'+\sum_{i=1}^{n-k}\alpha_i}_{n \Pc \cap \ZZ^N}+
\underbrace{\alpha_2'+\sum_{i=n-k+1}^{2(n-k)}\alpha_i}_{n \Pc \cap \ZZ^N}+
\sum_{i=1}^{m-2}\underbrace{\sum_{j=1}^n\alpha_{2(n-k)+(i-1)n+j}}_{n \Pc \cap \ZZ^N}.$$
This implies that $n\Pc$ possesses (IDP). \\
%
%
(2) It suffices to prove that for an integral convex polytope $\Pc \subset \RR^N$ 
of dimension $d$ with $\mu_\text{midp}(\Pc) \leq (d-1)/2$, 
$n\Pc$ possesses (IDP) for every $n \geq (d - 3)/2+\mu_\text{midp}(\Pc)$. 

For $m \geq 2$, let $\alpha \in m(n\Pc) \cap \ZZ^N$. 
Since $mn \geq 2n \geq d-3 + 2 \mu_\text{midp}(\Pc) \geq d-1$, thanks to Lemma \ref{hodai}, we obtain 
$$\alpha=\alpha'+\alpha_1+\cdots+\alpha_{mn-d+1},$$ 
where $\alpha' \in (d-1)\Pc \cap \ZZ^N$ and 
$\alpha_1,\ldots,\alpha_{mn-d+1} \in \Pc \cap \ZZ^N$. 

Let $k=\mu_\text{midp}(\Pc)$ and $\ell = \min\{ i : ik \geq d-1\}$. 
Since $k\Pc$ has (IDP), an element 
$\alpha'+\alpha_{mn-\ell k +1}+\cdots+\alpha_{mn - d+1}$ belonging to $\ell (k \Pc) \cap \ZZ^N$ 
can be written such as $\alpha_1'+\cdots+\alpha_\ell'$, 
where $\alpha_i' \in k \Pc \cap \ZZ^N$. 
Remark that $\ell k - d+1 \leq mn- d +1$ because 
$$mn - \ell k \geq 2n - \ell k \geq d-3+2k-\ell k \geq d-2 - (\ell - 1) k \geq 0.$$
Thus $\alpha$ can be rewritten as 
$$\alpha=\alpha_1'+\cdots+\alpha_\ell' + \alpha_1+\cdots+\alpha_{mn-\ell k}.$$ 
Let $p=\lfloor n/k \rfloor$ and $q=n-pk$, i.e., $n=pk+q$ with $0 \leq q \leq k-1$. 
When $p \geq \ell$, since $n \geq \ell k$, 
it follows easily that $\alpha$ can be written as a sum of $m$ elements of $n \Pc \cap \ZZ^N$. 
Assume that $p < \ell$. Then we have $mn-\ell k \geq q$ and $n - (\ell-p)k \geq 0$. In fact, 
\begin{align*}
mn - \ell k -q &\geq 2n-\ell k -q=n-(\ell-p)k \\
&\geq d-3+2k-\ell k -(k-1) = d-2 - (\ell -1 )k \geq 0.
\end{align*}
Thus we obtain that 
$$\alpha=\underbrace{\sum_{i=1}^p\alpha_i'+\sum_{j=1}^q \alpha_j}_{n \Pc \cap \ZZ^N}
+\underbrace{\sum_{i=p+1}^\ell \alpha_i'+\sum_{j=1}^{n-(\ell-p)k}\alpha_{q+j}}_{n \Pc \cap \ZZ^N}
+\sum_{r=1}^{m-2}\underbrace{\sum_{i=1}^n \alpha_{n-(\ell-p)k+q+(r-1)n+i}}_{n \Pc \cap \ZZ^N}.$$
This says that $n \Pc$ possesses (IDP), as desired. 
\end{proof}


As an immediate corollary of Theorem \ref{teiri}, we obtain the following. 
\begin{Corollary}
If $\mu_\text{{\em idp}}(\Pc)=d-1$, then $\mu_\text{{\em midp}}(\Pc)=d-1$. 
\end{Corollary}
\begin{proof}
Suppose that $\mu_\text{midp}(\Pc)\not=d-1$. In particular, $\mu_\text{midp}(\Pc) < d-1$. 
If $\mu_\text{midp}(\Pc) \geq (d-1)/2$, 
then $\mu_\text{idp}(\Pc)=\mu_\text{midp}(\Pc)<d-1$ by Theorem \ref{teiri} (1). 
Moreover, if $\mu_\text{midp}(\Pc) \leq (d-1)/2$, then 
$\mu_\text{idp}(\Pc) \leq (d-3)/2 + \mu_\text{midp}(\Pc) \leq (d-3)/2+(d-1)/2 < d-1$ by Theorem \ref{teiri} (2). 
Hence, $\mu_\text{idp}(\Pc)$ is never equal to $d-1$, as desired. 
\end{proof}




\begin{Question}\label{mondai} Work with the same notation as above. 
\begin{itemize}
\item[(1)] Is there some relation between $\mu_\text{{\em midp}}(\Pc)$, $\mu_\text{{\em idp}}(\Pc)$ 
and $\mu_\text{{\em Hilb}}(\Pc)$?  The examples given in \cite[Cor.\ 15]{LM} show that the
  relations may be complicated.
\item[(2)] Assume that $\mu_\text{{\em idp}}(\Pc)>1$. Is it true that 
$\mu_\text{{\em Hilb}}(\Pc)=2$ 
if $\mu_\text{{\em va}}(\Pc)=1$? 
\end{itemize}
\end{Question}

\begin{Remark}\label{workofLM}
The recent preprint \cite{LM} contains examples that shed light
on our invariants.
\begin{itemize}
\item[(1)] In an earlier version of our paper, we asked in Question
  \ref{mondai}(1) if there
  exists a polytope $\Pc$ such that $\mu_\text{{\em midp}}(\Pc) <
  \mu_\text{Hilb}(\Pc) < \mu_\text{idp}(\Pc)$.   As shown
  in \cite[Sec.\ 4]{LM}, the answer is yes.  
\item[(2)] In the earlier version, we asked in Question
  \ref{mondai}(2) if $\mu_\text{midp}(\Pc)=\mu_\text{idp}(\Pc)=2$ when $\mu_\text{va}(\Pc)=1$ and
  $\mu_\text{idp}(\Pc)>1$.  An example from
  \cite[Sec.\ 4]{LM} show that this can fail.
\item[(3)] In the earlier version, we also asked if $(n+m)\Pc$
  possesses (IDP) whenever $n\Pc$ and $m\Pc$ possess 
    (IDP).   The paper \cite{LM} constructs a 50-dimensional polytope $\Pc_{25,27}$
  such that $2\Pc_{25,27}$ and $3\Pc_{25,27}$ have (IDP) while $5\Pc_{25,27}$
  does not.  
\end{itemize}
\end{Remark}





\section{The case of dilated edge polytopes}


Finally, we discuss the case of edge polytopes. 

Recall that for a connected simple graph $G$ on the vertex set $\{1,\ldots,d\}$ 
with the edge set $E(G)$, the {\em edge polytope} of $G$ is 
the convex polytope $\Pc_G \subset \RR^d$ 
which is the convex hull of $\{\eb_i+\eb_j : \{i,j\} \in E(G)\}$. Also:
\begin{itemize}
\item An {\em odd} cycle is a cycle with odd length. 
\item A cycle $C$ in $G$ is called {\em minimal} if $C$ possesses no chord. 
\item A pair of disjoint odd cycles $C$ and $C'$ in $G$ is said to be {\em exceptional} 
if there is no bridge between $C$ and $C'$ in $G$. 
\item We say that $G$ satisfies the {\em odd cycle condition} 
if each pair of disjoint odd cycles is not exceptional. 
\end{itemize}


It is known by the proof of \cite[Theorem 2.2]{OH} that for a connected graph $G$, 
$\Pc_G$ has (IDP) if and only if $\Pc_G$ is normal, although this fact is not mentioned explicitly. 
It is also proved that $\Pc_G$ is normal if and only if $G$ satisfies the odd cycle condition (\cite[Corollary 2.3]{OH}). 

\begin{Proposition}
Let $G$ be a connected simple graph on 
$\{1,\ldots,d\}$ which does not satisfy the odd cycle condition. 
For disjoint odd cycles $C_1$ and $C_2$, let 
\begin{align*}
m(C_1,C_2)=\frac{\ell(C_1)+\ell(C_2)}{2}, \;\; 
\end{align*} 
where $\ell(C_i)$ denotes the length of a cycle $C_i$. 
For an edge polytope $\Pc_G$, one has 
\begin{align*}
\mu_\text{{\em va}}(\Pc_G)&=\mu_\text{{\em Hilb}}(\Pc_G)\\
&=\max\left\{m(C,C') : (C,C') \; \text{{\em 
is an exceptional pair of minimal odd cycles}}\right\} 
\end{align*}
and $$\mu_\text{{\em hole}}(\Pc_G)=\max\left\{\sum_{i=1}^l m(C_{2i-1},C_{2i})\right\},$$ 
where $C_1,\ldots,C_{2l}$ are disjoint and 
each of $(C_{2i-1},C_{2i})$ is an exceptional pair of minimal odd cycles. 
If there is no exceptional pair, we let these maximums be one. 
\end{Proposition}
\begin{proof}
In the case of edge polytopes, by \cite[Theorem 2.2]{OH}, 
$\Hc(\Cc(\Pc_G))$ and Box$(\Pc_G)$ can be written 
in terms of exceptional pairs of minimal odd cycles as follows: 
For a pair of minimal odd cycles $C$ and $C'$, let 
$$e(C,C')=\sum_{i \in V(C) \cup V(C')}\eb_i,$$ 
where $V(C)$ denotes the set of vertices of a cycle $C$. Then we have 
$$\Hc(\Cc(\Pc_G))=\{e(C, C') : (C, C') \text{ is an exceptional pair of minimal odd cycles}\}$$ 
and \begin{align}\label{box}
\text{Box}(\Pc_G)=\left\{\sum_{i=1}^le(C_{2i-1},C_{2i})\right\},\end{align}
where $C_1,\ldots,C_{2l}$ are disjoint and each of $(C_{2i-1},C_{2i})$ is an exceptional pair of minimal odd cycles. 
Since $e(C_1,C_2) \in m(C_1,C_2)\Pc_G \cap \ZZ^N$, we obtain $\mu_\text{Hilb}(\Pc_G)=M$, 
where $M=\max\{m(C,C') : (C,C') \; \text{is an exceptional pair of minimal odd cycles}\}$, 
and $\mu_\text{hole}(\Pc_G) = \max\left\{\sum_{i=1}^l m(C_{2i-1},C_{2i})\right\}$. 
Our goal is to show $\mu_\text{va}(\Pc_G) \geq M$. 

Let $C_1$ and $C_2$ be disjoint minimal odd cycles and 
let $(C_1,C_2)$ be exceptional and $M=m(C_1,C_2)$. 
Assume that $\{i_1,i_2\}$ is one edge in $C_1$. For each positive integer $\ell$, 
since there is no bridge between $C_1$ and $C_2$ and these cycles are minimal, one has 
$$e(C_1,C_2)+\ell(\eb_{i_1}+\eb_{i_2}) \in 
((M+\ell)\Pc_G \cap \ZZ^N) \setminus \{\alpha_1+\cdots+\alpha_{M+\ell} : \alpha_i \in \Pc_G \cap \ZZ^N\}.$$
Fix a positive integer $n$ with $n <M$. 
For every integer $m \geq \min\{ k : kn \geq M \}$, one has 
$$e(C_1,C_2)+(mn-M)(\eb_{i_1}+\eb_{i_2}) \in m(n \Pc_G) \cap \ZZ^N.$$ 
Since $n<M$, this integer point cannot be written as a sum of $m$ elements belonging to $n \Pc_G \cap \ZZ^N$. 
This says that $n \Pc_G$ is never very ample. Therefore, $\mu_\text{va}(\Pc_G) \geq M$, as desired. 
\end{proof}

On $\mu_\text{midp}(\Pc_G)$ and $\mu_\text{idp}(\Pc_G)$ of edge polytopes $\Pc_G$, 
these are not necessarily equal to $M$, although we still have 
$\mu_\text{idp}(\Pc_G) \geq \mu_\text{midp}(\Pc_G) \geq M$ because of $\mu_\text{va}(\Pc_G)=M$. 
\begin{Example}
Let us consider the graph $G$ on the vertex set $\{1,\ldots,25\}$ with the edge set 
\[
E(G)=\{\{3i+1,3i+2\},\{3i+2,3i+3\},\{3i+1,3i+3\},\{3i+1,25\} : 0 \le i
\le 7\}. 
\]
Then each of exceptional pairs of minimal odd cycles in this graph 
consists of two cycles of length 3. Thus 
we have $\mu_\text{va}(\Pc_G)=\mu_\text{Hilb}(\Pc_G)=3$. 
Moreover, since this graph contains four disjoint exceptional pairs of minimal odd cycles, 
one has $\mu_\text{hole}(\Pc_G)=12$. In addition, we also see that $3\Pc_G$ has (IDP). 
Hence $\mu_\text{midp}(\Pc_G)=3$. 
On the other hand, neither $4\Pc_G$ nor $5\Pc_G$ has (IDP). In fact, 
\begin{align*}
&(\underbrace{1,\ldots,1}_{24},0) \in 3(4\Pc_G) \cap \ZZ^{25} \setminus 
\{\alpha_1+\alpha_2+\alpha_3 : \alpha_i \in 4\Pc_G \cap \ZZ^{25}\}\;\;\;\text{and} \\
&(\underbrace{1,\ldots,1}_{20},0,0,0,0,0) \in 2(5\Pc_G) \cap \ZZ^{25} \setminus 
\{\alpha_1+\alpha_2 : \alpha_i \in 5\Pc_G \cap \ZZ^{25}\}. 
\end{align*}
Thus $\mu_\text{idp}(\Pc_G) \geq 6$. In fact, one can show that $\mu_\text{idp}(\Pc_G)=6$. 

Let us consider the graph $G'$ on the vertex set $\{1,\ldots,30\}$ with the edge set 
$$E(G')=E(G) \cup \{\{25+i,26+i\},\{26,30\} : i=0,1,2,3,4\}.$$ 
Then there is an exceptional pair consisting of minimal odd cycles of length 3 and 5. 
Thus $\mu_\text{va}(\Pc_{G'})=\mu_\text{Hilb}(\Pc_{G'})=4$. 
Moreover, one has $\mu_\text{hole}(\Pc_{G'})=13$. In addition, similar to the case of the above $G$, 
neither $4\Pc_{G'}$ nor $5\Pc_{G'}$ has (IDP). 
However, we can check that $k\Pc_{G'}$ has (IDP) for $k \geq 6$, 
implying $\mu_\text{midp}(\Pc_{G'})=\mu_\text{idp}(\Pc_{G'})=6$. 
\end{Example}

\begin{thebibliography}{99}

\bibitem{BDG} 
M. Beck, J. Delgado and J. Gubeladze, 
Very ample and Koszul segmental fibrations,
{\tt arXiv:1307.7422 [math.CO]}.

\bibitem{BR}
M. Beck and S. Robins,
``Computing the Continuous Discretely,''
Undergraduate Texts in Mathematics,
Springer, 2007.

\bibitem{BG}
W. Bruns and J. Gubeladze, 
``Polytopes, rings and K-theory,'' Springer--Verlag, Heidelberg, 2009. 

\bibitem{BGcover}
W. Bruns and J. Gubeladze,
{Unimodular covers of multiples of polytopes},
{\em Doc. Math.} {\bf 7} (2002), {463--480}.

\bibitem{BGT}
W. Bruns, J. Gubeladze and N. V. Trung, 
Normal polytopes, triangulations, and Koszul algebras, 
{\em J. Reine Angew. Math.} {\bf 485} (1997), 123--160. 

\bibitem{CLS} 
D. Cox, J. Little and H. Schenck, ``Toric varieties,'' Graduate
Studies in Mathematics, American Mathematical Society, 2011.

\bibitem{EwaldWessels}
G.\ Ewald and U.\ Wessels,
{On the ampleness of invertible sheaves in complete projective toric
  varieties},
{\em Results Math.} {\bf 19} (1991), {275--278}.

\bibitem{Gordan}
{P.\ Gordan},
{Ueber die {A}ufl\"osung linearer {G}leichungen mit reellen
  {C}oefficienten},
{\em Math. Ann.}
{\bf 6} (1873),
{23--28}.

\bibitem{HibiRedBook}
T. Hibi, ``Algebraic Combinatorics on Convex Polytopes,''
Carslaw Publications, Glebe NSW, Australia, 1992.

\bibitem{KKMS}
G.\ Kempf, F.\ Knudsen, D.\ Mumford and B.\ Saint--Donat,
{``Toroidal {Embeddings} {I},''}
Lecture Notes in Mathematics {\bf 339},
{Springer--Verlag},
1973.

\bibitem{LM}
M.\ Laso\'n and M. Micha{\l}ek,
{Non-normal, very ample polytopes -- constructions and examples}, 
arXiv:1406.4070 [math.CO].

\bibitem{LiuTrotterZiegler}
J.\ Liu, L.\ Trotter and G.\ Ziegler,
{On the height of the minimal {H}ilbert basis},
{\em Results Math.} {\bf 23} (1993), {374--376}.

\bibitem{MS}
E.\ Miller and B.\ Sturmfels, ``Combinatorial Commutative Algebra'',
Graduate Texts in Mathematics, Springer, 2005.

\bibitem{MFO07}
{Mini-Workshop: Projective normality of smooth toric
  varieties},
{Abstracts from the mini-workshop held August 12--18,
  2007. Organized by Christian Haase, Takayuki Hibi
  and Diane MacLagan},
{\em Oberwolfach Rep.}
{\bf 4} (2007), {2283--2320}.

\bibitem{OH}
H. Ohsugi and T. Hibi, 
Normal Polytopes Arising from Finite Graphs, {\em J. Algebra}
{\bf 207} (1998), 409--426. 

\bibitem{Sch}
A. Schrijver, 
``Theory of Linear and Integer Programming,''
John Wiley \& Sons, 1986.

\bibitem{vanDerCorput}
J.\ van der Corput,
Konstruktion der Minimalbasis f\"ur spezielle Diophantische Systeme
von linear-homogenen Gleichungen und Ungleichungen,
Proc. Roy. Acad. Amsterdam
{\bf 34} (1931),
515--523.

\end{thebibliography}



\end{document}
