文献あり

空間充填曲線の構成

690

これは物工/計数 Advent Calendar 2022 の 20 日目の記事です．

計数工学科 3 年のクマー ( @kuma_program ) と申します．
今の私がインターネット上に公開する文章は競技プログラミングについてのことがほとんどなのですが，今日は競プロに関係のない数学について書いていきたいと思います．

連続写像，全単射写像について

以下では単位区間を $I = [0, 1]$ , 単位正方形を $S = [0, 1] \times [0, 1]$ で表します．また選択公理も仮定しておきます． $I$ から $S$ への全単射が存在するのは非直感的な集合論の結果の一つです．それでは $I$ から $S$ への連続な全単射は存在するでしょうか？この疑問を解決するのが以下の補題です．

$X$ をコンパクト空間， $Y$ をハウスドルフ空間， $f : X \to Y$ を連続な全単射とする．このとき $f$ は同相写像である．

$f$ は連続な全単射であるから， $X$ の閉集合の $f$ による像が $Y$ の閉集合であることを示せばよい． $C \subset X$ を $X$ の閉集合とすると， $X$ はコンパクトであるから $C$ もコンパクトである． $f$ の連続性からその像 $f (C)$ もコンパクトで， $Y$ はハウスドルフ空間であるから $f (C)$ は閉である．(証明終)

ここから以下を得ることができます．

$I$ から $S$ への連続な全単射は存在しない．

$f : I \to S$ が連続な全単射であると仮定する． $I, S$ はコンパクトハウスドルフ空間であるから補題 1 より $f$ は同相写像である．一方で $I$ から $\frac{1}{2} \in I$ を除くと連結性を失うが， $S$ から任意に 1 点を除いても連結性を保つので $I$ と $S$ は同相ではない．これは矛盾である．(証明終)

それでは単射性を諦めた場合はどうなるでしょうか． $I$ からの連続像とは $S$ 内のパスですから，それの $S$ における測度は直感的には $0$ になりそうなものです．よって $I$ から $S$ への連続全射を作るのは厳しそうに思えます．しかしそのような直感に反して次が成り立ちます．

$I$ から $S$ への連続な全射写像が存在する．

$I$ から $S$ への連続な全射写像のことを空間充填曲線と呼びます．ここからは空間充填曲線の具体的な構成について書いていきます．このような曲線には様々なものが考えられますが，今回はそのうちの 1 つであるペアノ曲線について書いていきます．

空間充填曲線の構成

以下はこの記事のみにおいて用いる記号や用語です．

線分

$p, q \in S$ に対し $L (p, q) = {(1 - t) p + t q ∣ t \in [0, 1]}$ と表し， $p$ と $q$ を結ぶ線分と呼ぶ．

折れ線

$C \subset S$ が $s \in S$ を始点， $t \in S$ を終点とする折れ線であるとは，
$S$ における有限長の点列 $v_{0} = s, v_{1}, \dots, v_{n} = t \in S$ が存在して $C = ⋃_{k = 1}^{n} L (v_{k - 1}, v_{k})$ が成り立つことをいう．始点と終点のことをまとめて端点とよぶ．

空間充填曲線を構成する前に， $S$ 内の折れ線の列 $(C_{n})_{n = 0, 1, \dots,}$ であって $C_{n}$ の端点が $(\frac{1}{2 \cdot 3^{n}}, \frac{1}{2 \cdot 3^{n}}), (1 - \frac{1}{2 \cdot 3^{n}}, 1 - \frac{1}{2 \cdot 3^{n}})$ であるようなものを以下のように帰納的に構成します :

