View of Strongly Koszul algebras

STRONGLY KOSZUL ALGEBRAS

JU«RGEN HERZOG, TAKAYUKI HIBI and GAETANA RESTUCCIA

Introduction

In this paper we introduce a condition for homogeneous K-algebras, which implies that these algebras are Koszul, that is, that their residue class field has a linear resolution.

Important classes of Koszul algebras, discovered by Fro«berg [5], are the K-algebras K‰x₁;. . .;x_nŠ=I, where the generators of I are quadratic mono- mials. As already observed in [4], any colon ideal of the form …xi1;. . .;xik†:xiK‡1 in a Fro«berg ring is generated by a subsequence of x₁;. . .;x_n. This observation, as indicated in [4], yields a simple proof of the fact that Fro«berg rings are Koszul.

In this paper we call a homogeneous K-algebraRstrongly Koszul, if the graded maximal ideal of R admits a minimal system of generators xˆx1;. . .;xnsuch that for each subsequence of the generators, a colon ideal as above, is again generated by a subsequence of x. In Section 1 we prove some basic properties of strongly Koszul algebras, and show in particularr, that any ideal generated by a partial sequence of xhas a linear resolution.

Analyzing the proof one finds a very explicit formula for the Poincare¨ series of an ideal generated by a subsequence ofx.

The notion of strongly Koszul algebras is particularly interesting for a homogeneous semigroupK‰SŠ. To each elements2S there is associated its divisor poset. It has been shown by Laudal and Sletsje [8] that the simplicial homology of the associated order complex is isomorphic to the sth graded component of Tor^K‰SŠ…K;K†. From this fact one deduces easily that K‰SŠ is Koszul if and only if all divisor posets are Cohen-Macaulay with respect to K; see for example [11] or [9]. On the other hand, the strongly Koszul prop- erty of K‰SŠ (with respect to the system of semigroup generators) is char- acterized by fact that all divisor posets of S are wonderful, see 1.4. In the same proposition it is also shown thatSis strongly Koszul if and only if the intersection of any two principal ideals…s1† \ …s2†of generators ofS is gen-

Received July 15, 1997.

erated in degree 2. We dot not know whether there is a natural bound for the degree of the generators of such intersections for arbitrary homogeneous semigroup rings. Denoting this bound byb…S†, it is clear thatb…S† ˆ2 if and ony ifS is strongly Koszul. In general one has, as noted in 1.7, thatb…S†is greater than or equal to the largest degree of a generating relation of the semigroupS. There is some computational evidence thatb…S† 3, ifShas a quadratic Gro«bner basis.

In Section 2 we show that Veronese subrings, tensor and Segre products of strongly Koszul semigroup rings are again strongly Koszul. Starting with polynomial rings and applying these operations in any order we arrive at semigroups which are strongly Koszul. We call the semigroups resulting from these operations ``elementary''. The non-elementary strongly Koszul algebras seem to be very rare. One such example is given in 1.6 (3). Due to their rarity a classification of the strongly Koszul algebras seems not to be impossible, and indeed, for restricted classes can be done.

In the following Sections 3 and 4 we prove that among the Hibi rings (these are K-algebras defined by lattices; see [6] and [7]), and among theK- algebras defined by bipartite graphs, the only strongly Koszul algebras are those which arise from polynomial rings by repeated tensor and Segre pro- duct operations.

The authors would like to thank E. De Negri and V. Welker for several discussions in connection with this paper.

1. Definition and basic properties of strongly Koszul algebras

LetK be a field, and let Rbe a homogeneousK-algebra, that is, a finitely generated gradedK-algebra which is generated overK by elements of degree 1. We denote bymthe graded maximal ofR.

Definition1.1. The homogeneousK-algebraRis calledstrongly Koszulif its graded maximal idealmadmits a minimal system of homogeneous gen- erators u1;. . .;un such that for all subsequences ui1;. . .;uir of u1; ;un with i1<i2<. . .<ir, and for alljˆ1;. . .;rÿ1, the colon ideal…ui1;. . .;uijÿ1†:uj

is generated by a subset of elements offu₁;. . .;u_ng.

The principal idea for the proof of the next theorem, which justifies our definition, can already been found in [4], where similar arguments are used in a more special situation.

Theorem 1.2.Let R be strongly Koszul with respect to the minimal homo- geneous system u₁. . .;u_n of generators of the graded maximal ideal mof R.

Then any ideal of the form…ui1;. . .;uir†has a linear resolution. In particular, R is Koszul.

Proof. Just as in [4] we call a graded R-module M linear if it admits a system of generators g₁;. . .;g_m, all of the same degree, such that for jˆ1;. . .;mthe colon ideals

…Rg₁‡. . .‡Rg_jÿ1†:g_jˆ fa2Rjag_j 2 …Rg₁‡. . .‡Rg_jÿ1†g are generated by subsets offu1;. . .;ung.

Notice that all the ideals…ui1;. . .;uir†are linear modules. Hence the theo- rem will be proved if we have shown that a linear module M has linear re- lations, and that the syzygy module of a linear module is again linear.

The first property is immediately clear. Indeed, if a₁g₁‡. . .‡a_mg_m is a homogeneous generating relation ofM, andajis the last non-zero coefficient of this relation, then aj is a generator of the colon ideal …Rg1‡. . .‡Rgjÿ1†:gj, and hence is of degree 1. Therefore, the relation is linear.

Let¹…M† denote the first syzygy module of M. We prove by induction on the number of generators of M, that ¹…M†is a linear module. If M is cyclic, then ¹…M† is an ideal generated by a subset of fu1;. . .;ung, and hence is linear. Now suppose that M is generated by the m elements g₁;. . .;g_m;m>1, for which M is linear. Then NˆRg₁‡. . .Rg_mÿ1 is also linear, and by induction hypothesis has a linear syzygy module¹…N†. Say, ¹…N† is linear with respect to its generators h₁;. . .;h_k. Now we build a suitable system of generators of¹…M†using the exact sequence

