Laying train tracks

This morning I was playing trains with my son Felix. At the moment he is much more interested in laying the tracks than putting the trains on and moving them around, but he doesn’t tend to get concerned about whether the track closes up to make a loop. The pieces of track are all roughly the following shape:

Eight of them fit together to make a circle; but the pieces of track can also be picked up and turned over, and connected in more complicated ways:

Or even more complicated:

(I love postscript!)

The last example illustrates the fundamental problem of laying train tracks: after laying a long stretch of track, it’s hard to get the two ends to match up precisely. The reason for this is quite straightforward: how close the ends are together doesn’t give a good indication of how many segments are needed to join them up.

A more “sophisticated” way of saying this has to do with holonomy and indiscrete representations. Let’s suppose we are laying the pieces of our track one by one, always attaching the next piece to the same end of what has been built so far. We have two choices of how to lay each subsequent piece of track; call these R and L depending on whether the piece bends to the right or to the left. A sequence of tracks is therefore encoded by a string in the 2-letter alphabet; for example, the nice complete track as above is encoded by the cyclic string RRRRRLRRRRRL (cyclic, because the track closes up to make a loop). There are some highly non-obvious constraints on the strings that are allowed if we insist that the tracks are embedded in the plane, but if we are happy with “immersed” train tracks, then any string in R and L is allowed, and determines a unique track, up to isometry. We would like to give some simple criterion to tell when a string corresponds to a closed track, and more generally, given a string, to give a simple method to determine the shortest string that can be added to it to close up the track.

This is a problem in group theory. Each R and L can be thought of as applying a 1/8 twist to the plane (clockwise or anticlockwise) centered at a point which can be determined from the current location of the track. In other words, we can think of appending an R or L as a right multiplication by an isometry of the plane, and we want to know exactly when a given composition represents the trivial isometry. If we let G denote the group generated by R and L, then the first and most significant observation is that G is indiscrete. That is, an element in G might move points a very small distance (i.e. the track might “almost” close up), but the shortest length of added track needed to close it completely might be arbitrarily long.

Let’s try to be a bit more systematic. The group of isometries of the Euclidean plane is a semidirect product; it contains a normal subgroup consisting of the group of translations, and the quotient is the orthogonal group of rotations. Each of the elements R and L corresponds to a 1/8 and -1/8 rotation respectively, so the first and most obvious condition to get the track to close up is that the number of Rs minus the number of Ls must be 8 times an integer. Incidentally, this integer is the winding number of the immersed track; a necessary (but not sufficient) for the track to be embedded is that this integer must be 1 or -1. If this condition is satisfied, the two ends of the track will be aligned in the correct way for them to join up, but their positions might differ by a translation. Evidently each R or L translates the “lock” in one of the eight directions NNE, ENE, ESE, SSE, SSW, WSW, WNW, NNW; after an order 1/16 rotation we could relabel these directions as N,NE,E,SE,S,SW,W,NW. If we identify the Euclidean plane with the complex plane, then (after a change of scale), the relative position of any two “locks” is an element of the additive group A generated by the 1/8 roots of unity. This group is an indiscrete subgroup of the translations of the plane, isomorphic to . But now the answer to our problem is obvious: instead of measuring distance in the plane, measure distance instead in A. On way to do this is to use the fact that the natural embedding is discrete, where maps an 1/8th root of unity to its cube. In terms of RL sequences, this means building two sequences of train tracks simultaneously; if the first corresponds to some sequence RRLRL etc., then the second corresponds to the sequence where each R is replaced with RRR and each L with LLL; i.e. RRRRRRLLLRRRLLL etc. in this example. If S is the first sequence, let’s call the second sequence S’. A track corresponding to S can be closed up by a small number of pieces providing both that track, and the track corresponding to S’, have ends which are close together in the usual sense. A very nice illustration of a closely related example is Rich Schwartz’s game “Lucy and Lily”.

How many closed tracks are there of a given length? Giving an exact formula is possible although a little tricky; it’s a bit easier to give an asymptotic formula, using some probability theory. Build a finite directed graph whose eight vertices correspond to the eight possible orientations of the end of the track, and put a directed edge from one vertex to another with the label R or L when orientations differ by an 1/8 turn in the positive or negative sense:

