Computational Invariant Theory

Gregor Kemper

IWR, Universität Heidelberg, Im Neuenheimer Feld 368 69 120 Heidelberg, Germany

                     email Gregor.Kemper@iwr.uni-heidelberg.de

February 10, 1998

Introduction

In the fall of 1997 I gave a series of lectures at Queen’s University on algorithms in invariant theory of finite groups. This article is an expanded version of the material presented there. The main topic is the calculation of the invariant ring of a finite group acting on a polynomial ring by linear transformations of the indeterminates. By “calculation” I mean finding a finite system of generators for the invariant ring, and (optionally) determining structural properties of it. In this exposition particular emphasis is placed on the case that the ground field has positive characteristic dividing the group order. We call this the modular case, and it is important for several reasons. First, many theoretical questions about the structure of modular invariant rings are still open. I will address the problems which I consider the most important or fascinating in the course of the paper. Thus it is very helpful to be able to compute modular invariant rings in order to gain experience, formulate or check conjectures, and gather some insight which in fortunate cases leads to proofs. Furthermore, the computation of modular invariant ring can be very useful for the study of cohomology of finite groups (see Adem and Milgram [1]). This exposition also treats the nonmodular case (characteristic zero or coprime to the group order), where computations are much easier and the theory is for the most part settled. There are also various applications in this case, such as the solution of algebraic equations or the study of dynamical systems with symmetries (see, for example, Gatermann [11], Worfolk [26]).

This is not a research paper, and so there is no claim of originality. In fact, most of the material is covered by the papers [14,15,18]. The goal is to give a coherent exposition of what is scattered through several original papers, which I hope is readable and assumes as little knowledge as possible.

There are several implementations of the algorithms treated in this text. The most efficient of these is contained in the Magma system (see Kemper and Steel [18] and Bosma et al. [6]). There is an older implementation in Maple written by myself, which can be obtained by anonymous ftp from

the site ftp.iwr.uni-heidelberg.de under /pub/kemper/INVAR2. A further implementation in

Singular has been written by Agnes Heydtmann (email agnes@math.uni-sb.de).

We will consider the following situation: K is a field, V is a finite dimensional vector space. Let x_{1}, …, x_{n} be a basis of V. Then we write K[V] for the polynomial ring K[x_{1}, …, x_{n}] over K with the x_{i} as indeterminates. More conceptually, K[V] can be defined as the symmetric algebra of V: K[V] = S(V). Let G ≤ GL(V) be a linear group on V. The action on V can be extended to an action of G on K[V] by automorphisms of K-algebras. The invariant ring K[V]^{G} is the set of all polynomials which are invariant under the action of G:

K[V]^{G} = {f ∈ K[V] | σ(f) = f ∀σ ∈ G}.

It is immediately clear that K[V]^{G} is an algebra over K.

Example. Let K = ℝ, V = ℝ^{2} and consider the orthogonal group G = O_{2}(ℝ). Clearly f_{2} = x_{1}^{2} + x_{2}^{2} is an invariant. Now take any invariant f ∈ K[V]^{G}. Then f must be constant on all orbits under G, i.e., under all circles about the origin. Hence f must be a function of the radius. This already makes it very plausible that f can be written as a polynomial in f_{2}, which is indeed the case for any invariant f. Hence K[V]^{G} is generated by f_{2} as an algebra over K.

Now consider the group H ≤ G generated by the matrix

(\begin{matrix}0 & 1 \\ −1 & 0 \end{matrix}) .

Clearly f_{2} is an invariant under H, too, and we find additional invariants

f_{4} = x_{1}^{2}x_{2}^{2} and g_{4} = x_{1}x_{2}(x_{1}^{2} − x_{2}^{2}).

It turns out that in this example K[V]^{H} is generated by f_{2}, f_{4}, and g_{4}. We will see in the sequel how this can be seen.

In both examples finite generating systems of the invariant ring as a K-algebra were given. This is and has always been a classical goal of invariant theory. The question whether a finite system of generators always exists is known as Hilbert’s 14th problem. The general answer turns out to be “no”, as was shown by Nagata’s counter example [19]. In fact, one has to assume that G is a reductive group in order to get the invariant rings of all representations of G to be finitely generated. This result was achieved by the combined effort of Hilbert [12], Nagata [20] and Popov [22]. In particular, all finite groups are reductive, and it was Noether [21] who already in 1926 gave a nonconstructive proof that K[V]^{G} is finitely generated if G is a finite group. In the following we will always restrict ourselves to the case of finite groups G. Our goal is to give algorithms to calculate a finite system of generators. We will follow a two-step approach, which consists of the computation of primary and secondary invariants. These are dealt with in Sections 2 and 3. Section 4 is devoted to the calculation of several properties of invariant rings. But first we have to see how invariants can be calculated at all.

1 Homogeneous components

The invariant ring K[V]^{G} is not finite dimensional as a vector space over K. But we have a natural decomposition of K[V]^{G} into its homogeneous components, which are finite dimensional and thus more accessible to computations: call a polynomial f ∈ K[V] homogeneous of degree d if in all monomials of f the sum of the exponents is d. Equivalently, f is homogeneous of degree d if it lies in the d-th symmetric power S^{d}(V) of V. The homogeneous polynomials of degree d form a vector space which we denote by K[V]_{d} (= S^{d}(V)), and we have

K[V] = ⨁_{d≥0} K[V]_{d}.

The monomials of degree d are a basis of K[V]_{d}, hence dim(K[V]_{d}) = \binom{n+d−1}{n−1}, where n = dim(V). Now observe that the action of G preserves the homogeneous components. Hence we also get a decomposition of the invariant ring

K[V]^{G} = ⨁_{d≥0} K[V]_{d}^{G}

into its homogeneous components. This section is devoted to the calculation of a basis of K[V]_{d}^{G} for a given d. This is the most basic task in computational invariant theory, and often the bottle neck of the algorithms that are discussed later.

1.1 The linear algebra method.

Let H ≤ G be a subgroup of G whose invariants of degree d are known (typically, the trivial group), and take a set S(G/H) ⊆ G such that H together with S(G/H) generates G. Take the |S(G/H)|- fold direct sum of K[V], whose components are indexed by the elements of S(G/H), and consider the map

K[V]^{H} → ⨁_{σ∈S(G/H)} K[V], f ↦ (σ(f) − f)_{σ∈S(G/H)}.

The kernel of this map is K[V]^{G}. Moreover, the map is K-linear (in fact it is a homomorphism of modules over K[V]^{G}), and it preserves the grading. Restriction to the degree-d components yields a linear map K[V]_{d}^{H} → K[V]_{d}^{|S(G/H)|} whose kernel is K[V]_{d}^{G}. This mapping is explicitly given, so its kernel can be effectively calculated by solving a system of linear equations over K. In the case H = 1, the number of unknowns in this system is \binom{n+d−1}{n−1}, and the number of equations is |S(G/H)| · \binom{n+d−1}{n−1}. This can become enormous for large values of n and d.

1.2 The Reynolds operator.

A further method to calculate the homogeneous component K[V]_{d}^{G} is by means of the Reynolds operator, which is only available in the non-modular case. More generally, let H ≤ G be a subgroup such that the index [G : H] is not divisible by the characteristic p of K. Then the relative Reynolds operator is defined as

π_{H}^{G}: K[V]^{H} → K[V]^{G}, f ↦ \frac{1}{[G : H]} ∑_{σ∈G/H} σ(f),

where G/H denotes a set of left coset representatives of H in G. This is independent of the choice of the coset representatives, and it is easily checked that π_{H}^{G} is a projection of modules over K[V]^{G}. In particular, the images under π_{H}^{G} of a basis of K[V]_{d}^{H} generate the desired vector space K[V]_{d}^{G}. It is again a problem of linear algebra to select a basis of K[V]_{d}^{G} from a generating set. In the nonmodular case there is a choice between using the Reynolds operator or the linear algebra method to calculate homogeneous invariants. In Kemper and Steel [18], the authors analyzed the complexities of both approaches. The general tendency is that the Reynolds operator performs better for small |G| and large d.

2 Homogeneous systems of parameters

The first strategic goal in the calculation of an invariant ring is the construction of a homogeneous system of parameters. This is best treated in the context of graded algebras. So suppose that R is a finitely generated graded algebra over K, i.e., R is a finitely generated commutative associative K-algebra with unity with a direct sum decomposition

R = ⨁_{d≥0} R_{d}

such that R_{i} · R_{j} ⊆ R_{i+j}, and moreover R_{0} = K. As explained in the previous section, invariant rings are graded algebras in this sense, and in fact the theory of graded algebras received much of its impetus from the study of invariant rings. It probably goes without saying that a nonzero element f ∈ R_{d} is called homogeneous of degree d, written as deg(f) = d. Moreover, we write R_{+} = ⊕_{d>0}R_{d} for the unique homogeneous maximal ideal of R. We will also consider graded R-modules, i.e., modules M over R with a direct sum decomposition

M = ⨁_{d≥N} M_{d}

with N ∈ ℤ such that R_{i}M_{j} ⊆ M_{i+j}. The following version of Nakayama’s lemma is of crucial importance.

Lemma 2.1. Let R be a graded K-algebra and M a graded R-module. Then for a subset S ⊆ M of homogeneous elements the following two conditions are equivalent:

(a) S generates M as an R-module.

(b) S generates M/R_{+}M as a vector space over K. Here R_{+}M is the submodule of M generated by the elements a · g with a ∈ R_{+}.

In particular, a generating set S for M is of minimal cardinality if no proper subset of S generates M.

Proof. Clearly if S generates M, it also generates M/R_{+}M as a K-vector space.

Now suppose that S generates M/R_{+}M and let g ∈ M be homogeneous of some degree d. Then by assumption

