A Database of Invariant Rings^{∗}

Gregor Kemper, Elmar Körding, Gunter Malle, B. Heinrich Matzat, Denis Vogel, and Gabor Wiese

November 10, 2000

Abstract

We announce the creation of a database of invariant rings. This database contains a large number of invariant rings of finite groups, mostly in the modular case. It gives information on generators and structural properties of the invariant rings. The main purpose is to provide a tool for researchers in invariant theory.

1 Introduction

Invariant theory of finite groups is a subject which has a large variety of applications, but also displays many open questions. This applies in particular to the modular case, where the characteristic of the ground field divides the group order. Consequently, much of the recent research activity went into this area (see Benson [1], Smith [16] and the references there). For a general introduction into the invariant theory of finite groups we refer the reader to the survey article by Stanley [17], or the book by Smith [15], which gives a problem-oriented presentation.

Research in invariant theory (and, in fact, many other areas of mathematics as well) greatly benefits from the availability of examples. Examples provide a means to gain experience and understanding, to find or test conjectures, search for interesting (counter-)examples, and sometimes to prove results. In invariant theory, new algorithms and the emergence of faster computers have made it possible to study problems in a way that would be impossible by hand calculations and ad hoc methods. In fact, the computational aspects of invariant theory have recently enjoyed considerable interest in their own right (as is documented by the book by Sturmfels [18] and many more recent papers such as Derksen and Kraft [6] or Kemper [10]). With this in mind, we have decided to assemble a collection of examples, in the form of a database, and to provide it to the public as a research tool. All computations were done in the computer algebra system MAGMA (Bosma et al. [2]), which has an efficient package for invariant theory (see Kemper and Steel [12]). We used the Sun computers at the IWR in Heidelberg. Currently the database contains 5922 examples, almost all modular, and takes about 100 Mbytes of storage space. The database, together with software for the retrieval of data, can be downloaded via anonymous ftp from the site

                             ftp.iwr.uni-heidelberg.de

in the directory

                               /pub/kemper/DataBase/

The database runs on Unix operating systems.

We ask users to quote this paper when they write articles on research which involved the database.

∗This project is supported by the Deutsche Forschungsgemeinschaft under the project Ma 1062/8-2 (“Invariantentheorie endlicher Gruppen”).

2 Concepts of the database

Retrieval functions. To use the database, one cannot look at all the several thousand examples with the “naked idea”. Instead, significant examples must be retrieved by systematic searches. For example, a user might want to

• see examples where Noether’s degree bound [13] is violated (i.e., the maximal degree of a generating invariant exceeds the group order |G|),

• know whether in all examples the Hilbert ideal (i.e., the ideal in the polynomial ring K[V] generated by all invariants of positive degree) is generated by homogeneous elements of degree at most |G|,

• find the invariant ring of some particular group, or of a group which is conjugate to it.

It should be clear from these examples that there is no way to define a fixed catalogue of criteria for which users can search the database. Therefore it seemed impossible to us to implement our retrieval functions within some standard database program. In fact, the only practical way how such criteria can be formulated in a language understandable to a computer is within some computer algebra system. Moreover, a user should be able to manipulate the data retrieved from the database and not just look at it. Therefore we have decided to base our retrieval functions on the computer algebra systems Magma (Bosma et al. [2]) and Maple (Char et al. [4]). There is the choice to use either one of these systems (which of course must be available). We provide access functions that take a boolean-valued function in Magma or Maple as an argument. Users can define search criteria with such functions. After a search has been done, the examples which meet the search criterion can be loaded into Magma or Maple, respectively, for closer examination. In the following section we present an example session which shows how this works. What made it easier for us to abandon the idea of using standard database software is the fact that we are dealing with a relatively small number of items, but the data stored for each item is quite large.

Incomplete data. A further problem that we had to find a way to handle is the inherent difficulty of computations in invariant theory. The algorithms require the computation of Gröbner bases and the solution of large systems of linear equations (see Kemper [9], Kemper and Steel [12]). Therefore there are examples in the database where not all information could be computed. For example, it may happen that for some invariant ring the primary invariants could be computed, but the secondary invariants were found to be out of reach. We also used an algorithm, found by Hughes and Kemper [8], which for groups of order divisible by p := char(K) but not by p^{2} calculates the Hilbert series and the depth of the invariant ring with a computational cost that is similar to the evaluation of Molien’s formula. Thus for (almost) all groups in the database of order not divisible by p^{2} we have the Hilbert series, depth, Cohen-Macaulay property, and the Gorenstein property of the invariant ring, although in many cases not even a set of primary invariants is known. We did not want to exclude such examples from the database. As a consequence, the retrieval functions have to be able to deal with incomplete information. For example, a search function supplied by a user might ask something about secondary invariants. Such a search function, when applied to a ring where the secondary invariants are not known, should not return “true” or “false”, but “unknown”. This feature was especially hard to implement in Magma, where there is no traperror mechanism.

