数論的アルゴリズムに付随するタイル張り
秋山 茂樹 (Shigeki AKIYAMA)
新潟大・理 (Faculty of Science, Niigata Univ.)

1

はじめに標準数系および Pisot 数系に自然なモデル化写像を用いることでユークリッド空間のタイル張りが付随する。このタイル張りは、それぞれの数系に固有の数論的なアルゴリズムのある種の基本領域（自然延長とそのマルコフ分割）を記述するのに役立つ。これは記号力学系の数論への重要な応用と見なせる。このような手法をもっと一般に拡張し（まだ実現していないが将来的には連分数アルゴリズムを含めるなど）、その数論への応用を期待するのは数論研究者として自然な立場である。ここではその方向での general nonsense の構成の暗中模索の現段階を論じたい。大風呂敷を広げるのは楽しいが、うまくまとまるかどうかはまだ分からない。

2

数論的アルゴリズムの定義

既に定義からして問題なのだが、とりあえず以下のようなものを考えよう。A を整数の要素からなる n × n 行列で全ての固有値の絶対値が 1 でないとする。このことを A は双曲的であるという。A の Rn への作用を拡大方向と縮小方向に直和分解する。拡大方向の部分空間を LE , 縮小方向の部分空間を LC とする。当然 Rnの元 v は v = vE + vC (vE ∈ LE , vC ∈ LC ) と一意に分解される。LE の適当なノルムを | · |E , 同様に LC のノルムを | · |C とする。

Definition 2.1. 写像 p : Zn → Zn に対して
1. p2 = p
2. 任意の x ∈ Zn に対して |p(x)|E が有界,3. |x|E が有界ならば |x − p(x)|C も有界が成り立つとき p を縮小方向への数論的射影であるという。また A と p の組(A, p) を縮小方向の数論的アルゴリズムという。

1Ã
!
√√
1 1Example 2.1. 双曲的行列 A =について、固有値 ω = 1+2 5 , ω 0 = 1−2 51 0
Ã !
Ã !
ω0ω
, LE = vR, LC = uR となる。このとき,u=で固有ベクトルは v =
1
1
Ã !
x
∈ Z2 に対して
yÃ ! Ã£√ ¤! Ã !
x(−ω 0 x − y)/ 5x√ ¤ =p= £の整数部
y(−x + ωy)/ 5yCと定めると数論的射影となる。ここで [x] は x の整数部分である。
Ã !
x
Example 2.2. 前の例と同じ状況で∈ Z2 に対してyÃ ! Ã!
xxp=yy − [ωx + y]は数論的射影となる事が確かめられる。このアルゴリズムは Z[β]≥0 からそれ自身への写像 x → ωx − [ωx] を自然に拡張したものである。
これらの例でも分かる事だが、数論的射影 p はベクトル空間 Rn から部分空間LC への自然射影にある意味で「近い」けれど異なるもので、離散的な射影である。
この微妙な差が、以下では本質的に重要な役割を果たす。このとき x ∈ Zn に Aをかけ p で射影する操作を繰り返すとp(A(x)), p(A(p(A(x)))), p(A(p(A(p(A(x)))))), . . .と書ける。
以下簡単のためこれを (pA)x, (pA)2 x, (pA)3 x, . . . と表す。以下のことは容易な事実だが基本的である。

Lemma 2.1. x ∈ Zn に対し ((pA)n x)∞
n=1 は周期列となる。
Proof. |(pA)n x|E < B となる。ν = min νi < 1 とおけば|(pA)n x|C = |A(pA)n−1 x − (A(pA)n−1 x − (pA)n x)|C
≤ |A(pA)n−1 x|C + B ≤ ν|(pA)n−1 x|C + B
より|(pA)n x|C ≤ ν n |x|C + B(ν n−1 + ν n−2 + · · · + 1)
2

