Is the Square a Secure Polygon?

In this week's episode of PBS Infinite Series, I shared the following puzzle:

Consider a square in the xy-plane, and let A (an "assassin") and T (a "target") be two arbitrary-but-fixed points within the square. Suppose that the square behaves like a billiard table, so that any ray (a.k.a "shot") from the assassin will bounce off the sides of the square, with the angle of incidence equaling the angle of reflection. 
Puzzle: Is it possible to block any possible shot from A to T by placing a finite number of points in the square?

As I mention in the video, this is one of a number of billiard problems that folks studying dynamical systems have asked. It was mentioned in a 2014 lecture given by Maryam Mirzakhani, which you can watch in the video on the left! Maryam describes the puzzle but leaves the audience to think about the solution. And in that audience was category theorist Emily Riehl, who did indeed think about a solution on and off for a few weeks. (You can read Emily's reflection on her experience in this AMS tribute to Maryam.)

Fast forward to last fall, when I ran into Emily at a Women in Topology workshop at MSRI. During a bus ride up the hill to the MSRI campus, Emily suggested that the puzzle might be a good fit for Infinite Series. I couldn't agree more! The solution she shared with me is delightfully simple for what seems to be an incredibly complicated puzzle. It's the solution she believes Maryam intended the audience to find, and it's what I want to share with you today! In the video above, I set up some of the mathematics needed to work through the solution, so if you haven't watched it already, now would be a good time. In any case, I'll assume you're comfortable with the notions of flat tori, a tiling of the xy-plane with flat tori, and a lattice in the xy-plane.

Alright, let's get to it!

My sincerest thanks go to Emily Riehl for today's episode and blog post!

The Answer (SPOILER ALERT)...

The answer is YES. It is possible to place a finite number of points in the square that will block any possible shot from $A$ to $T$. Moreover, 16 points will suffice!

The Solution

Step #1: Transfer the problem to the xy-plane.

Billiard trajectories (i.e. zig-zags on a square) can be tricky to analyze, so to make things easier, we want to find a way to replace any biliard trajectory by a line in the plane. (Why? Because zig-zags are hard. Lines are easy!) Now anytime a mathematician mentions the words "square" and "trajectory" and "line" in the same sentence, there's a 99.2% chance that flat torus is involved! So the goal for the first step in the solution is to somehow (we'll see how in a bit) use a flat torus to transfer the puzzle from the billiard table to the $xy$-plane.
To start, I'll pick up where we left off in the video — let's draw the billiard table as a square whose edges are each a different color. This will remind us that unlike a flat torus, none of the sides of this square are identified. I'll also pick two arbitrary-but-fixed points in the square, labeled $A$ (assassin) and $T$ (target). To distinguish the points visually, I've drawn the assassin as a white dot and the target as a black dot.
square.jpg
Now even though this square billiard table is not a flat torus, we can make a flat torus by sticking four of these billiard tables together! How? First notice that the square can be reflected in four different ways (including the "empty reflection").
4square.jpg
Square #1 represents the original square (with no reflection), and I've labeled its edges by north, south, east, and west. Square #2 is obtained by reflecting square #1 across a horizontal axis, so that the north and south sides get swapped. Square #3 is obtained by reflecting square #1 across a vertical axis, so that the east and west sides get swapped. We can also perform these two reflections in succession to swap both north/south and east/west. That's square #4. To get a torus, simply assemble these four squares as shown below!
 
torus.jpg
 

Now we can tile the plane with that torus. (In math lingo one says, "We can pass to the universal cover of the torus.")

zoom_yellow.jpg

In what follows, I'll refer to that yellow square that you see (labeled with 1) as the "original square." We'll think of it as the original billiard table, while the other squares are the copies/reflected copies. 

Okay, we’ve transferred our target/assassin problem from a square to the plane. So any trajectory on the billiard table will correspond to a line segment in the plane! For example, the trajectory from the assassin to the target on the left-hand side below IS the line segment on the right-hand side! (Verify this for a good mental check!)

trajectory copy.jpg

So we've successfully moved the puzzle from a square to the plane. That was the first step.

Step #2: Observe that the problem involves lattices!

Until now I've omitted a detail, but now's a good time to point it out. In the very first graphic above, you see that I plopped two points $A$ and $T$ (white and black) on the original square. Since those points lie on the original square, they must lie on the reflected copies, too!
4square_dots.jpg

