How Quickly Can You Fill Up a Circle?

This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American

Michael Boshernitzan, a math professor at my graduate school alma mater, Rice University, passed away last week. I took one class with him, but he had a larger impact in my life as my spouse Jon Chaika’s advisor. They had a wonderful advisor-student relationship, and I know Jon especially appreciated Michael's keen eye for interesting math questions and limitless enthusiasm for math. (It feels odd for me to refer to my husband as Chaika instead of Jon. But it also feels odd to refer to one person in a post by first name and one by last name or to refer to both by first name. With no non-odd options available, I will refer to them as Michael and Jon.)

After hearing the sad news, I found myself browsing his papers on the arXiv and decided to click on “The densest sequence in the unit circle,” which he and Jon cowrote a decade ago. The paper is only two pages long, and it’s kind of fun.

The title of their paper refers to the unit circle, which is usually defined to be the circle with radius 1, but the unit circle they are actually using is the circle with a circumference of 1 (hence a radius of 1/π). The distinction doesn’t really matter—they could multiply things by π as needed to ship their work over to the standard unit circle—but this fact can help us understand part of how they did their work. (Usually when mathematicians refer to a circle, we are referring to a hollow circle, not a filled-in circle, which we would call a disc. Unfortunately, we are often sloppy about this usage, saying things like "the area of a circle is πr²." The area of a circle is 0 because a circle is 1-dimensional, not 2-dimensional. The length of a circle is 2πr, and the area of a disc is πr².)

On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

One way to think of a circle is as an interval with its two ends glued together, in this case an interval with length 1. Doing arithmetic on this interval involves thinking about the “fractional part” of the numbers involved. The fractional part of a real number is what you get when you chop off anything to the left of the decimal point. The fractional part of 1.5 is 0.5, the fractional part of π is .14159…, the fractional part of 5 is 0. (As the π example shows, a number’s fractional part isn’t necessarily a fraction.) In the paper, Michael and Jon denote the fractional part of a number x by x (mod 1). 

Working with the fractional parts of numbers makes it easy to see the relationship between the number line and the circle and understand a big part of the paper: answering a question about points on the circle by doing arithmetic on the real number line. Dealing with fractional parts only, we can think about a number line being a bunch of intervals chopped up and stacked on top of each other, or better yet, as being wrapped around a circle infinitely many times.

Michael and Jon were looking for the densest way to fill up a circle with an infinite sequence of points. The only problem is it’s not obvious how to measure the density of a set of zero-dimensional points in a one-dimensional line. Part of the work in the paper, in fact, was to figure out a sensible ways to measure the property they were after.

The traditional definition of density for sets within the number line is that a set is dense if every small interval contains points in the set. Rational numbers are dense because any interval, no matter how small its length, contains at least one rational number. This notion of density is binary: a set is either dense or it is not. Many, many sequences of numbers in the circle (viewed as fractional parts of real numbers) are dense in this sense. For example, a sequence obtained by adding the same irrational number to the previous term over and over (and taking the fractional part of the answer) is dense in the circle. Eventually, some term of the sequence will hit any tiny interval in the circle. Adding a rational number over and over, on the other hand, is not dense because eventually you will be repeating the same number. For example, the sequence 0, 1/2, 1/2, 3/4, 0, 1/4, 1/2, 3/4,… only hits the same four numbers.

Many sequences are dense in this sense, but is there a way to quantify how quickly and effectively a sequence fills in the circle? Those are the notions Michael and Jon zeroed in on. They came up with two measures and a sequence that optimizes both of them to a certain extent.

The first measure is labeled D_n in the paper and measures the farthest away any point of the circle can be from the nearest point in the first n terms of the sequence. An example helps: Let’s pick a simple sequence, the sequence where the nth term is the number n/3 (mod 1). Starting at 0, this sequence goes 0, 1/3, 2/3, 0, 1/3, 2/3, and so on, just marching along the circle taking steps with length 1/3. After n=3, the density D_n stabilizes. The points 1/6, 1/2, and 5/6 are all halfway in between two of the points of the sequence, and they have distance 1/6 from the nearest point. Any other point on the circle is closer to a sequence point. So D_n is 1/6 for any n greater than or equal to 3. Calculating D_n for a more complicated sequence than 0, 1/3, 2/3 is of course going to be more challenging, but the big idea is that this measure keeps track of how badly the sequence misses hitting every point in the unit interval at the nth step for each n.

The other measure they used is called d_n (if you’re reading this post out loud, I’d recommend shouting D_n  and whispering d_n to help keep them straight in your mind), and it keeps track of how close the closest points of the sequence are to each other. In the case of 0, 1/3, 2/3, the closest points have distance 1/3 from each other, so d_n for that sequence is 1/3. This notion might be better thought of as sprawl than density: A sequence with large values of d_n is a sequence where each new term is pretty far from the previous terms.

The goal of the paper is to find a sequence that does a good job with both D_n and d_n. That means small values of D_n—the sequence is getting close to all the points in the circle—and large values of d_n—each new term of the sequence is pretty far from all the previous terms.

The winning sequence Michael and Jon found is actually not too hard to understand. It’s log₂(2k−1) (mod 1) with k=1, 2, 3, and so on. The function log₂(x) is the base 2 logarithm of x, the number to which 2 must be raised to get x; for example, 2³=8, so log₂(8)=3. Plugging in a few numbers, you can see that the sequence from the paper is the sequence of the fractional parts of the base 2 logarithms of odd whole numbers. That's a mouthful, but it's not hard to start plugging in numbers on an online calculator to get a feel for the beginning of the sequence. For small values of k, the fractional part of the base 2 logarithm of k moves around a lot. For large values of k, the sequence terms eventually get close together. (Try plugging in some 5- or 6-digit numbers for k and see how little the sequence moves from one term to the next.)

In their paper, Michael and Jon showed that the sequence of base 2 logs of odd numbers does a good job of both getting close to all the points in the circle and keeping the minimum distance between points of the sequence on the large side of what is possible. In particular, they show that competitor sequences may sometimes beat their sequence, but their sequence will win infinitely often. In fact, as n increases, their sequence gets winning-er and winning-er over all competitors.

This is not an earth-shattering paper, but I decided to dig into it because it was bite-sized and accessible to me, unlike some of his deeper work. It also fit the way I perceived Michael as a mathematician, though of course my perception was from a distance; I never worked with him. He liked asking and answering questions that were perfectly natural but no one had thought to ask before. While it took some elbow grease to set up in this blog post, the basic premise of the question would probably be straightforward to a math graduate student who had taken an introductory analysis class. Michael also loved clever, efficient arguments. After the basic terms are defined in this paper, the proofs of the two theorems only takes about half a page and doesn't require heavy mathematical machinery so much as astute observations about sequences and intervals. Math doesn't have to be earth-shattering to be worth thinking about, and I'm glad I spent some time thinking about this problem.