∞が成り立つことに注意すれば、((pA)n x)n=1 は Zn の有界列であるから周期をもつ。
特に、純周期的な元 x ∈ Zn の全体を P とすれば、（上の証明をよく見れば）有n限集合となる。また A = {x − p(x) | x ∈ p(Z )} は有限集合となる。A の元のことを Alphabet という。
A−k x が p(Zn ) に入る最小の k ∈ {0, 1, . . . , } に対して k − 1 のことを x の次数deg x と呼ぶ。次数 ∞ の元が存在する場合も考えられるが、ここでは次の仮定をおく。

Assumption 2.1. 任意の点 x ∈ Zn に対してある k ∈ {0, 1, . . . } が存在してA−k x ∈ p(Zn ) となる。
このとき x の元は A の元を用いて以下のごとく形式的周期列として展開することができる。

x = Adeg x a1 + Adeg x−1 a2 + · · · +(ai ∈ A)(1)

= a1 a2 . . .

(2)

実際、y = A− deg x−1 x とおけば ai ∈ A が存在してAy − (pA)y=a1A(pA)y − (pA)2 y

=

a2...
A(pA)n−1 y − (pA)n y=an従ってy=A−1 a1 + A−1 (pA)yy=

A−1 a1 + A−2 a2 + A−2 (pA)2 y...
y=A−1 a1 + A−2 a2 + · · · + A−n an + A−n (pA)n y

ここで n を十分大にとれば (pA)n y ∈ P となる。よってx = Adeg x a1 + Adeg x−1 a2 + · · · + Adeg x−n+1 an + A−n z,z∈Pとなる。P = {0} の場合は特に簡単で、全ての x ∈ Zn は有限の長さの Alphabetで展開される。以下記号力学系の言葉を用いる事にする。[17] この展開に現れるA の元からなる有限語の全体は shift の言語の公理を満たすので両側 A シフト
X = X(A, p) が決まる。タイル張りを実行するのに肝心の仮定は次のものである。

Assumption 2.2. X(A, p) は sofic shift である。
3

すなわち、ある有限オートマトンが存在して X(A, p) の元の任意の有限 blockはそのオートマトンにより受理される word として特徴づけられるものとする。たとえば例 2.2 は有限型シフトなので、sofic である。数論的アルゴリズムが sofic か否かは一般的には難しいが重要な問題と思われる。Assumption 2.2 はいささか扱いにくいので、もっと数論的でかつ記述的な公理があるべきだろうが、現状ではやむを得ない。

3

数論的タイル張りの定義

縮小方向の数論的アルゴリズム (A, p) に対して、Assumption 2.1, 2.2 が成立しているとする。x ∈ Zn の形式的展開を

x=∞X

A−i a−i = adeg(x) adeg(x)−1 . . . a0 .a−1 a−2 . . . ,i=− deg(x)P0とすればこの展開は周期的であった。adeg x . . . a0 = i=− deg(x) A−i a−i を x の整数
P∞部分、.a−1 a−2 · · · = i=1 A−i a−i を小数部分と呼ぶ。Zn 全体を小数部分 ω に関して分類することで[Zn =Sωωnという partition を得る。ここで Sω は Z の元で小数部分が ω であるもの全体である。Assumption 2.2 により、follower finiteness（または predecessor fininteness) が成り立つので Sω は平行移動を除いて有限個の種類からなる。ここで既に有限種類の集合によるある種のタイル張りが実現しているわけであるが、そのままでは Sω はコンパクトでさえないし、その形状はよく分からない。ここで次のことを仮定する。

