On relational complexity and base size of finite primitive groups

Abstract

In this paper 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 is best possible up to a small 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.

Cited by in corpus (2)

• Irredundant bases for the symmetric group
• The relational complexity of linear groups acting on subspaces