Vol. 318, No. 1, 2022

Download this article
Download this article For screen
For printing
Recent Issues
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Vol. 321: 1  2
Online Archive
The Journal
Editorial Board
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

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.

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