The relational complexity of linear groups acting on subspaces

Abstract

The relational complexity of a subgroup $G$ of $\mathrm{Sym}(\Omega )$ is a measure of the way in which the orbits of $G$ on ${\Omega }^k$ for various $k$ determine the original action of $G$. Very few precise values of relational complexity are known. This paper determines the exact relational complexity of all groups lying between ${\mathrm{PSL}}_n(\mathbb{F})$ and ${\mathrm{PGL}}_n(\mathbb{F})$, for an arbitrary field $\mathbb{F}$, acting on the set of $1$-dimensional subspaces of ${\mathbb{F}}^n$. We also bound the relational complexity of all groups lying between ${\mathrm{PSL}}_n(q)$ and $\mathrm{P}\Gamma {\mathrm{L}}_n(q)$, and generalise these results to the action on $m$-spaces for $m\ge 1$.

20 pages. Version 2: minor changes incorporating referee comments. To appear in J. Group Theory