キスナンバー

数学における未解決問題

( n + 1)次元ユークリッド空間における n次元球の最大可能なキス数はいくつですか？

幾何学において、数学的空間のキス数とは、その空間において、共通の単位球に接するように配置できる、重なり合わない単位球の最大数として定義されます。与えられた空間における球のパッキング（球の配置）に対して、個々の球について、その球が接する球の数としてキス数を定義することもできます。格子パッキングの場合、キス数はすべての球で同じですが、任意の球パッキングの場合、キス数は球ごとに異なる場合があります。

キッシング数には、ニュートン数（問題の考案者にちなんで）、接触数などの別名も使用されています。

一般に、キス数問題は、 ( n +1)次元ユークリッド空間における n次元球面の最大キス数を求める問題である。通常の球面は、3次元空間における2次元閉曲面に対応する。

球の中心が直線（1次元の場合）または平面（2次元の場合）に限定されている場合、キス数を求めることは容易です。3次元の場合、物理世界では概念化とモデル化が容易であるにもかかわらず、その解の証明は20世紀半ばまで数学者の手に負えませんでした。^[1]^[2]高次元での解ははるかに困難であり、厳密に解かれたケースはごくわずかです。その他のケースについては、調査によって上限と下限は決定されていますが、厳密な解は得られていません。^[3]

キスの最高記録

1次元

1次元では^[4]キス数は2である。

2次元

2次元では、キスの数は6です。

証明：中心Cを持つ円と、その円に中心C ₁、C ₂ 、…を持つ円が接しているとする。光線C C _iを考える。これらの光線はすべて同じ中心Cから発せられるため、隣接する光線間の角度の和は360°となる。

矛盾により、6つ以上の接する円があると仮定する。すると、少なくとも2つの隣接する直線、例えばC C ₁とC C ₂は、60°未満の角度で離れている。線分CC _{i は}、すべてのiに対して同じ長さ（2 r ）を持つ。したがって、三角形C C ₁C _2は二等辺三角形であり、その3番目の辺（C ₁C _{2 ）の辺の長さは2}r未満である。したがって、円1と円2は交差するが、これは矛盾である。^[5]

三次元

3次元では、接吻数は12だが、正しい値を確立するのは1次元や2次元の場合よりもずっと困難だった。12個の球をそれぞれが中央の球に接するように配置して十分な空間を残すことは簡単であり、13個目の球を詰め込む方法がないことは明らかではない（実際には、12個の外側の球のうちのどの2つでも、中心の球との接触を失うことなく、連続的な動きによって場所を交換できるほど十分な空間がある）。これは、数学者アイザック・ニュートンとデイビッド・グレゴリーの間の有名な意見の相違の主題であった。ニュートンは限界は12であると正しく考え、グレゴリーは13個目は収まると考えていた。ニュートンが正しかったという不完全な証明は19世紀にいくつか提示されたが、最も有名なのはラインホルト・ホッペによるものである。しかし、最初の正しい証明（ブラス、モーザー、パックによると）は1953年まで現れなかった。^[1]^[2]^[6]

中心球の12個の隣接原子は、すべての原子が同じ大きさの結晶格子（化学元素など）における原子の最大バルク配位数に対応します。配位数12は、立方最密充填構造または六方最密充填構造に見られます。

より大きな寸法

4次元では、キス数は24です。これは、2003年にオレグ・ムシンによって証明されました。^[7]^[8]以前は、答えは24か25であると考えられていました。中心の球の周りに24個の球を詰め込むのは簡単です（原点を中心とした適切にスケールされた24セルの頂点に球を配置できます）が、3次元の場合と同様に、多くのスペースが残ります（実際にはn = 3の場合よりも多くなります）ため、状況はさらに不明確でした。

高度に対称的なE8格子とリーチ格子の存在により、_n = 8（キス数は240）と n = 24（キス数は196,560）の既知の結果が得られている。 ^[9]^[10]n 次元におけるキス数は他の次元では不明である。

