SAGBI BASES IN RINGS OF MULTIPLICATIVE INVARIANTS

ZINOVY REICHSTEIN

Abstract. Let k be a field and G be a finite subgroup of GL_{n}(ℤ). We show that the ring of multiplicative invariants k[x_{1}^{±1}, …, x_{n}^{±1}]^{G} has a finite SAGBI basis if and only if G is generated by reflections.

1. Introduction

Let k[x] = k[x_{1}, …, x_{n}] be the polynomial ring in n variables over a field k and let ℕ denotes the set of non-negative integers. If a = (a_{1}, …, a_{n}) ∈ ℕ^{n}, we shall write x^{a} in place of x_{1}^{a_{1}} … x_{n}^{a_{n}}. We begin by recalling the following: Definition 1.1. A term order in k[x] is a total order ≻ on ℕ^{n} such that

(i) a ≻ (0, …, 0) for every nonzero a ∈ ℕ^{n}, and

(ii) ≻ is compatible with addition, i.e., if a ≻ b then a + c ≻ b + c for any a, b, c ∈ ℕ^{n}. (Equivalently, if a ≻ b and and c ⪰ d then a + c ≻ b + d.)

A prototypical example is the usual lexicographic order on ℕ^{n}; other examples can be found in, e.g, [3, Section 1.2] and [15, p. 4]. Given a non-zero element f = ∑ c_{a}x^{a} ∈ k[x], we define the initial exponent in(f) of f to be the largest exponent a (with respect to ≻) such that c_{a} ≠ 0. If R is a subring of k[x] then we define

(1)  In(R) = {in(f) : 0 ≠ f ∈ R} .

It is easy to see that In(R) is a subsemigroup of ℕ^{n}. If {in(f_{λ}) | λ ∈ Λ} is a generating set for this semigroup, where each f_{λ} ∈ R, then R = k[f_{λ} | λ ∈ Λ]. In fact, a simple algorithm, due to Kapur-Madlener [10] and Robbiano-Sweedler [13], expresses a given nonzero element α ∈ R as a polynomial in f_{λ} as follows. Write in(α) = d_{1}in(f_{λ_{1}})+⋯+d_{r}in(f_{λ_{r}}) for some d_{1}, …, d_{r} ∈ ℕ. Dividing the leading coefficient of α by the leading coefficient of f_{λ_{1}}^{d_{1}} … f_{λ_{r}}^{d_{r}}, we obtain a c ∈ k such that the leading term of α is the same as the leading term of cf_{λ_{1}}^{d_{1}} … f_{λ_{r}}^{d_{r}}. Set α_{1} = α − cf_{λ_{1}}^{d_{1}} … f_{λ_{r}}^{d_{r}}. If α_{1} = 0 then we are done; otherwise we replace α by α_{1} and proceed inductively. Since α_{1} has a smaller leading exponent than α, and ℕ^{n} is well ordered with respect to ≻ (see [3, Corollary 2.4.6]), this process will terminate, resulting in an expression for α as a polynomial in f_{λ}. We shall refer to this procedure as the subduction algorithm.

1991 Mathematics Subject Classification. 13A50, 20C10, 13P99, 52B20, 52B55.

Key words and phrases. SAGBI basis, term order, initial term, subduction algorithm, Gröbner basis, multiplicative groups action, algebra of invariants, integral representation, reflection group, permutation group, convex cone, polyhedral cone, finitely generated semigroup.

The subduction algorithm is analogous to expressing an element of an ideal of k[x] in terms of a Gröbner basis; for this reason a generating set for the semigroup In(R) is called a SAGBI basis of R, where SAGBI stands for “Subalgebra Analog to Gröbner Bases for Ideals”. (The terms “SAGBI basis” and “subduction algorithm” was introduced to Robbiano and Sweedler in [13].) The analogy with Gröbner bases is not perfect though because not every subring R ⊂ k[x] has a finite SAGBI basis; see e.g., [13, 1.20 or 4.11], or [15, pp. 99-100]. It is an important open problem to determine which subrings R of k[x] have a finite SAGBI basis; see [15, p. 100].

We will now consider a parallel situation, where R is a subring of the ring k[x^{±1}] = k[x_{1}^{±1}, …, x_{n}^{±1}] of Laurent polynomials in n variables over k. Our first task is to define a term order in k[x^{±1}]. Definition 1.2. By a term order in k[x^{±1}] we shall mean a total order ≻ on ℤ^{n} compatible with addition. That is, if a ≻ b then a + c ≻ b + c for any a, b, c ∈ ℤ^{n}.

Our requirements on ≻ are considerably weaker here than in Definition 1.1. In fact, conditions (i) and (ii) of Definition 1.1 cannot both hold in an ordered group; thus we have little choice but to drop (i).

Given a term order in k[x^{±1}], we can define the initial exponent in(f) for every nonzero f ∈ R and the semigroup of initial exponents In(R) in the same way as before; cf. (1). We shall say that {f_{λ} | λ ∈ Λ} ⊂ R is a SAGBI basis of R if

(a) in(f_{λ}) generate In(R) as a semigroup, as λ ranges over Λ, and

(b) the subduction algorithm described above terminates for every α ∈ R. Note that the steps in the subduction algorithm are not always uniquely determined. Each step involves writing an element of In(R) as a nonnegative integral linear combination of in(f_{λ}), and there may be more than one way to do this. Condition (b) requires that the algorithm should terminate no matter what choices are made.

The question we would like to address is: Question 1.3. Which subrings R of the Laurent polynomial ring k[x^{±1}] have a finite SAGBI basis?

At first glance, this is a rather odd question to ask. First of all, we have to decide whether or not In(R) is finitely generated, and as we pointed out above, this is an open problem even in the special case where R is contained in the polynomial ring k[x]. Secondly, a priori the existence of a finite SAGBI basis depends on the term order ≻. Thirdly, for the purpose of performing computations, we would like the answer to be positive. On the other hand, since ℤ^{n} is not well ordered with respect to ≻, there is no reason to expect the subduction algorithm to terminate. Thus even in those cases where we can establish that In(R) is finitely generated, the answer appears likely to be negative.

The purpose of this paper is to show that, notwithstanding these considerations, Question 1.3 can be completely answered in the case where R is the invariant ring for a multiplicative group action and that for many rings of this type, the answer is, indeed, positive, without any assumptions on the base field k or on the term order ≻.

Before stating our main results, we need to introduce some terminology. Let G be a finite subgroup of GL_{n}(ℤ). Recall that the natural (multiplicative) action of G on k[x^{±1}] = k[x_{1}^{±1}, …, x_{n}^{±1}] is defined by linearly extending the formula g(x^{a}) = x^{g(a)} to all of k[x^{±1}]; here, as usual, x^{a} = x_{1}^{a_{1}} … x_{n}^{a_{n}} is a Laurent monomial. Recall also that g ∈ GL_{n}(ℝ) is called a reflection if g^{2} = id, and the eigenvalues of g are −1 (with multiplicity 1) and 1 (with multiplicity n − 1). We shall say that G ⊂ GL_{n}(ℝ) is a reflection group if G is generated by reflections. Theorem 1.4. Let R = k[x^{±1}]^{G} be the ring of multiplicative invariants for a finite subgroup G of GL_{n}(ℤ). Then the semigroup In(R) is finitely generated if and only if G is a reflection group.

