Целующий номер - Kissing number

В геометрия, то номер поцелуя из математическое пространство определяется как наибольшее количество неперекрывающихся единиц сферы которые могут быть расположены в этом пространстве так, чтобы каждый из них касался общей единичной сферы. Для данного упаковка сфер (расположение сфер) в данном пространстве, число поцелуев также может быть определено для каждой отдельной сферы как количество сфер, которых она касается. Для решетка упаковка числа поцелуев одинакова для каждой сферы, но для произвольной упаковки число поцелуев может варьироваться от одной сферы к другой.

Другие использованные названия числа поцелуев: Число Ньютона (после автора проблемы), и Контактный телефон.

В целом проблема с числом поцелуев ищет максимально возможное число поцелуев для п-мерные сферы в (п + 1) -мерный Евклидово пространство. Обычные сферы соответствуют двумерным замкнутым поверхностям в трехмерном пространстве.

Нахождение числа поцелуев, когда центры сфер ограничены линией (одномерный случай) или плоскостью (двумерный случай), тривиально. Доказать решение трехмерного случая, несмотря на то, что его легко концептуализировать и смоделировать в физическом мире, ускользало от математиков до середины 20 века.^[1][2] Решения в более высоких измерениях значительно сложнее, и только несколько случаев были решены точно. Для других исследования определили верхнюю и нижнюю границы, но не точные решения.^[3]

Известные величайшие числа поцелуев

В одном измерении^[4] число поцелуев - 2:

В двух измерениях число поцелуев - 6:

Доказательство: Рассмотрим круг с центром C которого касаются круги с центрами C₁, C₂, .... Рассмотрим лучи C C_я. Все эти лучи исходят из одного центра C, поэтому сумма углов между соседними лучами равна 360 °.

Предположим от противного, что касающихся кругов больше шести. Тогда хотя бы два соседних луча, скажем C C₁ и C C₂, разделены углом менее 60 °. Сегменты С С_я одинаковой длины - 2р - для всех я. Следовательно, треугольник C C₁ C₂ является равнобедренный, а его третья сторона - C₁ C₂ - имеет длину стороны менее 2р. Следовательно, круги 1 и 2 пересекаются - противоречие.^[5]

Высоко симметричная реализация числа поцелуев 12 в трех измерениях заключается в совмещении центров внешних сфер с вершинами правильный икосаэдр. Это оставляет чуть больше 0,1 радиуса между двумя соседними сферами.

В трех измерениях число поцелуев равно 12, но точное значение установить было гораздо труднее, чем в измерениях один и два. Легко расположить 12 сфер так, чтобы каждая касалась центральной сферы, но остается много места, и не очевидно, что нет возможности упаковать 13-ю сферу. (Фактически, существует так много дополнительного пространства, что любые две из 12 внешних сфер могут поменяться местами посредством непрерывного движения, при этом ни одна из внешних сфер не теряет контакта с центральной.) Это стало предметом известного разногласия между математиками. Исаак Ньютон и Дэвид Грегори. Ньютон правильно считал, что предел равен 12; Грегори подумал, что подойдет и 13-й. Некоторые неполные доказательства того, что Ньютон был прав, были предложены в девятнадцатом веке, особенно одно из них: Рейнхольд Хоппе, но первое правильное доказательство (согласно Брассу, Мозеру и Паху) появилось только в 1953 году.^[1][2][6]

Двенадцать соседей центральной сферы соответствуют максимальной объемной координационный номер атома в кристаллическая решетка в котором все атомы имеют одинаковый размер (как в химическом элементе). Координационное число 12 находится в кубический плотно упакованный или шестиугольный плотно упакованный структура.

В четырех измерениях в течение некоторого времени было известно, что ответ будет либо 24, либо 25. Несложно создать упаковку из 24 сфер вокруг центральной сферы (можно разместить сферы в вершинах соответственно масштабированной сферы). 24-элементный с центром в начале координат). Как и в случае с трехмерным пространством, остается много места - фактически даже больше, чем для п = 3 - так что ситуация была еще менее ясной. В 2003 году Олег Мусин подтвердил целующий номер для п = 4 до 24, используя тонкий трюк.^[7][8]

Число поцелуев в п размеры неизвестно для п > 4, кроме п = 8 (240), и п = 24 (196,560).^[9][10] Результаты в этих размерах связаны с существованием высокосимметричных решеток: E₈ решетка и Решетка пиявки.

Если договоренности ограничены решетка расположения, в которых центры сфер все лежат в точках в решетка, то это ограниченное число поцелуев известно п = От 1 до 9 и п = 24 измерения.^[11] Для измерений 5, 6 и 7 расположение с наивысшим известным числом поцелуев, обнаруженное до сих пор, является оптимальным расположением решетки, но не исключено существование нерешетчатого расположения с более высоким числом поцелуев.