配置が格子配置に制限され、球の中心がすべて格子内の点上にある場合、この制限されたキス数はn = 1〜9次元およびn = 24次元で知られています。^[11] 5次元、6次元、7次元の場合、これまでに見つかった最高のキス数を持つ配置が最適な格子配置ですが、より高いキス数を持つ非格子配置の存在が排除されていません。

いくつかの既知の境界

次の表は、様々な次元におけるキス数の既知の境界をいくつか示しています。^[12]^[13]キス数が既知の次元は太字で示されています。

寸法	下限	上限
1	2
2	6
3	12
4	24 ^[7]
5	40	44
6	72	77
7	126	134
8	240
9	306	363
10	510	553
11	593 ^[14]	868
12	840	1,355
13	1,154	2,064
14	1,932	3,174
15	2,564	4,853
16	4,320	7,320
17	5,730	10,978
18	7,654	16,406
19	11,692	24,417
20	19,448	36,195
21	29,768	53,524
22	49,896	80,810
23	93,150	122,351
24	196,560
25	197,056 ^[15]	265,006
26	198,550 ^[15]	367,775
27	200,044 ^[15]	522,212
28	204,520 ^[15]	752,292
29	209,496 ^[15]	1,075,991
30	220,440 ^[15]	1,537,707
31	238,078 ^[15]	2,213,487
32	345,408	3,162,316

一般化

キス数問題は、任意の凸体の、あるコピーに接する重なり合わない合同なコピーの最大数を求める問題に一般化できる。この問題には、コピーが元の物体に合同であるだけでよいか、元の物体を平行移動したものに合同であるだけでよいか、あるいは格子によって平行移動したものに合同である必要があるかによって、異なるバージョンが存在する。例えば、正四面体の場合、格子キス数と平行移動キス数はどちらも18であるのに対し、合同キス数は少なくとも56であることが知られている。^[16]

アルゴリズム

交差グラフには、近似率がキス数に依存する近似アルゴリズムがいくつかあります。 ^[17]例えば、回転した単位正方形の集合の最大の非交差部分集合を見つけるための多項式時間10近似アルゴリズムがあります。

数学的な記述

キス数問題は、不等式の集合に対する解の存在として述べられる。球の中心のN次元位置ベクトルの集合をとする。この球の集合が中心球の周囲に重なり合うことなく存在できる条件は、以下の通りである。^[18] $x_{n}$ $\exists x\ \left\{\forall _{n}\{x_{n}^{\textsf {T}}x_{n}=1\}\land \forall _{m,n:m\neq n}\{(x_{n}-x_{m})^{\textsf {T}}(x_{n}-x_{m})\geq 1\}\right\}$

このように、各次元の問題は実数の存在理論で表現できる。しかし、この形式の問題を解く一般的な方法は少なくとも指数関数的な時間を要するため、この問題は4次元までしか解かれていない。変数を追加することで、これはN ( N − 1)/2 + DN個の変数からなる単一の4次方程式に変換できる。 ^[19] $y_{nm}$ $\exists xy\ \left\{\sum _{n}\left(x_{n}^{\textsf {T}}x_{n}-1\right)^{2}+\sum _{m,n:m<n}{\Big (}(x_{n}-x_{m})^{\textsf {T}}(x_{n}-x_{m})-1-(y_{nm})^{2}{\Big )}^{2}=0\right\}$

したがって、 D = 5次元、N = 40 + 1ベクトルの場合を解くことは、1025 変数の4次多項式の実数解の存在を決定することと等価です。D = 24次元、N = 196560 + 1の場合、4次多項式は19,322,732,544変数を持ちます。距離幾何学における別の表現は、m^{番目の球面}とn^番目の球面の間の距離の2乗によって与えられます。 $R_{mn}$ $\exists R\ \{\forall _{n}\{R_{0n}=1\}\land \forall _{m,n:m<n}\{R_{mn}\geq 1\}\}$