g = ∑_{i=1}^{m} α_{i}g_{i} + ∑_{j=1}^{r} a_{j}h_{j}

with g_{1}, …, g_{m} ∈ S, α_{i} ∈ K, a_{j} ∈ R_{+} and h_{j} ∈ M. By multiplying out homogeneous parts and omitting those summands which are not of degree d, we can assume that the a_{j} and h_{j} are homogeneous with deg(a_{j}h_{j}) = d. Hence deg(h_{j}) < d and h_{j} lies in the submodule spanned by S by induction on d, which works since {N, N + 1, N + 2, … } is a well-ordered set. Hence g lies in the module spanned by S.

The last remark on minimality follows from the corresponding property of vector spaces.

We write dim(R) for the Krull dimension of R.

Definition 2.2. Let n = dim(R). A set {f_{1}, …, f_{n}} ⊆ R_{+} of homogeneous elements of positive degree is called a homogeneous system of parameters if R is finitely generated as a module over the subalgebra A = K[f_{1}, …, f_{n}] generated by the f_{i}.

If R = K[V]^{G} is an invariant ring, the members of a homogeneous system of parameters are also called primary invariants.

Note that dim(R) is the minimal number n such that f_{1}, …, f_{n} ∈ R can exist with the property that R is a finitely generated K[f_{1}, …, f_{n}]-module, since this implies dim(R) = dim(K[f_{1}, …, f_{n}]) ≤ n. (A finite extension of a ring has the same dimension, see Eisenbud [9, Proposition 9.2].) We have equality if and only if f_{1}, …, f_{n} are algebraically independent over K. This shows that the elements of a homogeneous system of parameters are always algebraically independent, so A = K[f_{1}, …, f_{n}] is isomorphic to a polynomial ring. Using Lemma 2.1, we get the following geometric characterization, which is the key to all methods to construct homogeneous systems of parameters.

Proposition 2.3. Let f_{1}, …, f_{n} ∈ R_{+} be homogeneous elements with n = dim(R). Then the following statements are equivalent:

(a) {f_{1}, …, f_{n}} is a homogeneous system of parameters.

(b) dim(R/(f_{1}, …, f_{n})) = 0.

(c) dim(R/(f_{1}, …, f_{i})) = n − i for i = 1, …, n.

If R = K[V]^{G} is the invariant ring of a finite group, then the above statements are equivalent to

(d) VK̄(f_{1}, …, f_{n}) = {0}, where VK̄(f_{1}, …, f_{n}) is defined as {v ∈ K̄ ⊗_{K} V | f_{i}(v) = 0 for i = 1, …, n} and K̄ is an algebraic closure of K.

We will try to give a proof here which uses only some very basic facts from commutative algebra. It is intertwined with the proof of the following:

Theorem 2.4 (Noether Normalization). If R is a finitely generated graded algebra, then a homogeneous system of parameters exists.

Proof of Proposition 2.3 and Theorem 2.4. By Lemma 2.1, {f_{1}, …, f_{n}} is a homogeneous system of parameters if and only if the quotient algebra R′ := R/(f_{1}, …, f_{n}) has finite dimension as a K-vector space. This is equivalent to the condition that R′_{d} = 0 for d sufficiently large, or that R′_{+} is the radical ideal of the zero-ideal. This shows the equivalence of (a) and (b) in Proposition 2.3.

We prove Theorem 2.4 by induction on n = dim(R). If n = 0, then by the above the empty set is a homogeneous system of parameters. Suppose that n > 0 and let P_{1}, …, P_{r} be the associated prime ideals of the zero-ideal with dim(R/P_{i}) = n. By the prime avoidance lemma (see Eisenbud [9, Lemma 3.3]), there exists a homogeneous element f_{1} ∈ R_{+} with f_{1} ∉ P_{i} for all i, and it follows dim(R/(f_{1})) < n. Now the theorem follows by induction.

Clearly the statement (c) from Proposition 2.3 is stronger than (b), so we must show that it is also implied by (a) and (b). If fact, if {f_{1}, …, f_{n}} is a homogeneous system of parameters, then R_{i} := R/(f_{1}, …, f_{i}) is finitely generated as a module over K[\overline{f_{i+1}}, …, \overline{f_{n}}] where the bars denote the classes modulo (f_{1}, …, f_{i}), hence m := dim R_{i} ≤ n − i by the remark after Definition 2.2. On the other hand, by Theorem 2.4 there exists a homogeneous system of parameters \{\overline{g_{1}}, …, \overline{g}_{m}\} in R_{i}, hence R is finitely generated over K[f_{1}, …, f_{i}, g_{1}, …, g_{m}] and therefore i + m ≥ n. With the above we obtain dim(R_{i}) = n − i.

To prove the equivalence of (d), we first note that K[V] is finitely generated as a module over K[V]^{G}. In fact, f ∈ K[V] is a zero of the monic polynomial

∏_{σ∈G} (X − σ(f)) ∈ K[V]^{G}[X].

It follows that {f_{1}, …, f_{n}} ⊂ K[V]_{+}^{G} is a homogeneous system of parameters for K[V]^{G} if and only if it is a homogeneous system of parameters fro K[V], which is equivalent to dim(K[V]/(f_{1}, …, f_{n})) = 0, or |VK̄(f_{1}, …, f_{n})| < ∞. The last condition is equivalent to (d), since if VK̄(f_{1}, …, f_{n}) contains a nonzero point, it also contains the line joining this point and 0 by homogeneity.

We can see now that in the example from the Introduction the invariants f_{2} and f_{4} form a homogeneous system of parameters. We note the following as a by-product of the above proof:

Proposition 2.5. The polynomial ring K[V] is finitely generated as a module over K[V]^{G}. In particular,

dim(K[V]^{G}) = dim_{K}(V).

2.1 Dade’s algorithm.

It is important to note that there are many choices of a homogeneous system of parameters. For example, one can substitute any member of a homogeneous system of parameters by a power of itself. As we will see in the next section, it is crucial for the efficiency of subsequent calculations that a homogeneous system of parameters is chosen whose degrees are as small as possible. In particular, one usually wants to minimize the product ∏_{i=1}^{n} deg(f_{i}) (see Propositions 3.1 and 4.1). An algorithm for the construction of a homogeneous system of parameters for K[V]^{G} was given by Dade (see Stanley [25]). It is based on the following observation.

Proposition 2.6. Let n = dim(V) and suppose that l_{1}, …, l_{n} ∈ V^{∗} \ {0} are linear forms such that

l_{i} ∉ ⋃_{σ_{1},... ,σ_{i−1}∈G} ⟨σ_{1}(l_{1}), …, σ_{i−1}(l_{i−1})⟩_{K−vector space} for i = 2, …, n.

Let f_{i} be the product over all l in the G-orbit of l_{i}, then {f_{1}, …, f_{n}} is a homogeneous system of parameters of K[V]^{G}.

Proof. We show that condition (d) from Proposition 2.3 is satisfied. Take v ∈ VK̄(f_{1}, …, f_{n}). Then (σ_{i}(l_{i})) (v) = 0 for some σ_{i} ∈ G. But the assumption says that σ_{1}(l_{1}), …, σ_{n}(l_{n}) forms a basis of V^{∗}, hence v = 0.

It is clear how Proposition 2.6 can be turned into an algorithm, provided that the ground field K is large enough to make the avoidance of a union of at most |G|^{n−1} proper subspaces possible. This algorithm is simple and quick, but the main drawback is that it tends to produce invariants whose degrees are of the same order of magnitude as |G|. For some experimental data on this see Kemper [15]. In that paper, various other approaches for the calculation of a homogeneous system of parameters are also explored, with the outcome that a computable criterion to decide whether a given degree vector d_{1}, …, d_{n} gives the degrees of some homogeneous system of parameters is required in order to obtain an algorithm which always produces an optimal homogeneous system of parameters.

2.2 An algorithm for optimal homogeneous systems of parameters.

The following provides a criterion for the existence of a homogeneous systems of parameters of given degrees.

Theorem 2.7 (Kemper [15]). Let R be a graded algebra of Krull dimension n over an infinite field K and let d_{1}, …, d_{k} ∈ ℕ = {1, 2, 3, … }. Then the following are equivalent:

(a) There exist homogeneous f_{1}, …, f_{k} ∈ R with deg(f_{i}) = d_{i} such that

dim(R/(f_{1}, …, f_{k})) = n − k.

(b) For each subset I ⊆ {1, …, k} the inequality

dim (R/(R_{d_{i}} | i ∈ I)) ≤ n − |I|

holds. Here (R_{d_{i}} | i ∈ I) denotes the ideal in R generated by the union of all homogeneous components R_{d_{i}} with i ∈ I.

The implication “(a) ⇒ (b)” also holds if K is a finite field.

Proof. First we prove that (a) implies (b). In fact, if dim(R/(f_{1}, …, f_{k})) = n − k, then f_{1}, …, f_{k} can be extended to a homogeneous system of parameters by Theorem 2.4 and Proposition 2.3, hence Proposition 2.3(c) implies dim(R/(f_{i} | i ∈ I)) = n − |I| for any I ⊆ {1, …, k}. But the ideal (R_{d_{i}} | i ∈ I) is bigger than (f_{i} | i ∈ I), and the inequality in (b) follows.

Now we prove the converse by induction on k. For k = 0, (a) is clearly satisfied. Assume k > 0 and write d_{R}(I) = dim (R/(R_{d_{i}} | i ∈ I)) for I ⊆ {1, …, k}. Also write Ass_{min}(I) for the set of all associated prime ideals P ⊆ R of (R_{d_{i}} | i ∈ I) with dim(R/P) = n − |I|. Then Ass_{min}(I) is a (possibly empty) finite set. For I ⊆ {1, …, k − 1} and P ∈ Ass_{min}(I) we have R_{d_{k}} ⊈ P, since otherwise (R_{d_{i}} | i ∈ I ∪ {k}) ⊆ P, so

