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

————————————————————————

Российская Академия Наук

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

УДК 514.17

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

ГЕОМЕТРИЧЕСКИЕ ЗАДАЧИ УПАКОВОК СФЕР

И СМЕЖНЫЕ ПРОБЛЕМЫ

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

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

АВТОРЕФЕРАТ

диссертации на соискание учёной степени доктора физико–математических наук

Москва — 2013

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

Официальные оппоненты: доктор физико-математических наук, член­ корреспондент РАН, профессор Веснин Андрей Юрьевич доктор физико-математических наук Дужин Сергей Васильевич доктор физико-математических наук, про­ фессор Сабитов Иджад Хакович

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

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

С диссертацией можно ознакомиться в библиотеке Математического инсти­ тута им. В. А. Стеклова РАН.

Автореферат разослан « » 2013г.

Учёный секретарь диссертационного совета Д.002.022. доктор физико-математических наук, профессор Долбилин Н. П.

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

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

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

Очевидно, что (2) = 6. В трехмерном пространстве, в задаче о кон­ тактных числах спрашивается: “Как много белых бильярдных шаров могут одновременно касаться черного бильярдного шара?” Наиболее симметричная конфигурация, 12 бильярдных шаров вокруг од­ ного, это когда центры 12 шаров расположены в вершинах правильного ико­ саэдра, а центральный шар расположен в центре икосаэдра. Однако, эти внешних шаров не касаются друг друга и могут свободно перемещаться по по­ верхности центрального шара. Таким образом, возможно, что эти 12 шаров можно сдвинуть в одну сторону, так что найдется место для 13-го шара?

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

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

Schtte K. and v. d. Waerden B.L., Das Problem der dreizehn Kugeln, Math. Ann. v.

u 125 (1953), p. 325–334.

Если говорить коротко, то доказательство Шютте – Ван дер Вардена основано на переборе неприводимых контактных графов. Предположим, что центр центрального находится в начале координат 0. Обозначим через 1,..., точки (векторы) касания внешними шарами центрального шара.

Тогда угол между любыми двумя векторами и не меньше /3 и очевид­ но, что проблема контактных чисел эквивалентна нахождению максимально­ го числа точек на сфере в -мерном пространстве с угловыми расстояния­ ми между точками не меньше 60.

Заметим, что это ведет к важному обобщению:

Mножество точек на сфере в R называется сферическим кодом, ес­ ли минимальное угловое расстояние между точками этого множества не меньше чем.

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

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

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

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

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

Значительный прогресс по проблеме контактных чисел произошел в конце 1970-х годов. В 1978 году Г.А. Кабатянский и В.И. Левенштейн получили но­ вые асимптотические оценки для сферических кодов и плотностей упаковок 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– Brczky K., Packing of spheres in spaces of constant curvature, Acta Math. Acad. Sci. Hung. v.

(1978), p. 243– шаров4. В частности, они доказали, что (Нижняя оценка 20.2075(1+(1)) была известна задолго до этого.) В 1979 году В.И. Левенштейн5 и независимо от него А. Одлыжко и Н. Сло­ эн доказали, что (8) = 240 и (24) = 196560. В работе Одлыжко–Слоэна сравнения с границами Кокстера, при = 4, 5, 6, 7, и 8 новые границы были 25, 46, 82, 140, и 240, соответственно.

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

Все результаты о контактных числах конца 1970-х годов были получены с помощью метода Дельсарта. Метод Дельсарта позволяет получать верхние Кабатянский Г. А. и Левенштейн В. И., О границах для упаковок на сфере и в пространстве, Про­ блемы передачи информации, 14(1), с. 3–25, Левенштейн В. И., О границах для упаковок в -мерном евклидовом пространстве, Докл. АН СССР, т. 245 (1979). с. 1299– Odlyzko A.M. and Sloane N.J.A. New bounds on the number of unit spheres that can touch a unit sphere in dimensions, J. of Combinatorial Theory, A26 (1979), p. 210–214.

Арестов В. В., Бабенко А. Г., О схеме Дельсарта оценки контактных чисел, Труды Мат. ин-та им.

В.А. Стеклова РАН, т. 219 (1997), с. 44– Mittelmann H. D. and Vallentin F., High accuracy semidefinite programming bounds for kissing numbers, Experimental Mathematics, v. 19 (2009), p. 174–178.

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

Пусть — метрическое пространство с функцией расстояния (, ).

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

Иногда удобно рассматривать «непрерывный» вариант этого определе­ ния. То есть, потребовать, чтобы для любой непрерывной функции () и меры на Легко видеть, что если 1 () и 2 () положительно определенные функции, (Из леммы Шура следует, что и произведение двух положительно определен­ ных функций, тоже положительно определенная функция.) Пусть нам удалось найти такую положительно определенную функцию () на пространстве, и число > 0, что для функции () = () +, выполнено следующее Delsarte P., Goethals J. M., and Seidel J. J. Spherical codes and designs, Geometriae Dedicata, v. 6(3) p.

