arXiv:1211.5755v2 [math.CO] 15 Jun 2013

INTEGER DECOMPOSITION PROPERTY OF DILATED
POLYTOPES
DAVID A. COX, CHRISTIAN HAASE, TAKAYUKI HIBI AND AKIHIRO HIGASHITANI
Abstract. Let P ⊂ RN be an integral convex polytope of dimension d and write
kP, where k = 1, 2, . . . , for dilations of P. We say that P possesses the integer
decomposition property if, for any integer k = 1, 2, . . . and for any α ∈ kP ∩ ZN ,
there exist α1 , . . . , αk belonging to P ∩ ZN such that α = α1 + · · · + αk . A
fundamental question is to determine the integers k > 0 for which the dilated
polytope kP 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.

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 integral convex polytope is a
convex polytope all of whose vertices have integer coordinates.
There is an entire network [12, p.2313] of combinatorial and algebraic properties of
integral polytopes for which it is interesting to study the behavior under dilations [3,
4, 10]. In the present paper, we are especially interested in the integer decomposition
property of integral convex polytopes, which is particularly important in the theory
and application of integer programming [15, §22.10].
(0.1) We say that an integral convex polytope P ⊂ RN possesses the integer
decomposition property or (IDP) for short if, for every integer k = 1, 2, . . . and for all
α ∈ kP ∩ZN , there exist α1 , . . . , αk belonging to P ∩ZN such that α = α1 + · · ·+ αk .
Here, kP = {kα : α ∈ P} ⊂ RN is the dilated polytope.
Furthermore, we say that an integral convex polytope P ⊂ RN is very ample if, for
any sufficiently large integer k ≫ 0 and for any α ∈ kP ∩ ZN , there exist α1 , . . . , αk
belonging to P ∩ ZN such that α = α1 + · · · + αk . Thus in particular if P possesses
(IDP), then P is very ample.
(0.2) Let C ⊂ RN be a pointed, rational and polyhedral cone generated by rational
vectors a1 , . . . , am ∈ QN . Thus
C = R≥0 {a1 , . . . , am } = {λ1 a1 + · · · + λm am : λ1 , . . . , λm ∈ R≥0 }
2010 Mathematics Subject Classification: Primary 52B20; Secondary 14Q15, 14M25.
Keywords: dilated polytope, integer decomposition property, Hilbert basis.
1

such that {0} is the largest linear subspace contained in C. A finite set of integer
vectors {h1 , . . . , hs } ⊂ ZN is called a Hilbert basis of C if
C ∩ ZN = Z≥0 {h1 , . . . , hs } := {λ1 h1 + · · · + λs hs : λ1 , . . . , λs ∈ Z≥0 }.
A Hilbert basis exists [7] and a minimal Hilbert basis is unique [16]. Let H(C) denote
the minimal Hilbert basis of C. In terms of Hilbert bases, an integral convex polytope
P ⊂ RN is very ample if and only if for all vertices α of P the set (P − α) ∩ ZN is
a Hilbert basis for the cone it generates (cf. [2, Ex. 2.23]).
e ⊂ RN +1 for the integral convex polytope {(α, 1) ∈ RN +1 : α ∈ P}.
We will write P
Let C(P) ⊂ RN +1 denote the pointed rational polyhedral cone generated by the
e The degree of (α, n) ∈ C(P) ∩ ZN +1 is deg(α, n) = n.
vertices of P.
(0.3) A simplex S ⊂ RN is called empty if S ∩ZN is the set of vertices of S. Given
an empty simplex S ⊂ RN , we define the finite subset Box(S) ⊂ C(S) as follows:


 X

Box(S) =
ri (vi , 1) ∈ ZN +1 : 0 ≤ ri < 1 .


N
vi ∈S∩Z

