When does a fractal tree stay bounded, and when does it explode off to infinity? In the last post we looked at a few fractal trees and set up an interactive demo so we could get some intuition on what fractal trees and how their parameters influence how they look. Now let’s dive into some of the math behind them.

If you play around with the demo you’ll see that as you increase the scale parameters the tree quickly expands to fill the entire screen (though the demo automatically rescales things to counteract that somewhat). The demo only goes out to 100 layers from the root which is usually enough to be visually indistinguishable from an arbitrary number of iterations. However, in certain cases it may seem like the tree stops growing when really it has reached the limits of the demo. So the question is: when does the tree grow endlessly and when does it stay bounded? In order to answer this we’ll need to set up some formal definitions so that we have a firm base to build from.

A tree is a structure on the complex plane defined by four parameters: two rotation angles θ1,θ2[π,π] and two scaling factors s1,s2R+. You could alternatively use two arbitrary complex numbers, but keeping the rotation and scale separate is useful later. A tree is composed of branches, a branch is a line segment on the complex plane and will be written as (x,y). The branches that make up a given tree are defined as follows:

  1. (0,i) is a branch in the tree
  2. If (x,y) is a branch in the tree, then (y,y+s1eiθ1(yx)) and (y,y+s2eiθ2(yx)) are also branches in the tree

In other words, at the end of each branch we can add two more branches by rotating and scaling the previous branch according to the tree’s parameters. We could instead choose (0,1) as the initial branch which might feel a bit more natural, but I like (0,i) because it rotates the tree upright on a standard plot of the complex plane. This definition works well to showcase the recursive structure baked into these trees and is nicely compact and concise. However, it can be a bit difficult to work with when we want to start proving things. To that end, we’ll also set up an alternative definition based on infinite series which will let us take advantage of a lot of powerful pre-existing math.

A path is a sequence (dk)k=1 over the set {1,2}. It indicates a sequence of turns taken starting at the root of a tree, moving higher in the tree with each step.

Given a path (dk)k=1, let

