# A group acting on colourings of a set

Suppose I have a set $L$ with some permutation group $G$ defined upon it, which I think of as a symmetry group. I want to consider the set $F$ of functions $f: L \to C$, for some set $C$. It seems that there should be a natural way in which the group $G$ can also be applied to this set of functions, but I'm not sure of the best way to think about it in terms of abstract algebra.

As a concrete example, let $L$ be the faces of a cube, and let $G$ be the group of rotations of the cube. Then $F$ is equivalent to the set of colourings of the cube's faces, with $C$ being the set of possible colours. Given such a colouring, the cube can be rotated to produce another colouring. This allows us, for example, to define a set of equivalence classes where two colourings are considered equivalent if the cube can be rotated to produce one from the other.

It seems there at least two ways one could think about this. One is to define a group action of $G$ upon $F$. Another is to think about the symmetries of $F$ as being a group in its own right, which is somehow derived from $L$ and $|C|$. Perhaps there are others. But in either case I don't quite know how to express the idea formally.

This seems like it should be a fairly common concept with a collection of well-known standard results, and perhaps some nice generalisations. However, I don't know its name, and the introductory group theory texts I've consulted don't seem to cover it, so I would be grateful if anyone can point me in the right direction.

My real reason for wanting to do this is as follows: a cellular automaton is a type of dynamical system, whose state space is the set of colourings of an infinite lattice. The state transition function is typically invariant to translations of the lattice, and optionally also to rotations and reflections. I would like to generalise this concept, allowing us to talk about cellular automata as discrete dynamical systems with a particular type of symmetry.

-

## 1 Answer

$G$ acts on functions by $f(x) \mapsto f(g^{-1} x)$. This kind of action is studied, for example, in combinatorics in the context of the Pólya enumeration theorem. It is also studied in harmonic analysis, with $C$ the real or complex numbers, where it is used to generalize the Fourier transform; see Pontryagin duality.

More abstractly, the construction $L \mapsto \text{Hom}(L, C)$, where $\text{Hom}$ denotes the set of functions from $L$ to $C$, is an example of a contravariant functor. In particular, that means if a monoid $M$ acts on $L$, then the opposite monoid $M^{op}$ naturally acts on functions $L \to C$ via $f(x) \mapsto f(mx)$. In the special case of groups inversion provides a canonical isomorphism $G \cong G^{op}$, so we can turn an action of $G^{op}$ into an action of $G$. This is done in, for example, representation theory in order to construct dual representations.

-
Thanks, this is all useful stuff. I'm curious, though: why do you write $f(x) \mapsto f(g^{-1}x)$ and not $f(x) \mapsto f(gx)$? (I didn't find any reference to this action on the linked Wikipedia page for the Pólya enumeration theorem, though that page does look very relevant.) – Nathaniel May 8 '14 at 14:08
@Nathaniel: $f(x) \mapsto f(gx)$ is not an action of $G$, but an action of the opposite group $G^{op}$. – Qiaochu Yuan May 8 '14 at 18:33
Ok, I see it - sorry for the slightly silly question. – Nathaniel May 9 '14 at 1:49