Gröbner bases for p-group algebras

David J. Green Department of Mathematics University of Wuppertal D–42097 Wuppertal, Germany.

              green@math.uni-wuppertal.de

17 May 1999

Abstract

Experiment shows that the reverse length-lexicographical word ordering consistently yields far smaller Gröbner bases for modular p-group algebras than the length-lexicographical ordering. For the so-called Jennings word ordering, based on a special power-conjugate group presentation, the associated monomial algebra is a group invariant. The package Present finds Gröbner bases for these three orderings.

1 Introduction

Let G be a finite p-group. One way to do computational homological algebra over the modular group algebra 𝔽_{p}G is to realise it as a finitely presented associative algebra, together with a Gröbner basis for the relations ideal. There are then several methods available for computing minimal projective resolutions [Feustel et al. 1993], [E. Green et al. 1998], [D. Green 1999].

The algebra generators are required to lie in the Jacobson radical. Usually one chooses generators g_{i} for the group, and then takes the a_{i} = g_{i} − 1 as generators for 𝔽_{p}G. See [Farkas et al. 1993] or [D. Green 1997] for an introduction to noncommutative Gröbner bases.

The choice of word ordering is of prime importance in the design of efficient Gröbner basis methods. This paper compares the usefulness in our context of three word orderings, and announces a package Present for computing Gröbner bases with respect to these orderings. They are:

• The length-lexicographical ordering (LL): the standard ordering for homological algebra over associative algebras.

• The reverse length-lexicographical ordering (RLL) allows one to read off the radical layers. Empirically, it always yields a small Gröbner basis.

• The Jennings ordering (see Definition 3.5) is defined on special presentations, which are constructed using the Jennings series and involve some redundant generators. Broadly speaking, it is for p-group algebras what power-conjugate presentations are for p-groups. All Gröbner bases have the same size, and in fact the associated monomial algebra is an invariant of the group’s order.

The criteria for comparing orderings are:

• Smallest size of Gröbner basis, taken over all choices of generators.

• How easy is it to realise a small Gröbner basis? That is, how sensitive is size of Gröbner basis to choice of generators?

• How many properties of the Gröbner basis (e.g., maximum length of a reduced word) do not depend on choice of generators?

In Sections 2 and 3 we look at the orderings one by one. For each ordering, a method is presented for computing the Gröbner basis for the relations ideal. These methods were implemented in the package Present. Data structures and other aspects of the implementation are discussed in Section 4. Results obtained using Present are presented in Section 5, where we draw conclusions about the comparative usefulness of the orderings.

The package Present is written partly in Magma code and partly in C. See the end of the paper for details of how to obtain it.

Acknowledgements This work was started while I was at the Institute for Experimental Mathematics in Essen, Germany. I am very grateful to the Institute for the continuing use of their computing facilities.

2 Gröbner bases

First we recall the basics about Gröbner bases in free associative algebras. Let M be the free associative monoid with 1 on a finite set A. That is, the elements of M are words in the alphabet A. Assume we have an ordering on M which is admissible in the following sense (far weaker than that of [Feustel et al. 1993]):

Definition 2.1 Let M be a free monoid. An ordering on M is called admissible if uv_{1}w ≤ uv_{2}w whenever u, v_{1}, v_{2}, w are elements of M with v_{1} ≤ v_{2}.

Now let A be a set of algebra generators for 𝔽_{p}G, all lying in the Jacobson radical J(𝔽_{p}G). Then M is the set of monomials in the free associative 𝔽_{p}- algebra on A. Write I for the relations ideal: the kernel of projection from this free algebra to 𝔽_{p}G. A word w ∈ M is called a tip if it is tha largest word in the support of some element of I; if not, it is called a nontip. That is, the nontips are the words whose images in 𝔽_{p}G are linearly independent of the images of their predecessors. It follows immediately that the images of the nontips are linearly independent in 𝔽_{p}G.

Lemma 2.2 With the above assumptions, the nontips form a basis for 𝔽_{p}G.

Proof. By Nakayama’s Lemma, J^{N}(𝔽_{p}G) is zero for some N. All algebra generators lie in J, and so only finitely many words are nonzero in 𝔽_{p}G. These span 𝔽_{p}G, and contain the nontips as a spanning subset.

