Метод проективных неравенств и совершенные формы тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Анзин, Максим Михайлович

• Анзин, Максим Михайлович
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Анзин, Максим Михайлович

Глава I. Введение.

§0. Краткая характеристика работы.

§1. Основные понятия и факты.

§2. Основная задача и роль метода проективных неравенств.

§3. Алгоритм Г.Ф. Вороного, исторический обзор.

Глава II. Метод проективных неравенств.

§4. Конус определенности К, вариантный многочлен p(t).

§5. Вариации и оценки.

§6. Основные вариации и оценки.

Глава III. Приложения метода проективных неравенств.

§7. Исследование первой совершенной формы U„ ~(Pq1)

А.Н.Коркина и Е.И.Золотарева.

§8. Исследование новой бесконечной по п серии совершенных форм hn(\).

§9. Исследование третьей совершенной формы qj^ Г.Ф.Вороного.

Глава IV. Новый взгляд на результаты Г.Ф.Вороного.

§10. Описание строения окрестностей Г.Ф.Вороного предельных форм А.Н.Коркина и Е.И.Золотарева W„ (для п> 10, п = 2к) и Т„ (для л>11? п = 2к + \).

§11. Описание строения окрестности Г.Ф. Вороного для третьей совершенной формы ср^ для п g \к2 -\,к2 +1 ,к2 +3,}.

Введение диссертации (часть автореферата) на тему «Метод проективных неравенств и совершенные формы»

§0. Краткая характеристика работы

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

В общем виде (когда все центры шаров упаковки не обязательно образуют точечную решетку) эта проблема была поставлена Кеплером в его трактате «О шестиугольных снежинках» (рассматривался плоский и трехмерный случаи). На данный момент общая проблема упаковки шаров решена лишь для плоского случая. В трехмерном случае она до сих пор остается открытой.

Напротив, проблема плотнейших решетчатых упаковок шаров ("решетчатая проблема") решена до размерности п< 8, здесь основные результаты принадлежат Лагранжу, Гауссу, Коркину, Золотареву, Вороному, Барнсу, Блихфельдту и Ветчинкину.

Впервые конечный алгоритм решения решетчатой проблемы для любого п (на языке положительно определенных квадратичных форм (ПКФ)) был получен Вороным. Им было введено понятие совершенной (квадратичной) формы, далее было доказано, что каждая "плотнейшая", т.е. дающая решетку плотнейшей упаковки, форма является совершенной и то, что совершенных форм с точностью до эквивалентности конечное число. Алгоритм Вороного заключается в некотором правиле перебора конечных граней максимальной размерности так называемого "совершенного полиэдра Вороного" (полиэдра П(и)). Каждой такой грани естественно ставится во взаимно однозначное соответствие ПКФ, которая оказывается совершенной. Существо алгоритма заключается в переходе от одной известной ("первой") совершенной грани ко всем граням, смежным с исходной по гиперграням ("стенкам"). Множество всех совершенных граней (форм), смежных с исходной и рассматриваемых с точностью до эквивалентности, называется окрестностью Вороного исходной формы. На очередном шаге алгорима Вороного, для каждой новой формы из окрестности исходной, отыскивается ее окрестность и т.д. Алгоритм Вороного заканчивается, когда для каждой из найденных на очередном шаге совершенных форм найдется эквивалентная ей форма, полученная на каком-либо из предыдущих шагов.

К настоящему времени алгоритм Вороного полностью проведен для всех п < 8. Для п < 5 он был проведен самим Вороным. Оказалось, что для п = 2,3,4,5 с точностью до эквивалентности существует, соответственно 1,1,2 и 3 совершенные формы. Кроме этого, для любых размерностей п > 6 Вороной провел первые два шага своего общего алгоритма. На втором шаге он полностью описал строение «второй» совершенной грани и для любых размерностей нашел одну из форм из окрестности второй грани — так называемую третью совершенную форму (отвечающую «большой стенке»). Однако он не стал перечислять все ее минимальные векторы и проводить третий шаг своего алгоритма.

В дальнейшем, другими авторами было показано, что совершенных форм существует всего: при « = 6 - семь, при п-1 - тридцать три. В 2000 году французские математики объявили,' что провели алгоритм Вороного (с использованием ЭВМ) для п = 8 и получили более миллиона попарно неэквивалентных совершенных форм. На следующем шаге, начиная с /7 = 9, проведение алгоритма Вороного для полиэдра П(и), оказалось трудно выполнимыми.

