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

московский государственный университет

имени М.В. ЛОМОНОСОВА Механико-математический факультет ' ■г Б ОД

2 3 НОВ 2000

На правах рукописи УДК 514.174+517.5

Андреев Николай Николаевич

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

01.01.01 — математический анализ

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

Москва - 2000

Работа выполнена на кафедре Общих проблем управления механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководители — доктор физико-математических наук,

профессор C.B. Конягин доктор физико-математических наук, профессор В.А. Юдин Официальные оппоненты — доктор физико-математических наук,

старший научный сотрудник В.М. Сидельников

кандидат физико-математических наук доцент Д.В. Горбачев

Ведущая организация — Уральский Государственный

Университет

Защита диссертации состоится 15 декабря 2000 г. в 16 ч. 15 мин. на заседании диссертационного совета Д.053.05.04 при Московском государственном университете им. М.В. Ломоносова по адресу: 119899, ГСП, Москва, Воробьевы горы, МГУ, механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

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

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

BISA.fSi 93 BKf.WfO*

'Т.П. Лукашенко

£/#/.¿3 ûs

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

Актуальность темы. Теория приближения индивидуальных функций берет начало с пионерских работ П.Л. Чебышева второй половины XIX века и до сих пор является мощным инструментом, используемым как при решении задач самой математики, так и прикладных задач. Диссертация посвящена решению старых классических задач дискретной геометрии о расположении точек на сфере с помощью экстремальных задач теории приближения индивидуальных функций с ограничениями на аппарат приближения.

Во многих экстремальных задачах расположения точек на сфере, при решении которых удается воспользоваться методами теории приближений, большую роль имеет понятие дизайна. Конечное множество точек X = {х'*'}^-! С Sm~l С Кт и весов {p/t}£Li называется взвешенным сферическим дизайном порядка q, если кубатурная формула

,/(*)<& = !>/(*<«), X> = 1 (1)

mes Л Js.„-, к=1 к=1

верна для всех алгебраических полиномов /(х) степени не выше q (под степенью монома ха = х"1 • ... • х"™ понимается сумма показателей Q) + ... + ат). Множества являющиеся дизайнами представляют большой интерес, так как кубатурные формулы находят большое применение в вычислительной математике и во многих других областях. Кроме того, дизайны оказываются решением многих задач об экстремальных расположениях точек на сфере. В диссертации рассматривается случай положительных весов: р* >0, к = 1,..., N.

Основная задача состоит в нахождении множеств Л' и весов {p/t}^! для которых выполняется (1). Особый интерес представляют множества Л' содержащие минимальное количество точек, необходимое для выполнения (1). Такие множества называются минимальными взвешенными сферическими дизайнами. Отдельный интерес представляет случай равных весов — кубатурные формулы Чебышевского типа. В этом случае употребляются термины дизайн и минимальный дизайн.

Простейший минимальный сферический дизайн - - две противоположные точки сферы Sm~l являющиеся минимальным дизайном первого порядка. Примерами дизайнов являются вершины правильных многогранников. Так правильный симплекс вписанный в сферу S"'~x — множество из m + 1 точки с равными попарными расстояниями — является минимальным дизайном 2 порядка для любого т. Октаэдр

]

