Normalisers of primitive permutation groups in quasipolynomial time

Colva Mary Roney-Dougal; Sergio Siccha

doi:10.1112/blms.12330

Normalisers of primitive permutation groups in quasipolynomial time

Research output: Contribution to journal › Article › peer-review

Abstract

We show that given generators for subgroups G and H of S_n, if G is primitive then generators for N_H(G) may be computed in quasipolynomial time, namely 2^{O(log^3 n}). The previous best known bound was simply exponential.

Original language	English
Pages (from-to)	358-366
Journal	Bulletin of the London Mathematical Society
Volume	52
Issue number	2
Early online date	7 Apr 2020
DOIs	https://doi.org/10.1112/blms.12330
Publication status	Published - 23 Apr 2020

Access to Document

10.1112/blms.12330

normaliser_final_accepted
© 2020 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence. This work has been made available online in accordance with publisher policies or with permission. Permission for further reuse of this content should be sought from the publisher or the rights holder. This is the author created accepted manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://doi.org/10.1112/blms.12330
Accepted author manuscript, 271 KB

https://arxiv.org/abs/2002.01377Licence: CC BY

Colva Roney-Dougal, OBE
- Colva.Roney-Dougalst-andrews.acuk
Person: Academic

Cite this

@article{bea49b5af24047d18409591eaa6d49bc,

title = "Normalisers of primitive permutation groups in quasipolynomial time",

abstract = "We show that given generators for subgroups G and H of Sn, if G is primitive then generators for NH(G) may be computed in quasipolynomial time, namely 2O(log^3 n). The previous best known bound was simply exponential.",

author = "Roney-Dougal, {Colva Mary} and Sergio Siccha",

note = "Funding: Isaac Newton Institute for Mathematical Sciences for support and hospitality during the programme “Groups, Representations and Applications: New perspectives”, when work on this paper was undertaken. This work was supported by EPSRC grant number EP/R014604/1.",

year = "2020",

month = apr,

day = "23",

doi = "10.1112/blms.12330",

language = "English",

volume = "52",

pages = "358--366",

journal = "Bulletin of the London Mathematical Society",

issn = "0024-6093",

publisher = "Oxford University Press",

number = "2",

}

TY - JOUR

T1 - Normalisers of primitive permutation groups in quasipolynomial time

AU - Roney-Dougal, Colva Mary

AU - Siccha, Sergio

N1 - Funding: Isaac Newton Institute for Mathematical Sciences for support and hospitality during the programme “Groups, Representations and Applications: New perspectives”, when work on this paper was undertaken. This work was supported by EPSRC grant number EP/R014604/1.

PY - 2020/4/23

Y1 - 2020/4/23

N2 - We show that given generators for subgroups G and H of Sn, if G is primitive then generators for NH(G) may be computed in quasipolynomial time, namely 2O(log^3 n). The previous best known bound was simply exponential.

AB - We show that given generators for subgroups G and H of Sn, if G is primitive then generators for NH(G) may be computed in quasipolynomial time, namely 2O(log^3 n). The previous best known bound was simply exponential.

U2 - 10.1112/blms.12330

DO - 10.1112/blms.12330

M3 - Article

SN - 0024-6093

VL - 52

SP - 358

EP - 366

JO - Bulletin of the London Mathematical Society

JF - Bulletin of the London Mathematical Society

IS - 2

ER -

Normalisers of primitive permutation groups in quasipolynomial time

Abstract

Access to Document

Fingerprint

Profiles

Colva Roney-Dougal, OBE

Cite this