Combinatorial
Dynamics

David Hillman

STEP 1:
 
 define sets of combinatorial n-dimensional spaces

space sets for 1-d cellular automata

space sets for 1-d cellular automata: revised

oriented space sets

all arrows point in the same direction

studied in symbolic dynamics (topological conjugacy and flow equivalence of subshifts of finite type)

asymmetrical space sets

no piece of space is equal to its reflection

symmetrical space sets

there exists a piece of space that is equal to its reflection

algebraic notation

1. assign variable names to oriented cells

2. generate all oriented pieces of space ("segments") via noncommutative multiplication

3. rules for *

1. (SuperStar[((SuperStar[s]))]) = s

2. \(TraditionalForm\`\(\((st)\)\^*\)\) = (SuperStar[t])(SuperStar[s]) ( which implies that (SuperStar[((Subscript[s, 1])(Subscript[s, 2])...(Subscript[s, k]))]) = (SuperStar[(Subscript[s, k])])...(SuperStar[(Subscript[s, 2])])(SuperStar[(Subscript[s, 1])])  )
	                                      3. (s + t\(TraditionalForm\`\()\^*\)\) = (SuperStar[s]) + (SuperStar[t])

( * is called an involution )

4. notation for a circular oriented space

⟨ s ⟩ means: glue one end of the oriented segment s to the other to make a circular oriented space
⟨ a b ⟩ = ⟨ b a ⟩, ⟨ s \(TraditionalForm\`\(⟩\^*\)\) = ⟨ (SuperStar[s]) ⟩

a labelled graph associated with a width-w space set

1. assign lower-case variable names to oriented width-w segments

2. assign upper-case variable names to oriented width-(w-1) segments

3. construct the graph. The vertices are the upper-case letters. The edges are the lower-case letters.

The graph defines a new space set. The allowed neighborhoods are the length-2 paths. The segments are the directed paths. The spaces are the bi-infinite directed paths or loops. There is a local, invertible map between the old space set and the new one.

the characteristic property of these graphs:
a hermitian "adjacency matrix"

Choose an ordered list of vertices:  v = { A, B, (SuperStar[B]), C }
Let M[[i,j]] be the formal sum of edges going from (SuperStar[v[[i]]]) to v[[j]]. Then

M = (({{0, w, 0, 0}, {\(w\^*\), z, 0, 0}, {0, 0, x, y}, {0, 0, \(y\^*\), 0}}))

M is called hermitian because M[[i,j]] = (SuperStar[M[[j,i]]]).

Note also one other important property of the graph: every edge and vertex in the graph is labelled differently.

We'll call these *-graphs. Since every space set can be represented as a *-graph, we'll forget about representing space sets by width-w allowed neighborhoods and say:

One-dimensional combinatorial space sets and *-graphs are exactly the same thing.

STEP 2:
 
 define local, invertible maps between space sets

renaming

Renaming the vertices or edges gives an invertible, local map. The only requirement is that every vertex and edge have a distinct name. Elements in the left-hand graph are mapped to corresponding elements in the right-hand graph.

⟨ w x (SuperStar[w]) ⟩ ↔ ⟨ u x (SuperStar[u]) ⟩

There's nothing special about which edge is named w and which (SuperStar[w]); these can be switched.

⟨ w x (SuperStar[w]) ⟩ ↔ ⟨ (SuperStar[w]) x w ⟩

If the graph has a symmetry then renaming can be used to create a map from the space set to itself.

⟨ w x (SuperStar[w]) ⟩ ↔ ⟨ (SuperStar[w]) z w ⟩

adding or removing a vertex with no edges attached

Clearly a vertex with no edges attached does not appear in any space. So we can add or remove them at will without changing the space set. If the vertex is asymmetrical we must add or remove both orientations of it.

⟨ w x (SuperStar[w]) ⟩ ↔ ⟨ w x (SuperStar[w]) ⟩

adding or removing an edge

To remove an edge:

1. choose an asymmetrical edge e that connects two distinct vertices

2. for each length-2 path p beginning with e or ending with (SuperStar[e]), and for each length-3 path p beginning with e and ending with (SuperStar[e]), insert a new edge u(p). The new edges have the property that (SuperStar[(u(p))]) = u((SuperStar[p])).

3. remove edges e and (SuperStar[e])

The map between spaces works by first replacing each length-3 path p mentioned above by u(p), and then replacing all remaining length-2 paths p by u(p).

⟨ w y (SuperStar[y]) z x (SuperStar[w]) w x (SuperStar[w]) ⟩ ↔ ⟨ u(wy) (SuperStar[y]) z u(\(xw\^*\)) u(wx(SuperStar[w])) ⟩

To add an edge you just do this same thing in reverse.

finding laws of evolution

All maps are generated by the kinds we've already seen.

So to find laws of evolution you just generate maps between space sets
and pick out those that map a space set to itself.

It's easy!

conclusion

I've left out a lot that is interesting:

The equivalence problem: which space sets can be mapped to which? Franks (1984) solved this for the most important class of oriented space sets. I recently solved it for the most important class of asymmetric space sets.The answer is related to Witt equivalence classes of integral quadratic forms.The question remains open for symmetric space sets.

The linear-algebraic nature of these systems is very deep. They have something to do with hermitian forms and additive categories. This still remains to be worked out.

Connections with physics: (1) invariants (constants of motion) in these system naturally involve complex numbers; (2) I've shown that to deal with the CPT symmetry and the presence of antimatter one simply requires that the law of evolution be of the form AB with (A^2) = (B^2) = identity (the argument holds in higher dimensions as well); 3) I have a beginning understanding of the concept of a combinatorial Lorentz metric, and some examples.

There are plenty of open questions (especially since so far I'm probably the only person working on most of this), and there's lots of work to be done. Please join in!

Unfortunately I keep not getting around to finishing papers. But I'm glad to communicate with anyone about this subject.

David Hillman
email: dhi@cablespeed.com
email: hillman@wolfram.com

PhD dissertation (1995): Combinatorial Spacetimes
      http://xxx.lanl.gov/abs/hep-th/9805066