Presentations of semigroup algebras of weighted trees

DOI 10.1007/s10801-009-0195-y

Presentations of semigroup algebras of weighted trees

Christopher Manon

Received: 18 September 2008 / Accepted: 19 June 2009 / Published online: 16 July 2009

© The Author(s) 2009. This article is published with open access at Springerlink.com

Abstract We study presentations for subalgebras of invariants of the coordinate al- gebras of binary symmetric models of phylogenetic trees studied by Buczynska and Wisniewski in (J. Eur. Math. Soc. 9:609–635,2007). These algebras arise as toric degenerations of projective coordinate rings of the moduli of weighted points on the projective line, and projective coordinate rings of the moduli of quasiparabolic semi- simple rank two bundles on the projective line.

Keywords Toric ideal·Polytope·Phylogenetics

1 Introduction

LetT be an abstract trivalent tree with leavesV (T), edgesE(T), and non-leaf ver- ticesI (T), by trivalent we mean that the valence ofv∈I (T)is always three. Letei

be the unique edge incident to the leafi∈V (T). LetY be the unique trivalent tree with three leaves. For eachv∈I (T)we pick an injective mapi_v:Y →T, sending the unique member ofI (Y )tov. We denote the members ofE(Y )byE,F, andG.

We say that two leavese, f∈V (T)are paired if they are connected to a common in- ternal vertex. Members ofV (T)which are not paired are called lone leaves. We will be concerned with properties of weightings of trivalent trees, defined as a functions

ω:E(T)→Z_≥0.

The author was supported by the NSF FRG grant DMS-0554254. The author will include these results in his doctoral thesis.

