Mark Dow

Geek art

Simple recursive systems and fractal patterns

Thue-Morse sequence tilings and patterns

    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). Ted 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 nontrivial ways), variations of the basic tiling pattern, and extensions to sequences with more than two symbols.

The Thue-Morse sequence
Construction of a 2-D Thue-Morse pattern

Specific examples of 1 and 2-D Thue-Morse tilings and patterns
Thue-Morse double chain, link to
Double chain
Redundant Quadrapii, link to
Redundant Quadrapii
Orthologia, link to
Orthologia
Thue-Morse Four knot tiling, link to
Four knot



                                           
Thue-Morse rings, link to
Rings
Thue-Morse aifoil, link to
Airfoil
Thue-Morse folding, link to
Folding
                                           

Thue-Morse tilings of other motifs
Thue-Morse X tiling, link to Thue-Morse diag1 tiling, link to Thue-Morse  dual twist tiling, link to Thue-Morse half-diagonal tiling, link to Thue-Morse half-diagonal shaded tiling, link to Thue-Morse star1 tiling, link to Thue-Morse star tiling, link to

Neigborhood dependent Thue-Morse tilings
Thue-Morse polygonal tiling, link to Thue-Morse mesh tiling, link to Thue-Morse  double double tiling, link to Thue-Morse double diagonal tiling, link to Thue-Morse long diagonal tiling, link to Thue-Morse space-filling colored tiling, link to Thue-Morse binary pyramid tiling, link to Thue-Morse semi-circle tiling, link to Thue-Morse anti 2 tiling, link to

3-D Thue-Morse pattern (cube)
Thue-Morse cube, link to

Thue-Morse tesselations of simple 3x3 motifs
Three bars motifs, link to Three bars motifs, link to Decimated three bars motifs, link to Decimated three bars motifs, link to Decimated three bars motifs, link to Plus motif, link to Plus motif decimated, link to Plus motif decimated, link to Plus motif decimated, link to

Matlab code for general Thue-Morse tilings

Matlab code for neigborhood dependent Thue-Morse tilings

References


The Thue-Morse sequence

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

 a b b a b a a b b a a b a b b a b a a b a b b a a b b a b a a b ...
or
Thue-Morse sequence, 1-D

There are several methods for constructing the sequence. One algorithm involves repeated concatenation;
{
Start with one symbol (a, or a black square) and concate its complementary symbol string (b, or a white square).
Repeat this complementary concatenation using the result as the input to the next repetion.


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:

a; { a -> a b },  { b -> b a }
or
Thue-Morse recurrent algorithm

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

generation 0:  a
generation 1:  a b
generation 2:  a b b a
generation 3:  a b b a   b a a b
generation 4:  a b b a   b a a b  b a a b  a b b a  
generation 5:  a b b a   b a a b  b a a b  a b b a    b a a b  a b b a  a b b a   b a a b  
.
.
.

    or
Thue-Morse sequence construction, by generation

    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:
2-D Thue-Morse, first generation
1st generation
(corresponding to :
a b ...
b a
...
)

B/W symbols
The two symbols, distinguished by color (black and white).
2-D Thue-Morse, second generation
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.
2-D Thue-Morse, third generation
3rd generation

Odd generations are not bilaterally symmetric (horizontally or vertically), but are symmetric across the diagonals.
2-D Thue-Morse, fourth generation
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:
2-D Thue-Morse algorithm graphic
2-D Thue-Morse by generation ...

    For examples and discussion of similar symbol replacement systems, see "Simple recursive systems 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 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. The two motifs can be related by a rotation, mirroring, luminance inversion, or any different coloring of the same pattern.

Double chain

    Chains are one dimensional analogs of chainmail weaves. There is less freedom in one dimension, and I thought all 1-D interlinkage would be periodic. But here's an example of a nontrivial non-periodic chain, a simple replacement of the Thue-Morse sequence with a universal motif pair.


Double chain algorithm graphic
The recursive replacement system of a single motif and its mirror image.
Thue-Morse sequence of double chain motifs, link to
The 5th generation chain. All links are 1, 3, or 5 units long.

Thue-Morse sequence of double chain motifs colored by chain, link to
The chain colored to highlight the two chains, red and blue.
Although the two chains are interlinked, they are independent in that, when taught, one can be shifted independent of the other.

Thue-Morse sequence of double chain motifs colored by link, link to
The chain colored to highlight the links. The two chains are distinguished as red-orange-yellows and blue-greens.

MATLAB command:
>> imOut = L_system_tiling( 'TM', [ng],  2, 1, 0, 'double_chain_close_motif.png', 0, [0 1], [1 0] );
where [ng] is the number of generations.

Redundant Quadrapii

basis tile for Redundant Quadrapii I, link to
A basis motif, or tile, formed of logarithmic spirals with a pitch of pi/4. See Logarithmic spirals, waves and tilings for details and Matlab code for generating logarithmic spiral divisions of the plane.
motif pair for Redundant Quadrapii I, link to
Two square motifs, side-by-side, 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.

Thue-Morse pattern with spiral motif algorithm graphic
The recursive replacement system that results in the 2-D Thue-Morse pattern.
Thue-Morse pattern outline for Redundant Quadrapii I
Fourth order Thue-Morse tiling of the motif pair.
Redundant Quadrapii I, link to
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.]

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

