When we say “polyhedral cone” we have so far always meant closed polyhedral
cones, and unless stated otherwise we still mean that polyhedral cones are
closed. By anopen polyhedral cone inR^{n} we mean a finite intersection of open
halfspaces passing through the origin. IfC⊆R^{n}is a set with the property that
there exists a linear subspaceL⊆R^{n} withC ⊆LandC considered as a subset
ofL(in the topology induced onL) thenCis called arelatively open polyhedral
cone. Alternatively, if we do not wish to use topological notions, we can define
a relatively open polyhedral cone to be the intersection of an open polyhedral
cone and a linear subspace ofR^{n}.

Example 4.4.1 The sets

• R^{3}_{>0} ⊆R^{3}

• R^{2}_{>0}× {(0)} ⊆R^{3}

• {(0,0,0)} ⊆ R^{3}
are relatively open cones.

In this subsection we will prove that for fixed ideal I the equivalence relation defined in Equation 1, page 40 gives rise to equivalence classes which are rel- atively open cones - almost. Example 4.0.21 showed that equivalence classes may be non-convex, so we need to be careful when stating our result.

In [13] proofs of some of the following statements are given, but therev∈R^{n}
is assumed to have non-negative entries. In the following we need to be more
careful. The vectorv may have negative entries.

Lemma 4.4.2 [7, Lemma 2.12] Let I ⊆k[x_{1}, . . . , xn]be an ideal, andv∈R^{n}.
If f ∈ in_{v}(I) then we may write f as a sum P

iin_{v}(c_{i}) with c_{i} ∈ I and each
inv(ci) having different v-degree.

Proof. By definition of the initial ideal we may write f as P

iaiinv(pi) where pi∈I andai are polynomials. In fact we may assume that ai are single terms.

We rewrite f = P

iaiinv(pi) = P

iinv(aipi). So in fact, we may assume that ai = 1. All terms of each summand inv(pi) have the same v-degree. Suppose inv(pi) and inv(pj) have the samev-degree. Then either inv(pi) + inv(pj) = 0 or inv(pi) + inv(pj) = in(pi+pj). In the sum P

iinv(pi) we may therefore group polynomials together, possibly removing summands, until the sum involves only summands with different v-degrees. 2

Lemma 4.4.3 [7, Lemma 2.13] Let I ⊆k[x_{1}, . . . , x_{n}]be an ideal and≺a term
ordering. If a vector v is in C≺(I) then in≺(inv(I)) = in≺(I).

Proof. To prove “⊇” we look at a generator of in≺(f) where f ∈ G≺(I) and
observe that by Corollary 4.2.4 in≺(f) = in≺(inv(f)). This proves in≺(f) ∈
in_{≺}(inv(I)).

To prove “⊆” we let f ∈ inv(I). By the Lemma above we may write f =P

iinv(ci) withci∈I and ci having differentv-degree. There must exist j
such that in_{≺}(f) = in_{≺}(inv(cj)). We want to prove that this is in in_{≺}(I). Using
the division algorithm withG≺(I) and ≺we write

c_{j} =m_{1}g_{1}+· · ·+m_{r}g_{r}

withmi being terms andgi ∈ G≺(I). We now argue that thev-degree ofcj is≥
thev-degree of anym_{i}g_{i}. The reason for this is that thev-degree ofpin the algo-
rithm is non-strictly decreasing. Namely we cancel a term ofpwith the largest
term of (a multiple of) anfi ∈ G≺(I) in the algorithm, possibly introducing new
terms and canceling other. The terms that are introduced cannot have larger
v-degree than the term P we wish to cancel because in≺(inv(fi)) = in≺(fi) by
Corollary 4.2.4. The terms migi are produced by the algorithm when the ai

are modified. At this point the v-degree is bounded by the degree of p. We conclude that for all terms ofmigi have smaller degree thancj. Hence

inv(cj) =X

i∈J

inv(migi)

for some index set J. In the “P := in_{≺}(p)” variant of the division algorithm
in_{≺}(p) gets≺smaller in each iteration. Therefore in_{≺}(m_{1}g_{1}), . . . ,in_{≺}(m_{r}g_{r}) are
all different. By Corollary 4.2.4 they equal in≺(inv(m1g1)), . . . ,in≺(inv(mrgr)).

The initial term in_{≺}(inv(cj)) = in_{≺}(P

i∈Jinv(migi)) must equal in_{≺}(inv(migi)) =
in_{≺}(m_{i}g_{i}) for somei. This proves in_{≺}(in_{v}(c_{j})) is in in_{≺}(I). 2

Corollary 4.4.4 [7, Corollary 2.14] Let I ⊆ k[x1, . . . , xn] be an ideal, ≺ a
term ordering andv∈C≺(I). Then G^{≺}(inv(I)) ={inv(f) :f ∈ G^{≺}(I)}.