We have H(C(S)) ⊆ Box(S) ∪ (Se ∩ ZN +1 ).
Let, in general, P ⊂ RN be an integral convex polytope of dimension d. We then
define Box(P) by setting
[
e ∩ ZN +1 ),
Box(P) =
Box(S) \ Z≥0 (P
S

where S runs over all empty simplices of dimension d with S ⊂ P. Each element
S
belonging to Box(P) is called a hole of P. We have H(C(P)) ⊆ S H(C(S)) ⊆
e ∩ ZN +1 ).
Box(P) ∪ (P
(0.4) Let δ(P) = (δ0 , δ1 , . . . , δd ) denote the δ-vector ([8, Chapter XI]) of an integral convex polytope P ⊂ RN of dimension d. We write k0 for the smallest integer
k > 0 for which k(P \ ∂P) ∩ Zd 6= ∅ and i0 for the largest integer i for which δi 6= 0.
It is known [1, Theorem 4.5] that
k0 = (d + 1) − i0 .

Definition 0.1. Given an integral convex polytope P ⊂ RN , we introduce the
invariants
µva (P), µmidp(P), µidp(P), µHilb(P), µhole (P), µEhr (P),
each of which is defined in what follows:
• µva (P) is the smallest integer k > 0 for which the dilated polytope kP is
very ample;
• µmidp(P) is the smallest integer k > 0 for which the dilated polytope kP
possesses (IDP);
2

• µidp (P) is the smallest integer k > 0 for which the dilated polytopes nP
possess (IDP) for all n ≥ k;
• µHilb(P) is the maximal degree of elements belonging to the minimal Hilbert
basis H(C(P)) of C(P);
• µhole (P) is the maximal degree of elements belonging to Box(P), with the
convention that µhole (P) = 1 if Box(P) = ∅;
• µEhr (P) is the largest integer i > 0 for which δi 6= 0, where (δ0 , δ1 , . . . , δd )
denotes the δ-vector of P.
The final goal of our research project is to find a combinatorial characterization
of the sequences
µ(P) = (µva (P), µmidp(P), µidp (P), µHilb(P), µhole (P), µEhr (P))
arising from integral convex polytopes P of dimension d.
First of all, in Section 1, we give basic inequalities which the above sequence µ(P)
satisfies. More precisely, Theorem 1.1 says that
1 ≤ µva (P) ≤ µmidp (P) ≤ µidp (P) ≤ µhole (P) ≤ µEhr (P) ≤ d;
1 ≤ µva (P) ≤ µHilb(P) ≤ µhole (P) ≤ d − 1.
Various examples will be supplied in Section 2. In Theorem 2.1, we prove that,
given integers d ≥ 3 and 2 ≤ j ≤ d−1, there exists an empty simplex P of dimension
d with µ(P) = (j, j, j, j, j, j). In Theorem 2.6, we prove that, given an integer d ≥ 4,
there exists an integral convex polytope P of dimension d such that µHilb(P) = d − 1
and µmidp (P) = µidp (P) = d − 2. In addition, we give examples of integral convex
polytopes P, P ′ and P ′′ with
• µva (P) < µmidp(P), µva (P) < µHilb(P);
• µmidp(P ′ ) < µidp (P ′ ) < µhole (P ′ ), µHilb(P ′ ) < µhole (P ′ );
• µhole (P ′′ ) < µEhr (P ′′ ).
Moreover, in Section 3, more detailed relations between µmidp (P) and µidp (P) will
be discussed (Theorem 3.2). Finally, we compute in Section 4 the invariants of edge
polytopes arising from finite graphs.
1. Invariants related to dilated polytopes
In this section, we discuss the sequence µ(P) of the invariants of an integral convex
polytopes P of dimension d related to (IDP). More precisely, we prove the following.
Theorem 1.1. For the invariants appearing in the introduction of an integral convex
polytope P ⊂ RN of dimension d, the following inequalities hold:
(1)

1 ≤ µva (P) ≤ µmidp(P) ≤ µidp(P) ≤ µhole (P) ≤ µEhr (P) ≤ d
and 1 ≤ µva (P) ≤ µHilb(P) ≤ µhole (P) ≤ d − 1.
3

Proof. The inequalities 1 ≤ µva (P) ≤ µmidp (P) ≤ µidp (P) and µEhr (P) ≤ d are clear
from their definitions. On the other hand, since the assertions are obvious if P has
(IDP), we assume that Box(P) is not empty.
• µidp (P) ≤ µhole (P): This inequality is proved, though not stated, in [11]. We give
the proof for the sake of completeness.
It follows from Gordan’s Lemma [15, Theorem 16.4] and Carathéodory’s Theorem
[15, Corollary 7.1i] that C(P) ∩ ZN +1 consists of the elements of
e ∩ ZN +1 )}.
{α + x : α ∈ Box(P) ∪ {0}, x ∈ Z≥0 (P

Thus for n ≥ µhole (P) and an element α ∈ ℓ(nP) ∩ ZN , we can write (α, ℓn) ∈
C(P) ∩ ZN +1 as (α0 , n0 ) + (α1 , 1) + . . . + (αr , 1) with n0 ≤ n. These summands can
now be grouped into ℓ elements of nPe ∩ ZN +1 .
• µhole (P) ≤ µEhr (P): This inequality follows from the fact that δi counts box points
of degree i in a triangulation of P, cf. [1, Pf. of Thm. 3.12]. Here is the argument.
Let (α, µhole (P)) ∈ Box(P) attain µhole (P). Then, by definition of Box(P), we
can describe (α, µhole(P)) as a linear combination of (d + 1) linearly independent
Pd
e Say, (α, µhole (P)) =
, 1) with 0 ≤ ri < 1. Let
lattice vectors in P.
i=0 ri (v
Pi d
Pd
N +1
. Since 1 − ri > 0 and i=0 (1 − ri ) = d + 1 − µhole(P),
β = i=0 (1 − ri )(vi , 1) ∈ Z
one has β ∈ (d+1−µhole(P))(P\∂P)∩ZN , certifying d+1−µEhr(P) ≤ d+1−µhole(P).
• µva (P) ≤ µHilb(P): Let α be a vertex of P, and let β be an integer point in
the cone generated by P − α. Then, for a sufficiently large integer k, we have
(β + kα, k) ∈ C(P) ∩ ZN +1 . This point can be written as a nonnegative integral
P
linear combination of H(C(P)): (β + kα, k) = h∈H(C(P)) wh h with wh ∈ Z≥0 . This
implies that
X


(β, 0) =
wh (h + (µHilb(P) − deg(h))(α, 1)) − µHilb(P)(α, 1)
h∈H(C(P))

is a nonnegative integral linear combination of integer points in µHilb(P)(P−α)×{0},
showing that µHilb(P)P is very ample.
• µHilb (P) ≤ µhole (P): This follows from H(C(P)) ⊆ Box(P) ∪ (Pe ∩ ZN +1 ).
• µhole (P) ≤ d − 1: Here is the argument from [11]. Let S ⊂ RN be an empty
simplex of dimension d and let v0 , v1 , . . . , vd be its vertices. Given v ∈ Box(S) there
P
are r0 , r1 , . . . , rd with 0 ≤ ri < 1 such that v = di=0 ri (vi , 1). Since ri < 1, one has
P
deg(v) = di=0 ri < d + 1. Suppose that deg(v) = d. Then all ri must be positive.
P
Moreover, we have di=0 (1 − ri ) = 1 and 0 < 1 − ri < 1. Thus the integer point
Pd
i=0 (1−ri )vi belongs to the interior of S, a contradiction. Hence deg(v) ≤ d−1. 
2. Proper inequalities of (1)

In this section, we present a lot of examples of integral convex polytopes. Each
of the examples satisfies a proper inequality in (1).
4

Before giving them, we see that there exists an integral convex polytope P attaining µva (P) = µmidp(P) = µidp (P) = µHilb (P) = µhole (P) = µEhr (P).
Theorem 2.1. Given integers d ≥ 3 and 2 ≤ j ≤ d−1, there exists an empty simplex
P of dimension d with µva (P) = µmidp(P) = µidp (P) = µHilb(P) = µhole (P) =
µEhr (P) = j.
Proof. Fix positive integers d and j with d ≥ 3 and 2 ≤ j ≤ d − 1. Write P(d, j) ⊂
Rd for the convex hull of {v0 , v1 , . . . , vd } ⊂ ZN , where v0 = 0 = (0, . . . , 0) and
vi , i = 1, . . . , d, is the ith row vector of the matrix


1 0
0 ··· ··· ··· 0



0 1 . . .
0


.
.
. .. .. ..
.. 
.
.
.

.

.
.
.. ..
..
.
 ..
.
(2)
.
.
.
.


.
..
..
. . .. 
 ..
.
.
. .




.
.
0
. 1 0
1 ···

1

···

0

0

j

Here there are j 1’s in the dth row. Let P = P(d, j) and (δ0 , δ1 , . . . , δd ) be the
δ-vector of P. We prove that P enjoys the required properties.
Let ei ∈ Rd for i = 1, . . . , d denote a unit coordinate vector of Rd . Since the
determinant of (2) is j, the normalized volume of P is j. Moreover,
j

q
qX
j−q
(3) (v0 , 1) +
(vd , 1) = (e1 + · · · + ej + (j − q)ed , q + 1),
(vi , 1) +
j
j i=1
j

where q = 1, . . . , j − 1. Thus δq ≥ 1 for q = 2, . . . , j ([8, Proposition 27.7]). Since
Pd
i=0 δi = j and each δi is nonnegative, one has
(δ0 , δ1 , . . . , δd ) = (1, 0, 1, 1, . . . , 1, 0, . . . , 0).
| {z }
j−1

In particular, µEhr (P) = j. Moreover, from δ1 = 0, P is an empty simplex. Thus,
once we show µva (P) ≥ j, we conclude that P has the desired properties by (1) in
Theorem 1.1.
Using (3), one can show without difficulty that the Hilbert basis H(C(P)) is
e ∩ Zd+1 ) ∪ {(e1 + · · · + ej + (j − q + 1)ed , q) : q = 2, . . . , j}.
(P

Now, we show that kP cannot be very ample for 1 ≤ k < j. Let k be an integer
with 1 ≤ k < j and m the least common multiple of k and j. Write m = kg with
g ≥ 2. Let
α = (α0 , m + ℓk), α0 = (m − j + ℓk + 1)e1 + e2 + · · · + ej + ed ,
5

where ℓ is an arbitrary nonnegative integer. Since
α = (m − j + ℓk)(v1 , 1) + (e1 + · · · + ej + ed , j),
it follows that α belongs to C(P) ∩ Zd+1 . This implies, first, that α 6∈ Z≥0 (Pe ∩ Zd+1 )
and, second, that
α0 ∈ (m + ℓk)P ∩ ZN = (g + ℓ)(kP) ∩ ZN .

If kP was very ample, then for sufficiently large, we could write α0 = α1 + · · ·+ αg+ℓ ,
where α1 , . . . , αg+ℓ ∈ kP ∩ZN . Then the dth coordinate of each of α1 , . . . , αg+ℓ must
be 0 or 1. Consider (αi , k) ∈ C(P) ∩ Zd+1 for 1 ≤ i ≤ g + ℓ. Since each h ∈ H(C(P))
with 2 ≤ deg h ≤ k is of the form
h = (e1 + · · · + ej + (j − i + 1)ed , i),
where i = 2, . . . , k, none of α1 , . . . , αg+ℓ can be expressed by using such elements.
Thus each of (α1 , k), . . . , (αg+ℓ , k) must be written as the sum of k elements belonging
e ∩ Zd+1 . It then follows that α = (α0 , m + ℓk) can be written as the sum of
to P
e ∩ Zd+1 . This contradicts α 6∈ Z≥0 (P
e ∩ Zd+1 ).
(m + ℓk) elements belonging to P
Consequently, kP cannot be very ample, as required.


The following three examples (Example 2.2, 2.3 and 2.4) show the existence of
integral convex polytopes attaining each of proper inequalities of (1).
Example 2.2 (µva (P) < µmidp(P) and µva (P) < µHilb(P)). In [9, Theorem 0.1],
for each d ≥ 3, the fourth author establishes an example of a very ample integral
convex polytope not having (IDP). From the proof there, we know that this polytope
satisfies µva (P) = 1 but µmidp(P) = µHilb(P) = 2.

Example 2.3 (µmidp (P) < µidp (P) < µhole (P) and µHilb (P) < µhole (P)). Let
d = 2m − 1 with m ≥ 4 and P be the integral simplex whose vertex set is
{0, e1 , . . . , ed−1 , (m − 1)e1 + · · · + (m − 1)ed−1 + med }. Then it is immediate to
see that one has
Box(P) = {(j, . . . , j, 2j) : j = 1, . . . , m − 1}.
Thus, for j = 2, . . . , m − 1, we can write (j, . . . , j, 2j) = j(1, . . . , 1, 2). This implies
that {x ∈ H(C(P)) : deg(x) ≥ 2} = {(1, . . . , 1, 2)}. Hence µHilb(P) = 2, while
µhole (P) = 2m − 2 = d − 1.
Moreover, we also know that
(4)

e ∩ Zd+1 )∪
C(P) ∩ Zd+1 = Z≥0 (P

e ∩ Zd+1 )}.
{(j, . . . , j, 2j) + x : 1 ≤ j ≤ m − 1, x ∈ Z≥0 (P

It then follows from (4) that for every element α in 2kP ∩Zd with k ≥ 1, we can write
α = α1 + · · · + αℓ , where k ≤ ℓ ≤ 2k and αi ∈ P ∩ Zd or αi = (1, . . . , 1) ∈ 2P ∩ Zd .
6

By rewriting appropriately, we can express α = α1′ + · · · + αk′ , where αi′ ∈ 2P ∩ Zd .
This means that µmidp(P) = 2.
On the other hand, we have (3, . . . , 3) ∈ 2(3P) ∩ Zd but (3, . . . , 3) 6∈ {α + β :
α, β ∈ 3P ∩ Zd } because of 3 ≤ m − 1 and (4). Similarly, kP does not possess (IDP)
when k is odd and k ≤ m − 1. However, if k ≥ m, then Q = kP has (IDP). In fact,
for α ∈ ℓQ ∩ Zd with ℓ ≥ 2, since ℓk ≥ 2k ≥ 2m and Box(P) has at most degree
2m − 2 elements, we can express α as α = (j, . . . , j) + α′ , where 1 ≤ j ≤ m − 1 and
α′ ∈ {α1′ + · · · + αq′ : αi ∈ P ∩ Zd , q ≥ 2}. Thanks to q ≥ 2, α can be described as a
sum of ℓ elements belonging to Q ∩ Zd . Hence we obtain
(
m−1
if m is odd,
µidp (P) =
m
if m is even.
Therefore, in summary,
2 = µHilb(P) = µmidp (P) < µidp (P) = 2

jmk
2

< µhole (P) = 2m − 2.

Example 2.4 (µhole (P) < µEhr (P)). When P is an integral convex polytope of
dimesnion d which does not have (IDP) and contains an integer point in its interior,
one has µEhr (P) = d but µhole (P) ≤ d − 1. For example, let us consider the integral
simplex P of dimension d ≥ 3 whose vertices are 0 and the row vectors of d × d
matrix


1
0 ··· ···
0

.. 
..
 0
.
. 
1


..  .
 ..
..
..
..
.
.
.
 .
. 


 0
··· 0
1
0 
d+1 ··· ··· d+1 d+2
Let v0 = 0 and let vi denote the ith row vector. Then the integer point
2
1
v0 +
(v1 + · · · + vd ) = (1, . . . , 1)
d+2
d+2
is contained in the interior of P, implying µEhr (P) = d. On the other hand, it is
easy to see that






d+1
d+1
d+1
Box(P) =
+ 1, . . . ,
+ 1,
,
2
2
2
 
implying µhole (P) = d+1
.
2

Next, we consider possible relations between µHilb (P) and µmidp (P) and also between µHilb(P) and µidp (P). As is shown below, there are no relations between
them.
7

Example 2.5 (µHilb(P) < µmidp (P)). The following integral simplex P of dimension
13 has µHilb(P) = 3 but
 µmidp
(P) = 4: Let P be a convex hull of 0 and the row
A 0
vectors of the matrix
, where A (resp. B) is a 7 × 7 (resp. 6 × 6) matrix
0 B
such that




1 0 ··· ··· 0
1 0 ··· ··· 0


.. 
.. 
0 1 . . .

0 1 . . .
.
.




.
.
.
.
. ..
..
. . . ).
..
. . .  (resp.  . . .
.
.
. .
.
.
. .
.
.




0 · · · 0
0 · · · 0
1 0
1 0
1 ··· ··· 1 2
3 ··· ··· 3 4

Notice that A corresponds to the polytope in Example 2.3 in the case of m = 4. It
can be verified that
H(C(P)) = (Pe ∩ Zd+1 ) ∪ {(1, . . . , 1, 0, . . . , 0, 2), (0, . . . , 0, 1, . . . , 1, 3)}.
| {z } | {z }
| {z } | {z }
7

6

7

6

Thus µHilb(P) = 3. On the other hand, neither 2P nor 3P possesses (IDP). (In fact,
f ∩ Zd+1 ) and (3, . . . , 3, 0, . . . , 0, 6) ∈
(0, . . . , 0, 1, . . . , 1, 4) ∈ C(2P) ∩ Zd+1 \ Z≥0 (2P
f ∩ Zd+1 ).) Hence µmidp (P) ≥ 4. In fact, one can show that
C(3P) ∩ Zd+1 \ Z≥0 (3P
µmidp (P) = 4.
Note that an example attaining µHilb(P) < µidp(P) has been already given in
Example 2.3. The following theorem gives an example attaining both µHilb (P) >
µmidp (P) and µHilb(P) > µidp (P).
Theorem 2.6. Given an integer d ≥ 4, there exists an integral convex polytope P
of dimension d such that µHilb (P) = d − 1 and µmidp (P) = µidp (P) = d − 2.
Proof. Work with a fixed integer d ≥ 4 and let M = d(d − 2) + 1. We define vj ∈ Zd ,
1 ≤ i ≤ d, as follows:


j = 0,

0,
vj = ej ,
j = 1, . . . , d − 1,


e1 + · · · + ed−1 + Med , j = d.

Let vj′ = vj + ed for j = 0, 1, . . . , d. We write P ⊂ Rd for the integral convex
polytope of dimension d with the vertices v0 , v1 , . . . , vd and v0′ , v1′ , . . . , vd′ . Such a
convex polytope appears in [13, Section 1].
It will be proved that P enjoys the required properties.
(First Step) First of all, the Hilbert basis H(C(P)) must be computed. If q ∈
{1, . . . , M − 1}, then there exist unique integers k and s with 1 ≤ k ≤ d − 2 and
8

1 ≤ s ≤ d such that q = (k − 1)d + s. Since
d−1

(d − 2)s − k + 1
q
M −q X
(vj , 1) + (vd , 1)
(v0 , 1) +
M
M j=1
M

= (e1 + · · · + ed−1 + qed , d − k) ∈ Zd+1 ,

it follows that (e1 + · · · + ed−1 + qed , d − k) ∈ C(P) ∩ Zd+1 . When k = 1 and
s = 1, . . . , d − 1, one has q = s and
(e1 + · · · + ed−1 + qed , d − 1) =

s
X

(vj′ , 1) +

j=1

d−1
X

(vj , 1).

j=s+1

Hence (e1 + · · · + ed−1 + qed , d − 1) cannot belong to H(C(P)). Now, it is routine
work to show that, by considering the facets of the cone C(P), the Hilbert basis
H(C(P)) coincides with
(Pe ∩ Zd+1 ) ∪ {(e1 + · · · + ed−1 + qed , d − ⌊(q − 1)/d⌋ − 1) : q = d, . . . , M − 1}.

Thus, in particular, µHilb(P) = d − 1.
(Second Step) Let

u(k)
s = e1 + · · · + ed−1 + ((k − 1)d + s)ed ,
where k = 2, . . . , d − 2 and s = 1, . . . , d, and
u = e1 + · · · + ed−1 + ded .
One can easily see the identities
(u, d − 1) + (vi , 1) =

(vi′ , 1)

+

d−1
X

(vj′ , 1) for i = 0, 1, . . . , d,

j=1

(2)

(u, d − 1) + (vi′ , 1) = (v0 , 1) + (vi , 1) + (u1 , d − 2) for i = 0, 1, . . . , d,
(u, d − 1) +

(us(d−2) , 2)

s−1
d−1
X
X
′
= (v0 , 1) + (vd , 1) +
(vj , 1) +
(vj , 1),
j=1

(k+1)
(u, d − 1) + (u(k)
, d − k − 1) +
s , d − k) = (us

j=s

d−1
X

(vj , 1) for k = 2, . . . , d − 3,

j=0

(u, d − 1) + (u, d − 1) =

(2)
(ud , d

− 2) +

d−1
X

(vj , 1).

j=0

It then follows that
(C(P) ∩ Zd+1 ) \ {(u, d − 1)} = Z≥0 (H(C(P)) \ {(u, d − 1)}).
9

Moreover, if k + k ′ ≥ d, then
(k ′ )

′
(u(k)
s , d − k) + (us′ , d − k ) =
(
(k+k ′ −d+1)
(vd , 1) + (us+s′−1
, 2d − k − k ′ − 1),

if s + s′ ≤ d + 1,

(k+k ′ −d+2)

(v0 , 1) + (vd , 1) + (us+s′−1−d , 2d − k − k ′ − 2),

if s + s′ ≥ d + 2.

If k + k ′ ≤ d − 1, then
(k ′ )

′
(u(k)
s , d − k) + (us′ , d − k ) =
( (k+k′−1)
P
P′
(us
, d − k − k ′ + 1) + sj=1(vj′ , 1) + d−1
j=s′ +1 (vj , 1),
P
(k+k ′ )
d−1
(us
, d − k − k ′ ) + j=0 (vj , 1),

if s′ ≤ d − 1,
if s′ = d.
(k)

Consequently, when we write α ∈ C(P) ∩ Zd+1 by using at least two us ’s, we can
(k)
(k)
reduce one us . Hence α can be expressed by using at most one us belonging to
H(C(P)).
(Third Step) Let P ′ = (d − 2)P and α ∈ nP ′ ∩ Zd . Since d ≥ 4, one has
n(d − 2) 6= d − 1. Thus α 6= u. By virture of the (Second Step), there exists an
expression of α of the form
n(d−2)−deg(v′ )
′

(α, n(d − 2)) = v +

X

(vj′′ , 1),

j=1

(k)

where v ′ ∈ {(us , d − k) : k = 2, . . . , d − 2, s = 1, . . . , d} and each vj′′ ∈ P ∩ Zd . Since
the degree of v ′ is at most d − 2, there exists an expression of α of the form
α = α1 + · · · + αn
with each αi ∈ P ′ ∩ Zd . Hence P ′ possesses (IDP).
(Fourth Step) By µidp(P) ≤ d − 1, kP possesses (IDP) for k ≥ d − 1. Thus, by
(Third Step), we obtain µidp (P) ≤ d − 2. Now it is easy to see that for r < d − 2,
rP never possesses (IDP). Therefore, we conclude that µmidp (P) = µidp (P) = d − 2,
as required.

3. Restrictions on invariants
In this section, we discuss more restrictions on the invariants. We consider the
following question.
Question 3.1. Let d, a1 , a2 , a3 , a4 , a5 , a6 be positive integers satisfying
a1 ≤ a2 ≤ a3 ≤ a5 ≤ a6 ≤ d and a1 ≤ a4 ≤ a5 ≤ d − 1.
Then does there exist an integral convex polytope P of dimension d such that
µva (P) = a1 , µmidp(P) = a2 , µidp (P) = a3 , µHilb(P) = a4 , µhole (P) = a5
and µEhr (P) = a6 ?
10

From some easy observations, we cannot assign these positive integers freely. In
fact, it is obvious that
• if either µmidp (P) or µHilb(P) is 1, then µva (P) = µmidp (P) = µidp (P) =
µHilb(P) = µhole (P) = 1;
• if µmidp (P) < µidp (P), then µidp (P) ≥ µmidp (P) + 2.
Moreover, we also see non-trivial restrictions.
Theorem 3.2. The following assertions hold:
(1) if µmidp (P) ≥ (d − 1)/2, then µidp (P) = µmidp(P);
(2) if µmidp (P) ≤ (d − 1)/2, then µidp (P) ≤ (d − 3)/2 + µmidp (P).
Before proving these, we prove the following lemma.
Lemma 3.3 (cf. [5, Theorem 2.2.12]). Let P ⊂ RN be an integral convex polytope
of dimension d. Given α ∈ nP ∩ ZN for n ≥ d − 1, α can be written like
α = α′ + α1 + · · · + αn−d+1 ,
where α′ ∈ (d − 1)P ∩ ZN and α1 , . . . , αn−d+1 ∈ P ∩ ZN .
A proof of this lemma appears in the proof of [5, Theorem 2.2.12].
Proof of Theorem 3.2. (1) It suffices to show that for an integral convex polytope
P ⊂ RN of dimension d with µmidp (P) ≥ (d − 1)/2, nP possesses (IDP) for every
n ≥ µmidp (P).
Let k = µmidp (P). Let n ≥ k and let α ∈ m(nP) ∩ ZN for m ≥ 2. Since
mn ≥ 2n ≥ 2k ≥ d − 1, thanks to Lemma 3.3, we obtain
α = α′ + α1 + · · · + αmn−d+1 ,
where α′ ∈ (d − 1)P ∩ ZN and α1 , . . . , αmn−d+1 ∈ P ∩ ZN . Moreove, since kP has
(IDP), there are α1′ and α2′ in kP ∩ ZN such that
α1′ + α2′ = α′ + αmn−2k+1 + · · · + αmn−d+1 ∈ 2kP ∩ ZN .
Therefore,
α=

α1′
|

+

n−k
X

2(n−k)

αi + α2′

{zi=1 }

nP∩ZN

|

+

X

αi +

i=n−k+1

{z

nP∩ZN

}

m−2
n
XX

α2(n−k)+(i−1)n+j .

i=1 j=1

|

{z

nP∩ZN

}

This implies that nP possesses (IDP).
(2) It suffices to prove that for an integral convex polytope P ⊂ RN of dimension d
with µmidp (P) ≤ (d − 1)/2, nP possesses (IDP) for every n ≥ (d − 3)/2 + µmidp (P).
For m ≥ 2, let α ∈ m(nP) ∩ ZN . Since mn ≥ 2n ≥ d − 3 + 2µmidp(P) ≥ d − 1,
thanks to Lemma 3.3, we obtain
α = α′ + α1 + · · · + αmn−d+1 ,
11

where α′ ∈ (d − 1)P ∩ ZN and α1 , . . . , αmn−d+1 ∈ P ∩ ZN .
Let k = µmidp(P) and ℓ = min{i : ik ≥ d − 1}. Since kP has (IDP), an element
′
α + αmn−ℓk+1 + · · · + αmn−d+1 belonging to ℓ(kP) ∩ ZN can be written such as
α1′ + · · · + αℓ′ , where αi′ ∈ kP ∩ ZN . Remark that ℓk − d + 1 ≤ mn − d + 1 because
mn − ℓk ≥ 2n − ℓk ≥ d − 3 + 2k − ℓk ≥ d − 2 − (ℓ − 1)k ≥ 0.
Thus α can be rewritten as
α = α1′ + · · · + αℓ′ + α1 + · · · + αmn−ℓk .
Let p = ⌊n/k⌋ and q = n−pk, i.e., n = pk +q with 0 ≤ q ≤ k −1. When p ≥ ℓ, since
n ≥ ℓk, it follows easily that α can be written as a sum of m elements of nP ∩ ZN .
Assume that p < ℓ. Then we have mn − ℓk ≥ q and n − (ℓ − p)k ≥ 0. In fact,
mn − ℓk − q ≥ 2n − ℓk − q = n − (ℓ − p)k
≥ d − 3 + 2k − ℓk − (k − 1) = d − 2 − (ℓ − 1)k ≥ 0.
Thus we obtain that
α=

p
X
i=1

|

αi′

+
{z

q
X
j=1

nP∩ZN

αj +
}

ℓ
X

i=p+1

|

n−(ℓ−p)k

αi′

+

X

{z

αq+j +

j=1

nP∩ZN

This says that nP possesses (IDP), as desired.

}

m−2
n
XX

αn−(ℓ−p)k+q+(r−1)n+i .

r=1 i=1

|

{z

nP∩ZN

}



As an immediate corollary of Theorem 3.2, we obtain the following.
Corollary 3.4. If µidp (P) = d − 1, then µmidp(P) = d − 1.
Proof. Suppose that µmidp (P) 6= d−1. In particular, µmidp(P) < d−1. If µmidp (P) ≥
(d − 1)/2, then µidp (P) = µmidp (P) < d − 1 by Theorem 3.2 (1). Moreover, if
µmidp (P) ≤ (d − 1)/2, then µidp (P) ≤ (d − 3)/2 + µmidp(P) ≤ (d − 3)/2 + (d − 1)/2 <
d − 1 by Theorem 3.2 (2). Hence, µidp (P) is never equal to d − 1, as desired.

Question 3.5. Work with the same notation as above.
(1) Is there some relation between µmidp(P), µidp (P) and µHilb(P)? For example,
does there exist an example of polytope P such that µmidp (P) < µHilb(P) <
µidp (P)?
(2) Is it true that µmidp(P) = µidp (P) = µHilb (P) = 2 if µva (P) = 1?
Moreover, the following is also interesting.
Question 3.6. For n, m ≥ 1, does (n + m)P possess (IDP) if nP and mP possess
(IDP)?
In general, Question 3.6 is no longer true for a Minkowski sum of polytopes having
(IDP). For example, conv({(0, 0, 0), (1, 0, 0), (0, 1, 0)}) and conv({(0, 0, 0), (1, 1, 3)})
possess (IDP), but their Minkowski sum does not.
12

Remark 3.7. In the book [2], two notions closely related to (IDP) are described.
Let P ⊂ RN be an integral convex polytope of dimension d. We say that P is
integrally closed if P satisfies
e ∩ ZN +1 ) = C(P) ∩ ZN +1
Z≥0 (P

and we say that P is normal if P satisfies

e ∩ ZN +1 ) = C(P) ∩ Z(Pe ∩ ZN +1 ).
Z≥0 (P

Then P satisfying (IDP) is equivalent P being integrally closed, but not necessarily
equivalent to P being normal.
4. 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, . . . , d} with the
edge set E(G), the edge polytope of G is the convex polytope PG ⊂ Rd which is the
convex hull of {ei + ej : {i, j} ∈ E(G)}. Also:
• An odd cycle is a cycle with odd length.
• A cycle C in G is called minimal if C possesses no chord.
• A pair of distinct odd cycles C and C ′ in G is said to be exceptional if there
is no bridge between C and C ′ in G.
• We say that G satisfies the odd cycle condition if each pair of distinct odd
cycles is not exceptional.
It is known that PG has (IDP) if and only if G satisfies the odd cycle condition
([14, Corollary 2.3]).
Proposition 4.1. Let G be a connected simple graph on {1, . . . , d} which does not
satisfy the odd cycle condition. For distinct odd cycles C1 and C2 , let
m(C1 , C2 ) =

ℓ(C1 ) + ℓ(C2 )
,
2

where ℓ(Ci ) denotes the length of a cycle Ci . For an edge polytope PG , one has
µva (PG ) = µHilb(PG )
= max {m(C, C ′ ) : (C, C ′ ) is an exceptional pair of minimal odd cycles}
and
µhole (PG ) = max

( l
X
i=1

)

m(C2i−1 , C2i ) ,

where C1 , . . . , C2l are distinct and each of (C2i−1 , C2i ) is an exceptional pair of minimal odd cycles.
13

Proof. In the case of edge polytopes, by [14, Theorem 2.2], H(C(PG )) and Box(PG )
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
X
e(C, C ′ ) =
ei ,
i∈V (C)∪V (C ′ )

where V (C) denotes the set of vertices of a cycle C. Then we have
H(C(PG )) = {e(C, C ′) : (C, C ′) is an exceptional pair of minimal odd cycles}
and
(5)

Box(PG ) =

( l
X
i=1

)

e(C2i−1 , C2i ) ,

where C1 , . . . , C2l are distinct and each of (C2i−1 , C2i ) is an exceptional pair of minimal odd cycles. Since e(C1 , C2 ) ∈ m(C1 , C2 )PG ∩ ZN , we obtain µHilb(PG ) = M,
where M = max{m(C,
C ′) : (C, C ′) is anoexceptional pair of minimal odd cycles},
nP
l
and µhole (PG ) = max
i=1 m(C2i−1 , C2i ) . Our goal is to show µva (PG ) ≥ M.
Let C1 and C2 be distinct minimal odd cycles and let (C1 , C2 ) be exceptional and
M = m(C1 , C2 ). Assume that {i1 , i2 } is one edge in C1 . For each positive integer ℓ,
since there is no bridge between C1 and C2 and these cycles are minimal, one has
e(C1 , C2 ) + ℓ(ei1 + ei2 ) ∈ ((M + ℓ)PG ∩ ZN ) \ {α1 + · · · + αM +ℓ : αi ∈ PG ∩ ZN }.
Fix a positive integer n with n < M. For every integer m ≥ min{k : kn ≥ M}, one
has
e(C1 , C2 ) + (mn − M)(ei1 + ei2 ) ∈ m(nPG ) ∩ ZN .
Since n < M, this integer point cannot be written as a sum of m elements belonging
to nPG ∩ ZN . This says that nPG is never very ample. Therefore, µva (PG ) ≥ M, as
desired.

On µmidp (PG ) and µidp(PG ) of edge polytopes PG , these are not necessarily equal
to M, although we still have µidp (PG ) ≥ µmidp (PG ) ≥ M because of µva (PG ) = M.
Example 4.2. Let us consider the graph G on the vertex set {1, . . . , 25} with the
edge set
E(G) = {{3i + 1, 3i + 2}, {3i + 2, 3i + 3}, {3i + 1, 3i + 3}, {3i + 1, 25} : i = 0, . . . , 7}.
Then each of exceptional pairs of minimal odd cycles in this graph consists of two
cycles of length 3. Thus we have µva (PG ) = µHilb(PG ) = 3. Moreover, since
this graph contains four distinct exceptional pairs of minimal odd cycles, one has
14

µhole (PG ) = 12. In addition, we also see that 3PG has (IDP). Hence µmidp (PG ) = 3.
On the other hand, neither 4PG nor 5PG has (IDP). In fact,
(1, . . . , 1, 0) ∈ 3(4PG ) ∩ Z25 \ {α1 + α2 + α3 : αi ∈ 4PG ∩ Z25 } and
| {z }
24

(1, . . . , 1, 0, 0, 0, 0, 0) ∈ 2(5PG ) ∩ Z25 \ {α1 + α2 : αi ∈ 5PG ∩ Z25 }.
| {z }
20

Thus µidp (PG ) ≥ 6. In fact, one can show that µidp(PG ) = 6.
Let us consider the graph G′ on the vertex set {1, . . . , 30} with the edge set
E(G′ ) = E(G) ∪ {{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 µva (PG′ ) = µHilb(PG′ ) = 4. Moreover, one has µhole (PG′ ) = 13. In addition,
similar to the case of the above G, neither 4PG′ nor 5PG′ has (IDP). However, we
can check that kPG′ has (IDP) for k ≥ 6, implying µmidp (PG′ ) = µidp(PG′ ) = 6.
References
[1] M. Beck and S. Robins, “Computing the Continuous Discretely,” Undergraduate Texts in
Mathematics, Springer, 2007.
[2] W. Bruns and J. Gubeladze, “Polytopes, rings and K-theory,” Springer–Verlag, Heidelberg,
2009.
[3] W. Bruns and J. Gubeladze, Unimodular covers of multiples of polytopes, Doc. Math. 7 (2002),
463–480.
[4] W. Bruns, J. Gubeladze and N. V. Trung, Normal polytopes, triangulations, and Koszul
algebras, J. Reine Angew. Math. 485 (1997), 123–160.
[5] D. Cox, J. Little and H. Schenck, “Toric varieties,” American Mathematical Society, 2011.
[6] G. Ewald and U. Wessels, On the ampleness of invertible sheaves in complete projective toric
varieties, Results Math. 19 (1991), 275–278.
[7] P. Gordan, Ueber die Auflösung linearer Gleichungen mit reellen Coefficienten, Math. Ann. 6
(1873), 23–28.
[8] T. Hibi, “Algebraic Combinatorics on Convex Polytopes,” Carslaw Publications, Glebe NSW,
Australia, 1992.
[9] A. Higashitani, Non-normal very ample polytopes and their holes, arXiv:1208.3955v2.
[10] G. Kempf, F. Knudsen, D. Mumford and B. Saint–Donat, “Toroidal Embeddings I,” Lecture
Notes in Mathematics 339, Springer–Verlag, 1973.
[11] J. Liu, L. Trotter and G. Ziegler, On the height of the minimal Hilbert basis, Results Math.
23 (1993), 374–376.
[12] Mini-Workshop: Projective normality of smooth toric varieties, Abstracts from the miniworkshop held August 12–18, 2007. Organized by Christian Haase, Takayuki Hibi and Diane
MacLagan, Oberwolfach Rep. 4 (2007), 2283–2320.
[13] S. Ogata, Very ample but not normal lattice polytopes, to appear in Beiträge Algebra Geom..
[14] H. Ohsugi and T. Hibi, Normal Polytopes Arising from Finite Graphs, J. Algebra 207 (1998),
409–426.
[15] A. Schrijver, “Theory of Linear and Integer Programming,” John Wiley & Sons, 1986.
15

[16] J. van der Corput, Konstruktion der Minimalbasis für spezielle Diophantische Systeme von
linear-homogenen Gleichungen und Ungleichungen, Proc. Roy. Acad. Amsterdam 34 (1931),
515–523.
David A. Cox, Department of Mathematics, Amherst College, Amherst, MA
01002-5000, USA
E-mail address: dac@math.amherst.edu
Christian Haase, Mathematics, Goethe-Universität Frankfurt/Main, Germany
E-mail address: haase@math.uni-frankfurt.de
Takayuki Hibi, Department of Pure and Applied Mathematics, Graduate School
of Information Science and Technology,pe Osaka University, Toyonaka, Osaka
560-0043, Japan
E-mail address: hibi@math.sci.osaka-u.ac.jp
Akihiro Higashitani, Department of Pure and Applied Mathematics, Graduate
School of Information Science and Technology, Osaka University, Toyonaka, Osaka 560-0043, Japan
E-mail address: a-higashitani@cr.math.sci.osaka-u.ac.jp

16

