Геометрические задачи упаковок сфер и смежные проблемы

Мусин, Олег Рустумович

Геометрические задачи упаковок сфер и смежные проблемы тема автореферата и диссертации по математике, 01.01.04 ВАК РФ

Мусин, Олег Рустумович АВТОР

доктора физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.04 КОД ВАК РФ

Диссертация по математике на тему «Геометрические задачи упаковок сфер и смежные проблемы»

Автореферат диссертации на тему "Геометрические задачи упаковок сфер и смежные проблемы"

Математический институт им. В. А. Стеклова Российская Академия Наук

На правах рукописи УДК 514.17

Мусин Олег Рустумович

ГЕОМЕТРИЧЕСКИЕ ЗАДАЧИ УПАКОВОК СФЕР И СМЕЖНЫЕ ПРОБЛЕМЫ

Специальность 005540147

01.01.04 - геометрия и топология

2 8 НОЯ 2013

АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора физико-математических наук

Москва - 2013

005540147

Работа выполнена в Институте Проблем. Передачи Информации РАН.

Официальные оппоненты: доктор физико-математических наук, член-

корреспондент РАН. профессор Веснин Андрей Юрьевич доктор физико-математических наук Дужин Сергей Васильевич доктор физико-математических наук, профессор

Сабит.ов Идэ/сад Хакович Ведущая организация: Санкт-Петербургский государственный

университет

Защита состоится 27 декабря 2013г. в 13:00 на заседании диссертационного совета Д.002.022.03 при Математическом институте им. В. А. Стеклова Российской Академии Наук по адресу: 119991 Москва, ул. Губкина, д. 8

С диссертацией можно ознакомиться в библиотеке Математического института им. В. А. Стеклова РАН. Автореферат разослан <<2^>> _ 2013г.

Учёный секретарь диссертационного совета Д. 002.022.03

доктор физико-математических наук, профессор

Долбилин Н. П.

Общая характеристика работы

Актуальность темы

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

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

Очевидно, что к(2) = 6. В трехмерном пространстве, в задаче о контактных числах спрашивается: "Как много белых бильярдных шаров могут одновременно касаться черного бильярдного шара?"

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

Этот вопрос был предметом спора между И. Ньютоном и Д. Грегори в 1694 году. Ньютон считал, что к(3) = 12, в то время как Грегори думал, что ответ может быть равен 13. Эту задачу Ньютона - Грегори часто называют проблемой тринадцати шаров.

Проблема тринадцати шаров оказалось достаточно трудной и была решена только в 1953 году. К. Шютте и Б.Л. Ван дер Варден 1 доказали, что Ньютон был прав и к(3) = 12.

1 Schütte К. and v. d. Waerden B.L., Das Problem der dreizehn Kugeln, Math. Ann. v. 125 (1953), p. 325-334.

Если говорить коротко, то доказательство Шютте - Ван дер Вардена основано на переборе неприводимых контактных графов. Предположим, что центр центрального находится в начале координат 0. Обозначим через Ai,..., An точки (векторы) касания внешними шарами центрального шара. Тогда угол между любыми двумя векторами Ai и Aj не меньше 7г/3 и очевидно, что проблема контактных чисел эквивалентна нахождению максимального числа точек N на сфере в тг-мерном пространстве с угловыми расстояниями между точками не меньше 60°.

Заметим, что это ведет к важному обобщению: Множество точек на сфере в М™ называется сферическим ip—кодом, если минимальное угловое расстояние между точками этого множества не меньше чем <р.

Обозначим через А(п, ф) максимальную мощность сферического tp—кода в размерности п. Тогда

к(п) = А(п, 60°).

Предположим, что А\,.. ■, Ак точки на сфере. Будем считать эти точки вершинами контактного графа Г. Соединим две вершины графа Г ребром (кратчайшей дугой на сфере), если эти точки находятся на минимальном расстоянии между точками Ai, иными словами, соответствующие внешние шары касаются.

Таким образом, задача тринадцати шаров сводится к доказательству того, что на единичной сфере В2 не найдется контактного контактного графа Г с ребрами одинаковой длины, которая не меньше чем 60° в угловом измерении.

Совсем недавно мы с A.C. Тарасовым решили строгую проблему тринадцати шаров [13]. (Эту проблему еще называют проблемой Таммеса для 13 точек.) Если считать, что радиус центрального шара равен 1, а внешние 13 шаров имеют одинаковый радиус г, то надо найти такую конфигурацию

13 шаров, чтобы этот радиус был максимально возможным. Наше решение этой задачи основано на компьютерном переборе неприводимых контактных графов и было доказано, что максимальный радиус г « 0,9165, или, эквивалентно, минимальное расстояние между точками касания на сфере и 57,14°. (Эта работа не вошла в данную диссертацию, хотя и была мотирована работами автора по контактным числам.)

Рассмотрим контактные числа в размерности 4 и выше. Сначало покажем, что к(4) ^ 24. Заметим, что у единичного шара в К4 с центром в начале координат (0,0,0, 0) имеется ровно 24 единичных шара, касающихся его, с центрами в (±\/2, ±\/2,0,0) со всеми переменами знаков и перестановками координат. Выпуклая оболочка этих 24 точек образует знаменитый 24-гранник - один из шести правильных многогранников в размерности 4.

Отметим, что у двух замечательных решеток: Eg (решетка Коркина-Золо-тарева) и Л24 (решетка Лича) число минимальных векторов равно 240 и 196560, соответственно. Отсюда следует, что к(8) ^ 240 и к{24) ^ 196560.

Первые нетривиальные верхние оценки на контактные числа к(п) были получены Г.С.М. Кокстером в 1963 году2 и для п = 4,5,6,7, и 8 эти оценки были 26, 48, 85, 146, и 244, соответственно. Доказательства Кокстера были основаны на гипотезе о плотнейшей упаковке сферы, которая была доказана К. Бёрёцким в 1978 году3.

Значительный прогресс по проблеме контактных чисел произошел в конце 1970-х годов. В 1978 году Г.А. Кабатянский и В.И. Левенпттейн получили новые асимптотические оценки для сферических кодов и плотностей упаковок

2 Coxeter H.S.M., An upper bound for the number of equal nonoverlapping spheres that can touch another of the same size, Proc. of Symp. in Pure Math. AMS, v. 7 (1963), p. 53-71

3 Böröczky К., Packing of spheres in spaces of constant curvature, Acta Math. Acad. Sei. Hung. v. 32 (1978), p. 243-261

шаров4. В частности, они доказали, что

