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

Куклин, Николай Алексеевич АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Екатеринбург МЕСТО ЗАЩИТЫ
2014 ГОД ЗАЩИТЫ
   
01.01.07 КОД ВАК РФ
Автореферат по математике на тему «Аналитические методы в экстремальных геометрических задачах на евклидовой сфере»
 
Автореферат диссертации на тему "Аналитические методы в экстремальных геометрических задачах на евклидовой сфере"

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

Куклин Николай Алексеевич

АНАЛИТИЧЕСКИЕ МЕТОДЫ В ЭКСТРЕМАЛЬНЫХ ГЕОМЕТРИЧЕСКИХ ЗАДАЧАХ НА ЕВКЛИДОВОЙ СФЕРЕ

01.01.07 — вычислительная математика

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

г ( НОЯ 2014

Екатеринбург — 2014

005556031

Работа выполнена в отделе аппроксимации и приложений Федерального государственного бюджетного учреждения науки «Институт математики и механики имени H.H. Красовского» Уральского отделения Российской академии

доктор физико-математических наук, профессор Арестов Виталий Владимирович.

Горбачев Дмитрий Викторович, доктор физико-математических наук, профессор кафедры прикладной математики и информатики института прикладной математики и компьютерных наук ФБГОУ ВПО «Тульский государственный университет», г. Тула.

Хамисов Олег Валерьевич, доктор физико-математических наук, заведующий отделом прикладной математики №90 Института систем энергетики им. Л. А. Мелентьева СО РАН, г. Иркутск.

ФБГОУ ВПО «Саратовский государственный университет имени Н.Г. Чернышевского».

Защита состоится 24 декабря 2014 года в II00 на заседании диссертационного совета Д 004.006.04 при Институте математики и механики имени H.H. Красовского УрО РАН по адресу: г. Екатеринбург, ул. Софьи Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН и на сайте ИММ УрО РАН: http://wwwrus.imm.uran.ru/Cl6/Diss/default.aspx.

Автореферат разослан ноября 2014 года.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук

наук (ИММ УрО РАН) Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Скарин Владимир Дмитриевич

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

Актуальность темы. В диссертационной работе изучается экстремальная задача для положительно определенных непрерывных на отрезке функций с односторонним ограничением, возникшая из применения схемы Дель-сарта для оценки сверху мощности сферических кодов. Схема Дельсарта появилась в исследованиях Ф. Дельсарта [4,17] границ упаковок в некоторых метрических пространствах. В дальнейшем эта схема была развита и успешно применена в работах Г.А. Кабатянского и В.И. Левенштейна [7], Э. Одлыжко и Н.Слоэна [21], В.И. Левенштейна [9,10], В.М. Сидельникова [12], В.В. Арестова и А.Г. Бабенко [1,2], Д.В. Штрома [15], О.Р. Мусина [11,19, 20]. При применении схемы Дельсарта возникает задача бесконечномерного линейного программирования (которую мы будем называть задачей Дельсарта), ее решение дает оценку сверху мощности сферического кода. Изложение этих результатов и другая родственная, богатая информация имеется в монографии Дж.Конвея и Н.Слоэна [8]. Отметим еще работу В.А.Юдина [16], в которой для изучения достаточно общей задачи минимизации функции фиксированного числа точек на единичной сфере евклидова пространства Rm применяется аналог схемы Дельсарта. Дальнейшие результаты, касающиеся минимизации ньютоновского потенциала конечной системы зарядов на сфере, были получены Н.Н.Андреевым, Г.Коном и Р.Шварцем. Недавно схема Дельсарта была улучшена за счет применения полуопределенного программирования (SDP) в работах К. Башок, Ф. Валлентина, Г. Кона и О.Р. Мусина (см., например, [18]).

Введем скалярное произведение векторов f = (£ь fm)>

т] = (Vi, m, ■■•,Vm) е Rm, тп > 2, по формуле = £7=1 ZjVj- Для вещественного числа s б [-1,1) сферическим s-кодом называется (конечное) множество точек П на единичной сфере пространства R7" такое, что для любых различных точек tj е П выполняется неравенство fr/ ü s. В дальнейшем нас будут интересовать ¿-коды. Обозначим через тт максимальную мощность сферического ¿-кода в размерности тп ^ 2.

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

