Base sizes of group actions

Minimal base sizes

In this post I will talk about the concept of a base of a group action. This gives rise to a property of the action which is often interesting to calculate: the minimal base size.

Firstly let $G$ be a group acting transitively on a set $\Omega$. We say that $G$ acts transitively if for every $x,y \in \Omega$ there exists $g \in G$ such that $x^g = y$.

Now let $B$ be a subset of $X$. We denote by $G_B$ the pointwise stabiliser of $B$. This is the set of $g \in G$ such that $x^g = x$ for all $x \in B$, i.e. the collection of all $g \in G$ that fix or "stabilise" every element of $B$. We call such a subset $B$ a base for the action if its pointwise stabiliser is trivial, that is, $G_B = {1}$. This means that only the identity fixes all elements of $B$.

The main use for bases is in the field of computational group theory. The main reason for this is that the action a group on a base gives a lot of information about the full action of the group. To see this let $G$ act on $\Omega$ transitively with $B$ a base. Suppose that we have $g,h \in G$ acting identically on the base, i.e. let $x^g = x^h$ for all $x \in B$. Then $x^{gh^-1} = x$ for all $x \in B$ and so $gh^-1 = 1$ by definition of a base. Hence $g = h$. Thus the action of $g$ on $\Omega$ can be stored in a computer using only $|B|$ elements instead of $|\Omega|$.

The reason that this is useful is that bases in general are very small. For a group $G$ we denote its minimal base size by $b(G)$. Note that we talk about minimal base size since if $B$ is a base for an action then any subset of $\Omega$ containing $B$ will also be a base. Although there are some groups with large minimal base size compared to their size (for example $b(S_n) = n-1$) in most cases the minimal base size will be many times smaller than the size of the group. For example a very unique group known as the Monster group contains around $10^{54}$ elements. There is an action of this group on a set of size around $10^{20}$ - an extension of another group called the Baby monster group. The minimal base size for this action, however, is just $3$. This means that this enormous action is completely determined by the action of the Monster group on just $3$ elements.