フィボナッチ・ワード

幅の異なる2種類の縞だけで、繰り返しのない1次元パターンができる。長さ n の切れ端の種類は n+1 で、回折の明るい点は2つの波数の整数結合に乗る。

なにか

このギャラリーのあちこちにフィボナッチ数列が顔を出す。ヒマワリの螺旋の本数、Glass パターンの相方が 21 番先、Hat の鏡映比 1/φ⁴がその例である。ここでは、その数列を生む語そのものを取り上げる。

フィボナッチ・ワードは、文字 a を ab に、b を a に置き換える操作を繰り返してできる語である。a から始めると a → ab → aba → abaab → abaababa → … と伸びていく。長さは 1, 2, 3, 5, 8, 13 とフィボナッチ数で増え、a の数と b の数もフィボナッチ数で、比は黄金比 φ に近づく。a を長さ φ の縞、b を長さ 1 の縞にすると、2種類の幅の縞だけでできた帯になる。この帯は決して周期的に繰り返さないのに、どこを切り出しても同じ切れ端が別の場所に現れる。この性質が準周期で、フィボナッチ・ワードはペンローズ・Hat・アンマンとビーンカーという2次元の非周期タイリングの、1次元の祖先にあたる。

3つの作り方が同じ語を出す

世代ごとの縞と、その下に数の帳簿（長さ987・aが610・bが377・複雑さp(n)=n+1・φ倍の自己相似のずれ1.2e-10）を書いた図 — 上に世代ごとの縞（第1〜10世代）と第12世代の帯を、下に数の帳簿を置いた

1つ目は置換で、上で見た作り方である。2つ目は切断投影である。傾き 1/φ の直線を整数格子に引き、縦の格子線と横の格子線のどちらを横切ったかを順に読む。式にすると f_k = ⌊(k+2)/φ²⌋ − ⌊(k+1)/φ²⌋ で、0 を a、1 を b と読む。これはアンマン–ビーンカーを作ったのと同じ「高い次元の格子を斜めに切って射影する」作り方の1次元版にあたる。3つ目は自己相似である。縞の境界を φ 倍すると、φ·φ = φ + 1 は ab の長さ、φ·1 = φ は a の長さなので、元の境界にぴったり乗る。

置換の語と切断投影の語は、987 文字すべてで一致した。自己相似は第16世代の 1,598 点で確かめ、ずれは最大でも 1.2×10⁻¹⁰ だった。切断投影の式の添字は4通り試した。置換の語と合うのは k+2 と k+1 の組だけで、ほかの3通りは 0〜3 文字目で食い違う。

非周期の中で、いちばん単純

「決して繰り返さない」を測る物差しが複雑さである。長さ n の切れ端が何種類あるかを数え、p(n) と書く。周期語なら n を大きくしても増えず（ab の繰り返しはいつも 2 種類）、でたらめな語なら最大の 2ⁿ 種類に近い数になる。フィボナッチ・ワードの第14世代（987 文字）で数えると、n = 1〜14 のすべてで p(n) = n + 1 ちょうどだった。非周期であるためには p(n) ≥ n + 1 が要ると知られていて、その最小値をぴったり達成する語は Sturmian 語と呼ばれる。同じ 987 文字の中に bb は現れず、a が3つ続く場所もない。各世代の語から最後の2文字を落とすと回文になる。

縞に光を当てる

第13世代610本のタイルの境界の1次元構造因子S(q)を0からq=12まで描いた図。鋭い点が並び、各点に(m,n)の整数ラベルがつく — 第13世代（610 本）の境界 611 点の構造因子を描いた。明るい点はすべて q = m·q₁ + n·q₂ の整数結合に乗り、q₂/q₁ は φ になる。基本の点のひとつは 2π/(φ+2) にある

Hat の回折像と同じ計算を、1次元の縞に当てる。回折像は点ばかり（純点スペクトル）だが、周期格子なら1つの波数の整数倍で済むところ、ここでは2つの波数 q₁, q₂ の整数結合が要る。しかも q₂/q₁ = φ は無理数なので、m·q₁ + n·q₂ は数直線上に稠密に散らばる。それでも明るいのは小さい整数の組だけである。明るい 16 点すべてが |m|,|n| ≤ 12 の結合に 0.01 以内で乗り、比は φ に 6×10⁻⁶ で一致した。

語の長さ L が有限なので、強い点の両脇 ±2π/L には副極大が出る。副極大は語を長くすると位置が動くが、本物の点は縞を 610 本から 1,597 本に増やしても 10⁻⁴ しか動かない。この違いを使って副極大を除いた。基本の波数 q₁ と q₂ には、残りの点がいちばん多く整数結合に乗る2本を選んだ。

どう作ったか

置換、切断投影、縞の境界、複雑さ、周期の探索、1次元の構造因子を、外部のライブラリを使わずに書いた。構造因子の山は、波数を 6,000 刻みで粗く走査してから、山ごとに細かく登って位置を決めている。複雑さの比較のために周期語とでたらめな語も数えた。長さ 8 の切れ端は、周期語で 2 種類、でたらめな語で 100 種類を超え、フィボナッチ・ワードでは 9 種類だった。

出典

数理: M. Morse, G. A. Hedlund, "Symbolic dynamics II: Sturmian trajectories" (1940)／M. Lothaire, "Algebraic Combinatorics on Words" (2002) 第2章／M. Senechal, "Quasicrystals and Geometry" (1995) 1次元の切断投影と回折。無限に続く語についての定理はこれらの文献によるもので、このページで確かめたのは有限の語（987〜1,597 文字）だけである
親戚: フィロタキシス（黄金角の連分数）・アンマン–ビーンカー（切断投影）・Hat の回折像（構造因子）・ユークリッドリズム（同じ Sturmian 語がリズムにもなる）
生成: generators/fibword.js（fibword.svg 縞と世代・fibword-diffraction.svg 回折）