All About That Base

by Jonathan Kujawa


At the University of Oklahoma last week.

While considering topics for this month's 3QD essay, the US Senate voted to approve a tax bill which not only dramatically reshapes US tax law, but says a great deal about our society's values. We're in an era where research and education are dramatically underfunded and underappreciated, to be knowledgeable about a subject is an automatic disqualification, and where what things which should be a question of fact and evidence are being dragged down into the political muck. I thought about writing about the Dark Ages and how the advancement of knowledge is not guaranteed. About the danger of eating our seed corn. About how it feels like we are truly living in the darkest timeline [1]. But here at 3QD this is preaching to the choir. I'd rather light a candle which can be shared with others. I'd rather talk about Exploding Dots.

In math even the most innocuous ideas can lead to undiscovered worlds. All we need is equal doses of creativity and bravery. The creativity to ask crazy questions and the bravery to try crazy things. As I tell my students, bravery in math should be easy to come by. There is no harm in trying. After all, this isn't brain surgery or nuclear engineering — nobody will die if we screw up! — just erase and try again.

The really scarce commodity is creativity. After 18+ years of schools drilling the creativity right out of your skull, it's awfully hard to let your mathematical freak flag fly. As David Hilbert said when he heard one of his students had dropped out to study poetry, "Good, he did not have enough imagination to become a mathematician". But, with some practice, we can undo the damage of our early years and start to see the wonders of the mathematical universe. Sometimes all it takes is a new perspective.


Photo by Nicolás Boullosa.

To start, let's talk about the Fibonacci sequence. As you might remember, this is the sequence of numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269,… and so on, where each number is obtained by summing the previous two. Faithful 3QD readers might recall we ran across the Fibonacci sequence three years ago. In it, we learned Carmichael showed nearly every Fibonacci number contains a prime factor which has not occurred as a factor in any of the numbers which occur earlier in the sequence. The simple rule of adding two to get the next gives us a sequence of numbers of infinitely rich complexity! In that essay we talked about the work of Dr. Krieger. She showed there are many other sequences with the same rich supply of prime factors and that her examples have close connections to the Mandelbrot set.

Now let us look at the Fibonacci sequence from a different perspective. Instead of asking for lots of different factors, let us instead pick a single factor and see when it occurs. For example, our fixed factor could be 2. A number has 2 as a factor if and only if it is even. So the question is, which Fibonacci numbers are even? Looking at our list, it appears every third number in the Fibonacci sequence is even. Indeed, once you notice that odd + odd is even, and odd + even and even+odd are odd, it is not too hard to see this holds true for all the Fibonacci numbers. Without even computing it, I know that the 2017th and 2018th Fibonacci numbers will be odd, while the 2019th will be even!

The big new idea is to ask what happens if you look at a fixed divisor. There is nothing special about 2. We could ask which Fibonacci numbers are evenly divisible by 3 or 4 or 10 or 9276581. If there were no beauty in the universe, perhaps we wouldn't dare to dream our pattern should have an analogue for other divisors. Fortunately, regardless of human affairs, the universe continues to be beautiful. There is a result which goes back to Lagrange in the 1780s which says that if you pick any m as your fixed divisor, then m will periodically be a factor of the Fibonacci numbers. That is, there is a number d (which will depend on m) such that m is a factor of the dth, 2dth, 3dth, 4dth, … Fibonacci numbers, but not of the others!

More generally, you can look at not just if m is a factor, but look at remainders when you divide by m. So if m=3, then the possible remainders are 0 (when 3 is a factor), 1, and 2. It is called "reducing modulo m" when you look at just the remainders after division by m. For example, when m is 2, the Fibonacci sequence reduces modulo 2 and becomes 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, ….. When you reduce modulo 3, the Fibonacci sequence becomes 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, … If you look closely, you'll see it repeats over and over, with the sequence of remainders repeating every eight numbers.

Lagrange showed, for every m, the Fibonacci sequence is periodic like this when you reduce modulo m. The remainders will repeat over and over. Before we leave the Fibonacci numbers, let me mention two other cool facts which I find equally mysterious and amazing. The first is that, while the sequence of remainders repeats every three numbers when our divisor is 2, this is the exception. For every other divisor the length of the repeating pattern is an even number. Second, while a repeating sequence of remainders might have several zeros (namely, whenever m evenly divides the Fibonacci number), it has to be that the number of zeros in each repeat is 1, 2, or 4! For example, when we reduced modulo 3 earlier, we got exactly two zeros in each repeat. For mysterious reasons we can't have three zeros or anything else but 1, 2, or 4 zeros in each repeat.

