Monsky’s Theorem, or the genius of bizarre thinking

I was shown this by the illustrious Nir Avni, and it was so beautiful and bizarre that I presented it at our undergrad math seminar that week.  Now a friend of mine wants to turn it into art, and I’m writing it up in service of that lofty goal.  Kate, may your project join the slim annals of awesome math-themed visual art.

The question is: for what n can you cut a square into n triangles of equal area?  By slicing it into rectangles and cutting each rectangle into two triangles, it’s easy to see that you can get any even number, as the pictures below show.

So can you do it with an odd number of triangles?  Think about it a bit, and after the jump, we’ll think about it together.  (This post will be at a lower level than most of my other writing here — it should be understandable by math undergrads and ideally even the Laity.  Let me know how I’m doing!)

This problem was posed in the American Mathematical Monthly by Fred Richman in 1965, and five years later, Paul Monsky gave the answer.  You cannot divide a square into an odd number of equal-area triangles.  Monsky’s proof uses two facts:

  1. Sperner’s Lemma, a sort of combinatorial version of the Brouwer Fixed-Point Theorem, and
  2. the theory of the 2-adic valuation v_2 on the rational numbers \mathbb{Q}.

Let’s look at each of these in turn.

Sperner’s Lemma.  Consider a triangulation of a triangle T whose vertices are colored red, green, and blue, subject to the conditions that:

  • one of the three vertices of T is red, one is green, and one is blue;
  • on the edge of T between its red and green vertices, only red and green vertices appear, and likewise for the other two edges.

Then an odd number of the small triangles appearing in the triangulation have one vertex of each color.  (Most importantly, there’s at least one such triangle!)

An odd number of red-green-blue triangles!

By a triangulation, I mean a way of cutting our triangle T up into smaller triangles such that these triangles meet each other along entire edges — they’re not allowed to overlap or only meet along half an edge.  The picture should give you a good idea of how this works, as well as an example of the Lemma in action. 

A key point of the proof is that we can turn this triangulation into a graph: a simple and much-studied mathematical object, defined as a set of vertices (points) connected by edges (lines), with at most one edge between any pair of vertices.  In applications, graphs are often used to model networks like electrical grids, railway systems, computer networks, social groups, and so on.  It might not seem like there’s much to say about graphs, but the following fact, which we’ll use to prove Sperner’s Lemma, is first evidence to the contrary.

Handshaking Lemma.  In any graph, the number of vertices with an odd number of edges attached to them is always even.

Proof.  Let’s count the number of edges attached to each vertex (the math term for this is the degree of that vertex), and add these numbers together.  Call this number N.  Since every edge is attached to exactly two vertices, the number N should be exactly twice the number of edges — in particular, it’s even!  Now, each vertex with even degree contributes an even number to N, and thus the remainder — the sum of all the odd degrees in the graph — must also be even.  A sum of an odd number of odd numbers is never even, so there must be an even number of vertices with odd degree.

To make things a little more concrete, here’s where this lemma got its name.  Imagine each vertex is a person at a party, and the edges are handshakes.  The lemma is now just a reflection of the fact that each handshake involves two hands, and thus if we count a hand each time it shakes another hand, an even number of hands have been shook.  \square

Now, the obvious way to turn a Sperner-style triangulation into a graph is to let the vertices and edges of the graph just be the vertices and edges of the triangulation.  But that’s not what we’re going to do.  A key point about math is that the same sorts of structures can arise from physical, real-world obviousness as from more abstract, less intuitive constructions — and we can use the same sorts of thought processes to analyze them!  Here’s the proof:

Proof of Sperner’s Lemma.  Starting with our triangulation of the big triangle T, let G be the following graph.  There’s one vertex for each little triangle in the triangulation, and one vertex for the area outside of T.  Two vertices of G are connected by an edge if and only if there’s an edge of the triangulation between the corresponding regions, which has one red and one green vertex.  The picture below shows this happening.

The graph G is drawn in purple. The vertices of degree 1 are the red-green-blue triangles!

