Twindragons and a Binary System for Complex Numbers

twindragon
number systems
fractals
Author

Jonny Comes

Published

October 21, 2023

Standard binary

This post is not about the standard binary number system, but it’s a decent place to start the discussion. In standard binary, every integer is represented by a string of 1’s and 0’s. To determine which integer is represented by a given string we translate the string into a sum of powers of 2. For example, in the standard binary system \(\textcolor{#17a2b8}{1100}\) represents the integer \[\textcolor{#17a2b8}{1}\cdot2^3+\textcolor{#17a2b8}{1}\cdot2^2+\textcolor{#17a2b8}{0}\cdot2^1+\textcolor{#17a2b8}{0}\cdot2^0,\] which (in the standard decimal system) is 12. Since the representation of numbers relies on powers of 2, we say that the standard binary system uses base 2.

The twindragon binary system for complex numbers

This post is concerned with a (non-standard) binary number system whose base is the complex number \(i-1\). We’ll see the beautiful fractal known as the twindragon showing up when we visualize this number system in the complex plane, so we call this number system the twindragon binary system.

First calculations

Let’s look at the same binary string 1100 from above, but this time using the new base of \(i-1\). In the twindragon binary system \(\textcolor{#e95420}{1100}\) represents \[\textcolor{#e95420}{1}(i-1)^3+\textcolor{#e95420}{1}(i-1)^2+\textcolor{#e95420}{0}(i-1)^1+\textcolor{#e95420}{0}(i-1)^0. \tag{1}\] For another example, in twindragon binary \(1111001\) represents \[(i-1)^6+(i-1)^5+(i-1)^4+(i-1)^3+(i-1)^0. \tag{2}\] To simplify these expressions, it will be useful to know powers of \(i-1\). Here are the first several: \[\begin{array}{|c|c|} \hline n & (i-1)^n \\ \hline 0 & 1 \\ 1 & i-1 \\ 2 & -2i \\ 3 & 2+2i \\ 4 & -4 \\ 5 & 4-4i \\ 6 & 8i \\ 7 & -8-8i \\ 8 & 16 \\ \hline \end{array}\] Using these powers we can simplify (1) to see that \(\textcolor{#e95420}{1100}\) is the twindragon binary representation of the integer 2. Simplifying (2) shows us \(1111001\) is the twindragon binary representation of the complex number \(3+6i\).

Notice that sums of powers of \(i-1\) will always result in a Guassian integer. In fact, we will soon see that each Guassian integer arises (uniquely) in this way.

Twindragon representations of units

Towards showing all Guassian integers have a twindragon binary representation, we start with the smallest. Of course, the twindragon representation of 0 is merely 0. The next smallest Gaussian integers are the four units: \(\pm 1, \pm i\). The following table shows the twindragon representations of those units. One can verify the values in the table using the methods above. \[\begin{array}{|c|c|} \hline \text{Gaussian} & \text{twindragon} \\ \text{integer} & \text{binary} \\ \hline 1 & 1 \\ i & 11 \\ -i & 111 \\ -1 & 11101 \\ \hline \end{array} \tag{3}\] Every other Guassian integer is the sum of unit Guassian integers. Since we know how the twindragon represents all the units, to see how to represent an arbitrary Guassian integer it suffices to provide an algorithm for twindragon addition.

Twindragon addition algorithm

The addition algorithm for the twindragon binary system is similar to the one using standard binary: stack the binary strings atop one another lining up the rightmost bit, then add bits one by one from right to left with the appropriate carry procedure. There are, however, two key rules for twindragon addition that make the algorithm quite different from the standard one.

A twindragon carry rule

The first key difference is the manner in which one “carries” bits. In the standard algorithm, one needs to “carry a 1” whenever the adding two 1’s. This corresponds to the fact that the standard binary representation of 2 (i.e. 1+1) is 10. As we’ve seen above, the twindragon binary representation of the integer 2 is 1100. Thus we have the following twindragon carry rule:

\[\begin{array}{cr} & 1\\ + & 1\\ \hline & 1100 \end{array} \tag{4}\]

This means that when the twindragon adds two 1’s it carries both 1’s to the positions according to the carry rule (4). For example, consider the following sum: \[\begin{array}{cr} & 111001\\ + & 101010\\ \hline \end{array}\] Starting from the right, the first three columns of bits are easily handled, leaving us at the following point: \[\begin{array}{cr} & 11\textcolor{#e95420}{1}\textcolor{#aea79f}{001}\\ + & 10\textcolor{#e95420}{1}\textcolor{#aea79f}{010}\\ \hline & 011 \end{array}\] Now, we carry the next two 1’s according to the carry rule (4) leaving us with the following: \[\begin{array}{cr} & \textcolor{#e95420}{1100}\phantom{000}\\ & 11\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}001}\\ + & 10\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}010}\\ \hline & 0011 \end{array}\] The next column of bits is easily handled, leaving us in a position where we will have to carry two 1’s again: \[\begin{array}{cr} & 1\textcolor{#e95420}{1}\textcolor{#aea79f}{00}\phantom{000}\\ & \textcolor{#e95420}{1}\textcolor{#aea79f}{11001}\\ + & 1\textcolor{#aea79f}{01010}\\ \hline & 10011 \end{array}\] Again, we carry according to the carry rule (4) leaving us with \[\begin{array}{cr} & \textcolor{#e95420}{1100}\phantom{00000} \\ & 1\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}00}\phantom{000}\\ & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}11001}\\ + & \textcolor{#aea79f}{101010}\\ \hline & 110011 \end{array}\] The last three columns involve no carries, which gives the final result: \[\begin{array}{cr} & \textcolor{#aea79f}{1100}\phantom{00000} \\ & \textcolor{#aea79f}{1100}\phantom{000}\\ & \textcolor{#aea79f}{111001}\\ + & \textcolor{#aea79f}{101010}\\ \hline & 111110011 \end{array}\]

A twindragon cancel rule

Recall from (3) that the twindragon representations of \(i\) and \(-i\) are 11 and 111, respectively. As a consequence, we get the following twindragon cancel rule: \[\begin{array}{cr} & 11\\ + & 111\\ \hline & 0 \end{array} \tag{5}\] Observe that the sum in (5) cannot be computed in a finite number of steps using just the carry rule (4). Indeed, applying the carry rule to the rightmost bits in the sum above gives the following \[ \begin{array}{cr} & 1\textcolor{#e95420}{1}\\ + & 11\textcolor{#e95420}{1}\\ \hline \end{array} \quad\leadsto\quad \begin{array}{cr} & \textcolor{#e95420}{1100}\\ & 1\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}}\\ + & 11\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}}\\ \hline & 0 \end{array} \] If we ignore the 0’s and drop the top two 1’s down a row or two, then we are left with the following: \[\begin{array}{cr} & 11\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}}\\ + & 111\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}}\\ \hline & 0 \end{array}\] Computing the sum of the remaining columns of bits is the same sum we started with. Thus, if we continue then we will get a never-ending sting of 0’s as a result (which could be considered correct), but the algorithm never terminates.

It turns out that the combination of the carry rule (4) and cancel rule (5) suffice to compute the sum of any two binary strings in a finite number of steps. The most efficient way is to apply the cancel rule whenever possible. Here’s an example: \[\begin{array}{cr} & 111011111\\ + & 10110110\\ \hline \end{array}\] To start, note that we can use the cancel rule (5) as follows: \[ \begin{array}{cr} & 11101\textcolor{#e95420}{111}1\\ + & 10110\textcolor{#e95420}{11}0\\ \hline \end{array} \quad\leadsto\quad \begin{array}{cr} & 11101\textcolor{#e95420}{000}1\\ + & 10110\textcolor{#e95420}{00}0\\ \hline \end{array} \] Now, we proceed from right to left, and nothing interesting happens (thanks to all the new 0’s) until we reach the following point: \[\begin{array}{cr} & 11101\textcolor{#aea79f}{0001}\\ + & 1011\textcolor{#aea79f}{0000}\\ \hline & 0001 \end{array}\] Next, we apply the carry rule (4): \[ \begin{array}{cr} \\ & 1110\textcolor{#e95420}{1}\textcolor{#aea79f}{0001}\\ + & 101\textcolor{#e95420}{1}\textcolor{#aea79f}{0000}\\ \hline & 0001 \end{array} \quad\leadsto\quad \begin{array}{cr} & \textcolor{#e95420}{1100}\phantom{0000}\\ & 1110\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}0001}\\ + & 101\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}0000}\\ \hline & 00001 \end{array} \] Now, we can once again apply the cancel rule (5): \[ \begin{array}{cr} & \textcolor{#e95420}{11}0\textcolor{#aea79f}{0}\phantom{0000}\\ & \textcolor{#e95420}{111}0\textcolor{#aea79f}{10001}\\ + & 101\textcolor{#aea79f}{10000}\\ \hline & 00001 \end{array} \quad\leadsto\quad \begin{array}{cr} & \textcolor{#e95420}{00}0\textcolor{#aea79f}{0}\phantom{0000}\\ & \textcolor{#e95420}{000}0\textcolor{#aea79f}{10001}\\ + & 101\textcolor{#aea79f}{10000}\\ \hline & 00001 \end{array} \] The rest of the calculation is straightforward, giving the following result: \[\begin{array}{cr} & \textcolor{#aea79f}{0000}\phantom{0000}\\ & \textcolor{#aea79f}{000010001}\\ + & \textcolor{#aea79f}{10110000}\\ \hline & 10100001 \end{array}\]

The addition algorithm

As the example above illustrates, the following algorithm can be used to compute the sum of any finite collection of binary strings in the twindragon binary system:

  • Stack the binary strings atop one another in the usual way.
  • Start with the rightmost column of bits.
  • While there are still columns of nonzero bits to add:
    • Apply the cancel rule as many times as possible.
    • While there are at least two 1’s in the current column:
      • Apply the carry rule.
      • Apply the cancel rule if possible.
    • Add the remaining bits in the column (at most one of which is a 1).
    • Move one column to the left

The proof that the algorithm always terminates can be found below.

Proof

It suffices to prove that the twindragon sum of two binary strings terminates. By adding extra 0’s to the left of one string if necessary, we may assume both strings have the same length. Thus, the sum has the following form: \[\begin{array}{cccccc} & a_n & \cdots & a_2 & a_1 & a_0\\ + & b_n & \cdots & b_2 & b_1 & a_0\\ \hline \end{array}\] We proceed by inducting on the number of 1’s that need to be added. If at any point we can apply the cancel rule, the number of 1’s decreases by five, and we are done by induction. Thus, we may assume it is never possible to apply the cancel rule. Starting on the right, add all the columns that contain only 0’s bringing us to a point looking like the following: \[\begin{array}{cccccc} & a_n & \cdots & a_{j+1} & a_j & \textcolor{#aea79f}{0\cdots0}\\ + & b_n & \cdots & b_{j+1} & b_j & \textcolor{#aea79f}{0\cdots0}\\ \hline &&&&& 0\cdots0 \end{array}\] Where at least one of \(a_j\) or \(b_j\) is 1. If the other is 0, then we add that column without a carry, the remaining columns will have one fewer 1, and we are done by induction. Thus we only need to consider the case where both \(a_j\) and \(b_j\) are 1, and we carry: \[\begin{array}{ccccccc} & a_n & \cdots & a_{j+3} & a_{j+2} & a_{j+1} & \textcolor{#e95420}{1}~\textcolor{#aea79f}{0\cdots0}\\ + & b_n & \cdots & b_{j+3} & b_{j+2} & b_{j+1} & \textcolor{#e95420}{1}~\textcolor{#aea79f}{0\cdots0}\\ \hline &&&&&& \phantom{1~}0\cdots0 \end{array}\] \[\begin{array}{ccccccr} &&&\textcolor{#e95420}{1}&\textcolor{#e95420}{1}&\textcolor{#e95420}{0}& \textcolor{#e95420}{0}~\phantom{0\cdots0} \\ & a_n & \cdots & a_{j+3} & a_{j+2} & a_{j+1} & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}~0\cdots0}\\ + & b_n & \cdots & b_{j+3} & b_{j+2} & b_{j+1} & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}~0\cdots0}\\ \hline &&&&&& 0~0\cdots0 \end{array}\] Now, we may assume \(a_{j+1}\) and \(b_{j+1}\) are either both 0’s or both 1’s (else we can add that column, and we’re done by induction). In either case, adding the \((j+1)^{\text{st}}\) column will not contribute any more 1’s to the \((j+2)^{\text{nd}}\) column. Thus we may assume one of \(a_{j+2}\) and \(b_{j+2}\) is 0 and the other is 1 (else adding the \((j+2)^{\text{nd}}\) column will result in a 1, and the remaining columns will have one fewer 1, and we’re done by induction). Without loss of generality, we may assume \(a_{j+2}=1\) and \(b_{j+2}=0\), so the sum looks like \[\begin{array}{ccccccr} &&& 1 & 1 & 0 & \textcolor{#aea79f}{0}~\phantom{0\cdots0} \\ & a_n & \cdots & a_{j+3} & 1 & a_{j+1} & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}~0\cdots0}\\ + & b_n & \cdots & b_{j+3} & 0 & b_{j+1} & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}~0\cdots0}\\ \hline &&&&&& 0~0\cdots0 \end{array}\] Now, if \(a_{j+1}\) and \(b_{j+1}\) are both 1’s, then we can apply the cancel rule (and we’re done by induction), so it suffices to consider the case where they are both 0. Then we add the \((j+1)^{\text{st}}\) column and we perform a carry on the \((j+2)^{\text{nd}}\) column: \[\begin{array}{ccccccr} &&&&& 1 & \textcolor{#e95420}{1} ~ \textcolor{#aea79f}{0}~\textcolor{#aea79f}{0}~\phantom{0\cdots0} \\ & a_n & \cdots & a_{j+5} & a_{j+4} & a_{j+3} & \textcolor{#e95420}{1} ~ \textcolor{#aea79f}{0~\hspace{-5.75pt}\not{1}~0\cdots0}\\ + & b_n & \cdots & b_{j+5} & b_{j+4} & b_{j+3} & 0 ~ \textcolor{#aea79f}{0~\hspace{-5.75pt}\not{1}~0\cdots0}\\ \hline &&&&&& 0~0~0\cdots0 \end{array}\]

\[\begin{array}{ccccccr} & & & \textcolor{#e95420}{1} & \textcolor{#e95420}{1} & \textcolor{#e95420}{0} & \textcolor{#e95420}{0}\phantom{~0~0~0\cdots0}\\ &&&&& 1 & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}~0}~\textcolor{#aea79f}{0}~\phantom{0\cdots0} \\ & a_n & \cdots & a_{j+5} & a_{j+4} & a_{j+3} & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}~0~\hspace{-5.75pt}\not{1}~0\cdots0}\\ + & b_n & \cdots & b_{j+5} & b_{j+4} & b_{j+3} & \textcolor{#aea79f}{0~0~\hspace{-5.75pt}\not{1}~0\cdots0}\\ \hline &&&&&& 0~0~0~0\cdots0 \end{array}\] Arguing as before, if both \(a_{j+3}\) and \(b_{j+3}\) are 0, then adding the \((j+3)^{\text{rd}}\) column will leave us with one fewer 1 (and we’d be done by induction). Thus, we may assume there are two 1’s in the \((j+3)^{\text{rd}}\) column. Since a carry from the \((j+3)^{\text{rd}}\) column will not contribute a 1 to the \((j+4)^{\text{th}}\) column, similar reasoning allows us to assume one of \(a_{j+4}\) and \(b_{j+4}\) is a 1. But now we are in a situation where the \((j+3)^{\text{rd}}\) and \((j+4)^{\text{th}}\) columns each have two 1’s, and the \((j+5)^{\text{th}}\) column has a 1. Then we can apply the cancel rule, and we are done by induction.

Twindragon representations of all Gaussian integers

To see that every Gaussian integer has a twindragon representation, notice that every Gaussian integer can be written as a sum of the units \(\pm1\) and \(\pm i\). Since we know how to represent those units in twindragon binary (see (3)) we can find the desired twindragon representation using the addition algorithm. For example, to find the twindragon representation of \(-3+5i\) we add three copies of the representation of \(-1\) (11101) to five copies of the representation of \(i\) (11). For those who are interested, the details of finding the representation of \(-3+5i\) can be found below.
Details Let’s see what happens: \[\begin{array}{cr} & 11101\\ & 11101\\ & 11101\\ & 11\\ & 11\\ & 11\\ & 11\\ + & 11\\ \hline \end{array}\] First, let’s shift the bits down in the left three columns for convenience: \[\begin{array}{cr} & 1\\ & 1\\ & 1\\ & 11\\ & 11\\ & 11111\\ & 11111\\ + & 11111\\ \hline \end{array}\] Now, we can apply a the cancel rule (5) a couple times: \[ \begin{array}{cr} & 1\\ & 1\\ & 1\\ & 11\\ & \textcolor{#e95420}{ 11}\\ & 11\textcolor{#e95420}{111}\\ & 1\textcolor{blue}{11}11\\ + & \textcolor{blue}{111}11\\ \hline \end{array} \quad\leadsto\quad \begin{array}{cr} & 1\\ & 1\\ & 1\\ & 11\\ & \textcolor{#e95420}{ 00}\\ & 11\textcolor{#e95420}{000}\\ & 1\textcolor{blue}{00}11\\ + & \textcolor{blue}{000}11\\ \hline \end{array} \] After shifting the bits down again (for convenience) we have: \[\begin{array}{cr} & 1\\ & 1\\ & 1\\ & 11\\ & 10011\\ + & 11011\\ \hline \end{array}\] Next, we apply the carry rule (4) one time to the rightmost column to get \[ \begin{array}{cr} & \textcolor{#e95420}{1}\\ & \textcolor{#e95420}{1}\\ & 1\\ & 11\\ & 10011\\ + & 11011\\ \hline \end{array} \quad\leadsto\quad \begin{array}{cr} & \textcolor{#e95420}{1100}\\ & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}}\\ & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}}\\ & 1\\ & 11\\ & 10011\\ + & 11011\\ \hline \end{array}\] Dropping bits (and removing crossed out ones) gives the following, where we apply the cancel rule (5): \[ \begin{array}{cr} & 1\\ & \textcolor{#e95420}{11}\\ & 11\textcolor{#e95420}{111}\\ + & 11011\\ \hline \end{array} \quad\leadsto\quad \begin{array}{cr} & 1\\ & \textcolor{#e95420}{00}\\ & 11\textcolor{#e95420}{000}\\ + & 11011\\ \hline \end{array} \] Let’s drop the bits again, and then we apply the carry rule to the right column: \[ \begin{array}{cr} \\ & 1100\textcolor{#e95420}{1}\\ + & 1101\textcolor{#e95420}{1}\\ \hline \end{array} \quad\leadsto\quad \begin{array}{cr} & \textcolor{#e95420}{1100}\\ & 1100\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}}\\ + & 1101\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}}\\ \hline \end{array} \] Now we sum the three rightmost columns to get: \[ \begin{array}{cr} & 1\textcolor{#aea79f}{100}\\ & 11\textcolor{#aea79f}{00\hspace{-5.75pt}\not{1}}\\ + & 11\textcolor{#aea79f}{01\hspace{-5.75pt}\not{1}}\\ \hline & 110 \end{array} \] The next column requires a carry: \[ \begin{array}{cr} & \textcolor{#e95420}{1}\textcolor{#aea79f}{100}\\ & 1\textcolor{#e95420}{1}\textcolor{#aea79f}{00\hspace{-5.75pt}\not{1}}\\ + & 11\textcolor{#aea79f}{01\hspace{-5.75pt}\not{1}}\\ \hline & 110 \end{array} \quad\leadsto\quad \begin{array}{cr} & \textcolor{#e95420}{1100}\phantom{000}\\ & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}100}\\ & 1\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}00\hspace{-5.75pt}\not{1}}\\ + & 11\textcolor{#aea79f}{01\hspace{-5.75pt}\not{1}}\\ \hline & 110 \end{array} \] We now add the current column of bits, and then drop the other bits for convenience: \[ \begin{array}{cr} & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}100}\\ & 1\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}00\hspace{-5.75pt}\not{1}}\\ + & 111\textcolor{#aea79f}{101\hspace{-5.75pt}\not{1}}\\ \hline & 1110 \end{array} \] The next column uses a carry rule: \[ \begin{array}{cr} & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}100}\\ & \textcolor{#e95420}{1}\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}00\hspace{-5.75pt}\not{1}}\\ + & 11\textcolor{#e95420}{1}\textcolor{#aea79f}{101\hspace{-5.75pt}\not{1}}\\ \hline & 1110 \end{array} \quad\leadsto\quad \begin{array}{cr} & \textcolor{#e95420}{1100}\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}100}\\ & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}\hspace{-5.75pt}\not{1}00\hspace{-5.75pt}\not{1}}\\ + & 11\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}101\hspace{-5.75pt}\not{1}}\\ \hline & 1110 \end{array} \] Now we can sum the current column, and the next one. After dropping some bits we are left with \[ \begin{array}{cr} & 1\textcolor{#aea79f}{0\hspace{-5.75pt}\not{1}\hspace{-5.75pt}\not{1}00\hspace{-5.75pt}\not{1}}\\ + & 11\textcolor{#aea79f}{1\hspace{-5.75pt}\not{1}101\hspace{-5.75pt}\not{1}}\\ \hline & 101110 \end{array} \] One last carry: \[ \begin{array}{cr} \\ & \textcolor{#e95420}{1}\textcolor{#aea79f}{0\hspace{-5.75pt}\not{1}\hspace{-5.75pt}\not{1}00\hspace{-5.75pt}\not{1}}\\ + & 1\textcolor{#e95420}{1}\textcolor{#aea79f}{1\hspace{-5.75pt}\not{1}101\hspace{-5.75pt}\not{1}}\\ \hline & 101110 \end{array} \quad\leadsto\quad \begin{array}{cr} & \textcolor{#e95420}{1100}\phantom{000000}\\ & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}0\hspace{-5.75pt}\not{1}\hspace{-5.75pt}\not{1}00\hspace{-5.75pt}\not{1}}\\ + & 1\textcolor{#aea79f}{\hspace{-5.75pt}\not{1}1\hspace{-5.75pt}\not{1}101\hspace{-5.75pt}\not{1}}\\ \hline & 101110 \end{array} \] The rest is straightforward: \[ \begin{array}{cr} & \textcolor{#aea79f}{1100}\phantom{000000} \\ & \textcolor{#aea79f}{\hspace{-5.75pt}\not{1}0\hspace{-5.75pt}\not{1}\hspace{-5.75pt}\not{1}00\hspace{-5.75pt}\not{1}} \\ + & \textcolor{#aea79f}{1\hspace{-5.75pt}\not{1}1\hspace{-5.75pt}\not{1}101\hspace{-5.75pt}\not{1}}\\ \hline & \text{$1110101110$} \end{array} \] Thus, we have found that the twindragon representation of \(-3+5i\) is \(1110101110\).

Twindragons in the complex plane

We have seen that every Gaussian integer has a twindragon representation. In fact, these representations are unique (it’s a fun exercise to prove this). Thus, we have a way to label every point in the lattice of Gaussian integers in the complex plane with a binary string.

In the following plot, a unit square is drawn around each of the \(2^{15}\) Gaussian integers whose twindragon representations use 15 or fewer bits. The color of the square is determined by the length of the binary string: the more bits, the darker the square. For example, 0 is the lightest color; you can find it in the middle of the picture (you can zoom in). The next lightest square is 1, then 10 and 11 are just a little darker, and so on. The darkest squares are the \(2^{14}\) Gaussian integers whose twindragon representations are 15 bits long.

As the color darkens, the corresponding regions in the plane are approaching the beautiful Davis-Knuth dragon, also known as the twindragon, hence the name of the binary system.

Code 
import { chart } from "d/3964d6d505b9f008"
chart

A twindragon fractiling

We can extend the twindragon system from Gaussian integers to all complex numbers by adding fractional parts. For example, we write \(101.01\) for the complex number \[(i-1)^2 + (i-1)^0 + (i-1)^{-2} = 1-1.5i\] We call \(101\) and \(0.01\) the whole and fraction parts of \(101.01\), respectively. Notice that representations with nonzero fraction parts can indeed have non-integer real or imaginary parts. One can show that every complex number can be represented in twindragon binary if we allow (possibly infinitely long) fraction parts. It should be noted that we no longer get uniqueness of representations after adding fraction parts.

If we plot all the complex numbers whose twindragon representation have the same fixed whole part, the result is a twindragon. Moreover, all these twindragons (one for each Gaussian integer) tile the complex plane. Such a tiling by fractals is sometimes called a fractiling. We can see this twindragon fractiling in the following plot. There we plot each complex number whose twindragon representation has whole part with at most 3 bits, and fraction with at most 13 bits. The color of these \(2^{16}\) points corresponds to the whole part as follows:

\[\begin{array}{|c|cccccccc|} \hline \text{whole part} & 0 & 1 & 10 & 11 & 100 & 101 & 110 & 111\\ \hline \text{color} & \textcolor{#ff6961}{\bullet} & \textcolor{#ffb480}{\bullet} & \textcolor{#f8f38d}{\bullet} & \textcolor{#42d6a4}{\bullet} & \textcolor{#08cad1}{\bullet} & \textcolor{#59adf6}{\bullet} & \textcolor{#9d94ff}{\bullet} & \textcolor{#c780e8}{\bullet} \\ \hline \end{array}\]

Code 
import { fractionChart } from "d/526bb5e596bf883a"
fractionChart

A twindragon of twindragons

In the first plot, we used unit squares to represent each Gaussian integer, and those squares nicely tiled the complex plane. However, those squares are not the best picture of the Gaussian integers from the viewpoint of the twindragon. Indeed, the second plot shows that we should really replace those unit squares with “unit twindragons”, i.e. the collection of all points in the complex plane that share the same whole part. In the final plot below, we plot all complex numbers whose twindragon representation has whole part with at most 11 bits, and fraction part with at most 6 bits. The points are colored according to the length of their whole part (the longer the whole part the darker the point).

Code 
import { twindragonChart } from "d/60ea50d21dd08209"
twindragonChart

References

I first learned about the twindragon binary number system and the corresponding fractiling of the complex plane from G. Edgar’s book Measure, Topology, and Fractal Geometry. The first appearance the twindragon binary number system is in W. Penny’s A “Binary” System for Complex Numbers. I believe the first connection between the number system and the twindragon fractal is due to D. Knuth: Number representations and dragon curves.