By admissibility, the tips form an ideal in the free monoid M. This ideal has a unique smallest generating set. It consists of the minimal tips, a tip being called minimal if and only if all proper subwords are nontips. Define

G := {w − ν(w) | w a minimal tip} ,

where ν(w) is the linear combination of nontips which in 𝔽_{p}G equals w. Then G and the length N words together generate I. So, in the presence of the constraint A^{N} ⊆ I, the set G is a Gröbner basis for I: the unique completely reduced Gröbner basis for this ordering.

Remark 2.3 For the length-lexicographical and Jennings orderings, the constraint A^{N} ⊆ I is not necessary.

2.1 The length-lexicographical ordering

Denote by ℓ(w) the length of a word w ∈ M. Putting an ordering on the set A of algebra generators induces a lexicographical ordering ≤_{lex} on M. The lengthlexicographical ordering ≤_{LL} on M is then defined as follows:

w_{1} ≤_{LL} w_{2} if ℓ(w_{1}) < ℓ(w_{2}),
or same length, and w_{1} ≤_{lex} w_{2}.

This ordering is admissible. Moreover, each word w ∈ M has only finitely many predecessors under ≤_{LL}. We do not use the Buchberger algorithm to compute the Gröbner basis, because for p-group algebras it takes an unreasonable amount of time to stop. Rather, we exploit the fact that 𝔽_{p}G is finite-dimensional, which means that it is feasible to list all the nontips.

Computing a Gröbner basis Construct G in Magma using a faithful permutation representation. Choose minimal generators g_{1}, …, g_{r} for G, and set a_{i} = g_{i} − 1. Take the a_{i} as the set A of algebra generators. Record the matrix for the right multiplication action of each a_{i}, with basis the group elements.

Using these matrices, each word is constructed as a linear combination of the group elements, starting with the smallest word and proceeding in LL-order. Gaussian elimination allows us to distinguish the tips from the nontips. We stop when we have found all the nontips: their number is known in advance. The list of minimal tips is deduced from the list of nontips by word manipulation. Change of basis gives us the matrix for the multiplication action of each generator with respect to the basis of nontips, and we can read off ν(w) for each minimal tip w from these matrices.

2.2 The reverse length-lexicographical ordering

Again defined on the free monoid M on an ordered set A, this admissible ordering is the opposite of LL. Namely,

w_{1} ≤_{RLL} w_{2} if and only if w_{1} ≥_{LL} w_{2} .

Note that RLL is not a well-ordering.

Lemma 2.4 The RLL-nontips of length at least r constitute a basis for J^{r}(𝔽_{p}G). Hence the length r RLL-nontips are a basis for a complement of J^{r+1} in J^{r}.

Proof. The words of length at least r span J^{r}. If a linear combination of length r words lies in J^{r+1}, then the largest length r word involved is a tip.

Magma can compute the smallest N such that J^{N} is zero (using the Jennings series, the dimensions of all radical layers can be computed). So we could obtain the nontips by running through the words of length at most N in RLL order. But this could take forever. For example, if G is a Sylow 2-subgroup of the sporadic finite simple group Co_{3}, then N = 23 and A has size 4. Hence the number of words of length N is 2^{46}.

Computing a Gröbner basis A length r word is a tip if and only if it lies in the space spanned by its length r RLL-predecessors and by J^{r+1}(𝔽_{p}G). Using Gaussian elimination and the matrices for the algebra generators, we can calculate a basis for J^{r+1} from one for J^{r}. So we start with r = 0 and work through to r = N. All length r nontips are words of the form w.a with a ∈ A and w a length r − 1 nontip. We work through these words in RLL-order. Once we have the nontips, we proceed as for LL.

3 The Jennings ordering

For r ≥ 1, define F_{r}(G) to be the rth dimension subgroup of the finite p-group G. That is,

F_{r}(G) = {g ∈ G | g − 1 ∈ J^{r}(𝔽_{p}G)} .

Clearly G = F_{1}(G) ≥ F_{2}(G) ≥ · · ·. The F_{r} do eventually reach the trivial group, and they form a central series, the Jennings series for G. This series need not be strictly decreasing, however. These and more facts about the Jennings series are demonstrated in Section 3.14 of [Benson 1991]