Consider the edge between the red and the green vertex of T.  The triangulation might put new vertices on this edge, splitting it into smaller edges, but we required all these vertices to be red or green, remember?  Since we have to change from red to green at some point as we move along the edge, one of these smaller edges must be a red-green edge.  In fact, an odd number must be — if not, we’d start at red and end up at red again.  Meanwhile, none of the other edges on the outside of T are red-green, so the vertex of G representing the outside region has odd degree.

The Handshaking Lemma tells us that there are in total an even number of vertices of G with this property.  Since we’ve just found one, there are an odd number appearing inside the triangle.  Obviously, every little triangle has at most three triangles adjoining it, and thus every vertex of G has degree at most 3.  But in fact, a vertex representing a little triangle can’t have degree three — this would mean that triangle has three red-green edges, an impossibility.  Thus, there are an odd number of vertices inside T with degree exactly 1.  This means the corresponding little triangles each have one red-green edge, which immediately implies that the remaining vertex is blue.  Thus, there are an odd number of red-green-blue triangles.  \square

A few notes about this:

  1. Note how useful and important the basic concepts of ‘even’ and ‘odd’ are.  This is a recurring theme in this whole blog post, and I’d argue it’s also a recurring theme in all of mathematics.
  2. Sperner’s Lemma generalizes to higher dimensions.

    One-dimensional Sperner’s Lemma — there are an odd number of red-green edges.

    For instance, in three dimensions, instead of triangulating a triangle and coloring its vertices three colors, we’d split a tetrahedron into smaller tetrahedra and color the vertices four colors.  You use an induction argument to prove this — for a hint about how this goes, note that the second paragraph of the proof uses the one-dimensional version, i.e. the statement that a line segment with vertices placed on it colored red and green, such that one of the endpoints of the segment is red and the other is green, has an odd number of red-green subsegments.

  3. As I said earlier, this statement is related to Brouwer’s Fixed-Point Theorem, which says that any continuous map from a disk to itself has a fixed point.  One of the great math-historical tragedies is the story of L. E. J. Brouwer, who proved his eponymic theorem via a proof by contradiction, then later went kinda philosophically mental and embraced a fringe system of logic called Intuitionism that considered proofs by contradiction invalid, and ended up repudiating his own theorem.  As was discovered after his death, Sperner’s Lemma can be used to give a proof of the Fixed-Point Theorem that’s valid in Intuitionism, posthumously vindicating the old man in his own weird, frenzied eyes.

Take a breather, ruminate, and when you get back we’ll introduce the second step of the proof.


Now let’s switch tacks drastically and talk about arithmetic.  The rational numbers \mathbb{Q}, recall, are all the real numbers that can be written as fractions a/b, where a and b are (positive or negative) integers.  We can write rational numbers uniquely as products of powers of primes, x = \pm p_1^{n_1}\dotsm p_k^{n_k}, where we’re letting the exponents be negative in order to deal with the non-integers.  (Not sure of people’s background, so to be totally, clear remember that a^{-b} = \frac{1}{a^b}, so that the primes appearing with negative exponents are supposed to be factors of the denominator and those with positive exponents are factors of the numerator.)

Now, there’s a function on \mathbb{Q}, called the 2-adic absolute value, defined by

|x|_2 = 2^{-n}, where n is the power of 2 appearing in the factorization of x.

So, for example, |6|_2 = 1/2 since 6 = 2^1\cdot 3^1; |-3/20|_2 = 4 since -3/20 = -2^{-2}\cdot 3^1\cdot 5^{-1}; and |1|_2 = |5|_2 = |9/17|_2 = 1, since there are no factors of two appearing in their factorizations.  We define |0|_2 to just be zero.  You should observe that the 2-adic absolute value has the following properties for all x and y:

  1. |xy|_2 = |x|_2 \cdot |y|_2.
  2. |x+y|_2 \le |x|_2 + |y|_2.  Even better, |x+y|_2 \le \max(|x|_2,|y|_2), with equality if |x|_2 \ne |y|_2.

This is one way of visualizing the rational numbers with the 2-adic absolute value. (Source: Wikipedia)

