Метод проективных неравенств и совершенные формы

• Автор: Анзин, Максим Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 75 с. : ил.

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

§7. Исследование первой совершенной формы U„ ~ (р^п)
А.Н.Коркина и Е.И.Золотарева
§8. Исследование новой бесконечной по « серии совершенных
форм hn{)
§9. Исследование третьей совершенной формы <р(2п) Г.Ф.Вороного
Глава IV. Новый взгляд на результаты Г.Ф.Вороного.
§10. Описание строения окрестностей Г.Ф.Вороного предельных форм А.Н.Коркина и Е.И.Золотарева W„ (для н>10, п = 2к)
и Тя (для п> , п-2к + )
§11. Описание строения окрестности Г.Ф. Вороного для третьей
совершенной формы для п £ [к2 - 1 ,к2 +1 ,к2 + 3,}
§12. Заключение
ПРИЛОЖЕНИЕ. Перечисление минимальных векторов для предельных форм
А.Н. Коркина и Е.И. Золотарева W„ (для «>10, п = 2к) и Т„ (для
«>11, п-2к +1)
Литература

ГЛАВА I
ВВЕДЕНИЕ
§0. Краткая характеристика работы
Настоящая работа непосредственно связана с проблемой разыскания плотнейших решетчатых упаковок равных шаров в евклидовом пространстве.
В общем виде (когда все центры шаров упаковки не обязательно образуют точечную решетку) эта проблема была поставлена Кеплером в его трактате «О шестиугольных снежинках» (рассматривался плоский и трехмерный случаи). На данный момент общая проблема упаковки шаров решена лишь для плоского случая. В трехмерном случае она до сих пор остается открытой.
Напротив, проблема плотнейших решетчатых упаковок шаров ("решетчатая проблема") решена до размерности и <8, здесь основные результаты принадлежат Лагранжу, Гауссу, Коркину, Золотареву, Вороному, Барнсу, Блихфельдту и Ветчинкину.
Впервые конечный алгоритм решения решетчатой проблемы для любого п (па языке положительно определенных квадратичных форм (ПКФ)) был получен Вороным. Им было введено понятие совершенной (квадратичной) формы, далее было доказано, что каждая "плотнейшая", т.е. дающая решетку плотнейшей упаковки, форма является совершенной и то, что совершенных форм с точностью до эквивалентности конечное число. Алгоритм Вороного заключается в некотором правиле перебора конечных граней максимальной размерности так называемого "совершенного полиэдра Вороного" (полиэдра П(н)). Каждой такой грани естественно ставится во взаимно однозначное соответствие ПКФ, которая оказывается совершенной. Существо алгоритма заключается в переходе от одной известной (“первой”) совершенной грани ко всем граням, смежным с исходной по гиперграням (“стенкам”). Множество всех совершенных граней (форм), смежных с исходной и рассматриваемых с точностью до эквивалентности, называется окрестностью Вороного исходной формы. На очередном шаге алгорима Вороного, для каждой новой формы из окрестности исходной, отыскивается ее окрестность и т.д. Алгоритм Вороного заканчивается, когда для каждой из найденных на очередном шаге совершенных форм найдется эквивалентная ей форма, полученная на каком-либо из предыдущих шагов.
К настоящему времени алгоритм Вороного полностью проведен для всех п < 8. Для п < 5 он был проведен самим Вороным. Оказалось, что для п = 2,3,4,5 с точностью до эквивалентности существует, соответственно 1,1,2 и 3 совершенные формы. Кроме этого, для любых размерностей п > 6 Вороной провел первые два шага своего общего алгоритма. На втором шаге он полностью описал строение «второй» совершенной грани и для любых размерностей нашел одну из форм из окрестности второй грани - так называемую третью совершенную форму (отвечающую «большой стенке»). Однако он не стал перечислять все ее минимальные векторы и проводить третий шаг своего алгоритма.
В дальнейшем, другими авторами было показано, что совершенных форм существует всего: при « = 6 - семь, при п = 7 - тридцать три. В 2000 году французские математики объявили,- что провели алгоритм Вороного (с использованием ЭВМ) для п = 8 и получили более миллиона попарно неэквивалентных совершенных форм. На следующем шаге, начиная с п = 9, проведение алгоритма Вороного для полиэдра П(н), оказалось трудно выполнимыми.
Основной целью диссертационной работы является развитие методов, позволяющих для любых размерностей преодолевать вычислительные сложности в задачах ПКФ, и применение этих методов для проведения третьего шага общего алгоритма Вороного для п> 9. Это удалось сделать для всех размерностей вида п й [к2 -1 ,к2 + 1 ,к2 +з}, в частности, для п = 9.
Работа состоит из четырех глав и Приложения.
Глава I - вводная.
Во второй главе излагается «метод проективных неравенств», который позволяет решать задачу о нахождении арифметического минимума и всех его целочисленных представлений для произвольной ПКФ.
В третьей главе дается три приложения метода проективных неравенств к исследованию совершенных форм. В частности, этот метод используется для перечисления всех минимальных векторов классической третьей совершенной формы Г.Ф. Вороного для любых п >9. Кроме этого, найдена новая бесконечная 110 п серия совершенных форм из окрестности Вороного второй совершенной формы, отвечающая одному частному случаю «малых стенок».
В четвертой главе дано полное описание строения граней совершенного полиэдра Вороного, отвечающих классическим совершенным формам
порожденную преобразованиями ^12, з, . , я, (8.17) и 50 (8.18). Относительно
действия этой подгруппы множество представлений арифметического минимума формы ки^.2{х) разбивается на следующие две орбиты (8.14): первая орбита О, состоит из векторов (//), (Ш), (у//); вторая орбита 02 - из векторов (/), (/у), (у) и (у/).
Используя лемму Скотта, ищем разложение (8.15) для формы к2к+2 (х) в виде
бе! к

(к + 1)
7Г /?24+2 (Х) = Р 51 (Х) + Рг$2 (Х)>

(8.21)
где &,.(х) = 51 (т/>х)2. 2 = 1,2, - соответствующие квадратичные формы. Обе
т,€0,
формы £,(х) задаются матрицами М вида (8.16), где
М, : а1-2к1+2, Ьх- 4, с]=2к1-2к, <7, =-2к, ех=2;

а2 ~сг = 2/с3 - к2 + к, Ь2=4к, сі2=-2к2, е2=2 к.
Коэффициенты р!=р,(к), / = 1,2, разложения (8.21) ищем в виде решения системы линейных уравнений над кольцом многочленов от одной переменной к с целыми коэффициентами (см. также утверждение 8.1):

а: ' 2/с2 +2 2/с3 -к2 + к ' 2къ-2кг+2к'
Ь: 4 4/с Лк —
с: 2к2 —2к 2 к3-к2+к 1 Рг(П) 2к3 - 2к2 +к-
сі: -2 к -2 к2 -2 к2 + к
е: 2 2 ку 2 к-
При к> 2 эта система имеет единственное решение

{.Ріік)) 2 к

2{к-)
(8.22)
Как видим, при к >2 оба коэффициента р,(&), / = 1,2, положительные и по лемме Скотта и теореме Вороного форма к2к+2(х) является предельной. Из (8.22) видно, что при к = 2 (я = 6) рх = р2. В этом случае группа Н(6) подстановок формы /г6(х) действует транзитивно на множестве всех минимальных векторов. При к> 3 коэффициенты р, и р2 различные и, следовательно, число орбит минимальных векторов формы кп+2 (х) равно в точности двум.
На этом завершается доказательство теоремы 8.1.