Here There Be Dragons

Last week my daughter asked me about weird bases. “Do bases have to be integers?” “Do they have to be real?” (She’s heard about complex numbers such as i, the infamous square root of minus one.) Then she asked “How would you write 256 in base i+1?”

She swears that she made up the question on the spot, but the answer is suspiciously nice, as we can see by starting with i+1 and repeatedly squaring. If we multiply i+1 by itself we get (i+1)·(i+1) = i·i + 1 + 1·i + 1·1, or –1 + i + i + 1; the –1 and the 1 cancel, so we get (i+1)2 = 2i. Square both sides: (i+1)4 = (2i)(2i) = (2)(2)(i)(i) = (4)(–1) = –4. Square again: (i+1)8 = (–4)(–4) = 16. Square one last time: (i+1)16 = (16)(16) = 256. So 256 equals 1 times (i+1)16, plus 0 times (i+1)15, plus 0 times (i+1)14, plus …, plus 0 times (i+1)1, plus 0 times (i+1)0, and we conclude that the base i+1 representation of 256 is 1 followed by sixteen 0’s: 10000000000000000. (What are the chances?)

I posted this on Twitter, and someone wrote “Impressive; how old is she?”.  My daughter just turned 13, and 13 is (16)+(–4)+(1) which equals (i+1)8 + (i+1)4 + (i+1)0, so I wrote back “She just turned 100010001.”

But then I got to thinking: do I really know how to write every positive integer in base i+1? Or did I just get lucky?

Well, obviously I was very lucky to be asked about 256, which is an exact power of i+1. The number 13, although usually considered unlucky, is luckily expressible as a sum of three powers of i+1.

The question “Can every counting number be expressed as a sum of powers of i+1?” is easy: we can just add (i+1)0 (better known as 1) to itself over and over again to reach any counting number we like. But if we want base i+1 to use only the digits 0 and 1, then we’d better not repeat any powers. Not so easy!

I asked my chums at math-fun (a mathematical email forum for serious amateurs and playful professionals) to help me out with base i+1 (though I called it base 1+i, and will do so hereafter, since by convention the real part of a complex number is given first). When we add up powers of 1+i, we get complex numbers of the form a+bi, where a and b are ordinary integers. Complex numbers of this kind are called Gaussian integers. Can we write all Gaussian integers as sums of different powers of 1+i? If not all of them, then which ones?

Before we press ahead with the question, let’s consider why people like me ask it. Base ten is the favorite base of humans, and base two is the favorite base of computers; why think about other bases? 

For math-funsters (as we call ourselves), the answer is “Because it’s fun”. More personally, and more specifically, for me it’s the kind of fun I had as a kid, growing up in Great Neck, exploring undeveloped patches of land adjacent to where the houses were, filling in the blank spaces in my mental map of the town. On old maps made by European travelers, one sometimes sees the words “Here there be dragons”, indicating an unexplored and potentially dangerous part of the sea. For me, suburbia is too tame, and dragons are too seldom. Ironically, some of us dragon-lovers banish the very dragons we love by the act of mapping the places they haunt (see my recent tongue-in-cheek tweet about this).

Before I share with you a bit of what I’ve learned from the math-fun gang, it’s worth mentioning that as of 2021 the phrase “base 1+i” has no universally agreed-upon meaning. Do we insist that only the digits 0 and 1 be allowed? If so, we have to face the fact that some numbers can’t be represented in base 1+i at all; in fact, the number 2 can’t. Will we therefore allow ourselves the digits 0, 1, and 2? Then some numbers might end up having more than one representation; which one do we anoint as the “true” base 1+i representation? Maybe we’ll decide we’d rather have the allowed digits be –1, 0, and 1. That would be a different system for representing numbers, based on powers of 1+i; would it, too, deserve to be called “base 1+i”?

If we make the choice of forbidding all digits save 0 and 1, then we get a system that can’t represent the number 2, but it is a pretty system nonetheless. Here’s a picture showing all 256 of the Gaussian integers expressible in the form a(1+i)7 + b(1+i)6 + c(1+i)5 + d(1+i)4 + e(1+i)3 + f(1+i)2 + g(1+i)1 + h(1+i)0 where each of the numbers a,b,c,d,e,f,g,h is either 0 or 1:

Tom Karzes of math-fun made some pictures showing what goes on as we increase the number of digits even further. The shape shown above converges to a fractal known as a twindragon or Davis-Knuth dragon; some people call it the Jurassic Park dragon since successive approximations to the fractal were used by Michael Crichton to decorate the chapter title pages in his book “Jurassic Park”. See the Wikipedia page on dragon curves.

What intrigues me most is that the Gaussian integers that aren’t expressible as sums of distinct powers of 1+i (shown in white below) form the same shape as the Gaussian integers that are expressible as sums of distinct powers of 1+i (shown in black below).

The spiral reminds me a bit of the start of the yellow brick road in “The Wizard of Oz”, which appears to also be the start of a mysterious red brick road that nobody ever talks about:

In a more metaphysical vein, the yin-yang symmetry in Tom’s picture highlights the harmonious duality between the Possible and the Impossible in mathematics. Of course one can, in math as in real life, view a statement of impossibility as a thrown-down gauntlet, and try to meet the challenge. “You say I can’t write 2 as a sum of powers of 1+i? Well, what if I change the game? What if I allow negative exponents? What if I allow infinite sums?” Or one can simply accept the impossibility of some task as a part of mathematical reality and try to see the impossibility as a thing of beauty in itself, as part of a larger pattern. Seen in this light, the Possible and the Impossible can be not so much opposites as twins.

Anyway, from Tom’s picture we see that, in a certain sense, half of the Gaussian integers are expressible in base 1+i and half aren’t. [Note: After this article “went to press” Tom Karzes and Steve Lucas and I proved that the set of nonexpressible Gaussian integers is the set of expressible Gaussian integers rotated by 180 degrees about the complex number i/2.] This give us a quantitative answer to my question “How lucky was I that my daughter happened to pick a number (256) that lies in the representable set and that her age (13) happens to be in the representable set?” Each event had a one-in-two chance of happening, and if we regard the two events as statistically independent, then the chance I’d luck out in both ways is one-in-four, or 25%. So I was more fortunate than by rights should have been.

But of course, what really matters (even if it’s less quantifiable) is how supremely lucky I am to have a kid who asks me such stimulating questions!

8 thoughts on “Here There Be Dragons

  1. David Speyer

    So, if R is an integral domain, b is an element of R such that R/bR is finite, and {d1, d2, .., dn} are representatives for the equivalence classes of R/bR, we can try to write elements in R in base b with digits di. And then we can ask what fraction of elements of R can be so expressed. (It might depend on what notion of density we use in R, but let’s hope not.) Has anyone thought about this? Is it always rational? For example, what fraction of Z can be written in base 3, using the digits {0,1,5}?

    I have some vague memory that Kiran Kedlaya and some undergraduate were thinking about this when he and I were both at MIT (which narrows it down to 2008-2010).

    Liked by 1 person

    Reply
    1. jamespropp Post author

      Nice question! Changing your example slightly, if we do base three with the digit set {0,2,4} then we get exactly the even nonnegative integers, which I guess should be construed as having density 1/4 (though maybe its upper density, 1/2, is more like what you had in mind). For the digit set {0,1,5}, I have no idea what to expect. Would any readers like to do some experiments and report what they find?

      Like

      Reply
      1. Stephen Lucas

        For what it is worth, you can represent every natural number in base 3 using the digits 0,1,-7. Reference: D.W. Matula, Basic digit sets for radix representation, Journal of the Association for Computing Machinery 29(4) (1982) 1131–1143.

        Liked by 2 people

  2. David Speyer

    Actually, I am going to register a prediction that the limit doesn’t exist, but, rather, the fraction of expressible numbers less than 3^{t+k} approaches a periodic function of t, as we send k to infinity through the integers. For example, the fraction of expressible numbers less than 3^k is {0.666667, 0.666667, 0.62963, 0.62963, 0.625514} (maybe approaching 5/8?), whereas the fraction of expressible numbers less than 2*3^k is {0.666667, 0.722222, 0.740741, 0.746914, 0.748971} (maybe approaching 3/4?).

    I am reminded of the dance marathon problem: N people start dancing. Every time the song changes, each person independently chooses to sit down or keep dancing, with probability 1/2 for each. What is the probability that, at some point, exactly one dancer is left? The answer is a periodic function of log_2(N). See https://mathoverflow.net/questions/279231/the-dance-marathon-problem .

    Like

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s