Computational difficulty. The computational difficulty also led to some problems in the creation of the database. Usually when one performs difficult computations on a computer, one has the computer run for a while and at some point when patience runs out, one chooses to interrupt the computation and tries a different method. Obviously this approach is not feasible for computing several thousand of examples. Instead, we implemented a scheme where different steps (or groups of steps) in the computation of each invariant ring are performed by different Magma processes which are run with a time and memory limit. If such a process terminates within the limit, it stores its results to a file for subsequent use in later steps. Otherwise, the invariant ring is transferred to a “problem queue”, where it can then be worked on by ad hoc or semi-automatic methods.

Efficient information transfer. When running the retrieval functions, information from the database is automatically read into Magma or Maple in order to apply the search function to the invariant rings. For reasons of efficiency it is important to transfer only that part of the information about each invariant ring into Magma or Maple which is actually needed for the evaluation of the search function. To decide what the relevant data is, one might subject the search function to a syntax analysis. Since this seemed impractical to us, we chose to implement a technique for dynamically determining the required information. More precisely, information that is found to be missing for the evaluation of the search function on some ring is reloaded for this ring, and then included into the list of necessary information for subsequent evaluations of the search function.

We believe that the specific difficulties we encountered in this project generalize to many other mathematical databases, and we hope that the concepts we developed will also be applicable in other contexts as well.

3 An example session

After the database has been downloaded, it requires a minimal amount of installation. For details see the documentation supplied with the database. Then the retrieval functions in Magma or Maple can be used. We present an example session in Magma, and remark that the usage in Maple is for the most part analogous. We start by calling the executable InvSearch. This starts Magma, reads in the retrieval functions and sets up the communication with the database. In the sequel we assume some basic familiarity with Magma.

(a) As a first example, suppose we are interested in the invariants of the group G = SO_{3}(𝔽_{5}) in the natural representation. The chances of finding the invariants of G in the database are much higher if we search for groups which are conjugate to G in GL_{3}(𝔽_{5}), rather than only for G itself. A test for this is provided by the function IsGroupConjugateTo, which is part of the retrieval functions. So we type:

     > G := SO(3,5);
     > T,F,U := SearchInvariants(func<R | IsGroupConjugateTo(R,G)>);
     > T;
     [ 10077 ]

The search through the database took 75 seconds. The function SearchInvariants is called with a boolean-valued function (the “search function”) as argument. This function has an invariant ring R as input and returns true if R is the invariant ring of a group conjugate to G. SearchInvariants returns three lists, T,F, and U, which stand for the invariant rings for which the search function yielded true, false, or could not be evaluated, respectively. Thus we have found exactly one invariant ring of a group conjugate to G. Every invariant ring is identified by a unique integer, its ExampleID. These ExampleID’s are listed in T,F, and U. So far, no invariant ring has been loaded into Magma. We load the one we are interested in now, and look at some of its properties.

     > R := RequestInvariants(T[1]);
     > DegreePrimaries(R);
     [ 2, 6, 20 ]
     > DegreeSecondaries(R);

[ 0, 25 ]
> Hypersurface(R);
true

(b) Next we want to test the conjecture (Conjecture 1 below) that if K[V]^{G} is Cohen-Macaulay, then Noether’s degree bound holds.

> CM,nCM,U := SearchInvariants(func<R | CohenMacaulay(R)>);
> #CM,#nCM,#U;
3330 1116 1476

This search took 19 seconds. So we have 3330 examples of Cohen-Macaulay invariant rings, 1116 examples of non-Cohen-Macaulay rings, and 1476 examples where the Cohen-Macaulay property could not be evaluated. Now we wish to single out those examples which satisfy Noether’s bound from the Cohen-Macaulay invariant rings. This can be done by giving a search range as a second argument to SearchInvariants. The minimal number k such that an invariant ring R can be generated by invariants of degree at most k is given by the function

