Larry Riddle, Agnes Scott College

Let \(\alpha\) be the complex number \(\alpha = e^{\theta i}=\cos{\theta} + i \sin{\theta}\). We can represent the trunk of the tree by the complex number \(i\) (which we can also think of geometrically as a vector). Recall that multiplying a vector by r will scale the vector by r, that multiplying the vector by \(\alpha\) corresponds to a counterclockwise rotation by θ, and multiplying by \(\alpha^{-1}\) corresponds to a clockwise rotation by θ. We also have \(\alpha^n = e^{n\theta i}=\cos{(n\theta)} + i \sin{(n\theta)}\) and \(\alpha^{-n} = e^{-n\theta i}=\cos{(n\theta)} - i \sin{(n\theta)}\) for all integers n.

Branch

To get to the top of the tree, we want to go vertically as much as possible for each new branch in the construction of the tree. Thus we want to alternate left and right branches. This gives the path (LR)^{∞}. In terms of the complex numbers, this means we want to alternate multiplying the vectors representing the branches by \(\alpha\) and \(\alpha^{-1}\), while also multiplying by r. The branch tip for this path is therefore located at the point \((x,y)\) corresponding to the complex number
\[
i + ir\alpha + ir^2 + ir^3\alpha + ir^4 + ir^5\alpha + ir^6 + ir^7\alpha + \dots \hspace{2.5in}
\]
\[
\begin{align}
\\
&= i \left( 1 + r^2 + r^4 + \dots \right) + i r\alpha \left( 1 + r^2 + r^4 + \dots \right) \\ \\
&= i \frac{1}{1-r^2} + i r \alpha\frac{1}{1-r^2} \\ \\
&= i \frac{1+r \alpha}{1-r^2} = iz.
\end{align}
\]

For this path we thus have \(x = \text{Re}(iz) = -\text{Im}(z) = \dfrac{-r \,\sin{(\theta)}}{1-r^2}\) and \(y = \text{Im}(iz) = \text{Re}(z) = \dfrac{1+r\, \cos{(\theta)}}{1-r^2}\).

Branch

Let k be the smallest integer such that kθ ≥ 360°. Consider the branch path that starts R^{k}. This path starts at the top of the trunk and goes clockwise until the last branch passes the upward vertical direction. If θ is of the form 360°/n, where n is an integer, then the last branch of R^{k} will actually be vertical. We now form the rest of the branches by alternating left and right. This yields the branch tip R^{k}(LR)^{∞}. Here is an example of the first 14 branches when θ = 70° and k = 6.

R^{6}(LR)^{4}, θ=70°

The branch tip for R^{k}(LR)^{∞} corresponds to the complex number

The y-coordinate of this branch tip is \(\text{Im}(iz) = \text{Re}(z)\), or

\[ \sum_{n=0}^{k}{r^n \cos(n \theta)} + \frac{r^{k+1} \cos((k-1)\theta) + r^{k+2} \cos(k \theta)}{1-r^2}. \]
For a given θ, we are interested in knowing when the branch tip for R^{k}(LR)^{∞} has a greater y-coordinate than the branch tip for (LR)^{∞}. For example, if θ = 150° and r = 0.8, then the following image shows the corresponding symmetric binary tree and the branch tips for these two specific paths (here k = 3).

Branch

Animation

Tree

Animation

θ = 150°, r = 0.8

The black path for R^{3}(LR)^{∞} has a branch tip with y-coordinate 1.19607 while the green path for (LR)^{∞} leads to a branch tip with y-coordinate only at 0.85328 (the x-coordinates are 0.28262 and −1.11111, respectively). You can get a sense of why this might happen in this example since the green path has mostly a horizontal direction while the black path is more vertical. The value of r is large enough that the black path will grow sufficiently upward to eventually extend above the end of the green path. You can see this happen by viewing the branch animation. If you watch the tree animation, you will see how this large value of r produces extensive overlap of the branches as the tree grows. Also notice in the figure above that the other "peaks" along the boundary are extensions of R^{3}(LR)^{∞} using initial branches of the form (RL)^{m}.

