MINIMAL GENERATING SETS OF LATTICE IDEALS

arXiv:1303.2303v4 [math.AC] 19 Jan 2017

HARA CHARALAMBOUS, APOSTOLOS THOMA, AND MARIUS VLADOIU
Abstract. Let L ⊂ Zn be a lattice and IL = hxu −xv : u−v ∈ Li be the corresponding
lattice ideal in k[x1 , . . . , xn ], where k is a field. In this paper we describe minimal binomial
generating sets of IL and their invariants. We use as a main tool a graph construction
on equivalence classes of fibers of IL . As one application of the theory developed we
characterize binomial complete intersection lattice ideals, a longstanding open problem
in the case of non-positive lattices.

1. Introduction
Let R = k[x1 , . . . , xn ] where k is a field, and let L be a lattice in Zn . The lattice ideal
IL is the ideal:
IL := hxu − xv : u − v ∈ Li .
Throughout this paper we call the set S a minimal generating set of IL if S consists of
binomials and is a minimal 1 system of generators of IL . If the minimal generating set
S of IL is of minimal cardinality, then we say that S is a cardinality-minimal generating
set and we write µ(IL ) for |S|. 2 Lattice ideals were first systematically studied in [13].
We note that toric ideals are lattice ideals IL for which the lattice L is the kernel of an
integer matrix. The study of lattice ideals is a rich subject on its own, see [24, 37] for the
general theory and [23] for recent developments. Moreover lattice ideals have applications
in various areas of mathematics, such as algebraic statistics [10, 29], integer programming
[12], hypergeometric differential equations [11], graph theory [28], etc.
There are two types of lattices in Zn , the positive ones and the non-positive ones. We
say that L is a positive lattice if L ∩ Nn = {0}. Otherwise, we say that L is a non-positive
lattice. Almost all results in the literature deal with positive lattices, with few exceptions
like in [5, 13, 15, 17, 21, 22, 27]. We survey below several well known facts for positive
lattices, as they pertain to our study. For the proofs we refer to [24] or [37] unless otherwise
noted. Let L be a positive lattice. We let {ei : 1 ≤ i ≤ n} be the canonical basis of Zn
and A be the subsemigroup of Zn /L generated by the elements {ai = ei + L : 1 ≤ i ≤ n}.
The semigroup A is partially ordered:
c ≥ d ⇐⇒ there is e ∈ A such that c = d + e .
For xv = xv11 · · · xvnn we set
degA (xv ) := v1 a1 + · · · + vn an ∈ A .
1991 Mathematics Subject Classification. 05E40, 13C40, 14M25, 60J10.
Key words and phrases. Binomial ideals, Markov basis, lattices.
1The notion of Markov basis was introduced in [10] to denote a generating binomial set of I , see [10,
L
Theorem 3.1]. Occasionally in the literature, especially in algebraic statistics, the minimal generating sets
are also referred to as minimal Markov bases.
2Even though for positive lattices the notions of minimal generating sets and cardinality-minimal generating sets coincide, this is not true for non-positive lattices.
1

It follows that IL is A-graded and that
IL = hxu − xv : degA (xu ) = degA (xv ) i .
For u ∈ Nn , the IL -fiber Fu is the set
Fu := {xv : xv − xu ∈ IL } = {xv : degA (xv ) = degA (xu )} .
Fu is a finite set for all u ∈ Nn . The homogeneous Nakayama Lemma applies and thus
all minimal generating sets of IL have the same cardinality and are cardinality-minimal
generating sets. Let S be a minimal generating set of IL and consider the multiset of
the fibers Fu , where xu is a monomial term of a binomial in S. By the results of [4] this
multiset is an invariant of IL . Lastly we note that the union3 of all minimal generating
sets of IL is a finite set, since all minimal generating sets are subsets of a finite set, the
Graver basis of IL , see [37].
How do these facts translate to non-positive lattices? Suppose that L is a non-positive
lattice and let A be (as before) the semigroup of Zn /L generated by the elements {ai =
ei + L : 1 ≤ i ≤ n}. The ideal IL is generated by the binomials xu − xv , with degA (xu ) =
degA (xv ) and the IL -fibers are defined in the same way as in the positive case. However,
the semigroup A is no longer partially ordered and the IL -fibers are no longer finite.
There are minimal generating sets which are not cardinality-minimal generating sets. In
the nonprincipal case, the multiset of the IL -fibers that correspond to a given cardinalityminimal generating set is not an invariant of IL and the union of all cardinality-minimal
generating sets of IL is an infinite set.
Consider, for example, the non-positive lattice L of Z2 generated by (1, 1), (5, 0). The
ideal IL is not principal and the sets {1 − xy, 1 − x5 }, {1 − xy, x3 − y 2 } are examples of
cardinality-minimal generating sets of IL . Thus µ(IL ) = 2. However {1−x2 y 2 , 1−x3 y 3 , 1−
x5 } is also a minimal generating set of IL and in fact IL has a minimal generating set4
of cardinality k, ∀k ≥ 2.5 The IL -fibers that contain 1 and x3 are distinct and thus
the multiset of the fibers for the above cardinality-minimal generating sets of IL are also
distinct, see Example 3.6(b) for a precise description of the IL -fibers.
The main purpose of this paper is to determine the invariants of the minimal generating
sets of IL , for any lattice L ⊂ Zn , and to show how to compute cardinality-minimal
generating sets of IL . To do so, we consider an equivalence relation among the IL -fibers
and order the equivalence classes. We appropriately choose the binomial generators that
correspond to the smallest possible equivalence class. Then we apply a graph construction
to the equivalence classes and determine trees on these graphs in order to identify the
binomials that could be part of a minimal generating set. In the process we identify the
invariants of the cardinality-minimal generating sets of IL . As an application of the theory
developed we characterize all binomial complete intersection lattice ideals, a longstanding
open problem. In more detail, the structure and the main results of this paper are as
follows.
In Section 2 we introduce and study the sublattice Lpure of L. This is the sublattice of
L generated by L ∩ Nn and in essence it measures the deviation of L from being positive.
3The union of all minimal generating sets of I is called the universal Markov basis of I , following [19,
L
L
Definition 3.1].
4Let p , . . . , p be s distinct primes and let a = (p · · · p )/p . Then h1−(xy)a1 , . . . , 1−(xy)as i = h1−xyi
1
s
i
1
s
i
and {1 − x5 , 1 − (xy)a1 , . . . , 1 − (xy)as } is a minimal generating set of IL of cardinality s + 1.
5There are cardinality-minimal generating sets that are not contained in the Graver basis of I , as is
L
the case for {1 − x2012 y 2017 , y 4 − x2013 y 2022 }. The union of the cardinality-minimal generating sets of IL
is an infinite set.
2

For example, the fibers of IL are finite if and only if Lpure is the zero lattice. The support
σ of Lpure is crucial to our study. Here σ is a subset of [n] = {1, . . . , n} and i ∈ σ if and
only if there is a u = (u1 , . . . , un ) ∈ Lpure so that ui 6= 0. In Corollary 2.14 we show that
a basis of Lpure can be chosen so that its elements are in Nn and have full support σ. This
will be needed in Section 4 when computing a basis of ILpure .
In Section 3 we define an equivalence relation among the IL -fibers. According to Definition 3.2, two IL -fibers F , G are equivalent if there exist u, v ∈ Nn such that xu F ⊂ G
and xv G ⊂ F . It is essential in our study that the cardinality of the equivalence classes of
the IL -fibers is a constant determined by σ, as Proposition 3.5 and Lemma 3.3 show. Next
we introduce a partial order “ ≤IL ” on the equivalence classes. This order is compatible
with the A-order in the case of a positive lattice L, and the set of equivalence classes has
a smallest element, namely the equivalence class of the fiber that contains 1. In Theorem 3.8 we show that any strictly descending chain of equivalence classes terminates, thus
allowing inductive arguments to work. Among all IL -fibers, we are primarily interested
in those whose equivalence classes correspond to elements participating in a cardinalityminimal generating set of IL . These are called Markov fibers, see Definition 3.9, and in
Corollary 3.14 we show that the set of these equivalence classes is an invariant of IL .
Section 4 is the core of this paper. Its main objective is the characterization of all
cardinality-minimal generating sets of IL . First we attack the case when L = Lpure : note
that in this case we know that IL is a binomial complete intersection, see [13, Theorem
2.1]. In the first main result of this section, Theorem 4.1, we describe all cardinalityminimal generating sets of IL . We remark that if L is not cyclic, then there are infinitely
many such bases. Next we make the transition to the general non-positive lattices by
taking a closer look to the equivalence classes not containing the fiber of 1. If F is such
an equivalence class, Definition 4.10 constructs a graph ΓF : the edges of ΓF determine
binomials that belong to minimal generating sets of IL . We reach the main result of this
section in Theorem 4.12 which describes all cardinality-minimal generating sets of IL , for
L an arbitrary lattice. We note that when L is positive, the description specializes to the
results of [4], see Remark 4.13 for more details. As a consequence of our main theorem we
can compute µ(IL ). This computation is the point of Theorem 4.14. Next we refine the
conclusion of Corollary 3.14 about the invariants of IL . Let S be a cardinality-minimal
generating set of IL . We show that the multiset, consisting of the equivalence classes of
the Markov fibers determined by S, is an invariant of all cardinality-minimal generating
sets of IL , see Corollary 4.15. This is the best result one can expect, as the example
of L = h(1, 1), (0, 5)i points out. Finally, in Corollary 4.16 we give an invariant of all
minimal generating sets of IL . They all determine the same multiset of equivalence classes
of fibers away from the fiber of 1. In the last part of Section 4 we discuss the indispensable
binomials and monomials of IL and show that in the general case of non-positive lattices,
the union of the cardinality-minimal generating sets of IL is an infinite set.
In Section 5 we determine the lattices L for which IL is a binomial complete intersection
ideal, see the beginning of the section for a short history pertaining to the case of positive
lattices. We note that this problem was completely solved for positive lattices, see [25,
Theorem 3.9]. We refer to [25] for a more comprehensive description of the problem. Even
though for positive lattices, the class of complete intersection ideals is the same as the
class of complete intersection binomial ideals, this is an open problem for non-positive
lattices. In Theorem 5.5 we show that IL is a binomial complete intersection ideal if and
only if ILσ is a complete intersection ideal, where Lσ is the lattice in the complement of σ.
In Corollary 5.6 we show that a necessary and sufficient condition for IL to be a binomial
3