Некоторые известные границы

В следующей таблице перечислены некоторые известные границы числа поцелуев в различных измерениях.^[3] Размеры, в которых известно число поцелуев, выделены жирным шрифтом.

Приблизительные оценки объема показывают, что число поцелуев п размеры растет экспоненциально в п. База экспоненциального роста неизвестна. Серая область на приведенном выше графике представляет возможные значения между известными верхней и нижней границами. Кружки обозначают точно известные значения.

Измерение	Ниже граница	Верхний граница
1	2
2	6
3	12
4	24[7]
5	40	44
6	72	78
7	126	134
8	240
9	306	364
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
19	10,668	24,812
20	17,400	36,764
21	27,720	54,584
22	49,896	82,340
23	93,150	124,416
24	196,560

Обобщение

Проблема числа поцелуев может быть обобщена на задачу нахождения максимального количества неперекрывающихся конгруэнтный копии любых выпуклое тело касаются данной копии тела. Существуют разные версии проблемы в зависимости от того, должны ли копии только соответствовать исходному телу, переводит оригинального корпуса, или переведенный решеткой. Для правильный тетраэдр Например, известно, что как решеточное число поцелуев, так и трансляционное число поцелуев равны 18, тогда как конгруэнтное число поцелуев не менее 56.^[13]

Алгоритмы

Есть несколько аппроксимационные алгоритмы на графы пересечений где коэффициент приближения зависит от числа поцелуев.^[14] Например, существует алгоритм 10-аппроксимации с полиномиальным временем для нахождения максимального непересекающегося подмножества набора повернутых единичных квадратов.

Математическое утверждение

Проблема числа поцелуев может быть сформулирована как существование решения множества неравенство. Позволять ${\displaystyle x_{n}}$ быть набором N D-мерные векторы положения центров сфер. Условие того, что этот набор сфер может лежать вокруг центральной сферы без перекрытия:

${\displaystyle \exists x\ \left\{\forall _{n}\{x_{n}^{T}x_{n}=1\}\land \forall _{m,n:m\neq n}\{(x_{n}-x_{m})^{T}(x_{n}-x_{m})\geq 1\}\right\}}$ ^[15]

Таким образом, проблема для каждого измерения может быть выражена в экзистенциальная теория реальности. Однако общие методы решения задач в таком виде требуют не менее экспоненциальное время вот почему эта проблема была решена только до четырех измерений. Добавляя дополнительные переменные, ${\displaystyle y_{nm}}$ это можно преобразовать в одиночный уравнение четвертой степени в N(N-1)/2 + DN переменные:

${\displaystyle \exists xy\ \left\{\sum _{n}(x_{n}^{T}x_{n}-1)^{2}+\sum _{m,n:m<n}{\Big (}(x_{n}-x_{m})^{T}(x_{n}-x_{m})-1-(y_{nm})^{2}{\Big )}^{2}=0\right\}}$ ^[16]

Поэтому для решения дела в D = 5 размеров и N = 40 + 1 векторов было бы эквивалентно определению существования реальных решений полинома четвертой степени от 1025 переменных. Для D = 24 размера и N = 196560 + 1, квартика будет иметь 19 322 732 544 переменных. Альтернативное утверждение с точки зрения геометрия расстояния дается квадратами расстояний ${\displaystyle R_{mn}}$ между тем м^th и п^th сфера.

${\displaystyle \exists R\ \{\forall _{n}\{R_{0n}=1\}\land \forall _{m,n:m<n}\{R_{mn}\geq 1\}\}}$

Это необходимо дополнить условием, что Определитель Кэли-Менгера равен нулю для любого набора точек, образующего (D + 1) симплекс в D размеры, так как этот объем должен быть нулевым. Параметр ${\displaystyle R_{mn}=1+{y_{mn}}^{2}}$ дает набор одновременных полиномиальных уравнений всего за у которые необходимо решать только для реальных значений. Эти два метода, будучи полностью эквивалентными, имеют различное применение. Например, во втором случае можно случайным образом изменить значения у небольшими суммами, чтобы попытаться минимизировать полином в терминаху.

Смотрите также

• Равносторонний размер
• Сферический код
• Гекслет Содди
• Набивка цилиндрической сферы

Примечания

