ナンバーズゲーム数学的な解説

ドパおじ数学パズル工房

元になった数学

このゲームは「数のゲーム(ナンバーズゲーム)」を元にしています。背後には、カルタン行列という数の表と、そこから生まれる折り返しの群(ワイル群、より一般にはコクセター群)があります。このページでは、ゲームの操作を、ベクトルと行列で書き直して、強収束の理由を説明します。

結論

「数 i をおす」は、1 つの行列 Sᵢ をかけることです。Sᵢ は、超平面 xᵢ = 0 を固定して、向きを反転する折り返し(鏡映)です。止まる場所は、すべての xᵢ ≤ 0 の領域です。順番を変えても、止まる場所も回数も同じになる(強収束)のは、どの 2 つの Sᵢ、Sⱼ の積も、決まった回数で単位行列に戻るとき(または、4 以上で戻らないとき)です。この条件は、2 つの相性の積だけで決まります。

数をベクトルに、表を行列にする

並んだ数を、列ベクトル x = (x₁, …, xₙ) とします。相性表は、n×n の行列 A = (aᵢⱼ) です。決まりは次の 3 つです。

対角成分は、aᵢᵢ = 2。
それ以外は、aᵢⱼ ≤ 0。
aᵢⱼ = 0 と aⱼᵢ = 0 は、同時に成り立つ。

この 3 つを満たす行列を、一般化カルタン行列と呼びます。ふつうのカルタン行列は、成分が整数で、あとで出てくる「有限型」のものだけです。ゲームの相性表は、成分が整数でなくてもかまいません。

おす操作は、行列をかけること

数 i をおすと、数の組は次のように変わります。

xᵢ ← −xᵢ xⱼ ← xⱼ − aⱼᵢ xᵢ (j ≠ i)

これは、x にある行列 Sᵢ をかけたものです。Sᵢ は、単位行列の i 列目だけを、次のように置き換えた行列です。

Sᵢ = I − (A の i 列目) × (i 番目の単位ベクトルの転置) = I − A eᵢ eᵢᵀ

i 列目の成分は、対角が 1 − 2 = −1、ほかが −aⱼᵢ です。ほかの列は、単位行列のままです。

Sᵢ は折り返し

Sᵢ には、次の性質があります。

Sᵢ² = I。aᵢᵢ = 2 だから、I − 2A eᵢeᵢᵀ + (eᵢᵀA eᵢ) A eᵢeᵢᵀ = I になります。2 回おすと、元に戻ります。
xᵢ = 0 の超平面上のベクトルは、Sᵢ x = x で、動きません(固有値 1 の固有空間)。
ベクトル A eᵢ は、Sᵢ(A eᵢ) = A eᵢ − 2 A eᵢ = −A eᵢ で、向きが反転します(固有値 −1)。
したがって det Sᵢ = −1 です。

つまり Sᵢ は、超平面 xᵢ = 0 を固定して、A eᵢ の向きを反転する折り返し(鏡映)です。A が対称でなくても、この形は変わりません。

止まる場所と回数

ゲームでおせるのは、xᵢ > 0 の数だけです。つまり、超平面 xᵢ = 0 の正の側にある点を、反対側へ折り返します。すべての数が 0 以下になると、おせなくなります。止まる場所は、次の領域です。

C = { x : すべての i で xᵢ ≤ 0 }

おす順を i₁, i₂, …, i_k とすると、止まったときの数の組は、Sᵢₖ ⋯ Sᵢ₂ Sᵢ₁ x で、おした回数は k です。ゲームは、行列の積で x を C まで運ぶ過程だと言えます。

強収束とは

強収束とは、おす順を変えても、止まったときの Sᵢₖ ⋯ Sᵢ₁ x も、おした回数 k も、変わらないことです。2 つとも同じでなければなりません。止まらない場合も含めて、どの順でおしても止まらない場合は、強収束です。

数が 2 個のとき

S₁ と S₂ の積を計算します。

S₁ = ( −1 0 ) S₂ = ( 1 −a₁₂ ) ( −a₂₁ 1 ) ( 0 −1 ) S₁S₂ = ( −1 a₁₂ ) κ = a₁₂ a₂₁ ( −a₂₁ κ − 1 )

この積は、行列式が 1 で、トレースが κ − 2 です。そのため、固有値 λ は、次の式を満たします。

