3.1 宿題の解説 - Researchmap

ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
3.1
21
宿題の解説
前回の宿題の解説をする．
$
'
問題 3.1
(宿題 2.9)
(1) 4 つの頂点からなるグラフは同形を除いていくつあるか．(同形を除いて全て決めよ．)
(2) R2 における 4 点からなる 2-距離集合を相似を除いて全て求めよ
(3) R2 における 5 点からなる 2-距離集合を全て求めよ．
(4) R2 における 6 点からなる 2-距離集合は存在しないことを示せ．
&
%
(1) 解説は坂内先生と生徒とのやりとりから始まった．
先生: この問題は，どの点とも結ばれていないような点があるグラフ，つまり図 1
のグラフも考えることに注意しよう．
図1
生徒 A にやってきたものを黒板に書いてもらう．
(a)
(b)
(e)
(f)
(i)
(j)
(c)
(d)
(g)
(h)
(k)
図 2 生徒が書いた 4 点からなるグラフ
生徒 B:
その中には同形なものが存在します．
先生: どれとどれが同形？
生徒 B: (c) と (f)，(j) と (k) が同形です．
坂内先生が対応を説明する．
ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
22
先生: 他にはない？
生徒: …
先生: 全く辺のない (l) も 4 点からなるグラフです．他にはないですか？
生徒 C が黒板の前に行き，(m) があることを指摘する．
(l)
(m)
図3
図4
先生: この 11 個ですべてであることはどうやって示せばいいですか？
生徒: …
坂内先生の解説が始まった．たとえば，辺の個数に注目する．辺の本数が 0, 1, 2, 3 のときには，
表 1 のグラフしかないことがわかる．
辺の本数
グラフ
0
(l)
1
(e)
2
(g),(h)
3
(b),(i),(m)
表1
4 つのときは補グラフを考えると，辺の本数が 2 本のときの個数と同じになる．ここで，次の関
係があることに注意する．
(g)
(j)
∼
=
(補グラフの関係)
(同形)
(h)
(a)
∼
=
(同形)
(補グラフの関係)
図5
補グラフの関係
5 本と 6 本の場合も 4 本の場合と同様に補グラフを考えて次の表 2 ができる．
(2) 第 1 回のときに扱った問題である．上の問題を参考にすることで，考えやすくなる．新たに図
6 が見つかった．
ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
辺の本数
0
1
2
3
4
5
6
合計
グラフの個数
1
1
2
3
2
1
1
11
23
表 2 辺の本数に着目したグラフの個数
図 6 新たに見つかった 4 点からなる 2-距離集合
(3) 上の問題を用いる．もう 1 点を加えて，2-距離集合ができるものを考えればよい．
(4) この問題も上の問題を用いる．
• 正 5 角形の内部にある場合
内部に正 3 角形が 5 つできる場合が可能性として考えられるが，辺の長さを計算すると，
この場合はあり得ないことがわかる．
• 正 5 角形の外周あるいは外部にある場合
正 5 角形の 2 つの点との距離を考えれば，2-距離集合ではないことがわかる．
宿題 3.2
3.2
(10/17 の公開講演会のときに提出) 自分なりの説明をつけて，問題 3.1 のまとめをせよ．
T (n) グラフの復習と本格的な研究課題
X = {1, 2, . . . , n} とし，V を X の 2 点からなる集合全体，つまり，
V = {{1, 2}, {1, 3}, . . . , {1, n}, {2, 3}, . . . , {n − 1, n}}
とおく．このとき， |V| =
(n)
2
=
n(n−1)
2
である．また辺 E については，2 つの点 {i, j} と {k, l} が
|{i, j} ∩ {k, l}| = 1 となるとき，つまり点 {i, j} と {k, l} が 1 つの文字だけを共有するときに辺で結ぶ
ことにする．このとき，G = (V, E) を T (n) グラフという．
問題 3.3
n = 4 のときの T (n) グラフはどのような図形になるか．*1
解答：T (4) グラフは図 7 のようになる．
事実 3.4
*1
T (5) の補グラフは第 2 回で述べた Petersen グラフである．
生徒に前に出てきて解答してもらった．
ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
24
{1, 2}
{2, 3}
{1, 3}
{2, 4}
{1, 4}
{3, 4}
図 8 Petersen グラフ
図 7 T (4) グラフ
T (n) の Rn−1 への埋め込みについて復習する．
T (n) の頂点 {(i, j) | 1 5 i < j 5 n} は
n(n−1)
2
個で，頂点 {i, j} に対して ei + e j ∈ Rn を対応させる．
{i, j} と {k, l} が辺で結ばれているとき，ei + e j と ek + el の間の距離は
√
2 であり, {i, j} と {k, l}
が結ばれていないとき，ei + e j と ek + el の間の距離は 2 である. このようにして T (n) は Rn の中
に 2-距離集合として埋め込まれた．
H = {(x1 , x2 , . . . , xn ) ∈ Rn | x1 + x2 + · · · + xn = 2}
とおくとこれは Rn の中の超平面だった．つまり，H Rn−1 である．これより，T (n) は Rn−1 の
中に 2-距離集合として埋め込まれた．
課題：T (n) のグラフは Rn−1 に 2-距離集合として埋め込まれた. この 2-距離集合は 2-距離集
合としていつ極大か？ (あるいは，この 2-距離集合を含む, より大きな 2-距離集合はいつ存在
するか？)
例 3.5
n = 3 のとき，T (3) は R2 に 2-距離集合 (実は 1-距離集合) として埋め込まれる．このと
き，T (3) は 2-距離集合として極大ではない．実際，問題 3.1 でやった次の 2-距離集合が存在する．
図9
R2 に埋め込まれた T (3) を含む 2-距離集合
n = 4 のとき，T (4) は R3 に 2-距離集合として埋め込まれる．実はこれは極大になっている． 課題を解くためのヒント：
もし T (n) が極大でなければ，次を満たすベクトル x = (x1 , x2 , . . . , xn ) ∈ Rn が存在する：
• x1 + x2 + · · · + xn = 2．
• x は各 ei + ej との距離が 2 または
x と e1 + e2 との距離は
√
2 である．
√
d(x, e1 + e2 ) = (x1 − 1)2 + (x2 − 1)2 + x32 + · · · + xn2
ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
25
となり，
d(x, e1 + e2 )2 = (x1 − 1)2 + (x2 − 1)2 + x32 + · · · + xn2
が成り立つ．同様にして
d(x, e1 + e3 )2 = (x1 − 1)2 + x22 + (x3 − 1)2 + x42 + · · · + xn2
となる．
(1) d(x, e1 + e2 ) = d(x, e1 + e3 ) のとき．d(x, e1 + e2 )2 = d(x, e1 + e3 )2 より
x12 − 2x1 + 1 + x22 − 2x2 + 1+x32 + · · · + xn2
= x12 − 2x1 + 1 + x22 + x32 − 2x3 + 1 + x42 + · · · + xn2 .
よって，−2x2 = −2x3 から x2 = x3 となる．
(2) d(x, e1 + e2 ) , d(x, e1 + e3 ) のとき．d(x, e1 + e2 )2 = 2 または 4，d(x, e1 + e3 )2 = 2 または 4 だ
から，d(x, e1 + e2 )2 = d(x, e1 + e3 )2 ± 2 となる．このとき −2x2 = −2x3 ± 2 から x2 = x3 ± 1
がいえる．
今の議論を任意の i と j に対しても同様に計算すると， xi = x j または xi = x j ± 1 となる．ここ
で x1 , . . . , xn は，ある実数 α を用いて α または α − 1 であるとしてよい．なぜなら，もしこれ以
外の数が現れるとすれば，任意の i と j に対して xi = x j または xi = x j ± 1 であることに矛盾して
しまう． x1 , . . . , xn の中に α が s 個で α − 1 が t 個あるとすると， x1 + x2 + · · · + xn = 2 より，
α
+ ··· +}
α + (α − 1) + (α − 1) + · · · + (α − 1) = 2.
| + α {z
|
{z
}
s
t
この式から n = 9 のときのみが，特別な場合 (Lisoněk [2] の例) であることがわかる．
宿題 3.6
3.3
(10/17 の公開講演会のときに提出) 上の議論を完成させよ．
Kissing number
問題 3.7
1 つの 10 円玉の回りに 10 円玉が最大何個置けるか．
解答：10 円玉の中心を結ぶと図 10 のように正 3 角形ができ，角度が
60◦ になる．このことから 1 つの 10 円玉の回りには 6 個の 10 円玉が
置けることがわかる．
10 円
60◦
同様の問題を R3 で考える．
図 10
ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
26
課題：R3 で，1 つの与えられた単位球の回りに同じ半径の球をそれと接するように (かつ互
いに重なり合わないように) 最大いくつ置けるか？
S 1 , S 2 , S 2 を 半 径 1 の 球 と し ，S 1 の 中 心 は 原 点 O と す る ．図 11 の よ う に 始 点 を 原
点 O と し ，S 2 の 中 心 方 向 の 単 位 ベ ク ト ル を x，S 3 の 中 心 方 向 の 単 位 ベ ク ト ル を y と す
る ．ま た ，x と y と の な す 角 を θ と お く ．x と y の 内 積 は x · y = ∥x∥∥y∥ cos θ だ か ら ，
S2
S 1 と S 3 ，S 2 と S 3 が接していて，S 2 と S 3 が重なり合わない
⇐⇒ θ = 60◦
⇐⇒ x · y 5
S3
1
．
2
x
S1
O
θ
y
図 11
定義 3.8（Kissing number） Rn の 1 つの単位球*2 の回りに同じ半径の球をそれと接するよ
うに (かつ互いに重なり合わないように) 置ける最大値を Kissing number といい，k(n) と
表す．
上で述べたことから，k(3) は次のように言い換えられる．k(3) は R3 の原点を始点とする単位ベ
クトルの集まりで，異なる 2 つのベクトルの内積が
1
2
以下になるものの個数の最大値である．
問題 3.9
k(3) = 12.
解答：12 個の点からなる次の集合を考える：
{
} {
}
1
1
1
1
1
1
√ (±1, ±1, 0), √ (±1, 0, ±1), √ (0, ±1, ±1) = √ (±e1 ± e2 ), √ (±e1 ± e3 ), √ (±e2 ± e3 ) .
2
2
2
2
2
2
ただし復号は同順ではなく，任意にとって良い．これら 12 個のベクトルの相異なる 2 つのベクト
ルの内積は −1, − 21 , 0,
1
2
のいずれかになる．これより，k(3) = 12 が示せた．
以下の事実を使って，正 12 面体の 12 個の点を用いて k(3) = 12 を示す方法もある．
事実 3.10
*2
正 12 面体の 12 個の頂点を考える．2 つの頂点間の角度は 63.4349 · · ·◦ である．
Rn の単位球についてはすぐ後で説明する.
ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
27
この事実からわかるように，R3 の場合は R2 のようにびっしりと並べられているのではなく，
隙間がある．このことから，k(3) が 12 であるか 13 でかあるかの論争が 17 世紀に Newton と
Gregory によって繰り広げられた．現在では次がわかっている．
事実 3.11
k(3) = 12.
定義 3.12（球面，単位球，球体） n = 3 のときと同様に，Rn で点 A から一定の距離 r の点
全体の「図形」を球面または球といい，A を中心，r を半径と呼ぶ．とくに半径が 1 の球 (通
常は中心が原点) を単位球という．また中身の詰まったものを球体と呼ぶ．
例 3.13
R2 の原点を中心とする単位球は，原点を中心とする半径 1 の円である．これを S 1 と表
す．R2 の原点を中心とする半径 1 の球体は，S 1 の中身も含めた円板である．
y
R2
図 12
y
R2
S1
O
x
1
O
R2 の原点を中心とする単位球
1
x
図 13 R2 の原点を中心とする半径 1 の球体
Rn のときも R3 と同様に 26 ページの図 11 を用いて，k(n) は Rn の原点を始点とする単位ベクト
ルの集まりで，異なる 2 つのベクトルの内積が
1
2
以下になるものの個数の最大値を考えれば良い．
問題 3.14
k(4) = 24.
解答：k(3) = 12 のときは次の集合を考えた：
{
}
1
√ (±ei ± ej ) 1 5 i < j 5 3 .
2
この証明と同様に，次の集合を考える：
{
}
1
√ (±ei ± ej ) 1 5 i < j 5 4 .
2
この集合の異なる 2 つのベクトルの内積は −1, − 12 , 0,
(4)
2
· 4 = 24 となる.
事実 3.15（O. R. Musin [3]） k(4) = 24.
1
2
となり，この集合の元の個数は 4C2 · 4 =
ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
28
[3] の後，Bachoc-Vallentin [1] によって別証明も考えられている．
n がさらに高次元の場合について考察する．n = 3, 4 のときと同様に次の集合を考える：
{
}
1
(3.1)
√ (±ei ± ej ) 1 5 i < j 5 n .
2
()
この集合の元の個数は n2 · 4 = 2n(n − 1) であり，表にすると以下のようになる．
次元
2
3
4
5
6
7
8
...
n
個数
4
12
24
40
60
84
112
...
2n(n − 1)
表 3 (3.1) の集合の個数
事実 3.16
k(8) = 240.
問題 3.17
k(8) = 240.
解答：上で述べた方法では，集合の個数が少ない．更に元の個数を増やして次の集合を考える：
{
} {
}
1
1
√ (±ei ± ej ) 1 5 i < j 5 8 ∪ √ (±e1 ± e2 ± · · · ± e8 ) −の個数は偶数個 .
8
2
∪ の前は表で述べたように 112 個あり，∪ の後ろは e1 から e7 の係数の符号を決めると e8 の係数
の符号は決まるから，個数は 27 = 128 個である．これらを合わせて 240 個になる．240 個のベク
トルの相異なる 2 つのベクトルの内積は，−1, − 12 , 0,
事実 3.18
1
2
となり， 12 以下になる．
k(24) = 196560.
n = 5, 6, . . . (ただし，n = 8 と n = 24 を除く) に関して k(n) の値はわかっていない．現時点で
は表 4 に示していることが知られている．
R3 のときは，事実 3.10 から正 12 面体の 2 つのとなり合う頂点の角度は 63.4349 · · ·◦ なので,
12 個の球の置き方に自由度がたくさんある．
事実 3.19
*3
R4 の場合について 24 個の球の置き方に自由度があるかどうかは未解決． *3
自由度はないと予想されている．
ESSP 数学 2009 年度講義ノート: 第 3 回 (10/10)
n
29
k(n)
Bachoc-Vallentin [1] 以前
最近の進展 (Bachoc-Vallentin)
2
6
6
3
12
12
4
24
24
5
40 ∼ 46
40 ∼ 45
6
72 ∼ 82
72 ∼ 78
7
126 ∼ 140
126 ∼ 135
8
240
240
9
306 ∼ 380
306 ∼ 366
10
500 ∼ 595
500 ∼ 567
24
196560
196560
表 4 k(n) の値
参考文献
[1] C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite programming. J. Amer. Math. Soc. 21 (2008), no. 3, 909–924.
[2] P. Lisoněk, New maximal two-distance sets, J. Combin. Theory Ser. A 77 (1997), 318–338.
[3] O. R. Musin, The kissing number in four dimensions, Ann. of Math. (2) 168 (2008), no. 1, 1–32.