標準数系の分類に関する最近の進展
秋山 茂樹 (AKIYAMA Shigeki)
新潟大・理 (Faculty of Science, Niigata Univ.)

1

はじめに標準数系とは剰余数系の一つであり、主にハンガリーの数学者たちが中心となって研究してきたものである。最近数年、新しいアイデアや論文が次々発表され、分類問題が大きく進んでいる。その状況を概説する。

2標準数系の定義

標準数系に関して一昨年の数理研でも講演し、その講究録 [7] に歴史的事項や入門的説明が書かれているので初めてこの話題を読むかたはまずそちらを参照されたい。ここでは、A.Pethő [17] により一般化された標準数系の定義を述べる。まずモニックな整係数多項式 P (x) ∈ Z[x] を考える。

P (x) =dX

pi xi ,

pd = 1i=0

P (x) は必ずしも既約とは仮定しない。P (x) の複素数体での根は全て絶対値が 1より大であるとき P (x) は拡大的という。当然、剰余環 R = Z[x]/(P (x)) は整域とは限らないが任意の R の元は d 次の多項式による代表元をもつ。いいかえるとZ-加群としては
R ' Zdとなる。つまり R の元は次数 d の多項式で表せるのだが、当然この際その係数はいくらでも大きいものが必要となる。標準数系は次の自然な問いからはじまるといってよい。

R の代表元を取り替えて（次数は気にしないで）係数を有界にとれるか？つまり、次数でなく高さ (Height) を上からおさえられるか。
R の元 α = x (mod P (x)) で生成されるイデアルを (α) と書く。容易に分かる
ように Z-加群としては
τ : R/(α) ' Z/p0 Z1である。このことから、上の問いを制限して次のような問題を考えることが自然である。

R の代表元を取り替えて、その係数を Z/p0 Z の一つの完全代表系にできるか？
特に、{0, 1, . . . , |p0 | − 1} にできるか？
この最後の問の答えが肯定的であるような P (x) は標準数系を定義するという。
P (x) が標準数系を定義するならば、任意の R の元 ξ を {0, 1, . . . , |p0 | − 1} を係数とする多項式として表すアルゴリズムが存在する。実際

ξ=MX

ai xi(mod P (x))

i=0=M
X

ai αi(1)i=0だから、a0 を知りたければ ξ を α で割った余りを計算する。{0, 1, . . . , |p0 | − 1}は完全代表系なのだから a0 の定め方は一意である。a0 が定まれば a1 を知るには(ξ − a0 )/α を α で割った余りを考えればよい。以下同様である。このような手順ゆえに標準数系は剰余数系とも呼ばれる。
写像 T : R → R を T (ξ) = (ξ − a0 )/α で定める。ただし ξ = ξ (mod α) とすると a0 ≡ τ (ξ) (mod p0 ) である。(1) の第一の表示法ではこの T は次のように表示される。
· ¸¶
d−1 µXa0T (ξ) ≡ai+1 − pi+1xi (mod P (x))
p0i=0
ここでは ad = 0 としている。整数演算のみで記述されるのでこのほうが使いやすい。次は基本的である。

Proposition 2.1 ([5], [12]). P (x) が拡大的ならば、任意の ξ ∈ R の軌道
ξ, T (ξ), T 2 (ξ), . . .
は循環する。すなわちある正整数 M, L があって n ≥ M ならば T n (ξ) = T n+L (ξ)
が成立する。

P を T によって純循環する元 ξ ∈ R の集まりとする。すなわち
P = {ξ ∈ R | 0 < ∃M ∈ Z ξ = T M (ξ)}としよう。命題 2.1 と同様な証明で P (x) が拡大的ならば P は有限集合であること、およびその大きさの評価ができる。容易にわかるように P = {0} であることと P (x) が標準数系を定義することは同値である。また、簡単なことだがp0 > 0は、P (x) が標準数系を定義するための必要条件である。というのは p0 < 0 だとP (x) に正の根があることとなるので負整数の (1) の形の表示は不可能であるからである。

