Computing normalisers of intransitive groups

Mun See Chang; Christopher Anthony Jefferson; Colva Mary Roney-Dougal

doi:10.1016/j.jalgebra.2022.05.001

Computing normalisers of intransitive groups

Mun See Chang^*, Christopher Anthony Jefferson, Colva Mary Roney-Dougal

^*Corresponding author for this work

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

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 (from-to)	429-458
Number of pages	30
Journal	Journal of Algebra
Volume	605
Early online date	25 May 2022
DOIs	https://doi.org/10.1016/j.jalgebra.2022.05.001
Publication status	Published - 1 Sept 2022

Keywords

Computational group theory
Backtrack search
Permutation groups

Access to Document

10.1016/j.jalgebra.2022.05.001Licence: CC BY

Chang_2022_JoA_Computing-normalisers-intrasensitive-groups_CC
Copyright © 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Final published version, 0.99 MBLicence: CC BY

Cite this

@article{a0c88a8007d64cd5acd9f45ab39ee1e3,

title = "Computing normalisers of intransitive groups",

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.",

keywords = "Computational group theory, Backtrack search, Permutation groups",

author = "Chang, {Mun See} and Jefferson, {Christopher Anthony} and Roney-Dougal, {Colva Mary}",

note = "Funding: The first and third authors would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme “Groups, Representations and Applications: New perspectives”, where work on this paper was undertaken. This work was supported by EPSRC grant no EP/R014604/1. This work was also partially supported by a grant from the Simons Foundation. The first and second authors are supported by the Royal Society (RGF\EA\181005 and URF\R\180015).",

year = "2022",

month = sep,

day = "1",

doi = "10.1016/j.jalgebra.2022.05.001",

language = "English",

volume = "605",

pages = "429--458",

journal = "Journal of Algebra",

issn = "0021-8693",

publisher = "Academic Press/Elsevier ",

}

TY - JOUR

T1 - Computing normalisers of intransitive groups

AU - Chang, Mun See

AU - Jefferson, Christopher Anthony

AU - Roney-Dougal, Colva Mary

N1 - Funding: The first and third authors would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme “Groups, Representations and Applications: New perspectives”, where work on this paper was undertaken. This work was supported by EPSRC grant no EP/R014604/1. This work was also partially supported by a grant from the Simons Foundation. The first and second authors are supported by the Royal Society (RGF\EA\181005 and URF\R\180015).

PY - 2022/9/1

Y1 - 2022/9/1

N2 - 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.

AB - 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.

KW - Computational group theory

KW - Backtrack search

KW - Permutation groups

UR - https://doi.org/10.48550/arXiv.2112.00388

U2 - 10.1016/j.jalgebra.2022.05.001

DO - 10.1016/j.jalgebra.2022.05.001

M3 - Article

SN - 0021-8693

VL - 605

SP - 429

EP - 458

JO - Journal of Algebra

JF - Journal of Algebra

ER -

Computing normalisers of intransitive groups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

RS Research Fellowship Renewal: RS Research Fellowship Renewal

A Learning, Optimising Compiler: A Learning, Optimising Compiler for Computational Group Theory

Cite this

Computing normalisers of intransitive groups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

RS Research Fellowship Renewal: RS Research Fellowship Renewal

A Learning, Optimising Compiler: A Learning, Optimising Compiler for Computational Group Theory

Cite this