# Fractal Trees: Boundedness

2020-09-06When 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.

#### Definition 1:

A *tree* is a structure on the complex plane defined by four parameters: two rotation angles $\theta_1, \theta_2 \in [-\pi, \pi]$ and two scaling factors $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)$. The branches that make up a given tree are defined as follows:

- $(0, i)$ is a branch in the tree
- If $(x,y)$ is a branch in the tree, then $(y, y + s_1 e^{i\theta_1} (y-x))$ and $(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)$ 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.

#### Definition 2:

A *path* is a sequence $(d_k)_{k=1}^{\infty}$ 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 $(d_k)_{k=1}^{\infty}$, let

$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

$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 $(p_k)_{k=0}^\infty$, $(p_k, p_{k+1})$ is a branch in the tree for all $k \in \mathbb{Z}_{\geq 0}$

## Show proof

Proceed by induction.

We have that $p_0 = i$ and $p_1 = i + is_{d_1}e^{i\theta_{d_1}}$. Since $(0, i)$ is a branch in the tree, then $(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 $(p_{k-1}, p_{k})$ is a branch in the tree. We have that

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

Therefore

$\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 $(p_k, p_{k+1})$ is a branch in the tree.

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

#### Lemma 2:

For every branch $(x,y)$ in the tree except $(0, i)$, there is at least one path and corresponding sequence $(p_k)_{k=0}^\infty$ such that $x = p_k$ and $y = p_{k+1}$ for some $k \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 + i s_1 e^{i\theta_1})$ and $(i, i + i s_2 e^{i\theta_2})$. Each of these can be reached with any path that starts with $d_1=1$ or $d_1=2$ respectively. In that case you have for $k=0$, $p_k = i$ and $p_{k+1} = i + is_{d_1}e^{i\theta_{d_1}}$.

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

$\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 $(f_j)_{j=1}^\infty$ such that $f_j=d_j$ for $j \leq k+1$ and $f_{k+2} = 1$. Then we have:

$\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. $(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 $(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 $(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)$ in the tree are within some radius $R$ of the origin. That is, $\vert x \vert, \vert y \vert \leq R$ for all branches in the tree for some $R \in \mathbb{R}^+$

#### Lemma 3:

A tree with $s_1 > 1$ or $s_2 > 1$ is unbounded.

## Show proof

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

$\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 $2R$. Now, since we assumed the tree is bounded and $(p_{k-1}, p_k)$ is a branch in the tree, $\vert p_{k-1} \vert, \vert p_k \vert \leq 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 $s_1 > 1$ or $s_2 > 1$. $\blacksquare$

#### Lemma 4:

A tree with $s_1 < 1$ and $s_2 < 1$ is bounded

## Show proof

Let $\hat{s} = max(s_1, s_2)$. Note $\vert b_0 \vert = \vert i \vert = 1$, and for $k \geq 1$

$\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 $\vert b_k \vert \leq \hat{s}^k$.

$\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)$ we have

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

#### Lemma 5:

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

## Show proof

This can be shown geometrically.

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:

$\frac{0.5}{r} = \cos(\phi)$

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

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

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 $\theta=0$.

#### Lemma 6:

A tree with $s_1 = 1, s_2 < 1$ and $\theta_1 \neq 0$ is bounded.

## Show proof

Take any branch $(x,y)$ and its corresponding path $(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,...$ 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 = \left\vert \frac{1}{2} \sec \left( \frac{\pi - \theta_1}{2} \right) \right\vert$. Therefore, any sum

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

$\left\vert \sum_{k=1}^{m} s_2^k e^{i k \theta_2} \right\vert \leq \frac{1}{1-s_2}$

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

$\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 $k$, therefore every branch in this tree is bounded. $\blacksquare$

#### Lemma 7:

A tree $s_1, s_2 = 1$ and $\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. $a 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 \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 \theta$ for any $k$, but eventually that wraps around past $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\pi$ and angles which are an irrational multiple of $2 \pi$. We'll call an angle which is a rational multiple of $2\pi$ a "rational angle" and an angle which is an irrational multiple of $2\pi$ an "irrational angle."

Multiples of rational angles will go to finitely many unique angles. In fact, if the angle is $\frac{p}{q} 2\pi$ with $\frac{p}{q}$ in reduced form, there will be $q$ unique angles at $\frac{k}{q} 2\pi$ for $0 \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 $x$ and $-\theta$ as $x^{-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:

$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, l$ are selected so that $e^{ik\theta_1} = e^{-i\theta_1}$ and $e^{il\theta_2} = e^{-i\theta_2}$ or at least approximately equal in the case of irrational angles. We can then reduce $\sum_{j=1}^k e^{ij\theta_1}$ to $-1$ as follows:

$\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 $e^{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 $\theta_2$. Now the sequence above becomes:

$\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 $\theta_1 \neq \theta_2$. Note that the last term in this series, before all the simplification, is $e^{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 $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 $s_1, s_2 \text{ and } \theta_1, \theta_2$):

- $s_1, s_2 < 1$
- $s_1 = 1, s_2 < 1, \text{ and } \theta_1 \neq 0$
- $s_1, s_2 = 1 \text{ and } \theta_1 = \theta_2 \neq 0$

Proof: Previous lemmas