2

3

標準数系の新しい判定法

ここまでの事は P (x) が既約の場合には講究録 [7] で述べられている。既約でない場合でもほぼ同様の議論ができると気付いたのは多少の進歩である。以下、もっと本質的な進歩についてのべたい。
P (x) が拡大的であっても、標準数系を定義するか否かは難しい問題である。2次の場合には [13], [14], [9] が完全に決定していたが、3 次以上の場合には、非常に部分的な結果以外ないという状態が約 20 年間続いた。この状態を破ったのが、
H.Brunotte [8] および 私と A.Pethő の共同による [3] である。[3] については以前の講究録 [7] で結果を述べているので詳しくは省略するが要するに P (x) の定数項が大きいときは問題が易しくなるという主張である。一方、[8] では次の事実が証明された。ここでは同値な形で [5] に従って記述しよう。まず T ∗ (x) = −T (−x)と置く。

Theorem 3.1 ([8], [5]). R の部分集合 K が存在して次の 3 つの性質を持つならば P (x) は標準数系を定義する。
(i) 0, 1, −1 ∈ K(ii) T (K) ∪ T ∗ (K) ⊂ Ki(iii) ∩∞i=0 T (K) = {0}この定理 3.1 の非常に優れた点は、P (x) が拡大的であるなら K が実際には有限集合として構成され、そのアルゴリズムは非常に高速なところである。P (x) が標準数系を定義するか否かを手計算でも容易に判定できる場合が多い。A.Pethő は
この K のことを ‘機知の集まり1 (set of wittiness)’ などと呼んでいる。アルゴリズムの形で述べれば• K1 = {0, 1, −1} とおき n = 2 とする。
• Kn = Kn−1 ∪ T (Kn−1 ) ∪ T ∗ (Kn−1 ) を計算する。
• もし Kn = Kn−1 ならば次のステップに進む。もしそうでないなら、n をn + 1 として前のステップに戻る。
• Kn の全ての元 ξ に対してある自然数 m があって T m (ξ) = 0 となるか否か確かめる。となる。(1) の整数表示を用いればこの計算は整数ベクトルの簡単な演算の組み合わせである。
この定理は非常に画期的なものなのに [8] では補題として述べられている。H.Brunotte
はまだ会ったことがないけれど慎み深い人物と思う。新事実の最初の証明は非常
1‘機知の集合’ では語感を失う感じがするのでこう訳したい。

3

