Projects per year
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 language | English |
---|---|
Article number | ADMA-D-21-00337 |
Number of pages | 7 |
Journal | Archiv der Mathematik |
Volume | First Online |
DOIs | |
Publication status | Published - 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.Projects
- 1 Finished
-
A Learning, Optimising Compiler: A Learning, Optimising Compiler for Computational Group Theory
Jefferson, C. A. (PI)
1/10/18 → 28/02/22
Project: Fellowship