Enzymind Labs

Thue-Morse sequence tilings

    Visually interesting two dimensional tilings can be constructed by abstracting the one dimensional Thue-Morse sequence to two dimensions and choosing compatible motifs. The Thue-Morse sequence's locally symmetric, highly repetative and redundant, but non-periodic properties result in tilings with the visual impression of order within disorder.

    Ted Bell motivated me to write a program for constructing these tilings after I showed him a short description of the Thue-Morse sequence from a book (chapter 30 of M.R. Schroeder "Number Theory in Science and Communication", Springer, Third edition 1997). He realized and sketched the basic tiling scheme, a natural dual division of the plane based on the tiling, and a higher order pattern that emerged. He also devised and made a sketch of this Gray code Thue-Morse binary fractal pattern. Since then we have thought about how to find interesting motifs (motifs such that edges match in non-trivial ways), variations of the basic tiling pattern, and extensions to sequences with more than two symbols.

The Thue-Morse sequence

    The Thue-Morse sequence is a non-periodic sequence of any two symbols:

or

There are several methods for constructing the sequence. One algorithm involves repeated concatenation;

Another method is more general - a recursive symbol replacement system. Starting with a, replace a with a b and b with b a, and then repeat these replacement rules indefinitely, always using the results as the input for the next generation:

or

Both algorithms result in the same series of generations of symbol strings:


or


    All sub-sequences (sets of adjacent symbols) will reoccur in this sequence. This can be demonstrated using the concatenation algorithm; since the complement of every sub-sequence is repeated, after two repetitions the original sub-sequence (the complement of the complement) will occur. But any sub-sequence never reoccurs at the same spacing throughout the sequence. So the sequence is non-periodic, but filled with redundant sub-sequences.

    Also, some substrings never reoccur adjacent to each other. For example a a a a and a b b a a b b a doesn't occur anywhere in the sequence. In fact, three of the same symbols, or three sets of any sub-sequence, in a row (e.g. a a a and b b b, or b b a a b b) doesn't occur. This property is called "cube-free".

