Аннотация:
В докладе предполагается обсудить проблему упаковки шаров и проблему упаковки сферических шапочек на сфере. Вопрос о контактном числе является важным частным случаем: спрашивается, какое наибольшее число равных шаров в $n$-мерном евклидовом пространстве может касаться одного шара того же размера. Будем обозначать это число $k(n)$. Контактное число в размерности 3 явилось предметом знаменитой дискуссии между И. Ньютоном и Д. Грегори в 1694 г. После нескольких ошибочных «доказательств» [например, Хоппе (1874)], равенство $k(3) = 12$ было доказано Шютте и Ван дер Варденом в 1953 г. В 1978 г. Г. А. Кабатянский и В. И. Левенштейн предложили новый подход в теории кодирования: так называемый метод Дельсарта, и с его помощью нашли верхние границы для плотности упаковки шаров и асимптотическую границу для $k(n)$. В 1979 г., методом Дельсарта, В. И. Левенштейн, и независимо Одлыжко и Слоэн доказали, что $k(8) = 240$, $k(24) = 196560$, а также $k(4) < 26$. В 1997 г. В. В. Арестов и А. Г. Бабенко доказали что методом Дельсарта не может быть получено неравенство $k(4) < 25$.
В 2003 г. докладчик предложил обобщение метода Дельсарта для сферических упаковок и доказал равенство $k(4) = 24$. Этим же методом получается доказательство (самое простое в настоящий момент): $k(3) = 12$. Недавно, подобным методом, докладчику удалось доказать равенство $B(4) = 18$, где $B(n)$ — одностороннее контактное число (one-sided kissing number). В докладе будут предложены схемы этих доказательств. Основой метода Дельсарта является линейное программирование (ЛП).
В докладе также предполагается обсудить новый метод для теории кодирования, основанный на выпуклом программировании (ВП). В частности, метод ВП дает лучшие верхние границы для $k(n)$ и $B(n)$, чем ЛП.
Для понимания доклада специальных знаний не потребуется.
|