My thesis advisor Robert Coleman passed away two years ago today (see this remembrance on my blog). One of the things I learned from Robert is that p-adic numbers have many unexpected applications (see, for example, this blog post). Today I want to share one of my favorite surprising applications of p-adic numbers, to a simple problem in Euclidean geometry.
Let be a positive integer. It is easy to see that a square can be dissected into triangles of equal area if is even (Exercise). What if is odd? If you play with the question for a bit, you probably won’t be surprised to learn that in this case it’s impossible. But you may be surprised to learn that this result was not proved until 1970, that the proof involved p-adic numbers, and that no proof is known which does not make use of p-adic numbers! We will give Paul Monsky and John Thomas’s beautiful argument, following in part the exposition from Proofs from the Book (5th edition) but emphasizing a bit more the connections to tropical geometry. The original paper of Monsky is available here.
Theorem: It is impossible to dissect a square into an odd number of triangles of equal area.
Proof: Without loss of generality we may assume that the square S has area 1. The idea is to color the vertices of the dissection using three colors (blue, green, and red) in such a way that:
(1) The coloring is a Sperner coloring (definition below), and hence, by a suitable variant of Sperner’s Lemma, at least one of the triangles in the dissection is a rainbow triangle, i.e., each vertex has a different color.
(2) A rainbow triangle cannot have area with odd.
We first explain what a Sperner coloring is, and why it guarantees the existence of a rainbow triangle in the dissection. We then explain how to color the vertices of the dissection in such a way that (1) and (2) are automatically satisfied.
A Sperner coloring is one in which:
(S1) Every side of S and every edge of a triangle T in the dissection uses only two of the three colors.
(S2) Some side of S has endpoints which are blue and red, and no other side of S contains both blue and red points.
Given a Sperner coloring, we claim that the number of rainbow triangles must be odd, and in particular there is at least one rainbow triangle! To see this, consider the edges between neighboring vertices in the dissection. We make the following observations:
(i) There are an odd number of blue-red segments along . Indeed, one endpoint of is blue, one is red, and all other vertices along are either blue or red. In walking from the red endpoint of to the blue one, there must be an odd number of color changes.
(ii) By (S2), there are no blue-red segments on any of the other sides of S.
(iii) A non-rainbow triangle contains an even number of blue-red edges on its boundary, while a rainbow triangle has an odd number of such edges.
Now what happens if we add up the number of blue-red segments on the boundary of T over all triangles T in the dissection? Well, every blue-red segment in the interior of S is counted twice, and there is an odd number of such segments on the boundary of S by (i) and (ii), so the total number is odd. It now follows from (iii) that there must be at least one rainbow triangle, proving the claim.
We are thus reduced to producing a Sperner coloring of the vertices of the dissection. We may assume without loss of generality that is the square whose vertices are We will first deal with the special case (due to Thomas) where the vertices of the dissection all have rational coordinates, and then discuss Monsky’s extension to the general case.
In the special case where all have rational coordinates, let denote the 2-adic valuation on (i.e., if with then is the power of 2 dividing minus the power of 2 dividing .) We color a point of according to the following rule:
Note that the tilted ‘Y’ shape in the middle of the above figure is a tropical line; in fact, it is precisely the image of the line under the tropicalization map sending to
Starting clockwise from the upper left corner, note that the four corners of S have tropicalizations and hence get colored blue, red, green, and blue, respectively. By inspection, the top edge of S uses only the colors blue and red, the left and bottom edges use only blue and green, and the right edge uses only green and red. This verifies property (S2), as well as part of (S1).
To check the Sperner property (S1) in full, it suffices to prove the more general fact that the intersection of any straight line L with the rational points of S consists of points which use at most two of the three colors. One way to see this is to use a bit of elementary tropical geometry: the image of under the tropicalization map is contained in a (possibly degenerate) tropical line in , which must be either a point, a line parallel to one of the three rays of , or a translation of . But it is easy to see that any such tropical line will intersect the above figure in just two of the three colored regions, so we’re done. (We will give a second, completely different, argument below.)
Now that we’ve checked that our coloring is a Sperner coloring, it remains to verify that a rainbow triangle cannot have area with odd. To see this, let be any triangle in the dissection. By a well-known formula in elementary geometry, if the vertices of are for , the area of is where
Expanding the determinant as an alternating sum of six terms, we have
Now suppose that is a rainbow triangle. Without loss of generality, is blue, is green, and is red. In this case, and all other terms in the six-term expansion of the determinant have valuation strictly larger than By the ultrametric inequality, it follows that Since when is odd, it follows in particular that as claimed!
Note also that if are points of for some line , the degenerate triangle formed by these points has area zero, and the determinental formula still applies, so cannot all have different colors (else we would have , a contradiction). This gives the alternate proof of the Sperner property (S1) promised above.
The argument is now finished in the special case where all have rational coordinates.
We now turn to the general case. Let be the extension of generated by the and coordinates of all vertices in our dissection. This is a finitely generated extension of . If is any extension of the 2-adic valuation on to , the exact same argument we just gave applies verbatim! So we are done by the classical theorem of Chevalley below. Q.E.D.
Theorem (Chevalley): If is a field, is a valuation on , and is a finitely generated field extension of , there exists a valuation on whose restriction to is .
(In fact, Chevalley proved this result without the restriction that is finitely generated, but we only need the finitely generated case, which is more elementary as it does not require invoking the axiom of choice like in the general case.)
Proof (sketch): Every finitely generated extension can be factored as where is finite and are algebraically independent over , i.e., is purely transcendental. It therefore suffices by induction to prove the theorem in the two special cases (i) algebraic and (ii) with transcendental over . In case (i), we may furthermore assume that is complete, and in this case it is well-known that there is a unique extension of to , given by the formula
In case (ii), there are many possible extensions. For one such extension, we first extend to the polynomial ring by defining and then extend to the quotient field by the formula . Q.E.D.
1. The argument given above actually proves the significantly stronger fact that it is impossible to dissect a square into triangles whose areas are all rational numbers with odd denominators.
2. In this paper, D. G. Mead proves the following extension of the Monsky-Thomas theorem:
Theorem (Mead): The unit hypercube in dimensions can be divided into simplices, all of equal volume, if and only if is a multiple of
The proof is similar to the proof of the Monsky-Thomas theorem, comprising (i) a generalization of Sperner’s Lemma to simplicial decompositions of -dimensional polytopes, (ii) a coloring scheme for each prime number which generalizes the one above in dimension 2 for , and (iii) the determanental formula for the volume of an -simplex, which involves a leading term of One finds that there exists a rainbow simplex and for each prime , we have This implies that divides as desired (the other direction is easy).
3. In a different direction, using the methods of Monsky, Thomas, and Mead, Kasimatis proves the following result:
Theorem (Kasimatis): Let be an integer. A regular -gon is dissectable into triangles with equal areas if and only if is a multiple of .
4. One can give a more elementary proof of the special case of Chevalley’s theorem needed for the proof of our main theorem on dissecting a square into triangles – see the appendix to Chapter 22 of Proofs from the Book.
5. My other favorite application of Sperner’s Lemma is to fair division problems, see for example this New York Times article.