To place Theorem 1.4 in the context of invariant theory, consider the linear action a finite subgroup H of GL_{n}(k) on the polynomial ring k[x] = k[x_{1}, …, x_{n}], where k is a field whose characteristic is prime to |H|. Recall that a nontrivial element g of GL_{n}(k) is called a pseudo-reflection if g has finite order and 1 is an eigenvalue of g of multiplicity n − 1. (Note that for k ⊂ ℝ the notions of reflection and pseudo-reflection coincide.) The celebrated theorem of Chevalley, Shephard and Todd asserts that H is generated by pseudo-reflections if and only if the ring of invariants k[x]^{H} is itself a polynomial ring; cf. e.g., [1, V.5] or [14, 2.4] . A variant of this result in the multiplicative context is due to Farkas, who showed that the multiplicative invariant ring k[x^{±1}]^{G} for a finite subgroup G ⊂ GL_{n}(ℤ) is a generalized polynomial ring (i.e., has the form k[u_{1}^{±1}, …, u_{m}^{±1}, w_{1}, …, w_{l}], where u_{1}, …, u_{m}, w_{1}, …, w_{l} are independent variables) if and only if G is generated by reflections and the G-lattice ℤ^{n}/(ℤ^{n})^{G} is a weight lattice in a suitable sense; see [5] and [6]. (Farkas assumed k = ℂ.) Theorem 1.4 may be viewed as an alternative and perhaps complementary, analogue of the Chevalley-Shephard-Todd theorem in the multiplicative setting. (Farkas’ results have been recently refined and extended by Lorenz [11], [12], who showed, in particular, that if G ⊂ GL_{n}(ℤ) is a reflection subgroup then k[x^{±1}]^{G} is a semigroup algebra; see [12, Theorem 2.4].)

Our second main result is the following: Theorem 1.5. Let G be a finite reflection subgroup of GL_{n}(ℤ). Then the invariant ring R = k[x_{1}^{±1}, …, x_{n}^{±1}]^{G} has a finite SAGBI basis.

Moreover, we will show that if (ℤ^{n})^{G} = (0) then R = k[x^{±1}]^{G} has a canonical “minimal” SAGBI basis, independent of the term order ≻; see Remark 7.1.

Of course, if G is not generated by reflections then, by Theorem 1.4 the invariant ring k[x^{±1}]^{G} cannot have a finite SAGBI basis. Thus Theorems 1.4 and 1.5 can be combined to give a complete answer to Question 1.3 in the case where R is a ring of multiplicative invariants:

Theorem 1.6. Let R = k[x^{±1}]^{G} be the ring of invariants for the multiplicative action of a finite group G ⊂ GL_{n}(ℤ). Then the following are equivalent:

(a) In(R) is finitely generated as a semigroup,

(b) R has a finite SAGBI basis, and

(c) G is a reflection group.

We remark that the properties of having a finitely generated semigroup of leading exponents or a finite SAGBI basis are not intrinsic to R = k[x^{±1}]^{G}; they depends on the embedding of R in k[x^{±1}]. On the other hand, Theorems 1.4-1.6 require no assumptions on the term order ≻ or the base field k. In fact, k can even be replaced by a rather general ring; see Remark 7.2.

Our proofs of Theorems 1.4 and 1.5, (presented, respectively, in Sections 3-4 and 5) are quite elementary; they rely only on a few simple properties of polyhedral cones and reflection groups in ℝ^{n}. Our background references for these subjects are, respectively, Ewald [4, Part 1] and Bourbaki [1, Chapter V]; some preliminary definitions and results can also be found in Section 2.

To state our last main result, consider the natural (permutation) action of a finite group H ⊂ S_{n} on the polynomial ring k[x] = k[x_{1}, …, x_{n}]. Göbel [7, 5.6] showed that the invariant ring R = k[x]^{H} has a finite SAGBI basis, with respect to the usual lexicographic term order in k[x], if and only if H = S_{n_{1}} × ⋯ × S_{n_{r}} for some partition n_{1} + ⋯ + n_{r} = n. Göbel further conjectured [8, p. 65] that the same should be true for an arbitrary term order in the sense of Definition 1.1 and proved this conjecture in the case where H = A_{n} is the alternating group [9]. In Section 6 we will prove Göbel’s conjecture, as an application of our Theorem 1.4:

Theorem 1.7. Let ≻ be a term order in k[x] = k[x_{1}, …, x_{n}] and let H ⊂ S_{n} be a permutation group. Then the ring of invariants k[x_{1}, …, x_{n}]^{G} has a finite SAGBI basis with respect to ≻ if and only if H = S_{n_{1}} × ⋯ × S_{n_{r}} for some partition n_{1} + ⋯ + n_{r} = n.

An independent proof Theorem 1.7 was recently obtained by Thiéry and Thomassé [16].

2. Preliminaries

2.1. Polyhedral cones. We define the positive span Pos(X) of a subset X of ℝ^{n} to be the set of points of the form r_{1}v_{1} + ⋯ + r_{m}v_{m}, where m ranges over the positive integers, v_{1}, …, v_{m} range over X and r_{1}, …, r_{m} range over the non-negative reals.

If X = {v_{1}, …, v_{n}} is a finite subset of ℝ^{n} (respectively, ℤ^{n}), then Pos(X) is called a polyhedral cone (respectively an integral polyhedral cone). We shall write Pos(v_{1}, …, v_{n}) in place of Pos({v_{1}, …, v_{n}}). Lemma 2.1. (a) C ⊂ ℝ^{n} is a polyhedral cone (respectively an integral polyhedral cone) if and only if there exist finitely many linear forms (respectively, linear forms with integer coefficients) l_{1}, …, l_{m} on ℝ^{n} such that

C = {v ∈ ℝ^{n} | l_{1}(v) ≥ 0, …, l_{m}(v) ≥ 0} .

(b) A polyhedral cone is closed in ℝ^{n}.

Proof. (a) is proved in [4, Theorem V.2.10]. (b) is an immediate consequence of (a). □

Lemma 2.2. Let C = Pos(v_{1}, …, v_{m}) be an integral polyhedral cone for some v_{i} = (x_{i1}, …, x_{in}) ∈ ℤ^{n}. Denote the (positive) least common multiple of the non-zero minors of the m × n-matrix (x_{ij}) by δ. Then for any lattice point w ∈ C ∩ ℤ^{n} there exist nonnegative integers n_{1}, …, n_{r} such that δw = n_{1}v_{1} + ⋯ + n_{m}v_{m}.

Proof. By Carathéodory’s theorem (see, e.g., [4, Theorem I.2.3(b)]), we can write w as a positive linear combination of a linearly independent subset of {v_{1}, …, v_{m}}. Thus we may assume without loss of generality that v_{1}, …, v_{m} are linearly independent and w = r_{1}v_{1} + ⋯ + r_{m}v_{m}, where r_{1}, …, r_{m} > 0. Now Cramer’s rule tells us that | det(M)|(r_{1}, …, r_{m}) ∈ ℤ^{m} for some nonsingular m × m-submatrix M of (x_{ij}). Moreover, since r_{1}, …, r_{m} > 0 we have