0!¹…N† !¹…M† !¹…M=N† !0:

The moduleM=N is cyclic with annihilator…Rg₁‡. . .‡Rg_mÿ1†:g_m, and so there exist 1i1 <i2 <. . .<ilnsuch that¹…M=N† ' …ui1. . .; uil†. Now we choose homogeneous elements hk‡1;. . .;hk‡l in ¹…M† mapping onto u_i1;. . .;u_il. We leave it to the reader to check that¹…M† is linear with re- spect to the generatorsh₁;. . .;h_k‡l.

One remarkable feature of Koszul algebras is that their Poincare¨ series is a rational function. Indeed, one has the following well-known identity

PK…t† HR…ÿt† ˆ1 for any Koszul algebra R. Here PM…t† ˆP

i0dimKTor^R_i…K;M†tⁱ denotes thePoincare¨ series, andHM…t† ˆP

i0dimKMitⁱ theHilbert series of a gra- dedR-moduleM. One proves the identity, noting that the Hilbert series ofK is 1, and that it can be computed uing the linear freeR-resolution ofK. The same argument shows that ifRis strongly Koszul, andI ˆ …u_i1;. . .;u_ik†, then

P_R=I…t† H_R…ÿt† ˆH_R=I…ÿt†:

The proof of Theorem 1.2 gives a more precise information about the Poin- care¨ series. For any two subsetsU;V ‰nŠ ˆ f1;. . .;ng, sayUˆ fi₁;. . .; :i_kg

with i₁<i₂<. . .<i_k, we denote by a_U;V the number of ideals

I…V† ˆ …ui†_i2V which are of the form…ui1;. . .;uijÿ1†;Uij for some jˆ1;. . .;k.

Now we choose some linear order of the subsets of‰nŠ, in other words a bi- jective map i:B_‰nŠ! f1;. . .;2ⁿg, where B_‰nŠ denotes the set of all subset of

‰nŠ, and consider the integer matrix Aˆ …a_U;V† where the entry a_U;V is at position…i…V†;i…U††:

The arguments in 1.2 then yield that P_I…U†…t† ˆ jUj ‡X

V

a_U;VP_I…V†…t†t;

where jUjdenotes the number of elements of U. Applying this formula re- cursively, we obtain the following formal power series with integer coeffi- cients:

P_I…U†…t† ˆX

i0

e_UAⁱwtⁱ;

where e_u is the row vector whose entries are all zero, except thei…U†-th en- try, which is 1, and wherewis the column vector whosei…V†-th entry isjVj for allV ‰nŠ. We set

BˆX

i0

Aⁱtⁱ:

ThenBis a matrix with coefficients inZ‰‰tŠŠ, and we have Bˆ …EÿAt†^ÿ1 and P…t† ˆBw;

where P…t†is the column vector with i…U†-th entryP_I…U† for all U ‰nŠ. It follows that wˆ …EÿAt†P…t†. Thus, if we set CˆEÿAt, and denote by C_U;V the submatrix of C which is obtained fromC by deleting the i…U†-th row and thei…V†-th column, Cramer's rule implies

Corollary 1.3. Let R be strongly Koszul. Then with the notation in- troduced one has

P_I…U†ˆX

V

…ÿ1†^{i…U†‡i…V†}jVjdetC_U;V

detC†^ÿ1:

Natural classes ofK-algebras to which our theory may be applied are the semigroup rings of homogeneous semigroups because their graded maximal ideal has a distinguished basis. We call a finitely generated subsemigroupS ofNⁿhomogeneousifS can be written as a disjoint union