Beta(R).
> NB,nNB,U := SearchInvariants(func<R | Beta(R) le GroupOrder(R)>,CM);
> #NB,#nNB,#U;
3105 0 225

Thus the conjecture could be verified in 3105 cases, and there is no counter-example.

4 Sources of examples and attributes stored

All finite groups with non-cyclic Sylow p-subgroup (p = char(K)) have an infinite number of nonisomorphic indecomposable representations over K. Thus there is no way in which the representations covered in our database can reach any level of comprehensiveness, and some degree of arbitrariness is therefore unavoidable in the choice of what linear groups we included in the database. This also means that for a user it will be a matter of luck if an invariant ring he or she is interested in will be contained in the database. In order to obtain a selection of examples which is not too biased in one direction or another, we decided to take our examples from the following sources:

(1) all subgroups of GL_{4}(𝔽_{2}),

(2) all 2-subgroups of GL_{5}(𝔽_{2}),

(3) all 3-subgroups of GL_{4}(𝔽_{3}),

(4) all subgroups of GL_{4}(𝔽_{3}) which can be generated by at most two elements,

(5) the exceptional irreducible complex reflection groups in characteristic 0, according to the classification by Shephard and Todd [14] (Here the generating invariants for the groups with numbers 36 and 37 (E_{7} and E_{8}) are not included in the data base because of storage problems, but they can be obtained from the authors upon request),

(6) a number of miscellaneous examples that seemed of special interest to us, including some small representations of quasi-simple groups,

(7) an assortment of representations up to degree 7 of groups of small order.

The groups under (7) were produced as follows. First we used the SmallGroups library in Magma to get some groups of small order. Then for each group and each prime p dividing the group order, we produced many “random” representations over 𝔽_{p^{i}} (1 ≤ i ≤ 3) by forming tensor products, symmetric powers, Jacobson radicals and other standard operations of representations we already had, and then extracting indecomposable representations from these with the Meat Axe. Since decomposable representations are also of considerable interest in invariant theory, we formed direct sums of the representations obtained in this way of total degree at most 7.

It should also be of interest what information we store for each invariant ring. The following is a partial list of attributes that we store for an invariant ring K[V]^{G}, wherever they could be computed.

(1) primary invariants,

(2) secondary invariants,

(3) fundamental invariants, i.e., a minimal system of generators of K[V]^{G},

(4) syzygies, i.e., algebraic relations between the fundamental invariants,

(5) “module-syzygies”, i.e., linear relations between the secondary invariants over the subalgebra generated by the primary invariants,

(6) the depth of K[V]^{G},

(7) the Hilbert series,

(8) the Cohen-Macaulay, Gorenstein, and complete intersection properties, and whether K[V]^{G} is a polynomial ring.

5 Some conjectures

We conclude this note by adding a few conjectures which have all been confirmed by the database. In the following, G ≤ GL(V) is a finite linear group in dimension n := dim(V).

Conjecture 1. If K[V]^{G} is Cohen-Macaulay, then Noether’s degree bound holds, i.e., K[V]^{G} is generated by homogeneous invariants of degrees at most |G|.

This conjecture generalizes the fact that Noether’s degree bound holds in the non-modular case, which was recently proved in full generality by Fleischmann [7]. We have 3330 examples of Cohen-Macaulay invariant rings in the database. Of these, 3105 are known to satisfy Noether’s bound, and for the rest generating invariants are not known. On the other hand, 133 examples from the database violate Noether’s bound. Another generalization is contained in the following conjecture.

Conjecture 2 (Derksen and Kemper [5, Conjecture 3.7.6]). Let I ⊂ K[V] be the “Hilbert ideal”, i.e., the ideal in the polynomial ring K[V] generated by all homogeneous invariants of positive degree. Then I is generated (as an ideal) by homogeneous elements of degree at most |G|.

Clearly Conjecture 2 holds if Noether’s degree bound is satisfied. But we also verified it for all 133 examples where Noether’s bound fails.

Conjecture 3 (Derksen, see Kemper [11]). Let f_{1}, …, f_{n} ∈ K[V]^{G} be primary invariants of degrees d_{1}, …, d_{n}. Then the degrees of the (corresponding) secondary invariants are bounded from above by d_{1} + ⋯ + d_{n} − n.

