REVERSE LEXICOGRAPHIC GRÖBNER BASES AND STRONGLY KOSZUL TORIC RINGS
KAZUNORI MATSUDA and HIDEFUMI OHSUGI
Abstract
Restuccia and Rinaldo proved that a standard gradedK-algebraK[x1, . . . , xn]/I is strongly Koszul if the reduced Gröbner basis ofIwith respect to any reverse lexicographic order is quad- ratic. In this paper, we give a sufficient condition for a toric ringK[A] to be strongly Koszul in terms of the reverse lexicographic Gröbner bases of its toric idealIA. This is a partial extension of a result given by Restuccia and Rinaldo.
In addition, we show that any strongly Koszul toric ring generated by squarefree monomials is compressed. Using this fact, we show that our sufficient condition forK[A] to be strongly Koszul is both necessary and sufficient whenK[A] is generated by squarefree monomials.
Introduction
Herzog, Hibi, and Restuccia [9] introduced the notion of strongly Koszul algebras. Let R be a standard graded K-algebra with the graded maximal idealᒊ. ThenRis said to bestrongly Koszul ifᒊadmits a minimal system of generatorsu1, . . . , unof the same degree such that for any 1≤i1<· · ·<
ir ≤nand for allj =1,2, . . . , r, the colon ideal(ui1, . . . , uij−1):uij ofRis generated by a subset of{u1, . . . , un}. Inspired by this notion, Conca, Trung, and Valla [4] introduced the notion of Koszul filtrations. A familyF of ideals ofRis called aKoszul filtrationifF satisfies (i) everyI ∈F is generated by linear forms; (ii)(0)andᒊare inF; and (iii) for each non-zero idealI ∈F, there existsJ ∈F withJ ⊂ I such thatI /J is cyclic andJ : I ∈ F. For example, ifR is strongly Koszul, thenF = {(0)} ∪ {(ui1, . . . , uir) | 1 ≤ i1<· · ·< ir ≤n,1≤r ≤n}is a Koszul filtration ofR. The existence of a Koszul filtration ofR is an effective sufficient condition forRto be Koszul.
Some classes of Koszul algebras which have special Koszul filtrations have been studied, e.g., universally Koszul algebras [2] and initially Koszul algebras [1].
On the other hand, it is important to characterize the Koszulness in terms of the Gröbner bases of its defining ideal. It is a well-known fact that ifRis G-quadratic (i.e., its defining ideal has a quadratic Gröbner basis) thenR is
Received 4 March 2014
Koszul. Conca, Rossi, and Valla [3] proved that, ifRis initially Koszul, then R is G-quadratic. Moreover, they and Blum gave a necessary and sufficient condition forR to be initially Koszul in terms of initial ideals of toric ideals ([1], [3]).
LetA= {u1, . . . , un}be a set of monomials of the same degree in a poly- nomial ringK[T] = K[t1, . . . , td] in d variables over a field K. Then the toric ringK[A] ⊂ K[T] is a semigroup ring generated by the set Aover K. Let K[X] = K[x1, . . . , xn] be a polynomial ring in n variables over K. The toric ideal IA of K[A] is the kernel of the surjective homomorph- ism π:K[X] → K[A] defined by π(xi) = ui for each 1 ≤ i ≤ n. Then we haveK[A] K[X]/IA. A toric ringK[A] is called compressed [16] if
√in<(IA)=in<(IA)for any reverse lexicographic order<.
In this paper, we study Gröbner bases of toric ideals of strongly Koszul toric rings. First, in Section 1, we give a sufficient condition for K[A] to be strongly Koszul in terms of the Gröbner bases ofIA (Theorem 1.2). We then have Corollary 1.3, i.e., if the reduced Gröbner basis ofIAwith respect to any reverse lexicographic order is quadratic, thenK[A] is strongly Koszul [15, Theorem 2.7]. On the other hand, Examples 1.6 and 1.7 are counterexamples of [15, Conjecture 3.11] (i.e., counterexamples of the converse of Corollary 1.3).
In Section 2, we discuss strongly Koszul toric rings generated by squarefree monomials. We show that such toric rings are compressed (Theorem 2.1).
Using this fact, we show that the sufficient condition forK[A] to be strongly Koszul in Theorem 1.2 is both necessary and sufficient when the toric rings are generated by squarefree monomials (Theorem 2.3).
1. Gröbner bases and strong Koszulness
First, we give a sufficient condition for toric rings to be strongly Koszul in terms of the reverse lexicographic Gröbner bases. We need the following lemma:
Lemma1.1.Suppose that, for each1≤i < j ≤n, there exists a monomial order≺such that, with respect to≺, an arbitrary binomialgin the reduced Gröbner basis ofIAsatisfies the following conditions:
(i) xi |in≺(g)andxj in≺(g)⇒g =xixk−xjxfor some1≤k, ≤n, (ii) xj |in≺(g)andxi in≺(g)⇒g =xjx−xixkfor some1≤k, ≤n.
Then,K[A]is strongly Koszul.
Proof. Suppose thatK[A] is not strongly Koszul. By [9, Proposition 1.4], there exists a monomialuk1· · ·uksof a minimal set of generators of(ui)∩(uj) such thats ≥3. Sinceuk1· · ·uks belongs to(ui)∩(uj), there exist binomials xk1· · ·xks−xiXα andxk1· · ·xks−xjXβ inIA. LetGbe the reduced Gröbner basis ofIA with respect to≺. SincexiXα −xjXβ ∈IAis reduced to 0 with
respect to G, it follows that bothxiXα and xjXβ are reduced to the same monomialmwith respect toG.
Suppose that g ∈ G is used in the computation xiXα→G m and that xi
divides in≺(g). Ifxj divides in≺(g), then it follows thatxk1· · ·xks −xixjXγ belongs toIA. Thus,uiuj dividesuk1· · ·uks. This contradicts thatuk1· · ·uks belongs to a minimal set of generators of (ui)∩(uj). If xj does not divide in≺(g), theng = xixk −xjx by assumption (i). Hence, uiuk ∈ (ui)∩(uj) dividesuk1· · ·uks. This contradicts thatuk1· · ·uks belongs to a minimal set of generators of(ui)∩(uj).
Therefore,xinever appears in the initial monomials ofg∈Gwhich are used in the computationxiXα →G m. Hence,xidividesm. By the same argument, it follows thatxjnever appears in the initial monomials ofg ∈Gwhich are used in the computationxjXβ →G m, and hence,xj dividesm. Thus, xixj divides m, which means thatuiuj dividesuk1· · ·uks. This contradicts thatuk1· · ·uks belongs to a minimal set of generators of(ui)∩(uj).
Let G(I ) denote the (unique) minimal set of monomial generators of a monomial ideal I. Given an ordering xi1 < xi2 < · · · < xin of variables {x1, . . . , xn}, let<rlex denote the reverse lexicographic order induced by the ordering<.
Theorem 1.2. Suppose that, for each 1 ≤ i < j ≤ n, there exists an orderingxi1 < xi2 <· · ·< xin with{i1, i2} = {i, j}, such that any monomial inG(in<rlex(IA))∩(xi2)is quadratic. Then,K[A]is strongly Koszul.
Proof. We may assume thatxj < xi. By Lemma 1.1, it is enough to show that<rlexsatisfies conditions (i) and (ii) in Lemma 1.1. Letg be an arbitrary (irreducible) binomial in the reduced Gröbner basis ofIAwith respect to<rlex. Sincexj is the smallest variable,xj does not divide in<rlex(g). Hence,<rlex
satisfies condition (ii). Suppose thatxi divides in<rlex(g). By the assumption for<, deg(in<rlex(g))=2. Hence,g=xixp−xqxr for some 1≤p, q, r≤n.
Sincexqxr <rlex xixp, we havej ∈ {q, r}, and hence,<rlex satisfies condi- tion (i).
As a corollary, in case of toric rings, we have a result of Restuccia and Rinaldo [15, Theorem 2.7]:
Corollary1.3.Suppose that the reduced Gröbner basis ofIAis quadratic with respect to any reverse lexicographic order. Then,K[A]is strongly Koszul.
Example1.4. LetK[An] = K[s, t1s, . . . , tns, t1−1s, . . . , tn−1s]. Then,IAn is the kernel of the surjective homomorphismπ:K[X]→K[An] defined by
π(z) = s, π(xi) = tis, and π(yi) = ti−1s. It is easy to see that K[An] is isomorphic to
K[A±G]=K
s, t1tn+1s, . . . , tntn+1s, t1−1tn−+11s, . . . , tn−1tn−+11s ,
whereA±Gis thecentrally symmetric configuration[13] ofAGassociated with the star graphG = K1,n withn+1 vertices. By [13, Theorem 4.4],IAn is generated by F = {xiyi − z2 | i = 1,2, . . . , n}. Then, the Buchberger criterion tells us that the setF ∪ {xiyi −xjyj |1≤i < j ≤n}is a Gröbner basis ofIAnwith respect to any monomial order (i.e., a universal Gröbner basis ofIAn). Thus, by Corollary 1.3,K[An] is strongly Koszul for alln∈N.
Eliminating the variablezfromF, by the same argument above, it follows that the toric ringK[Bn]=K[t1s, . . . , tns, t1−1s, . . . , tn−1s] is strongly Koszul for alln∈N. Note thatK[Bn] is isomorphic to some toric ring generated by squarefree monomials.
Remark1.5. A standard graded K-algebra R is said to bec-universally Koszul[6] if the set of all ideals ofR which are generated by subsets of the variables is a Koszul filtration of R. Ene, Herzog, and Hibi proved that a toric ringK[A] isc-universally Koszul if the reduced Gröbner basis ofIAis quadratic with respect to any reverse lexicographic order [6, Corollary 1.4].
However, it is known that a toric ringK[A] isc-universally Koszul if and only ifK[A] is strongly Koszul. See [14, Definition 7.2] or [11, Lemma 3.18]. So, [6, Corollary 1.4] is equivalent to Corollary 1.3.
In Section 2, we will show that the converse of Theorem 1.2 holds when K[A] is generated by squarefree monomials. However, the converse does not hold in general.
Example1.6. It is known [9] that any Veronese subring of a polynomial ring is strongly Koszul. LetK[A] be the fourth Veronese subring ofK[t1, t2], i.e.,K[A]=K[t14, t13t2, t12t22, t1t23, t24]. ThenIAis generated by the binomials
x3x5−x42, x1x3−x22, x32−x2x4, x1x5−x2x4, x2x3−x1x4, x3x4−x2x5. Let<be an ordering of variables such thatxi1 < xi2 < xi3 < xi4 < xi5 with {i1, i2} = {2,4}. Since bothx23−x12x4andx43−x2x52belong toIA, it is easy to see that eitherx23orx43belongs toG(in<rlex(IA))∩(xi2). Thus,IAdoes not satisfy the hypothesis of Theorem 1.2.
On the other hand, the converse of Corollary 1.3 does not hold even if K[A] is generated by squarefree monomials. Note that Examples 1.6 and 1.7 are counterexamples to [15, Conjecture 3.11].
Example1.7. LetK[A]=K[t4, t1t4, t2t4, t3t4, t1t2t4, t2t3t4, t1t3t4, t1t2t3t4], which is the toric ring of the stable set polytope of the empty graph with three vertices. Since any empty graph istrivially perfect (see also Example 2.2), K[A] is strongly Koszul. See [10] for the details. The toric idealIA is gener- ated by the binomials
x1x5−x2x3, x1x6−x3x4, x1x7−x2x4, x5x6−x3x8, x6x7−x4x8, x5x7−x2x8, x1x8−x4x5, x2x6−x4x5, x3x7−x4x5.
Let < be an ordering x4 < x3 < x2 < x1 < x8 < x7 < x6 < x5. Since, with respect to <rlex, the initial monomial (i.e., the first monomial) of any quadratic binomial above does not divide the initial monomialx2x3x8 ofx4x52−x2x3x8 ∈IA, we havex2x3x8 ∈ G(in<rlex(IA)). Thus, the reduced Gröbner basis ofIAwith respect to<rlexis not quadratic. Below, we show that Theorem 2.3 guarantees thatIA satisfies the hypothesis of Theorem 1.2. See also Example 2.2.
2. Strongly Koszul toric rings generated by squarefree monomials In this section, we consider the case whenK[A] issquarefree, i.e.,K[A] is isomorphic to a semigroup ring generated by squarefree monomials. A toric ringK[A] is calledcompressed [16] if√
in<(IA)= in<(IA)for any reverse lexicographic order<. It is known thatK[A] is normal if it is compressed.
Theorem2.1.Suppose thatK[A]is strongly Koszul. Then, the following conditions are equivalent:
(i) K[A]is squarefree;
(ii) IAhas no quadratic binomial of the formxi2−xjxk; (iii) K[A]is compressed.
In particular, any squarefree strongly Koszul toric ring is compressed.
Proof. First, (i)⇒(ii) is trivial. By [16, Theorem 2.4], we have (iii)⇒(i).
Thus it is enough to show (ii)⇒(iii).
Let K[A] be a strongly Koszul toric ring such that IA has no quadratic binomial of the formxi2−xjxk. Suppose that an irreducible binomialf = xi2Xα −xjXβ belongs to the reduced Gröbner basis of IA with respect to a reverse lexicographic order<rlex and that xj is the smallest variable inf. Then,u2iUα belongs to (Uα)∩(uj). SinceK[A] is strongly Koszul, by [9, Corollary 1.5], (Uα)∩(uj) is generated by the element in(Uα)∩(uj) of degree≤ deg(Xα)+1. Hence,u2iUα is generated by such elements. Thus, there exist binomialsxi2Xα −Xαxkx andxi2Xα −xjXγx in IA. Then, we havexi2−xkx ∈ IA. By assumption, we havexi2−xkx = 0, and hence,
i=k =. Thus, the binomialg=xiXα−xjXγ belongs toIA. Sincexj is the smallest variable inf, it follows thatxiXα is the initial monomial ofg. This contradicts thatf appears in the reduced Gröbner basis ofIAwith respect to
<rlex. Hence,K[A] is compressed.
Example2.2. LetGbe a simple graph on the vertex setV (G)= {1, . . . , d} with the edge setE(G). A subsetS ⊂ V (G) is said to bestableif{i, j} ∈/ E(G)for all i, j ∈ S. For each stable setS ofG, we define the monomial uS =td+1
i∈Sti inK[t1, . . . , td+1]. Then the toric ringK[QG] generated by {uS |Sis a stable set ofG}over a fieldKis called the toric ring of thestable set polytopeofG. It is known that
• K[QG] is compressed⇐⇒Gis perfect ([12, Example 1.3 (c)], [8]).
• K[QG] is strongly Koszul⇐⇒Gis trivially perfect ([10, Theorem 5.1]).
Here, a graphGis said to beperfectif the size of maximal clique ofGWequals to the chromatic number ofGWfor any induced subgraphGWofG, and a graph Gis said to betrivially perfectif the size of maximal stable set ofGW equals to the number of maximal cliques ofGW for any induced subgraphGW ofG.
(For the standard terminologies of graph theory, see [5].) Since any trivially perfect graph is perfect [7], these facts are consistent with Theorem 2.1. On the other hand, with respect to somelexicographic order, the initial ideal of the toric ideal in Example 1.7 is not generated by squarefree monomials.
Using Theorem 2.1, we now show that the converse of Theorem 1.2 holds whenK[A] is squarefree.
Theorem2.3.Suppose that K[A]is squarefree and strongly Koszul. Let 1≤i < j ≤n, and let<be any ordering of variables satisfying
xj < xi <{xk |uiuk/uj ∈K[A], k =j}<other variables.
Then, any monomial inG(in<rlex(IA))∩(xi)is quadratic.
Proof. Let G be the reduced Gröbner basis ofIA with respect to <rlex. Suppose thatxiXα ∈G(in<rlex(IA))∩(xi)is not quadratic. Then, there exists a binomialg =xiXα−xjXβ inG. Note that in<rlex(g)=xiXα is squarefree by Theorem 2.1. Hence,Xαis not divisible byxi. Moreover, sinceGis reduced, Xα is not divisible byxj.
Sinceg belongs to IA, it follows thatuiUα = ujUβ belongs to the ideal (ui)∩(uj). Then,uiUα is generated byuiuk = uju ∈ (ui)∩(uj)for some 1≤k, ≤n. Thus, there exist binomialsxiXα−xixkXγ andxiXα−xjxXγ inIA. Then, we haveXα−xkXγ ∈IA.Ifk ∈ {i, j}, thenXα ∈in<rlex(IA). This contradictsxiXα ∈G(in<rlex(IA)). Hence,k /∈ {i, j}. Then, 0=xixk−xjx∈ IA and in<rlex(xixk−xjx)=xixk. SincexiXα is not divisible byxixk,Xαis
not divisible byxk. In particular, 0 =Xα−xkXγ ∈ IAandXα <rlex xkXγ. Sinceuiuk/uj = u,xk belongs to{xk |uiuk/uj ∈K[A], k =j}. Thus, the smallest variablexmappearing inXα belongs to{xk |uiuk/uj ∈K[A], k = j}. Letum = uium/uj. Then,xixm−xjxm (= 0)belongs toIA. Therefore, xixmbelongs to in<rlex(IA)and dividesxiXα, which is a contradiction.
By Theorem 2.3, we can check whether a squarefree toric ringK[A] = K[u1, . . . , un] is strongly Koszul by computing the reverse lexicographic Gröbner bases ofIAat mostn(n−1)/2 times.
Acknowledgement. This research was supported by the JST (Japan Sci- ence and Technology Agency) CREST (Core Research for Evolutional Science and Technology) research project Harmony of Gröbner Bases and the Mod- ern Industrial Society, within the framework of the JST Mathematics Program
“Alliance for Breakthrough between Mathematics and Sciences”.
REFERENCES
1. Blum, S.,Initially Koszul algebras, Beiträge Algebra Geom. 41 (2000), no. 2, 455–467.
2. Conca, A.,Universally Koszul algebras, Math. Ann. 317 (2000), no. 2, 329–346.
3. Conca, A., Rossi, M. E., and Valla, G.,Gröbner flags and Gorenstein algebras, Compositio Math. 129 (2001), no. 1, 95–121.
4. Conca, A., Trung, N. V., and Valla, G.,Koszul property for points in projective spaces, Math.
Scand. 89 (2001), no. 2, 201–216.
5. Diestel, R.,Graph theory, fourth ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010.
6. Ene, V., Herzog, J., and Hibi, T.,Linear flags and Koszul filtrations, Kyoto J. Math. 55 (2015), no. 3, 517–530.
7. Golumbic, M. C.,Trivially perfect graphs, Discrete Math. 24 (1978), no. 1, 105–107.
8. Gouveia, J., Parrilo, P. A., and Thomas, R. R.,Theta bodies for polynomial ideals, SIAM J. Optim. 20 (2010), no. 4, 2097–2118.
9. Herzog, J., Hibi, T., and Restuccia, G.,Strongly Koszul algebras, Math. Scand. 86 (2000), no. 2, 161–178.
10. Matsuda, K.,Strong Koszulness of toric rings associated with stable set polytopes of trivially perfect graphs, J. Algebra Appl. 13 (2014), no. 4, 1350138, 11 pp.
11. Murai, S.,Free resolutions of lex-ideals over a Koszul toric ring, Trans. Amer. Math. Soc.
363 (2011), no. 2, 857–885.
12. Ohsugi, H. and Hibi, T.,Convex polytopes all of whose reverse lexicographic initial ideals are squarefree, Proc. Amer. Math. Soc. 129 (2001), no. 9, 2541–2546.
13. Ohsugi, H. and Hibi, T.,Centrally symmetric configurations of integer matrices, Nagoya Math. J. 216 (2014), 153–170.
14. Peeva, I.,Infinite free resolutions over toric rings, Syzygies and Hilbert functions, Lect. Notes Pure Appl. Math., vol. 254, Chapman & Hall/CRC, Boca Raton, FL, 2007, pp. 233–247.
15. Restuccia, G. and Rinaldo, G.,On certain classes of degree reverse lexicographic Gröbner bases, Int. Math. Forum 2 (2007), no. 21-24, 1053–1068.
16. Sullivant, S.,Compressed polytopes and statistical disclosure limitation, Tohoku Math. J. (2) 58 (2006), no. 3, 433–445.
DEPARTMENT OF PURE AND APPLIED MATHEMATICS GRADUATE SCHOOL OF INFORMATION SCIENCE AND TECHNOLOGY
OSAKA UNIVERSITY SUITA
OSAKA 565-0871 JAPAN
E-mail:kaz-matsuda@ist.osaka-u.ac.jp
MATHEMATICAL SCIENCES
FACULTY OF SCIENCE AND TECHNOLOGY KWANSEI GAKUIN UNIVERSITY SANDA
HYOGO 669-1337 JAPAN
E-mail:ohsugi@kwansei.ac.jp