We introduce methods for enumerating mixed orthogonal arrays of strength 3 and determine most of the arrays with run size up to 100.
A database of mixed orthogonal arrays based on this paper is also available.
We present algorithms to compute with relative root subgroups of twisted reductive groups. Given a Galois cocycle specifying a twisted form, we can find the relative root datum and Tits index, and carry out operations involving root elements. We can also find a presentation of the unipotent subgroup. Given a Tits index and the anisotropic subgroup, we can determine a cocycle with that index, if one exists.
We investigate the structure of the normaliser N in GLd(k) of the orthogonal omega group. We develop algorithms to compute the spinor norm, and hence to construct a homomorphism from N with kernel the omega group. These algorithms run in low-degree polynomial time (with a discrete log oracle in some cases) and are implemented in Magma. We also present similar algorithms for the normalisers of the other quasisimple classical groups.
We give an efficient Las Vegas type algorithm for Lang's Theorem in split connected reductive groups defined over finite fields of characteristic greater than 3. This algorithm can be used to construct many important structures in finite groups of Lie type. We use an algorithm for computing a Chevalley basis for a split reductive Lie algebra, which is of independent interest. For our time analysis we derive that the proportion of reflection derangements in a Weyl group is less than 2/3.
I have also written a short note on applying Lang's Theorem to groups of Lie type. This is based on a result in the book by Digne and Michel.
The unipotent groups are an important class of algebraic groups. We show that techniques used to compute with finitely generated nilpotent groups carry over to unipotent groups. We concentrate particularly on the maximal unipotent subgroup of a split reductive group and show how this improves computation in the reductive group itself.
We describe automated methods for constructing nonisomorphism proofs for pairs of graphs. The proofs can be human-readable or machine-readable. We have developed a proof generator for graph nonisomorphism, which allows users to input graphs and construct a proof of (non)isomorphism.
The proof constructor is accessible online.
We demonstrate a relationship between the representation theory of Borel subgroups and parabolic subgroups of general linear groups. In particular, we show that the representations of Borel subgroups could be computed from representations of certain maximal parabolic subgroups.
We describe two methods for computing with the elements of untwisted groups of Lie type: using the Steinberg presentation and highest weight representations. We give algorithms for element arithmetic within the Steinberg presentation. Conversion between this presentation and linear representations is achieved using a new generalisation of row and column reduction.
We describe the integration of permutation group algorithms with proof planning. We consider eight basic questions arising in computational permutation group theory, for which our code provides both answers and a set of certificates enabling a user, or an intelligent software system, to provide a full proof of correctness of the answer. To guarantee correctness we use proof planning techniques, which construct proofs in a human-oriented reasoning style. This gives the human mathematician the necessary insight into the computed solution, as well as make it feasible to check the solution for relatively large groups.
We show that the product replacement algorithm can be used be produce random elements of the Monster group. These random elements are shown to have the same distribution of element orders as uniformly distributed random elements after a small number of steps.
We present some new variations on the product replacement algorithm, together with some basic analysis and conjectures.
We compute conjugacy classes in maximal parabolic subgroups of the general linear group. This computation proceeds by reducing to a ``matrix problem''. Such problems involve finding normal forms for matrices under a specified set of row and column operations. We solve the relevant matrix problem in small dimensional cases. This gives us all conjugacy classes in maximal parabolic subgroups over a perfect field when one of the two blocks has dimension less than 6. In particular, this includes every maximal parabolic subgroup of GLn(k) for n < 12 and k a perfect field. If our field is finite of size q, we also show that the number of conjugacy classes, and so the number of characters, of these groups is a polynomial in q with integral coefficients.
We present a "practical" algorithm to construct random elements of a finite group. We analyse its theoretical behaviour and prove that asymptotically it produces uniformly distributed generating tuples of elements. We discuss tests to assess its effectiveness and use these to decide when its results are acceptable for some matrix groups.
We consider the application of the Schreier-Sims algorithm and its variations to matrix groups defined over finite fields. We propose a new algorithm for the selection of the base points and demonstrate that it both improves the performance of the algorithm for a large range of examples, and significantly extends the range of application. In particular, the random Schreier-Sims algorithm, with this enhancement, performs extremely well for almost simple groups.
The implementation of the random Schreier-Sims algorithm used for this paper is also available.
Morgenstern (1995) claimed to have constructed fundamental domains for congruence subgroups of the lattice group Gamma = PGL2(Fq[t]), and subgraphs providing the first known examples of linear families of bounded concentrators. His method was to construct the fundamental domain for a congruence subgroup as a `ramified covering' of the fundamental domain for Gamma on the Bruhat-Tits tree X = Xq+1 of G = PGL2(Fq((t-1))). We prove that Morgenstern's constructions do not yield the desired ramified coverings, and in particular yield graphs that are not connected in characteristic 2. It follows that Morgenstern's graphs cannot be quotient graphs by the action of congruence subgroups on the Bruhat-Tits tree. Moreover, subgraphs of Morgenstern's graphs which he claims to be expanders are also not connected. We clarify the construction of Morgenstern and we prove that his full graphs are connected only in odd characteristic. We also repair his constructions of ramified coverings. We construct fundamental domains for congruence subgroups of SL2(Fq[t]) and PGL2(Fq[t]) as ramified coverings, and we give explicit graphs of groups for a number of congruence subgroups. We thus provide new families of graphs whose level 0 - 1 subgraphs potentially have the expansion properties claimed by Morgenstern.
Describes a Magma package for Lie theoretic computation, including root data, Coxeter groups, complex reflection groups, the Steinberg presentation for groups of Lie type, and their representations over the natural field.
This is an introduction to data structures for permutation groups with a proof-theoretic flavour.
The minimal faithful permutation degree of a finite group G, denoted by mu(G) is the least non-negative integer n such that G embeds inside the symmetric group Sym(n). In this paper, we outline a Magma proof that 10 is the smallest degree for which there are groups G and H such that mu(G x H) < mu(G) + mu(H).
We present a new structural framework for computational group theory, based on chains of subgroups. This extends existing methods, such as Schreier-Sims techniques for permutation groups. This framework is now a part of the GAP 4 computational algebra system. It will be useful for implementing the matrix group recognition project.