В двумерном случае задача о нахождении числа тг решается просто: точками ¿-кода являются вершины правильного шестиугольника, вписанного в единичную окружность. Для размерностей тп > 3 точное значение числа тт известно лишь при тп = 3,4,8,24, а именно, т3 = 12 (К.Шютте,

Б.Л.вандерВарден [22], см. также [19]), т4 = 24 (О.Р.Мусин [11,20]), т8 = 240, 7*24 = 196560 (В.И. Левенштейн [9]; Э. Одлыжко, Н. Слоэн [21]); в остальных случаях известны лишь оценки снизу и сверху величины тт, например, 40 < 75 < 44 (верхняя оценка — см. [18]).

Конкретные расположения точек дают оценки снизу числатт (см. [8]). В данной работе оценки снизу величины тт не рассматриваются. Оценку сверху для гт дает подход Дельсарта, который мы сейчас приведем.

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

Определим множество Фт непрерывных на отрезке [—1, 1] функций, пред-ставимых рядами = Тл=о^РкР^^), f е [-1, 1], с суммируемой последовательностью вещественных коэффициентов: 1^*1 <

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

(1) /о = 1;

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

(3) /(¿) < 0 для любых f е [-1, §].

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

ОО

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

Можно рассмотреть более общую задачу типа (1), в которой третье условие f(t) < 0, t е [—1, заменено на /(f) < 0, t е [—1, cos в] для параметра в е (0,7г]. Обозначим значение обобщенной задачи Дельсарта через ит(в). Так же как и для углового расстояния величина ит(в) дает оценку сверху мощности сферического s-кода с угловым расстоянием s = cos в (см., [2, теорема А]).

В 1970 году венгерский математик П. Туран в частной беседе с С.Б. Стечкиным предложил задачу типа обобщенной задачи Дельсарта из предыдущего абзаца для т = 2, в которой условие /(f) < 0 для t е [—1, cos в] заменено на /(f) = 0 для t е [—1, cos в]. Данная задача называется задачей Турана; обозначим значение задачи Турана (т. е. величину типа (1) по только что описанному классу функций) через ит(9). В работе [13] (см. сборник трудов [14]) С.Б. Стечкин рассмотрел задачу Турана для# = где N ^ 2 —це-

4

лое число, нашел экстремальную функцию тах{0, уУ—^ агссоя £} и значение = N. Из последнего равенства следует, что для всех 0 = Щ, N ^ 2, значения задач Турана и Дельсарта при тп = 2 совпадают, а все экстремальные функции задачи Турана являются экстремальными функциями задачи Дельсарта. Позже задачи Турана и Дельсарта при тп = 2 для других в е (0, 7г] рассмотрели Д.В. Горбачев, А.С. Маношина, В.И. Иванов и Ю.Д. Рудомазина в работах [3,5,6]. В итоге был описан класс экстремальных функций в задаче Турана для в е (0, 7г] и установлено совпадение значений ит(в) = и2{в), в е (0, тг].

Отметим, что при тп = 2 существуют экстремальные функции задачи (1), отличные от экстремальных функций задачи Турана. Например, такими функциями являются многочлены + 1)(2£ + 1)2(2£ — 1), + 1)2(2£ + 1)2(2£ - 1), + 1)2(2£ + 1)2(2£ - 1)(4£2 - 104 + И), + 1)(2« + 1)2г2(2£ -1)(8£3 — 8£2 — Ы + 9), а также всевозможные выпуклые комбинации экстремальных функций задачи Турана и перечисленных многочленов. Насколько известно автору, такими комбинациями не исчерпывается весь класс экстремальных функций задачи (1) для тп = 2.

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

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

Во всех перечисленных в предыдущем абзаце случаях была найдена экстремальная функция, а для то ф 8,24 доказано, что она — единственна [1,15]. Во всех случаях последовательность коэффициентов экстремальной

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

