In this lecture, we extend the ideas of similarity and symmetry previously studied to consider cases of self-similarity which leads to fractals and somewhat amazingly explains the basics of plant structure and evolution.

- Symmetry, by Hermann Weyl, 1952.
- Algorithmic Beauty of Plants by P. Prusinkiewicz
- Chaos: Making a new science by James Gleick
- Fractals using iterated function systems (IFSs) at Yale
- The man who uncovered the secret lives of snowflakes
- Kepler and the snowflake

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 \(2 x^2 + y^2 = 1\), it is enough to integrate the area of a quarter and multiply by 4: \[\pi = 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 study of symmetries makes use of a topic in mathematics called “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.

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.

[Show code]

```
#!/usr/bin/env python
"""
Chaos game described in "Strange new science of chaos" documentary.
https://www.youtube.com/watch?v=fUsePzlOmxw
See also, The color of infinity with A. C. Clark
https://www.youtube.com/watch?v=Lk6QU94xAb8
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)
savefig('AttitudesGasket.png', bbox_inches = 'tight', transparent=True)
savefig('AttitudesGasket.pdf', bbox_inches = 'tight')
#show()
main()
```

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.

If we are only interested in the numbers and not the particular order, we can introduce a shorter notation using exponents to do the counting. Let \(j^{x(n)} a^{y(n)}\) represents \(x(n)\) juvenile pairs and \(y(n)\) adult pairs in month \(n\).

\[j^{x(n+1)} a^{y(n+1)} = (a)^{x(n)} (ja)^{y(n)} = j^{y(n)} a^{x(n)+y(n)}.\] This rewrite rule can be interpreted as a system of two first order difference equations for the numbers of juvenile and adult pairs after each month \(n\). \[\begin{align*}
x(n+1) &= y(n) \\
y(n+1) &= y(n)+x(n)
\end{align*}\] These two equations can be changed into a single equation for the total numbers of pairs \(F(n)\) as follows. \[\begin{align*}
F(n) &= y(n) + x(n),\\
F(n+1) &= x(n+1) + y(n+1) \\
&= y(n) + y(n) + x(n) \\
&= F(n) + y(n),\\
F(n+2) &= F(n+1) + y(n+1) \\
&= F(n+1) + y(n) + x(n) \\
&= F(n+1) + F(n).
\end{align*}\] So, the governing equation for the total number of rabbit pairs, which we can call Fibonacci’s equation, is the second-order linear difference equation

\[F(n+2) = F(n+1) + F(n).\] Since we know \(F(0) = 1\) and \(F(1) = 1\), we can calculate the solution sequence directly: \[1,1,2,3,5,8,13,21,34, \ldots\] A formula for the full solution that can be used to skip terms is found using the guess \(F(n) = C \lambda^n\). In order to find the specific solution, we can use our initial conditions to determine the values of \(C\). Python’s sympy toolbox can speed this process up for us.

[Show code]

```
from sympy import symbols, rsolve, Eq, latex
F, n = symbols('F, n')
equation = Eq(F(n+2), F(n) + F(n+1))
initialcondition = {F(0):1, F(1):1}
# rsolve is used to solve common difference equations
sol = rsolve(equation, F(n), initialcondition)
pprint(sol)
print [ sol.subs(n,i).expand() for i in range(10) ] # to check result
print latex(Eq(F(n), sol))
```

\[F{\left (n \right )} = \left(\frac{1}{2} + \frac{\sqrt{5}}{2}\right)^{n} \left(\frac{\sqrt{5}}{10} + \frac{1}{2}\right) + \left(\frac{1}{2}- \frac{\sqrt{5}}{2}\right)^{n} \left(\frac{1}{2}- \frac{\sqrt{5}}{10}\right)\]

It’s rather cool that, even though the solution formula involves the \(\sqrt{5}\), our sequence is all integers. Actually, it’s not just the \(\sqrt{5}\) but the full **golden ratio** \(\phi:= (1+\sqrt{5})/2 \approx 1.618033\). The golden ratio was first discovered as part of the construction of perfect pentagons, and has been associated with numerology mysticism since the Pythagorian cult thousands of years ago. Since the reciprical of the golden ratio \[\frac{1}{\phi} = \frac{ -1 + \sqrt{5} }{2},\] the general solution of Fibonacci’s equation can be given as \[F(n) = a \phi^n + b \left(\frac{-1}{\phi}\right)^{n}\] Since \(\phi>1\), then as we do more iterations, the ratio of successive Fibonacci numbers, \[\lim _ {n \rightarrow \infty} F(n+1) / F(n) = \phi\]

The trick we’ve used above of representing objects algebraically is very useful, and can be applied very productively in a number of contexts as we will see below and later on.

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.

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.

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. With the colors restored, the encoding of the third iteration is

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

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

One interpretation: modeling is working to find simple ways to express the important features of complicated things.

Find the general solution of the second order linear homogeneous difference equation \(z _ {t+2} = 2 z _ {t+1} + z _ {t}\) and determine the specific solution when \(z _ 0 =1\) and \(z _ 1 = 2\).

Aphids are common insects known to reproduce parthenogenicly, with female aphids giving birth to only females for most of the year. Suppose there is 1 baby female aphid in a woman’s garden today. In 2 days, that aphid will become an adult and give birth to 1 baby aphid each day afterward. Find a single difference equation for the total number of aphids on day \(t\). (

*Do not attempt to solve this equation – it’s too much work for a homework problem.*)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.

Draw 2 iterations of this L-system applied to the initial condition \(Y\).

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

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

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

(Extra Hard) Develop rewrite systems that capture the distinctions between the tree profiles below.