There’s likewise a p-adic absolute value for every prime p, defined similarly and with the same properties.  (Why only for primes?)  The standard absolute value, defined by |x| = x if x is positive and -x if x is negative, has these properties as well, except for the ‘even better’ part.  In fact, these absolute values — the p-adic absolute values for prime p and the standard absolute value (which mathematicians sometimes call ‘the prime \infty‘ like the ridiculous bat-monsters they are) — are, up to rescaling, the only functions with these properties on \mathbb{Q}.  Ultimately, this is why mathematicians care about them.  See, the standard absolute value is useful because it gives us notions of size and location on \mathbb{Q} — we can say how far apart numbers are, and how large and small they are.  The 2-adic absolute value does this too, but in a markedly different way.  Now the small numbers are the ‘most even’ numbers, i.e. those divisible by large powers of two, and the large numbers are those with large powers of two in their denominators.  With this notion of size, \mathbb{Q} is much harder to draw or visualize, as it doesn’t sit on a line, but you can still do geometric arguments with it, and eventually even things like calculus.  (The ‘even better’ in property 2 above often makes this geometry even easier to do!)  The p-adic viewpoint is that only thinking about \mathbb{Q} as sitting in the number line is like only reading the last page of a novel — to get the full story, you need to look at all the p-adic absolute values too.  Here’s a brief introduction to these ways of thinking.

Enough philosophy.  The only other thing you need to know about the 2-adic absolute value is the following theorem, which is hard and which I won’t prove.  Remember that \mathbb{R} is set of real numbers, that is, the whole number line, including both \mathbb{Q} and the irrational numbers like \pi and \sqrt{2}.

Theorem.  There exists a function |\cdot|_2: \mathbb{R} \to [0,\infty] that agrees with the 2-adic absolute value on \mathbb{Q} and that satisfies properties 1 and 2 above.

I’m not going to explicitly describe such a function, either, as for stupid reasons it’s effectively impossible to do so — there are an infinite number of them and the Axiom of Choice is necessary to construct one.  It’s clear by property 1, for example, that |\sqrt{2}|_2 = 1/\sqrt{2}, but to define the whole function we’d need to give |\pi|_2, |e|_2, and so on.  If this makes you uncomfortable, it’s worth pointing out that we don’t actually need choice to prove Monsky’s Theorem, since we’re only ever dealing with a finite number of points; if you’re still uncomfortable, feel free to only consider triangulations of squares such that all the vertices involved have rational coordinates.

When you return from the bathroom/tanning salon/offshore tax haven at which you’re attempting to establish residency, we’ll prove Monsky’s Theorem.


Proof of Monsky’s Theorem.  Remember that we’re starting out with a square divided into triangles.  We lose no generality by putting this square in the coordinate plane, with vertices (0,0), (1,0), (0,1), and (1,1).  As you may have guessed, we want to color the vertices of this triangulation in order to use Sperner’s Lemma, and you know what?  Let’s just go ahead and color every point in the plane.  (Please don’t actually try to do this.)  Color a point (x,y):

  • red if |x|_2 and |y|_2 are both less than 1;
  • blue if |x|_2 \ge |y|_2 and |x|_2 \ge 1;
  • green if otherwise, i.e. if |y|_2 > |x|_2 and |y|_2 \ge 1.

An example of a triangulated square, with colored vertices. (I haven’t written coordinates for the points, so there’s no way to tell if this coloring is correct or not — it’s just an example.)

In particular, the corner (0,0) of the square is colored red, (1,0) is colored blue, (0,1) is colored green, and (1,1) is colored blue.  More generally, every point on the x-axis is colored red or blue (the y coordinate is zero and has |y|_2 = 0), every point on the y-axis is colored red or green (ditto for x), and every point on the remaining two sides of the square is colored blue or green (one coordinate is 1 and has 2-adic absolute value 1).  Let’s forget for a moment that (1,1) is a vertex of our square — let’s pretend it’s a triangle that just had a bad day and bent one of its edges.  By what I just said, this triangle satisfies the conditions of Sperner’s Lemma!

