p-adic Numbers and Dissections of Squares into Triangles

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 $n$ be a positive integer. It is easy to see that a square can be dissected into $n$ triangles of equal area if $n$ is even (Exercise). What if $n$ 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 $\frac{1}{n}$ with $n$ 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 $\sigma$ of S has endpoints which are blue and red, and no other side of S contains both blue and red points.

A Sperner coloring of the vertices of a dissection of the square into triangles

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 $\sigma$ . Indeed, one endpoint of $\sigma$ is blue, one is red, and all other vertices along $\sigma$ are either blue or red. In walking from the red endpoint of $\sigma$ 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 $S$ is the square whose vertices are $(1,1), (2,1), (1,2), (2,2).$ We will first deal with the special case (due to Thomas) where the vertices $Q_i = (x_i,y_i)$ of the dissection all have rational coordinates, and then discuss Monsky’s extension to the general case.

In the special case where all $x_i, y_i$ have rational coordinates, let $v = v_2 : {\mathbb Q} \to {\mathbb R}$ denote the 2-adic valuation on ${\mathbb Q}$ (i.e., if $\alpha = a/b$ with $a,b \in {\mathbb Z}$ then $v_2(\alpha)$ is the power of 2 dividing $a$ minus the power of 2 dividing $b$ .) We color a point $P = (x,y)$ of $S$ according to the following rule:

${\rm B} = \{ v(x) \leq 0, v(y) \}, {\rm R} = \{ 0 < v(x),v(y)\}, {\rm G} = \{ v(y) \leq 0, v(y) < v(x) \}$

Note that the tilted ‘Y’ shape in the middle of the above figure is a tropical line; in fact, it is precisely the image $L_0$ of the line $x + y + 1 = 0$ under the tropicalization map $({\mathbb Q}^*)^2 \to {\mathbb R}^2$ sending $(x,y)$ to $(v(x),v(y)).$

Starting clockwise from the upper left corner, note that the four corners of S have tropicalizations $(0,1), (1,1), (1,0), (0,0)$ and hence get colored blue, red, green, and blue, respectively. By inspection, the top edge $\sigma$ 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 $L \cap ({\mathbb Q}^*)^2$ under the tropicalization map is contained in a (possibly degenerate) tropical line in ${\mathbb R}^2$ , which must be either a point, a line parallel to one of the three rays of $L_0$ , or a translation of $L_0$ . 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 $\frac{1}{n}$ with $n$ odd. To see this, let $T$ be any triangle in the dissection. By a well-known formula in elementary geometry, if the vertices of $T$ are $P_i = (x_i,y_i)$ for $i=1,2,3$ , the area $A$ of $T$ is $\frac{1}{2} {\rm det}(M),$ where

$M = \left( \begin{array}{lll} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \\ \end{array} \right).$

Expanding the determinant as an alternating sum of six terms, we have $A = \frac{1}{2} (x_1 y_2 - x_1 y_3 + y_1 x_3 - y_1 x_2 + x_2 y_3 - x_3 y_2).$

Now suppose that $T$ is a rainbow triangle. Without loss of generality, $P_1$ is blue, $P_2$ is green, and $P_3$ is red. In this case, $v(x_1 y_2) = v(x_1) + v(y_2) \leq 0$ and all other terms $x_i y_j$ in the six-term expansion of the determinant have valuation strictly larger than $v(x_1 y_2).$ By the ultrametric inequality, it follows that $v(A) = v({\rm det}(M)) - 1 = v(x_1 y_2) - 1 \leq -1.$ Since $v(\frac{1}{n}) = 0$ when $n$ is odd, it follows in particular that $A \neq \frac{1}{n}$ as claimed!

