Birkhoffの再帰定理

同義語:Birkhoffの回帰定理Birkhoff recurrence theorem

概要

Birkhoffの再帰定理(Birkhoff recurrence theorem)とは、コンパクトな距離空間の上の連続写像には、自分のいくらでも近くへ無限回戻ってくる点(再帰点)が必ずあるという定理のことである。より強く、戻る時刻の隙間が有界な一様再帰点があり、どの点の軌道の閉包もそれを含む。証明の鍵は極小集合で、点が一様再帰点であることとその軌道の閉包が極小集合であることは同値であり、測度を使う Poincaré の再帰定理と違って位相だけから従う。多重の再帰は van der Waerden の定理と同値である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: コンパクト空間, 距離空間, Zornの補題

Birkhoffの再帰定理(Birkhoff recurrence theorem)は、コンパクトな距離空間 $X$ の上の連続写像 $T\colon X\to X$ には、自分のいくらでも近くへ無限回戻ってくる点 $x$(再帰点)が必ずあるという定理である。より強く、戻ってくる時刻の間隔が有界になる点(一様再帰点)があり、どの点の軌道の閉包もそのような点を含む。
Poincaréの再帰定理 は不変な有限測度を仮定し、「ほとんどすべての点」が戻ることを示す。Birkhoff の定理は測度を使わず、位相(コンパクト性と連続性)だけから「戻る点がある」ことを示す。鍵は、閉じた不変集合のうちそれ以上小さくできないもの(極小集合)を考えることである。同じ「再帰定理」の名をもつ計算可能性理論の Kleeneの再帰定理 や、時間平均の収束を述べる Birkhoff の エルゴード定理 とは別の定理である。
この記事では、一様再帰点と極小集合の関係(thm-brt-characterization)を証明し、そこから再帰定理(thm-brt-main)を導く。さらに、$k$ 重の位相的な再帰が van der Waerdenの定理 と同値であること(thm-brt-multiple・prop-brt-vdw)を示す。

Poincaré の再帰定理Birkhoff の再帰定理
仮定有限な不変測度、可測な変換コンパクトな距離空間、連続写像
結論ほとんどすべての点が戻る戻る点(一様再帰点)がある
道具測度の有限性極小集合(Zornの補題)

定義

以下、$(X,d)$ を空でないコンパクトな 距離空間、$T\colon X\to X$ を連続写像とし、$T^0=\mathrm{id}$、$T^{n+1}=T\circ T^n$ とする。点 $x$ の 軌道 を $O(x)=\{T^nx: n\ge0\}$、その閉包を $\overline{O(x)}$ と書く。開集合 $U$ について、$x$ が $U$ にいる時刻の集合を
$$ N(x,U)=\{n\ge0: T^nx\in U\} $$
とおく。$\mathbb Z_{\ge0}$ の部分集合 $S$ が 隙間が有界(syndetic)であるとは、ある $L\ge1$ があって、連続する $L$ 個の整数 $m,m+1,\dots,m+L-1$($m\ge0$)のどれにも $S$ の元が含まれることをいう。

再帰点と一様再帰点
  1. $x\in X$ が 再帰点(recurrent point)であるとは、$x$ のどの開近傍 $U$ についても $T^nx\in U$ となる $n\ge1$ が無限個あることをいう。
  2. $x\in X$ が 一様再帰点(uniformly recurrent point)であるとは、$x$ のどの開近傍 $U$ についても $N(x,U)$ の隙間が有界であることをいう。

