Projects per year
Abstract
The normaliser problem takes as input subgroups G and H of the symmetric group S_{n}, and asks one to compute N_{G}(H). The fastest known algorithm for this problem is simply exponential, whilst more efficient algorithms are known for restricted classes of groups. In this paper, we will focus on groups with many orbits. We give a new algorithm for the normaliser problem for these groups that performs many orders of magnitude faster than previous implementations in GAP. We also prove that the normaliser problem for the special case G=S_{n} is at least as hard as computing the group of monomial automorphisms of a linear code over any field of fixed prime order.
Original language  English 

Pages (fromto)  429458 
Number of pages  30 
Journal  Journal of Algebra 
Volume  605 
Early online date  25 May 2022 
DOIs  
Publication status  Published  1 Sept 2022 
Keywords
 Computational group theory
 Backtrack search
 Permutation groups
Fingerprint
Dive into the research topics of 'Computing normalisers of intransitive groups'. Together they form a unique fingerprint.Projects
 2 Finished


A Learning, Optimising Compiler: A Learning, Optimising Compiler for Computational Group Theory
1/10/18 → 28/02/22
Project: Fellowship