| det(M)|(r_{1}, …, r_{m}) ∈ ℕ^{m} .

Consequently, δ(r_{1}, …, r_{m}) ∈ ℕ^{m}, as claimed. □

2.2. Saturated semigroups. We shall call a subsemigroup S of ℤ^{n} saturated if na ∈ S implies a ∈ S for any a ∈ S and any integer n ≥ 1. Lemma 2.3. Let S be a saturated subsemigroup of ℤ^{n}. Then S = Pos(S) ∩ ℤ^{n}.

Proof. Clearly S ⊂ Pos(S) ∩ ℤ^{n}. To prove the opposite inclusion, note that by Lemma 2.2, for every w ∈ Pos(S) ∩ ℤ^{n} there exists a positive integer δ such that δw ∈ S. Since S is saturated, w ∈ S, as claimed. □

Proposition 2.4. Let S be a saturated subsemigroup of ℤ^{n}. Then the following are equivalent:

(a) S is finitely generated (as a semigroup),

(b) Pos(S) is an integral polyhedral cone.

Proof. (a) ⟹ (b): If S is generated by x_{1}, …, x_{m} then clearly

Pos(S) = Pos(x_{1}, …, x_{m})

is an integral polyhedral cone.

(b) ⟹ (a): By Lemma 2.3, S = Pos(S) ∩ ℤ^{n}. The desired result now follows from Gordan’s Lemma [4, V.3.4] which says that Pos(S) ∩ ℤ^{n} is finitely generated. □

2.3. The sets A^{≻} and X^{≻}. Definition 2.5. Given a finite subgroup G of GL_{n}(ℤ), we define

A^{≻}(G) = {a ∈ ℤ^{n} | a ⪰ g(a) for any g ∈ G}

and

X^{≻}(G) = Pos(A^{≻}(G)) .

If the reference to G is clear from the context, we shall write A^{≻} and X^{≻} in place of A^{≻}(G) and X^{≻}(G) respectively. Lemma 2.6. Let G be a finite subgroup of GL_{n}(ℤ) and let R = k[x^{±1}]^{G}. Then

(a) In(R) = A^{≻}(G).

(b) In(R) is a saturated subsemigroup of ℤ^{n}.

(c) In(R) is a finitely generated semigroup if and only if X^{≻}(G) is an integral polyhedral cone.

Proof. (a) Suppose a ∈ In(R), i.e., a = in(f) for some f ∈ R. Then x^{a} enters into f ∈ R with a non-zero coefficient, and hence, so does x^{g(a)} for every g ∈ G. Since x^{a} is the initial term of f, a ⪯ g(a) for any g ∈ G. Hence, a ∈ A^{≻}(G).

Conversely, suppose a ∈ A^{≻}(G). Then f = ∑ x^{g(a)} is a non-zero element of R and a = in(f) ∈ In(R).

(b) follows from (a), since A^{≻}(G) is clearly a saturated subsemigroup of ℤ^{n}; cf. Definition 2.5.

(c) is immediate from (b) and Proposition 2.4. □

We remark that Lemma 2.6(b) fails if we consider a linear (rather than a multiplicative) action of a finite group G, either on the polynomial ring k[x] or on the Laurent polynomial ring k[x^{±1}]. For example, suppose n = 1, and G = {1, τ} ≃ ℤ/2ℤ acts by τ(x_{1}) = −x_{1}. Then neither In(k[x]^{G}) = 2ℕ nor In(k[x^{±1}]^{G}) = 2ℤ is a saturated subsemigroup of ℤ.

2.4. Fundamental sets. Definition 2.7. Suppose a group G is acting on a set E. We shall call F ⊂ E a fundamental set for this action if each G-orbit in F intersects E in exactly one point. Equivalently, F is a fundamental set for the G-action on E if the following conditions are satisfied.

(i) ∪_{g∈G} g(F) = E and

(ii) If g(a) ∈ F for some a ∈ F and g ∈ G, then g(a) = a.

Note the we are not assuming anything about the topology of F (or E); for this reason we are prefer the term “fundamental set” to the more commonly used “fundaments region” or “fundamental domain”.

Lemma 2.8. Let G be a finite subgroup of GL_{n}(ℤ).

(a) A^{≻} is a fundamental set for the G-action on ℤ^{n}.

(b) If X^{≻} is an integer polyhedral cone then X^{≻} is a fundamental set for the G-action on ℝ^{n}.

Proof. (a) Immediate from the definition of A^{≻}, since every G-orbit in ℤ^{n} has a unique maximal element with respect to ≻.

(b) To prove (i), set V = ∪_{g∈G} g(X^{≻}). Then V contains ∪_{g∈G} g(A^{≻}), which is equal to ℤ^{n} by part (a). Since V is a positive cone, i.e., rV = V for every real number r > 0, V contains ℚ^{n}. Since V is closed in ℝ^{n} (cf. Lemma 2.1(b)), this implies V = ℝ^{n}, as claimed.

To prove (ii), suppose g(v) ∈ X^{≻} for some v ∈ X^{≻}; in other words, v ∈ X^{≻} ∩g^{−1}(X). We want to show g(v) = v. By Lemma 2.1(a), X^{≻} ∩g^{−1}(X^{≻}) is an integer polyhedral cone, i.e., X^{≻}∩g^{−1}(X^{≻}) = Pos(v_{1}, …, v_{m}) for some v_{1}, …, v_{m} ∈ ℤ^{n}. Thus it is enough to show that v_{1}, …, v_{m} are fixed by G. In other words, we may assume without loss of generality that v = v_{i} for some i = 1, …, m. But then v ∈ X^{≻} ∩ ℤ^{n} = A^{≻}; cf. Lemma 2.3, and the desired identity, g(v) = v, follows from part (a). □

Corollary 2.9. A^{≻} (and thus X^{≻}) cannot be covered by a finite union of hyperplanes in ℝ^{n}.

Proof. Assume the contrary: A^{≻} ⊂ H_{1} ∪ ⋯ ∪ H_{r}, where each H_{i} is a hyperplane. By Lemma 2.8(b), ℤ^{n} = ∪_{g∈G} g(A^{≻}). Thus ℤ^{n} is covered by the (finitely many) hyperplanes g(H_{i}), where g ∈ G and 1 ≤ i ≤ r, a contradiction. □

3. Proof of Theorem 1.4: the “if” direction

In view of Lemma 2.6(c), it suffices to prove the following: Proposition 3.1. Suppose G is a finite reflection subgroup of GL_{n}(ℤ). Then X^{≻} is an integral polyhedral cone.

Proof. We will denote the reflections in G by s_{1}, …, s_{m} ∈ G. Let e_{i} be an eigenvector of s_{i} associated to the eigenvalue −1. Since s_{i} ∈ GL_{n}(ℤ), we can choose e_{i} ∈ ℤ^{n}; moreover, after possibly replacing e_{i} by −e_{i}, we may assume e_{i} ⪰ (0, …, 0). Define linear forms l_{1}, …, l_{m}: ℝ^{n} ⟶ ℝ by l_{i}(v) = <v, e_{i}>, where

