ヒルベルト曲線

1本の線が正方形を埋め尽くす。「番号が近いなら場所も近い」は定数倍で守られるが、「場所が近いなら番号も近い」はどの曲線も守れない。

なにか

線は 1 次元、面は 2 次元。なのに 1 本の線で正方形を「埋め尽くす」ことができる。1890 年に Peano が式で示し、1891 年に Hilbert が図で描ける形にした。作り方は自己相似で、正方形を 4 つに割って小さい曲線を回して置き、それを繰り返す。次数を上げるほど線は面に近づき、極限では正方形のすべての点を通る。身近には、刺繍やプリント基板の一筆書き、画像の走査順、地図の検索索引（近い場所を近い番号にする）に使われる。

「近さ」は 2 方向ある

16×16を埋める4本の線（ヒルベルト・Moore・蛇行・Z順）と、次数を上げたときの2つの局所性のグラフ — 上＝同じ 16×16 を埋める 4 本の線（番号順に色を薄く）／下＝次数 n を上げたときの「番号が近い→場所が近い」と「場所が近い→番号が近い」の物差し

線でマスに番号をつけるとき、望みは 2 つある。番号が近ければ場所も近い（線をたどれば近くにいる）と、場所が近ければ番号も近い（隣のマスは番号も隣）。この 2 つを、ヒルベルトと、行ごとに折り返す蛇行、ビットを交互に並べる Z 順（Morton）で測った。

前者を守るのはヒルベルトだけだった。全対で |Δp|²/|Δi| の最大をとると、次数 2〜6 で 2.5 → 3.6 → 4.5 → 5.2 → 5.6 と頭打ち（蛇行は 63・Z 順は 3,970 と、マスの数 N とともに伸びる）。ただし「6 に下から近づいている」という読みは誤りだった。曲線そのものの最大値は 6 で、Bauman が 2006 年に証明している（Mathematical Notes 80(5), p.609 の定理 1「ペアノ・ヒルベルト曲線の平方対 1 次の拡大率は 6 に等しい」）。

6 は近づくだけの値ではなく、実際に達する値である。論文は p.611 で t₁ = 23/48・t₂ = 25/48 の 2 点を挙げ、(1/2)² ÷ (25/48 − 23/48) = 6 と書いている。手元の曲線でも確かめた。t を 4 進で有理数のまま展開して p(t) を出すと、p(23/48) = (1/4, 1/2)・p(25/48) = (3/4, 1/2) で、正方形の水平な中心線の上に乗る。比は 6.000000000 になった。次数を上げても 6 に届かないのは曲線の性質ではなく、こちらが k/4ⁿ という時刻しか見ていないからである。23/48 の分母には 3 が入るので、どれだけ次数を上げても格子には載らない。

「Hölder 1/2 の定数」と呼ぶときは、2 乗の側の定数であることを添えないと誤読を招く。|Δp| ≤ C·|Δi|^1/2 の形で書くなら C = √6 ≒ 2.449 になる。Bauman 自身は Hölder という語を使わず、「square-to-linear（平方対 1 次）」と呼んでいる。

後者はどの線も守れない。隣り合うマスの番号差の最大は、ヒルベルト ⌊5N/6⌋・Z 順 (N+2)/3・蛇行 2√N−1（n=3〜7 で式に一致）。つまりヒルベルトがいちばん悪く、蛇行がいちばんよい。1 本の線には端が 2 つしかないので、面を埋めればどこかで隣のマスが遠い番号になる。ヒルベルトはその代わりに「線をたどれば近い」方を定数で守っている。

作り方は 2 経路で照合した。L-system の亀（A → +BF−AFA−FB+, B → −AF+BFB+FA−）とビット演算（番号 d を 2 ビットずつ読んで回転・鏡映）が、次数 1〜5 の 4〜1,024 点で完全一致。全対の最大は 4ⁿ 点の総当たりなので n=6（840 万対）まで。Moore 曲線（次数 n−1 のヒルベルト 4 本を回して閉じる）は最後の点が最初の隣に戻る輪で、一筆書きの刺繍に向く。

→ ドラゴン曲線（同じく 1 本の線が面を埋める。こちらは折り紙から）

→ フィボナッチ・ワード（置換で伸びる、もうひとつの 1 次元）

→ コーラム（一筆書きの、もうひとつの型＝輪をつなぎ替える）

どう作ったか

生成器は generators/hilbert.js で、ヒルベルト曲線は L-system の亀とビット演算の 2 通りに書いて、点列が完全に一致することを確かめてから使っている。対照には蛇行・Z 順・Moore を並べた。平方対 1 次の比は、4ⁿ 点の総当たりで次数 6 まで測っている。連続版の p(t) は、t を 4 進で有理数のまま展開して出した（浮動小数で桁を取ると 26 桁で精度が尽きる）。

出典

数理: D. Hilbert, "Über die stetige Abbildung einer Linie auf ein Flächenstück", Math. Ann. 38 (1891)／G. Peano (1890)／E. H. Moore (1900)／K. E. Bauman, "The dilation factor of the Peano–Hilbert curve", Mathematical Notes 80 (2006), 609–620＝最大が 6 であること（p.609 の定理 1）と、それを達する 2 点 23/48・25/48（p.611）。達成されることは手元でも計算して確かめた（tools/explore/hilbert-dilation-6.js）
親戚: ドラゴン曲線・フィボナッチ・ワード・コーラム・ペンローズ（置換で作る自己相似）
生成: generators/hilbert.js（hilbert.svg 次数 6・hilbert-book.svg 4 本の線と 2 つの局所性）