12年間ずっと壁に貼ってあった、あのフラクタル

(chriskw.xyz)

2 ポイント投稿者 GN⁺ 2025-05-23 | 1件のコメント | WhatsAppで共有

中学生のときに方眼紙に描いた正方形の複製パターンを12年間壁に貼ったままにしておき、それを wallflower というフラクタルとして分析し、L-System、線形代数、数体系、高次元への一般化にまでつなげている
1つの正方形から始めて、現在の形を上下左右に複製し、次の段階では約 27度回転した方向 に複製する手順が、平面を埋めるフラクタルを生み出す
単純な L-System 規則 R → RLR, L → RLL は似た輪郭を作るが同じ図形ではなく、より一般的な形は Quadratic von Koch island、Quadratic Flake、Minkowski Sausage などとして文書化されている
wallflower は行列 (M=\begin{bmatrix}-2&1\1&2\end{bmatrix}) を底とし、方向ベクトルを数字として使う 行列ベースの数体系 として解釈でき、(\det(M)=-5) が反復ごとに向きを反転させる
3D への一般化は対称性と重なりの問題で不格好になり、4D では条件を満たす行列で orthotopeflower を作れたが、同じ制約のもとでは 1D・2D・4D だけが可能に見える

壁に貼ってあったフラクタルの始まり

中学生のとき、方眼紙に正方形を繰り返し結合して複製する落書きを作り、後で分析しようと壁に貼っておいた
花びらのように広がる構造と、長く壁に貼られていた経緯から、このフラクタルを wallflower と呼ぶ
もともと描いていた手順は次のとおり
- 1個の正方形から始める
- 現在の状態のコピー4つを左、右、上、下に配置する
- 次は現在の状態のコピー4つを、同じ4方向で約 27度時計回り に傾いた位置へ配置する
- 方眼紙が埋まるまで、この2つの配置方法を交互に繰り返す
この手順は Gosper Curve のように、反復すれば平面上の任意の領域を覆うことができ、各中間状態も平面をタイル状に埋められる

L-System とほとんど同じだが異なる輪郭

約1年前、この輪郭は L-System で作れると考えた
使用した規則は90度の右回転 (R) と左回転 (L) だけで構成される
- 開始文字列は (RRRR)
- 各反復で (R \rightarrow RLR)、(L \rightarrow RLL) に置換する
最初の数段階は wallflower と同じ輪郭に見えたが、アニメーションを作って 4回目の反復 から両者がずれることを確認した
違いはコピーの配置方法にある
- 「drag and drop」方式は、3回目の反復のコピーを中心を基準に上下左右へそのまま配置する
- L-System 方式は、コピーを対角方向に配置する
L-System が作る形はすでに各所で文書化されている
- List of fractals の「Quadratic von Koch island」
- Koch snowflake の「Quadratic Flake」
- Minkowski Sausage
- Jeffrey Ventrella の Mandelbrot’s Quartet
壁にあった drag and drop 版の変形は、Google画像検索や Wikipedia を調べても同じ形が見つからなかった
wallflower に合う規則として (L \rightarrow RLR)、(R \rightarrow LLR) を見つけたが、この規則は段階ごとに輪郭を描く向きが 反転する効果 を生む

フラクタルを数える方法

wallflower は原点から外向きに大きくなるので、自然数と格子座標を対応づける方法として見ることができる
中心の正方形を0とし、最初の反復で追加される周囲の4つの正方形に、時計回りで 1、2、3、4 と番号を振る
次の反復では上から下、左から右へ走査して番号を付けることもできるが、この方法は再帰構造とあまり相性がよくない
各花びらが前の反復のコピーであることを使えば、花びらの内部でも花びら同士の間でも、中心から外へ 番号付けを再利用できる
この番号付けでは、5の倍数、(5n+1)、25の倍数などが傾いた格子パターンを作る
理由は各反復の正方形の数が (1, 5, 25, 125, ...) と増えるためである
- 各反復では、前の状態1つにコピー4つを加えて合計 5倍になる
- そのため 5 の冪と 5進表記が構造によく対応する

