Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

Поцелуи-1d.svg

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

Поцелуи-2d.svg

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

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

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

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

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

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

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

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

Некоторые известные границы [ править ]

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

Приблизительные оценки объема показывают, что число поцелуев в n измерениях растет экспоненциально в n . База экспоненциального роста неизвестна. Серая область на приведенном выше графике представляет возможные значения между известными верхней и нижней границами. Кружки обозначают точно известные значения.
ИзмерениеНижняя
граница		Верхняя
граница
12
26
312
424 [7]
54044
67278
7126134
8240
9306364
10500554
11582870
128401,357
131,154 [12]2 069
141 606 [12]3 183
152,5644 866
1643207 355
175 34611 072
187 39816 572
1910 66824 812
2017 40036 764
21 год27 72054 584
2249 89682 340
2393 150124 416
24196 560

Обобщение [ править ]

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

Алгоритмы [ править ]

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

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

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

 [15]

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

 [16]

Следовательно, решение случая в D  = 5 измерениях и N  =  40  + 1 векторах было бы эквивалентно определению существования реальных решений полинома четвертой степени от 1025 переменных. Для измерений D = 24 и N  =  196560  + 1 квартика будет иметь 19 322 732 544 переменных. Альтернативное утверждение с точки зрения геометрии расстояний дается квадратом расстояний между m- й и n- й сферами.

Это должно быть дополнено условием, что определитель Кэли – Менгера равен нулю для любого набора точек, который образует ( D  + 1) симплекс в D измерениях, так как этот объем должен быть равен нулю. Установка дает набор одновременных полиномиальных уравнений только для y, которые необходимо решать только для реальных значений. Эти два метода, будучи полностью эквивалентными, имеют различное применение. Например, во втором случае можно случайным образом изменить значения y на небольшие количества, чтобы попытаться минимизировать многочлен в терминах  y .

См. Также [ править ]

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

Примечания [ править ]

  1. ^ a b Конвей, Джон Х .; Нил Дж. А. Слоан (1999). Сферические упаковки, решетки и группы (3-е изд.). Нью-Йорк: Springer-Verlag. п. 21 . ISBN 0-387-98585-9.
  2. ^ a b Брасс, Питер; Moser, WOJ; Пах, Янош (2005). Проблемы исследования дискретной геометрии . Springer. п. 93 . ISBN 978-0-387-23815-9.
  3. ^ a b Mittelmann, Hans D .; Валлентин, Франк (2009). «Высокоточные полуопределенные границы программирования для целующихся чисел». Экспериментальная математика . 19 : 174–178. arXiv : 0902.1105 . Bibcode : 2009arXiv0902.1105M .
  4. ^ Обратите внимание, что в одном измерении «сферы» - это просто пары точек, разделенных единичным расстоянием. (Вертикальное измерение одномерной иллюстрации просто вызывает воспоминания.) В отличие от более высоких измерений, необходимо указать, что внутренняя часть сфер (открытые интервалы единичной длины) не перекрываются, чтобы была конечная упаковка плотность.
  5. ^ См. Также лемму 3.1 в Marathe, MV; Breu, H .; Хант, HB; Рави, СС; Розенкранц, DJ (1995). «Простая эвристика для графов единичного диска». Сети . 25 (2): 59. arXiv : math / 9409226 . DOI : 10.1002 / нетто.3230250205 .
  6. ^ Zong, Chuanming (2008), «Число поцелуев, число блокировки и число покрытия выпуклого тела», в Goodman, Jacob E .; Пах, Йонинос; Ричард Поллак (ред.), Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя (совместная летняя исследовательская конференция AMS-IMS-SIAM, 18–22 июня 2006 г., Сноуберд, Юта) , Contemporary Mathematics, 453 , Providence, RI: American Mathematical общ . , С. 529-548, DOI : 10,1090 / conm / 453/08812 , ISBN 9780821842393, Руководство по ремонту  2405694.
  7. ^ а б О. Р. Мусин (2003). «Проблема двадцати пяти сфер». Русь. Математика. Surv . 58 (4): 794–795. Bibcode : 2003RuMaS..58..794M . DOI : 10.1070 / RM2003v058n04ABEH000651 .
  8. ^ Пфендер, Флориан; Циглер, Гюнтер М. (сентябрь 2004 г.). «Целующиеся числа, упаковки сфер и некоторые неожиданные доказательства» (PDF) . Уведомления Американского математического общества : 873–883. .
  9. ↑ Левенштейн, Владимир I. (1979). "О границах для упаковок в п-мерное евклидово пространство" [О границах для упаковок в п - мерное евклидово пространства]. Доклады Академии Наук СССР . 245 (6): 1299–1303.
  10. ^ Odlyzko, AM , Sloane, NJA Новые границы количества единичных сфер, которые могут касаться единичной сферы в n измерениях. J. Combin. Теория Сер. А 26 (1979), нет. 2, 210—214
  11. ^ Вайсштейн, Эрик В. «Целующийся номер» . MathWorld .
  12. ^ а б В. А. Зиновьев, Т. Эриксон (1999).Новые нижние оценки на контактное число для небольших размерностей. Пробл. Передачи Информ. (на русском). 35 (4): 3–11.Английский перевод: В.А. Зиновьев, Т. Эриксон (1999). «Новые нижние границы для контактных номеров в малых размерах». Проблемы передачи информации . 35 (4): 287–294. Руководство по ремонту 1737742 . 
  13. ^ Лагариас, Джеффри С .; Цзун, Чуаньмин (декабрь 2012 г.). "Тайны упаковки правильных тетраэдров" (PDF) . Уведомления Американского математического общества : 1540–1549.
  14. ^ Каммер, Франк; Толей, Торстен (июль 2012 г.). «Алгоритмы аппроксимации графов пересечений». Алгоритмика . 68 (2): 312–336. DOI : 10.1007 / s00453-012-9671-1 .
  15. ^ Числа т и п бежать от 1 до N . - последовательность из N позиционных векторов. Поскольку условие, стоящее за вторым универсальным квантором (), не меняется, если m и n меняютсяместами, достаточно позволить этому квантору простираться чуть выше. Радиусы сфер для упрощения приняты равными 1/2.
  16. ^ Что касается матрицы, нужнытолько элементы с m < n . Или, что эквивалентно, матрицу можно считать антисимметричной. В любом случае матрица имеет только N ( N  - 1) \ 2 свободных скалярных переменных. Кроме того, существуют N D -мерных векторов x n , которые соответствуют матрицеиз N векторов-столбцов.

Ссылки [ править ]

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

Внешние ссылки [ править ]

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