6.11 Global Symmetries and Conservation Laws

Given the rule (stated here using numbers rather than our usual letters)

if we reverse the elements in each relation we get:

But the canonical version of this rule is:

In graphical form, the rule and its transform are:

Most rules would not be left invariant under a reversal of each relation. For example, the rule

yields after reversal of each relation

but the canonical form of this is

which is not the same as the original rule.

If a rule is invariant under a symmetry operation such as reversing each relation, it implies that the rule commutes with the symmetry operation. So given a rule R and a symmetry operation Θ, this means that for any state S, R (Θ S) must be the same as Θ (R S).

With the symmetric rule above, evolving from a particular initial state gives:

But now reversing the relations in the initial state gives essentially the same evolution, but with states whose relations have been reversed:

For the nonsymmetric rule above, evolution from a particular initial state gives:

But if one now reverses the relations in the initial state, the evolution is completely different:

For rules with binary relations, the only symmetry operation that can operate on relations is reversal, corresponding to the permutation {2,1}. Of the 73 distinct 1₂  2₂ rules, 11 have this symmetry. Of the 4702 2₂  3₂ rules, 92 have the symmetry. Of the 40,405 2₂  4₂ rules, 363 have the symmetry. Those with the most complex behavior are:

For rules with ternary relations, there are six distinct symmetry classes corresponding to the six subgroups of the symmetric group S₃: no invariance, invariance under transposition of two elements (3 cases of S₂) ({1,3,2}, {3,2,1} or {2,1,3} only), invariance under cyclic rotation (A₃) ({2,3,1} and {3,1,2}), or invariance under any permutation (full S₃). Here are the numbers of rules of various signatures with these different symmetries:

Examples of rules with full S₃ symmetry include (compare 7.2):

An example of a rule with only cyclic (A₃) symmetry is:

The existence of symmetry in a rule has implications for its multiway graph, effectively breaking its state transition graph into pieces corresponding to different cosets (compare [1:p963]). For example, starting from all 102 distinct 2-element ternary hypergraphs, the first completely symmetric rule above gives multiway system:

A somewhat simpler example of a completely symmetric rule is:

This rule has a simple conservation law: it generates new relations but not new elements. And as a result its multiway graph breaks into multiple separate components.

In general one can imagine many different kinds of conservation laws, some associated with identifiable symmetries, and some not. To get a sense of what can happen, let us consider the simpler case of string substitution systems.

The rule (which has reversal symmetry)

gives a multiway graph which consists of separate components distinguished by their total numbers of As and Bs:

The rule

gives the same basic structure, but now what distinguishes the components is the difference in the number of ABs vs. BAs that occur in each string. In both these examples, the number of distinct components increases linearly with the length of the strings.

The rule

already gives exactly two components, one with an even number of Bs, and one with an odd number:

The rule

also gives two components, but now these just correspond to strings that start with A or start with B.