Аналитические методы в экстремальных геометрических задачах на евклидовой сфере тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат наук Куклин, Николай Алексеевич

• Куклин, Николай Алексеевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Куклин, Николай Алексеевич

Содержание

Список обозначений

Введение

1 Двойственность в задаче Дельсарта

1.1 Прямая и двойственная задачи Дельсарта. Теоремы двойственности

1.2 Сведение задачи к системе нелинейных алгебраических уравнений

1.3 Оценки параметров экстремальных функций и мер

2 Алгоритмы и их реализация

2.1 Интервальная арифметика и интервальная теорема Штурма

2.2 Сведение полиномиальных задач бесконечномерного линейного программирования к задачам SDP

2.3 Решение задачи Дельсарта с помощью построения базиса Гребнера

2.4 Программа в Maple построения базиса Гребнера системы (1.2.2)

3 Задача Дельсарта в конкретных размерностях

3.1 Задача Дельсарта в трехмерном пространстве

3.2 Результаты для новых больших размерностей

3.3 Решение задачи Дельсарта в размерности 173

Список литературы

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

Список обозначений

|ЛГ| — мощность множества ./V; Ъ — кольцо целых чисел;

— множество целых неотрицательных чисел; — поле рациональных чисел; = {£ = (6) ■ • • > £тп) I 6,6, • • •, Ст е М} — га-мерное евклидово пространство;

Сп = {г = (21, 22, • • ■, гп) | 21, 22,..., е С} — н-мерное унитарное пространство;

тт — контактное число га-мерного евклидова пространства, га ^ 2;

0 — система ультрасферических многочленов степени к е ортогональных на отрезке [—1,1] с весом ф{£) = (1 — ¿2)а, а = (га — 3)/2, га ^ 2, нормированных условием Р^п\1) = 1;

{/а;}£°=о — коэффициенты (Фурье) функции /, суммируемой с весом ф на отрезке [—1,1] по системе

С (К) — банахово пространство вещественнозначных непрерывных функций на компакте К с: [—1, 1] с равномерной нормой;

Фт с С[— 1, 1] — множество функций с суммируемым рядом коэффициентов по многочленам

Тт с Фт — множество допустимых функций в задаче Дельсарта, га ^ 2;

ит — значение прямой задачи Дельсарта, т ^ 2;

а Тт — множество экстремальных функций в задаче Дельсарта; В(К) — сигма-алгебра борелевских подмножеств компакта а: с [-1,1];

гса(К) — банахово пространство вещественнозначных регулярных счетно-аддитивных функций множества (мер), определенных на сг-алгебре В(К), где К с [—1,1] — замкнутое множество; норма в этом пространстве определяется как ¡/¿Ц = тах^щк) уьВ — пипд^^) /лВ:

гса+(К) с: гса(К) — конус неотрицательных мер на компакте А-с [-1,1];

<5(£) е гса+({£}) — мера Дирака, сосредоточенная в точке Ь е К. с единичным весом;

йирр(^) е В(К) — носитель меры ¡1 е гса +(К)\

-/"СО ^/-¿ОО — интеграл Лебега по мере /I е гса+(Я"); = Рк^Ю ~ коэффициент (Фурье) меры /х е гса +{К) для к е и т ^ 2;

ЛЛт с: гса+[—1, — множество допустимых мер в двойственной задаче Дельсарта, т ^ 2;

ьт — значение двойственной задачи Дельсарта, т ^ 2; М*т с Л4т — множество экстремальных мер в двойственной задаче Дельсарта, гп ^ 2;

с1пп(У) — размерность вещественного линейного пространства V; зр(б') — подпространство линейного пространства V, образованное семейством векторов с V; К - ноле О или Е;

К [г] — кольцо многочленов над полем К, зависящих от (комплексных) переменных г = [г\, ¿2, • • •, ¿п)\

(F) с К [г] — идеал, порожденный семейством многочленов F с ВД;

V(.F) с С" — множество общих комплексных нулей семейства многочленов F с 1С [г];

Z" = Z+ х Z+ х ■ • ■ х Z+ - множество мультииндексов;

_ . _ _ __zan __ М0Н0М) Где z е Сп — (формальная) переменная

иае Z" — мул ьтиин деке;

< — лексикографический (линейный) порядок на множестве мультииндексов или мономов;

LM(/) — старший относительно порядка < моном (без коэффициента) многочлена / е 1С[2];

LC(/) — коэффициент перед LM(/); LT(/) = LC(/)-lm(./');

K[L] — кольцо многочленов над полем К, зависящих от одной (вещественной) переменной £;

deg(/) — степень многочлена / е К[t];

с K[t] — множество многочленов степени не выше d е Z+; d ^ — конус многочленов с вещественными коэффициен-

тами, представимых в виде конечной суммы квадратов многочленов из

Щ'tW,

шоп(/) = \LC(f)\ — многочлен / е К[t], деленный на модуль своего старшего коэффициента;

геш(/, д) б К[£] — остаток от деления многочлена / е К[£] на многочлен 5 б K[i];

sign(£) — знак вещественного числа £;

sch(/, t) — число перемен знака последовательности Штурма многочлена / g K[i] в конечной точке ¿el или в бесконечно удаленной точке t е {—со, оо};

М^о ~~ множество вещественных квадратных положительно полуопределенных матриц размера 1x1]

Ат — матрица, транспонированная для матрицы А] det(A) — определитель матрицы А]

А • В = AijBij — скалярное произведение симметричных

матриц А = (Aj)jJ=i и В = (Bij)\ ,j=l размера 1x1]

SDP — Semidefinite programming — полуопределенное программирование;