Therefore they also appear in the tiling of the plane!

 

While this may look pretty, it'll be more helpful if we focus on the assassin and the target in their respective squares, rather than all jumbled together. I've drawn this below. 

4planes.jpg
For the moment, let's only focus on what's happening with the copies of square #1. We've got a bunch of repeating black and white dots! The technical word for repeating dots is a lattice.

More formally: Given a point $(x,y)\in\mathbb{R}\times \mathbb{R}$, the lattice generated by $(x,y)$ is the set of points $\{(x,y)+(n,m)\;\vert\;n,m\in\mathbb{Z}\}$. In other words, start at $(x,y)$ and move $m$ units left/right and $n$ units up/down, where $m$ and $n$ range over all possible integers. The resulting collection of points is called a lattice, which is really just a translated copy of $\mathbb{Z}\times\mathbb{Z}$. (You can think of $\mathbb{Z}\times\mathbb{Z}$ as the lattice generated by $(0,0)$.)

In the previous graphic, we observed that the target in the original square generates a lattice, which we'll call Lattice #1. In the graphic below, I've done a little rescaling so that the set of black dots really is like $\mathbb{Z}\times\mathbb{Z}$, rather than $2\mathbb{Z}\times2\mathbb{Z}$. (i.e. so that the black dots really are spaced out by a factor of one, rather than a factor of two. This is what I'm referring to in the "small technicality alert" in the graphic below.)
Lattice1.jpg
Of course, a similar story holds for the assassin $A$ — it generates its own lattice, though I won't draw it because we won't need it! It'll suffice to consider the original assassin (the assassin in the original square) and not its copies. Also remember — we've only focused on square #1! We actually get more lattices because of the three other squares, and we'll focus on those generated by the target. So in addition to Lattice #1, let's call Lattice #2 the lattice generated by the target in square #2; Lattice #3 the lattice generated by the target in square #3; Lattice #4 the lattice generated by the target in square #4. Here are the pictures.
threeLattices.jpg
Woo! That's a lot of dots.

At this point, you might wonder why we're not worrying about the lattices generated by the assassin. Why represent the assassin as a single dot rather than as lattices, as we did with the target? The answer lies in the following observation: The original problem consists of two points $A$ and $T$ on a square billiard table, and so when we tile the plane with those cleverly-crafted flat tori,
trajectory2.jpg

This is the key! In fact, it bears repeating:

 

 Any shot from the assassin to the target in the original billiard table can be represented by a line segment in the plane that goes from the assassin in the original square to a copy of the target in one of the four lattices. 

 

So to solve the puzzle, let's make the following strategy.

 

STRATEGY:
To block any shot from the assassin to the target, we need to block any shot that can occur in each of the four lattices. 

 
Let's call this process protecting the lattice. To solve the puzzle, then, we first need to protect Lattice #1, then we need to protect Lattice #2, then we need to protect Lattice #3, and finally we need to protect Lattice #4.

Fortunately, this isn't as complicated as it seems! As we'll see below, once we figure out a way to protect Lattice #1, we'll be able to apply similar arguments to protect the remaining three lattices. In other words, if we can protect Lattice #1 using $k$ "security agents," then we may conclude that a total of $4k$ security agents are needed protect the full plane. That is, it will take a total of $4k$ security agents to block any shot from the assassin to the target! So what is this special integer $k$? Let's find out in the next steps.

Step 3: Protect Lattice #1

Here's a picture of Lattice #1 again. I've plotted the original assassin in the original square, circled below.

 
Lattice1 (new).jpg
 
To make things easier to visualize, let's introduce a new coordinate plane - one where the original assassin lies at the origin, like this:
Lattice1 (newest).jpg
I've drawn the new axes in dark blue to emphasize that this really is a new grid! Now suppose that the original target has coordinates $(a,b)$ in this plane. (I realize it looks like $(a,b)=(\frac{1}{2},\frac{1}{2})$, but that's only due to poor artistic planning. The target needn't be in the center of the blue squares!) Then the coordinates of the target in the other three squares nearest the origin are as shown below.
ab.jpg
And now we're getting really close! Remember, our goal is to block any shot from the assassin (the origin) to the target (the dots). So naturally, we want block those four closest shots, right? So let’s place a "security agent" — indicated by a red dot and labled with $B_1, B_2, B_3,$ and $B_4$ — in between the assassin and the target in each of the four closest squares. Where exactly? How about the midpoint! It's the easiest thing we can try. Plus, we can write down exact coordinates for the agents!
blockers.jpg
Moreover, each point $B_1,B_2,B_3,B_4$ generates its OWN lattice! And the idea is that $B_1$ (and its copies), for instance, could potentially block other shots, too — those that come from all angles that might have bounced off the walls several times, but haven’t yet hit the target. I won't draw the pictures for these lattices, but the idea comes in handy soon, so be sure to keep it in mind!

In any case, we've certainly blocked the four closest shots from the assassin to the target. But what about ANY shot? How many more agents do we need? I claim the answer is zero. ZERO! In other words — and this is really amazing — the claim is that $B_1,B_2,B_3,B_4$ will block any shot from the assassin to the target, not just the four closest shots! It only takes FOUR agents to protect Lattice #1!

Observing why this is true is the final step.

Step #4: Make the final observation!

The goal in this step is to show that ANY trajectory from the assassin (origin) to the target (one of the dots) in Lattice #1 must intersect one of the points in the lattice generated by either $B_1$, $B_2$, $B_3$, or $B_4$.

Here's the proof of that claim.

Consider an arbitrary shot from the assassin to the target. On the plane, this corresponds to a straight line segment from the origin to a point of the form $(a+m,b+n)$ for some integers $m$ and $n$. To block this shot, let's place a new point $B$ at the midpoint of that line segment. Thus $B$ has coordinates $(\frac{a+m}{2} , \frac{b+n}{2})$.
 
Block1(final).jpg
 
Now here's the punchline! Depending on the parity of $m$ and $n$, the point $B$ is REALLY a copy of either $B_1$ or $B_2$ or $B_3$ or $B_4$!! In other words, this new security agent $B$ isn't so new after all! It lies in the lattice generated by one of the four blockers already chosen! Indeed:
 
punchline.jpg
 

For example, $m=1$ and $n=2$ in the illustration above. This puts us in case 4, so that $B=(\frac{a-1}{2},\frac{b+2}{2})$ is a point in the lattice generated by $B_2$. And this agent blocks that particular trajectory that we saw earlier! Indeed, notice that in the middle graphic below, the target is in one of the squares labeled 1, which guarantees it's a point in Lattice #1. Moreover, we can get to that square by starting at the original square, then moving up by two squares labeled 1 (this corresponds to $n=2$) and then moving right by one square labeled 1 (this corresponds to $m=1$).

FINAL.jpg
BINGO! Once we place the first four security agents down, we automatically block any other shot in the first lattice. It takes just four agents to protect Lattice #1! (So that special integer $k$ we were looking for earlier is $k=4$.) And what's great is that the argument we used to protect Lattice #1 works for any lattice! In particular, this means we can protect Lattice #2, Lattice #3, and Lattice #4 using just four agents each! Therefore we need a total of $$4\times 4 = 16$$ agents to secure the square!

Conclusion? The square is a secure polygon!

Food for thought

I didn't draw the lattices generated by the agents, but you might have a bit of fun doing this — see where they lie on the original plane (the one with all the colors) and convince yourself that every shot the assassin takes really is blocked! Also, we showed that 16 points will suffice, but could fewer than 16 work, depending on where the assassin and target are located? (For example, if the target is in the center of the billiard table, then you only get one lattice rather than four.)

You might also wonder about other (regular) polygons. Today we saw that the square is secure. But what about triangles? Pentagons? Hexagons? For which $n$ is an $n$-gon a secure polygon? I'll leave you to ponder the answers.

Until next time!

crumbs!

 
Screen Shot 2017-10-13 at 7.29.07 PM.png
 
 

One day while doing a computation on the board in front of my students,
I accidentally wrote 1 + 1 = 1. (No idea why.)

 

Student: Um, don't you mean 1 + 1 = 2?

Me (embarrassed): Oh right, thanks.
[Erases mistake. Pauses.]
Wait. Is there a universe in which 1 + 1 = 1?

Class: ... [Stares blankly]

Me: That's not such a strange question. Don't you know that YOU live in a world where 11 + 1 = 0?

Class:... [Jaws drop.]

Me: Yeah! Think about it! 12 = 0 and 13 = 1 and 14 = 2 and 15 = 3... sound familiar?

Class: Military time!

Me: Exactly! [Points to clock on the wall and starts impromptu lesson on modular arithmetic.]

 
 

I hope at least one student was convinced that math is cool.

'Cause I'm convinced that making mistakes isn't always a bad thing!

Limits and Colimits, Part 2 (Definitions)

Limits and Colimits, Part 2 (Definitions)

Welcome back to our mini-series on categorical limits and colimits! In Part 1 we gave an intuitive answer to the question, "What arelimits and colimits?" As we saw then, there are two main ways that mathematicians construct new objects from a collection of given objects: 1) take a "sub-collection," contingent on some condition or 2) "glue" things together. The first construction is usually a limit, the second is usually a colimit. Of course, this might've left the reader wondering, "Okay... but what are we taking the (co)limit of?" The answer? A diagram. And as we saw a couple of weeks ago, a diagram is really a functor.