Sˆ[

i0

S_i

with S₀ˆ f0g;S_i‡S_jS_i‡j for all i;j, and S generated by the elements of S1. The elements ofSi are called elements of degreei.

It is clear that the semigroup ringRˆK‰SŠof a homogeneous semigroup is a homogeneous K-algebra, with homogeneous components RiˆKSi. We identifyRwith the subring of the polynomial ringK‰x₁;. . .;x_nŠwithK-basis x^aˆx^a₁¹. . .x^a_nⁿ,a2S.

Typical examples of homogeneous semigroup rings are theK-subalgebras of a polynomial ring which are generated by a set of monomials which are all of same degree.

Let S be a homogeneous semigroup, and let a₁;. . .;a_m be its degree one generators. Then RˆK‰SŠ is generated by the monomials u_iˆx^ai for

iˆ1;. . .;m. We say that S is strongly Koszul, ifR is strongly Koszul with

respect to the generators u1:. . .;um. Obviously, this property only depends onS, and not on the fieldK.

It is convenient to identify the elements of the semigroupS with the cor- responding monomials inK‰SŠ. In particular theu_i will be identified with the generators ofS.

The next simple proposition interprets the property ``strongly Koszul'' in terms of the divisor poset ofS. We considerSa poset, called thedivisor po- set of s, by introducing the following partial order: lets1;s22S; then

s1s2; if there exists t2S such that s2ˆs1‡t:

Notice that S is a locally finite poset, in other words, any interval

‰s;tŠ ˆ fa2Sjsatgis finite. Let be an arbitrary poset, andu;v2. One says thatucoversv, ifv<uand there is nowwithv<w<u.

The locally finite poset is calledwonderful orlocally upper semimodular if whenever v₁ andv₂ coveru and v₁;v₂<vfor some v2, then there exists t2;tv, which covers each ofv₁andv₂.

Proposition 1.4. Let S be a homogeneous semigroup, and let u₁;. . .;u_m2 K‰SŠbe the generators of S. Then the following conditions are equivalent:

(a) S is strongly Koszul;

(b) the divisor poset of S is wonderful;

(c) the ideals…ui† \ …uj†are generated in degree2for all i6ˆj.

Proof. The equivalence of (b) and (c) is straightforward. In order to prove that (c) implies (a) we notice that there is a graded isomorphism

…ui†:…uj† ! ……ui† \ …uj††…ÿ1†

which maps an element a2 …ui†:…uj†toauj2 …ui† \ …uj†. Since S is strongly

Koszul, the ideal…u_i†:…u_j†is generated in degree 1, and so…u_i† \ …u_j†is gen- erated in degree 2.

Conversely, suppose that condition (c) is satisfied, and let a2 …uiÿ1;. . .;ujÿ1†:uij. We use the fact that K‰SŠ has a multi-graded struc- ture (where the monomials is given the multi-degree determined by their ex- ponent). Thus, since theuiare multi-homogeneous, it follows that the colon ideal …u_i1;. . .;u_ijÿ1†:u_ij is multi-graded, and hence is generated by mono- pmials. Therefore we may assume thata is a monomial, and conclude that auij ˆbuik for some kjÿ1 and some monomials b. But this implies that auij 2 …uij† \ …uik†. Now if we assume thatais a generator of the colon ideal, then it follows that auij is a generator of …uij† \ …uik†. By assumption, this ideal is generated in degree 2, so thatais of degree 1, as desired.

Corollary 1.5. Let S be a strongly Koszul semigroup, u and v be two semigroup elements of degree n and m, respectively. Then the ideal…u† \ …v†is generated in degreen‡m.

Proof. We proceed by induction on degreen‡m. Forn‡mˆ2, the as- sertion follows from 1.4. Now let n‡m>2. Then we may assume that n>1, and we writeuˆu⁰uiwhereu⁰is of degreenÿ1 andui is a semigroup generator. Now letw2 …u† \ …w†. Thenw2 …u⁰† \ …v† \ …ui†. Therefore there exists a generator z2 …u⁰† \ …v† such that w2 …z† \ …ui†. Our induction hy- pothesis implies that degzn‡mÿ1. Let z⁰ˆz=u⁰ and w⁰ˆw=u⁰. Then w⁰2 …z⁰† \ …u_i†. Let y be a generator of …z⁰† \ …u_i† such that w⁰2 …y⁰†. since degz⁰‡degu_i1‡m<n‡m, we have degy⁰1‡m, by induction hy- pothesis. Set yˆy⁰u⁰; then y2 …u† \ …v†, degyn‡m and w2 …y†, as de- sired.

LetRbe the semigroup ring of a homogeneous semigroupS. Then one has the following hierarchy of properties:

The defining of R has a Gro«bner basis of quadrics, or R is strongly Koszul)Ris Koszul )Ris defined by quadrics.

We do not know whether the defining ideal of a stongly Koszul semigroup has a Gro«bner basis of quadrics.

In concluding this section we consider a few Examples1.6. (1) The semigroup ring

RˆK‰x₁s;. . .;x_ns;x₁t;. . .;x_ntŠ

is strongly Koszul. Indeed, R has the K-basis x^asⁱt^j with a2Nⁿ, and jaj ˆi‡j where jaj ˆP_n

kˆ1a_k. Suppose u2 …x_ks† \ …x_ls†;k6ˆl;uˆx^asⁱt^j. Theni1; ifiˆ1, thenj1, and x_kx_lstdividesu, and ifi>1, thenx_kx_ls²

dividesu. In any case we see thatuis a multiple of an element of degree 2 of the intersection…x_ks† \ …x_ls†.

We also have to consider the case that u2 …xks† \ …xlt†. It is clear that i1 and j1. If k6ˆl, then xkxlst dividesu, and if kˆl eitherak>1, in which case x²_kst dividesu, orar1 for some other r. In this casexkxrstdi- videsu. Again we see that in all casesuis a multiple of an element of degree 2 in the intersection…x_ks† \ …x_lt†.

This example is part of a more general class of strongly Koszul algebras studied in the next section.

(2) Let Sbe a homogeneous semigroup which is defined by one quadric:

In other words, K‰SŠ 'K‰x₁;. . .;x_nŠ=…f†where f ˆvÿwis a quadratic bi- nomial. We claim thatS is strongly Koszul. In order to prove this we show that for any two numbers 1i<jn, the annihilator ofu_j in K‰SŠ=…u_i†is generated in degree 1. Here, as before, theuidenote the generators ofS, that is, the residues of thexi modulof.

Ifx_i does not dividevorw, thenu_jis regular onK‰SŠ=…u_i†. In this case the assertion is trivial. On the other hand, ifx_idivides, sayv, andwˆx_kx_l, then u_j is again regular onK‰SŠin casej6ˆkandj6ˆl, while the annihilator ofu_j is…ul†in casejˆk, and is…uk†in casejˆl

(3) We denote by Rn;d theK-subalgebra of the polynomial ring in n vari- ables which is generated by all squarefree monomials of degreed. It has been shown by Sturmsfels [12] that the defining ideals of these algebras (which we call squarefree Veronese rings) have a quadratic Gro«bner basis, and thus these algebras are Koszul. We refer the reader to the paper De Negri [10] for related results.

We claim that forn2d‡ ‰d=2Š;Rn;d is not strongly Koszul. Here we de- note by‰xŠthe integer part of a real numberx. We prove the assertion ford even (the proof ford odd is similar). We considerR_n;d as the subring of the polynomial ring S in the variables x1;. . .;xd;y1;. . .;yd;z1. . .;z_‰d=2Š;. . . We first notice that the i-th graded component of Rn;d has aK-basis consisting of all monomials of degreeidwhose exponents are bounded byi. Therefore we see that

uˆ …x₁. . .x_d†…y₁. . .y_d†…z²₁. . .z²_d=2†

belongs to Rn;d. Set u1ˆx1. . .xd and u2 ˆy1. . .yd; then it is obvious that the only generator of degree 2 of …u1† \ …u2† is u1u2. Note that u is not a multiple ofu₁u₂ since the complementary factorz²₁. . .z²_d=2does not belong to R_n;d. On the other handu2 …u₁† \ …u₂†, so thatuis a generator of degree 3 of …u₁† \ …u₂†.

