STRONGLY ROBUST TORIC IDEALS IN CODIMENSION 2

arXiv:1610.07476v2 [math.AC] 30 Mar 2017

SETH SULLIVANT
Abstract. A homogeneous ideal is robust if its universal Gröbner basis is also a minimal
generating set. For toric ideals, one has the stronger definition: A toric ideal is strongly
robust if its Graver basis equals the set of indispensable binomials. We characterize the
codimension 2 strongly robust toric ideals by their Gale diagrams. This give a positive
answer to a question of Petrovic, Thoma, and Vladoiu in the case of codimension 2 toric
ideals.

1. Introduction
A homogeneous ideal is robust if its universal Gröbner basis is also a minimal generating
set. Although one typically expects the universal Gröbner basis to be much larger than a
minimal generating set (and hence most ideals are far from robust), there are a surprising
number of examples of ideals that are robust. Usually these examples have rich underlying
combinatorics. Three well-known example are: the ideals of maximal minors of generic
matrices of indeterminates [BZ93, SZ93], the vanishing ideal of the closure of an affine
linear space in (P1 )n [AB16], and toric ideals of Lawrence type (see [Stu96, Chapter 7]).
Let A ∈ Zd×n be an integer matrix of rank d, and K[p] := K[p1 , . . . , pn ] the polynomial
ring in n indeterminates. The toric ideal associated to the matrix A is the binomial ideal
IA = hpu − pv : u, v ∈ Nn , Au = Avi.
Properties of the generating set of IA and the geometry of the corresponding variety
are determined by combinatorial properties of the matrix A, and many conditions can
be expressed in terms of linear algebra over the integers. Boocher and Robeva [BR15]
initiated a systematic study of robustness of toric ideals and introduced the word “robust”.
They showed that a set of quadratic binomials generate a robust ideal if and only if it is
the direct sum of ideals of maximal minors of 2 × ni generic matrices on disjoint sets of
variables. Since these ideals are toric ideals of Lawrence type, one wonders if all robust
toric ideals must be of Lawrence type. Petrovic, Thoma, and Vladoiu [PTV15] studied
this problem by introducing an oriented matroid concept they call “bouquets”, which we
explain below. They also introduced a strengthening of robust for toric ideals, which they
called ∅-Lawrence, and we call strongly robust, that involves looking at a superset of the
universal Gröbner basis called the Graver basis (explained in Section 2).
One motivation for studying strongly robust toric ideals comes from algebraic statistics.
Recall that the generating set of a toric ideal is called a Markov basis. This is because the
binomial generators can be used as a set of moves to perform a random walk on the fiber
F(u) = {v ∈ Nn : Au = Av} (see [DS98]). While any binomial generating set of the toric
ideal can be used to generate the associated Markov chain, Markov bases that make rapid
1

2

SETH SULLIVANT

connections between elements of all fibers should be preferred since our intuition tells
us that these Markov chains will mix more rapidly. One desirable property of a Markov
basis that guarantees short connections it the distance-reducing property [TA05]. Since
Graver bases always satisfy the distance-reducing property, strongly robust toric ideals
have the pleasing property that every Markov basis is distance-reducing. This suggests
that strongly robust toric ideals should have nice properties from the standpoint of mixing
times of the associated Markov chain.
Associated to the matrix A is the Gale transform B which is a n × n − d integer matrix
whose columns span kerZ A. When describing the matrix A, we often think about it as
a list of column vectors A = {a1 , a2 , . . . , an }. When describing the Gale transform we
think about it as a list of row vectors B = {b1 , b2 , . . . , bn }. A bouquet is a maximal subset
S ⊆ [n] such that span(bs : s ∈ S) in one-dimensional. A bouquet S is mixed if not all
elements {bs : s ∈ S} lie in the same orthant. In the language of matroid theory, bouquets
correspond to rank one flats of the dual matroid associated to A.
A key observation of [PTV15] is that the toric ideals of Lawrence type have many mixed
bouquets. Recall that if A ∈ Zd×n , the Lawrence lifting of A is the matrix


