arXiv:1701.02471v3 [math.CO] 26 Nov 2017

EXISTENCE OF REGULAR UNIMODULAR TRIANGULATIONS
OF DILATED EMPTY SIMPLICES
TAKAYUKI HIBI, AKIHIRO HIGASHITANI AND KOUTAROU YOSHIDA

Abstract. Given integers k and m with k ≥ 2 and m ≥ 2, let P be an empty
simplex of dimension (2k − 1) whose δ-polynomial is of the form 1 + (m − 1)tk . In
the present paper, the necessary and sufficient condition for the k-th dilation kP
of P to have a regular unimodular triangulation will be presented.

1. Introduction
1.1. Integral convex polytopes and δ-polynomials. An integral convex polytope is a convex polytope whose vertices are integer points. For an integral convex
P
polytope P ⊂ Rd of dimension d, we consider the generating function n≥0 |nP ∩
Zd |tn , where nP = {nα | α ∈ P }. Then it is well-known that this becomes a rational
function of the form
X
δP (t)
|nP ∩ Zd |tn =
,
(1 − t)d+1
n≥0

where δP (t) is a polynomial in t of degree at most d with nonnegative integer coefficients. The polynomial δP (t) is called the δ-polynomial, also known as the (Ehrhart)
h∗ -polynomial of P . For more details on δ-polynomials of integral convex polytopes,
please refer to [2] or [7].
1.2. Empty simplices. An integral simplex P ⊂ Rd is called empty if P contains
no integer point except for its vertices. Note that P is an empty simplex if and
only if the linear term of δP (t) vanishes. Empty simplices are of particular interest
in the area of not only combinatorics on integral convex polytopes but also toric
geometry. Especially, the characterization problem of empty simplices is one of
the most important topics. Originally, the empty simplices of dimension 3 were
completely characterized by G. K. White ([14]). Note that the δ-polynomial of
every empty simplex of dimension 3 is of the form 1 + (m − 1)t2 for some positive
integer m. Recently, this characterization of empty simplices has been generalized
by Batyrev–Hofscheier [1]. More precisely, the following theorem has been proved.

2010 Mathematics Subject Classification: Primary 52B20; Secondary 52B11.
Keywords: regular unimodular triangulation, empty simplex, integer decomposition property,
toric ideal, Gröbner basis
The second author is partially supported by JSPS Grant-in-Aid for Young Scientists (B) ♯17K14177.
1

Theorem 1.1 (cf. [1, Theorem 2.5]). Given an integer k ≥ 2, let d = 2k − 1.
Then P ⊂ Rd is an empty simplex of dimension d whose δ-polynomial is of the form
1 + (m − 1)tk for some m ≥ 2 if and only if there are integers a1 , . . . , ak−1 with
1 ≤ ai ≤ m/2 and (ai , m) = 1 for each 1 ≤ i ≤ k − 1 such that P is unimodularly
equivalent to the convex hull of
(
)
k−1
d−1
X
X
(1)
0, e1 , . . . , ed−1 ,
ai ei +
(m − ad−j )ej + med .
i=1

j=k

Here (a, b) denotes the greatest common divisor of two positive integers a and b,
e1 , . . . , ed ∈ Rd are the unit coordinate vectors of Rd and 0 ∈ Rd is the origin.
Given integers a1 , . . . , ak−1 , m with 1 ≤ ai ≤ m/2 and (ai , m) = 1 for each i, let
P (a1 , . . . , ak−1 , m) denote the convex hull of (1).
1.3. The integer decomposition property and unimodular triangulations.
We say that an integral convex polytope P ⊂ Rd has the integer decomposition
property (IDP, for short) if for each integer n ≥ 1 and for each γ ∈ nP ∩ Zd , there
exist γ (1) , . . . , γ (n) belonging to P ∩ Zd such that γ = γ (1) + · · · + γ (n) .
Under the assumption that the affine lattice generated by P ∩ Zd is equal to the
whole lattice Zd , the following implications for integral convex polytopes hold:
a regular unimodular triangulation ⇒ a unimodular triangulation
⇒ a unimodular covering ⇒ IDP
(Please refer the reader to [13] for the notions of (regular) unimodular triangulation
or unimodular covering.) Note that for each implication, there exists an example of
an integral convex polytope not satisfying the converse (see [10], [6] and [3]).
1.4. Motivation and results. For any integral convex polytope P of dimension
d, we know by [4, Theorem 1.3.3] that nP always has IDP for every n ≥ d − 1.
Moreover, we also know by [4, Theorem 1.3.1] that there exists a constant n0 such
that nP has a unimodular covering for every n ≥ n0 . However, it is still open
whether there really exists a constant n0 such that nP has a (regular) unimodular
triangulation for every n ≥ n0 , while it is only known that there exists a constant c
such that cP has a unimodular triangulation ([9, Theorem 4.1 (p. 161)]).
On the other hand, it is proved in [8] and [12] that for any 3-dimensional integral
convex polytope P , nP has a unimodular triangulation for n = 4 ([8]) and every
n ≥ 6 ([12, Theorem 1.4]). For the proofs of those results, the discussions about
the existence of a (regular) unimodular triangulation of the dilated empty simplices
of dimension 3 are crucial, where for an empty simplex P , a dilated empty simplex
means a simplex nP for some positive integer n. Hence, for the further investigation
of higher-dimensional cases, the existence of a unimodular triangulation of dilated
empty simplices might be important. Since P (a1 , . . . , ak−1 , m) can be understood
as a generalization of empty simplices of dimension 3, it is quite reasonable to
2

