# Symmetry and fractals

( previous, home, next )

In this chapter, we extend the ideas of similarity and symmetry cases of self-similarity which leads to fractals and somewhat amazingly explains the basics of plant structure and growth.

## Fractal dimension and power laws

Anther interesting hypothesis for the origin of power laws is that nature has a fractal geometry and the odd power-laws we witness are a consequence.

Box dimension/fractal dimension/cover dimension is a way of quantifying the “dimension” of a set by how the cover count of that set scales with cover radius. The simplest example is box dimension. Imagine we have a subset of a rectangle we wish to study. One thing we can do is to discretize the subset by laying down a square grid over our rectangle and asking which squares intersect the set. This would give us a simplified representation of the subset. However, we know this representation will be inaccurate in the same way a low resolution bitmap image is inaccurate. We can improve on the inaccuracies by using a finer grid.

The down-side of higher resolution is that more boxes are needed to cover the subset. So it’s useful to know how the number of boxes changes as we reduce the grid size. Let $$\delta$$ be the distance between grid lines and $$n(\delta)$$ be the number of $$\delta \times \delta$$ boxes needed to cover the subset. If the subset is a finite number of points, then $$\lim _ {\delta \rightarrow 0} n(\delta)$$ is the number of points in the set. But if the subset if infinite, $$n(\delta)$$ may exhibit scaling law behavior as the grid becomes infinitely accurate.

If the set is a simple line, $$n(\delta) ~ \frac{1}{\delta}$$. If the set is a simple line, $$n(\delta) ~ \frac{1}{\delta}$$.

Consider Sierpinski’s Triangle gasket, starting from one initial equilateral triangle. Let’s tile the gasket with triangles of side length $$\delta$$ and count them, so $$n(\delta)$$ is the number of pieces.

$n(\delta/2) = 3 n(\delta)$

This is a functional equation, and has solution

$n(\delta) = \frac{C}{ \delta^{\log(3)/\log(2)}}$

$$A(\delta/2) = (1/4) A(\delta)$$

## Symmetry and Self-similarity

Trigonometry and Cartesian geometry are powerful tools, but one aspect of geometry that they do not address is symmetry. Symmetry is a mysterious but common phenomena in nature. We humans and many animals have bilateral symmetry. Snowflakes, bee hives, plants, and other things have their own symmetries. Some examples are shown above, ranging in scale from the microscopic to the intergalactic.

We can often make use of symmetries in our models and calculations. For example, to approximate the area of an ellipse $$x^2 + 4 y^2 = 1$$, it is enough to integrate the area of a quarter-ellipse and multiply by 4: $\frac{\pi}{2} = 4 \int _ {0}^1 \sqrt{1-2 x^2} dx.$ When a problem is radially symmetric, we might simplify our equations by using polar coordinates. And when a function has periodic symmetry, we can make use of Fourier analysis to simplify it.

The mathematical study of symmetries is commonly considered a subfield of “group theory”. We will not delve into group theory here; while the basic ideas are relatively intuitive, the abstract mathematical translation of these ideas sometimes does more to obscure than illuminate. However, there is one subtopic in symmetries that is particularly interesting from a modeling perspective: self-similarity. Self-similarity is a phenomena we sometimes observe in the natural world, were small parts of an object are very similar to larger parts that they make up.

The most familiar example of this may be a fern leaf, where each large leaf is make up of smaller leaves with similar shapes to the large leaf they compose. In mathematics, there are objects like the Mandelbrot set where this self-similarity goes on over and over again at smaller and smaller scales forever – we call such objects fractals.

Another example commonly invoked is the shape of the coastline of an island. From a satellite photograph, it might seem like an island has a relatively well-defined coast. But as we zoom on, we discover bays, harbors through which the cost winds. If we zoom in farther, we find marshes and beaches with there own twists and turns, and if we zoom in farther still, we find individual rocks around which the coastline turns (ignoring tidal affects, for the sake of argument). The coastline has a degree of self-similarity as we zoom in – it can be modelled as a fractal.

[Show code]
from pylab import *

def main():
p = 0.5
x =[ 0., 1.]
for t in range(12):
Y = []
for i in range(len(x)-1):
y = (x[i+1] - x[i])*0.5
q = y*1j*float(randn(1))*p
Y.append(x[i])
Y.append(x[i]+y+q)
Y.append(x[-1])
x = Y
s = 0.1
x.insert(0,0-s*1j)
x.append(1-s*1j)
x = array(x, dtype=complex)
fill(x.real, x.imag, 'k')
xlim(0,1)
ylim(-0.5,0.5)
axis('equal')
savefig('coast.png',dpi=600, transparent=True)