complete intersection ideal, is either for L to be equal to Lpure or for a basis of Lσ to have
vectors giving the rows of a mixed dominating matrix. Thus Corollary 5.6 completely
characterizes binomial complete intersection lattice ideals for arbitrary lattices.
In Section 6 we work in detail an example: we use the techniques developed in this
paper, in order to compute all cardinality-minimal generating sets of a lattice ideal.
2. Fibers, the Pure Sublattice and Bases of a Lattice
Let L be a lattice in Zn , R = k[x1 , . . . , xn ] be the polynomial ring over a field k and
IL ⊆ R be the lattice ideal:
IL = hxu − xv : u, v ∈ Nn , u − v ∈ Li.
Definition 2.1. We let µ(IL ) be the minimal cardinality of a minimal generating set of
IL . In other words, µ(IL ) is the cardinal of a cardinality-minimal generating set of IL .
We denote by Tn the set of monomials of R including 1 = x0 and by N the set Z≥0 . If J
is a monomial ideal of R we denote by G(J) the unique minimal set of monomial generators
of J. For r ∈ N we let [r] = {1, . . . , r}. Let a = (a1 , . . . , an ), b = (b1 , . . . , bn ) ∈ Zn . We
write a ≥ 0 if a ∈ Nn . If either a ≥ 0 or −a ≥ 0 we say that a is pure. With this
terminology, a lattice L is non-positive if and only if it contains a nonzero pure vector,
otherwise it is positive. We write a ≥ b if ai ≥ bi for i = 1, . . . , n, and we say that a, b
are incomparable if a − b is not pure. In general we let supp(a) = {i : ai 6= 0} ⊂ [n]. For
any subset X of Zn we let
[
supp(X) :=
supp(w) .
w∈X

Tn

Definition 2.2. We say that F ⊂
is an IL -fiber if there exists xu ∈ Tn such that
v
n
u
F = {x ∈ T : v − u ∈ L}. If x ∈ F , and F is an IL -fiber we write Fu or Fxu
for F . If B ∈ IL and B = xu − xv we write FB for Fu . When F is an IL -fiber we let
MF = hxu : xu ∈ F i be the monomial ideal generated by the elements of F .
From the properties of the lattice and the definition of lattice ideals we get the following:
Proposition 2.3. If xv ∈ Fu then Fu = Fv . Moreover Fu = {xv : xv − xu ∈ IL }. If
xu − xv ∈ IL then u − v ∈ L.
We remark that Fu is a singleton if and only if there is no binomial 0 6= B ∈ IL such that
FB = Fu . We note that F ⊂ MF and G(MF ) ⊂ F . The following proposition follows also
from [24, Theorem 8.6].
Proposition 2.4. Let L ⊂ Zn be a lattice. The following are equivalent:
(1) The lattice L is non-positive.
(2) All IL -fibers are infinite.
(3) There exists an IL -fiber which is infinite.
Proof. (1) ⇒ (2) : Let F be an IL -fiber and suppose that 0 6= u ∈ L ∩ Nn . It is easy to see
that if v ∈ Nn and F is the IL -fiber such that xv ∈ F , then xv+lu ∈ F for all l ∈ N. Thus
F is infinite. Implication (2) ⇒ (3) is obvious. For (3) ⇒ (1) suppose that an IL -fiber F
is infinite. Let xv ∈ F be such that xv ∈
/ G(MF ). Note that since F is infinite such a v
exists. Since xv ∈ MF , there exists a monomial xu ∈ G(MF ) such that xu |xv and thus
xv = xw xu for 0 6= w ∈ Nn . Since xv , xu ∈ F it follows that w = v − u ∈ L. Therefore
0 6= w ∈ L ∩ Nn and consequently L is non-positive.

4

Corollary 2.5. Let L ⊂ Zn be a lattice. The lattice L is positive if and only if G(MF ) = F ,
where F is any IL -fiber.
Proof. Suppose that L ∩ Nn = {0}. Since MF = hF i to prove that G(MF ) = F , it is
enough to show that if xa 6= xb ∈ F then a and b are incomparable. Suppose otherwise.
Then a − b ∈ L is pure, a contradiction. For the other direction suppose that G(MF ) = F .
Thus F is finite and the conclusion follows from Proposition 2.4.

In the following definition we introduce the induced lattices that appear in our work
and the related notation.
Definition 2.6. We let L+ = L ∩ Nn , σ = supp(L+ ) and Lpure be the subgroup of L
generated by L+ . If u = (ui ) ∈ Zn and σ = [n], then we set u[n] = 0. Otherwise we let uσ
σ
σ
be the vector (ui )i∈σ
/ . We define L to be the lattice generated by the vectors u where
u ∈ L. Finally, if σ 6= ∅, we let uσ = (ui )i∈σ and (Lpure )σ to be the lattice generated by
the vectors uσ , u ∈ Lpure . If u = (ui ) ∈ Zn and σ = ∅, then we set u∅ = 0.
In the course of the proof of Proposition 2.4 we proved the following:
Proposition 2.7. Let L ⊂ Zn be a lattice and let F be an IL -fiber. If G(MF ) =
{xa1 , . . . , xas } then
s
[
{xai xw : w ∈ L+ } .
F =
i=1

The next proposition considers the support of the elements of L that belong to Lpure.
Proposition 2.8. There exists an element w in L+ such that supp(w) = σ. For u ∈ L
we have that supp(u) ⊂ σ if and only if u ∈ Lpure .
Proof. The existence of w follows from the observation that if w1 , w2 ∈ L+ then w1 +w2 ∈
L+ and supp(w1 ) ∪ supp(w2 ) = supp(w1 + w2 ).
Suppose now that u ∈ L and supp(u) ⊂ σ. Let w ∈ L+ be such that supp(w) = σ. It
is clear that for l ∈ N, l ≫ 0, u + lw = w′ ∈ Nn . Since u, lw ∈ L it follows that w′ ∈ L
and thus w′ ∈ L+ . Therefore u = w′ − lw ∈ Lpure.

The following is an immediate consequence of Proposition 2.8.
Corollary 2.9. Let L ⊂ Zn be a lattice and u ∈ L. Then u ∈ Lpure if and only if uσ = 0.
We note that since Lpure is generated by the elements of L+ it is clear that
supp(Lpure ) = σ .
Definition 2.10. A nonzero vector u ∈ L is called L–primitive if whenever λu ∈ L where
λ ∈ Q then λ ∈ Z. In other words, u is L–primitive if and only if Qu ∩ L = Zu.
Equivalently u is L–primitive if it is the “smallest” element of L in the direction determined
by u.
Proposition 2.11. Let 0 6= v ∈ L. There is an L–primitive vector u ∈ L such that
v = λu for λ ∈ Z.
Proof. Since v ∈ L \ {0} it follows that Qv ∩ L is a nonzero subgroup of L. Hence Qv ∩ L
is a free abelian group of rank 1, whose generator is the desired u.

Consider now any basis of L as a Z-module. The next theorem states that the elements
of such a basis are necessarily L–primitive.
5

Theorem 2.12. Let L ⊂ Zn be a lattice and let B be a basis of L as a Z-module. The
elements of B are L–primitive.
Proof. Since L is a sublattice of Zn , there exists an r ∈ N such that L ∼
= Zr , r = rank(L).
Let B = {u1 , . . . , ur }. Since B is a basis then it follows immediately that Qui ∩ L = Zui
for all i.

The next theorem shows that given an L–primitive vector, one can find a basis of L
that contains it.
Theorem 2.13. Let L be a lattice and u an L–primitive vector. There exists a basis B
of L such that u ∈ B.
Proof. Since L is a lattice then L/Zu is a finitely generated abelian group. If L/Zu is
not torsion-free then there exists a v ∈ L \ Zu such that λv ∈ Zu for some positive
integer λ > 1. This implies that Qu ∩ L ) Zu, a contradiction to the fact that u is Lprimitive. Thus L/Zu is torsion-free and consequently a free abelian group of rank equal
to rank(L) − 1. Now lifting the elements of any basis of L/Zu to elements of L and adding
u we obtain a basis of L.

As the next corollary shows, we can find bases of Lpure whose elements are in Nn having
full support σ.
Corollary 2.14. Let L be a non-positive lattice. There exists a basis of Lpure whose
elements are in L+ and have support equal to σ.
Proof. By Proposition 2.8 and Proposition 2.11 there is an L-primitive vector u1 ∈ L+
such that supp(u1 ) = σ. By Theorem 2.13 there exists a basis {u1 , . . . , ur } of Lpure. It is
clear that for l ≫ 0, u′i = ui + lu1 ∈ L+ for i = 2, . . . , r. The set {u1 , u′2 , . . . , u′r } has the
desired properties.

Bases of the lattice L are clearly important for the study of IL , even though they do not
directly give the elements of the minimal generating sets of IL . Indeed, it is well known
that the following holds:
+

−

−

+

IL = (xu1 − xu1 , . . . , xur − xur ) : (x1 · · · xn )∞ ,
where u1 , . . . , ur form a basis of L and ui + , ui − ∈ Nn are (for all i) the unique vectors of
disjoint support, such that ui = ui + − ui − , see [37, Lemma 12.2].
In the next two sections we describe all minimal generating sets of lattice ideals using
properties of the IL -fibers and of the bases of Lpure .
3. Fibers and minimal generating sets of Lattice Ideals
Let L ⊂ Zn be a lattice and R = k[x1 , . . . , xn ], where k is a field. If G ⊂ Tn and v ∈ Nn
we let xv G := {xv xu : xu ∈ G}.
Lemma 3.1. Let G, F be IL -fibers. If there exists w1 ∈ Nn , xu ∈ G such that xw1 xu ∈ F
then xw1 G ⊂ F . Moreover if xw2 F ⊂ G for w2 ∈ Nn then w1 + w2 ∈ L+ and supp(wi ) ⊂
σ, i = 1, 2.
′

Proof. Suppose that xw1 xu = xv ∈ F and let xu ∈ G. Since u′ − u ∈ L it follows that
′
(w1 + u′ ) − v ∈ L and thus xw1 +u ∈ F .
If in addition xw2 F ⊂ G it follows that xw1 +w2 F ⊂ F . Since xw1 +w2 xv , xv ∈ F it
follows that w1 + w2 ∈ L ∩ Nn .

6

Definition 3.2. Let F , G be IL -fibers. We say that F ≡IL G if there exist u, v ∈ Nn
such that xu F ⊂ G and xv G ⊂ F .
It is immediate that F ≡IL G is an equivalence relation among the IL -fibers. We denote
the equivalence class of F by F . Thus
F = {G : G is an IL -fiber, G ≡IL F } .
We note that F ≡IL G implies that the cardinality of F is equal to the cardinality of G.
Lemma 3.3. If L is positive and F is an IL -fiber then F = {F }.
Proof. By Proposition 2.4, |F | < ∞. Let G be an IL -fiber, G ≡IL F . There are u, v ∈ Nn
such that xu F ⊂ G and xv G ⊂ F . Since |F | = |xu F | = |G| = |xv G| it follows that
xv xu F = F and xv = xu = 1.

Next we want to investigate the number of equivalent fibers inside each equivalence
class when Lpure 6= {0} and σ 6= ∅. First we note the following:
Lemma 3.4. Let σ 6= ∅, F an IL -fiber and u ∈ Nn such that supp(u) ⊂ σ. If G is an
IL -fiber with the property xu F ⊂ G then G ∈ F .
Proof. Let w ∈ L+ be such that supp(w) = σ. There exists l ≫ 0 such that lw − u ∈ Nn .
Since lw ∈ L it follows that xlw F ⊂ F . Let xv ∈ G such that xv = xu xp for xp ∈ F . It
follows that xlw−u xv = xlw xp ∈ F and thus xlw−u G ⊂ F by Lemma 3.1.

We recall that if u ∈ Zn , then uσ = (ui )i∈σ . Thus, if s = |σ|, then we can assume that
uσ ⊂ Zs and that (Lpure )σ is a sublattice of Zs .
Proposition 3.5. Let L be a non-positive lattice and F an IL -fiber. The cardinality of F
is equal to |Zs /(Lpure )σ |, where s = |σ|.
Proof. For every G ∈ F choose uG ∈ Nn such that xuG F ⊂ G. Let
φ : F → Zs /(Lpure )σ , φ(G) = (uG )σ + (Lpure )σ .
The definition of φ is independent of the choice of uG . Indeed suppose that u, v ∈ Nn are
such that xu F ⊂ G and xv F ⊂ G. This implies that u − v ∈ L. By Lemma 3.1 it follows
that uσ = vσ = 0 and by Proposition 2.8 we obtain u − v ∈ Lpure and uσ − vσ ∈ (Lpure )σ .
We will show that ϕ is a bijection: the only part needing proof is the surjectivity of
ϕ. Let u′ + (Lpure )σ be an element of Zs /(Lpure )σ . First we remark that we can assume
without loss of generality that u′ ∈ Ns . Indeed, let w ∈ L+ be such that | supp(wσ )| = s.
It is clear that for l ≫ 0, lwσ + u′ ∈ Ns and thus u′ + (Lpure )σ = (lw + u′ ) + (Lpure )σ .
Let u ∈ Nn be such that uσ = 0, uσ = u′ and let G be the IL -fiber such that xu F ⊂ G.
By Remark 3.4 it follows that G ∈ F , and thus φ(G) = u′ + (Lpure )σ .

Examples 3.6. (a) We consider the lattice ideal IL = h1 − xyi ⊂ k[x, y] where L =
h(1, 1)i ⊂ Z2 . There are infinitely many IL -fibers: for any c ∈ Z the set Fc = {xi y j :
i − j = c} is an IL -fiber. All IL -fibers are infinite and belong to the same equivalence
class: the cardinality of this equivalence class is |Z|. Indeed Lpure = L, and Z2 / L ∼
= Z.
(b) If we consider the lattice ideal IL = h1−xy, 1−x5 i ⊂ k[x, y], where L = h(1, 1), (5, 0)i ⊂
Z2 then there are exactly five infinite IL -fibers:
Fk = {xi y j : i − j ≡ k

mod 5},

0≤k≤4,

which are all equivalent. Hence we have only one equivalence class F0 = {F0 , . . . , F4 }
which has five equivalent fibers. Indeed Lpure = L and Z2 /L ∼
= Z5 .
7

We define the relation “≤IL ” among the equivalence classes of IL -fibers.
Definition 3.7. Let F , G be IL -fibers. We say that F ≤IL G if there exists u ∈ Nn such
that xu F ⊂ G.
It is immediate that “≤IL ” is well defined and is a partial order among the equivalence
classes of IL -fibers. For simplicity of notation we occasionally write F ≤IL G if F ≤IL G
and F <IL G if F ≤IL G and F 6= G. We note that F{1} ≤IL F for any IL -fiber F . We
also remark that if L is positive then <IL gives the ordering on the fibers of IL induced
by the Zn /L-degrees, see [4, Section 2].
Theorem 3.8. Any strictly descending chain of equivalence classes of IL -fibers is finite.
Proof. Assume that
F 1 >IL · · · >IL F k >IL F k+1 >IL · · ·
is a chain of equivalence classes of fibers with no least element. Choose a representative
Fi , i ∈ N for each class. Next consider the corresponding ascending chain of monomial
ideals:
MF1 ⊂ · · · ⊂ MF1 + · · · + MFk ⊂ MF1 + · · · + MFk+1 ⊂ · · ·
The chain stabilizes at some step, say s, so that
MF1 + · · · + MFs = MF1 + · · · + MFs+1 .
Let xa ∈ G(MFs+1 ). By the above equality it follows that xa ∈ MFi for some 1 ≤ i < s + 1
and xa = xu xb where xb ∈ G(MFi ). Since xu xb ∈ Fs+1 it follows that xu Fi ⊂ Fs+1 . This

leads to a contradiction since F s+1 <IL F i .
Definition 3.9. Let F be an IL -fiber. We say that F is a Markov fiber if there exists a
cardinality-minimal generating set S of IL such that F = F B for some B in S.
Next, we generalize the constructions of [4, Section 2] to arbitrary lattice ideals. Let F
be an IL -fiber. We let
IL,<F = hB ∈ IL : B binomial, FB <IL Fi
and
IL,≤F = hB ∈ IL : B binomial, FB ≤IL Fi.
We note that IL,<F = 0 if there is no IL -fiber G such that G <IL F . It is clear that the
definition of these ideals does not depend on the chosen fiber representative. Finally if S
is any subset of binomials of IL we let
SF = {B ∈ S : F B ≤IL F }.
Remark 3.10. We will pay extra attention to the fiber that contains 1, F{1} . Let S be a
set of binomials of IL . According to the definitions
SF {1} = {B ∈ S : FB ∈ F {1} } and ILpure = IL,≤F {1} .
We isolate the following proposition whose proof is within the proof of [17, Lemma A.1].
8

Proposition 3.11. Let S be a minimal generating set of IL , F an IL -fiber, xw1 , xw2 ∈ F .
There exists a subset T ⊂ SF such that
X
xw 1 − xw 2 =
±xai,B B,
i,B

where B ∈ T , ai,B ∈ Nn and ai,B 6= aj,B for i 6= j.
We note that in the summation, the binomials B ∈ T may appear more than once. The
emphasis of the above statement is that when summing up and factoring out the binomials
B ∈ T , we get an expression
X
xw 1 − xw 2 =
f i Bi

where Bi 6= Bj ∈ T , for i 6= j, and all nonzero coefficients of the monomial terms of the fi
are ±1. Next we describe the ideals IL,<F and IL,≤F in terms of the generators of IL .

Proposition 3.12. Let S be a generating system of binomials for IL . The following hold:
IL,<F = hB : B ∈ S, F B <IL F i
and
IL,≤F = hB : B ∈ S, F B ≤IL F i.
Proof. We will show the statement for IL,<F , the other one having a similar proof. Let
J = hB : B ∈ S, F B <IL F i. We will show that J = IL,<F . It is clear that J ⊂ IL,<F .
To show the other containment it is enough to show that if B = xu − xv ∈ IL,<F then
B ∈ J. Let B = xu − xv ∈ IL,<F . Since B ∈ IL , by Proposition 3.11 it follows that
Pt
ai,Bi
B =
Bi where Bi ∈ S are not necessarily distinct while ai,Bi 6= aj,Bj for
i=1 ±x
Bi = Bj and i 6= j. We will do induction on t. Without loss of generality we can assume
that B1 = xu1 − xv1 and xa1 xu1 = xu , the other cases being done similarly. First we show
the inductive step. Suppose that t = 1. Since xa1 xu1 = xu it follows that xa1 FB1 ⊂ FB .
Thus F B1 ≤IL F B . Since F B <IL F we see that F B1 <IL F . Assume now that t > 1 and
consider B ′ = B − xa1 B1 = xa1 xv1 − xv . Since FB ′ = FB , it follows that B ′ ∈ IL,<F and
we are done by induction.

We can now determine when the IL -fiber F is a Markov fiber, in terms of the subideals
of IL , defined earlier.
Theorem 3.13. Let F be an IL -fiber. F is a Markov fiber if and only if IL,<F 6= IL,≤F .
Proof. Let S be a cardinality-minimal generating set of IL . If IL,<F 6= I≤F then by
Proposition 3.12 there exists a B ∈ S such that FB ≡IL F . For the converse assume that

there exists B ∈ S such that F B = F . It follows immediately that IL,<F 6= IL,≤F .
Corollary 3.14. The set of equivalence classes of Markov fibers of a lattice ideal IL is an
invariant of IL .
In the following section, we will refine this result taking under account the number of
times an equivalence class of a Markov fiber appears in a cardinality-minimal generating
set of IL , see Theorem 4.16.
9

4. Generating sets of lattice ideals
4.1. Pure Lattices. First we consider the case of L ⊂ Zn being a pure lattice, i.e. when L
is generated by its pure elements and show how to obtain all cardinality-minimal generating
sets of IL . Let S = {B1 , . . . , Br } be a set of binomials of IL . We say that S ′ is a
rearrangement of S if there is a bijective function f : S → S ′ such that f (Bi ) = ±Bj .
Compositions of rearrangements are rearrangements. It is clear that if S is a generating
set of IL then all rearrangements of S are generating sets of IL . The theorem below
generalizes [38, Lemma 2.1].
Theorem 4.1. Let L = Lpure be a pure lattice of rank r, σ = supp(L) and S a set
of r binomials of IL . The set S generates IL if and only if there is a rearrangement
{xu1 − xv1 , xu2 − xv2 , . . . , xur − xvr } of S such that the following three conditions are
satisfied:
(1) {u1 − v1 , . . . , ur − vr } is a basis of L,
(2) for i ∈ [r], supp(ui ) ∪ supp(vi ) ⊂ σ,
S
(3) (a) xv1 = 1 and (b) supp(vi ) ⊂ i−1
j=1 supp(uj ) for 2 ≤ i ≤ r.

Proof. Suppose first that S = {B1 , . . . , Br } generates IL . We let Bj = xbj −xcj for j ∈ [r].
Let u ∈ L. According to Proposition 3.11 there is an index set A such that
X
+
−
xu − xu =
±xal (xbj − xcj ),
l∈A

Nn .

where il ∈ [r], al ∈
Expanding the RHS, equating the exponents of the equal monomial
terms, subtracting the expressions for u+ and u− and substituting al , l ∈ A, one gets that
u ∈ Z(b1 − c1 ) + · · · + Z(br − cr ). This shows that L = Z(b1 − c1 ) + · · · + Z(br − cr ). Since
rank(L) = r it follows that {b1 − c1 , . . . , br − cr } is a basis of L. Next we remark that
supp(bi ) ⊂ σ if and only if supp(ci ) ⊂ σ. Indeed this is immediate since supp(bi −ci ) ⊂ σ.
Now suppose that for some i ∈ [r], supp(bi ) 6⊂ σ. We claim that Bi = xbi −xci is redundant
−
+
in S as a generator of IL . For this we will show that if u ∈ L then xu − xu can be
written as a linear combination of the elements of S \ {Bi }. Indeed consider again the
relation
X
+
−
±xal (Bjl )
xu − xu =
l

of Proposition 3.11. Substitute the value 0 to any variable xj where j ∈
/ σ: the terms in
the above relation involving Bi disappear. Thus S \ {Bi } is a generating set of IL . This
is of course a contradiction by the generalized Krull’s Principal Ideal Theorem, since the
height of IL is r, see [13, Theorem 2.1]. To show that there is a rearrangement of S that
satisfies the conditions of the theorem we notice that S contains a binomial Bj with 1 as
one of its monomial terms. Indeed
let w ∈ L+ with supp(w) = σ, see Proposition 2.8.
P
w
w
a
Since x − 1 ∈ IL , x − 1 =
±x l (Bil ). It is clear that there exists a value of l such
that a monomial term of Bil is equal to 1 (and al = 0): otherwise xw − 1 ∈ hx1 , . . . , xn i,
a contradiction. It is immediate that we can rearrange S by a bijective function f1 so
that f1 (Bil ) = xu1 − 1. Next we claim that there is B = xb − xc ∈ S such that B 6= Bil
and supp(b) or supp(c) ⊂ supp(u1 ). Indeed, suppose not. Then clearly supp(u1 ) 6= σ.
Consider again the expression
X
X
xw − 1 =
x a t B il +
±xat (Bit ) .
t∈A,it 6=il

t∈A,it =il

10

Substitute the value 1 for all variables whose index is in supp(u1 ) and the value 0 for all
other variables. We obtain a contradiction: −1 = 0. To avoid the contradiction there
must be B ∈ S so that ±B = xu2 − xv2 and supp(v2 ) ⊂ supp(u1 ). We rearrange f1 (S)
by f2 which keeps all elements of f1 (S) fixed but B: f2 (B) = xu2 − xv2 . More generally
once fs has been defined for s < r so that the third condition is satisfied for all i ≤ s, the
same argument produces fs+1 with the desired property.
We now prove the converse. Consider a set S of binomials whose rearrangement {xu1 −
1, xu2 − xv2 , . . . , xur − xvr } satisfies the three conditions of the theorem. Let J = hxu1 −
1, . . . , xur −xvr i.SWe will show that J = IL . It is clear that J ⊂
S IL . Since u1 , . . . , ur −vr is
a basis of L and ri=1 (supp(ui )∪supp(vi )) ⊂ σ it is clear that ri=1 (supp(ui )∪supp(vi )) =
σ. By the third condition it follows that
r
[

supp(ui ) = σ .

i=1

Next we will show that for every k ∈ [r] there exists wk ∈ L+ such that xwk − 1 ∈ J
S
and supp(wk ) = kj=1 supp(uj ). For k = 1 we set w1 = u1 . Since supp(v2 ) ⊂ supp(u1 )
there exists λ1 ∈ N, λ1 ≫ 0 such that λ1 w1 > v2 . We set w2 = (λ1 w1 − v2 ) + u2 ;
supp(w2 ) = supp(u1 ) ∪ supp(u2 ). Moreover
xw2 − 1 = xλ1 w1 −v2 (xu2 − xv2 ) + xλ1 w1 − 1 ∈ J ,
as wanted. It is clear that this construction generalizes for all k ∈ [r]. In particular
supp(wr ) = σ.
We will now show that if u − v ∈ L then xu − xv ∈ J, which ends the proof. Since
J : (x1 · · · xn )∞ = IL there exists w ∈ Nn such that xw (xu − xv ) ∈ J. By the second
condition it is clear that w can be chosen so that supp(w) ⊂ σ. Since supp(wr ) = σ there
exists λ ∈ N, λ ≫ 0 such that λwr > w. Therefore xλwr (xu − xv ) ∈ J. It follows that
xu − xv = (xλwr − 1)(xv − xu ) − xλwr (xu − xv ) ∈ J
and consequently IL = J.



We remark that the binomials of a generating set of IL when L = Lpure might have a
common monomial factor according to Theorem 4.1. Note also that if E = {u1 , . . . , ur } is
+
−
+
a basis of L such that u1 ∈ L+ and supp(u1 ) = σ then the set {1−xu1 , xu2 −xu2 , . . . , xur −
−
xur } is a cardinality-minimal generating set of IL . On the other hand such a basis E for
L = Lpure exists by Corollary 2.14. This implies that if L = Lpure , the ideal IL is always
a complete intersection, which follows from [13, Theorem 2.1]. In section 5 we determine
when IL is a binomial complete intersection ideal for arbitrary lattices. In the next example
we show that all conditions of Theorem 4.1 are necessary.
Example 4.2. Let L ⊂ Z3 be the lattice generated by (1, 1, 0), (0, 5, 0). It is not hard
to see that IL = h1 − x1 x2 , 1 − x51 i ⊂ k[x1 , x2 , x3 ]. Consider also the following sets:
E23 = {x51 − 1, x52 − 1}, E13 = {x1 x2 − 1, x52 x3 − x3 }, E12a = {x51 − 1, x22 x1 − x2 } and
E12b = {x21 x22 − x1 x2 , x51 x2 − x2 }. One can show via Gröbner bases computation that these
sets do not generate IL . We note that each of these sets satisfies all except one of the
conditions of Theorem 4.1, the missing index indicating which one.
11

4.2. Minimal generating sets of lattice ideals. Next we characterize the generating
sets of lattice ideals starting from the criterion given in [17, Introduction]. Let L ⊂ Zn be
−
+
a lattice and S a subset of IL consisting of binomials of the form xu − xu where u ∈ L.
Let F be an IL -fiber. The sequence (xa1 , xa2 , . . . , xak ) is an S-path from xu to xv if
• xa 1 = xu , xa k = xv
• for j = 1, . . . , k each xaj in the sequence belongs to the fiber F and
• xaj − xaj+1 is equal to xwj Bj or −xwj Bj for some Bj ∈ S, wj ∈ Nn .
Theorem 4.3 ([17]). The set S of binomials of IL is a generating set of IL if and only if
for every IL -fiber F there is an S-path between any two elements of F .
Let F be an IL -fiber and G(MF ) = {xa1 , . . . , xas }. We define a relation “∼” among the
elements of G(MF ) as follows:
\
(aj + L+ ) 6= ∅.
xai ∼ xaj iff (ai + L+ )
We note that if L+ = {0} then xai ∼ xaj only when xai = xaj .

Lemma 4.4. “∼” is an equivalence relation among the elements of G(MF ).
Proof. It is enough to show transitivity. We can assume that Lpure 6= {0}, the other case
being trivial. Suppose that
xai ∼ xaj and xaj ∼ xak .
Thus there exist ui , uj , vj , vk ∈ L+ such that
ai + ui = aj + uj and aj + vj = ak + vk .
Therefore
ai + (ui + vj ) = ak + (uj + vk ),
and the proof is complete.



For the following lemma, we recall that uσ stands for the vector (ui )i∈σ
/ .
Lemma 4.5. Let G(MF ) = {xa1 , . . . , xas }. The following holds for the elements of
G(MF ):
xai ∼ xaj if and only if aσi = aσj .
Proof. We can assume that L+ 6= {0}, the other case being trivial. Let w ∈ L+ such
that supp(w) = σ. Suppose that aσi = aσj . Since u = ai − aj ∈ L it follows that uσ = 0
and thus supp(u) ⊂ σ. Therefore there exists λ ≫ 0 such that u + λw ∈ Nn . Since
u + λw ∈ L+ and ai + λw = aj + (u + λw) it follows that xai ∼ xaj .
Suppose now that xai ∼ xaj . There exist ui , uj ∈ L+ such that ai + ui = aj + uj .
Therefore
aσi = (ai + ui )σ = (aj + uj )σ = aσj ,
and we are done.



Lemma 4.6. Let G(MF ) = {xa1 , . . . , xas }. The following holds for the elements of
G(MF ):
xai 6∼ xaj if and only if aσi , aσj are incomparable.
12

Proof. We will show that xai 6∼ xaj implies that aσi and aσj are incomparable. Suppose
otherwise. Without loss of generality we can assume that aσi −aσj > 0. Let u = ai −aj . Let
w ∈ L+ such that supp(w) = σ. We can find λ ∈ N large enough so that all coordinates
(u + λw)i > 0 for i ∈ σ. Since λwσ = 0 and uσ > 0 it follows that u + λw > 0 and
thus u + λw ∈ L+ . Since ai + λw = aj + (u + λw) and λw, u + λw ∈ L+ it follows that
xai ∼ xaj , a contradiction. The other implication follows immediately from the previous
lemma.

Lemmas 4.5 and 4.6 imply that there are only two possibilities for aσi , aσj , when xai , xaj
are minimal generators of MF : either aσi = aσj or aσi , aσj are incomparable. If X ⊂ Zn by
X σ we mean the set whose elements are the vectors uσ where u ∈ X. In particular
σ

G(MF )σ = {xu : xu ∈ G(MF )} .
Note that the cardinality of G(MF )σ might be less than the cardinality of G(MF ).
Lemma 4.7. If F, F ′ are two equivalent IL fibers, then G(MF )σ = G(MF ′ )σ .
Proof. Since F, F ′ are equivalent IL -fibers, there exist monomials xu , xv such that xu F ⊂
F ′ and xv F ′ ⊂ F . Therefore xu+v F ⊂ F and u + v ∈ L+ . Since u, v ∈ Nn it follows that
supp(u), supp(v) ⊂ σ. Let G(MF ) = {xa1 , . . . , xas }, G(MF ′ ) = {xb1 , . . . , xbr }. To show
the desired equality it suffices to show that for any i ∈ [s] there is j ∈ [r] so that aσi = bσj ,
the other inclusion being taken care by symmetry.
Since xai xu is in F ′ there exists j ∈ [r] such that xbj divides xai xu . Therefore ai + u −
bj ∈ Nn . Since supp(u) ⊂ σ it follows that
(ai + u − bj )σ = aσi − bσj ≥ 0
and aσi ≥ bσj . Similarly there exists k ∈ [s] such that bσj ≥ aσk . Therefore aσi ≥ bσj ≥ aσk

and aσi ≥ aσk . It follows that aσi = aσk and thus aσi = bσj .
Let F be any IL -fiber. We construct a graph GF and then we build on GF to construct
a graph ΓF , that will be crucial in determining when a set of binomials of IL generates
IL,≤F .
σ

σ

Definition 4.8. Let F be an IL -fiber, G(MF )σ = {xa1 , . . . , xak } where xai ∈ G(MF ) for
i ∈ [k]. We define GF = (V (G), E(G)) to be the graph with V (G) = [k], and
E(G) = {{i, j} : ∃ xui , xuj ∈ F such that uσi = aσi , uσj = aσj , xui − xuj ∈ IL,<F } .
The graph GF is independent of the fiber representative F , up to reordering of the
vertices. This is immediate for V (G), by Lemma 4.7. Next we show the independence
of E(G). Suppose that xui − xuj ∈ IL,<F where xui , xuj ∈ F and uσi = aσi , uσj = aσj .
Let F ′ ∈ F and let xu , xv be such that xu F ⊂ F ′ and xv F ′ ⊂ F . By Lemma 3.1,
supp(u) ∪ supp(v) ⊂ σ and thus uσ = vσ = 0. Moreover xu xui − xu xuj ∈ IL,<F ,
(u + ui )σ = uσ + uσi = uσi = aσi , (u + uj )σ = aσj and thus E(G) is independent on the
choice of the fiber representative F .
Example 4.9. Let L be the sublattice of Z5 , generated by v1 = (3, 0, 1, −1, 0), v2 =
(0, 1, 6, 0, −1), v3 = (1, 1, 0, 0, 0) and v4 = (5, 0, 0, 0, 0). It is easy to see that Lpure =
Zv3 + Zv4 and thus σ = {1, 2}. Since Fx5 = Fx64 , the IL -fiber F = Fx5 is a Markov fiber6.
A straightforward computation shows that
G(MF ) = {x5 , x41 x63 , x1 x53 x4 , x31 x43 x24 , x33 x34 , x21 x23 x44 , x41 x3 x54 , x1 x64 , x2 x63 , x42 x53 x4 , x22 x43 x24 ,
6This is proved in detail in the last section.
13

x32 x23 x44 , x2 x3 x54 , x42 x64 }.
Indeed, if one solves the system that results from the observation that xv11 · · · xv55 ∈ F if
and only if
(v1 , v2 , v3 , v4 , v5 − 1) = β1 v1 + · · · + β4 v4 = (3β1 + β3 + 5β4 , β2 + β3 , β1 + 6β2 , −β1 , −β2 ),
for some (β1 , . . . , β4 ) ∈ Z4 , then obtains the above displayed monomials. Therefore
k
G(MF )σ = {x5 , x63 , x53 x4 , x43 x24 , x33 x34 , x23 x44 , x3 x54 , x64 } = {x5 } ∪ {x6−k
3 x4 : k = 0, . . . , 6}.

Thus the graph GF consists of 8 vertices. One can show that the vertex that corresponds
σ
to x5 is isolated. If x5 was not isolated, there would be xu , xv ∈ F , such that xu = x5 ,
σ
6−k
xv = x3 xk4 and xu − xv ∈ I<F . But this means that there would be a w ∈ L+ , so that
xu = xw x5 . Thus, since x5 (xw − 1) ∈ I<F , we get that x5 − xv = (xu − xv ) − x5 (xw − 1) ∈
I<F . This leads to a contradiction, by Theorem 3.13, since Fx5 is a Markov fiber. It
is also relatively easy to show that any other two vertices of GF are connected by an
edge. Consider for example the vertices that correspond to the monomials x63 and x53 x4 .
They are connected via an edge since (x41 x63 )σ = x63 , (x1 x53 x4 )σ = x53 x4 , x41 x63 − x1 x53 x4 =
x1 x53 (x31 x3 − x4 ) and F x4 <IL F x5 , implying that x41 x63 − x1 x53 x4 ∈ I<F . Therefore GF
has two connected components: an isolated vertex corresponding to x5 and the complete
graph on the remaining seven vertices.
Definition 4.10. We let ΓF to be the complete graph whose vertices are the connected
components of GF . Let B = xu − xv ∈ IL such that FB ∈ F . We identify B with an
σ
σ
edge of ΓF if xu 6= xv , B ∈ IL,≤F and B 6∈ IL,<F . For a subset S of binomials of IL we
denote by ΓF (S) the subgraph of ΓF induced by the binomials B ∈ S such that FB ∈ F .
We note that different binomials might correspond to the same edge of ΓF .
Lemma 4.11. Let L ⊂ Zn be a lattice and S a subset of IL consisting of binomials such
that ILpure = hSF {1} i and ΓF (S) is a spanning tree of ΓF for every IL -fiber F . Then the
set S is a generating set of IL .
Proof. If L = Lpure then the conclusion is straightforward since GF {1} is an isolated vertex,
and so is ΓF {1} . Thus we may assume that the lattice L is non-pure or equivalently that
there exists a fiber F such that F ∈
/ F {1} . We will show that for any IL -fiber F and any
xu , xv ∈ F there is an S-path between xu , xv . This was already noticed if F ∈ F {1} . By
Theorem 3.8 we can assume that there is an S-path between any two elements of G for all
σ
σ
G such that G <IL F . We note that u − v ∈ L. Suppose that G(MF )σ = {xa1 , . . . , xak }
where xa1 , . . . , xak ∈ G(MF ). We examine three cases.
Case 1. If uσ = vσ then (u−v)σ = 0 and by Corollary 2.9 it follows that u−v ∈ Lpure .
Therefore xu − xv ∈ ILpure and since ILpure = hSF {1} i it follows that xu − xv ∈ hSi.
Case 2. Suppose that uσ 6= vσ and that the vertices of GF corresponding to uσ and
σ
v are in the same connected component of GF . Assume that uσ = aσi and vσ = aσj and
that i = i1 , . . . , il = j is a path in GF . By applying induction on l it is enough to prove
the statement when l = 2 and {i, j} is an edge of GF . It follows from the definition of
GF that there exists a binomial xw − xz ∈ IL,<F such that wσ = uσ , zσ = vσ . Moreover
xw , xz ∈ G where G <IL F . Thus there is a monomial xa such that xa G ⊂ F . By Case 1
above, there is an S-path from xu to xw+a and an S-path from xv to xz+a . By assumption
there is an S-path from xw to xz , and thus also from xw+a to xz+a . Putting the S-paths
14

together one gets an S-path from xu to xv . We point out that the above argument shows
that xu − xv ∈ IL,<F .
Case 3. Suppose that uσ 6= vσ and that the vertices of GF corresponding to uσ
and vσ are in disconnected components of GF . Since S determines a spanning tree of
ΓF there is a series of edges in ΓF that leads from the component that corresponds to
σ
σ
xu to the component that corresponds to xv . As before it is enough to prove the
statement when the components are adjacent. This means that there exists a binomial
′
′
B = xu − xv ∈ (IL,≤F \ IL,<F ) ∩ S such that u′ σ , uσ correspond to the same connected
′
′
component of GF and similarly for v′ σ , vσ . The monomials xu ,xv of B, belong to a fiber
′
′
equivalent to F . It follows that there is b ∈ Nn such that xu +b and xv +b belong to F
′
′
′
′
and thus the sequence (xu +b , xv +b ) is an S-path from xu +b to xv +b . By Case 2 above,
′
′
there is an S-path from xu to xu +b and an S-path from xv to xv +b . Joining these paths
one gets an S-path from xu to xv .

We let t(F ) denote the number of vertices of ΓF . Thus
t(F ) := |V (ΓF )|.
We note that to construct a spanning tree of ΓF we need exactly t(F ) − 1 binomials. To
prove the next theorem we will use Theorem 4.3.
Theorem 4.12. Let L ⊂ Zn be a lattice and S a subset of IL consisting of binomials. The
set S is a cardinality-minimal generating set of IL if and only if the following conditions
are satisfied:
• ΓF (S) is a spanning tree of ΓF for every IL -fiber F , and |SF | = t(F ) − 1 for every
IL -fiber F such that F ∈
/ F {1} ,
• |SF {1} | = rank(Lpure ) and
• ILpure = hSF {1} i.
Proof. Suppose that S is a cardinality-minimal generating set of IL . We will show that
S satisfies the three conditions of the theorem. We note that since S is a generating set
of IL , by Proposition 3.12 and Remark 3.10 it follows that hSF {1} i = ILpure . Moreover
if |SF {1} | > rank(Lpure ), then by Theorem 4.1 one can replace the binomials in SF {1}
by a cardinality-minimal generating set of ILpure . The new set thus produced is still a
generating set of IL , according to Lemma 4.11, and has smaller cardinality than S, a
contradiction. Next we show that for an arbitrary IL -fiber F , ΓF (S) is a spanning tree
of ΓF . Indeed, by Theorem 4.3, S induces a spanning graph in F . Since GF comes from
F by identifying components and similarly for ΓF from GF , it follows that ΓF (S) is a
spanning graph of ΓF . We show that ΓF (S) is a tree of ΓF . If not, ΓF (S) has a cycle in
ΓF . We omit from S the binomial that induces an edge on this cycle. The resulting set
still satisfies the conditions of Lemma 4.11 and is thus a generating set of IL of smaller
cardinality, a contradiction. Similarly, if for some fiber F such that F ∈
/ F {1} we have
|SF | > t(F ) − 1 then there is a binomial in SF that does not correspond to an edge of
ΓF (S) or two binomials that correspond to the same edge. Then one binomial could be
omitted from S and the resulting set would still be a generating set of IL .
Conversely let S be a set that satisfies the three conditions of the theorem. By
Lemma 4.11, S is a generating set of IL . Suppose that there is a cardinality-minimal generating set S ′ of IL such that |S ′ | < |S|. Let F be a Markov fiber such that |SF′ | < |SF |. We
15

note that F ∈
/ F {1} since |SF′

{1}

| ≥ rank(Lpure ) = |SF {1} |. Moreover |SF | = t(F )−1 ≤ |SF′ |,

a contradiction. Therefore S is a cardinality-minimal generating set of IL .



Remark 4.13. When Lpure = {0} then the construction and conditions on ΓF coincide
with the construction and conditions of Sb from [4], since by Proposition 2.4 G(MF ) = F .
Furthermore, in this case Theorem 4.12 becomes the join of [4, Theorem 2.6] and [4,
Theorem 2.7]. To understand better how Theorem 4.12 works to compute all (infinitely
many) cardinality-minimal generating sets in the general case of a non-positive lattice, see
the example worked in great detail from Section 6.
We remark that for all but finitely many equivalence classes of fibers F , t(F ) = 1. Indeed
by Corollary 3.14 the set consisting of equivalence classes of Markov fibers is finite. If an
IL -fiber F is not a Markov fiber, then by Theorem 3.13 it follows that IL,≤F = IL,<F and
hence GF consists of only one connected component. The next result is the main theorem
of this section. Its proof is an immediate consequence of Theorem 4.12.
Theorem 4.14. Let L ⊂ Zn be a lattice and µ(IL ) be the cardinal of a cardinality-minimal
generating set of IL . Then
X
µ(IL ) = rank(Lpure ) +
(t(F ) − 1),
F 6=F {1}

where the sum runs over all distinct equivalence classes of Markov fibers.
The next corollary follows from Corollary 3.14 and Theorem 4.12. It generalizes the
corresponding result for positive lattices, see [3, Theorem 2.5] and [12, Theorem 1.3.2].
Corollary 4.15. Let L ⊂ Zn be a lattice, µ = µ(IL ) and {B1 , . . . , Bµ } a cardinalityminimal generating set of IL . The multiset
{F B1 , . . . , F Bµ }
is an invariant of IL .
The following result concerns an arbitrary minimal generating set of IL : the play in the
cardinality of such a set only concerns the pure part of L. Note that if Lpure 6= 0 then IL
can be minimally generated by µ(IL ) + k binomials for every k ∈ N. More precisely, all
extra k binomials are given by the fiber F{1} with a similar argument as the one given in
introduction for the lattice L = h(1, 1), (5, 0)i. The proof of Corollary 4.16 follows directly
from the proof of Theorem 4.12.
Corollary 4.16. Let L be a lattice and S = {B1 , . . . , Bt } a minimal generating set of IL .
The multiset
{F Bi : FBi 6∈ F {1} }
is an invariant of IL .
4.3. Applications. In the last years, due to applications of minimal generating sets to
algebraic statistics, there is an interest in determining the indispensable binomials of a
lattice ideal, see [28, 29, 4, 1, 30]. Of particular interest is the case when all elements in
a minimal generating set of the lattice ideal are indispensable as is the case for generic
lattice ideals, see [31].
Definition 4.17. A binomial is called indispensable (weakly indispensable, respectively)
if it appears in every minimal generating set (every cardinality-minimal generating set,
16

respectively) of IL up to a constant multiple. A monomial xu is called indispensable (weakly
indispensable, respectively) if for every minimal generating set (every cardinality-minimal
generating set, respectively) S of IL there is a binomial B ∈ S so that xu is a monomial
term of B.
Note that an indispensable binomial/monomial is weakly indispensable. If L is positive then the characterization of indispensable binomials is given by [4, Corollary 2.10],
see also [4, Theorem 3.4]. Note that in the case of positive lattices the notions of indispensable and weakly indispensable coincide. Recently, a polynomial-time algorithm for
computing all indispensable binomials from a given system of binomial generators of an
arbitrary binomial ideal was given in [7, Algorithm 1]. Next we complete the classification
of indispensable binomials/monomials of lattice ideals in the case of non-positive lattices.
Theorem 4.18. Let L be a non-positive lattice. Then IL has no indispensable binomials,
but it has one indispensable monomial, 1 = x0 . If rank(Lpure ) > 1 then there are no
weakly indispensable binomials and only one weakly indispensable monomial 1 = x0 . If
rank(Lpure ) = 1 there exists exactly one weakly indispensable binomial and exactly two
weakly indispensable monomials.
Proof. Let L be a lattice such that rank(Lpure ) = r ≥ 1 and S a cardinality-minimal generating set of IL . In order to determine the (weakly) indispensable binomials/monomials
of IL we analyze the two cases of Markov fibers which might contain them: 1) F ∈ F {1}
and 2) F ∈
/ F {1} .
In the first case, if Lpure has rank 1 then Lpure = hui, where u ∈ L+ is L-primitive
and by Theorem 4.1 and Theorem 4.12 we have that SF {1} = {xu − 1}. Thus, when
rank(Lpure ) = 1 we have one weakly indispensable binomial and two weakly indispensable
monomials, which correspond to fiber F{1} . Replacing xu − 1 from a cardinality-minimal
generating set with x2u − 1, x3u − 1 we obtain a minimal generating set of IL . Hence
we have no indispensable binomials corresponding to a fiber F ∈ F {1} . However, 1 is an
indispensable monomial of IL because otherwise the ideal IL would be contained in the
maximal ideal hx1 , . . . , xn i, a contradiction since rank(Lpure ) > 0.
Suppose now that Lpure has rank r > 1. Without loss of generality we can assume that
SF {1} = {xu1 − 1, . . . , xur − xvr } satisfies the three conditions of Theorem 4.1. For every
i ≥ 2 let u′i = ui + u1 and vi′ = vi + u1 and note that u′i − vi′ = ui − vi . By Theorem 4.1
′
′
′
′
it follows that {xu1 − 1, xu2 − xv2 , . . . , xur − xvr } is also a cardinality-minimal generating
set of ILpure having only one binomial in common with SF {1} . Since rank(Lpure ) > 1 there
are infinitely many L-primitive elements of full support and thus infinitely many bases of
Lpure as in Corollary 2.14. Any of these bases induces a cardinality-minimal generating
set of ILpure , see Theorem 4.1. By applying the above trick to any of these cardinalityminimal generating sets we conclude that there are no weakly indispensable binomials for
IL corresponding to a fiber F ∈ F {1} , but there is one weakly indispensable monomial of
IL belonging to F{1} and is 1 = x0 . Obviously there are no indispensable binomials in this
case, but 1 is an indispensable monomial with the same argument as before.
In the second case assume that there exists a Markov fiber F such that F ∈
/ F {1} ,
that is F >IL F {1} . Then we prove that there are infinitely many distinct choices for
the binomials that determine any edge in a spanning tree of ΓF . Since F is a Markov
fiber, Theorem 3.13 says that IL,<F 6= IL,≤F . Thus there exists B = xu − xv , such
that FB ∈ F and B ∈
/ I<F . We note that uσ 6= vσ : otherwise u − v ∈ Lpure and
17

