Agnes Scott College
Larry Riddle, Agnes Scott College

Heighway Z2 Dragon Boundary Points

rectangle

For n ≥ 1, let bn represent a non-negative integer whose base-4 representation has n digits consisting of only 0 and 1. We define b0 = 0. These numbers come from the Moser-de Bruijin sequence consisting of the sums of distinct powers of 4. For each n there are 2n possibilities for bn, each of which is less than 4n/3.

Right Side along x = 7/3

To see what happens during the iterations of the Heighway Z2 dragon, start with the symmetric segment −1 ≤ x ≤ 1. The figure below shows the second iteration.

edge2
iteration:

The blue segment extends from y = 0 to y = −1. We can think of starting a new sequence of iterations on this blue segment within the iterations of the red dragon. (Strictly speaking, the IFS must be changed to reflect working on the smaller blue version; the scaling/rotations for each function will remain the same, but the translation vectors would change.) Click on each of the buttons from iteration 3 to iteration 6 button to see the change in the red and blue segments. Each of the blue segments is also a segment of the red dragon. The right most edge now has a segment, shown in green, that extends from y = −3/4 to y = −1. It is 1/4 the size of the original blue segment. Now start a new sequence of iterations on this green segment (again with a modified IFS with different translation vectors). The pattern between iterations 2 and 6 will repeat with the green segments. Click on the iterations from 7 to 10 to see the figure after 10 iterations with the red segments and 4 iterations with the green segments. Each of the green segments is also a segment of the red dragon. The right most green segment extends from y = −15/16 to y = −1. It is 1/4 the size of the original green segment from iteration 6.

The following figures show the right most part of the Z2 dragon after 6 iterations (left) and 10 iterations (right). The grid size is 1/8 x 1/8.

edgeproof6   edgeproof10

We focus on the farthest right most vertical line segments above the x-axis in these figures. The segment for iteration 6 extends from y = 0 to y = 1/4 and is of length 1/4. As shown above, after four additional iterations this segment has yielded two new right most vertical line segments of length 1/16 and whose lower endpoints are at y = 0 and y = 1/4. The endpoints of the iteration 6 segment become the lower endpoints of the two segments in iteration 10.

Each sequence of four iterations will double the number of these right most line segments and reduce their size by a factor of 1/4. We claim that at iteration 4n+6, the lower point of each such segment is at a point whose y-coordinate is of the form \(\dfrac{b_n}{4^n}\) for n ≥ 0. In the left figure we have n = 0 and b0 = 0. This gives the coordinate 0/1 = 0. In the right figure we have n = 1 and the only choices for b1 are (0)4 and (1)4 which give the endpoints with x-coordinates 0 and 1/4. So the claim holds for n = 0 and n = 1.

Suppose the claim is true for iteration 4n+6. A right most vertical line segment with lower endpoint y =\(\dfrac{b_n}{4^n}\) at iteration 4n+6 will have length \(\dfrac{1}{4^{n+1}}\). After four additional iterations, this segment will be replaced by two new segments with lower endpoints with y-coordinates

\[ y =\frac{b_n}{4^n} = \frac{4b_n}{4^{n+1}} \: \text{ and } \: y =\frac{b_n}{4^n} + \frac{1}{4^{n+1}} = \frac{4b_n+1}{4^{n+1}}\]

The result of multiplying bn by 4 will just shift all the digits in the base-4 representation of bn to the left and add a 0 at the end. Similarly, 4bn+1 will shift all the digits in the base-4 representation of bn to the left and add a 1 at the end. Thus in both cases the numerator of the y-coordinates of the new endpoints will contain only the digits 0 or 1 and there will be at most n+1 digits. Since this holds for all the segments from iteration 4n+6, the claim is also true for all the segments in iteration 4(n+1)+6.

Once a right most vertical line segment appears in an iteration with lower endpoint having y-coordinate \(\dfrac{b_n}{4^n}\), all cycles of 4 iterations will continue to have a right most vertical line segment with a lower endpoint that has that same y-coordinate. Thus those endpoints will converge to the point \(\left( \dfrac{7}{3}, \dfrac{b_n}{4^n}\right)\) on the boundary of the Z2 dragon.

At iteration 4n+6, the endpoint with the largest y-coordinate would be when bn = (11...11)4 with n digits in the base-4 representation. This would produce the fraction

\[\frac{1+4+4^2+\ldots+4^{n-1}}{4^n} = \frac{4^n-1}{3 \cdot {4^n}} \]

As n goes to infinity, this y-coordinate converges to 1/3. Thus all the right most boundary points above the x-axis in the Z2 dragon lie between y = 0 and y = 1/3.