Отметим, что при m = 8,24 экстремальная функция не единственна и ситуация очень похожа на ситуацию для m — 2, описанную выше. А именно, в размерности 8 кроме экстремального многочлена y(i + 1)(21 + l)2t2(2t ~ 1) (см. [9,21]) нам известны экстремальные многочлены у (i+l)2(2£+l)2i2(2i—l) и | (t + 1) (2t + l)2t2 (2i - 1) (6t3 - 9t2 + 3é + 80) ; в размерности 24 кроме + l)(2t + l)2(4i + l)2i2(4£ - 1)2(2£ - 1) (см. [9,21]) нам известен экстремальный многочлен ЩЦ + l)2(2i + l)2(4i + l)2i2(4i - 1)2(2£ - 1). Кроме того, очевидно, экстремальными функциями являются всевозможные выпуклые комбинации выписанных многочленов, и, по-видимому, весь класс экстремальных функций не исчерпывается такими комбинациями.

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

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

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

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

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

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

6

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

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

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

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

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

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

& = f Plm\t)dv(t), k> 0.

Jk

Пусть Mm с rca+[—1, есть множество мер ц таких, что > —1 для всех k > 1. Элементы множества Мт будем в дальнейшем называть допустимыми мерами. Двойственная задача Дельсарта состоит в отыскании величины

vm = 1 + sup И = 1 + sup До- (3)

Ч емт lieMm

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

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

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

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

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

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

Во втором параграфе на основе теоремы двойственности получены необходимые и достаточные условия существования экстремального многочлена некоторого определенного вида (теоремы 1.2.1 и 1.2.2 соответственно). Данный результат обобщает результаты работ [1,15] и позволяет восстанавливать экстремальные элементы задач (1) и (3) по информации об экстремальном многочлене.

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

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

С каждым типом (d,N,p,r) свяжем следующие многочлены, зависящие от переменной £, а также формально зависящие от переменных Zq, Z\,... , Zr-i,Bo, Rl, ■•■, Rd-p~2r-2-

C(t) = tr - Zr-ilT1 + ... + (-l)rZo-,

p(t) = tfH-2r-i - Rd-p.2r-2td'p-2r-2 + . ■ • + {—l)d~v~2r~lRa\ ^o(t) = (t + i)pC(i) (i - 1/2) (i - l); f4v

<Pj(t) = V ■ tpo(t), Uj <d-p-r-3; v 1

^(t) = (i + l)4(i)(i-l/2); a(t) = (t + lf Ç4t)(t-1/2) p(t).

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

I ) к> о

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

М+ Ehw Gk(Vi)> 0. 0<j<d-p-r-3;

S -д0 - <т(1) = 0; а/ь = 0, к е N, зависящую от переменных