これに、 D次元の( D +1)単体を形成する任意の点集合に対して、ケーリー・メンガー行列式がゼロになるという条件を付け加える必要があります。なぜなら、その体積はゼロでなければならないからです。と設定すると、 yのみに関する連立多項式方程式の集合が得られ、これは実数値についてのみ解く必要があります。2つの方法は完全に同等ですが、それぞれ異なる用途があります。例えば、2番目のケースでは、 yの値をランダムに少しずつ変更することで、 yに関する多項式を最小化しようと試みることができます。 $R_{mn}=1+{y_{mn}}^{2}$

参照

注記

^ ab Conway, John H. ; Neil JA Sloane (1999). Sphere Packings, Lattices and Groups (第3版). ニューヨーク: Springer-Verlag. p. 21. ISBN 0-387-98585-9。
^ ab Brass, Peter; Moser, WOJ; Pach, János (2005).離散幾何学における研究課題. Springer. p. 93. ISBN 978-0-387-23815-9。
^ ミッテルマン, ハンス・D.; ヴァレンティン, フランク (2010). 「キス数に対する高精度半正定値計画法の境界」.実験数学. 19 (2): 174– 178. arXiv : 0902.1105 . Bibcode :2009arXiv0902.1105M. doi :10.1080/10586458.2010.10129070. S2CID 218279.
^ 1次元では、「球」は単位距離で隔てられた点のペアに過ぎないことに注意してください。（1次元の図の垂直方向の次元は、単にイメージを喚起するだけです。）高次元とは異なり、有限の充填密度を実現するためには、球の内部（単位長さの開区間）が重なり合わないように指定する必要があります。
^ Marathe , MV; Breu, H.; Hunt, HB; Ravi, SS; Rosenkrantz, DJ (1995). "Simple heuristics for unit disk graphs". Networks . 25 (2): 59. arXiv : math/9409226 . doi :10.1002/net.3230250205.の補題3.1も参照。
^ Zong, Chuanming (2008). 「凸体のキス数、ブロッキング数、被覆数」。Goodman, Jacob E.、Pach, Jínos、Pollack, Richard (編).離散幾何学と計算幾何学のサーベイ：20年後 (AMS-IMS-SIAM 合同夏季研究会議、2006年6月18日～22日、ユタ州スノーバード)。Contemporary Mathematics. 第453巻. プロビデンス、ロードアイランド州：アメリカ数学会. pp. 529– 548. doi :10.1090/conm/453/08812. ISBN 9780821842393. MR 2405694。。
^ ab OR Musin (2003). 「25球の問題」. Russ. Math. Surv . 58 (4): 794– 795. Bibcode :2003RuMaS..58..794M. doi :10.1070/RM2003v058n04ABEH000651. S2CID 250839515.
^ Pfender, Florian; Ziegler, Günter M. (2004年9月). 「Kissing number, sphere packings, and some expected proves」(PDF) .アメリカ数学会報: 873–883 .。
^ レーベンシュタイン、ウラジーミル I. (1979)。 "О границах для упаковок в n-мерном евклидовом пространстве" [ n次元ユークリッド空間のパッキングの範囲について]。Doklady Akademii Nauk SSSR (ロシア語)。245 (6): 1299–1303。
^ Odlyzko, AM ; Sloane, NJA (1979). 「n次元において単位球に接することができる単位球の数に関する新たな境界」. Journal of Combinatorial Theory . Series A. 26 (2): 210– 214. doi : 10.1016/0097-3165(79)90074-8 .
^ Weisstein, Eric W.「Kissing Number」. MathWorld .
^ https://dspace.mit.edu/bitstream/handle/1721.1/153312/table.pdf?sequence=8
^ Machado, Fabrício C.; Oliveira, Fernando M. (2018). 「多項式対称性を利用したキッシング数の半正定値計画限界の改良」.実験数学. 27 (3): 362– 369. arXiv : 1609.05167 . doi :10.1080/10586458.2017.1286273. S2CID 52903026.
^ Genkina, Dina (2025年5月14日). 「新しいAIモデルが『キス問題』などの解決を前進させる」IEEE Spectrum . 2025年8月22日閲覧。
^ abcdefg 馬、成東;テオ・タオ、チャオウェイ。リー・ペンギュ。劉明豪。チェン・ハオジュン。マオ、ジハオ。チェン、ユアン。チー、ユアン。ヤン、ヤオドン（2025 年 11 月 17 日）。「ゲーム理論の強化学習でキス数を見つける」。arXiv。
^ ラガリアス、ジェフリー・C.；ゾン、チュアンミン（2012年12月）「正四面体のパッキングにおける謎」（PDF）アメリカ数学会報：1540- 1549年。
^ Kammer, Frank; Tholey, Torsten (2012年7月). 「交差グラフの近似アルゴリズム」. Algorithmica . 68 (2): 312– 336. doi :10.1007/s00453-012-9671-1. S2CID 3065780.
^ mとnは 1 からNまでの値をとる。はN 個の位置ベクトルの列である。第二全称量指定子 ( ) の条件はmとn を入れ替えても変わらないので、この量指定子をのすぐ上に拡張すれば十分である。簡略化のため、球面の半径は 1/2 と仮定する。 $x=(x_{n})_{N}$ $\forall$ $m,n:m<n$
^ 行列に関しては、 m < nとなる要素のみが必要です。あるいは、行列は反対称であると仮定することもできます。いずれにせよ、行列はN ( N − 1)/2個の自由スカラー変数を持ちます。さらに、 N個の列ベクトルからなる行列に対応するN個のD次元ベクトルx _nがあります。 $y=(y_{mn})_{N\times {N}}$ $x=(x_{nd})_{N\times D}$