xu − xv ∈ ILpure = IL,≤F {1} ⊂ IL,<F , a contradiction. Therefore B produces an edge in
ΓF and can be made part of a cardinality-minimal generating set S of IL . Since L is nonpositive there exist vectors w1 , w2 ∈ L+ \ {0}. Then B ′ = xu+w1 − xv+w2 gives exactly
the same edge as B and can replace B in S. Hence we obtain that there are no weakly
indispensable binomials or monomials of IL corresponding to a fiber F ∈
/ F {1} . This
also implies that in the second case there are no indispensable binomials or monomials of
IL .

One nice practical application of Theorem 4.18 is to detect whether a lattice is positive
or not. Indeed, given any arbitrary set of vectors which span a lattice L then: 1) apply one
of the existing algorithms, for example the one from [2] or [17], to compute a generating set
of IL , and 2) decide that L is positive if and only if 1 is not in the support of any binomial
from the computed generating set. The latter is true by Theorem 4.18 since for nonpositive lattices the corresponding lattice ideals have 1 as indispensable monomial while
for positive lattices the fiber of 1 consists only of 1. Next we present another application
following from the proof of Theorem 4.18. First we define the universal Markov basis of
IL to be the union of all cardinality-minimal generating sets of IL , up to a sign.
Theorem 4.19. Let L be a lattice. If rank(Lpure ) > 1 or rank(Lpure ) = 1 and L 6= Lpure
then the universal Markov basis of IL is infinite.
Note that the alternative definition of universal Markov basis as the union of all minimal
generating sets would also imply the conclusion of Theorem 4.19 and only under the
assumption that the lattice is non-positive, as explained in the Introduction. However,
both definitions are identical in the case of positive lattices, since a minimal generating
set is automatically a cardinality-minimal generating set, and they match the definition of
universal Markov basis introduced in [19, Definition 3.1]. For positive lattices the vectors
corresponding to the universal Markov basis have also an useful algebraic description, see
[6, Proposition 1.4]. We note that for non-positive lattices L satisfying the hypotheses
of Theorem 4.19 the universal Markov basis of IL is not contained in the Graver basis,
since the Graver basis is finite (see [37, Algorithm 7.2]). Moreover, Theorem 4.19 was
the the starting point for classifying the lattices for which the universal Markov basis is
contained either in the Graver basis or the universal Gröbner basis, see [5, Theorem 2.3]
or [5, Theorem 2.7].
The Markov complexity of an integer matrix, see [33] for the definition, is another topic
of interest in algebraic statistics, related to the universal Markov basis. We note that the
results of this paper and in particular Theorems 4.1, 4.12 are used in [5, Section 3] to give
necessary and sufficient conditions for the Markov complexity to be finite.
5. Binomial Complete Intersection Lattice Ideals
In this section we characterize all binomial complete intersection lattice ideals. This is
a problem that engaged mathematicians starting in 1970, see [16]. We recall that a lattice
ideal IL of height r is a complete intersection if there exist polynomials P1 , . . . , Pr such
that IL = hP1 , . . . , Pr i and IL is a binomial complete intersection if there exist binomials
B1 , . . . , Br such that IL = hB1 , . . . , Br i. In the case of positive lattices Nakayama’s lemma
applies and then complete intersection lattice ideals are automatically binomial complete
intersections. Furthermore, for positive lattices the problem was gradually solved in a
series of papers [16, 9, 36, 20, 39, 26, 34, 32, 14, 35, 25]. The final conclusion is that IL
is a complete intersection if and only if the matrix M whose rows correspond to a basis
18