(2)  <x, y> = ∑_{g∈G} g(x) · g(y) .

is a G-invariant positive-definite bilinear form on ℝ^{n}. (Here x · y is the standard inner product on ℝ^{n}.) Note that s_{i} is an orthogonal (with respect to < · , · >) reflection in the hyperplane H_{i} = {v ∈ ℝ^{n} | l_{i} = 0} and that the linear forms l_{i} have integer coefficients.

Let C = {v ∈ ℝ^{n} | l_{i}(v) ≥ 0 for i = 1, …, m}. By Lemma 2.1(a), C is an integral polyhedral cone. Our goal is to prove that X^{≻} = C.

First we will show that X^{≻} ⊂ C. Recall that X^{≻} is defined as Pos(A^{≻}); thus it is enough to show that A^{≻} ⊂ C. Assume the contrary: there exists a v ∈ A^{≻} such that v ∉ C, i.e., l_{i}(v) < 0 for some i = 1, …, m. Then by our choice of e_{i}

s_{i}(v) = v − 2\frac{l_{i}(v)}{<v, v>}e_{i} ≻ v ,

contradicting v ∈ A^{≻}. This proves that X^{≻} ⊂ C.

To prove the opposite inclusion, recall that by Corollary 2.9 X^{≻} is not contained in a finite union of hyperplanes. Since X^{≻} ⊂ C, neither is C. Thus

C_{0} = {v ∈ ℝ^{n} | l_{i}(v) > 0 for i = 1, …, m}

is non-empty and is a chamber for the collection of hyperplanes H_{1}, …, H_{m}; cf. [1, V.3.1]. Consequently, C = \overline{C_{0}} (see [1, V.1.3, formula (6)]) and C ⊂ ℝ^{n} is a fundamental set for the G-action on ℝ^{n} (see [1, V.3.3, Theorem 2]).

We are now ready to show that C ⊂ X^{≻}. Suppose C = Pos(v_{1}, …, v_{t}) for some v_{1}, …, v_{t} ∈ ℤ^{n}. Then it is enough to show that each v_{i} lies in A^{≻}. Set v = v_{i} and choose a g ∈ G such that g(v) ∈ A^{≻}; cf. Lemma 2.8(a). Since A^{≻} ⊂ X^{≻} ⊂ C, both v and g(v) lie in C. Since C is a fundamental set for the G-action on ℝ^{n}, this implies v = g(v). In particular, v ∈ A^{≻}, as claimed. This completes the proof of Proposition 3.1. □

4. Proof of Theorem 1.4: the “only if” direction

Assume that In(k[x^{±1}]^{G}) is a finitely generated semigroup for some G ⊂ GL_{n}(ℤ). We want to show that G is generated by reflections. By Lemma 2.6(c), X^{≻} is an integral polyhedral cone. Thus in order to complete the proof of Theorem 1.4 it suffices to establish the following: Proposition 4.1. Suppose X is a fundamental set for the natural action of a finite subgroup G ⊂ GL_{n}(ℝ) on ℝ^{n}. If X is a polyhedral cone then G is generated by reflections.

For the purpose of proving Theorem 1.4, we only need a special case of Proposition 4.1: we may assume that G ⊂ GL_{n}(ℤ) and X = X^{≻}(G) is an integral polyhedral cone. Note however, that if G ⊂ GL_{n}(ℤ) and X(G) is a polyhedral cone then Propositions 3.1 and 4.1 imply that X(G) is automatically integral.

The rest of this section will be devoted to proving Proposition 4.1. Let < · , · > be the G-invariant positive-definite bilinear from on ℝ^{n} given by (2).

Since X is a fundamental set for the G-action on ℝ^{n}, X is not contained in a hyperplane; thus dim(X) = n. Let h_{1}, …, h_{m} be the (closed) facets (i.e., (n − 1)-dimensional faces) of X, H_{i} = Span_{ℝ}(h_{i}) be the hyperplane in ℝ^{n} containing h_{i}, and s_{i} be the orthogonal (with respect to < · , · >) reflection in H_{i}. Lemma 4.2. (a) The boundary of X is contained in Y = ∪_{g(X)≠X}g(X).

(b) s_{i} ∈ G for any i = 1, …, m.

Proof. (a) Assume the contrary: a boundary point v of X does not lie in Y. Since Y is a closed subset of ℝ^{n} (cf. Lemma 2.1(b)), B ∩ Y = ∅ for some open ball B centered at v. Since v is a boundary point of X (cf. Lemma 2.1(b)), there exists a w ∈ B − X. Thus w ∉ Y ∪ X. On the other hand, since X is a fundamental set for the G-action on ℝ^{n}, we know that Y ∪ X = ℝ^{n}, a contradiction.

(b) Suppose v lies in a facet h_{i} of X. By part (a), g^{−1}(v) ∈ X, for some 1 ≠ g ∈ G. Since X is a fundamental set for G, this is only possible if g^{−1}(v) = v. In other words, every facet h_{i} lies in the union of the linear spaces L_{g}, where

(3)  L_{g} = (ℝ^{n})^{g} = {x ∈ ℝ^{n} | g(x) = x}

and g ranges over those g ∈ G for which g(X) ≠ X. But then each supporting hyperplane H_{i} also lies in ∪_{g∈G}L_{g}. Since H_{i} cannot be covered by a finite number of proper linear subspaces, we conclude that H_{i} ⊂ L_{g_{i}} for some 1 ≠ g_{i} ∈ G. Since dim(H_{i}) = n − 1 and dim(L_{g_{i}}) ≤ n − 1, this is only possible if H_{i} = L_{g_{i}}. Since g_{i} preserves < · , · > and fixes each point of H_{i}, we conclude that g_{i} is the orthogonal reflection in H_{i}, i.e., g_{i} = s_{i}. Thus s_{i} ∈ G, as claimed. □

We are now ready to complete the proof of Proposition 4.1. Let G_{0} be the subgroup of G generated by s_{1}, …, s_{m}, and let F be the collection of hyperplanes of the form g_{0}(H_{i}), where g_{0} ∈ G_{0} and i = 1, …, m. Note that F is a G_{0}-invariant collection of hyperplanes in ℝ^{n} and that G_{0} contains the orthogonal reflection g_{0}s_{i}g_{0}^{−1} in the hyperplane g_{0}(H_{i}).

Since X is a fundamental set for the G-action on ℝ^{n}, it cannot be covered by finitely many hyperplanes. Thus we can choose a point v in X such that g(v) ≠ v for any 1 ≠ g ∈ G. In particular v ∉ H for any hyperplane H ∈ F; otherwise s(v) = v, where s ∈ G_{0} ⊂ G is the orthogonal reflection in H. Now let C be the (unique) chamber, relative to the collection of hyperplanes F, such that v ∈ C. Since H_{1}, …, H_{m} ∈ F, we have C ⊂ X. Moreover, since X is closed in ℝ^{n} (cf. Lemma 2.1(b)), \overline{C} ⊂ X. By [1, Lemma V.3.1.1], \overline{C} is a fundamental set for the action of G_{0} on ℝ^{n}. In particular, every point in ℝ^{n} can be written in the form g_{0}(c) for some c ∈ \overline{C} and g_{0} ∈ G_{0}.