参考文献

コーン、ヘンリー；リー、アンキ（2024）「17次元から21次元におけるキス数の改善」arXiv : 2411.04916 [math.MG].
T.アステとD.ウィア 『完璧な梱包の追求』（Institute Of Physics Publishing London 2000）ISBN 0-7503-0648-3
ガブリエル・ネーベとニール・スローンが管理する、現在知られているキスの最高回数表（下限値）
バチョック, クリスティン; ヴァレンティン, フランク (2008). 「半正定値計画法によるキス数に対する新たな上限値」アメリカ数学会誌. 21 (3): 909– 924. arXiv : math.MG/0608426 . Bibcode :2008JAMS...21..909B. doi :10.1090/S0894-0347-07-00589-9. MR 2393433. S2CID 204096.

外部リンク

グライム、ジェイムス (2018年10月10日). 「Kissing Numbers」（ビデオ） . youtube .ブレイディ・ハラン. 2021年12月12日時点のオリジナルよりアーカイブ。2018年10月11日閲覧。

[Conway-1] Conway, John H. ; Neil JA Sloane (1999). Sphere Packings, Lattices and Groups (第3版). ニューヨーク: Springer-Verlag. p. 21. ISBN 0-387-98585-9。

[Brass-2] Brass, Peter; Moser, WOJ; Pach, János (2005).離散幾何学における研究課題. Springer. p. 93. ISBN 978-0-387-23815-9。

[Mittlemann-3] ミッテルマン, ハンス・D.; ヴァレンティン, フランク (2010). 「キス数に対する高精度半正定値計画法の境界」.実験数学. 19 (2): 174– 178. arXiv : 0902.1105 . Bibcode :2009arXiv0902.1105M. doi :10.1080/10586458.2010.10129070. S2CID 218279.

[4] 1次元では、「球」は単位距離で隔てられた点のペアに過ぎないことに注意してください。（1次元の図の垂直方向の次元は、単にイメージを喚起するだけです。）高次元とは異なり、有限の充填密度を実現するためには、球の内部（単位長さの開区間）が重なり合わないように指定する必要があります。

