Vol. 318, No. 1, 2022

Download this article
Download this article For screen
For printing
Recent Issues
Vol. 325: 1
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Vol. 320: 1  2
Vol. 319: 1  2
Vol. 318: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
Submission Guidelines
Submission Form
Policies for Authors
 
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
 
Other MSP Journals
On relational complexity and base size of finite primitive groups

Veronica Kelsey and Colva M. Roney-Dougal

Vol. 318 (2022), No. 1, 89–108
DOI: 10.2140/pjm.2022.318.89
Abstract

We show that if G is a primitive subgroup of S n that is not large base, then any irredundant base for G has size at most 5log n. This is the first logarithmic bound on the size of an irredundant base for such groups, and it is the best possible up to a multiplicative constant. As a corollary, the relational complexity of G is at most 5log n + 1, and the maximal size of a minimal base and the height are both at most 5log n. Furthermore, we deduce that a base for G of size at most 5log n can be computed in polynomial time.

Keywords
permutation group, base size, relational complexity, computational complexity
Mathematical Subject Classification
Primary: 20B15, 20B25, 20E32, 20-08
Milestones
Received: 29 July 2021
Revised: 15 November 2021
Accepted: 25 December 2021
Published: 1 August 2022
Authors
Veronica Kelsey
Department of Mathematics
University of Manchester
Manchester
United Kingdom
Colva M. Roney-Dougal
Mathematical Institute
University of St. Andrews
Fife
United Kingdom