Brouwerの不動点定理

同義語：Brouwer fixed-point theoremブラウワーの不動点定理

概要

動機

区間 $[0,1]$ からそれ自身への連続関数 $f$ のグラフを、正方形 $[0,1]\times[0,1]$ の中に描いてみる。グラフは左の辺 $x=0$ のどこかから出発して右の辺 $x=1$ のどこかで終わり、途中で途切れない。すると、左下の角から右上の角へ引いた対角線 $y=x$ と、グラフはどこかで必ず交わる。交点 $x$ では $f(x)=x$ であり、この点は $f$ で動かない。たとえば $f(x)=\cos x$ は $[0,1]$ を $[\cos1,1]\subset[0,1]$ に写し、$\cos x=x$ となる点 $x\approx0.739085$ がある。
同じことが平面の円板でも起こる。同じ大きさの 2 枚の紙を重ね、上の紙だけをくしゃくしゃに丸めて、下の紙からはみ出さないように置き直す。このとき、上の紙のある点は、丸める前にいた下の紙の点の真上に必ず来る。上の紙の各点を、その真下にある下の紙の点に対応させる写像が、紙からそれ自身への連続写像になるからである。このように「閉円板からそれ自身への連続写像は必ず動かない点をもつ」ことを主張するのが Brouwer の不動点定理である。
本記事では 1 次元の場合を中間値の定理で、2 次元の場合を三角形の分割の色塗りについての Sperner の補題で完全に証明する。一般の次元でも同じ定理が成り立つ。

定理の主張

写像 $f\colon X\to X$ について、$f(x)=x$ を満たす点 $x\in X$ を $f$ の不動点という。$n\ge1$ について
$$ D^n:=\{x\in\mathbb{R}^n\mid\|x\|\le1\} $$
を $n$ 次元の閉球（$n=2$ のとき閉円板）とする（$\|\cdot\|$ は Euclid ノルム）。

Brouwerの不動点定理

$n\ge1$ とする。連続写像 $f\colon D^n\to D^n$ は少なくとも 1 つの不動点をもつ。

証明の所在

本記事では $n=1$（prop-brouwer-fp-dim-one）と $n=2$（thm-brouwer-fp-dim-two）の場合を完全に証明する。一般の $n$ については、主張は Brouwer の 1911 年の論文にある Bro11。下の Sperner の補題の $n$ 次元版（$n$ 次元単体の分割の $n+1$ 色での色塗り）は Sperner の 1928 年の論文で証明されており Spe28、それを使えば prf-brouwer-fp-triangle と同じ論法で一般の $n$ の場合が得られる。ホモロジー群を使う証明は Hat02 Corollary 2.15 にある。

$D^n$ と同相な空間でも同じことが成り立つ。

同相な空間への移し替え

位相空間 $X$ と $Y$ が同相で、$X$ からそれ自身へのどの連続写像も不動点をもつならば、$Y$ からそれ自身へのどの連続写像も不動点をもつ。

$h\colon X\to Y$ を同相写像、$f\colon Y\to Y$ を連続写像とする。$h^{-1}\circ f\circ h\colon X\to X$ は連続なので不動点 $x$ をもち、$h^{-1}(f(h(x)))=x$ である。両辺に $h$ を施すと $f(h(x))=h(x)$ となり、$h(x)$ は $f$ の不動点である。$\square$

たとえば閉じた正方形や閉じた三角形は閉円板と同相なので、それらからそれ自身への連続写像も不動点をもつ。

1次元の場合

閉区間の場合

$a< b$ とする。連続関数 $f\colon[a,b]\to[a,b]$ は不動点をもつ。特に $D^1=[-1,1]$ について thm-brouwer-fp が成り立つ。

中間値の定理による証明

$g(x):=f(x)-x$ とおくと $g$ は $[a,b]$ 上で連続である。$f(a)\ge a$ なので $g(a)\ge0$、$f(b)\le b$ なので $g(b)\le0$ である。中間値の定理により $g(c)=0$ となる $c\in[a,b]$ があり、$f(c)=c$ である。$\square$

動機の段落の「グラフが対角線と交わる」は、この証明の $g$ の符号が左端で $0$ 以上、右端で $0$ 以下であることを言い換えたものである。2 次元では「符号が変わる」という議論がそのままでは使えないので、次節では代わりに数え上げを使う。