$C_{0} = {(\frac{1}{2}, \frac{1}{2})}$ ．
$n \geq 1$ の場合． $C_{n - 1}$ を $\frac{1}{3}$ 倍に縮小したもの 5 個と，それを $y$ 軸に関して反転させたもの 4 個を図のように交互に並べる．隣り合った $C_{n - 1}$ の端点どうしのうちいくつかを図のように線分で結び，全体として 1 つの折れ線になるようにする．これを $C_{n}$ とする．
図において， $C_{n - 1}$ を $\frac{1}{3}$ 倍に縮小した図形も $C_{n - 1}$ と表記している．また $C_{n - 1}$ を左右反転させた図形は $C_{n - 1}^{'}$ と表記している．赤や緑の点は $C_{n - 1}, C_{n - 1}^{'}$ それぞれの端点である．

!FORMULA[69][-2145492130][0] の構成． $C_{n} (n \geq 1)$ の構成．

具体的な $C_{n}$ の形状は以下の図のようになります．( $n \geq 3$ の図は描くのが大変だったので省略しました．見たい方は"ペアノ曲線"などで検索すると見つかると思います)

!FORMULA[72][-549657587][0]の形状 $C_{n} (n = 0, 1, 2)$ の形状

折れ線の列 $(C_{n})$ が得られましたが，このままでは $C_{n}$ を $I$ からの連続像とするにはやや不便なので， $C_{n}$ を少し伸ばした曲線 ${\tilde{C}}_{n}$ を以下で定義します : $C_{n}$ に線分 $L ((0, \frac{1}{2 \cdot 3^{n}}), (\frac{1}{2 \cdot 3^{n}}, \frac{1}{2 \cdot 3^{n}})), L ((1 - \frac{1}{2 \cdot 3^{n}}, 1 - \frac{1}{2 \cdot 3^{n}}), (1, 1 - \frac{1}{2 \cdot 3^{n}}))$ をつなげて ${\tilde{C}}_{n}$ とする． $(0, \frac{1}{2 \cdot 3^{n}}), (1, 1 - \frac{1}{2 \cdot 3^{n}})$ をそれぞれ ${\tilde{C}}_{n}$ の始点と終点とする．

さらに $n \in Z_{\geq 0}$ について連続写像 $f_{n} : I \to S$ を以下を満たすように定めます (以下を満たすような $f_{n}$ の定め方は一意に存在します)：

$f_{n} (I) = {\tilde{C}}_{n}$ ．
$f_{n} (0) = (0, \frac{1}{2 \cdot 3^{n}}), f_{n} (1) = (1, 1 - \frac{1}{2 \cdot 3^{n}})$ ．
$f_{n}$ は単射である．
任意の $t \in I$ について， ${\tilde{C}}_{n}$ の始点 $(0, \frac{1}{2 \cdot 3^{n}})$ から $f_{n} (t)$ まで折れ線に沿って辿るとその経路長は $3^{n} t$ である．

!FORMULA[94][-1472264107][0] の構成． ${\tilde{C}}_{2}, f_{2}$ の構成．

平たく言えば折れ線 ${\tilde{C}}_{n}$ の上を等速度で動くように $f_{n} (t)$ を定めるということです．

$f_{n}$ の定め方から以下の命題を示すことができます．
表記の簡略化のため， $1 \leq i, j \leq 3^{n}$ を満たす $n, i, j \in Z_{\geq 0}$ に対して， $S_{n} (i, j) = [\frac{i - 1}{3^{n}}, \frac{i}{3^{n}}] \times [\frac{j - 1}{3^{n}}, \frac{j}{3^{n}}]$ と書くことにします．

任意の $n \in Z_{\geq 0}, 1 \leq i, j, \leq 3^{n}$ について，
$f_{n}^{- 1} (S_{n} (i, j)) = f_{n + 1}^{- 1} (S_{n} (i, j)) = \dots = f_{m}^{- 1} (S_{n} (i, j)) = \dots$
が成り立ち，これは長さが $\frac{1}{9^{n}}$ の 1 つの閉区間になっている．(証明略)

この命題 4 を用いると命題 5 を示すことができます．

直径

$(X, d)$ を距離空間とする．空でない有界な部分集合 $A \subset X$ の直径を $sup_{x, y \in X} d (x, y)$ で定め， $diam (A)$ で表す．