1. Конвей, Джон Х.; Нил Дж. А. Sloane (1999). Сферические упаковки, решетки и группы (3-е изд.). Нью-Йорк: Springer-Verlag. п.21. ISBN  0-387-98585-9.
2. Брасс, Питер; Moser, W.O.J .; Пах, Янош (2005). Проблемы исследования дискретной геометрии. Springer. п.93. ISBN  978-0-387-23815-9.
3. Mittelmann, Hans D .; Валлентин, Франк (2009). «Высокоточные полуопределенные границы программирования для целующихся чисел». Экспериментальная математика. 19: 174–178. arXiv:0902.1105. Bibcode:2009arXiv0902.1105M.
4. Обратите внимание, что в одном измерении «сферы» - это просто пары точек, разделенных единичным расстоянием. (Вертикальное измерение одномерной иллюстрации просто вызывает воспоминания.) В отличие от более высоких измерений, необходимо указать, что внутренняя часть сфер (открытые интервалы единичной длины) не перекрываются, чтобы была конечная упаковка. плотность.
5. Также лемму 3.1 в Marathe, M. V .; Breu, H .; Хант, H. B .; Ravi, S. S .; Розенкранц, Д. Дж. (1995). «Простая эвристика для графов единичного диска». Сети. 25 (2): 59. arXiv:математика / 9409226. Дои:10.1002 / нетто.3230250205.
6. Zong, Chuanming (2008), «Число поцелуев, число блокировки и число покрытия выпуклого тела», Goodman, Jacob E .; Пах, Йонинос; Поллак, Ричард (ред.), Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя (Совместная летняя исследовательская конференция AMS-IMS-SIAM, 18–22 июня 2006 г., Snowbird, Юта), Современная математика, 453, Провиденс, Род-Айленд: Американское математическое общество, стр. 529–548, Дои:10.1090 / conm / 453/08812, ISBN  9780821842393, МИСТЕР  2405694.
7. О. Р. Мусин (2003). «Проблема двадцати пяти сфер». Русь. Математика. Surv. 58 (4): 794–795. Bibcode:2003RuMaS..58..794M. Дои:10.1070 / RM2003v058n04ABEH000651.
8. Пфендер, Флориан; Циглер, Гюнтер М. (Сентябрь 2004 г.). «Целующиеся числа, упаковки сфер и некоторые неожиданные доказательства» (PDF). Уведомления Американского математического общества: 873–883..
9. Левенштейн, Владимир И. (1979). "О границах для упаковок в n-мерном евклидовом пространстве" [О границах для упаковок в п-мерное евклидово пространство. Доклады Академии Наук СССР (на русском). 245 (6): 1299–1303.
10. Одлызко, А.М., Слоан, Н. Дж. А. Новые границы количества единичных сфер, которые могут касаться единичной сферы в n измерениях. J. Combin. Теория Сер. А 26 (1979), нет. 2, 210—214
11. Вайсштейн, Эрик В. "Целующийся номер". MathWorld.
12. В. А. Зиновьев, Т. Эриксон (1999). Новые нижние оценки на контактное число для небольших размерностей. Пробл. Передачи Информ. (на русском). 35 (4): 3–11. Английский перевод: Зиновьев В.А., Эриксон Т. (1999). «Новые нижние границы для контактных номеров в малых размерах». Проблемы передачи информации. 35 (4): 287–294. МИСТЕР  1737742.
13. Lagarias, Jeffrey C .; Цзун, Чуаньмин (декабрь 2012 г.). «Тайны упаковки правильных тетраэдров» (PDF). Уведомления Американского математического общества: 1540–1549.
14. Каммер, Франк; Толей, Торстен (июль 2012 г.). «Алгоритмы аппроксимации графов пересечений». Алгоритмика. 68 (2): 312–336. Дои:10.1007 / s00453-012-9671-1.
15. Числа м и п бегать от 1 до N. ${\displaystyle x=(x_{n})_{N}}$ это последовательность N позиционные векторы. В качестве условия второго универсального квантора (${\displaystyle \forall }$) не меняется, если м и п обменяны, достаточно позволить этому квантору простираться чуть более ${\displaystyle m,n:m<n}$. Радиусы сфер для упрощения приняты равными 1/2.
16. По поводу матрицы ${\displaystyle y=(y_{mn})_{N\times {N}}}$ только записи, имеющие м<п необходимы. Или, что эквивалентно, матрицу можно считать антисимметричной. В любом случае матрица простоN(N - 1) 2 свободных скалярных переменных. Кроме того, есть N D-мерные векторы Икс_п, что соответствует матрице ${\displaystyle x=(x_{nd})_{N\times {D}}}$ из N векторы-столбцы.

Рекомендации

• Т. Асте и Д. Уир В поисках идеальной упаковки (Лондонский институт физики, 2000 г.) ISBN  0-7503-0648-3
• Таблица самых высоких чисел поцелуев, известных в настоящее время поддерживается Габриэле Небе и Нил Слоан (нижняя граница)
• Бачок, Кристина; Валлентин, Франк (2008), "Новые верхние границы для целующихся чисел из полуопределенного программирования", Журнал Американского математического общества, 21 (3): 909–924, arXiv:math.MG/0608426, Дои:10.1090 / S0894-0347-07-00589-9, МИСТЕР  2393433

внешняя ссылка

• Грайм, Джеймс. «Целующиеся числа» (видео). YouTube. Брэди Харан. Получено 11 октября 2018.