Содержание к диссертации
Введение
1. Введение.
0. Краткая характеристика работы 3
1. Основные понятия и факты 5
2. Основная задача и роль метода проективных неравенств 7
3. Алгоритм Г.Ф. Вороного, исторический обзор 11
2. Метод проективных неравенств.
4. Конус определенности К, вариантный многочлен p(t) 16
5. Вариации и оценки 17
6. Основные вариации и оценки 20
3. Приложения метода проективных неравенств.
7. Исследование первой совершенной формы U„ ~ 8. Исследование новой бесконечной по п серии совершенных форм hn(\) 24 9. Исследование третьей совершенной формы ср^ Г.Ф.Вороного 36 4. Новый взгляд на результаты Г.Ф.Вороного. 10. Описание строения окрестностей Г.Ф.Вороного предельных форм А.Н.Коркина и Е.И.Золотарева W„ (для п > 10, п = 2к) и Т„ (для л>11? л = 2 + 1) 60 11. Описание строения окрестности Г.Ф. Вороного для третьей совершенной формы ср^р для п [к2 - \,к2 + \,к2 +3,) 67 Заключение 71 Введение к работе 0. Краткая характеристика работы Настоящая работа непосредственно связана с проблемой разыскания плотней ших решетчатых упаковок равных шаров в евклидовом пространстве. В общем виде (когда все центры шаров упаковки не обязательно образуют точечную решетку) эта проблема была поставлена Кеплером в его трактате «О шестиугольных снежинках» (рассматривался плоский и трехмерный случаи). На данный момент общая проблема упаковки шаров решена лишь для плоского случая. В трехмерном случае она до сих пор остается открытой. Напротив, проблема плотнейших решетчатых упаковок шаров ("решетчатая проблема") решена до размерности л<8, здесь основные результаты принадлежат Лагранжу, Гауссу, Коркину, Золотареву, Вороному, Барнсу, Блихфельдту и Ветчинкину. Впервые конечный алгоритм решения решетчатой проблемы для любого п (на языке положительно определенных квадратичных форм (ПКФ)) был получен Вороным. Им было введено понятие совершенной (квадратичной) формы, далее было доказано, что каждая "плотнейшая", т.е. дающая решетку плотнейшей упаковки, форма является совершенной и то, что совершенных форм с точностью до эквивалентности конечное число. Алгоритм Вороного заключается в некотором правиле перебора конечных граней максимальной размерности так называемого "совершенного полиэдра Вороного" (полиэдра П(и)). Каждой такой грани естественно ставится во взаимно однозначное соответствие ПКФ, которая оказывается совершенной. Существо алгоритма заключается в переходе от одной известной ("первой") совершенной грани ко всем граням, смежным с исходной по гиперграням ("стенкам"). Множество всех совершенных граней (форм), смежных с исходной и рассматриваемых с точностью до эквивалентности, называется окрестностью Вороного исходной формы. На очередном шаге алгорима Вороного, для каждой новой формы из окрестности исходной, отыскивается ее окрестность и т.д. Алгоритм Вороного заканчивается, когда для каждой из найденных на очередном шаге совершенных форм найдется эквивалентная ей форма, полученная на каком-либо из предыдущих шагов. К настоящему времени алгоритм Вороного полностью проведен для всех п < 8. Для п < 5 он был проведен самим Вороным. Оказалось, что для п = 2,3,4,5 с точностью до эквивалентности существует, соответственно 1,1,2 и 3 совершенные формы. Кроме этого, для любых размерностей п > 6 Вороной провел первые два шага своего общего алгоритма. На втором шаге он полностью описал строение «второй» совершенной грани и для любых размерностей нашел одну из форм из окрестности второй грани — так называемую третью совершенную форму (отвечающую «большой стенке»). Однако он не стал перечислять все ее минимальные векторы и проводить третий шаг своего алгоритма. В дальнейшем, другими авторами было показано, что совершенных форм существует всего: при л = 6 - семь, при п-1 - тридцать три. В 2000 году французские математики объявили,' что провели алгоритм Вороного (с использованием ЭВМ) для п = 8 и получили более миллиона попарно неэквивалентных совершенных форм. На следующем шаге, начиная с /7 = 9, проведение алгоритма Вороного для полиэдра П(«), оказалось трудно выполнимыми. Основной целью диссертационной работы является развитие методов, позволяющих для любых размерностей преодолевать вычислительные сложности в задачах ПКФ, и применение этих методов для проведения третьего шага общего алгоритма Вороного для п>9. Это удалось сделать для всех размерностей вида п < [к2 -\,к2 +l,k2 +3J, в частности, для п = 9. Работа состоит из четырех глав и Приложения. В исследованиях по геометрии ПКФ и, в частности, в исследованиях о предельных и совершенных формах ключевой является следующая Задача 1. Для данной ПКФ fix): 1) определить min / - значение ее арифме- тического минимума; 2) найти все векторы ±ml,...,±ms GZ" - представления минимума формы С вычислительной точки зрения, задача 1 является трудной. Разные авторы использовали для ее решения различные приемы и методы. В настоящей работе мы предлагаем универсальный метод решения задачи 1, который называем методом проективных неравенств. Дадим краткое описание этого метода и объясним его значение. Пусть f{\) - ПКФ и вектор х0 eR" является представлением числа с = /(х0) 0 для формы f. В главе II предлагается способ получения различного рода называемых нами проективных неравенств вида где g(x) - произвольная ненулевая квадратичная форма, которую будем называть вариацией формы /, а числа /,+ и /Г вычисляются по формам fug. Для нахождения всех целочисленных векторов Z = (Z,,...,Z„)GZ" -представлений некоторой величины о 0 для исходной формы /(х) - мы выгодным способом подбираем различные вариации g,(x), / = 1,2,... , и для каждой из них составляем проективные неравенства (2.1). Получающиеся неравенства дают нам ограничения на координаты z), / = 1,...,я, отыскиваемых векторов. Задача состоит в том, чтобы указать такой набор вариаций g,(x), проективные неравенства (2.1) для которого ограничивали бы в Z" лишь конечное число векторов. Отметим, что все известные автору алгоритмы решения задачи 1 основаны на неравенствах, которые являются частными случаями проективных неравенств (2.1). Так, например, алгоритмы, предложенные в [4,5], основаны на неравенствах (2.1), получающихся для п вариаций g/(x) = :c/2, / = 1,..., п. Алгоритм, предложенный С.С. Рышковым и Е.П. Барановским в [1], основан на неравенствах (2.1) для единственной вариации g(x) = Y xi Более эффективный метод решения задачи 1 был предложен в [2] Коркиным и Золотаревым. Он основан на разложении исходной ПКФ по Лагранжу. В дальнейшем, этот их метод был переоткрыт в [6] У. Финком и М. Постом. (Аналогичные истории происходили и с другими классическими результатами Коркина и Золотарева). Однако и этот алгоритм удается интерпретировать как алгоритм, основанный на некоторых проективных неравенствах. Только в этом последнем случае речь идет не о конечном числе используемых вариаций, а о нескольких бесконечных классах вариаций. Но мы на этом подробно не останавливаемся. Автором реализован алгоритм, основанный на неравенствах (2.1), получающихся для вариаций gi(x) = xf, / = 1,..., и, и giJ(x) = 2xixJ, \ i j n. Метод проективных неравенств можно использовать в различных задачах геометрии ПКФ. Причем не только в аналитических исследованиях, но и в практических вопросах создания различных алгоритмов для решения задач ПКФ. В главе III настоящей работы мы демонстрируем возможности метода проективных неравенств и даем три его приложения, которым посвящены, соответственно, 7, 8 и 9. Наиболее эффектной, на наш взгляд, работа метода проективных неравенств оказывается при исследовании в 7, главы III, классической совершенной формы U„(x) Коркина и Золотарева [2], где обсуждаются новые неравенства (2.1), получающиеся для вариаций g(. (х) = 2х;- Xj, \ i j п . Результаты двух других параграфов 8 и 9 являются новыми, впервые получены автором в [7,8], и посвящены различным вопросам дальнейшего развития общего алгоритма Г.Ф. Вороного по перечислению совершенных форм. В 8, главы III, мы исследуем новую бесконечную по п серию совершенных форм hn{\) из окрестности Вороного второй совершенной формы ф\"\ отвечающую одному частному случаю «малых стенок» второй совершенной грани. При этом мы решаем следующие две задачи: а) находим параметр t «отклонения» от второй совершенной грани (см. 3) и находим форму hn{\) - соседствующую с 0?И); б) для формы Л„(х) полностью решаем задачу 1, а также даем ответы на другие вопросы. В 9, главы III, мы для любых размерностей и 9, проводим подробные исследования для третьей совершенной формы Вороного (Р2П\ которая также принадлежит окрестности Вороного второй совершенной формы р\п), но только отвечает случаю «больших стенок» (которые все попарно эквивалентны между собой) второй совершенной грани. Для формы (р Вороной решил следующие две задачи: а) нашел параметр t «отклонения» от второй совершенной грани (см. 3) и нашел форму (р(2п) - соседа р\п)\ б) для формы (р(2п) он решил только пункт 1) задачи I, то есть определил значение арифметического минимума. В настоящей работе мы, непосредственно вслед за Вороным, решаем и пункт 2) задачи 1 для формы Р2П), и перечисляем все ее минимальные векторы. В результате исследований, проведенных в главе III становится очевидно, что роль метода проективных неравенств не ограничивается лишь решением задачи 1, а выходит за эти рамки. В подтверждение этому, укажем на следующие три обстоятельства. Первое обстоятельство. Форма /z„(x), впервые открытая в работе автора [7], в дальнейшем была переоткрыта другими авторами в [9]. Причем также при помощи нашего метода проективных неравенств. На основе формы hn{\) в [9] была сконструирована новая бесконечная по п серия симплексов Делоне относительного объема п-Ъ. На сегодня это является лучшим из известных результатом в этой области. То есть наши результаты получили приложение в другой задаче. Второе обстоятельство. Наши исследования относительно формы cpSf дали, в частности, следующие результаты, которые оказались неожиданными. Нам удалось показать, что для всех размерностей вида п . [к2 -1,к2 +1, к2 + 3, j, п 9, у формы р(2п) имеется единственный «новый» минимальный вектор. Т.е. такой, который не является одновременно минимальным вектором и для формы р\п). Из этого очевидным образом следует, что совершенная грань полиэдра Вороного, отвечающая форме (р при указанных п является пирамидой, построенной над «большой стенкой» (над большой гипергранью) грани (р\п). Это позволило дать для указанных размерностей конструктивное описание третьей совершенной грани, отвечающей форме (р , и свести такое описание к классическому случаю конструктивного описания «большой стенки» грани р\п) - основанию пирамиды. Этому посвящен 11. Тем самым, для всех размерностей п 9, п[к2 -\,к2 +\,к2 +3,] мы впервые полностью провели третий шаг общего алгоритма Г.Ф. Вороного по перечислению совершенных форм. Третье обстоятельство. В главе IV мы исследуем совершенные формы А.Н.Коркина и Е.И.Золотарева W„ и Т„ (см. [2] и 3 этой гл.) и даем небольшой по объему, но важный с точки зрения алгоритма Вороного по перечислению совершенных форм, следующий результат. В работах [10,11] нам удалось доказать, что грани полиэдра Вороного (см. [1,3]), отвечающие при п = 2к \0 формам ср\п) и W„, и при п = 2к +1 11 - формам ф\п) и Тп афинно эквивалентны. То есть окрестности Вороного форм W„ и Т„ устроены локально комбинаторно эквивалентно окрестности формы (р\п) при п четных и нечетных соответственно. Таким образом, нам удалось показать, что существуют и другие совершенные грани (для форм Ww и Т„), окрестности Вороного которых локально комбинаторно устроены абсолютно так же, как и окрестность Вороного для совершенной грани формы ср\п). Это позволяет автоматически переносить результаты Вороного и на эти примеры, и исследовать их аналогичным образом при помощи нашего метода проективных неравенств. Но это уже выходит за рамки настоящей работы. Проведенные нами исследования позволяют по-новому взглянуть на результаты Г.Ф. Вороного о совершенных формах и поставить некоторые важные вопросы. Пусть f{ s) = YJfijxixj " ПКФ и g(x) = Y,gyxixj " некоторая ее вариация с сигнатурой г = (r(+),r(_),r(0)). В пространстве параметров HN формы f и g определяют некоторую двумерную плоскость Р = /, g). Рассмотрим пересечение этой плоскости с множеством L (4.1) (рис.1) и конусом определенности К . Поскольку для произвольной формы / из условия / eL следует Я/ Є Li для любых Я є R, то для нахождения пересечения плоскости Р с множеством L достаточно: 1) построить пересечение L с прямой f = f — tg и 2) для вектора g, параллельного данной прямой, выяснить g єІ_. или gL. Таким образом, с учетом описанной выше ситуации пересечение плоскости Р с множеством Li есть набор прямых, проходящих через общее начало - точку OeR - и пересекающих прямую / = /g в точках, отвечающих корням t , /=1,...,г(+), и tj, / = 1,...,г(_), вариантного многочлена p{t). Кроме того, если вариация g{x) вырождена (g є L.), то в пересечение Р Г) L входит также и прямая, проходящая через начало - точку 0 eR - в направлении вектора g. Форма g по отношению к конусу определенности К может занимать одно из трех положений: а) эллиптическое, когда g є К ; б) параболическое, когда g є д К \ {0}; в) гиперболическое, когда g є 1RN \ К . Рассмотрим образы точек плоскости Р на проективной прямой Р1 (рис. 2). Множеству К на проективной прямой отвечает некоторый отрезок определенности [о,6]сР . Пополним прямую f — f — tg бесконечно удаленной точкой /ю (/ = со) и обозначим через / + и t7 те значения параметра /, при которых на проективной прямой Р1 образ / пересекается с границами а и Ъ отрезка определенности. Иными словами, tt и t7 - это ближайшие к нулю корни вариантного многочлена pit) со стороны соответственно положительного и отрицательного направлений с допустимым переходом (в случае невырожденности вариации g) через бесконечность / = +со. Очевидно, что варьированная форма fix) является определенной (не обязательно строго) лишь при значениях параметра t, лежащих в отрезке (в проективном смысле) [t ,tt]. При таких / для произвольного вектора х0єКя, представляющего значение /0=/(хо) для формы /, выполняется неравенство f(xo) = fog(xQ) 0, из которого мы получим следующее Утверждение 5.1. Пусть даны две квадратичные формы fix), g(x) Ф 0 от одного и того же числа переменных хєЕ", и пусть f(x) 0 - положительно определенная. Рассмотрим вариацию f(x) = f(x) — tg(x) и определим вариантный многочлен pit) = det f - det(/ -1 g). Пусть tt и t - это блиоісайшие к нулю корни вариантного многочлена p{t), являющиеся границами отрезка определенности [t ,tt] (в проективном смысле, как это определено выше). Тогда для произвольного вектора х0 eR", представляющего значение /о =/(хо) для формы f, выполняются неравенства Доказательство. Любая пара квадратичных форм, одна из которых (f(x)) является положительно определенной приводится1 при помощи некоторого линейного не вырожденного преобразования к каноническому виду. То есть существует преобразование М, заданное некоторой матрицей М, detM O, в результате которого формы f(x) и g(x) принимают вид В новом базисе вариантный многочлен принимает следующий вид 1 См., например Л. И. Кострикии, Введение в алгебру. Часть II. Линейная алгебра. Издание второе. Москва, Физматлит, 2001, Гл. 3, 3, п.5, Теорема 8, стр. 135. і Поскольку g(x)#0, то среди величин Я, имеются отличные от нуля. Запишем их в виде - //," = Я, ... -//;,., = Я (. (/г,- 0), //,+ = At+rt.y ... //,., = Яг(.)+г 0 (ju 0), Я,=0, для / = г(_) +г(+) + 1,...,я. Если среди величин Л,, имеются значения разных знаков, то /Г = - l///j" , tt = \/// . . Если все Я, одного знака (например, положительные), то в случае г(+) « мы имеем: t7 =-00, r.+ = іЛи ,м , а в случае г(+) = л: /." = l///,+ , /,+ = l/// c В любом случае для значений te[t7,tt] форма f(x) = f(x)g(x) является положительной и для вектора XQGR": /0 = /(Х0) выполняется неравенство /(х0) = /0-/g(x0) 0, из которого мы получаем (5.1). Замечание 5.1. В дальнейшем неравенства (5.1) мы будем называть эллиптическими (параболическими, гиперболическими) проективными неравенствами в соответствии с тем, какое положение относительно конуса К занимает форма g{x). 6. Основные вариации и оценки В этом параграфе мы приводим примеры различных вариаций и получаем для них неравенства (5.1), которые будут использоваться нами в дальнейшем. Через fix) = Yjfuxixj обозначим некоторую ПКФ с матрицей F. I. Параболические вариации. Пусть /(х) = /,лг, +... + 1пхп - некоторая ненулевая линейная форма, зависящая от переменных х,,...,хп. Рассмотрим вариацию g(x) = /2(x) = (/1xI+... + /„xJ2 0. (6.1) Вариация g(x) имеет сигнатуру г = (г(+),г(_),г(0)) = (1,0,«-1). Вариантный многочлен p{t) = det f = det(/ - tg) согласно утв. 4.1, является многочленом первой степени с единственным конечным положительным корнем / +. Чуть ниже мы покажем, что он имеет вид где 1 = (/] ,...,/„ )т є В." - вектор, составленный из коэффициентов линейной формы /(х), /(_1) - форма, взаимная По отношению к форме /, т. е. заданная матрицей F , обратной к матрице F. Отметим сразу, что в этом случае / + = 1/у (_,)(0 +о, й --оо и проективные неравенства (5.1) имеют вид При 1 = е;, / = 1,...,л, где е;(0,...,1,...,0)г - единичный вектор, неравенства (6.3) превращаются в следующие: где F/7 - матрица алгебраического дополнения элемента fit матрицы F. Именно на таких неравенствах основаны алгоритмы решения задачи 1 из 2, предложенные в [4,5], однако сами неравенства (6.4) выводятся в этих работах в результате рассмотрения взаимной решетки, т. е. из других соображений. Доказательство (6.2). Обозначим через f,,...,f„ и g,,...,g;i столбцы соответственно матриц F и G форм /(х) и g(x), а сами матрицы F и G - в виде строк своих столбцов: F = (f,,...,! „), G =(g,,...,g„). В силу (6.1) все столбцы g,. матрицы G пропорциональны столбцу 1 коэффициентов линейной формы /(х): g;-=/,. I, / = 1,...,и. Пользуясь полилинейностыо определителя как функции своих столбцов, представляем определитель варьированной формы /, т.е. определитель ее матрицы F = F — / G, в виде где h,- =ff. или h,- =g/. Все слагаемые в (6.5), содержащие более одного столбца из g,-, / = 1,...,/7, равны нулю. Поэтому (6.5) перепишется как Разлагая в (6.6) определители det(f,,...,I,...,f„) по элементам столбца 1, получаем (6.2): где F,y - соответствующие алгебраические дополнения для элементов матрицы F. Соотношение (6.2) доказано. II. Гиперболические вариации. Для ПКФ f(x) среди прочих гиперболических мы будем рассматривать вариации Иногда мы будем рассматривать и вариации g0,(x) = 2х0х,, \ j n, где -х0 = хх + ... + хп. В этом случае согласно утв. 4.1, вариантный многочлен является многочленом второй степени и имеет вид /(х), tj - матрица алгебраического дополнения элемента fy матрицы F, a U/y - матрица, получающаяся из матрицы F путем вычеркивания строк и столбцов с номерами / и j. Очевидно, detU,y 0 и, следовательно, многочлен /?,у(0 имеет один положительный корень 0 ґ.+ +оо и один отрицательный корень -оо /Г 0. Проективные неравенства (5.1) в этом случае равносильны неравенствам III. Эллиптические вариации. Для ПКФ /(х) среди прочих эллиптических мы будем рассматривать вариацию В этом случае согласно утв. 4.1, вариантный многочлен является многочленом п-й степени и имеет вид p(t) = detf = det(FE)=Zn(0, где F = {/ .} - матрица формы /, Е - единичная матрица размера п, характеристический многочлен. В этом случае все корни 0 tx =tmin t2 ... /„ = max вариантного многочлена %n(f) положительные, tt m\n-, t max и проективные неравенства (5.1) выглядят следующим образом: /o/ Z /o/ ma.. (6-Ю) Замечание 6.1. Пусть е,,...,ем - единичные векторы. В гл. III при решении задачи 1 из 2 мы будем использовать неравенства (6.3), (6.4) и (6.9), в которых /0 заменено на т: т = min f(el) = min fu. 1. Формулировка теоремы Вороного о совершенности формы (р2" Формулы (ЗЛО) для р = р„ в форме р2п) = (р\п) — рпхххъ определены начиная лишь ся 4, поэтому форму р2п) будем считать заданной для всех п 4. В [3] был получен следующий результат. Теорема 9.1 (Г.Ф. Вороной). При всех п А для формы (р2п) выполняются условия: (і) (р2" 0 - является совершенной формой; (И) арифметический минимум формы (р2 равен т\пф2 = 1. В настоящей работе мы дополняем эти результаты Вороного следующими. Теорема 9.2. При всех п 9 для формы р2п) выполняются также и условия: (7/7) количество (пар взаимно противоположных) целочисленных векторов -представлений арифметического минимума формы ср равно: (iv) в разд.З 9 мы перечисляем все векторы ± z є Z", для которых ср2 (z) 1, п 9. Для всех таких векторов выполняется равенство р2 (z) = l. Мы даем подробное описание всех таких векторов, которые оказываются минимальными векторами формы р2п) (см. утв. 9.5-9.8). Кроме этого, из [2,3] известно, что число минимальных векторов sn = s((p2n)) для п 9 равно: s4 = 12, s5 =20, s6 =36, s1 =63, sg =120. В разд. 3 этого параграфа мы приводим подробное доказательство п. (/v) теоремы 9.2. А в этом разделе мы из п. (iv) теоремы 9.2 доказываем все остальные пункты, а именно - пункт (/7/) теоремы 9.2 и теорему 9.1. Основные шаги таковы. Вначале мы доказываем положительную определенность формы (р Далее пункт (/77) теоремы 9.2 является следствием утв. 9.5 — 9.8 разд. 3. Пункт (/7) теоремы 9.1 является прямым следствием пункта (/V) теоремы 9.2. Оставшийся пункт (/ ) теоремы 9.1 мы доказываем в следствии 9.1. Итак, докажем положительную определенность. Для этого предварительно докажем следующее утверждение. Лемма 9.1. Для р-рп=р{п) из (3.10), при любых п = т2 + р 5, т 2, 1 р 2т +1, выполняется неравенство Причем равенство q(n, рп) = 0 достигается лишь при четных р = 2т. Замечание 9.1. Лемма 9.1 будет использоваться нами при доказательстве положительности в части (/) теоремы 9.1 и при выводе оценок на координаты минимальных векторов формы (р (см. разд. 2). Доказательство. Для каждого из случаев, отвечающих трем различным формулам в (ЗЛО), выразим через тир величины п = т2 + р (1 р 2т + \), р = рп и подставим их в (9.2). Многочлен q(n, р) превратится при этом в функцию rj(m, р) = q(n(m, /?), рп (т, р)), которая имеет вид: Далее отдельно рассмотрим все три случая (см. (9.3)). Случай р = \, п-т1 +1. Для доказательства неравенства п(т,р) 0, достаточно показать, что для многочлена, входящего в числитель соответствующей формулы (9.3), выполняется неравенство h(m) = Ът — 4т -1 0, при всех т 2. Это следует из того, что в этом многочлене второй степени старший коэффициент 3 0 и //(1) = -2 0, а //(2) = 3 0 (см. рис.3). В точках т = \ и т = 2 функция h(m) меняет знак с "-" на "+", из чего следует положительность h{m) 0 и п(т,р) 0. Случай р - нечетное, 3 р 2т + \, п = т + р. Для доказательства неравенства rj(m,p) 0, достаточно показать, что при указанных ограничениях на р, больше нуля является соответствующий многочлен, входящий в числитель формулы (9.3). Рассмотрим этот многочлен: Далее в многочлене h(m, р) сгруппируем слагаемые первое со вторым и третье с четвертым. При этом вынесем за скобки общие множители: в первом случае т ,-во втором (р - 3). Получим: h2{т, р) = -р2 + (4т + 3)рх - 4т р. Оба многочлена hx{m,p) и h2(m,p) являются многочленами второй степени относительно переменной р со старшим коэффициентом "-1". И оба в концах отрезка 3 р 2т +1 принимают положительные значения, а при р = 0 - оба отрицательные: при всех т 0 и при всех р: 3 р 2т + 1, /;2(w,3) = 8w 0; h2{m,2m + \) = 2(2т2 + m + l) 0; h2(m,0) --4m 0. Поэтому графики функций hif / = 1,2, как функций от переменной р имеют вид, указанный на рис. 4. Из чего следуют строгие неравенства hx (w, р) 0 A2(m,/?) 0J Из (9.5) следует строгое неравенство h(m, р) 0 в (9.4). Случай р - четное, 0 р 2т + 1, п-т + р. Для доказательства неравенства /7(w, р) 0 (в этом случае неравенство не является строгим), достаточно ЭТОТ многочлен удается разложить на множители. Первый из них 2т — р при указанных ограничениях на целое четное р: 0 р 2т.+ 1, т.е. 2 р 2т является неотрицательным и достигает значения 0 только при р-2т. Покажем, что второй множитель, при рассматриваемых ограничениях на целое четное р: О р 2т +1, всегда строго больше нуля. Рассмотрим этот множитель: h (m,p) = 2m3 +(р-4)т2 +(2р + 4)т + р2 -4р-4. Далее в многочлене h {m, р) сгруппируем слагаемые первое со вторым и третье с четвертым. В первом случае вынесем за скобки общий множитель т2. Получим: h 2(m,p) = p2 +(2т-4)р + 4(т-\). При рассматриваемых в лемме 9.1 ограничениях т 2 и р: 1 р 2т + 1, всегда выполняются строгие неравенства h[(m,p) 0 и h 2(m,p) 0, из чего следует и строгое неравенство h (m, р) 0 для (9.6). Лемма 9.1 доказана. Следствие 9.1 (см. п. (/) теоремы 9.1). При любых п :4 квадратичная форма (р2п) =(р\п) - рпхххъ, где рп - из (3.10), является положительно определенной. Доказательство. Для доказательства положительной определенности формы (р достаточно доказать, что ее определитель больше нуля. Для п = 4, р = \ и непосредственной проверкой проверяем q?24) 0. Для п 4, вычисляем определитель: Доказательство. Из (ЗЛО) находим /?9 = 5/6, далее при п 9 из (9.8) следует 5/6 = р9 рп 0 и следствие 9.2 доказано. Следствие 9.3. Из условия (//) теоремы 9.1 и условия (///) теоремы 9.2 следует условие (і) теоремы 9.1. А именно: форма р2" = (р\п) — рпхххъ, где рп - из (3.10) является совершенной. Доказательство. По лемме 1.1 об отрезке, для любой формы /є[# ("); 2 )] т.е. формы / = Я(р\п) +(1-/1)ср2п), где 0 Я 1, лежащей на отрезке, определяемом второй и третьей совершенными формами, выполняется равенство min / = Я min (р\п) + (1 - Я) min р{2п) = 1. Для всех внутренних форм отрезка З } ; " значение min/ = 1 достигается на одних и тех же минимальных векторах, число которых равно s - s(f) - (п - I)2, и которые являются общими как для ср\"\ так и для (р (см. также утв. 3.2). Далее для совершенности формы ср2п\ достаточно выполнения условия Для ср (9.11) следует из (9.1). Следствие 9.3 доказано. В разд. 3 мы будем перечислять все минимальные векторы meZ" для третьей совершенной формы (р2п) Фактически это будет перечисление таких векторов, для которых р2"\т) = \. Многие из таких векторов оказываются заранее известными, и мы их указываем в этом параграфе. Для этого обратим внимание, что для любых форм вида к которым относится и третья совершенная форма ( 2"ЧХ) = /(")(Х)» Для Р Рп- где рп - из (ЗЛО)), выполняются соотношения: = Я(р\п Х) +{\-Я)ср2п-х\ гдеЯ = \-р/рп, ря-из (3.10). В последнем случае (9.13) мы полагали хп =0. К аналогичному результату мы приходим и в каждом из случаев х{ = 0, где / є {4,...,« — 1}. Причем форма (9.13) принимает тот же вид, что и форма (9.12), но только число ее переменных на единицу меньше. В силу равенств (9.13), мы получаем возможность сводить задачу о перечислении векторов meZ" - представлений минимума формы (р2 к классическим результатам Вороного [3], т.е. для меньших размерностей. Следствие 9.4 (об отрезке ] ,(Л), р2п] [). Пусть п п 4 и форма Вороного (р(2"\х) = (р[ (х) - р{п)хххъ, где р{п) = рп, рп- из (3.10), является совершенной со значением арифметического минимума min (р = 1. Тогда для любых ri п для форм вида /(л) (х) = (р\п) (х) — р(п ) х1 х3 ё\ср\п), р2п ], выполняется равенство: 1) min/(w)=l. Если р(п ) р{п), то для формы /(и) є\(р\п\(р(2\ выполняются и условия: 2)s(fM) = (n-\)2; Преобразование (9.14), ограниченное на линейные формы /2(х),...,/я(х), т.е. для /,(х) = 0 (или - что то же - х3=0), аналогично преобразованию (3.6) для размерности п — \. Эта аналогия устанавливается при помощи следующего соответствия Поэтому преобразование (9.14) переводит те минимальные векторы формы (р гп) , которые одновременно являются и минимальными векторами формы (р\п) (см. следствие 9.4), в подсистему системы векторов (3.7). Эта подсистема хорошо известна, строится по векторам из п. 3) следствия 9.4, и ей отвечает символ «большой стенки» в двухцветном символе (см. рис. 5 а), б) и утв. 10.4). Этот символ для формы (р выглядит так, как указано на рис. 6 а). На рис. 6 б) изображен символ, дополняющий первый до полного символа. В символе большой стенки, изображенном на рис. 6 а), все ребра, исходящие из вершины символа с номером 1 - "красные" и отвечают формам (х, — х()2, где / = 2,...,п. Размерность любой стенки, как гиперграни совершенной грани полиэдра Вороного, равна N{n)-2 = 2. Относительно каждого ребра символа вида (х, —xt) , как вершины грани в полиэдре Вороного, большая стенка имеет пирамидальное строение. А именно, для любой формы (х, -х,)2 большая стенка является пирамидой с вершиной пирамиды в форме (х, -х,)2 и с основанием, определяемым всеми остальными формами (xt ±х.) символа, т. е. всеми остальными ребрами символа большой стенки. 2. Совершенная грань р2п). У формы ср2"\ в случае размерностей иг [к2 -\,к2 +\,к2 +3,), п 9, имеется единственный новый минимальный вектор (9.30), т.е. такой, который не является одновременно и минимальным вектором для формы (pSf . Если п = т2+р, 1 р 2т + 1, то такой вектор в координатах //(х).(9.14) имеет вид т — 1, если р - четное , тя, если р - нечетное. Вектору ±-10 (11.1) поставим в соответствие квадратичную форму (10,х)2 =(// ,-х2-...-х„)2. (11.2) Обозначим через Vx,V2,...,Vn вершины совершенной грани р2п\ которым отвечают формы (10,х) , (л:, -х{) , і = 2,...,п, соответственно. Утверждение 11.1. Для всех размерностей п . \к2 —\,к2 + \,к2 + 3, ), п 9, совершенная грань формы (р2 является пирамидой. Основанием этой пирамиды является большая стенка совершенной грани (р\ , а вершиной пирамиды - форма, соответствующая форме (10,х)2 (11.2). Доказательство следует из утв. 9.5 и совершенности формы ср . Утверждение 11.2. Для всех размерностей п [к2 -\,к2 + \,к2 + 3,), п 9, совершенная грань формы ср2 является "п-этажной" пирамидой. Эта грань образована п вершинами (как вершинами пирамиды) Vx,V2,...,Vn, которые соответствуют формам (10,х)2, (;c, -х,)2, / = 2,...,и, а основанием пирамиды является совершенная гранью (р\п . Основанию этой пирамиды — грани (р\п в координатах /,(х) (9.14) соответствует полный двухцветный символ, построенный на вершинах символа с номерами і = 2,..., п (см. рис. б). Доказательство следует из утв. 11.1 и из пирамидальной структуры строения большой стенки. Утверждения 11.1 и 11.2 позволяют следующим образом изобразить совершенную грань формы р2п) (см. рис. 7). В работе [3] Г.Ф. Вороной построил теорию совершенных форм. Он доказал, что в каждой размерности п 2 существует лишь конечное число классов эквивалентности таких форм. Для « = 2,3,4,5 он перечислил все классы совершенных форм, которых оказалось, соответственно 1,1,2 и 5. В дальнейшем, все совершенные формы были перечислены: для /7 = 6 - в [13] - их оказалось 7; для /7 = 7 -в[14]-их оказалось 33. Известно также, что все совершенные формы перечислены и для и = 8, где их оказалось около одного миллиона. Кроме исследований для п 6, Вороной для всех размерностей п 6 провел первые два шага своего общего алгоритма по перечислению совершенных форм. А именно, он конструктивно описал строение первой и второй совершенных граней, отвечающих формам р п) и р\п). То есть для каждой размерности Вороной исследовал всего лишь по две формы. С учетом того обстоятельства, что уже для /7 = 8 количество совершенных форм оказалось очень большим, » результаты Вороного в [3] могли быть восприняты как «малая часть от общего объема». Это также дало основания считать, что в отношении практических вычислений, Вороной реализовал свой алгоритм «лишь в є-окрестности второй совершенной грани». Наши исследования приводят к следующим выводам 1. Результаты Вороного относительно строения второй совершенной грани один-в-один приложимы к исследованию и других совершенных граней (например, W„ и Tw). 2. Описание строения других совершенных граней удается сводить к результатам Вороного о строении второй совершенной грани. Эти наблюдения подводят нас к следующему взгляду на результаты Вороного об окрестности второй совершенной формы, которые диаметрально противоположны тому взгляду, что это «лишь в с -окрестности». И мы ставим следующий, важный с нашей точки зрения Вопрос. А не есть ли результаты Вороного о строении второй совершенной грани «вся теория целиком»! В стремлении получить ответ на этот вопрос, мы предпринимаем дальнейшие исследования.Основная задача и роль метода проективных неравенств
Вариации и оценки
Исследование третьей совершенной формы ср^ Г.Ф.Вороного
Описание строения окрестности Г.Ф. Вороного для третьей совершенной формы ср^р для п [к2 - \,к2 + \,к2 +3,)
Похожие диссертации на Метод проективных неравенств и совершенные формы
