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<!--FUNCTION\; APPLICATION-->}_n$ that is not large base, then any irredundant base for $G$ has size at most $5\log <!--FUNCTION\; APPLICATION-->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\log <!--FUNCTION\; APPLICATION-->n+1$, and the maximal size of a minimal base and the height are both at most $5\log <!--FUNCTION\; APPLICATION-->n$. Furthermore, we deduce that a base for $G$ of size at most $5\log <!--FUNCTION\; APPLICATION-->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