Simple recursive systems and fractal 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.

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

Construction of a 2-D Thue-Morse pattern

Specific examples of 1 and 2-D Thue-Morse tilings and patterns

Double chain |
Redundant Quadrapii |
Orthologia |
Four knot |

Rings |
Airfoil |
Folding |

Neigborhood dependent Thue-Morse tilings

Matlab
code for general Thue-Morse tilings

Matlab code for neigborhood dependent Thue-Morse tilings

References

Matlab code for neigborhood dependent Thue-Morse tilings

References

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.

} 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 }

orBoth 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

orgeneration 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

.

.

.

.

.

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]

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

>> imOut = L_system_tiling( 'TM', [n_{g}],
2, 1, 0, 'double_chain_close_motif.png',
0, [0 1], [1 0] );

*where **[n*_{g}]
is the number of generations.

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. |
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. The recursive replacement system that results in the 2-D Thue-Morse pattern. |
Fourth order Thue-Morse tiling of the motif pair. |
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] );

>> nimOut = L_system_tiling( 'TM', 4, 2, 1, 0, '2x4_Log_spiral_motif_thumbnail.jpg', 0, [0 1; 1 0], [1 0; 0 1] );

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 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 (2

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.

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

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

% 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;

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.

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

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

>>
imageMatrix = L_system_tiling(
'TM', [n_{g}], 2, 1, 0, 'motif.jpg', 0, [0 1; 1 0], [1 0; 0
1] );

where n_{g }is the number of
generations desired, and motif.jpg
is an image file containing a pair of side-by-side motifs.

where n

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 2

{

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

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

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

}% 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

A Matlab program used for a few special cases:

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( [n_{g}],'motif.jpg' , 2 );

where n_{g }is the number of generations desired, and motif.jpg is an image file containing a motif
specified by a 2x4 set of
basis elements.

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

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

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

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

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