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

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

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

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

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

Известные самые популярные номера поцелуев

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

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

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

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

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

Предположим от противного, что соприкасающихся кругов больше шести. Тогда по крайней мере два соседних луча, скажем и CC _CC 2 , 1 _{разделены} углом менее 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, либо 25. Несложно создать упаковку из 24 сфер вокруг центральной сферы (можно разместить сферы в вершинах подходящего масштаба 24-клеточной центрированной сферы). в источнике). Как и в трехмерном случае, остается много места — даже больше, чем при n = 3, — поэтому ситуация была еще менее ясной. В 2003 году Олег Мусин доказал, что число поцелуев при n = 4 равно 24. ^[7]^[8]

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

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

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

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

Измерение	Ниже граница	Верхний граница
1	2
2	6
3	12
4	24 ^[7]
5	40	44
6	72	78
7	126	134
8	240
9	306	363
10	510	553
11	592	868
12	840	1,355
13	1,154	2,064
14	1,932	3,174
15	2,564	4,853
16	4,320	7,320
17	5,346	10,978
18	7,398	16,406
19	10,668	24,417
20	17,400	36,195
21	27,720	53,524
22	49,896	80,810
23	93,150	122,351
24	196,560

Обобщение

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

Алгоритмы

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

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

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

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

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

См. также

Примечания

↑ Перейти обратно: Перейти обратно: ^а ^б Конвей, Джон Х .; Нил Дж. А. Слоан (1999). Сферические упаковки, решетки и группы (3-е изд.). Нью-Йорк: Springer-Verlag. п. 21 . ISBN 0-387-98585-9 .
↑ Перейти обратно: Перейти обратно: ^а ^б Брасс, Питер; Мозер, WOJ; Пах, Янош (2005). Проблемы исследования дискретной геометрии . Спрингер. п. 93 . ISBN 978-0-387-23815-9 .
^ Миттельманн, Ганс Д.; Валлентин, Франк (2010). «Ограничения полуопределенного программирования высокой точности для чисел поцелуев». Экспериментальная математика . 19 (2): 174–178. arXiv : 0902.1105 . Бибкод : 2009arXiv0902.1105M . дои : 10.1080/10586458.2010.10129070 . S2CID 218279 .
^ Обратите внимание, что в одном измерении «сферы» представляют собой просто пары точек, разделенных единичным расстоянием. (Вертикальный размер одномерной иллюстрации просто наводит на размышления.) В отличие от более высоких измерений, необходимо указать, что внутренняя часть сфер (открытые интервалы единичной длины) не перекрываются, чтобы существовала конечная упаковка. плотность.
^ См. также лемму 3.1 в Марат, МВ; Бреу, Х.; Хант, HB; Рави, СС; Розенкранц, диджей (1995). «Простые эвристики для единичных дисковых графов». Сети . 25 (2): 59. arXiv : math/9409226 . дои : 10.1002/net.3230250205 .
^ Цзун, Чуаньмин (2008). «Поцелуйное число, блокирующее число и покрывающее число выпуклого тела». В Гудмане, Джейкоб Э.; Пач, Жинос; Поллак, Ричард (ред.). Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя (Совместная летняя исследовательская конференция AMS-IMS-SIAM, 18–22 июня 2006 г., Сноуберд, Юта) . Современная математика. Том. 453. Провиденс, Род-Айленд: Американское математическое общество. стр. 529–548. дои : 10.1090/conm/453/08812 . ISBN 9780821842393 . МР 2405694 . .
↑ Перейти обратно: Перейти обратно: ^а ^б О. Р. Мусин (2003). «Проблема двадцати пяти сфер». Расс. Математика. Сурв . 58 (4): 794–795. Бибкод : 2003РуМаС..58..794М . дои : 10.1070/RM2003v058n04ABEH000651 . S2CID 250839515 .
^ Пфендер, Флориан; Циглер, Гюнтер М. (сентябрь 2004 г.). «Целующиеся числа, упаковки сфер и некоторые неожиданные доказательства» (PDF) . Уведомления Американского математического общества : 873–883. .
^ Levenshtein, Vladimir I. (1979). "О границах для упаковок в n-мерном евклидовом пространстве" [On bounds for packings in n -dimensional Euclidean space]. Doklady Akademii Nauk SSSR (in Russian). 245 (6): 1299–1303.
^ Одлизко, А.М. ; Слоан, Нью-Джерси (1979). «Новые ограничения на количество единичных сфер, которые могут касаться единичной сферы в n измерениях» . Журнал комбинаторной теории . Серия А. 26 (2): 210–214. дои : 10.1016/0097-3165(79)90074-8 .
^ Вайсштейн, Эрик В. «Номер поцелуев» . Математический мир .
^ Мачадо, Фабрисио К.; Оливейра, Фернандо М. (2018). «Улучшение полуопределенной программной границы числа поцелуев путем использования полиномиальной симметрии». Экспериментальная математика . 27 (3): 362–369. arXiv : 1609.05167 . дои : 10.1080/10586458.2017.1286273 . S2CID 52903026 .
^ Лагариас, Джеффри С.; Цзун, Чуаньмин (декабрь 2012 г.). «Тайны упаковки правильных тетраэдров» (PDF) . Уведомления Американского математического общества : 1540–1549.
^ Каммер, Фрэнк; Толи, Торстен (июль 2012 г.). «Алгоритмы аппроксимации графов пересечений» . Алгоритмика . 68 (2): 312–336. дои : 10.1007/s00453-012-9671-1 . S2CID 3065780 .
^ Числа m и n 1 до N. принимаются от $x=(x_{n})_{N}$ представляет собой последовательность N позиционных векторов. В качестве условия второго квантора всеобщности ( $\forall$ ) не меняется, если поменять местами m и n , достаточно позволить этому квантору простираться чуть выше $m,n:m<n$ . Для упрощения радиусы сфер принимаются равными 1/2.
^ О матрице $y=(y_{mn})_{N\times {N}}$ только записи, имеющие m < n необходимы . Или, что эквивалентно, матрицу можно считать антисимметричной. В любом случае матрица имеет всего N ( N − 1)/2 свободных скалярных переменных. Кроме того, существуют N D -мерные векторы x _n , соответствующие матрице $x=(x_{nd})_{N\times D}$ из N векторов-столбцов.

