Group Actions

The theory of finite automata works with finite alphabets. The article Automata with Group Actions by Bojanczyk et al. is one recent attempt to extend the theory to infinite alphabets. To do so, the authors use a basic notion from group theory, namely group action. Here I review the facts about group actions that are necessary to understand Bojanczyk's article.

Recall that a group is a set $G$ together with a binary operation that has an identity, is associative, and each element has an inverse:

• $1 \pi=\pi 1$, for all $\pi \in G$
  
• $(\pi\sigma)\tau=\pi(\sigma\tau)$, for all $\pi,\sigma,\tau\in G$, and
  
• there exist a $\pi^{-1}\in G$ such that $\pi\pi^{-1}=\pi^{-1}\pi=1$, for all $\pi\in G$
  

The typical example of a group is the set of permutations of some set $X$. Its elements have the type $X \to X$. The identity is the identity function. The binary operation is function composition, which is always associative. Each permutation has an inverse almost by definition. (Permutations are those functions that have inverses.) This group is sometimes denoted $\mathrm{Sym}(X)$ and is called the symmetric group of $X$.

Recall also that a function $f : G \to H$ is called a homomorphism when $f(\pi\sigma)=f(\pi)f(\sigma)$ for all $\pi,\sigma \in G$. We say that $f$ preserves the group operation. In particular, $f(1)=1$ or, more precisely, $f(1_G)=1_H$. In words, homomorphisms map the identity of one group to the identity of the other. This is easy to prove, and makes a nice exercise.

A group action is a homomorphism from $G$ to $\mathrm{Sym}(X)$. The set $X$ is called a $G$-Set.

The simplest group action is the trivial action, which maps all elements of $G$ to the identity permutation of $X$,

I know of two reasons why group actions are an interesting concept. First, they let you think of elements of a group $G$ as symmetries of a set $X$ and therefore they partition the set $X$ into equivalence classes. You change the group $G$, you change which elements of $X$ are "essentially the same." Second, once you have group actions for $X$ and $Y$ you also have group actions for $X \times Y$ and $X+Y$ and $X^*$. So group actions build up nicely.

The picture I have in my mind when I talk about G-Sets is a bunch of points (the elements of $X$) with a bunch of arcs between them. Each arc is labelled by an element of $G$. When we look at all arcs labelled by $\pi$ (where $\pi \in G$) we get the picture of a permutation on $X$. That is, a bunch of (disjoint) cycles. When we look at the arcs labelled by $1_G$ we see a loop on each point. In general, we see $|G|$ arcs getting out of each point. This picture has a few more properties. If there is an arc from $x$ to $y$ and one from $y$ to $z$, then there is an arc from $x$ to $z$. In other words, the digraph I'm describing is transitively closed. Proving this property makes another nice exercise. In yet other words, for all $x$ and $y$ either there is an arc from $x$ to $y$ or there is no path from $x$ to $y$. The (strongly) connected components of this graph are the equivalence classes that $G$ determines on $X$. The equivalence class of an element $x \in X$ is called its orbit. Another property of this graph (the Burnside lemma) is that the points in each orbit have exactly $|G|$ loops in total. (Well, I admit: This is not quite the standard formulation.)

To discuss how group actions build up it's useful to finally introduce some (common) notation. We write $x \cdot \pi = y$ when the permutation associated with $\pi \in G$ maps $x \in X$ to $y \in Y$. So, in a way, the dot $\cdot$ represents the (still nameless) group action. Typically, we use the following.

• $(x,y) \cdot \pi = (x \cdot \pi, y \cdot \pi)$
  
• $[x_0,\ldots,x_{n-1}]\cdot \pi = [x_0\cdot\pi,\ldots,x_{n-1}\cdot\pi]$
  

A subset $Z$ of $X$ is said to be invariant (or equivariant) when it is a union of orbits. Equivalently, $Z$ is said to be invariant when each $\pi \in G$ permutes its elements, that is $Z \cdot \pi = Z$. (The graph picture is very handy to figure out why these two definitions are equivalent.)

Now suppose that the $G$-Set is $X \times Y$ and we are given a function $f : X \to Y$. We say that $f$ is invariant when the subset $\{\,(x,f(x))\mid x\in X\,\}$ is invariant. In other words, when $$f(x \cdot \pi) = f(x) \cdot \pi$$ for all $x \in X$ and $\pi \in G$. Invariant functions are closed under composition. $G$-Set is the category of $G$-Sets with the arrows being invariant functions.

How is this at all relevant to finite automata over infinite alphabets? Well, very roughly, a finite automaton over infinite alphabets is one that cannot distinguish between symmetric traces. For example, an automaton might say that "given two iterators $\alpha$ and $\beta$ on a collection $\gamma$, it is illegal to use $\alpha$ to modify $\gamma$ and then continue to use $\beta$." The exact values $\alpha$, $\beta$, and $\gamma$ are irrelevant, so if a trace with some values is accepted, then so are all traces obtained by pointwise permuting the values in the trace. I realize this is rather unclear, but I plan to talk about it in a future post.

In the meantime, there are two other nice references on group actions that I know of: Wikipedia and a recent post on Gower's blog.