d_{R}(I ∪ {k}) ≥ dim(R/P) = n − |I| > n − |I ∪ {k}|

in contradiction to (b). Therefore R_{d_{k}} ∩ P is a proper subspace of R_{d_{k}}. Hence by the infinity of K there exists f_{k} ∈ R_{d_{k}} such that for all I ⊆ {1, …, k − 1} and all P ∈ Ass_{min}(I) we have f_{k} ∉ P. With R′ := R/(f_{k}), this implies that d_{R′}(I) ≤ n − |I| − 1. In particular, dim(R′) = n − 1 (take I = ∅ and observe that f_{k} can be extended to a homogeneous system of parameters), hence the conditions in (b) hold for R′ and k′ = k − 1 and the proof is complete by induction.

The purpose of Theorem 2.7 was to obtain an effective criterion for d_{1}, …, d_{n} to appear as the degrees of a homogeneous system of parameters, so now we explain how the conditions from (b) can be checked algorithmically in the case that R = K[V]^{G}. First, the ideals (K[V]_{d_{i}}^{G} | i ∈ I) ⊆ K[V]^{G} for I ⊆ {1, …, n} can be calculated since K-bases for the subspaces K[V]_{d_{i}}^{G} can be obtained by the methods of Section 1. Moreover, Proposition 2.5 implies that the dimension of an ideal I ⊆ K[V]^{G} equals the dimension of the ideal (I) ⊆ K[V] generated by I in K[V]. So we need an algorithm to compute dimensions of ideals I ⊂ K[V] = K[x_{1}, …, x_{n}] in a polynomial ring. Such an algorithm is provided by Gröbner bases. Indeed, let B be a Gröbner basis of I with respect to any term order which refines the order given by the total degree. Then Becker and Weispfenning [4, Lemma 9.23 and Theorem 9.27] give a simple combinatorial procedure to calculate the dimension of K[x_{1}, …, x_{n}]/I: it is the maximal cardinality of a subset I ⊆ {x_{1}, …, x_{n}} such that every lead monomial of a polynomial from B involves a variable x_{i} which is not in I.

We obtain the following rough idea of an algorithm for the construction of a optimal homogeneous system of parameters.

(1) Loop through all degree vectors (d_{1}, …, d_{n}) ∈ ℕ^{n}, ordered by rising values of ∏_{i=1}^{n} d_{i}, until one is found which satisfies the conditions in (b) of Theorem 2.7.

(2) Loop through all f_{1} ∈ R_{d_{1}} until f_{1} is found such that (d_{2}, …, d_{n}) satisfies the conditions in (b) of Theorem 2.7, with R replaced by R/(f_{1}).

(3) By recursion, obtain f_{2}, …, f_{n} of degrees d_{2}, …, d_{n} such that f_{1}, …, f_{n} is the desired homogeneous system of parameters.

(4) If the loop through R_{d_{i}} fails at some level in the recursion (which by Theorem 2.7 can only happen if K is finite), go back into the loop (1) and choose a new degree vector (d_{1}, …, d_{n}).

To make the algorithm more precise, one has to specify a procedure to enumerate the (possibly infinite) vector space R_{d_{i}} in such a way that for a nonzero polynomial f on R_{d_{i}} a vector is found after finitely many steps where f takes a nonzero value. For details, we refer to [15] and remark here that this is not a problem either in theoretical or in practical terms. While it is clear that the above algorithm terminates and produces a homogeneous system of parameters with a minimal degree product, it still appears quite appalling, since it involves up to 2^{n} Gröbner basis computations for the tests of the conditions from (b) of Theorem 2.7 for each degree vector, and a further minimum of 2^{n} Gröbner basis computations for the recursive construction of the f_{i}.

However, with a few modifications the algorithm becomes quite feasible. Most importantly, some strong and easily testable restrictions are applied on degree vectors before they are passed to the recursive loops. I will discuss such restrictions below (Section 2.3). Furthermore, in the recursive loops as few of the conditions from (b) of Theorem 2.7 as possible are applied. Thus a refined algorithm is obtained which is given in detail in [15]. I sometimes compare this refined algorithm to an assembly line which produces a package containing polynomials which eventually will become a homogeneous system of parameters. There are n workers and a foreman, and at the start the foreman chooses a degree vector (d_{1}, …, d_{n}) which satisfies the applicable restrictions. He hands a barrel containing the elements of R_{d_{i}} to the i-th worker, and the assembly starts with each worker tossing a random element f_{i} from his barrel into the package and shoving it down the line. Only the last worker performs the appropriate dimension test, and if it fails, he pushes the package back to his predecessor. Then each worker applies just enough conditions from (b) of Theorem 2.7 to find out whether the failure was his fault (i.e., the package could have traveled further down the line with a better choice of f_{i}), and in that case puts in a better f_{i}. Otherwise, he pushes the package back up. If the package travels back to the first worker and he decides that the failure was not due to him (namely, some condition from (b) of Theorem 2.7 on the degrees (d_{1}, …, d_{n}) was false), then the foreman has to choose new degrees d_{i}.

The justification for such an approach is that the subset of R_{d_{1}} × ⋯ × R_{d_{n}} consisting of those (f_{1}, …, f_{n}) which form a homogeneous system of parameters is Zariski-open, and that the restrictions on (d_{1}, …, d_{n}) yield a good chance that it is non-empty. Therefore the refined algorithm probabilistically only requires one Gröbner basis computation. The refined algorithm is implemented in Magma, and experience shows that it works quite well.

2.3 Hilbert series and restrictions on degree vectors.

Since R is assumed to be a finitely generated graded algebra, the K-dimension of each homogeneous component R_{d} is finite. The Hilbert series of R is the formal power series

H(R, t) = ∑_{d≥0} dim_{K}(R_{d}) · t^{d} ∈ ℂ[[t]].

Let f_{1}, …, f_{n} be a homogeneous system of parameters of degrees d_{1}, …, d_{n}. We can calculate the Hilbert series of A = K[f_{1}, …, f_{n}] by using the fact that A is isomorphic to a polynomial ring, in other words, A ≅ K[f_{1}] ⊗_{K} ⋯ ⊗_{K} K[f_{n}], and the fact that the Hilbert series is multiplicative with respect to tensor products. The result is

H(A, t) = \frac{1}{(1 − t^{d_{1}}) ⋯ (1 − t^{d_{n}})}.  (2.1)

By looking at a free resolution of R as a module over A (see Section 4.3), we conclude that the Hilbert series of R can then be written as

H(R, t) = \frac{f(t)}{(1 − t^{d_{1}}) ⋯ (1 − t^{d_{n}})} with f(t) ∈ ℤ[t].  (2.2)

Multiplying this by (1 − t)^{n} and substituting t = 1 yields the value f(1)/(d_{1} ⋯ d_{n}), hence H(R, t) has a pole at t = 1 of order at most n. Therefore we have a Laurent expansion

H(R, t) = \frac{a_{0}}{(1 − t)^{n}} + \frac{a_{1}}{(1 − t)^{n−1}} + …

about t = 1, with a_{0} = f(1)/(d_{1} ⋯ d_{n}). Since H(R, t) is coefficient-wise bounded from below by H(A, t) = ∏_{i=1}^{n}(1 − t^{d_{i}})^{−1}, the coefficient a_{0} must be nonzero. It is often called the degree of R, and written as deg(R) = a_{0}. Since f(1) is an integer, we have seen that the product d_{1} ⋯ d_{n} is a multiple of 1/ deg(R). The degree of R is often known even if the Hilbert series is not. In the case that R is the invariant ring K[V]^{G}, we have deg(K[V]^{G}) = 1/|G| by Smith [24, Theorem 5.5.3]. We have obtained:

Proposition 2.8. If d_{1}, …, d_{n} are the degrees of a homogeneous system of parameters of K[V]^{G}, then the product d_{1} ⋯ d_{n} is divisible by |G|.

This poses a restriction on the degrees d_{1}, …, d_{n} which is always applicable. A stronger restriction is obtained by using Equation (2.2) directly in cases where the Hilbert series is known. Indeed, picking the smallest d_{i} such that H(R, t) · ∏_{i=1}^{n}(1 − t^{d_{i}}) is a polynomial with integral coefficients often yields the actual degrees of a homogeneous system of parameters. In the non-modular case, one even knows that the coefficients of f(t) are non-negative (see Equation (3.1) on page 10). Now if R = K[V]^{G} and the characteristic of K is zero, then the Hilbert series can be calculated without touching a single invariant by Molien’s marvelous formula

H(K[V]^{G}, t) = \frac{1}{|G|} ∑_{σ∈G} \frac{1}{det(1 − tσ)}.  (2.3)

Observe that this formula is even nicer than it looks at a first glance, since the expression det(1−tσ) only depends on the conjugacy class of σ in G (even in GL(V)). In fact, Molien’s formula can be evaluated from the knowledge of the character of the representation and the power maps of G alone. It is now time to look at an example.

Example 2.9.

(a) We consider the permutation group G of order 4 generated by (1, 2)(3, 4) and (1, 4)(2, 3) and its invariants over K = ℚ. Molien’s formula yields

H(K[V]^{G}, t) = \frac{1}{4} (\frac{1}{(1 − t)^{4}} + \frac{3}{(1 − t^{2})^{2}} ) = \frac{t^{2} − t + 1}{(1 − t)^{2}(1 − t^{2})^{2}} = \frac{1 + t^{3}}{(1 − t)(1 − t^{2})^{3}} ,

so (1, 2, 2, 2) is the smallest possible degree vector for primary invariants. Indeed, we find