Ссылки

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

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

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

[Conway-1] Перейти обратно: Перейти обратно: ^а ^б Конвей, Джон Х .; Нил Дж. А. Слоан (1999). Сферические упаковки, решетки и группы (3-е изд.). Нью-Йорк: Springer-Verlag. п. 21 . ISBN 0-387-98585-9 .

[Brass-2] Перейти обратно: Перейти обратно: ^а ^б Брасс, Питер; Мозер, WOJ; Пах, Янош (2005). Проблемы исследования дискретной геометрии . Спрингер. п. 93 . ISBN 978-0-387-23815-9 .

[Mittlemann-3] Миттельманн, Ганс Д.; Валлентин, Франк (2010). «Ограничения полуопределенного программирования высокой точности для чисел поцелуев». Экспериментальная математика . 19 (2): 174–178. arXiv : 0902.1105 . Бибкод : 2009arXiv0902.1105M . дои : 10.1080/10586458.2010.10129070 . S2CID 218279 .

[4] Обратите внимание, что в одном измерении «сферы» представляют собой просто пары точек, разделенных единичным расстоянием. (Вертикальный размер одномерной иллюстрации просто наводит на размышления.) В отличие от более высоких измерений, необходимо указать, что внутренняя часть сфер (открытые интервалы единичной длины) не перекрываются, чтобы существовала конечная упаковка. плотность.

[5] См. также лемму 3.1 в Марат, МВ; Бреу, Х.; Хант, HB; Рави, СС; Розенкранц, диджей (1995). «Простые эвристики для единичных дисковых графов». Сети . 25 (2): 59. arXiv : math/9409226 . дои : 10.1002/net.3230250205 .

[6] Цзун, Чуаньмин (2008). «Поцелуйное число, блокирующее число и покрывающее число выпуклого тела». В Гудмане, Джейкоб Э.; Пач, Жинос; Поллак, Ричард (ред.). Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя (Совместная летняя исследовательская конференция AMS-IMS-SIAM, 18–22 июня 2006 г., Сноуберд, Юта) . Современная математика. Том. 453. Провиденс, Род-Айленд: Американское математическое общество. стр. 529–548. дои : 10.1090/conm/453/08812 . ISBN 9780821842393 . МР 2405694 . .

[Musin-7] Перейти обратно: Перейти обратно: ^а ^б О. Р. Мусин (2003). «Проблема двадцати пяти сфер». Расс. Математика. Сурв . 58 (4): 794–795. Бибкод : 2003РуМаС..58..794М . дои : 10.1070/RM2003v058n04ABEH000651 . S2CID 250839515 .

[8] Пфендер, Флориан; Циглер, Гюнтер М. (сентябрь 2004 г.). «Целующиеся числа, упаковки сфер и некоторые неожиданные доказательства» (PDF) . Уведомления Американского математического общества : 873–883. .

[9] Levenshtein, Vladimir I. (1979). "О границах для упаковок в n-мерном евклидовом пространстве" [On bounds for packings in n -dimensional Euclidean space]. Doklady Akademii Nauk SSSR (in Russian). 245 (6): 1299–1303.

[10] Одлизко, А.М. ; Слоан, Нью-Джерси (1979). «Новые ограничения на количество единичных сфер, которые могут касаться единичной сферы в n измерениях» . Журнал комбинаторной теории . Серия А. 26 (2): 210–214. дои : 10.1016/0097-3165(79)90074-8 .

