Введение к работе
Актуальность темы. Теория приближения индивидуальных функций берет начало с пионерских работ П.Л. Чсбышева второй половины XIX века и до сих пор является мощным инструментом, используемым как при решении задач самой математики, так и прикладных задач. Диссертация посвящена решению старых классических задач дискретной геометрии о расположении точек на сфере с помощью экстремальных задач теории приближения индивидуальных функций с ограничениями на аппарат приближения.
Во многих экстремальных задачах расположения точек на сфере, при решении которых удается воспользоваться методами теории приближений, большую роль имеет понятие дизайна. Конечное множество точек X = {a^fc'}jbLi С Sm~l С Кт и весов {р/і-}Г=і называется взвешенным сферическим дизайном порядка q, если кубатурная формула
^У=тІ /Міг^й/Л Х> = 1 (1)
mesa JSm-i k=l k=i
верна для всех алгебраических полиномов f(x) степени не выше q (под степенью монома Xа = х"х ... а;"" понимается сумма показателей Q) + ... + ат). Множества являющиеся дизайнами представляют большой интерес, так как кубатурные формулы находят большое применение в вычислительной математике и во многих других областях. Кроме того, дизайны оказываются решением многих задач об экстремальных расположениях точек на сфере. В диссертации рассматривается случай положительных весов: р/. > О, к = 1,..., N.
Основная задача состоит в нахождении множеств Л' и весов {Pk}^=i для которых выполняется (1). Особый интерес представляют множества Л' содержащие минимальное количество точек, необходимое для выполнения (1). Такие множества называются минимальными взвешенными сферическими дизайнами. Отдельный интерес представляет случай равных весов — кубатурные формулы Чебышевского типа. В этом случае употребляются термины дизайн и минимальный дизайн.
Простейший минимальный сферический дизайн - - две противоположные точки сферы Sm~l являющиеся минимальным дизайном первого порядка. Примерами дизайнов являются вершины правильных многогранников. Так правильный симплекс вписанный в сферу S'"~x — множество из т + 1 точки с равными попарными расстояниями — является минимальным дизайном 2 порядка для любого т. Октаэдр
]
вписанный в сферу (множество точек пересечения 5"'-1 с координатными осями) является минимальным дизайном 3 порядка на сфере любой размерности. Вершины икосаэдра образуют минимальный дизайн порядка 5 на S2. В то же время вершины куба и додекаэдра являясь дизайнами соответственно 3 и 5 порядка не являются минимальными. Все вышеперечисленные минимальные дизайны являются минимальными и в классах взвешенных дизайнов соответствующих порядков. В общей ситуации это не всегда так: минимальный дизайн 5 порядка на S3 с равными весами содержит 24 точки, в то же время существует1 взвешенный дизайн 5 порядка содержащий 23 точки.
Простейшими квадратурными формулами на отрезке — формулой прямоугольника, формулой трапеций, формулой Симпсона — математики пользовались с давних времен. К. Гаусс построил квадратурную формулу на отрезке из N узлов и весов, точную для алгебраических многочленов степени 2N — 1 и доказал, что меньшим количеством узлов обойтись нельзя.
П.Л. Чебышев рассматривал задачу нахождения N узлов квадратурной формулы с равными весами на отрезке, точной для многочленов порядка N. Он в явном виде указал узлы при N = 1,...,7. Впоследствии, С.Н Бернштеин показал, что такая квадратурная формула возможна лишь для N — 1,..., 7, 9.
Дальнейшее развитие математики привело к изучению кубатурных формул на сфере. Интерес к рассматриваемому вопросу в конце XIX века был связан2 с исследованиями по проблеме Варинга, а так же с задачей представления {х\ 4- ... + х2п)к в виде суммы четных степеней линейных форм от її,..., хт (в современных терминах — задачей изометрического вложения / в 'Jw2)- Так в 1859 г. Лиувилль нашел (будем использовать современную терминологию) дизайн 5 порядка на S3. В 1876, 1877 гг. Лукач находит дизайны 5 порядка на S2 и 53. В начале века Гурвиц нашел дизайн 9 порядка на S3. Примерно в это же время А.И. Коркиным, Е.И. Золотаревым, Блихфельдом и рядом других математиков проводились исследования по теории квадратичных форм и решетчатым упаковкам пространств. Впоследствии выяснилось, что минимальные вектора некоторых решеток являются хорошими сферическими дизайнами. В середине XX века интерес к
1 Hardm R.H., Sloane N.J.Л. Expressing (a2 + b2 + с2 + d2)3 as a sum of 23 sixth
powers II J. of Combinatorial Theory, Ser. A. 1994. V. 68. P. 481-485.
2 Reznich B. Sums of even powers of real linear forms // Mem. AMS. 1992. V. 9G,
№ 463.
дизайнам снова возрос. В 1948 г. В.А. Диткин доказали, что вершины икосаэдра являются дизайном 5 порядка на 53. Многочисленные исследования по конструированию дизайнов на основе орбитных кодов принадлежат С.Л. Соболеву и его ученикам.
Оценкам снизу мощности минимальных сферических дизайнов посвящено много работ. Бурное развитие эта тематика получила после работы Ф. Дельсарта, Дж. Гетелса, Я. Зейделя3 в которой они начали использовать методы анализа для решения задач дискретной геометрии; ввели термин "дизайн" и получили оценку снизу мощности сферического дизайна с равными весами. Эта оценка дала возможность доказать минимальность дизайнов, образованных вершинами октаэдра, вершинами икосаэдра, решеткой Лича и еще ряда других известных дизайнов. Однако в целом эта оценка оказалась4 плохой — она может быть точна лишь на небольшом количестве дизайнов. Возникшие новые методы получения оценок снизу мощности сферических дизайнов стали использовать свойство положительной определенности специальных функций. Затем эта тематика получила развитие в ряде работ, среди которых следует отметить работы Н. Слоэна, А. Одлыжко, Ф. Дельсарта, Дж. Гетелса, Я. Зейделя, В.И. Левенштейна, В.М. Сидельникопа, В.А. Юдина. Основная идея, принадлежащая Ф. Дельсарту, состоит в использовании многочленов Гегенбауэра и их свойства положительной определенности.
За последние годы доказана минимальность лишь нескольких дизайнов5. Задача нахождения минимального дизайна 11 порядка на S3 рассматривалась несколькими авторами. Из общей оценки работы Дельсарта-Гетелся-Зейделя следует, что мощность дизайна 11 порядка на S3 не меньше 112. В работе В.А. Юдина6 приведена общая оценка, из которой следует, что мощность минимального дизайна 11 порядка на S3 не меньше 117. Такая же оценка получена в работе болгарских математиков7. В пункте 1.3 доказывается, что минимальный сферический
^Delsarte P., Goelhals J.M., Seidel J.J. Spherical codes and designs // Geometriae Dedicata. 1977. V. 6. P. 363-388.
4Bannai E., Dumerell П.М. Tight spherical designs. 1. // J. Math. Soc. Japan. 1979. V. 31. P. 199-207.
Bannai E., Damerell H.M. Tight spherical designs. II. // J. London math. Soc. 1980. V. 21. P. 13-30.
bSeidel J.J. Isometric embeddings and geometric designs // Discrete Math. 1994. V. 136. P. 281-293.
6IO()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 — {х^}^=1 С 5m_1 называется сферическим т-кодом, если
x(,^x(j' ^ т для всех 1 ^ i,j, <; N, г ф j.
Действительно, если известно, что при передаче точки і'*' искажения не слишком велики и принятая точка г'*'' всегда удовлетворяет условию х^'х'^' > г/2 зная сам код — набор точек со сферы, которые могли быть переданы — всегда можно однозначно восстановить передававшуюся информацию. Желание передавать максимально большой объем информации приводит к задаче нахождения сферических кодов, содержащих максимально возможное число точек при заданных m и г.
Использование свойств ортогональных многочленов в задачах кодирования было начато Ф. Дельсартом. Для оценок мощности кодов из пространства Хемминга (вершины единичного 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 показано, что при т = 4 максимальный сферический соя(7г/5)-код содержит 120 точек.
Глава 3 посвящена задаче об энергии и сходной с ней задачам. Рассматриваются задачи о нахождении величин
(2) (3) (4)
N 1
W(m,N)= inf У^ r-7^ гг; її
S(m,N)= sup У2\х^-х^\,
i(4,..:iI(N)S">-i , i = 1 N
P(m,N) = sup П |x(i) -x(j)|.
,7;n),...,I(N)eS'"-1 i.J = ,
Наилучшие, в смысле минимума потенциальной энергии системы, расположения зарядов на отрезке были найдены Г. Сегё9. Им было показано, что если в концах отрезка [—1,1] помещено два положительных заряда, то N единичных зарядов на [—1,1] расположенных в нулях многочлена Якоби (с параметрами определяемыми по зарядам, расположенным на концах отрезка) доставляют минимум потенциальной энергии рассмотренной системы.
Задача о нахождении величины W(m, N) является обобщением классической проблемы расположения зарядов на сфере в трехмерном пространстве с минимальной потенциальной энергией. В начале века английский физик Дж.Дж. Томсон проводил10 эксперимент по нахождению наилучших расположений небольших количеств зарядов на сфере трехмерного пространства. При ./V = 4, G, 12 эксперименты приводили к классическим конфигурациям: тетраэдру, октаэдру и икосаэдру. Аналогичная задача, о нахождении расположения точек с минимальной энергией в дискретных пространствах, была поставлена С.В. Яблонским. Случай суммы попарных расстояний S(d, JV) был рассмотрен Л.Ф. Тотом11. Задача о произведении, связанная с проблемой Фекете о расположении, максимизирующем определитель Вандермонда, N точек
9 Сегё Г. Ортогональные многочлены. — М.: Физматлит, 1962.
10 Whyte L.L. Unique arrangements of points on a sphere // The Amer. Math. Monthly.
1952. V. 59, № 9. P. 60C-611.
11 Tom Л.Ф. Расположения на плоскости, па сфере и п пространстве. — М.: Физ
матлит. 1958.
в заданной области, появилась в начале XX века. В настоящее время, она нашла применение в теории сложности.
Решение этих классических задач было известно лишь в следующих случаях, причем экстремальные конфигурации одинаковы для всех трех задач: т = 2, N — произвольное; т — произвольное, N = т + 1; т — произвольное, TV = 2m; т = 8, N = 240. Доказательство последних двух случаев стало возможным лишь после привлечения техники экстремальных задач теории приближения. Отталкиваясь от экстремальных задач применяемых в теории кодирования, в связи с задачей об энергии, В.А. Юдин рассмотрел12 задачу приближения функции 1/{2(1 — і)}'"1-2)/2 снизу на отрезке [—1,1] в метрике L\ с весом (1 — 2)(т-3)/2 конусом положительно определенных функций. Им было показано, что величина уклонения в этой задаче участвует в оценке снизу функионала энергии.
Оценки с другой стороны во всех трех задачах доставляют хорошо известные конфигурации точек на сфере.
Решая экстремальную задачу поставленную В.А. Юдиным для т = 3, N = 12; т - 4, N = 120; т = 24, N = 196560 и сходные с ней экстремальные задачи теории функций в главе 3 получено решение задач об энергии, сумме и произведении в указанных случаях.
Цель работы. Решить задачу о минимальном дизайне 11 порядка на S3 и задачу о максимальном соз(7г/5)-коде на S3. Привести новые точные решения задачи об энергии, сумме и произведении.
Методы исследования. В работе используются методы экстремальных задач теории приближений, связь задач о расположении точек на сфере с экстремальными задачами теории функций.
Научная новизна. Результаты диссертации являются новыми и заключаются в следующем:
-
Доказано, что минимальный взвешенный дизайн 11 порядка на 53 содержит 120 точек и экстремальным является дизайн с равными весами.
-
Доказано, что максимальный сферический соя(7г/5)-код на S3 содержит 120 точек.
12Юдии В.А. Минимум потенциальной энергии точечной системы зарядов // Дискр. мат. 1992. Т. 4, № 2. С. 115-121.
3. Решена задача о нахождении расположения N одинаковых зарядов на Sm_l минимизирующем потенциальную энергию системы в случаях: т. = 3, N = 12; т = 4, N = 120; т = 24, N = 19G560. В этих же случаях решены задачи о максимизации суммы и произведения попарных расстояний N точек, расположенных на Sm~'.
Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты и методы могут быть использованы специалистами в области дискретной геометрии, конструктивной теории функций.
Апробация диссертации. Результаты диссертации докладывались на Саратовской Зимней школе по теории функций (Саратов, 1996; Саратов, 1998; Саратов, 2000); Летней школе по теории функций памяти СБ. Стечкина (Миасс, 1996 г.; Миасс, 1997 г.; Миасс, 1998 г.); на конференции по теории функций посвященной памяти СБ. Стечкина (Екатеринбург, 2000); на конференции по приближению функций многих переменных (Германия, 2000); на семинаре по теории приближений в МИР АН (под руководством СА. Теляковского).
Публикации. Результаты диссертации опубликованы в пяти работах, список которых приведен в конце автореферата.
Структура и объем работы. Диссертация состоит из введения и трех глав. Текст диссертации изложен на 41 странице. Список литературы содержит 33 наименования.