f_{1} = x_{1} + x_{2} + x_{3} + x_{4},  f_{2} = (x_{1} − x_{2} + x_{3} − x_{4})^{2},
f_{3} = (x_{1} − x_{2} − x_{3} + x_{4})^{2}, f_{4} = (x_{1} + x_{2} − x_{3} − x_{4})^{2}.

(b) Now take the abelian group G of order 8 generated by the matrices

(\begin{matrix}1 \\ & 1 \\ & & i \end{matrix}) and (\begin{matrix}−1 \\ & −1 \\ & & 1 \end{matrix}) ∈ GL_{3}(ℂ).

This is an example of Stanley (see Sloane [23]). Molien’s formula yields

H(K[V]^{G}, t) = \frac{1}{(1 − t^{2})^{3}} ,

so the degree vector (d_{1}, d_{2}, d_{3}) = (2, 2, 2) meets the above restrictions and is minimal with that property. But K[V]_{2}^{G} is generated by x_{1}^{2}, x_{1}x_{2} and x_{2}^{2}, so we obtain the Krull dimension dim(K[V]^{G}/(K[V]_{2}^{G})) = 1. But the condition in Theorem 2.7(b) for I = {1, 2, 3} is dim(K[V]^{G}/(K[V]_{2}^{G})) ≤ 3 − |I| = 0, hence there are no primary invariants of degrees (2, 2, 2). The degree vector with the second-lowest product is (d_{1}, d_{2}, d_{3}) = (2, 2, 4), and here the algorithm readily finds primary invariants

f_{1} = x_{1}^{2}, f_{2} = x_{2}^{2}, f_{3} = x_{3}^{4}.

As we have seen here and will see in the sequel, the knowledge of the Hilbert series is extremely helpful, so we ask for generalizations of Molien’s formula. In the non-modular case (char(K) does not divide |G|), Molien’s formula still holds, but we have to form the determinants in Equation (2.3) by Brauer-lifting the eigenvalues of σ ∈ G to complex roots of unity. Moreover, if G acts as a permutation group on a basis of V, we can use Molien’s formula by “pretending” that the representation is in characteristic 0. A common generalization is the case where V is a trivial source module. For details, we refer to Kemper [17]. In that paper, the so-called extended Hilbert series H̃(K[V], G, t) is also discussed. This is the formal power series whose coefficients are not the dimensions of K[V]_{d}^{G} but the multiplicities of the trivial module K as a composition factor of K[V]_{d}. It is shown how H̃(K[V], G, t) can be calculated from the knowledge of the Brauer character table of G, and that Equation (2.2) holds for H̃(K[V], G, t) as well. Thus we get a similar restriction on the degrees of primary invariants in the modular case as well.

A further restriction which does not originate from the Hilbert series and is applicable in the general case of a finitely generated graded algebra R is the following. Suppose that d_{1}, …, d_{n} are the degrees of a homogeneous system of parameters f_{1}, …, f_{n}, with d_{1} ≤ … ≤ d_{n}. For d ∈ ℕ let J_{d} be the ideal in R generated by all components R_{i} with 1 ≤ i ≤ d. Then

dim(R/J_{d_{i}}) ≤ dim(R/(f_{1}, …, f_{i})) = n − i,

hence

d_{i} ≥ min{d | dim(R/J_{d}) ≤ n − i}.  (2.4)

This provides lower bounds for the degrees d_{i}, which in many cases turn out to be sharp. We will look at an example in Section 5.

3 Secondary invariants

In this section we assume that primary invariants f_{1}, …, f_{n} ∈ K[V]^{G} have been constructed, so K[V]^{G} is generated by homogeneous invariants g_{1}, …, g_{m} as a module over A = K[f_{1}, …, f_{n}]. Such generators g_{i} will be called secondary invariants. Together with the primary invariants, the g_{i} generate K[V]^{G} as an algebra over K. It should be emphasized that neither primary nor secondary invariants are uniquely determined, and that being a primary or a secondary invariant is not an intrinsic property of an invariant. These notions merely describe the role of some invariants in a special choice of a generating system. This section is devoted to the task of finding secondary invariants. Looking for homogeneous generators of K[V]^{G} as a module over A is equivalent to looking for generators of K[V]^{G}/A_{+}K[V]^{G} as a vector space over K (Lemma 2.1). It follows that a system of secondary invariants which is minimal in the sense that no generator can be omitted is also minimal in the sense that it has minimal cardinality, and moreover the degrees of such a system is uniquely determined. We have entirely different algorithms for the modular and non-modular case.

3.1 The non-modular case

We assume that the characteristic of K is not a divisor of the group order |G|. As we shall see, this has several beneficial effects on the efficiency of our algorithms. First, the invariant ring is always Cohen-Macaulay, i.e., it is free as a module over A = K[f_{1}, …, f_{n}] (see Hochster and Eagon [13]). This property is independent of the choice of the homogeneous system of parameters. From the above remark, it follows that any system g_{1}, …, g_{m} of secondary invariants from which none can be omitted is a system of free generators. Let e_{1}, …, e_{m} be the degrees of the g_{i}. Then it follows from the additivity of the Hilbert series with respect to direct sums and from Equation (2.1) that

H(K[V]^{G}, t) = \frac{t^{e_{1}} + ⋯ + t^{e_{m}}}{(1 − t^{d_{1}}) ⋯ (1 − t^{d_{n}})},  (3.1)

where as usual d_{i} = deg(f_{i}). Furthermore, we can easily calculate the Hilbert series by Molien’s formula (2.3) (with a possible Brauer-lift). Thus comparing Equations (3.1) and (2.3) yields the complete information about the degrees of the secondary invariants! Also, comparing (3.1) and (2.2) shows that f(1) = m, hence 1/|G| = deg(K[V]^{G}) = m/(d_{1} ⋯ d_{n}). We have proved:

Proposition 3.1. If K[V]^{G} is Cohen-Macaulay, then the (minimal) number of secondary invariants is ∏_{i=1}^{n} deg(f_{i})/|G|.

In order to find the g_{i} most efficiently, we use Lemma 2.1 again. Let g_{1}, …, g_{m} ∈ K[V]^{G} be homogeneous invariants, with m = ∏_{i=1}^{n} d_{i}/|G|. Then the g_{i} are secondary invariants if and only if they generate K[V]^{G}/A_{+}K[V]^{G} as a vector space over K. Since the number of g_{i} is correct, this is equivalent to the condition that the g_{i} are linearly independent modulo A_{+}K[V]^{G}. A_{+}K[V]^{G} is the ideal in K[V]^{G} generated by f_{1}, …, f_{n}, but one cannot calculate with an ideal in K[V]^{G} before K[V]^{G} itself is known. To circumvent this problem, consider the map

K[V]^{G} → K[V]/(f_{1}, …, f_{n}), f ↦ f + (f_{1}, …, f_{n}),

where (f_{1}, …, f_{n}) is now an ideal in the polynomial ring K[V]. Clearly A_{+}K[V]^{G} lies in the kernel. Conversely, an element f in the kernel has the form f = h_{1}f_{1} + ⋯ + h_{n}f_{n}, and applying the Reynolds operator π^{G} yields f = π^{G}(f) = π^{G}(h_{1})f_{1} + ⋯ + π^{G}(h_{n})f_{n} ∈ A_{+}K[V]^{G}. Therefore we have an embedding

K[V]^{G}/A_{+}K[V]^{G} ↪ K[V]/(f_{1}, …, f_{n}),

and conclude that g_{1}, …, g_{m} are secondary invariants if and only if they are linearly independent modulo the ideal I := (f_{1}, …, f_{n}) in K[V]. Now let B be a Gröbner basis of I with respect to any term order, and denote the normal form with respect to B by N_{B}. Such a Gröbner basis has already been calculated in the process of finding the primary invariants f_{i}, so there is no extra cost involved. Then for α_{1}, …, α_{m} ∈ K we have

α_{1}g_{1} + ⋯ + α_{m}g_{m} ∈ I ⟺ α_{1}N_{B}(g_{1}) + ⋯ + α_{m}N_{B}(g_{m}) = 0,

so all we have to do is check the linear independence of the normal forms of the g_{i}.

We arrive at the following algorithm:

(1) Let B be a Gröbner basis of the ideal (f_{1}, …, f_{n}) ⊆ K[V] generated by the primary invariants. (B was already calculated when the f_{i} were constructed.)

(2) Calculate the degrees e_{1}, …, e_{m} by using Molien’s formula (2.3) and comparing to (3.1).

(3) For i = 1, …, m perform the following two steps:

(4) Calculate a basis of the homogeneous component K[V]_{e_{i}}^{G} by using the methods from Section 1.

(5) Select an element g_{i} from this basis such that the normal form N_{B}(g_{i}) lies outside the K-vector space generated by the polynomials N_{B}(g_{1}), …, N_{B}(g_{i−1}).

(6) The invariants g_{1}, …, g_{m} are secondary invariants.

One further optimization can be achieved by trying to use products of secondary invariants of smaller degrees as new secondary invariants. This is very often successful and has two benefits: it can save the calculation of homogeneous components K[V]_{e_{i}}^{G} for some large e_{i}, and it produces a minimal system of generators of K[V]^{G} as an algebra over A = K[f_{1}, …, f_{n}] as a by-product.

Example 3.2.

(a) We can now finish the computation of the invariant ring from Example 2.9(a). From the Hilbert series we see that the secondary invariants are of degrees 1 and 3. Using the above algorithm yields secondary invariants

g_{1} = 1, g_{2} = x_{1}^{3} + x_{2}^{3} + x_{3}^{3} + x_{4}^{3}.

(b) In Aslaksen et al. [2], the authors considered the permutation representation on 6 symbols of the symmetric group G = S_{4} given by (1, 4, 6, 3)(2, 5) and (2, 4)(3, 5). The ground field is K = ℚ. Molien’s formula yields