Read More

Brouwer's Fixed Point Theorem (Proof)

Brouwer's Fixed Point Theorem (Proof)

Today I'd like to talk about Brouwer's Fixed Point Theorem. Literally! It's the subject of this week's episode on PBS Infinite Series. Brouwer's Fixed Point Theorem is a result from topology that says no matter how you stretch, twist, morph, or deform a disc (so long as you don't tear it), there's always one point that ends up in its original location.

Read More

A Diagram is a Functor

Last week was the start of a mini-series on limits and colimits in category theory. We began by answering a few basic questions, including, "What ARE (co)limits?" In short, they are a way to construct new mathematical objects from old ones. For more on this non-technical answer, be sure to check out Limits and Colimits, Part 1. Towards the end of that post, I mentioned that (co)limits aren't really related to limits of sequences in topology and analysis (but see here). There is, however, one similarity. In analysis, we ask for the limit of a sequence. In category theory, we also ask for the (co)limit OF something. But if that "something" is not a sequence, then what is it?Answer: a diagram.

Read More

Limits and Colimits, Part 1 (Introduction)

Limits and Colimits, Part 1 (Introduction)

I'd like to embark on yet another mini-series here on the blog. The topic this time? Limits and colimits in category theory! But even if you're not familiar with category theory, I do hope you'll keep reading. Today's post is just an informal, non-technical introduction. And regardless of your categorical background, you've certainly come across many examples of limits and colimits, perhaps without knowing it! They appear everywhere - in topology, set theory, group theory, ring theory, linear algebra, differential geometry, number theory, algebraic geometry. The list goes on. But before diving in, I'd like to start off by answering a few basic questions.