再帰点であることは $\liminf_{n\to\infty}d(T^nx,x)=0$ と同値である(開球 $\{y: d(y,x)< 1/j\}$ を近傍にとればよい)。一様再帰点では、$N(x,U)$ は $0$ を含み隙間が有界なので無限集合であり、とくに再帰点である。逆は成り立たない(ex-brt-shift)。定義は Bla93 pp. 38–39 のもので、そこでは $X$ はコンパクト Hausdorff 空間である。
不変閉集合(空でない閉集合 $Y$ で $T(Y)\subset Y$)、極小集合(自分以外の不変閉集合を含まない不変閉集合)、極小($X$ 自身が極小集合)の定義は 一意エルゴード性 の定義「不変閉集合と極小性」のとおりとする。$T$ の連続性から $T(\overline{O(x)})\subset\overline{O(x)}$ なので、$\overline{O(x)}$ は $x$ を含む最小の不変閉集合である。

極小集合と一様再帰

極小集合の存在

$X$ の不変閉集合 $Y$ は、極小集合を含む。

鎖の共通部分

$\mathcal F$ を $Y$ に含まれる不変閉集合の全体とし、包含の逆で順序を入れる。$\mathcal F$ の鎖 $(Z_\lambda)$ をとる。有限個の共通部分は鎖の中で最小のものに等しく空でないので、$X$ のコンパクト性から $Z=\bigcap_\lambda Z_\lambda$ は空でない。$Z$ は閉集合で、$T(Z)\subset\bigcap_\lambda T(Z_\lambda)\subset\bigcap_\lambda Z_\lambda=Z$ である。よって $Z\in\mathcal F$ は鎖の上界(包含では下界)であり、Zornの補題 により $\mathcal F$ には包含について極小な元 $M$ がある。$M$ に含まれる不変閉集合はやはり $\mathcal F$ に属するので $M$ に等しく、$M$ は極小集合である。$\square$

証明に距離は使っていない。コンパクトでないと極小集合はないことがある(ex-brt-table の 3 行目)。

一様再帰点と極小集合

$x\in X$ について、次は同値である。

  1. $x$ は一様再帰点である。
  2. $\overline{O(x)}$ は極小集合である。
戻らない点の集合と、近くに留まる時間

$Y=\overline{O(x)}$ とおく。
2 ならば 1。 $U$ を $x$ の開近傍とし、
$$ C=\{y\in Y: \text{すべての } j\ge0 \text{ で } T^jy\notin U\}=Y\setminus\bigcup_{j\ge0}T^{-j}U $$
とおく。$T^{-j}U$ は開集合なので $C$ は閉集合であり、$y\in C$ なら $T^j(Ty)=T^{j+1}y\notin U$ なので $T(C)\subset C$ である。$x\in U$ なので $x\notin C$ であり、$C\ne Y$ である。$Y$ は極小なので $C$ は不変閉集合になれず、$C=\emptyset$、すなわち $Y\subset\bigcup_{j\ge0}T^{-j}U$ である。$Y$ はコンパクトなので、ある $J$ について $Y\subset\bigcup_{j=0}^{J}T^{-j}U$ となる。$m\ge0$ を任意にとると $T^mx\in Y$ なので、$T^mx\in T^{-j}U$、すなわち $m+j\in N(x,U)$ となる $0\le j\le J$ がある。よって $N(x,U)$ は $L=J+1$ で隙間が有界である。
1 ならば 2。 $Y$ は不変閉集合である。$Z\subset Y$ を不変閉集合とし、$x\in Z$ を示す。そうすれば $O(x)\subset Z$ で、$Z$ は閉集合なので $Y\subset Z$ となり、$Y$ は極小である。
$x\notin Z$ と仮定する。$Z$ はコンパクトなので $\delta=d(x,Z)/2>0$ である。$U=\{y: d(y,x)< \delta\}$ とおき、$N(x,U)$ の隙間の幅を $L$ とする。$U$ の点 $y$ は $d(y,Z)\ge d(x,Z)-d(x,y)>\delta$ をみたす。$z\in Z$ を 1 つとる。$T,T^2,\dots,T^{L-1}$ は $z$ で連続なので、$\eta>0$ を、$d(y,z)< \eta$ なら $0\le j< L$ で $d(T^jy,T^jz)< \delta$ となるようにとれる。$z\in Y$ なので $d(T^mx,z)< \eta$ となる $m\ge0$ がある。このとき $0\le j< L$ で $T^jz\in Z$ だから
$$ d(T^{m+j}x,Z)\le d(T^{m+j}x,T^jz)< \delta $$
であり、$T^{m+j}x\notin U$ である。連続する $L$ 個の時刻 $m,\dots,m+L-1$ がどれも $N(x,U)$ に入らず、$L$ の取り方に反する。$\square$