H(K[V]^{G}, t) = \frac{1 + t^{3} + t^{4} + t^{5} + t^{6} + t^{9}}{(1 − t)(1 − t^{2})^{2}(1 − t^{3})^{2}(1 − t^{4})}.

Indeed, we find primary invariants of degrees 1,2,2,3,3,4. As secondary invariants we obtain

1, g_{3}, g_{4}, g_{5}, g_{3}^{2}, g_{4}g_{5},

where each g_{i} has degree i. Note that we only had to compute invariants of degrees up to 5. The complete computation takes about one second in Magma on a Sun workstation, and confirms the results from [2].

(c) A three-dimensional representation of the group G = A_{5} over K = ℝ is given by

(1, 2, 4) ↦ (\begin{matrix}1 & (1 + \sqrt{5})/2 & 0 \\ 0 & 0 & 1 \\ 0 & −1 & −1 \end{matrix}) , (1, 2, 3, 4, 5) ↦ (\begin{matrix}−(1 + \sqrt{5})/2 & −(1 + \sqrt{5})/2 & 0 \\ 0 & 0 & −1 \\ (1 + \sqrt{5})/2 & 1 & 1 \end{matrix}) .

The Hilbert series is

H(K[V]^{G}, t) = \frac{1 + t^{15}}{(1 − t^{2})(1 − t^{6})(1 − t^{10})},

and Magma finds primary invariants of degrees 2,6,10 and secondary invariants of degrees 0 and 15 in about half a second.

3.2 The modular case

Almost everything that we used in the non-modular case is missing in the modular case: the Cohen-Macaulay property fails in general, there is no Molien’s formula and no Reynolds operator. Neither is there any a priori bound known on the degrees of secondary invariants. In that case, we have a completely different approach to the calculation of secondary invariants which is nevertheless very straightforward.

First, choose a subgroup H ≤ G with char(K) ∤ |H| (for example, the trivial group). Then use the algorithm from Section 3.1 to calculate (a minimal set of) secondary invariants h_{1}, …, h_{r} ∈ K[V]^{H} with respect to the primary invariants f_{1}, …, f_{n} that were chosen for G. Since K[V]^{H} is Cohen-Macaulay, the h_{i} define an isomorphism A^{r} → K[V]^{H} between a free module of rank r over A = K[f_{1}, …, f_{n}] and the invariant ring of H. If we assign the degrees of the h_{i} to the free generators of A^{r}, this isomorphism becomes degree-preserving. Now take a set S(G/H) ⊆ G which generates G together with H, and consider the map

K[V]^{H} → ⨁_{σ∈S(G/H)} K[V], f ↦ (σ(f) − f)_{σ∈S(G/H)},

whose kernel is K[V]^{G} (see Section 1). Observe that this map is a homomorphism of A-modules. The polynomial ring is Cohen-Macaulay (take {x_{1}, …, x_{n}} as a homogeneous system of parameters), hence it is a free module over A whose rank is ∏_{i=1}^{n} deg(f_{i}) by Proposition 3.1. Hence ⊕_{σ∈S(G/H)}K[V] ≅ A^{k} with k = |S(G/H)| · ∏_{i=1}^{n} deg(f_{i}) (often an enormous number). We obtain the following commutative diagram with exact rows, where the map A^{r} → A^{k} is defined by the commutativity and M is its kernel.

\begin{aligned}0 & ⟶ & K[V]^{G} & ⟶ & K[V]^{H} & ⟶ & ⨁_{σ∈S(G/H)} K[V] \\ & & ↑≀ & & ↑≀ & & ↑≀ \\ 0 & ⟶ & M & ⟶ & A^{r} & ⟶ & A^{k} \end{aligned}  (3.2)

Observe that each map in the diagram is a degree-preserving homomorphism of graded A-modules.

Suppose we can calculate generators for the module M. Then we will obtain secondary invariants as the images of these generators under the map A^{r} → K[V]^{H}, which is given by the secondary invariants h_{i} of H. Now A = K[f_{1}, …, f_{n}] is isomorphic to a polynomial algebra, and A^{r} → A^{k} is a homomorphism of free modules over A. But there are standard techniques (involving Gröbner bases) to calculate kernels of such maps. We will give a brief account of how these techniques work, but before doing so let us summarize the algorithm for the computation of secondary invariants in the modular case.

(1) Choose a subgroup H ≤ G with char(K) ∤ |G| and calculate secondary invariants h_{1}, …, h_{r} ∈ K[V]^{H} for H with respect to the primary invariants f_{1}, …, f_{n} that were chosen for G. The h_{i} define a map A^{r} → K[V]^{H}, where as usual A = K[f_{1}, …, f_{n}].

(2) Calculate generators for K[V] as an A-module. These give a map A^{k} → ⊕_{σ∈S(G/H)}K[V], where S(G/H) ⊆ G together with H generates G.

(3) Calculate the preimage under the map A^{k} → ⊕_{σ∈S(G/H)}K[V] of each (σ(h_{i}) − h_{i})_{σ∈S(G/H)} (i = 1, …, r). This is done by writing down a general element of A^{k} of degree equal to deg(h_{i}) with unknown coefficients, mapping it into ⊕_{σ∈S(G/H)}K[V], equating to (σ(h_{i})−h_{i})_{σ∈S(G/H)}, and solving for the unknown coefficients. This is a system of inhomogeneous linear equations over K.

(4) The preimages calculated in step (3) define the map A^{r} → A^{k} from the diagram (3.2). Calculate generators of its kernel M using the method described below.

(5) Use linear algebra to omit generators of M which are redundant. By Lemma 2.1, this will result in a system of generators with minimal cardinality.

(6) Apply the map A^{r} → K[V]^{H} to the generators of M. The result is a set of minimal secondary invariants for K[V]^{G}.

The calculation of syzygy modules

Suppose that A is a polynomial ring in variables t_{1}, …, t_{n} and φ: A^{r} → A^{k} is a homomorphism between free A-modules, given by the images v_{1}, …, v_{r} of the free generators of A^{r}. We are interested in the kernel M of φ, which is also called the syzygy module of the v_{i}. We give a short summary of a technique for computing generators of M which can be found (with proofs) in Becker and Weispfenning [4, Section 6.1]. The first step is the calculation of a Gröbner basis of the submodule in A^{k} generated by the v_{i}. This requires some explanation: in A^{k}, a monomial is a vector with only one nonzero component which is a monomial in A in the usual sense. We can now fix a term order on the monomials in A^{k} (where usually precedence is given to the term in A over the position in the vector) and then talk about the leading monomial of a nonzero vector v ∈ A^{k}. Now a Gröbner basis is calculated by the usual Buchberger algorithm, with the modification that s-polynomials are only formed from vectors whose leading monomials “meet” at the same position in the vector.

So suppose that a Gröbner basis w_{1}, …, w_{s} ∈ A^{k} of the module generated by the v_{i} has been calculated. Then for a pair i, j ∈ {1, …, s} where the leading monomials of w_{i} and w_{j} meet, the s-polynomial has the normal form 0 with respect to w_{1}, …, w_{s}, since this is a Gröbner basis. Therefore we have an equation

spoly(w_{i}, w_{j}) − ∑_{ν=1}^{s} a_{ν}w_{ν} = 0

with a_{ν} ∈ A, i.e., we have a syzygy r_{i,j} ∈ A^{s} of the w_{i}. Let R be the set of all syzygies obtained in this way. It can be shown that R generates the syzygy module of the w_{i}. But we are interested in the syzygies of the v_{i}, and this requires a further step.

Since the w_{i} and the v_{i} generate the same submodule of A^{k}, there exist matrices C ∈ A^{s×r} and D ∈ A^{r×s} such that

(w_{1} ; ⋮ ; w_{s}) = C · (v_{1} ; ⋮ ; v_{r}) and (v_{1} ; ⋮ ; v_{r}) = D · (w_{1} ; ⋮ ; w_{s}) .

The matrix C can be obtained by tracing the formation of the w_{i} during the Buchberger algorithm, and D is computed by taking the normal forms of the v_{i} with respect to w_{1}, …, w_{s} (which are 0) and keeping track of the coefficients. Now usually DC is not the identical matrix I_{r}, but we have

(DC − I_{r}) · (v_{1} ; ⋮ ; v_{r}) = 0.

Hence the rows of DC − I_{r} give a set R′ of syzygies of the v_{i}. Finally, the union

R′ ∪ {(a_{1} … a_{s}) · C | (a_{1} … a_{s}) ∈ R}

is the desired generating set of the syzygy module M of the v_{i} (see Becker and Weispfenning [4, Theorem 6.4]). So again the hard work lies in the computation of a Gröbner basis.

Returning to the algorithm for the computation of secondary invariants in the modular case, it is worth noting that in many examples the linear algebra involved in step (3) is much more expensive than the calculation of the syzygy module in step (4). Example 3.3. We look at two examples now.

(a) Let G be the permutation group of order 2 on 6 symbols, generated by (1, 2)(3, 4)(5, 6), and take K to be 𝔽_{2}. Denote the variables of K[V] by x_{1}, y_{1}, x_{2}, y_{2}, x_{3}, y_{3}, so the action of G is by exchanging x_{i} and y_{i}. We find primary invariants

x_{i} + y_{i} and x_{i}y_{i} (i = 1, 2, 3).

Using the above algorithm, Magma finds the following minimal set of secondary invariants:

1, x_{i}y_{j} + x_{j}y_{i} (1 ≤ i < j ≤ 3) and x_{1}x_{2}x_{3} + y_{1}y_{2}y_{3}.

The complete computation takes less than 1/10 seconds. Note that in this example the number of secondary invariants (5) exceeds the product of the degrees of the primary invariants divided by the group order (4), hence by Proposition 3.1 K[V]^{G} is not Cohen-Macaulay.