[To Do: Overlap free, WWa also doesn't occur, see Mathworld and Wikipedia]
 

Construction of a 2-D Thue-Morse pattern

    A 2-D Thue-Morse pattern, where each row and column is a Thue-Morse sequence, can also be formed by a recursive concatenation as described above. The complement of an array of symbols is concatenated to itself, first in one direction and then the other:

1st generation (corresponding to : a b ... b a ... ) The two symbols, distinguished by color (black and white).

2nd generation (corresponding to : a b b a ... b a a b b a a b a b b a ... ) Note that rows and columns are all Thue-Morse sequences.

3rd generation Odd generations are not bilaterally symmetric (horizontally or vertically), but are symmetric across the diagonals.

4th generation Even generations are bilaterally symmetric as well as symmetric across the diagonals.

8th order, click for large version

    A recursive symbol replacement system that results in the same 2-D Thue-Morse pattern:

...

    For examples and discussion of similar symbol replacement systems, see "Simple recurrent sequences and simple fractal patterns".

[To Do: L-shaped patterns don't occur in 2-D, and other properties.]

    All of the tilings on this page are formed by replacing these 2-D arrays of symbols with two square or rectangular motifs; the motifs are used as symbols. Many of the tilings are dual: the motifs of the two tiles are geometrically related. In most of these dual tilings, the two motifs are related by a 90 degree rotation.

3-D Thue-Morse pattern (Thue-Morse cube)

    A 3-D (or higher dimensional) Thue-Morse pattern is formed by extension of the one and two dimensional algorithms (see above). The recursive symbol replacement system is represented as:
where the symbols (black, white squares) occupy a cube's coordinate volume elements. 

A surface rendering (sterero pair, cross view) of the 3-D Thue-Morse pattern, or Thue-Morse cube, using empty and filled space as symbols. Third generation, 8x8x8.	A 2-D slice through a symmetry plane of the 3-D Thue-Morse cube (at left). Seventh generation, 128x128x128. The long range self-similar structure of the Thue-Morse pattern is more easily seen in this slice than in the 2-D square system's pattern. Notice the slightly lighter/darker trapezoids that repeat at different scales; it is a discrete similarity tiling.

[To Do: Reference and link to 3-D L-system code. Include example volumes.]


Redundant Quadrapii

A basis motif, or tile. (see Logarithmic spirals, waves and tilings for details and Matlab code)

A pair of square motifs formed by a combination of 2x4 basis motifs rotated and mirrored. Note that the right set of 2x2 basis motifs are a  90 degree rotation of the left set of 2x2 basis motifs. [To Do: Include recursive replacement system graphic.]

Fourth order tiling of the basis tile set.

The tiling, colored by shapes of contiguous regions. Shape relief rendering done with Matlab morphological erosion and Space Software. [To Do: Add example volume and Matlab erosion code.]

Orthologia

Thue-Morse in rabbit land

Orthologia twist (animation) Ortho_twist_640_640.swf   10 MB, 640 x 640 px. Ortho_twist_640_480.wmv  7 MB, 640 x 480 px.

Othologia trispiralis

    An imaginary beast, a bugit, based on a logarithmic spiral similarity tiling and the Thue-Morse sequence. [To Do: Context of a square tesselation and Thue-Morse coloring.]

    The basis pattern (at left) is an infinite dissection of the plane by logarithmic spirals, a binary fractal. It's a checkerboard division (8x2) of the plane by logarithmic spirals with a pitch of +/- pi/4 radians. The checkerboard is colored (orthogonal to the contours) by the third order (2^3 = 8 element) Thue-Morse sequence [0 1 1 0 1 0 0 1]. The relative phase between the two sets of opposite chirality spirals rotates through pi/2 radians; in this example the phase of one set is fixed.

    There is a nice bi-stable perception illusion in the animation (above left): when I first see it, I percieve a wholistic pattern rotating CW and shrinking. But after a short time, I see half the contours as fixed, and the other half rotating (with no shrinking). Try fixating on a single edge point to experience the second percept.

    Also see description, notes and code for the Orthologia images.


Four knot

    A 2-D Thue-Morse pattern where the symbols are replaced by a motif that visually connects all adjacent symbols. The result is a woven pattern, with each "strand" forming a simple closed loop.

The two square motifs, side-by-side, where each motif is a pi/2 rotation of the other. The recursive replacement system that results in the 2-D Thue-Morse pattern.

Oblique viewpoint rendering of the motif used to construct Thue-Morse chain images. (Stereo pair, cross-view.) Constructed and rendered with Space Software, using a single chiral spline segment, rotated/mirrored four times. (Credit to Greg Scott for writing the spline code.) curveA_b_4.vol.gz (2 MB)

The Thue-Morse tiling.

The pattern after a pi/4 rotation and coloring of connected elements -- only those elements that are closed on this portion of the potentially infinite tiling.

Matlab command (for the Thue-Morse tiling of this motif pair):
>> nimOut = L_system_tiling( 'TM', 4, 2, 1, 0, 'Chain_bc_motif_thumbnail.jpg', 0, [0 1; 1 0], [1 0; 0 1] );

    Why this works (nested circuits in this weave pattern, colored by connectivity in the left image) is a mystery to me. How would a larger Thue-Morse pattern with the same motifs be connected? I designed the motif, shading and coloring, but I didn't design the pattern; I found it.

[ To Do: Tiling variations, their basis tiles, colorings, and comments ]

Matlab code for general Thue-Morse tilings

    Here's the Matlab code that generates these patterns, of any order, from a set of motifs:  

The code is reasonably clean, but a bit hard to follow, not very flexible, and not well documented.

------11/20/07-------
    I generalized this program, so it can generate patterns and tilings of any one or two dimensional L-system, not only the Thue-Morse system. See L-system program and code, and the work-in-progress "Simple recurrent sequences and simple fractal patterns" for related examples. The sytntax and formating of the motif is different for the L-system code, but the basic 2-D Thue-Morse pattern (8th generation) is generated by the Matlab command:

 --------------------------

    The one dimensional Thue-Morse sequence can be easily generated using Matlab's syntax. Using [0,1] as the symbols, a sequence that is 2ⁿ elements long is generated (using the logical NOT operator "~") with the code:

[ To Do: Ideas for the future, references ]

------------------------------------
There are no restrictions on use of the images or code on this page. Claiming to be the originator of the material, explicitly or implicitly, is bad karma. A link (if appropriate), a note to dow[at]uoregon.edu, and credit are appreciated but not required.

Comments are welcome (dow[at]uoregon.edu).