Conjecture 3 was proved in the Cohen-Macaulay case by Broer [3]. The secondary invariants are only known for 771 of the 1116 non-Cohen-Macaulay invariant rings in the database. In all 771 examples, Conjecture 3 holds.

Conjecture 4 (Kemper [11, Conjecture 22]). The degree of the Hilbert series H(K[V]^{G}, t) (as a rational function in ℂ(t)) is at most −n.

Conjecture 4 is true in the Cohen-Macaulay case, since in this case it is equivalent to Conjecture 3. We verified the conjecture for all 1116 invariant rings in the database which are not Cohen-Macaulay.

Conjecture 5. If K[V]^{G} is Cohen-Macaulay and G ≤ SL(V), then K[V]^{G} is Gorenstein.

Conjecture 5 is true in the non-modular case by a result of Watanabe [19, 20]. 1916 examples in our database satisfy the hypothesis of Conjecture 5, and all are Gorenstein. On the other hand, we have 893 examples which are Cohen-Macaulay but not Gorenstein (where the groups are not contained in SL(V), of course).

References

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

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

[3] Abraham Broer, Remarks on Invariant Theory of Finite Groups, preprint, Université de Montréal, Montréal, 1997.

[4] B. Char, K. Geddes, G. Gonnet, M. Monagan, S. Watt, Maple Reference Manual, Waterloo Maple Publishing, Waterloo, Ontario 1990.

[5] Harm Derksen, Gregor Kemper, Computational Invariant Theory, Springer-Verlag, Berlin, Heidelberg, New York 2000, in preparation.

[6] Harm Derksen, Hanspeter Kraft, Constructive Invariant Theory, in: Algèbre non commutative, groupes quantiques et invariants (Reims, 1995), Sémin. Congr. 36, pp. 221–244, Soc. Math. France, Paris 1997.

[7] Peter Fleischmann, The Noether Bound in Invariant Theory of Finite Groups, Adv. in Math. (2000), to appear.

[8] Ian Hughes, Gregor Kemper, Symmetric Powers of Modular Representations for Groups with a Sylow Subgroup of Prime Order, J. of Algebra (2000), to appear.

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

[10] Gregor Kemper, Computational Invariant Theory, The Curves Seminar at Queen’s, Volume XII, in: Queen’s Papers in Pure and Applied Math. 114 (1998).

[11] Gregor Kemper, Hilbert Series and Degree Bounds in Invariant Theory, in: B. Heinrich Matzat, Gert-Martin Greuel, Gerhard Hiss, eds., Algorithmic Algebra and Number Theory, Springer-Verlag, Heidelberg 1999.

[12] Gregor Kemper, Allan Steel, Some Algorithms in Invariant Theory of Finite Groups, in: P. Dräxler, G.O. Michler, C. M. Ringel, eds., Computational Methods for Representations of Groups and Algebras, Euroconference in Essen, April 1-5 1997, Progress in Mathematics 173, Birkhäuser, Basel 1999.

[13] Emmy Noether, Der Endlichkeitssatz der Invarianten endlicher Gruppen, Math. Ann. 77 (1916), 89–92.

[14] G. C. Shephard, J. A. Todd, Finite Unitary Reflection Groups, Canad. J. Math. 6 (1954), 274–304.

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

[16] Larry Smith, Polynomial Invariants of Finite Groups: A Survey of Recent Developments, Bull. Amer. Math. Soc. 34 (1997), 211–250.

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

[18] Bernd Sturmfels, Algorithms in Invariant Theory, Springer-Verlag, Wien, New York 1993.

[19] Keiichi Watanabe, Certain Invariant Subrings are Gorenstein I, Osaka J. Math. 11 (1974), 1–8.

[20] Keiichi Watanabe, Certain Invariant Subrings are Gorenstein II, Osaka J. Math. 11 (1974), 379–388.

Authors’ addresses:

Gunter Malle  all others:
FB Mathematik/Informatik IWR
Universität Gh Kassel  Universität Heidelberg
Heinrich-Plett-Str. 40  Im Neuenheimer Feld 368
34 132 Kassel  69 120 Heidelberg
Germany  Germany

Gregor.Kemper@iwr.uni-heidelberg.de
koerding@tphys.uni-heidelberg.de
malle@mathematik.uni-kassel.de|
matzat@iwr.uni-heidelberg.de
Denis.Vogel@iwr.uni-heidelberg.de
gwiese@ix.urz.uni-heidelberg.de