The right most segments below the x-axis at iteration 4n+6 are just vertical translations by 1 of those above the x-axis. The right most boundary points in the fourth quadrant are therefore at the points \(\left( \dfrac{7}{3}, -1+\dfrac{b_n}{4^n}\right)\) and lie between y = −2/3 and y = −1.

Top Side along y = 5/3

The argument is similar to that above for the right side. Starting with the initial line segment −1 ≤ x ≤ 1, the following figures show the top most part of the Z2 dragon after 4 iterations (top) and 8 iterations (bottom). The grid size is 1/8 x 1/8.

topedge4
 
topedge8

We focus on the top most horizontal line segments to the right of the y-axis in these figures. The segment for iteration 4 extends from x = 1/2 to x = 1 and is of length 1/2. After four additional iterations, this segment has yielded two new top most horizontal line segments of length 1/8 and whose right endpoints are at x = 1/2 and x = 1. The endpoints of the iteration 4 segment become the right endpoints of the two segments in iteration 8.

Each sequence of four iterations will double the number of these top most line segments and reduce their size by a factor of 1/4. We claim that at iteration 4n+4, the right endpoint of each such segment is at a point whose x-coordinate is of the form \(1-\dfrac{b_n}{2 \cdot 4^{n-1}}\) for n ≥ 0. In the top figure we have n = 0 and b0 = 0. This gives the coordinate x = 1. In the bottom figure we have n = 1 and the only choices for b1 are (0)4 and (1)4 which give the endpoints with x-coordinates 1 and 1/2. Thus the claim holds for n = 0 and n = 1.

Suppose the claim is true for iteration 4n+4. A top most horizontal line segment with a right endpoint with x-coordinate \(1-\dfrac{b_n}{2 \cdot 4^{n-1}}\) at iteration 4n+4 will have length \(\dfrac{1}{2 \cdot 4^n}\). After four additional iterations, this segment will be replaced by two new segments with right endpoints with x-coordinates

\[x =1 -\frac{b_n}{2 \cdot 4^{n-1}} = 1 - \frac{4b_n}{2 \cdot 4^{n}} \: \text{ and } \: x =1-\frac{b_n}{2 \cdot 4^{n-1}} - \frac{1}{2 \cdot 4^{n}} =1- \frac{4b_n+1}{2 \cdot 4^{n}}\]

The result of multiplying bn by 4 will just shift all the digits in the base-4 representation of bn to the left and add a 0 at the end. Similarly, 4bn+1 will shift all the digits in the base-4 representation of bn to the left and add a 1 at the end. Thus in both cases the numerator of the x-coordinates of the new endpoints will contain only the digits 0 or 1 and there will be at most n+1 digits. Since this holds for all the segments from iteration 4n+4, the claim is also true for all the segments in iteration 4(n+1)+4.

Once a top most horizontal line segment appears in an iteration with right endpoint having x-coordinate \(1-\dfrac{b_n}{2 \cdot 4^{n-1}}\), all cycles of 4 iterations will continue to have a top most horizontal line segment with a right endpoint that has that same x-coordinate. Thus those endpoints will converge to the point \( \left( 1-\dfrac{b_n}{2 \cdot 4^{n-1}}, \dfrac{5}{3} \right) \) on the top boundary of the Z2 dragon.

At iteration 4n+4, the endpoint with the largest y-coordinate would be when bn = (11...11)4 with n digits in the base-4 representation. This would produce the x-coordinate

\[1-\frac{1+4+4^2+\ldots+4^{n-1}}{2 \cdot 4^{n-1}} = 1-\frac{4^n-1}{3 \cdot 2 \cdot {4^{n-1}}} \]

As n goes to infinity, this x-coordinate converges to 1 - 2/3 = 1/3. Thus all the top most boundary points in the Z2 dragon in the first quadrant lie between x = 1/3 and x = 1.

The top most segments to the left of the y-axis at iteration 4n+4 are just horizontal translations by 2 of those to the right of the y-axis. The top most boundary points in quadrant 2 are therefore at the points \(\left( -1-\dfrac{b_n}{2 \cdot 4^{n-1}}, \dfrac{5}{3} \right)\) and lie between x = −5/3 and x = −1.

Left Side along x = −7/3

By the symmetry of the Z2 dragon, if (x,y) is a point in the dragon, then so is (−x, −y). Therefor the left most boundary points occur at points of the form \[ \left( -\frac{7}{3}, 1-\frac{b_n}{4^n} \right) \; \text{ and } \; \left( -\frac{7}{3}, -\frac{b_n}{4^n} \right) \]

Bottom Side along y = −5/3

By the symmetry of the Z2 dragon, the bottom most boundary points occur at points of the form \[ \left( -1+\frac{b_n}{2 \cdot 4^{n-1}}, -\frac{5}{3} \right) \; \text{ and } \; \left( 1+\frac{b_n}{2 \cdot 4^{n-1}}, -\frac{5}{3} \right) \]