2次元の場合：Spernerの補題による証明

三角形とその分割

円板の代わりに三角形で考える。$e_1=(1,0,0)$、$e_2=(0,1,0)$、$e_3=(0,0,1)$ を頂点とする $\mathbb{R}^3$ の中の三角形
$$ T:=\{x=(x_1,x_2,x_3)\in\mathbb{R}^3\mid x_1,x_2,x_3\ge0,\ x_1+x_2+x_3=1\} $$
を使う。$x\in T$ の成分 $x_i$ は、$x$ が頂点 $e_i$ にどれだけ近いかを表す重みである。$e_i$ と $e_j$ を結ぶ辺の上の点は、残りの成分が $0$ の点である。
正の整数 $k$ を固定し、成分がすべて $1/k$ の整数倍である $T$ の点を格子点とする。格子点 $(a/k,b/k,c/k)$（$a,b,c\ge0$、$a+b+c=k$）を頂点とする小三角形
$$ \{(a+1,b,c),(a,b+1,c),(a,b,c+1)\}/k\quad(a+b+c=k-1),\qquad \{(a,b+1,c+1),(a+1,b,c+1),(a+1,b+1,c)\}/k\quad(a+b+c=k-2) $$
によって、$T$ は $k^2$ 個の合同な小三角形に分割される（各辺を $k$ 等分して、辺に平行な線を引いた三角形の格子である）。小三角形の辺の長さは $\sqrt2/k$ である。この分割では、$T$ の内部にある小三角形の辺はちょうど 2 つの小三角形に共有され、$T$ の周の上にある小三角形の辺はちょうど 1 つの小三角形に属する。実際、$k$ 倍した座標で書くと、上の 2 種類の小三角形は $\{w+e_1,w+e_2,w+e_3\}$（$w$ は成分が非負で和が $k-1$）と $\{w'-e_1,w'-e_2,w'-e_3\}$（$w'$ は成分が正で和が $k+1$）である。小三角形の辺 $\{P,Q\}$ は、$\{i,j,l\}=\{1,2,3\}$ として $P-Q=e_i-e_j$ の形をしており、$P_l=Q_l$ である。これを辺にもつ前者の形の小三角形は $w=P-e_i$ のものだけで、これは常に存在する。後者の形のものは $w'=P+e_j$ のものだけで、これが存在する（$w'$ の成分がすべて正になる）のは $P_l\ge1$ のときに限る。$P_l=Q_l=0$ なら辺は $T$ の周の $x_l=0$ の部分にあり、$P_l\ge1$ なら辺の両端以外の点は成分がすべて正なので $T$ の内部にある。

Spernerの補題

Spernerの色塗り

上の分割の格子点に $1,2,3$ のいずれかの色 $\lambda(v)$ を塗る。どの格子点 $v$ についても $v$ の $\lambda(v)$ 番目の成分が正であるとき、すなわち
$$ \lambda(v)\in\{\,i\mid v_i>0\,\} $$
であるとき、$\lambda$ を Sperner の色塗りという。3 つの頂点の色が $1,2,3$ すべてそろった小三角形を全色三角形という。

Sperner の色塗りでは、頂点 $e_i$ には色 $i$ が塗られ（正の成分は $i$ 番目だけ）、$e_i$ と $e_j$ を結ぶ辺の上の格子点には色 $i$ か $j$ が塗られる。内部の格子点の色は自由である。

Spernerの補題

Sperner の色塗りでは、全色三角形の個数は奇数である。特に、全色三角形が少なくとも 1 つある。

扉を数える証明

両端の色が $1$ と $2$ である小三角形の辺を扉と呼ぶ。各小三角形 $\Delta$ について、$\Delta$ の 3 辺のうち扉であるものの個数を $d(\Delta)$ とし、$D:=\sum_\Delta d(\Delta)$ を 2 通りに数える。
小三角形ごとに見る。$\Delta$ の頂点の色が $\{1,2,3\}$ なら扉はちょうど 1 本、色が $1,1,2$ または $1,2,2$ なら扉はちょうど 2 本、それ以外（色 $1$ か色 $2$ の一方が現れない）なら扉は無い。したがって $D$ は、全色三角形の個数を $N$ として $D\equiv N\pmod2$ を満たす。
扉ごとに見る。$T$ の内部にある扉は 2 つの小三角形に共有されるので $D$ に 2 回数えられ、周の上にある扉は 1 回数えられる。よって $D$ は周の上の扉の個数と偶奇が一致する。周のうち $e_2$ と $e_3$ を結ぶ辺の上の格子点の色は $2$ か $3$、$e_1$ と $e_3$ を結ぶ辺の上では $1$ か $3$ なので、そこに扉は無い。$e_1$ と $e_2$ を結ぶ辺の上には $k+1$ 個の格子点が並び、色はすべて $1$ か $2$ で、$e_1$ の色は $1$、$e_2$ の色は $2$ である。$e_1$ から $e_2$ へ順にたどると、色が $1$ と $2$ の間で切り替わる回数は奇数であり（$1$ から始まって $2$ で終わる）、切り替わる箇所がちょうど扉である。したがって周の上の扉の個数は奇数である。
以上より $N\equiv D\equiv1\pmod2$ であり、$N$ は奇数である。$\square$

k=2 の場合

$k=2$ では格子点は 3 頂点 $e_1,e_2,e_3$ と 3 辺の中点 $m_{12},m_{13},m_{23}$（$m_{ij}$ は $e_i$ と $e_j$ の中点）の 6 個、小三角形は $4$ 個である。Sperner の色塗りでは $m_{12}$ は色 $1$ か $2$、$m_{13}$ は $1$ か $3$、$m_{23}$ は $2$ か $3$ に塗られる。たとえば $m_{12}=1$、$m_{13}=3$、$m_{23}=2$ と塗ると、4 つの小三角形の色は $\{e_1,m_{12},m_{13}\}=\{1,1,3\}$、$\{m_{12},e_2,m_{23}\}=\{1,2,2\}$、$\{m_{13},m_{23},e_3\}=\{3,2,3\}$、中央の $\{m_{12},m_{23},m_{13}\}=\{1,2,3\}$ で、全色三角形は中央の 1 個である。扉は $e_1$–$e_2$ 辺上の $m_{12}$–$e_2$ と、内部の $m_{12}$–$m_{23}$ の 2 本で、$D=d(\{1,2,2\})+d(\{1,2,3\})=2+1=3$ は奇数である。

三角形の不動点

三角形の場合

連続写像 $f\colon T\to T$ は不動点をもつ。

Spernerの補題とBolzano–Weierstrassの定理による証明

$f(x)=(f_1(x),f_2(x),f_3(x))$ と成分で書く。$f(x)\in T$ なので $f_i(x)\ge0$、$f_1(x)+f_2(x)+f_3(x)=1$ である。
段階 1（色の塗り方）：各 $x\in T$ について、$x_i>0$ かつ $f_i(x)\le x_i$ を満たす $i$ が存在する。実際、$x_i>0$ となるすべての $i$ で $f_i(x)>x_i$ だとすると
$$ 1=\sum_{i=1}^3f_i(x)\ge\sum_{i:\,x_i>0}f_i(x)>\sum_{i:\,x_i>0}x_i=1 $$
となって矛盾する（$x\in T$ なので $x_i>0$ となる $i$ は少なくとも 1 つある）。そのような $i$ のうち最小のものを $\lambda(x)$ とする。$\lambda(x)$ 番目の成分は正なので、各 $k$ について $\lambda$ を格子点に制限したものは Sperner の色塗りである。
段階 2（全色三角形の列）：lem-brouwer-fp-sperner により、各 $k\ge1$ について $k$ 等分の分割に全色三角形があり、その頂点のうち色 $1,2,3$ のものを $a^{(k)},b^{(k)},c^{(k)}$ とする。これらは互いの距離が $\sqrt2/k$ 以下で、色の定め方から
$$ f_1(a^{(k)})\le a^{(k)}_1,\qquad f_2(b^{(k)})\le b^{(k)}_2,\qquad f_3(c^{(k)})\le c^{(k)}_3 $$
を満たす。
段階 3（極限）：$T$ は $\mathbb{R}^3$ の有界閉集合なので、Bolzano–Weierstrassの定理により点列 $(a^{(k)})$ は $T$ の点 $x$ に収束する部分列 $(a^{(k_j)})$ をもつ。$\|b^{(k)}-a^{(k)}\|\le\sqrt2/k\to0$ なので $b^{(k_j)}\to x$、同様に $c^{(k_j)}\to x$ である。$f$ の連続性により、上の 3 つの不等式で $j\to\infty$ とすると
$$ f_1(x)\le x_1,\qquad f_2(x)\le x_2,\qquad f_3(x)\le x_3 $$
を得る。両辺の和はどちらも $1$ なので 3 つとも等号であり、$f(x)=x$ である。$\square$

円板への移し替え

三角形と円板は同相

三角形 $T$ と閉円板 $D^2$ は同相である。

ゲージ関数による証明

$T$ の重心 $g=(1/3,1/3,1/3)$ を原点に平行移動すると、$T-g$ は 2 次元の部分空間 $W:=\{z\in\mathbb{R}^3\mid z_1+z_2+z_3=0\}$ の中の集合
$$ T-g=\{z\in W\mid -3z_i\le1\ (i=1,2,3)\} $$
になる。$W$ は内積を保つ線形写像で $\mathbb{R}^2$ と同一視できるので、$T-g$ が $W$ の閉単位円板 $B:=\{w\in W\mid\|w\|\le1\}$ と同相であることを示せばよい。
$\mu(z):=\max_i(-3z_i)$ とおく。$\mu$ は 3 つの 1 次式の最大値なので連続で、$t\ge0$ について $\mu(tz)=t\mu(z)$ を満たし、$T-g=\{z\in W\mid\mu(z)\le1\}$ である。$z\in W$、$z\ne0$ なら、成分の和が $0$ なので負の成分があり、$\mu(z)>0$ である。$W$ の単位円周はコンパクトで $\mu$ はその上で正の連続関数なので、最小値 $m>0$ と最大値 $M$ をもち、$m\|z\|\le\mu(z)\le M\|z\|$（$z\in W$）となる。
$h(z):=\dfrac{\mu(z)}{\|z\|}z$（$z\ne0$）、$h(0):=0$ と定め、$h'(w):=\dfrac{\|w\|}{\mu(w)}w$（$w\ne0$）、$h'(0):=0$ と定める。$\|h(z)\|=\mu(z)$、$\mu(h'(w))=\|w\|$ なので $h$ は $T-g$ を $B$ に、$h'$ は $B$ を $T-g$ に写し、直接の計算で $h'\circ h$、$h\circ h'$ は恒等写像である。$0$ 以外では連続関数の積と商なので連続であり、$0$ では $\|h(z)\|\le M\|z\|$、$\|h'(w)\|\le\|w\|/m$ より連続である。よって $h$ は同相写像である。$\square$

2次元のBrouwerの不動点定理

連続写像 $f\colon D^2\to D^2$ は不動点をもつ。

prop-brouwer-fp-triangle により $T$ からそれ自身へのどの連続写像も不動点をもつ。lem-brouwer-fp-triangle-disk により $T$ と $D^2$ は同相なので、prop-brouwer-fp-homeo により $D^2$ でも同じことが成り立つ。$\square$

例と反例

半径の違う円板と正方形

中心 $c$、半径 $r>0$ の閉円板 $\{x\in\mathbb{R}^2\mid\|x-c\|\le r\}$ は $x\mapsto(x-c)/r$ で $D^2$ と同相なので、そこからそれ自身への連続写像は不動点をもつ。閉じた正方形 $[-1,1]^2$ も、prf-brouwer-fp-triangle-disk と同じゲージ関数 $\mu(z)=\max(|z_1|,|z_2|)$ を使った写像で $D^2$ と同相であり、同じ結論が成り立つ。たとえば $f(x,y)=\bigl(\tfrac12\cos y,\ \tfrac12\sin x\bigr)$ は $[-1,1]^2$ をそれ自身に写す連続写像なので、$\tfrac12\cos y=x$、$\tfrac12\sin x=y$ を同時に満たす点がある。

反例：開円板

開円板 $U=\{x\in\mathbb{R}^2\mid\|x\|<1\}$ と $p=(1,0)$ について、$f(x):=\tfrac12(x+p)$ とおく。$\|f(x)\|\le\tfrac12(\|x\|+1)<1$ なので $f$ は $U$ からそれ自身への連続写像である。$f(x)=x$ なら $x=p$ だが $p\notin U$ なので、$f$ は $U$ に不動点をもたない。$f$ は連続で、$U$ は穴の無い円板状の集合であるが、$U$ は閉じていない（コンパクト空間でない）。「閉」の仮定を外すと定理の結論は破れる。

反例：円環と円周

円環 $A=\{x\in\mathbb{R}^2\mid1\le\|x\|\le2\}$ を原点のまわりに角 $\theta$（$0<\theta<2\pi$）だけ回転する写像は、$A$ からそれ自身への連続写像で、不動点は原点だけだが原点は $A$ に属さないので、$A$ 上に不動点をもたない。回転は連続で $A$ はコンパクトであるが、$A$ には穴があり $D^2$ と同相でない（同相なら prop-brouwer-fp-homeo と thm-brouwer-fp-dim-two により回転が不動点をもつはずなので、この例そのものが同相でないことを示している）。単位円周 $S^1$ の回転や対蹠写像 $x\mapsto-x$ も同様である。定理は「コンパクトな図形なら何でもよい」わけではなく、閉円板と同相であること（穴が無いこと）が効いている。

反例：連続でない写像

$f\colon D^2\to D^2$ を、$x\ne0$ では $f(x)=-x$、$f(0)=(1/2,0)$ と定める。$x\ne0$ で $-x=x$ となることはなく、$f(0)\ne0$ なので、$f$ は不動点をもたない。$f$ は $D^2$ からそれ自身への写像だが原点で連続でなく、連続性の仮定を外すと結論は破れる。1 次元でも、$[0,1]$ 上で $x<1/2$ なら $1$、$x\ge1/2$ なら $0$ をとる関数は不動点をもたない。

反例：平面全体

平行移動 $x\mapsto x+(1,0)$ は $\mathbb{R}^2$ からそれ自身への連続写像で、不動点をもたない。$\mathbb{R}^2$ は穴が無く閉集合でもあるが、有界でない。

補足

レトラクトとの同値性と基本群による証明

$D^n$ の境界の球面 $S^{n-1}$ が $D^n$ のレトラクトでない（$D^n$ から $S^{n-1}$ への連続写像で $S^{n-1}$ の各点を動かさないものが無い）ことは、thm-brouwer-fp と同値である。不動点をもたない $f$ があれば、$f(x)$ から $x$ へ向かう半直線が球面と交わる点を $x$ に対応させてレトラクションが作れるからである（レトラクトの記事の命題「Brouwerの不動点定理との同値性」とその証明）。$n=2$ では、基本群について $\pi_1(S^1)\cong\mathbb{Z}$、$\pi_1(D^2)=0$ であることから $S^1$ が $D^2$ のレトラクトでないことが従い、2 次元の場合の別証明になる（基本群の記事の例「円周」、Hat02 §1.1 Theorem 1.9）。本記事の Sperner の補題による証明は、基本群やホモロジー群を使わず、数え上げと点列の極限だけで済む点に特徴がある。

扉をたどって全色三角形を見つける

prf-brouwer-fp-sperner の扉の見方から、全色三角形を具体的に見つける手順も得られる。周の上の扉から $T$ の中へ入ると、入った小三角形が全色三角形でなければ（色が $1,1,2$ か $1,2,2$）、入った扉とは別の扉がちょうど 1 本あるので、そこから隣の小三角形へ出る。小三角形は有限個で、どの小三角形も扉を 2 本までしかもたないので、同じ小三角形に 2 度入ることはなく、この道は全色三角形で止まるか、周の上の別の扉から外へ出る。周の上の扉は奇数本なので、周から入って周へ出る道で組にならない扉が残り、そこから入った道は全色三角形で止まる。$k$ を大きくしてこの手順を行えば、$f$ の不動点の近似が計算できる。

名前と歴史

一般の $n$ についての不動点定理は L. E. J. Brouwer の 1911 年の論文「多様体の写像について」にある Bro11。E. Sperner は 1928 年の論文で、単体の分割の色塗りについての補題（Sperner の補題）を証明し、それを次元の不変性の新しい証明に用いた Spe28。