study the existence of a unimodular triangulation of the dilated empty simplex.
Moreover, since kP (a1 , . . . , ak−1 , m) has IDP but k ′ P (a1 , . . . , ak−1 , m) does not for
any k ′ < k (see Proposition 2.1), it is natural to discuss the existence of a unimodular
triangulation of kP (a1 , . . . , ak−1 , m).
The purpose of the present paper is to show the following:
Theorem 1.2 (Main Theorem). Given an integer k ≥ 2, let d = 2k − 1 and let
P ⊂ Rd be an empty simplex whose δ-polynomial is of the form 1 + (m − 1)tk for
some m ≥ 2. Then kP has a regular unimodular triangulation if and only if P is
unimodularly equivalent to the convex hull of
(
)
k−1
d−1
X
X
0, e1 , . . . , ed−1 ,
ei + (m − 1)
ej + med .
i=1

j=k

Remark 1.3. This theorem can be regarded as a generalization of (a part of) [12,
Corollary 3.5].

Theorem 1.2 says that P is an empty simplex with δP (t) = 1 + (m − 1)tk for some
m ≥ 2 whose k-th dilation has a regular unimodular triangulation if and only if P
is unimodularly equivalent to P (1, . . . , 1, m). The proof of the necessity of Theorem
1.2 is given in Section 3 (Proposition 3.1) and the sufficiency is given in Section 4
(Proposition 4.1), respectively.
Furthermore, by Proposition 2.1 together with Theorem 1.2, we obtain
Corollary 1.4. For any integer k ≥ 2, there exists an empty simplex P of dimension
(2k − 1) such that kP has IDP but has no regular unimodular triangulation.
2. Integer decomposition property of P (a1 , . . . , ak−1, m)
Before proving the main theorem (Theorem 1.2), we prove the following:
Proposition 2.1. Let P = P (a1 , . . . , ak−1 , m), where a1 , . . . , ak−1 , m are integers
with 1 ≤ ai ≤ m/2 and (ai , m) = 1 for each i. Then nP has IDP for a positive
integer n if and only if n ≥ k.
Pk−1
P
Proof. Let v0 = 0, vj = ej for 1 ≤ j ≤ d − 1 and vd = i=1
ai ei + d−1
j=k (m −
ad−j )ej + med . We define wi by setting

!
i(m − a1 ) + ia1
i(m − ak−1 ) + iak−1 iak−1 + i(m − ak−1 )
ia1 + i(m − a1 )
,...,
,
,...,
,i
m
m
m
m

for each 1 ≤ i ≤ m − 1, where ℓ denotes the remainder of ℓ divided by m. Then we
can see that
k−1
d−1
X
X
i
i(m − ap )
iad−q
m−i
v0 +
vp +
vq + vd
wi =
m
m
m
m
p=1
q=k
3

and

k−1
X
j=1

i(m − aj ) iaj
+
m
m

!

+

m−i
i
+
= k, which says that wi ∈ kP ∩ Zd for
m
m

