Контактное число

Контактное число (англ. kissing numbers, число Ньютона^[1][2], в химии соответствует координационному числу^[2]) — максимальное количество шаров единичного радиуса, которые могут одновременно касаться одного такого же шара в n-мерном евклидовом пространстве (предполагается, что шары не проникают друг в друга, то есть объём пересечения любых двух шаров равен нулю).

Следует отличать контактное число от контактного числа на решётке^[3] — аналогичного параметра для плотнейшей регулярной упаковки шаров. Вычисление контактного числа в общем случае до сих пор является нерешённой математической задачей.

История

В одномерном случае задача формулируется так: сколько отрезков единичной длины могут касаться такого же отрезка? Легко показать, что ответ — 2:

В двумерном случае можно интерпретировать задачу как нахождение максимального числа монеток, касающихся центральной. Легко доказать (просто приведя пример), что можно разместить 6 монет:

Это значит, что $N(2)\geqslant 6$. С другой стороны, каждая касающаяся окружность отсекает на центральной окружности дугу в 60°, и эти дуги не пересекаются, значит $N(2)\leqslant 360/60=6$. Видно, что в данном случае оценки сверху и снизу совпали и $N(2)= 6$.

Пример расположения 12 шаров

В трехмерном случае речь уже идет о шарах. Здесь также легко построить пример с 12 шарами, касающимися центрального — они расположены в вершинах икосаэдра — поэтому $N(3)\geqslant 12$. Данная нижняя оценка была известна ещё Ньютону.

Это расположение не плотное, между шарами будут довольно заметные зазоры. Оценка же сверху стала причиной известного спора между Ньютоном и Д. Грегори в 1694 году. Ньютон утверждал, что $N(3) = 12$, а Грегори возражал, что может быть можно расположить и 13 шаров. Он провёл вычисления, и выяснил, что площадь центрального шара более чем в 14 раз больше площади проекции каждого из касающихся шаров, так что $N(3) \leqslant 14$. Если позволить менять радиусы шаров всего на 2 % то оказывается возможным прислонить 14 шаров! Лишь в 1953 году в статье Шютте и ван дер Вардена^[4] была окончательно установлена правота Ньютона, несмотря на отсутствие у того строгого доказательства.

В четырёхмерном случае представить себе шар уже довольно сложно. Размещение 24 четырёхмерных сфер вокруг центральной было известно довольно давно, оно столь же регулярное, как и в двумерном случае и решает одновременно и задачу о контактном числе на решётке. Это то же размещение, что у целых единичных кватернионов. В явном виде это расположение было указано в 1900 году Госсетом.^[5] Ещё раньше оно было найдено (в эквивалентной задаче) в 1872 году российскими математиками Коркиным и Золотарёвым.^[6][7] Это расположение дало оценку снизу $N(4) \geqslant 24$. Попытки оценить это число сверху привели к развитию тонких методов теории функций, но не давали точного результата. Сначала удалось доказать, что $N(4) \leqslant 26$, потом удалось снизить верхнюю границу до 25. И лишь в 2003 году российскому математику Олегу Мусину удалось доказать, что $N(4) = 24$.^[8]

В размерностях 8 и 24 точная оценка была получена гораздо раньше^[9][10]. Доказательство основано на равенстве контактного числа и контактного числа на решётке в этих размерностях: решётки E8 (для размерности 8) и решётки Лича (для размерности 24).

Известные значения и оценки

На данный момент точные значения контактных чисел известны лишь для $n\leq 4$, а также для $n = 8$ и $n = 24$. Для некоторых других значений известны верхние и нижние оценки.

Размерность	Нижняя граница	Верхняя граница
1	2
2	6
3	12
4	24[8]
5	40	44[11]
6	72	78[11]
7	126	134[11]
8	240
9	306	364[11]
10	500	554
11	582	870
12	840	1 357
13	1 154[12]	2 069
14	1 606[12]	3 183
15	2 564	4 866
16	4 320	7 355
17	5 346	11 072
18	7 398	16 572[11]
19	10 688	24 812[11]
20	17 400	36 764[11]
21	27 720	54 584[11]
22	49 896	82 340
23	93 150	124 416
24	196 560

Применение

Задача имеет и вполне практическое применение в теории кодирования.

См. также

• Упаковка шаров
• Открытые математические проблемы

Примечания

1. ↑ Яглом, И. М. Проблема тринадцати шаров. — Киев: Вища школа, 1975. — 84 с.
2. ↑ ^{1 2} Дж. Конвей, Н. Слоэн Упаковки шаров, решётки и группы. — М.: Мир, 1990. — Т. 1. — 415 с. — ISBN 5-03-002368-2
3. ↑ Контактные числа на решётках: последовательность A001116 в OEIS
4. ↑ Schütte, K. and van der Waerden, B. L. (1953). «Das Problem der dreizehn Kugeln». Math. Ann. 125 (1): 325-334. DOI:10.1007/BF01343127.
5. ↑ Gosset, Thorold (1900). «On the regular and semi-regular figures in space of n dimensions». Messenger of Mathematics 29: 43–48.
6. ↑ Korkine A., Zolotareff G. (1872). «Sur les formes quadratiques positives quaternaires». Math. Ann. 5 (4): 581—583. DOI:10.1007/BF01442912. Рус. пер.: Золотарев Е. И. Полн. собр. соч. — Л.: Изд-во АН СССР, 1931. — С. 66—68.
7. ↑ Н.Н. Андреев, В.А. Юдин Арфиметический минимум квадратичной формы и сферические коды // Математическое просвещение. — 1998. — № 2. — С. 133-140.
8. ↑ ^{1 2} Мусин О. Р. Проблема двадцати пяти сфер // УМН. — 2003. — Т. 58. — № 4(352). — С. 153-154.
9. ↑ Левенштейн В. И. О границах для упаковок в n-мерном евклидовом пространстве // ДАН СССР. — 1979. — Т. 245. — С. 1299–1303.
10. ↑ A. M. Odlyzko, N. J. A. Sloane (1979). «New bounds on the number of unit spheres that can touch a unit sphere in n dimensions». J. Combin. Theory Ser. A 26: 210–214. DOI:10.1016/0097-3165(79)90074-8.
11. ↑ ^{1 2 3 4 5 6 7 8} Hans D. Mittelmann and Frank Vallentin [http://arxiv.org/abs/0902.1105 High-Accuracy Semidefinite Programming Bounds for Kissing Numbers] // Experimental Mathematics. — 2010. — Т. 19. — № 2. — С. 174-178.
12. ↑ ^{1 2} В. А. Зиновьев, Т. Эриксон Новые нижние оценки на контактное число для небольших размерностей // Пробл. передачи информ.. — 1999. — Т. 35. — № 4. — С. 3–11.

Ссылки

• Контактное число шаров и сферические коды. Математические этюды.
• Шарыгин, Г. И. Контактные числа и проблема тринадцати шаров // Математика. — Издательский дом «Первое сентября», 2007. — № 9 (623).
• Шарыгин, Г. И. Контактные числа и проблема тринадцати шаров // Потенциал. — 2009. — № 6.
• Арестов В. В., Бабенко А. Г. О схеме Дельсарта оценки контактных чисел // Труды Мат. ин-та им. В.А. Стеклова РАН. — 1997. — Т. 219. — С. 44-73.