Now to Exploding Dots! So far as I know, they were first introduced by James Stanton. There is a delightful webpage with a series of videos which tell the tale of Exploding Dots from beginning to end. Stanton developed the videos for the 2017 Global Math Project. The idea of the GMP is to provide a delightful and meaningful mathematical topic suitable for folks of all ages. In 2017 this was Exploding Dots. I'll only give you a taste. You'll need to check out the videos for the full story. I can't recommend them highly enough to anyone over the age of five with an interest in math.

You might have never thought about why or how we write numbers the way we do. It has to do with the fact that we write numbers in base 10 (no doubt because most of us have ten fingers!), When we write 2017, we mean there are 2 1000s, 0 100s, 1 ten, and 7 ones. Like the metric system, our number system is based on a conversion rate of 10 to 1. If you give me 10 ones, then that is worth 1 ten. If you give me 10 hundreds, then that is worth 1 thousand. And vice versa. But this is just a way of choosing to write numbers, it doesn't change the underlying math. Let us free our minds!

Once again, a change of perspective is helpful. Once you notice that 10 isn't so special, you reveal new ways of writing numbers. As most people know, computers prefer to work in base 2. This means 2 ones are worth 1 two, 2 twos are worth 1 four, 2 fours are worth 1 eight, and so on. The Babylonians used base 60. And so do we sometimes. For example, 60 seconds is 1 minute and 60 minutes is 1 hour. Octopii no doubt write their numbers in base 8.

Our usual number system is so deeply ingrained that it can be quite hard to even imagine doing math using a different base. Fortunately, James Tanton has given us an intuitive, visual, and delightful way to work with numbers which frees our mind from the tyranny of base 10. He calls it Exploding Dots. There is a sequence of boxes, read right to left, and an exchange rate to go between boxes. For example, the 1←2 Exploding Dots machine lets you move dots from right to left at the exchange rate of 2 to 1 (or left to right at the exchange rate of 1 to 2). When 2 dots are converted to 1, Tanton calls this Dot Explosion [2].

Screen Shot 2017-12-03 at 7.25.43 PM

Exploding Dots!

Given a number, you can convert it into its diagram by dumping that many dots into the right-most box, and then using as many Dot Explosions as you can to move them left. With a little practice, it becomes easy to draw the dot diagram for any number, regardless of the conversion rate, and, conversely, to read off a number from its dot diagram.

You can use Exploding Dot diagrams to add numbers. Just draw the two diagrams which represent the numbers, combine their dots box by box, and use dot explosions to simplify the result. Using anti-dots (which annihilate ordinary dots) you can do subtraction. Even more remarkably, you can just as easily do multiplication and division! If you think about it for a few minutes, you'll realize if you use 1←2 dot diagrams then you're doing base 2 math. If you use 1←10 dot diagrams, then you're doing base 10. If you use 1←8, then you're doing octopus math.

Screen Shot 2017-12-03 at 7.48.29 PM

The 3 to 2 Conversion.

Tanton's Exploding Dots gives us a new perspective. For example, what happens if you use a -1←10 conversion rate? The Exploding Dot diagrams work equally well as long as you remember that a negative stands for an anti-dot. This means 10 dots in the rightmost box now converts into 1 anti-dot in the second box, 10 dots in the second box will convert to 1 anti-dot in the third box, whereas 10 anti-dots in the second box will convert to 1 regular dot in the third box. Once you have that sorted, the Exploding Dot diagrams work like a charm. You can convert numbers into the diagrams, use them to add, subtract, multiply, and divide, and convert the result back into a number. You get the right answer, but what the heck is going on?

It sounds crazy, but the -1←10 Exploding Dot machine is doing math in base -10. In base 10, 2017 represents 2(1000) + 0(100) + 1(10) + 7(1) = 2(103) + 0(102) + 1(101) + 7(100). You could instead think to work in base -10. If you write numbers in this way, then 2017 represents 2((-10)3) + 0((-102) + 1((-10)1) + 7((-10)0)=2(-1000)+0(-100)+1(-10)+7 = -2003. There is nothing stopping you from doing this but cowardice and dullness of mind. Mathematics is equally happy in all bases.

How about a 2←3 conversion rate? What happens if you use Exploding Dot diagrams with this conversion rate? The short answer is that nothing happens! The diagrams continue to work beautifully. What the hell is going on? Astonishingly, you are doing math in base 3/2. It turns out that the diagrams and the math work equally well even with a rational number as a base. As we said, mathematics is equally happy in all bases!

Now that your mind has been freed, you should see if you can make sense of writing numbers in base π. Or what a 2←x means if x is a variable.

In the end, it's all about that base.

[1] Non-US readers can hardly pat themselves on the back. Things seem pretty dire all around. Besides, if the US is the steam-engine which often pulls us all forward, it can as easily be the anchor which pulls us all down.

[2] I'd call it Dot Implosion, but he's Australian, which probably has something to do with it :-).