#### Vol. 318, No. 1, 2022

 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 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 $5\mathrm{log}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 $5\mathrm{log}n+1$, and the maximal size of a minimal base and the height are both at most $5\mathrm{log}n$. Furthermore, we deduce that a base for $G$ of size at most $5\mathrm{log}n$ can be computed in polynomial time.

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

or by using our contact form.