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.

Savannah fractal tree
Savannah fractal tree

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.

Definition 1:

A tree is a structure on the complex plane defined by four parameters: two rotation angles θ1,θ2[π,π]\theta_1, \theta_2 \in [-\pi, \pi] and two scaling factors s1,s2R+s_1, s_2 \in \mathbb{R}^+. 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)(x,y). The branches that make up a given tree are defined as follows:

  1. (0,i)(0, i) is a branch in the tree
  2. If (x,y)(x,y) is a branch in the tree, then (y,y+s1eiθ1(yx))(y, y + s_1 e^{i\theta_1} (y-x)) and (y,y+s2eiθ2(yx))(y, y + s_2 e^{i\theta_2} (y-x)) 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)(0,1) as the initial branch which might feel a bit more natural, but I like (0,i)(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.

Definition 2:

A path is a sequence (dk)k=1(d_k)_{k=1}^{\infty} over the set {1,2}\{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(d_k)_{k=1}^{\infty}, let

bk={i,k=0ij=1ksdjeiθdj,k1 b_k = \begin{cases} i, & k = 0 \\ i \prod_{j=1}^{k} s_{d_j}e^{i\theta_{d_j}}, & k \geq 1 \\ \end{cases}

be the sequence of offsets between branching points on the path, and

pk=j=0kbj p_k = \sum_{j=0}^k b_j

be the sequence of branching points on the path.

Lemma 1:

For any path and its corresponding sequence (pk)k=0(p_k)_{k=0}^\infty, (pk,pk+1)(p_k, p_{k+1}) is a branch in the tree for all kZ0k \in \mathbb{Z}_{\geq 0}

Show proof

Proceed by induction.

We have that p0=ip_0 = i and p1=i+isd1eiθd1p_1 = i + is_{d_1}e^{i\theta_{d_1}}. Since (0,i)(0, i) is a branch in the tree, then (p0,p1)=(i,i+sd1eiθd1(i0))(p_0, p_1) = (i, i + s_{d_1}e^{i\theta_{d_1}}(i-0)) is also a branch in the tree by the second rule in the definition of a tree.

Now, assume that (pk1,pk)(p_{k-1}, p_{k}) is a branch in the tree. We have that

pk+1pk=bk+1=sdk+1eiθdk+1bk=sdk+1eiθdk+1(pkpk1) \begin{aligned} &p_{k+1} - p_{k}\\ = &b_{k+1} \\ = &s_{d_{k+1}}e^{i\theta_{d_{k+1}}} b_{k} \\ = &s_{d_{k+1}}e^{i\theta_{d_{k+1}}} (p_k - p_{k-1}) \end{aligned}


(pk,pk+1)=(pk,pk+pk+1pk)=(pk,pk+sdk+1eiθdk+1(pkpk1)) \begin{aligned} &(p_k, p_{k+1}) \\ = &(p_k, p_k + p_{k+1} - p_k) \\ = &(p_k, p_k + s_{d_{k+1}}e^{i\theta_{d_{k+1}}} (p_k - p_{k-1})) \end{aligned}

And (pk,pk+1)(p_k, p_{k+1}) is a branch in the tree.

Therefore, by induction (pk,pk+1)(p_k, p_{k+1}) is a branch in the tree for all k0k\geq 0. \blacksquare

Lemma 2:

For every branch (x,y)(x,y) in the tree except (0,i)(0, i), there is at least one path and corresponding sequence (pk)k=0(p_k)_{k=0}^\infty such that x=pkx = p_k and y=pk+1y = p_{k+1} for some kZ0k \in \mathbb{Z}_{\geq 0}.

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)(i, i + i s_1 e^{i\theta_1}) and (i,i+is2eiθ2)(i, i + i s_2 e^{i\theta_2}). Each of these can be reached with any path that starts with d1=1d_1=1 or d1=2d_1=2 respectively. In that case you have for k=0k=0, pk=ip_k = i and pk+1=i+isd1eiθd1p_{k+1} = i + is_{d_1}e^{i\theta_{d_1}}.

Now we assume that (x,y)(x,y) is a branch in the tree which can be reached by the path (dj)j=1(d_j)_{j=1}^\infty such that x=pkx=p_{k} and y=pk+1y=p_{k+1} for some kk. Another branch can be constructed using the rule involving s1s_1 and θ1\theta_1 (the proof is identical for s2s_2 and θ2\theta_2). This new branch is then:

(pk+1,pk+1+s1eiθ1(pk+1pk))=(pk+1,pk+1+s1eiθ1(bk+1)) \begin{aligned} &(p_{k+1}, p_{k+1} + s_1e^{i\theta_1}(p_{k+1} - p_{k}))\\ =&(p_{k+1}, p_{k+1} + s_1e^{i\theta_1}(b_{k+1}))\\ \end{aligned}

If we take any path (fj)j=1(f_j)_{j=1}^\infty such that fj=djf_j=d_j for jk+1j \leq k+1 and fk+2=1f_{k+2} = 1. Then we have:

(pk+1,pk+1+s1eiθ1(bk+1))=(pk+1,pk+1+bk+2)=(pk+1,pk+2) \begin{aligned} &(p_{k+1}, p_{k+1} + s_1e^{i\theta_1}(b_{k+1}))\\ =&(p_{k+1}, p_{k+1} + b_{k+2}) \\ =&(p_{k+1}, p_{k+2}) \end{aligned}

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

Theorem 1:

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

Proof: 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(b_k)_{k=0}^{\infty} is then the branch you visit at each step in the path with one end translated down to the origin, and (pk)k=0(p_k)_{k=0}^{\infty} 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(p_k)_{k=0}^{\infty} 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.

Definition 3:

A tree is bounded if all branches (x,y)(x,y) in the tree are within some radius RR of the origin. That is, x,yR\vert x \vert, \vert y \vert \leq R for all branches in the tree for some RR+R \in \mathbb{R}^+

Lemma 3:

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

Show proof

We can prove this by contradiction. Suppose without loss of generality that s1>1s_1 > 1 and that the tree is bounded with radius RR. Take the path dk=1d_k = 1 for all kk, and corresponding sequence (pk)k=0(p_k)_{k=0}^\infty. Let k>logs12Rk > \log_{s_1} 2R then

bk=ij=1ks1eiθ1=is1keikθ1bk=s1k>2R \begin{aligned} b_k &= i\prod_{j=1}^k s_1 e^{i\theta_1} = i s_1^k e^{ik\theta_1} \\ \vert b_k \vert &= s_1^k > 2R \end{aligned}

That is, we can find a individual branch in the tree whose length is greater than 2R2R. Now, since we assumed the tree is bounded and (pk1,pk)(p_{k-1}, p_k) is a branch in the tree, pk1,pkR\vert p_{k-1} \vert, \vert p_k \vert \leq R

pk=bk+pk1pk=bk+pk1bkpk1>2RR=Rpk>R \begin{aligned} p_{k} &= b_{k} + p_{k-1} \\ \vert p_k \vert &= \vert b_k + p_{k-1} \vert \\ &\geq \vert b_k \vert - \vert p_{k-1} \vert \\ &> 2R - R \\ &=R \\ p_k &> R \end{aligned}

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

Lemma 4:

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

Show proof

Let s^=max(s1,s2)\hat{s} = max(s_1, s_2). Note b0=i=1\vert b_0 \vert = \vert i \vert = 1, and for k1k \geq 1

bk=ij=1ksdjeiθdj=j=1ksdj=s1ns2m for some n+m=ks^k \begin{aligned} \vert b_k \vert =& \vert i \vert \prod_{j=1}^k \vert s_{d_j} e^{i\theta_{d_j}} \vert\\ &=\prod_{j=1}^k s_{d_j} \\ &=s_1^n s_2^m \text{ for some } n + m = k \\ &\leq \hat{s}^k \\ \end{aligned}

Therefore bks^k\vert b_k \vert \leq \hat{s}^k.

pk=j=0kbjj=0kbjj=0ks^j11s^ \begin{aligned} \vert p_k \vert &= \left\vert \sum_{j=0}^k b_j \right\vert \\ &\leq \sum_{j=0}^k \vert b_j \vert \\ &\leq \sum_{j=0}^k \hat{s}^j \\ &\leq \frac{1}{1-\hat{s}} \end{aligned}

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

x,y11s^ x, y \leq \frac{1}{1-\hat{s}}

And the tree is bounded. \blacksquare

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=1s_1 = 1 and θ1=0\theta_1 = 0 we get a tree with straight vertical line and the tree is unbounded. With s1=1s_1 = 1, θ10\theta_1 \neq 0, and s2<1s_2 < 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=1s_1, s_2 = 1 and θ1θ2\theta_1 \neq \theta_2, then the tree is again unbounded. If s1,s2=1s_1, s_2 = 1 and θ1=θ2\theta_1 = \theta_2 we end up with a single circular loop which is bounded.

Lemma 5:

A tree with a scale factor s=1s=1 and rotation angle θ0\theta \neq 0 forms loops of radius 12sec(πθ2)\frac{1}{2} \sec \left( \frac{\pi - \theta}{2} \right)

Show proof

This can be shown geometrically.

Geometric diagram showing a proof of the formula for the loop radius
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 θ\theta. 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{:target="_blank"}.

In order to derive the formula we need to first show that the two angles labeled ϕ\phi 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{:target="_blank"} 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(ϕ) \frac{0.5}{r} = \cos(\phi)

We can then use 2ϕ+θ=πϕ=πθ22 \phi + \theta = \pi \Rightarrow \phi = \frac{\pi - \theta}{2} and rearrange the equation to get:

r=12sec(πθ2) r = \left\vert \frac{1}{2} \sec \left( \frac{\pi - \theta}{2} \right) \right\vert

Plot of the loop radius formula
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 θ\theta and repeating the same argument. \blacksquare

Note that as θ\theta 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\theta=0.

Lemma 6:

A tree with s1=1,s2<1s_1 = 1, s_2 < 1 and θ10\theta_1 \neq 0 is bounded.

Show proof

Take any branch (x,y)(x,y) and its corresponding path (dk)k=1n(d_k)_{k=1}^{n}.

The path can be broken into a stretches of ones and twos. That is, a pattern like 1,...,2,...,1,...,2,...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)r = \left\vert \frac{1}{2} \sec \left( \frac{\pi - \theta_1}{2} \right) \right\vert. Therefore, any sum

k=1ms1keikθ12r=sec(πθ12) \left\vert \sum_{k=1}^{m} s_1^k e^{i k \theta_1} \right\vert \leq 2r = \left\vert \sec \left( \frac{\pi - \theta_1}{2} \right) \right\vert

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

k=1ms2keikθ211s2 \left\vert \sum_{k=1}^{m} s_2^k e^{i k \theta_2} \right\vert \leq \frac{1}{1-s_2}

Let xkx_k be sequence of run lengths for each stretch of ones and yky_k 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 s2s_2 factors, but we can put an upper bound on this by reducing to just one s2s_2 per sequence of twos since s2<1s_2 < 1. That lets us bound the sequence as follows:

pk=ij=0kbj=j=0kbjj=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) \begin{aligned} \vert p_k \vert &= \left\vert i \sum_{j=0}^k b_j \right\vert = \left\vert \sum_{j=0}^k b_j \right\vert \\ &\leq \left\vert \sum_{j=0}^k s_2^{j} \left( \sum_{l=1}^{x_j} e^{i l \theta_1} + e^{i x_j \theta_1} \sum_{l=1}^{y_j} s_2^l e^{i l \theta_2} \right) \right| \\ &\leq \sum_{j=0}^k s_2^j \left( \left\vert \sum_{l=1}^{x_j} e^{i l \theta_1} \right\vert + \left\vert \sum_{l=1}^{y_j} s_2^l e^{i l \theta_2} \right\vert \right) \\ &\leq \sum_{j=0}^k s_2^j \left( \left\vert \sec \left( \frac{\pi - \theta_1}{2} \right) \right\vert + \frac{1}{1-s_2} \right) \\ &= \left( \sum_{j=0}^k s_2^j \right) \left( \left\vert \sec \left( \frac{\pi - \theta_1}{2} \right) \right\vert + \frac{1}{1-s_2} \right) \\ &\leq \frac{1}{1-s_2} \left( \left\vert \sec \left( \frac{\pi - \theta_1}{2} \right) \right\vert + \frac{1}{1-s_2} \right) \end{aligned}

