Поцелуй номер

Геометрическая концепция

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

Другие названия числа поцелуя, которые использовались, — это число Ньютона (по имени создателя проблемы) и контактное число .

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

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

Известно наибольшее количество поцелуев

Одно измерение

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

Два измерения

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

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

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

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

Три измерения

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

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

Большие размеры

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

Существование высокосимметричной решетки E 8 и решетки Лича позволило получить известные результаты для n = 8 (где число контактов равно 240) и n = 24 (где оно равно 196 560). ^{[9] [10]} Число контактов в n- мерном пространстве неизвестно для других измерений.

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

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

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

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

Обобщение

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

Алгоритмы

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

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

Проблему числа поцелуев можно сформулировать как существование решения для набора неравенств . Пусть будет набором N D -мерных радиус-векторов центров сфер. Условие того, что этот набор сфер может лежать вокруг центральной сферы без перекрытия, таково: ^[15] ${\displaystyle x_{n}}$ $${\displaystyle \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\}}$$

Таким образом, проблема для каждого измерения может быть выражена в экзистенциальной теории вещественных чисел . Однако общие методы решения задач в этой форме требуют по крайней мере экспоненциальное время , поэтому эта проблема была решена только до четырех измерений. Добавляя дополнительные переменные, это можно преобразовать в одно уравнение четвертой степени в N ( N  − 1)/2 + DN переменных: ^[16] ${\displaystyle y_{nm}}$ $${\displaystyle \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 переменных. Для D = 24 измерений и N  =  196560  + 1 квартика будет иметь 19 322 732 544 переменных. Альтернативное утверждение в терминах геометрии расстояний дается квадратами расстояний между m ^-й и n ^-й сферами: ${\displaystyle R_{mn}}$ $${\displaystyle \exists R\ \{\forall _{n}\{R_{0n}=1\}\land \forall _{m,n:m<n}\{R_{mn}\geq 1\}\}}$$

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

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

• Равносторонний размер
• Сферический код
• Гекслет Содди
• Цилиндрическая сферическая упаковка

Примечания

1. Conway, John H. ; Neil JA Sloane (1999). Упаковки сфер, решетки и группы (3-е изд.). Нью-Йорк: Springer-Verlag. стр. 21. ISBN 0-387-98585-9.
2. Brass, Peter; Moser, WOJ; Pach, János (2005). Исследовательские проблемы в дискретной геометрии . Springer. стр. 93. ISBN 978-0-387-23815-9.
3. Миттельманн, Ганс Д.; Валлентин, Франк (2010). «Высокоточные границы полуопределенного программирования для целующихся чисел». Экспериментальная математика . 19 (2): 174–178. arXiv : 0902.1105 . Bibcode : 2009arXiv0902.1105M. doi : 10.1080/10586458.2010.10129070. S2CID  218279.
4. Обратите внимание, что в одном измерении «сферы» — это просто пары точек, разделенных единичным расстоянием. (Вертикальное измерение одномерной иллюстрации носит исключительно условный характер.) В отличие от более высоких измерений, необходимо указать, что внутренняя часть сфер (открытые интервалы единичной длины) не перекрывается, чтобы обеспечить конечную плотность упаковки.
5. См. также лемму 3.1 в Marathe, MV; Breu, H.; Hunt, HB; Ravi, SS; Rosenkrantz, DJ (1995). "Простые эвристики для графов единичных дисков". Networks . 25 (2): 59. arXiv : math/9409226 . doi :10.1002/net.3230250205.
6. Zong, Chuanming (2008). "The kissing number, blocking number and covering number of a convex body". В Goodman, Jacob E.; Pach, J├ínos; Pollack, Richard (ред.). Surveys on Discrete and Computational Geometry: Twenty Years Later (AMS-IMS-SIAM Joint Summer Research Conference, June 18–22, 2006, Snowbird, Utah) . Contemporary Mathematics. Vol. 453. Providence, RI: American Mathematical Society. pp. 529–548. doi :10.1090/conm/453/08812. ISBN 9780821842393. МР  2405694..
7. О. Р. Мусин (2003). «Задача о двадцати пяти шарах». Russ. Math. Surv . 58 (4): 794–795. Bibcode :2003RuMaS..58..794M. doi :10.1070/RM2003v058n04ABEH000651. S2CID  250839515.
8. Пфендер, Флориан; Циглер, Гюнтер М. (сентябрь 2004 г.). «Целующиеся числа, упаковки сфер и некоторые неожиданные доказательства» (PDF) . Notices of the American Mathematical Society : 873–883..
9. Левенштейн, Владимир И. (1979). «О границах для упаковок в n -мерном евклидовом пространстве». Доклады Академии наук СССР . 245 (6): 1299–1303.
10. Odlyzko, AM ; Sloane, NJA (1979). "Новые границы числа единичных сфер, которые могут касаться единичной сферы в n измерениях". Журнал комбинаторной теории . Серия A. 26 (2): 210–214. doi : 10.1016/0097-3165(79)90074-8 .
11. Вайсштейн, Эрик В. «Число поцелуев». MathWorld .
12. Мачадо, Фабрисио К.; Оливейра, Фернандо М. (2018). «Улучшение границы полуопределенного программирования для числа поцелуев с помощью использования полиномиальной симметрии». Experimental Mathematics . 27 (3): 362–369. arXiv : 1609.05167 . doi :10.1080/10586458.2017.1286273. S2CID  52903026.
13. Lagarias, Jeffrey C.; Zong, Chuanming (декабрь 2012 г.). «Загадки упаковки правильных тетраэдров» (PDF) . Notices of the American Mathematical Society : 1540–1549.
14. Каммер, Франк; Толей, Торстен (июль 2012 г.). «Алгоритмы аппроксимации для графов пересечений». Algorithmica . 68 (2): 312–336. doi :10.1007/s00453-012-9671-1. S2CID  3065780.
15. Числа m и n пробегают от 1 до N . — последовательность позиционных векторов N. Поскольку условие, стоящее за вторым квантором всеобщности ( ), не меняется при замене m и n , достаточно позволить этому квантору простираться чуть дальше . Для упрощения радиусы сфер предполагаются равными 1/2. ${\displaystyle x=(x_{n})_{N}}$ ${\displaystyle \forall }$ ${\displaystyle m,n:m<n}$
16. Что касается матрицы, то нужны только элементы, имеющие m  <  n . Или, что эквивалентно, матрицу можно считать антисимметричной. В любом случае матрица имеет всего N ( N  − 1)/2 свободных скалярных переменных. Кроме того, есть N D -мерных векторов x _n , которые соответствуют матрице из N векторов-столбцов. ${\displaystyle y=(y_{mn})_{N\times {N}}}$ ${\displaystyle x=(x_{nd})_{N\times D}}$

Ссылки

• Т. Асте и Д. Уайр. В поисках идеальной упаковки (Institute Of Physics Publishing London 2000) ISBN 0-7503-0648-3 
• Таблица самых высоких известных в настоящее время чисел поцелуев, поддерживаемая Габриэле Небе и Нилом Слоаном (нижние границы)
• Bachoc, Christine ; Vallentin, Frank (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.

Внешние ссылки

• Грайм, Джеймс. "Kissing Numbers" (видео) . youtube . Брэди Харан . Архивировано из оригинала 2021-12-12 . Получено 11 октября 2018 .