For dˆ2 the bound for n is the best possible. Indeed, one easily checks thatR4;2is strongly Koszul.

Remark1.7. In general it seems hard to determine the degree of the gen- erators of the intersections …u_i† \ …u_j† for a homogeneous semigroup ring K‰SŠ ˆK‰u₁;. . .;u_nŠ. We denote by b…S† the highest possible degree of a generator of any such intersection.

LetI be the defining ideal ofK‰SŠ. The idealI is generated by binomials.

Letd be the highest degree of an element in a minimal set m of binomial generators of I. Then one has b…S† d. Indeed, let :K‰x₁;. . .;x_nŠ ! K‰u₁;. . .;u_nŠ be the canonical epimorphism with …x_i† ˆu_i for iˆ1;. . .;n, and suppose thatf ˆf1ÿf2 is a binomial ofm. Suppose further thatxijf1

andxjjf2. Then,aˆuiuˆujv, whereaˆ…f1†;uˆ…f1=xi†andvˆ…f2=xj†.

Therefore,a2 …ui† \ …uj†.

We claim that a is a generator of …u_i† \ …u_j†. Of course, the desired in- equality will follows then from this assertion.

Supposea is not a generator of …ui† \ …uj†. Then there exists a monomial (of the generatorsu1;. . .;un†a⁰2 …ui† \ …uj†withaˆa⁰d for some monomial d. Say, a⁰ˆuiu⁰ˆujv⁰. Then

0ˆu_iuÿu_jvˆd…u_iu⁰ÿu_jv⁰† ‡u_i…uÿdu⁰† ÿu_j…vÿdv⁰†:

The binomials on the right hand side are all equal to zero, so they corre- spond to binomial relations. Thus this equations tells us that f is not a minimal binomial relation, a contradiction.

2. Classes of strongly Koszul algebras

In this section we consider certain ring constructions which yield classes of strongly Koszul algebras.

Proposition 2.1. Let S be a strongly Koszul semigroup, and let u₁;. . .;u_m2K‰SŠ be the generators of the graded maximal ideal of RˆK‰SŠ

which correspond to the generators of S. Then

(a) R=…ui1;. . .;uik†is strongly Koszul for any subsequence ui1;. . .;uik of the generators u1;. . .;un.

(b) R=J is strongly Koszul for any ideal J R generated by monomials of degree2in the u_isuch that for all monomials u_iu_j in J and all k6ˆi;j one has …uiuj†:uk‡J ˆ …ui:uk† ˆ …uj:uk† ‡J.

Proof. LetL be any ideal inR generated by monomials in the u_i. Then R=L is multigraded. Therefore if we denote by ui the residue class ofui in R=L, then the strongly Koszul property forR=Lis equivalent to the follow- ing two conditions:

(1) for allkwithu_k6ˆ0, the annihilator ofu_kis generated in degree 1, and (2) …u_i† \ …u_j†is generated in degree 2 for alli6ˆj.

We leave it to the reader to check (1) and (2) in case (a). Now suppose we are in case (b), and letv6ˆ0 be a monomial inR=J annihilating someu_k6ˆ0.

Then vuk2J, and so v2 …uiuj†:uk for some uiuj2J. If k6ˆi;j, then our hypotheses imply that v2 …ui:uk†or v2 …uj:uk†. Thus, since Ris strongly Koszul, it follows thatvˆwul for whichuluk2 …uiuj†. Ifkˆiorkˆj;vis a multiple ofu_i or ofu_j. In both cases one concludes that the annihilator ofu_k is generated in degree 1. Condition (2) for the ringR=J is inherited fromR.

As consequence of 2.1 (b) we have that Fro«berg rings are strongly Koszul, a result which is already implicitly contained in [4].

Corollary2.2.Let R be the factor ring of a polynomial ring by quadratic monomials. Then R is strongly Koszul.

Other classes of examples are derived from the tensor product. LetRand P be homogeneous K-algebras. The tensor product R_KP is again a homogeneous K-algebra with homogeneous components…RP†_iˆL

j‡kˆi

RjKRk. The Segre product RP of R and P is the homogeneous sub- algebra ofRkPwith homogeneous components…RP†_iˆRikPi, while the fibre productRPofRandPis defined to be the factor ring ofR_KP modulo the ideal generated by all elementsrswith r2R₁ and s2P₁. Fi- nally, the d-the Veronese ring of R is the subring R^d† of R with homo- geneous components…R^d††_iˆRid.

Now we can show the following result, whose analogue is partly known for Koszul algebras by Backelin and Fro«berg [2].

Proposition 2.3.Let S and T be homogeneous semigroups, RˆK‰SŠand PˆK‰TŠ the corresponding semigroup rings over some field K, and Q be the tensor product, the Segre product, or the fiber product of R and P. Then

(a) the Veronese rings R^d†are strongly Koszul if R is strongly Koszul;

(b) Q is strongly Koszul, if and only if R and P are strongly Koszul.

Proof. (a) In order to show that the Veronese rings R^d† are strongly Koszul, we note that R^d†ˆK‰S^d†Š where S^d† is the homogeneous sub- semigroupS

iSid ofS. Notice further that…S;†is a graded poset sinceSis homogeneous. Hence it is clear that our assertion follows once we have proved the following statement: suppose thatSis a graded, wonderful poset.

Given elements u;v₁;v₂2S with u<v₁;v₂ <v and such that

deg…v₁† ÿdeg…u† ˆi and deg…v₂† ÿdeg…u† ˆj. Then there exists tv with

deg…t† ÿdeg…u† ˆi‡jsuch thatv1;v2<t.

This simple and well-known combinatorial statement is proved by induc- tion oni‡j. Subtracting from all elements the smallest elementu, we may assume thatuˆ0. Ifi‡jˆ2, then this is just the property wonderful. Now

supppose thati‡j>2, and, say,i2. Then there is an elementwof degree iÿ1 with 0<w<v₁. By induction hypothesis, there exists an elements2S of degreei‡jÿ1 withw;v₂<svNow we apply again our induction hy- pothesis to the situation w<v1;sv, and find an element tvof degree deg…v1† ‡deg…s† ÿ2deg…w† ˆi‡jwithv1;s<t. This proves the assertion.

(b) Observe thatRP'K‰STŠwhereST is the product of the two semigroups S and T. The elements of ST are the pairs …s;t† with s2S and t2T, and with componentwise addition. We leave it to the reader to check the easy fact that …ST;† is wonderful if …S;† and …T;† are wonderful.

To show that the Segre productRP is strongly Koszul is even simpler.

We have RPˆK‰STŠ where ST is the subsemigroup of ST con- sisting of all elements …s;t† with deg…s† ˆdeg…t†. Now suppose …s;t† and …u;v†cover…a;b†and…s;t†,…u;v†<…f;g†. Thensanducovera,tandvcover b,u<f andt;v<g. Therefore, there existk2Sandl2T such thatkcov- erssandu;l coverstandv, and such thatkf andlf. Then…k;l†covers …s;t†and…u;v†and…k;l† …f;g†.

The assertion for the fiber product follows from 2.1 (b).

Conversely assume thatQis strongly Koszul (with respect to the natural algebra generators, say, w1;. . .;wk†. Let RˆK‰u1;. . .;unŠ and Pˆ K‰v1;. . .;vmŠwhere the generatorsuiandvj correspond the generatorsSand T. We will see that there exist subsequences W₁ andW₂ of w₁;. . .;w_k such that Q=…W₁† 'R and Q=…W₂† 'P. Hence for the tensor product and the Segre product it follows from 2.1 (a) that Rand S are strongly Koszul. In the proof of 2.1 (a) we made use of the fact that a semigroup ring is multi- graded. Since the fibre product of two semigroup rings is multi-graded too, the proof given there carries over, so that 2.1 (a) is also valid for the fiber product. Thus if the fiber product is strongly Koszul, we also conclude that RandSare strongly Koszul.

The choice of the setsW1 andW2 is as follows: if Qis the tensor or fiber product, we let W1ˆ f1v1;. . .;1vmg and W2ˆ fu11;. . .;un1g; if Q is the Segre product, we let W1 ˆ fuivjjiˆ2;. . .;n;jˆ1;. . .;mg and W₂ˆ fu_iv_jjiˆ1;. . .;n;jˆ2;. . .;mg.

We dot not know whether 2.3 holds more generally for arbitrary strongly Koszul algebras as defined in 1.1.

It is known [1] that the sufficiently high Veronese subrings of an arbitrary homogeneousK-algebra are Koszul. The following example shows that this is not true for the property ``strongly Koszul''. Indeed, consider in K‰x1;x2;x3Šthe lexsegmentLin degree 2 with smallest element x2x3, that is, the set of monomials

fx²₁;x₁x₂;x₂x₃;x²₂;x₂x₃g;

and let Rbe the homogeneousK-algebra generated over K by these mono- mials. For eachd, the element …x^2d₁ †…x^d₂x^d₃†² of degree 3 inR^d†is a generator of the intersection…x^2d₁ † \ …x^2d₂ †. In other words,noVeronese subring ofRis strongly Koszul.

Definition 2.4. We call a semigroupS trivialif, starting with polynomial rings,K‰SŠis obtained by repeated applications of Segre products and tensor products.

In the next sections we will show that for certain classes of semigroup rings, the only strongly Koszul algebras are the trivial ones. On the other hand, the ringR_2;4 in 1.6 (2) is an example of a non-trivial Strongly Koszul algebra.

3. The classification of strongly Koszul Hibi rings

The Segre product of two polynomial rings may be viewed as the Hibi ring of the product poset of two chains, and hence such a ring is strongly Koszul.

In this section we classify all distributive lattices whose Hibi rings are strongly Koszul.

LetLbe a finite distributive lattice andK‰xj2LŠthe polynomial ring injLjindeterminates over a fieldK. Following [6] (see also [7]) we define the Hibi ringrK‰LŠassociated with the lattice Lby

rK‰LŠ ˆK‰xj2LŠ=…xxÿx^x_j; 2L†:

Then, rk‰LŠ is, in fact, a normal affine homogeneous semigroup ring.

Moreover, r_k‰LŠ is an algebra with straightening laws on L over K. Let b…L;d† denote the set of those monomials of r_K‰LŠ of the form x₁x₂ x_d with each _i2L such that _{12 d} in L for d ˆ1;2. . .;and setb…L;0† ˆ f1g. Then,S₁

dˆ0b…L;d†is aK-basis ofrK‰LŠ.

Thus, given any monomialuˆx1x2 xd ofrK‰LŠof degree d, there ex- ists a unique monomial v2b…L;d† with vˆu. We call such a monomial v2b…L;d† the standard expression of u. If vˆx₁x₂ x_d with _{1 2 d} is the standard expression of uˆx₁x₂ x_d, then it follows that

_kˆ ^

1i1<i2<<ikd

…_i1__i2_ __ik† …1†

for each 1kd.

The following theorem follows from our classification of strongly Koszul Hibi rings. However, its short and direct proof may be of interest.

Theorem3.1.If L is Boolean, thenb_K‰LŠis strongly Koszul.

Proof. Fix arbitrary two monomial generatorsx and x of rK‰LŠ. Our goal is to prove that the ideal…x† \ …x†is generated in degree 2.

We first show thatxx, where; 2Lwith, belongs to…x† \ …x†if and only if^ and _. In fact, if xxˆxx ˆx_x for some

; 2L, then ˆ^ˆ^ and _ˆ_. Thus, ^ and _. Now, suppose that ^ and _. SinceL is Boolean, the closed interval‰; ŠofLis again Boolean. Thus, we can find; 2 ‰; Š such that ^ˆ; _ˆ and ^ˆ; _ˆ. Hence, xxˆxx ˆxx. Thus,xx2 …x† \ …x†, as desired.

If uˆx1x2 xd with 12 d belongs to …x† \ …x† and if uˆxx1 xdÿ1 ˆxx1 xdÿ1 for some i's and j's in L, then the ex- istence and uniqueness of standard expressions (1) guarantee that

₁ˆ^₁^ ^_dÿ1ˆ^₁^ ^_dÿ1 d ˆ_1_ _dÿ1ˆ_1_ _dÿ1

Thus, in particular, 1d and 1d, i.e., 1^ and _d. Hence,1d belongs to…x† \ …x†. Thus,…x† \ …x†is generated in degree 2, as required.

Birkhoff's fundamental structure theorem [3] for finite distributive lattices guarantees that, for any finite distributive lattice L, there exists a unique posetP such thatLis isomorphic to the lattice J…P† consisting of all poset ideals ofP, ordered by inclusion. Suppose Pcontains an element p wich is comparable with any other element of P. Consider the subposets P1ˆ fq2Pjq<pg and P2ˆ fq2Pjq>pg of P, and set L1ˆJ…P1†;

L2ˆJ…P2† and LˆJ…P†. then it is easy to see that rK‰LŠ ' r_K‰L₁Š r_K‰L₂Š. Thus in view of 2.3,r_K‰LŠis strongly Koszul if and only if r_K‰L₁Šandr_K‰L₂Šare strongly Koszul.

The posetPissimpleif there is no element ofPwhich is comparable with any other element of P. Hence in order to find distributive lattices whose Hibi rings are strongly Koszul it suffices to consider latticesJ…P†of simple posets P. Another reduction is possible: one calls a poset connected, if its Hasse diagram is connected. Suppose the poset P is not connected. Then there exist two non-empty subposetsP1 andP2 of Psuch that the elements ofP1 andP2 are incomparable. LetL1ˆJ…P1†,L2ˆJ…P2†andLˆJ…p†; it is not difficult to see thatrK‰LŠ 'rK‰L1Š rK‰L2Š. In particular, it follows

from 2.3 that r_K‰LŠ is strongly Koszul if and only if, for all connected componentsL⁰ofL;r_k‰L⁰Šare strongly Koszul.

Starting from polynomial rings, repeated application of Segre products and tensor products strongly produces Koszul Hibi rings. Such a Hibi ring is calledtrivial.

Now we are ready to formulate our classification result.

Theorem3.2.A Hibi ring is strongly Koszul if and only if it is trivial.

We observed already one implication. The other one will follow from Theorem 3.3.Suppose that a finite poset P is simple and connected. Then, the Hibi ring rK‰LŠ associated with the distributive lattice LˆJ…P† is not strongly Koszul.

The proof of this theorem is a consequence of the next two lemmata.

Lemma 3.4. Suppose that a finite poset P possesses a saturated chain c1 <c2< <cm…m2†together with a;b2P such that(i)cmcovers b;(ii) a covers c1;(iii)c16b;(iv)a6cm. Let LˆJ…P†denote the finite distributive lattice consisting of all poset ideals of P. Then,r_K‰LŠis not strongly Koszul.

Proof. Let I denote the poset ideal of P consisting of those elements q2Pwith c₁6q andb6q. Also, set…b;a†:ˆ fq2Pjb<q<ag(possibly, empty) and ‰c₁;c_mŠ:ˆ fq2Pjc₁ qc_mg. We then define the elements

; ; ; and belonging toLˆJ…P†by

ˆI; ˆI[ fb;c₁g; ˆI[ fa;bg [ …b;a† [ ‰c₁;c_mŠ;

ˆI[ fc1g; ˆI[ fa;bg [ …b;ag [ fc1g:

Then, inr_K‰LŠ;xxx2 …x† [ …x†. In fact,

xxxˆx_i[fbgxxˆxxx_{i[fbg[‰c1;cmŠ}:

First, we show, in general, that if; 2Lwith and ifxx2 …x†\

…x†, then c₁2 and c_m62. Let xxˆxx⁰ ˆxx⁰ for some ⁰; ⁰2L.

Sincea2, we havea2_⁰ˆ_⁰. Thus,a2⁰. Hence,c₁2⁰. Then, c1 2^⁰ˆ. Since b62, we have b62^⁰ˆ^⁰. Thus, b62⁰. Hence,cm62⁰. Then,cm62_⁰ˆ.

Now, if xxx is not a generator of …x† \ …x†, then xxx for some

; ; 2L with xx2 …x† \ …x†and . Sincec_m2(thusc_m62) and sincec_m2,c_mmust belong to. Hence,c₁2. Sincec₁2(thusc₁2†,c₁ belongs to each of ; and . However, c162, a contradiction. Hence, xxx must be a generator of…x† \ …x†. Thus,rK‰LŠis not strongly Kos- zul as required.

Lemma 3.5. Every simple and connected (finite) poset P possesses a satu- rated chain c₁<c₂<. . .<c_m…m2† together with a;b2P satisfying the above conditions(i)^(iv)in Lemma3.4.

Proof. We denote minimal elementswandw⁰in Pwith w6ˆw⁰. IfPnfwg is simple and connected, then we can find a required chain together with two elements inPnfwg.

First, suppose that Pnfwg is not connected. Let Q1;. . .;Qs…s2†denote the connected components ofPnfwg withw⁰2Q₁. We choose a walk.

wˆz1!z2! !ztÿ1!ztˆw⁰

withz_i6ˆz_j ifi6ˆjcombiningwwithw⁰inQ₁[ fwg. Here,!is the covering relation, i.e., for each 1i<t, either z_i coversz_i‡1 orz_i is covered byz_i‡1. Let 2j<t denote the maximal integer for which wz_j and construct a saturated chain wˆc1<c2< <cmˆzj. Then, xj‡1<zj since w6zj‡1. Also, choose y2Q2 which covers w in P. Then, the saturated chain wˆc₁<c₂ < <c_mˆz_j together with aˆy…>w†and bˆz_j‡1…<z_j†sa- tisfy the conditions in Lemma 3.4.

Second, suppose thatPnfwgis not simple. Letp₁;. . .;p_t …t1†denote the elements such that eachpiis comparable with an arbitrary element inPnfwg and asume that p1< <pt in P. We choose z2P which covers w in P.

Then, z>pt since P is simple. Also, choose a saturated chain p_t ˆy₁<y₂< <y_t in P such thaty_t is not comparable withzin P. Let 1j<tdenote the maximal integer for which y_j<zand construct a satu- rated chain yjˆc1<c2 < <cmˆz. Then, the saturated chain yjˆc1<c2< <cmˆz together with aˆyj‡1…>yj† and bˆw…<z† sa- tisfy the conditions in Lemma 3.4.

4. The classification of strongly Koszul algebras which are defined by bi- partite graphs

Let G be a graph on the vertex set V ˆ f1;. . .;ng. To G we associate the subring K‰GŠof the polynomial ring K‰x1;. . .;xnŠ which is generated by all monomialsxixj for which…i;j†is an edge ofG. We call the graphGstrongly Koszul, ifK‰GŠis strongly Koszul.

For example, if we let G be the complete graph, then K‰GŠis the second Veronese subring ofK‰x₁;. . .;x_nŠ, and we know from 2.3 thatG is strongly Koszul. On the other hand, if we letGbe the complete graph without loops, that is,Ghas all possible edges, except the loops…i;i†, thenK‰GŠis a second squarefree Veronese ring, and it follows from Example 1.6 (2), thatGis not strongly Koszul forn5.

The question arises which graphs Gare strongly Koszul. We will restrict ourselves to consider bipartite graphs, because we do not know the general answer. Recall that a graph G on a vertex set V is called bipartite if the vertex set can be writen as a disjoint union VˆV1[V2 such that all edges of G are of the form …i;j†with i2V1 nd j2V2. G is called a complete bi- partite graph(on…V₁;v₂††, if all the edges…i;j†withi2V₂ belong toG. No- tice that ifGis a complete bipartite graph on…V₁;V₂†, thenK‰GŠis the Segre product of the polynomial ring in the variablesxi; i2V1, and of the poly- nomial ring in the variablesxi; i2V2. Therefore, by 2.3,Gis strongly Kos- zul. We shall see that these are essentially the only strongly Koszul grphs.

We first show

Lemma4.1.Every cycle of a strongly Koszul bipartite graph G has all pos- sible chords.

Proof. Notice that a cycleCin a bipartite graph necessarily has an even number of vertices. Indeed, we may assume that…1;2†;…2;3†;. . .;…mÿ1;m†

and …m;1† are the edges of the cycle. Then, if 12V₁, then all the ``odd'' vertices 2i‡1 belong to V<sub>1</sub> and the ``even'' vertices to V₂. In particular, mˆ2kfor some integerk2.

Now assume that some possible chord ofCdoes not belong toG. We may assume that this is cord …1;2i† for some i with 1<i<k. We consider the elements

uˆY^iÿ1

jˆ1

…x2jx2j‡1† and vˆY^kÿ1

jˆi

…x2j‡1x2j‡2†:

Then deguˆiÿ1, degvˆkÿi and uv is the only element of …u† \ …v† of degreekÿ1. On the other hand, we see that the elementwˆQ_k

iˆ1xibelongs to …u† \ …v†. We have that wis not a multiple of uv, because the remaining factor is just the missing chord. Sowis a generator of …u† \ …v†of degree k, contradicting 1.5.

Lemma4.2.If C₁and C₂are cycles of a(not necessarily bipartite)graph and if there exist at least two common vertices of C1and C2, then for any vertex i of C1and for any vertex j of C2 we can find a cycle C which contains both i and j.

Proof. We may assume thati does not belong toC₂ and that j does not belong to C1. Let and denote two common vertices ofC1 and C2 such thatibelongs to an arcÿ ofC1betweenand, and that no vertex…66ˆ; † of ÿ belongs to C₂. We then choose an arc ÿ⁰ of C₂ between and such thatj belongs toÿ⁰. Now, ÿ[ÿ⁰ is a cycle which contains both i andj, as required.

Corollary4.3.Let C₁ and C₂ be two cycles of a strongly Kosul bipartite graph G which have at least one common edge. Then there exists a complete bipartite subgraph of G which contains both C₁and C₂.

Proof. LetV₁andV₂ be the partition of the vertex setVofG. Leti2V₁ andj2V₂ and suppose that both vertices belong to C₁[C₂. We will show that…i;j†is an edge ofG. If both the vertices belong to eitherC1orC2, then the assertion follows from 4.1. Now suppose thatiis a vertex of, say,C1and j a vertex of C₂. Since C₁ and C₂ have an edge in common, by 4.2 we can find a cycleC(which is a subgraph ofC₁[C₂†with the verticesiandj. Now we apply again 4.1 in order to conclude that…i;j†is an edge ofG.

One more ingredient is needed in order to prove the main result of this section. Let G be a bipartite graph. We want to describe the relations of K‰GŠ. Consider the polynomial ringP defined over K in the indeterminates yij for all …i;j† which are edges of G. For convenience Yij and yji will be identified. LetI be the kernel of theK-algebra homomorphism which sends y_ij to x_ix_j. To each even closed walk ÿ of G with edges …i₁;i₂†;…i₂;i₃†;. . .;…i_2kÿ1;i_2k†;…i_2k;i₁†we assign the relation

fÿ ˆY^k

jˆ1

yi2jÿ1;;i2jÿY^k

jˆ1

yi2j;i2j‡1

withi2k‡1ˆi1.

Lemma4.4.The relation ideal I of K‰GŠis generated by all the relations fC, where C is a cycle of G.

Proof. It follows from, e.g., [12, Proof of Theorem 9.1] that I is gener- ated by all the relationsfÿ, whereÿ is an even closed walk ofG. Letÿ be an even closed walk with edges…i₁;i₂†;…i₂;i₃†;. . .;…i_2kÿ1;i_2k†;…i_2k;i₁†and suppose thatÿ is not a cycle. We may assume thati_2p‡1 ˆi₁ for some 1p<k. Let ÿ₁ denote the even closed subwalk with edges …i₁;i₂†;…i₂;i₃†;. . .;…i_2pÿ1;i_2p†;

…i2p;i1†andÿ2the even closed subwalk with edges…i1;i2p‡2†;…i2p‡2;i2p‡3†;. . .; …i2kÿ1;i2k†;…i2k;i1†. Then, we have

f_ÿ ˆY^k

jˆ1

y_i2jÿ1;i2j ÿY^k

jˆ1

y_i2j;i2j‡1

ˆY^k

jˆ1

y_i2jÿ1;i2j ÿ Y^p

jˆ1

y_i2jÿ1;i2j

! Y^k

jˆp‡1

y_i2j;i2j‡1

!

‡ Y^p

jˆ1

y_i2jÿ1;i2j

! Y^k

jˆp‡1

y_i2j;i2j‡1

! ÿY^k

jˆ1

y_i2j;i2j‡1

ˆ Y^p

jˆ1

yi2jÿ1;i2j

! Y^k

jˆp‡1

yi2jÿ1;i2jÿ Y^k

jˆp‡1

yi2j;i2j‡1

!

‡ Y^p

jˆ1

yi2jÿ1;i2jÿY^p

jˆ1

yi2j;i2j‡1

! Y^k

jˆp‡1

yi2j;i2j‡1

!

ˆ Y^p

jˆ1

y_i2jÿ1;i2j

!

f_ÿ2‡f_ÿ1 Y^k

jˆp‡1

y_i2j;i2j‡1

! :

Hence, fÿ belongs to the ideal generated by all the relations fÿ1 and fÿ2. Thus, repeated applications of the technique guarantee thatf_ÿ belongs to the ideal generated by all the relationsf_C, whereC is a cycle ofG, as desired.

Now we are ready for the proof of

Theorem4.5.Let G be a strongly Koszul bipartite graph, and let G1;. . .;Gp

be the maximal complete bipartite subgraphs of G. Then K‰GŠ K‰G₁Š . . . K‰G_pŠ. In particular, since each K‰G_iŠis the Segre product of two polynomials rings, the semigroup defined by G is trivial.

Proof. Thanks to 4.3, ifeˆ …i;j†is an edge ofG_rande⁰ˆ …i⁰;j⁰†is an ede ofG_swithr6ˆs, then no cycle contains botheande⁰. Since by 4.4, the cycle relations generate the defining ideal of K‰GŠ, we see that there exist no gen- erating relations involving variables corresponding to Gr and Gs. This im- plies thatK‰GŠ K‰G₁Š . . .K‰G_pŠ, as desired.

REFERENCES

1, J. Backelin, On the rates of growth of the homologies of Veronese subrings, in:Algebra, Algebraic Topology and Their Interactions,J.-E. Roos, Ed., Lecture Notes in Math. 1183 (1986), 79^100.

2. J. Backelin and R. Fro«berg,Koszul algebras, Veronese subrings, and rings with linear re- solutions,Rev. Roum. Math. Pures Appl. 30 (1985), 549^565.

3. G. Birkhoff,Lattice theory,3rd. ed., Amer. Math. Soc. Colloq. Publ. No. 25, 1967.

4. W. Bruns, J. Herzog and U. Vetter, Syzygies and Walks, in: ICTP ProceedingsCommutative Algebra,A. Simis, N. V. Trung and G. Valla, Eds., World Scientific 1994, 36^57.

5. R. Fro«berg,Determination of a Class of Poincare¨ series,Math. Scand. 37 (1975), 29^39.

6. T. Hibi,Distributive lattices, affine semigroup rings, and algebras with straightening laws,in:

Commutative Algebra and Combinatorics,M. Nagata and H. Matsumura, Eds., Adv.

Stud. Pure Math. 11, 1987, 93^103.

7. T. Hibi, Algebraic Combinatorics on Convex Polytopes, Carslaw Publications, Glebe, N.S.W., Australia, 1992.

8. O. A. Laudal and A. Sletsje, Betti numbers of monoid algebras: Applications to2-dimen- sional torus embeddings,Math. Scand. 56 (1985), 145^162.

9. J. Herzog, V. Reiner and V. Welker,The Koszul property in affine semigroup rings,Pac. J.

Math. 186 (1998), 39^65.

10. E. De Negri,Toric rings generated by stable sets of monomials,Math. Nachr. 203 (1999), 31^

11. I. Peeva, V. Reiner and B. Sturmfels,45. How to shell a monoid,Math. Ann. 310 (1998), 379^

12. B. Sturmfels,194. Gro«bner Bases and Convex Polytopes,Univ. Lecture Ser. 8 (1995).

FB6 MATHEMATIK UND INFORMATIK UNIVERSIØT GH-ESSEN

45117 ESSEM GERMANY

mat300@@une-essen.de

DEPARTMENT OF MATHEMATICS GRADUATE SCHOOL OF SCIENCE OSAKA UNIVERSITY

TOYONAKA, OSAKA 560, JAPAN

E-mail:hibi@@math.sci.osaka-uc.jp

DEPARTIMENTO DI MATEMATICA UNIVERSITA DI MESSINA

CONTRADA PAPARDO SALITA SPERONE 3 98166 SANT'AGATA, MESSINA, ITALIA

E-mail:grest@@imeuniv.unime.it