Read More

Topology vs. "A Topology" (cont.)

Topology vs. "A Topology" (cont.)

This blog post is a continuation of today's episode on PBS Infinite Series, "Topology vs. 'a' Topology." My hope is that this episode and post will be helpful to anyone who's heard of topology and thought, "Hey! This sounds cool!" then picked up a book (or asked Google) to learn more, only to find those formidable three axioms of 'a topology' that, admittedly, do not sound cool.

But it turns out those axioms are what's "under the hood" of the whole topological business! So without further ado, let's pick up where we left off in the video.

Read More

Multiplying Non-Numbers

Multiplying Non-Numbers

In last last week's episode of PBS Infinite Series, we talked about different flavors of multiplication (like associativity and commutativity) to think about when multiplying things that aren't numbers. My examples of multiplying non-numbers were vectors and matrices, which come from the land of algebra. Today I'd like to highlight another example:

We can multiply shapes!

Read More

What is an Operad? Part 2

What is an Operad? Part 2

Last week we introduced the definition of an operad: it's a sequence of sets or vector spaces or topological spaces or most anything you like (whose elements we think of as abstract operations), together with composition maps and a way to permute the inputs using symmetric groups. We also defined an algebra over an operad, which a way to realize each abstract operation as an actualoperation. Now it's time for some examples!

Read More

What is an Operad? Part 1

What is an Operad? Part 1

If you browse through the research of your local algebraist, homotopy theorist, algebraic topologist or―well, anyone whose research involves an operation of some type, you might come across the word "operad." But what are operads? And what are they good for? Loosely speaking, operads―which come in a wide variety of types―keep track of various "flavors" of operations.

Read More