Birkhoff の再帰定理

Birkhoff の再帰定理

$X$ を空でないコンパクトな距離空間、$T\colon X\to X$ を連続写像とする。

  1. 極小集合の点はすべて一様再帰点である。
  2. どの $x\in X$ についても、$\overline{O(x)}$ は一様再帰点を含む。
  3. とくに $T$ は一様再帰点をもち、それは再帰点である。
極小集合を経由する

1:$M$ を極小集合、$y\in M$ とする。$\overline{O(y)}$ は $M$ に含まれる不変閉集合なので、$M$ の極小性から $\overline{O(y)}=M$ である。thm-brt-characterization の 2 ならば 1 により、$y$ は一様再帰点である。
2:$\overline{O(x)}$ は不変閉集合なので、lem-brt-zorn により極小集合 $M\subset\overline{O(x)}$ を含む。1 により $M$ の点は一様再帰点である。
3:2 を $X$ の 1 点に当てる。一様再帰点が再帰点であることは def-brt-recurrent の後で見た。$\square$

2 は、どの点の軌道も、一様再帰点のいくらでも近くを通ることを意味する。Birkhoff は連続時間の流れについて、極小集合に属する運動を再帰的(recurrent)と呼び、その特徴づけ(Bir27 第 VII 章 §7、pp. 198–200)と、任意の運動の極限点の集合が極小集合を含むこと(§8、pp. 200–201)を示した。§8 の証明は Zorn の補題を使わず、空間を細かく分けた小領域のうち軌道が入るものの数を最小にする操作を繰り返して極小集合を作っている。第 VII 章の脚注は、この章の内容が Bir12 などの論文と深く関係すると述べている(Bir27 p. 189)。
測度による別の証明。 再帰点の存在だけなら、測度からも示せる。Krylov–Bogolyubovの定理 により $T$ は不変な Borel 確率測度 $\mu$ をもつ。コンパクトな距離空間は 第2可算空間 なので、Poincaréの再帰定理 の定理「ほとんどすべての点は自分の近くに戻る」により、$\mu$ についてほとんどすべての点は再帰点であり、$\mu(X)=1$ なので再帰点がある。この方法では一様再帰点は得られない。

例

円周の無理回転

$X=\mathbb R/\mathbb Z$、$d$ を円周上の距離、$\alpha$ を無理数として $T(x)=x+\alpha$ とする。円周の回転 の定理「無理回転は極小」により $X$ は極小集合であり、thm-brt-main の 1 によりすべての点が一様再帰点である。たとえば $x=0$、$U=\{y: d(y,0)< \varepsilon\}$ のとき、$N(0,U)$ は $n\alpha$ を最も近い整数との差が $\varepsilon$ 未満になる $n$ の集合であり、その隙間は有界である。

再帰点だが一様再帰点でない点