θ = 150°, r = 0.8

red: R^{3}(LR)^{∞}

blue: (RL)R^{3}(LR)^{∞}

brown: (RL)^{2}R^{3}(LR)^{∞}

Case

Let y_{k} be the y-coordinate of the R^{k}(LR)^{∞} branch tip and let y_{0} be the
y-coordinate of the (LR)^{∞} branch tip. For a fixed θ, these coordinates depend on the value of r.
Let \(f_\theta (r)=y_k - y_0\) be the difference between the y-coordinates of the two branch tips, so
\[
f_\theta (r) = \sum_{n=0}^{k}{r^n \cos(n \theta)} + \frac{r^{k+1} \cos((k-1)\theta) + r^{k+2} \cos(k \theta) -1-r\cos( \theta)}{1-r^2}
\]
If \(f_\theta (r)\) is negative then y_{k} is less than y_{0}, and if \(f_\theta (r)\) is positive then y_{k} is greater than y_{0}. We consider two different cases depending on the value of θ.
#### Case 1: \(\theta = \dfrac{360^{\circ}}{k}\) where k is an integer

Note that k ≥ 3 since θ < 180°, and that θ ≤ 1° for all k ≥ 360. The largest possible angle is 120° (for k = 3).
#### Case 2: \(\theta \neq \dfrac{360^{\circ}}{n}\) for any integer n

For this special case we have kθ = 360° and therefore the last branch of R^{k} is vertical, but of length r^{k}. From this point on, the branches of R^{k}(LR)^{∞} alternate in the same pattern that the (LR)^{∞} branches did from the beginning, but can never catch up, and thus y_{k} will be less than y_{0}. The following image shows what happens for θ = 120° with r = 0.9. The red path will have y_{0} = 2.89474 and the black path will have y_{3} = 2.25526.

θ = 120°, r = 0.9

Why does this happen for these special values of θ? Because kθ = 360°, \(\cos(k \theta) = \cos(360^{\circ}) = 1\) and \(\cos((k-1)\theta) = \cos(360^{\circ}-\theta) = \cos(\theta)\). Therefore

\[ f_\theta (r) = \sum_{n=0}^{k}{r^n \cos(n \theta)} + \frac{r^{k+1} \cos(\theta) + r^{k+2} -1-r\cos( \theta)}{1-r^2}. \]It can then be shown [Details] that the graph of \(f_\theta (r)\) starts at (0,0) and initially begins decreasing in a concave down fashion as r increases. Moreover, with the help of L'Hospital's rule, we can determine that

\[ \begin{align} \lim_{r \rightarrow 1^{-}} f_\theta(r) &= \sum_{n=0}^{k}{\cos(n \theta)} + \lim_{r \rightarrow 1^{-}} \frac{(k+1)r^k \cos(\theta) + (k+2)r^{k+1} - \cos(\theta)}{-2r} \\ \\ &= 1 + \frac{(k+1)\cos(\theta)+k+2-\cos(\theta)}{-2} = -\frac{k}{2}(1+\cos(\theta)). \end{align} \]
Therefore \(\lim_{r \rightarrow 1^{-}} f_\theta(r) < 0\) suggesting that \(f_\theta(r)\) always remains negative as r goes from 0 to 1. This would imply that y_{0} is always greater than y_{k} for all r between 0 and 1 for these special values of θ. To see that this is actually the case, click on the Play button below to see the graphs of \(f_\theta(r)\) for k from 3 to 360, corresponding to the 358 special θ values of the form 360°/k between 1° and 120°. The graph is shown only for 0.9 ≤ r ≤ 1 since the scale on the vertical axis will prevent the very small values of \(f_\theta(r)\) from being shown for small values of r.

Now the smallest integer k such that kθ > 360° is \(k = \left\lceil \frac{360^\circ}{\theta} \right\rceil\), where \(\lceil x \rceil\) is the ceiling function, i.e. the smallest integer greater than or equal to x. As in case 1, the value of k can be any integer greater than or equal to 3.