main()

Fractals can occur in surprising places. Another classic example is found in a simple model of persuasion. Suppose we have a person who listens to 3 different sources of propaganda. Each time they hear from one of these sources, their overall attitude shifts a fixed proportion towards that source. But which propaganda source they hear from each time is a drawing of lots, and so the changing of their attitude follows a particular kind of random walk.

[Show code]
#!/usr/bin/env python

"""
Chaos game described in "Strange new science of chaos" documentary.

and "Fractal Geometry"
"""

import random
from matplotlib.pyplot import *
from scipy import exp, pi

#b = (1.+0j, 0+1.j, 0.+0j)
#b = (1, exp(pi*8j/12.), exp(-pi*8j/12) )
b = (1j, exp(pi*14j/12.), exp(-pi*2j/12) )

def F(r, n_steps = 4000):
x = random.choice(b)
e = []
for t in range(n_steps):
#e.append((x.real + 0.5*x.imag, x.imag*c ))
e.append( (x.real, x.imag) )
x += r*(random.choice(b) - x)
return e

def main():
r = 0.50
e = F(r)
u, v = zip(*e)
plot(u,v,'.',markersize=1)
xlim(-1.1,1.1)
ylim(-0.6,1.1)
#show()

main()

This model of attitude change doesn’t have anything in common with ferns. But when the shift in attitude is 50-50 each step and we plot all the values the person’s attitude takes over time, the picture becomes a rather shocking fractal that we call Sierpinski’s triangle gasket.

## Fibonacci’s rabbits

One of the oldest cases of self-similarity can be found in an arithmetic problem that is more than 800 years old – though at the time, the author and readers didn’t recognize it as such. In 1202, Leonardo “Fibonacci” Pisano published a book Liber Abacci which introduced the western world to the Hindu-Arabic place-valued decimal system we still use today. Within the book was the following problem.

How Many Pairs of Rabbits Are Created by One Pair in One Year?

A certain man had one pair of rabbits together in a certain enclosed place, and one wishes to know how many are created from the pair in one year when it is the nature of them in a single month to bear another pair, and in the second month those born to bear also.

Fibonacci provided a solution as well:

Because the above written pair in the first month bore, you will double it; there will be two pairs in one month. One of these, namely the first, bears in the second month, and thus there are in the second month 3 pairs; of these in one month two are pregnant, and in the third month 2 pairs of rabbits are born, and thus there are 5 pairs in the month; in this month 3 pairs are pregnant, and in the fourth month there are 8 pairs, of which 5 pairs bear another 5 pairs; these are added to the 8 pairs making 13 pairs in the fifth month; these 5 pairs that are born in this month do not mate in this month, but another 8 pairs are pregnant, and thus there are in the sixth month 21 pairs; [p284] to these are added the 13 pairs that are born in the seventh month; there will be 34 pairs in this month; to this are added the 21 pairs that are born in the eighth month; there will be 55 pairs in this month; to these are added the 34 pairs that are born in the ninth month; there will be 89 pairs in this month; to these are added again the 55 pairs that are born in the tenth month; there will be 144 pairs in this month; to these are added again the 89 pairs that are born in the eleventh month; there will be 233 pairs in this month.

As you can see, this problem can be solved rather directly, and doesn’t seem to have anything to do with symmetry. But suppose we visualize what was happening to the pairs of rabbits using algebra. Let each character $$j$$ represent one pair of juvenile rabbits, and each character $$a$$ represent one pair of adult rabbits. In one month, each juvenile pair becomes an adult pair ($$j$$ becomes $$a$$), and each adult pair becomes creates a new juvenile pair ($$a$$ becomes $$aj$$). If we start with one pair of juvenile rabbits, then the population’s state changes as follows:

Month State Pair Count
0 j 1
1 a 1
2 aj 2
3 aj a 3
4 aj a aj 5
5 aj a aj aj a 8
6 aj a aj aj a aj a aj 13
7 aj a aj aj a aj a aj aj a aj aj a 21

These are getting very long, but we can already see a pattern. Notice that each state from month 2 on is made up of the previous two states joined together: $$aj = (a) (j)$$, $$aja = (aj)(a)$$, … The sequence of states is self-similar. It follows immediately that the number of pairs in generation $$t$$, $$n(t)$$, is the sum of the number of pairs in the previous two generations, $$n(t) = n(t-1) + n(t-2)$$.