of L is “mixed dominating”: every row of M has a positive and negative entry and M
contains no square submatrix with this property, see [25, Theorem 3.9]. However, when L
is non-positive the problem was open and we give a complete answer in Theorem 5.5 and
Corollary 5.6.
We recall that σ is the maximum support of an element of L∩Nn , Lpure is the sublattice
n σ
σ
of L generated by the elements of L ∩ Nn , uσ = (ui )i∈σ
/ ∈ (Z ) and L is the sublattice
n
σ
σ
of (Z ) generated by the vectors u , where u ∈ L.
As an immediate consequence of definitions and Corollary 2.9 we have the following
equivalences:
σ = ∅ ⇔ Lpure = {0} ⇔ L is positive ⇔ Lσ = L,
and
L is pure ⇔ L = Lpure ⇔ Lσ = {0}.
First we have the following:
Remark 5.1. Lσ is a positive lattice.
Proof. The conclusion follows at once when σ = ∅. Assume now that σ 6= ∅ and let
w ∈ L ∩ Nn be such that supp(w) = σ. If 0 6= uσ ∈ Lσ ∩ (Nn )σ then there exists k ∈ N,
k ≫ 0 such that u′ = u + kw ∈ L ∩ Nn . Thus σ ( supp(u′ ), a contradiction.

Next we show that the rank of L is determined by the ranks of its sublattice Lpure and
the lattice Lσ .
Proposition 5.2. Let L ⊂ Zn be a lattice. Then L ∼
= Lσ ⊕ Lpure .
Proof. The following is a split exact sequence of Z-modules:
π

0 −→ Lpure ֒→ L → Lσ −→ 0,
where π is the restriction of the canonical projection Zn → (Zn )σ given by u → π(u) =
(ui )i∈σ
/ . For the exactness, we note that π is a surjective homomorphism of Z-modules
whose kernel is Lpure , by Corollary 2.9.

We consider the lattice ideal ILσ in Rσ := k[xi : i 6∈ σ]. We show that in order to
compute the ILσ -fibers, it is enough to consider the generating sets of the corresponding
IL -fibers.
σ

Lemma 5.3. Let L ⊂ Zn be a lattice and u ∈ Nn . Then the ILσ -fiber of xu is G(MFu )σ ,
where Fu is the IL -fiber of xu .
′

Proof. Let u′ = uσ ∈ (Nn )σ and denote by F ′ the ILσ -fiber of xu . It follows from Remark
5.1 that F ′ is finite. We will show that F ′ = Fuσ and thus by Proposition 2.7 we obtain
F ′ = G(MFu )σ , since for any vector t ∈ L+ we have tσ = 0. To prove this, consider first
σ
an element xv ∈ Fu . Then v − u ∈ L and vσ − uσ ∈ Lσ . Hence xv ∈ F ′ and we obtain
′
the inclusion F ′ ⊃ Fuσ . For the converse inclusion, let xv ∈ F ′ . Then u′ − v′ ∈ Lσ and it
follows that there exists a vector w ∈ L such that u′ − v′ = wσ . Therefore v′ = (u − w)σ .
′

Since u − (u − w) = w ∈ L we obtain that xu−w ∈ Fu and xv ∈ Fuσ , as desired.
Next we show that the cardinality µ(IL ) of a cardinality-minimal generating set of IL
depends on the cardinality µ(ILσ ) of a cardinality-minimal generating set of ILσ .
Theorem 5.4. Let L be a lattice. Then
µ(IL ) = µ(ILσ ) + rank(Lpure ).
19

Proof. If L is positive then Lpure = {0}, L = Lσ and the conclusion is obvious. On
the other hand, when L is a pure lattice then Lσ = {0} and the conclusion follows from
Theorem 4.1. Assume now that L is non-positive and non-pure, that is both Lpure and
P
Lσ are nonzero. By Theorem 4.14 we have µ(IL ) = rank(Lpure ) + F u 6=F {1} (t(F u ) − 1).

/ F {1} . Thus,
Applying Lemma 5.3 the graphs ΓF u and ΓF uσ are equal for any fiber Fu ∈
P
applying once more Theorem 4.14 we obtain µ(ILσ ) = F u 6=F {1} (t(F u ) − 1), since Lσ is
positive.

The following theorem follows directly from Proposition 5.2 and Theorem 5.4 and determines the binomial complete intersection lattice ideals. It is the main theorem of this
section.

Theorem 5.5. Let L ⊂ Zn be a lattice. The ideal IL is binomial complete intersection if
and only if ILσ is complete intersection.
We can describe the lattices for which IL is a binomial complete intersection. Recall
that a mixed dominating matrix M has the property that every row of M has a positive
and negative entry and M contains no square submatrix with this property.
Corollary 5.6. Let L ⊂ Zn be a lattice. The ideal IL is binomial complete intersection
if and only if either Lσ = {0} or there exists a basis of Lσ such that its vectors give the
rows of a mixed dominating matrix.
Proof. If the lattice L is pure, or equivalently Lσ = {0}, then by [13, Theorem 2.1] or
Theorem 4.1 the ideal IL is binomial complete intersection. Assume now that L is nonpure. Since by Remark 5.1 Lσ is positive, the proof follows from Theorem 5.5 and [25,
Theorem 3.9].

Remark 5.7. Let L ⊂ Zn be a non-pure lattice, r = rank(L) and r+ = rank(Lpure ). The
previous corollary states that IL is binomial complete intersection if and only if there is a
basis of L whose vectors give the rows of


A M
C 0
where A ∈ M(r−r+ )×|σ| (Z), the matrix M ∈ M(r−r+ )×(n−|σ|) (Z) is mixed dominating, the
matrix C ∈ Mr+ ×|σ| (Z) is a matrix whose rows satisfy the conditions of Theorem 4.1, and
0 is the zero matrix. For example, any matrix with entries in N and linearly independent
rows has the desired property for C above, while for a mixed dominating matrix M one can
use [25, Remark 3.17] or [14, Theorem 2.2]. By working with the appropriate size matrices
one can easily obtain a class of lattice ideals that are binomial complete intersections.
6. Example
Algorithms for computing a generating set for lattice ideals were given in [18, 2, 17].
In the following example we use the techniques introduced in this paper to show how
to obtain all cardinality-minimal generating sets of a lattice ideal. Let L be the lattice
of Example 4.9. L is generated by the vectors v1 = (3, 0, 1, −1, 0), v2 = (0, 1, 6, 0, −1),
v3 = (1, 1, 0, 0, 0) and v4 = (5, 0, 0, 0, 0). We note that v5 = (0, 5, 0, 0, 0) ∈ L,
L+ = L ∩ N5 = Nv3 + Nv4 + Nv5
and
Lpure = Zv3 + Zv4 .
20

Thus rank(Lpure ) = 2, σ = {1, 2}. Let F be an IL -fiber. Since |Z2 /(Lpure )σ | = 5 it follows
by Proposition 3.5 that F consists of five equivalent fibers. In particular, let F{1} be the
fiber that contains 1 = x0 . As in Example 3.6(b) we see that
F {1} = {F{1} , Fx1 , Fx21 , Fx31 , Fx41 }
where for each 0 ≤ k ≤ 4, the fiber Fxk consists of the monomials xi1 xj2 with i − j ≡ k
1
mod 5. Thus if xu ∈ R then
F xu = {Fxu , Fxu x1 , Fxu x21 , Fxu x31 , Fxu x41 }.
Note that every equivalence class of fibers is in the form F xn4 for some n ∈ N and
F {1} <IL F x4 <IL F x24 <IL · · · <IL F xn4 <IL · · · .

(1)

It is clear that the above equivalence classes of fibers are pairwise distinct: use Lemma 3.1
and notice that there is no w ∈ N5 with supp(w) ⊂ σ such that w + (0, 0, 0, k, 0) ∈ L.
To find a generating set of IL in R = k[x1 , . . . , x5 ] one first computes the ideal
hx4 − x31 x3 , x5 − x2 x63 , 1 − x1 x2 , 1 − x51 i : (x1 · · · x5 )∞
using for example CoCoA [8]. Computing IL,<F

xi
4

and IL,≤F

xi
4
x64

with the use of Proposi-

tion 3.12 we conclude via Theorem 3.13 that F{1} , Fx4 and F are the Markov fibers.
Let S be a cardinality-minimal generating set of IL . According to Theorem 4.12,
|SF {1} | = rank(Lpure ) = 2 and SF {1} must generate ILpure = h1 − x51 , 1 − x1 x2 i. We note
that by Theorem 4.1 there are infinitely many choices for binomials B1 , B2 that generate
ILpure , and one way of constructing infinitely many such binomials is using Theorem 2.13
with Corollary 2.14. We remark that the multiset {FB1 , FB2 } equals {F{1} , F }, where F
can be any of the five fibers of F {1} .
Consider now the Markov fiber Fx4 . It is an easy exercise that
G(MFx4 ) = {x22 x3 , x31 x3 , x4 }.
Thus G(MFx4 )σ = {x4 , x3 }. Since IL,<F x = ILpure it is immediate that GF x consists of
4

4

two isolated vertices. Thus t(F x4 ) = 2 and exactly one binomial is needed to construct
a spanning tree of ΓF x . To obtain a cardinality-minimal generating set, according to
4
Theorem 4.12, we need to add to SF {1} a binomial B3 = ±(xu −xv ) such that xu ∈ x3 Fx3+i
1

and xv ∈ x4 Fxi1 , where 0 ≤ i ≤ 4. For example, any of the binomials x21 x4 − x3 and
x2 x3 − x2016
x4 can be chosen as B3 .
1
Next consider the Markov fiber F ′ = Fx64 , for which F ′ = {Fx64 , Fx1 x64 , Fx5 }. Based on
Lemma 4.7 and as in Example 4.9 we have
G(MF ′ )σ = {x5 , x63 , x53 x4 , x43 x24 , x33 x34 , x23 x44 , x3 x54 , x64 }.
Since the graph GF ′ consists of two connected components (see Example 4.9), we need
one more binomial B4 = ±(xw1 − xw2 ) so that xw1 ∈ x5 Fxi and xw2 is in the union of the
1
sets x63 Fx4+i , x53 x4 Fx1+i , x43 x24 Fx3+i , x33 x34 Fxi , x23 x44 Fx2+i , x3 x54 Fx4+i , x64 Fx1+i , 0 ≤ i ≤ 4.
1

1

1

1

1

1

1

x3 x54 − x31 x5 can be chosen as
For example any of the binomials x23 x44 − x22 x5 and x21 x2015
2
B4 .
According to Theorem 4.12, S = {B1 , B2 , B3 , B4 } is a cardinality-minimal generating
set of IL . Thus µ(IL ) = 4 and IL is a binomial complete intersection. This also follows
21

immediately from Corollary 5.6, since Lσ is generated by v1σ , v2σ and the matrix


1 −1 0
6 0 −1
is mixed dominating.
Acknowledgment. The authors would like to thank Ezra Miller for useful discussions
on binomial fibers, back in 2009, that initiated this work. Also, we thank the anonymous
referee for several helpful suggestions on the terminology of this paper and for simplifying
the proofs of Propositions 2.11, 5.2 and Theorems 2.12, 2.13. This paper was partially
written during the visit of the second and third author at the University of Ioannina. The
third author was supported by a Romanian grant awarded by UEFISCDI, project number
83/2010, PNII-RU code TE 46/2010, program Human Resources, “Algebraic modeling of
some combinatorial objects and computational applications”.
References
[1] S. Aoki, A. Takemura, R. Yoshida, Indispensable monomials of toric ideals and Markov bases, J.
Symbolic Comput. 43 (2008), 490–507.
[2] A. Bigatti, R. LaScala, L. Robbiano, Computing toric ideals, J. Symbolic Computation 27 (1999),
351–365.
[3] E. Briales, A. Campillo, C. Marijuán, P. Pisón, Minimal systems of generators for ideals of semigroups,
J. Pure Appl. Algebra 124 (1998), 7–30.
[4] H. Charalambous, A. Katsabekis, A. Thoma, Minimal systems of binomial generators and the indispensable complex of a toric ideal, Proc. Amer. Math. Soc. 135 (2007), 3443–3451.
[5] H. Charalambous, A. Thoma, M. Vladoiu, Markov bases and generalized Lawrence liftings, Annals of
Combinatorics 19 (2015), 661–669.
[6] H. Charalambous, A. Thoma, M. Vladoiu, Markov complexity of monomial curves, J. Algebra 417
(2014) 391–411.
[7] H. Charalambous, A. Thoma, M. Vladoiu, Binomial fibers and indispensable binomials, J. Symbolic
Computation 74 (2016), 578–591.
[8] CoCoATeam, CoCoA: a system for doing Computations in Commutative Algebra, available at
http://cocoa.dima.unige.it
[9] Ch. Delorme, Sous monoides d’intersection complete de N , Ann. Sci. École Norm. Sup. (4) 9 (1976),
145–154.
[10] P. Diaconis, B. Sturmfels, Algebraic algorithms for sampling from conditional distributions, Ann.
Statist., 26 (1998), 363–397.
[11] A. Dickenstein, L.F. Matusevich, E. Miller, Combinatorics of binomial primary decomposition, Math.
Z. 264 (2010), 745–763.
[12] M. Drton, B. Sturmfels, S. Sullivant, Lectures on algebraic statistics, Oberwolfach Seminars, 39.
Birkhäuser Verlag, Basel, 2009. viii+171 pp.
[13] D. Eisenbud, B. Sturmfels, Binomial ideals, Duke Math. J. 84 (1996), 1–45.
[14] K. Fischer, W. Morris, J. Shapiro, Affine semigroup rings that are complete intersections, Proc. Amer.
Math. Soc. 125 (1995), 3137–3145.
[15] I. Gitler, E. Reyes, J. A. Vega, Complete intersection toric ideals of oriented graphs and Chorded-Theta
subgraphs, J. Algebr. Comb. 38 (2013), 721–744.
[16] J. Herzog, Generators and relations of abelian semigroups and semigroup rings, Manuscripta Math. 3
(1970), 175–193.
[17] R. Hemmecke, P. Malkin, Computing generating sets of lattice ideals and Markov bases of lattices, J.
Symbolic Computation 44 (2009), 1463–1476.
[18] S. Hoşten, B. Sturmfels, GRIN: an implementation of Gröbner bases for integer programming, in
Integer Programming and Combinatorial Optimization (Copenhagen), LNCS 920 Springer Verlag
(1995), 267–276.
[19] S. Hoşten, S. Sullivant, A finiteness theorem for Markov bases of hierarchical models, J. Combin.
Theory Ser. A 114 (2007), 311–321.
22

[20] M. N. Ishida, Normal semigroup rings which are complete intersections, in: Proc. Symposium on
Commtative Algebra, Karuizawa, 1978.
[21] T. Kähle, E. Miller, Decompositions of commutative monoid congruences and binomial ideals, Algebra
Number Theory 8 (2014) 1297–1364.
[22] H. López, R. Villarreal, Complete intersections in binomial and lattice ideals, Internat. J. Algebra
Comput. 23 (2013) 1419–1429.
[23] E. Miller, Theory and Applications of lattice point methods for binomial ideals, in Combinatorial
Aspects of Commutative Algebra and Algebraic Geometry, Proceedings of Abel Symposium held at
Voss, Norway, 14 June 2009, Abel Symposia, vol. 6, Springer Berlin Heidelberg, (2011), pp. 99–154.
[24] E. Miller, B. Sturmfels, Combinatorial Commutative Algebra, Grad. Texts in Math., vol. 227, SpringerVerlag, New York, (2005).
[25] M. Morales, A. Thoma, Complete intersection lattice ideals, J. Algebra 284 (2005), 755–770.
[26] H. Nakajima, Affine torus embeddings which are complete intersections, Tôhoku Math. J. 38 (1986),
85–98.
[27] L. O’Carroll, F. Planas–Vilanova, R. Villarreal, Degree and algebraic properties of lattice and matrix
ideals, SIAM J. Discrete Math. 28 (2014), no. 1, 394–427.
[28] H. Ohsugi, T. Hibi, Indispensable binomials of finite graphs, J. Algebra Appl. 4 (2005), 421–434.
[29] H. Ohsugi, T. Hibi, Toric ideals arising from contingency tables, Proceedings of the Ramanujan
Mathematical Society’s Lecture Notes Series, (2006), 87–111.
[30] I. Ojeda, A. Vigneron-Tenorio, Indispensable binomials in semigroup ideals, Proc. Amer. Math. Soc.
138 (2010), 4205–4216.
[31] I. Peeva, B. Sturmfels, Generic lattice ideals, J. Amer. Math. Soc. 11 (1998), 363–373.
[32] J. C. Rosales, P. A. Garcia-Sanchez, On complete intersection affine semigroups, Commun. Algebra
23 (1995), 5395–5412.
[33] F. Santos, B. Sturmfels, Higher Lawrence configurations, J. Combin. Theory Ser. A 103, 151–164
(2003).
[34] U. Schäfer, Der kanonische modul monomialer raumkurven, Diplomarbeit, Martin-Luther-Universität
Halle/Wittenberg, Halle, (1985).
[35] G. Scheja, O. Scheja, U. Storch, On regular sequences of binomials, Manuscripta Math. 98 (1999),
115–132.
[36] R. P. Stanley, Relative invariants of finite groups generated by pseudoreflections, J. Algebra 49 (1977),
134–148.
[37] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series, No. 8 American Mathematical Society Providence, R.I. (1995).
[38] B. Sturmfels, R. Weismantel, G. Ziegler, Gröbner Bases of Lattices, Corner Polyhedra, and Integer
Programming, Beiträge zur Algebra und Geometrie, Contributions to Algebra and Geometry, 36
(1995), 281–298.
[39] K. Watanabe, Invariant subrings which are complete intersections, I (Invariant subrings of finite
abelian groups), Nagoya Math. 77 (1980), 89–98.
Department of Mathematics, Aristotle University of Thessaloniki, Thessaloniki, 54124,
Greece
E-mail address: hara@math.auth.gr
Department of Mathematics, University of Ioannina, Ioannina 45110, Greece
E-mail address: athoma@uoi.gr
Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei
14, Bucharest, RO-010014, Romania
E-mail address: vladoiu@fmi.unibuc.ro

23