к(п) ^ 2a401n(1-o(1».

(Нижняя оценка 2а2075п(1+°(1)) была известна задолго до этого.)

В 1979 году В.И. Левенштейн0 и независимо от него А. Одлыжко и Н. Сло-эн 6 доказали, что к(8) = 240 и к(24) = 196560. В работе Одлыжко-Слоэна также улучшены верхние граница для к(п) при 3 < п ^ 24. В частности, для сравнения с границами Кокстера, при п = 4,5,6,7, и 8 новые границы были 25, 46, 82, 140, и 240. соответственно.

В последующие годы, вплоть до 2003 года, улучшения для к(п), п < 24, были не очень значительны. В.В. Арестов и А.Г. Бабенко доказали, что граница к(4) ^ 25 не может быть улучшена методом Дельсарта7. В 2003 году нами было опубликовано короткое сообщение с наброском доказательства равенства к(4) = 24 [1]. (Полное доказательство опубликовано в работе [6].)

В 2009 году Г. Д. Миттелманн и Ф. Валлентин8, используя полуопределенное программирование, улучшили верхние границы для к(п), где 4 < п < 24, п ф 8. Для сравнения с предыдущими результатами, при п = 5,6, и 7 новые границы 44, 78, и 134, соответственно. Однако, эти границы превосходят известные нижние границы в этих размерностях: 40, 72, и 126.

Все результаты о контактных числах конца 1970-х годов были получены с помощью метода Дельсарта. Метод Дельсарта позволяет получать верхние

4 Кабатянский Г. А. и Левенштейн В. И., О границах для упаковок на сфере и в пространстве. Проблемы передачи информации. 14(1). с. 3-25, 1978

5 Левенштейн В. И.. О границах для упаковок в п-мсрном евклидовом пространстве, Докл. АН СССР, т. 245 (1979). с. 1299-1303

6 Odlyzko A.M. and Sloane N.J.A. New bounds on the number of unit spheres that can touch a unit sphere in n dimensions, J. of Combinatorial Theory. A26 (1979), p. 210-214.

7 Арестов В. В., Бабенко А. Г. , О схеме Дельсарта оценки контактных чисел. Труды Мат. ин-та им. В.А. Стеклова РАН, т. 219 (1997), с. 44-73

8 Mittelmann Н. D. and Vallentin F., High accuracy semidefinit-e programming bounds for kissing numbers, Experimental Mathematics, v. 19 (2009), p. 174-178.

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

Пусть М. - метрическое пространство с функцией расстояния т{х,у). Функция д(т) (определенная на множестве всех расстояний М), называется положительно определенной на М, если для любого набора точек xi, Х2, ..., хдг и любых чисел щ, 112, ■ ■ ■, ujv выполнено:

д(т(хих^)щи^ ^ 0.

i.j—l

Иногда удобно рассматривать «непрерывный» вариант этого определения. То есть, потребовать, чтобы для любой непрерывной функции и{х) и меры ¡л на М

g(T(x,y))u(x)u(y)diixdfiy ^ 0.

Легко видеть, что если g\{t) и g2(t) положительно определенные функции, т0 Ci5i(t) + C2<?2(i) положительно определенная функция для любых ci, С2 ^ 0. (Из леммы Шура следует, что и произведение двух положительно определенных функций, тоже положительно определенная функция.)

Пусть нам удалось найти такую положительно определенную функцию g(t) на пространстве М, и число с > 0, что для функции f(t) = g(t) + с, выполнено следующее

ДО) = 1,

f(t) sC 0, при всех t G Т С R.

9 Delsarte P., Goethals J. М., and Seidel J. J. Spherical codes and designs, Geometriae Dedicate, v. 6(3) p. 363-388, 1977.

Рассмотрим набор точек X = {х,-, г = 1...., N] в М. таких, что расстояния между любыми двумя точками лежат в Т. Давайте оценим сумму

Sf(X)

i,j= 1

двумя способами. С одной стороны

Sf(X) = £ 9(r(xi. Xj)) + cN2 ^ cN\ ij=1

поскольку функция g(t) положительно определена.

С другой стороны, поскольку при i Ф j расстояние r(xt-, Xj) 6 Г, т.е. f(r(xi,xj)) ^ 0, получаем

sf(x)=х; дфь +Е ^ n-i^j i=1

Объединяя эти два неравенства, мы получаем, что

N ^ с~\

Это неравенство и называется границей Делъсарта.

Предположим, что Т = {f € R : t ^ d}. Тогда условие т(х,у) £ Т означает, что расстояния между точками хну не меньше d. Таким- образом, метод Дельсарта позволяет оценить возможное количество точек в М на расстоянии не менее d друг от друга.

И.Я. Шёнберг10 нашел все положительно определенные функции на сфере. Оказывается, что все п. о. ф. являются выпуклой комбинаций многочленов Гегенбауэра (от косинуса углов между точками).

10 Schoenberg I. J., Positive definite functions on spheres, Duke Mathematical Journal, v. 9(1), p. 96-108, 1942.

Напомним определение многочленов Гегенбауэра.

G^(x) = lt Gf(x) = x, = ...,

П(п), ч _ (2fc+n-4) W-(fe-l) Gll'2(x) Uk \X) — k+n-3

Имеет место следующая замечательная теорема: Теорема Шёнберга. Функции имеющие вид

ос

g{t) = ^ (cos t), Of ^ О,

г=0

являются положительно определенными функциями на сфере Sn_1.

Обратное тоже верно, любая положительно определенная функция на S"-1 представляется в таком виде.

Из теоремы Шёнберга легко вытекает граница Дельсарта для контактных чисел:

Теорема Дельсарта-Кабатянского-Левенштейна. Пусть,

/(х) = со + ciG?(i) + • • • + cmGnm(x),

где со > 0 и все ci ^ 0, при i ^ 1. ¿'ели /(х) ^ 0 при х G [—1,1/2], то

/(1)

&(п) ^

Со

Если применить эту теорему для п = 8 и

/(х) = ^Гх-^ х2 + ^ (х + 1),

то поскольку

'<*> - ш+ + W + S0'«++ W +

получим /с(8) ^ 240, а неравенство fc(8) ^ 240 влечет равенство к(8) = 240.

Аналогично доказывается равенство к(24) = 196560. Здесь

По всей видимости, с помощью метода Дельсарта можно решить проблему контактных только в размерностях п = 2, 8, 24. Десять лет назад, Д. В. Штром с помощью компьютера проверил этот метод для к(п) аж до размерности 161, и нигде не обнаружил таких замечательных равенств как при п = 2, 8, 24.

Рассмотрим теперь задачу, поставленную Л. Фейшем Тотом и X. Саксом в 1976 году:

Пусть Н - замкнутое полупространство в М™. Обозначим через S единичный шар в Н, касающейся опорной гиперплоскости задающей Н. Односторонним контактным чиааом В(п) будем называть наибольшее число не пересекающихся единичных шаров в Н, одновременно касающихся S. Найти явные значения В(п) для п — 2,3,4,...

Легко видеть, что В(2) = 4. Для п = 3 задача была решена Г. Фейшем Тотом в 1981 году11. Было показано, что В{3) = 9. Покажем, что В {А) ^ 18. Пусть

рг = (А, 0,0, А), Р2 = (-А,0,0,Л),

Р{з.4} = (0, ±А, О, А), р{5:6} = (0,0, ±А, Л),

Р{7.....ю> = (±А ±А, 0,0), Р{„,...,14} = (±Л, 0, ±А, 0),

рцъ.....is} = (0,±Д±Л,0),

где А = \/у/2. Заметим, что все 18 точек {pj лежат на верхней полусфере и минимальное угловое расстояние между ними равно 7г/3.

11 Fejes Toth G., Ten-neighbor packing of equal balls. Periodica Math. Hungar., v. 12 (1981), c. 125-127.

В 1991 г., для п = 4, Л. Сабо, используя границу Одлыжко-Слоэна: к(4) < 25 доказал, что В{4) ^ 20. В 2005 г. К. Бездек, используя наш результат к{ 4) = 24, показал что В (А) ^ 19 и выдвинул гипотезу, что В{ 4) = 18. Мы доказали эту гипотезу в 2006 году |4].

В работах [5,7] мы получили несколько новых верхних границ для В(п). Однако, все эти границы были улучшены с помощью полуопределенного программирования в работе К. Башок и Ф. Валлентина12. В этой же работе была доказана наша гипотеза, что В(8) = 183 из работы [4].

В диссертации мы также рассматриваем задачу о максимальных множествах с двумя расстояниями.

Множество S в Мп или Sn_1 (или любом другом метрическом пространстве) называется множеством с s расстояниями (по-английски s-distance set), если расстояние между его точками принимает не более чем s значений.

Для s = 2 С. Дж. Эйнхорн и И.Я. Шёнберг13 показали, что существует лишь конечное число множеств (с точностью до подобия) с двумя расстояниями в R™, состоящих из более чем п + 2 точек.

Отметим, что верхние оценки на мощность множеств с s расстояниями в Rn известны около 30-ти лет. В частности, Блокхаус доказал, что число точек у множества S с двумя расстояниями в Rn не превосходит (п + 1)(п + 2)/2. Как показал П. Лисонек14, эта оценка достигается в размерности 8.

Имеется пример множества с двумя расстояниями в Rn, состоящего из = п(п + 1)/2 точек. Мы будем обозначать это множество Мп. Рассмотрим правильный симплекс в R", у которого длины всех ребер равны 1. У

12 Bachoc С. and Vallentin F., Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps, European J. Combin., v. 30 (2009), p. 625-637.

13 Einhorn S. J. and Schoenberg I. J., On Euclidean sets having only two distances between points I, II. Indag. Math., v. 14 (1966), pp. 479-488, 489-504.

14 Lisonek P., New maximal two-distance sets, Journal of Combinatorial Theory, Series A, v. 77(2), p. 318-338, 1997.

этого симплекса всего п(п + 1)/2 ребер. Их середины будут образовывать множество с двумя расстояниями. Действительно, если два ребра имеют общую вершину, то расстояние между их серединами равно 1/2 (поскольку соединяющий их отрезок будет средней линией треугольника образованного вершинами этих ребер). Если не имеют, то 1/\/2, поскольку в этом случае вершины этих ребер являются вершинами правильного трехмерного тетраэдра, а между серединами противоположных ребер правильного тетраэдра именно такое расстояние.

Это множество можно описать также с помощью ортонормированного базиса еь ег,..., е„+1 пространства Кп+1. Рассмотрим точки вида

+ (1 < г <.7 < п + 1).

Расстояние между такими точками может быть равно либо у/2 либо 2, в зависимости от того имеют ли они общую единицу в координатной записи или нет. Сумма координат получившихся п(п+1)/2 точек будет равна 2 и поэтому они будут лежать в гиперплоскости задаваемой уравнением хг + .. .+хп+г = 2.

Заметим, что если а и Ь (а < Ь) - два расстояния множества М„, то Ь2/а2 — 2. Оказывается, что подобное свойство верно для всех достаточно больших множеств с двумя расстояниями.

Ларман, Роджерс и Зейдель15 доказали, что если множество с двумя расстояниями а и 6 (а < Ь) в М" состоит из более чем 2п + 3 точек, то

к ~ 1 , ™ о / , / 1 + ^/2«

— = ——, где к € N и 2 ^ к < ----

о1 к I

В работе Дельсарта, Гуталса и Зейделя77, которую мы упоминали в связи с методом Дельсарта, были получены оценки для случая, когда точки множества £ лежат на сфере в К™. (Мы будем называть такие множества

15 Larman D. G., Rogers C. A. , and Seidel J. J., On two-distance sets in Euclidean space. Bulletin of the London Mathematical Society, v. 9(3), p. 261-267, 1977.

сферическими множествами с двумя расстояниями.) В этом случае оценка будет п(п + 3)/2. Заметим, что эта оценка достигается для п = 2, б и 22.

Обозначим максимальную мощность сферического множества с двумя расстояниями через д(п). Тогда

для 6 < п < 22 и 23 < п < 40. Недавно этот результат был расширен для п = 23 и 40 ^ п ^ 93 (п ф 46, 78) в работе А. Варга и В.-Ш. Ю16.

Цель работы

1. Решить проблему контактных чисел для размерности 4.

2. Дать новое доказательство проблемы тринадцати шаров.

3. Решить проблему односторонних контактных чисел для размерности 4.

4. Получить новые оценки для сферических множеств с двумя и тремя расстояниями.

Научная новизна.

Основными результатами диссертации являются следующие:

1. Доказано, что k(4) = 24.

2. Получено новое доказательство равенства /с(3) = 12. Это доказательство аналогично предыдущему, хотя технически намного проще.

16 Barg A. and Yu W. Н., New bounds for spherical tuio-distance sets, Experimental Math., v. 22, no. 2, 2013, p. 187-194.

В работе |8] мы улучшили эту оценку и было показано, что

3. Для доказательства неравенства к(4) < 25 был разработан метод неприводимых множеств. Классификация этих множеств для числа точек т ^ 6 позволило оценить частичные суммы 5/(Х) и тем самым доказать неравенство.

4. Доказано, что В(4) = 18. Технически, это доказательство оказалось сложнее чем доказательство 1. В доказательстве используется комбинация метода Дельсарта, ОМД и элементов теории сферических кодов в сферических шапочках. (Более подробно эта теория рассмотрена в работе [5].)

5. Доказана следующая теорема:

Пусть 5 - это множество с двумя расстояниями а и ¡3, расположенное на единичной сфере в Жп, причем сумма этих (угловых) расстояний не превосходит ж, т.е. а + в ^ тт. Тогда количество точек в 5 не превосходит п(п + 1)/2.

6. Доказано, что

д(п) - мощность максимального сферического множества с двумя расстояниями в Мп, где 6<п<22и23<п< 40, равна п(п + 1)/2.

Доказательство основано на комбинации предыдущей теоремы, теоремы Лармана-Роджерса-Зейделя и метода Дельсарта.

7. Получены новые оценки на мощность сферических множеств с тремя расстояниями. В частности, доказано что мощность максимального сферического множества с тремя расстояниями в М8 равна 120, а в размерности 22, т. е. на сфере §21, его мощность равна 2025.

Основные методы исследования

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

Публикации.

Основное содержание диссертации опубликовано в 15 работах, список которых приведен в конце автореферата [1-15].

Структура и объем диссертации.

Диссертационная работа состоит из введения и трех глав.

Краткое содержание работы

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

Содержание главы 1

Первая глава диссертации посвящена решению проблемы контактных чисел в размерности 4. Здесь приведено подробное доказательство равенства к(4) = 24, а также дано новое решение проблемы тринадцати шаров.

Теорема А. /с(4) = 24.

Доказательство Теоремы А основано на обобщенном методе Дельсарта (ОМД). Первым шагом в этом методе является построение "подходящего"

многочлена f(t). Этот многочлен ищется в форме

k=1

В классическом методе Дельсарта на коэффициенты q накладывается условие /(i) ^ 0 на отрезке [—1,1/2]. Как мы показали выше, из этого условия вытекает неравенство Sj(X) ^ Аг/(1).

В ОМД мы ослабляем это условие и требуем, чтобы при заданном параметре to функция f(t) ^ 0 на отрезке [iо.1/2] и чтобы функция / была монотонно убывающей на интервале [— l.io]. Параметр to и коэффициенты Cj ищутся такими, чтобы, по возможности, минимизировать сумму S/(X).

Рассмотрим на единичной сфере Sn_1 набор точек У = {у0, yi,..., ут}. Обозначим, через hm максимум суммы H(Y) := /(l)+/(yo-yi)+. • -+/(У0'Ут) по всем таким наборам Y, что

yi ■ yj ^ 1/2 для всех i ф j, у0 ■ Vi ^ ¿о Для г = 1,..., т.

При т = 0 зададим ho := /(1).

Условия на Y задают определенные условия на т. Обозначим через /и, максимально возможное то. Тогда имеет место следующая верхняя граница:

Кп) ^ —meai{h0,hi,...,hp}. (1)

со

Величина ц может быть оценена через сферические коды меньшей размерности:

ц<л(п- 1, arccos • (2)

Рассмотрим многочлен, являющийся "подходящим" для ОМД при п = 4:

_ 1344 9 2688 7 1764 5 2048 4 1229 3 516 2 217 2 W):~ 25 25 + 25 + 125 125 125 500 125'

Разложив /4 по многочленам Гегенбауэра 11к = (в этой размерности это многочлены Чебьппева второго рода) получим

Стало быть со = 1, а все остальные с; ^ 0. Здесь ¿о = -0,6058. Из (2) следует

1/2 — ¿2

/х ^ А(3, у>о), где <ро := агссоэ-^ « 77,8707°.

1 — ¿0

К. Шютте и Б.Л. Ван дер Варден17 доказали, что А(3, <р) = 7 только если < 77,8696°. Поскольку > 77,8696°, то ц. = 6. Таким образом, доказательство Теоремы А сведено к доказательству того, что Нт < 25 при т — 0,1,2,3,4,5,6. Несложно видеть, что

Н0 = /(1) = 18, 774, Л-1 = /(1) + /(-1) = 24,48.

Для случая ш = 2 можно показать, что максимум Н{¥) достигается когда точки у\ и у2 располагаются на расстоянии 150° от точки уо. Тогда

Н2 = /(1) + 2/(соэ 150°) и 24,8644.

Наиболее сложная часть доказательства - это вычисление 1гт при т = 3,4, 5. Если точки уо, у\,..., ут на §3 являются максимальной конфигурацией для кт, то это множество пеприводимо.■ Это означает, что точки множества Рт :— {у,-, г = 1,..., т}, которые лежат от уо на расстоянии не ближе чем агссоэ ^ нельзя отодвинуть от уо, чтобы какие-то расстояния между ними не стали бы меньше 60°.

Можно показать, что неприводимое множество Р3 образует треугольник со сторонами равными 60°, Р4 образует правильный тетраэдр, а Р5 - бипира-миду у которой все ребра длиной 60°, кроме возможно одного, являющегося

17 Schütte K. and v. d. Waerden B.L.. Auf welcher Kugel haben 5,6.7,8 oder 9 Punkte mit Mindeslabstand 1 Platz?, Math. Ann. v. 123 (1951), p. 96-124.

стороной треугольника, разбивающего Р5 на две пирамиды. (Удивительно, но это утверждение не является тривиальным, по-крайней мере мы не смогли найти простые рассуждения, и полное его доказательство занимает около 9 страниц.)

Следующим шагом является вычисление верхних границ для hm. Для этого Рт разбивается на клетки (параллелепипеды), на которых при фиксированных {yi, г — 1,..., m} функция Р(уо) :— H (Y) достигает максимума в вершинах. При достаточно мелком разбиение можно показать, что

/г3 < 24,8345, Д4 < 24,818, h5 < 24,685

Для случая m = 6 можно рассмотреть точку уг-, ближайшую к уо и оставшиеся пять точек. Поскольку у нас уже оценка для пяти точек, а расстояние до ближайшей j/j можно оценить, то это можно использовать для оценки hg. Вычисления показывают, что

/г6 < 24,7762 < Л2.

Таким образом, max {/iq, h,?, /13, /14, h5, h б} = /12 < 25.

Аналогично Теореме А доказывается Теорема В. /с(3) = 12.

В этом случае подходящий многочлен

, . ч 2431 q 1287 7 18333 , 343 4 83 3 213j2 t 1

ut) =-19 --1' 4--15 + -—r - —i3--12 +---,