A 0
Λ(A) =
∈ Z(d+n)×2n
I I
where I denotes an n×n identity matrix. A toric ideal IC is said to be of Lawrence type if
it is equal to IΛ(A) for some matrix A, perhaps after permuting the indeterminates. Note
that
kerZ Λ(A) = {(u, −u) ∈ Z2n : u ∈ kerZ A}.
This means that for a toric ideal of Lawrence type, every s ∈ [2n] belongs to a mixed
bouquet. Petrovic, Thoma, and Vladoiu also show how to use the bouquet structure to
produce new examples of strongly robust toric ideals that are not of Lawrence type, and
they posed the following question about strongly robust toric ideals.
Question 1.1. If IA is a strongly robust toric ideal, must A have a mixed bouquet?
If A ∈ Zd×n is a toric ideal, with d = rankA, then the codimension of IA is n − d.
When the codimension of IA is one, in which case IA is a principal ideal, Question 1.1 is
trivial since A consists of a single bouquet that must be mixed if IA is positively graded.
We also provide a positive answer to Question 1.1 in the case that IA has codimension 2
by giving a complete characterization of the strongly robust codimension 2 toric ideals in
terms of the Gale transform, which is described in following sections. One consequence is
the following:
Theorem 1.2. Let A ∈ Z(n−2)×n be a full rank matrix, and B̃ = {b1 , . . . , bn } ⊆ Z2 be
the reduced Gale transform of A. If IA is a strongly robust toric ideal then conv(B̃) is a
centrally symmetric polygon.
In fact, Theorem 1.2 provides a stronger answer to Question 1.1 in the case of codimension 2 toric ideals.
Corollary 1.3. If a codimension 2 toric ideal IA is strongly robust then A has at least 2
mixed bouquets.

STRONGLY ROBUST TORIC IDEALS IN CODIMENSION 2

3

Both of these results will be a consequence of the general characterization of strongly
robust codimension 2 toric ideals that we prove in the next section. The proof uses
the Peeva-Sturmfels [PS98] theory of toric ideals of codimension 2. While the result of
Theorem 1.2 does not directly generalize to toric ideals of higher codimension, it does
suggest that the property of being strongly robust is connected to the geometry of the
Gale transform, which might suggest other approaches to Question 1.1.
2. Proof of Theorem 1.2 and Corollary 1.3
To prove Theorem 1.2 we need more details about strongly robust toric ideals, and
results about generating sets of codimension 2 toric ideals. Note that the main definitions
and constructions will be illustrated in Example 2.8.
First of all, we need to formally introduce the definition of strongly robust toric ideal
[BBD+ 15, PTV15]. To explain this we introduce some definitions. Given a vector u ∈ Zn
the support of u, supp(u) ⊆ [n] is the set of indices i where ui is not zero. Let u ∈ Nn . The
fiber of u is the set F(u) = {v ∈ Nn : Au = Av}. Clearly if pu − pv ∈ IA then u, v belong
to the same fiber. A binomial pu − pv is called an indispensable binomial if F(u) = {u, v}
and supp(u) ∩ supp(v) = ∅. The set of all indispensable binomials is denoted S(A). A
0
0
binomial pu − pv ∈ IA is called primitive if there is no other binomial pu − pv ∈ IA such
0
0
that pu |pu and pv |pv . The set of all primitive binomials in IA is called the Graver basis
of A, and denoted Gr(A). The universal Gröbner basis of A is a subset of the Graver
basis, and the set of indispensable binomials are a subset of the universal Gröbner basis.
The set of indispensable binomials appear in every binomial minimal generating set of IA .
This leads to the following definition:
Definition 2.1. The toric ideal IA is strongly robust if S(A) = Gr(A).
In [PTV15] strongly robust toric ideals are called ∅-Lawrence. Clearly every strongly
robust toric ideal is robust. Boocher et al [BBD+ 15] wonder (Question 6.1) if robust
implies strongly robust for toric ideals, and prove this is true in some instance associated
to graphs.
One useful tool for analyzing the Graver bases of IA , is its connection to the Lawrence
lifting. Recall that the definition of the Lawrence lifting from the introduction. Its toric
ideal IΛ(A) we consider to be in the ring K[p, q] with 2n indeterminates. Binomials in IΛ(A)
have the form pu q v − pv q u such that pu − pv ∈ IA .
Theorem 2.2. [Stu96, Alg 7.2] Let A ∈ Zd×n . Let M = {pui q vi − pvi q ui : i = 1, . . . , m} be
a binomial minimal generating set of the toric ideal IΛ(A) . Then {pui − pvi : i = 1, . . . , m}
is the Graver basis of IA .
A key tool for studying toric ideals in codimension 2 are the reduced Gale diagrams.
These were used by Peeva and Sturmfels [PS98] to give a compete description of the free
resolution of codimension 2 toric ideals. We define them now:
Let A ∈ Z(n−2)×n be a matrix of rank n − 2 and B the resulting Gale configuration.
Let B = {b1 , . . . , bn } be the resulting list of row vectors, with bi = (bi1 , bi2 ). The reduced