Which is constant with respect to kk, therefore every branch in this tree is bounded. \blacksquare

Lemma 7:

A tree s1,s2=1s_1, s_2 = 1 and θ1θ2\theta_1 \neq \theta_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. aba1b1a b a^{-1} b^{-1} .

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 θ-\theta (or an approximation) as an integer multiple of θ\theta 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 θ\theta be a branching angle, it's obvious that one application of this angle from the root gives us a rotation of θ\theta. A second application gives us an angle of 2θ2 \theta. 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θk \theta for any kk, but eventually that wraps around past 2π2 \pi 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π2\pi and angles which are an irrational multiple of 2π2 \pi. We'll call an angle which is a rational multiple of 2π2\pi a "rational angle" and an angle which is an irrational multiple of 2π2\pi an "irrational angle."

Multiples of rational angles will go to finitely many unique angles. In fact, if the angle is pq2π\frac{p}{q} 2\pi with pq\frac{p}{q} in reduced form, there will be qq unique angles at kq2π\frac{k}{q} 2\pi for 0k<q0 \leq k < 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 θ\theta as xx and θ-\theta as x1x^{-1}. We know that θ-\theta can be constructed by repeated rotations by θ\theta by the argument above. For an irrational angle, we can take θ\theta and an arbitrarily close approximation of θ-\theta which we can also construct by repeated applications of θ\theta.