Proof. To show that we have a Gr¨obner basis we must prove that in_{≺}(inv(I)) =
hin≺(inv(f)) : f ∈ G≺(I)i. By the lemma in≺(inv(I)) = in≺(I). By Corol-
lary 4.2.4 {in≺(inv(f)) : f ∈ G≺(I)} = {in≺(f) : f ∈ G≺(I)}, which equals
in_{≺}(I) since G≺(I) is a Gr¨obner basis. The set{in_{≺}(inv(f)) : f ∈ G≺(I)} is a
minimal generating set since {in_{≺}(f) : f ∈ G≺(I)} is. The set {in_{v}(f) : f ∈
G≺(I)} is a reduced Gr¨obner basis because no non-initial terms of elements in
G≺(I) are in in_{≺}(I) = in_{≺}(inv(I)). 2

Algorithm 4.4.5

Input: An ideal I ⊆k[x1, . . . , xn]and a vector v ∈R^{n}_{≥0} and a term order ≺.
Output: A reduced Gr¨obner basis forinv(I) with respect to ≺.

• ComputeG≺v(I).

• Return{inv(f) :f ∈ G≺v(I)}.

Proof. We first prove that v ∈ C≺v(I) using Corollary 4.2.4. For g in the Gr¨obner basis of the corollary we have to check that in≺v(g) = in≺v(inv(g)), but this holds for any polynomial g. The correctness now follows from Corol- lary 4.4.4. 2

Example 4.4.6 LetI =hx+y+z^{2}, y^{2}−z^{3}i ⊆Q[x, y, z] and v= (0,1,1). To
compute in_{v}(I) we first compute

G≺v(I) ={z^{2}+y+x,
yz+y^{2}+xz,

y^{3}+y^{2}+ 2xy−xy^{2}+x^{2}−x^{2}z}
where≺is some term ordering. We now take initial forms:

G≺(inv(I)) ={z^{2}, yz+y^{2}, y^{3}}.
Lemma 4.4.7 If in_{≺}(I) = in_{≺}^{′}(I) thenG≺(I) =G≺^{′}(I).

Proof. Exercise! Hint: the proof of Proposition 1.6.14. 2

Proposition 4.4.8 Let I ⊆k[x_{1}, . . . , x_{n}]be an ideal. There exists only finitely
many initial ideals of the form inv(I) where v∈R^{n}_{≥0}.

Proof. By Proposition 4.1.1 there are only finitely many initial ideals of the form in(I)≺. It follows from Lemma 4.4.7 above that there are only a finite number of reduced Gr¨obner bases ofI. By Corollary 4.4.4 a generating set for any initial ideal is gotten by taking initial forms of one of these Gr¨obner bases.

There are only a finite number of choices for what terms a vectorv will pick.

2

Proposition 4.4.9 [7, Proposition 2.6] Let I ⊆ k[x_{1}, . . . , x_{n}] be an ideal and

≺a term order and v∈C≺(I). For u∈R^{n} we have:

inu(I) = inv(I)⇔ ∀g∈ G^{≺}(I) : inu(g) = inv(g).

Proof. ⇐: Since v∈C_{≺}(I), Corollary 4.2.4 shows that in_{≺}(g) = in_{≺}(in_{v}(g)) =
in≺(inu(g)). Applying the corollary again we getu∈C≺(I). By Corollary 4.4.4
G≺(inv(I)) ={inv(f) :f ∈ G≺(I)}={inu(f) :f ∈ G≺(I)}=G≺(inu(I)). Since
the Gr¨obner bases are the same, in_{v}(I) = in_{u}(I).

⇒: Let g ∈ G≺(I). By Corollary 4.2.4 we have in≺(inv(g)) = in≺(g). By
Lemma 4.4.3, since v ∈ C_{≺}(I), in_{≺}(inu(g)) ∈ in_{≺}(inu(I)) = in_{≺}(inv(I)) =
in_{≺}(I). Since g comes from a reduced basis only one term is in in_{≺}(I). Hence
in≺(inu(g)) = in≺(g) = in≺(inv(g)). Now we cancel out the term by subtract-
ing. Suppose inu(g)−inv(g) ∈inu(I) = inv(I) is non-zero. Then in_{≺}(inu(g)−
in_{v}(g)) ∈ in_{≺}(in_{v}(I)) = in_{≺}(I), contradicting that g contains only one term
from in≺(I).2

Example 4.4.10 Write up inequality system for having

Lemma 4.4.11 Given a polynomial g ∈ k[x1, . . . , xn] and a vector v ∈ R^{n}.
The set of vectors u such that inu(g) = inv(g) is a relatively open polyhedral
cone.

Proof. It is straight forward to see that inu(g) = inv(g) translates into equations
(arising from having all terms in inv(g) having the same u-degree) and strict
inequalities (arising from having all other terms of g u-degree less than the
u-degree of in_{v}(g)). Hence the set is a relatively open polyhedral cone. 2

We conclude, using the proposition, that every equivalence class described by the proposition is a finite intersections relatively open polyhedral cones and therefore a relatively open polyhedral cone.

4.5 The relative interior of a cone is an equivalence class