任意の $t \in I$ に対して， $(f_{n} (t))_{n}$ は $S$ 内のコーシー列となっている．従って $S$ 内に収束先 $f (t) = lim_{n \to \infty} f_{n} (t)$ が存在する．またこの収束は $t \in I$ によらず一様である．

各 $n \in Z_{\geq 0}$ について $⋃_{1 \leq i, j \leq 3^{n}} S_{n} (i, j) = S$ であることに注意する．以下の条件を満たす添字の組の列 $((i_{n}, j_{n}))_{n = 0, 1, \dots}, 1 \leq i_{n}, j_{n} \leq 3^{n}$ をとる：

$\forall n \in Z_{\geq 0}, f_{n} (t) \in S_{n} (i_{n}, j_{n})$ ．
$S = S_{0} (i_{0}, j_{0}) \supset S_{1} (i_{1}, j_{1}) \supset \dots \supset S_{n} (i_{n}, j_{n}) \supset S_{n + 1} (i_{n + 1}, j_{n + 1}) \supset \dots$

このような $i_{n}, j_{n}$ が存在することは補題 4 から従う(詳細は省略する)．各 $n \in Z_{\geq 0}$ について $f_{n} (t), f_{n + 1} (t), \dots, \in S_{n} (i_{n}, j_{n})$ であり， $diam (S_{n} (i_{n}, j_{n})) = \frac{\sqrt{2}}{3^{n}} \to 0$ であるから $(f_{n} (t))_{n}$ はコーシー列である．

$S$ はコンパクトであるから $(f_{n} (t))_{n}$ の収束先 $lim_{n \to \infty} f_{n} (t)$ が存在し，これを $f (t)$ とおく．任意の $n \in Z_{\geq 0}$ について列 $(f_{n} (t), f_{n + 1} (t), \dots)$ は $S_{n} (i_{n}, j_{n})$ 内のコーシー列でもあるから， $f (t) \in S_{n} (i_{n}, j_{n})$ である．よって $| f_{n} (t) - f (t) | \leq diam (S_{n} (i_{n}, j_{n})) = \frac{\sqrt{2}}{3^{n}} \to 0 (n \to \infty)$ であり，この収束は $t$ によらない．(証明終)

折れ線の列の極限として写像 $f : I \to S$ を得ることができました．さらに次が成り立ちます．

$f : I \to S, t \mapsto lim_{n \to \infty} f_{n} (t)$ は連続である．

各 $f_{n}$ は連続で， $f$ はその一様収束極限であることから従う．(証明終)

全射性の証明

あとは $f$ が全射であることを示せば空間充填曲線を構成できたことになります．証明の前に次の補題を紹介します．

$(X, d)$ を距離空間とする．また $K_{1} \supset K_{2} \supset \dots \supset K_{n} \supset \dots$ は $X$ の空でないコンパクト部分集合の減少列であって， $lim_{n \to \infty} diam (K_{n}) = 0$ を満たすとする．
このとき $| ⋂_{n = 1}^{\infty} K_{n} | = 1$ である．また各 $n$ について $x_{n} \in K_{n}$ であるならば，点列 $(x_{n})_{n \in Z_{\geq 0}}$ は $⋂_{n = 1}^{\infty} K_{n}$ の唯一の元に収束する．

$x, y \in ⋂_{n = 1}^{\infty} K_{n}$ とすると $diam (K_{n}) \geq d (x, y)$ である．一方 $lim_{n \to \infty} diam (K_{n}) = 0$ より $d (x, y) = 0$ , よって $x = y$ である．これは $| ⋂_{n = 1}^{\infty} K_{n} | \leq 1$ を意味する．
各 $n \in Z_{> 0}$ について $x_{n} \in K_{n}$ であるとする．各 $n_{0} \in Z_{> 0}$ に対して $(x_{n_{0} + n})_{n \in Z_{\geq 0}}$ は $K_{n_{0}}$ 内のコーシー列であり， $K_{n_{0}}$ はコンパクトであるから，収束先 $lim_{n \to \infty} x_{n_{0} + n} \in K_{n_{0}}$ が存在する．一方 $lim_{n \to \infty} x_{n_{0} + n} = lim_{n \to \infty} x_{n}$ でもあり， $n_{0} \in Z_{> 0}$ は任意であるから $lim_{n \to \infty} x_{n} \in ⋂_{n = 1}^{\infty} K_{n}$ である．(証明終)