вписанный в сферу (множество точек пересечения 5'"-1 с координатными осями) является минимальным дизайном 3 порядка на сфере любой размерности. Вершины икосаэдра образуют минимальный дизайн порядка 5 на й2. В то же время вершины куба и додекаэдра являясь дизайнами соответственно 3 и 5 порядка не являются минимальными. Все вышеперечисленные минимальные дизайны являются минимальными и в классах взвешенных дизайнов соответствующих порядков. В общей ситуации это не всегда так: минимальный дизайн 5 порядка на 53 с равными весами содержит 24 точки, в то же время существует1 взвешенный дизайн 5 порядка содержащий 23 точки.

Простейшими квадратурными формулами на отрезке — формулой прямоугольника, формулой трапеций, формулой Симпсона — математики пользовались с давних времен. К. Гаусс построил квадратурную формулу на отрезке из N узлов и весов, точную для алгебраических многочленов степени 2Л^ — 1 и доказал, что меньшим количеством узлов обойтись нельзя.

П.Л. Чебышев рассматривал задачу нахождения N узлов квадратурной формулы с равными весами на отрезке, точной для многочленов порядка N. Он в явном виде указал узлы при N = 1,..., 7. Впоследствии, С.Н Бернштейн показал, что такал квадратурная формула возможна лишь для N — I,... ,7, 9.

Дальнейшее развитие математики привело к изучению кубатурных формул на сфере. Интерес к рассматриваемому вопросу в конце XIX века был связан2 с исследованиями по проблеме Варинга, а так же с задачей представления (х{ + ... + х?п)к в виде суммы четных степеней линейных форм от 11,..., хт (в современных терминах — задачей изометрического вложения I™ в Так в 1859 г. Лиувилль нашел (будем использовать современную терминологию) дизайн 5 порядка на Б3. В 1876, 1877 гг. Лукач находит дизайны 5 порядка на 52 и 53. В начале века Гурвиц нашел дизайн 9 порядка на 53. Примерно в это же время А.И. Коркиным, Е.И. Золотаревым, Блихфельдом и рядом других математиков проводились исследования по теории квадратичных форм и решетчатым упаковкам пространств. Впоследствии выяснилось, что минимальные вектора некоторых решеток являются хорошими сферическими дизайнами. В середине XX века интерес к

1 Hardin R.H., Sloane N.J.A. Expressing (a2 + b2 + c? + d2)3 as a sum of 23 sixth powers // J. of Combinatorial Theory, Ser. A. 1994. V. 68. P. 481-485.

2Reznich B. Sums of even powers of real linear forms // Mem. AMS. 1992. V. 95, № 463.

дизайнам снова возрос. В 1948 г. В.А. Диткин доказали, что вершины икосаэдра являются дизайном 5 порядка на S3. Многочисленные исследования по конструированию дизайнов на основе орбитных кодов принадлежат С.Л. Соболеву и его ученикам.

Оценкам снизу мощности минимальных сферических дизайнов посвящено много работ. Бурное развитие эта тематика получила после работы Ф. Дельсарта, Дж. Гетелса, Я. Зейделя3 в которой они начали использовать методы анализа для решения задач дискретной геометрии; ввели термин "дизайн" и получили оценку снизу мощности сферического дизайна с равными весами. Эта оценка дала возможность доказать минимальность дизайнов, образованных вершинами октаэдра, вершинами икосаэдра, решеткой Лича и еще ряда других известных дизайнов. Однако в целом эта оценка оказалась4 плохой — она может быть точна лишь на небольшом количестве дизайнов. Возникшие новые методы получения оценок снизу мощности сферических дизайнов стали использовать свойство положительной определенности специальных функций. Затем эта тематика получила развитие в ряде работ, среди которых следует отметить работы Н. Слоэна, А. Одлыжко, Ф. Дельсарта, Дж. Гетелса, Я. Зейделя, В.И. Левенштейна, В.М. Сидельникопа, В.А. Юдина. Основная идея, принадлежащая Ф. Дельсарту, состоит в использовании многочленов Гегенбауэра и их свойства положительной определенности.

За последние годы доказана минимальность лишь нескольких дизайнов5. Задача нахождения минимального дизайна 11 порядка на S3 рассматривалась несколькими авторами. Из общей оценки работы Дельсарта-Гетелся-Зейделя следует, что мощность дизайна 11 порядка на S3 не меньше 112. В работе В.А. Юдина6 приведена общая оценка, из которой следует, что мощность минимального дизайна 11 порядка на S3 не меньше 117. Такая же оценка получена в работе болгарских математиков7. В пункте 1.3 доказывается, что минимальный сферический

sDelsarte P., Goelhals J.M., Seidel J.J. Spherical codes and designs // Geometriae Dedicata. 1977. V. 6. P. 363-388.

4Bannai R, Dumerell R.M. Tight spherical designs. 1. // J. Math. Soc. Japan. 1979. V. 31. P. 199-207.

Bannai E., Damerell Ü.M. Tight spherical designs. II. // J. London math. Soc. 1980. V. 21. P. 13-30.

5Seidel J.J. Isometric embeddings and geometric designs // Discrete Math. 1994. V. 136. P. 281-293.

6IOf)uH В.Л. Нижние оценки для сферических дизайнов // Известия РАН. Сер. мат. 1997. Т. 61, № 3. С. 213-223.

7 Nikova S., Boyvalenkov P. Improvements of the lower bounds of the size of some

дизайн 11 порядка на S3 содержит 120 точек.

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

Конечное подмножество точек X — {х^}]^ С 5m_1 называется сферическим т-кодом, если

х^х^' ^ т для всех 1 ^ г, j, <С N, г ф j.

Действительно, если известно, что при передаче точки х^ искажения не слишком велики и принятая точка г'*'' всегда удовлетворяет условию х^'х'^' > г/2 зная сам код — набор точек со сферы, которые могли быть переданы — всегда можно однозначно восстановить передававшуюся информацию. Желание передавать максимально большой объем информации приводит к задаче нахождения сферических кодов, содержащих максимально возможное число точек при заданных тп и г.

Использование свойств ортогональных многочленов в задачах кодирования было начато Ф. Дельсартом. Для оценок мощности кодов из пространства Хемминга (вершины единичного m-мерного куба) использовалось свойство положительной определенности многочленов Кравчука. Задача, первоначально поставленная для многочленов, разлагающихся с положительными коэффициентами по многочленам Гегенбауэра, получила развитие в работах Г.А. Кабатянского, В.И. Левенштейна, В.М. Сидельникова, А. Одлыжко, Н. Слоэна8.

На этом пути были получены принципиально новые оценки плотности упаковки шаров в евклидовом пространстве.

spherical designs // Mathematika Balkanica, в печати.

&Delsarte Ph. Bounds for unrestricted codes, by linear programing // Philips Res. Rep. 1972. V. 2. P. 272-289.

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

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

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

Odlyzko A.M., Sloane N.J.A., New bounds on the number of unit spheres that can touch a unit sphere in n dimensions // J. Comb. Theory. A. 2G. 1979. P. 210-214.

На основе использования свойств многочленов Гегенбауэра в пункте 2.2 показано, что при m = 4 максимальный сферический cos(7r/5)-KOfl содержит 120 точек.

Глава 3 посвящена задаче об энергии и сходной с ней задачам. Рассматриваются задачи о нахождении величин

N 1

IV(771, TV) = inf У" m-гл—(2)

i.j=i * 1 ■ ¿i

N

S(m, TV) = sup Y* |zW (3)

N

P(m,N)= sup TT |x(i)-x(j)|. (4)

.7:(l),...,I<W>6Sm-1 ¡., = 1

Наилучшие, в смысле минимума потенциальной энергии системы, расположения зарядов на отрезке были найдены Г. Сегё9. Им было показано, что если в концах отрезка [—1,1] помещено два положительных заряда, то TV единичных зарядов на [—1,1] расположенных в нулях многочлена Якоби (с параметрами определяемыми по зарядам, расположенным на концах отрезка) доставляют минимум потенциальной энергии рассмотренной системы.

Задача о нахождении величины W(m, TV) является обобщением классической проблемы расположения зарядов на сфере в трехмерном пространстве с минимальной потенциальной энергией. В начале века английский физик Дж.Дж. Томсон проводил10 эксперимент по нахождению наилучших расположений небольших количеств зарядов на сфере трехмерного пространства. При TV = 4, G, 12 эксперименты приводили к классическим конфигурациям: тетраэдру, октаэдру и икосаэдру. Аналогичная задача, о нахождении расположения точек с минимальной энергией в дискретных пространствах, была поставлена C.B. Яблонским. Случай суммы попарных расстояний S(d, TV) был рассмотрен Л.Ф. Тотом11. Задача о произведении, связанная с проблемой Фекете о расположении, максимизирующем определитель Вандермонда, TV точек

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

10 Whyte L.L. Unique arrangements of points on a sphere // The Amer. Math. Monthly. 1952. V. 59, N< 9. P. 60G-611.

11 Тот Л.Ф. Расположения на плоскости, па сфере и п пространстве. — М.: Физматлит. 1958.

в заданной области, появилась в начале XX века. В настоящее время, она нашла применение в теории сложности.

Решение этих классических задач было известно лишь в следующих случаях, причем экстремальные конфигурации одинаковы для всех трех задач: тп = 2, N — произвольное; т — произвольное, N = т + 1; т — произвольное, N — 2т; т = 8, N = 240. Доказательство последних двух случаев стало возможным лишь после привлечения техники экстремальных задач теории приближения. Отталкиваясь от экстремальных задач применяемых в теории кодирования, в связи с задачей об энергии, В.А. Юдин рассмотрел12 задачу приближения функции 1 /{2(1 — ¿)}('п-2)/2 снизу на отрезке [—1,1] в метрике Ь\ с весом (1 — £2)(т~3)/2 конусом положительно определенных функций. Им было показано, что величина уклонения в этой задаче участвует в оценке снизу функионала энергии.

Оценки с другой стороны во всех трех задачах доставляют хорошо известные конфигурации точек на сфере.

Решая экстремальную задачу поставленную В.А. Юдиным для т = 3, N = 12; то = 4, N = 120; т = 24, N = 196560 и сходные с ней экстремальные задачи теории функций в главе 3 получено решение задач об энергии, сумме и произведении в указанных случаях.

Цель работы. Решить задачу о минимальном дизайне 11 порядка на 53 и задачу о максимальном соз(7г/5)-коде на 53. Привести новые точные решения задачи об энергии, сумме и произведении.

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

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

1. Доказано, что минимальный взвешенный дизайн 11 порядка на 53 содержит 120 точек и экстремальным является дизайн с равными весами.

2. Доказано, что максимальный сферический соя(7г/5)-код на 53 содержит 120 то^ек.

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

3. Решена задача о нахождении расположения N одинаковых зарядов на 5"1_| минимизирующем потенциальную энергию системы в случаях: т. = 3, N = 12; т = 4, N = 120; т = 24, N = 190560. В этих же случаях решены задачи о максимизации суммы и произведения попарных расстояний N точек, расположенных на 5т_|.

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

Апробация диссертации. Результаты диссертации докладывались на Саратовской Зимней школе по теории функций (Саратов, 1996; Саратов, 1998; Саратов, 2000); Летней школе по теории функций памяти С.Б. Стечкина (Миасс, 1996 г.; Миасс, 1997 г.; Миасс, 1998 г.); на конференции по теории функций посвященной памяти С.Б. Стечкина (Екатеринбург, 2000); на конференции по приближению функций многих переменных (Германия, 2000); на семинаре по теории приближений в МИР АН (под руководством С. А. Теляковского).

Публикации. Результаты диссертации опубликованы в пяти работах, список которых приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения и трех глав. Текст диссертации изложен на 41 странице. Список литературы содержит 33 наименования.

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

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

Глава 1. Первая глава диссертации посвящена оценкам снизу мощности дизайнов. Пусть 5т_1 = {(х! ,х2, • • • ,хт) € К™ | х2 + х\ + ... + х2, = 1} —• единичная сфера в т,-мерном евклидовом пространстве;

для 2,2/6 Кт через ху обозначим скалярное произведение векторов; |х| = %/хх.

Определение. Конечное множество точек А' = С £,'"~1 и

весов {р^называется взвешенным сферическим дизайном порядка д, если кубатурная формула

,/(*)«** = Х>/(*(4)), £> = 1 (5)

верна для всех алгебраических полиномов /(х) степени не выше q (под степенью монома ха — • ... • хпонимается сумма показателей «1 + • • • + ост).

Задача состоит в нахождении множеств X и весов для ко-

торых выполняется (5). Множества X, содержащие минимальное количество точек, необходимые для выполнения (5) называются минимальными взвешенными сферическими дизайнами. В случае равных весов употребляются термины дизайн и минимальный дизайн. Мощность (количество точек) минимального взвешенного дизайна порядка q на 5т_1 обозначим через М{т,д), мощность минимального дизайна порядка д с равными весами ■— М*(т,д); очевидно А^*(т,д) ^ ^(тп,^).

Через

о обозначим многочлены Гегенбауэра — систему ортогональных многочленов на отрезке [—1,1] с весом (1 — ¿2)<т_3)/2) нормированных условием С1т'(1) = 1. В геометрических задачах используется положительная определенность многочленов Гегенбауэра13: для любого конечного множества точек ж'1', ... из 5"1-1, любого и 6 N и любых £ 1,..., € С справедливо неравенство

¿с!г)(*(кУп)Ьй> о. к,1=1

В терминах многочленов Гегенбауэра можно дать эквивалентное (5) определение понятия дизайна.

Определение. Взвешенным дизайном порядка д называется конечное множества точек X = С 5'"-1 и весов {р*}^, Лк=1 Рь ~ Для которого справедливы равенства N

£ С<т>(А<'>= 0 для и =1,2,...,д. к,1=1

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

Наряду со взвешенными дизайнами порядка q рассматриваемыми выше, рассматривается понятие D-дизайна, по-видимому введенное Ф. Дельсартом.

Определение. Множество точек X = {х(А,}^=1 с 5m_1 и весов {p*}b=ii Tlfk^xPk — 1 называется взвешенным £>-дизайном, где D С N есть подмножество натурального ряда, если справедливы равенства N

J2 G[m){x(k)x(l))pkpi =0 для v € D. к,1=1

При D = {1,2,...,<7} это определение совпадает с понятием классического взвешенного дизайна порядка q. Многие дизайны порядка q являются D-дизайнами для более широкого чем {1, 2,..., 9} множества D. Интересным является £>-множество 120 вершин правильного многогранника в®'с символом Шлефли {3,3,5}. Эта конфигурация состоящая из

8 точек вида (±1,0,0,0), (0,±1,0,0), (0,0,±1,0), (0,0,0,±1);

16 точек вида (±1/2, ±1/2, ±1/2, ±1/2);

96 точек полученных четными перестановками координат

из 8 точек вида (±(\/5 + 1)/4, ±1/2, ±(\/5 - 1)/4,0);

обладает многочисленными замечательными свойствами и мы обозначим ее ОТ. Как известно14 множество ОТ является дизайном 11 порядка. На самом деле ОТ является Dwrhзайном для множества

D<xn = {все нечетные натуральные числа} U

U {2,4,6,8,10,14,16,18,22, 26,28,34,38,46,58}.

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

На классе непрерывных на отрезке [—1,1] функций f(t) удовлетворяющих условиям:

1. /(f) ^ 0, -l^i^l, /(1)>0; 2- fit) = I, /„ ^ 0 при 2/ > 12;

найти величину

«Ф™. ,6,

/о

14 Салихов Г.Н. Кубатурные формулы для гиперсферы, инвариантные относительно группы правильного GOO-гранника // Доклады ЛИ СХ'СР. 1975. Т. 223, № 5. С. 1075-1078.

Найдены экстремальные многочлены 17 порядка. Из общей оценки мощности дизайна, приведенной в пункте 1.2 следует, что решение этой экстремальной задачи дает оценку снизу мощности сферического дизайна 11 порядка на S3.

На основе решения задачи (6) в пункте 1.3 доказывается следующая теорема.

Теорема. Пусть множество X — С S3 есть минималь-

ный взвешенный дизайн порядка 11 с положительными весами. Тогда

N = N( 4,11) = N'(4,11) = 120.

Глава 2. В этой главе диссертации рассматривается задача о сферическом коде. Конечное подмножество точек X = С 5m_1 называется сферическим т-ко дом, если

х^х^ ^ т для всех 1 ^ i,j, ^ N, i ф j.

Задача состоит в отыскании множеств Л", содержащих наибольшее возможное количество точек при заданных т и т.

Пусть АС(т,т) есть класс непрерывных на [-1,1] функций f(t) удовлетворяющих условиям: 1. f(t) < 0 при t 6 [—1,т];

2- /(«) = 0 U Gim)(0- /о > 0, 0 для всех * е N. Рассмотрим величину

K(m, т) = inf

/е/С(т,т) fQ

Эта величина дает оценку сверху мощности сферичечкого т-кода на 5т~К

В пункте 2.2 показано, что K(4,cos(n/5)) ^ 120. Указано семейство экстремальных многочленов 17 порядка.

Вследствии того, что сферическая конфигурация ЯЛ содержит 120 точек и является соз(7г/5)-кодом, доказана следующая теорема.

Теорема. Максимальный соэ(тт/5)-код на S3 содержит 120 точек.

Глава 3. В третьей главе рассматривается задача об энергии (2) и сходные с ней задачи (3), (4). Рассмотрим следующую экстремальную задачу поставленную В.А. Юдиным.

На классе У(т) непрерывных на отрезке [—1,1] функций f[t) удовлетворяющих условиям:

1. m ^ i/{2(i-0}(,n-2)/2, -i^Î^I;

2. ДО = о Su Gim\t), Û^o для всех и e N;

найти величину

Y(m,N)= sup {N2f0-Nf(l)}.

fÇy(m)

Эта величина оценивает функционал энергии (2) снизу:

W{m,N) Z Y (m, N).

Аналогичные экстремальные задачи могут быть рассмотрены и в связи с задачами (3), (4).

На классе Т(т) непрерывных на отрезке [—1,1] функций ДО, удовлетворяющих условиям:

1. ДО > >/2(1-0, -1 < t < 1;

2. ДО = EZo I GÎm\t), fu^O для всех и G N; найти величину

Т(т, N) = inf {N2 Jo - N f(l)}. /ет(т)

В пункте 3.1.2 показано, что эта величина оценивает S{m, N) сверху:

S(m,N) ^ T{m,N).

Рассматривая класс Л(т) непрерывных на отрезке [—1,1] функций /(£), удовлетворяющих условиям:

1. ДО ^111^/2(1-0- -l^i^l;

2- /(0 = ЕГ=о f" GÎm)(t), /„ ^ 0 для всех i/fN; и величину

A(m,N) = inf {yV2/0 -Nf(l)}.

/£-A(m)

в пункте 3.1.3 получается оценка

P(m,N) ¡С А(т, N).

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

Теорема. Пусть т = 3 и N — 12. Тогда

1У(3,12) = 6 + 30\Д + 2\/5, 5(3,12) = 24 + 24\] 25 + 10>/5,

П132

т12) = -рои экстремальной сферической конфигурацией являются вершины икосаэдра.

Теорема. Пусть т = 4 и N = 120. Тогда И'(4,120) = 10790,

5(4,120) = 240(11 + 15л/2 + 10\/3 + + 6^5 + 2уД>) ,

Р(4,120) = 21920 • З1200 • 5720

и экстремальной является сферическая конфигурация 9Л. Теорема. Пусть т - 24, N = 196560. Тогда

= 211621330216387662351781

V Ч, »иоии; 207360000000000

5(24,196560) = 393120 х

х (2301 + 46575\/2 + 2300\/3 + 11776\/б 4- 11776\Л0),

/о25852 523552 \ 106-560

Р(24,196560) — ^-

и экстремальной конфигурацией являются минимальные вектора решетки Лича.

Благодарности. Я выражаю благодарность Владимиру Александровичу Юдину за постоянное внимание и многочисленные обсуждения, а так же Сергею Владимировичу Конягину за внимание к работе. Я выражаю благодарность Мише Фейгину и всем друзьям за дружбу и поддержку.

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

[1] Andrr.cv N.N., Yudin V.A. Problems of Approximation Theory in Discrete Geometry // Mathematical Research. 1999. V. 107 (Advances in Multivariate Appr.), P. 19-32.

В этой работе автору принадлежит решение задачи о максимальном сферическом соз(7г/5)-коде и решение задачи об энергии в случае решетки Лича.

[2] Andreev N.N. An extremal property oh the icosahedron // East Journal on Approximations 1996. V. 2, N. 4, pp. 459-462.

[3] Андреев Н.Н. Расположение точек на сфере с минимальной энергией // Труды МИРАН. 1997. Т. 219. С. 27-31.

[4] Андреев Н.Н. Минимальный дизайн 11 порядка на трехмерной сфере // Матем. заметки. 2000. Т. 67, № 4. С. 489-497.

[5] Андреев Н.Н. Один сферический код // Успехи матем. наук. 1999. Т. 54, Л'« 1. С. 255-256.

Введение

1. Задача о минимальном дизайне

1.1. Многочлены Гегенбауэра и дизайны

1.2. Оценка снизу мощности D-дизайна.

1.3. Минимальный дизайн 11 порядка на 53.

2. Задача о максимальном сферическом коде

2.1. Оценка сверху мощности т-кода.

2.2. Максимальный (cos f )-код на S3.

3. Задача об энергии, произведении и сумме

3.1. Оценка общего случая.

3.1.1. Задача об энергии.

3.1.2. Задача о сумме.

3.1.3. Задача о произведении.

3.2. Интерполяционные многочлены Эрмита.

3.3. Случай 12 точек на икосаэдр

3.4. Случай 120 точек на S3: сферическая конфигурация Ш

3.5. Случай 196560 точек на S23: решетка Лича.

Теория приближения индивидуальных функций берет начало с пионерских работ П.Л. Чебышева второй половины XIX века и до сих пор является мощным инструментом, используемым как при решении задач самой математики, так и прикладных задач. Диссертация посвящена решению старых классических задач дискретной геометрии о расположении точек на сфере с помощью экстремальных задач теории приближения индивидуальных функций с ограничениями на аппарат приближения.

Во многих экстремальных задачах расположения точек на сфере, при решении которых удается воспользоваться методами теории приближений, большую роль имеет понятие дизайна. Конечное множество точек X = С 5т1 С Мт и весов {рк}^=\ называется взвешенным сферическим дизайном порядка д, если кубатурная формула верна для всех алгебраических полиномов /(ж) степени не выше д (под степенью монома ха = ж"1 • . • хпонимается сумма показателей а\ + . + ат). Множества являющиеся дизайнами представляют большой интерес, так как кубатурные формулы находят большое применение в вычислительной математике и во многих других областях. Кроме того, дизайны оказываются решением многих задач об экстремальных расположениях точек на сфере. В диссертации рассматривается случай положительных весов: р^> 0, к = 1,. ^ N.

Основная задача состоит в нахождении множеств X и весов {рк}^=\ для которых выполняется (1). Особый интерес представляют множества X содержащие минимальное количество точек, необходимое для

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

Простейший минимальный сферический дизайн — две противоположные точки сферы 5т1 являющиеся минимальным дизайном первого порядка. Примерами дизайнов являются вершины правильных многогранников. Так правильный симплекс вписанный в сферу 5т1 (множество из т + 1 точки с равными попарными расстояниями, рис. 1) является минимальным дизайном 2 порядка для любого га. Октаэдр вписанный в сферу (множество точек пересечения б™-1 с координатными осями, рис. 2) является минимальным дизайном 3 порядка на сфере любой размерности. Вершины икосаэдра (рис. 3) образуют минимальный дизайн порядка 5 на 52. В то же время вершины куба и додекаэдра являясь дизайнами соответственно 3 и 5 порядка не являются минимальными. Все вышеперечисленные минимальные дизайны являются минимальными и в классах взвешенных дизайнов соответствующих порядков. В общей ситуации это не всегда так: минимальный дизайн 5 порядка на 53 с равными весами содержит 24 точки, в то же время существует [1] взвешенный дизайн 5 порядка содержащий 23 точки.

Простейшими квадратурными формулами на отрезке — формулой прямоугольника, формулой трапеций, формулой Симпсона — математики пользовались с давних времен. К. Гаусс построил квадратурную формулу на отрезке из N узлов и весов, точную для алгебраических многочленов степени 2N — 1 и доказал, что меньшим количеством узлов обойтись нельзя.

П.Л. Чебышев рассматривал задачу нахождения N узлов квадратурной формулы с равными весами на отрезке, точной для алгебраических многочленов порядка N. Он в явном виде указал узлы при N = 1,. ,7. Впоследствии, С.Н Бернштейн показал, что такая квадратурная формула возможна лишь для N = 1,., 7, 9.

Дальнейшее развитие математики привело к изучению кубатурных формул на сфере. Интерес к рассматриваемому вопросу в конце XIX века был связан (см. [2]) с исследованиями по проблеме Варинга, а так же с задачей представления (xf + . + в виде суммы четных степеней линейных форм от Xi,. ,хт (в современных терминах — задачей изометрического вложения в ^/г)- Так в 1859 г. Лиувилль нашел (будем использовать современную терминологию) дизайн 5 порядка на 53. В 1876, 1877 гг. Лукач находит дизайны 5 порядка на S2 и S3. В начале века Гурвиц нашел дизайн 8 порядка на 53. Примерно в это же время А.И. Коркиным, Е.И. Золотаревым, Блихфельдом и рядом других математиков проводились исследования по теории квадратичных форм и решетчатым упаковкам пространств. Впоследствии выяснилось, что минимальные вектора некоторых решеток являются хорошими сферическими дизайнами. В середине XX века интерес к дизайнам снова возрос. В 1948 г. В.А. Диткин доказал, что вершины икосаэдра являются дизайном 5 порядка на S3. Многочисленные исследования по конструированию дизайнов на основе орбитных кодов принадлежат С.Л. Соболеву (см. [3]) и его ученикам.

Количество точек минимального взвешенного дизайна порядка q на 5m1 будем обозначать N(m,q), а минимального дизайна с равными весами — 7V*(m, g); очевидно N*(m, q) ^ N(m, q). Оценкам снизу мощности минимальных сферических дизайнов посвящено много работ. Бурное развитие эта тематика получила после работы Ф. Дельсарта, Дж. Гетелса, Я. Зейделя [4] в которой они начали использовать методы анализа для решения задач дискретной геометрии; ввели термин "дизайн" и получили оценку снизу мощности сферического дизайна с равными весами /т + «-1\/т + «-2\

V т - 1 )

Оценка (2) дала возможность доказать минимальность дизайнов, образованных вершинами октаэдра, вершинами икосаэдра, решеткой Лича и еще ряда других известных дизайнов. Однако в целом эта оценка оказалась [5] плохой — она может быть точна лишь на небольшом количестве дизайнов. Возникшие новые методы получения оценок снизу мощности сферических дизайнов стали использовать свойство положительной определенности специальных функций в задаче оценки мощности сферических дизайнов. Затем эта тематика получила развитие в ряде работ, среди которых следует отметить работы Н. Слоэна, А. Одлыжко, Ф. Дельсарта, Дж. Гетелса, Я. Зейделя, В.И. Левенштейна, В.М. Сидельникова, В.А. Юдина. Основная идея, принадлежащая Ф. Дельсарту, состоит в использовании многочленов Гегенбауэра — многочленов, ортогональных на отрезке

1,1] с весом (1 — ¿2)(т~3)/2 (см. пункт 1.1) и их свойства положительной определенности ([6, стр. 318]): для любого конечного множества точек . из 5т1, любого и £ N и любых £1,., £лг Е С справедливо неравенство N

0. (3) к,1=1

Определение дизайна может быть переписано в следующем, эквивалентном, виде: взвешенный дизайн порядка q есть множество точек X = С /6>т1 и весов {рк}к=1^ Для которого справедливы равенства N 0 для 1/ = 1,2,.,д. к,1=1

Такая запись дает возможность ввести новое определение Б-дизайна, по-видимому возникшее у Ф. Дельсарта (см. [7]). Множество точек X = С и весов {рк}к=1 называется взвешенным

-дизайном, где Б С N есть подмножество натурального ряда, если справедливы равенства N

YJGtn)(x^x^)pkpl = 0 для и еИ. к,1=1

При В = {1, 2,.,д} это определение совпадает с классическим определением взвешенного дизайна порядка д. Многие дизайны порядка д являются В-дизайнами для более широкого чем {1, 2,., д} множества И и этот факт иногда оказывается важным при оценке мощности дизайнов и в других вопросах.

Интересным является ^-множество 120 вершин правильного многогранника в Ж4 с символом Шлефли {3,3,5} [8, с. 494]. Эта конфигурация состоящая из

8 точек вида (±1,0,0,0), (0, ±1,0,0), (0,0, ±1,0), (0,0,0,±1);

16 точек вида (±1/2, ±1/2, ±1/2, ±1/2);

96 точек полученных четными перестановками координат из 8 точек вида (±(>/5 ± 1)/4, ±1/2, ±(\/б - 1)/4, 0); обладает многочисленными замечательными свойствами и мы обозначим ее ЯЯ. Как было показано в [9] множество Ш является дизайном 11 порядка. На самом деле ЭДТ является (см. [29]) Дщ-дизайном для множества

От — {все нечетные натуральные числа}и и {2,4,6,8,10,14,16,18, 22, 26,28, 34,38,46,58}.

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

На классе непрерывных на отрезке [—1,1] функций /(¿) удовлетворяющих условиям:

1. /№^0, /(1)>0;

2- /(*) = Е,евт % ^ (*), 0 приг/> 12; найти величину вирДЯ (5) о

Найдены экстремальные многочлены 17 порядка.

Из общей оценки мощности дизайна, приведенной в пункте 1.2 следует, что решение этой экстремальной задачи дает оценку снизу мощности сферического дизайна 11 порядка на 53. За последние годы доказана минимальность лишь нескольких дизайнов (см. обзор [10], и работу [1]). Задача нахождения минимального дизайна 11 порядка на 53 рассматривалась несколькими авторами. Из общей оценки работы [4] следует, что мощность дизайна 11 порядка на 53 не меньше 112. В работе [11] приведена общая оценка, из которой следует, что мощность минимального дизайна 11 порядка на 53 не меньше 117. Такая же оценка получена в [12].

На основе решения задачи (5) в пункте 1.3 доказывается, что минимальный сферический дизайн 11 порядка на 5'3 содержит 120 точек.

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

Конечное подмножество точек X = С 5т1 называется сферическим г-ко дом, если х^х^ ^ т для всех 1 ^ г, у, ^ N. г ф у.

Действительно, если известно, что при передаче точки х^ искажения не слишком велики и принятая точка х^' всегда удовлетворяет условию х^х^' > > т/2 зная сам код — набор точек со сферы, которые могли быть переданы — всегда можно однозначно восстановить передававшуюся информацию. Желание передавать максимально большой объем информации приводит к задаче нахождения сферических кодов, содержащих максимально возможное число точек при заданных тит.

При т = 1/2 это знаменитая задача о контактном числе шаров, возникшая задолго до появления сферических кодов, исправляющих ошибки: сколько шаров одинакового радиуса в пространстве Жт могут касаться одного фиксированного шара того же радиуса. Решение задачи о контактном числе известно только при т = 2, 3, 8, 24 [6, с. 45]. При т — 2 решение тривиально. Случай га = 3 был предметом знаменитой дискуссии И. Ньютона и Д. Грегори 1649 г. Гипотеза И. Ньютона (12 шаров) была доказана лишь в конце XIX века (см. [6]). В размерностях 8 и 24 решение задачи, полученное В.И. Левенштейном и одновременно А. Одлыжко и Н. Слоэном, было основано на использовании экстремальных задач теории функций.

Использование свойств ортогональных многочленов в задачах кодирования было начато Ф. Дельсартом. Для оценок мощности кодов из пространства Хемминга (вершины единичного т-мерного куба) использовалось свойство положительной определенности многочленов Кравчука — аналог свойства (3) многочленов Гегенбауэра. Задача, первоначально поставленная для многочленов, разлагающихся с положительными коэффициентами по многочленам Гегенбауэра, получила развитие в работах Г.А. Кабатянского, В.И. Левенштейна, В.М. Сидельникова, А. Одлыжко, Н. Слоэна [13, 14, 15, 16, 17].

На этом пути были получены принципиально новые оценки плотности упаковки шаров в евклидовом пространстве.

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

Пусть /С(т, т) есть класс непрерывных на [-1,1] функций удовлетворяющих условиям:

1. /(*) ^Опри* €[-1,т];

2- /М - % То > 0, 0 для всех

Найти величину

К(т,т)= и* (6)

С(ш,г)

Эта величина дает (см. пункт 2.1) оценку сверху мощности сферического т-кода на Экстремальные функции являются наилучшим приближением снизу ступенчатой функции, равной 0 на [—1, г] и положительной константе на (т, 1], классом /С(т,г) в метрике L\ с весом (1 ¿2)(т-3)/2

В пункте 2.2 задача (6) решена для т — 4 и г = cos |. Найдены многочлены 17 степени, являющиеся экстремальными в этой задаче при рассматриваемых значениях параметров.

На основе решения этой задачи в п. 2.2 показано (см., также [33]), что при т — 4 максимальный сферический (cos |)-код содержит 120 точек.

Глава 3 посвящена задаче об энергии и сходной с ней задачам. Для N точек {а^}^! С Sm~l введем функционалы N

VF(m, N, х

S(m,N,x{1\. Ы0 - хЩ

J=1 1 1 N т-2

Xх 1 гфд N гф]

Рассмотрим задачи о нахождении величин

W{m, N) = inf W(m, iV, x

S(m,N)= sup S{m,N,x^\.,xiN)), (8)

P{m,N)= sup P(m,iV,z(1),.,z(Ar)). (9)

Наилучшие, в смысле минимума потенциальной энергии системы, расположения зарядов на отрезке были найдены Г. Сегё [18, с. 149]. Им было показано, что если в концах отрезка [—1,1] помещено два положительных заряда, то N единичных зарядов на [—1,1] расположенных в нулях многочлена Якоби (с параметрами определяемыми по зарядам, расположенным на концах отрезка) доставляют минимум потенциальной энергии рассмотренной системы.

Задача (7) о нахождении величины W(m, N) является обобщением классической проблемы расположения зарядов на сфере в трехмерном пространстве. В начале века английский физик Дж.Дж. Томсон проводил [19] эксперимент по нахождению наилучших расположений небольших количеств зарядов на сфере трехмерного пространства. При N = 4,6,12 эксперименты приводили к классическим конфигурациям: тетраэдру, октаэдру и икосаэдру. Аналогичная задача, о нахождении расположения точек с минимальной энергией в дискретных пространствах, была поставлена C.B. Яблонским (см. [20]). Случай (8) суммы попарных расстояний S(d, N) был рассмотрен Л.Ф. Тотом в [21, гл. 5]. Задача (9) о произведении, связанная с проблемой Фекете о расположении, максимизирующем определитель Вандермонда, N точек в заданной области, появилась в начале XX века (см. [22]). В настоящее время, она нашла применение в теории сложности.

Решение этих классических задач было известно лишь в следующих случаях, причем экстремальные конфигурации одинаковы для всех трех задач. m = 2, N — любое (считается, что W(2, N, ., х^) — = iïj ln ~ Экстремальная конфигурация — вершины правильного iV-угольника. Решение задачи об энергии и произведении в этом случае приведено в [23]. m — произвольное, N = 2, 3 — тривиально. Экстремальные конфигурации — две противоположные точки сферы и вершины правильного треугольника, вписанного в большую окружность сферы соответственно. m — произвольное, N = т+1. Экстремальная конфигурация — вершины симплекса вписанного в сферу. Этот случай, как и предыдущий, несложно доказывается с помощью неравенств о средних гармоническом, геометрическом, арифметическом и квадратичном. m — произвольное, N = 2т. Экстремальная конфигурация — вершины октаэдра, вписанного в единичную сферу (см. [24]). m = 8, N = 240. Экстремальная конфигурация — концы минимальных векторов решетки Коркина-Золотарева (в [25] доказательство приведено только для энергии, случаи суммы и произведения делается аналогично).

Доказательство последних двух случаев стало возможным лишь после привлечения техники экстремальных задач теории приближения. Отталкиваясь от экстремальных задач применяемых в теории кодирования, рассмотренных выше, в связи с задачей об энергии В.А. Юдин рассмотрел задачу приближения функции 1/{2(1 — ¿)}(т2)/2 снизу на отрезке [—1,1] в метрике Li с весом (1 — ¿2)(т~3)/2 конусом положительно определенных функций.

На классе У{т) непрерывных на отрезке [—1,1] функций f(t) удовлетворяющих условиям:

1. f(t) ^ 1/{2(1 - 1)Ут~2У2, -1 < t < 1;

2- № = I I > 0 для всех г/ G N; найти величину

Y(m, N) = sup {N2f0-Nf(l)}. (10) fey(m)

Эта величина оценивает функционал энергии снизу (см. пункт 3.1.1):

W(m,N) > Y(m,N).

Именно на этом пути основывалось нахождение величин W(m, 2m), W{8,240) [25, 26]. При решении экстремальной задачи (10) для проверки условия 1 класса У(т) стали использоваться свойства интерполяционных многочленов Эрмита.

Сходные с (10) экстремальные задачи могут быть рассмотрены (см. пункты 3.1.2 и 3.1.3) и для оценок сверху величин (8), (9).

Оценки с другой стороны во всех трех задачах доставляют хорошо известные конфигурации точек на сфере.

Решая экстремальную задачу (10) для m = 3,iV = 12;m = 4, N — = 120; m = 24, N = 196560 и сходные с ней экстремальные задачи теории функций в главе 3 мы получим решения задач об энергии, сумме и произведении в следующих случаях. т = 3, N = 12. Экстремальная конфигурация есть вершины правильного икосаэдра, вписанного в сферу (см. [30]). т = 4, N = 120. Экстремальной является сферическая конфигурация Ш (см. [32]). га = 24, N = 196560. Экстремальная конфигурация задается концами минимальных векторов решетки Лича (см. [31]).

Отметим еще раз, что применение экстремальных задач теории функций к решению задач дискретной геометрии стало возможным за счет использования свойства положительной определенности. Подобные идеи использовались в теории вероятностей, теории кодирования, теории функций. Примерами могут служить исследования И. Шенберга по функциональным неравенствам, исследования А.Г. Бабенко, В.И. Иванова, Н.И. Черных по экстремальным задачам, связанным с теоремой Джексона в пространствах Ьр.

Мы видим, что начиная с классических работ П.Л. Чебышева теория приближения на протяжении уже многих лет помогает в решении задач, возникающих в самых разных областях математики.

Я выражаю благодарность Владимиру Александровичу Юдину за постоянное внимание и многочисленные обсуждения, а так же Сергею Владимировичу Конягину за внимание к работе. Я выражаю благодарность Мише Фейгину и всем друзьям за дружбу и поддержку.

1. Odlyzko A.M., Sloane N.J.A. New bounds on the number of unit spheres that can touch a unit sphere in n dimensions //J. Comb. Theory. A. 26. 1979. P. 210-214.

2. Delsarte Ph. Bounds for unrestricted codes, by linear programing // Philips Res. Rep. 1972. V. 2. P. 272-289.

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

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

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

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

7. Whyte L.L. Unique arrangements of points on a sphere // The Amer. Math. Monthly. 1952. V. 59, № 9. P. 606-611.

8. Леонтьев В.К. Асимптотически устойчивые расположения зарядов в вершинах единичного n-мерного куба // Пробл. кибернетики. 1970. Т. 23. С. 27-42.

9. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. — М.: Физматлит. 1958.

10. Ахиезер Н.И. Лекции по теории аппроксимации. — М, 1947.

11. Карлин С., Стадден В. Чебышевские системы и их применение в анализеи статистике. —М.: Наука, 1976.

12. Kolushov А. V., Youdin V.A. Extremal dispositions of points on a unit sphere // Analysis Mathematica 1997. V. 23, № 1. P. 25-34.

13. Колушов А.В., Юдин В.А. О конструкции Коркина-Золотарева // Дискретная математика. 1994. Т. 6, вып. 1. С. 155-157.

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

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

16. Уолш Дж. Интерполяция и аппроксимация рациональными функциями в комплексной области. — М.: ИЛ, 1961.гэе*й*рст8ЕНН^'--¡ШЯМОТЕКА

17. Andreev N.N., Yudin V.A. Problems of Approximation Theory in Discrete Geometry // Mathematical Research. 1999. V. 107 (Advances in Multivariate Appr.), P. 19-32.

18. Andreev N.N. An extremal property oh the icosahedron // East Journal on Approximations 1996. V. 2, N. 4, pp. 459-462.

19. Андреев Н.Н. Расположение точек на сфере с минимальной энергией // Труды МИРАН. 1997. Т. 219. С. 27-31.

20. Андреев Н.Н. Минимальный дизайн 11 порядка на трехмерной сфере // Матем. заметки. 2000. Т. 67, № 4. С. 489-497.

21. Андреев Н.Н. Один сферический код // Успехи матем. наук. 1999. Т. 54, № 1. С. 255-256.