(b) Let G be the 3-modular reduction of the Weyl group of type H_{4}. This is a subgroup of order 14 400 of GL_{4}(𝔽_{9}). We will calculate the invariant ring of this group in Section 5. Here we look at a p-Sylow subgroup P of G, for p = 3. P has order 9 and can be generated by the matrices

(\begin{matrix}1 & 0 & 0 & 0 \\ w + 1 & 1 & 0 & 0 \\ −1 & 0 & 1 & 0 \\ w & 0 & −1 & 1 \end{matrix}) , (\begin{matrix}1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ w & −w & w & 1 \end{matrix}) ∈ GL_{4}(𝔽_{9}),

where w^{2} − w − 1 = 0. The computation of primary and secondary invariants by Magma takes about 4 seconds. The result are primary invariants of degrees 1,2,3,9 and secondary invariants of degrees 0,3,4,7,8,11. In this example, the number of secondary invariants equals ∏_{i=1}^{n} deg(f_{i})/|G|. As we will see in Proposition 4.1, this means that K[V]^{G} is Cohen-Macaulay.

4 Properties of the invariant ring

One of the main reasons for computing invariant rings is that one wants to study their structural properties. This is especially interesting in the modular case, where many theoretical questions are still open, and computations help to gain experience, counter examples, ideas for conjectures and in fortunate cases also for proofs. In this section we will see how most interesting properties of invariant rings can easily be extracted from the data which are available after the calculation of primary and secondary invariants. The first three subsections concern only the modular case, and the last two are also interesting in the non-modular case.

4.1 The Cohen-Macaulay property

We have already seen that in the non-modular case all invariant rings of finite groups are Cohen-Macaulay, and we have seen an example in the modular case where K[V]^{G} is not Cohen-Macaulay (Example 3.3(a)). In that example, we used Proposition 3.1, and we will now explain why the converse of this proposition also holds. Indeed, the polynomial ring K[V] is Cohen-Macaulay, and so by Proposition 3.1 it is a free module of rank d = ∏_{i=1}^{n} d_{i} over K[f_{1}, …, f_{n}], where the f_{i} are primary invariants and the d_{i} their degrees. Hence K(V), the field of fractions of K[V], is a vector space of dimension d over the rational function field K(f_{1}, …, f_{n}) generated by the f_{i}. The invariant field K(V)^{G} is an intermediate field between K(f_{1}, …, f_{n}) and K(V), and the index [K(V) : K(V)^{G}] is equal to |G| by Galois theory. Hence [K(V)^{G} : K(f_{1}, …, f_{n})] = d/|G|. (This provides another proof of the fact that |G| divides the degree product of the primary invariants, which we used in Section 2.) Now it is easily seen that a system of secondary invariants always generates K(V)^{G} as a vector space over K(f_{1}, …, f_{n}), hence such a system must have at least d/|G| elements, and more than d/|G| will be linearly dependent over K[f_{1}, …, f_{n}]. Thus we have proved:

Proposition 4.1. Let m be the minimal number of secondary invariants with respect to primary invariants of degrees d_{1}, …, d_{n}. Then

m ≥ \frac{d_{1} ⋯ d_{n}}{|G|} ,

and equality holds if and only if K[V]^{G} is Cohen-Macaulay.

This provides a criterion which involves no further computations at all to check the Cohen-Macaulay property. For example, we see that the invariant ring in Example 3.3(b) is Cohen-Macaulay.

Experience so far seems to suggest that “most” modular invariant rings are not Cohen-Macaulay. Several classes of linear groups whose invariant rings are not Cohen-Macaulay are given in Kemper [16]. For example, if the characteristic p of K divides |G| and the rank of σ−1 is sufficiently large for all elements σ ∈ G of order p, then K[V]^{G} is not Cohen-Macaulay.

4.2 Free resolutions and depth

If the invariant ring is not Cohen-Macaulay, then there are linear relations between the secondary invariants with coefficients in the algebra A = K[f_{1}, …, f_{n}] generated by the primary invariants. The methods to deal with them apply in the more general situation of graded algebras. So as in Section 2, let R be a finitely generated graded algebra over R_{0} = K, and let A = K[f_{1}, …, f_{n}] be the subalgebra generated by a homogeneous system of parameters. Assume that, as in Section 3.2, we have calculated R as a module over A by giving generators of a submodule M ⊆ A^{r} which is isomorphic to R (see diagram 3.2). Then to calculate relations over A between the generators is again the computation of a syzygy module. Indeed, giving m generators for M ⊆ A^{r} is the same as giving a homomorphism A^{m} → A^{r} whose image is M ≅ R. But we saw in Section 3.2 how kernels of such maps can be calculated. So let S ⊆ A^{m} be the kernel, then we have an exact sequence 0 → S → F_{0} → R → 0, where we have written F_{0} for the free module A^{r} to get a more convenient notation. Since all maps are degree-preserving, S is a graded module, hence by Lemma 2.1, a generating system for S of minimal cardinality can be obtained by deleting superfluous generators.

Now we can continue in the same way and calculate minimal relations between the generators of S, which leads to an exact sequence 0 → S′ → F_{1} → F_{0} → R → 0. By Hilbert’s syzygy theorem (see, for example, Benson [5, Theorem 4.2.2]), this process stops after at most n steps, so we will finally arrive at an exact sequence of graded A-modules with degree-preserving maps

0 ⟶ F_{l} ⟶ … ⟶ F_{1} ⟶ F_{0} ⟶ R ⟶ 0,  (4.1)

where the F_{i} are all free modules. Such a sequence is called a minimal free resolution of R. The length l does not depend on the choice of the generators of the various kernels, as can be seen by applying Lemma 2.1. It requires some commutative algebra to show that l does not even depend on the choice of the homogeneous system of parameters (see Benson [5, Section 4.4]). The value l is called the homological dimension of R. Thus R is Cohen-Macaulay if and only if the homological dimension is zero, so it is fair to say that the homological dimension measures the deviation from being Cohen-Macaulay. Another invariant of R which is closely related to the homological dimension is its depth. Indeed, by the formula of Auslander and Buchsbaum (see Benson [5, Theorem 4.4.4]), we have

depth(R) = n − l.

For all that matters here, this can be taken as the definition of the depth. Originally, the depth is defined as the maximal length of a regular sequence in R, i.e., a sequence f_{1}, …, f_{d} ∈ R_{+} of homogeneous elements such that f_{i} is not a zero divisor on R/(f_{1}, …, f_{i−1}), for all i = 1, …, d.

So we have seen that the depth of invariant rings of finite groups can be calculated algorithmically. Experience shows that this is an easy task compared to the bulk of work that goes into the calculation of primary and secondary invariants. There are few general results known about the depth of modular invariant rings. The paper of Ellingsrud and Skjelbred [10] gives a formula for the depth in the case of cyclic p-groups, where p = char(K). Recently Campbell et al. [8] found a generalization and an elementary proof of this formula. For example, the invariant ring considered in Example 3.3(a) has depth 5 and hence homological dimension 1.

4.3 The Hilbert series

If we have an exact sequence of finite dimensional vector spaces starting and ending with 0, then the dimension formula says that the alternating sum of the dimensions is zero. Hence the same is true if we consider graded modules and their Hilbert series. So from (4.1) we obtain

H(R, t) = ∑_{i=0}^{r}(−1)^{i}H(F_{i}, t).

Observe that the free generators of F_{i} must be of the right degrees to make the maps in (4.1) degree-preserving. If these degrees are e_{i,1}, …, e_{i,s_{i}}, then

H(F_{i}, t) = (t^{e_{i,1}} + ⋯ + t^{e_{i,s_{i}}}) · H(A, t) = \frac{t^{e_{i,1}} + ⋯ + t^{e_{i,s_{i}}}}{(1 − t^{deg(f_{1})}) ⋯ (1 − t^{deg(f_{n})})}

(see Equation (2.1)).

Another method to calculate the Hilbert series of an invariant ring appears by considering diagram 3.2 again. If N ⊆ A^{k} is the image of the map A^{r} → A^{k}, then

H(K[V]^{G}, t) = H(A^{r}, t) − H(N, t) = H(A^{r}, t) − H(A^{k}, t) + H(A^{k}/N, t).

But H(A^{r}, t) and H(A^{k}, t) are known, and H(A^{k}/N, t) can be computed by a combinatorial algorithm (Bayer and Stillman [3]) from a Gröbner basis of N. Now fortunately a Gröbner basis of N has already been calculated as the first step in the syzygy calculation leading to M.

One reason why it is interesting to know the Hilbert series of a graded algebra R is that one can use it to check the so-called Gorenstein property: R is Gorenstein if and only if it is Cohen-Macaulay and the Hilbert series satisfies

H(R, 1/t) = (−1)^{dim(R)}t^{l} · H(R, t)

for some l ∈ ℤ. For example, the invariant rings in Example 3.2(a)–(c) and Example 3.3(b) are Gorenstein.

4.4 Minimal algebra-generators and β

Let R be a graded algebra over R_{0} = K and g_{1}, …, g_{r} ∈ R_{+} homogeneous. Then it is seen as in the proof of Lemma 2.1 that g_{1}, …, g_{r} generate R as an algebra over K if and only if they generate the ideal R_{+} ⊆ R. Moreover, by Lemma 2.1 this is equivalent to the condition that the images of the g_{i} generate the quotient R_{+}/R_{+}^{2} as a vector space over K. Hence a homogeneous system of algebra generators has minimal cardinality if no generator is superfluous, and then the number and degrees of the generators are uniquely determined. In particular the maximal degree β(R) of a generator is well defined. One also sees that β(R) remains unchanged under extensions of the ground field, i.e., if we pass from R to R ⊗_{K} L for L ≥ K a field extension. Equivalently, β(R) is the minimal number d such that R is generated as a K-algebra by homogeneous elements of degrees ≤ d.