bk={i,k=0ij=1ksdjeiθdj,k1 pk=j=0kbj

For any path and its corresponding sequence (pk)k=0, (pk,pk+1) is a branch in the tree for all kZ0

Show proof

Proceed by induction.

We have that p0=i and p1=i+isd1eiθd1. Since (0,i) is a branch in the tree, then (p0,p1)=(i,i+sd1eiθd1(i0)) is also a branch in the tree by the second rule in the definition of a tree.

Now, assume that (pk1,pk) is a branch in the tree. We have that

pk+1pk=bk+1=sdk+1eiθdk+1bk=sdk+1eiθdk+1(pkpk1)

Therefore

(pk,pk+1)=(pk,pk+pk+1pk)=(pk,pk+sdk+1eiθdk+1(pkpk1))

And (pk,pk+1) is a branch in the tree.

Therefore, by induction (pk,pk+1) is a branch in the tree for all k0.

For every branch (x,y) in the tree except (0,i), there is at least one path and corresponding sequence (pk)k=0 such that x=pk and y=pk+1 for some kZ0.

Show proof

This is a fairly simple induction proof, but relies on structural induction rather than regular induction.

For the base case, we start with the children of the root: (i,i+is1eiθ1) and (i,i+is2eiθ2). Each of these can be reached with any path that starts with d1=1 or d1=2 respectively. In that case you have for k=0, pk=i and pk+1=i+isd1eiθd1.

Now we assume that (x,y) is a branch in the tree which can be reached by the path (dj)j=1 such that x=pk and y=pk+1 for some k. Another branch can be constructed using the rule involving s1 and θ1 (the proof is identical for s2 and θ2). This new branch is then:

(pk+1,pk+1+s1eiθ1(pk+1pk))=(pk+1,pk+1+s1eiθ1(bk+1))

If we take any path (fj)j=1 such that fj=dj for jk+1 and fk+2=1. Then we have:

(pk+1,pk+1+s1eiθ1(bk+1))=(pk+1,pk+1+bk+2)=(pk+1,pk+2)

Therefore if a branch can be reached with a path then both of its children can also be reached by a path.

And so by structural induction, we have that all branches in the tree can be reached by at least one path.

A branch can be reached by a path as defined above if and only if it is part of the tree.

Previous two lemmas

So what does all this mean? Essentially, we pick some path up the tree and specify it by the series of left and right turns you make each time a branch splits into two more branches. (bk)k=0 is then the branch you visit at each step in the path with one end translated down to the origin, and (pk)k=0 is the sequence of junction points you reach as you follow the path. Finally, you can reconstruct the path by connecting consecutive elements of the (pk)k=0 sequence. Most importantly, this view of picking a path up the tree is equivalent to the recursive definition.

Now that we have this all set up, we can put some bounds on our trees.

A tree is bounded if all branches (x,y) in the tree are within some radius R of the origin. That is, |x|,|y|R for all branches in the tree for some RR+

A tree with s1>1 or s2>1 is unbounded.

Show proof

We can prove this by contradiction. Suppose without loss of generality that s1>1 and that the tree is bounded with radius R. Take the path dk=1 for all k, and corresponding sequence (pk)k=0. Let k>logs12R then

bk=ij=1ks1eiθ1=is1keikθ1|bk|=s1k>2R

That is, we can find a individual branch in the tree whose length is greater than 2R. Now, since we assumed the tree is bounded and (pk1,pk) is a branch in the tree, |pk1|,|pk|R

pk=bk+pk1|pk|=|bk+pk1||bk||pk1|>2RR=Rpk>R

Which is a contradiction. Therefore, the tree cannot be bounded with s1>1 or s2>1.

A tree with s1<1 and s2<1 is bounded

Show proof

Let s^=max(s1,s2). Note |b0|=|i|=1, and for k1

|bk|=|i|j=1k|sdjeiθdj|=j=1ksdj=s1ns2m for some n+m=ks^k

Therefore |bk|s^k.

|pk|=|j=0kbj|j=0k|bj|j=0ks^j11s^

Therefore, for any branch (x,y) we have

x,y11s^

And the tree is bounded.

The remaining case is when either scale factor is exactly one. Within that case are a few interesting subcases. For one, if we have s1=1 and θ1=0 we get a tree with straight vertical line and the tree is unbounded. With s1=1, θ10, and s2<1, the branches that don’t shrink stay contained in circular loops and so you end up with lots of loops branching off of each other but the tree stays bounded. If s1,s2=1 and θ1θ2, then the tree is again unbounded. If s1,s2=1 and θ1=θ2 we end up with a single circular loop which is bounded.

A tree with a scale factor s=1 and rotation angle θ0 forms loops of radius 12sec(πθ2)

Show proof

This can be shown geometrically.

Geometric diagram showing a proof of the formula for the loop radius

You can also play with this interactive version on GeoGebra.

Here we have two adjacent branches with the second scaled by 1 and rotated by θ. The dashed circle indicates that the two branches have equal length. We can draw the solid circle with the three endpoints of the two segments on the border because any three points describe a circle.

In order to derive the formula we need to first show that the two angles labeled ϕ are in fact equal. That can be done by connecting all three endpoints of the segments to the center of the solid circle and showing that the two triangles formed are congruent isosceles triangles which implies that the two angles are in fact equal.

Second, we use the fact that the perpendicular bisector of a chord passes through the center of the circle to draw the right triangle shown in the diagram which connects the shared endpoint of the two segments, the center of the solid circle, and the midpoint of the second segment.

We can then use some basic trigonometry to derive the relationship:

0.5r=cos(ϕ)

We can then use 2ϕ+θ=πϕ=πθ2 and rearrange the equation to get:

r=|12sec(πθ2)|

Plot of the loop radius formula

You can show that all the branches that come from these parameters lie on the same circle by rotating the entire diagram by θ and repeating the same argument.

Note that as θ approaches zero the formula gives us a radius that approaches infinity. A circle with a radius of infinity can be thought of as equivalent to a straight line which is what we get with θ=0.

A tree with s1=1,s2<1 and θ10 is bounded.

Show proof

Take any branch (x,y) and its corresponding path (dk)k=1n.

The path can be broken into a stretches of ones and twos. That is, a pattern like 1,...,2,...,1,...,2,... potentially with zero ones in the first stretch.

Every stretch of repeated ones is bounded since all such branches lie on a circle of radius r=|12sec(πθ12)|. Therefore, any sum

|k=1ms1keikθ1|2r=|sec(πθ12)|

Similarly, every stretch of repeated twos is bounded due to the lemma above showing trees with scale factor < 1 are bounded.

|k=1ms2keikθ2|11s2

Let xk be sequence of run lengths for each stretch of ones and yk be the sequence of run lengths for each stretch of twos. Then we can break apart the repeated pattern of a stretch of ones followed by a stretch of twos to put a bound on the whole series. Note that each subsequent sequence of twos adds some number of s2 factors, but we can put an upper bound on this by reducing to just one s2 per sequence of twos since s2<1. That lets us bound the sequence as follows:

|pk|=|ij=0kbj|=|j=0kbj||j=0ks2j(l=1xjeilθ1+eixjθ1l=1yjs2leilθ2)|j=0ks2j(|l=1xjeilθ1|+|l=1yjs2leilθ2|)j=0ks2j(|sec(πθ12)|+11s2)=(j=0ks2j)(|sec(πθ12)|+11s2)11s2(|sec(πθ12)|+11s2)

Which is constant with respect to k, therefore every branch in this tree is bounded.

A tree s1,s2=1 and θ1θ2 is unbounded.

Show proof

The goal here is to construct a finite-length pattern which ends with a branch facing straight up (i.e. with an angle of 0) which doesn’t double back to the root of the tree. Repeating such a pattern of branches leads to a path which continues out in a way that avoids falling into a closed circle. To do this we’ll use a pattern from group theory called the commutator, i.e. aba1b1.

In particular we’re going to make use of the fact that the total rotation over a sequence of branches is independent of their order (i.e. commutative), while the final position is not. We’ll show that we can construct θ (or an approximation) as an integer multiple of θ which will be the inverse in this case. Then we’ll show that the commutator pattern is a way to sequence these turns which satisfies the conditions above.

First, let’s investigate which angles we can construct with a given branching angle. Let θ be a branching angle, it’s obvious that one application of this angle from the root gives us a rotation of θ. A second application gives us an angle of 2θ. Note that this isn’t the angle from the origin to the end of the branch, it’s the orientation of the branch itself. So obviously we can construct the angle kθ for any k, but eventually that wraps around past 2π so what unique angles does that actually give us? Well, we’ve constructed the Circle Group so we can take some results from there. At this point there is a divide between angles which are a rational multiple of 2π and angles which are an irrational multiple of 2π. We’ll call an angle which is a rational multiple of 2π a “rational angle” and an angle which is an irrational multiple of 2π an “irrational angle.”

Multiples of rational angles will go to finitely many unique angles. In fact, if the angle is pq2π with pq in reduced form, there will be q unique angles at kq2π for 0k<q. Notably, this set of unique angles is a subgroup of the circle group which means that for every angle that you can construct, you can also construct its negation (this is part of the definition of a group).

Multiples of irrational angles will go to infinitely many unique angles, and in fact any angle can be approximated arbitrarily well by an integer multiple of an irrational angle.

So, for a rational angle we can take θ as x and θ as x1. We know that θ can be constructed by repeated rotations by θ by the argument above. For an irrational angle, we can take θ and an arbitrarily close approximation of θ which we can also construct by repeated applications of θ.

We then can take the sequence:

eiθ1+eiθ1eiθ2+eiθ1eiθ2j=1keijθ1+eiθ1eiθ2eikθ1j=1leijθ2

Where k,l are selected so that eikθ1=eiθ1 and eilθ2=eiθ2 or at least approximately equal in the case of irrational angles. We can then reduce j=1keijθ1 to 1 as follows:

j=1keijθ1=eiθ1(1eikθ1)1eiθ1=eiθ1(1eiθ1)1eiθ11eiθ11eiθ1=(2eiθ1eiθ1)2eiθ1eiθ1=1

Which is undefined when eiθ1=1θ1=0, but in that case the tree is unbounded anyway because we have a straight vertical line. Similar holds for θ2. Now the sequence above becomes:

eiθ1+eiθ1eiθ2eiθ1eiθ2eiθ1eiθ2eiθ1=eiθ1eiθ2

This is non-zero whenever θ1θ2. Note that the last term in this series, before all the simplification, is eiθ1eiθ2eiθ1eiθ2=1. Therefore, by repeating this sequence of branches we can travel arbitrarily far from the origin and the tree is unbounded.

This proof does gloss over the irrational angle case somewhat. To be more thorough you would need to show that a close approximation of eiθ leads to a close approximation of the final term. However, the core argument doesn’t change so this case is mostly omitted for the sake of brevity in an already long proof.

A tree is bounded if and only if one of the following is true (for some ordering of s1,s2 and θ1,θ2):

  1. s1,s2<1
  2. s1=1,s2<1, and θ10
  3. s1,s2=1 and θ1=θ20

Previous lemmas