ICMS

Jul 27, 2009 - Jul 31, 2009

Informatics Forum, University of Edinburgh

Organisers

Name	Institution
Holt, Derek	University of Warwick
Linton, Steve	University of St. Andrews
Roney-Dougal, Colva	University of St. Andrews

 

Short report

Computing in finite matrix groups has been an active area of research within Computational Group Theory for about 15 years and remains so today. This was nevertheless the first Workshop that was concerned specifically with that topic.

There are currently two major software packages, written in Magma and GAP, which are broadly capable of identifying the composition factors of a matrix group of dimension up to a few hundred over a moderately sized finite field.

The aims of the Workshop were to ascertain the current state of play, to educate and inspire the enthusiasm of younger researchers, to attempt to solve some challenge problems, and to make concrete plans for future research.

The high quality of the talks, the generous allocation of time for collaboration, and the focused theme all featured as highlights in participants' evaluations. Several new research relationships involving younger researchers were developed.

Future plans included: extending the methods to groups defined over infinite fields; determining which algorithms are polynomial; extending available facilities and making them usable by nonspecialists;
looking for new methods, such as computing symbolically rather than in specific groups. For several of these projects, specific work-plans were drawn up. Overall, the aims of he Workshop were achieved!

Download the full report here.

 

Introduction to workshop

Computing in finite permutation groups is feasible for groups of large order and degree, and facilities for carrying out such computations are available via GAP and MAGMA to the whole mathematical community. Their effective use requires no specialised knowledge of computational group theory.

The same is not true for computing in finite matrix groups, even in small degree over moderately sized finite fields. As an example, to perform many types of computation in GAP or MAGMA in Sp(8,7), it is necessary to work in its permutation representation of degree 960800, which is possible but very slow, and is about at the limit of feasiblity for general purpose computations in finite matrix groups. This is a consequence of large, quasisimple matrix groups generally having no subgroups of low index. It is a serious issue, because there are regular requests from a wide variety of mathematicians for information on items such as the maximal subgroups or the character tables of various matrix groups, particularly the classical groups over finite fields.

Over the past 15 years basic practical algorithms for finite matrix groups have been developed. This is collectively called the matrix group recognition project (MGRP). Software is now available that can generally compute a composition series of such a group of degree up to a few hundred. However, these programs are currently usable only by experts, and relatively few facilities are available for performing further computations.

The meeting will be concerned with two principal current aims of the MGRP:

• Complete the remaining gaps in the Composition Tree program, and enable the computation of a chief series passing through a certain series of three characteristic subgroups.
• Use this as a starting point for further algorithm design for finite matrix groups, such as Sylow subgroups, conjugacy classes of elements and maximal subgroups, centralizers, normalizers and intersections of subgroups, ordinary (eventually modular) character tables, subspace stabilisers, tensor decomposition stabilisers, etc.

 

Arrangements

Registration fee

A registration fee is payable in advance. Delegates will be contacted directly with information about this.

 

Accommodation

Delegates who have asked ICMS to book their accommodation will be housed in single occupancy ensuite rooms. Rooms have been booked in two locations: The Kenneth MacKenzie Suite in the city centre, and Chancellor's Court in the Pollock Halls area.

A map of the location of the two accommodation venues and the location of the workshop venue can be found here.

 

Photos

There are two photos of the workshop delegates available for download. Both files are over 1 MB in size so they might take a little while to download over a slow connection. Download photo one and photo two.

Programme

Please note that this programme is subject to change

Monday 27 July

10.30 - 11.00	Registration and coffee/tea
11.00 - 12.00	Eamonn O'Brien (University of Auckland) A new implementation of CompositionTree Link to pdf of slides
12.00 - 14.00	Lunch break (Sandwich buffet served)
14.00 - 15.00	Akos Seress (The Ohio State University) Polynomial-time theory of matrix groups
15.00 - 16.00	Panel discussion
16.00 - 16.30	Coffee/tea
16.30 - 17.00	Frank Lübeck (RWTH Aachen) Computing defining characteristic representations
17.00 - 17.30	Csaba Schneider (University of Lisbon) Constructive membership testing in black-box groups Link to pdf of slides
Evening	Research "Cambridge style"; venue TBA

 