363–388, 1977.

ния между любыми двумя точками лежат в. Давайте оценим сумму двумя способами.

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

С другой стороны, поскольку при = расстояние (, ), т.е.

Объединяя эти два неравенства, мы получаем, что Это неравенство и называется границей Дельсарта.

означает, что расстояния между точками и не меньше. Таким обра­ зом, метод Дельсарта позволяет оценить возможное количество точек в на расстоянии не менее друг от друга.

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

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

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

Имеет место следующая замечательная теорема:

Теорема Шёнберга. Функции имеющие вид являются положительно определенными функциями на сфере S1.

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

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

Теорема Дельсарта–Кабатянского–Левенштейна. Пусть, Если применить эту теорему для = 8 и то поскольку Аналогично доказывается равенство (24) = 196560. Здесь По всей видимости, с помощью метода Дельсарта можно решить пробле­ му контактных только в размерностях = 2, 8, 24. Десять лет назад, Д. В.

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

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

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

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

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

Fejes Tth G., Ten-neighbor packing of equal balls, Periodica Math. Hungar., v. 12 (1981), с. 125–127.

В 1991 г., для = 4, Л. Сабо, используя границу Одлыжко-Слоэна: (4) 25 доказал, что (4) 20. В 2005 г. K. Бездек, используя наш результат доказали эту гипотезу в 2006 году [4].

В работах [5,7] мы получили несколько новых верхних границ для ().

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

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

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

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

Отметим, что верхние оценки на мощность множеств с расстояниями в R известны около 30-ти лет. В частности, Блокхаус доказал, что число точек у множества с двумя расстояниями в R не превосходит ( + 1)( + 2)/2.

Как показал П. Лисонек14, эта оценка достигается в размерности 8.

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

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

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.

Lisonk 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, 2,..., +1 пространства R+1. Рассмотрим точки вида зависимости от того имеют ли они общую единицу в координатной записи или нет. Сумма координат получившихся (+1)/2 точек будет равна 2 и поэтому они будут лежать в гиперплоскости задаваемой уравнением 1 +...++1 = 2.

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