[5] Marathe , MV; Breu, H.; Hunt, HB; Ravi, SS; Rosenkrantz, DJ (1995). "Simple heuristics for unit disk graphs". Networks . 25 (2): 59. arXiv : math/9409226 . doi :10.1002/net.3230250205.の補題3.1も参照。

[6] Zong, Chuanming (2008). 「凸体のキス数、ブロッキング数、被覆数」。Goodman, Jacob E.、Pach, Jínos、Pollack, Richard (編).離散幾何学と計算幾何学のサーベイ：20年後 (AMS-IMS-SIAM 合同夏季研究会議、2006年6月18日～22日、ユタ州スノーバード)。Contemporary Mathematics. 第453巻. プロビデンス、ロードアイランド州：アメリカ数学会. pp. 529– 548. doi :10.1090/conm/453/08812. ISBN 9780821842393. MR 2405694。。

[Musin-7] OR Musin (2003). 「25球の問題」. Russ. Math. Surv . 58 (4): 794– 795. Bibcode :2003RuMaS..58..794M. doi :10.1070/RM2003v058n04ABEH000651. S2CID 250839515.

[8] Pfender, Florian; Ziegler, Günter M. (2004年9月). 「Kissing number, sphere packings, and some expected proves」(PDF) .アメリカ数学会報: 873–883 .。

[9] レーベンシュタイン、ウラジーミル I. (1979)。 "О границах для упаковок в n-мерном евклидовом пространстве" [ n次元ユークリッド空間のパッキングの範囲について]。Doklady Akademii Nauk SSSR (ロシア語)。245 (6): 1299–1303。

[10] Odlyzko, AM ; Sloane, NJA (1979). 「n次元において単位球に接することができる単位球の数に関する新たな境界」. Journal of Combinatorial Theory . Series A. 26 (2): 210– 214. doi : 10.1016/0097-3165(79)90074-8 .

[11] Weisstein, Eric W.「Kissing Number」. MathWorld .

[12] ttps://dspace.mit.edu/bitstream/handle/1721.1/153312/table.pdf?sequence=8

[Machado-13] Machado, Fabrício C.; Oliveira, Fernando M. (2018). 「多項式対称性を利用したキッシング数の半正定値計画限界の改良」.実験数学. 27 (3): 362– 369. arXiv : 1609.05167 . doi :10.1080/10586458.2017.1286273. S2CID 52903026.

[14] Genkina, Dina (2025年5月14日). 「新しいAIモデルが『キス問題』などの解決を前進させる」IEEE Spectrum . 2025年8月22日閲覧。

[packingstar2025-15] 馬、成東;テオ・タオ、チャオウェイ。リー・ペンギュ。劉明豪。チェン・ハオジュン。マオ、ジハオ。チェン、ユアン。チー、ユアン。ヤン、ヤオドン（2025 年 11 月 17 日）。「ゲーム理論の強化学習でキス数を見つける」。arXiv。

[16] ラガリアス、ジェフリー・C.；ゾン、チュアンミン（2012年12月）「正四面体のパッキングにおける謎」（PDF）アメリカ数学会報：1540- 1549年。

[17] Kammer, Frank; Tholey, Torsten (2012年7月). 「交差グラフの近似アルゴリズム」. Algorithmica . 68 (2): 312– 336. doi :10.1007/s00453-012-9671-1. S2CID 3065780.

[18] とnは 1 からNまでの値をとる。はN 個の位置ベクトルの列である。第二全称量指定子 ( ) の条件はmとn を入れ替えても変わらないので、この量指定子をのすぐ上に拡張すれば十分である。簡略化のため、球面の半径は 1/2 と仮定する。 $x=(x_{n})_{N}$ $\forall$ $m,n:m<n$