$f$ の全射性を証明しましょう．

$f$ は全射である．

$(x, y) \in S$ を任意に取る．以下の条件を満たす添字の組の列 $((i_{n}, j_{n}))_{n \in Z_{\geq 0}}, 1 \leq i_{n}, j_{n} \leq 3^{n}$ をとる(存在性の証明は省略)：

$(x, y) \in ⋂_{n \in Z_{\geq 0}} S_{n} (i_{n}, j_{n})$ ．
$S = S_{0} (i_{0}, j_{0}) \supset S_{1} (i_{1}, j_{1}) \supset \dots \supset S_{n} (i_{n}, j_{n}) \supset S_{n + 1} (i_{n + 1}, j_{n + 1}) \supset \dots$

$I_{n} = f_{n}^{- 1} (S_{n} (i_{n}, j_{n})) \subset S$ とおくと，補題 4 および $i_{n}, j_{n}$ の取り方から $I = I_{0} \supset I_{1} \supset I_{2} \supset \dots$ が成り立ち，各 $I_{n}$ は長さ $\frac{1}{9^{n}}$ の閉区間である．補題 7 より $⋂_{n \in Z_{\geq 0}} I_{n}$ の唯一の元 $t \in ⋂_{n \in Z_{\geq 0}} I_{n}$ が存在する． $I_{n}$ の定義と補題 4 より $m \geq n$ に対して $f_{m} (t) \in S_{n} (i_{n}, j_{n})$ が成り立つ．よって $f_{n} (t)$ の収束先は $f (t)$ は $⋂_{n \in Z_{\geq 0}} S_{n} (i_{n}, j_{n})$ の元である．補題 7 よりこの収束先は $(x, y)$ に一致する．(証明終)

以上で空間充填曲線を構成することができました．

この曲線を図に描いてみたいところですが，少なくともその全貌を描こうとすると $S$ を覆いつくしてしまうので，何が何だか分からない絵になりそうです．

応用

こんな不思議な曲線が存在したところで工学的な応用なんてあるのか？と思っていましたが，実際に空間充填曲線そのものが使われることはないようです．いかんせん形状が複雑すぎて([1]によるといたるところ微分不可能だそうです)実在する物体をその形にしたりするようなことが絶望的なのだと思います．

ただし上の証明で用いたように折れ線を細かくしていくとやがて正方形全体を覆うようになるという発想自体は画像処理などの分野で用いられるようです[1]．

おわりに

個人的な話になりますが，この記事を執筆した経緯について書きたいと思います．
私がいま履修している幾何学の授業で，ある日空間充填曲線の話が少し紹介されていて，そんなものがあるのかと興味をもちました．そしてその具体的な構成を調べようとしたのですが，どのウェブサイトも折れ線の極限として空間充填曲線が得られるとしか書いておらず，それがどういった意味での極限なのか，また全射性はどうやって保証されるのかがなかなか理解できずにいました．色々考えて自分でなんとか練りだしたのがこの記事にある証明です．
特にどこかにある記事をまとめたりしたわけでもないので，何か間違いや説明が至らない点があると思います．遠慮なくコメントなどで指摘して下さると嬉しいです．

応物アドカレの記事は面白いものばかりで，記事を読むことが最近の毎日の楽しみになっています．企画者と執筆者のみなさんにとても感謝しています．この記事が誰かの暇つぶしにでもなったら私は満足です．

ここまで読んで下さってありがとうございました．