each i.
Now, we see that
d
d
· · + P ∩ Z}d +{wi }1≤i≤m−1 )
(2) nP ∩ Zd = (P
· · + P ∩ Z}d ) ⊔ (P
| ∩ Z + ·{z
| ∩ Z + ·{z
n

n−k

P
for every n ≥ k. In fact, for any α ∈ nP ∩ Zd , we can write α = di=0 ri vi , where
P
P
P
ri ≥ 0 for each i and di=0 ri = n. Let β = di=0 ⌊ri ⌋vi and β ′ = di=0 (ri − ⌊ri ⌋)vi .
Note that 0 ≤ ri − ⌊ri ⌋ < 1. When β ′ = 0, one has α = β ∈ |P ∩ Zd + ·{z
· · + P ∩ Z}d .
n

Assume β ′ 6= 0. Now, it is well-known that the δ-polynomial of an integral simplex
can be computed as follows: for an integral simplex P ⊂ Rd of dimension d with its δP
P
P
polynomial di=0 δi ti , we have δj = |{α ∈ Zd | α = di=0 si vi , 0 ≤ si < 1, di=0 si =
j}| for each 0 ≤ j ≤ d. (Consult, e.g., [7, Proposition 27.7].) In our case, since
δP (t) = 1 + (m − 1)tk , we see the equality
)
(
d
d
X
X
(3)
si vi , 0 ≤ si < 1,
si ∈ Z>0 = {w1 , . . . , wm−1 }.
α ∈ Zd α =
i=0

i=0

′

Hence, we obtain β belongs to {w1 , . . . , wm−1 } and

d
α = β + β′ ∈ P
· · + P ∩ Z}d +{wi }1≤i≤m−1 .
| ∩ Z + ·{z
n−k

By (2), we can discuss as follows:

• When n ≥ k, let γ ∈ ℓ(nP ) ∩ Zd for ℓ ≥ 1. Since ℓn ≥ n ≥ k, it follows
from (2) that there exist γ (1) , . . . , γ (ℓ) belonging to nP ∩ Zd such that γ =
γ (1) + · · · + γ (ℓ) . This means that nP has IDP.
• When n < k, let ℓ′ be a minimum positive integer with ℓ′ n ≥ k. Then
wi + (ℓ′ n − k)v0 ∈ ℓ′ nP ∩ Zd for each i, while wi + (ℓ′ n − k)v0 cannot be
written as a sum of ℓ′ elements in nP ∩ Zd because we have wi 6∈ (k ′ P ∩
Zd ) + ((k − k ′ )P ∩ Zd ) for any 1 ≤ k ′ ≤ k − 1, which follows from (3), and
wi ∈ kP ∩ Zd . This means that nP does not have IDP.
Therefore, we conclude that nP has IDP if and only if n ≥ k.



From (2), we obtain the following which we will use later:
d
kP ∩ Zd = (P
· · + P ∩ Z}d ) ⊔ {wi }1≤i≤m−1 .
| ∩ Z + ·{z
k

Moreover, from this equation we can also see that the affine lattice generated by
kP ∩ Zd becomes Zd . In fact, since 0 = kv0 ∈ kP ∩ Zd , ei = (k − 1)v0 + vi ∈ kP ∩ Zd
P
for each 1 ≤ i ≤ d − 1 and w1 = di=1 ei ∈ kP ∩ Zd , we observe that the lattice
points e1 , . . . , ed−1 , w1 generate Zd .
4

Remark 2.2. In [5], several invariants concerning the dilation of integral convex
polytopes are studied. For the case P = P (a1 , . . . , ak−1 , m), we can show that
µva (P ) = µEhr (P ) = k. Hence, by [5, Theorem 1.1], we obtain that all invariants
defined there are equal to k.
3. Proof of Theorem 1.2 : the necessity
This section is devoted to giving a proof of the necessity of Theorem 1.2. We
prove the following:
Proposition 3.1. Given an integer k ≥ 2, let d = 2k − 1, let m ≥ 2 be an integer
and let ai , bi be positive integers with ai + bi = m and (ai , m) = 1 for each 1 ≤ i ≤ k.
Let
)!
(
d−1
k−1
X
X
bd−j ej + med
⊂ Rd .
P = conv
0, e1 , . . . , ed−1 ,
ai ei +
i=1

j=k

Assume that there is j such that 2 ≤ aj ≤ m − 2. Then kP does not have a regular
unimodular triangulation.

Similar to the previous section, let v0 = 0, vj = ej for 1 ≤ j ≤ d − 1, vd =
Pd−1
Pk−1
j=k bd−j ej + med and let
i=1 ai ei +
!
ib1 + ia1
ibk−1 + iak−1 iak−1 + ibk−1
ia1 + ib1
wi =
,...,
,
,...,
, i ∈ Rd
m
m
m
m
d
for each 1 ≤ i ≤ m − 1. Let A = P
· · + P ∩ Z}d . Then
| ∩ Z + ·{z
k

kP ∩ Zd = A ⊔ {wi }1≤i≤k .

For the proof of Proposition 3.1, we prepare three lemmas (Lemma 3.2, Lemma 3.3
and Lemma 3.4). In the proofs of those lemmas, we will use the following notation.
For x ∈ Rd , let pj (x) denote the j-th coordinate of x. Remark that for 1 ≤ i ≤ m−1
and 1 ≤ j ≤ k − 1, we have pj (wi ) + p2k−1−j (wi ) = i + 1
Lemma 3.2. For any 2 ≤ i ≤ m−2, there exist v, v ′ ∈ A which satisfy the equalities
wi−1 + wi+1 − 2wi = v − v ′ and wm−(i−1) + wm−(i+1) − 2wm−i = v ′ − v.
Proof. For simplicity, we denote w ∗ = wi−1 + wi+1 − 2wi .
assertion is obvious, so we suppose w ∗ 6= 0.
It follows from an easy calculation that

(i − 1)bj + (i + 1)bj − 2ibj



,


m
∗
pj (w ) = (i − 1)a2k−j−1 + (i + 1)a2k−j−1 − 2ia2k−j−1

,


m


0,
5

If w ∗ = 0, then the

if 1 ≤ j ≤ k − 1,
if k ≤ j ≤ 2k − 2,
if j = 2k − 1.

Hence we can see that −1 ≤ pj (w ∗ ) ≤ 1 and pj (w ∗ ) + p2k−1−j (w ∗) = 0 for 1 ≤ j ≤
2k − 2. Without loss of generality, we may assume p1 (w ∗ ) = 1 by w ∗ 6= 0. We define
v, v ′ ∈ Rd as follows:



2, if j = 1,
pj (v) = 1, if j ≥ 2 and pj (w ∗ ) = 1,


0, if j ≥ 2 and p (w ∗ ) = −1, 0,
j

and




1,
′
pj (v ) = 1,


0,

if j = 1,
if j ≥ 2 and pj (w ∗) = −1,
if j ≥ 2 and pj (w ∗) = 1, 0.

Then we can verify that wi−1 + wi+1 − 2wi = v − v ′ . Since pj (w ∗ ) + p2k−1−j (w ∗) = 0
2k−1
2k−1
P
P
for 1 ≤ j ≤ 2k − 2, one has
pj (v),
pj (v ′ ) ≤ k. Moreover, p2k−1 (v) =
j=1

j=1

p2k−1 (v ′ ) = 0. Thus we know that v and v ′ are contained in A. Since we see that
(m − i)bj + ibj = (m − i)aj + iaj = m for 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ k − 1, we
obtain pj (wi−1 + wi+1 − 2wi ) = −pj (wm−(i−1) + wm−(i+1) − 2wm−i ). Hence we have

that wm−(i−1) + wm−(i+1) − 2wm−i = v ′ − v.
Lemma 3.3. Let 2 ≤ a ≤ m − 2 be an integer and suppose aa′ = 1, where 2 ≤ a′ ≤
m − 2. Then there exist u, u′ ∈ A which satisfy w(a−1)a′ + w(a+1)a′ − 2w1 = u − u′
and w((m−1)a−1)a′ + w((m−1)a+1)a′ − 2wm−1 = u′ − u.
Proof. Let w ∗∗ = w(a−1)a′ + w(a+1)a′ − 2w1 . At first, we show that


if 1 ≤ j ≤ k − 1,

aj − 1 or aj or aj + 1,
∗∗
pj (w ) = b2k−1−j − 1 or b2k−1−j or b2k−1−j + 1, if k ≤ j ≤ 2k − 2,


m,
if j = 2k − 1.

We see that p2k−1 (w ∗∗ ) = (a − 1)a′ + (a + 1)a′ − 2 = 1 − a′ + 1 + a′ − 2 = m + 1 −
a′ +1+a′ −2 = m. Since pi (w ∗∗ )+p2k−1−i (w ∗∗ ) = (a − 1)a′ +1+(a + 1)a′ +1−4 = m,
we consider pi (w ∗∗ ) only for 1 ≤ i ≤ k − 1. For 1 ≤ i ≤ k − 1,

(a − 1)a′ bi + (a − 1)a′ ai + (a + 1)a′ bi + (a + 1)a′ ai
−2
m
bi − a′ bi + bi + a′ bi + (m + 2)ai
=
− 2.
m
Since bi − a′ bi + bi + a′ bi = 2bi + m or 2bi or 2bi − m, one sees that pi (w ∗∗ ) = ai + 1
or ai or ai − 1. Note that for i with ai = a, we see that pi (w ∗∗ ) = ai .
When w ∗∗ = vd , we may set u = vd and u′ = 0. Hence, without loss of generality,
we assume p1 (w ∗∗ ) = a1 + 1. In addition, since 2 ≤ ai = a ≤ m − 2 for some i, we
pi (w ∗∗ ) =

6

may also assume i = 2, i.e., a2 = a. Then we have p2 (w ∗∗ ) = a2 = a. We define
u, u′ ∈ Rd as follows:


2, if j = 1,






0, if j = 2,
′′
pj (u ) = 1, if 3 ≤ j ≤ 2k − 2 and pj (w ∗∗ − vd ) = 1,




0, if 3 ≤ j ≤ 2k − 2 and pj (w ∗∗ − vd ) = −1 or 0,



0, if j = 2k − 1,

and

′

pj (u ) =



1,






0,
1,




0,



0,

if j = 1,
if j = 2,
if 3 ≤ j ≤ 2k − 2 and pj (w ∗∗ − vd ) = −1,
if 3 ≤ j ≤ 2k − 2 and pj (w ∗∗ − vd ) = 1 or 0,
if j = 2k − 1

and take u = vd + u′′ . From the above discussion and the equalities (a − 1)a′ +
((m − 1)a + 1)a′ = (a + 1)a′ + ((m − 1)a − 1)a′ = m, we see that u and u′ are the
desired ones by the similar discussion in the proof of Lemma 3.2.

Lemma 3.4. For v, v ′ ∈ A given in Lemma 3.2 and u, u′ ∈ A given in Lemma 3.3,
we consider h1 , h2 ∈ A.
• If v + wi = h1 + h2 for some i, then v = h1 or v = h2 .
• If v ′ + wi = h1 + h2 for some i, then v ′ = h1 or v ′ = h2 .
• If u + w1 = h1 + h2 , then u = h1 or u = h2 .
• If u′ + wm−1 = h1 + h2 , then u′ = h1 or u′ = h2 .
Proof. We prove the first statement. The other statements are proved in the similar
way. We assume that there exist h1 and h2 in A satisfying v + wi = h1 + h2 for
some i and v 6= h1 and v 6= h2 . Since p2k−1 (v + wi ) = p2k−1 (h1 + h2 ) = i and
2 ≤ i ≤ m − 2, we have h1 = wi1 and h2 = wi2 , where 1 ≤ i1 ≤ i2 ≤ m − 1.
Therefore, p1 (h1 + h2 ) + p2k−2 (h1 + h2 ) = p1 (h1 ) + p2k−2 (h1 ) + p1 (h2 ) + p2k−2 (h2 ) =
p2k−1 (h1 )+1+p2k−1(h2 )+1 = p2k−1 (h1 +h2 )+2 = i+2, but p1 (v+wi )+p2k−2(v+wi ) =
p1 (v) + p1 (wi ) + p2k−2 (v) + p2k−2 (wi ) = i + 3, a contradiction.

±
Let K be a field. Let K[t±
1 , . . . , td , s] denote the Laurent polynomial ring with
(d + 1) variables. For an integral simplex P ⊂ Rd in Proposition 3.1, if α =
(α1 , . . . , αd ) ∈ kP ∩ Zd , then we write uα for the Laurent monomial tα1 1 · · · tαd d ∈
±
K[t±
1 , . . . , td , s]. The Ehrhart ring K[kP ] of kP is the subring of K[t1 , . . . , td , s]
generated by those monomials uα s with α ∈ kP ∩ Zd . Note that this K[kP ] is
usually called the toric ring of kP , but the toric ring of an integral convex polytope
Q coincides with the Ehrhart ring of Q if and only if Q has IDP, so we can call K[kP ]

7

the Ehrhart ring. Let S = K[{xi1 ···ik }0≤i1 ≤···≤ik ≤d , {yj }1≤j≤m−1 ] be the polynomial

ring with ( d+k
+ m − 1) variables with deg(xi1 ···ik ) = deg(yj ) = 1. We define the
k
surjective ring homomorphism π : S → K[kP ] by setting π(xi1 ···ik ) = uvi1 +···+vik s
and π(yj ) = uwj s. Let I denote the kernel of π and we call I the toric ideal of kP . It
is known that kP has a regular unimodular triangulation if and only if there exists
a monomial order < on S such that the initial ideal in< (I) of I with respect to < is
squarefree (e.g., see [13, Corollary 8.9]). In what follows, we will prove there is no
such monomial order.
Proof of Proposition 3.1. It follows from Lemma 3.2 that there exist variables xJ and
xJ ′ of S such that both xJ yi−1 yi+1 −xJ ′ yi2 and xJ ′ ym−(i−1) ym−(i+1) −xJ ym−i 2 belong to
I or both yi−1 yi+1 −yi2 and ym−(i−1) ym−(i+1) −ym−i 2 belong to I for each 2 ≤ i ≤ m−2.
Moreover, it follows from Lemma 3.3 that there exist variables xL and xL′ of S such
that both xL y(a−1)a′ y(a+1)a′ −xL′ y12 and xL′ y((m−1)a−1)a′ y((m−1)a+1)a′ −xL ym−1 2 belong
to I.
On the contrary, suppose kP has a regular unimodular triangulation, namely there
exists a monomial order < such that in< (I) is squarefree. Then, for all six binomials
just appearing above, their initial monomials are the first monomials. In fact, for
the four cubic binomials above, if the second monomial of one of those binomials is
an initial monomial, since it is not squarefree but in< (I) is squarefree, the second
monomial is divisible by a quadratic monomial belonging to in< (I). Hence, there
exsits a binomial whose initial monomial is such quadratic monomial. However, this
contradicts to Lemma 3.4.
Thus, we conclude that, for any monomial order <, one has xJ ′ yi2 < xJ yi−1 yi+1
and xJ ym−i 2 < xJ ′ ym−(i−1) ym−(i+1) for any 2 ≤ i ≤ m − 2. Then yi2ym−i 2 <
yi−1 ym−(i−1) yi+1 ym−(i+1) holds. Thus, we have yi ym−i < yi−1ym−(i−1) or yi ym−i <
yi+1 ym−(i+1) . Similarly, we also have y1 ym−1 < y(a−1)a′ y((m−1)a+1)a′ or y1 ym−1 <
y(a+1)a′ y((m−1)a−1)a′ , and recall (a − 1)a′ + ((m − 1)a + 1)a′ = m and (a + 1)a′ +
((m − 1)a − 1)a′ = m. Thus, for any 1 ≤ i ≤ m − 1, there exists 1 ≤ j ≤ m − 1
such that yi ym−i < yj ym−j . This is a contradiction.


4. Proof of Theorem 1.2 : the sufficiency
This section is devoted to giving a proof of the sufficiency of Theorem 1.2. We
prove the following:
Proposition 4.1. Given an integer k ≥ 2, let d = 2k − 1. Let m ≥ 2 be an integer
and let
)!
(
k−1
d−1
X
X
ej + med
⊂ Rd .
P = conv
0, e1 , . . . , ed−1 ,
ei + (m − 1)
i=1

j=k

8

Then kP has a regular unimodular triangulation.
The strategy of our proof is to show the existence of a monomial order < such
that the toric ideal of kP has a squarefree initial ideal. In what follows, we work
with the same notation on the toric ideal of kP as those in Section 3.
Pk−1
ei + (m −
Proof of Proposition 4.1. Let v0 = 0, vi = ei for 1 ≤ i ≤ d − 1, vd = i=1
Pd
Pk−1
Pd−1
1) j=k ej + med and let wj = i=1 ei + ℓ j=k ej for 1 ≤ ℓ ≤ m − 1. Then we see
that
kP ∩ Zd = {vi1 + · · · + vik | 0 ≤ i1 ≤ · · · ≤ ik ≤ d} ⊔ {wj | 1 ≤ j ≤ m − 1} .
Let u0 = 01 · · · k − 1 and um = kk + 1 · · · d be the sequences of indices. Then
we let y0 = xu0 and ym = xum and we never use xu0 and xum . Namely, for each
variable xs = xi1 ···ik with 0 ≤ i1 ≤ · · · ≤ ik ≤ d appearing below, we implicitly
assume that s 6= u0 and s 6= um . Moreover, we recall the notion of sorting. For a
sequence ℓ1 , . . . , ℓp , let sort(ℓ1 · · · ℓp ) denote the permutation ℓi1 , . . . , ℓip of ℓ1 , . . . , ℓp
with ℓi1 ≤ · · · ≤ ℓip . We say that a monomial xs1 · · · xsℓ is sorted if sort(s1 s2 . . . sℓ ) =
s1,1 s2,1 · · · sℓ,1 s1,2 · · · sℓ,2 · · · sℓ,k , where si = si,1 si,2 · · · si,k with 0 ≤ si,1 ≤ · · · ≤ si,k ≤
m for each 1 ≤ i ≤ ℓ.
First, we define (k + 2) sets G1,1 , G1,2 , G1,3 , G2 , . . . , Gk of binomials as follows:

G1,1 = xs1 xs2 − xs′1 xs′2 | sort(s1 s2 ) = sort(s′1 s′2 ) ,

G1,2 = xs1 xs2 − xs′1 yp | p ∈ {0, m}, sort(s1 s2 ) = sort(s′1 up ) ,
G1,3 = {xs1 xs2 − yp yq | p, q ∈ {0, m}, sort(s1 s2 ) = sort(up uq )},

where each xs is of the form xs1 ···sk for some 0 ≤ s1 ≤ · · · ≤ sk ≤ d and runs over
all possible s’s (but s 6∈ {u0 , um }),
G2 = {yp ys − yq yr | 0 ≤ p ≤ q ≤ r ≤ s ≤ m, p + s = q + r} , and
S
S

f0 , 1≤j≤n sej 6⊃ uf
1≤j≤n sej 6⊃ u
m



j6=i
j6=i



for every i = 1, · · · , n,
Gn =
xs1 xs2 · · · xsn − xt1 · · · xtn−1 yp p ∈ {0, m},



sort(t1 t2 · · · tn−1 up )



= s1,1 s2,1 · · · sn,1 s1,2 · · · sn,2 · · · sn,k















,

for 3 ≤ n ≤ k, where we denote e
s = {s1 , . . . , sk } for s = s1 · · · sk , and si =
si,1 si,2 · · · si,k .
S
Let G = G1,1 ∪ G1,2 ∪ G1,3 ∪ ki=2 Gi .
Q
Q
Q
Q
Next, we define the monomial order on S as follows: s xs t yt < s′ xs′ t′ yt′ ⇐⇒
Q
Q
(i) (the total degree of s xs ) < (the total degree of s′ xs′ ), or
Q
Q
Q
Q
(ii) (the total degree of s xs ) = (the total degree of s′ xs′ ) and s xs < s′ xs′
with respect to a sorting order (see [13, Section 14]), or
9

(iii)

Q

Q
Q
Q
xs = s′ xs′ and t yt < t′ yt′ with respect to the lexicographic order
induced by a ordering of variables ym < · · · < y0 .
s

We show that the initial monomial of each binomial in G is squarefree.

• On each binomial in G1,1 , G1,2 , G1,3 : by the property of a sorting order (the
definition (ii) of the monomial order <), we know in< (xs1 xs2 − xs′1 xs′2 ) is
squarefree. Regrading xs1 xs2 − xs′1 yp , its initial monomial should be the first
one by the definition (i) of <. If s1 = s2 , i.e., the initial monomial is of the
form x2s for some s = s1 · · · sk , then sort(s′1 up ) = s1 s1 · · · sk sk , so s′1 should
be also up , a contradiction. Similarly, the initial monomial of xs1 xs2 − yp yq
is also the first one and squarefree.
• On each binomial in G2 : by the definition (iii) of <, we easily see that the
initial monomial is the first one and squarefree.
• On each binomial in Gn : by the definition (i) of <, we see that the initial monomial is the first one. Moreover, by definition of each binomial in
S
Sn e′
S
f0 (resp.
f
f0 , (resp.
Gn , since nj=1 sej ⊃ u
1≤j≤n sej 6⊃ u
m ) but
j=1 sj ⊃ u
j6=i
S
e′
f
1≤j≤n sj 6⊃ u
m ), we also see that the first monomial is squarefree.
j6=i

Our goal is to prove that G forms a Gröbner basis of I with respect to the
monomial order < defined above. It is easy to see that G ⊂ I. It follows from [11]
that, in order to prove that G is a Gröbner basis of I, we may prove the following
assertion:
If u and v are monomials belonging to S with u 6= v
such that u ∈
/ in< (G) and v ∈
/ in< (G), then π(u) 6= π(v),

where in< (G) = (in< (g) | g ∈ G).
Let u, v ∈ S be monomials such that u ∈
/ in< (G) and v ∈
/ in< (G). Since each of u
and v is not divisible by the initial monomials in G, those must be of the forms
′

′

u = xs1 xs2 · · · xsℓ yic1 yi+1 c2 , v = xs′1 xs′2 · · · xs′ℓ′ yi′ c1 yi′ +1 c2 ,
where
• 0 ≤ i, i′ ≤ m − 1, c1 , c2 , c′1 , c′2 ≥ 0 (note that any monomial yi yi+ε with ε ≥ 2
can be divisible by the initial monomial in G2 );
• xs1 xs2 . . . xsℓ and xs′1 xs′2 . . . xs′ℓ′ are sorted (otherwise, it follows from the property of the sorting order that xs1 xs2 . . . xsℓ or xs′1 xs′2 . . . xs′ℓ′ is divisible by an
initial monomial of G1,1 ∪ G1,2 ∪ G1,3 );
S
Sℓ′ e′
S
S′
f
f0 and ℓj=1 sej 6⊃ uf
f0 , ℓj=1 se′j 6⊃ u
• ℓj=1 sej 6⊃ u
m (otherwise,
m,
j=1 sj 6⊃ u
′
′
′
we can see that xs1 xs2 · · · xsℓ and xs1 xs2 · · · xsℓ′ are divisible by the initial
monomial in G1,2 , G1,3 or Gn for some 3 ≤ n ≤ k).
Suppose π(u) = π(v). In what follows, we will show that u = v.
10

Let π(xsi ) = uαi s and π(xs′i ) = uαi ′ s. Since
c′

c′

π(xs1 xs2 · · · xsℓ )π(yic1 yi+1 c2 ) = π(xs′1 xs′2 · · · xs′ℓ′ )π(yi′1 yi′2+1 )
and π(yj ) = t1 · · · tk−1 tjk · · · tjd s for each j, we can write
(α1 + · · · + αℓ ) − (α1′ + · · · + αℓ′ ′ ) = (a, · · · , a, b, · · · , b) ∈ Zd ,
| {z } | {z }

(4)

k−1

k

where αj = vsj,1 + · · · + vsj,k and αj′ = vs′j,1 + · · · + vs′j,k for each j, a = c′1 + c′2 − c1 − c2
and b = c′1 i′ + c′2 (i′ + 1) − (c1 i + c2 (i + 1)).
For each k ≤ j ≤ d, let
ej =

ℓ
X

′

|{r | si,r = j, 1 ≤ r ≤ k}| −

i=1

ℓ
X

|{r | s′i,r = j, 1 ≤ r ≤ k}|.

i=1

Then the d-th coordinate of the left-hand side of (4) is equal to med by the form of
each of v0 , . . . , vd . Thus, b = med .
Assume that ed is non-negative. Then b ≥ 0. If there is d in {k, k + 1, . . . , d} \
Sn
ei , then we can see that the d-th coordinate of the left-hand side of (4) is noni=1 s
S
positive, so we have b = ed = 0. Otherwise, take j ∈ {k, k + 1, . . . , d} \ ℓi=1 sei with
S
S
j 6= d. Remark that {k, k + 1, . . . , d} \ ℓi=1 sei 6= ∅ since ℓi=1 sei 6⊃ uf
m . Then the
j-th coordinate of the left-hand side of (4) is equal to (m − 1)ed + ej , where ej is
S
non-positive by j 6∈ ℓi=1 sei . Thus b = med = (m − 1)ed + ej implies that b = ed = 0.
Similarly, even if ed is non-positive, by repacing the roles of si ’s and s′i ’s, we conclude
that b = ed = 0.
On the other hand, by comparing the degrees of u and v, we can see that ℓ + c1 +
c2 = ℓ′ + c1 ′ + c2 ′ . Moreover, since c1 ′ + c2 ′ − c1 − c2 = a, we obtain ℓ − ℓ′ = a.
Assume that a ≥ 0. (The case a ≤ 0 is similar.) By (4) and b = ed = 0, we see that
· · 1} · · · |k − 1 ·{z
· · k − 1}).
· · 0} |1 ·{z
sort(s1 · · · sℓ ) = sort(s′1 · · · s′ℓ′ 0| ·{z
a

Sℓ

a

a

f0 , we have a = 0. Therefore, we see that ℓ = ℓ′ . Since v1 , . . . , vd
From j=1 sej 6⊃ u
are linearly independent and both s1 s2 . . . sℓ and s′1 s′2 . . . s′ℓ′ are sorted, we conclude
that xs1 xs2 · · · xsℓ = xs′1 xs′2 · · · xs′ℓ′ .
′
′
Our remaining task is to check that yic1 yi+1 c2 = yi′ c1 yi′+1 c2 . From a = b = 0, we
know that c′1 + c′2 = c1 + c2 and c′1 i′ + c′2 (i′ + 1) = c1 i + c2 (i + 1). Without loss of
generality, we may assume i′ ≥ i. By deleting c′1 , we obtain (c1 + c2)(i′ − i) = c2 − c′2 .
• When i′ = i, since c2 − c′2 = 0, we obtain that c2 = c′2 , and thus c1 = c′1 .
c′ c′
c2
Hence, yic1 yi+1
= yi′1 yi′2+1 .
• When i′ = i + 1, we have c1 + c2 = c2 − c′2 . Hence, we see that c1 = −c′2 , i.e.,
c′ c′
c2
c2
c1 = c′2 = 0. Thus, c′1 = c2 . Therefore, we obtain yic1 yi+1
= yi′1 yi′2+1 = yi+1
.
′
′
′
• Assume i −i ≥ 2. Then we have 2(c1 +c2 ) ≤ c2 −c2 , i.e., 2c1 +c2 +c2 ≤ 0, i.e.,
c′ c′
c2
c1 = c2 = c′2 = 0 and c′1 = 0. Hence, we obtain that yic1 yi+1
= yi′1 yi′2+1 = 1.
11

Consequently, we conclude that yic1 yi+1 c2 = yi′ c1 yi′ +1 c2 , as required.
′

′



References
[1] V. Batyrev and J. Hofscheier, A generalization of a theorem of G. K. White, arXiv:1004.3411.
[2] M. Beck and S. Robins, “Computing the Continuous Discretely”, Undergraduate Texts in
Mathematics, Springer, 2007.
[3] W. Bruns and J. Gubeladze, Normality and covering properties of affine semigroups. J. Reine
Angew. Math. 510 (1999), 151–178.
[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. A. Cox, C. Haase, T. Hibi and A. Higashitani, Integer decomposition property of dilated
polytopes, Electron. J. Combin., 21 (2014), 1–17.
[6] R. T. Firla and G. M. Ziegler, Hilbert Bases, Unimodular Triangulations, and Binary Covers
of Rational Polyhedral Cones, Discrete Comput. Geom. 21 (1999), 205–216.
[7] T. Hibi, “Algebraic Combinatorics on Convex Polytopes”, Carslaw Publications, Glebe NSW,
Australia, 1992.
[8] J.-M. Kantor and K. S. Sarkaria, On primitive subdivisions of an elementary tetrahedron,
Pacific J. Math. 211 (2003), 123–155,
[9] G. Kempf, F. Knudsen, D. Mumford and B. Saint-Donat, Toroidal Embeddings I. Lecture
Notes in Math. 339, Springer, 1973.
[10] H. Ohsugi and T. Hibi, A normal (0, 1)-polytope none of whose regular triangulations is
unimodular, Discrete Comput. Geom. 21 (1999), 201–204.
[11] H. Ohsugi and T. Hibi, Quadratic initial ideals of root systems, Proc. Amer. Math. Soc. 130
(2002), 1913–1922.
[12] F. Santos and G. M. Ziegler, Unimodular triangulations of dilated 3-polytopes, Trans. Moscow
Math. Soc. 2013 (2014), 293–311.
[13] B. Sturmfels, “Gröbner Bases and Convex Polytopes”, volume 8 of University Lecture Series,
American Mathematical Society, Providence, RI, 1995.
[14] G. K. White, Lattice tetrahedra, Canad. J. Math. 16 (1964), 389–396.
Takayuki Hibi, Department of Pure and Applied Mathematics, Graduate School
of Information Science and Technology, Osaka University, Suita, Osaka 565-0871,
Japan
E-mail address: hibi@math.sci.osaka-u.ac.jp
Akihiro Higashitani, Department of Mathematics, Kyoto Sangyo University, Motoyama, Kamigamo, Kita-Ku, Kyoto, Japan, 603-8555
E-mail address: ahigashi@cc.kyoto-su.ac.jp
Koutarou Yoshida, Department of Pure and Applied Mathematics, Graduate
School of Information Science and Technology, Osaka University, Suita, Osaka
565-0871, Japan
E-mail address: yoshidakiiciva08@yahoo.co.jp

12

