## Proving Nash’s Theorem (Part 2)

As promised, I will attempt to finish up the rest of the proof for Nash’s Theorem tonight (albeit a few weeks late). Let’s start again with a few definitions from where we left off.

1. A subset of $\mathbb{R}^m$ is compact if the set is closed and bounded. Every sequence in a compact set has a convergent subsequence.
2. The centroid of a simplex $x^0 \cdot \cdot \cdot x^m$ is the average of the its vertices or, in mathematical terms, the centroid is $\frac{1}{m+1} \displaystyle\sum\limits_{i=0}^m x^i$.
3. Now we are set to prove Brouwer’s Fixed Point Theorem which states that a continuous function $f:\bigtriangleup_m \to \bigtriangleup_m$ mapping a transformation of a simplex contains a fixed point $z$ for $z\epsilon \bigtriangleup_m$ such that $f(z) = z$. There are various different proofs of this theorem spread out through mathematical literature (for examples, see here, here, and here). However, I will be following the proof explained by Shosham and Leyton-Brown since the proof uses Sperner’s lemma (and is one of the easier proofs to understand).
1. To begin, let $\epsilon > 0$. We then simplicially subdivide $\bigtriangleup_m$ such that the Euclidean distance between any two vertices in a subsimplex is at most $\epsilon$. We label the vertices in the subsimplex with a labeling function $\lambda(v)$ where $\lambda(v) \epsilon \chi(v) \cap \left\{i: f_i(v) \leq v_i\right\}$(1). For each vertex in the division, $v$, $v_i$ is the $i$th component of the vertex and $f_i(v)$ is the $i$th component of $f(v)$. To ensure that $\lambda(v)$ is well defined, we must show that $f_i(v)$ weakly decreases $v_i$ for all possible $i$. We show this by assuming first the opposite that $f_i(v) > v_i$ for all $i \epsilon \chi(v)$. Given the definition of a standard simplex (all vertices within the simplex is some combination of the components), we know that $\displaystyle\sum\limits_{i=0}^m v_i = 1$. By the definition of $\chi(v)$, a component is greater than zero, $v_j > 0$, if and only if $j\epsilon\chi(v)$. Thus, we can deduce the following rule:

$\displaystyle\sum\limits_{j\epsilon\chi(v)} v_j = \displaystyle\sum\limits_{i=0}^m v_i = 1$

(2)

By our assumption, $f_j(v) > v_j$ for all $j \epsilon \chi(v)$ so we conclude that:

$\displaystyle\sum\limits_{j\epsilon\chi(v)} f_j(v) > \displaystyle\sum\limits_{j\epsilon\chi(v)} v_j = 1$

(3)

Given that $f(v)$ is on the standard simplex, we know that

$\displaystyle\sum\limits_{j\epsilon\chi(v)} f_j(v) \leq \displaystyle\sum\limits_{i=0}^m f_i(v) = 1$

(4)

We have reached a contradiction by Eqs. 3 and 4. Therefore, $\lambda(v)$ is well defined and satisfies Eq. 1 with a non-empty set on the right for every $i\epsilon \chi(v)$.

2. Since we have shown that $\lambda(v)$ is a proper labeling, we know by Sperner’s lemma that a complete labeling exists in the subsimplexes. As we let $\epsilon$ approach zero, we see a convergent sequence composed of the centroids of the completely labeled subsimplexes. We can call the point that the sequence of centroids converges to $z$. As $\epsilon \rightarrow 0$, every point of the completely labeled subsimplex, $p^0...p^m$, will converge to $z$, $p^i \rightarrow z$ where $i = {0, ..., m}$. Thus, we have $f(z) = z$ since $f_i(z) = z_i$ for all $i \epsilon \chi(z)$. This is because we have shown that $f_i(v) \leq v_i$. Since all points of the completely labeled subsimplex converges to $z$, $p^0...p^m = z$. If $f_i(z) < z_i$, then

$\displaystyle\sum\limits_{i=0}^m f_i(z) < \displaystyle\sum\limits_{i=0}^m z_i$

(5)

But we know by definition that

$\displaystyle\sum\limits_{i=0}^m f_i(z) = 1$

(6)

and

$\displaystyle\sum\limits_{i=0}^m z_i = 1$

(7)

so Eqs. 5, 6 and 7 reach a contradiction and $f_i(z) = z_i$ for all $i\epsilon\chi(z)$ and $f(z) = z$. QED

It appears that it has taken longer to write the proof for Brouwer’s theorem than expected. I will finish up the last and final part (where I actually prove Nash’s theorem–hard to believe) in my final blog post for Proving Nash’s Theorem.