二次標準数系によるタイル張りについて
秋山茂樹（新潟大）

概要
筆者は近年、主に Pisot 数系とそこから生ずる相対タイリングに関して考えてきたが、昨年になって、古くからハンガリーの I.Kátai を中心とする数学者の考えていた標準数系というものを学習する機会を得た。そこに生起する様々な問題は、Pisot 数系でのそれと極めて似かよっており、さらに構造が比較的簡単で研究がしやすい対象であることに気がついた。Pisot 数系での問題の方針が少し行き詰まっているところだったので、標準数系で同様な問題を考えることは有益に思われた。実際、Pisot 数系では出来ていないタイプの数系の特徴づけ（定理 5) や、対応するタイルの位相的性質の記述（定理 9)が可能なことが分かってきた。（以下は文献 [1] と [2] の内容およびその発展[3] にかんする解説である。）

1

標準数系の定義と基本的結果
γ を代数的整数、R を Z[γ]/(γ) の完全代表系とする。

定義 1 (数系の定義). 組 {γ, R} が数系をなすとは任意の y ∈ Z[γ] にたいし ai ∈R, (i = 1, . . . , `(y)) が存在してy=`(y)Xai γ i ,ai ∈ R(1)i=0と表示されるときに言う。

R が完全代表系なので容易に分かるように y の表示は存在するならば一意的である。N (·) を絶対ノルムとしたとき N = {0, 1, . . . , N (γ) − 1} とおく。{γ, N } が数系をなすとき特にこれを標準数系という。N は γ のみによって決まるので簡単に γ が標準数系をなすと言うこともある。γ の Z の上の最小多項式を Irr(γ) とかく。γ が標準数系をなすならば、明らかにその共役 γ 0 も標準数系をなす。従って既約な多項式 P (X) があればその根の置換にかんしては標準数系であるか否かは不変である。そこで既約多項式 P (X) が標準数系をなすという言い方も用いる。11

さらに、既約でない多項式での標準数系も考えられる。[14]1

D.E. Knuth は [10] にてコンピュータのアルゴリズムへの応用を視野に負の整数をベースとした進法を考えた。標準数系の起源は明確には分からないのだが、この負数の進法の事まで含むならば、アマチュア数学者を含めて、以前から考えられていたもののようである。
例 1. −n (n = 2, 3, . . . ) は標準数系をなす。たとえば n = 2 の場合−3 = (−2)3 + (−2)2 + (−2)0 = 1101
−2 = (−2)1 = 10−1 = (−2)1 + (−2)0 = 11
1 = (−2)0 = 12 = (−2)2 + (−2)1 = 110
3 = (−2)2 + (−2)1 + (−2)0 = 111
4 = (−2)2 = 100
5 = (−2)2 + (−2)0 = 101
6 = (−2)4 + (−2)3 + (−2)1 = 11010というように全ての整数が符号なしの 0, 1 で表示される。負の数か正の数かは桁数の偶奇性で判定される。

D.E.Knuth [10] の興味深いアイデアはこれをガウス整数にまで広げた点にある。
√
例 2. γ = −1 + −1 は標準数系をなす。実際 N (γ) = 2 ゆえ N = {0, 1} であり
1 = 1
2 = γ(−2 − γ) = γ(γ + γ 2 ) = γ 2 + γ 3 = 1100
3 = 1 + γ 2 + γ 3 = 1101
4 = −γ 4 = γ 4 (1 + γ)2 = γ 4 + γ 6 + γ 7 + γ 8 = 111010000
5 = 1 + γ 4 + γ 6 + γ 7 + γ 8 = 111010001√のように全ての Z[ −1] の元は表示される。
さらに彼はこの数系から双頭の龍（Twin Dragon）と呼ばれる美しいフラクタルタイルを構成できることを注意した。これに関しては §3 で詳しく述べる。
I.Kátai と B.Kovács は二次の標準数系を完全に分類した。彼らの仕事は整数環の元に限った形で述べられているが、少し言い替えると次のように述べることができる。
定理 1 (Kátai & Kovács [8], [9]). 二次の代数的整数 γ の最小多項式を Irr(γ) =x2 + Ax + B とするとき、γ が標準数系をなすことと−1 ≤ A ≤ B,は同値である。

2B≥2「代数的整数がいつ標準数系をなすのか？」という問題は多くの関心を呼んできた。
定理 2 (Kovács [11]). Irr(γ) = xd + pd−1 xd−1 + pd−2 xd−2 + · · · + p0 が 1 ≤ pd−1 ≤pd−2 ≤ · · · ≤ p0 を満たすならば γ は標準数系をなす。
これは簡単だが興味深い結果であり、次を含む。
系 1 (Kovács [11]). γ を代数的整数とする。十分大きな n に対して −n + γ は標準数系をなす。
次の結果は、固定した γ が標準数系（一般に数系）をなすかどうかの計算可能な必要十分条件を与える。
定理 3 (Kovács, Pethö [12]). γ を代数的整数とし、M を Z の部分集合とし、A = maxa∈N |a| とおく。このとき {γ, M} が数系となるための必要十分条件は次の全条件が成立することである。

1. |γ (j) | > 1 が全ての共役で成り立つ。
2. M は 0 を含む Z[γ]/(γ) の完全代表系。
3. 次の有限集合の元が {γ, M} で有限表示をもつ。
¯
¾½
¯ (j)
A¯x ∈ Z[γ] ¯ |x | ≤ (j)|γ | − 1
一体どのような monic 多項式の根がこの条件を満たすのかは一見しても分からないのがこの定理の弱点である。

2

標準数系の新しい十分条件

ここではいかなる monic 多項式が標準数系を与えるのかを別の角度から考察する。まず y ∈ Z[γ] をいかに (1) の形に変形するか考える。γ が標準数系をなすとすれば y ≡ a0 mod γ である。R が完全代表系なのだから a0 は唯一である。次のa1 を知りたければ (y − a0 )/γ ≡ a1 mod γ という計算を行うであろう。以下同様にして ai たちは i = 0, 1, . . . の順に γ での剰余をとっていくと決まる。このような手順で digit が決まっていくので、本稿の「数系」を剰余数系と呼ぶ場合もある。
Pisot 数系は強欲算法により digit を上から順に定めるが、剰余数系は剰余算法で下から順に定まっていくのである。さて γ の次数を d とし最小多項式をIrr(γ) =dXpi xi ,i=03pd = 1とする。任意の α ∈ Z[γ] は

α=d−1Xaj γ j ,aj ∈ Z

j=0と一意的に表示できる。上で述べた逐次剰余を計算して取り除いてゆくアルゴリズムはこの表現を用いると写像

T (α) =q−1X(aj+1 − qpj+1 )γ j ,q = [a0 /p0 ]j=0により表される。ここで [x] は x の整数部分を表す。すなわちもし、Z[γ] が標準数系ならば任意の y ∈ Z[γ] について `(y) ∈ Z≥0 が定まり

y=¸`(y) · jXT (y) の定数項
p0j=0γjとなる。但し T j は T の j 回繰り返しである。さて Irr(γ) の全根の絶対値が 1 より大であるとき γ は拡大的 (expanding) という。次は基本的である。
補題 1 (I. Kátai and I. Kőrnyei [7]). γ が拡大的な代数的整数ならば任意のy ∈ Z[γ] の T の iteration による軌道 (T j (y))j=0,1,... は周期的である。さらに純周期的な軌道を持つ y は有限個である。
ここで周期的というのはある L ∈ Z≥1 があって十分大きい j に対して T j+L (y) =T j (y) の成り立つことであり、純周期的とは全ての j = 0, 1, . . . で同じ式が成立することである。補題 1 により純周期的な元全体のなす有限集合を P とかく。すると P = {0} と γ が標準数系をなすことは同値である。我々の論文 [2] のアイデア
はこの軌道全体を考え、評価関数をうまく選ぶことで P が簡単に記述できる集合の部分集合となることを示すことにある。
定理 4 ([2]). M ∈ Z≥1 とし、

µp0 >

11+M

¶Xd|pj |j=1と仮定する。（ただし、pj が全て零でなければ上の不等式は等号も許す。）このとき γ が標準数系をなすための必要十分条件は
Ã d−1!
d−1X
X
α=εj pd+i−j γ ii=0j=iで εj ∈ [1 − M, M ] ∩ Z なるものが有限表示をもつ事である。

4すなわち、最小多項式の定数項が十分大ならば非常に少ない範囲をテストすれば標準数系か否か判定できるのである。定理 3 はいかなる γ にも適用可能な必要十分条件を示しているのに対し、この定理は全ての場合には適用できない。しかし適用可能な場合には整数演算しか要せず試験する範囲も狭いのでアルゴリズムとしては非常に高速である。この判定法を用いると次のような定性的な主張も導ける。

Pd
Pd
定理 5 ([2]). p2 , . . . , pd−1 , i=1 pi を非負とし、p0 > 2 i=1 |pi | と仮定する。このとき γ は標準数系をなす。pi が全て非零ならば最後の条件は等号成立の場合でもよい。
Pd
この定理の条件のうち、p2 , . . . , pd−1 , i=1 pi を非負とするという部分は d = 3の場合には標準数系となるための必要条件でもある。すなわち、3 次で定数項の大なる標準数系の特徴づけを与える定理となっている。しかし、残念なことに 4 次以上では必要条件ではない。

3標準数系タイル張り√
既に述べたように、Knuth は γ = −1 + −1 にたいし
¯( ∞)
¯X¯
T =ai γ −i ¯ ai = 0, 1¯i=1というコンパクト集合を考えた。定義から容易に分かるように

γT = T ∪ (T + 1)が成り立つ。すなわち二枚のコピーを張り合わせると自分自身と相似となる。また[(T + y)C=√y∈ [ −1]Zも分かるので、T により複素平面は自己相似タイル張りされるのである。このタイルはその形状の美しさから双頭の龍 (Twin Dragon) と呼ばれている。
コンピュータの発達によりこのような美しい図形が実際に図示されるようになったことが、この分野への興味を広げるきっかけとなった。筆者はこれが数学の発展が自己完結的でないことを示しているように思う。オイラーが手計算により多数の数値実験をしたことは良く知られている。いまや、そのような実験はごく簡単にできる。思ってもみないような現象や謎がいくつも見つかりコンピュータによる実験や図示はとても生産的だと思う。

5= 1i1+i-101-1-i-i

図 1: 双頭の龍によるタイル張り
さて、Knuth の考えたタイル張りを一般化しよう。γ を拡大的な代数的整数、その次数を d とする。R を modγ の完全代表系、Φ を Q(γ) の Rd への標準的な埋め込みとする。
¯( ∞)
¯X
¯
T =ai Φ(γ −i ) ¯ ai ∈ R¯i=1と置く。γ は拡大的ゆえ無限和は収束する。
定理 6 (I. Kátai and I. Kőrnyei [7]). T は Rn の compact な集合で[(T + Φ(ω))
Rn =Zω∈ [γ]が成立する。さらに {γ, R} が数系をなすならば上記のタイリングの重なりは測度ゼロである。すなわち異なる ωi ∈ Z[γ], (i = 1, 2) に対してµn ((T + ω1 ) ∩ (T + ω2 )) = 0を満たす。ここで µn は n 次元 Lebesgue 測度である。
この定理は数系に対応するタイル張りは一枚のタイルの平行移動で実現され、タイルどうしの交わりは測度ゼロであることを示しており基本的である。Knuthのタイル張りは自己相似性をもつが、一般には自己アファイン性をもつ。実際、
γ K (K = 1, 2, . . . ) を掛ける操作は Rn の中では固有値が全て 1 より大な行列を掛6ける操作 GK と翻訳され、G1 (T ) =[(T + Φ(y))

y∈Nが成り立つ。Pisot 数系と最大の違いはこの場合タイリングが周期的であることである。これが様々な位相的構造を考える際に問題を簡単にする。
上述の定理は原点が T の内点であることや T = Inn(T ) を含んでいる。筆者は[4] において Pisot 数系の場合に原点が中心タイルの内点であることを先に導くことでタイルの交わりが測度零であることや T = Inn(T ) を導いた。標準数系の場合にもそのような手順で再証明することが可能である。

Pisot 数系と同様の方法で次が示せる。
定理 7 ([1]). deg(γ) = 2 ならば T は弧状連結である。
任意の次数の γ で T は弧状連結であることが期待される。その関係では K.S.
Lau と R. Hui により Pisot 数系における Dynamical Norm 予想 ([5]) の対応物が提起されている。
境界に関しても Pisot 数系同様 ∂(T ) は有限個のグラフ付き自己アファイン集合の合併であろうと予想される。そしてそれを考える際にタイルの内部構造を調べることがとくに重要となる。
標準数系に関し特筆すべきことは Cubic Pisot 数系の内部構造の予想 [5] の対応物が２次標準数系の場合にも存在し、今度は証明できるという事にある。平面のタイル張りだから 3 個のタイルの共通部分を頂点と呼ぶのが自然である。T の頂点の集合を V (T ) と書く。このとき Irr(γ) = x2 + Ax + B とすると定理 8 ([1]). 2A ≥ B + 3 ならば Inn(T ) は無限個の連結成分をもち V (T ) は無限集合である。さらに 2A > B + 3 のとき V (T ) は非加算集合である。
は困難なく Cubic Pisot と同様に証明できる。V (T ) が非可算になるのはいささか病的と思われるかも知れない。しかし実際にはかなり多くの場合にこのような不条理が起きている。いつまともなタイル張りが生ずるのかが問題となる。タイルを

1. V (T ) が有限のとき T を ordinary、
2. V (T ) が可算無限のとき T を strange、
3. V (T ) が非可算無限のとき T を pathologicalと呼ぼう。上の主張から 2A < B + 3 ならば ordinary ではないかと思える。これが [1] における予想であった。筆者は最終的にこの予想を肯定的に示すことができた。

7

定理 9 ([3]). 2A < B + 3 ならば T および Inn(T ) は単連結（従って連結）である。このとき V (T ) は A = 0 の場合 4 個、その他の場合 6 個の元からなる。
A > 0 の場合だけ書くと

P1 = 0.[0(A − 1)(B − 1)], P2 = 0.[0(B − 1)(B − A)],
P3 = 0.[(A − 1)(B − 1)0], P4 = 0.[(B − 1)(B − A)0],
P5 = 0.[(B − 1)0(A − 1)], P6 = 0.[(B − A)0(B − 1)]に対応する点が T の頂点の全体である。但し [a1 a2 · · · aM ] は循環節を表す。さらに ∂(T ) は有限個のグラフ付き自己アファイン集合の合併である。その集合方程式の本質的部分を平行移動を無視し隣接関係のみに注目して書くとG2 (U ) = V ∪ U ∪ V ∪ U ∪ · · · ∪ V( # V = B − A + 1)

G2 (V ) = U ∪ V ∪ U ∪ V ∪ · · · ∪ U( # U = A)となる。とくに γ が総実でないばあいには GK は相似拡大であり、この場合にはHaussdorff 次元も計算できる。κ を x3 − (A − 1)x2 − (B − A)x − B の最大実根とするとlog |κ|dimH (∂(T )) =log |γ|となる。
この主張のもっとも著しい点は単連結性にあるのであって、他の事実は系として自然に導かれる。なお最後の Hausdorff 次元の計算は新しい結果ではない。たとえば [6], [13] 参照。また 2A = B + 3 のとき T が strange かどうかは未解決である。
これにより、２次標準数系の場合にはある程度満足すべき結果を得られた。しかし上述したようにまだ未解決な部分が多い。逆に未解決な問題ばかり押し寄せてきて押しつぶされそうな感じさえするのだが。

参考文献[1] S. Akiyama and J. Thuswaldner, Topological properties of two-dimensional
number systems, to appear in Journal de Théorie des Nombres de Bordeaux.
[2] S. Akiyama and A. Pethő, On canonical number system, to appear in Theoretical Computer Science.
[3] S.Akiyama, Topological structure of fractal tiling generated by quadratic
number system, in preparation.
8[4] 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.
[5] S.Akiyama, Dynamical Norm conjecture and Pisot tiling (Japanese), RIMS
Lecture Notes, 1091 (1999) 241–250.
[6] Sh. Ito, On the fractal curves induced from the complex radix expansion,
Tokyo J. Math, 12 (2) (1989) 299–320[7] I. Kátai and I. Kőrnyei, On Number Systems in Algebraic Number Fields,Publ. Math. Debrecen 41 no. 3–4 (1992) 289–294.
[8] I. Kátai and B. Kovács, Canonical Number Systems in Imaginary QuadraticFields, Acta Math. Hungar. 37 (1981) 159–164.
[9] I. Kátai and B. Kovács, Kanonische Zahlensysteme in der Theorie derQuadratischen Zahlen, Acta Sci. Math. (Szeged) 42 (1980) 99–107.
[10] D. E. Knuth, The Art of Computer Programming, Vol. 2 Semi numerical
Algorithms, Addison Wesley (1998) London 3rd-edition.
[11] B. Kovács, Canonical number systems in algebraic number fields, Acta Math.
Acad. Sci. Hungar. 37 (1981), 405–407.
[12] B. Kovács and A. Pethő, Number systems in integral domains, especially inorders of algebraic number fields, Acta Sci. Math. Szeged, 55 (1991) 287–299.
[13] W. Müller and J. M. Thuswaldner and R. F. Tichy, Fractal Properties ofNumber Systems, preprint.
[14] A. Pethő, On a polynomial transformation and its application to the construction of a public key cryptosystem, Computational Number Theory, Proc.,
Walter de Gruyter Publ. Comp. Eds.: A. Pethő, M. Pohst, H.G. Zimmer andH.C. Williams, 1991, pp 31-44.

Shigeki Akiyama
Department of Mathematics, Faculty of Science
Niigata University,
Ikarashi-2 8050, Niigata
950-2181, JAPANE-mail: akiyama@math.sc.niigata-u.ac.jp
http://mathalg.ge.niigata-u.ac.jp/~akiyama
9