Tuesday 28 July

10.00 - 11.00	Charles Leedham-Green (Queen Mary University of London) Seeking and finding
11.00 - 11.30	Coffee/tea
11.30 - 12.30	Max Neunhoffer (University of St Andrews) The current state of the recog package Link to pdf of slides Link to pdf of handout
12.30 - 15.30	Lunch break and time for collaborations
15.30 - 16.00	Coffee/tea
16.00 - 16.30	Derek Holt (University of Warwick) Rearranging the terms of a composition series
16.30 - 17.00	Peter Brooksbank (Bucknell University) Matrix group algorithms via matrix algebras
	Knowledge Transfer event
17.15 - 17.30	Registration for Knowledge Transfer participants (N/A for workshop delegates)
17.30 - 17.45	Steve Linton (University of St Andrews) Welcome and Introduction to Computational Group Theory Link to pdf of slides
17.45 - 18.00	Herbert Fruchtl (EaStCHEM) The computing needs of EaStCHEM
18.00 - 18.15	TBA
18.15 - 19.30	Wine reception and time for informal discussion
19.30	Dinner at Pink Olive, 55-57 West Nicolson Street

 

Wednesday 29 July

10.00 - 10.30	Alice Niemeyer (University of Western Australia) Estimating proportions of elements in finite classical groups
10.30 - 11.00	Cheryl Praeger (University of Western Australia) Estimation problems in finite classical groups Link to PDF of slides
11.00 - 11.30	Coffee/Tea
11.30 - 12.00	John Bray (Queen Mary University of London) Title TBA
12.00 - 12.30	Steve Glasby (Central Washington University) Random remarks on randomness Download PDF of slides
12.30 - 15.30	Lunch break and time for collaboration
15.30 - 16.00	Coffee/tea
16.00 - 16.30	Bill Unger (University of Sydney) Matrix groups in Magma
16.30 - 17.00	Alexander Hulpke (Colorado State University) Centralizers and Normalizers in the general linear group Link to pdf of slides
17.00 - 17.30	George Havas (The University of Queensland) On computing efficient presentations for simple groups Link to pdf of slides

 

Thursday 30 July

10.00 - 10.30	Dane Flannery (National University of Ireland, Galway) Deciding finiteness of matrix groups Link to pdf of slides
10.30 - 11.00	Scott Murray (University of Sydney) Computation with the Lie correspondence Link to pdf of slides
11.00 - 11.30	Coffee/Tea
11.30 - 12.00	Richard Parker High performance Meataxe Link to pdf of slides
12.00 - 12.30	Tobias Rossmann (National University of Ireland, Galway) Irreducibility and primitivity testing of finite nilpotent matrix groups over number fields Link to PDF of slides
12.30 - 15.30	Lunch break and time for collaboration
15.30 - 16.00	Tea/coffee
16.00 - 16.30	James Wilson (Ohio State University) Unique decompositions of large unipotent groups Link to pdf of slides
16.30 - 17.00	Damien Burns (University of Auckland) A constructive recognition algorithm for classical groups
19.00	Workshop dinner at Blonde, 75 St Leonard's Street

 

Friday 31 July

10.00 - 10.30	Kay Maagard (University of Birmingham) Constructive recognition of exceptional groups of Lie type
10.30 - 11.00	Felix Noeske (RWTH Aachen) Matching simple modules of condensed algebras
11.00 - 11.30	Coffee/Tea
11.30 - 12.30	Panel discussion
12.30 - 13.30	Lunch break
13.30 - 14.00	Gerhard Hiss (RWTH Aachen) Imprimitive irreducible representations of finite quasisimple groups Link to PDF of slides

Presentations:

Presentation Details
Brooksbank, Peter
Matrix group algorithms via matrix algebras
View Abstract Hide Abstract
In this talk I will discuss some algorithmic problems for matrix groups that appear to be best approached via matrix algebras of one form or another. The basic idea is to associate to a certain type of group problem a related algebra problem that can be solved efficiently. One then translates that solution constructively into a solution of the original group problem. This philosophy has been applied successfully in joint work with Eamonn O'Brien. More recently, in joint work with James Wilson, a method was devised to construct the intersection of a collection of classical groups defined naturally on a common (finite) vector space of odd characteristic. In this talk I will describe our approach to this problem via *-algebras (algebras equipped with an involutory anti-automorphism). One by-product of our work is a suite of algorithms that efficiency determines the structure of such algebras.
Burns, Damien
A constructive recognition algorithm for classical groups
View Abstract Hide Abstract
Let $G < GL(n; F)$ be a classical group in its natural representation, defined over a field $F$ of odd characteristic. Suppose $X C GL(d; F)$ generates a group $H$ that is isomorphic to $G$. We define a set $E$ of standard generators for $G$ and describe an algorithm to constuct the image of $E$ in $H$ as words on $X$.
Flannery, Dane
Deciding finiteness of matrix groups
View Abstract Hide Abstract
Deciding finiteness is a fundamental computational problem in any class of potentially infinite groups. For an arbitrary class of groups the problem may not even be decidable. We have shown that for finitely generated linear groups over an arbitrary field the problem is decidable, and have developed a new technique for deciding finiteness. Using that technique we have obtained practical algorithms for deciding finiteness of matrix groups over function fields. Together with algorithms of Babai et. al., this affords a solution of the finiteness problem for matrix groups over any field. (Joint work with Alla Detinko.)
Glasby, Stephen
Random remarks on randomness
View Abstract Hide Abstract
This talk focuses on the problem of selecting random elements, particularly from matrix groups over a field. Problems arise when the field is infinite: should we use uniform selection from a given finite subset, or should we consider translation-invariant measures? One approach involves bounding the number of roots of a non-zero multivariate polynomial in a hypercube, another approach for compact classical groups involves factorizations of matrices.
Havas, George
On computing efficient presentations for simple groups
View Abstract Hide Abstract
There is much interest in finding short presentations for the finite simple groups. Indeed it has been suggested that all these groups are efficient in a technical sense. I will describe methods for computing such efficient presentations and give examples of new efficient presentations.
Hiss, Gerhard
Imprimitive irreducible representations of finite quasisimple groups
View Abstract Hide Abstract
This is a report on an ongoing project with Bill Huson and Kay Magaard to determine the imprimitive irreducible representations of finite quasisimple groups. I will mostly explain the - somewhat unexpected - results and only shortly comment on the methods used. Of course, I will also discuss the relevance of our results to matrix group recognition.
Holt, Derek
Rearranging the terms of a composition series
View Abstract Hide Abstract
The "Composition Tree" algorithm of Leedham-Green and O'Brien computes what is essentially a composition series of a large finite matrix or permutation group G. Experience has shown that, for further structural computations in G, a chief series that passes through three specific characteristic subgroups of G (the solvable radical L of G, the group M such that M/L = socle(G/L), and the kernel K of the permutation action of G on the nonabelian simple factors of M/L induced by conjugation) is particularly useful. In this talk, we describe a method of computing such a chief series starting from a composition tree. The method can be described as rearranging the terms of the given composition series. The performance of an experimental implementation of part of this procedure is encouraging.
Hulpke, Alexander
Centralizers and Normalizers in the general linear group
View Abstract Hide Abstract
Centralizer computation in the general linear group is essentially a normal form problem. I want to try to use this asa step towards computing normalizers of comparatively small subgroups.
Leedham-Green, Charles
Seeking and finding
View Abstract Hide Abstract
The matrix recognition project is very strongly based on random searches. Efficient searching is not only of practical importance, it reduces the theoretical complexity as well. Joint work with H. Baarnhielm.
Lübeck, Frank
Computing defining characteristic representations
View Abstract Hide Abstract
This is a report on a software package I'm currently developing (using GAP and CHEVIE). It is for computing characters and representations of groups of Lie type in defining characteristic. During this workshop we can find out how parts of this package can be used in the matrix group recognition project and what may be interesting additional functionality in this context.
Magaard, Kay
Constructive recognition of exceptional groups of Lie type
View Abstract Hide Abstract
I will report on algorithms for constructively recognizing exceptional groups of Lie type.
Murray, Scott
Computation with the Lie correspondence
View Abstract Hide Abstract
The matrix group recognition project deals with abstract matrix groups over finite fields. However, many of the groups that occur can also be viewed as connected algebraic groups. Examples include the classical groups and other finite groups of Lie type. I will discuss applications of the Lie correspondence between connected groups and Lie algebras. This correspondence fails to be one-to-one over finite fields, and I will discuss ways of avoiding the problems caused by this failure.
Neunhoeffer, Max
The current state of the recog package
View Abstract Hide Abstract
I will give a talk/demonstration about the current state of the matrix group recognition package "recog" in GAP. I will demonstrate what already works well and what does not and try to give an idea why. My major goal for this talk is to give the audience a feeling what things are currently computationally feasible using this software.
Niemeyer, Alice
Estimating proportions of elements in finite classical groups
View Abstract Hide Abstract
For the complexity analysis of many algorithms we need precise estimates of the proportions of certain elements in finite classical groups. We consider subsets $Q$ of a finite simple group $G$ of Lie type which exhibit certain closure properties. We translate the problem of determining the proportion of elements of $G$ that lie in $Q$ into two subproblems: * Determine the proportion of elements of $Q$ in the maximal tori of $G$ * Determine the proportions of certain relevant elements in permutation groups. (Joint work with Cheryl Praeger)
Noeske, Felix
Matching simple modules of condensed algebras
View Abstract Hide Abstract
Let A be a finite dimensional algebra over a finite field F. Condensing an A-module V with two different idempotents e and e' leads to the problem that to compare the composition series of Ve and Ve', we need to match the composition factors of both modules. In other words, given a composition factor S of Ve, we have to find a composition factor S' of Ve' such that there exists a composition factor of V with e S and e' S', or prove that no such S' exists. In this talk, we present a computationally tractable solution to this problem, and illustrate how its application was a crucial step in the recent proof of the 3-modular character table of the sporadic simple Harada Norton group.
O'Brien, Eamonn
A new implementation of CompositionTree
View Abstract Hide Abstract
Over the past year, we have developed a new implementation in Magma of the composition tree algorithm, and also developed the necessary machinery to construct a chief series for a linear group. We report on this implementation and consider its limitations.
Parker, Richard
High performance Meataxe
View Abstract Hide Abstract
Modern computers have cache memory that is much faster than ordinary memory. Changes are appropriate to the way matrices are handled over finite fields to take account of this.
Praeger, Cheryl
Estimation problems in finite classical groups
View Abstract Hide Abstract
Estimating the proportions of various types of elements in simple groups is often important for bounding the error in Monte Carlo algorithms for computing in such groups. The problem of finding good estimates in classical groups seems to be intertwined with similar (or sometimes not so similar) problems for permutation groups.
Rossmann, Tobias
Irreducibility testing of finite nilpotent matrix groups over number fields
View Abstract Hide Abstract
We describe an algorithm which tests whether a finite nilpotent matrix group over a number field is irreducible. We also comment on our implementation of this algorithm.
Schneider, Csaba
Constructive membership testing in black-box groups
View Abstract Hide Abstract
We generalise a sifting procedure introduced originally by Sims for computation with permutation groups. Our version is given in the context of black-box groups, and is based on a chain of subsets rather than a subgroup chain. We apply our procedure to solve the constructive recognition problem for black-box sporadic simple groups and black-box special linear groups. Our algorithms are implemented in the GAP computational algebra system and experiments show that they work well in practice. Their theoretical complexity is also calculated. This is joint work with Sophie Ambrose, Scott Murray, Max Neunhoeffer, and Cheryl Praeger.
Seress, Akos
Polynomial-time theory of Matrix groups
View Abstract Hide Abstract
There is a Monte Carlo algorithm that given $G le GL(n,p^e)$ with odd $p$, computes $|G|$ and a composition series in $G$. The algorithm can also test membership in $G$ constructively, which means that it constructs a straight-line program from the input generators to any given $g in G$. If $G$ has no composition factors of exceptional Lie type then the algorithm can be upgraded to Las Vegas. If $p=2$ then we can do all the tasks above in groups with no exceptional factors. The running time is polynomial in the input length, using number theory oracles for factorization and discrete logarithm. The algorithm is based on the black-box group approach of Babai and Beals, but it also uses recent results utilizing centralizer of involution computations. The talk is based on the paper Laszlo Babai, Robert Beals, Akos Seress: Polynomial-time theory of matrix groups, Proc. 41st STOC (2009), pp. 55--64.
Unger, William
Matrix Groups in Magma
View Abstract Hide Abstract
I will present an overview of the facilities in Magma for computing the structure of matrix groups over finite fields. We begin by giving a brief review of recent development of the fast linear algebra tools important in Matrix Group Recognition. Magma's traditional BSGS approach to computing group structure has recently been augmented by trivial Fitting group algorithms, in both the matrix and permutation group cases. After giving a brief summary of current TF algorithms, we outline plans to transfer these algorithms to the composition tree TF model. We conclude with a brief summary of the status in Magma of recognition algorithms for quasi-simple matrix groups, and algorithms for determining their structural properties.
Wilson, James
Unique decompositions of large unipotent groups
View Abstract Hide Abstract
Groups of unipotent matrices (and general p-groups) can seem stunningly similar when compared through quotients of the various central series. An alternative is to decompose groups into various products of subgroups (by means of direct, central, and a host of related decompositions). A theorem is proved that these decompositions are unique. Another shows that there are roughly as many decomposable groups are indecomposable groups. Finally, polynomial time algorithms are given which have handled groups of order p^256 in under a half-hour, and without restrictions on p. [This reports on joint work with P. A. Brooksbank.]

