I'm experimenting with rules for a cellular automaton in a hexagonal grid. I am wondering how to enforce symmetry.
For example a cell can be either "alive" or "dead". Let's say a rule maps the state of 6 neighbours to the next state of the center. There are 2^6 possible rules (easy to enumerate).
But now I would like those rules to be symmetric. After some research I found that the dihedral group (D6) describes the symmetry I want. But I just remembered that group theory exists at all, so I'm a bit lost with my next question:
How can I enumerate all possible rules that are invariant to this symmetry? Is there a notation or concept to help with this?
I have done it manually and counted 13(*) possible inputs that are distinguishable if the rule is invariant to D6 transformations of its input. But how can I count them formally? What group-theory concept(s) should I study for this?
(*) Here are the 13 I've found (click to enlarge):
These are binary bracelets. That article invokes the Pólya enumeration theorem, but you can also derive the result using Burnside’s lemma, which is less general but slightly more accessible. To do so, you need to count the pairs $(S,C)$ of symmetry operations $S$ and configurations $C$ such that $S$ leaves $C$ invariant. This you can do by counting the orbits of each symmetry operation; each orbit can independently be assigned a colour to obtain an input that the operation leaves invariant, so $n$ orbits yield $2^n$ invariant configurations.
In your case, the identity has $6$ orbits, a rotation through $60°$ (of which there are $2$) has $1$ orbit, a rotation through $120°$ (of which there are $2$) has $2$ orbits, the rotation through $180°$ has $3$ orbits, a reflection in a line through two corners (of which there are $3$) has $4$ orbits, and a reflection in an edge bisector (of which there are $3$) has $3$ orbits. Thus, in total there are
$$ 2^6+2\cdot2^1+2\cdot2^2+2^3+3\cdot2^4+3\cdot2^3 = 156 $$
pairs of symmetry operations and invariant configurations, so by Burnside’s lemma, as the group has $12$ elements, there are $\frac{156}{12}=13$ inequivalent configurations.