We then can take the sequence:

eiθ1+eiθ1eiθ2+eiθ1eiθ2j=1keijθ1+eiθ1eiθ2eikθ1j=1leijθ2 e^{i\theta_1} + e^{i\theta_1}e^{i\theta_2} + e^{i\theta_1}e^{i\theta_2} \sum_{j=1}^k e^{ij\theta_1} + e^{i\theta_1}e^{i\theta_2}e^{ik\theta_1} \sum_{j=1}^l e^{ij\theta_2}

Where k,lk, l are selected so that eikθ1=eiθ1e^{ik\theta_1} = e^{-i\theta_1} and eilθ2=eiθ2e^{il\theta_2} = e^{-i\theta_2} or at least approximately equal in the case of irrational angles. We can then reduce j=1keijθ1\sum_{j=1}^k e^{ij\theta_1} to 1-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 \begin{aligned} &\sum_{j=1}^k e^{ij\theta_1} \\ =&\frac{e^{i\theta_1}(1 - e^{ik\theta_1})}{1 - e^{i\theta_1}} \\ =&\frac{e^{i\theta_1}(1 - e^{-i\theta_1})}{1 - e^{i\theta_1}} \frac{1-e^{-i\theta_1}}{1-e^{-i\theta_1}} \\ =&\frac{-(2 - e^{i\theta_1} - e^{-i\theta_1} )}{2 - e^{i\theta_1} - e^{-i\theta_1}} = -1 \end{aligned}