$X=\{0,1\}^{\mathbb Z_{\ge0}}$ に距離
$$ d(x,y)=2^{-\min\{i: x_i\ne y_i\}}\quad(x\ne y),\qquad d(x,x)=0 $$
を入れ、$\sigma$ を左シフト $(\sigma x)_i=x_{i+1}$ とする。$X$ はコンパクトで $\sigma$ は連続である(記号力学)。$d(x,y)<2^{-n}$ は $x_0\dots x_n=y_0\dots y_n$ と同値である。
有限語を長さの順、同じ長さの中では辞書式の順に並べて
$$ x=0\,1\,00\,01\,10\,11\,000\,001\cdots $$
と全部つなげた点を考える。

  1. $x$ は再帰点である。 $x$ の最初の $n+1$ 文字 $w$ は有限語なので、長さ $|w|$ の語の区画に現れ、さらに $w$ を接頭辞とする長さ $\ell$ の語はどの $\ell>|w|$ でも長さ $\ell$ の区画に現れる。これらの出現位置 $p$ は無限個あり、$d(\sigma^px,x)<2^{-n}$ である。
  2. $x$ は一様再帰点でない。 長さ $\ell$ の区画には語 $0^\ell$ が現れるので、$\overline{O(x)}$ は $0^\infty=000\cdots$ を含む。$\{0^\infty\}$ は $\sigma$ で動かない閉集合であり、$x$ は $1$ を含むので $x\notin\{0^\infty\}$ である。よって $\overline{O(x)}$ は極小でなく、thm-brt-characterization により $x$ は一様再帰点でない。
  3. 一方 thm-brt-main の 2 が保証する一様再帰点は、ここでは $0^\infty$ がその 1 つである。周期点($\sigma^py=y$ となる $p\ge1$ がある点 $y$)はどれも、軌道が有限集合で極小なので一様再帰点である。

多重再帰と van der Waerden の定理

再帰点 $x$ は $T^nx$ が $x$ に近い $n$ をもつ。同じ $n$ で $T^{2n}x,\dots,T^{kn}x$ もいっせいに $x$ に近くできる、というのが多重再帰である。極小集合の上では、これは van der Waerdenの定理 の定理「van der Waerdenの定理」($r$ 色に塗った $\{1,\dots,N\}$ は $N\ge W(r,k)$ なら同色の長さ $k$ の等差数列を含む)から従う。

位相的多重再帰定理

$X$ を空でないコンパクトな距離空間、$T\colon X\to X$ を連続写像、$k\ge1$ とする。ある $x\in X$ と、$n_j\to\infty$ をみたす正の整数の列 $(n_j)$ があって、
$$ T^{in_j}x\to x\quad(j\to\infty,\ i=1,\dots,k) $$
となる。$x$ は極小集合の中から選べる。

色分けと Baire の範疇定理

lem-brt-zorn により極小集合 $M$ をとる。$M$ はコンパクトな距離空間で $T(M)\subset M$ である。
段階 1:どの空でない開集合も多重に戻る。 $V\subset M$ を($M$ の相対位相で)空でない開集合とする。$C=M\setminus\bigcup_{j\ge0}T^{-j}V$ は prf-brt-characterization と同じく閉集合で $T(C)\subset C$ をみたし、$V$ の点を含まないので $C\ne M$、よって極小性から $C=\emptyset$ である。コンパクト性から、ある $J$ について $M=\bigcup_{j=0}^{J}T^{-j}V$ となる。
$y_0\in M$ を 1 つとり、$m\ge0$ に $T^my_0\in T^{-j}V$ となる最小の $j\in\{0,\dots,J\}$ を色として与える。色は $J+1$ 個なので、van der Waerden の定理により、同色の長さ $k+1$ の等差数列 $a,a+n,\dots,a+kn$($n\ge1$)がある。その色を $j$ とし、$y=T^{a+j}y_0$ とおくと、$i=0,1,\dots,k$ で $T^{in}y=T^{j}T^{a+in}y_0\in V$ である。よって
$$ y\in V\cap T^{-n}V\cap\cdots\cap T^{-kn}V\ne\emptyset. $$
段階 2:開稠密な集合。 $\varepsilon>0$ について
$$ G_\varepsilon=\{x\in M: \text{ある } n\ge 1 \text{ で、} i=1,\dots,k \text{ について } d(T^{in}x,x)< \varepsilon\} $$
とおく。各 $n$ について条件をみたす $x$ の集合は $T^{in}$ の連続性から開集合なので、$G_\varepsilon$ は $M$ の開集合である。$M$ の空でない開集合 $W$ をとり、直径が $\varepsilon$ 未満の空でない開集合 $V\subset W$ を選ぶ。段階 1 により $n\ge1$ と $y\in V$ で $T^{in}y\in V$($i=1,\dots,k$)となるものがあり、$d(T^{in}y,y)< \varepsilon$ だから $y\in G_\varepsilon\cap W$ である。よって $G_\varepsilon$ は稠密である。
段階 3:Baire。 $M$ は完備な距離空間なので、Baireの範疇定理 により $\bigcap_{j\ge1}G_{1/j}$ は稠密で、とくに点 $x$ を含む。各 $j$ で $d(T^{im_j}x,x)<1/j$($i=1,\dots,k$)をみたす $m_j\ge1$ がある。

  • $(m_j)$ が有界でなければ、$m_j\to\infty$ となる部分列を $n_j$ とすればよい。
  • $(m_j)$ が有界なら、ある値 $m$ が無限個の $j$ で現れ、$d(T^mx,x)<1/j$ が無限個の $j$ で成り立つので $T^mx=x$ である。このとき $n_j=jm$ とおくと $T^{in_j}x=x$ であり、$n_j\to\infty$ である。
    どちらの場合も求める列が得られる。$\square$