## Building fractals with self-similar sequences

The sequence of letters in Fibonacci’s rabbit problem is fun, but rather parochial on second glance. There is a form of self-similarity in the sequences, each string being built from the previous strings, but there does not seem of much interest beyond that. The big leap forward came from Aristid Lindenmayer in 1968. Lindenmeyer conjectured that self-similar strings like Fibonacci’s have meaning and that these and other “rewrite systems,” i.e., substitution rules for replacing characters with other characters, lead to patterns that can be interpreted as geometric descriptions of real-world objects.

### Turtle graphics with python code

Before we precede further with our modeling, we need to make a brief diversion to introduce a Logo. Logo was a computer language developed in the 1970s to help kids learn to program. One of the big ideas of Logo was to make programming intuitive using graphics. Logo used a cursor it called the “turtle”. You would give the turtle instructions like “move forward 10 units” and “turn right 50 degrees” and you could see the turtle moving across the computer screen following your instructions. By giving the turtle a carefully selected list of instructions, you could make it draw cool things. Over the decades, Logo has been reimplemented and extended to keep up with changes in our technology. Turtle graphics have been implemented in javascript, for example.

### Lindenmayer Systems

The graphics of the Logo language are more than just a kids’ toy – they can be a powerful tool for geometric modeling. This is done by mapping each character of the string to a turtle command like “backward 10” or “turn left 30 degrees”.

As a first example, suppose we let ‘f’ represent forward drawing, ‘-’ represent a left turn of 60 degrees, and ‘+’ represent a right turn of 60 degrees. Start with an equilateral triangle that is encoded as $$f++f++f++$$. Now, at each iteration, replacing the all the occurrences of side $$f$$ with $$f-f++f-f$$, a new segment containing part of a triangle. Using turtle graphics to draw the initial condition and the first 3 iterations, we get the following.

If this rewriting is continued indefinitely, we will obtain the perimeter of a Koch snowflake, a fractal that starts as an equilateral triangle, and is expanded in each step by adding new equilateral triangles to the middle of each side.

[Show code]
from lsystem import LSystem, Turtle

def main():
# Turtle setup
t = Turtle()
t.setperiod(0) # number of actions between refreshes
t.setcolor('white')
t.setpensize(1)
t.ht().rt(90).pd()
#t.ht().pu().bottom().pd() # initial position and pen state

# map from symbols to turtle actions
actionmap = { \
'f' : lambda : t.forward(z), \
'+' : lambda : t.left(60.), \
'-' : lambda : t.right(60.), \
}

# Rule specifications
rule = ('f', 'f-f++f-f')
ic = 'f++f++f++' # initial condition
n = 4 # number of iterations
z = 2.0 # step size

L = LSystem(rule)
for i in L.itr(n).on(ic).str():
actionmap[i]()
t.sleep(5) # refresh and sleep

main()

Our second example is the dragon curve, a fractal brought to popular attention by Michael Crichton’s exceptional science fiction novel Jurassic Park (which is far better than the movie). Consider a rewrite system where $$f$$ is forward, $$-$$ is right 90 degrees, $$+$$ is left 90 degrees, and there are two dummy variables $$x$$ and $$y$$ which do not correspond to any action. If we start with $$fx$$, and apply the rewrite rules $x \rightarrow x+yf+, \quad y \rightarrow -fx-y.$ It starts with a segment. Then a right angle. At the earliest iterations, the steps give no hints of what the future holds. But as iterations progress, changes become more complicated, even surprising. New patterns coalesce, and are immediately subsumed into elaborations, until something entirely novel and unanticipated emerges.

Here is a dragon curve rewrite animation

For a final example, let’s allow segments of different colors to have different rewrite rules. Specifically, let $$Y$$ represent the yellow segments, $$G$$ represent the green segments, $$-$$ be a left turn of 60 degrees, and $$+$$ be a right turn of 60 degrees. Start with a single yellow segment $$Y$$. Then the rewrite iteration is performed based on substitutions of the form

$Y \rightarrow -G+Y+G-, \quad G \rightarrow +Y-G-Y+$

Drawing the first few iterations, we obtain the following.

As the number of iterations increases, we obtain a curve called the arrowhead curve, which creates another form of Sierpinski’s Triangle gasket.