Which is undefined when eiθ1=1θ1=0e^{i\theta_1} = 1 \Rightarrow \theta_1 = 0, but in that case the tree is unbounded anyway because we have a straight vertical line. Similar holds for θ2\theta_2. Now the sequence above becomes:

eiθ1+eiθ1eiθ2eiθ1eiθ2eiθ1eiθ2eiθ1=eiθ1eiθ2 \begin{aligned} &e^{i\theta_1} + e^{i\theta_1}e^{i\theta_2} - e^{i\theta_1}e^{i\theta_2} - e^{i\theta_1}e^{i\theta_2}e^{-i\theta_1} \\ =&e^{i\theta_1} - e^{i\theta_2} \end{aligned}

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

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θe^{-i\theta} 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.

Theorem 2:

A tree is bounded if and only if one of the following is true (for some ordering of s1,s2 and θ1,θ2s_1, s_2 \text{ and } \theta_1, \theta_2):

  1. s1,s2<1s_1, s_2 < 1
  2. s1=1,s2<1, and θ10s_1 = 1, s_2 < 1, \text{ and } \theta_1 \neq 0
  3. s1,s2=1 and θ1=θ20s_1, s_2 = 1 \text{ and } \theta_1 = \theta_2 \neq 0

Proof: Previous lemmas