λ² − (κ − 2) λ + 1 = 0

κ の大きさで、3 つの場合に分かれます。

0 ≤ κ < 4:固有値は、複素数の e^(±iφ) で、2cos φ = κ − 2 です。S₁S₂ は、角 φ の回転になります。κ = 2 + 2cos φ = 4cos²(φ/2) です。
κ = 4:固有値は 1 の重解で、S₁S₂ は、平行移動のような行列(ジョルダン型)です。何回かけても、元に戻りません。
κ > 4:固有値は、1 でない正の実数と、その逆数です。何回かけても、元に戻りません。

S₁S₂ が、ちょうど m 回で単位行列に戻る(位数が m)のは、φ = 2π/m のときです。つまり、次のとおりです。

κ = a₁₂ a₂₁ = 4cos²(π/m) (m = 2, 3, 4, 5, …)

m	κ
2	0
3	1
4	2
5	(3+√5)/2 = φ²(黄金比の 2 乗)
6	3

κ がこの形でないとき、S₁S₂ は、角が π の有理数倍でない回転なので、何回かけても元に戻りません。κ ≥ 4 のときも、戻りません。

強収束と、関係式

数が 2 個で、最初に 2 つとも正だとします。最初の 1 手だけ、数 1 か数 2 を選べます。そのあとは、おせる数が 1 つしかありません。つまり、おす順は、1,2,1,2,… と 2,1,2,1,… の 2 通りです。この 2 通りが、同じ場所に、同じ回数で止まることが、強収束です。

2 つの順が合流するための条件は、次の関係式です。

S₁S₂S₁ ⋯ (m 個) = S₂S₁S₂ ⋯ (m 個)

これは、(S₁S₂)ᵐ = I と同じです。κ = 4cos²(π/m) のときに成り立ちます。κ ≥ 4 のときは、どちらの順でも止まりません。それ以外のときは、関係式が成り立たず、2 つの順の結果が分かれます。

数が 3 個以上のとき

強収束かどうかは、2 つずつの組を調べれば決まります。どの i, j の組も、(SᵢSⱼ)ᵐ = I となる m があるか(κ が 4cos²(π/m))、κ ≥ 4 であれば、強収束です。これは、折り返しの群がコクセター群になり、おした回数が、群の元の「長さ」になるためです。コクセター群では、同じ元を表す最短の式は、関係式を使った入れ替えで、すべて結びつきます(ティッツの定理)。だから、止まる場所も、最短の回数も、順番によりません。このゲームでは、ランダムな 3×3 の表 189 通りで、実際に確かめました。

閉じていない組が 1 つでもあると、はじめの数によっては、順番で結果が分かれます。

止まるか、止まらないか

表は、次の 3 つのどれかに分かれます(連結な場合)。

有限型:A の、すべての主小行列式が正です。どの順でも、必ず止まります。折り返しの群が有限だからです。
アフィン型:A が特異で、正の成分のベクトル δ がある型です。次の節で、止まる条件を導きます。
それ以外(不定値型):群が無限で、はじめの数によって、止まることも止まらないこともあります。

アフィン型:δ・v の符号が、止まる条件になる

ここでは、数の組を v、その成分を xᵢ と書きます。おせるのは xᵢ > 0 の数で、おすことは、単純反射 sᵢ をかけることです。止まるのは、すべての xᵢ ≤ 0 のとき、つまり次の領域に入ったときです。

C₋ = { v : すべての i で xᵢ ≤ 0 }

1. アフィン型では、δ がある

アフィン型では、成分がすべて正のベクトル c = (cᵢ) で、A をかけると 0 になるものがあります(cᵢ > 0)。このゲームの向き(xⱼ ← xⱼ − aⱼᵢ xᵢ)では、成分 aⱼᵢ の並べ方に合わせて、次の式になります。

Σⱼ cⱼ aⱼᵢ = 0 (すべての i) つまり cᵀA = 0

aᵢⱼ の並べ方を逆に書く流儀では、同じものが A c = 0 と書かれます。この c を使って、δ = Σ cᵢ αᵢ と定めます(αᵢ は単純根)。これが、アフィン型の虚根 δ(null root)です。

2. δ・v は、おしても変わらない