Definition 3.1 Let G be a p-group of order p^{n}. Elements g_{1}, …, g_{n} of G are Jennings pc-generators for G if the first m_{1} elements g_{i} are minimal generators for F_{1}(G)/F_{2}(G), the next m_{2} are minimal generators for F_{2}/F_{3}, and so on.

Jennings pc-generators do yield a polycyclic presentation for G, as we now see.

Lemma 3.2 Let g_{1}, …, g_{n} be Jennings pc-generators for G. For each 1 ≤ i ≤ n, we have g_{i}^{p} ∈ ⟨g_{i+1}, …, g_{n}⟩; and [g_{i}, g_{j}] ∈ ⟨g_{j+1} …, g_{n}⟩ for 1 ≤ i < j ≤ n.

Proof. It is known that [F_{r}, F_{s}] ≤ F_{r+s} and that pth powers of elements of F_{r} lie in F_{pr}.

Example 3.3 Let G = ⟨a, b, c, ϕ⟩ be the following semidirect product group of order 32: the subgroup ⟨a, b, c⟩ is normal, and elementary abelian of order eight. The order of ϕ is four, and the effect of conjugation on the left by ϕ is

a ⟼ b ⟼ c ⟼ abc .

Then F_{2} = ⟨ab, ac, ϕ^{2}⟩ and F_{3} = ⟨ac⟩ are elementary abelian, and so a, ϕ, ab, ϕ^{2}, ac are Jennings pc-generators for G.

The last three generators are Jennings pc-generators for F_{2}. Another family of Jennings pc-generators for F_{2} is ac, ab, ϕ^{2}. This family cannot be extended to Jennings pc-generators for G, since [ϕ, ab] = ac. Hence to find Jennings pcgenerators for G, it is not enough to take minimal generators for G and add on Jennings pc-generators for F_{2}.

Definition 3.4 Let g_{1}, …, g_{n} be Jennings pc-generators for G. Then a_{1}, …, a_{n} are Jennings generators for the group algebra 𝔽_{p}G, where a_{i} = g_{i} − 1. We say a_{i} has dimension r if a_{i} ∈ J^{r}(𝔽_{p}G) \ J^{r+1}(𝔽_{p}G), or equivalently g_{i} ∈ F_{r} \ F_{r+1}.

Order the Jennings generators as follows: a_{1} < a_{2} < ⋯ < a_{n}. For a word w in these generators, define its dimension dim(w) in the obvious additive way:

dim(a_{i_{1}} … a_{i_{r}}) = ∑_{j=1}^{r} dim(a_{i_{j}}) .

Definition 3.5 The Jennings ordering is the following ordering on the monoid of words in the Jennings generators:

w_{1} ≤_{J} w_{2} if dim(w_{1}) > dim(w_{2}),
or dimensions equal and ℓ(w_{1}) < ℓ(w_{2}),
or same dimension and length, and w_{1} ≥_{lex} w_{2}.

Observe that the Jennings ordering is admissible; and that dim(w) ≥ ℓ(w) for each word w. The next result tells us that it is straightforward to calculate the Gröbner basis for the Jennings ordering.

Proposition 3.6 Let a_{1}, …, a_{n} be Jennings generators for 𝔽_{p}G. The minimal tips are the words a_{i}^{p} and a_{j}a_{k} with j < k. The nontips are the words a_{n}^{e_{n}}a_{n−1}^{e_{n−1}} … a_{1}^{e_{1}} with 0 ≤ e_{i} ≤ p − 1. A nontip w lies in J^{r} \ J^{r+1} if and only dim(w) = r.

Proof. We just have to show that a_{i}^{p} and a_{j}a_{k} (j < k) are tips. For then all nontips are of the form claimed, and the number of nontips equals the number of claimed nontips. So the nontips and hence the minimal tips are as claimed. The distribution in radical layers then follows from Jennings’ theorem (Theorem 3.14.6 in [Benson 1991]).

