Целующий номер ber

редактировать

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

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

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

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

Содержание

1 Известные наибольшие числа поцелуев
2 Некоторые известные границы
3 Обобщение
4 Алгоритмы
5 Математическое утверждение
6 См. Также
7 Примечания
8 Ссылки
9 Внешние ссылки

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

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

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

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

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

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

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

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

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

Число поцелуев в n измерениях неизвестно для n>4, за исключением n. = 8 (240) и n = 24 (196 560). Результаты в этих размерах проистекают из существования высокосимметричных решеток: E8решетки и решетки Пиявки.

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

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

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

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

Размер	Нижняя. граница	Верхняя. граница
1	2
2	6
3	12
4	24
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	2,069
14	1,606	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.

Алгоритмы

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

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

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

∃ x {∀ n {xn T xn = 1} ∧ ∀ m, n: m ≠ n {(xn - xm) T (xn - хм) ≥ 1}} {\ Displaystyle \ существует х \ \ 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 \}}

{\ 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 \}}

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

∃ xy {∑ n (xn T xn - 1) 2 + ∑ m, n: m < n ( ( x n − x m) T ( x n − x m) − 1 − ( y n m) 2) 2 = 0 } {\displaystyle \exists xy\ \left\{\sum _{n}(x_{n}^{T}x_{n}-1)^{2}+\sum _{m,n:m

{\ 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_ {нм}) ^ {2} {\ Big)} ^ {2} = 0 \ right \}}

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

∃ R {∀ n {R 0 n = 1} ∧ ∀ m, n: m < n { R m n ≥ 1 } } {\displaystyle \exists R\ \{\forall _{n}\{R_{0n}=1\}\land \forall _{m,n:m

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

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

См. Также

Примечания

Ссылки

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

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

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