Assumption 3.1. Rn から Rc への自然射影 Φ : v → vc について Φ(Zn ) は Rcで彫密である。
この仮定は c < n ならば generic には成立するし、いままで扱った具体例ではいつでも成立していた。([15], [2], [3]) この仮定の下に、[Φ(Zn ) =Φ(Sω )ωの Rc での閉包をとると

Rc =S[Φ(Sω )ωを得る。この右辺は一般には ω Φ(Sω ) にはならないが多くの場合にこの二つは等しくなる。例えば Sω が局所有限性を満たせばよいが、局所有限でない場合でも、等しくなる場合もあるので少々あらっぽく

4Assumption 3.2.
Rc =[Φ(Sω )ωとここでは仮定しておく。([15], [6]) この場合のコンパクト集合 Tω = Φ(Sω ) がどのような集合かが研究の対象である。この Tω のもっとも重要な性質は

1. Tω はコンパクトで平行移動を除いて有限個である。
2. T は膨張分割原理を満足する。すなわち AT は有限個のタイルの合併である。
([18], [10])
この二つの性質は数論的アルゴリズム (A, p) から自然に導かれる。考えられる問題を上げてみたい。
1. Tω は、内部の閉包と一致するか？
2. Tω は Rc のルベーグ測度の意味で overlapping でないか？
3. T は連結か？
4. T の内部はどのような位相的構造をもつか？
5. ∂(T ) はどのような位相的構造をもつか？
これらの問にたいする答えは Pisot 数系や、標準数系の場合に具体化しても、全面的に解決したものは少なく、多くの未解決問題が残されている。参考文献は多数あるがその一部を文末につけてある。([15], [14], [2], [3], [5], [20]) 最近、問題 2に関しては弱有限性という概念が重要な役割を果たすことが分かってきた。([12],[6])4マルコフ分割との関係

タイル張りは両側 A シフト X(A, p) のマルコフ分割の具体的構成の問題と深く関係する。まず X(A, p) の元に対して前節同様に整数部分、小数部分を定義する。
整数部分に関しては Φ でモデル化することで Tλ を対応させる。ここで λ は空語である。Assumption 3.1 同様に拡大方向への自然射影 Ψ : Rn → Re に関して Ψ(シフトの小数部分) が彫密に埋め込まれていると仮定しよう。すると、前節同様に整数部分 ω 0 で分類することで拡大方向に別種のタイル張り[Re =Ψ(Sω0 )ω0が構成できることが期待される。各タイルを Fω0 と書こう。このとき X(A, p) 上のシフト写像 σ は −Tλ × Fλ の上に自然に幾何学的に実現される。すなわち

5σX(A, p) −−−→ X(A, p)(−Φ,Ψ)(−Φ,Ψ)yy(3)−Tλ × Fλ −−−→ −Tλ × Fλ×Aのような形の図式を考えることが出来る。符号 − はここでは無意味な感じがするが、実は自然な意味を持っていてアルゴリズムを −Tλ × Fλ 上の力学系として具体化する際に役に立つ。実際にはこの両側の集合の部分集合上でほとんど oneto one な写像にでき、これがマルコフ分割を与えていることが分かる場合が多い。
例えば X(A, p) は有限型ならば実際にマルコフ分割となる。実際、Pisot 単数による Pisot 数系のタイル張りは、有限型ならばいままでの仮定の全てを満足するのでマルコフ分割を自然に与える。このことは β 展開の準周期軌道の精密な記述に役立つ。×A というのもずいぶん乱暴な言葉使いであるが正確に記述するには sofic
shift のグラフを具体的に与えなければならないし、digit の受け渡しを詳述するためには多数の記号を要するのでここでは省略する。タイリング力学系に関しては[21], [24],[23]。その数論的応用に関しては [13], [8]。マルコフ分割に関しては [17],[16], [20] などを見よ。
筆者は数論に記号力学系のアイデアが大いに役立つと思う。一般に力学系の研究は測度論的なところがあり、測度零の例外集合などは無視する議論が多い。しかし数論研究者の立場からは整数自体がそもそも測度零の集合であり、無視されてはかなわないとも思うだろう。マルコフ分割についてもこの状況は似ており、分割の境界（測度零）上の記述は力学系研究者の興味をあまり引いていない。しかし、[13] の研究は境界上を含めた研究であり、数論と力学系を結ぶ Breakthroughかもしれない。まだまだ、両者の間に橋を架けるには時間がかかりそうだが、将来性はあるのではないかと思っている。

参考文献[1] S.Akiyama, Pisot numbers and greedy algorithm, ‘Number Theory, Diophantine, Computational and Algebraic Aspects’, ed. by K. Györy, A. Pethö andV.T.Sós, 9–21, de Gruyter 1998.
[2] S.Akiyama and T.Sadahiro, A self-similar tiling generated by the minimal
Pisot number, Acta Math. Info. Univ. Ostraviensis 6 (1998) 9–26.
[3] S.Akiyama, Self affine tiling and Pisot numeration system, ‘Number Theory
and its Applications’, ed. by K. Györy and S. Kanemitsu, 7–17 Kluwer 1999.

6

[4] S.Akiyama, Cubic Pisot units with finite beta expansions, ‘Algebraic Number
Theory and Diophantine Analysis’, ed. F.Halter-Koch and R.F.Tichy, 11–26,
de Gruyter 2000.
[5] S. Akiyama and J. Thuswaldner, Topological properties of two-dimensional
number systems, Journal de Théorie des Nombres de Bordeaux 12 (2000)
69-79.
[6] S. Akiyama, On the boundary of the tiling generated by Pisot numbers, toappear in Journal of Math. Soc. Japan.
[7] P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals, preprint.
[8] M. Furukado and S. Ito, The quasi-periodic tiling of the plane and Markov
subshifts. Japan. J. Math. (N.S.) 24 (1998), no. 1, 1–42.
[9] W.L. Gilbert, Fractal geometry derived from complex bases, Math. Intelligencer 4 (1982) 78–86.
[10] K. Gröchenig and A. Haas. Self-similar lattice tilings. J. Fourier Anal. Appl.,
1 (1994) 131–170.
[11] M.Hata, On the Structure of Self-Similar Sets, Japan J. Appl. Math. 2 (1985)
381–414[12] K.-H. Indlekofer, I. Kátai and P. Racsko, Some Remarks on Generalized Number Systems, Acta Sci. Math. (Szeged) 57 (1993) 543–553.
[13] S. Ito and Y.Sano, On periodic β-expansions of Pisot Numbers and Rauzy
fractal, preprint.
[14] I. Kátai, Number Systems and Fractal Geometry, preprint[15] I. Kátai and I. Kőrnyei, On Number Systems in Algebraic Number Fields,Publ. Math. Debrecen 41 no. 3–4 (1992) 289–294.
[16] R.Kenyon and A.Vershik, Arithmetic construction of sofic partitions of hyperbolic toral automorphisms. Ergodic Theory Dynam. Systems 18 (1998)
357–372.
[17] D.Lind and B.Marcus, An introduction to symbolic dynamics and coding,Cambridge Univ. Press 1995.
[18] J. C. Lagarias and Y. Wang, Self-affine tiles in Rn . Adv. Math. 121 (1996)
21–49.
7

[19] W. Müller, J. M. Thuswaldner and R. F. Tichy, Fractal Properties of Number
Systems, Periodica Math. Hungar., to appear.
[20] B.Praggastis, Markov partition for hyperbolic toral automorphism,
Ph.D.Thesis, Univ. of Washington, 1992.
[21] G.Rauzy, Nombres Algébriques et substitutions, Bull. Soc. France 110 (1982)
147-178.
[22] R. Strichartz and Y. Wang, Geometry of Self-Affine Tiles I, Indiana Univ.
Math. J., 48 (1999) 1–23.
[23] B.Solomyak, Dynamics of self-similar tilings. Ergodic Theory Dynam. Systems
17 (1997), no. 3, 695–738.
[24] W.P.Thurston, Groups, Tilings and Finite state automata, AMS Colloquium
lectures, 1989.
[25] A. Vince, Digit Tiling of Euclidean Space. In Directions in mathematical quasicristals, pp. 329–370. Amer. Math. Soc., Providence, RI, 2000.
[26] Y. Wang Self-affine tiles. Advances in wavelets (Hong Kong, 1997), pp. 261–282, Springer, Singapore, 1999.

8