J3y J 80 20 400 40 10 100 10 200'

t0 = —0, 5907, ¡1 = 4, hmax = h\ = 12,88. Разложение /3 по многочленам (з)

Лежандра Рк = Gk имеет вид

/з = Р0 + 1,6Р1 + 3,48Р2 + 1,65Р3 + 1,96Р4 + 0,1Р5 + 0, 32РЭ, а стало быть со = 1, сг- > 0. В итоге мы получаем, что

к{3) = 12,88 < 13. 18

Содержание главы 2

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

Теорема С. В{4) = 18.

В доказательстве используется комбинация метода Дельсарта, ОМД и элементов теории сферических кодов в сферических тапочках.

Обозначим через S+ замкнутую верхнюю полусферу единичной сферы §n_1, т.е. хп > 0, и S+ является сферической тапочкой радиуса 90° с центром в «северном полюсе» N = (0,..., 0,1).

Пусть Р - конечное множество в S+. Введем обозначения:

Ра := {р € Р : 90° ^ dist(p, N) > 60°}, а{Р) := \Ра\,

Рь = {реР: dist(p, N) < 60°}, b{P) := \Pb\.

Тогда

P=Pa\JPb, \P\=a(P) + b(P).

Лемма Cl. Пусть P С S+ С §n_1 является сферическим 7г/3—кодом. Тогда