In particular, there’s at least one little triangle in our triangulation with one red vertex, one green vertex, and one blue vertex.  Since these colors now mean something in terms of the 2-adic absolute value, we can try to compute its area.  To make things easier, let’s translate the triangle so that its red vertex is at (0,0).  This doesn’t change its area, but I need to convince you it won’t change the vertex colors either.  We already saw that (0,0) is red, so that vertex is fine.  For the other two vertices, we’re moving a point (x,y) to (x-a,y-b), where (a,b) are the coordinates of the red point.  By property 1 of the 2-adic valuation, |a|_2 = |-a|_2.  By the ‘even better’ of property 2, if |x|_2 \ge 1 and |a|_2 < 1, then |x-a|_2 = |x+(-a)|_2 = |x|_2, and likewise for y and b.  Thus if both |x|_2 and |y|_2 are at least 1, the absolute values of the translated coordinates stay the same, and the color of the translated point remains the same.  If one of |x|_2 and |y|_2 is less than 1, then it’s possible that translation changes it.  However, by the ‘even better’ again, this absolute value can only decrease under translation, so the color of the translated point remains the same.

A translation moving the red vertex to zero doesn’t change the color of the triangles vertices.

So now we have a triangle with one corner at (0,0) and with the other two corners colored blue and green.  What does this tell us about its area?  Well, it’s a simple fact from coordinate geometry that if these corners are (x_1,y_1) and (x_2, y_2), then the area of the triangle is A = \frac{1}{2}|x_1y_2 - x_2y_1| — this is a standard absolute value, not a 2-adic one, natch.  Now we just calculate, using what we know about the 2-adic absolute value.  First, taking the standard absolute value of a number multiplies it by \pm 1, so its 2-adic absolute value doesn’t change, by property 1.  Therefore,

\begin{displaystyle}\begin{aligned}|\frac{1}{2}|x_1y_2 - x_2y_1||_2 &= 2|x_1y_2 - x_2y_1|_2 \\ &\le 2\max(|x_1y_2|_2, |x_2y_1|_2) \\ &= 2\max(|x_1|_2 |y_2|_2, |x_2|_2 |y_1|_2). \end{aligned}\end{displaystyle}

Let’s say that (x_1,y_1) is the blue point and (x_2, y_2) is the green one.  Then x_1 and y_2 have larger 2-adic absolute values than y_1 and x_2 respectively, with the inequality being strict in the second case.  Thus |x_1|_2 |y_2|_2 > |x_2|_2 |y_1|_2.  Since this inequality is strict, the \le in the above calculation is actually an =, and we get |A|_2 = 2|x_1|_2|y_2|_2.  But both these absolute values are at least 1, so |A|_2 \ge 2.  This means that, if A is rational and written in lowest terms (i.e. we’ve cancelled all the common factors in the numerator and denominator), it must have an even denominator.  But if we could split the square into an odd number of triangles of equal area, these areas would all be 1 divided by an odd number — namely, the number of triangles used!  Thus, this must be impossible.  This concludes the proof.  \square

Take a look at what we just did.  We colored a graph, proved things about it by turning it into a different graph, defined a radically new absolute value, used it to color every point on the plane, and used that to tell us about the areas of triangles.  There’s been a running theme throughout: there are lots of different ways to say that something’s even or odd, and lots of different information that you can get out of it.  Yet again, the simplest ideas lead to the cleverest proofs and the most unique, intriguing results.  Hope you think so too — and are perhaps inspired to include a little more bizarre thinking in your life.

Advertisements

3 thoughts on “Monsky’s Theorem, or the genius of bizarre thinking

  1. Pingback: Brouwer’s fixed-point theorem | Complex Projective 4-Space

  2. (This post will be at a lower level than most of my other writing here — it should be understandable by math undergrads and ideally even the Laity. Let me know how I’m doing!)

    Well, if you’re writing for “the laiety”, then these are wasted words.

  3. I love your explanation of the 2-adic valuation. (However I’ve googled it several times so I’m not a great test case.)

    Overall I think this is too jargon-y to appeal to “the laiety” — and if you want to do that, you should pick an application domain that’s relevant/interesting to normal people and then show how using these lemmas and isomorphisms you can infer something un-intuitive about the thing they are familiar with. (The result should be stated in plain language, and be interesting.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s