数 i をおすことは、単純反射 sᵢ をかけることです。δ は、カルタン形式の核にあるので、すべての i で sᵢ(δ) = δ が成り立ちます。したがって、次のとおりです。

δ・sᵢ(v) = sᵢ(δ)・sᵢ(v) = δ・v

3. 止まる領域では、δ・v ≤ 0

xᵢ = αᵢ・v だから、次のとおりです。

δ・v = Σ cᵢ (αᵢ・v) = Σ cᵢ xᵢ

cᵢ > 0 で、止まっているときは xᵢ ≤ 0 だから、δ・v ≤ 0 です。止まる領域の内部(すべての xᵢ < 0)では、δ・v < 0 です。ここまでで分かるのは、「止まる ⇒ δ・v ≤ 0」だけです。

4. 逆:δ・v < 0 なら、必ず止まる

アフィン型のコクセター群では、止まる(止まる領域に運べる)数の組の集まりは、ティッツ錐です。ティッツ錐の内部は、次のとおりです。

ティッツ錐の内部 = { v : δ・v < 0 }

したがって、次の関係が成り立ちます。

δ・v < 0 ⇔ v はティッツ錐の内部 ⇔ ゲームは止まる

5. δ・v = 0 のとき、止まらずに、くり返す

はじめに δ・v = 0 なら、ゲーム中ずっと δ・v = 0 です。止まる領域の内部では δ・v < 0 なので、そこには入れません。アフィン型では、δ・v = 0 は、ゲームが同じ数の組をくり返すこと(ループ)と同じです。

6. δ・v > 0 のとき

δ・v > 0 も、止まる領域に入れません。この場合、数の組は、くり返さずに、どんどん大きくなります。

δ・v	ゲームの動き
< 0	止まる
= 0	止まらず、同じ組をくり返す(ループ)
> 0	止まらず、くり返さずに、どんどん大きくなる

アフィン型で、すべての相性が −1 の表(3 個)を、ゲームで確かめました。(1, −2, −2) や (1, 1, −5) は止まり、(1, −1, 0) や (2, −1, −1) は 3〜6 回でくり返しに入りました。(1, 1, 1) や (3, 1, 0.5) は、300 回おしても、止まらず、くり返しもしませんでした。

アフィン型では、動きは、δ・v = (定数) の平面の上の折り返しになり、平面をタイルのように敷き詰めます。角が 60°-60°-60°、45°-45°-90°、30°-60°-90° の三角形で、同じことが起こります。

7. 表から δ を求める方法

アフィン型の表 A が与えられたら、次の順で、止まるかどうかが分かります。

A の核を求める(このゲームの向きでは cᵀA = 0、逆の流儀では A c = 0 を解く)。
成分がすべて正の核ベクトル c を探す。見つかれば、δ = Σ cᵢ αᵢ とする。
はじめの数の組 v = (x₁, …, xₙ) について、δ・v = Σ cᵢ xᵢ を計算する。
符号を見る。Σ cᵢ xᵢ < 0 なら止まる。= 0 ならループ。> 0 なら止まらない。

8. 例:Ã₂

A = [[2, −1, −1], [−1, 2, −1], [−1, −1, 2]]

A に (1, 1, 1) をかけると (0, 0, 0) になるので、c = (1, 1, 1)、δ = α₁ + α₂ + α₃ です。したがって δ・v = x₁ + x₂ + x₃ となります。

x₁ + x₂ + x₃ < 0 → 止まる / = 0 → ループ / > 0 → 止まらない

9. 最重要ポイント

表 A → 正の核ベクトル c → δ → δ・v = Σ cᵢ xᵢ の符号 → ゲームの動き。アフィン型なら、この値の符号だけで、止まる・ループ・止まらないが分かります。

ゲームでの操作

相性表の、斜め以外の数字(A の成分)を書き換えられます。式(−phi、−sqrt(2) など)も入れられます。
はじめの数(x)も書き換えられます。
黄色の数(xᵢ > 0)をおすと、Sᵢ をかけた結果になります。「1 つ戻す」で戻せます。
止まると、おした順、止まったときの数、おした回数が、記録に残ります。「最初から」で、ちがう順にやり直します。
記録の数と回数が、両方同じなら成功です。「すべての順で調べる」で、いまの数について、すべての順を調べられます。

ナンバーズゲーム 数学的な解説