It is clear that the invariant ring K[V]^{G} is generated as a K-algebra by the primary and secondary invariants. Although the secondary invariants are minimal module-generators, they are not minimal algebra-generators. For example, 1 is always a secondary invariant, but it is redundant as an algebra-generator. To test whether a given generator f within a system S of homogeneous algebragenerators is redundant is a linear algebra problem. The procedure is to set up a general element of the same degree as f in the algebra generated by S \ {f} with unknown coefficients, equating to f and extracting the corresponding system of linear equations by comparison of coefficients. The system is solvable if and only if f can be omitted from S. Starting with S as the union of the primary and secondary invariants, one thus gets a minimal system of algebra-generators, and by the above, β(K[V]^{G}) is its maximal degree.

Example 4.2. In Example 3.2, we have β(K[V]^{G}) = 3, 5, 15 in part (a),(b),(c), respectively. In Example 3.3(a), it is easily checked that the secondary invariant x_{1}x_{2}x_{3}+y_{1}y_{2}y_{3} cannot be expressed in terms of invariants of lower degree, hence β(K[V]^{G}) = 3. This shows that Noether’s degree bound (which says that β(K[V]^{G}) ≤ |G| if char(K) > |G|) does not hold in the modular case. In Example 3.3(b), we obtain minimal algebra generators of degrees 1,2,3,3,4,9, so the secondary invariants of degrees 7,8,11 are redundant. We obtain β(K[V]^{G}) = 9 = |G|, which confirms a conjecture made by the author that Noether’s degree bound holds if the invariant ring is Cohen-Macaulay.

4.5 Syzygies

Suppose we have generators h_{1}, …, h_{r} of a K-algebra R. Then we have a presentation of R if we know the kernel I of the map

Φ: K[t_{1}, …, t_{r}] → R, t_{i} ↦ h_{i},

where the t_{i} are indeterminates. It is one of the basic tasks in invariant theory to compute generators of I as an ideal in the polynomial ring K[t_{1}, …, t_{r}]. The elements of I are usually called syzygies. When we were talking about syzygies in the preceding sections of this text, we meant elements in the kernel of a map of modules, not algebras. But in fact we deal with a special case here, since R becomes a module over K[t_{1}, …, t_{r}] via Φ, and then Φ is a module-homomorphism. We have shown how kernels of maps between free modules over a polynomial ring can be computed. But here the situation is different since R is usually not free, so we need different methods. Before explaining them, we remark that if R is a graded algebra and the h_{i} are homogeneous, then I becomes a homogeneous ideal if we set deg(t_{i}) = deg(h_{i}).

The Gröbner basis method

Suppose now that R ⊆ K[x_{1}, …, x_{n}] is a subalgebra of a polynomial ring. Then the standard method to calculate syzygies is the following. Form the ideal

J = (h_{1} − t_{1}, …, h_{r} − t_{r}) ⊆ K[x_{1}, …, x_{n}, t_{1}, …, t_{r}]

and calculate a Gröbner basis B of J with respect to a term order with the property that x_{i} is greater than any monomial in the t_{j}’s for i = 1, …, n. For example, one can use the lexicographical term order with x_{1} > … > x_{n} > t_{1} > … > t_{r}. Then it is easy to see that the intersection B_{t} = B ∩ K[t_{1}, …, t_{r}] generates the desired ideal I = ker(Φ) (see Becker and Weispfenning [4, Proposition 6.15]). If the h_{i} are homogeneous polynomials, then the syzygies in B_{t} are also homogeneous (with the proper choice of degrees of the t_{i}), since the Buchberger algorithm preserves homogeneity. Hence by Lemma 2.1 one obtains a generating set for I of minimal cardinality by omitting superfluous generators from B_{t}. This can be done by the usual linear algebra methods.

The linear algebra method

Now we make the more restrictive assumption that R is a graded algebra and that the set {h_{1}, …, h_{r}} is the union of a homogeneous system of parameters {f_{1}, …, f_{n}} and a generating set {g_{1}, …, g_{m}} of R as a module over A = K[f_{1}, …, f_{n}]. This is the situation that we have after primary and secondary invariants have been calculated. Since the f_{i} are algebraically independent, we are looking for the kernel I of the map

A[t_{1}, …, t_{m}] → R, t_{i} ↦ g_{i},

where the t_{i} are again indeterminates. Suppose that S ⊆ I is a set of relations containing

(a) generators for the A-module I ∩ (⊕_{i=1}^{m}A · t_{i}) of A-linear relations between the g_{i}, and

(b) for each 1 ≤ i ≤ j ≤ m a relation of the form t_{i}t_{j} − f_{i,j} with f_{i,j} ∈ ⊕_{k=1}^{m}A · t_{k}.

Then it is easy to show that S generates I (see Kemper and Steel [18, Proposition 12]). In other words, all that we have to know are the linear relations between the g_{i} with coefficients in A and the representation of each product g_{i}g_{j} as an element of ⊕_{k=1}^{m}A · g_{k}. We explained in Section 4.2 how the linear relations can be calculated. The representation of a product g_{i}g_{j} or, more generally, a homogeneous element f ∈ R of degree d, say, as an element of ⊕_{i=1}^{m}A · g_{i} can be calculated by equating f to a general element of ⊕_{i=1}^{m}A · g_{i} of degree d with unknown coefficients and solving the resulting inhomogeneous system of linear equations over K. This approach usually performs better than the Gröbner basis method. Nevertheless, the computation of relations can sometimes be quite expensive.

It is often important to obtain a minimal system of generators for the ideal I. If R is a graded algebra, Lemma 2.1 applies again and tells us that it is enough to omit superfluous generators. If the linear algebra method is used, one can go a bit further by detecting superfluous relations even before calculating them: it is quite easy to decide whether the ideal generated by the relations that have already been computed at some point contains a relation giving the desired representation for a product g_{i}g_{j}. In fact, this again comes down to the solution of a system of linear equations.

R is said to be a complete intersection if the minimal number of generators of I is r−dim(R), where r is the number of algebra-generators of R and dim(R) is the Krull dimension. In other words, the dimension of the variety VK̄(r_{1}, …, r_{i}) decreases by 1 with each new generating relation r_{i} as it enters into the ideal. If R is graded, then this property is independent of the choice of the generators and of the minimal generating relations. In Example 3.2(a) and (c) the invariant rings are complete intersections.

5 Using ad hoc methods

It often happens in “real life” situations that the algorithms given in the above sections require too much time or memory to be feasible anymore. Then one has to put ones hope in ad hoc methods, which in some cases work and produce the invariant ring, and depend on a mixture of experience, luck and naive optimism. In order to give a feeling of some of the methods that can be applied, we look at an example of a linear group for which the standard algorithms fail. This group G is the 3-modular reduction of the Weyl group of type H_{4} of order 14 400. G is a subgroup of GL_{4}(𝔽_{9}) and can be generated by the full permutation group S_{4} together with the matrices

(\begin{matrix}−1 & 0 & 0 & 0 \\ 0 & −1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}) and (\begin{matrix}0 & −1 & −1 & ζ^{2} \\ −1 & 0 & −1 & ζ^{2} \\ −1 & −1 & 0 & ζ^{2} \\ ζ^{2} & ζ^{2} & ζ^{2} & −1 \end{matrix}) ,

where ζ ∈ 𝔽_{9} is an element of order 8. G is a group generated by reflections, but since its order is a multiple of the characteristic of K, the invariant ring need not be isomorphic to a polynomial ring. In Example 3.3(b) we have calculated the invariant ring of a p-Sylow subgroup of G, for p = 3, and seen that this invariant ring is Cohen-Macaulay. It follows by a theorem of Campbell et al. [7] that the invariant ring K[V]^{G} of G is also Cohen-Macaulay. In order to compute it, we first need to find primary invariants.

5.1 Finding primary invariants

We first use the inequality (2.4) to get an idea of the degrees d_{i} that primary invariants can have. The computation of the homogeneous components K[V]_{d}^{G} is feasible up to degrees around d = 40, and (2.4) yields

d_{1} ≥ 2, d_{2} ≥ 10, and d_{3} ≥ 36

but no information on the last degree d_{4}. By trying random invariants f_{2}, f_{10}, f_{36} of degrees 2, 10 and 36 we are lucky enough to arrive at an ideal (f_{2}, f_{10}, f_{36}) of dimension 1, so there is only one further primary invariant missing. We have

f_{2} = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2}, f_{10} = x_{1}^{10} + x_{2}^{10} + x_{3}^{10} + x_{4}^{10},

but f_{36} is much more complicated. By Proposition 3.1 the degree d_{4} of the missing primary invariant must be a multiple of |G|/(d_{1}d_{2}d_{3}) = 20. We already know that d_{4} > 20, and we rule out the possibility d_{4} = 40 by using (2.4) again. So our hope is that we will find a last primary invariant f_{60} of degree 60. However, it is impossible due to time and storage problems to compute all invariants of degree 60. Instead, we try to construct f_{60} by using Steenrod operations.

Steenrod operations are a very helpful tool in modular invariant theory, and we explain their definition by following Smith [24]. Suppose K = 𝔽_{q} is a finite field. Then we take an additional indeterminate T and define a homomorphism P: K[V] → K[V][T] of K-algebras by sending x_{i} to x_{i} + x_{i}^{q} · T. It is easily checked that P commutes with the action of GL(V) on K[V]. For f ∈ K[V], write

P (f) = ∑_{i≥0} P^{i}(f) · T^{i}.

Then P^{i}(f) is the i-th Steenrod operation of f. It follows from the GL(V)-compatibility of P than Steenrod operations of invariants are again invariants. It is also easy to check that for a homogeneous f

deg(P^{i}(f)) = deg(f) + i(q − 1)

if P^{i}(f) is nonzero, and P^{i}(f) = 0 if i > deg(f).