[11] Вайсштейн, Эрик В. «Номер поцелуев» . Математический мир .

[Machado-12] Мачадо, Фабрисио К.; Оливейра, Фернандо М. (2018). «Улучшение полуопределенной программной границы числа поцелуев путем использования полиномиальной симметрии». Экспериментальная математика . 27 (3): 362–369. arXiv : 1609.05167 . дои : 10.1080/10586458.2017.1286273 . S2CID 52903026 .

[13] Лагариас, Джеффри С.; Цзун, Чуаньмин (декабрь 2012 г.). «Тайны упаковки правильных тетраэдров» (PDF) . Уведомления Американского математического общества : 1540–1549.

[14] Каммер, Фрэнк; Толи, Торстен (июль 2012 г.). «Алгоритмы аппроксимации графов пересечений» . Алгоритмика . 68 (2): 312–336. дои : 10.1007/s00453-012-9671-1 . S2CID 3065780 .

[15] Числа m и n 1 до N. принимаются от $x=(x_{n})_{N}$ представляет собой последовательность N позиционных векторов. В качестве условия второго квантора всеобщности ( $\forall$ ) не меняется, если поменять местами m и n , достаточно позволить этому квантору простираться чуть выше $m,n:m<n$ . Для упрощения радиусы сфер принимаются равными 1/2.

[16] О матрице $y=(y_{mn})_{N\times {N}}$ только записи, имеющие m < n необходимы . Или, что эквивалентно, матрицу можно считать антисимметричной. В любом случае матрица имеет всего N ( N − 1)/2 свободных скалярных переменных. Кроме того, существуют N D -мерные векторы x _n , соответствующие матрице $x=(x_{nd})_{N\times D}$ из N векторов-столбцов.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

v т и сэр Исаак Ньютон
Publications	Fluxions (1671) De Motu (1684) Principia (1687) Opticks (1704) Queries (1704) Arithmetica (1707) De Analysi (1711)
Other writings	Quaestiones (1661–1665) "standing on the shoulders of giants" (1675) Notes on the Jewish Temple (c. 1680) "General Scholium" (1713; "hypotheses non fingo" ) Ancient Kingdoms Amended (1728) Corruptions of Scripture (1754)
Contributions	Calculus fluxion Impact depth Inertia Newton disc Newton polygon Newton–Okounkov body Newton's reflector Newtonian telescope Newton scale Newton's metal Spectrum Structural coloration
Newtonianism	Bucket argument Newton's inequalities Newton's law of cooling Newton's law of universal gravitation post-Newtonian expansion parameterized gravitational constant Newton–Cartan theory Schrödinger–Newton equation Newton's laws of motion Kepler's laws Newtonian dynamics Newton's method in optimization Apollonius's problem truncated Newton method Gauss–Newton algorithm Newton's rings Newton's theorem about ovals Newton–Pepys problem Newtonian potential Newtonian fluid Classical mechanics Corpuscular theory of light Leibniz–Newton calculus controversy Newton's notation Rotating spheres Newton's cannonball Newton–Cotes formulas Newton's method generalized Gauss–Newton method Newton fractal Newton's identities Newton polynomial Newton's theorem of revolving orbits Newton–Euler equations Newton number kissing number problem Newton's quotient Parallelogram of force Newton–Puiseux theorem Absolute space and time Luminiferous aether Newtonian series table
Personal life	Woolsthorpe Manor (birthplace) Cranbury Park (home) Early life Later life Apple tree Religious views Occult studies Scientific Revolution Copernican Revolution
Relations	Catherine Barton (niece) John Conduitt (nephew-in-law) Isaac Barrow (professor) William Clarke (mentor) Benjamin Pulleyn (tutor) John Keill (disciple) William Stukeley (friend) William Jones (friend) Abraham de Moivre (friend)
Depictions	Newton by Blake (monotype) Newton by Paolozzi (sculpture) Isaac Newton Gargoyle Astronomers Monument
Namesake	Newton (unit) Newton's cradle Isaac Newton Institute Isaac Newton Medal Isaac Newton Telescope Isaac Newton Group of Telescopes XMM-Newton Sir Isaac Newton Sixth Form Statal Institute of Higher Education Isaac Newton Newton International Fellowship
Categories	Isaac Newton

v т и Проблемы с упаковкой
Abstract packing	Bin Set
Circle packing	In a circle / equilateral triangle / isosceles right triangle / square Apollonian gasket Circle packing theorem Tammes problem (on sphere)
Sphere packing	Apollonian Finite In a sphere In a cube In a cylinder Close-packing Kissing number Sphere-packing (Hamming) bound
Other 2-D packing	Square packing
Other 3-D packing	Tetrahedron Ellipsoid
Puzzles	Conway Slothouber–Graatsma