The Kakeya Problem

Originally developed as a lesson for high school students at Emory Math Circle and taught in September 2022.

Overview

In this lesson, we will introduce students to the Kakeya conjecture through exploration. For the warmup, students will think about the classical Kakeya problem: finding the smallest possible region in the plane through which we can sweep a unit length needle 180 degrees. Then we will think about a generalization of this problem to n by n grids. Students will have to figure out what a “line” is in this context, what possible slopes they can have, and then reason about Kakeya sets --- sets of points which contain a line of each possible slope --- in this new context.

Objectives and transferable skills

• Kakeya sets: students will find Kakeya sets in the real plane and over finite fields.
• Geometric reasoning: students will develop an intuition for lines and slopes in the context of an n by n grid.
• Observation and conjecture: students will practice making observations, formulating conjectures, and testing them by studying further examples.

Resources and supplies

• Warmup worksheet (easily done on the board without printing out)
• Activity worksheet
• Whiteboards for students to easily draw and erase (or extra scrap paper).

Warmup

Let's say we have a needle of length 1 sitting in the plane. Our goal is to rotate the needle a full 180 degrees, using any continuous motion in the plane --- like translation or rotation from any fixed point.

This is too easy if we're allowed to use the whole plane! Let's constrain ourselves by requiring that we start with the needle inside some region, and all our rotation and translation has to stay within that region.

Goal: minimize the area of this region.

This is still pretty easy if we take our region to be a "big" rectangle (where big is relative to the length of the needle), as shown on the warmup worksheet. As a warmup, try to make the region as small as possible, in terms of its area! As you do, think about the following questions:

• What properties does your smallest (so far at least!) region have? Is it convex or concave?
• How much "wiggle room" do you seem to have on your needle's path? If you have some, can you use that to eliminate some area?
• Lines have slopes. Which slopes does our needle (i.e. line segment) take on as we continuously rotate it around in the plane?

If we can turn our needle all the way around, we hit every possible slope! Kakeya was originally interested in region in the (real Euclidean) plane with the property that they contained a unit length line segment of every slope (including vertical). Kakeya also thought he found the smallest area such region, drawn at the top of this post --- but there turn out to be smaller ones! This is the topic for another time, but look up Besicovitch needle sets if you are interested in learning more. Instead, we're going to turn to a different version of the problem.

Kakeya sets on grids

Consider an n x n grid, like the 3 x 3 and 5 x 5 ones on the worksheet. What is a line in this setting? What slopes can a line have? It might help to think about what characteristics lines usually have, and how we can carry those over to our setting.

I think it's easiest to characterize a line by a point and a direction. Or, we can think of a line as joining two points, which implicitly defines a notion of direction/slope. Thinking along these lines (ha!), we can join any two points in our grid by a line! Some of these are sort of obvious, like the vertical and horizontal ones below.

Others are more subtle! What if we join the points (0,0) and (2,1), which has a slope of 1/2. Unlike the lines above, it only passes two points on our grid. But if we extend the grid, we see it also passes through (4,2); shifting this point to the left by 3, back onto our original square, we get the point (1,2), giving us the green "line" below.

It's more straightforward to think of the line just as the collection of grid points, in this case \(\{(0,0), (2,1), (1,2)\}\). What's really going on is that we are looking at lines in the plane of integers modulo 3. This is why it makes some amount of sense to identify (4,2) with (1,2), and why our lines don't always look like the ones we are used to.

A Kakeya set is a subset of the plane that contains all possible slopes. In the n x n grid setting, it is a subset of points that contains at least one line of every slope. As in the warmup, our challenge is to find the smallest Kakeya set --- this time we measure size by number of points, rather than area.

Questions

(See also the worksheet.)

1. Convince yourself that the notion of "lines" above makes sense! Draw some examples.
2. Do you notice anything fishy? More precisely, can you find any examples of lines that turn out to be the same? (Hint: try finding another line that contains the same three points as the green line above, but without starting with (0,0) and (2,1).)
3. How many possible slopes of lines on the 3 x 3 grid are there?
4. What is the smallest Kakeya set you can find on the 3 x 3 grid? Can you prove that your answer is the best possible?

Challenge questions

1. Repeat all the questions above, but with a 5 x 5 grid.
2. Repeat all the questions above, but with a 4 x 4 grid. What is different here?
3. Using all of your observations so far, what can you say about this problem on an n x n grid?
4. How could we generalize this problem to n x n x n cubes?

Discussion

Spoiler alert! Below I'll share some answers and insight about the questions above. Try them on your own first, before reading ahead, and proceed only if you're stuck or ready to check your answers and reasoning.

Show/hide question 1 Show/hide question 2 Show/hide question 3 Show/hide question 4

Instructor notes

I was originally inspired to write this lesson by a graduate student seminar talk on the Kakeya problem. The first time I taught it was for our advanced high school math circle, and it was fun because of the open-endedness: I gave the students time to think on their own and explore what the most reasonable definition of "line" and "slope" should be, before having us settle on the one I outline above.

Depending on how much or little the students know about modular arithmetic and finite fields --- and how much time is available --- when I teach this lesson again, I will probably either (a) just define the lines on the grid as above or (b) give the students more time to explore this and make their own definitions. Even with the definition given, there's a lot to explore, such as when two lines that a priori are different happen to coincide (Question 2 above).