GMP — GNU Multiple Precision — открытая библиотека, реализующая арифметику произвольной точности для целых чисел, рациональных чисел, а также чисел с фиксированным числом знаков после запятой;

SDPA-GMP — SDP Algorithm — свободный пакет, использующий библиотеку GMP для решения задач SDP с любой точностью; Haskell — язык программирования.

Введение диссертации (часть автореферата) на тему «Аналитические методы в экстремальных геометрических задачах на евклидовой сфере»

Введение

В диссертационной работе изучается экстремальная задача для положительно определенных непрерывных на отрезке функций с односторонним ограничением, возникшая из применения схемы Дель-сарта для оценки сверху мощности сферических кодов. Схема Дель-сарта появилась в исследованиях Ф. Дельсарта [7, 29] границ упаковок в некоторых метрических пространствах. В дальнейшем эта схема была развита и успешно применена в работах Г.А. Кабатянского и В.И. Левенштейна [11], Э.Одлыжко и Н. Слоэна [36], В.И. Левенштейна [14,15], В.М. Сидельникова [19], В.В.Арестова и А.Г. Бабенко [2,3], Д.В.Штрома [25], О.Р. Мусина [17,33,34]. При применении схемы Дельсарта возникает задача бесконечномерного линейного программирования (которую мы будем называть задачей Дельсарта), ее решение дает оценку сверху мощности сферического кода. Изложение этих результатов и другая родственная, богатая информация имеется в монографии Дж. Конвея и Н. Слоэна [13]. Отметим еще работу В.А.Юдина [26], в которой для изучения достаточно общей задачи минимизации функции фиксированного числа точек на единичной сфере евклидова пространства Rm применяется аналог схемы Дельсарта. Дальнейшие результаты, касающиеся минимизации ньютоновского потенциала конечной системы зарядов на сфере, были получены Н.Н.Андреевым, Г. Коном и

Р. Шварцем. Недавно схема Дельсарта была улучшена за счет применения полуопределенного программирования (SDP) в работах К. Башок, Ф.Валлентина, Г.Кона и О.Р.Мусина (см., например, [32]).

Введем скалярное произведение векторов £ = (£i, ■ • •, Çm), V = (тух, 7/2, .. •, г}т) б R"\ m ^ 2, по формуле £г) = х fyrjj. Для вещественного числа s g [—1,1) сферическим s-кодом называется (конечное) множество точек Q на единичной сфере пространства такое, что для любых различных точек rj g Q выполняется неравенство £77 ^ s. В дальнейшем нас будут интересовать ^-коды. Обозначим через тт максимальную мощность сферического |-кода в размерности m ^ 2.

Нетрудно понять, что тт совпадает с контактным числом пространства Шт — максимальным числом шаров единичного радиуса с непересекающимися внутренностями, касающихся единичного шара пространства. Точки касания шаров как раз и являются точками сферического 5~кода.

В двумерном случае задача о нахождении числа тг решается просто: точками |-кода являются вершины правильного шестиугольника, вписанного в единичную окружность. Для размерностей m ^ 3 точное значение числа тт известно лишь при m = 3,4,8,24, а именно, т3 = 12 (К.Шютте, Б.Л. вандерВарден [37], см. также [33]), 74 = 24 (О.Р.Мусин [17,34]), т§ = 240, т24 = 196560 (В.И.Левешптейн [14]; Э. Одлыжко, Н. Слоэн [36]); в остальных случаях известны лишь оценки снизу и сверху величины тт, например, 40 ^ 75 ^ 44 (верхняя оценка — см. [32]).

Конкретные расположения точек дают оценки снизу числа тт (см. [13]). В данной работе оценки снизу величины тт не рассматрива-

ются. Оценку сверху для тт дает подход Дельсарта, который мы сейчас приведем.

Обозначим через Р^ ультрасферические многочлены (многочлены Гегенбауэра) степени к = 0,1,2..., ортогональные на [—1, 1] с весом ф(Ь) — (1 — ¿2)(т-3)/2 и нормированные условием Р^т\ 1) = 1; см., например, [22, гл. 7, §6].

Определим множество Фт непрерывных на отрезке [—1, 1] функций, представимых рядами

00

к=О

с суммируемой последовательностью вещественных коэффициентов: Е"=о \Фк\ <

Рассмотрим множество Тт с: Фш функций /, обладающих следующими тремя свойствами:

(1) /о = 1;

(2) Д ^ 0 для всех к ^ 1;

(3) /(£) ^ 0 для любых Ь е [-1, ±].

Элементы множества Тт (при конкретном т) будем в дальнейшем называть допустимыми функциями. Задача Дельсарта состоит в отыскании величины

00

и экстремальных функций, на которых достигается нижняя грань в (0.1). Известно (см., например, [3, теорема А]), что тт ^ ит для всех т ^ 2.

