Computing normalisers of intransitive groups

Research output: Contribution to journalArticlepeer-review

Abstract

The normaliser problem takes as input subgroups G and H of the symmetric group Sn, and asks one to compute NG(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=Sn  is at least as hard as computing the group of monomial automorphisms of a linear code over any field of fixed prime order.
Original languageEnglish
Pages (from-to)429-458
Number of pages30
JournalJournal of Algebra
Volume605
Early online date25 May 2022
DOIs
Publication statusPublished - 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.

Cite this