On relational complexity and base size of finite primitive groups

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

PDF Access Denied

We have not been able to recognize your IP address 3.143.168.172 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-recommendation 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:

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

Vol. 318, No. 1, 2022

Veronica Kelsey and Colva M. Roney-Dougal

Abstract

PDF Access Denied

Keywords

Mathematical Subject Classification

Milestones

Authors