逆に、多重再帰定理から van der Waerden の定理が出る。力学系の定理から組合せ論の定理を導くこの方法は Furstenberg と Weiss が FW78 で展開した(Bla93 p. 33)。

多重再帰から van der Waerden へ

thm-brt-multiple を認めると、次が成り立つ:$\mathbb Z_{\ge0}$ を有限個の色で塗ると、どの $k\ge1$ についても同色の長さ $k+1$ の等差数列 $a,a+n,\dots,a+kn$($n\ge1$)がある。

シフトの軌道閉包

色を $\{1,\dots,r\}$、塗り分けを $c\colon\mathbb Z_{\ge0}\to\{1,\dots,r\}$ とする。$\Sigma=\{1,\dots,r\}^{\mathbb Z_{\ge0}}$ に ex-brt-shift と同じ距離を入れ、シフト $\sigma$ を考える。$c\in\Sigma$ の軌道閉包 $X=\overline{O(c)}$ はコンパクトで $\sigma(X)\subset X$ である。thm-brt-multiple を $(X,\sigma)$ に当てると、$x\in X$ と $n\ge1$ で $d(\sigma^{in}x,x)<1$、すなわち $(\sigma^{in}x)_0=x_0$($i=1,\dots,k$)となるものがある。よって $x_0=x_n=x_{2n}=\cdots=x_{kn}$ である。
$x\in\overline{O(c)}$ なので、$d(\sigma^ac,x)<2^{-kn}$ となる $a\ge0$ がある。これは $c_{a+t}=x_t$($0\le t\le kn$)を意味するので、$c_a=c_{a+n}=\cdots=c_{a+kn}$ となる。$\square$

有限版($\{1,\dots,N\}$ の塗り分けで $N$ が大きければよい)は、この無限版から対角線論法で得られる:どの $N$ にも単色の長さ $k+1$ の等差数列を含まない塗り分け $c_N$ があるなら、各位置の色が最終的に一定になる部分列をとって $\mathbb Z_{\ge0}$ の塗り分け $c$ を作ると、$c$ の単色の等差数列はある $c_N$ の単色の等差数列になり、矛盾する。

反例:仮定を外すと成り立たないこと

thm-brt-main の仮定はコンパクト性と連続性であり、lem-brt-zorn はコンパクト性を使う。1 つずつ外すと結論が成り立たない。

仮定を 1 つ外した反例
外した仮定例成り立たない結論
コンパクト性$X=\mathbb R$、$T(x)=x+1$再帰点がある(thm-brt-main の 3)
連続性下の $X\subset[0,1]$ と $T$再帰点がある(thm-brt-main の 3)
コンパクト性$X=\mathbb R$、$T(x)=x+1$極小集合がある(lem-brt-zorn)