We claim that G = G_{0}. Indeed, suppose g ∈ G. Write g(v) as g_{0}(c) for some c ∈ \overline{C}. Since X is a fundamental set for the action of G on ℝ^{n} and both v and c = g_{0}^{−1}g(v) lie in X, we conclude that v = c, or equivalently g_{0}^{−1}g ∈ Stab_{G}(v). But Stab_{G}(v) = {1} by our choice of v. Thus g = g_{0} ∈ G_{0}. This shows that G = G_{0}, i.e., G is generated by reflections. □

5. Proof of Theorem 1.5

We now return to the situation of Section 3; we begin by recalling the notations introduced there. Let G be a finite subgroup of GL_{n}(ℤ). Denote the reflections contained in G by s_{1}, …, s_{m}; we shall assume that these elements generate G. For each i = 1, …, m choose an eigenvector e_{i} ∈ ℤ^{n} of s_{i} associated to eigenvalue −1. After possibly replacing e_{i} by −e_{i}, we may assume e_{i} ≻ (0, …, 0) for every i. We fix a G-invariant positivedefinite bilinear form < · , · > defined over ℤ; cf. (2). For i = 1, …, m, set l_{i}(v) = <v, e_{i}> and H_{i} = {v ∈ ℝ^{n} | l_{i}(v) = 0}; note that each l_{i} is a linear form on ℝ^{n} with integer coefficients. In Section 3 we showed that

C_{0} = {v ∈ ℝ^{n} | l_{i}(v) > 0 for i = 1, …, m}

is a chamber for the collection of hyperplanes H_{1}, …, H_{m} and

(4)  X^{≻} = \overline{C_{0}} = \{v ∈ ℝ^{n} | l_{i}(v) ≥ 0 for i = 1, …, m\}.

After possibly renumbering the reflections s_{1}, …, s_{m}, we may assume that the hyperplanes H_{1}, …, H_{t} are the walls of C_{0} for some t ≤ m. That is,

(5)  X^{≻} = {v ∈ ℝ^{n} | l_{i}(v) ≥ 0 for i = 1, …, t}.

Lemma 5.1. <e_{i}, e_{j}> ≤ 0 for any distinct i, j = 1, …, t.

Proof. Since A^{≻} is not contained in a finite union of hyperplanes (see Corollary 2.9), there exists a point v ∈ A^{≻} ∩ C_{0}. Now by the definition of A^{≻},

n_{i} = s_{i}(v) − v = −2\frac{l_{i}(v)}{<v, v>}e_{i}

is an inward normal vector to H_{i}. Note that l_{i}(v) > 0, because v lies in C_{0}. Thus n_{i} is a negative multiple of e_{i} for every i = 1, …, t. The lemma now follows from by [1, Proposition V.3.4.3(iii)], which says that <n_{i}, n_{j}> ≤ 0. □

Lemma 5.2. Suppose v ∈ ℤ^{n}. Then the following are equivalent: (a) g(v) = v for every g ∈ G.

(b) both v and −v lie in A^{≻},

(c) both v and −v lie in X^{≻},

(d) l_{i}(v) = 0 for every i = 1, …, m,

(e) l_{i}(v) = 0 for every i = 1, …, t.

Proof. (a) ⇔ (b): By Definition 2.5, v ∈ A^{≻} iff v ⪰ g(v) for every g ∈ G. Thus −v ∈ A^{≻} iff v ⪯ g(v) for every g ∈ G, and v, −v both lie in A^{≻} iff v = g(v) for every g ∈ G, i.e., v ∈ (ℤ^{n})^{G}.

(b) ⇔ (c) follows from the fact that A^{≻} = X^{≻} ∩ ℤ^{n}; cf. Lemma 2.3.

(c) ⇔ (d) follows from (4).

(c) ⇔ (e) follows from (5). □

Lemma 5.3. (a) (ℝ^{n})^{G} = Span_{ℝ}(e_{1}, …, e_{m})^{⊥} = Span_{ℝ}(e_{1}, …, e_{t})^{⊥}, where W^{⊥} denotes the orthogonal complement of a subspace W in ℝ^{n}.

(b) (ℤ^{n})^{G} = (0) if and only if e_{1}, …, e_{t} span ℝ^{n}.

Proof. (a) is an immediate consequence of Lemma 5.2. (b) Follows from (a) and the fact that the vector space (ℝ^{n})^{G} is defined over ℚ. □

Remark 5.4. In the language of [4], Lemma 5.3(b) can be restated as follows: (ℤ^{n})^{G} = (0) if and only if X^{≻} has an apex at (0); cf. [4, Lemma V.2.2(c)]. Proposition 5.5. A^{≻} ∩ Span_{ℝ}(e_{1}, …, e_{t}) is well ordered with respect to ≻.

Proof. (a) Assume the contrary: there exists an infinite strictly decreasing sequence

(6)  a_{1} ≻ a_{2} ≻ a_{3} ≻ …

in A^{≻} ∩ Span_{ℝ}(e_{1}, …, e_{t}). Note that l_{1}(a_{i}) is a non-negative integer for every i ≥ 1. Thus we can choose i_{1} ≥ 1 so that l_{1}(a_{i_{1}}) ≤ l_{1}(a_{i}) for every i ≥ 1. Now choose i_{2} so that l_{1}(a_{i_{2}}) ≤ l_{1}(a_{j}) for all j ≥ i_{1} + 1, i_{3} so that l_{1}(a_{i_{2}}) ≤ l_{1}(a_{h}) for all h ≥ i_{2} + 1, etc. Thus after replacing the sequence (6) by a subsequence we may assume that l_{1}(a_{1}) ≥ l_{1}(a_{2}) ≥ . . .. Proceeding inductively (with l_{1} replaced by l_{2}, then l_{3}, etc.), we conclude that, after replacing (6) by a subsequence, we may assume l_{j}(a_{i+1}) ≥ l_{j}(a_{i}) for every j = 1, …, t and every i ≥ 1.

Now consider the element b = a_{2}−a_{1} ≺ (0, …, 0). Since we are assuming that a_{1} and a_{2} lie in Span_{ℝ}(e_{1}, …, e_{t}), we can write b = r_{1}e_{1} + ⋯ + r_{t}e_{t}, where r_{1}, …, r_{t} are rational numbers. Since l_{j}(b) ≤ 0 for every j = 1, …, t, and <e_{i}, e_{j}> ≤ 0 whenever i ≠ j, [1, Lemma V.3.5.6] says that each r_{i} ≥ 0, i.e., r_{i} = \frac{p_{i}}{q}, where p_{1}, …, p_{t}, q ∈ ℕ and q ≠ 0. Now

qb = p_{1}e_{1} + ⋯ + p_{t}e_{t} .