[19] 行列に関しては、 m < nとなる要素のみが必要です。あるいは、行列は反対称であると仮定することもできます。いずれにせよ、行列はN ( N − 1)/2個の自由スカラー変数を持ちます。さらに、 N個の列ベクトルからなる行列に対応するN個のD次元ベクトルx _nがあります。 $y=(y_{mn})_{N\times {N}}$ $x=(x_{nd})_{N\times D}$

v t e アイザック・ニュートン卿
出版物	フラクションズ（1671）デ・モトゥ（1684）プリンキピア（1687）光学（1704）クエリ (1704) 算術書（1707）『分析論』（1711年）
その他の著作	クエスティオネス（1661–1665）「巨人の肩の上に立つ」（1675）ユダヤ神殿に関する覚書（1680年頃）「ゼネラル・スコリウム」 (1713; 「フィンゴ以外の仮説」 ) 古代王国改訂版（1728年）聖書の改ざん（1754年）
貢献	微積分フラクション衝撃の深さ慣性ニュートンディスクニュートン多角形ニュートン・オクンコフ体ニュートンの反射鏡ニュートン式望遠鏡ニュートンスケールニュートンの金属スペクトラム構造色
ニュートン主義	バケット引数ニュートンの不等式ニュートンの冷却の法則ニュートンの万有引力の法則ポストニュートン膨張パラメータ化された重力定数ニュートン・カルタン理論シュレーディンガー・ニュートン方程式ニュートンの運動の法則ケプラーの法則ニュートン力学最適化におけるニュートン法アポロニウスの問題打ち切りニュートン法ガウス・ニュートン法ニュートンリング楕円に関するニュートンの定理ニュートン・ピープス問題ニュートンポテンシャルニュートン流体古典力学光の粒子理論フック・ニュートン論争ライプニッツ・ニュートン微積分論争ニュートン記法回転する球体ニュートンの砲弾ニュートン・コーツの公式ニュートン法一般化ガウス・ニュートン法ニュートンフラクタルニュートンの恒等式ニュートン多項式ニュートンの回転軌道の定理ニュートン・オイラー方程式ニュートン数キス数問題ニュートンの商力の平行四辺形ニュートン・ピュイズーの定理絶対空間と時間光伝導エーテルニュートン級数テーブル
私生活	ウールズソープ・マナー（出生地）クランベリーパーク（ホーム）若いころ晩年リンゴの木宗教観オカルト研究科学革命コペルニクス的転回
関係	キャサリン・バートン（姪）ジョン・コンデュイット（義理の甥）アイザック・バロー（教授）ウィリアム・クラーク（メンター）ベンジャミン・プーリン（講師）ロジャー・コーツ（学生）ウィリアム・ウィストン（学生）ジョン・キール（弟子）ウィリアム・スタクリー（友人）ウィリアム・ジョーンズ（友人）アブラハム・ド・モアブル（友人）
描写	ニュートン・バイ・ブレイク（モノタイプ）パオロッツィ作「ニュートン」（彫刻）アイザック・ニュートンのガーゴイル天文学者の記念碑ベンジャミン・フランクリンの肖像
同名の人物	ニュートン（単位）ニュートンのゆりかごアイザック・ニュートン研究所アイザック・ニュートン・メダルアイザック・ニュートン望遠鏡アイザック・ニュートン望遠鏡グループ XMMニュートンサー・アイザック・ニュートン・シックスフォーム国立高等教育研究所アイザック・ニュートンニュートン国際フェローシップ
カテゴリー	アイザック・ニュートン

v t e 梱包の問題
抽象的なパッキング	ビンセット
円充填	円 /正三角形 /直角二等辺三角形 /正方形アポロニアンガスケット円充填定理ドイルスパイラルタムズ問題（球面上）
球詰め	アポロニアン有限球体の中で立方体の中にシリンダー内密集キスナンバー球詰め（ハミング）境界
その他の2次元パッキング	スクエアパッキング
その他の3Dパッキング	四面体楕円
パズル	コンウェイスロトウバー・グラーツマ