• Ingen resultater fundet

View of Reverse Lexicographic Gröbner Bases and Strongly Koszul Toric Rings

N/A
N/A
Info
Hent
Protected

Academic year: 2022

Del "View of Reverse Lexicographic Gröbner Bases and Strongly Koszul Toric Rings"

Copied!
8
0
0

Indlæser.... (se fuldtekst nu)

Hele teksten

(1)

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<· · ·<

irnand 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) everyIF is generated by linear forms; (ii)(0)andᒊare inF; and (iii) for each non-zero idealIF, there existsJF withJI such thatI /J is cyclic andJ : IF. For example, ifR is strongly Koszul, thenF = {(0)} ∪ {(ui1, . . . , uir) | 1 ≤ i1<· · ·< irn,1≤rn}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

(2)

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 ≤ in. 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 < jn, there exists a monomial ordersuch that, with respect to, an arbitrary binomialgin the reduced Gröbner basis ofIAsatisfies the following conditions:

(i) xi |in(g)andxj in(g)g =xixkxjxfor some1≤k, n, (ii) xj |in(g)andxi in(g)g =xjxxixkfor 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· · ·xksxiXα andxk1· · ·xksxjXβ inIA. LetGbe the reduced Gröbner basis ofIA with respect to≺. SincexiXαxjXβIAis reduced to 0 with

(3)

respect to G, it follows that bothxiXα and xjXβ are reduced to the same monomialmwith respect toG.

Suppose that gG is used in the computation xiXαG m and that xi

divides in(g). Ifxj divides in(g), then it follows thatxk1· · ·xksxixjXγ 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 = xixkxjx 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 ofgGwhich are used in the computationxiXαG m. Hence,xidividesm. By the same argument, it follows thatxjnever appears in the initial monomials ofgGwhich 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 < jn, 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=xixpxqxr for some 1≤p, q, rn.

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, t11s, . . . , tn1s]. Then,IAn is the kernel of the surjective homomorphismπ:K[X]K[An] defined by

(4)

π(z) = s, π(xi) = tis, and π(yi) = ti1s. It is easy to see that K[An] is isomorphic to

K[A±G]=K

s, t1tn+1s, . . . , tntn+1s, t11tn+11s, . . . , tn1tn+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 = {xiyiz2 | i = 1,2, . . . , n}. Then, the Buchberger criterion tells us that the setF ∪ {xiyixjyj |1≤i < jn}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, t11s, . . . , tn1s] 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

x3x5x42, x1x3x22, x32x2x4, x1x5x2x4, x2x3x1x4, x3x4x2x5. Let<be an ordering of variables such thatxi1 < xi2 < xi3 < xi4 < xi5 with {i1, i2} = {2,4}. Since bothx23x12x4andx43x2x52belong 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].

(5)

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

x1x5x2x3, x1x6x3x4, x1x7x2x4, x5x6x3x8, x6x7x4x8, x5x7x2x8, x1x8x4x5, x2x6x4x5, x3x7x4x5.

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 ofx4x52x2x3x8IA, we havex2x3x8G(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 formxi2xjxk; (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 formxi2xjxk. 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 havexi2xkxIA. By assumption, we havexi2xkx = 0, and hence,

(6)

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 subsetSV (G) is said to bestableif{i, j} ∈/ E(G)for all i, jS. For each stable setS ofG, we define the monomial uS =td+1

iSti 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 < jn, and let<be any ordering of variables satisfying

xj < xi <{xk |uiuk/ujK[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=xixkxjxIA and in<rlex(xixkxjx)=xixk. SincexiXα is not divisible byxixk,Xαis

(7)

not divisible byxk. In particular, 0 =XαxkXγIAandXα <rlex xkXγ. Sinceuiuk/uj = u,xk belongs to{xk |uiuk/ujK[A], k =j}. Thus, the smallest variablexmappearing inXα belongs to{xk |uiuk/ujK[A], k = j}. Letum = uium/uj. Then,xixmxjxm (= 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.

(8)

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

Referencer

RELATEREDE DOKUMENTER

A Change of China`s View of the International Order and Pushing for the Building of a Community with a Shared Future for Mankind..

s.t. It is again a linear programming problem, so nothing is gained with respect to ease of solution – we have no reason to believe that DP is any easier to solve than P. However,

Specifically we show that a spectral set possessing a spectrum that is a strongly periodic set must tile R by translates of a strongly periodic set depending only on the spectrum,

Given a quadratic string matcher that searches for the first occurrence of a pattern in a text, a partial evaluator specializes this string matcher with respect to a pattern and

Both views are discussed and illustrated in relation to three specifi c issues: (a) the concept of a dictionary of Economics; (b) the sources of lexicographic data used in

With the knowledge of how a dealer’s balance sheet is affected, we calculate the necessary haircut on the reverse repo the dealer will enter with the hedge fund for the dealer to meet

When you ask a Danish average 1 class in the first year of upper secondary school to write about their conceptions of learning you would get statements like the ones in Figure 2

We give a characteristic p proof of the Bott vanishing theo- rem [4] for projective toric varieties using that the Frobenius morphism on a toric variety lifts to characteristic p 2..