(i) а(Р) + 2Ъ(Р) ^ fc(n);

(ii) а(Р) ^ А(п - l,arccos(l/v/3)).

Методом Дельсарта можно доказать, что А{3, arceos (1/л/З)) ^ 15. Следовательно для п = 4 из Леммы С1 следует

а + 26 ^ к(4) = 24, а ^ 15, а + b = В{4) ^ 18.

Из этих неравенств получаются только следующие возможности для |Р|, а(Р)

и Ь(Р):

|Р| = 19, (а, Ь) = (15,4); (14,5) 19

|Р| = 18, (a, b) = (15,3); (14,4); (13, 5); (12, 6) Для того, чтобы доказать Теорему С надо доказать, что Лемма С2. (a,b) Ф (15,4).

Лемма СЗ. (а, Ъ) ф (14,5).

Доказательства этих лемм оказалось довольно сложным технически. Для этого пришлось обобщить границу Дельсарта для кодов в сферических шапочках. В доказательстве Леммы СЗ также использовались вычислительные приемы из ОМД.

В заключительной части главы 2 рассматриваются некоторые обобщения Леммы С1 для кодов в сферических тапочках. Введем следующие обозначения:

А(п, в, ф) - максимальная мощность сферического в—кода в сферической шапочке радиуса ф\

В(п,в) := А(п,д,ж/2) - максимальная мощность сферического в—кода в полусфере 5+;

ш(в,а,/3) - функция, определяемая уравнением

cos в — cos a cos j3

cos и>{в,а,0) =-:-—-.

sin a sm р

Теорема D.

(г) А(п,9,ф) ^ B{n,u(e,ib)), где в ^ 2-ф ^ тг;

„ч А(п-1,д) + А(п,в) - cosd

(и) В(п,в)^-±-'-j--cosa-

cos {9/2)'

Содержание главы 3