If dim(a_{i}) = r then a_{i}^{p} lies in 𝔽_{p}F_{pr}, which is generated by the a_{j} with dim(a_{j}) ≥ pr. Hence a_{i}^{p} is a linear combination of words in these a_{j}. Each such word either has dimension greater than pr or has length one. So a_{i}^{p} is a tip, since it has length p.

Similarly, if dim(a_{j}) = s and dim(a_{k}) = t, then c = [g_{j}, g_{k}] lies in F_{s+t}. Set γ = c − 1, so that γ ∈ 𝔽_{p}F_{s+t}. Arguing as above, γ is a linear combination of words smaller than a_{j}a_{k} or a_{k}a_{j}. Since g_{j}g_{k} = cg_{k}g_{j}, we have

a_{j}a_{k} = a_{k}a_{j} + γ + γa_{k} + γa_{j} + γa_{k}a_{j} ,

and the right hand side is a linear combination of words smaller than a_{j}a_{k}.

Example 3.7 Let G be the cyclic group of order four. Then Jennings pcgenerators for G are g_{1}, g_{2} with g_{1}^{2} = g_{2}, g_{2}^{2} = 1 and [g_{1}, g_{2}] = 1. The corresponding Jennings generators for 𝔽_{p}G are a_{1} = g_{1} − 1 and a_{2} = g_{2} − 1. The minimal tips are a_{1}^{2}, a_{1}a_{2} and a_{2}^{2}; the nontips are a_{2}a_{1}, a_{2}, a_{1}, 1 in ascending order; and the Gröbner basis is

a_{1}^{2} + a_{2} ,  a_{1}a_{2} + a_{2}a_{1} ,  a_{2}^{2} .

Remark 3.8 Jennings pc-generators are usually not minimal group generators. This means that there are relations involving length one words. However, the Jennings ordering does guarantee that all tips have length at least two.

Computing a Gröbner basis Get Magma to compute the Jennings series. Use this to pick Jennings pc-generators for G. The nontips and the minimal tips are known by Proposition 3.6. Proceed as for LL.

4 The implementation

In this section we provide an overview of the package Present, and describe the data structures used. Some components of Present are written in Magma code, others are written in C. The C components use M. Ringe’s C MeatAxe to handle vectors and matrices over finite fields.

Groups must be constructed in Magma as permutation groups. The function regularPermutationAction is provided to convert pc-groups (and hence matrix groups too) into permutation groups using the regular permutation action.

4.1 Selecting minimal generators

To choose minimal generators for a p-group G in pc-presentation, Present first asks Magma for the Frattini subgroup Φ(G), and sets H = Φ(G). Then it selects an element g ∈ G − H, adds this to the list of generators, and replaces H by ⟨g, H⟩. This is repeated until H is equal to G. At this point the elements g constitute a minimal generating set.

There remains the question of which element of G−H to select at each stage. Two generator selection methods were investigated:

• The most obvious method: pick g ∈ G−H completely at random. Minimal generators constructed in this way are called arbitrary minimal generators.

• Calculate the exponent of each element of G − H, and pick g at random from amongst those with the smallest exponent. Such minimal generators are called smallest exponent minimal generators.

The merits of these two methods are compared in Section 5. By default, Present uses the smallest exponent method for LL, and the arbitrary method for RLL.

4.2 The nontips tree

The group generators are passed to the C programs as a list of permutations. For the Jennings ordering, generator dimensions are passed too. The Gröbner basis is now determined by the method for the chosen ordering given above.

The nontips are words, and all proper subwords of a nontip are again nontips. Hence the most natural way to store the nontips is as a tree, in which the children of a word w are the nontips of the form w.a with a ∈ A, the set of algebra generators. On the other hand, the nontips constitute an ordered basis, and so we also want to be able to address them as an array.

In Present, the nontips are stored as a length |G| array of pathnodes. The class pathnode contains

• the word w itself, its array index and its length

• an array of pointers to its children, indexed by the elements of A. (If w.a is a tip, then the corresponding pointer is null.)

• a pointer to the parent word. Also, which child of the parent it is.

The nontips are stored in the array in ascending order for LL, and in descending order for RLL and the Jennings ordering. This means that the root of the tree is always located in the first entry of the array; and that the nontips tree can be built while the nontips are being determined.