1 行目の確認。 $X$ は完備な距離空間で $T$ は連続だが、コンパクトでない。$|T^nx-x|=n\ge1$ なので、どの $x$ も開近傍 $(x-\tfrac12,x+\tfrac12)$ に $n\ge1$ で戻らず、再帰点はない。
2 行目の確認。 $a_n=1-2^{-n-1}$、$b_n=2^{-n-1}$($n\ge1$)とし、
$$ X=\{0,1\}\cup\{a_n: n\ge1\}\cup\{b_n: n\ge1\}, $$
$$ T(0)=a_1,\quad T(a_n)=a_{n+1},\quad T(1)=b_1,\quad T(b_n)=b_{n+1} $$
とおく。$X$ は $[0,1]$ の有界閉集合(集積点は $0$ と $1$ だけで、どちらも $X$ に属する)なのでコンパクトである。$b_n\to0$ だが $T(b_n)=b_{n+1}\to0\ne a_1=T(0)$ なので、$T$ は $0$ で連続でない。再帰点はない:

  • $0$ の軌道 $a_1,a_2,\dots$ は $[3/4,1)$ にあり、$0$ の近傍 $[0,\tfrac12)$ に入らない。$1$ の軌道 $b_1,b_2,\dots$ は $(0,1/4]$ にあり、$1$ の近傍 $(\tfrac12,1]$ に入らない。
  • $a_n$ の軌道 $a_{n+1},a_{n+2},\dots$ は $a_{n+1}$ 以上なので、$a_n$ の近傍 $(a_n-r,a_n+r)$、$r=a_{n+1}-a_n$ に入らない。$b_n$ の軌道も同様に $b_{n+1}$ 以下にとどまる。

3 行目の確認。 $Y\subset\mathbb R$ を空でない閉集合で $T(Y)\subset Y$ とし、$y\in Y$ をとる。$Y'=Y\cap[y+1,\infty)$ は閉集合で、$y+1=T(y)\in Y'$ なので空でなく、$t\in Y'$ なら $t+1\in Y\cap[y+1,\infty)$ なので $T(Y')\subset Y'$ である。$y\notin Y'$ なので $Y'$ は $Y$ に真に含まれる不変閉集合であり、$Y$ は極小集合でない。よって極小集合は 1 つもない。

コンパクトでも、極小集合の点以外は一様再帰点とは限らない(ex-brt-shift)。thm-brt-main が保証するのは「ある点」であって「すべての点」ではない。
一様再帰点は超フィルターを使っても特徴づけられ、Furstenberg による Hindmanの定理 の証明などに使われる(Bla93 pp. 39–41、pp. 47–48)。

関連項目

参考文献

[1]
George D. Birkhoff, Dynamical Systems, American Mathematical Society(American Mathematical Society Colloquium Publications, Vol. IX), 1927, 第 VII 章 §7 Recurrent motions(極小集合と再帰的な運動、pp. 198–200)、§8(任意の運動の極限点の集合が極小集合を含むこと、pp. 200–201)、第 VII 章の脚注(p. 189)。頁は 1927 年版のもの
[2]
Andreas Blass, Ultrafilters: where topological dynamics = algebra = combinatorics, Topology Proceedings 18 (1993), pp. 33–56, 1993, Furstenberg らの方法(p. 33)、力学系の定義(p. 38)、再帰点と一様再帰点の定義(pp. 38–39)、Theorem 1(pp. 39–41)、Hindman の定理の Furstenberg による証明(pp. 47–48)
[3]
H. Furstenberg, B. Weiss, Topological dynamics and combinatorial number theory, Journal d'Analyse Mathématique 34 (1978), pp. 61–85, 1978
[4]
G. D. Birkhoff, Quelques théorèmes sur le mouvement des systèmes dynamiques, Bulletin de la Société Mathématique de France 40 (1912), pp. 305–323, 1912

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する