4

SETH SULLIVANT

Gale configuration B̃ = {b̃1 , . . . , b̃n } is obtained by setting
b̃i = gcd(bi1 , bi2 )−1 (−bi2 , bi1 ).
That is, B̃ is obtained from B by rotating the vectors by 90 degrees and scaling so that
elements in each vector are relatively prime. For the notion of a minimal generating set
to be meaningful, we need to assume that the toric ideal IA is positively graded. In terms
of the reduced Gale configuration, this means that there is no nonzero vector w ∈ Q2
such that wT b̃i > 0 for all i. With this assumption, the vectors b̃i can be ordered in such
a way that each pair b̃i , b̃i+1 span a cone such that no other b̃j lies in the interior of the
cone (where b̃n+1 = b̃1 ).
For each cone cone(b̃i , b̃i+1 ), let Hi be its Hilbert basis, which is the minimum generating set of the monoid cone(b̃i , b̃i+1 ) ∩ Z2 . Define the Hilbert basis of the reduced Gale
configuration to be the set:
HA = {u ∈ Z2 : both u and − u are in H1 ∪ H2 ∪ · · · ∪ Hn }.
Theorem 2.3. [PS98, Theorem 3.7] Let A ∈ Z(n−2)×n have rank n − 2, and B the Gale
configuration. A vector u ∈ Z2 is in HA if and only if p(Bu)+ − p(Bu)− is an indispensable
binomial of the toric ideal IA . Furthermore, the indispensable binomials are a generating
set for IA , unless there are no indispensable binomials, in which case IA is a complete
intersection.
Hilbert bases are complicated to compute for general cones, but in dimension 2 there
is a particularly simple geometric description.
Proposition 2.4. Let a, b ∈ Z2 and let P = cone(a, b). The Hilbert basis of P consists
of all lattice points in the polyhedron conv((P ∩ Z2 ) \ {(0, 0)}) that are visible from the
origin.
Combining Theorems 2.2 and 2.3, the Graver basis of A can also be characterized in
terms of the reduced Gale configuration.
Corollary 2.5. Let A ∈ Z(n−2)×n have rank n − 2, and B the Gale configuration. Suppose
that kerZ A ∩ Nn = {0}. A vector u ∈ Z2 has either u or − u ∈ H1 ∪ · · · ∪ Hn if and only
if p(Bu)+ − p(Bu)− is a primitive binomial of the toric ideal IA .
Proof. For the Gale configuration B of A, define B ± := B ∪ −B, which is the Gale
configuration of the Lawrence lifting Λ(A), and let B̃ ± be its reduced Gale configuration.
As for B, we assume that the elements of B̃ ± are ordered so that each cone cone(b̃i , b̃i+1 )
no other b̃j lies in its interior. Let Hi± be the Hilbert basis of cone(b̃i , b̃i+1 ). Since B̃ ±
is centrally symmetric, the Hilbert basis of the resulting Lawrence configuration Λ(A)
will be the union of all the Hi± . By Theorem 2.3 these vectors determine the minimal
generating set of IΛ(A) . By Theorem 2.2 those vectors then determine the Graver basis of
IA . So to prove the corollary, we need to show that every u in some Hi± , either u or −u
appears in H1 ∪ · · · ∪ Hn .
So let u ∈ Hi± . If b̃i and b̃i+1 are both in B or both in −B, then cone(b̃i , b̃i+1 ) or
cone(−b̃i , −b̃i+1 ) is one of the cones described in the Hilbert basis of A, so u or −u