Можно рассмотреть более общую задачу типа (0.1), в которой третье условие /(£) ^ 0, t е [—1, заменено на /(£) ^ 0, t е [—1, cos в] для

параметра 9 е (0, 7г]. Обозначим значение обобщенной задачи Дельсарта через ит{9). Так же как и для углового расстояния величина ит{9) дает оценку сверху мощности сферического s-кода с угловым расстоянием s = cos 9 (см., [3, теорема А]).

В 1970 году венгерский математик П.Туран в частной беседе с С.Б. Стечкиным предложил задачу типа обобщенной задачи Дельсарта из предыдущего абзаца для т = 2, в которой условие /(i) ^ 0 для t е [—1, cos 0] заменено на f(t) = 0 для t е [—1, cos в\. Данная задача называется задачей Турана; обозначим значение задачи Турана (т.е. величину типа (0.1) но только что описанному классу функций) через ит{9). В работе [20] (см. сборник трудов [21]) С.Б.Стечкин рассмотрел задачу Турана для в = где N ^ 2 — целое число, нашел экстремальную функцию max{0, N — ^ arccos t} и значение ит( jf) — N. Из последнего равенства следует, что для всех 9 = N ^ 2, значения задач Турана и Дельсарта при m = 2 совпадают, а все экстремальные функции задачи Турана являются экстремальными функциями задачи Дельсарта. Позже задачи Турана и Дельсарта при m = 2 для других в е (0, 7г] рассмотрели Д.В.Горбачев, А.С. Маношина, В.И.Иванов и Ю.Д. Рудомазина в работах [5,9,10]. В итоге был описан класс экстремальных функций в задаче Турана для в е (0, тг] и установлено совпадение значений ит{9) = 9 е (0, 7г].

Отметим, что при m = 2 существуют экстремальные функции задачи (0.1), отличные от экстремальных функций задачи Турана. Например, такими функциями являются многочлены + 1)(21 + 1)2(21 — 1), ±(£ + l)2(2i + 1)2(2£ - 1), + 1)2(2£ + 1)2(2£ - 1)(4£2 - 10£ + 11),

+ 1)(2£ + l)2i2(2£ - 1)(8£3 - 812 -81 + 9), а также всевозможные выпуклые комбинации экстремальных функций задачи Турана и перечис-

ленных многочленов. Насколько известно автору, такими комбинациями не исчерпывается весь класс экстремальных функций задачи (0.1) для т = 2.

Для т ^ 3 о числах ит известно гораздо больше, чем о контактных числах тт. При 777, = 8,24 величины ит фактически были найдены В.И. Левенгатейном [14] и Э. Одлыжко, Н. Слоэном [36], поскольку в [14] и [36] оценки сверху для тт были получены с помощью конкретных функций из классов Тт и они совпали с известными нижними оценками. Непосредственно задачу Дельсарта (0.1) впервые результативно изучали В.В. Арестов и А.Г. Бабенко [2]; они показали, что для размерности тп — 4 задача Дельсарта имеет значение щ = 25.5584.... Как видно, в этом случае классическая схема Дельсарта не позволяет получить оценку 74 ^ 24, совпадающую с известной оценкой снизу 24 ^ 74. Позже Д.В. Штром [25] нашел величины ит для следующих размерностей:

5 ^ т ^ 7, 9 ^ тп ^ 23, 25 ^ гга < 146, 148 ^ тп ^ 156, тп = 161.

Во всех перечисленных в предыдущем абзаце случаях была найдена экстремальная функция, а для т Ф 8, 24 доказано, что она — единственна [2,25]. Во всех случаях последовательность коэффициентов {/а,-}/£=о экстремальной функции состоит из конечного числа отличных от нуля чисел. Другими словами, экстремальной функцией задачи (0.1) при указанных га является алгебраический многочлен, причем его степень растет с ростом размерности.

Отметим, что при га = 8,24 экстремальная функция не единственна и ситуация очень похожа на ситуацию для т = 2, описанную выше. А именно, в размерности 8 кроме экстремально-

го многочлена f(t + 1)(2£ + lft2(2t - 1) (см. [14, 36]) нам известны экстремальные многочлены + l)2(2i + l)2t2(2t — 1) и | (i + 1) (2i + l)212 (21 - 1) (6i3 - 912 + 3i + 80); в размерности 24 кроме ^(¿ + l)(2i + l)2(4i + l)2i2(4i-l)2(2i-l) (см. [14,36]) нам известен экстремальный многочлен —1)2(2£ + l)2(4i + l)2i2(4i — 1)2(2£ — 1). Кроме того, очевидно, экстремальными функциями являются всевозможные выпуклые комбинации выписанных многочленов, и, по-видимому, весь класс экстремальных функций не исчерпывается такими комбинациями.

Цель работы состоит в разработке новых методов решения задачи Дельсарта оценки мощности сферических кодов с заданным угловым расстоянием; программная реализация данных методов и их применение для решения задачи Дельсарта в конкретных случаях.

Методы исследования. Новые методы решения задачи Дельсарта основаны на теории двойственности в выпуклом анализе, которая впервые была применена в [2]. Численные результаты основаны на использовании методов решения задач полуопределенного программирования с применением кластера «Уран» ИММ УрО РАН. Дальнейшие результаты получаются за счет применения вычислительной коммутативной алгебры (алгоритмы для многочленов одной переменной и базисы Гребнера) и интервальной арифметики.

Научная новизна. Результаты диссертации являются новыми. Основные из них заключаются в следующем.

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

решения задач SDP — SDPA-GMP. На основе этой информации строится система нелинейных алгебраических уравнений для решения прямой и двойственной задачи Дельсарта. В первом методе получившаяся система решается с помощью построения базиса Гребнера. Второй метод использует SDP для получения численных решений ряда вспомогательных задач бесконечномерного линейного программирования; затем из этой информации при помощи интервальной арифметики устанавливается вид экстремального многочлена в задаче Дельсарта и его единственность. Все необходимые алгоритмы реализованы на языке программирования Haskell и в системе символьных вычислений Maple.

2. Дано решение задачи Дельсарта в 11 новых больших размерностях: 147, 157, 158, 159, 160, 162, 163, 164, 165, 167, 173; найдены экстремальные многочлены и доказана их единственность. Структура полученных экстремальных многочленов отличается от структуры экстремальных многочленов в меньших размерностях 4 ^ т ^ 146 (т Ф 8,24). Для исследования использовалось SDP и построение базисов Гребнера.