As before [Details], the graph of \(f_\theta (r)\) starts at (0,0) and initially begins decreasing in a concave down fashion as r increases. This time, however, we have \(\lim_{r \rightarrow 1^{-}} f_\theta (r) = +\infty\). To see why, we just need to verify that the numerator of the fraction in the expression for \(f_\theta (r)\) is positive when r = 1 since the denominator is positive and goes to 0 as r approaches 1 from the left. So we need to verify that \[ N(\theta) = \cos((k-1)\theta) + \cos(k \theta) -1-\cos( \theta) > 0 \text{ when } \frac{360^\circ}{k} < \theta < \frac{360^\circ}{k-1} \] where \(k = \lceil \frac{360^\circ}{\theta} \rceil\). For example, for 120° < θ < 180° with k = 3, \[N(\theta) = \cos(2\theta) + \cos(3 \theta) -1-\cos( \theta) = -2 \sin^2(\theta) (2\cos(\theta)+1) > 0\] since \(2\cos(\theta)+1 < 0\) for 120° < θ < 180°. Note that N(120°) = N(180°) = 0, and that in general, N(360°/k) = N(360°/(k-1)) = 0.

Shown below is the graph of \(N(\theta)\) showing that \(N(\theta)\) is positive for all θ except for those of the form 360°/k (which pile up very quickly as k gets large and θ approaches 0.)

Because \(f_\theta (r)\) is negative for small r and \(\lim_{r \rightarrow 1^{-}} f_\theta (r) = +\infty\), there must be some some r_{T} between 0 and 1 where \(f_\theta (r_T) = 0.\) The two images below show the graphs of \(f_\theta (r)\) for θ = 65° and θ = 135°. The shapes of these graphs are typical for all values of θ in case 2.

θ = 65° r _{T} = 0.96984 |
θ = 135° r _{T} = \(\frac{1}{\sqrt{2}}\) = 0.70711 |

The equation \(f_\theta (r) = 0\) can be solved numerically to find the solution r_{T}. The next two figures show the graph of r_{T} for 0° < θ < 180°, and a close up of this graph just on the range 10° < θ < 90°.

Several observations. First, the equation \(f_\theta (r) = 0\) has no solution for r > 0 when θ is of the form 360°/k for some integer k. These are the special angles in case 1. Therefore r_{T} does not exist at these special values of θ. However, what the graphs show is that r_{T} approaches 1 as θ approaches one of these special angles.

Second, for θ < 90°, the value of the critical scaling factor r_{T} is greater than 0.94, so for all practical purposes the top of a "reasonable" symmetric binary tree for this range of θ will be determined by the (LR)^{∞} path and have value \((1+r\cos(\theta))/(1-r^2)\). Any choice of r > 0.94 will produce a tree that has a massive overlap of branches.

Third, the situation is a bit different for θ > 90°, and in particular for θ > 120°. Note that on this latter interval, the value of r_{T} converges to 1/2 as θ approaches 180°. We can, in fact, solve \(f_\theta (r) = 0\) explicitly for r for those values of θ in these two intervals [Calculation Details] to get
\[
\begin{align}
90^\circ < \theta < 120^\circ &\Rightarrow r_T = - \frac{{\cos ( {{{\theta}}} ) + \sqrt { - 3\cos^2 {{( {{{\theta}}} )}} + 1} }}{{4\cos^2 {{( {{{\theta}}} )}} - 1}} \\ \\
120^\circ < \theta < 180^\circ &\Rightarrow r_T = -\frac{1}{2\cos(\theta)}
\end{align}
\]

Finally, it is interesting to note that for θ ≥ 135°, the critical scaling factor r_{T} is the same value as r_{sc} for which the binary tree of angle θ is self-contacting. Here is a comparison of the two graphs of r_{T} versus r_{sc}. For r_{sc} < r < r_{T}, the binary tree will have overlapping branches, but the top of the branch tips will still correspond to the (LR)^{∞} path.

brown: r_{T}

blue: r_{sc}