Основной целью диссертационной работы является развитие методов, позволяющих для любых размерностей преодолевать вычислительные сложности в задачах ПКФ, и применение этих методов для проведения третьего шага общего алгоритма Вороного для п>9. Это удалось сделать для всех размерностей вида п <£ [к2 - \,к2 +1 ,к2 + з|, в частности, для п = 9.

Работа состоит из четырех глав и Приложения.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Анзин, Максим Михайлович

§12. Заключение.

В работе [3] Г.Ф. Вороной построил теорию совершенных форм. Он доказал, что в каждой размерности п > 2 существует лишь конечное число классов эквивалентности таких форм. Для « = 2,3,4,5 он перечислил все классы совершенных форм, которых оказалось, соответственно 1,1,2 и 5. В дальнейшем, все совершенные формы были перечислены: для /7 = 6 - в [13] - их оказалось 7; для « = 7 - в[14]-их оказалось 33. Известно также, что все совершенные формы перечислены и для и = 8, где их оказалось около одного миллиона.

Кроме исследований для п < 6, Вороной для всех размерностей п > 6 провел первые два шага своего общего алгоритма по перечислению совершенных форм. А именно, 6н конструктивно описал строение первой и второй совершенных граней, отвечающих формам <р^0п) и (р\п). То есть для каждой размерности Вороной исследовал всего лишь по две формы. С учетом того обстоятельства, что уже для /7 = 8 количество совершенных форм оказалось очень большим, » результаты Вороного в [3] могли быть восприняты как «малая часть от общего объема». Это также дало основания считать, что в отношении практических вычислений, Вороной реализовал свой алгоритм «лишь в £-окрестности второй совершенной грани».

Наши исследования приводят к следующим выводам

1. Результаты Вороного относительно строения второй совершенной грани один-в-один приложимы к исследованию и других совершенных граней (например, и Т„).

2. Описание строения других совершенных граней удается сводить к результатам Вороного о строении второй совершенной грани.

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

Вопрос. А не есть ли результаты Вороного о строении второй совершенной грани «вся теория целиком»?

В стремлении получить ответ на этот вопрос, мы предпринимаем дальнейшие исследования.

Список литературы диссертационного исследования кандидат физико-математических наук Анзин, Максим Михайлович, 2003 год

1. Рышков С. Барановский Е.П. Классические методы теории решетчатых упаковок// УМН. 1979. Т.34, №4. 3-63.

2. KorkineA., ZolotareffG. Sur les formes quadratiques// Math. Ann. 1873. Bd. 6. S. 366-389. См. также: Золотарев Е.И. Поли. собр. соч. М.: Изд-во АН СССР. 1931. Т.1. 109-137.

3. Вороной Г.Ф. О некоторых свойствах пололсительпых совершенных квадратичных форм// Собр. соч. Киев: Изд-во АН УССР, 1952. Т.2. 171-238.

4. КиутД. Искусство программирования для ЭВМ. М: Мир, 1977. Т.2. 105-125.

5. Dieter U. How to calculate shortest vectors in a lattice// Math. Comput. 1975. Vol. 29, N 131. P.827-833.

6. Finck U., Post M. Improved methods for calculating vectors of short length in a lattice: AMS Subject classification 10-04,10E25, 10C25. Math. Inst.'Univ. Dusseldorf.

7. Aimm M.M. О варианиях положителы1ых квадратичных форм (с прилолсением к исследованию совершенных форм).//Тр. МИАН. 1991. Т 196. 11-26.

8. Апзин М.М., О третьей совершенной форме Г.Ф. Вороного// 3-я Мелсдународная конференция по геометрии «в целом». Тезисы докладов. Черкассы 1999. 5-6.

9. Erdahl R., Ryhnikov К., An Infinite Series of Perfect Quadratic Forms and Big Delaunay Simplices in Z''//Tp. МИАН. 2002. T 239. С 170-178.

10. Coxe/erЯ^S'.M,Extremeforms//Can. J.ofMath.- 1951 - V. 3 - P . 391-441.

11. Barnes E.S., The complete enumeration of extreme senary forms// Phil. Trans. Royal Soc. of 1.ondon, Ser. A - 1957 -V. 249, N 969 - P. 461-506.

12. Jaquet D.-O., Enumeration complete des classes de formes parfaites en dimensuon 111 Univ. De Neuchatel-1991. 15. Larmouth J. The enumeration of perfect forms// Computers in number theory. L.; N. Y., 1971. P. 237-239.'

13. Scott P.R. On perfect and extreme forms// J. Austral. Math. Soc. 1964. N 4. P. 56-77.

14. Stacey K.C. The enumeration of perfect quadratic forms in seven variables: Diss. Doct. Philos. Oxford: Univ. press, 1973. ^