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 \mathbb{Z}^4. 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 \text{id} \times \sigma: A \to \mathbb{C} \times \mathbb{C} is discrete, where \sigma 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 \Gamma 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 \Gamma 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 A \cong \mathbb{Z}^4 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 \Gamma; this is an example of a stationary Markov chain, and the value of the function \sum T on a random walk of length n satisfies a central limit theorem. We want more precise information, namely the chance that a random walk returns to its initial vertex, and satisfies \sum T=0; 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 n is even, and 0 if n is odd. Similarly, \sum T can only be zero if n is even, in which case the chance P(n) that \sum T=0 satisfies \sigma^4 n^2 P(n) \to 2/2\pi^2 as n \to \infty, where \sigma is a particular algebraic number approximately equal to 1.1024. Since the number of RL words of length n is 2^n, this means that the number of closed tracks of (even) length n has order 2^n/n^2.

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




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
5 5 scale
1 4 div setlinewidth
20 30 translate
/socket {
 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
} def
/Rtrack {
 -1 0 translate
 5 0 3 135 180 arc
 5 0 5 135 180 arc
 5 0 translate
 -45 rotate
 -5 0 translate
} def
/Ltrack {
 -1 1 scale
} def
/R {
 4 0 translate
 -45 rotate
 -4 0 translate
} def
/L {
 -4 0 translate
 45 rotate
 4 0 translate
} def
70 20 translate
This entry was posted in Ergodic Theory, Euclidean Geometry and tagged , , , , . Bookmark the permalink.

16 Responses to Laying train tracks

  1. Pingback: ACME Science » The Internet Maths Aperiodical –

  2. Anonymous says:

    This is really nice! Given an embedded train track, is there a nice way to tell whether there is a way to close the loop so that the closed loop is also embedded?

    • Danny Calegari says:

      This is quite a difficult question in general, but I can try to give a few vague ideas. Part of the problem is that it is possible to have an embedded train track which can’t be extended to a closed up embedded train track. This is actually quite easy to arrange: if the embedded train track has a long narrow cul-de-sac, then a path that enters won’t have enough room to turn around without intersecting itself or the walls of the dead end. So imagine someone laying out track more or less randomly, but trying to look ahead a bit to avoid cul-de-sacs. Conformally speaking, the size of a cul-de-sac depends (roughly) only on the narrowest bottleneck, not on how big it is past that bottleneck. So by avoiding bottlenecks and self-intersections and otherwise laying track “randomly”, the track that’s laid out will, on the large scale, resemble some conformally invariant random embedded path, which is to say SLE at some parameter. A segment of path of length n will tend to have diameter about sqrt(n) (it can’t be smaller than this, since it has area n and is embedded). Moreover, the distance between the endpoints measured in the translation group A (which is abstractly isomorphic to Z^4) will be usually of order sqrt(n). Now, providing neither end is trapped in a cul-de-sac, the path can be closed up to an embedded track by adding an additional O(sqrt(n)) pieces. First, give yourself a bit of room by extending the two ends outwards in “spikes” from what’s laid out so far. Then the trick is to add a big embedded “loop” of the form (LR)^{n_1}R(LR)^{n_2}R . . . (LR)^{n_8}R. If the n_i are all reasonably large (say, of order twice the diameter) and are chosen so that this new loop represents the inverse in A of what is laid out so far, then it will close up the track in an embedded way.

  3. Swiat Gal says:

    -1. Would you mind posting the postscript code you are so proud of? What tools do you use?

    0. I think that declaring groups by generators and relations is some misidea. I think that we should investigate more groups defined by action (of generators). Alas, using presentations as tools.

    1. The group generated by L and S is virtually abelian, so the word problem is easy to solve. I did not derive the representattion of it, but it is a finite index subgroup of the group generated by a rotation O by π/4 and a translation T. Then R=OT, L=TO^{-1}. (T is the vector between the ends of the track rotated by π/8.)

    The relations in the group generated by T and O are: O^8, (O^4T)^2, [O^iTO^{-1},T]. Then if you want to know if a LR-word closes you write it in terms of O and T, you group conjugates of T, commute (is it the right verb for moving commuting elements?) them
    to cancel (or not). There are only few left if and only if you could close the track if few steps.

    2. What is the index of Γ_0:= in Γ:=? What is the presentation of Γ_0? I know tat I need to take representatives of cosets of Γ_0 together with L and R and play with Tietze moves…

  4. Swiat Gal says:

    Actually, I have chosen a dumb reference point At the beginning of the track. If I take it to be the centre of the R-circle the group Γ_0 is generated by the rotation R and the translation RL. And the relations for R and RL are the same as for O and T.

  5. Swiat Gal says:

    Just for fun I wrote down presentation for Γ_0: R^8, (R^5L)^4, (R^7L^3)^4. Of course the third relator is obtained from the second by substituting R^3 and L^3 for R and S respectively (3.5≡7(8)). So,
    the two track you have mention at the beggining are almosl all you would like to know about that group.

    BTW. you should have cusps (switches?) in your tracks. R^2L^{-2}R^2L^{-2} is a nice closed track!

  6. Swiat Gal says:

    Oops! I forgot to copy one more relation LRRL=RLLR.

  7. Sheldon says:

    Proof that geometry is applicable in all arenas of life!

  8. human mathematics says:

    Are you on twitter? The name @lamington doesn’t look like you … if you could tweet @isomorphisms that would make it easy for me to find you.

  9. Pingback: Group Theoretic Origin of the Domino Height Functions « monsieurcactus

  10. Jeff says:

    Interesting post even for a layman like myself. I was thinking about this problem, to write a program to generate all track layouts for a given set of pieces.

    How does having more track piece types change things? It appears to not fundamentally change anything other than make the problem more messy.

    • Danny Calegari says:

      Hi Jeff – I think it would be very interesting to try to enumerate (eg by computer) all possible *embedded* (i.e. without self-intersections) tracks of a given length. Even with only two pieces as above this is already very complicated I think. One way to adjust the parameters of the problem is to change the “angle” through which a piece of track turns from 2\pi/8 to 2\pi/n for some other integer n. Please let me know if you decide to write your program, and how it turns out.

  11. I do not know if it’s just me or if perhaps everybody else experiencing issues with your blog. It seems like some of the written text within your content are running off the screen. Can someone else please comment and let me know if this is happening to them as well? This may be a problem with my internet browser because I’ve had this happen previously.
    Thank you

  12. Pingback: ACMEScience » Blog Archive » The Internet Maths Aperiodical – dinner and a theorem

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s