[Show code]
from lsystem import LSystem, Turtle
import sys

def main():
# Turtle setup
t = Turtle()
t.setperiod(1) # number of actions between refreshes
t.setpensize(3)
t.ht().pu().bk(120).rt(90).bk(120).pd() # initial position and pen state

# map from symbols to turtle actions
actionmap = { \
'Y' : lambda : t.setcolor('yellow').forward(z), \
'G' : lambda : t.setcolor('green').forward(z), \
'+' : lambda : t.left(60.), \
'-' : lambda : t.right(60.), \
}

# Rule specifications
rule = (('Y','+G-Y-G+'), ('G','-Y+G+Y-'))
ic = 'Y' # initial condition
n = 4 # number of iterations
z = 400./2**n # step size

L = LSystem(rule)

#print L.dup(n).on(ic).str()

SA = L.itr(3).on(ic).str()
print(SA)
for i in SA:
actionmap[i]()

if __name__ == '__main__' or sys.argv[0] == __name__:
input("<return when done>")
else:
t.sleep(5)

main()

It should noted that these “forward” problems of creating a curve from iteration of a rewrite rule is easy, but the corresponding “backward” problems of determining the rewrite rule based on the curve can be substantially harder. For example, the third iteration in the construction of the arrowhead curve is encoded by the string

+f-f-f+f+f+f+f-f-f-f+f+f-f-f-f-f+f+f-f-f-f+f+f+f+f-f-f

where $$f$$ is used to represent any line segment. This encoding is missing the important information about the color of the segments, which has been lost from the drawing. It is also missing turns of the form +- and -+ which can appear in the rewrite process but cancel each other out. With the colors and extra turns restored, the encoding of the third iteration was actually

+-+G-Y-G++-Y+G+Y-++G-Y-G+–+-Y+G+Y–+G-Y-G+–Y+G+Y-+–+G-Y-G++-Y+G+Y-++G-Y-G+-+

### Plant Morphology

While the use of rewrite systems to create geometric fractals is interesting, the really compelling application is plant morphology. After extending the turtle language to include a simple stack that remembers the turtles location and orientation, and using “[" to push the current state onto the stack, and using “]” to pop a state off the stack, one can find some simple rewrite rules that create images having remarkable similarity to real plants and seaweeds.

[Show code]
from lsystem import LSystem, Turtle

def main():
# Turtle setup
t = Turtle()
t.setperiod(40) # number of actions between refreshes
t.setcolor('green')
t.setpensize(1)
t.ht().pu().bottom().pd() # initial position and pen state

# map from symbols to turtle actions
actionmap = { \
'F' : lambda : t.forward(z), \
'[' : lambda : t.push(), \
']' : lambda : t.pop(), \
'+' : lambda : t.left(d), \
'-' : lambda : t.right(d), \
}

# Rule specifications
rule = ('F','F[+F]F[-F]F')
ic = 'F' # initial condition
n = 5 # number of iterations
d = 25.7 # turn angle
z = 1.0 # step size

L = LSystem(rule)

for i in L.itr(n).on(ic).str():
actionmap[i]()

t.saveimg('lsys_planta.png')

main()

## Discussion

Unlike many of the areas of math modelling we will study, fractal modelling is very open-ended area of descriptive geometry. One interpretation of modeling is that it is a search for simple ways to express the important features of complicated things. In that sense, these models are very successful. On the other hand, as far was we’ve presented things, construction of fractal models is largely trial-and-error. We have not presented any system for determining which rewrite rules or algorithms should be used to create specific fractal geometries. Mysteries and opportunities abound, and we leave it to you to explore the ideas further.

# Exercises

1. Consider the L-System $$(Y \rightarrow Y-G+Y+G-Y, G \rightarrow G+Y-G-Y+G)$$ where $$-$$ is a left turn of 90 degrees, $$+$$ is a right turn of 90 degrees, and both $$Y$$ and $$G$$ represent forward motion of one unit.

1. Draw 2 iterations of this L-system applied to the initial condition $$Y$$.

2. Use your answer to (a) to draw the result of two iterations of the L-system applied to the initial condition $$Y+Y+Y+Y$$.

2. (Hard) Find a short encoding for the figure below using a rewrite rule similar to those discussed in class.

3. (Hard) Find the shortest encoding for the figure below using a rewrite rule similar to those discussed in class.

4. (Open) Develop rewrite systems that capture the distinctions between the tree profiles below.

( previous, home, next )