\documentclass[12pt]{amsart}
%%% PACKAGES %%%
\usepackage{comment}
\usepackage{enumerate}
\usepackage{fullpage}
%\usepackage{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{xy}
\input xy
\xyoption{all}
\usepackage{tikz}
%\geometry{lmargin=1in, rmargin=1in, tmargin=1in, bmargin=1in}
%%% THEOREMS %%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{case}{Case}
\newtheorem*{claim}{Claim}
\newtheorem{counterexample}{Counterexample}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{exercise}{Exercise}[section]
\newtheorem*{note}{Note}
\newtheorem{problem}[exercise]{Problem}
\newtheorem*{remark}{Remark}
\newtheorem*{question}{Question}
\newtheorem*{joke}{Joke}
\newtheorem*{motivation}{Motivation}
\theoremstyle{remark}
\newtheorem*{solution}{Solution}
%%% LETTERS %%%
\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\d{\delta}
\def\e{\varepsilon}
\def\z{\zeta}
\def\h{\eta}
\def\th{\theta}
\def\i{\iota}
\def\k{\kappa}
\def\l{\lambda}
\def\m{\mu}
\def\n{\nu}
\def\o{\omicron}
\def\p{\rho}
\def\s{\sigma}
\def\t{\tau}
\def\u{\upsilon}
\def\f{\phi}
\def\x{\chi}
\def\y{\psi}
\def\w{\omega}
\def\D{\Delta}
\def\F{\Phi}
\def\G{\Gamma}
\def\Th{\Theta}
\def\L{\Lambda}
\def\X{\Xi}
\def\Y{\Psi}
\def\S{\Sigma}
\def\U{\Upsilon}
\def\W{\Omega}
\def\AA{\mathbb{A}}
\def\BB{\mathbb{B}}
\def\CC{\mathbb{C}}
\def\DD{\mathbb{D}}
\def\EE{\mathbb{E}}
\def\FF{\mathbb{F}}
\def\GG{\mathbb{G}}
\def\HH{\mathbb{H}}
\def\II{\mathbb{I}}
\def\JJ{\mathbb{J}}
\def\KK{\mathbb{K}}
\def\LL{\mathbb{L}}
\def\MM{\mathbb{M}}
\def\NN{\mathbb{N}}
\def\OO{\mathbb{O}}
\def\PP{\mathbb{P}}
\def\QQ{\mathbb{Q}}
\def\RR{\mathbb{R}}
\def\SS{\mathbb{S}}
\def\TT{\mathbb{T}}
\def\UU{\mathbb{U}}
\def\VV{\mathbb{V}}
\def\WW{\mathbb{W}}
\def\XX{\mathbb{X}}
\def\YY{\mathbb{Y}}
\def\ZZ{\mathbb{Z}}
\def\cA{\mathcal{A}}
\def\cB{\mathcal{B}}
\def\cC{\mathcal{C}}
\def\cD{\mathcal{D}}
\def\cE{\mathcal{E}}
\def\cF{\mathcal{F}}
\def\cG{\mathcal{G}}
\def\cH{\mathcal{H}}
\def\cI{\mathcal{I}}
\def\cJ{\mathcal{J}}
\def\cK{\mathcal{K}}
\def\cL{\mathcal{L}}
\def\cM{\mathcal{M}}
\def\cN{\mathcal{N}}
\def\cO{\mathcal{O}}
\def\cP{\mathcal{P}}
\def\cQ{\mathcal{Q}}
\def\cR{\mathcal{R}}
\def\cS{\mathcal{S}}
\def\cT{\mathcal{T}}
\def\cU{\mathcal{U}}
\def\cV{\mathcal{V}}
\def\cW{\mathcal{W}}
\def\cX{\mathcal{X}}
\def\cY{\mathcal{Y}}
\def\cZ{\mathcal{Z}}
%%% OTHER MATH COMMANDS %%%
\def\pd{\partial}
\def\ol{\overline}
\def\ul{\underline}
%%% SPECIAL MATH COMMANDS %%%
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\Ker}{Ker}
\def\Im{\operatorname{Im}}
%%% AMSART DATA %%%
\title{Sperner's Lemma}
\setcounter{tocdepth}{1}
\email{moorxu@stanford.edu}
\author{Moor Xu}
%%% BEGIN DOCUMENT %%%
\begin{document}
%%%%%%%%%%%% TO DO %%%%%%%%%%%%%
% Fix valuation -> absolute value
% Insert reference to Lang
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
Is it possible to dissect a square into an odd number of triangles of equal
area? This question was first answered by Paul Monsky in 1970, and the solution
requires elements from two seemingly disjoint areas of mathematics: number
theory and combinatorial topology. Along the way, we will see $p$-adic numbers
and a combinatorial proof of Brouwer's fixed point theorem.
%%% OLD ABSTRACT:
%The main theorem of the talk will be that any dissection of a square into
%triangles of equal areas requires an even number of such triangles; a square
%cannot be divided into an odd number of triangles with equal areas. This
%theorem was first proved by Paul Monsky in 1970, and the proof requires
%elements from two seemingly disjoint areas of mathematics: number theory and
%combinatorial topology.
\end{abstract}
\maketitle
%\tableofcontents
\section{Introduction}
We will discuss a simple theorem that is connected with some interesting
results. The topic is dissection of polygons into triangles.
We want triangles of equal areas -- equiareal triangulation.
\begin{theorem}
If a square is cut into triangles of equal areas, then the number of triangles
must be even.
\end{theorem}
We start with a little history.
\begin{remark}
The first person who thought about this was Fred Richman (1965) at New Mexico
State. He was preparing a masters exam, and he wanted to include this but
couldn't solve it.
He asked the problem in the Am. Math. Monthly, and Paul Monsky proved the
theorem in 1970.
\end{remark}
There are several results of a similar nature, but there are many
more open problems than results. The proof of this fact is difficult and makes
use of two disjoint areas of mathematics.
This is the only known proof so far. There are two ingredients:
\begin{enumerate}
\item combinatorial / topological
\item number theoretic / algebraic.
\end{enumerate}
\section{Sperner's Lemma}
We start with the topological part.
Let $P$ be a polygon in the plane, and consider a triangulation of this
polygon. Color each vertex of this triangulation
by one of three colors $1$, $2$, or $3$.
An edge is called a \emph{12-edge}
if its endpoints is colored $1$ and $2$, and a
triangle is said to be \emph{complete}
if each of its vertices is colored using a
different color.
\begin{lemma}[Sperner, 1928]
If we have a polygon whose
vertices are colored by three colors and a triangulation is given for this
polygon, the number of complete triangles (with three different colors) is equal
to the number of 12-edges on the boundary of the polygon (mod 2).
\end{lemma}
This is a way to predict if we have a complete triangle inside the polygon.
\begin{proof}
Put a dot on each side of each
12-segment. We want to count the number of dots in two different ways.
Firstly, each interior segment contributes either 0 or 2 dots
(depending on whether it is a 12-edge),
while each boundary segment contributes 0 or 1 dots. The number of dots is
therefore equal to the number of 12-edges on the boundary of the polygon
(mod 2).
\begin{center}
\begin{tikzpicture}
\fill[gray!30!white] (-3,0)--(-2.25,1.3)--(0,0)--cycle;
\fill[gray!30!white] (1.5,2.6)--(3,0)--(1.5,1)--cycle;
\fill[gray!30!white] (1.5,2.6)--(0,0)--(1.5,1)--cycle;
\draw (-3,0) node[below left]{2}--(0,0) node[below]{3};
\draw (0,0)--(3,0) node[below right]{3};
\draw (3,0)--(1.5,2.6) node[right]{1};
\draw (1.5,2.6)--(0,5.2) node[above]{1};
\draw (1.5,2.6)--(0,0);
\draw[very thick] (1.5,2.6)--(1.5,1) node[below]{2}
node[left,midway]{$\bullet$} node[right,midway]{$\bullet$};
\draw (0,0)--(1.5,1);
\draw (3,0)--(1.5,1);
\draw[very thick] (-3,0)--(-2.25,1.3) node[left]{1}
node[left,midway]{$\bullet$} node[right,midway]{$\bullet$};
\draw (-2.25,1.3)--(-1.5,2.6) node[left]{1};
\draw[very thick] (-1.5,2.6)--(-0.75,3.9) node[left]{2}
node[left,midway]{$\bullet$} node[right,midway]{$\bullet$};
\draw[very thick] (-0.75,3.9)--(0,5.2)
node[left,midway]{$\bullet$} node[right,midway]{$\bullet$};
\draw (-2.25,1.3)--(0,0);
\draw (-1.5,2.6)--(0,0);
\draw[very thick] (-0.75,3.9)--(1.5,2.6)
node[above,midway]{$\bullet$} node[below,midway]{$\bullet$};
\draw (-1.5,2.6)--(1.5,2.6);
\fill[red] (0,5.2) circle (2pt);
\fill[green] (-0.75,3.9) circle (2pt);
\fill[red] (-1.5,2.6) circle (2pt);
\fill[red] (-2.25,1.3) circle (2pt);
\fill[green] (-3,0) circle (2pt);
\fill[blue] (0,0) circle (2pt);
\fill[blue] (3,0) circle (2pt);
\fill[green] (1.5,1) circle (2pt);
\fill[red] (1.5,2.6) circle (2pt);
\end{tikzpicture}
\end{center}
Now count the number of dots in each triangle.
Complete triangles contain one dot (check this), while
other triangles contain an even number of dots.
Therefore, the number of dots is equal to the number of complete triangles (mod
2). This concludes the proof.
\end{proof}
%%%%%%%%%%%%%%%%
\section{Brouwer fixed point theorem}
\textit{This is an optional section. Later sections do not depend on it.}
\begin{theorem} \label{brouwer}
Let $B^n$ be the $n$-dimensional ball. Then any continuous map $f : B^n \to
B^n$ has a fixed point.
\end{theorem}
\begin{example}
In the one-dimensional case, this is simply a consequence of the intermediate
value theorem.
\end{example}
This is much less trivial in higher dimensions. In the two-dimensional case, we
can prove this using Sperner's lemma.
We'll need to use a lemma that is a simple corollary of Sperner's Lemma.
\begin{lemma} \label{lemmabrouwer}
Consider a triangulation $T$ of a triangle $ABC$.
Color the outer three vertices $A$, $B$, $C$ as
$1$, $2$, and $3$ respectively.
Use only colors $\{ 1, 2 \}$ on the edge $AB$, only colors
$\{1,3\}$ on the edge $AC$, and only colors $\{2,3\}$ on the edge $BC$. This
triangulation contains a complete triangle.
\end{lemma}
\begin{proof}
A 12-boundary
edge can only appear on the side with endpoints colored $1$ and $2$,
so there are an odd number of 12-edges on the boundary.
\end{proof}
\begin{remark}
This works for all polygons, not just triangles.
We will use a related result in our proof of the Monsky theorem.
\end{remark}
\begin{proof}[Proof of Theorem \ref{brouwer} in case $n=2$]
Since a disk is homeomorphic to a triangle, it suffices to prove that any
continuous map on a triangle has a fixed point.
Let $\triangle$ be the triangle in $\RR^3$ with vertices $e_1 = (1, 0, 0)$,
$e_2 = (0,1,0)$, and $e_3 = (0, 0, 1)$. In other words,
\[
\triangle = \{ (a_1, a_2, a_3) \in [0, 1]^3 : a_1 + a_2 + a_3 = 1 \}.
\]
Suppose to the contrary that a continuous map $f:
\triangle \to \triangle$ has no fixed point.
For each of these triangulations, color the vertices with the colors $\{ 1, 2,
3 \}$. For each $v \in T$, define the coloring of $v$ to be the minimum color
$i$ such that $f(v)_i < v_i$, that is, the minimum index $i$ such
that the $i$-th coordinate of $f(v) - v$ is negative. This is well-defined
assuming that $f$ has no fixed point because we know that the sum of the
coordinates of $v$ and $f(v)$ are the same.
We claim that $e_1$, $e_2$, and $e_3$ are colored differently. Indeed, they
each maximize a different coordinate and hence are first negative at that
coordinate. Furthermore, a vertex on the $e_1 e_2$ edge has $a_3 = 0$, so that
$f(v) - v$ has nonnegative third coordinate and is hence colored $1$ or $2$.
The same is true for the other coordinates, and we are therefore in the case
of Lemma \ref{lemmabrouwer}. Hence, for any triangulation $T_k$, there is a
small complete triangle $\triangle_k$.
Let $\d(T)$ denote the maximal length of an edge in a triangulation $T$. It is
easy to construct a sequence of triangulations $T_1, T_2, \dots$ such that
$\d(T_k) \to 0$ as $k \to \infty$.
These triangles $\triangle_k$ don't necessarily have to converge to a point,
but every sequence in a compact space has a convergent subsequence. So there
is some subsequence of triangles $\triangle_{k_1}, \triangle_{k_2}, \dots$ that
converges to some point $x$. We know that for each $i$, there are vertices
$v_{i,1}$, $v_{i,2}$, $v_{i,3}$ really close to $x$ such that $f(v_{i,1})$ has
its first coordinate less than that of $v_{i,1}$. This means that $f(x)$ has
its first coordinate at most that of $x$. The same is true for the second and
third coordinates. This means that therefore $f(x) = x$.
\end{proof}
%%%%%%%%%%%%%%%%%%
\section{$2$-adic valuations}
The second ingredient of the theorem is number theory. We are interested in
2-adic valuations. First, what is a valuation? A valuation measures how big a
number is. The absolute value is the most common example of a valuation.
A valuation $|\cdot|$ must have the following properties:
\begin{enumerate}
\item $|x| \ge 0$
\item $|x| = 0$ if and only if $x = 0$
\item $|x \cdot y| = |x| \cdot |y|$
\item $|x + y| \le |x| + |y|$.
\end{enumerate}
Another example of a valuation is the 2-adic valuation.
\begin{definition}
Any rational number $x = p/q$ can be written as $x = 2^n \frac ab$ where $a$
and $b$ is odd. (Here, $n$ might be negative.) The \emph{2-adic valuation} of
$x$ is defined to be $|x|_2 = (1/2)^n$.
\end{definition}
\begin{example}
For example, note that $|1|_2 = 1$, $|2|_2 = 1/2$, $|6|_2 = 1/2$, and
$|20|_2 = 1/4$.
\end{example}
\begin{remark}
Note that an integer has 2-adic valuation less than 1 if and only if it is
even. Otherwise, the 2-adic valuation is 1.
\end{remark}
\begin{example}
As further examples, $|1/3|_2 = 1$, $|3/20|_2 = 4$, and $|13/16|_2 = 16$.
\end{example}
It is easy to check that this is a valuation. In particular, we will use the
following properties:
\begin{enumerate}
\item $|0|_2 = 0$
\item $|mn|_2 = |m|_2 |n|_2$
\item $|m+n|_2 \le |m|_2 + |n|_2$.
\item if $|m|_2 < |n|_2$ then $|m + n|_2 = |n|_2$.
\end{enumerate}
This defines the 2-adic valuations of rational numbers. What if we wanted to
define the 2-adic valuation of the real numbers? We need a
magic wand to do this. In some cases, it is clear how to extend from the
rationals to the reals. As an example, we have
$|\sqrt2|_2 |\sqrt2|_2 = |2|_2 = \frac12$,
so it makes sense to define $|\sqrt2|_2 = \frac1{\sqrt2}$. What about defining
a value for $|\pi|_2$? In fact, this can be done consistently for all real
numbers, using the axiom of choice.
We can analogously define $p$-adic valuations, but we don't need that now.
\section{Proof of Monsky's theorem}
We can color points in $\RR^2$ according to the following sets:
\begin{align*}
S_1 &= \{(x, y): |x|_2 < 1, |y|_2 < 1 \} \\
S_2 &= \{(x, y): |x|_2 \ge 1, |x|_2 \ge |y|_2 \} \\
S_3 &= \{(x, y): |y|_2 \ge 1, |y|_2 > |x|_2 \}.
\end{align*}
Notice that classes 2 and 3 are translation invariant under points in class 1.
\begin{lemma}
Let a triangle with vertices in $\RR^2$ be complete. Then its area satisfies
\[ |\text{area}|_2 > 1. \]
This means that it has two in the denominator.
\end{lemma}
\begin{proof}
By translation invariance, we can assume that the triangle is at the origin,
in which case we can write its area as a determinant. Let $(x_2, y_2)$ and
$(x_3, y_3)$ be colored $2$ and 3. Then,
\[ \frac12 \left\lvert \begin{matrix}
x_2 & x_3 \\
y_2 & y_3
\end{matrix} \right\rvert
= \frac{x_2 y_3 - x_3 y_2}{2}.
\]
Furthermore, we have $|x_2|_2 \ge |y_2|_2$ and $|y_3|_2 > |x_3|_2$, where
$|x_2|_2 , |y_3|_2 > 1$.
Therefore, $x_2 y_3$ dominates, having $|x_2y_3|_2 > |x_3y_2|_2$. This means
that
\[
|\text{area}|_2
= \left| \frac12 \right|_2 \cdot |x_2 y_3 - x_3 y_2|_2
%= 2 \cdot \max (|x_2 y_3|_2, |x_3 y_2|_2)
= 2 \cdot |x_2 y_3|_2 = 2 |x_2|_2 |y_3|_2 \ge 2.
\]
This proves the lemma.
\end{proof}
We can now finish the proof of the Monsky theorem.
\begin{theorem}
Given a dissection of a square $S$
into $m$ triangles of equal area, $m$ is even.
\end{theorem}
\begin{proof}
Without loss of generality,
let the vertices of the square $S$ be $(0, 0)$, $(0, 1)$, $(1, 0)$, $(1, 1)$.
Consider a triangulation $T$ of $S$, and just as in the above way, we can
color the vertices of $T$. Observe that on the boundary $\pd S$, $12$-edges can
only occur on the edge connecting $(0,0)$ and $(1,0)$; furthermore, vertices
colored 3 cannot occur on this edge, so there must be an odd number of
$12$-edges.
Therefore, by Sperner's
Lemma, there is a complete triangle in $T$. So its area $A$
has a 2-adic valuation
$|A|_2 > 1$. But the area of $S$ is $mA = 1$, so
$|m|_2 < 1$, which means that $m$ is even.
\end{proof}
\section{Generalizations and Closing Thoughts}
Why do we care about equiareal triangulation? Yes, it is a cool problem with a
cool solution. However, this problem has no clear applications to anything in
the real world, or even in other parts of mathematics. Instead, we are
interested in this problem because it connects seemingly disjoint areas of
mathematics and inspires us to study things that we might otherwise ignore.
We want to finish with some results of the same spirit.
\begin{enumerate}
\item We partition the $n$-dimensional cube and partition into simplices. The
number of simplices must be a multiple of $n!$.
\item We partition regular $n$-gons for $n > 4$. The number of triangles is
divisible by $n$.
\item For a centrally symmetric polygon, the answer is the same as for the
square. This was conjectured by Stein and proven by Monsky in 1990.
\item This seems somewhat paradoxical. Take a polygon and try to dissect it
into triangles of equal areas. There are some polygons for which this can't be
done. An example is the trapezoid with vertices $(0, 0)$, $(0, 1)$, $(1, 0)$,
and $(a, 1)$, where $a$ is not algebraic. This is similar to what we were doing
before.
\end{enumerate}
Now we mention some open problems.
\begin{enumerate}
\item Suppose we have a centrally symmetric polyhedron in any dimension. Is it
true that when we decompose it into simplices, there must be an even number of
them?
\item A polygon is called balanced if for every direction, the vector sum of
edges of that direction is zero. An example is polygons with sides of only two
directions. Triangles are not balanced. A balanced polygon is dissected into
triangles of equal areas, there are an even number of them. This has been
proven only in special cases: rational edges or edges with only two directions.
\end{enumerate}
All of the known results have been done in essentially the same method. It
would be interesting to find a new method to approach this.
\end{document}