Some details on its construction, description and notes.

Orthologia

Thue-Morse in rabbit land
Thue-Morse in rabbit land, and link to larger version
Orthologia twist (animation)
Orthologia twist animation, link to
Ortho_twist_640_640.swf   10 MB, 640 x 640 px.
Ortho_twist_640_480.wmv  7 MB, 640 x 480 px.
Othologia trispiralisOrthologia trispiralis. link to
An imaginary beast, a bugit, based on a logarithmic spiral similarity tiling and colored by the Thue-Morse sequence. [To Do: Context of a square tesselation and Thue-Morse coloring.]

    The basis pattern (at left) is an infinite division 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 repetition of the third generation (23 = 8 element) Thue-Morse sequence [0 1 1 0 1 0 0 1], where 1 and 0 represent black and white. 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, and Logarithmic spirals, waves and tilings for details and Matlab code for generating logarithmic spiral divisions of the plane.


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.

Four knot 1 motif
The two square motifs, side-by-side, where each motif is a pi/2 rotation of the other.

Thue-Morse with Four knot motif algorithm graphic
The recursive replacement system that results in the 2-D Thue-Morse pattern.
oblique view of the Four knot motif, link to Oblique viewpoint rendering of the 3-D 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)
Four knot 1 uncolored pattern, link to
The Thue-Morse tiling.
Four knot 1, link to
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.

Thue-Morse tilings of other motifs

Thue-Morse X tiling, link to

Xi_motif
Xi_motif.png
(5x5 px.)
Thue-Morse diag1 tiling, link to

diag1 motif
diag1_motif.png
Thue-Morse  dual twist tiling, link to

dual twist motif
dual_twist_motif.png

dual_motif, large
Thue-Morse half-diagonal tiling, link to

Half-diagonal motif, link to
Half_diagonal_motif
Thue-Morse half-diagonal shaded tiling, link to

Half-diagonal motif, link to
Half_diagonal_shaded

6th generation pattern
Thue-Morse star1 tiling, link to

star1 motif
star 1 motif

star 1 motif, large
Thue-Morse star tiling, link to

star motif
star 1 motif

star motif, large

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:
3-D Thue-Morse algorithm graphic
where the symbols (black, white squares) occupy a cube's coordinate volume elements. 

3-D Thue-Morse pattern or cube, link to
diagonal slice of the3-D Thue-Morse cube, link to
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.]

Thue-Morse rings

     The algorithm for generating these two figures, a discrete and continuous representation of the Thue-Morse sequence, are nealy identical.
Thue-Morse rings, link to
Thue-Morse airfoil, link to Rendering of continuous rings with a range of generation offsets, link to
Each sequential generation of the Thue-Morse sequence in concentric rings, starting at the horizontal. The first generation is at the center. The black and white patterns are identical after a half turn about the center. It is a binary fractal. Each circle, centered at the patterns singular point, is patterned as the first elements of a Thue-Morse sequence, a longer part of the sequence at larger radii. The second generation is at the center. The prominant aliasing is due to the nature of the sequence, its arithmetic subsequences and how they interact with the integer lattice of the grid.  Rendering of continuous rings with a range of generation offsets.
(stereo pair, cross-view)

MATLAB commands:

>> Thue_Morse_rings( 100,  9, 1.0, true, true );     % Discrete version above.
% Harcoded information:
strFilename = 'Thue-Morse_rings.png';
bDiscrete = true;
nSize       = 2048;
flC = nSize/2;

>> Thue_Morse_rings( 100, 13, 2.0, true, true );     % Continuous version above.
% Harcoded information:
strFilename = 'Thue-Morse_airfoil_2.png';
bDiscrete = false;
nSize       = 2048;
flC = 1300;             % ~10.2*nSize/16 - 1;

See Thue_Morse_rings.m header for hardcoded parameters of variations and other details.

Thue-Morse foldings

     How might a Thue-Morse (TM) sequence occur through physical processes? Might something like a linear chain of algae, where two characteristics are TM along the chain, form naturally? Or a non-periodic crystal with molecular sheet structure in a TM sequence?
    Repeated folding is a recursive process, and sequences related to the TM sequences can be encoded in the direction of folds and the layering of the folds. This is an example of a maze derived from such a folding. Traversing the maze from one red dot to the other crosses the horizontal midline in a TM sequence, where up and down (direction of crossing) are the symbols of the TM sequence.