S,Rq, Ль • • ., J?d_p-2r-2i {GfcJfceW, Zq, Z\,.. .,ZT-\. (6)

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

Если формальным переменным (6) придать конкретные (комплексные) значения, то многочлены (4) становятся многочленами от одной переменной t. При этом многочлен tpo имеет степень р + г + 2. Обозначим его корни через to,ti,... ,tp+r = 1/2, tp+r+i = 1, и с каждым из этих корней U свяжем многочлен cjj(f) = <fio(t) ■ (t —t,)-1 и число

= S ■ ((<*)£+ £ Gt(wj)fc) • (wi(tj))0 < t < p + г + 1.

\ keN '

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

* ¿=0 '

Теорема 1.2.1. Пусть m > 2, ц — экстремальная мера задачи (3) и f — экстремальный многочлен задачи (1) типа (d,N,p,r). Тогда для типа (d,N,p,r) существует решение системы. (5), которое удовлетворяет условиям

(Cl) a(t) « 0, t е [-1,

(С2) справедливы неравенства Эо > 0 и Эк > 0 для всех k > 1; (СЗ) для всех 0 i < р + г выполняется неравенство Li а- 0; (С4) Gk^0 дляке JV; (С5) Gk > 0 <?лл всех к> d;

(Сб) многочлен £ имеет г простых нулей —\<tv<...< ip+1—i < (С7) выполняются равенства S = ит = /(1);

(С8) / = сг/сто;

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

р+г

(i^J^LMU), (7)

«-о

где <5(i) есть дельта-мера Дирака, сосредоточенная в точке t.

Теорема 1.2.2. Пусть тп > 2, (d,N,p,r) — некоторый тип и существует решение системы (5), удовлетворяющее условиям (Cl)~(С6) предыдущей теоремы. Тогда многочлен f = ст/сто имеет тип (d,N,p,r) и является экстремальным в задаче (1), а дискретная мера (7) является экстремальной в задаче (3).

Более того, если выполнены условия (Е1) Эк > 0 для всех 1 ^ к ^ d, к ф N; (Е2) Ь{ > 0 при О ^ % < р + г; (ЕЗ) Gk > О для к е N и к > d;

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

то найденный экстремальный многочлен f является единственной экстремальной функцией задачи (1), а мера fi — единственной экстремальной мерой задачи (3).

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

Теорема 1.3.1. Пусть тп ^ 2,

(1) число В 6 R такое, что ит < В;

(2) / ^ 1 — целое число;

(3) мера и е rca+([-l, j] и {1}) удовлетворяет условиям 9/. > 0 при к > 1, к Ф I и Р; > 1.

Тогда для коэффициента fi экстремальной функции f задачи (1) справедливо неравенство fi < — щ.

Теорема 1.3.3. Пусть

(1) число Лей удовлетворяет условию A si ит;

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

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

(3.1) hk>0 npukTt О,

(3.2) h(t) s£ -1, t e E и h(t) < 0, t e [-1, ±]\.E.

Тогда для экстремальной меры ц задачи (3) справедливо неравенство цЕ < h(l) - Ah0.

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

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

В § 2.2 мы приводим понятие задачи полуопределенного программирования (SDP) и указываем методы сведения некоторых полиномиальных задач

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

В §2.3 мы приводим основные определения и результаты об идеалах в кольцах многочленов и базисах Гребнера. Затем описываем метод решения задачи Дельсарта через теорему 1.2.2. В § 2.4 выписана программа для системы компьютерной алгебры Maple, которая строит базис Гребнера системы (5).

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

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

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

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

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

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

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

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

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

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

Теорема 3.2.1. В размерностях (8) экстремальная функция задачи (1) единственная и является многочленом типа (с1,М,р,г) с параметрами, описанными в таблице:

то d N Р г

147 42 {34,35,36} и {39,40,41} 1 17

157 44 {35,36,37} и {40,41,42,43} 0 18

158 44 {36,37,38} и {41,42,43} 1 18

159 44 {36,37,38} и {41,42,43} 1 18

100 44 {36,37,38} и {41,42,43} 1 18

162 45 {36,37,38,39} и {41,42,43,44} 0 18

163 45 {36,37,38,39} и {41,42,43,44} 0 18

164 45 {36,37,38,39} и {41,42,43,44} 0 18

165 45 {36,37,38,39} и {41,42,43,44} 0 18

167 41 {37,38,39} 0 19

173 47 {38,39,40,41} и {43,44,45,46} 0 19

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

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

Основные результаты

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

2. Дано решение задачи Дельсарта в 11 новых больших размерностях: 147, 157, 158, 159, 160, 162, 163, 164,165,167, 173; найдены экстремальные много-

12

члены и доказана их единственность. Структура полученных экстремальных многочленов отличается от структуры экстремальных многочленов в меньших размерностях 4 ^ тп ^ 146 (ш Ф 8,24). Для исследования использовалось SDP и построение базисов Гребнера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21. 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

32. Куклин H.A. Задача Дельсарта в трехмерном пространстве // Современные проблемы математики и ее приложений: труды 45-й Международной молодежной школы-конференции, посвященной 75-летию В.И.Бердышева. Екатеринбург: ИММ УрО РАН, УрФУ, 2014. С. 140-142.

Подписано в печать 12.11.2014 Формат 60x84 1/16 Бумага офсетная. Усл. печ. л. 0,92 Тираж 100 экз. Заказ № 30181

Отпечатано в типографии ИПЦ УрФУ 620000, Екатеринбург, ул. Тургенева,4