ICMS 2014 Session: Software, algorithms, and applications of Computational Group Theory

Organizers

• Heiko Dietrich (Monash University, Melbourne, Australia)
• Alexander Hulpke (Colorado State University, Fort Collins, CO, USA)

Aim and Scope

Topics (including, but not limited to)

Software design for, or new algorithmic developments with implementations (stand-alone or as part of larger packages) for:

• Group Theory
• Semigroup Theory
• Lie Algebras
• Association Schemes
• Combinatorial structures, utilizing symmetries.
• new mathematical results in these areas (such as classifications of objects) that only were feasible using software.

Publications

• A short abstract will appear on the permanent conference web page (see below) as soon as accepted.
• An extended abstract will appear on the permanent conference web page (see below) as soon as accepted.
  It will also appear on the proceedings that will be distributed during the meeting.

Submission Guidelines

• If you would like to give a talk at ICMS, you need to submit first a short abstract and then later an extended abstract. See the guideline for the details.
  Please send your submission by email to both organizers and use ICMS 2014 as subject: Heiko Dietrich and Alexander Hulpke.

Talks/Abstracts

1. Alexander Hulpke (Colorado State University, USA)
   Software for Groups: Theory and Practice
   Over the last two decades software has become an accepted tool in group theory. But it often seems hard to predict which calculations will be easy in practice, and which ones are not feasible at all. Complexity analysis can be helpful, but does not always give a full picture. I will survey what methods are generally available, which ones only in theory, and what obstacles, sometimes involving algorithmic problems in other areas of mathematics, lie in the way of attacking problems that are currently infeasible.

2. Şükrü Yalçinkaya (Istanbul University, Istanbul, Turkey)
   New approaches in black box group theory
   (joint work with Alexandre Borovik)
   Black box groups are introduced as an idealised setting for randomised algorithms for solving permutation and matrix group problems in computational group theory. A black box group is a black box (or an oracle, or a device, or an algorithm) operating with binary strings of uniform length which encrypt (not necessarily in a unique way) elements of some finite group. Group operations, taking inverses and deciding whether two strings represent the same group elements are done by the black box. In this context, a natural task is to find a probabilistic algorithm which determines the isomorphism type of a group within given arbitrarily small probability of error. More desirable algorithms, constructive recognition algorithms, are the ones producing an isomorphism between a black box copy of a finite group and its natural copy. In this talk I will introduce a new approach in black box group theory which deals with black box group problems in the category of black boxes and their morphisms. This enables us to enrich black box groups by actions of outer autmorphisms like constructing Frobenius map or a diagonal automorphism of projective special linear groups. I will focus on a polynomial time construction of a black box projective plane over a black box field and constructive recognition problem for projective general linear groups. In particular, the solution of an old problem about constructing a unipotent element in groups of Lie type of odd characteristic will be presented.

3. Bettina Eick (TU Braunschweig, Germany)
   Approximating generators for integral arithmetic groups
   A rational algebraic group \(G(\mathbb{Q})\) is a subgroup of \(\text{GL}(n,\mathbb{Q})\) defined by a finite set of polynomial equations \(f_1, \ldots, f_l \in \mathbb{Q}[x_1, \ldots,x_{n^2}]\). More precisely, if \(\overline{g} \in \mathbb{Q}^{n^2}\) denotes the list of the entries of \(g \in \text{GL}(n, \mathbb{Q})\), then \(G(\mathbb{Q}) = \{ g \in \text{GL}(n, \mathbb{Q}) \mid f_i(\overline{g}) = 0 \mbox{ for } 1 \leq i \leq l \}\). The integral arithmetic groups associated to \(G(\mathbb{Q})\) are the subgroups of finite index in \(G(\mathbb{Z}) = G(\mathbb{Q}) \cap \text{GL}(n,\mathbb{Z})\). Borel and Harish-Chandra proved that every integral arithmetic group is finitely generated. Grunewald and Segal showed that the construction of a finite set of generators for an integral arithmetic group is an algorithmically decidable problem. However, a practical algorithm to construct such a set of generators is not available at current. In this talk we describe a software package for the computer algebra system GAP which allows to approximate generators for \(G(\mathbb{Z})\) via computations in finite matrix groups of the type \(\text{GL}(n, \mathbb{Z}/m\mathbb{Z})\). We also discuss other approaches towards computations with arithemtic groups including applications of algebraic geometry.

4. Heiko Dietrich (Monash University, Australia)
   A GAP package for computing with real semisimple Lie algebras
   (joint work with Paolo Faccin and Willem de Graaf)
   The structure theory of complex semisimple Lie algebras uses many combinatorial objects such as root systems, Weyl groups, and Dynkin diagrams, which makes the theory accessible for computer investigations. Computer algebra systems, like GAP, Magma, and LiE, contain software for computing with complex Lie algebras. Also the real semisimple Lie algebras are classified, and there exists a detailed structure theory. However, with the exception of the ATLAS project (USA), there has not been much effort to develop software for computing with real semisimple Lie algebras. We report on the functionality and the underlying theory of our GAP package 'CoReLG' (Computing with Real Lie Groups); it provides functions to construct real semisimple Lie algebras, to check for isomorphisms, and to compute Cartan decompositions, Cartan subalgebras, and nilpotent orbits.