Thue-Morse folded maze


    See Thue-Morse sequence foldings for how this was constructed and some discussion.

Programs and code for general Thue-Morse tilings, MATLAB


    The MATLAB code and resouces for generating these Thue-Morse systems, and any one or two dimensional L-system on a square grid are available at L-system program and code. Also see the work-in-progress "Simple recurrent sequences and simple fractal patterns" for related examples.

    The MATLAB syntax for generating the 2-D Thue-Morse pattern is:

>> imageMatrix = L_system_tiling( 'TM', [ng], 2, 1, 0, 'motif.jpg', 0, [0 1; 1 0], [1 0; 0 1] );
where ng is the number of generations desired, and motif.jpg is an image file containing a pair of side-by-side motifs.

    Many of these tilings are formed by replacing each symbol of a Thue-Morse pattern with a square (or rectangular) image. This can be done manually using copy/paste in an image editor, but for large tilings it is convenient to automate the process.

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

{
% Construct a Thue-Morse vector of length 2^n:

vctTM = 0;    % initial element [0,1]

for i = 1 : n    % where n is the number of generations
   
    % Double the length, using the compliment of the original array element(s) as the new element(s).
    vctTM( length( vctTM ) + 1 : 2*length( vctTM ) ) = ~vctTM; 
end
}

    This can be extended to the two dimensional Thue-Morse pattern, where each row and column is a Thue-Morse sequence. [To Do: Show this code too.]


Program and code for neigborhood dependent Thue-Morse tilings, MATLAB

    Some of these tilings are neighborhood dependent: the square (or rectangular) image that replaces the symbol depends on what symbols surround the symbol that is replaced. For the Thue-Morse pattern there are a only a small set of possible nearest neighbor patterns. [To Do: Illustrate the six nearest neighbor configuations and rotations.]

    A Matlab program used for a few special cases:
Thue_Morse_tiling.m

    The program is not general as it only handles a couple kinds of neighborhood relationships and possible replacement . How it operates and the reasoning behind the particular orderings is not obvious, even to me.

    Example usage (see file header for details):  
 
>> imageMatrix = Thue_Morse_tiling( [ng],'motif.jpg' , 2 );
where ng is the number of generations desired, and motif.jpg is an image file containing a motif specified by a 2x4 set of basis elements.

this motif image:
example" letters" basis tile set
letters_8motif.png
results in this tiling, with ng = 3:example Thue-Morse tiling

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


[ To Do: Ideas for the future ]


What does the autocorrelation of TM, TM(t), look like as the string length goes to infinity?

References

OEIS A010060

C. A. Pickover, Wonders of Numbers, Adventures in Mathematics, Mind and Meaning, Chapter 17, 'The Pipes of Papua,' Oxford University Press, Oxford, England, 2000, pages 34 - 38.

C. A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 60.


"The computational generative patterns in Indonesian batik"
Situngkir, H. (2008)

The paper discusses the terminology behind batik crafting and showed the aspects of self-similarity in its ornaments. Even though a product of batik cannot be reduced merely into its decorative properties, it is shown that computation can capture some interesting aspects in the batik-making ornamentation. There are three methods that can be exploited to the generative batik, i.e.: using fractal as the main source of decorative patterns, the hybrid batik that is emerged from the acquisition of L-System Thue-Morse algorithm for the harmonization within the grand designs by using both fractal images and traditional batik patterns, and using the random image tessellation as well as previous tiling algorithms for generating batik designs. The latest can be delivered by using a broad sources of motifs and traditionally recognized graphics. The paper concludes with certain aspects that shows how the harmony of traditional crafting and modern computation could bring us a more creative aspects of the beautiful harmony inherited in the aesthetic aspects of batik crafting.

Two-dimensional photonic aperiodic crystals based on Thue-Morse sequence
Luigi Moretti and Vito Mocella, Optics Express, Vol. 15, Issue 23, pp. 15314-15323 (2007)

We investigate from a theoretical point of view the photonic properties of a two dimensional photonic aperiodic crystal. These structures are obtained by removing the lattice points from a square arrangement, following the inflation rules emerging from the Thue-Morse sequence. The photonic bandgap analysis is performed by means of the density of states calculation. The mechanism of bandgap formation is investigated adopting the single scattering model, and the Mie scattering. The electromagnetic field distribution can be represented as quasi-localized states. Finally, a generalized method to obtain aperiodic photonic structures has been proposed.


"Number Theory in Science and Communication", chapter 30, Springer, Third edition 1997 (at Amazon)
M.R. Schroeder
(Manfred Robert Schroeder)
Universitätsprofessor Physik

University of Goettingen, Germany



------------------------------------
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).