Введение
Геометрическая концепция
В геометрии число поцелуев математического пространства определяется как максимальное количество неперекрывающихся единичных сфер, которые можно расположить в этом пространстве таким образом, чтобы каждая из них касалась общей единичной сферы. Для заданной упаковки сфер в заданном пространстве число поцелуев также может быть определено для каждой отдельной сферы как количество сфер, которых она касается. Для решётчатой упаковки число поцелуев одинаково для каждой сферы, но для произвольной упаковки сфер число поцелуев может варьироваться от сферы к сфере. Другими названиями для числа поцелуев являются число Ньютона (по имени автора задачи) и контактное число. В общем случае, задача о числе поцелуев заключается в поиске максимально возможного числа поцелуев для n-мерных сфер в (n+1)-мерном евклидовом пространстве. Обычные сферы соответствуют двумерным замкнутым поверхностям в трехмерном пространстве. Нахождение числа поцелуев, когда центры сфер ограничены линией (одномерный случай) или плоскостью (двумерный случай), является тривиальной задачей. Доказательство решения для трехмерного случая, несмотря на то, что его легко представить и смоделировать в физическом мире, оставалось недоступным для математиков до середины XX века.
In geometry, the kissing number of a mathematical space is defined as the greatest number of non overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing (arrangement of spheres) in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another. Other names for kissing number that have been used are Newton number (after the originator of the problem), and contact number. In general, the kissing number problem seeks the maximum possible kissing number for n dimensional spheres in (n + 1) dimensional Euclidean space. Ordinary spheres correspond to two dimensional closed surfaces in three dimensional space. Finding the kissing number when centers of spheres are confined to a line (the one dimensional case) or a plane (two dimensional case) is trivial. Proving a solution to the three dimensional case, despite being easy to conceptualise and model in the physical world, eluded mathematicians until the mid 20th century.
Три измерения
В трех измерениях число поцелуев равно 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 измерений найденное на данный момент расположение с наибольшим известным числом поцелуев является оптимальным решетчатым расположением, однако возможность существования нерешетчатого расположения с большим числом поцелуев не исключена.
Алгоритмы
Существуют несколько алгоритмов приближения для графов пересечений, где коэффициент приближения зависит от числа касаний. Например, существует полиномиальный алгоритм приближения с коэффициентом 10 для нахождения максимального непересекающегося подмножества множества повернутых единичных квадратов.
a polynomial time 10 approximation algorithm to find a maximum non intersecting subset of a set of rotated unit squares.
Математическое утверждение
Проблема числа поцелуев может быть сформулирована как существование решения набора неравенств. Пусть – множество N D-мерных векторов, задающих положения центров сфер. Условие, при котором этот набор сфер может располагаться вокруг центральной сферы, не перекрываясь, следующее: Таким образом, задача для каждой размерности может быть выражена в экзистенциальной теории вещественных чисел. Однако общие методы решения задач в такой форме требуют как минимум экспоненциального времени, поэтому эта проблема решена лишь для измерений до четырех включительно. Добавляя дополнительные переменные, её можно свести к одному уравнению четвёртой степени с N(N–1)/2 + DN переменными: следовательно, решение задачи в D = 5 измерениях и N = 40 + 1 векторах эквивалентно определению существования вещественных решений уравнения четвёртой степени с 1025 переменными. Для D = 24 измерений и N = 196560 + 1, уравнение четвёртой степени будет содержать 19 322 732 544 переменных. Альтернативная формулировка в терминах геометрии расстояний выражается через квадраты расстояний между m-й и n-й сферами: это условие необходимо дополнить требованием, чтобы определитель Кейли–Менгера был равен нулю для любого набора точек, образующих (D + 1)-симплекс в D измерениях, поскольку его объём должен быть равен нулю. Приравнивая к нулю, получаем систему одновременных полиномиальных уравнений, содержащую только y, которую необходимо решать, находя лишь вещественные корни. Оба метода, будучи полностью эквивалентными, имеют различные области применения. Например, во втором случае можно случайным образом изменять значения y на небольшие величины, чтобы попытаться минимизировать полином, выраженный через y.
Thus the problem for each dimension can be expressed in the existential theory of the reals. However, general methods of solving problems in this form take at least exponential time which is why this problem has only been solved up to four dimensions. By adding additional variables, this can be converted to a single quartic equation in N(N − 1)/2 + DN variables:
Therefore, to solve the case in D = 5 dimensions and N = 40 + 1 vectors would be equivalent to determining the existence of real solutions to a quartic polynomial in 1025 variables. For the D = 24 dimensions and N = 196560 + 1, the quartic would have 19,322,732,544 variables. An alternative statement in terms of distance geometry is given by the distances squared between the mth and nth sphere:
This must be supplemented with the condition that the Cayley–Menger determinant is zero for any set of points which forms a (D + 1) simplex in D dimensions, since that volume must be zero. Setting gives a set of simultaneous polynomial equations in just y which must be solved for real values only. The two methods, being entirely equivalent, have various different uses. For example, in the second case one can randomly alter the values of the y by small amounts to try to minimise the polynomial in terms of the y.