Note also that if $P_1, P_2, P_3$ are points of $L \cap ({\mathbb Q}^*)^2$ for some line $L$ , the degenerate triangle formed by these points has area zero, and the determinental formula still applies, so $P_1, P_2, P_3$ cannot all have different colors (else we would have $+\infty = v(0) \leq -1$ , 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 $x_i, y_i$ have rational coordinates.

We now turn to the general case. Let $K$ be the extension of ${\mathbb Q}$ generated by the $x$ and $y$ coordinates of all vertices $Q_i$ in our dissection. This is a finitely generated extension of ${\mathbb Q}$ . If $v$ is any extension of the 2-adic valuation on ${\mathbb Q}$ to $K$ , 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 $k$ is a field, $v_0 : k^* \to {\mathbb R}$ is a valuation on $k$ , and $K$ is a finitely generated field extension of $k$ , there exists a valuation $v$ on $K$ whose restriction to $k$ is $v_0$ .

(In fact, Chevalley proved this result without the restriction that $K/k$ 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 $K/k$ can be factored as $K / k(t_1,\ldots,t_m) / k$ where $K / k(t_1,\ldots,t_m)$ is finite and $t_1,\ldots,t_m$ are algebraically independent over $k$ , i.e., $k(t_1,\ldots,t_m) / k$ is purely transcendental. It therefore suffices by induction to prove the theorem in the two special cases (i) $K/k$ algebraic and (ii) $K = k(t)$ with $t$ transcendental over $k$ . In case (i), we may furthermore assume that $k$ is complete, and in this case it is well-known that there is a unique extension of $v_0$ to $K$ , given by the formula

$v(\alpha) = \frac{1}{[K:k]} v_0({\rm Norm}^K_k(\alpha)).$

In case (ii), there are many possible extensions. For one such extension, we first extend $v_0$ to the polynomial ring $k[t]$ by defining $v(\sum a_i t^i) = {\rm min}(v(a_i)),$ and then extend to the quotient field $k(t)$ by the formula $v(P/Q) = v(P) - v(Q)$ . Q.E.D.

Concluding remarks:

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 $n$ dimensions can be divided into $m$ simplices, all of equal volume, if and only if $m$ is a multiple of $n!.$

The proof is similar to the proof of the Monsky-Thomas theorem, comprising (i) a generalization of Sperner’s Lemma to simplicial decompositions of $n$ -dimensional polytopes, (ii) a coloring scheme for each prime number $p$ which generalizes the one above in dimension 2 for $p=2$ , and (iii) the determanental formula for the volume of an $n$ -simplex, which involves a leading term of $\frac{1}{n!}.$ One finds that there exists a rainbow simplex $T$ and for each prime $p$ , we have $v_p(1/m) = v_p({\rm vol}(T)) \leq -v_p(n!).$ This implies that $n!$ divides $m$ 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 $n \geq 5$ be an integer. A regular $n$ -gon is dissectable into $m$ triangles with equal areas if and only if $m$ is a multiple of $n$ .

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.

5 thoughts on “p-adic Numbers and Dissections of Squares into Triangles”

Pingback: Dissecting squares into equal-area triangles: idle questions | Quomodocumque
Daniele Turchetti says:

April 26, 2016 at 6:28 pm

This theorem is also one of my favorite applications of p-adic numbers! The tropical interpretation seems a little bit “ad hoc” to me, though: do you know of other results that you can get by coloring planary graphs according to the relative position of the vertices with respect to some tropical curves?

- Matt Baker says:
  
  April 27, 2016 at 7:16 pm
  
  No, unfortunately I don’t know of any other results which can be proved in this way. I don’t actually think of the tropical interpretation as “ad hoc”, but I guess that’s a subjective matter…
  
Damásdi Gábor says:

April 9, 2019 at 12:56 pm

The same connection is also pointed out in this article: https://arxiv.org/abs/1206.4591

- Matt Baker says:
  
  April 9, 2019 at 11:44 pm
  
  Thank you for the reference.

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

p-adic Numbers and Dissections of Squares into Triangles

5 thoughts on “p-adic Numbers and Dissections of Squares into Triangles”

Leave a Reply Cancel reply

Share this:

Like this:

Related

5 thoughts on “p-adic Numbers and Dissections of Squares into Triangles”

Leave a Reply Cancel reply