Primitive normalisers in quasipolynomial time

Mun See Chang*, Colva Mary Roney-Dougal

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Downloads (Pure)

Abstract

The normaliser problem has as input two subgroups H and K of the symmetric group Sn, and asks for a generating set for NK(H): it is not known to have a subexponential time solution. It is proved in [Roney-Dougal & Siccha, 2020] that if H is primitive then the normaliser problem can be solved in quasipolynomial time. We show that for all subgroups H and K of Sn, in quasipolynomial time we can decide whether NSn(H) is primitive, and if so compute NK(H). Hence we reduce the question of whether one can solve the normaliser problem in quasipolynomial time to the case where the normaliser in Sn is known not to be primitive.
Original languageEnglish
Article numberADMA-D-21-00337
Number of pages7
JournalArchiv der Mathematik
VolumeFirst Online
DOIs
Publication statusPublished - 26 Oct 2021

Keywords

  • Computation
  • Primitive groups
  • Permutation groups,

Fingerprint

Dive into the research topics of 'Primitive normalisers in quasipolynomial time'. Together they form a unique fingerprint.

Cite this