STRONGLY ROBUST TORIC IDEALS IN CODIMENSION 2

5

belongs to H1 ∪ · · · ∪ Hn . This leaves the case that b̃i ∈ B and b̃i+1 ∈ −B (the reverse
situation follows from a symmetric argument). Looking at the ordering on B, there will
be a unique smallest j such that b̃j ∈ B and cone(b̃i , b̃j ) forms one of the cones for
computing H1 ∪ · · · ∪ Hn . Similarly, the there is a unique largest k such that −b̃k ∈ B
and cone(−b̃k , −b̃i+1 ) forms one of the cones for computing H1 ∪ · · · ∪ Hn . These vectors
are guaranteed to exist by the positive grading assumption that Clearly, we have that
kerZ A ∩ Nn = {0}.
cone(b̃i , b̃i+1 ) = cone(b̃i , b̃j ) ∩ cone(b̃k , b̃i+1 ).
Furthermore, if we let
Pi,i+1 = conv(cone(b̃i , b̃i+1 ) ∩ Z2 \ {(0, 0)})
and defined Pi,j and Pk,i+1 similarly, then we have that
Pi,i+1 = Pi,j ∩ Pk,i+1 .
Since each of Pi,i+1 , Pi,j , and Pk,i+1 is the convex hull of lattice points, the lattice points
visible from the origin in Pi,i+1 , will be either a lattice point visible from the origin in Pi,j
or in Pk,i+1 , or both. In the case that u ∈ Pi,i+1 is a lattice point visible from the origin
with u ∈ Pi,j , then u ∈ H1 ∪ · · · ∪ Hn . In the case that u ∈ Pi,i+1 is a lattice point visible
from the origin with u ∈ Pk,i+1 then −u ∈ H1 ∪ · · · ∪ Hn .

Corollary 2.5 then reduces the problem of characterizing strongly robust toric ideals in
codimension 2 to the following problem.
Problem 2.6. For which rank n − 2 matrices A ∈ Z(n−2)×n is the Hilbert basis HA equal
to H1 ∪ H2 ∪ · · · ∪ Hn ?
The answer is contained in the following Lemma.
Lemma 2.7. Let A ∈ Z(n−2)×n have rank n − 2 and B̃ the reduced Gale diagram. Then
IA is strongly robust if and only if for each bi ∈ B̃, −bi ∈ HA .
Proof. Clearly the condition of the theorem is necessary since bi itself always belongs to
H1 ∪ · · · ∪ Hn . On the other hand, if −bi ∈ HA but −bi ∈
/ B, we can add it to B without
changing HA . Indeed, if cone(bj , bj+1 ) contains −bi as a visible lattice point of Pj,j+1 ,
then the visible lattice points arising in the cones cone(bj , −bi ) and cone(−bi , bj+1 ) are
precisely the visible lattice points in Pj,j+1 . By repeating this procedure, we end up with
a Gale diagram that contains only pairs bi , −bi , which is the Gale diagram of a Lawrence
matrix. Hence, IA is strongly robust.

Now we are in a position to Prove Theorem 1.2.
Proof of Theorem 1.2. Suppose that IA is a strongly robust toric ideal in codimension 2,
let B̃ be the reduced Gale configuration, and P = conv(B̃) the convex hull of the elements
in B̃. Let b̃ be a vertex of P . We must show that −b̃ is also a vertex of P to see that P
is centrally symmetric.
Since b̃ ∈ B, and IA is strongly robust, −b̃ belongs to HA , by Lemma 2.7. If −b̃ is not
a vertex of P , then there are two vectors b1 , b2 ∈ B̃ such that −b̃ is in conv(b1, b2, (0, 0)).

6

SETH SULLIVANT

Figure 1. The reduced Gale transform of the matrix in Example 2.8. The
dots represent the points in the set HA .
Applying Lemma 2.7 again, we have the −b1 and −b2 are in HA . In particular, these two
vectors are in P , by Proposition 2.4. However, this forces that b̃ ∈ conv(−b1, −b2, (0, 0)),
so b̃ could not be a vertex of P .