に込み入っていることが多いけれど、この定理 3.1 の証明もかなり込み入っている。フォローできるけれどどうやって思いつくのか分からない。また、この第二ステップが有限回で終了するかの記述もなされていなかった。(これは [5] で証明された。）Brunotte はこの定理の応用として高次でも非零の係数が 3 個の多項式
P (x) について、いつ標準数系を定義するのかを調べている。定理の汎用性に比べ、実際に応用した範囲は随分狭い感じがする。そのことは、その後の展開でより一層明らかになってくる。
オートマトンの名人芸をもつ J.Thuswaldner と K. Scheicher は、私と Pethő の仕事 [3] に影響を受けて、高次の標準数系の分類問題に乗り出した。([19]) 一方、私はそんな事情はつゆ知らず中国の武漢大学 (Wuhan Univ.) の饒 輝2 (Rao Hui)と同じ問題に取りかかっていた。([5]) この二つの論文は方法こそ全くといって良いほど異なるが到達点は似かよっており、研究時期も近い。二つの論文に共通する結果は次のものである。

Theorem 3.2. P (x) =Pd

i=0 pi xiが次の不等式を満たすとき標準数系を定義する。

(i) p2 ≥ 0, p3 ≥ 0 . . . , pd−1 ≥ 0(ii) p1 + p2 + · · · + pd ≥ 0(iii) p0 > |p1 | + |p2 | + · · · + |pd |これは [3] に予想として述べられていたものである。この結果に関しては、[19]の方に先取権がある。おそらく数ヶ月の差であるが彼らがこの結論に到達し論文化する方が早かった。私と Rao Hui は、彼らと独立に結果を得ていたのだが、プレプリントをもらって驚いたものである。ただ、我々の結果の方が若干適用範囲が広く、視点方法が全く異なり論文にしても問題なさそうなので少し安心した。
J.Thuswaldner と K. Scheicher のアイデアはこの標準数系において加法を記述するオートマトンが強支配条件

p0 > |p1 | + |p2 | + · · · + |pd |(2)の仮定の下では記述が簡単になる事である。一方 Rao Hui と私のアイデアは、M.Hollander が別の数系に対して博士論文で用いたに対するアイデアをうまく適用する事である。その主な部分は、数系に対してある記号力学系を対応させ、その上で左右のシフトを繰り返し用い背理法による議論を行う点にある。
二つの論文は見かけは全く別ものだが、じっくり比較するとアイデアに似たところがあることが分かってきた。さらに、[19] のアイデアと H.Brunotte のアイデアを融合することで我々は [5] において定理 3.1 の非常に見通しのよい証明を得た。
2

ちょっと変かもしれないが Rao や Hui ではあまりに短いので、友人は彼を呼ぶとき、姓の饒Rao と名の輝 Hui を連結してラオフイまたはラオヘイと発音している。まさに天才であまりに理解力が高いのでいつも驚かされる。また無類の文学好きで日本文学にも通じていてこちらが恥ずかしくなるほどの知識の持ち主である。西洋式だと Hui Rao かもしれないが、関係者一同慣れているので以降アジア式姓名順で呼ぶ。

4

分かってみると物事は非常に単純なことが多いが、この証明は全くあきれるほど簡単であるので紹介しよう。以下の証明が決定版になることは疑いないと思う。

Proof of Theorem 3.1. そのような K が存在すれば全ての Z[α] の元が (1) の表示を持つことを示そう。さて a ∈ Z[α] が (1) の表示を持つことは、ある自然数 m が存在して T m (a) = 0 と同値であった。x が (1) の表現を持つと仮定し、y ∈ K とする。 x + y が (1) の表示を持つことを示そう。この事と K の性質 (i)から Z[α] の全ての元が (1) の表示を持つことを示すのは容易である。さて a, b を{0, 1, . . . , |p0 | − 1} の元で a ≡ τ (x) (mod p0 ), b ≡ τ (y) (mod p0 ) を満たすとする。
すると a + b < |p0 | ならばT (x + y) =x+y−a−b= T (x) + T (y),α

また a + b ≥ |p0 | ならばT (x + y) =x + y − a − b − |p0 |= T (x) − T (−y) = T (x) + T ∗ (y)αとなること3 が確かめられる。これを繰り返せばある自然数 m があって T m (x) = 0
だから
T n (x + y) = T k1 T k2 . . . T kn (y)となる。ここで T kj は T または T ∗ である。K の性質 (ii) より右辺は再び K に属する。従って K の性質 (iii) よりある m が存在して T m (x + y) = 0 となる。
従って K がうまく取れる場合には、P (x) が標準数系を定義するか否かは簡単になる。例えば次の支配条件を満たすならば記述はとても易しい。

p0 ≥ |p1 | + |p2 | + · · · + |pd |(3)

そして、それが Theorem 3.2 の証明の基礎ともなるのである。そのことを次節で説明しよう。

4

記号力学系的なアイデア

既に述べたように、[5] では、M.Hollander [10] の記号力学系的なアイデアを援用した。R を Z-加群とみたとき基底 {1, α, α2 , . . . , αd−1 } をもつ。ここで次の基底

3

この場合 x, y は α で割り切れないので a, b は正である。よって T (−y) = (−y − (|p0 | − b))/αであることに注意すればよい。

5

変換を考える。
  w1
pd0 ...
  0w2  pd−1 pd  w3  = pd−2 pd−1 pd   ..   .  wdp1

p2

...
...
0..
.

p3


01
0 α 
 2 
0 α .
  ..  . ...
...
...

. . . pd−1 pdαd−1

この基底 {w1 , w2 , . . . , wd } 自体は自然なもので [8], [3], [19] にすでに使用されているし、[9] の ‘Clearing Algorithm’ にもそのアイデアは発見できる。写像 ι : Zd → RPdを ι(z1 , z2 , . . . , zd ) = i=1 zi wi とし、シフト写像 σ : Zd → Zd をσ(z1 , z2 , . . . , zd ) = (z2 , z3 , . . . , zd+1 )と置く。但し"Pzd+1 = −di=1 zi pd−i+1#p0とする。すると次の可換図式が成立する。
σZd −−−→ Zdιιyy(4)R −−−→ RT

つまり (R, T ) の力学系が (Zd , σ) の記号力学系に翻訳されたのである。しかし、このままでは使用する文字が有限個ではない。しかし標準数系の判定には P のみが必要であり、ここに制限すれば、有限文字を用いたものとなる。さらに zd+1 は0 ≤ z1 pd + z2 pd−1 + · · · + zd p1 + zd+1 p0 < p0 ,の関係を満たす唯一の整数であるが、この表示はシフトとの関係で都合がよい。この式を見れば支配条件 (3) の下では zi (i = 1, . . . , d) が絶対値 1 以下ならば zd+1Pdもそうであることは明らかである。さらに K = { i=1 zi wi | |zi | ≤ 1} は Theorem
3.1 の条件 (i)(ii) を満たすことが上の可換図式をみれば容易に検証できる。すな
わちTheorem 4.1. 支配条件 (3) を満たすとき
S = {ξ ∈ R | ξ =dX

zi w i|zi | ≤ 1}

i=1のすべての元が表示 (1) をもてば P (x) が標準数系を定義する。

6

が言える。さらに、P に話を制限し、zi の最大値、最小値に注目して議論を行えば、様々な興味深い主張がえられる。Theorem 3.2 もこの方法で証明される。さらにたとえばTheorem 4.2. P (x) が拡大的で (3) を満たしさらに係数 pk が負で、それを除き非負としよう。すると P (x) が標準数系を定義することとXpki ≥ 01≤ki≤dは同値である。ということも証明できるのである。これは [19] には見られない [5] の新しい型の議論である。

5

高次の標準数系の分類にむけてすでに述べたように P (x) が標準数系を定義するか否かは 2 次の場合には [13],[14] と [9] 4 により行われた。その結果は簡明で P (x) = x2 + p1 x + p0 が標準数系を定義することは−1 ≤ p1 ≤ p0 , p0 ≥ 2と同値というものである。当然、この結果を 3 次以上の場合に拡張しようという試みは多数あったと想像される。しかしこれは見かけより複雑な問題で私の意見
では、Hopeless にみえる。部分的な進歩はある。最近 [6] では、’ 機知の集まり’ Kを構成する方法で、多数の標準数系になる場合、および、ならない場合を記述した。残念なことに K の濃度は一様に有界ではないように思われる。このような状況でも通用する良いアイデアが要求されている。
少々妥協して支配条件 (3) の下で問題を考えてみる。この場合には Theorem 4.1
により R の 3d 個の元の軌道だけみれば判定は可能である。さらに強支配条件 (2)のもとではTheorem 5.1. 強支配条件 (2) 下では
S = {ξ ∈ R | ξ =dX

zi w izi ∈ {0, 1}}i=1のすべての元が表示 (1) をもてば P (x) が標準数系を定義する。
が成り立つので 2d 個の元の軌道を調べる問題となる。従ってこの場合は頑張れば不等式で必要十分条件を記述することができる。これを三次、四次で実行した
4独立な仕事のようで、優先権に関しては論文に記述がない。

7

結果が [19] にある。ただし、四次の場合でも少なくとも最初の原稿では間違いがあった。
（これは本人に知らせてある。）実際この計算は、固定した P (x) なら易し
いが P (x) 全体を同時に扱うとなると、不等式や論理式数十個を同時に扱う必要が生じる。計算がコンピュータにのらないので長期の神経戦となる。とても五次は扱えない。そこで、私と Rao Hui は [5] で標準数系となるためのさらに細かい必要条件を導き、それを併用することで場合分けの数をかなり減少させた。これが功を奏して四次、五次でも見やすい結果を以下のように導くことに成功した。もちろん、不等式や論理式の述べ方は一通りではないので別表示もあり得る。この計算は六次以上でも可能だが、高次を調べると統一的な理解に近づくという様子がみえないのでここらで引き返すのが妥当かも知れない。

Theorem 5.2. P (x) = x3 + p2 x2 + p1 x + p0 が p0 > 1 + |p2 | + |p1 | を満たす整数係数多項式とする。このとき P (x) が標準数系を定義するための必要十分条件はp2 ≥ 0 かつ 1 + p2 + p1 ≥ 0 である。
Theorem 5.3. P (x) = x4 + p3 x3 + p2 x2 + p1 x + p0 が p0 > 1 + |p3 | + |p2 | + |p1 |を満たすとする。P (x) が標準数系を定義するための必要十分条件は次の 5 個の条件を満たすことである。
p3 ≥ −1
p2 ≥ −1
p3 + p2 ≥ −1
1 + p3 + p2 + p1 ≥ 0
p3 = −1 ⇒ p1 ≤ −2
Theorem 5.4. P (x) = x5 + p4 x4 + p3 x3 + p2 x2 + p1 x + p0 が p0 > 1 + |p4 | + |p3 | +|p2 | + |p1 | を満たすとき P (x) が標準数系を定義するための必要十分条件は次の 5個の条件を満たすことである。
p2 + p4 ≥ 0
1 + p4 + p3 + p2 + p1 ≥ 0
p4 < 0 ⇒ p4 = −1, p3 ≥ 1, p1 ≤ −2
p3 < 0, p1 + p4 ≥ 0 ⇒ p3 ≥ −1, p2 ≤ −2
p3 < 0, p1 + p4 < 0 ⇒ p4 ≥ 0, p4 + p3 ≥ 0
さて A.Pethő は次の面白い予想をしている。

Conjecture 5.1. P (x) が標準数系を定義するならば、1 + P (x) も標準数系を定義する。

8

今までの全ての計算結果が、この予想を支持している。もし、この予想を仮定すれば、p0 が十分大きいなどという支配条件なしで 次のような興味深いことが言える。

Theorem 5.5. Pethő 予想が正しいとする。このとき二変数自然数値関数 f が存在して P (x) = x3 + p2 x2 + p1 x + p0 が標準数系を定義するための必要十分条件は
p2 ≥ 0 かつ 1 + p2 + p1 ≥ 0 かつ p0 ≥ f (p2 , p1 ) である。
Theorem 5.6. Pethő 予想が正しいとする。このとき三変数自然数値関数 f が存在して P (x) = x4 + p3 x3 + p2 x2 + p1 x + p0 が P (x) が標準数系を定義するための必要十分条件は次の 6 個の条件を満たすことである。
p3 ≥ −1p2 ≥ −1
p3 + p2 ≥ −1
1 + p3 + p2 + p1 ≥ 0
p3 = −1 ⇒ p1 ≤ −2p0 ≥ f (p3 , p2 , p1 )実際、P (x) が標準数系を定義するならば自然数 n に対して n + P (x) も標準数系を定義するはず。しかし、n を大にとれば n + P (x) は支配条件を満たすのでTheorem 5.2 や Theorem 5.3 が有効となる。従い、Theorem 5.2, 5.3 にでてくる条件以外は、もはや P (x) の持つべき必要条件はないはずである。
高次でも同様のことが言える。つまり、Pethő 予想が真なら Theorem 5.1 の要求する必要条件と、p0 の最小値を与える関数 f を決定すれば分類終了となる。いいかえると、標準数系の分類は簡単な部分と難しい部分に綺麗に分割できる。
このようなわけで Pethő 予想は標準数系の分類における今後のもっとも重要な予想と言えるだろう。私は f の具体的な記述は三次でも非常に難しいのではないかと感じる。[6] など今までの計算結果から f がある種のカオス的な様相を持っているように思うのである。もしそうだとすれば Theorem 5.5 や 5.6 の形が望みうる最終形に近いのかもしれない。

参考文献[1] S. Akiyama, On the boundary of the tiling generated by Pisot numbers, toappear in Journal of Math. Soc. Japan 54 (2002).
[2] S. Akiyama and J.M.Thuswaldner, Topological properties of two-dimensional
number systems, Journal de Théorie des Nombres de Bordeaux 12 (2000)
69–79.
9[3] S. Akiyama and A. Pethő, On canonical number systems, Theoretical Computer Science 270 (2002) 921-933.
[4] S. Akiyama and J.M. Thuswaldner, On the topological structure of fractal
tilings generated by quadratic number systems, submitted.
[5] S. Akiyama and H. Rao , New criteria for canonical number systems, submitted.
[6] S. Akiyama, H. Brunotte and A. Pethoe, Cubic CNS Polynomials, notes on
a conjecture of W.J.Gilbert, submitted.
[7] 秋山茂樹, 二次標準数系によるタイル張りについて, 数理研講究録 1160 (2000)
237–245.
[8] H. Brunotte, On trinomial basis of Radix Representations of Algebraic Integers. Acta Sci. Math. (Szeged) 67 (2001) 521-527.
[9] W.J.Gilbert, Radix representations of quadratic number fields, J. Math. Anal.
Appl. 83 (1981) 263–274.
[10] M. Hollander, Linear Numeration systems, Finite Beta Expansions, and Discrete Spectrum of Substitution Dynamical Systems, Doctorial thesis for Washington Univ.
[11] I. Kátai and J. Szabó, Canonical number systems for complex integers, Acta
Sci. Math. (Szeged) 37 (1975) 255–260.
[12] I. Kátai and I. Kőrnyei, On number systems in algebraic number fields, Publ.
Math. Debrecen 41 no. 3–4 (1992) 289–294.
[13] I. Kátai and B. Kovács, Canonical number systems in imaginary quadratic
fields, Acta Math. Hungar. 37 (1981) 159–164.
[14] I. Kátai and B. Kovács, Kanonische Zahlensysteme in der Theorie derquadratischen Zahlen, Acta Sci. Math. (Szeged) 42 (1980) 99–107.
[15] B. Kovács, Canonical number systems in algebraic number fields, Acta Math.
Acad. Sci. Hungar. 37 (1981), 405–407.
[16] 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.

10[17] 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.
[18] K. Scheicher, Kanonische Ziffernsysteme und Automaten, Grazer Math. Ber.,
333 (1997), 1–17.
[19] K. Scheicher and J.M.Thuswaldner, On the characterization of Canonicalnumber system, submitted.
[20] J.M.Thuswaldner, Elementary properties of canonical number systems inquadratic fields, in: Applications of Fibonacci numbers Vol. 7, (Graz, 1996),
405–414, Kluwer Acad. Publ., Dordrecht, 1998.
秋山茂樹
Shigeki AKIYAMA
新潟大学理学部数学教室
新潟市五十嵐 2 の町 8050
e-mail: akiyama@math.sc.niigata-u.ac.jp

11