無理回転のコード化：再帰再生構造∗
秋山茂樹 (Shigeki AKIYAMA, Niigata Univ.)†

概要
無理回転のコード化には様々な角度からの研究がある。ここでは、スツルム列と呼ばれる古典的なコード化を一般化し、単位円周の任意分割に対応するコードを考える。このコードが常に置換規則の逆極限の構造を持つこと、および、その構造を決める置換規則が最終的に周期的となる場合を分類することを示すことができたので報告する (c.f. [2])。

一次元トーラス R/Z を半開区間 [0, 1) と同一視する。回転数 ξ ∈ R \ Qを固定し [0, 1) をI0 ∪ I1 = [0, 1 − ξ) ∪ [1 − ξ, 1)のように二つに分割する。スツルム語は R/Z の無理回転 x 7→ x + ξ のコード化で初期値 µ を決めるとJ(µ)J(µ + ξ)J(µ + 2ξ) . . .と書ける。ここでJ(x) =(0 x ∈ I0
1 x ∈ I1とする。つまり n = 0, 1, 2 . . . について µ + nξ (mod 1) が前半の区間に軌道が入った時は 0、後半に入ったときは 1 としてできる右側無限語である。
A = {0, 1, . . . , k − 1} を k 個の文字の集合とし A∗ を A 上の有限語の全体とする。A∗ は空語 λ を単位元とし、文字列の連結を二項演算とするモノイドとなる。また AN で A 上の右無限語の全体とする。
∗†

English title: ‘Coding of irrational rotation: recursively renewable structure’
白坂政行氏との共同研究

1

C を空でない有限集合とする。モノイド A∗ から C ∗ への準同型 σ で文字の長さが非減少となるものを非負準同型という。非負準同型 σ は生成元 a ∈ A の像 σ(a) ∈ C ∗ \ {λ} を決めることにより定まる。非負準同型 σ の作用は AN から C N に自然に拡張される。置換規則とは A∗ からA∗ への非負準同型である。
フィボナッチ語は {0, 1}N の元で置換規則 σ(0) = 01, σ(1) = 0 の固定点、つまり σ(z) = z を満たす右無限語でσ(0) = 01
σ 2 (0) = 010
σ 3 (0) = 01001
σ 4 (0) = 01001010
σ ∞ (0) = 0100101001001 . . .のようにして簡単に計算できる。
フィボナッチ語は無限語の中の ‘Miss word1 ’ のような存在で多数の異なる分野に現れ名前も少しずつ異なる。たとえば数理物理ではフィボナッチ鎖、数論では Beatty 列、格子のビリヤード軌道を表し切断列とも呼ば√れる。フィボナッチ語はスツルム語でもある。実際、ξ = µ = (3 − 5)/2ととればよい。このようにスツルム語が置換規則の固定点でもある場合置換規則不変と呼ばれる。置換規則不変なスツルム語の完全な記述は次で得られた。
定理 1 (安冨 [9]). 回転数 ξ 、初期値 µ のスツルム語が置換規則不変となるのは以下の条件が満たされるときでありその時に限る:(i) 回転数 ξ が二次無理数で µ ∈ Q(ξ)(ii) ξ 0 > 1, 1 − ξ 0 ≤ µ0 ≤ ξ 0 または ξ 0 < 0, ξ 0 ≤ µ0 ≤ 1 − ξ 0
ここで x0 は x ∈ Q(ξ) のガロア共役である。
本稿では置換規則不変性より弱い性質を導入する。無限語 z ∈ AN が再帰 k-再生性 を持つとは A = {0, 1, . . . k − 1} 上の置換規則の列 {φi } が存在して
φ1
φ2
φ3z = z0 ←− z1 ←− z2 ←− . . .
1R.Tijdeman の受け売り。私にはこのような洒落た表現はできません。

2と書けることとする。ここで zi ∈ AN とする。この φi の取り方は一意的ではない。再帰 k-再生性を持つ語は逆極限 limφ AN の元と見ることがで←− iきる。ただし自明な場合を除くため全ての a ∈ A について φ1 φ2 . . . φm (a)の長さが m → ∞ で発散すると仮定しておく。
一般にスツルム語は再帰 2-再生性を持つ。このことを少し説明しよう。
与えられた無限語 w の長さ n の部分語の個数を pw (n) と書き複雑度という。周期語については pw (n) は有界であり、非周期的であれば pw (n) > nである。スツルム語 w は複雑度最小の非周期語であり、pw (n) = n + 1 を満たす語と特徴づけられる。とくに p(1) = 2 なので A = {0, 1} としてよく、p(2) = 3 より長さ 2 の部分語はちょうど 3 個ある。非周期的となる
ため 00 または 11 のどちらか一方は決して現れないことが分かる。そこでたとえば 00 が禁止とし、0 で始まる語を考えると 01 と 1 の二つのブロックに分割される。これを新たに名前をつけ替えて 01 → 0, 1 → 1 と置換すれば再びスツルム列となる。このような置換操作は何回でも繰り返すことができる。この置換操作の列の同じ操作をまとめて情報を圧縮し加速する (multiplicative coding) と連分数のアルゴリズムが対応する。
詳しい説明は例えば [5] のスツルム列の章を参照のこと。
このように再帰再生性の概念はスツルム列の持っている逆極限の構造を一般に拡張したものである。このような逆極限の構造は自己相似性を持つタイル張りによく見られる。

(a) 椅子タイル(b) 親タイルの構造

上図のタイル張りは椅子タイルと呼ばれており、右のようにタイルを3いくつか組み合わせた親タイルによるタイル張りともみなせる。親タイルは元のタイルと相似である。その組み合わせの方法は一意的である。拡大率を固定したときの親タイルの一意性はタイル張りが非周期的である
ことを示すのに本質的である (Solomyak [8])。図 1 のペンローズタイルも同様な性質を持っている事が知られている (Grünbaum-Shephard [6])。

図 1: ペンローズタイル

半開区間 [0, 1) の任意の k 区間への分割:

0 = ω0 < ω1 < · · · < ωk−1 < ωk = 1.
を考える。一般回転列とは初期値 µ の無理回転 x 7→ x + ξ のコード化でJ(µ)J(µ + ξ)J(µ + 2ξ) . . .と定義される。ただし x ∈ [ωi , ωi+1 ) のとき J(x) = i とする。つまり i番目の区間に x が入ったとき i という文字を割り振るのである。
定理 2 ([2]). 回転数 ξ, 初期値 µ、分割

0 = ω0 < ω1 < · · · < ωk−1 < ωk = 1.に対応する一般回転列は再帰 (k + 1)-再生性を持つ。

4

例 1. 初期値 µ = 0、回転数 ξ = 2−2/3 で分割

0 < 1/3 < 1に対応する一般回転列は再帰 3-再生性を持つ。:

01011011010110110111101101101011011010110110 . . .
= 01 01 1 01 1 01 01 1 01 1 01 11 1 01 1 01 1 01 01 1 01 1 01 01 1 01 1 01 . . .
φ1← 00202002020120202002020020201202020020200202 . . .
= 002 02 002 02 012 02 02 002 02 002 02 012 02 02 002 02 002 02 012 . . .
φ2← 02021220202122020212202021220212202021220202 . . .
ここでは上線でブロックされる様子を表し、その下の行ではそのブロッ
クに {0, 1, 2} の名前を付けている。このように名づける理由は証明に現れる誘導力学系の形による。
測度論的な力学系が与えられたとき Poincaré の再帰性定理により正測度をもつ任意の部分集合 S を考えると S のほとんど全ての点の軌道は再帰的である。従って S への ﬁrst return map により新たな力学系が定義できる。これを誘導力学系という。
初期値 µ = 0 の場合の定理 2 の証明の概略を説明する。

• より小さい区間への誘導力学系が帰納的に無理回転で構成される。
その小区間を [0, ξn ) と書くと ξn+1 の値は [0, ξn−1 ) ' R/ξn−1 Z に働く無理回転 x 7→ x + ξn が初めて [0, ξn ) に入る ﬁrst return の像である。比 ξn+1 /ξn は 負の連分数 (NCF) アルゴリズム» ¼
11x→−xxにより ξ0 = 1 と ξ1 /ξ0 = ξ から順に計算される。

1

ξ=

1a1 −

1a2 −a3 − · · · −

1an −

5

ξn+1ξn• 例 1 のようにブロック化を行う過程は、この小さい無理回転のコード化である。そのコード化は J から帰納的に構成され、[0, ξn ) から A∗ への関数 Jn で記述される。NCF の Ostrowski 数系 と双対 Ostrowski 数系が Jn の不連続点（Jn の像の文字列が変化する点）を記述する。
• 一回目の誘導力学系 [0, ξ1 ) では不連続点が一つ増えるが、n ≥ 2 のとき [0, ξn ) に不連続点数は増加しない。従って不連続点ははじめはk − 1 あるが、以降は高々 k 個であるので、これをコード化すると再帰 (k + 1)-再生性を持つ。
順に誘導力学系を作る様子を記述すると図 2 のようになる。無理回転
は二区間に関する区間交換の力学系とみることができ、その立場での誘導力学系の作り方は図 3 のようである。

図 2: 生成された誘導回転

これで一般回転列は再帰 (k + 1)-再生性を持つことがわかった。したがって一般回転列には A = {0, 1, . . . k} 上の置換規則の列 {φi } が対応する。
次の問題は、どのような場合にこの置換規則の列がいつ周期的にとれるかである。置換規則不変な語は
φφφz ←− z ←− z ←− . . .
であるから最も単純な場合で、一つの置換規則 φ のみで記述される.

6

図 3: ２区間交換の誘導力学系

A 上の置換規則 φ が原始的とは、ある自然数 n があって φn (a) が Aの全ての文字を含むことである。
無限語 x ∈ AN が原始置換的とは原始的な置換規則の固定点の非負準同型による像であることをいう。すなわち B 上の 原始的置換規則 σ お
よび B ∗ から A∗ への非負準同型 ψ があって y = σ(y), x = ψ(y) が成り立つとき x は原始置換的という。
x ∈ AN が再帰 (k + 1)-再生性を持つならば、{0, 1, . . . k} 上の置換規則の列 {φi } により記述される。この列が周期的に取れるならばある自然数 m と ` があって φi+` = φi が i ≥ m で成り立つ。従って σ =φm φm+1 . . . φm+`−1 , ψ = φ1 φ2 . . . φm−1 と置けばよい。σ が原始的であれば x は原始置換的となる。一般回転列ではこの原始的という条件は容易に満たされる。原始置換的な一般回転列を分類しておくのは重要である。
定理 3 ([2]). 回転数 ξ 、初期値 µ で k 個の分割

0 = ω0 < ω1 < · · · < ωk−1 < ωk = 1.に対応する一般回転列が原始置換的になるための必要十分条件は ξ が二次無理数で µ ∈ Q(ξ) かつ ωi ∈ Q(ξ) となること、言いかえると全パラメータが同じ実二次体に属することである。
この定理は、いくつかの知られた結果の拡張になっている。Adamczewski[1] は２区間への分割で µ = 0 の場合に少し条件をつけて証明した。
Berthé-Holton-Zamboni [3] は対応する結果をスツルム列の場合を証明

7

している。この定理 3 の証明は若干込み入っているが概略の第一段階は次のとおり:• 全パラメータが二次体に入る場合、誘導力学系の不連続点は双対
Ostrowski 展開で記述したとき Pisot 単数を底とする β-展開で記述されるのでその周期性は比較的容易に示せる。
• 逆を示すためには以下の Durand [4] および Holton-Zamboni [7] による帰還語に関する結果を用いる。
z = z1 z2 · · · ∈ AN の preﬁx とは z1 z2 . . . zk という形の有限語のことである。z ∈ AN を一様再帰的（どの部分語も無限回あらわれ、その間隔が有界）な無限語とし preﬁx w を固定する。帰還語 y (6= λ) とは z の部分語であって yw に w が先頭と末尾に二回のみ現れる語である。分かりやすく言えば z に w が現れたところで z を分割しブロック化を行ってできるのが帰還語である。例 1 の z で w = 010 としてみると
z = 01011011010110110111101101101011011010110110 . . .
= 01011011010110110111101101101011011010110110 . . .
= 01011011 0101101101111011011 01011011 0101101101111011011 . . .
← 01010101101010102010101011010101020101010110101 . . . (誘導語)の３行目に現れている 010 で始まる上線ブロックが帰還語となる。z の一様再帰性により帰還語の個数は有限なので、帰還語の出現した順に 0, 1, . . .と名前を与えていくと新たな語が生じる。これを誘導語と呼ぶ。この場
合 2 に対応する帰還語は 01011011011 である。誘導語は preﬁx が定まると一つ定まる。preﬁx は無限個あるので誘導語の全体も一般には無限集合である。Durand [4] と Holton-Zamboni [7] はこの誘導語の全体が有限集合をなすことと z が原始置換的であることが同値であることを示した。
この帰還語と誘導語は記号力学系と語の組み合わせ論における重要な道具である。
定理 3 の証明の第二段階は次のとおり:• 一般回転列の十分に長い preﬁx をとるとその帰還語から作られた誘
導語はある３区間交換の誘導力学系のコード化であることを示す。
３区間交換が生じる様子を図 4 に示す。
8

図 4: ３区間交換 誘導力学系• ３区間交換が唯一エルゴード的となるためには、その端点の逆軌道が交わらない (i.d.o.c.) 条件が必要である。
• 不連続点の様子を双対 Ostrowski 展開によって精密にしらべ、preﬁxを十分に長くするとこの条件が満たされることを示す。
• 誘導力学系に生じる３区間交換の区間の長さの比は、（唯一エルゴード性により）preﬁx を定めれば、コードの無限語から一意的に復元される。preﬁx を動かしたときこの比の全体の集合は誘導語の有限性により有限集合をなす。このことを用いるとパラメータがすべて同一の二次体に属することが示せる。
以上のように証明は終了するが、発展としていろいろな問題が考えられる。

• 一般回転列を再帰再生性を持つ語の全体の集合の中で特徴づけられるか。
• 定理 3 を他の力学系に拡張すること。たとえば一般の区間交換力学系など。
• 一般回転列の中で置換規則の固定点になるものを代数的に特徴づけられないか。

9

参考文献
[1] B. Adamczewski,
Codages de rotations et phénomènes
d’autosimilarité., J. Théor. Nombres Bordeaux 14 (2002), no. 2,351–386.
[2] S. Akiyama and M. Shirasaka, Recursively renewable words and codingof irrational rotations, J. Math. Soc. Japan 59 (2007), no. 4, 1199–1234.
[3] V. Berthé, C. Holton, and L.Q. Zamboni, Initial powers of sturmian
sequences, Acta Arith 122 (2006), no. 4, 315–347.
[4] F. Durand, A characterization of substitutive sequences using returnwords, Discrete Math. 179 (1998), no. 1-3, 89–101.
[5] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag,
Berlin, 2002.
[6] B. Grünbaum and G. C. Shephard, Tilings and patterns, W. H. Freeman and Company, New York, 1987.
[7] C. Holton and L.Q. Zamboni, Descendants of primitive substitutions,Theory Comput. Syst. 32 (1999), no. 2, 133–157.
[8] B. Solomyak, Nonperiodicity implies unique composition for selfsimilar translationally ﬁnite tilings, Discrete Comput. Geom. 20(1998), no. 2, 265–279.
[9] S. Yasutomi, On sturmian sequences which are invariant under some
substitutions, Number theory and its applications (Kyoto, 1997),
Kluwer Acad. Publ., Dordrecht, 1999, pp. 347–373.

10