Fractal Trees: Boundedness

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$

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$

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$

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$

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

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$

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.