ICMS 2020 Session: Groups and group actions
All sessions
Organizers
Aims and Scope
This session is for facilitating the communication among
the researchers and the developers and the users of computer algebra software, with an
emphasis on group theoretic algorithms.
Topics (including, but not limited to)
- Methods and algorithms for permutation groups,
matrix groups and finitely presented groups
- Applications of group theoretic algorithms
- State of the art of methods for finite and infinite matrix groups
- Implementation of algorithms in existing computer algebra software
Publications
-
A short abstract will appear on the permanent conference web page (see below) as soon as accepted.
-
An extended abstract may be submitted for the conference proceedings that will be distributed during the meeting.
-
A journal special issue consisting of full papers will be organized immediately after the meeting.
Talks/Abstracts (preliminary version, in alphabetical order)
Please note: The talks are given via pre-recorded videos, and questions can be asked
at the discussion sessions.
A full timetable can be found at the bottom of this page:
Homepage virtual ICMS 2020
Wednesday 2-2.30 pm:
Rebecca Waldecker, Chris Jefferson, and (hopefully!) Sergio Siccha.
Wednesday 3.50-4.20 pm:
Max Horn, Tobias Moede and Alexander Hulpke.
Thursday 2-2.30 pm:
Anton Betten and Sasha Borovik.
Thursday 3.50-4.20 pm:
Bettina Eick and Charles Leedham-Green.
-
Dominik Bernhardt: Automorphism groups of graphs with two vertex orbits
In this talk we will investigate how to construct automorphism groups of graphs with few
vertex orbits.
The base case is to construct automorphism groups with 2 vertex orbits.
We
will see how to describe their group theoretic structure and give hints towards an algorithm
for constructing these groups and towards generalisations to more orbits.
-
Anton Betten: Invariant Relations and Group Orbits
Orbit computations are essential for the classification of many kinds of mathematical
objects, in particular in the fields of finite geometry and combinatorics. Often times, an
invariant relation can be exploited to reduce the original problem to a smaller problem. By
means of iterated application of this reduction principle, a complicated classification problem
is reduced to a sequence of problems that are easer to handle. The algorithm is related but
different from the technique of orderly generation and canonical augmentation. This
talk discusses the reduction step with one invariant relation. It is the basis for a step-bystep
classification algorithm using a suitable partially ordered set. Implementations of the
algorithm in C++ and in GAP will be discussed. Some recent applications will be
discussed.
-
Alexandre Borovik and Sukru Yalcinkaya: Homomorphic encryption an some black box attacks
We offer a systematic approach to a class of attacks on communication
channels protected by homomorphic encryption based on black box algebraic
analysis. Our conclusion is that wide classes of algebraic structures
should not be used as ambient structures for homomorphic encryption.
We give some examples for groups and rings, but our general methodology
is applicable much wider.
-
Bettina Eick: Symbolic computation with finite p-groups
This is joint work with Michael Vaughan-Lee.
The p-groups of order dividing p^7 have been classified for all primes
p. This classification is available in computational format in the
LiePRing Package of GAP. We show how this can be used in computations
with finite p-groups without specifying the prime p. In particular,
we show how the Schur multipliers of the groups of order dividing p^7
can be determined for all primes p.
-
Ruth Hoffmann: Computing Stabiliser Chains Efficiently
Stabiliser chains are fundamental to the understanding and
computing with permutation groups. A byproduct of the computation of
these chains is creating a strong generating set. But the computation
of stabiliser chains can create a bottleneck within other algorithms.
We will survey the currently existing stabiliser chain algorithms and
explore different approaches to improve the compute time of stabiliser chains.
-
Max Horn: The OSCAR system
The goal of the OSCAR project is to develop a comprehensive open source computer algebra system
for computations in algebra, geometry, and number theory.
The project builds on and extends four cornerstone systems: GAP (computational discrete algebra,
in particular group and representation theory),
Singular (commutative and non-commutative algebra, algebraic geometry), Polymake (polyhedral geometry),
and Antic/Hecke/Nemo (number theory),
as well as further libraries and packages.
All this is joined together by the Julia programming language, an interactive and expressive
programing language originally developed for numerical sciences, and with very active development by third parties,
allowing us to focus on working on a computer algebra system instead of developing yet another language.
Julia offers a compelling combination of a powerful yet easy to use high-level language,
with high performance execution driven by Just-in-time compilation (JIT).
In this talk I will explain the key ideas behind OSCAR, give some interactive demonstrations
of some of its capabilities, and talk about our plans for its future development.
-
Alexander Hulpke: Rewriting Systems, Cohomology and Construction of Groups
I will describe new functionality in GAP that allows the computation of
2-cohomology and associated group extensions, based on a confluent
rewriting system for the factor group. This enables us to extend existing
algorithms for group construction to the case of nonsolvable groups. I
will explain how to do this, taking the (hitherto only partially
classified) perfect groups of order up to 1 million as an example and
describe the interplay between new and existing (sometimes suddenly
insufficient for the new application) routines in GAP.
-
Christopher Jefferson: Efficient Canonical Images in Permutation Groups
The Partition Backtrack framework of Jeffery Leon has for many years been
the main technique used for solving a wide range of problems on Permutation
Groups, including intersection, stabilizer and normalizer.
Partition Backtrack is theoretically similar to the Nauty system of Brendan
McKay, which is used for finding both isomorphisms and canonical images of
graphs.
The most significant defect of Partition Backtrack is it's inability to
find canonical images. In this talk I will show the connections between
Partition Backtrack and Nauty, and how Partition Backtrack can be extended
to support Canonical Images. This will make use of recent improvements to
Partition Backtrack to use directed graphs by Jefferson, Waldecker and Wilson.
-
Charles Leedham-Green: Calculating the intersection of two matrix groups over a finite field
This is joint work with Eamonn O’Brien.
There is no prospect of an algorithm to solve the general problem with a useful complexity analysis.
For example, the problem is at least as hard as graph isomorphism. Some of the basic ideas are as follows.
1. First attack the problem of finding the intersection of two maximal subgroups (more precisely, of two subgroups
that contain maximal subgroups of the special linear group).
2. The essential problem is to obtain a good upper bound. So to compute the intersection I of G and H,
aim to find an overgroup K of
I such that |K:I| is not too big.
3. To obtain K, use geometry.
3. It is necessary, for recursion, to consider the problem of computing the intersection of a set of subgroups of the general linear group.
4. We hope to be able to develop the roundabout, a technique that rests on tensoring and chopping, but at the time of writing it has
not got to a useful state.
-
Tobias Moede: A nilpotent quotient algorithm and its application to integral group rings
This is joint work with Bettina Eick. We introduce an algorithm to determine the class-c quotient of a
finitely presented associative Z-algebra.
We apply this in the calculation of the class-c quotient
I(G)/I(G)^{c+1}, where G is a finitely presented group and I(G)
the augmentation ideal of its integral group ring ZG.
This allows us to read off the isomorphism types of the augmentation
quotients Q_n(G)=I(G)^n/I(G)^{n+1} for 1 \leq n \leq c.
-
Sergio Siccha:
Normalizers of primitive groups with non-regular socle in polynomial time
The normalizer problem has as input generating sets X and
Y for subgroups G and H of the symmetric group S_n, and asks
one to return generators for N_H(G).
Polynomial time solutions are known for many permutation group
problems. However, in addition to the normaliser problem, polynomial
time algorithms for computing set stabilisers, centralisers and
intersections of permutation groups have so far proven elusive. The
latter three problems are polynomial time equivalent and their
equivalence class is called the \emph{Luks class}. While solving these
problems is of direct practical interest, they also yield interesting
phenomena from a complexity theoretical point of view. The famous
graph isomorphism problem reduces in polynomial time to the problems
in the Luks class, which in turn reduce to the normalizer problem.
However, no reductions in the reverse direction are known.
For a primitive group with non-regular socle G we present an
algorithm to compute the normalizer N_{S_n}(G) both practically
efficiently and in polynomial time. For primitive groups $G$ of the
above type, this yields a reduction of the normalizer problem to the
Luks class.
-
Rebecca Waldecker: Backtrack methods and canonical images
In this overview talk I will introduce the concept of backtrack search and briefly describe the recent new approach using stacks of directed graphs.
As one of the applications is the computation of canonical images, I will also introduce the concept of canonical images,
why they are useful and how we could approach computing them.