The left hand side ≺ (0, …, 0), and the right hand side is ⪰ (0, …, 0) by our choice of the vectors e_{i}. This contradiction shows that A^{≻} is well ordered. □

Corollary 5.6. Suppose G ⊂ GL_{n}(ℤ) is a finite reflection group and (ℤ^{n})^{G} = (0). If the initial exponents of the elements f_{λ} ∈ k[x^{±1}]^{G} generate In(k[x^{±1}]^{G}) then {f_{λ}} is a SAGBI basis of k[x^{±1}]^{G}.

Proof. By Lemma 5.3(b), Span_{ℝ}(e_{1}, …, e_{t}) = ℝ^{n} and by Proposition 5.5

A^{≻} = A^{≻} ∩ Span_{ℝ}(e_{1}, …, e_{t})

is well ordered. The subduction algorithm will create a strictly decreasing sequence of leading terms in A^{≻}; this sequence has to terminate. Thus the algorithm will terminate as well. □

Note that by Theorem 1.4 there exists a finite collection of elements f_{λ} ∈ k[x^{±1}]^{G} such that in(f_{λ}) generate In(k[x^{±1}]^{G}) as a semigroup. Thus in the case where (ℤ^{n})^{G} = (0), Theorem 1.5 is an immediate consequence of Corollary 5.6. We now turn to the general case, i.e., to the case where (ℤ^{n})^{G} may not be trivial. Example 5.7. Let n = 1 and G = {1}, so that k[x^{±1}]^{G} = k[x^{±1}] (here x = x_{1}). Of course, ℤ^{G} = ℤ ≠ (0). The initial exponents, 1 and −1, of the elements f_{1} = x and f_{2} = x^{−1} − x^{−2} generate In(k[x^{±1}]^{G}) = ℤ. We also have k[x^{±1}]^{G} = k[x^{±1}] = k[f_{1}, f_{2}]. Assume for simplicity that k is a field of characteristic 0.

We will now attempt to apply the subduction algorithm to express α = x^{−1} as a polynomial in f_{1} and f_{2}. The first step yields α_{1} = α − f_{2} = x^{−2}, the second α_{2} = α_{1} − f_{2}^{2} = 2x^{−3} − x^{−4}, etc. If we carry our the subduction algorithm by subtracting off scalar multiple of a power of f_{2} at each stage, the “remainder” α_{i} after i steps will have leading exponent −i − 1, and the algorithm will not terminate. We conclude that f_{1} and f_{2} do not form a SAGBI basis of k[x^{±1}] = k[x^{±1}]^{G}. □

Example 5.7 shows that Corollary 5.6 fails if (ℤ^{n})^{G} ≠ (0). Fortunately, it can be salvaged in this more general situation, if we choose our elements f_{λ} a little more carefully.

Recall that X^{≻} = Pos(A^{≻}) is an integral polyhedral cone. Write X^{≻} = Pos(v_{1}, …, v_{r}), where v_{1}, …, v_{r} ∈ X^{≻} ∩ ℤ^{n} = A^{≻}, and let

f_{i} = ∑_{g∈G} x^{g(v_{i})} .

The following Proposition completes the proof of Theorem 1.5. Proposition 5.8. f_{1}, …, f_{r} form a SAGBI basis of k[x^{±1}]^{G}.

Proof. By our construction the initial forms in(f_{1}), …, in(f_{r}) generate A^{≻} = In(k[x^{±1}]^{G}) as a semigroup. To show that they form a SAGBI basis, suppose we apply the subduction algorithm to express a given element α ∈ k[x^{±1}]^{G} in terms of f_{1}, …, f_{r}. This algorithm will produce a sequence of elements α_{0} = α, α_{1}, α_{2}, α_{3} … with leading terms

(7)  in(α_{0}) ≻ in(α_{1}) ≻ in(α_{2}) ≻ ….

Our goal is to show that this sequence will terminate. The idea of the proof is to consider the orthogonal decomposition in(α_{i}) = b_{i}+z_{i}, where b_{i} ∈ (ℝ^{n})^{G} and z_{i} ∈ Span_{ℝ}(e_{1}, …, e_{t}); cf. Lemma 5.3(a). We would then like to show that the sequence {z_{i}} terminates because of Proposition 5.5 and the sequence {b_{i}} terminates because it can only assume finitely many values. Since we are working over ℤ, rather than ℝ, this needs to be done with some care (in particular, the b_{i} ∈ (ℝ^{n})^{G} and z_{i} ∈ Span_{ℝ}(e_{1}, …, e_{t}) defined below are the orthogonal components of |G| in(α_{i}), rather than in(α_{i})), but this is the idea behind the argument to follow.

Assume, to the contrary, that the sequence (7) of initial terms does not terminate. Let p: ℝ^{n} ⟶ (ℝ^{n})^{G} be given by

p(v) = ∑_{g∈G} g(v) .

We claim that for every monomial x^{v} that appears in α there exists a monomial x^{w} that appears in α_{1}, such that p(v) = p(w). Indeed, suppose α_{1} = α − cf_{1}^{d_{1}} … f_{r}^{d_{r}}, where 0 ≠ c ∈ k, d_{1}, …, d_{r} ∈ ℕ, and

d_{1}v_{1} + ⋯ + d_{r}v_{r} = in(α) .

Every monomial that occurs in α_{1} either (i) occurs in α or (ii) occurs in f_{1}^{d_{1}} … f_{r}^{d_{r}} (or both). In case (i) the claim is trivial: we can take w = v. In case (ii), v has the form

v = d_{1}g_{1}(v_{1}) + ⋯ + d_{r}g_{r}(v_{r})

for some g_{1}, …, g_{r} ∈ G. Thus

p(v) = d_{1}p(v_{1}) + ⋯ + d_{r}p(v_{r}) = p(d_{1}v_{1} + ⋯ + d_{r}v_{r}) = p(in(α)) ,

so that in case (ii), we can take w = in(α). This proves the claim.

Let E = {p(v)}, where x^{v} ranges over the monomials of α and let b_{i} = p(in(α_{i})). Applying the claim inductively, we see that b_{i} ∈ E for every i ≥ 1. Since E is a finite set, there is an infinite subsequence w_{1} ≻ w_{2} ≻ … of the sequence of initial terms (7) such that p(w_{1}) = p(w_{2}) = …, say, p(w_{i}) = b for every i ≥ 1.

We claim that this is impossible. Consider the sequence z_{i} = |G| w_{i} − b for i ≥ 1. Then

(i) z_{1} ≻ z_{2} ≻ z_{3} ≻ …,

(ii) z_{i} ∈ A^{≻} for each i ≥ 1, and

(iii) z_{i} ∈ Span_{ℝ}(e_{1}, …, e_{t}) for each i ≥ 1.

(i) is obvious because w_{i} form a strictly decreasing sequence. To prove (ii), note that w_{i} ∈ A^{≻}, i.e., w_{i} ⪰ g(w_{i}) for any g ∈ G. Multiplying both sides by the positive integer |G| and subtracting b = g(b), we obtain z_{i} ⪰ g(z_{i}), as desired. To prove (iii), we only need to show that z_{i} is orthogonal to every c ∈ (ℝ^{n})^{G}; cf. Lemma 5.3(a). Indeed,

