Base sizes of primitive groups: bounds with explicit constants (Q1755548): Difference between revisions

Let $G$ be a permutation group on a set $\Omega$ of size $n$. A subset $\Sigma\subseteq\Omega$ is a base of $G$ if the pointwise stabilizer of $\Sigma$ is $1$; $b(G)$ is defined to be the size of the smallest base. It is easily seen that $\left\vert G\right\vert \leq n^{b(G)}$ and so $b(G)\geq (\log\left\vert G\right\vert )/\log n$ for each permutation group of degree $n$. On the other hand, \textit{H. Duyan} et al. [Adv. Math. 331, 720--747 (2018; Zbl 1428.20005)] recently answered a question of \textit{L. Pyber} [DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 11, 197--219 (1993; Zbl 0799.20005)] by showing that there exists a constant $c>0$ such that $b(G)<45(\log\left\vert G\right\vert)/\log n+c$ whenever $G$ is primitive. The authors of the present paper improve this by showing that $b(G)\leq2(\log\left\vert G\right\vert)/\log n+24$ whenever $G$ is primitive. This result is almost best possible since they can construct, for infinitely many integers $n$, a primitive group $G\ $such that $b(G)\geq2(\log\left\vert G\right\vert)/\log n-2$. The proof of the main theorem requires the classification of finite simple groups and involves a careful case-by-case analysis. A\ corollary of the theorem is that if $G$ is a primitive group and does not contain the alternating group $\mathrm{Alt}(\Omega)$, then $b(G)\leq\max\left\{\sqrt{n},25\right\} $.