The Roots of Unity

Two primal pleasures from my years of childhood (and maybe my years of infancy too, though how would I know?) are feelings I’ll call coziness and spaciousness. The first is the feeling I’d get at night pulling the blankets up over my head; the second is the feeling I’d get standing on a beach staring out at the ocean. These pleasures seem like opposites, but sometimes you can have both at once — for instance, when beneath those blankets you have a flashlight and a book full of magic and adventure. I’ve learned that the adventure called mathematics has its own ways of combining the love of the large with the delight of the small, and I’m going to tell you about one of my favorite combinations of these two opposite pleasures: the roots of unity.

WORLDS IN GRAINS OF SAND

In the tidy world of modular arithmetic, if you count too high you return to zero, like the fabled fisherman and his wife whose riches increase until at the end they wind up back where they started. We all should probably say “modular arithmetics” (with a final “s”) since there are many of these systems (infinitely many, in fact!), but I’ve never heard anybody use the phrase in the plural. For each positive integer n, called the modulus, there’s an arithmetic with the bizarre property that if you count up to n, you just land back at 0. Here’s what the table for addition looks like when n=4 (“mod 4 arithmetic”):

Here 1 plus 1 is 2 as in normal arithmetic, but 2 plus 2 is 0 and 3 plus 3 is 2.

Modular arithmetic might seem like an arcane game, but back before computers rescued bookkeepers from the error-prone drudgery of hand-calculation (shortly before putting most of them out of business altogether), mod 9 arithmetic, as embodied in the procedure of “casting out nines”, was a crucial way of checking one’s work for mistakes. And now that we have those computers, mod p arithmetic (where p is a huge prime), and relatedly the arithmetic of finite fields, are the cornerstone of cryptographic security for internet commerce.

A natural way to represent mod n arithmetic is to use a clock-face with n evenly spaced markings, running from 0 to n−1. Here for instance is a 12-hour clock, with the usual 12 replaced by the mathematically more sensible 0. To compute 8 plus 9 in mod 12 arithmetic, start at 8 o’clock and advance clockwise by 9 positions; you end up at 5 o’clock, so 8 plus 9 is 5 in mod 12 arithmetic.

When we want to talk about two different moduli at once, we can include subscripts on the plus-signs, asserting for instance that “8 +₁₂ 9 = 5″ and “8 +₁₀ 9 = 7″. More frequently, mathematicians write “8 + 9 ≡ 5 (mod 12)” and “8 + 9 ≡ 7 (mod 10)”. Either way, it’s important to understand that the different modular arithmetics aren’t in conflict, even if they might seem to contradict one another if we leave out the subscripts or the parenthesized context-indicators. You can view them as mutually parallel microworlds, little pocket universes of Number. If I were an artist I’d draw a picture of a child blowing an infinite cascade of ever-larger bubbles, representing mod-2 arithmetic, mod-3 arithmetic, mod-4 arithmetic, and so on — something like

but with a child creating those arithmetics by blowing through a glowing circular wand.