<z_{i}, c> = |G| <w_{i}, c>−<p(w_{i}), c> = |G| <w_{i}, c>−∑_{g∈G} <g(w_{i}), g(c)> = 0 .

This proves (iii).

Thus {z_{i}} is a strictly decreasing sequence in A^{≻} ∩ Span_{ℝ}(e_{1}, …, e_{t}), contradicting Proposition 5.5. This shows that the subduction algorithm will terminate, i.e., f_{1}, …, f_{r} form a SAGBI basis of k[x^{±1}]^{≻}, as claimed. □

6. Proof of Theorem 1.7

In this section we will deduce Göbel’s conjecture (Theorem 1.7) from Theorem 1.4.

Elements of H may be viewed as n × n-permutation matrices; this gives a natural inclusion H ⊂ GL_{n}(ℤ). However, since we are interested in polynomial invariants of H, we will apply Theorem 1.4 not to H itself but to the larger group G = <H, D> ⊂ GL_{n}(ℤ), where D is the subgroup of diagonal matrices in GL_{n}(ℤ). (In other words, D = {diag(ϵ_{1}, …, ϵ_{n})}, where each ϵ_{i} = ±1.) It is easy to see that G ≃ D {> \atop ◁} H is a finite group.

The idea of the proof is to relate In(k[x]^{H}) to In(k[x^{±1}]^{G}), where k[x^{±1}] = k[x_{1}^{±1}, …, x_{n}^{±1}] is the Laurent polynomial ring. To define In(k[x^{±1}]^{G}), we need to extend our term order ≻ from k[x] to k[x^{±1}]. There is a unique such extension (which, by abuse of notation, we shall continue to denote by ≻): for any a and b ∈ ℤ^{n} we define

(8) a ≻ b iff a + m(1, …, 1) ≻ b + m(1, …, 1) for some m ≫ 0.

One easily checks that this definition is independent of the choice of m, as long as a + m(1, …, 1) and b + m(1, …, 1) ∈ ℕ^{n}, and that the resulting order is a term order in k[x^{±1}] in the sense of Definition 1.2. Moreover, relative to this term order, In(k[x]^{H}) = In(k[x^{±1}]^{G}); indeed, both are equal to

{a = (a_{1}, …, a_{n}) ∈ ℤ^{n} | a_{1}, …, a_{n} ≥ 0 and h(a) ⪰ a for every h ∈ H}.

Theorem 1.4 now tells us that In(k[x]^{H}) = In(k[x^{±1}]^{G}) has a finite SAGBI basis if and only if G is a reflection group. Theorem 1.7 is thus a consequence of the following group-theoretic lemma. Lemma 6.1. Let H ⊂ S_{n} and G = D {> \atop ◁} H ⊂ GL_{n}(ℤ) be as above. Then the following conditions are equivalent:

(a) G is a reflection group,

(b) H is generated by transpositions,

(c) H = S_{n_{1}} × ⋯ × S_{n_{r}} for some partition n_{1} + ⋯ + n_{r} = n.

The equivalence (b) ⟺ (c) is a simple exercise in finite group theory; we leave it to the reader.

(b) ⟹ (a): D is clearly generated by reflections. Since a transposition in H (viewed as an element of GL_{n}(ℤ)) is a reflection, (b) says that H is also generated by reflections. Hence, so is G = <D, H>.

Our proof of the implication (a) ⟹ (b) relies on the following claim: Write g = dh, where d ∈ D and h ∈ H. If g is a reflection then h = id or h is a transposition. Indeed, since G = D {> \atop ◁} H, id = g^{2} = d(hdh^{−1})h^{2} implies (i) h^{2} = id, i.e., h is a product of, say, r disjoint transpositions, and (ii) dhdh^{−1} = id, i.e., d and h commute. It is now easy to see that the only eigenvalues of g are −1 and 1, and that −1 occurs with multiplicity ≥ r. If g is a reflection, this implies r ≤ 1, i.e., h = id or h is a transposition. This proves the claim.

Now suppose G is generated by reflections g_{1} = d_{1}h_{1}, …, g_{m} = d_{m}h_{m}, where each d_{i} ∈ D and each h_{i} ∈ H. Then H = G/D is generated by h_{1}, …, h_{m}. The claim tells us that each h_{i} = id or a transposition. Thus H is generated by transpositions. This completes the proof of Lemma 6.1 and thus of Theorem 1.7.

7. Final remarks

Remark 7.1. Suppose G ⊂ GL_{n}(ℤ) is a finite reflection group and (ℤ^{n})^{G} = (0). Then there is a canonical choice of a SAGBI basis {f_{1}, …, f_{r}} in R = k[x^{±1}]^{G} independent of the term order ≻.

Indeed, in this case the integral polyhedral cone X^{≻} has an apex at 0 (cf. Remark 5.4); thus by [4, Lemma V.3.5], In(R) = A^{≻} = X^{≻} ∩ ℤ^{n} has a unique minimal system of (semigroup) generators v_{1}, …, v_{r}. Now define

f_{i} = ∑_{g∈G} x^{g(v_{i})} ;

for i = 1, …, r. These elements form a SAGBI basis by Corollary 5.6 (or alternatively, by Proposition 5.8). To see that this SAGBI basis is independent of the term order, let ≻′ be another term order in k[x^{±1}], v_{1}′, …, v_{r}′ be a minimal set of generators for A^{≻′} = X^{≻′} ∩ ℤ^{n} and

f′_{i} = ∑_{g∈G} x^{g(v′_{i})} .

If s_{1}, …, s_{m} are the reflections in G, set H_{i} = (ℝ^{n})^{s_{i}}, as before. Since X^{≻} and X^{≻′} are both chambers for the G-invariant collection of hyperplanes H_{1}, …, H_{m}, there exists a g_{0} ∈ G such that X^{≻′} = g_{0}(X^{≻}); see [1, Lemma V.3.1.2]. Then g_{0}(v_{1}), …, g_{0}(v_{r}) is another minimal system of generators of A^{≻′}; thus, up to renumbering, v_{i}′ = g_{0}(v_{i}) for i = 1, …, r. Consequently, f_{i} = f′_{i} for every i = 1, …, r, as claimed. Remark 7.2. The arguments we used in proving Theorems 1.4 and 1.5 are quite insensitive to the base field k. Informally speaking, the action takes place in the exponents of monomials (both literally and metaphorically), and the coefficients of these monomials play only a minor role in our considerations. In fact,

(a) Theorems 1.4 and 1.7 remain true if the base field k is replaced by a (not necessarily comutative) ring. Our only requirements are that k should be nontrivial (i.e., k ≠ (0)) and should have no zero divisors (otherwise, In(R) may not be a semigroup). The proof remains the same, with one exception: if k does not have a unit element, then f = ∑ x^{g(a)} in the proof of Lemma 2.6(a) should be redefined as f = ∑ cx^{g(a)}, where c is a nonzero element of k.