Третья глава диссертации посвящена сферическим множествам с двумя и тремя расстояниями.

Напомним, что для сферических множеств 5 в размерности п верна верхняя границы, полученная в работе Дельсарта-Гуталса-Зейделя??:

151 <

Эта оценка, как впрочем и другие оценки для множеств с 5 расстояниями, получены с помощью так называемого полиномиального метода. Для этого по множеству £ строится система линейно-независимых многочленов и оценка получается из-за того, что число этих многочленов ограничено размерностью соответствующего пространства многочленов. Мы применили полиномиальный метод для сферических множеств с двумя расстояниями, сумма которых не превосходит тг.

Теорема Е. Пусть 5 - это множество с двумя расстояниями а и /3, расположенное на единичной сфере в К", причем сумма этих (угловых) расстояний не превосходит тт, т.е. а + 0 ^ тг. Тогда количество точек в 5 не превосходит п(п + 1)/2.

Напомним, что нижняя граница для д(п) - мощности максимального множества с двумя расстояниями, тоже равна п{п+ 1)/2. Поэтому, если д(п) > ?г(п + 1)/2, то у максимального множества в этой размерности а + (5 > тг.

Пусть а := соэа и Ь := со яр. Тогда условие а + ¡3 ^ тг эквивалентно условию а + Ь ^ 0. Для того, чтобы оценить д{п) можно применить метод Дельсарта для /, определенной на множестве Т = {а, 6} с а + Ь < 0. В главе 2 явно выписаны 5 многочленов Р.г = 1,2, 3,4, 5, которые используются в качестве / для границы Дельсарта. (Степени этих многочленов не превосходят

4.)

Из теоремы Лармана-Роджерса-Зейделя77 следует, что

Ь(а) = (ка — 1)/(к — 1), к = 2,...,тк:= [(1 + ^2п)/2\.

Для фиксированного к мы получаем однопараметрическое семейство пар точек Т = {а, Ь(а)} с

Давайте зафиксируем размерность п. Рассмотрим все к = 2,..., Следующий шаг: для каждого из 5 случаев / = Д находим границу Дельсарта на Т = {а, Ь(а)}. Для каждого а 6 Iк, взяв минимум из этих пяти границ, получим оценку сверху С (а). Если мы возьмем максимум С на то получим верхнюю оценку для 5 с а 4- Ь < 0. Последний шаг: если эта оценка для всех к не больше чем п(п + 1)/2, то д(п) = п(п + 1)/2. Вычисления по этой схеме доказывают следующую теорему:

Теорема Г. Если 6 < п < 22 или 23 < тг < 40, то

Мы уже отмечали, что недавно этот результат был расширен для п = 23 и 40 ^ п ^ 93 (п ф 46,78).

Заметим, что 6, 22, 46, 78 являются числами вида (2т + I)2 — 3, где тп = 1,2,3,4. Это приводит к следующей гипотезе:

Мощность максимального сферического множества с двумя расстояниями в Мп, где п > 6 ипф Am2 + 4m — 2, m е N, равна п(п + 1)/2.

В совместной работе [10] мы с A.M. Баргом применили эту схему для двоичных и равновесных кодов с двумя расстояниями. Также были получены новые границы для множеств с s- расстояниями.

п{п+ 1) 9(п) = -—

Для п = 23

д{23) = 276 или 277.

В последней части главы 3 разбираются результаты о сферических множествах с тремя расстояниями, полученных совместно с X. Нозаки. Здесь тоже применима схема доказательства Теоремы F.

В этой схеме важную роль играет теорема Лармана-Роджерса-Зейделя. Эта теорема была обобщена X. Нозаки для множеств es- расстояниями18. Используя это обобщение, в главе 3 доказывается следующая

Теорема G. Обозначим через Т(п) максимальную мощность сферического множества с тремя расстояниями в п—мерном пространстве. Тогда

1. Т(8) = 120 и Т(22) = 2025.

2. Т{4) ^ 27, Г(5) ^ 39 и Т{7) ^ 91.

3. Т(п) ^ п(п + 1)(п + 2)/6 для п = 6 и 9 < n ^ 19.

4. Т(п) s$ (тг + 3)(п2 + 2)/6 для 20 ^ п ^ 30.

5. Т(п) ^ (тг2 - 1)(п + 6)/6 для 31 ^ п < 50.

Теоретическая и практическая ценность

Диссертация носит теоретический характер. Полученные в диссертации результаты представляют интерес для дискретной и вычислительной геометрии, теории упаковок шаров, комбинаторике, и теории кодов. Результаты диссертации могут быть полезны для специалистов из Математического института им. В. А. Стеклова РАН, Института Проблем Передачи Информации им. А. А. Харкевича РАН, Московского государственного университета им. М.В. Ломоносова, Института теоретической физики им. Л. Д. Ландау

18 Nozaki Н., A generalization of Larman-Rogers-Seidel's theorem, Discrete Math. v. 311 (2011), p. 792-799.

РАН, Санкт-Петербургского государственного университета, Новосибирского государственного университета, Ярославского государственного университета им. П. Г. Демидова, Независимого московского университета.

Апробация результатов

Результаты диссертации многократно докладывались на различных международных конференциях (более 30) и на семинарах различных университетов и научных институтов России, США, Японии, Германии, Франции, Канады и др. (более 100 докладов).

Приведем здесь краткий перечень международных конференций за последние 5 лет в которых принимал участие автор:

- European Congress of Mathematics, Amsterdam, 14-18 July, 2008 (приглашенный доклад);

- International conference «Linear and semidefinite programming bounds» (Bonn, HausdorfT institute, February 25-29, 2008);

- International conference on Discrete Geometry and Algebraic Combinatorics, South Padre Island, Texas, USA (2008, 2009, 2010, 2012, 2013);

- International conference «Combinatorial Geometry», 14-19 июня 2009 г. Будапешт, Венгрия;

- «Regional AMS meeting», 30 октября-1 ноября 2009, Бока Ратон, США;

- «Canadian Math. Soc. meeting», December 4-6, 2009, University of Windsor;

- International conference «Topology, Geometry, and Dynamics: Rokhlin Memorial (11-16 января 2010 г., г. Санкт-Петербург);

- X Международный семинар «Дискретная математика и её приложения» (Москва, 1-6 февраля 2010 г.).

- «International Conference on Topology and its Applications», г. Нафпактос, Греция, 26-30 июня 2010 года.

- Международная конференция «Геометрия и топология, алгебра и теория чисел, приложения», посвященная 120-летию со дня рождения Б. Н. Делоне, (Москва, 16-20 августа 2010);

- Международная конференция «Метрическая геометрия поверхностей и многогранников», посвященная 100-летию со дня рождения Н. В. Ефимова, (Москва, 18-21 августа 2010);

- Международная конференция «Геометрия и интегрируемые системы» (к 60-летию И. М. Кричевера), г. Москва, 27-30 декабря 2010 г.;

- International conference «Dubrovnik VII - Geometrie Topology», June 26-July 3, 2011

- Международная математическая конференция «50 лет ИППИ», 25-29 июля 2011 г.;

- International conference «Discrete Geometry and Optimization», Toronto, Fields Inst., September 19-23, 2011;

- International conference «Sphere Packings», Toronto, Fields Inst., November 14-18, 2011;

- Международная топологическая конференция «Александровские чтения» (21-25 мая 2012 г., г. Москва)

- Международный Семинар «Вычислительная и Дискретная Геометрия и Топология», 4-12 марта 2012 г., 1ST (г. Вена, Австрия);

- «XIII Международный Семинар по Алгебраической и Комбинаторной Теории Кодов (АССТ2012)», Поморье, Болгария, 15-21 июня, 2012 г.;

- Международная конференция «Оптимальные и почти оптимальные конфигурации на решетках и многообразиях», Обервольфах, Германия, 19-24 августа 2012 г.;

- Международный Семинар «Сферические дизайны и близкие вопросы», Шанхай, КНР, 18-23 ноября 2012 г.;

- «14th International Conference Approximation Theory», San Antonio, Texas,

April 7-10, 2013;

- Международная конференция «Алгебраическая топология и абелевы функции», посвященная 70-летию В. М. Бухштабера (18-22 июня 2013 г., МИАН, г. Москва);

- Международная конференция «Дизайны, Коды, Графы и Смежные Области», Университет Киото, Япония, 1-3 июля 2013 г.

Публикации автора по теме диссертации

[1] Мусин О. Р. Проблем,а двадцати пяти сфер, УМЫ, т. 58 (2003), № 4, с. 153-154.

[2] Musin O.R., An extension of Delsarte's method. The kissing problem in three and four dimensions, The Proceedings of СОЕ Workshop on Sphere Packings, Kyushi University Press, p. 1-25, 2005.

[3] Musin O.R., The kissing problem in three dimensions. Discrete Comput. Geom., v. 35 (2006), p. 375-384.

[4] Musin O.R., The one-sided kissing number in four dimensions, Periodica Math. Hungar., v. 53 (2006), p. 209-225.

[5] Barg A., Musin O.R., Codes in spherical caps, Advances in Math, of Communicatio v. 1 (2007), p. 131-149.

[6] Musin O.R., The kissing number in four dimensions, Annals of Math., v. 168

(2008), no. 1, p. 1-32

[7] Musin O.R., Bounds for codes by semidefinite programming, Тр. МИАН, т. 263 (2008), с. 143-158.

[8] Musin O.R., Spherical two-distance sets, J. Comb. Theory, Ser. A, v. 116

(2009), p. 988-995.

[9] Musin O.R., Positive definite functions in distance geometry, European Congress of Mathematics, Amsterdam, 14-18 July, 2008, p. 115-134, EMS Pub!., 2010.

[10] Barg A., Musin. O.R., Bounds on sets with few distances, J. of Comb. Theory, Ser. A, v. 118 (2011), p. 1465-1474.

[11] Musin O.R., Nozaki H, Bounds on three- and higher-distance sets, European Journal of Combinatorics, v. 32 (2011) p. 1182-1190

[12] Boyvalenkov P., Dodunekov S., Musin O.R., A survey on the kissing numbers, Serdica Mathematical Journal, v. 38 (2012), p. 507-522.

[13] Musin O.R., Tarasov A.S., The Strong Thirteen Spheres Problem, Discrete Comput. Geom., v. 48 (2012), p. 128-141

[14] Акопян А.В., Кабатянский Г.А., Мусин О.P., Контактные числа, коды и сферические многочлены, Математическое просвещение. Третья Серия, Вып. 16 (2012), с. 57-74.

[15] Акопян А.В., Мусин О.Р., О множествах с двумя расстояниями, Математическое просвещение. Третья Серия, Вып. 17 (2013), с. 136-151.

Подписано в печать 19.09.2013 тираж 100 экз.

Отпечатано в Математическом институте им. В.А. Стеклова РАН Москва, 119991, ул. Губкина, 8

Текст научной работы диссертации и автореферата по математике, доктора физико-математических наук, Мусин, Олег Рустумович, Москва

Институт Проблем Передачи Информации РАН

На правах рукописи

05201450196

Мусин Олег Рустумович

ГЕОМЕТРИЧЕСКИЕ ЗАДАЧИ УПАКОВОК СФЕР И СМЕЖНЫЕ ПРОБЛЕМЫ

01.01.04 — Геометрия и Топология

Диссертация на соискание ученой степени доктора физико-математических наук

Москва - 2013

ОГЛАВЛЕНИЕ

Стр.

Используемые обозначения 5

Введение 6

0.1. Контактные числа..........................................................6

0.2. Метод Дельсарта для контактных чисел................................9

0.3. Односторонние контактные числа....................12

0.4. Множества с двумя расстояниями....................13

0.5. Содержание работы............................15

ГЛАВА 1. Проблема контактных чисел в размерности 4 23

1.1. Основные теоремы............................23

1.2. Метод Дельсарта для сферических кодов................24

1.2.1. Теорема Шёнберга...........................25

1.2.2. Многочлены Гегенбауэра........................25

1.2.3. Неравенство Дельсарта.........................26

1.2.4. Доказательство Леммы А1.......................27

1.2.5. Граница Дельсарта...........................27

1.3. Обобщение метода Дельсарта......................28

1.3.1. Обобщенная граница Дельсарта....................28

1.3.2. Класс функций .........................30

1.3.3. Выпуклость...............................30

1.3.4. Границы для /и,.............................33

1.3.5. Оптимизационная проблема......................35

1.4. Алгоритм вычисления подходящих многочленов............36

1.5. Оптимальные и неприводимые множества...............37

1.5.1. Условие монотонности и оптимальные множества..........37

1.5.2. Неприводимые множества.......................39

1.5.3. Неприводимые множества на §2....................41

1.5.4. Вращения и неприводимые множества в размерности п......42

1.5.5. Неприводимые множества на сфере §3................45

1.5.6. Оптимизационная задача........................49

1.6. Вычисление Нт..............................50

1.6.1. Случай т = 2..............................51

1.6.2. Функция Ок...............................51

1.6.3. Экстремальные точки функции на В...............52

1.6.4. Верхние границы для Нт.......................55

1.6.5. Верхние границы для Нт........................57

1.7. Доказательство Леммы А2........................59

1.8. Проблема тринадцати шаров.......................60

ГЛАВА 2. Проблема односторонних контактных чисел в размерности 4 и

коды в сферических шапочках. 65

2.1. Одностороннее контактное число в размерности 3...........65

2.2. Оптимальные расположения для В(п).................66

2.3. Обобщение метода Дельсарта для кодов на полусфере........69

2.4. В(4)=18..................................75

2.5. О соотношениях между к(п) и В(п)..................82

2.6. Коды в сферических шапочках.....................83

ГЛАВА 3. Сферические множества с двумя расстояниями. 87

3.1. Множества с двумя расстояниями....................87

3.2. Максимальные множества с двумя расстояниями для п ^ 3.....89

3.3. Максимальные множества с двумя расстояниями в пространствах размерности 4, 5, 6, 7, и 8........................90

3.4. Граница для сферических множеств с двумя расстояниями.....93

3.5. Метод Дельсарта для множеств с двумя расстояниями........95

3.6. Границы Я{ъ\а)..............................97

3.7. Максимальные сферические множества с двумя расстояниями. . . 99

3.8. Максимальные сферические множества с тремя расстояниями. . . . 101

Список использованных источников

103

ИСПОЛЬЗУЕМЫЕ ОБОЗНАЧЕНИЯ

1. Mn — n-мерное евклидово пространство.

2. Sd — ¿-мерная единичная сфера.

3. к{п) — контактное число в размерности п.

4. А(п, ф) — максимальная мощность сферического </?—кода на Sn_1.

5. dist(х, у) — угловое расстояние между точками хиуна сфере.

6. G^ — многочлен Гегенбауэра степени к в размерности п.

7. dim Л4 — размерность пространства Л4.

8. В(п) — одностороннее контактное число в размерности п.

9. А(п, <р, ip) — максимальная мощность сферического ip—кода в сферической шапочке радиуса ф на Sn_1.

10. В(п, ср) := А(п, <р, 7г/2) - максимальная мощность сферического (р—кода в полусфере.

11. д(п) — мощность максимального сферического множества с двумя расстояниями в размерности п.

12. Т(п) — максимальная мощность сферического множества с тремя расстояниями в размерности п.

ВВЕДЕНИЕ

0.1. Контактные числа.

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

Этот вопрос был предметом спора между И. Ньютоном и Д. Грегори в 1694 году. Ньютон считал, что к{3) = 12, в то время как Грегори думал, что ответ может быть равен 13. Эту задачу Ньютона - Грегори часто называют проблемой тринадцати шаров.

Проблема тринадцати шаров оказалось достаточно трудной и была решена только в 1953 году. К. Шютте и Б.Л. Ван дер Варден [50] доказали, что Ньютон был прав и к(3) = 12. (О других доказательствах и истории этой задачи см. [1], [15], [17], [27], [28], [29], [30], [34], [36], [43], [46], [51], [58], [62].)

Если говорить коротко, то доказательство Шютте - Ван дер Вардена основано на переборе неприводимых контактных графов. Предположим, что центр центрального шара находится в начале координат 0. Обозначим через точки (векторы) касания внешними шарами центрального шара. Тогда угол между любыми двумя векторами Ai и Aj не меньше 7г/3 и очевидно, что проблема контактных чисел эквивалентна нахождению максимального числа точек N на сфере в n-мерном пространстве с угловыми расстояниями между точками не меньше 60°.

Заметим, что это ведет к важному обобщению: Множество точек на сфере в Мп называется сферическим ip—кодом, если минимальное угловое расстояние между точками этого множества не меньше чем ср.

Обозначим через А(п, ip) максимальную мощность сферического <р>—кода в размерности п. Тогда

к(п) = Л(п,60°).

Предположим, что ..., An точки на сфере. Будем считать эти точки вершинами контактного графа Г. Соединим две вершины графа Г ребром (кратчайшей дугой на сфере), если эти точки находятся на минимальном расстоянии между точками А*, иными словами, соответствующие внешние шары касаются.

Таким образом, задача тринадцати шаров сводится к доказательству того, что на единичной сфере §2 не найдется контактного графа Г с ребрами одинаковой длины, которая не меньше чем 60° в угловом измерении.

Совсем недавно мы с A.C. Тарасовым решили строгую проблему тринадцати шаров [43]. (Эту проблему еще называют проблемой Таммеса для 13 точек.) Если считать, что радиус центрального шара равен 1, а внешние 13 шаров имеют одинаковый радиус г, то надо найти такую конфигурацию 13 шаров, чтобы этот радиус был максимально возможным. Наше решение

этой задачи основано на компьютерном переборе неприводимых контактных графов и было доказано, что максимальный радиус г « О,9165, или, эквивалентно, минимальное расстояние между точками касания на сфере ~ 57,14°. (Эта работа не вошла в данную диссертацию, хотя и была мотирована работами автора по контактным числам.)

Рассмотрим контактные числа в размерности 4 и выше. Сначала покажем, что к(4) ^ 24. Заметим, что у единичного шара в R4 с центром в начале координат (0,0,0,0) имеется ровно 24 единичных шара, касающихся его, с центрами в (±\/2, ±-\/2, 0,0) со всеми переменами знаков и перестановками координат. Выпуклая оболочка этих 24 точек образует знаменитый 24-гранник - один из шести правильных многогранников в размерности 4.

Отметим, что у двух замечательных решеток: (решетка Коркина-Золотарева) и Л24 (решетка Лича) число минимальных векторов равно 240 и 196560, соответственно. Отсюда следует, что /с(8) ^ 240 и к(24) ^ 196560.

Первые нетривиальные верхние оценки на контактные числа к(п) были получены Г.С.М. Кокстером в 1963 году [18] и для п — 4,5,6, 7, и 8 эти оценки были 26, 48, 85, 146, и 244, соответственно. Доказательства Кокстера были основаны на гипотезе о плотнейшей упаковке сферы, которая была доказана К. Бёрёцким в 1978 году [14]

Значительный прогресс по проблеме контактных чисел произошел в конце 1970-х годов. В 1978 году Г.А. Кабатянский и В.И. Левенштейн получили новые асимптотические оценки для сферических кодов и плотностей упаковок шаров [57]. В частности, они доказали, что

(Нижняя оценка 2а2075п(1+о(1)) была известна задолго до этого.)

В 1979 году В.И. Левенштейн [59] и независимо от него А. Одлыжко и Н. Слоэн [45] доказали, что к{8) = 240 и к{24) = 196560. В работе Одлыжко-Слоэна также улучшены верхние граница для к(п) при 3 < п ^ 24. В част-

ности, для сравнения с границами Кокстера, при п = 4,5,6,7, и 8 новые границы были 25, 46, 82, 140, и 240, соответственно.

В последующие годы, вплоть до 2003 года, улучшения для к(п), п < 24, были не очень значительны. В.В. Арестов и А.Г. Бабенко доказали, что граница к(4) ^ 25 не может быть улучшена методом Дельсарта [56]. В 2003 году нами было опубликовано короткое сообщение с наброском доказательства равенства А;(4) = 24 [60]. (Полное доказательство опубликовано в работе [38].)

В 2009 году Г. Д. Миттелманн и Ф. Валлентин [35], используя полуопределенное программирование, улучшили верхние границы для к(п), где 4 < п < 24, п ^ 8. Для сравнения с предыдущими результатами, при п = 5,6, и 7 новые границы 44, 78, и 134, соответственно. Однако, эти границы превосходят известные нижние границы в этих размерностях: 40, 72, и 126.

0.2. Метод Дельсарта для контактных чисел.

Все результаты о контактных числах конца 1970-х годов были получены с помощью метода Дельсарта. Метод Дельсарта позволяет получать верхние оценки для сферических кодов и многих других дискретных задач. В частности, сам метод был придуман Дельсартом для получения верхних оценок на мощность кодов, исправляющих ошибки. Для случая сферы, этот метод был подробно рассмотрен в работе Дельсарта, Гуталса, и Зейделя [23] и в уже упомянутой выше статье Кабатянского и Левенштейна [57].

Пусть Л4 - метрическое пространство с функцией расстояния т(х,у). Функция д(т) (определенная на множестве всех расстояний Л4), называется положительно определенной на Л4, если для любого набора точек х\, Х2, ..., хдг и любых чисел щ, ..., им выполнено:

Т^ д{т{х^х^))щщ ^ 0.

г,7=1

Иногда удобно рассматривать «непрерывный» вариант этого определе-

ния. То есть, потребовать, чтобы для любой непрерывной функции и{х) и меры ц на Л4

J J g(T(x,y))u(x)u(y)dfj,xdfiy ^ 0.

Легко видеть, что если g\{t) и g2(t) положительно определенные функции, то Ci^i(i)+C2p2(i) положительно определенная функция для любых С\, Ci ^ 0. (Из леммы Шура следует, что и произведение двух положительно определенных функций, тоже положительно определенная функция.)

Пусть нам удалось найти такую положительно определенную функцию g(t) на пространстве J\4, и число с > 0, что для функции fit) = g(t) + с, выполнено следующее

/(0) = 1,

f(t) ^ 0, при всех t е Т С R.

Рассмотрим набор точек X = {xi, i = 1,..., N} в Л4 таких, что расстояния между любыми двумя точками лежат в Т. Давайте оценим сумму

Sf(X) := ^/(г(хг,^))

м=1

двумя способами. С одной стороны

Sf(X) = Е 9(T(xi,Xj)) + cN2 ^ cN2, i,j=1

поскольку функция g(t) положительно определена.

С другой стороны, поскольку при i у£ j расстояние r(xi,xj) £ Т, т.е. f(r(xi,xj)) ^ 0, получаем

Sf(X) = £ ¡(т(хг, Xj)) + £ /(0) ^ N.

гф] ¿=1

Объединяя эти два неравенства, мы получаем, что

N < с"1.

Это неравенство и называется границей Дельсарта.

Предположим, что Т = {£ £ К : £ ^ д}. Тогда условие т(х, у) еТ означает, что расстояния между точками х и у не меньше (1. Таким образом, метод Дельсарта позволяет оценить возможное количество точек в на расстоянии не менее сI друг от друга.

И.Я. Шёнберг [48] нашел все положительно определенные функции на сфере. Оказывается, что все п. о. ф. являются выпуклой комбинаций многочленов Гегенбауэра (от косинуса углов между точками).

Напомним определение многочленов Гегенбауэра.

г{п)( Ч _ (2/С+П-4) Е С^{х)-{к-1) С^2(х) ик Vх) ~ к+п—3

Имеет место следующая замечательная теорема: Теорема Шёнберга. Функции имеющие вид

ОО

;тг— 1

g(t) = ^2aiG(T\cost), О,

г=0

являются положительно определенными функциями на сфере §г

Обратное тоже верно, любая положительно определенная функция на Sn_1 представляется в таком виде.

Из теоремы Шёнберга легко вытекает граница Дельсарта для контактных чисел:

Теорема Дельсарта-Кабатянского-Левенштейна. Пусть,

f{x) = Со + ciG?(®) + ■ ■ • + cmGnm{x), где со > 0 и все С{ ^ 0, при г ^ 1. Если f(x) ^ 0 при х Е [—1,1/2], то

ни) < т.

Со

Если применить эту теорему для п — 8 и то поскольку

получим к(8) ^ 240, а неравенство к(8) ^ 240 влечет равенство к(8) = 240. Аналогично доказывается равенство Тс(24) = 196560. Здесь

><*> = !!(*"Й М)'*2(*+I)2 (*+{Г +^

0.3. Односторонние контактные числа.

Рассмотрим теперь задачу, поставленную Л. Фейшем Тотом и X. Саксом в 1976 году:

Пусть Н - замкнутое полупространство в Мп. Обозначим через 5 единичный шар в Н, касающейся опорной гиперплоскости задающей Н. Односторонним контактным числом В(п) будем называть наибольшее число не пересекающихся единичных шаров в Н, одновременно касающихся 5. Найти явные значения В(п) для п = 2,3,4,...

Легко видеть, что В{2) = 4. Для п = 3 задача была решена Г. Фейшем Тотом в 1981 году [25]. Было показано, что В(3) = 9. Покажем, что В{4) ^ 18. Пусть

Р1 = (А 0,0, А), р2 = (—А, 0, 0, А),

р{з;4} = (О, ±А, О, А), p{5ß} = (О, О, ±А, А),

Р{7,...,ю> = (±А ±А 0,0), р{11.....i4> = (±Д 0, ±Д 0),

Р{15,...,18} = (0,±Д=Ь4,0),

где А = 1/-\/2. Заметим, что все 18 точек {р{\ лежат на верхней полусфере и минимальное угловое расстояние между ними равно 7г/3. В 1991 г., для п = 4, Л. Сабо [53], используя границу Одлыжко-Слоэна: к(4) < 25 доказал, что В(4) ^ 20. В 2005 г. К. Бездек, используя наш результат /с (4) = 24, показал что В(4) ^ 19 и выдвинул гипотезу, что В{А) = 18. Мы доказали эту гипотезу в 2006 году [37].

В работах [4,39] мы получили несколько новых верхних границ для В(п). Однако, все эти границы были улучшены с помощью полуопределенного программирования в работе К. Башок и Ф. Валлентина [2] В этой же работе была доказана наша гипотеза, что В (8) — 183 из работы [37].

0-4. Множества с двумя расстояниями.

В диссертации мы также рассматриваем задачу о максимальных множествах с двумя расстояниями.

Множество S в Мп или Sn_1 (или любом другом метрическом пространстве) называется множеством с расстояниями (по-английски -distance set), если расстояние между его точками принимает не более чем значений.

Для =2 С. Дж. Эйнхорн и И.Я. Шёнберг [24] показали, что существует лишь конечное число множеств (с точностью до подобия) с двумя расстояниями в Rn, состоящих из более чем п + 2 точек.

Отметим, что верхние оценки на мощность множеств с расстояниями в Rn известны около 30-ти лет. В частности, Блокхаус доказал, что число точек у множества S с двумя расстояниями в Мп не превосходит (п + 1)(п + 2)/2. Как показал П. Лисонек [33], эта оценка достигается в размерности 8.

Имеется пример множества с двумя расстояниями в Мп, состоящего из С2+1 = п(п + 1)/2 точек. Мы будем обозначать это множество Мп. Рассмотрим правильный симплекс в 1п, у которого длины всех ребер равны 1. У этого симплекса всего п(п + 1)/2 ребер. Их середины будут образовывать множество с двумя расстояниями. Действительно, если два ребра имеют общую вершину, то расстояние между их серединами равно 1/2 (поскольку соединяющий их отрезок будет средней линией треугольника образованного вершинами этих ребер). Если не имеют, то 1/л/2, поскольку в этом случае вершины этих ребер являются вершинами правильного трехмерного тетраэдра, а между серединами противоположных ребер правильного тетраэдра именно такое расстояние.

Это множество можно описать также с помощью ортонормированного базиса 1, 2, • • •, п+1 пространства . Рассмотрим точки вида

; + ^ (1 ^ г < ] ^ п+ 1).

Заметим, что если а и Ъ (а < Ь) - два расстояния множества Мп, то Ъ2/а2 = 2. Оказывается, что подобное свойство верно для всех достаточно больших множеств с двумя расстояниями.

Ларман, Роджерс и Зейдель [31] доказали, что если множество с двумя расстояниями а и Ъ (а < Ъ) в Мп состоит из более чем 2п + 3 точек, то

а2 к-1 , _ ^ , 1 + л/2п

тт = -г—, гдеА;еМи20^-•

Ъ1 к 2

В работе Дельсарта, Гуталса и Зейделя [23], которую мы упоминали в связи с методом Дельсарта, были получены оценки для случая, когда точки множества £ лежат на сфере в Мп. (Мы будем называть такие множества

сферическими множествами с двумя расстояниями.) В этом случае оценка будет п(п + 3)/2. Заметим, что эта оценка достигается для п — 2, 6 и 22.

Обозначим максимальную мощность сферического множества с двумя расстоян