Participants

Name	Institution
Bray, John	Queen Mary, University of London
Britnell, John	University of Leeds
Brooksbank, Peter	Bucknell University
Burns, Damien	University of Auckland
Carlson, Jon	University of Georgia
Coutts, Hannah	University of St Andrews
Dietrich, Heiko	Technical University of Braunschweig
Flannery, Dane	National University of Ireland, Galway
Glasby, Stephen	Central Washington University
Havas, George	The University of Queensland
Hiss, Gerhard	RWTH Aachen
Holt, Derek	University of Warwick
Hulpke, Alexander	Colorado State University
Leedham-Green, Charles	Queen Mary, University of London
Linton, Steve	University of St. Andrews
Lübeck, Frank	RWTH Aachen
Lux, Klaus	University of Arizona
Magaard, Kay	University of Birmingham
Malle, Gunter	University of Kaiserslautern
Murray, Scott	University of Sydney
Neunhoeffer, Max	University of St Andrews
Niemeyer, Alice	University of Western Australia
Noeske, Felix	RWTH Aachen
O'Brien, Eamonn	University of Auckland
Parker, Richard	None
Praeger, Cheryl	University of Western Australia
Roney-Dougal, Colva	University of St. Andrews
Rossmann, Tobias	NUI Galway
Ryba, Alex	City University of New York
Schneider, Csaba	University of Lisbon
Seress, Akos	The Ohio State University
Unger, William	University of Sydney
Wilson, James	The Ohio State University
Wilson, Rob	Queen Mary, University of London
Yalcinkaya, Sukru	University of Western Australia