A fun puzzle involving modular arithmetic is Lights Out. The classic version is mod 2, but Christian Lawson-Perfect’s implementation allows you to use any modulus between 2 and 10. When you click on a square, its intensity (represented by a number between 0 and n−1) advances by 1 or jumps back down to 0 if it was n−1. At the start of the puzzle all the lights are off, which means the puzzle is solved, so you could stop there but that’s not very much fun. To make things interesting, click a few squares at random to turn lights on to various brightness levels, scrambling things up, and now try to click squares strategically to get all the lights off again. There’s always a way to do it (see Endnote #3). But suppose the initial intensity levels were set randomly. Is there always a way to turn all the lights out? If not, is there a way to do it when it can be done, and to recognize when it can’t? The key to answering these questions is a knowledge of modular arithmetic (see the article by Giffen and Parker in the References).

ESCAPING THE LINE

Most of you have probably seen the number line:

It’s a sensational tool for making sense of numbers, and here I’m using the word “sensational” quite literally. By bringing our visual (and, in the best classrooms, kinesthetic) sense to bear on the number-concept, the number line gives us a way to put −3 and 1/2 and 1.7 into a unified framework. But there’s no mathematical reason to put positive numbers on the right and negative numbers on the left. For that matter, there’s no mathematical reason for the number line to be horizontal. A vertical line would do just as well, with the positive numbers above 0 and the negative numbers below, and this convention is more intuitive for applications like measuring altitude.

One of the most profound mathematical revolutions of the past five hundred years is the introduction and domestication of complex numbers. These are number-like mathematical beasts that don’t fit anywhere on the number line, being neither positive nor negative nor zero. Such paradoxical numbers were dismissed and resisted for a long time, but they eventually proved their worth in many branches of science, from biomechanics to electrical engineering, and they’ve transformed pure mathematics in countless ways. The most famous of these new numbers is i, the square root of −1. It’s nowhere to be found on the number line; to make it “sensible”, we need to break the bonds of 1 dimension and replace the number line by a 2-dimensional number plane. i is by convention placed one unit above the real number 0, and its twin −i is placed one unit below. All the points in the plane correspond to numbers; for instance, the point 3 units above the real number 2 is the complex number 2+3i. The plane is transformed: where Euclid saw it as full of points, we can see it as full of numbers, stretching out in every direction as far the eye can see. Mathematicians call the set of complex numbers ℂ, and like to envision it as a plane in this way.

But again, I want to point out that there’s nothing mathematically necessary about the convention of using a horizontal line for the real numbers and a vertical line for the imaginary numbers, and in a way the standard convention represents a missed opportunity. One of the pillars of the theory of complex numbers is the operation that swaps +i with −i, and correspondingly swaps each complex number a+bi with its mirror-twin a−bi. Meanwhile, the natural world at human-scale is deeply symmetrical between right and left. It would be lovely if the symmetry between right and left matched up with the symmetry between +i and −i, with a version of the complex plane that looked like this:

As far as I know, nobody has advocated this alternative picture of the complex numbers with a vertical axis of bilateral symmetry, so for now, we’ll stick with the standard picture of ℂ. (But don’t forget this alternative picture; I’ll come back to it at the end.)

Interestingly, mathematicians have no special symbol for the set of imaginary numbers. That’s because the imaginary numbers, taken by themselves, don’t form a rich number system; you can add and subtract them, but you can’t multiply and divide them without leaving the set of imaginary numbers.

THE ROOTS OF UNITY

The complex number i satisfies the equation x⁴ = 1 (check it: i⁴ = (i²)² = (−1)² = 1), as does its twin, the complex number −i; for that matter, so do the numbers 1 and −1 (which have dual citizenship in both the real numbers and the complex numbers). These four complex numbers, taken together, are all the solutions to x⁴ = 1 in ℂ. We call them the four 4th roots of 1. They form a square, and it’s no coincidence — for every n > 2, there are exactly n solutions to the equation xⁿ = 1 in ℂ, and they form the vertices of a regular n-gon centered at 0, with the vertices evenly spaced around the circle of radius 1. (See Endnote #4 for an explicit formula for the nth roots of 1.)

For example, the complex number (1/2) + (sqrt(3)/2) i is a 6th root of 1, and if you take its powers, you get all six 6th roots of 1.

On the other hand, the complex number (sqrt(2)/2) + (sqrt(2)/2) i is an 8th root of 1, and if you take its powers, you get all eight 8th roots of 1.

In this setting, it’s common to refer to 1 as “unity” (which has always sounded a bit metaphysical to me, but that’s what everyone calls the number 1 when they talk about its complex roots).

Here’s a puzzle that I think was originally invented by me (but if you think otherwise please let me know): Given a circle of 12 lights, exactly one of which is initially on, it is permitted to change the state of a bulb provided that one also changes the state of every dth bulb after it (where d is some divisor of 12 other than 12 itself), provided that all 12/d bulbs were originally in the same state as one another. Is it possible to turn all the bulbs on by making a sequence of moves of this kind? See Christian Lawson-Perfect’s neat implementation.

You won’t be surprised to learn that this puzzle has a cute analysis involving complex numbers (hinging on the fact that the n nth roots of 1 add to 0 in the complex plane), but there is another way to analyze it using physical reasoning. See Endnote #5.

THE CONNECTION

To see how modular arithmetic hides inside the complex numbers, think about the sequence i⁰, i¹, i², i³, i⁴, i⁵, etc. It goes 1, i, −1, −i, 1, i, etc., repeating forever. The fact that i³ times i³ equals i² in the complex numbers corresponds in a very precise way to the fact that 3 plus 3 equals 2 in mod-4 arithmetic.

For the price of replacing addition by multiplication, we can create a model of mod n arithmetic whose elements are not the ordinary integers 0, 1, 2, …, n−1 but the complex numbers ζ⁰, ζ¹, ζ², …, ζⁿ⁻¹, where ζ is a primitive nth root of unity (that is, an nth root of unity that isn’t a 1st, 2nd, 3rd, …, or (n−1)st root of unity). Here’s how the correspondence looks for n=4:

What I like about this correspondence is the way in which the unit circle in the complex plane serves as a common ground for all the different modular arithmetics. In our child-blowing-bubbles picture, the modular arithmetics were seen as separate things; now we see that if they’re suitably re-interpreted, they cohabit quite intimately.

THE MORAL

Look at what’s happened here. We’ve learned that there’s a place (namely the complex plane) where all our modular arithmetics can coexist. What’s more, we’ve seen that the small-is-beautiful philosophy (“There are too many counting numbers; let’s get rid of most of them”) and the bigger-is-better philosophy (“There are too few real numbers; if −1 doesn’t have a square root, let’s invent one!”) meet in the construction of the set of complex roots of unity.

Might the roots of unity be a prototype for the ways in which two opposed tendencies, properly understood, sometimes aren’t in conflict after all? Might the roots of unity also symbolize the way in which systems that seem disjoint (like those bubbles of modular arithmetic) sometimes, after a shift of context, turn out to fit together in unforeseeably beautiful ways?

Mathematics can reconcile seemingly opposed truths, not just holding them in tension but joining them together in harmony. Can this kind of harmonious coexistence prevail in other domains? Might the roots of unity be a model for situations in which people who seem to be saying irreconcilable things about one and the same subject are actually talking about two different things? Can math serve as, if not a root of unity, at least a path to unity?

Let me be so brash as to propose that we make the roots of unity a visual emblem for the ways in which this reconciliation can take place not just in the pristine world of mathematics but also, just maybe, in the real world.

What should our emblem look like?

There are infinitely many roots of unity, densely occupying the unit circle in the complex plane, but we don’t want our emblem to be just a circle, so let’s call special attention to the simplest roots of unity: say the 1st, 2nd, and 3rd roots of unity. Let’s highlight those complex numbers by joining them to the center of the unit circle, the number 0. And while we’re at it, let’s adopt the symmetrical, “alternative” picture of the complex numbers I mentioned earlier, putting 1 above 0 (instead of to its right), and −1 below 0 (instead of to its left). Here’s what we get:

I propose this logo not just as a symbol of reconciliation, but also as a symbol of equity and generosity: it’s the visual manifestation of “My friend and I were going to split this pizza two ways, but you look hungry; pull up a chair, and my friend and I will each share with you some of what we have.”

And if this you’ve seen this logo before, or something that looks a lot like it, well, now you know its hidden mathematical meaning!

Next month: On Size, Death, and Dinosaurs.

Thanks to Henry Baker, Sandi Gubin, Evelyn Lamb, Christian Lawson-Perfect, Henri Picciotto, and Francis Su.

ENDNOTES

#1. When I was in college, I fantasized about writing a science fiction trilogy whose three constituent novels would all have mathematically evocative titles: “The Higher Powers”, “The Identity Matrix”, and “The Roots of Unity”. But I never got beyond coming up with the titles and sketching in my mind’s eye the cover-art for the paperback edition.

#2. Mod n is different from base n. For instance, in base 2, 1 plus 1 is written as 10, but it’s just a different way of writing the ordinary number two, while in mod 2, 1 plus 1 is zero.

#3. Suppose the Lights Out puzzle (with n intensity levels) started with all lights out, and some moves were made. Then you can undo that succession of moves by doing them all in reverse order, repeating each move n−1 times.

#4. The n nth roots of 1 can be written in the form (cos (2πk/n)) + (sin (2πk/n)) i, where k takes the values 0 through n−1.

#5. The puzzle cannot be solved. One way to see this is to look at the sum S of the 12th roots of unity that correspond to the lights that are on at any moment. Initially, there’s only one light on, so S is some non-zero complex number (one of the 12th roots of unity). In the final configuration, we want all 12 lights to be on, so the sum S needs to become 0 (the sum of all of the 12th roots of 1). But now we notice that every time we turn lights on or off, we don’t change the value of S! That’s because we’re always adding or subtracting a bunch of roots of unity that, being symmetrically arranged around 0, must add up to 0. For instance, say we turn on lights 1, 5, and 9. Then we’re increasing S by ζ¹ + ζ⁵ + ζ⁹, where ζ is a primitive 12th root of 1. But ζ¹ + ζ⁵ + ζ⁹ = ζ (1 + ζ⁴ + ζ⁸); the parenthetical expression is the sum of the 3rd roots of 1, so it equals 0, which implies that ζ¹ + ζ⁵ + ζ⁹ = 0.

A different way to think about the puzzle, without using complex numbers, it is to look at the center of mass of the lights that are on, and to run the process backwards, from finish to start. At the start of the time-reversed puzzle, when all the lights are on, the center of mass of the lights that are on is at the center of the circle (call this point O). When we turn some of the lights on or off, the lights that are being flipped from on to off or vice versa always form a polygon whose center of mass is at O, so after the flip, the center of mass, which formerly was at O, is still at O. So no matter how many flips we do, we can never reach a configuration in which the center of mass of the turned-on lights isn’t at O, such as in particular a configuration in which exactly one light is on.

In the version of the puzzle that I’ve seen (see for instance page 93 of Andrescu and Gelca’s book), the number of lights is an arbitrary positive integer n (not necessarily 12), but the same reasoning applies.

It’s natural to ask (leaving aside the trivial case n=1) whether every configuration in which the center of mass of the turned-on lights is at O is accessible from every other configuration of this kind. I don’t know the answer, but maybe one of you can tell me.

#6. The real origin of the peace sign, alas, has nothing to do with the roots of unity; I believe the Wikipedia entry on peace symbols offers a trustworthy account. In the standard version of the symbol, the two arms make a 45 degree angle with the vertical arm (leg?), rather than a 60 degree angle. But if you use Google Images you’ll see that there’s some variety. I favor the more generously proportioned version, because it represents a fair way to split a circle three ways, thereby connoting justice as well as peace.

Given an ordinary round pizza, how many straight cuts of the usual kind (from the center of the pizza to a point on the edge) do you need to make in advance if you want to be able to share the pizza equitably among all the guests at your party, if all you know is that the number of guests will be somewhere between 1 and n? For instance, when n is 3, the roots-of-unity logo shows that it can be done with four cuts, and it’s easy to see that three cuts won’t do the job. This question is equivalent to the question “What’s the smallest number of pieces of a cake such that the pieces can be distributed equally among k guests for any k=1,2,…,n?”; the answer is known for all n up to 8. See the Online Encyclopedia of Integer Sequences entry for sequence A265286.

#7. The fancy way to relate mod n arithmetic with the complex plane is by way of the function that sends each real number x to the complex number (cos 2πx) + (sin 2πx) i on the unit circle. As an intermediate step, I like to imagine the real number line coiled up into a “number helix”; when you view it from the side it looks like a sine wave, but when you view it from above it looks like a circle, and the infinitely many integer points on the number line get smooshed down to just a finite collection of points on the unit circle: the nth roots of unity.

REFERENCES

Titu Andrescu and Razvan Gelca’s book “Mathematical Olympiad Challenges” contains a statement of the circle-of-lights puzzle, but I do not know who originated this particular Olympiad problem. You can also see the problem (with a hint and a solution) online in Miguel Lerma’s notes on solving mathematical problems by using complex numbers.

Martin Gardner’s essay “Imaginary Numbers” (an early version of which appeared in Scientific American in 1979, and which was published as chapter 17 of Fractal Music, Hypercards, and More) is a great source of information on imaginary numbers. Among other things, it addresses the common question “What about three-dimensional numbers, and four-dimensional numbers, and so on?”

Geogebra has a web-page that lets you play with roots of unity: https://www.geogebra.org/m/N7HBg9Zb

Alexander Giffen and Darren Parker analyzed mod n Lights Out in the following article: On Generalizing the “Lights Out” Game and a Generalization of Parity Domination. Ars Combinatoria, vol. 111 (2013), pp. 273-288.

Evelyn Lamb runs a Scientific American blog called “The Roots of Unity”, and if you aren’t a regular reader of it, you should be! Check out for instance her essay “What are roots of unity?”

Christian Lawson-Perfect has created web-versions of both the mod n Lights Out puzzle on a square grid and the lights-in-a-circle puzzle. Check out http://somethingorotherwhatever.com/lights-modular-out/ and http://somethingorotherwhatever.com/circular-lights-out/ respectively.

Paul Nahin’s book “An Imaginary Tale: The Story of Sqrt(−1)” gives a scholarly yet readable account of how imaginary and complex numbers were discovered.

Henri Picciotto has a couple of good pages about complex numbers: https://www.mathedpage.org/kinesthetics/complex.html gives a kinesthetic justification of the (traditional) location of the square root of -1, and https://www.mathedpage.org/alg-2/complex/  describes various complex number arithmetic games in GeoGebra that are available online.

Grant Sanderson has made many fine videos about math under the nom-d’ordinateur “3Blue1Brown”; if you want to see his take on the function that sends x to (cos 2πx) + (sin 2πx) i, check out his video “Euler’s formula with introductory group theory”.

Steve Wittens has created cool stuff on the complex numbers at acko.net. In particular, check out “How to Fold a Julia Fractal”. It’s about much more than folding Julia fractals; Wittens introduces complex numbers by way of their dynamics (that is, by way of questions like “What happens to α when we add β to it?” and “What happens to α when we multiply it by β?”, where α and β are complex numbers). He has a refreshingly down-to-earth take on things.