(b) Theorem 1.5, Theorem 1.6 and Proposition 5.8 remain true if k is assumed to be a ring with a unit element 1 and without zero divisors, provided that we modify the definition of the subduction algorithm (as described in the Introduction) as follows: each f_{λ} is required to be monic i.e., its initial terms should have coefficient 1. (Otherwise we will have trouble defining the subduction algorithm, before we can even ask whether it terminates or not.) Corollary 5.6 remain true, if we impose this additional requirement on {f_{λ}}. The proofs remain unchanged.

We conclude this paper with the example that originally motivated Theorem 1.4. Example 7.3. Let C_{2} = {1, τ} be a group of order 2. Consider the action of G_{n} = S_{n} × C_{2} on

L_{n} = {a = (a_{1}, …, a_{n}) ∈ ℤ^{n} | a_{1} + ⋯ + a_{n} = 0} ≃ ℤ^{n−1} ,

where S_{n} acts by permuting the coordinates and C_{2} acts via τ(a) = −a. For n ≥ 3, the resulting integral representation G ⟶ GL(L_{n}) is easily seen to be faithful; thus we can think of G_{n} as a finite subgroup of GL(L_{n}) = GL_{n−1}(ℤ). This representation and the ring of multiplicative invariants R_{n} = k[L_{n}]^{G_{n}} (here k[L_{n}] = k[x_{1}^{±1}, …, x_{n−1}^{±1}]) arise in crystallography; in particular, one would like to know whether or not this ring has a SAGBI basis; cf. [2].

It is easy to see that G_{n} is generated by reflections if and only if n ≤ 4. Indeed, the reflections in G_{3} are (ij) and (ij)τ, where 1 ≤ i < j ≤ 3; these elements clearly generate G_{3}. The reflections in G_{4} are elements of the form (ij) where 1 ≤ i < j ≤ 4 and (ij)(hl)τ, where {i, j, h, l} = {1, 2, 3, 4}; these elements generate G_{4}. For n ≥ 5 the only reflections in G_{n} are transpositions in S_{n}; the subgroup they generate is S_{n}, not all of G_{n}. Thus Theorem 1.4 tells us that the semigroup A^{≻} = In(R_{n}) is not finitely generated for any n ≥ 5. The following direct proof of this fact, in the case where ≻ is the restriction of the usual lexicographic order of ℤ^{n} to L_{n}, was shown to us by J. Friedman:

Denote the j-th component of a ∈ ℤ^{n} by a[j], so that a = (a[1], …, a[n]). The semigroup of initial terms A_{n}^{≻} = In(k[L_{n}]^{G_{n}}) with respect to this order consists of elements a ∈ ℤ^{n} satisfying the following conditions:

(i) a ∈ L_{n}, i.e., a[1] + ⋯ + a[n] = 0,

(ii) a[1] ≥ ⋯ ≥ a[n], and

(iii) (a[1], …, a[n]) ⪰ (−a[n], …, −a[1]) Assume the contrary: there exists a finite set F of generators for A_{n}^{≻}. Write F = F_{0} ∪ F_{1} ∪ F_{2} ∪ …, where F_{i} consists of those f ∈ F with f[1] + f[n] = i.

Consider the element a = (t^{2} + 1, t, t, 0, …, 0, −2t − 1, −t^{2}) of A^{≻}, where t ≥ 2 is an integer parameter, to be specified later. Write a = f_{1} + ... + f_{N} as a sum of (not necessarily distinct) elements of F. Since a[1] + a[n] = 1, exactly one of the elements f_{i} (say, f_{N}) lies in F_{1}, and all others lie in F_{0}. On the other hand, for any f ∈ F_{0}, f[2] + f[n − 1] ≥ 0. Thus

−t − 1 = a[2] + a[n − 1] = (f_{1}[2] + f_{1}[n − 1]) + ⋯ + (f_{N}[2] + f_{N}[n − 1]) ≥

f_{N}[2] + f_{N}[n − 1] ≥ min_{f∈F_{1}}(f[2] + f[n − 1]) .

The last inequality cannot hold for sufficiently large t, a contradiction. Thus A^{≻} is not finitely generated for any n ≥ 5. □

Theorem 1.5 also tells us that L_{n}^{G_{n}} has a finite SAGBI basis for n = 3 and 4. Explicit SAGBI bases in these cases and some computations with them can be found in [2]. □

Acknowledgments

I would like to thank Joel Friedman for suggesting Proposition 2.4 and contributing the argument of Example 7.3, Martin Lorenz and the referee for bringing the papers [11] and [12] to my attention, and Joe Buhler, Claudio Procesi, Nicolas Thiéri and Rekha Thomas for stimulating discussions.

References

[1] N. Bourbaki, Groupes et Algébres de Lie, Hermann, 1968.

[2] J. Buhler, Z. Reichstein, Symmetric functions and the phase problem in crystallography, in preparation.

[3] D. Cox, J. Little, D. O’Shea, Using algebraic geometry. Graduate Texts in Mathematics, 185. Springer-Verlag, New York, 1998.

[4] G. Ewald, Combinatorial Convexity and Algebraic Geometry, Springer-Verlag, 1996.

[5] D. R. Farkas, Multiplicative invariants, LÉnseignement Mathématique, 30 (1984), 141 – 157.

[6] D. R. Farkas, Reflection groups and multiplicative invariants, Rocky Mountain J. Math, 16, no. 2 (1986), 215-222.

[7] M. Göbel, A constructive description of SAGBI bases for polynomial invariants of permutation groups, J. Symbolic Comput. 26 (1998), no. 3, 261–272.

[8] M. Göbel, The optimal lower bound for generators of invariant rings without finite SAGBI bases with respect to any admissible order, Discrete Math. Theor. Comput. Sci. 3 (1999), no. 2, 65–70 (electronic).

[9] M. Göbel, Rings of polynomial invariants of the alternating group have no finite SAGBI bases with respect to any admissible order, Inform. Process. Lett. 74 (2000), no. 1-2, 15–18.

[10] D. Kapur, K. Madlener, A completion procedure for computing a canonical basis for a k-subalgebra, Computers and mathematics (Cambridge, MA, 1989), 1–11, Springer, New York, 1989.

[11] M. Lorenz, Regularity of multiplicative invariants, Comm. Algebra 24 (1996), no. 3, 1051–1055.

[12] M. Lorenz, Multiplicative invariants and semigroup algebras, Algebr. Represent. Theory 4 (2001), no. 3, 293–304.

[13] L. Robbiano, M. Sweedler, Subalgebra bases, Commutative algebra (Salvador, 1988), Lecture Notes in Math., 1430 (1990), Springer, Berlin, 1990, 61-87.

[14] B. Sturmfels, Algorithms in Invariant Theory, Texts and Monographs in Symbolic Computation, Springer-Verlag, 1993.

[15] B. Sturmfels, Gröbner Bases and Convex Polytopes, University Lecture Series, vol. 8, Amer. Math. Soc., 1995.

[16] N. M. Thiéry, S. Thomassé, SAGBI bases of permutation groups and convex cones, preprint.

Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada

E-mail address: reichst@@math.ubc.ca