3. Исследована задача Дельсарта в трехмерном случае. Доказано, что единственной экстремальной функцией задачи является многочлен 27 степени, который представим в виде линейной комбинации многочленов Лежандра порядков 0,1, 2, 3,4, 5, 8, 9,10,20,27 с положительными коэффициентами, имеет простой нуль в точке 1/2 и пять двойных нулей в интервале (—1, Установлены близкие двусторонние оценки для коэффициентов этого многочлена. Исследована двойственная задача для неотрицательных мер на отрезке [—1, в частности, доказано, что экстремальная мера единственная.

Научная значимость. Разработанные методы могут быть использованы для решения задач бесконечномерного линейного программиро-

вания типа задачи Дельсарта. Например, для исследования задачи об упаковке в размерностях 8 и 24. Свойства новых экстремальных многочленов в больших размерностях могут быть применены для уточнения скорости роста величины тт при т со.

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

Апробация работы. Результаты диссертации были представлены на летних Школах С.Б. Стечкина по теории функций (Миасс, 2010-2014); международной конференции «Алгоритмический анализ неустойчивых задач», посвященной памяти В.К.Иванова (Екатеринбург, 2011); международных конференциях «Современные проблемы математики, механики, информатики» (Тула, 2012, 2013); молодежных конференциях, проводимых ИММ УрО РАН (Екатеринбург, 2010-2012, 2014). Автор выступал с докладами по теме диссертации па следующих научных семинарах: «Экстремальные задачи теории функций и операторов» под руководством В.В. Арестова в Уральском федеральном университете (2010-2014); «Сферические коды» под руководством А.Г. Бабенко и А.Н. Борбунова в Уральском федеральном университете (2010-2013); на совместном семинаре отделов Аппроксимации и приложений и Теории приближения функций в ИММ УрО РАН (2012-2014).

Публикации. Основные результаты по теме диссертации изложены в 10 публикациях [38-47], 3 из которых — в журналах, рекомендованных ВАК [38-40], 7 — в трудах и тезисах конференций [41-47].

Объем и структура работы. Диссертация состоит из введения, трех глав и списка литературы. Главы разбиты на 10 параграфов. Пол-

ный объем диссертации составляет 98 страниц. Список литературы содержит 47 наименований.

Основное содержание работы. В первой главе исследуется взаимосвязь между прямой и двойственной задачами Дельсарта.

В § 1.1 выписана двойственная задача к задаче Дельсарта (0.1) и приведены основные законы двойственности, впервые установленные в [2]. Обозначим через гса(К) пространство вещественнозначных регулярных счетно-аддитивных функций множества, определенных на сг-алгебре В(К) борелевских подмножеств компакта К с: [—1, 1]. Элементы этого пространства в дальнейшем будем называть мерами. Пространство гса (К) банахово относительно нормы

|Ы| = max аВ — min цВ, 1 ВеВ(К) ВеБ(К)

являющейся полной вариацией меры ц.

Рассмотрим конус гса +{К) с гса (К) неотрицательных мер. Для меры /х е гса +(К) введем числа

ßk

= Г pjr\t)d»(t), 0.

JK

Пусть Л4 = Л4т а гса+[— 1, есть множество мер ¡1 таких, что Д/с ^ — 1 для всех Элементы множества Л4т будем в дальнейшем

называть допустимыми мерами. Двойственная задача Дельсарта состоит в отыскании величины

vm = 1 + sup \\ц\\ = 1 + sup До- (0-3)

цеМ ¡¡.еЛЛ

Теорема двойственности. Пусть т ^ 2. Тогда

(1) величины ит и ут достигаются;

(2) выполняется равенство ит = ьт\

(3) допустимые функция / и мера ¡л экстремальны тогда и только тогда, когда они обладают следующими свойствами:

(3.1) если номер к ^ 1 таков, что > —1, то = 0;

(3.2) функция / обрагцается в нуль на носителе меры ц.

Во втором параграфе на основе теоремы двойственности получены необходимые и достаточные условия существования экстремального многочлена некоторого определенного вида (теоремы 0.1 и 0.2 соответственно). Данный результат обобщает результаты работ [2,25] и позволяет восстанавливать экстремальные элементы задач (0.1) и (0.3) по информации об экстремальном многочлене.

А именно, типом (экстремального многочлена) назовем четверку ((¿, Ы,р,г), где ¿^Оиг^О — целые числа, р = 0 или р — 1, и N а {1, 2,..., ¿ — 1} — множество чисел. Потребуем, чтобы выполнялось неравенство с1 — р — 2г — 1^0.

Будем говорить, что экстремальный многочлен / задачи (0.1) имеет тип (й, N,p,r), если / обращается в нуль в точке 1/2: /(1/2) = 0, й = с^(/), N = {к < с1 | /л; = 0}, р — 1, если /(—1) = 0 и р = 0 иначе, и г — число корней многочлена / в интервале (—1,

С каждым типом (с?, г) свяжем следующие многочлены, зависящие от переменной а также формально зависящие от переменных Zr-l,Ro, /¡4, . . . , Я,1-р-2г-2'-

Ç(t) = f - Zr-itr~l + ... + {-iyz0;

pit) = td-P~2r~1 - Rd-p-2r-2td~p~2r~2 + • ■ • + (-l)d_p~2r~1i2o; Vo(t) = (t + iy ((t) (t - 1/2) (t - I);

ф(1) = {i + If W) (i — 1/2); a(t) = (i + 1)42W (t- 1/2)^(0-

Разложим каждый из них по системе 1Р1 ультрасферических мно-

(. J к^о

гочленов. С каждым типом свяжем систему нелинейных алгебраических уравнений

г

(<Pj)o+ Uteiv Gk(<Pj)k= 0, Q^j^d-p-r-з-,

S-($o + ZtkeNGk$k)-ilj{l) = Q] < 4 J (0.5)

5 • Э0 - (j(l) = 0; ак = 0, feeiV,

зависящую от переменных

S, Rq, Ri, ... , Rd-p-2r-2, {GkjkeN, Zq, Z\, . . . , Zr-1-

(0.6)

Число уравнений системы (0.5) совпадает с числом неизвестных и равно d+\N\-p-r.

Если формальным переменным (0.6) придать конкретные (комплексные) значения, то многочлены (0.4) становятся многочленами от одной переменной t. При этом многочлен </?о имеет степень р + г + 2. Обозна-

чим его корни через ¿о, ¿1,..., Ьр+Г = 1/2, tp+r+l = 1, и с каждым из этих корней и свяжем многочлен шг(Ь) = ■ (£ — ¿г)-1 и число

и = в - Е вьы!) • Ыи))~\ о

V 1-е ЛА /

А-еДт '

Помимо того, для номеров к > д введем числа

=

1 Г р+г \

,=п /

5 х

4 г=0

Теорема 0.1. Пусть гп ^ 2, /л — экстремальная мера задачи (0.3) и / — экстремальный многочлен задачи (0-1) типа (с/, г). Тогда для типа ((I, г) существует решение системы (0.5), которое удовлетворяет условиям

(С1) а(£) ^ 0, £ е [-1, 1];

(С2) справедливы неравенства Эо > 0 и Эк ^ 0 длл есеж к ^ 1; (СЗ) для есеж 0 ^ г ^ р + г выполняется неравенство Д.- ^ 0; (С4) вк^О дляке ЛГ; (С5) С/с ^ 0 для есеж к > д]

(С6) многочлен £ имеет г простых нулей —1<1Р<...< Ьр+г-1 < (С7) выполняются равенства Б = ит = /(1);

(С8) / =

(С9) справедливо равенство

р+г

= £ (0.7)

г=0

г(?е $(£) естъ дельта-мера Дирака, сосредоточенная в точке

Теорема 0.2. Пусть га ^ 2, г) — некоторый тип и суще-

ствует решение системы (0.5), удовлетворяющее условиям (С1)-(С6) предыдущей теоремы. Тогда многочлен / = сг/<т0 имеет тип (д,АТ,р,г) и является экстремальным в задаче (0.1), а дискретная мера (0.7) является экстремальной в задаче (0.3). Более того, если выполнены условия (Е1) Эк > 0 для всех 1 ^ к < д, к $ А/"; (Е2) Ь{ > 0 при 0 ^ г ^ р + г; (ЕЗ) С/г > 0 для к е N и к> д]

(Е4) существует лишь одно решение системы (0.5), удовлетворяющее условиям (С1)-(С7),

то найденный экстремальный многочлен / является единственной экстремальной функцией задачи (0.1), а мера [г — единственной экстремальной мерой задачи (0.3).

В § 1.3 доказаны следующие две теоремы, которые позволяют оценить коэффициенты экстремальной функции и значения экстремальной меры.

Теорема 0.3. Пусть га ^ 2,

(1) число В еШ такое, что ит ^ В;

(2) I ^ 1 — целое число\

(3) мера ь> е гса+([— 1, и {1}) удовлетворяет условиям ь>к ^ 0 при к ^ 1, к Ф I и щ ^ 1.

Тогда для коэффициента // экстремальной функции f задачи (0.1) справедливо неравенство ¡1 ^ —

Теорема 0.4. Пусть га ^ 2,

(1) число А е М удовлетворяет условию А ^ ит\

(2) Е с [— 1, j] — замкнутое множество;

(3) функция h е Фт удовлетворяет следующим условиям:

(3.1) hk^0 прик^ О,

(3.2) h(t) ^ -1, t е Е и ^(¿) 0, t е [-1, \ Е.

Тогда для экстремальной меры /i задачи (0.3) справедливо неравенство ¡лЕ ^ h{ 1) — Ah0.

Для получения хороших оценок в теоремах 0.3 и 0.4 требуется предварительно численно решать вспомогательные задачи бесконечномерного линейного программирования.

Во второй главе описаны методы и алгоритмы, необходимые для решения задач (0.1) и (0.3). В §2.1 даны некоторые понятия и факты интервальной арифметики, а также доказывается интервальный вариант теоремы Штурма.

В §2.2 мы приводим понятие задачи полуопределенного программирования (SDP) и указываем методы сведения некоторых полиномиальных задач бесконечномерного линейного программирования (задач, в которых требуется найти экстремальный многочлен) к задачам SDP для последующего численного решения. А именно, описана схема сведения к SDP следующих задач:

• задачи Дельсарта (0.1);

• вспомогательной задачи из теоремы 0.3;

• вспомогательной задачи из теоремы 0.4.

В §2.3 мы приводим основные определения и результаты об идеалах в кольцах многочленов и базисах Гребнера. Затем описываем метод решения задачи Дельсарта через теорему 0.2. В § 2.4 выписана програм-

ма для системы компьютерной алгебры Maple, в которой строится базис Гребнера системы (0.5).

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

Теорема 0.5. При m = 3 единственной экстремальной функцией задачи (0.1) является многочлен 27 степени, который представим в виде линейной комбинации многочленов Лежандра порядков 0,1,2,3,4, 5,8,9,10,20, 27 с положительными коэффициентами, имеет простой нуль в точке 1/2 и пять двойных нулей в интервале (—1,

Из теоремы 0.1 следует, что данный многочлен может быть восстановлен из решения системы (0.5), соответствующей типу

(27, {6,7,11,12,13,14,15,16,17,18,19,21,22, 23, 24, 25, 26}, 0,5).

Доказательство теоремы 0.5 основано на получении оценок из теорем 0.3 и 0.4 (эти оценки получены из решения соответствующих задач SDP при помощи открытого пакета SDPA-GMP), а также применении интервальной арифметики и интервальной теоремы Штурма.

Для значения щ задачи справедливы оценки

13.15822571531178091985014536493872725

13.15822571531178091985014536507.

В этом параграфе доказан также следующий результат, устанавливающий единственность экстремальной меры в двойственной задаче (0.3) при m = 3.

Теорема 0.6. Экстремальная мера задачи (0.3) при m = 3 единственная. Эта мера дискретная и сосредоточена в шести нулях экстремального многочлена задачи (0.1).

Во втором параграфе третьей главы приведен тип экстремальных многочленов задачи (0.1) в размерностях

m = 147,157,158,159,160,162,163,164,165,167,173. (0.8)

Доказательство основано на вычислении базиса Гребнера системы (0.5) и применении теоремы 0.2.

Теорема 0.7. В размерностях (0.8) экстремальная функция задачи (0.1) единственная и является многочленом типа (d,N,p,r) с параметрами, описанными в табл. 1.

В табл. 2 приведены соответствующие значения ит задачи Дельсарта, а также отношения B^/um, где В*п — оценки сверху числа ит, полученные В.И. Левенштейном в [15, теорема 4.1].

Ввиду громоздкости вычислений мы разбираем подробно лишь случай m = 173 в § 3.3.

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

Глава 1

Двойственность в задаче Дельсарта

В данной главе исследуется взаимосвязь между прямой и двойственной задачами Дельсарта. Во всех параграфах мы рассматриваем задачу Дельсарта для фиксированного параметра т ^ 2.

1.1 Прямая и двойственная задачи Дельсарта. Теоремы двойственности

В данном параграфе мы выписываем двойственную задачу к задаче Дельсарта и приводим основные законы двойственности, впервые установленные в [2]. Отметим, что в работе [2] двойственная задача формулируется в терминах функций ограниченной вариации, а мы рассматриваем ее в терминах мер. Эти две формулировки двойственной задачи эквивалентны, однако, нам удобнее рассматривать задачу именно в терминах мер.

Пусть т ^ 2 — целое число. Обозначим через {Рультрасферические многочлены (многочлены Гегенбауэра) степени Л; = 0,1,2..., ортогональные на [—1, 1] с весом (1 — ¿2)(т~3)/2 и нормированные условием Р^т\1) = 1; см., например, [22, гл. 7, §6].

Определим множество Ф = Ф7П непрерывных на отрезке [—1, 1] функций, пред ставимых рядами

00

к=О

с суммируемой последовательностью вещественных коэффициентов: 2а°= о < 00 • Из условия ортогональности многочленов следует, что для любых (/зеФи/г^О справедлива формула

1

^ = тМ ^ ю Р - ^(7П~3)/2 ^ (1лл)

4 Л

1

4™) = | (Р,(ш)(£))2(1 --1

Отметим, что операция вычисления коэффициента линейная, т.е. для любых функций <р,ф е Ф, вещественных чисел а, Ь и любого номера

/ч

/с ^ 0 выполняется равенство + Ьф)^— аф+ Ъфь-

Рассмотрим множество Т = с Ф функций /, обладающих следующими тремя свойствами:

(1) /о = 1;

(2) ^ 0 для всех к ^ 1;

(3) /(£) ^ 0 для любых г б [-1, 5].

Элементы множества Т будем в дальнейшем называть допустимыми функциями. Задача Дельсарта состоит в отыскании величины

и экстремальных функций, на которых достигается нижняя грань

Более общая задача исследовалась в работе [2], где была, в частности, доказана достижимость величины и (см. теорему 1.1.6 ниже). Введем множество экстремальных функций Т* = Т*п <= Т, состоящее из тех допустимых функций /, для которых /(1) = и.

Для решения задач типа (1.1.2) в [2] рассматривались двойственные им задачи. Для формулировки двойственной к (1.1.2) задачи рассмотрим банахово пространство гса(К) (см. [6, гл. IV, §2, определение 17]) вещественнозначных регулярных счетно-аддитивных функций множества, определенных на а-алгебре В(К) борелевских подмножеств компакта К с: [—1, 1]. Элементы этого пространства в дальнейшем будем называть мерами. Нормой в этом пространстве является вариация меры:

Обозначим через тса.+ (К) с гса (К) конус неотрицательных мер, т.е. таких мер ц е гса(^), что ¡лВ ^ 0 для любых множеств В е В (К). Для меры е гса +(К) введем числа

(1.1.2)

в (1.1.2).

= шах и В — тт иВ, и, е гса!

ВеВ{К) ВеВ(К)

ВеВ{К)

здесь и далее интегралы понимаются как интегралы Лебега по мере. Отметим, что в силу теоремы Леви (см., например, [6, гл. III, §6, следствие 17]) справедливо равенство

J 00

<p(t) dfi(t) = V $крк, ipe Ф, fie гса +(К). (1.1.3)

к ыо

Пусть Л4 = Л4т cz rca+[—1, есть множество мер р таких, что рк ^ — 1 для всех к ^ 1. Элементы множества Л4 будем в дальнейшем называть допустимыми мерами. На множестве Л4 рассмотрим задачу о вычислении величины

V = vm = 1 + sup \\р\\ = 1 + sup До- (1.1.4)

цеМ. 11.еЛ4

Введем множество экстремальных мер Ai* = Ai*n с= Ai, на которых достигается верхняя грань в (1.1.4), т. е. выполняются равенства 1 + ||/л|| = l + ßo = v.

Задача (1.1.4) является классической двойственной задачей для задачи (1.1.2) (см., например, [4,16,27]). Следующие утверждения параграфа устанавливают двойственность.

Теорема 1.1.1 (Слабая теорема двойственности). Справедливо неравенство V ^ и.

Доказательство. Отметим, что нулевая мера принадлежит множеству Ai, поэтому 1 < v. Если множество Т пусто, то неравенство V ^ и становится очевидным неравенством v ^ сю. Предположим, что Т ф 0; пусть р е Ai и / е Т. Докажем, что выполняется неравенство 1 + I/¿I ^ /( 1), тогда при взятии sup слева и inf справа, получим требуемое неравенство v ^ и.

Поскольку мера неотрицательна, а функция неположительна на отрезке [—1, 1], имеем

1/2

О ^ -1

j/(W)-

Воспользуемся равенствами (1.1.3), /о = 1 и До =

1/2

О ^ -1

iuu

№ dfi(t) = и + ^ /фк

к=\

и неравенствами fk ^ 0, ^ — 1 для к ^ 1: 1/2

Р оо оо

о ^ /(¿) = и + 2 ЛЯ ^ II/"I! - Ц А

•J I__1 7__1

к=1 fc=l

Добавим и вычтем 1 справа: 1/2

Р 00 00

О ^ /(£) (¿МО = 1И + 21кПк > N1 - 2 Л = 1 +М - Я1)- (1-1-5)

J^ jfe=l fc=l

Полученное неравенство эквивалентно неравенству 1 + ¡/¿Ц < /(1). □

Замечание 1.1.2. Неравенства 1 + ||д|| ^ v ^ и ^ /(1) выполняются для любых допустимых /i е Л4, f е Т. Вместе с равенством и = v (см. теорему 1.1.6 ниже) это позволяет получить значение задачи Дельсарта и с любой точностью через численное решение задачи.

Обозначим через supp(^) носитель меры fi е гса+(.?Г), т.е. множество всех таких точек t е К, что для любой открытой окрестности U

(в индуцированной топологии компакта К) точки Ь выполняется строгое неравенство рХ] > 0. Носитель меры обладает следующими свойствами.

Утверждение 1.1.3. Пусть К а [—1, 1] — замкнутое множество и //е гса +(-&')• Тогда выполняются следующие утверждения:

(1) зирр(^) — замкнутое множество, и следовательно зирр(^) е

(2) множество К' = К\зирр(д) обладает нулевой мерой, и потому справедливо равенство

(3) если f — непрерывная неположительная на К функция, то следующие утверждения эквивалентны:

(3.2) функция f зануляется на носителе меры ¡1, т. е. f(t) = 0 для всех t е supp(/i);

Доказательство. (1) Пусть t — предельная точка множества supp(/i) и U — некоторая открытая (в К) окрестность этой точки. Тогда существует точка £' е supp(ц) n U, t' ф t\ для этой точки множество U также является открытой окрестностью. По определению носителя получаем ¡iU > 0. Это неравенство справедливо для всех открытых окрестностей точки t, поэтому t е supp(/i).

Список литературы диссертационного исследования кандидат наук Куклин, Николай Алексеевич, 2014 год

Список литературы

1. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987. С. 356.

2. Арестов В.В., Бабенко А.Г. О схеме Дельсарта оценки контактных чисел // Тр. МИАН. 1997. Т. 219. С. 44-73.

3. Арестов В.В., Бабенко А.Г. Оценки максимального значения углового кодового расстояния для 24 и 25 точек на единичной сфере в R4 // Матем. заметки. 2000. Т. 68, № 4. С. 483-503.

4. Голыитейн Е.Г. Теория двойственности в математическом программировании и ее приложения. М.: Наука, 1971. С. 351.

5. Горбачев Д.В., Маношина A.C. Экстремальная задача Турана для периодических функций с малым носителем и ее приложения // Матем. заметки. 2004. Т. 76, № 5. С. 688-700.

6. Данфорд Н., Шварц Дж. Линейные операторы. Общая теория. М.: Изд-во иностр. лит, 1962. С. 896.

7. Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования. М.: Мир, 1976. С. 136.

8. Дзядык B.K. Введение в теорию равномерного приближения функций полиномами. М.: Наука, 1977. С. 512.

9. Иванов В.И., Горбачев Д.В., Рудомазина Ю.Д. Некоторые экстремальные задачи для периодических функций с условиями на их значения и коэффициенты Фурье // Тр. Ин-та математики и механики УрО РАН. 2005. Т. 11, № 2. С. 92-111.

10. Иванов В.И. О задачах Турана и Дельсарта для периодических положительно определенных функций // Матем. заметки. 2006. Т. 80, № 6. С. 934-939.

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

12. Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. М.: Мир, 2000. С. 687.

13. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. М.: Мир, 1990. С. 791.

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

15. Левенштейн В.И. Границы для упаковок метрических пространств и некоторые их приложения // Проблемы кибернетики. 1983. Т. 40. С. 44-110.

16. Магарил-Ильяев Г.Г., Тихомиров В.М. Выпуклый анализ и его приложения. Изд. 2-е, исправл. М.: Едиториал УРСС, 2003. С. 176.

17. Мусин O.P. Проблема двадцати пяти сфер // Успехи мат. наук. 2003. Т. 58, № 4. С. 153-154.

18. Сеге Г. Ортогональные многочлены. М.: Физматгиз, 1962. С. 500.

19. Сидельников В.М. Об экстремальных многочленах, используемых при оценках мощности кода // Проблемы передачи информации. 1980. Т. 16, № 3. С. 17-30.

20. Стечкин С.Б. Одна экстремальная задача для тригонометрических рядов с неотрицательными коэффициентами // Acta Math. Acad. Scient. Hungaricae. 1972. T. 23, № 3-4. P. 289-291.

21. Стечкин С.Б. Избранные труды: Математика. М.: Наука, 1998. С. 384.

22. Суетин П.К. Классические ортогональные многочлены: 3-е изд., пе-рераб. и доп. М.: Физматлит, 2005. С. 480.

23. Хинчин А.Я. Цепные дроби: 2-е изд. M., JL: государственное издательство технико-теоретической литературы, 1949. С. 112.

24. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989. С. 656.

25. Штром Д.В. Метод Дельсарта в задаче о контактных числах евклидовых пространств больших размерностей // Тр. Ин-та математики и механики УрО РАН. 2002. Т. 8, № 2. С. 162-189.

26. Юдин В.А. Минимум потенциальной энергии точечной системы зарядов // Дискрет, математика. 1992. Т. 4, № 2. С. 115-121.

27. Anderson E., Nash P. Linear programming in infinite-dimensional spaces: Theory and Applications. Chichester etc.: Wiley, 1987. P. 172. (Wiley Intersci. ser. in discrete mathematics and optimization).

28. Buchberger B. An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Ph.D. thesis: University of Innsbruck. 1965 // J. Symb. Comp. 2006. Vol. 41. P. 475-511. (English translation by M. Abramson).

29. Delsarte P. Bounds for unrestricted codes, by linear programming // Philips Res. Rep. 1972. Vol. 27. P. 272-289.

30. Faugere J.-C. A new efficient algorithm for computing Groebner bases (jP4) // J- Pure and Appl. Alg. 1999. Vol. 139, no. 1-3. P. 61-88.

31. Lasserre J. Moments, Positive Polynomials and Their Applications. Imperial College Press Optimization Series, 2010. P. 361.

32. Mittelmann H., Vallentin F. High-accuracy semidefinite programming bounds for kissing numbers // Experiment. Math. 2010. Vol. 19, no. 2. P. 174-178.

33. Musin O. The kissing problem in three dimensions // Discrete Comput. Geom. 2006. Vol. 35, no. 3. P. 375-384.

34. Musin O. The kissing number in four dimensions // Ann. of Math. 2008. Vol. 168, no. 1. P. 1-32.

35. Nakata M. A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite programming solver: SDPA-GMP, -QD and -DD. Proceedings of 2010 IEEE Multi-Conference on Systems and Control, 2010. P. 29-34.

36. Odlyzko A., Sloane N. New bounds on the number of unit spheres that can touch a unit sphere in n dimensions //J. Combinatorial Theory. Ser. A. 1979. Vol. 26, no. 2. P. 210-214.

37. Schutte K., van der Waerden B.L. Das Problem der dreizehn Kugeln // Math. Ann. 1953. Bd. 125. S. 325-334.

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

В ведущих рецензируемых научных журналах, рекомендованных ВАК:

38. Куклин H.A. Вид экстремальной функции в задаче Дельсарта оценки сверху контактного числа трехмерного пространства // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 3. С. 225-232.

39. Куклин H.A. Метод Дельсарта в задаче о контактных числах пространств больших размерностей // Тр. Ин-та математики и механики УрО РАН. 2012. Т. 18, № 4. С. 224-239.

40. Куклин H.A. Экстремальная функция в задаче Дельсарта оценки сверху контактного числа трехмерного пространства // Тр. Ин-та математики и механики УрО РАН. 2014. Т. 20, № 1. С. 130-141.

В трудах и тезисах конференций:

41. Куклин H.A. Аналитический метод в задаче о контактном числе трехмерного пространства // Проблемы теоретической и прикладной математики: Тезисы 41-й Всероссийской молодежной конференции. Екатеринбург: Институт математики и механики УрО РАН, 2010. С. 159-164.

42. Куклин H.A. Метод Дельсарта в задаче о контактном числе трехмерного пространства // Современные проблемы математики: Тезисы 42-й Всероссийской молодежной школы-конференции. Екатеринбург: Институт математики и механики УрО РАН, 2011. С. 137-138.

43. Куклин H.A. Вид экстремальной функции в задаче Дельсарта // Алгоритмический анализ неустойчивых задач: Тезисы докладов Меж-

дународной конференции, посвященной памяти В.К. Иванова. Екатеринбург: ИММ УрО РАН, 2011. С. 46-47.

44. Куклин H.A. Задача Дельсарта для оценки сверху контактных чисел пространств больших размерностей // Современные проблемы математики: Тезисы Международной (43-й Всероссийской) молодежной школы-конференции. Екатеринбург: Институт математики и механики УрО РАН, 2012. С. 253-255.

45. Куклин H.A. Экстремальные функции в задаче Дельсарта оценки сверху контактных чисел // Материалы международной научной конференции "Современные проблемы математики, механики, информатики". Тула: Изд-во ТулГУ, 2012. С. 54-55.

46. Куклин H.A. Задача Дельсарта для оценки контактного числа пространства R3 // Материалы международной научной конференции "Современные проблемы математики, механики, информатики". Тула: Изд-во ТулГУ, 2013. С. 83-85.

47. Куклин H.A. Задача Дельсарта в трехмерном пространстве // Совре-

менные проблемы математики и ее приложений: труды 45-й Международной молодежной школы-конференции, посвященной 75-летию В.И.Бердышева. Екатеринбург: ИММ УрО РАН, УрФУ, 2014. С. 140142.