行列を底として使う数体系

ある数を 5進数の桁のように分解すると、各桁に対応するベクトルを足し合わせて、フラクタル格子上での位置を求められる
たとえば 231 は (200 + 30 + 1) と見なして、それぞれの位置ベクトルを足し合わせて 231 の位置を得る
1桁の値は方向ベクトルとして定義される
- (\vec{0}=(0,0))
- (\vec{1}=(1,0))
- (\vec{2}=(0,1))
- (\vec{3}=(-1,0))
- (\vec{4}=(0,-1))
(10^n) 形の桁値は、当初は偶数・奇数で分かれる条件式で表されていたが、1つの行列を繰り返し適用すれば条件なしで計算できる
使用した行列は次のとおり

[ M=\begin{bmatrix} -2 & 1 \ 1 & 2 \end{bmatrix} ]

この行列は (M^2=5I) となり、2段階ごとに大きさが5倍に整列する
したがって次のように表せる

[ \overrightarrow{(10^n)}=M^n\vec{1} ]

この構造は、スカラーの底とスカラーの数字を使う通常の位取り記数法ではなく、行列の底 と ベクトルの数字 を使う数体系として見られる

determinant が2つのフラクタルを分ける

(M) の行列式は (\det(M)=-5) であり、負の行列式のため反復ごとに空間の向きが反転する
この反転のため、元の番号付けと比べて 20 や 40 のような値の位置が入れ替わって見える
反転を避けるには、正の行列式を持つ行列を選べる

