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 * + *i·*1 + 1·*i* + 1·1, or –1 + *i* + *i* + 1; the –1 and the 1 cancel, so we get (*i*+1)^{2} = 2*i*. Square both sides: (*i*+1)^{4} = (2*i*)(2*i*) = (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!

dpthurstDid someone point out that every number is representable in base i-1?

LikeLiked by 1 person

jamesproppPost authorThanks for reminding me to mention this!

LikeLike

David SpeyerSo, 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).

LikeLiked by 1 person

jamesproppPost authorNice 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?

LikeLike

David SpeyerBetween 1 and 1000, there are 663 numbers expressible with {0,1,5}, giving a density of 2/3 among positive integers, or 1/3 among all integers.

A plot of the cumulative count suggests that it is becoming linear, although there is a big dip between about 150 and 250 and another from about 450 to 650, so I’m not sure. See http://www.math.lsa.umich.edu/~speyer/digits.png . Maybe the dips are centered on 2×3^k ?

LikeLiked by 1 person

Stephen LucasFor 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.

LikeLiked by 2 people

David SpeyerThanks for the reference! Matula’s Theorem 5 gives us a way to understand why base 1+i caused problems: (1+i)-1 is a unit, and hence divides everything.

LikeLiked by 1 person

David SpeyerActually, 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 .

LikeLike

Pingback: Tricks of the Trade |