C. Manon (

Department of Mathematics, University of Maryland, College Park, MD 20742, USA e-mail:manonc@math.umd.edu

The mapsi_vdefine pull-back operations on weightings by the formulas i_v^∗(ω)(E)=ω(i_v(E)),

i_v^∗(ω)(F )=ω(i_v(F )), i_v^∗(ω)(G)=ω(iv(G)).

Definition 1.1 LetS_T be the graded semigroup whereS_T[k]is the set of weightings which satisfy the following conditions.

(1) For allv∈I (T)the numbersi^∗_v(ω)(E),i_v^∗(ω)(F )andi_v^∗(ω)(G)satisfy

|i^∗_v(ω)(E)−i_v^∗(ω)(F )| ≤i_v^∗(ω)(G)≤ |i_v^∗(ω)(E)+i_v^∗(ω)(F )|. These are referred to as the triangle inequalities.

(2) i_v^∗(ω)(E)+i_v^∗(ω)(F )+i_v^∗(ω)(G)is even.

(3)

i∈V (T)ω(e_i)=2k.

Note that because the triangle inequalities hold for the integers i_v^∗(ω)(E), i_v^∗(ω)(F ),andi_v^∗(ω)(G) if and only if a triangle exists with these side lengths, the condition is symmetric inE, F,andG.In [8] Speyer and Sturmfels show that the semigroup algebrasC[S_T]may be realized as projective coordinate rings of flat toric deformations ofGr2(Cⁿ)wheren= |V (T)|,for the Plücker embedding. This semi- group is also multigraded, with the grading given by the weightsω(ei)on the leaf edges of the tree. For a vector of non-negative integers r=(r1, . . . , rn)we letS_T[r] be the set of weightingsω∈S_T withω(ei)=ri.

Definition 1.2 Let r:V (T)→Z_≥0be a vector of non-negative integers. LetS_T(r) be the multigraded subsemigroup ofS_T formed by the piecesS_T[kr].

In general we will focus on weightings of trivalent trees such that the vector of edge weights r has an even total sum, because of the following proposition. The proof provides a nice introduction to the study of weights on trivalent trees.

Proposition 1.3 LetT be a trivalent tree. If r has an odd total sum, then there is no weighting ofT satisfying the parity condition with edges weighted by r.

Proof Note that this is true by definition forT =Y.Suppose that the result holds for every trivalent tree withn−1 leaves, and consider aT withn leaves. Pick paired leavese, f inV (T),and letT be the trivalent tree obtained by forgettingeand f, and the edges connected to them. Let gbe the internal edge ofT which shares a vertex withf andg.Note that we may considerga leaf ofT. Any weightingω which satisfies parity also defines a weighting ofTby restriction. By the induction hypothesis,ω|_T weights an even number ofV (T)with odd numbers. There are two cases, ifgis weighted odd then by parity only one ofeorf may be weighted odd. If gis weighted even, then either botheandf are weighted odd, or neither is weighted

odd. This shows that any weighting ofT must have leaf weights which sum to an

even number.

It follows from work in [8] that graded algebrasC[S_T(r)]are homogeneous coor- dinate rings for projective embeddings of flat toric deformations ofGr₂(Cⁿ)//_rT, the weight variety of the Grassmannian of 2-planes associated to r, or equivalentlyMr, the moduli space of r-weighted points onCP¹ (see [6] for this connection). In [6]

this degeneration is used to construct presentations of the projective coordinate ring ofMrfor the Plücker embedding, and it is shown that these algebras are generated in degree 1 and have relations generated by quadrics and cubics for certainT and r.

This is the starting point for the present paper. Forgetting the grading for a moment, geometricallyS_T is the semigroup of lattice points in a coneP_T inR^|E(T)|.The in- equalities definingP_T are given by the triangle inequalities, and the parity condition defines a certain sublattice ofZ^|E(T)|.LetT1andT2be trivalent trees withN1and N₂leaves, respectively. Identify the leaf 1 fromT2 with the leafN₁fromT1, rela- belling the leaves ofT2as follows, 2→N₁+1, . . . , N2→N₁+N₂−1. This creates a tree with a unique vertex of valence 2, replace this vertex and both of its incident edges with a single edge, the resulting treeT1∗T2is trivalent. We call this operation merging, see Figure1for an example. Leti∈V (T),and denote the projection onto thee_i-th component ofR^|E(T)|byπ_i.It is simple to check that

P_T1∗T2=P_T1×πN1=π1P_T2.

Where the right hand side is the fibered product of the polytopesP_T1 andP_T2over the mapsπ_N1 andπ₁.In particular this implies that allP_T are fibered products of copies ofP_Y.This is reminiscent of the theory of moduli of structures on orientable surfaces, where structures on a surface of high genus can be glued together from structures on three-punctured spheres over a pair-of-pants decomposition. The reason for this resemblance is not entirely accidental, see [5] for a moduli-of-surfaces interpretation of spaces associated to the semigroupS_T. Buczynska and Wisniewski define merging in [3], where they show that a similar fibered product formula holds for a class of semigroups of weightings which we will now introduce.

Definition 1.4 For a trivalent tree T let(T)be the polytope in R^|E(T)| formed by the convex hull of weightingsω such that ω(e)∈ {0,1}for all e∈E(T),and i_v^∗(ω)(E)+i_v^∗(ω)(F )+i_v^∗(ω)(G)∈2Zfor allv∈I (T).

It is shown in [3] (proposition 1.13) that(T)is a fibered product of|I (T)|copies of(Y ).The lattice point semigroup ofL(T)=(T)+. . .+(T)is isomorphic to the following semigroup.

Definition 1.5 LetLbe a positive integer. LetS_T^L be the graded semigroup where S_T^L[k]is the set of weightingsωofT which satisfy

(1) For allv∈I (T)the numbersi_v^∗(ω)(E),i_v^∗(ω)(F )andi_v^∗(ω)(G)satisfy the tri- angle inequalities.

(2) i_v^∗(ω)(E)+i_v^∗(ω)(F )+i_v^∗(ω)(G)is even.

(3) i_v^∗(ω)(E)+i_v^∗(ω)(F )+i_v^∗(ω)(G)≤2kL.

This last condition is referred to as the level condition.

Note thatS_T¹ has a fibered product decomposition into copiesS_Y¹ in a way com- pletely analogous toS_T.To see that the lattice points of(T)correspond with the first graded piece ofS_T¹,one need only use the fibered product decomposition of both objects. We observe that the lattice points of(Y )are given by the degree 1 members ofS_Y¹.In [3] Buczynska and Wisniewski study the algebrasC[S_T¹],proving that they are all deformation equivalent. However, they do not construct an analogue of the pro- jective coordinate ring of the Grassmannian of two planes in this context, namely an algebra for eachnwhich flatly degenerates to the semigroup algebraC[S¹_T]for each treeT withnleaves while preserving the multigrading defined by the edge weights and the level.

In [10], Sturmfels and Xu show how to flatly deform the multigraded Cox-Nagata ring R^G to each C[S_T¹]. The structure of this ring was studied by Castravet and Tevelev in [4] and by Mukai in [7]. LetRbe a polynomial ring overCin 2nvariables,

Fig. 1 Merging two trees

and letGbe a subspace ofCⁿof codimensiond. There is an action ofGonRwhich generalizes the construction used by Nagata in his solution to Hilbert’s 14th problem.

Whend≥3 the invariant ringR^Gis isomorphic to the Cox ring ofX_G,the blow-up ofP^d−1atnpoints determined byG,see [10] for a discussion of this connection. Let Kbe the pullback of the canonical class onP^d−1,and let theEi be the associated distinguished classes of the blow-up. Then

Cox(X_G)=

(u,r)

H⁰(X_G, rK+(u₁−r)E₁+. . .+(u_n−r)E_n).

Sturmfels and Xu prove the following theorem.

Theorem 1.6 IfGis generic and of codimension 2, R^Gflatly degenerates toC[S_T¹] for each treeT withnleaves.

The ringR^Gcomes equipped with a multigrading given by(r,u) ∈Zⁿ⁺¹.We re- label the(r,u) component ofR^Gwith the multigrade(r, L)withL=(_n

i=1u_i)−r, r1=u1, . . . , rn−1=un−1,andrn=(n

i=1ui)−r−un.This multigrade agrees with the one onC[S_T¹]induced by the levelLand the leaf weights under the flat defor- mation, see [10] for details. Since the multigrading is given by the Picard Group of the blow-up, we refer to it as the Picard grading, and we refer to the associ- ated torus acting on the ring as the Picard torus. The analogue of the projective coordinate ringsC[Mr]in this context are the multigrade(r, L)Veronese subrings R^G(r, L),obtained by taking the direct sum of all components ofR^Gwith multigrade a multiple of(r, L). These are the projective coordinate rings of the embeddings of X(n−3,n), the blow-up of Pⁿ⁻³ at n points, corresponding to various members of P ic(X_(n−3,n)).LetS_T^L(r)be the subsemigroup ofS_T¹ of pieces with multigrade a multiple of(r, L).It follows thatC[S_T^L(r)]is a toric deformation ofR^G(r, L). Sturm- fels and Xu point out that the ringC[Gr₂(Cⁿ)]is isomorphic as a multigraded algebra toCox(X_(n−3,n−1)).This gives a common interpretation of both types of semigroups of weighted trees considered here as toric deformations of projective coordinate rings associated to embeddings of blow-ups of projective spaces. It was also noted in [10]

that by a theorem of Bauer [2],X_(n−3,n) is related to N(0,n),the moduli space of quasiparabolic semistable rank 2 bundles onP¹,by a sequence of flops. This implies that these spaces share the same Cox ring, and that the algebrasC[S_T^L(r)]are toric deformations of the projective coordinate rings associated to line bundles onN(0,n).

We study the degrees of presentation and relation generation for presentations of a large class of the ringsC[S_T^L(r)],finding upper bounds for both of these numbers.

The techniques used are such that the same results immediately hold forC[S_T(r)] as well, in particular we give a different proof of a fundamental result of [6] on a presentation of these rings. It follows that the same bounds on generator and relation degrees also apply toR^G(r, L)whenGis of codimension 2 and 1,andC[Mr]as well. In particular our results apply to the projective coordinate rings of a large class of embeddings of blow-ups ofPⁿ⁻³atnandn−1 points. From now on we assume Gis of codimension 2 unless otherwise indicated.

1.1 Statement of Results

We now state the main results of the paper. We will be focusing on the following class ofS_T^L(r).

Definition 1.7 We call the triple(T,r, L)admissible ifL is even, r(i)is even for every lone leafi, and r(j )+r(k)is even for all paired leavesj,k.

Remark 1.8 The assumption that r has an even total sum implies that an even num- ber, 2Mof the entries of r are odd. Choosing T with 2M paired leaves then guar- antees that (T,r, L)is admissible, provided that L is even. This is important for constructing presentations ofR^G(r, L), since this ring always has a flat deformation toC[S_T^L(r)]for some admissible(T,r, L)whenLis even. Also note that the second Veronese subring ofC[S_T^L(r)]is the semigroup algebra associated to(T,2r,2L), which is always admissible.

Theorem 1.9 For (T,r, L) admissible with L >2, C[S_T^L(r)] is generated in de- gree 1.

Theorem 1.10 For(T,r, L)admissible withL >2,C[S_T^L(r)]has relations gener- ated in degree at most 3.

As a corollary we get the same results forS_T(r)when(T,r)satisfy admissibility conditions. These theorems are proved in Sections 2, 3, and 4. In Section 5 we look at some special cases, and investigate what can go wrong when(T,r, L)is not an admissible triple.

1.2 Outline of techniques

To prove Theorems1.9and1.10we use two main ideas. First, we employ the follow- ing trivial but useful observation.

Proposition 1.11 Let(T,r, L)be admissible, then for any weighting ω∈S_T^L(r), ω(e)is an even number wheneis not an edge connected to a paired leaf.

This allows us to drop the parity condition thati_v^∗(ω)(E)+i_v^∗(ω)(F )+i_v^∗(ω)(G) is even by forgetting the paired leaves and halving all remaining weights.

Fig. 2 Clipping the paired leaves ofT

Definition 1.12 Letc(T)be the subtree ofT given by forgetting all edges incident to paired leaves. We callc(T)a clipping ofT.

Definition 1.13 LetU_c(^L_T)(r)be the graded semigroup of weightings onc(T)such that the members ofU_c(^L_T)(r)[k]satisfy the triangle inequalities, the new level condi- tioni_v^∗(ω)(E)+i_v^∗(ω)(F )+i_v^∗(ω)(G)≤kL, and the following conditions.

1. ω(e_i)=k^r(i)₂ foria lone leaf ofT.

2. ^k|r(i)−₂^{r(j )|}≤ω(e)≤^k|r(i)+₂^{r(j )|}forethe unique edge ofT connected to the vertex which is connected to the paired leavesiandj.

3. ω(e)+^kr(i)+₂^{kr(j )}≤kL.

Also, letU_c(^L_T) be the graded semigroup of weightings which satisfy the triangle inequalities and the new level condition forL. The following is a consequence of these definitions.

Proposition 1.14 For(T,r, L)admissible, U_c(^L_T)(r)∼=S_T^L(r) as graded semigroups.

The next main idea is to undertake the analysis ofU_c(^L_T)(r)by first considering the weightingsi_v^∗(ω)∈U_Y^L. After constructing an object inU_Y^L, like a factorization or a relation, we “glue” these objects back together along edges shared by the var- iousi_v(Y )with the fibered product. We obtain information about U_Y^L by studying the geometry of the following polytope. LetP3(L)be the convex hull of(0,0,0), (^L₂,^L₂,0),(^L₂,0,^L₂), and(0,^L₂,^L₂).

The graded semigroup of lattice points forP₃(L)is clearlyU_Y^L. By a lattice equiv- alence of polytopesP,Q⊂Rⁿwith respect to a lattice⊂Rⁿwe mean a compo- sition of translations by members ofand members ofGL()⊂GLn(R)which takesP toQ. If P andQ are lattice equivalent it is easy to show that they have isomorphic graded semigroups of lattice points. WhenLis an even integer (admissi- bility condition) the intersection of this polytope with any translate of the unit cube inR³, is, up to lattice equivalence, one of the polytopes shown in Figure4.

In Section 2 we show that these polytopes are normal, and the relations of their associated semigroups are generated in degree at most 3. In Sections 3 and 4 we will lift these properties toU_c(^L_T)(r), and thereforeS_T^L(r)for(T,r, L)admissible. Facts about the six polytopes above also allow us to carry out a more detailed study of the semigroupsS_T^L(r)in Section 5, for example they allow us to show the redundancy of the cubic relations for certain(T,r, L).

We thank John Millson for introducing us to this problem, Ben Howard for many useful and encouraging conversations and for first introducing us to the commuta- tive algebra of semigroup rings, Larry O’Neil for several useful conversations on the cone of triples which satisfy the triangle inequalities, the referees for many useful suggestions, and Bernd Sturmfels for introducing us to Graver bases and shortening the proof of Theorems2.2and2.4.

Fig. 3 P3(2L)

Fig. 4 Cube Polytopes

2 The Cube Semigroups

In this section we prove that the intersection of any translate of the unit cube of R³withP3(L) produces a normal polytope whose semigroup of lattice points has relations generated in degree at most 3 whenLis even. LetP₃be the cone of triples of nonnegative integers which satisfy the triangle inequalities, and letC(m1, m2, m3) denote the unit cuberoot ed at(m1, m2, m3)∈R³,

C(m1, m2, m3)=conv{(m1+1, m2+2, m3+3)|_i∈ {0,1}}.

We wish to classify the polytopes which have the presentationC(m₁, m₂, m₃)∩P₃. SinceP₃ is symmetric we may assume that(m₁, m₂, m₃)is ordered by magnitude withm3the largest. In this analysis we keep track of the triangle inequalities with the quantitiesn_i=m_j+m_k−m_i. For example, a point(m₁, m₂, m₃)is a member ofP₃

ifn_i≥0 for eachi. Immediately we have the following inequalities.

n1≥n2≥n3, n2≥0.

Ifn3<−2 then no member ofC(m1, m2, m3)can belong to P3. Ifn3≥ −2 then there are six distinct possibilities, we list each case along with the standard lattice members ofC(m1, m2, m3)∩P3−(m1, m2, m3).

Condition C(m₁, m₂, m₃)∩P₃−(m₁, m₂, m₃)

n₃= −2 (1,1,0)

n3= −1 (1,1,0), (0,1,0), (1,0,0), (1,1,1)

n₁=n₂=n₃=0 (1,1,0), (0,1,1), (1,0,1), (1,1,1), (0,0,0) n1>0, n2=n3=0 (1,1,0), (0,1,1), (1,0,1), (1,1,1), (0,0,0), (0,0,1) n₁, n₂>0, n₃=0 (1,1,0), (0,1,1), (1,0,1), (1,1,1), (0,0,0), (0,0,1), (0,1,0)

ni>0 all lattice points of the cube

The figure below illustrates these arrangements.

Now we will see what happens when we intersectP₃with the half space defined by the inequalityv1+v2+v3≤2L to getP3(2L). The reader may want to refer to Figure6for this part. The convex setC(m1, m2, m3)∩P3(2L)can be one of the above polytopes (up to lattice equivalence), or one of them intersected with the half planev₁+v₂+v₃≤2L. Note that a vertexvinC(m₁, m₂, m₃)∩P₃(2L)lying on a facet ofP₃necessarily satisfiesv₁+v₂+v₃=0 mod 2. In Figure6these points are colored black.

The hyperplane defined by the equationv1+v2+v3=2Lmust intersect these polytopes at collections of three black points. If we assume that the lower left corner is (0,0,0), these points have coordinates {(1,1,0), (1,0,1), (0,1,1)}, or

Fig. 5 Primitive cube semigroups

Fig. 6 Cube semigroups with the latticev1+v2+v3=0 mod 2

Fig. 7 New Possibilities for C(m1, m2, m3)∩P3(2L)

{(1,0,0), (0,1,0), (0,0,1)}. Figure6represents the new possibilities we must con- sider. The polytope pictured lower center in Figure7is the only case which is not lattice equivalent to one pictured in Figure5. It is rooted at(0,0,0)and occurs only whenL=1 (level condition is 2). The point(1,1,1)in its second Minkowski sum cannot be expressed as the sum of two lattice points of degree one, so this is not a normal polytope. This is the reason we stipulate thatL >2 in Theorem1.9.

Now we analyze eachC(m1, m2, m3)∩P3(2L). Since lattice equivalent polytopes have isomorphic semigroups of lattice points, it suffices to investigate the polytopes listed in Figure5.

Caution 2.1 In [3], Buczynska and Wisniewski study a normal polytope with the same vertices as the non-normal polytope mentioned above. This is possible because they are using the latticev₁+v₂+v₃=0 mod 2, not the standard lattice.

2.1 Graver Bases of the unit Cube

We make use of the computational algebra package 4ti2, [1] to compute the Graver basis of the toric ideal of the unit 3-cube. Material on the Gröbner theory of toric

ideals coming from polytopes can be found in [9].

(1,0,0)+(1,1,1)=(1,0,1)+(1,1,0) (0,1,0)+(1,1,1)=(0,1,1)+(1,1,0) (0,0,0)+(1,1,1)=(0,0,1)+(1,1,0) (0,0,1)+(1,1,1)=(0,0,1)+(1,0,1) (0,0,0)+(1,1,1)=(0,1,0)+(1,0,1) (0,0,1)+(1,1,0)=(0,1,0)+(1,0,1) (0,0,0)+(1,1,1)=(0,1,1)+(1,0,0) (0,0,1)+(1,1,0)=(0,1,1)+(1,0,0) (0,1,0)+(1,0,1)=(0,1,1)+(1,0,0) (0,0,0)+(1,1,0)=(0,1,0)+(1,0,0) (0,0,0)+(1,0,1)=(0,0,1)+(1,0,0) (0,0,0)+(0,1,1)=(0,0,1)+(0,1,0)

(0,1,0)+(1,0,0)+(1,1,1)=(0,0,1)+(1,1,0)+(1,1,0) (0,0,0)+(1,1,1)+(1,1,1)=(0,1,1)+(1,0,1)+(1,1,0) (0,0,1)+(1,0,0)+(1,1,1)=(0,1,0)+(1,0,1)+(1,0,1) (0,0,1)+(0,0,1)+(1,1,0)=(0,0,0)+(0,1,1)+(1,0,1) (0,0,0)+(0,1,1)+(1,1,0)=(0,1,0)+(0,1,0)+(1,0,1) (0,0,0)+(1,0,1)+(1,0,1)=(0,1,1)+(1,0,0)+(1,0,0) (0,0,1)+(0,1,0)+(1,1,1)=(0,1,1)+(0,1,1)+(1,0,0) (0,0,0)+(0,0,0)+(1,1,1)=(1,0,0)+(0,1,0)+(0,0,1)

Operating on this set of monomials, one can show that the toric ideal of every sub-polytope of the unit 3-cube which is not a simplex has a square-free Gröbner basis. This, combined with the fact that the sub-polytopes withn₃= −2 and−1 are unimodular simplices shows the following theorem.

Theorem 2.2 SupposeL=1, then for all(m1, m2, m3), ifC(m1, m2, m3)∩P3(2L) is non-empty then it is a normal lattice polytope.

Remark 2.3 This theorem implies, among other things, that ifω∈U_Y^2L[k], then

ω=

k

i=1

W_i forW_i∈P3(2L)with the property that each

W_i=X+(₁, ₂, ₃)

withj∈ {0,1}for allifor a fixedX∈R³. It is easy to show that

X=(ω(E)

k ,ω(F )

k ,ω(G) k ).

Therefore eachWi is(^ω(E)_k ,^{ω(F )}_k ,^ω(G)_k )with either floor or ceiling applied to each entry.

Now we move on to relations. LetS(m₁, m₂, m₃)be the semigroup of lattice points forC(m₁, m₂, m₃)∩P₃(2L)−(m₁, m₂, m₃). Once again it suffices to treat the cases represented in Figure5.

Theorem 2.4 All relations for the semigroup S(m₁, m₂, m₃) are reducible to quadrics and cubics.

Proof By Proposition 4.13 of [9], a Graver basis for any subpolytopeP of the unit 3- cube is obtained by taking the members of the Graver basis of the unit 3-cube which have entries in the lattice points ofP. Since these are all quadrics and cubics, we are

done.

Up to equivalence and after accounting for redundancy, all relations considered here are of the form

(1,0,0)+(0,1,0)=(1,1,0)+(0,0,0) (1,0,1)+(0,1,0)=(1,1,1)+(0,0,0) (1,0,1)+(1,1,0)=(1,1,1)+(1,0,0)

(1,1,1)+(1,1,1)+(0,0,0)=(1,1,0)+(1,0,1)+(0,1,1),

with the last one the only degree 3 relation, we refer to it as the “degenerated Segre Cubic” (see [6]).

3 Proof of Theorem1.9

In this section we use Theorem2.2to prove thatU_c(^L_T)(r)is generated in degree 1, which then proves Theorem1.9. For eachv∈I (T)we have the morphism of graded semigroups

i_v^∗:U_c(^L_T)(r)→U_Y^L.

Given a weight ω∈U_c(^L_T)(r)we factor i_v^∗(ω) for each v∈I (c(T)) using Theo- rem2.2. Then special properties of the weightings obtained by this procedure will allow us to glue the factors of thei_v^∗(ω)back together along merged edges to obtain a factorization ofω. First we must make sure that our factorization procedure does not disrupt the conditions at the edges ofc(T).

Lemma 3.1 Let ω∈ U_c(^L_T)(r)[k], and let v ∈ I (T) be connected to a leaf of c(T) at E. If i^∗_v(ω) =η₁+. . . +η_k is any factorization of i_v^∗(ω) with η_i ∈ C(^iv∗(ω)(E)_k ,^{iv∗(ω)(F )}_k ,^iv∗(ω)(G)_k ), thenηi(E)satisfies the appropriate edge con- dition for elements inU_c(^L_T)(r)[1].

Proof IfE is attached to a lone leaf of T theni_v^∗(ω)(E)=kr(e) for i_v(E)=e, e∈V (T). By Remark2.3

η_i(E)= r(e) =r(e)

or

η_i(E)= r(e) +1=r(e)+1.

Since_k

i=1η_i(E)=kr(e) we must haveη_i(E)=r(e) for alli. IfE is a stalk of paired leavesiandj inT then we must have

k|r(i)−r(j )|

2 ≤ω_Y(E)≤k|r(i)+r(j )|

2 .

Note that both bounds are divisible byk. Since floor preserves lower bounds we have

|r(i)−r(j )|

2 ≤ i_v^∗(ω)(E)

k ,

and since ceiling preserves upper bounds we have i_v^∗(ω)(E)

k ≤|r(i)+r(j )|

2 .

Therefore eachηi satisfies

|r(i)−r(j )|

2 ≤η_i(E)≤|r(i)+r(j )|

2 .

Now that we can safely use Theorem2.2with eachi_v^∗:U_c(^L_T)(r)→U_Y^L, we will establish tools to extend factorization properties ofU_Y^LtoU_c(^L_T)(r)by exploiting the fibered product structure of the ambient semigroupU_c(^L_T). The following concept allows us to control conditions on the edges of two trees we wish to merge.

Definition 3.2 We say that a list of nonnegative integers{X1, . . . , X_n}is balanced if

|X_i−X_j| =1 or 0 for alli,j.

Lemma 3.3 If two lists{X1, . . . , Xn}and{Z1, . . . , Zm}are balanced, have the same total sum, andn=m, then they are the same list up to permutation.

Proof LetC₁be the smallest member of{X₁, . . . , X_n}, andC₂be the smallest mem- ber of{Z1, . . . , Z_n}.LetSbe the total sum of either list. Both lists are balanced, so we must haveS=nC1+k1=nC2+k2,wherek1andk2are non-negative integers less than or equal ton.Suppose without loss of generality thatk2−k1is non-negative, then it must be divisible byn. By assumption, this can only happen ifk2=k1,in which caseC1=C2,and the lists have the same members.

Proposition 3.4 The semigroupU_c(^L_T)(r)is generated in degree 1.

Proof Recall that by Remark2.3, for any edgeE∈Y the edge weights of a factor- izationi^∗_v(ω)=η1+. . . η_ksatisfyη_i(E)= ^iv∗(ω)(E)_k or^iv∗(ω)(E)_k . Take any twov1, v₂which share a common edgeEinc(T). Letω∈U_c(^L_T)(r)[k]and let{η₁¹, . . . , η¹_k} and{η²₁, . . . , η²_k}be factorizations of i_v^∗

1(ω) andi_v^∗

2(ω)respectively. Then the lists

{η¹₁(E), . . . , η¹_k(E)}and{η²₁(E), . . . , η²_k(E)}are balanced and have the same sum, so by Lemma3.3they are the same list up to some permutation. We may glue factors η_i¹andη²_j whenη¹_i(E)=η²_j(E), the above observation guarantees that anyη¹_i has an available partnerη²_j. The proposition now follows by induction on the number of

v∈I (c(T)). This implies Theorem1.9.

4 Proof of Theorem1.10

In this section we show how to get all relations inU_c(^L_T)(r)from those lifted fromU_Y^L. The procedure follows the same pattern as the proof of Theorem1.9. We consider the image of a relationω1+. . .+ωn=η1+. . .+ηnunder a mapi_v^∗:U_c(^L_T)(r)→U_Y^L, using Theorem2.4we convert this to a trivial relation using relations of degree at most 3. We then give a recipe for lifting each of these relations back toU_c(^L_T)(r). The result is a way to convertω1+. . .+ωn=η1+. . .+ηnto a relation which is trivial over the trinodevusing quadrics and cubics. In this way we take a general relation to a trivial relation onev∈I (c(T))at a time.

Definition 4.1 A set of degree 1 elements{ω₁, . . . , ω_k} inU_c(^L_T)(r)is said to be balanced when the set{ω₁(E), . . . , ω_k(E)}is balanced for allE∈c(T). A relation ω₁+. . .+ω_k=η₁+. . .+η_k inU_c(^L_T)(r)is said to be balanced when{ω₁, . . . , ω_k} and{η₁, . . . , η_k}are balanced.

The following lemmas show that we need only consider balanced relations.

Lemma 4.2 Any list of non-negative integersS= {X1, . . . , Xn}can be converted to a balanced listT = {Y1, . . . , Yn}with_n

i=1Yi=_n

i=1Xi by replacing a pairXi

andXj with^Xi+X₂ ^jand^Xi+X₂ ^ja finite number of times.

Proof Letd(S)be the difference between the maximum and minimum elements ofS.

It is clear that with a finite number of exchanges {X_i, X_j} → {X_i+X_j

2 ,X_i+X_j

2 }

We get a new setSwithd(S) > d(S), unlessd(S)=1 or 0. Since this happens if and only ofSis balanced, the lemma follows by induction.

Lemma 4.3 Let

ω₁+. . .+ω_k=η₁+. . .+η_k

be a relation inU_c(^L_T)(r). Then it can be converted to a balanced relation ω₁ +. . .+ω_k=η₁+. . .+η_k

using only degree 2 relations.

Fig. 8 Component subtrees about a vertex

Proof First we note that we may use the proof of Theorem1.9to factor the weighting ω1+ω2intoω₁+ω₂so that{ω₁, ω₂}is balanced. Using this and Lemma4.2we can find

ω₁ +. . .+ω_k=ω1+. . .+ωk

such that the set{ω₁(E), . . . , ω_k(E)}is balanced for some specificE, employing only degree 2 relations. Observe that if{ω1(F ), . . . , ωk(F )}is balanced for someF, the same is true for{ω₁(F ), . . . , ω_k(F )}, after a series of degree 2 applications of1.9.

This shows that we may inductively convert{ω1, . . . , ωk}to{ω₁, . . . , ω_k}with the property that{ω₁(E), . . . , ω_k(E)}is a balanced list for all edgesE, using only degree 2 relations. Applying the same procedure to theη_i then proves the lemma.

The next lemma shows how we lift a balanced relation inU_Y^Lto one inU_c(^L_T)(r).

Lemma 4.4 Let{ω₁. . . ω_k}be a balanced set of elements inU_c(^L_T)(r). Leti_v^∗(ω₁)+ . . .+i_v^∗(ω_k)=η1+. . .+η_k be a balanced degreek relation in the appropriate S(m₁, m₂, m₃)⊂U_Y^L. Then theη_i may be lifted to weightings ofc(T)giving a rela- tion of degreekinU_c(^L_T)(r)which agrees with the relation above wheni_v^∗is applied, and is a permutation ofi_v^∗(ω₁) . . . i_v^∗(ω_k)forv=v.

Proof Letc(T)(E)be the unique connected subtrivalent tree ofc(T)which includes vand has the property that any pathγ⊂c(T)(E)with endpoints at a vertexv=vin c(T)(E)andvincludes the edgeE(see Figure8), definec(T)(F )andc(T)(G)in the same way. To makeη₁. . . η_k overc(T), note that the list{i_c(^∗_T)(E)(ω_i)(E)}is the same as the list{η_i(E)}up to permutation, because they are both balanced lists with the same sum and the same number of elements, so we may glue these weightings

together to make a tuple overc(T).

Suppose we are given a balanced relation

ω₁+. . .+ω_k=η₁+. . .+η_k. We can pick anyv∈I (c(T)),and consider the relation

i_v^∗(ω1)+. . .+i_v^∗(ω_k)=i_v^∗(η1)+. . .+i_v^∗(η_k).

We convert this to a trivial relation using a series of relations in the appro- priate S(m₁, m₂, m₃), then lift the result back to U_c(^L_T)(r). For any v =v in I (c(T)), this process only permutes the members of {i_v^∗(ω₁), . . . , i_v^∗(ω_k)} and {i_v^∗(η₁), . . . , i_v^∗(η_k)},which does not change whether or not this was a balanced rela- tion. In this way, we may convert any balanced relation inU_c(^L_T)(r)to a trivial relation onev∈I (c(T))at a time.

Proposition 4.5 LetNbe the maximum degree of relations needed to generate all re- lations in the semigroupsS(m1, m2, m3). Then the semigroupU_c(^L_T)(r)has relations generated in degree bounded byN.

This proposition, coupled with Theorem2.4proves Theorem1.10. We recap the con- tent of the last two sections with the following theorem.

Theorem 4.6 Let(T,r, L)be admissible. Then the ringC[U_c(^L_T)(r)]has a presen- tation

0 −−−−→ I −−−−→ C[X] −−−−→ C[U_c(^L_T)(r)] −−−−→ 0

whereXis the set of degree 1 elements ofU_c(^L_T)(r), andI is the ideal generated by two types of binomials,

[ω1] ◦. . .◦ [ω_n] − [η1] ◦. . .◦ [η_n].

(1) Binomials where n ≤ 3, i_v^∗(ω1)+. . . +i_v^∗(ωn)=i_v^∗(η1)+. . . +i_v^∗(ηn) is a balanced relation in U_Y^L for some specific v, and {i_v^∗(ω1), . . . , i_v^∗(ωn)} = {i_v^∗(η1), . . . , i_v^∗(η_n)}forv=v.

(2) Binomials where n =2 and i_v^∗(ω₁)+i_v^∗(ω₂)=i_v^∗(η₁)+i_v^∗(η₂) such that {i_v^∗(ω1), i_v^∗(ω2)}is balanced for allv∈I (c(T)).

This induces a presentation forC[S_T^L(r)]by isomorphism.

Corollary 4.7 The same holds forC[S_T(r)].

Proof For each pair(T,r)it is easy to show that there is a numberN (T,r), such that any weightingωwhich satisfies the triangle inequalities onT and hasω(e_i)= ri must haveω(e)≤N (T,r)for e∈E(T).Because of thisS_T^L(r)=S_T(r)for L

sufficiently large.

5 Special Cases and Observations

In this section we collect results on some special cases ofC[S_T^L(r)]. In particular we study some instances when cubic relations are unnecessary, we give some examples where the semigroup is not generated in degree 1, we analyze the case whenL is allowed to be odd, and we give instances where cubic relations are necessary.

5.1 The Caterpillar Tree

One consequence of the proof of Theorem2.4is that a semigroupU_c(^L_T)(r)which omits or only partially admits the semigroupS(0,0,0)or S(L−1, L−1,0)as an image of one of the morphismsi_v^∗manages to avoid degree 3 relations entirely. The next proposition illustrates one such example, the semigroups of weightings on the caterpillar tree, pictured below.

Proposition 5.1 LetT0be the caterpillar tree, and let r(i)be even for alli∈V (T0).

ThenS^2L_T

0(r)is generated in degree 1, with relations generated by quadrics.

Proof We catalogue the weightsi_v^∗(ω) which can appear in degree 1. For the sake of simplicity we divide all weights by 2. Suppose i_v(G) is an external edge, then i_v^∗(ω)(E)andi_v^∗(ω)(F )satisfy the following inequalities

i_v^∗(ω)(E)≤i_v^∗(ω)(F )+r(i)

i_v^∗(ω)(F )≤i_v^∗(ω)(E)+r(i) i_v^∗(ω)(E)+i^∗_v(ω)(F )+r(i)≤2L

where i_v^∗(ω)(G) =r(i). These conditions define a polytope in R² with vertices (L, L−r(i)),(L−r(i), L),(r(i),0)and(0,r(i)). Pictured below is the caseL=9, 2r(i)=6.

When two edges are external, the polytope is an integral line segment. Note that the intersection of any lattice cube inR² with the above polytope is a simplex or a unit square. Both of these polytopes have at most quadrics for relations in their semigroup of lattice points. Hence the argument used to prove Theorem1.10shows thatU_c(^2L_T

0)(r)needs only quadric relations.

Fig. 9 The Caterpillar tree

Fig. 10 The caseL=9, 2r(i)=6

Corollary 5.2 If L >1, and r is a vector of nonnegative integers, the ring R^G(2L,2r)has a presentation with defining ideal generated by quadrics. In partic- ular, the second Veronese subring of anyR^G(r, L)has such a presentation ifL >1.

Note that the same applies toC[M2r]. 5.2 Counterexamples to Degree 1 generation

Now we’ll see examples of(r,T, L)such thatS_T^L(r)is not generated in degree 1.

We will begin by defining a certain class of paths in the treeT. LetT have an even number of leaves. We claim that there is a set of edgesA(T)⊂E(T)the members of which are assigned odd numbers by any weightingωwhich assigns an odd number to each leaf ofT. It suffices to establish the stronger result that the parity of members of V (T)determines the parity of every edge inT. To see this, first note that the parity of two edges of a trinode determines the parity of the third edge, an induction argument on the number of edges inT does the rest.

Proposition 5.3 LetT be as above. The setA(T)is a union of edges from disjoint paths inT.

Proof Exactly two out of three edges in each trinode can be assigned an odd number, by the parity condition. This establishes the proposition.

From now on we letO(T)denote the set of paths established by the previous proposition.

Proposition 5.4 Let(r,T, L)be such that the edges connected to the endpoints of each member ofO(T)are given the same parity by r. Assume further that there is a γ∈O(T)such that end points ofγ are connected to edgeseandf with r(e)and r(f )odd. If there is a degree 2 weighting which assigns 0 to any edge in γ, then S_T^2L(r)is not generated in degree 1.