Vol. 318, No. 1, 2022

Download this article
Download this article For screen
For printing
Recent Issues
Vol. 320: 1
Vol. 319: 1  2
Vol. 318: 1  2
Vol. 317: 1  2
Vol. 316: 1  2
Vol. 315: 1  2
Vol. 314: 1  2
Vol. 313: 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
This article is available for purchase or by subscription. See below.
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.

PDF Access Denied

We have not been able to recognize your IP address as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

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