Ларман, Роджерс и Зейдель15 доказали, что если множество с двумя рас­ стояниями и ( < ) в R состоит из более чем 2 + 3 точек, то В работе Дельсарта, Гуталса и Зейделя9, которую мы упоминали в свя­ зи с методом Дельсарта, были получены оценки для случая, когда точки множества лежат на сфере в R. (Мы будем называть такие множества 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, 6 и 22.

Обозначим максимальную мощность сферического множества с двумя расстояниями через (). Тогда В работе [8] мы улучшили эту оценку и было показано, что для 6 < < 22 и 23 < < 40. Недавно этот результат был расширен для Цель работы 1. Решить проблему контактных чисел для размерности 4.

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

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

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

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

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

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

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

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

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

Пусть — это множество с двумя расстояниями и, располо­ женное на единичной сфере в R, причем сумма этих (угловых) рас­ стояний не превосходит, т.е. +. Тогда количество точек в не превосходит ( + 1)/2.

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

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

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

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

Публикации.

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

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

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

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

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

Теорема A. (4) = 24.

Доказательство Теоремы A основано на обобщенном методе Дельсарта (ОМД). Первым шагом в этом методе является построение “подходящего” многочлена (). Этот многочлен ищется в форме В классическом методе Дельсарта на коэффициенты накладывается условие () 0 на отрезке [1, 1/2]. Как мы показали выше, из этого В ОМД мы ослабляем это условие и требуем, чтобы при заданном па­ монотонно убывающей на интервале [1, 0 ]. Параметр 0 и коэффициенты ищутся такими, чтобы, по возможности, минимизировать сумму ().

Рассмотрим на единичной сфере S1 набор точек = {0, 1,..., }.

Обозначим, через максимум суммы ( ) := (1)+ (0 ·1 )+...+ (0 · ) по всем таким наборам, что При = 0 зададим 0 := (1).

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

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

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

Разложив 4 по многочленам Гегенбауэра = (в этой размерности это многочлены Чебышева второго рода) получим Здесь 0 = 0, 6058. Из (2) следует К. Шютте и Б.Л. Ван дер Варден17 доказали, что (3, ) = 7 только если < 77, 8696. Поскольку 0 > 77, 8696, то = 6.

Таким образом, доказательство Теоремы A сведено к доказательству того, что < 25 при = 0, 1, 2, 3, 4, 5, 6. Несложно видеть, что Для случая = 2 можно показать, что максимум ( ) достигается когда точки 1 и 2 располагаются на расстоянии 150 от точки 0. Тогда Наиболее сложная часть доказательства - это вычисление при = 3, 4, 5. Если точки 0, 1,..., на S3 являются максимальной конфигураци­ ей для, то это множество неприводимо. Это означает, что точки множе­ ства := {, = 1,..., }, которые лежат от 0 на расстоянии не ближе чем arccos 0 нельзя отодвинуть от 0, чтобы какие-то расстояния между ними не стали бы меньше 60.

Можно показать, что неприводимое множество 3 образует треугольник со сторонами равными 60, 4 образует правильный тетраэдр, а 5 - бипира­ миду у которой все ребра длиной 60, кроме возможно одного, являющегося Schtte K. and v. d. Waerden B.L., Auf welcher Kugel haben 5,6,7,8 oder 9 Punkte mit Mindestabstand 1 Platz?, Math. Ann. v. 123 (1951), p. 96–124.

стороной треугольника, разбивающего 5 на две пирамиды. (Удивительно, но это утверждение не является тривиальным, по-крайней мере мы не смогли найти простые рассуждения, и полное его доказательство занимает около страниц.) Следующим шагом является вычисление верхних границ для. Для этого разбивается на клетки (параллелепипеды) на которых при фикси­ рованных {, = 1,..., } функция (0 ) := ( ) достигает максимума в вершинах. При достаточно мелком разбиение можно показать, что Для случая = 6 можно рассмотреть точку ближайшую к 0 и остав­ шиеся пять точек. Поскольку у нас уже оценка для пяти точек, а расстояние до ближайшей можно оценить, то это можно использовать для оценки 6.

Вычисления показывают, что Таким образом, max {0, 1, 2, 3, 4, 5, 6 } = 2 < 25.

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

В этом случае подходящий многочлен 0 = 0, 5907, = 4, = 1 = 12, 88. Разложение 3 по многочленам Лежандра = имеет вид а стало быть 0 = 1, 0. В итоге мы получаем, что Содержание главы Вторая глава диссертации посвящена решению проблемы односторонних контактных чисел в размерности 4 и оценке мощности сферических кодов в сферических шапочках.

Теорема C. (4) = 18.

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

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

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

Тогда Лемма C1. Пусть + S1 является сферическим /3кодом. Тогда (ii) ( ) вательно для = 4 из Леммы C1 следует Из этих неравенств получаются только следующие возможности для | |, ( ) и ( ):

Для того, чтобы доказать Теорему С надо доказать, что Лемма C2. (, ) = (15, 4).

Лемма C3. (, ) = (14, 5).

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

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

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

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

(,, ) - функция, определяемая уравнением Теорема D.

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

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

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

Теорема E. Пусть — это множество с двумя расстояниями и, расположенное на единичной сфере в R, причем сумма этих (угловых) рас­ стояний не превосходит, т.е. + превосходит ( + 1)/2.

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

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

Теорема F. Если 6 < < 22 или 23 < < 40, то Для = Мы уже отмечали, что недавно этот результат был расширен для = Заметим, что 6, 22, 46, 78 являются числами вида (2 + 1)2 3, где = 1, 2, 3, 4. Это приводит к следующей гипотезе:

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

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

В этой схеме важную роль играет теорема Лармана-Роджерса-Зейделя.

Эта теорема была обобщена Х. Нозаки для множеств с - расстояниями18.

Используя это обобщение, в главе 3 доказывается следующая Теорема G. Обозначим через () максимальную мощность сферического множества с тремя расстояниями в мерном пространстве. Тогда Теоретическая и практическая ценность Диссертация носит теоретический характер. Полученные в диссертации результаты представляют интерес для дискретной и вычислительной геомет­ рии, теории упаковок шаров, комбинаторике, и теории кодов. Результаты диссертации могут быть полезны для специалистов из Математического ин­ ститута им. В. А. Стеклова РАН, Института Проблем Передачи Информа­ ции им. А. А. Харкевича РАН, Московского государственного университета им. М. В. Ломоносова, Института теоретической физики им. Л. Д. Ландау Nozaki H., 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, Hausdorff 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 - Geometric Topology», June 26–July 3, - Международная математическая конференция «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 г., IST (г. Вена, Австрия);

- «XIII Международный Семинар по Алгебраической и Комбинаторной Тео­ рии Кодов (ACCT2012)», Поморье, Болгария, 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 COE 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 Communications, v. 1 (2007), p. 131–149.

[6] Musin O.R., The kissing number in four dimensions, Annals of Math., v. (2008), no. 1, p. 1– [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. (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 Publ., 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– [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– [14] Акопян А.В., Кабатянский Г.А., Мусин О.Р., Контактные числа, коды и сферические многочлены, Математическое просвещение. Третья Серия, Вып.

16 (2012), с. 57–74.

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