We continue the construction of primary invariants. First note that f_{10} = −P^{1}(f_{2}). Now f_{60} = P^{3}(f_{36}) has the desired degree 60, and indeed we are lucky enough to find that the ideal generated by f_{2}, f_{10}, f_{36} and f_{60} has dimension 0. Thus a complete system of primary invariant is found.

5.2 Finding secondary invariants

Since we know that K[V]^{G} is Cohen-Macaulay, the number of secondary invariants must be d_{1}d_{2}d_{3}d_{4}/|G| = 3 by Proposition 3.1. However, it is impossible to run the standard algorithm given in Section 3.2 for this group, and it is a very hard calculation to produce the secondary invariant by linear algebra methods. Instead we choose another approach. The first secondary invariant is always g_{1} = 1. Now we consider the dimensions of the homogeneous components K[V]_{d}^{G} and compare them to the dimensions of A_{d}, where A = K[f_{2}, f_{10}, f_{36}, f_{60}]. This way, we find that d = 22 is the first degree where these dimensions differ, hence there exists an invariant g_{22} ∈ K[V]^{G} \ A of degree 22, which is the second secondary invariant. It is quite easy to find such a g_{22} by linear algebra, but g_{22} is too long to be printed here. Now we are optimistic and guess that the third (and last) secondary invariant is g_{22}^{2}. Assuming that this is true, we must have g_{22}^{3} ∈ A + A · g_{22} + A · g_{22}^{2}. Indeed we quickly find the relation

g_{22}^{3} + (f_{2}^{11} − f_{2}f_{10}^{2})g_{22}^{2} + (f_{2}^{17}f_{10} − f_{2}^{7}f_{10}^{3} − f_{2}^{12}f_{10}^{2} + f_{2}^{4}f_{36} + f_{2}^{2}f_{10}^{4})g_{22} +

+ f_{2}^{18}f_{10}^{3} − f_{2}^{28}f_{10} + f_{10}^{3}f_{36} + f_{2}^{15}f_{36} − f_{2}^{13}f_{10}^{4} − f_{2}^{5}f_{10}^{2}f_{36} + f_{2}^{8}f_{10}^{5} − f_{2}^{3}f_{60} = 0 (5.1)

by linear algebra. Let R = K[f_{2}, f_{10}, f_{36}, f_{60}, g_{22}] be the K-algebra generated by f_{2}, f_{10}, f_{36}, f_{60} and g_{22}, then we claim that K[V]^{G} = R. We will use the following proposition for this purpose.

Proposition 5.1. Suppose that R ≤ K[V]^{G} is a subalgebra of an invariant ring of a finite group. Then R = K[V]^{G} if and only if the following three conditions hold:

(a) The field of fractions Quot(R) of R coincides with the invariant field K(V)^{G} = Quot(K[V]^{G}),

(b) K[V]^{G} is integral over R, and

(c) R is integrally closed (in its field of fractions).

Proof. First suppose that R = K[V]^{G}. Then clearly Quot(R) = Quot(K[V]^{G}), hence (a) and (b) hold. Furthermore, if f ∈ K(V)^{G} is integral over R = K[V]^{G}, then f is also integral over K[V], hence f ∈ K[V] since polynomial rings are integrally closed. It follows that f ∈ K(V)^{G} ∩ K[V] = K[V]^{G}. Hence R is also integrally closed.

Now suppose that (a)–(c) hold for R, and take an invariant f ∈ K[V]^{G}. Then f ∈ K(V)^{G} = Quot(R) is integral over R, hence (c) implies that f ∈ R, so R = K[V]^{G}.

Returning to our example, we first prove that the condition (a) from Proposition 5.1 holds. Indeed,

[K(V)^{G} : K(f_{2}, f_{10}, f_{36}, f_{60})] = \frac{2 · 10 · 36 · 60}{|G|} = 3

(see before Proposition 4.1), so g_{22} ∉ K(f_{2}, f_{10}, f_{36}, f_{60}) implies Quot(R) = K(V)^{G}. Furthermore, K[V]^{G} is integral over R since R contains a homogeneous system of parameters. The hardest part is the verification of condition (c). We first observe that Equation (5.1) gives a presentation of R, since the minimal polynomial of g_{22} over K(f_{2}, f_{10}, f_{36}, f_{60}) has the degree 3. Moreover, the relation shows that

R[f_{2}^{−1}] = K[f_{2}, f_{10}, f_{36}, g_{22}, f_{2}^{−1}]

is the localization of a unique factorization domain and hence itself a unique factorization domain. Now an elementary argument shows that if f_{2} is a prime element in R, then R must also be a unique factorization domain, and then it is integrally closed. In order to prove that f_{2} ∈ R is a prime element, we consider the quotient ring R/(f_{2}) and from Equation (5.1) find the presentation

R/(f_{2}) = K[f_{10}, f_{36}, f_{60}, g_{22}]/(g_{22}^{3} + f_{10}^{3}f_{36}).

Since the polynomial that is factored out is clearly irreducible, R/(f_{2}) is a domain and hence f_{2} is a prime element as claimed.

Thus we conclude that indeed K[V]^{G} = R, and 1, g_{22}, g_{22}^{2} are secondary invariants. In summary, we have seen that K[V]^{G} is not a polynomial ring in spite of the fact that G is generated by reflections, but K[V]^{G} is a complete intersection.

Using methods like these, Gunter Malle and I recently managed to classify all irreducible reflection groups that are not classical groups whose invariant rings are complete intersections.

References

[1] Alejandro Adem, R. James Milgram, Cohomology of Finite Groups, Springer-Verlag, Berlin, Heidelberg, New York 1994.

[2] Helmer Aslaksen, Shih-Piug Chan, Tor Gulliksen, Invariants of S_{4} and the Shape of Sets of Vectors, Applicable Algebra in Engeneering, Communication and Computing 7 (1996), 53–57.

[3] Dave Bayer, Mike Stillman, Computation of Hilbert Functions, J. Symbolic Computation 14 (1992), 31–50.

[4] Thomas Becker, Volker Weispfenning, Gröbner Bases, Springer-Verlag, Berlin, Heidelberg, New York 1993.

[5] David J. Benson, Polynomial Invariants of Finite Groups, Lond. Math. Soc. Lecture Note Ser. 190, Cambridge Univ. Press, Cambridge 1993.

[6] Wieb Bosma, John J. Cannon, Catherine Playoust, The Magma Algebra System I: The User Language, J. Symbolic Computation 24 (1997).

[7] H. E. A. Campbell, I. Hughes, R. D. Pollack, Rings of Invariants and p-Sylow Subgroups, Canad. Math. Bull. 34(1) (1991), 42–47.

[8] H. E. A. Campbell, I. P. Hughes, G. Kemper, R. J. Shank, D. L. Wehlau, Depth of Modular Invariant Rings, submitted, 1997.

[9] David Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Springer-Verlag, New York 1995.

[10] Geir Ellingsrud, Tor Skjelbred, Profondeur d’anneaux d’invariants en caractéristique p, Compos. Math. 41 (1980), 233–244.

[11] Karin Gatermann, Semi-Invariants, Equivariants and Algorithms, Appl. Algebra Eng. Comm. Comput. 7 (1996), 105–124.

[12] David Hilbert, Über die Theorie der algebraischen Formen, Math. Ann. 36 (1890), 473–534.

[13] M. Hochster, J. A. Eagon, Cohen-Macaulay Rings, Invariant Theory, and the Generic Perfection of Determinantal Loci, Amer. J. of Math. 93 (1971), 1020–1058.

[14] Gregor Kemper, Calculating Invariant Rings of Finite Groups over Arbitrary Fields, J. Symbolic Computation 21 (1996), 351–366.

[15] Gregor Kemper, Calculating Optimal Homogeneous Systems of Parameters, submitted; IWR Preprint 97-08, Heidelberg 1997.

[16] Gregor Kemper, On the Cohen-Macaulay Property of Modular Invariant Rings, IWR Preprint 97-38, Heidelberg 1997.

[17] Gregor Kemper, Hilbert Series and Degree Bounds in Invariant Theory, submitted; IWR Preprint 97-45, Heidelberg 1997.

[18] Gregor Kemper, Allan Steel, Some Algorithms in Invariant Theory of Finite Groups, in: P. Dräxler, G.O. Michler, C. M. Ringel, eds., Proceedings of the Euroconference on Computational Methods for Representations of Groups and Algebras, Progress in Mathematics, Birkhäuser, Basel (to appear).

[19] M. Nagata, On the 14th Problem of Hilbert, Amer. J. of Math. 81 (1959), 766–772.

[20] M. Nagata, Lectures on the Fourteenth Problem of Hilbert, Tata Institute of Fundamental Research, Bombay 1965.

[21] Emmy Noether, Der Endlichkeitssatz der Invarianten endlicher linearer Gruppen der Charkteristik p, Nachr. Ges. Wiss. Göttingen (1926), 28–35.

[22] Vladimir L. Popov, On Hilbert’s Theorem on Invariants, Dokl. Akad. Nauk SSSR 249 (1979), English translation Soviet Math. Dokl. 20 (1979), 1318–1322.

[23] N. J. A. Sloane, Error-Correcting Codes and Invariant Theory: New Applications of a Nineteenth-Century Technique, Amer. Math. Monthly 84 (1977), 82–107.

[24] Larry Smith, Polynomial Invariants of Finite Groups, A. K. Peters, Wellesley, Mass. 1995.

[25] Richard P. Stanley, Invariants of Finite Groups and their Applications to Combinatorics, Bull. Amer. Math. Soc. 1(3) (1979), 475–511.

[26] Patrick A. Worfolk, Zeros of Equivariant Vector Fields: Algorithms for an Invariant Approach, J. Symbolic Computation 17 (1994), 487–511.