5. Attila Egry-Nagy (University of Western Sydney, Australia)
   Bacterial Genomics and Computational Group Theory
   (joint work with Andrew Francis and Volker Gebhardt)
   Bacterial genomes can be modelled as permutations of conserved regions. These regions are sequences of nucleotides that are identified for a set of bacterial genomes through sequence alignment, and are presumed to be preserved through the underlying process, whether through chance or selection. Once a correspondence is established between genomes and permutations, the problem of determining the evolutionary distance between genomes (in order to construct phylogenetic trees) can be tackled by use of group-theoretical tools such as the word distance in Cayley graphs, stabilizer subgroups for modelling biological constraints, using presentations for finding geodesic words, etc. Most of the groups involved in this research are well-studied (symmetric, hyperoctahedral), but the generating sets are derived from models of the biological processes, and often have different properties from standard generating sets. Furthermore, the number of regions we need to calculate with are beyond the limits of simple brute-force methods. In this talk we describe how the computational tools are used in these biological projects, and what are the algorithms that still need to be developed. We also briefly introduce our GAP package BioGAP.

6. Attila Egry-Nagy (University of Western Sydney, Australia)
   Cascade (De)Compositions of Finite Transformation Semigroups and Permutation Groups
   (joint work with James D. Mitchell and Chrystopher L. Nehaniv)
   Wreath products are widely used theoretical constructions in group and semigroup theory whenever one needs to build a composite structure with hierarchical relations between the building blocks. However, from a computational/engineering perspective they are less useful since wreath products are subject to combinatorial explosions and we are often interested only in substructures of them. Cascade products precisely build these substructures by defining the hierarchical connections explicitly using dependency functions. As input, given a group or a semigroup with unknown internal structure, the goal of cascade decomposition algorithms is to come up with a list of simpler building blocks and put them together in a cascade product, which realizes in some sense the original group or semigroup. Roughly speaking, for permutation groups, cascade product decompositions can be interpreted as putting the inner workings of the Schreier-Sims algorithm (generalized to any subgroup chain) into an external product form, therefore one gets an isomorphism in the group case. For semigroups, Krohn-Rhodes decompositions can be computationally represented by cascade products of transformation semigroups. In this talk we describe how the GAP package SgpDec (sgpdec.sf.net) implements cascade products and decomposition algorithms and we also give a few application scenarios.

7. Raimundas Vidunas (National Kapodistrian University of Athens, Greece)
   Computation of genus 0 Belyi functions
   (joint work with Mark van Hoeij)
   Belyi functions is a captivating field of research in algebraic geometry, complex analysis, Galois theory. However, computation of Belyi functions of degree over 20 is still considered hard. If the desired branching pattern is nearly regular, pull-back transformations of hypergeometric equations to Fuchsian equations with just a few singularities can be used. This allows computation of Belyi functions of degree 60 and beyond. An implementation in Maple for computing genus 0 Belyi functions will be presented. The implementation is available at http://users.uoa.gr/~rvidunas/ComputeBelyi.mpl.

8. Yasuhiro Momose (Shinshu University, Japan)
   On computation of the first Baues--Wirsching cohomology of a freely-generated small category
   (joint work with Yasuhide Numata)
   The Baues--Wirsching cohomology is one of the cohomologies of a small category. The coefficient is a functor from the category of factorizations to the category of vector spaces, which is called a natural system. It is known that the Baues--Wirsching cohomology is a generalization of the cohomology of a group, the singular cohomology of the classifying space of a small category, and so on. The Baues--Wirsching cohomology is an invariant for the equivalence of small categories. To compute the Baues--Wirsching cohomology is important in this sense. It is known that if the coefficient is the composition of a functor and the target functor, then the zeroth Baues--Wirsching cohomology is isomorphic to the limit of the functor. It is also known that the Baues--Wirsching cohomology vanishes at second and more when the small category is generated by a finite quiver freely. Therefore, we are interested in describing the first Baues--Wirsching cohomology in the case where the small category is generated by a finite quiver freely and the coefficient is a natural system obtained by the composition of a functor and the target functor. of the small category generated by a finite quiver freely. We give an algorithm to obtain generators of the vector space of inner derivations. It is known that there exists a surjection from the vector space of derivations of the small category to the first Baues--Wirsching cohomology whose kernel is the vector space of inner derivations. We apply our algorithm to some examples of finite quivers to calculate the first Baues--Wirsching cohomology. <\ol>