[ M'=\begin{bmatrix} 2 & 1 \ -1 & 2 \end{bmatrix} ]

[ \det(M')=5 ]

(M') は向きを反転させず、数ベクトルを時計回りに回転させ続け、この行列を底として使うと先ほどの L-System 版 が再現される
2つのフラクタルの違いは次のとおり
- wallflower は (\det(M)=-5) の (M) から生まれる
- より一般的な quadratic flake 系は (\det(M')=5) の (M') から生まれる
行列式の絶対値 5 は、各反復でフラクタルの大きさが5倍になる構造と一致している
- 行列式がもっと大きいとコピーの拡大が速すぎて空白ができる
- 行列式がもっと小さいとコピーの拡大が遅すぎて反復同士が重なる
約 27度 という角度は、整数座標、行列式 (\pm5)、ベクトル長 (\sqrt5) という条件から現れる (\langle1,2\rangle) ベクトルに関係している
- このベクトルの角度は (\arctan(2/1)\approx63.43^\circ)
- y軸基準では約27度ずれている

加法規則と桁上がり

ベクトルの加算は展開済みの桁値にはよく合うが、(\vec{2}+\vec{2}\neq\vec{4}) のように通常の数の足し算とは異なる動きをする
1 から 4 までは実際の数字というより、上、右、下、左の方向と考えるほうが自然である
反対方向同士は打ち消し合う
- (\vec{1}+\vec{3}=\vec{0})
- (\vec{2}+\vec{4}=\vec{0})
単位ベクトルの組み合わせを表にすると、一部の加算結果は2桁の値になる
そのため大きな数を足すときは、通常の筆算のように 桁上がり を処理する必要がある
例として (\vec{22}+\vec{1}) を計算すると、(\vec{2}+\vec{1}=\vec{13}) という規則のため結果は 133 になる
この加算体系が一般に機能するかどうかは証明せず、読者による検証に委ねている

3D と 4D への拡張

3D では、1つの立方体から始めて6方向へ複製する「3D plus」構造を考えた
3x3 行列に求める条件は次のとおり
- すべての要素が整数であること
- 各列ベクトルは原点からハミング距離 3 にあること
- 各反復でコピーを6個追加するため、大きさは7倍になり、行列式は (\pm7) であること
条件を満たす 3x3 行列は見つかったが、可視化すると反復が 押しつぶされたような形 になり、前の反復が露出してしまう問題があった
3D plus をもう2つ追加すると空いた部分を埋められ、8つの中心点がねじれた立方体の頂点のように並んだ
より対称的な配置にするには、各列が互いに直交し同じ長さを持つという条件で十分かもしれないが、3D では整数座標条件と両立せず不可能に見える
4D では条件がうまくかみ合う
- 各列ベクトルの成分平方和が 3 であればよい
- 4つの成分のうち3つを (\pm1)、1つを 0 にすることができる
次の 4x4 行列で 4D フラクタルを構成した

[ \begin{bmatrix} 0 & -1 & -1 & -1 \ 1 & 0 & -1 & 1 \ 1 & 1 & 0 & -1 \ 1 & -1 & 1 & 0 \end{bmatrix} ]

この 4D フラクタルを orthotopeflower と呼ぶ
4D の可視化は、(w) の値を固定した 3D スライスとして見るか、7x7 格子の中に 7x7 格子を配置して4次元の窓を表す方法で扱う
31x31x31x31 の表示窓では、3D で見られた過度な押しつぶれなしに外向きへ拡張していくように見える

より高次元と最後のどんでん返し

同じ制約を高次元へ拡張すると、条件を満たす次元は 1D、2D、4D だけのように見える
- 1D は balanced ternary
- 2D は wallflower または quadratic flake
- 4D は orthotopeflower
4D で選んだ行列はクォータニオン (i+j+k) をエンコードしており、そこから底が (i+j+k)、数字が (0,\pm1,\pm i,\pm j,\pm k) である balanced nonary quaternion base を考えられる
このクォータニオン体系が実際に機能するかははっきりせず、より多くの数学を知る未来の自分に託している
バーンアウト後に数学とプログラミングへの興味を取り戻そうとした試みが、古い落書きをフラクタル、数体系、線形代数、高次元へとつながる探究に変えた
最後のどんでん返しとして、記事中の可視化はサムネイルにある実際の壁のフラクタルとは一致していない
- 実際の壁の4回目の反復は、約27度 反対方向 に複製されている
- 当時は同じ方向に傾け続けると軸から外れると思って補正しようとしていたが、(M) の構造はすでに各段階で自動的に補正していた
- Donald Knuth も壁にフラクタルを貼るときに wrong turn をしたことがある、という話で締めくくっている

1件のコメント

GN⁺ 2025-05-23

Hacker Newsのコメント

洞察に富んだ丁寧な記事で、特に3Dビジュアライゼーションがよかった
以前、任意の画像からフラクタルっぽい効果を作ろうとして、再帰的デシメーションをいじって作ったものを思い出した
ここで直接試せる: https://jsfiddle.net/nicobrenner/a1t869qf/
Blursort 2x2を何度か押してフレームを作り、Animateを押せばよい。画像のコピー/ペーストも可能で、バックエンドなしで全部ブラウザ上で動く。モバイルではおすすめしない
- これが3Dでも動くのか気になる
これにハマって、L-systemで“wallflower”を埋める形を作ったようだ
https://onlinetools.com/math/l-system-generator?draw=AB&skip...
考え直すと、これはたぶん別のフラクタルを生成している気もするが、確信はない
- wallflower用の空間充填曲線を見つけた
  https://onlinetools.com/math/l-system-generator?draw=ABCD&sk...
  以前のものはKoch islandを埋める
軽く読める記事だと思っていたが、仕事をしなければならず、一部は流し読みするしかなかった
後で戻ってきていろいろ触ってみるつもりで、本当によくできた記事だ
予想よりはるかに深くて手ごわい記事で、献身ぶりが伝わってくる
著者に聞きたいのだが、今なら子ども部屋の壁には何を掛けることを勧めるのだろうか
- 子育ての専門家ではまったくないが、その瞬間に子どもが情熱や驚きを感じるものに関係しているなら、何でもよいと思う
  記事の終盤に燃え尽きについての段落を少し入れた。私の場合、問題の根は数学とプログラミングに対して抱いていた魅了や好奇心を失ってしまったことにあり、この記事を書くことで、以前は簡単に感じられていた子どものような驚きに再び触れられた
2桁の数同士の算術を確認してみたが、実際に動作する
41+14は12になるだろうと予想した。右に2マスと上に2マスを足すと、右に2マス、上に2マスだからだ
下の長い足し算では、=は同値であることを示すとき、つまり項の並べ替え(1+2=2+1)、数の分解(41=40+1)、1桁の加算(1+4=22)に使い、->はアルゴリズムが桁を与えるとき、<は次の列へ移動するときに使っている
41+14 = (40+1)+(10+4) = 40 + 10 + (1+4) = 40 + 10 + 22 -> 1s digit = 2 < 4 + 1 + 2 = 22 + 2 = 20 + 2 + 2 = 20 + 41 -> 10s digit = 1 < 2 + 4 = 0 -> done == 12
記事には互いに異なる2つの基数体系があり、1つは10, 20, 30, 40が時計回りで、もう1つは反時計回りだ。どちらも1, 2, 3, 4は時計回りだ。上の足し算は、加算表に使われている2つ目の体系、つまり10の位が反時計回りの体系に基づいている
もう一方の体系でも動く。14+21は12になるはずだ
14+21 =10+20+42 ->2 <1+2+4 =13+4 =10+3+4 =10+31 ->1 <1+3 =0 ==12
“middle out”の番号体系をどう思いついたのか気になる
自分で数学の問題を解くとき、こういうひらめきを得たような発想はなかなか思いつけない
- 記事では順序が少し違って見えるが、結局ある時点で、フラクタルが5倍に成長する仕組み、5進法の数体系、記事で言う「螺旋」が互いに噛み合うと気づいたことから始まった
  フラクタルをプログラムでどう描くかもかなり考えたが、自然なやり方は中央から始めて外側へ拡大していくことだった
  Richard Feynmanが頭の片隅にランダムな問題を十数個ほど置いておき、つながりが見えるたびに少しずつ前進させ、ついに1つを解くと、人々は彼が魔法のようにその場で思いついたのだと思った、という逸話がある。今回も少し似ていたが、私はそのレベルには遠く及ばず、十数個ではなく1つの問題についてかろうじてそうできただけだった
以前働いていた場所の壁に、これを大型プリントとして掛けていた
https://raw.githubusercontent.com/cies/haskell-fractal/refs/... [17MB、Githubで申し訳ない]
生成に使ったHaskellコードも入っている: https://github.com/cies/haskell-fractal
特にsharpen関数を思いつく過程が興味深かった。曲線フィッティングには、今はなくなったツールを使った: https://github.com/cies/haskell-fractal/blob/master/fractal....
楽しい小さなプロジェクトだった
「もっと多くの数学を知っている未来の自分に委任することにした」という部分に共感した
どの学位を取るか決めるうえでも、解く必要があったが、地図とインターネット接続が足りず解決できなかった問題リストが大きく影響した。ほとんどは線形代数の問題だった
パターンの式にタイプミスがあるようだ。“Looking closely you might pick up on the pattern”の直後の式は、5**nではなく5**(n/2)、5**(n-1)ではなく5**((n-1)/2)になるべきだ
\overrightarrow{10*4}は[0, 25]だが、元の式では[0, 625]になる
またKnuthのミスについては、YouTubeコメントで、彼のフラクタルは実は正しく、始点と終点を取り違えただけだと言われている。大まかに言えば、そのフラクタルは中央の回転を基準に対称で、まさにその回転をKnuthが間違っていると考えたのだ。いずれにせよフラクタル関連のミスをしたことにはなるので、結論は変わらない
- よく見つけた。式を直した