AFFINESEMIGROUPS
WINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO
ˆVIETˆTRUNGDedicatedtothememoryofGy¨orgyPoll´ak
(CommunicatedbyL´aszl´oM´arki)
1.INTRODUCTION
Affinesemigroups–discreteanaloguesofconvexpolyhedralcones–markthecross-roadsofalgebraicgeometry,commutativealgebraandintegerprogramming.Theycon-stitutethecombinatorialbackgroundforthetheoryoftoricvarieties,whichistheirmain
linktoalgebraicgeometry.InitiatedbytheworkofDemazure[De]andKempf,Knudsen,MumfordandSaint-Donat[KKMS]intheearly70s,toricgeometryisstillaveryactiveareaofresearch.
However,thelastdecadehasclearlywitnessedtheextensivestudyofaffinesemigroupsfromtheothertwoperspectives.Nodoubt,thisisduetothetremendouslyincreasedcomputationalpowerinalgebraicgeometry,implementedthroughthetheoryofGr¨obnerbases,and,ofcourse,tomoderncomputers.
Inthisarticleweoverviewthoseaspectsofthisdevelopmentthathavebeenrelevantforourownresearch,andposeseveralopenproblems.Answerstotheseproblemswouldcontributesubstantiallytothetheory.
Thepapertreatstwomaintopics:(1)affinesemigroupsandseveralcoveringproper-tiesforthemand(2)algebraicpropertiesforthecorrespondingrings(Koszul,Cohen-Macaulay,different“sizes”ofthedefiningbinomialideals).Weemphasizethespecialcasewhentheinitialdataareencodedintolatticepolytopes.Therelatedobjects–poly-topalsemigroupsandalgebras–providealinkwiththeclassicalthemeoftriangulationsintounimodularsimplices.
Wehavealsoincludedanalgorithmforcheckingthesemigroupcoveringpropertyinthemostgeneralsetting(Section4).Ourcounterexampletocertaincoveringconjectures(Section3)wasfoundbytheapplicationofasmallpartofthisalgorithm.Thegeneralalgorithmcouldbeusedforadeeperstudyofaffinesemigroups.
ThispaperisanexpandedversionofthetalksgivenbythefirstandthethirdauthorintheProblemsessionoftheColloquiumonSemigroupsheldinSzegedinJuly2000.
2
ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO
2.AFFINE
ANDPOLYTOPALSEMIGROUPSANDTHEIRALGEBRAS
Weusethefollowingnotation:Z,Q,Raretheadditivegroupsofintegral,rational,and
realnumbers,respectively;Z+,Q+andR+denotethecorrespondingadditivesubsemi-groupsofnon-negativenumbers,andN={1,2,...}.
2.1.Affinesemigroups.Anaffinesemigroupisasemigroup(alwayscontaininganeu-tralelement)whichisfinitelygeneratedandcanbeembeddedinZnforsomen∈N.GroupsisomorphictoZnarecalledlatticesinthefollowing.
Wewritegp(S)forthegroupofdifferencesofS,i.e.gp(S)isthesmallestgroup(uptoisomorphism)whichcontainsS.
IfSiscontainedinthelatticeLasasubsemigroup,thenx∈LisintegraloverSifcx∈S
¯LofSinL.ObviouslyS¯Lforsomec∈N,andthesetofallsuchxistheintegralclosureS
isagainasemigroup.AsweshallseeinProposition2.1.1,itisevenanaffinesemigroup,andcanbedescribedingeometricterms.
ByaconeinarealvectorspaceV=RnwemeanasubsetCsuchthatCisclosedunderlinearcombinationswithnon-negativerealcoefficients.Aconeisfinitelygeneratedifandonlyifitistheintersectionoffinitelymanyvectorhalfspaces.(Sometimesasetoftheformz+Cwillalsobecalledacone.)IfCisgeneratedbyvectorswithrationalor,equivalently,integralcomponents,thenCiscalledrational.Thisisthecaseifandonlyifthehalfspacescanbedescribedbyhomogeneouslinearinequalitieswithrational(orintegral)coefficients.
ThisappliesespeciallytotheconeC(S)generatedbySintherealvectorspaceL⊗R:(∗)
C(S)={x∈L⊗R:σi(x)≥0,i=1,...,s}
wheretheσiarelinearformsonL⊗Rwithintegralcoefficients.
Proposition2.1.1.(a)(Gordan’slemma)LetC⊂L⊗Rbeafinitelygeneratedrational
cone(i.e.generatedbyfinitelymanyvectorsfromL⊗Q).ThenL∩CisanaffinesemigroupandintegrallyclosedinL.
(b)LetSbeanaffinesubsemigroupofthelatticeL.Then
¯L=L∩C(S);(i)S
¯LsuchthatS¯L=u(ii)thereexistz1,...,zu∈Si=1zi+S;
¯Lisanaffinesemigroup.(iii)SProof.(a)NotethatCisgeneratedbyfinitelymanyelementsx1,...,xm∈L.Letx∈L∩C.Thenx=a1x1+···+amxmwithnon-negativerationalai.Setbi=⌊ai⌋.Then(∗)
x=(b1x1+···+bmxm)+(r1x1+···+rmxm),
0≤ri<1.
ThesecondsummandliesintheintersectionofLwithaboundedsubsetofC.Thusthereareonlyfinitelymanychoicesforit.Theseelementstogetherwithx1,...,xmgenerateL∩C.ThatL∩CisintegrallyclosedinLisevident.
(b)SetC=C(S),andchooseasystemx1,...,xmofgeneratorsofS.Theneveryx∈L∩C
hasarepresentation(∗).Multiplicationbyacommondenominatorofr1,...,rm
¯L.Ontheotherhand,L∩Cisintegrallyclosedby(a)sothatshowsthatx∈S
¯L=L∩C.S
PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS3
Theelementsy1,...,yucannowbechosenasthevectorsr1x1+···+rmxmap-pearingin(∗).Theirnumberisfinitesincetheyareallintegralandcontainedina
¯LasaboundedsubsetofL⊗R.Togetherwithx1,...,xmtheycertainlygenerateS
semigroup.
Proposition2.1.1showsthatnormalaffinesemigroupscanalsobedefinedbyfinitelygeneratedrationalconesC:thesemigroupS(C)=L∩CisaffineandintegrallyclosedinL.
WeintroducespecialterminologyinthecaseinwhichL=gp(S).Thentheintegral
¯=S¯gp(S)iscalledthenormalization,andSisnormalifS=S¯.ClearlytheclosureS
semigroupsS(C)arenormal,andconversely,everynormalaffinesemigroupShassucharepresentation,sinceS=S(C(S))(ingp(S)).
SupposethatL=gp(S)andthatrepresentation(∗)ofC(S)isirredundant.Thenthelin-earformsσidescribeexactlythesupporthyperplanesofC(S),andarethereforeuniquelydetermineduptoamultiplebyanon-negativefactor.Wecanchoosethemtohaveco-primeintegralcoefficients,andthentheσiareuniquelydetermined.WecallthemthesupportformsofS,andwrite
WecallasemigroupSpositiveif0istheonlyinvertibleelementinS.Itiseasilyseen¯ispositiveaswellandthatpositivityisequivalenttothefactthatC(S)isapointedthatS
conewithapex0.Itiseasilyseenthatthemapσ:S→Zs+,σ(x)=(σ1(x),...,σs(x)),isanembeddingifSpositive.ItfollowsthateveryelementofScanbewrittenasthesumofuniquelydeterminedirreducibleelements.SinceSisfinitelygenerated,thesetofirreducibleelementsisalsofinite.ItconstitutestheHilbertbasisHilb(S)ofS;clearlyHilb(S)istheuniquelydeterminedminimalsystemofgeneratorsofS.ForafinitelygeneratedpositiverationalconeCwesetHilb(C)=Hilb(S(C)).
EspeciallyfornormalStheassumptionthatSispositiveisnotasevererestriction.Itiseasilyseenthatonehasasplitting
intothemaximalsubgroupS0ofSandapositivenormalaffinesemigroupS′,namelytheimageofSingp(S)/S0.
2.2.Semigroupalgebras.NowletKbeafield.Thenwecanformthesemigroupal-gebraK[S].SinceSisfinitelygeneratedasasemigroup,K[S]isfinitelygeneratedasaK-algebra.WhenanembeddingS→Znisgiven,itinducesanembeddingK[S]→K[Zn],anduponthechoiceofabasisinZn,thealgebraK[Zn]canbeidentifiedwiththeLaurentpolynomialringK[T1±1,...,Tn±1].Underthisidentification,K[S]hasthemonomialbasisTa,a∈S⊂Zn(whereweusethenotationTa=T1a1···Tnan).
IfweidentifySwiththesemigroupK-basisofK[S],thenthereisaconflictofnotation:additioninthesemigroupturnsintomultiplicationinthering.Theonlywayoutwouldbetoavoidthisidentificationandalwaysusetheexponentialnotationasinthepreviousparagraph.However,thisisoftencumbersome.Wecanonlyaskthereadertoalwayspayattentiontothecontext.
S=S0⊕S′
supp(S)={σ1,...,σs}.
4
ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO
ItisnowclearthataffinesemigroupalgebrasarenothingbutsubalgebrasofK[T1±1,
...,Tn±1]generatedbyfinitelymanymonomials.Neverthelesstheabstractpointofviewhasmanyadvantages.WhenweconsidertheelementsofSasmembersofK[S],wewillusuallycallthemmonomials.Productsaswitha∈Kands∈Sarecalledterms.TheKrulldimensionofK[S]isgivenbyrank(S),sincerankSisobviouslyS=rankgp
thetranscendencedegreeofQF(K[S])=QFK[gp(S)]overK.
IfSispositive,thenHilb(S)isaminimalsetofgeneratorsforK[S].
Itisnotdifficulttocheck,andthereadershouldnotethattheusageoftheterms“in-tegralover”,“integralclosure”,“normal”and“normalization”isconsistentwithitsuse
¯L]istheintegralclosureofK[S]inthequotientfieldincommutativealgebra.SoK[S
QF(K[L])ofK[L]etc.
2.3.Polytopalsemigroupalgebras.LetMbeasubsetofRn.Weset
LM=M∩Zn,
soLMisthesetoflatticepointsinM,andEMistheimageofLMundertheembeddingRn→Rn+1,x→(x,1).VeryfrequentlywewillconsiderRnasahyperplaneofRn+1un-derthisembedding;thenwemayidentifyLMandEM.BySMwedenotethesubsemigroupofZn+1generatedbyEM.
NowsupposethatPisa(finiteconvex)latticepolytopeinRn,where‘lattice’meansthatalltheverticesofPbelongtotheintegrallatticeZn.TheaffinesemigroupsofthetypeSPwillbecalledpolytopalsemigroups.AlatticepolytopePisnormalifSPisanormalsemigroup.
EM={(x,1):x∈LM}⊂Zn+1;
PFIGURE1.Verticalcross-sectionofapolytopalsemigroup
LetKbeafield.Then
K[P]=K[SP]
iscalledapolytopalsemigroupalgebraorsimplyapolytopalalgebra.SincerankSP=dimP+1anddimK[P]=rankSPasremarkedabove,wehave
dimK[P]=dimP+1.
NotethatSP(or,moregenerally,SM)isagradedsemigroup,i.e.SP=∞i=0(SP)isuchthat(SP)i+(SP)j⊂(SP)i+j;itsi-thgradedcomponent(SP)iconsistsofalltheelements(x,i)∈SP.Moreover,SPisevenhomogeneous,namelygeneratedbyitselementsofdegree1.
PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS5
ThereforeR=K[P]isagradedK-algebrainanaturalwayandgeneratedbyitsdegree1elements.Itsi-thgradedcomponentRiistheK-vectorspacegeneratedby(SP)i.TheelementsofEP=(SP)1havedegree1,andthereforeRisahomogeneousK-algebraintheterminologyofBrunsandHerzog[BH].ThedefiningrelationsofK[P]arethebi-nomialsrepresentingtheaffinedependenciesofthelatticepointsofP.(InSection5wewilldiscussthepropertiesoftheidealgeneratedbythedefiningbinomials.)Someeasyexamples:
Examples2.3.1.(a)P=conv(1,4)∈R1.ThenPcontainsthelatticepoints1,2,3,4,
andtherelationsofthecorrespondinggeneratorsofK[P]aregivenby
22
X1X3=X2,X1X4=X2X3,X2X4=X3.
(b)P=conv(0,0),(0,1),(1,0),(1,1).ThelatticepointsofPareexactlythe4ver-tices,andthedefiningrelationofK[P]isX1X4=X2X3.
(c)P=conv(1,0),(0,1),(−1,−1).ThereisafourthlatticepointinP,namely(0,0),
andthedefiningrelationisX1X2X3=Y3(insuitablenotation).
FIGURE2.
NotethatthepolynomialringK[X1,...,Xn]isapolytopalalgebra,namelyK[∆n−1]where∆n−1denotesthe(n−1)-dimensionalunitsimplex.
ItisoftenusefultoreplaceapolytopePbyamultiplecPwithc∈N.ThelatticepointsincPcanbeidentifiedwiththelatticepointsofdegreecintheconeC(SP);infact,thelatterareexactlyoftheform(x,c)wherex∈LcP.
Polytopalsemigroupalgebrasappearasthecoordinateringsofprojectivetoricvari-eties;seeOda[Oda]
3.HILBERT
BASESOFAFFINENORMALSEMIGROUPS
3.1.Normalityandcovering.InthissectionwewillinvestigatethequestionwhetherthenormalityofapositiveaffinesemigroupcanbecharacterizedintermsofcombinatorialconditionsonitsHilbertbasis.
LetCbeaconeinRngeneratedbyfinitelymanyrational(orintegral)vectors.WesaythatacollectionofrationalsubconesC1,...,CmisatriangulationofCifCiissimplicialforalli(i.e.generatedbyalinearlyindependentsetofvectors),C=C1∪···∪CmandCi1∩···∩CikisafaceofCi1,...,Cikforeverysubset{i1,...,ik}⊂{1,...,m}.
LetMbeasubsetofaconeCasabove.AnM-triangulationofCisatriangulationintosimplicialconesspannedbysubsetsofM,andaHilberttriangulationisaHilb(S(C))-triangulationofC.
Correspondingly,aHilbertsubsemigroupS′ofSisasubsemigroupgeneratedbyasubsetofHilb(S).WesaythatSiscoveredbysubsemigroupsS1,...,SmifS=S1∪···∪Sm.
6
ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO
AsubsetXofZniscalledunimodularifitispartofabasisofZn;inotherwords,if
itislinearlyindependentandgeneratesadirectsummandofZn.Conesandsemigroupsareunimodulariftheyaregeneratedbyunimodularsets,andacollectionofunimodularobjectsislikewisecalledunimodular.
Proposition3.1.1.IfSiscoveredbyunimodularsubsemigroups,thenitisnormal.Moregenerally,ifSistheunionofnormalsubsemigroupsSisuchthatgp(Si)=gp(S),thenSisalsonormal.
Thisfollowsimmediatelyfromthedefinitionofnormality.
WewillseeinCorollary4.2.3thatthehypothesisgp(Si)=gp(S)issuperfluous,andthatitisevenenoughthattheSicoverS“asymptotically”.
Thefollowingconverseisimportantforthegeometryoftoricvarieties;itprovidesthecombinatorialbasisfortheequivariantresolutionoftheirsingularities.
Theorem3.1.2.EveryfinitelygeneratedrationalconeC⊂Rnhasaunimodulartrian-gulation.
ItisnotdifficulttoprovethetheoremforwhichwemayassumethatdimC=n.OnestartswithanarbitrarytriangulationofC,andconsiderseachoftheinvolvedsimplicialsubconesC′.TheshortestnonzerointegervectorsoneachoftheraysofC′formalinearlyindependentsetX.IfXisnotunimodular,thenXisnottheHilbertbasisofS(C′),andonesubdividesC′byoneofthevectorsr1x1+···+rmxmappearingintheproofofGordan’slemma.ForeachofthesimplicialsubconesC′′generatedbysubdivisionthegroupgp(S(C′′))hassmallerindexthangp(S(C′))inZn.Afterfinitelymanystepsonethusarrivesataunimodulartriangulation.
Especiallyforpolytopalsemigroups,Theorem3.1.2isnotreallysatisfactory,sinceitisnotpossibletointerpretitinthelatticestructureofapolytopeP⊂Zn.Infact,onlythesimplicialHilbertsubconesofC(SP)correspondtothelatticesimplicescontainedinP.Itisnothardtoseethattheconespannedbyalatticesimplexδ⊂Pisunimodularifandonlyifδhasthesmallestpossiblevolume1/n!.Suchsimplicesarealsocalledunimodular.Furthermore,P(regardlessofitsdimension)canbetriangulatedintoemptylatticesimplices,i.e.simplicesδsuchthatδ∩Znisexactlythesetofverticesofδ.
SupposenowthatPisalatticepolytopeofdimension2andtriangulateitintoemptylatticesimplices.Since,byPick’stheorem,anemptysimplexofdimension2hasarea1/2,oneautomaticallyhasaunimodulartriangulation.ItfollowsimmediatelythatSPistheunionofunimodularHilbertsubsemigroupsandthusnormal.Moreover,C(SP)hasaunimodularHilberttriangulation.
FIGURE3.Triangulationofalatticepolygon
PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS7
Moregenerally,Seb˝ohasshownthefollowing
Theorem3.1.3.Everypositivefinitelygeneratedconeofdimension3hasaunimodularHilberttriangulation.
WereferthereadertoSeb˝ospaper[Se]orto[BG3]fortheproof,whichisbynomeansstraightforward.ThemuchsimplerpolytopalcasediscussedaboveischaracterizedbythefactthattheelementsoftheHilbertbasisofC(S)lieinahyperplane.
Theorem3.1.3alsoholdsindimension1and2whereitiseasilyproved,butitcannotbeextendedtodimension≥4,asshownbyacounterexampleduetoBouvierandGonzalez-Sprinberg[BoGo].
Ashasbeenmentionedalready,triangulationsareveryinterestingobjectsforthege-ometryoftoricvarieties.TriangulationsalsoprovidetheconnectionbetweendiscretegeometryandGr¨obnerbasesofthebinomialidealdefiningasemigroupalgebra.SeeSturmfels[Stu1]forthisimportantandinterestingtheme;wewillbrieflydiscussitinSection5.
DespiteofcounterexamplestotheexistenceofunimodularHilberttriangulationsindimension≥4,itisstillreasonabletoconsiderthefollowing,verynaturalsufficientconditionofunimodularHilbertcoveringforpositivenormalsemigroupsS:(UHC)SiscoveredbyitsunimodularHilbertsubsemigroups.
Forpolytopalsemigroups(UHC)hasacleargeometricinterpretation:itjustsaysthatPistheunionofitsunimodularlatticesubsimplices.Seb˝o[Se,ConjectureB]hasconjecturedthat(UHC)issatisfiedbyallnormalaffinesemigroups.Belowwepresenta6-dimensionalcounterexampletoSeb˝o’sconjecture.Howevertherearealsopositiveresultson(UHC)andevenonunimodulartriangulationsformultiplescPofpolytopes;seeSubsection3.3.
Anaturalvariantof(UHC),andweakerthan(UHC),istheexistenceofafreeHilbertcover:
(FHC)Sistheunion(orcoveredby)thesubsemigroupsgeneratedbythelinearlyinde-pendentsubsetsofHilb(S).
For(FHC)–incontrastto(UHC)–itisnotevidentthatitimpliesthenormalityofthesemigroup.Neverthelessitdoesso,aswewillseeinCorollary4.2.3.Aformallyweaker–andcertainlythemostelementary–propertyistheintegralCarath´eodoryproperty:(ICP)EveryelementofShasarepresentationx=a1s1+···+amsmwithai∈Z+,si∈Hilb(C),andm≤rankS.
Herewehaveborrowedthewell-motivatedterminologyofFirlaandZiegler[FZ]:(ICP)isobviouslyadiscretevariantofCarath´eodory’stheoremforconvexcones.ItwasfirstaskedinCook,Fonlupt,andSchrijver[CFS]whetherallconeshave(ICP)andthenconjecturedin[Se,ConjectureA]thattheansweris‘yes’.LateronwewillusetherepresentationlengthforanelementxofapositiveaffinesemigroupS.Ifρ(x)≤m,wealsosaythatxism-represented.InordertomeasurethedeviationofSfrom(ICP),weintroducethenotion
ρ(x)=min{m|x=a1s1+···+amsm,ai∈Z+,si∈Hilb(S)}
8
ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO
ofCarath´eodoryrankofanaffinesemigroupS,
CR(S)=max{ρ(x)|x∈S}.
Variantsofthisnotion,calledasymptoticandvirtualCarath´eodoryrankwillbeintro-ducedinSection4.
Thefollowing10vectorsconstitutetheHilbertbasisofanormalpositivesemigroupS6:
z1=(0,1,0,0,0,0),z2=(0,0,1,0,0,0),z3=(0,0,0,1,0,0),z4=(0,0,0,0,1,0),z5=(0,0,0,0,0,1),
z6=(1,0,2,1,1,2),z7=(1,2,0,2,1,1),z8=(1,1,2,0,2,1),z9=(1,1,1,2,0,2),z10=(1,2,1,1,2,0).
Asacounterexampleto(UHC)itwasfoundbythefirsttwoauthors[BG1].IncooperationwithHenk,MartinandWeismantel[BGHMW]itwasthenshownthatCR(S6)=7sothat(ICP)doesnotholdforallnormalaffinesemigroupsS.TheconeC6andthesemigroupS6=S(C6)haveseveralremarkableproperties;forexample,Aut(S6)operatestransitivelyontheHilbertbasis.Thereadercaneasilycheckthatz1,...,z10lieonahyperplane.ThereforeS6=SPfora5-dimensionallatticepolytopeP.Furtherdetailscanbefoundinthepapersjustquoted.
AcrucialideainfindingS6wastheintroductionoftheclassoftightconesandsemi-groups;see[BG1].
SofaronedoesnotknowasemigroupSsatisfying(ICP),butnot(UHC).Thissuggeststhefollowingproblem:
Problem1.Does(ICP)imply(UHC)?
Sincethepositiveresultsendindimension3andthecounterexamplelivesindimension6,thesituationiscompletelyopenindimensions4and5:
Problem2.Proveordisprove(ICP)and/or(UHC)indimension4and5.
Wehaveseenabovethateverytriangulationofalatticepolygonintoemptylatticesimplicesisunimodular.Thispropertyistrulyrestrictedtodimensionatmost2.Infact,Hosten,MacLagan,andSturmfels[HMS]havegivenanexampleofa3-dimensionalconethatcontainsnofinitesetMoflatticepointssuchthateverytriangulationofCusingallthepointsofMisunimodular.
3.2.AnupperboundforCarath´eodoryrank.Letp1,...,pnbedifferentprimenum-bers,andsetqj=∏i=jpi.LetSbethesubsemigroupofZ+generatedbyq1,...,qn.Sincegcd(q1,...,qn)=1,thereexistsanm∈Z+withu∈Sforallu≥m.Chooseu≥msuchthatuisnotdivisiblebypi,i=1...,n.ThenalltheqimustbeinvolvedintherepresentationofubyelementsofHilb(S).ThisexampleshowsthatthereisnoboundofCR(S)intermsofrankSwithoutfurtherconditionsonS.
FornormalSthereisalinearboundforCR(S)asgivenbySeb˝o[Se]:Theorem3.2.1.LetSbeanormalpositiveaffinesemigroupofrank≥2.ThenCR(S)≤2(rank(S)−1).
PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS9
([0,x]=conv(0,x)isthelinesegmentjoining0andx).Inotherwords,thebottomisexactlythesetofpointsofC′(S)thatarevisiblefrom0(seeFigure4).
FortheproofwedenotebyC′(S)theconvexhullofS\\{0}(ingp(S)⊗R).ThenwedefinethebottomB(S)ofC′(S)by
B(S)=x∈C′(S):[0,x]∩C′(S)={x}
C′(S)FIGURE4.Thebottom
LetHbeasupporthyperplaneintersectingC′(S)inacompactfacet.ThenthereexistsauniqueprimitiveZ-linearformγongp(S)suchthatγ(x)=a>0forallx∈H(after
/,onehasa∈Z.Wecallγthetheextensionofγtogp(S)⊗R).SinceHilb(S)∩H=0
basicgradingofSassociatedwiththefacetH∩C′(S)ofC′(S).Itcanbethoughtofasthegradedstructure
degγ:S→Z+,x→γ(x).ProofofTheorem3.2.1.ItiseasilyseenthatthebottomofSistheunionoffinitelymany
latticepolytopesF,allofwhoselatticepointsbelongtoHilb(S).WenowtriangulateeachFintoemptylatticesubsimplices.Choosex∈S,andconsiderthelinesegment[0,x].ItintersectsthebottomofSinapointybelongingtosomesimplexσappearinginthetriangulationofacompactfacetFofC′(S).Letz1,...,zn∈Hilb(S),n=rank(S),betheverticesofσ.Thenwehave
x=(a1z1+···+anzn)+(q1z1+···+qnzn),
asintheproofofGordan’slemma.Setx′=∑ni=1qizi,letγbethebasicgradingofSassociatedwithF,anda=γ(y)fory∈F.Thenγ(x′) InviewofTheorem3.2.1itmakessensetoset CR(n)=maxCR(S):SisnormalpositiveandrankS=n. ai∈Z+,qi∈Q,0≤qi<1, 10 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO WiththisnotionwecanreformulateTheorem3.2.1asCR(n)≤2(n−1).Ontheother hand,thecounterexampleS6to(ICP)presentedaboveimpliesthat 7n CR(n)≥ 4hasmeanwhilebeensolvedpositively.SeeW.BrunsandJ.Gubeladze,Unimodularcovers ofmultiplesofpolytopes(inpreparation),whereasubexponentialboundforc0isgiven. 1Problem PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS11 4.ALGORITHMS FORCOVERINGS AnaffinesemigroupSisasubsetofafreeabeliangroupequippedwithaminimalamountofalgebraicstructure,butthissufficestospecifySbyfinitedata,namelyagener-atingset.Therefore,thequestionofdecidingwhetheranaffinesemigroupistheunionofagivensystemofsub-semigroups,alsospecifiedintermsofgenerators,seemsinterest-ing.InthissectionwedevelopanalgorithmdecidinginafinitenumberofstepswhetherSiscoveredbyasystemofsubsemigroups.Actually,intheprocessofcheckingthispropertywehavetotreatthemoregeneralsituationof“modules”overaffinesemigroups.TheconnectionwithCarath´eodoryranksand(ICP)willalsobeoutlined. Thealgorithmcontainssubalgorithmsforcheckingasymptoticandvirtualcoveringproperties. ForsubsetsA,B⊂Znweusethefollowingnotation π(A|B)=lim #{a∈A∩B:a<ε} ε→∞ 12 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO ConsideranaffinesemigroupSandafinitefamilyofaffinesemigroups S1,...,St⊂S. WesaythatSiscoveredasymptoticallybytheSiifπ(S1∪···∪St|S)=1.Oneshould observethatthenotionofasymptoticcoveringisanintrinsicpropertyofthesemigroupSandthefamily{S1,...,St}.Inotherwords,itdoesnotS→Zn.dependontheembedding Further,SissaidtobevirtuallycoveredbytheSiif#S\\(S1∪···∪St)<∞. NowassumewearegivenafinitelygeneratedS-moduleMandSi-submodulesMi⊂MsothatMi∈M(Si)i∈[1,t].Onethenintroducesthenotionsofcovering,asymptoticcoveringandvirtualcoveringofMbytheMiintheobviousway. ¯⊂S}Lemma4.2.1.ForanaffinesemigroupStheconductoridealcS¯/S={x∈S:x+S isanonemptyset. ¯beafinitegeneratingsetofS¯asamoduleProof.LetGbeageneratingsetofSandG ¯isinfactafinitelygeneratedS-module,hasbeenstatedinLemma2.1.1.overS.ThatS ¯,xz,yz∈G.Then∑z∈Gyz∈cSFixrepresentationsz=xz−yz,z∈G¯/S.¯onceagen-SinceonecaneffectivelycomputeasystemofgeneratorsoftheS-moduleS eratingsetofSisgiven,theproofofLemma4.2.1providesanalgorithmforcomputinganelementofcS¯/SifageneratingsetofSisgiven.ThisalgorithmiscalledCONDUCTOR.ConsideranaffinesemigroupS⊂Znandafamilyofaffinesub-semigroupsS1,...,St⊂S,t∈N.TheirconesinRnwillbedenotedcorrespondinglybyC(S),C(S1),...,C(St).Afamilyofnon-emptymodulesM∈M(S),M1∈M(S1),...,Mt∈M(St),suchthatM1,...,Mt⊂M(⊂Zn),isalsoassumedtobegiven.Put Σ=σ⊂[1,t]:dim(C(Si))=rankSandgp(Si)=gp(S) i∈σ i∈σ and Cσ= i∈σ C(Si),σ∈Σ. Lemma4.2.2.SisasymptoticallycoveredbyS1,...,StifandonlyifC(S)=ΣCσ. Moreover,MisasymptoticallycoveredbytheMiifandonlyifthefollowingimplicationholdsforeveryz∈Zn:/)(z+gp(S))∩M=0 =⇒ /}.Sisasymptoticallycoveredby{Sj:j∈[1,t],(z+gp(S))∩Mj=0 Proof.ConsiderfinitegeneratingsetsG⊂Si,i∈[1,n].TheaffinehyperplanesinR⊗ni gp(S),spannedbytheelementsof1Gi,cuttheconeC(S)intosubconeswhichwecallelementarycells,i.e.theelementarycellsarethemaximaldimensionalconesintheobtainedpolyhedralsubdivisionofC(S).Clearly,theelementarycellsareagainfiniterationalcones.SobyGordan’slemmathesemigroupsS∩Careallaffine.(ThegeneralformofGordan’slemmausedhereandbelowfollowsfrom2.1.1and[BG2,7.2].) PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS13 whereσE={i∈[1,n]:E⊂C(Si)},Erunningthroughthesetelementarycells. WeclaimthatSisasymptoticallycoveredifandonlyifσE∈Σ.Thisclearlyprovesthefirstpartofthelemma. The“onlyif”partoftheclaimfollowseasilyfromthefactthatgp(S∩E)=gp(S).Forthe“if”partwepickelementszi∈cS¯i/Si,i∈σE(Lemma4.2.1).ThentheassumptionσE∈Σimplies S0:=gp(S)∩E∩zi+C(Si)⊂S∩E i∈σE SisasymptoticallycoveredbytheSiifandonlyifπS1∪···∪SnS∩E=1forevery elementarycellE,orequivalently πSi∩ES∩E=1 i∈σE Nowassumetheimplication=⇒ofthelemmaholds.Miscontainedinfinitelymany residueclassesinZnmodulogp(S).Byfixingoriginsintheseclassesandtakinginter-sectionswiththemodulesM,M1,...,Mt,thegeneralcasereducestothesituationwhenM,M1,...,Mt⊂gp(S).Pickelementsyi∈Mi.Thenwehave Mσ:=gp(S)∩yi+zi+C(Si)⊂M,σ∈Σ, i∈σ andwearedonebecausebyelementarygeometricconsiderationonehas πSi∩ES0=1. i∈σE withthezichosenasabove.Wearedonebythefollowingobservations: Mσ⊂ and π i∈σ Mi σ∈Σ thelatterequalitybeingeasilydeducedfromtheconditionC(S)=ΣCσ. NowassumeMisasymptoticallycoveredbytheMi.Thenwehavetheimplication/)(z+gp(S))∩M=0 =⇒ (z+gp(S))∩Misasymptoticallycoveredby/}.{(z+gp(S))∩Mj:j∈[1,t],(z+gp(S))∩Mj=0 MσM=1, Itonlyremainstonoticethateachofthese(s+gp(S))∩Mjisasymptoticallycoveredby mj+Sforanarbitraryelementmj∈(z+gp(S))∩Mj,and,similarly,(z+gp(S))∩Misasymptoticallycoveredbym+S,m∈(z+gp(S))∩M. TheproofofLemma4.2.2givesanalgorithmdecidingwhetherSisasymptoticallycoveredbyS1,...St,usingexplicitgeneratingsetsasinput.Infact,theconditions(i)thatafiniterationalconeiscoveredbyasystemoffiniterationalsubconesand(ii)thatafinitelygeneratedfreeabeliangroupiscoveredbyasystemofsubgroups,canbothbecheckedeffectively.Itisofcoursenecessarythatweareabletocomputetheconeofanaffine 14 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO (ρistherepresentationlength,seeSubsection3.1),andthevirtualCarath´eodoryrank CRv(S)isdefinedas minr:#(S\\{x∈S:ρ(x)≤r})<∞.Lemma4.2.2hasthefollowing semigrouponceageneratingsetofthesemigroupisgiven(NORMALIZ),toformtheintersectionofasystemoffiniterationalcones(givenintermsofthesupportinequalities)and,furthermore,tocomputethegroupofdifferencesofanaffinesemigroups. Infact,fortheconecoveringpropertywefirsttriangulatethegivenconeC(usingonlyextremegenerators)andtheninspectsuccessivelytheresultingsimplicialsubconesasfollows.IfsuchasimplicialconeTiscontainedinoneofthegivencones,sayC1,...,Ct,itisneglectedandwepasstoanothersimplicialcone.IfitisnotcontainedinanyoftheconesC1,...,Ct,thenwesplitTintotwocones(ofthesamedimension)bytheaffinehullofafacetF⊂Ciforsomei∈[1,t].ThereafterthetwopiecesofTaretestedforthecontainmentpropertyinoneoftheCi.IfsuchafacetFinnotavailable,CisnotcoveredbytheCi.Theprocessmuststopbecauseweonlyhavefinitelymanyaffinespacesforsplittingtheproducedcones. Asforthegroupcoveringtest,wefirstformtheintersectionUofallthegivenfullranksubgroupsG1,...,Gm⊂Zr.ThenwecheckwhetheranelementofeachthefinitelymanyresidueclassesinZr/UinZrbelongstooneoftheGj. Moreover,usingthealgorithmINTERSECTIONinSubsection4.3below,whichcom-putesintersectionsofmoduleswithaffinesubspaces,wecanalsogiveanalgorithmfordecidingwhetherMisasymptoticallycoveredbyM1,...Mt(againusinggeneratingsetsasinput).OneonlyneedstoconsiderthefinitenumberofresidueclassesinZnmodulogp(S)representedbythegivengeneratorsofM–theirunioncontainsM. Theobtainedalgorithms,checkingtheasymptoticcoveringconditionbothforsemi-groupsandmodules,willbecalledASYMPTOTIC.Werecallfrom[BG1]thattheasymptoticCarath´eodoryrankCRa(S)ofapositiveaffinesemigroupS⊂Znisdefinedas minr:π({x∈S:ρ(x)≤r}|S)=1. Corollary4.2.3.(a)SupposeS⊂ZnisanaffinesemigroupandS1,...,Stareaffine sub-semigroupsS1,...,StofS.Ifthesesub-semigroupsarenormalandcoverSasymptotically,thenSisnormalandcoveredbyS1,...,St. (b)AssumeS⊂Znisapositiveaffinesemigroup.IfCRa(S)=rankSthenSisnormal, CRv(S)=CR(S)=rankSand,moreover,Ssatisfies(FHC).Inparticular,(ICP)and(FHC)areequivalentandtheyimplythenormality. (c)ForSasinuprightthereisanalgorithmforcomputingCR(S)and,inparticular,for checking(ICP)infinitelymanysteps.Proof.Claim(a)isadirectconsequenceofLemma4.2.2.Claim(b)followsfromthesamelemmaandtheobservationthatifCRa(S)=rankS,thenthefullrankfreesub-semigroupsofS,generatedbyelementsofHilb(S),coverSasymptotically.ThisissobecausethecontributionfromdegeneratesubsetsofHilb(S)is“thin”andcannotaffecttheasymptoticcoveringproperty.(c)followsfrom(b)andASYMPTOTIC. PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS15 Remark4.2.4.AmotivationfortheintroductionofasymptoticandvirtualCarath´eodoryranksofpositivesemigroupsisthefollowingimprovementofSeb˝o’sinequality3.2.1.SupposeSisanaffinepositivenormalsemigroupandrankS≥3;then CRa(S)≤2rankS−3 andif,inaddition,Sissmooth,then CRv(S)≤2rankS−3. S−1 “Smooth”heremeansZx+S≈Z⊕ZrankforeachextremegeneratorofS.(Equiv-+ alently,forafieldKthevarietySpec(K[S])\\{m}issmooth,wheremisthemonomialmaximalidealofK[S].)Theseinequalitieshavebeenprovedin[BG1]. 4.3.Virtualcovers.Nowwedevelopanalgorithmcheckingthevirtualcoveringcondi-tion.Firstweneedanauxiliaryalgorithmthatcomputesintersectionsofsemigroupsandmoduleswithaffinespaces. Moreprecisely,assumeS⊂ZnisanaffinesemigroupandM⊂ZnisafinitelygeneratedS-module,bothgivenintermsofgeneratingsets,sayGSandGM.LetH0⊂Rnbearationalsubspace,givenbyasystemofrationallinearforms,andh∈Qn.ByGordan’slemmaS0=S∩H0isanaffinesemigroupandby[BG2,7.2]Mh=M∩(h+H0)isafinitelygeneratedmoduleoverit.Ourgoalistofindtheirgeneratingsets. Byconsideringtheintersections(z+S)∩(h+H0),zrunningthroughGMonereducesthetasktothespecialcasewhenMisgeneratedbyasingleelement,i.e.whenMisaparallelshiftofSinZn,saybyz.ChangingMby−z+Mandhbyh−zwecanadditionallyassumeM=S.Furthermore,takingtheintersectionH0∩(R⊗gp(S)),wemaysupposethatH0⊂R⊗gp(S).Inotherwords,itisenoughtoconsiderthecasen=rankS. Fixasurjectivesemigrouphomomorphismϕ:Zs+→S,s=#GS,mappingthestandard sgeneratorsofZn+totheelementsofGS.ItgivesrisetoasurjectivelinearmappingR→ Rnwhichwedenoteagainbyϕ.NextwecomputeKer(ϕ)and,usingit,thepreimageL0=ϕ−1(H0)–thelatterisgeneratedbyKer(ϕ)andarbitrarilychosenpreimagesofabasisoftherationalspaceH0.Thenwefindanelementl∈ϕ−1(h).(Findingpreimagesrequiresonlysolvinglinearsystemsofequations.) WhenwehavecomputedageneratingsetofthesemigroupZs+∩L0andthatofthemoduleZs+∩(l+L0)overit,then,byapplyingϕ,wefindthedesiredgeneratingsets.Inotherwords,wehavefurtherreducedtheproblemtothespecialcasewhenS=Zn+.ThesemigroupZn+∩H0isnormalandpositive.ItsHilbertbasisiscomputedusingNOR-MALIZ. /.Thisisdoneasfollows.WecomputeaNextwecheckwhetherZn∩(h+H0)=0 groupbasisB1ofH0∩ZnandfindasystemofvectorsB2,disjointformB1,suchthatB1∪B2isabasisofZn.ThenB2correspondstoabasisoftherealspaceRn/H0.Weonlyneedtocheckthattheresidueclassofhisintegralwithrespecttoit.Thisisanecessary /.andsufficientconditionforZn∩(h+H0)=0 /,thenwecanpickalatticepointpinZn∩(h+H0).WedeclareIfZn∩(h+H0)=0 itastheoriginoftheaffinesubspacep+H0withthecoordinatesystemrepresentedbyp+B1. 16 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO nNextwecomputetheintersectionsC=Rn+∩H0andP=R+∩(h+H0),representing thembysystemsofinequalitiesinthecoordinatesystemsofH0andh+H0,whicharegivenbyB1andp+B1respectively. WecanmakethenaturalidentificationH0=Rm,m=#B1.ConsidertheconvexhullΠinRm+1ofthesubset (C,0)∪(−p+P,1)⊂Rm+1. ThecrucialobservationisthatΠisafiniterationalpointedcone(forasimilarconstructioninthecontextofdivisorialidealssee[BG2,Section5]).Then,usingagainNORMALIZwecomputeHilb(Π).ThelaststepconsistsoflistingthoseelementsofHilb(Π)whichhave1asthelastcoordinate.ReturningtotheoldcopyofRntheseelementsrepresenttheminimalgeneratingsetof ThisalgorithmwillbecalledINTERSECTION. NotethatwedonotexcludethecasewhenH0∩S={0}.ThenthealgorithmabovejustliststheelementsofthefinitesetM∩(h+H0). NowassumeS1,...,St⊂SandM,M1,...,MtareasinSubsection4.2,givenintermsoftheirgenerators.ByΣ,CσandziwerefertothesameobjectsasinLemma4.2.2.Wewilldescribeanalgorithmdecidingthevirtualcoveringpropertyforthegivensemigroupsandmodules.ItusesinductiononrankS. InthecaserankS=1oneeasilyobservesthatasymptoticandvirtualcoveringcondi-tionscoincidebyLemma4.2.1.SowecanapplyASYMPTOTIC. AssumerankS>1.UsingASYMPTOTICwefirstcheckthatwehaveatleastasymp-toticcovering.Letusfirstconsiderthecaseofsemigroups.Foreveryσ∈Σwecanpickanelement zσ∈i∈σ(zi+C(i)).Then Sσ:=gp(S)∩(zσ+Cσ)⊂S. Animportantobservationisthatthecomplement(Cσ∩S)\\Sσiscontainedinfinitelymanysetsofthetype(h+RF)∩S,whereh∈gp(S)andF⊂Cσisafacet.(RFreferstothelinearspacespannedbyF.)Moreover,wecanlistexplicitlysuchaffinesubspacesh+RFthatcoverthiscomplement.Namely,foranyfacetF⊂Cσweconsiderasystemofvectors {h0,h1,...,hvF(zσ)}⊂gp(S) n Rn+∩(h+H0)∈M(R+∩H0). satisfyingtheconditionvF(hj)=j,j∈[0,vF(zσ)],wherevF:gp(S)→Zisthesurjective grouphomomorphismuniquelydeterminedbytheconditionsv(RF∩gp(S))=0andvF((Cσ∩gp(S))≥0. ThesemigroupSisvirtuallycoveredbyS1,...,StifandonlyifS∩(h+RF)∈M(S∩RF)isvirtuallycoveredbythemodules forallthe(finitelymany)possibilitiesσ∈Σ,F⊂Cσandh∈gp(S)asabove. AlloftheseintersectionsemigroupsandmodulescanbecomputedwithINTERSEC-TION.Therefore,havingdecreasedtherankbyone,wecanuseinduction. Si∩(h+RF)∈M(Si∩RF), i∈[1,t] PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS17 InthecaseofmoduleswefirstreducethegeneralcasetothesituationwhenM⊂gp(S)–wejustsplittheproblemintofinitelymanysimilarproblemscorrespondingtothesetofresidueclassesofthegivengeneratorsofMmodulogp(S).Wethenpickelements(say,amongthegivengenerators)yi∈Mi,i∈[1,t]andalsoelements mσ∈ Wehave Mσ:=gp(S)∩(mσ+Cσ)⊂M, σ∈Σ. LetmbeanelementofthegivengeneratingsetforM.Thenthecomplement(M∩(m+Cσ))\\Mσiscontainedinfinitelymanysetsofthetype(h+RF)∩M,wheretheFareasaboveandtheh∈gp(S)constituteafinitesystemsuchthatthevF(h)exhausttheintegersbetweenvF(m)andvF(mσ).Weseethatallthestepswehavecarriedoutforthesemigroupscanbeperformedinthesituationofmodulesaswell–weonlyneedtogothroughthewholeprocessforeverygeneratorofM. Theproducedalgorithm,decidingthevirtualcoveringproperty,iscalledVIRTUAL.4.4.Covers.Nowwecompletethealgorithmdecidingcoveringpropertyforsemigroupsandtheirmodules,asmentionedatthebeginningofSection4.ThealgorithmwillbecalledCOVERING.Again,weuseinductiononrankofthebigsemigroup.AnalyzingVIRTUALoneobservesthattheinductivestepindevelopingCOVERINGcanbecopiedword-by-wordfromVIRTUAL.SotheonlythingweneedtodescribeisCOVERINGforrank1semigroups. AssumeS,S1,...,StandM,M1,...,Mtareasaboveand,inaddition,rankS=1.WerestrictourselvestothecasewhenSispositive.Theothercasecanbedonesimilarly.Aftercomputinggp(S),wecanassumegp(S)=Zwithoutlossofgenerality.SinceZiscoveredbyafinitesystemofsubgroupsexactlywhenoneofthesubgroupsisthewholeZwemustcheck(accordingtoLemma4.2.2)thatoneofthegroupsgp(S1),...,gp(St)coincideswithZ.Assumegp(S1)=Z.ByCONDUCTORwefindanelementz∈cS¯1/S1.Nowweonlyneedtomakesurethatthefiniteset[1,z]∩SisintheunionS1∪···∪St.ForthemoduleswefirstreducethegeneralcasetothesituationM⊂Z(aswedidintheprevioussubsection)and,byasuitableshift,furthertothespecialcase0∈M⊂Z+. /.Then,again,weByLemma4.2.2thereisnolossofgeneralityinassumingthatM1=0 onlyhaveafiniteproblemofcheckingthat[0,z+m]∩M⊂M1∪···∪Mt,wherezisasaboveandm∈M1isarbitrarilychosenelement(say,agivengenerator). Remark4.4.1.Asmentioned,ourgoalinthissectionwastoshowthatthequestionwhetheragivenaffinesemigroupiscoveredbyafinitesystemofaffinesub-semigroupscanbecheckedalgorithmically.However,wedidnottrytomakethealgorithmasopti-malaspossible.Forinstance,ourargumentsuseheavilyconductoridealsandweworkwithrandomelementsintheseideals.OntheotherhandinsomespecialcasesonecancomputecS¯/Sexactly.EspeciallythisispossibleinthesituationwhenSisapositiveaffinesemigroup,generatedbyrankS+1elements;see[RR]. Therealmotivationforimplementingapartofthealgorithmsabovewouldbeasemi-groupthatviolates(UHC),butresistsallrandomtestsfordetectingtheviolationof(ICP) i∈σ (yi+zi+C(Si)),σ∈Σ. 18 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO (or,equivalently,(FHC);seeCorollary4.2.3(b)).Unfortunately,sofarwehaveonlyfound 2essentiallydifferentsemigroupsviolating(UHC),andtheyviolate(ICP)too. 5.ALGEBRAIC PROPERTIESOFAFFINESEMIGROUPALGEBRAS InthissectionwealwaysconsideraffinesemigroupsSofZr+(oftenrwillbetherankofS,butwedonotnecessarilyassumethis).ThentheaffinesemigroupalgebraK[S]overafieldKcanbeviewedasasubalgebraofthepolynomialringK[T1,...,Tr]. 5.1.Definingequations.LetHilb(S)={x1,...,xn}.Considerthesemigrouphomomor-phismπ:Zn+→Sgivenby(u1,...,un)→u1x1+...+unxn.LetK[X]=K[X1,...,Xn]beapolynomialringoverafieldKinnindeterminates.Themapπliftstoahomomorphismofsemigroupalgebrasϕ:K[X]→K[S].ThekernelofϕisaprimeidealISinK[X]andwehavearepresentationofthesemigroupalgebra K[S]∼=K[X]/IS. TheidealISisoftencalledthetoricidealofS.Thefollowingresultiswell-known(for example,seeGilmer[Gi]). Proposition5.1.1.ThetoricidealISisgeneratedbythesetofbinomials {Xu−Xv|u,v∈Zn+withπ(u)=π(v)}. Letµ(I)denotetheminimalnumberofgeneratorsofanidealI.Becauseoftheabove propertyofISonemightthinkthatµ(IS)couldnotbebigor,moreprecisely,thatµ(IS)wereboundedbyanumberwhichdependsonlyonthenumbern.Butthatisnotthecase.LetSbeanumericalsemigroup,thatisS⊆Z+.Ifn=2,thenµ(IS)=1becauseISisaprincipalidealinK[X1,X2].Ifn=3,Herzog[He]provedthatµ(IS)≤3.Ifn≥4,Bresinsky[Bre1]showedthatµ(IS)canbearbitrarilylarge. However,onemayexpectthatµ(IS)dependsonlyonnforspecialclassesofaffinesemigroups.LetSbegeneratedbynnon-negativeintegersx1,...,xn.Withoutrestrictionwemayassumethatx1,...,xnhavenocommondivisorotherthan1.Thenthereexistsanintegercsuchthata∈Sforallintegersa≥c(i.e.cisintheconductorideal).Letcbetheleastintegerwiththisproperty.WecallSasymmetricnumericalsemigroupifa∈Swheneverc−a−1∈S,a∈N.Example5.1.2.LetS=6,7,8.Then S={0,6,7,8,12,13,14,15,16,18,19,20,21,22,...}. Hencec=18.ItiseasytocheckthatSisasymmetricnumericalsemigroup. Theinterestonsymmetricnumericalsemigroupsoriginatedfromtheclassificationofplanealgebroidbranches[Ap].Later,HerzogandKunz[HK]realizedthatsymmetricnumericalsemigroupscorrespondtoGorensteinaffinemonomialcurves. Problem6.LetSbeasymmetricnumericalsemigroup.Doesthereexistanupperboundforµ(IS)whichdependsonlyontheminimalnumberofgeneratorsofS? PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS19 Ifn=3,Herzog[He]provedthatµ(IS)=2.Ifn=4,Bresinsky[Bre2]provedthatµ(IS)≤5.Ifn=5,Bresinsky[Bre3,Theorem1]provedthatµ(IS)≤13,providedx1+x2=x3+x4.ItwasalsoBresinsky[Bre2,p.218],whoraisedtheaboveproblemwhichhasremainedopenuntiltoday. InsteadofestimatingthenumberofgeneratorsofISonecanalsotrytoboundthedegreeofthegenerators.WewilldiscussthisprobleminSubsections5.2and5.4. Wecalltheleastintegersforwhichthereexistbinomialsf1,...,fssuchthatISistheradicaloftheideal(f1,...,fs)thebinomialarithmeticalrankofISandwewilldenoteitbybar(IS).Geometrically,thismeansthattheaffinevarietydefinedbyISistheintersec-tionofthehypersurfacesf1=0,...,fs=0.Ingeneral,wehavehtIS≤bar(IS)≤µ(IS).Problem7.Doesthereexistanupperboundforbar(IS)intermsofn? Wementiononlyafewworksonthisproblem.IfSisahomogeneous(i.e.gradedandgeneratedbyelementsofdegree1)affinesemigroupinZ2+,Moh[M]provedthatbar(IS)=n−2forKofpositivecharacteristic.ThisimpliesthatISisaset-theoreticcompleteintersection.IfKhascharacteristic0andSisasabove,thenThoma[Th]hasshownthatbar(IS)=n−2ifISisacompleteintersection,otherwisebar(IS)=n−1.TheseresultshavebeenrecentlygeneralizedbyBarile,MoralesandThoma[BMT]toaffinesemigroupalgebrasoftheform as1d1dra11a1rasr K[S]=K[t1,...,tr,t1···tr,...,t1···tr], whered1,...,dranda11,...,asrarepositiveintegers. 5.2.InitialidealsandtheKoszulproperty.LetK[X]=K[X1,...,Xn]beapolynomial u1unwiththelatticeringoverafieldk.Asusual,wewillidentifyamonomialXu=X1···Xn pointu=(u1,...,un).Atotalorder WitheverymonomialidealJwecanassociatethefollowingcombinatorialobject ∆(J):={F⊆{1,...,n}:thereisnomonomialinJwhosesupportisF} wherethesupportofamonomialXaistheset{i:ai=0}.Clearly∆(J)isa√simplicialcomplexonthevertexset{1,...,n},anditeasilyseenthatJanditsradical Jisgeneratedbyallsquare-freemonomialsXi1···Xis, i1<··· ForatoricidealISonemayaskwhetherthereisacombinatorialdescriptionoftheinitialidealin(IS)or,atleast,theirradicals. 20 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO IntheremainingpartofthissubsectionweassumethatSisahomogeneousaffine semigroupSM⊂Zr+1withHilbertbasisM={x1,...,xn}⊂Zr.ByCwedenotetheconeC(S). AnM-triangulationofCiscalledregularifthereisaweightvectorω=(ω1,...,ωn)∈Rn+suchthatthesimplicialconesofthetriangulationarespannedexactlybythosesubsetsF⊂Mforwhichthereexistsavectorc∈Rrwith c,xj<ωjc,xi=ωi ifxi∈F,ifxj∈F. Geometrically,thesimplicialconesofaregulartriangulationofC(S)aretheprojectionsofthelowerfacesoftheconvexhullPofthevectors(x1,ω1),...,(xn,ωn)inRr+1ontothefirstrcoordinates.NotethatafaceofPislowerifithasanormalvectorwithnegativelastcoordinate. ItisclearthateveryM-triangulationofC(S)canbeidentifiedwiththesimplicialcom-plexofthosesubsets{i1,...,ir}⊆{1,...,n}forwhichthevectorsxi1,...,xirspanafaceofasimplicialconeofthetriangulation.Usingthisidentification,Sturmfels[Stu1],Theorem8.3andCorollary8.4,discoveredthefollowingconnectionsbetweentheinitialcomplexesofISandthetriangulationsofC(S). Theorem5.2.1.Theinitialcomplexes∆(in(IS))areexactlythesimplicialcomplexesoftheregularM-triangulationsofC(S). Corollary5.2.2.Theidealin(IS)isgeneratedbysquare-freemonomialsifandonlyifthecorrespondingregularM-triangulationofC(S)isunimodular. Therefore,ifIShasasquare-freeinitialideal,thenSmustbenormaland,beinggen-eratedindegree1,polytopal(seeProposition3.1.1).Ontheotherhand,asthecoun-terexampleinSubsection3.1shows,thereexistnormallatticepolytopeswithoutanyuni-modulartriangulation(evenwithoutunimodularcovering).ThereforeISneednothaveasquare-freeinitialidealfornormalpolytopalsemigroupsS.(Therealsoexistpolytopesthathaveaunimodulartriangulation,butnosuchregulartriangulation;seeOhsugiandHibi[OH1].) However,asobservedinSubsection3.1,anytriangulationofalatticepolytopeofdi-mension2intoemptylatticesimplicesisunimodularbyPick’stheorem,andIShasplentyofsquare-freeinitialidealsinthisspecialsituation. TheresultsofSturmfelsgiveusamethodtoprovethatasemigroupalgebraisKoszul.RecallthatahomogeneousalgebraAoverafieldKiscalledKoszulifKasanA-modulehasaresolution: ϕ1ϕ2 ···−→E2−→E1−→A−→K−→0, whereE1,E2,...arefreeR-modulesandtheentriesofthematricesϕ1,ϕ2,...areformsofdegree1inA.FormoreinformationseethesurveyofFr¨oberg[Fr]. LetA=R/IbeapresentationofA,whereRisapolynomialringoverKandIisahomogeneousidealinR.IfAisaKoszulalgebra,thenImustbegeneratedbyquadraticforms.Theconverseisnottrue.However,AisKoszulifthereexistsatermorder Inparticular,itcanbeshownthatifPisalatticepolytopeinR2withmorethan3latticepoints,thenK[P]isKoszulifandonlyiftheboundaryofPhasmorethan3latticepoints.Itwouldbeofinteresttofindmorelatticepolytopeswhichhaveunimodularregulartriangulationswhoseminimalnon-facesareedges.ForanylatticepolytopeP⊂Rr,itisknownthatthesemigroupalgebraK[cP]isKoszulforc≥r[BGT,Theorem1.3.3].Thishasledustothefollowingproblem. Problem8.DoescP,c≫0,haveaunimodularregulartriangulation∆suchthattheminimalnon-facesof∆areedges? WehavealreadystatedthisprobleminSubsection3.3,howeverwithouttheattribute“regular”andtheconditionthattheminimalnon-facesof∆shouldbeedges.Inthiscon-nectionwehavepointedoutthatunimodulartriangulationsforcPhavebeenconstructedforinfinitelymanycin[KKMS];thesetriangulationsareinfactregular. IthasbeenaskedwhetheraKoszulsemigroupalgebraalwayshasaninitialidealgen-eratedbyquadraticmonomials.ButthisquestionhasanegativeanswerbyRoosandSturmfels[RS].Therealsoexistnormalnon-Koszulsemigroupalgebrasdefinedbyqua-draticbinomials;seeOhsugiandHibi[OH2]. 5.3.TheCohen-MacaulayandBuchsbaumproperties.Let(A,m)bealocalring.Asystemofelementsx1,...,xsofAiscalledaregularsequenceif (x1,...,xi−1):xi=(x1,...,xi−1), Itiscalledaweak-regularsequenceif m(x1,...,xi−1):xi⊆(x1,...,xi−1), i=1,...,s. polytopePhasaunimodularregulartriangulationwhoseminimalnon-facesareedges,thenthesemigroupalgebraK[P]isKoszul. Wehaveprovedin[BGT]thatthefollowingclassesoflatticepolytopeshavethisprop-erty: (1)latticepolytopesinR2whoseboundarieshavemorethan3latticepoints, (2)latticepolytopesinRrwhosefacetsareparalleltothehyperplanesgivenbythe equationsTi=0andTi−Tj=0. i=1,...,s. Letd=dimA.Asystemofdelementsx1,...,xdofAiscalledasystemofparame-tersofAiftheideal(x1,...,xd)isanm-primaryideal.ThelocalringAiscalledaCohen-Macaulayringifthereexistsan(orevery)systemofparametersofAisaregularsequence.ItiscalledaBuchsbaumringifeverysystemofparametersofAisaweak-regularsequence.IfAisafinitelygeneratedhomogeneousalgebraoverafieldandmisitsmaximalhomogeneousideal,thenwecallAaCohen-Macaulayresp.BuchsbaumringifthelocalringofAatmisCohen-Macaulayresp.Buchsbaum.Cohen-Macaulayresp.BuchsbaumringscanbecharacterizedindifferentwaysandtheyhavebeenmainresearchtopicsinCommutativeAlgebra.See[BH]and[SV]formoreinformationontheseclassesofrings. ByafundamentaltheoremofHochster[Ho]normalaffinesemigroupringsareCohen-Macaulay.ForgeneralaffinesemigroupringstheCohen-Macaulaypropertyhasbeen 22 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO characterizedin[TH,Theorem3.1],whichisbasedonearlierworkofGotoandWatanabe [GW].FortwosubsetsEandFofZrweset E±F={v±w|v∈E,w∈F}. LetF1,...,FmbethefacetsoftheconeC(S).PutSi=S−(S∩Fi)and S= ′ m Si. i=1 ForeverysubsetJoftheset[1,m]={1,...,m}weset GJ= i∈J Si\\ Sj, i∈I(S∩ j∈J andwedenotebyπJthesimplicialcomplexofnon-emptysubsetsIofJwith Fi)={0}. Theorem5.3.1.K[S]isaCohen-Macaulayringifandonlyifthefollowingconditionsaresatisfied:(a)S′=S; (b)GJiseitheremptyoracyclicoverKforeverypropersubsetJof[1,m]. ThoughBuchsbaumringsenjoymanysimilarpropertieslikethoseofCohen-Macaulayrings,onehasbeenunabletofindasimilarcharacterizationfortheBuchsbaumpropertyofK[S]. Problem9.FindcriteriaforanaffinesemigroupalgebraK[S]tobeaBuchsbaumringintermsoftheaffinesemigroupS. RecallthatanaffinesemigroupSiscalledsimplicialifC(S)isspannedbyrvec-torsofS,wherer=rankS.Geometrically,thismeansthatC(S)hasrextremeraysor,equivalently,rfacets.ThisclasscontainsallaffinesemigroupsinZ2.Goto,SuzukiandWatanabe[GSW]resp.Trung[Tr1]gavethefollowingsimplecriteriaforasimplicialaffinesemigroupalgebratobeCohen-Macaulayresp.Buchsbaum. Theorem5.3.2.LetSbeasimplicialaffinesemigroupwithd=rankgp(S).Letv1,...,vdbethevectorsofSwhichspanC(S).Then(a)K[S]isCohen-Macaulayifandonlyif(b)K[S]isBuchsbaumifandonlyif {v∈gp(S):v+vi,v+vj∈Sforsomeindicesi=j}=S; Theabovecriteriaareeveneffective.Forexampleconsider(a).Thenweformtheintersection (−si+S)∩(−sj+S) ofS-modulesandtestwhetherthismoduleiscontainedinS.Section4containsalgo-rithmsforthesetasks.Fromthering-theoreticpointofview,themainspecialpropertyofsimplicialaffinesemigroupsistheexistenceofahomogeneoussystemofparameters {v∈gp(S)|v+2vi,v+2vj∈Sforsomeindicesi=j}+Hilb(S)⊆S. PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS23 consistingofmonomials.Thereforecertainhomologicalpropertiesthatdependonsystemofparameterscanbeformulatedintermsofthesemigroup. WhatweknowonagivenaffinesemigroupisusuallyitsHilbertbasis.Therefore,weraisethefollowingstrongerproblem. Problem10.FindcriteriaforK[S]tobeaCohen-MacaulayorBuchsbaumringintermsofHilb(S). ThisproblemisnotevensolvedfortheclassofhomogeneousaffinesemigroupsinZ2+whicharegeneratedbysubsetsof whereeisagivenpositivenumber.ThealgebraofthesemigroupgeneratedbythefullsetMeisjustthehomogeneouscoordinateringofthee-thVeroneseembeddingofthe(r−1)-dimensionalprojectivespace.ThealgebrasgeneratedbysubsetsofMearethehomogeneouscoordinateringsofprojectionsofthisVeronesevariety.Gr¨obner[Gr]wasthefirstwhostudiedtheCohen-Macaulaypropertyofsuchsemi-groupalgebras.LetHbeanarbitrarysubsetofMeandS=H.IfHisobtainedfromMebydeletingone,two,orthreevectors,weknowexactlywhenK[S]isaCohen-MacaulayorBuchsbaumring[Sch,Tr1,Hoa].Ifr=2,wemayidentifyHwiththesequenceα1,...,αnofthefirstcoordinatesofthevectorsofH.TherehavebeensomeattemptstodeterminewhenK[S]isaBuchsbaumorCohen-Macaulayringintermsofα1,...,αn.Butsatisfactoryanswerswereobtainedonlyinafewspecialcases[Bre4,BSV,Tr2].5.4.Castelnuovo-Mumfordregularity.LetA=t≥0Atbeafinitelygeneratedhomo-geneousalgebraoverthefieldK.LetA=R/IbearepresentationofA,whereRisapolynomialringoverKandIahomogeneousidealofR.ThenwehaveafiniteminimalfreeresolutionofAasagradedR-module: whereE1,...,EsaregradedR-modules.LetbibethemaximumdegreeofthegeneratorsofEi,i=1,...,s.ThentheCastelnuovo-MumfordregularityofAisdefinedasthenumberItisindependentoftherepresentationofA.Infact,itcanbedefinedsolelyintermsofAasfollows. LetmdenotethemaximalhomogeneousidealofA.ForanyA-moduleMweset Γm(M):={x∈M|xmt=0forsomenumbert≥0}. ThenΓm(∗)isaleftexactadditivefunctorfromthecategoryofA-modulesintoitself.Leti(∗)denotethei-thrightderivedfunctorofΓ(∗).ThenHi(M)iscalledthei-thlocalHmmm i(M)cohomologymoduleofM(withrespecttom).IfMisagradedA-module,thenHm i(M)=iisalsoagradedA-module.WriteHmt∈ZHm(M)t.Itisknownthatreg(A)isthe i(A)=0forallt>m−iandi≥0.leastintegermsuchthatHmt TheCastelnuovo-Mumfordregularityreg(A)isanextremelyimportantinvariantbe-causeitisameasureforthecomplexityofA.Forinstance,reg(A)+1isanupperbound reg(A):=max{bi−i|i=1,...,s}.0−→Es−→···−→E1−→R−→A−→0, Me={v=(v1,...,vr)∈Zr+|v1+···+vr=e}, 24 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO forthemaximaldegreeofthedefiningequationsoftheidealI.See[EG]and[Ei]for moreinformationontheCastelnuovo-Mumfordregularity. ItisastandardfactthattheHilbertfunctiondimKAtisapolynomialPA(t)ofdegreed−1fort≫0,whered=dimA.Ifwewrite PA(t)= etd−1 PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS25 SupposenowthatPisanormallatticepolytopeofdimensiond.ThentheCastelnuovo-MumfordregularityofR=K[P]hasaverysimplegeometricdescription.Infact, reg(R)=d+1−ℓ whereℓistheminimaldegreeofalatticepointintheinteriorofC(P).Inparticular,onealwayshasreg(A)≤d,anditfollowsthattheidealI=ISPisgeneratedbybinomialsofdegree≤d+1.Iteasilyseenthattheboundd+1isattainedifPisasimplex(i.e.spannedbyd+1latticepoints)withatleastonelatticepointinitsinterior,butnolatticepointsinitsboundarydifferentfromitsvertices.However,nocounterexampleseemstobeknowntothefollowingquestion: Problem12.LetPanormallatticepolytopeofdimensiondwhoseboundarycontainsatleastd+2latticepoints.IsK[P]definedbybinomialsofdegree≤d? Clearlytheansweris“yes”ifPhasnointeriorlatticepoint,andaswehaveseenintheprevioussection,itisalso“yes”ford=2sinceford=2onecanevenfindaGr¨obnerbasisofIofbinomialsofdegree2ifPcontainsatleast4latticepointsinitsboundary.Asfarasthecombinatoricsoftriangulationsisconcerned,theresultcanbeextendedtohigherdimension.Infact,onehasthefollowingtheorem([BGT,3.3.1]) Theorem5.4.1.LetPbealatticepolytopeofdimensiondwithatleastd+2latticepointsinitsboundaryandatleastoneinteriorlatticepoint.ThenPhasaregulartriangu-lation∆intoemptylatticesimplicessuchthattheminimalnon-facesof∆havedimension≤d−1. Sinceonecannotexpectthetriangulationtobeunimodularford≥3,thetheoremonlyboundsthedegreeofthegeneratorsof 26 ˆVIETˆTRUNGWINFRIEDBRUNS,JOSEPHGUBELADZE,ANDNGO [Bre3]H.Bresinsky,MonomialGorensteinideals,Manuscr.Math.29(1979),159–181. [Bre4]H.Bresinsky,MonomialBuchsbaumidealsinPr,Manuscr.Math.47(1984),105–132. [BSV]H.Bresinsky,P.SchenzelandW.Vogel,Onliaisons,arithmeticalBuchsbaumcurvesandmono-mialcurvesinP3,J.Algebra86(1984),283–301. [BG1]W.BrunsandJ.Gubeladze,Normalityandcoveringpropertiesofaffinesemigroups,J.Reine Angew.Math.510(1999),151–178. [BG2]W.BrunsandJ.Gubeladze,Divisoriallinearalgebraofnormalsemigrouprings,Algebr.Repre-sent.Theory,toappear. [BG3]W.BrunsandJ.Gubeladze,Semigroupalgebrasanddiscretegeometry,S´eminairesetCongr`es,to appear. [BGHMW]W.Bruns,J.Gubeladze,M.Henk,A.Martin,andR.Weismantel,Acounterexampletoan integeranalogueofCarath´eodory’stheorem,J.ReineAngew.Math.510(1999),179–185. [BGT]W.Bruns,J.Gubeladze,andN.V.Trung,Normalpolytopes,triangulations,andKoszulalgebras, J.ReineAngew.Math.485(1997),123–160. [BH]W.BrunsandJ.Herzog.Cohen–Macaulayrings(Rev.Ed.),CambridgeUniversityPress,1998.[BK]W.BrunsandR.Koch,Normaliz,aprogramtocomputenormalizationsofsemi-groups.Availablebyanonymousftpfromftp.mathematik.Uni-Osnabrueck.DE/pub/osm/kommalg/software/. [CFS]W.Cook,J.Fonlupt,andA.Schrijver,AnintegeranalogueofCarath´eodory’stheorem,J.Comb. Theory,Ser.B40(1986),63-70. [De]M.Demazure,Sous-groupesalg´ebriquesderangmaximumdugroupedeCremona,Ann.Sci. ´EcoleNorm.Sup.(4)3(1970),507-588. [Ei]D.Eisenbud,Commutativealgebrawithaviewtowardsalgebraicgeometry,Springer1995. [EG]D.EisenbudandS.Goto,Linearfreeresoultionsandminimalmultiplicity,J.Algebra88(1984), 89–133. [FZ]R.T.FirlaandG.M.Ziegler,Hilbertbases,unimodulartriangulations,andbinarycoversof rationalpolyhedralcones,DiscreteComp.Geom.21(1999),205–216. [Fr]R.Fr¨oberg,Koszulalgebras,preprint,LectureNotesPureAppl.Math.20Dekker(1999),337–350.[Gi]R.Gilmer,Commutativesemigrouprings,U.ChicagoPress,1984. [GSW]S.Goto,N.Suzuki,andK.Watanabe,Onaffinesemigrouprings,JapanJ.Math.2(1976),1–12.[GW]S.GotoandK.Watanabe,Ongradedrings,II(Zn-gradedrings),TokyoJ.Math.1(1978),237– 261. ¨[Gr]W.Gr¨obner,UberVeronesescheVariet¨atenundderenProjektionen,Arch.Math.16(1965),257– 264. [GLP]L.Gruson,R.Lazarsfeld,andC.Peskine,OnatheoremofCastelnuovoandtheequationsdefining spacecurves,Invent.Math.72(1983),301–316. [He]J.Herzog,GeneratorsandrelationsofAbeliansemigroupsandsemigrouprings,Manuscr.Math. 3(1970),175–193. [HK]J.HerzogandE.Kunz,DieWertehalbgruppeeineslokalenRingsderDimension1,Ber.Heidel-bergerAkad.Wiss.,IIAbh.(1971). [Hoa]L.T.Hoa,ClassificationofthetripleprojectionsofVeronesevarieties,Math.Nachr.128(1986), 185–197. [Ho]M.Hochster,Ringsofinvariantsoftori,Cohen–Macaulayringsgeneratedbymonomials,and polytopes,Ann.Math.96(1972),318–337. [HMS]S.Hosten,D.Maclagan,andB.Sturmfels,Supernormalvectorconfigurations,preprint.[KS]J.-M.KantorandK.S.Sarkaria,Onprimitivesubdivisionsofanelementarytetrahedron,preprint.[KKMS]G.Kempf,F.Knudsen,D.Mumford,andB.Saint-Donat,ToroidalembeddingsI,LectureNotes inMath.339,Springer,1973. [M]T.T.Moh,Set-theoreticcompleteintersection,Proc.Amer.Math.Soc.94(1985),217–220. [Oda]T.Oda,Convexbodiesandalgebraicgeometry(Anintroductiontothetheoryoftoricvarieties), Springer,1988. PROBLEMSANDALGORITHMSFORAFFINESEMIGROUPS27 [OH1]H.OhsugiandT.Hibi,Anormal(0,1)-polytopenoneofwhoseregulartriangulationsisunimodu-lar,DiscreteComput.Geom.21(1999),201–204. [OH2]H.OhsugiandT.Hibi,Toricidealsgeneratedbyquadraticbinomials,J.Algebra218(1999), 509–527. [PS]I.PeevaandB.Sturmfels,Syzygiesofcodimension2latticeideals,Math.Z.229(1998),163–194.[RR]L.ReidandL.Roberts,Monomialsubringsinarbitrarydimension,J.Algebra236(2001),703– 730. [RS]J-E.RoosandB.Sturmfels,AtoricringwithirrationalPoincar´e-Bettiseries,C.R.Acad.Sci. Paris326(1998),141–146. [SS]U.Sch¨aferandP.Schenzel,Dualizingcomplexesofaffinesemigrouprings,Trans.Amer.Math. Soc.322(1990),561–582. [Sch]P.Schenzel,OnVeroneseanembeddingsandprojectionsofVeroneseanvarieties,Arch.Math.30 (1978),391–397. [Se]A.Seb˝o,Hilbertbases,Carath´eodory’stheorem,andcombinatorialoptimization,in‘IntegerPro-grammingandCombinatorialOptimization’(R.Kannan,W.Pulleyblank,eds.),UniversityofWa-terlooPress,Waterloo1990,431–456. [St1]R.P.Stanley,Lineardiophantineequationsandlocalcohomology,Invent.Math.68(1982),175– 193. [St2]R.P.Stanley,Combinatoricsandcommutativealgebra(2nded.),Birkh¨auser1996.[SV]J.St¨uckradandW.Vogel,Buchsbaumringsandapplications,VEBDeutscherVerlagderWis-senschaften1986.[Stu1]B.Sturmfels,Gr¨obnerbasesandconvexpolytopes,AmericanMathematicalSociety1996. [Stu2]B.Sturmfels,Equationsdefiningtoricvarieties,Proc.SymposiaPureMath.62(1997),437–449.[Th]A.Thoma,Onthebinomialarithmeticrank,Arch.Math.74(2000),22–25. [Tr1]N.V.Trung,ClassificationofthedoubleprojectionsofVeronesevarieties,J.Math.KyotoUniv. 22(1983),567–581. [Tr2]N.V.Trung,Projectionsofone-dimensionalVeronesevarieties,Math.Nachr.118(1984),47–67.[TH]N.V.TrungandL.T.Hoa,AffinesemigroupsandCohen-Macaulayringsgeneratedbymonomials, Trans.Amer.Math.Soc.298(1986),145–167.¨OSNABRUCK¨,FBMATHEMATIK/INFORMATIK,49069OSNABRUCK¨,GERMANYUNIVERSITAT E-mailaddress:Winfried.Bruns@mathematik.uni-osnabrueck.de A.RAZMADZEMATHEMATICALINSTITUTE,ALEXIDZEST.1,380093TBILISI,GEORGIAE-mailaddress:gubel@rmi.acnet.ge INSTITUTEOFMATHEMATICS,VIENTOANHOC,P.O.BOX631,BOHO,HANOI,VIETNAME-mailaddress:nvtrung@thevinh.ncst.ac.vn ReceivedDecember21,2000andinfinalformJuly25,2001 因篇幅问题不能全部显示，请点此查看更多更全内容