For the second point, observe that the LL nontips are determined in ascending order. Also, the number of length r RLL nontips is known in advance, and they are determined in ascending order after all nontips of smaller length have been determined. Hence for LL and RLL, the index of each nontip is known the moment it is identified as a nontip.

Strictly, the Jennings nontips are an exception here. They are written down in lexicographical order, and then sorted into Jennings order.

4.3 The components of Present

The package Present consists of the package MakeBasis of Magma functions, and four C programs.

The Magma function makeBasis constructs nontips and action matrices for the LL and RLL orderings. A variant has a user-defined number of attempts at finding the smallest Gröbner basis. The function makeJenningsBasis constructs nontips and action matrices for the Jennings ordering. There is no need to have repeated attempts.

For each ordering, a flag allows the user to insist that the defining group generators are used. This eliminates the random component.

The C programs makeNontips and makeActionMatrices are invoked by the Magma functions to determine the nontips and the action matrices respectively. The program writeGroebnerBasis can then be used to write out the Gröbner basis and the minimal tips. The utility program groupInfo prints out relevant statistics on the groups by decoding the nontips file header.

5 Results and conclusions

The package Present was used to compare the orderings LL and RLL. The groups used in the comparison were: all 51 groups of order 32; all 267 groups of order 64; and eight Sylow p-subgroups of sporadic finite simple groups.

Define LL(G) to be the smallest size of a Gröbner basis for the relations ideal with respect to the LL ordering. Define RLL(G) similarly for RLL. Using Present we can obtain empirical approximations eLL(G) and eRLL(G) to these numbers.

By Propostion 3.6, all Gröbner bases for the Jennings ordering have the same size Je(G). This is \frac{1}{2}n(n + 1) for a group of order p^{n}.

5.1 Groups of order 32

There are 51 groups of order 32. The smallest Gröbner basis found in twenty attempts was recorded for each combination of: group, ordering (LL or RLL) and generator selection method (arbitrary or smallest).

For the RLL ordering, the generator selection method made no difference. For LL, smallest minimal generators yielded a smaller Gröbner basis in three cases: one less element for two groups, and three less for one group.

The comparative performance of the two orderings is shown below. The most extreme difference was for the group with Hall–Senior number 43, where eLL = 31 and eRLL = 10.

d := eLL − eRLL d < 0 d = 0 1 ≤ d ≤ 3 4 ≤ d ≤ 6 7 ≤ d ≤ 9 d ≥ 10 ; No. of groups  0  17  16  8  7  3

5.2 Groups of order 64

There are 267 groups of order 64. The smallest Gröbner basis found in twenty attempts was recorded for each combination of group, ordering and generator selection method.

For the RLL ordering, smallest minimal generators yielded a larger Gröbner basis in 63 cases, and a smaller Gröbner basis in one case. Each time, the difference was only one element. For LL, smallest minimal generators yielded a smaller Gröbner basis in 97 cases, with mean difference 3.3; and a larger Gröbner basis in 69 cases, with mean difference 4.6.

The comparative performance of the two orderings is shown below. The most extreme difference was for the group with Hall–Senior number 187, where eLL = 57 and eRLL = 10.

d := eLL − eRLL d < 0 d = 0 1 ≤ d ≤ 8 9 ≤ d ≤ 16 17 ≤ d ≤ 32 d ≥ 33 ; No. of groups  0  29  112  73  50  3

5.3 Sylow p-subgroups of sporadic finite simple groups

One of the main applications driving the development of group cohomology software is calculating the cohomology rings of sporadic finite simple groups. So Sylow p-subgroups of these groups are important examples for Present. Moreover, they are a good source of larger p-groups.

Arbitrary  Smallest exponent
Group Order Min Max μ σ Min Max μ σ
Syl_{2}(HS) 2^{9}  128 338 261 50 104 127 114 5
Syl_{2}(M_{24}) 2^{10}  433 906 706 101 183 543 373 81
Syl_{2}(Co_{3}) 2^{10}  502 871 690 92 212 574 405 85
Syl_{3}(McL) 3^{6}  126 333 258 50 133 245 197 43

Table 1: Generator selection methods compared for LL. Each sample size: 30.