Proof of Corollary 1.3. Since the polytope conv(B̃) must be two dimensional and is centrally symmetric, it must have at least two pairs of opposite vertices b̃1 , −b̃1 and b̃2 , −b̃2 .
These two pairs of opposite vertices yield two mixed bouquets of the matrix A.

Example 2.8. Let A be the matrix


1
0
A=
0
−2

0
1
1
0

1
0
0
0

0 0
0 1
1 0
0 −4


0
0

1
5

which has the Gale transform B and reduced Gale transform B̃ respectively:




1
2
−2 1
−2 1 
−1 −2




−1 −2
 2 −1
B̃ = 
B=


0
 0 −1
1
 2 −1
1
2
2
0
0
1
As can be see from the reduced Gale transform, illustrated in Figure 1, the matrix A
satisfies the condition of Lemma 2.7, and so the toric ideal is strongly robust. The minimal
generating set, which equals the Graver basis, consists of the following 6 binomials that
are in bijection with pairs of opposite lattice points in HA :
IA = hb5 − de5 f 4 , ae2 f 2 − b2 c, ab3 − cde3 f 2 , a2 b − c2 de, a3 ef 2 − bc3 d, a5 f 2 − c5 d2 i.
For example, the binomial a3 ef 2 − bc3 d corresponds to the point u = (1, 1) in the Gale
diagram, since Bu = (3, −1, −3, −1, 1, 2)T .

STRONGLY ROBUST TORIC IDEALS IN CODIMENSION 2

7

Acknowledgments
Seth Sullivant was partially supported by the David and Lucille Packard Foundation
and the US National Science Foundation (DMS 1615660).
References
[AB16]

Federico Ardila and Adam Boocher. The closure of a linear space in a product of lines. J.
Algebraic Combin., 43(1):199–235, 2016. http://dx.doi.org/10.1007/s10801-015-0634-x.
[BBD+ 15] Adam Boocher, Bryan Christopher Brown, Timothy Duff, Laura Lyman, Takumi Murayama,
Amy Nesky, and Karl Schaefer. Robust graph ideals. Ann. Comb., 19(4):641–660, 2015. http:
//dx.doi.org/10.1007/s00026-015-0288-3.
[BR15]
Adam Boocher and Elina Robeva. Robust toric ideals. J. Symbolic Comput., 68(1):254–264,
2015. http://dx.doi.org/10.1016/j.jsc.2014.09.019.
[BZ93]
David Bernstein and Andrei Zelevinsky. Combinatorics of maximal minors. J. Algebraic Combin., 2(2):111–121, 1993. http://dx.doi.org/10.1023/A:1022492222930.
[DS98]
Persi Diaconis and Bernd Sturmfels. Algebraic algorithms for sampling from conditional distributions. Ann. Statist., 26(1):363–397, 1998. http://dx.doi.org/10.1214/aos/1030563990.
[PS98]
Irena Peeva and Bernd Sturmfels. Syzygies of codimension 2 lattice ideals. Math. Z.,
229(1):163–194, 1998. http://dx.doi.org/10.1007/PL00004645.
[PTV15] Sonja Petrovic, Apostolos Thoma, and Marius Vladoiu. Bouquet algebras of toric ideals.
https://arxiv.org/abs/1507.02740, 2015.
[Stu96]
Bernd Sturmfels. Gröbner bases and convex polytopes, volume 8 of University Lecture Series.
American Mathematical Society, Providence, RI, 1996.
[SZ93]
Bernd Sturmfels and Andrei Zelevinsky. Maximal minors and their leading terms. Adv. Math.,
98(1):65–112, 1993. http://dx.doi.org/10.1006/aima.1993.1013.
[TA05]
Akimichi Takemura and Satoshi Aoki. Distance-reducing Markov bases for sampling from
a discrete sample space. Bernoulli, 11(5):793–813, 2005. http://dx.doi.org/10.3150/bj/
1130077594.
Department of Mathematics, North Carolina State University, Raleigh, NC 27695
E-mail address: smsulli2@ncsu.edu