There is a function T from the 16 edges to the set of 1/8th roots of unity, and the value on a given edge corresponds to the way in which appending an R or L in a given orientation translates the lock. An RL string determines a walk in the graph by proceeding at every stage along the edge with the label corresponding to the letter in the string. Then the total translation associated to a string is the sum of the function T on the edges visited in the corresponding path. We take this sum in the abstract group for simplicity. A path closes up if and only if it starts and ends at the same vertex, and if the T sum coming from the edges is zero.

A random string of Rs and Ls thereby corresponds to a random walk on the directed graph ; this is an example of a stationary Markov chain, and the value of the function on a random walk of length satisfies a central limit theorem. We want more precise information, namely the chance that a random walk returns to its initial vertex, and satisfies ; such a result is called a local limit theorem. The ergodic theorem says that the chance of returning to the origin is 1/4 if is even, and 0 if is odd. Similarly, can only be zero if is even, in which case the chance that satisfies as , where is a particular algebraic number approximately equal to 1.1024. Since the number of RL words of length n is , this means that the number of closed tracks of (even) length has order .

There are many obvious directions one can take these ideas. There is an obvious relation to Conway’s tiling groups, as explained by Thurston. The phenomenon of an indiscrete finitely generated group of isometries becoming discrete in a suitable (Galois twisted) product lies behind the construction of what are known as arithmetic lattices. One can also try to generalize this discussion to other geometries; e.g. to study train track configurations on the sphere, or in the hyperbolic plane. Finally, one can try to attack the much harder problem of enumerating the number of embedded closed tracks of given length (or finding an asymptotic formula). But we’ll save that for another post.

(Added December 7)

I thought it might be instructive to give an example of a “complicated” pair of closed (immersed) tracks corresponding to the pair of RL strings

LLRRLRRRLRLRRRRLLRRRLRLRLLLRLLLLLLRRRLRRRLRRRRRR

and

LLLLLLRRRRRRLLLRLLLRRRLLLRRRRLLLLLLRLLLRRRLLLRRRLRRRLLRLLLRLLLRR.

Each string is obtained from the other by substituting RRR for each R and LLL for each L (and then removing strings of 8 consecutive Rs or Ls, which just remove a little closed loop from the corresponding track). These strings were generated by the method described above: after laying down some random initial string, I added bits to each simultaneously in an effort to get both tracks to close up. I was quite pleased that this worked out nicely in practice. In case you want to have a play with this yourself, here is the postscript code to generate this figure. Fiddle with the RL strings at the ends to lay a different track. And if you come up with a nice pattern, please email me!

%!PS-Adobe-2.0 EPSF-2.0

%%BoundingBox: 0 0 540 300

gsave
5 5 scale
1 4 div setlinewidth

20 30 translate

/socket {
 newpath
 2 0 moveto
 1 -0.2 1 0 1.2 0.2 curveto
 1 0.4 0.2 2 sqrt mul -45 225 arc
 1 0 1 -0.2 0 0 curveto
 stroke
} def

/Rtrack {
 gsave
 -1 0 translate
 newpath
 5 0 3 135 180 arc
 stroke
 newpath
 5 0 5 135 180 arc
 stroke
 socket
 gsave
 5 0 translate
 -45 rotate
 -5 0 translate
 socket
 grestore
 grestore
} def

/Ltrack {
 gsave
 -1 1 scale
 Rtrack
 grestore
} def

/R {
 Rtrack
 4 0 translate
 -45 rotate
 -4 0 translate
} def

/L {
 Ltrack
 -4 0 translate
 45 rotate
 4 0 translate
} def

gsave
L L R R L R R R L R L R R R R L L R R R L R L R L L L R L L L L L L

R R R L R R R L R R R R R R
grestore

70 20 translate

L L L L L L R R R R R R L L L R L L L R R R L L L R R R R L L L L L

L R L L L R R R L L L R R R L R R R L L R L L L R L L L R R
grestore
%eof