Arbitrary  Smallest exponent
Group Order Min Max μ σ Min Max μ σ
Syl_{2}(HS) 2^{9}  10 13 11.0 1.1 11 13 11.9 0.9
Syl_{2}(M_{24}) 2^{10}  15 22 17.3 1.5 15 20 17.1 1.0
Syl_{2}(Co_{3}) 2^{10}  13 21 15.5 1.7 13 21 16.2 2.0
Syl_{3}(McL) 3^{6}  11 14 11.8 1.0 12 14 12.6 0.9

Table 2: Generator selection methods compared for RLL. Each sample size: 30.

The sensitivity of Gröbner basis size to generator choice was investigated by looking at four such Sylow p-subgroups. The program was run thirty times for each combination of: group, ordering (LL or RLL) and generator selection method. The results are shown in Tables 1 and 2. We give the smallest and largest sizes of Gröbner basis found, together with mean and standard deviation.

In Table 3, we compare smallest Gröbner basis sizes for all three orderings by looking at eight Sylow p-subgroups of sporadic finite simple groups. Each empirical value is based on at least twenty calculations.

5.4 Conclusions

Gröbner bases for the length-lexicographical ordering LL are consistently much larger than for the reverse length-lexicographical ordering RLL. In Table 3, the size of the smallest LL Gröbner basis lies between 14% and 33% of the group order. This means that the LL ordering is unsuitable for p-group algebras.

Sylow 2-subgroup of

Syl_{3} of
M_{22} HS M_{24} Co_{3} Suz Ru McL Suz
Order 2^{7} 2^{9} 2^{10} 2^{10} 2^{13} 2^{14}  3^{6} 3^{7}
eLL  34 104 150 236 2669 3111 126 417
eRLL  8 9 15 13 21 18 11 13
Je  28 45 55 55 91 105 21 28

Table 3: Smallest known Gröbner bases. Each sample size at least 20.

By contrast, RLL consistently yields very small Gröbner bases: the size behaving very roughly as the logarithm of the group order. Moreover, RLL allows one to read off the radical layers in the group algebra. Hence the RLL ordering is well-suited for computing with p-group algebras.

The Jennings ordering also seems to be suitable for computing with p-group algebras. Finding Jennings generators is easy, and it would appear that all Jennings generating sets are equally useful. Many properties of a Gröbner basis are invariants of the group’s order, including the size. Gröbner bases are not as small as for RLL, but this is compensated for by the fact that fewer multiplication operations are necessary to obtain the action of the average minimal tip.

The smallest exponent generator selection method seems to deliver a small LL Gröbner basis more often than the arbitrary method does: see Table 1. However, there are numerous exceptions amongst the groups of order 64. For the RLL ordering, all evidence suggests that the smallest exponent method should be avoided: it is no more reliable at yielding a small Gröbner basis than the arbitrary method, and sometimes misses the smallest Gröbner bases.

References

[Benson 1991] D. J. Benson. Representations and Cohomology I. Cambridge Stud. Adv. Math. 30. Cambridge Univ. Press, Cambridge, 1991.

[Farkas et al. 1993] D. R. Farkas, C. D. Feustel and E. L. Green. Synergy in the theory of Gröbner bases and path algebras. Canad. J. Math. 45 (1993), 727–739.

[Feustel et al. 1993] C. D. Feustel, E. L. Green, E. Kirkman and J. Kuzmanovich. Constructing projective resolutions. Comm. Algebra 21 (1993), 1869– 1887.

[D. Green 1997] D. J. Green. Constructing Projective Resolutions for p-groups. Vorlesungen Fachbereich Math. Univ. Essen 24 (1997), iv+55pp.

[D. Green 1999] D. J. Green. Computing minimal resolutions for p-groups: a storage-efficient Gröbner basis method. In preparation.

[E. Green et al. 1998] E. L. Green, Ø. Solberg and D. Zacharia. Minimal projective resolutions. Preprint, 1998.

Software availability The package Present is available at http://www.math. uni-wuppertal.de/˜ green/software.html, as is a copy of the C MeatAxe. The most recent version of the C MeatAxe is available at http://www-gap.dcs.st-and. ac.uk/˜ gap as a GAP 3 share package. The Magma home page is at http://www. maths.usyd.edu.au:8000/u/magma/.