Приведение по Коркину-Золотареву положительных квадратичных форм от n<=8 переменных (области и алгоритмы) тема диссертации и автореферата по ВАК РФ 01.01.04, кандидат физико-математических наук Новикова, Н.В.

• Новикова, Н.В.
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Новикова, Н.В.

Введение.

Глава I. Конечность числа неравенств, задающих области приведения.

§ I. Задача приведения.

§ 2. Приведение положительных квадратичных « форм по Коркину-Золотарёву.

§ 3. Неравенства приведения,возможность их выбора в конечном числе, области приведения

Глава П. Области и алгоритмы приведения для форм от 2-х и 3-х переменных.

§ I. Область приведения*^ и алгоритмOV^ •

§ 2. Область приведения Ж>3 и алгоритм Ot

Глава Ш. Общие вопросы строения и вывода областей и алгоритмов приведения по Коркнну-Золо-тарёву.

§ I. Преобразование И( {.

§ 2. Некоторые свойства разложений по Лангранжу положительных квадратичных форм

§ 3. Общая схема строения систем М^. Некоторые свойства неравенств из систем М^ при п * 8.

§ 4. Алгоритм при п £ 8: общая схема и доказательство конечности

Глава 1У.Построение областей и $CS.

§1. Область приведения Ж^ и алгоритм^.

§ 2. Область приведения

Глава У. Системы м п, при tb = 6,7,

§ I. Построение системы Ms.

§ 2. Система

§ 3. Построение системы Ms.

Заключительные замечания

Введение диссертации (часть автореферата) на тему «Приведение по Коркину-Золотареву положительных квадратичных форм от n<=8 переменных (области и алгоритмы)»

Большинство проблем геометрии положительных квадратичных форм исследуется и решается такими путями, которые требуют выбора некоторого способа целочисленного унвмояулярного приведения. Настоящая диссертация посвящена одному из таких способов -приведению по Коркину-Золотарёву. Для положительных квадратичных форм от трёх переменных это приведение было предложено в 1869 голу в магистерской диссертации Е.И. Золотарёва [i] , а для квадратичных форм от произвольного числа переменных - в совместной работе А.И. Коркина и Е.И. Золотарёва Г2], опубликованной в 1873 году.

До работ С 1,2] задача приведения положительных квадратичных форм рассматривалась 1&уссом [5J , Лагранжем [4j, Зеебе-ром [б], Эрмитом [6aJ . В работах [4] , [5] , И вопрос о приведении был решён, т.е. были разработаны некоторые определённые способы приведения, для форм 2-х и 3-х переменных. В работе [баЛ был предложен способ приведения, пригодный для положительных квадратичных форы произвольного числа переменных.

Приведение по Коркину-Золотарёву было использовано его авторами [2,3] для отыскания особых классов положительных квадратичных форм, представителей которых они назвали предельными формами. В работах [2,3] Коркин и Золотарёв нашли ряд важных соотношений между коэффициентами приведённых форм, вывели предельные формы от я- ^ 5 переменных и, как следствие последнего, получили для л-£5 значения постоянной Эрмита .

Изложение в работах Г2,з] велось ещё чисто арифметически. В дольне шлем, когда теория положительных квадратичных форм нашла приложение в геометрии решёток, методы Коркина и Золотарёва, развитые в работах Г2,з], сделались, и продолжают оставаться, одними из основополагающих в проблеме решётчатых упаковок равных шаров в пространствах Е (см. обзоры [7,8.1^.

На языке решёток предельный формам от п* переменных соответствуют ги - мерные решётки, на которых достигаются локальные максимумы плотности решётчатых упаковок равных шаров в пространстве Е , а по постоянной Эрмита выводится значение абсолютного максимума такого рода плотности. Таким образом, в работах [2,з] дано решение задачи о наиболее плотных решётчатых упаковках при

Впоследствии методы работ [2,3] были приложены и развиты для более высоких размерностей БЛихфельдтом, который нашёл £э] значения постоянной Эрмита при А- = 6,7,8 и тем самым решил задачу о наиболее плотных решётчатых упаковках в пространствах £ , , Е .К работе [9 J тесно примыкает недавняя статья Н.М. Ветчинкина [ю], где доказана единственность классов положительных квадратичных форм от /г- переменных, на которых достигаются значения]^, 6,7,8. Таков краткий перечень наиболее значительных результатов и работ, фундаментально опирающихся на приведение по Коркину-Золотарёву.

За время развития теории положительных квадратичных форм, сначала в арифметическом изложении, а затем как геометрии положительных квадратичных форд, были предложены и для некоторых, сравнительно небольших значений It в большей или меньшей степени детально разработаны многие способы приведе-' ния: приведение Эрмита, Минковского, Вороного, Зеллинга-Шарва (см. обзоры Cei,8], статьи [l2,I3]). В 1940 г. Б.А. Венков [14] (см. также [13J) открыл общий метод для построения при

- 6 ведений одного специального вида.

К настоящему времени одним из наиболее далеко продвинутых, как по величине значений lb , так и по детальности разработки, является приведение по Минковскому; области и алгоритмы этого приведения, не требующие перебора точек решётки, найдены при всех/t^7 (Минковский [15-18], С.С. Рынков [19 J, П.П. Там-мела [20,2l]J, некоторые из областей приведения исследованы очень подробно (Варне и Кон [22J, Рышков и Кон [23], Рышков, Кон и З.Д. Ломакина [24]). Б последние годы довольно много работ посвящено предложенному Г.Ф. Вороным [25] приведению по совершенным формам (Рышков [2б] , Стаей [27] , Ломакина [28,29]; см. также обзор [в]), найдены область и алгоритмы приведения по Зеллингу-Шарву при Ц=5 (е.П. Барановский [30]) , для vl~ Ъ рассмотрены некоторые из приведений Венкова (Рышков [13]).

В отличие от всех других перечисленных выше способов приведения, в случае приведения по Коркину-Золотарёву вопрос отыскания областей приведения, исключая почти тривиальный случай /t= 2, насколько нам известно, ни в каких публикациях не рассматривался. (Возможно, причиной этого была нелинейность задающих области приведения по Коркину-Золотарёву неравенств, которая позволяла предполагать трудность привлечения этих областей к решению задач геометрии положительных квадратичных форм. В других исследованных способах приведения их области приведения в пространстве коэффициентов форм задаются только линейными неравенствами).

Другим недостатком теории приведения по Коркину-Золотарёву было то, что известный алгоритм этого приведения (см., например [II]) базировался на переборах точек решётки, соответствующей приводимой положительной квадратичной форле.

С.С. Рышков поставил перед автором настоящей диссертации задачу об отыскании областей приведения по Коркину-Золотарёву при ^>3 и о построении такого алгоритма приведения в эти области, который был бы в той же мере удобен для пользования, как, например, алгоритм приведения по Минковскому при /г-£7. Позднее аналогичные вопросы были сформулированы в книге Кас-седса [3lJ. Полученные при решении этой задачи результаты и легли в основу предлагаемой диссертации.

Известный алгоритм приведения по Коркину-Золотарёву, если его высказать на геометрическом языке приведённых реперов решётки (см. [ll]), заключается в следующем. В решётке Q. , соответствующей приводимой форме /(к*ос^ ) j в качестве первого вектора €< приведённого репера выбирается один из минимальных векторов решётки /J . Затем решётка /J проецируется Ha(V- ij - мерное линейное подпространство, ортогональное — * п («--о вектору ив полученной проецированием решётке Л» выбирается один из её минимальных Еекторов . Среди векторов решётки Q , проекцией которых является вектор

- , в качестве второго вектора ^ приведенного репера берётся самый короткий, причём образующий с вектором неострый угол. .Здлее решётка проецируется на (н*- 2) -мерное линейное подпространство, ортогональное векторам и , в проекции i j. решётки // на это подпространство выбирается один из минимальных векторов е5 , и среди векторов решётки // , проекцией которых являются векторы

- ^з , б качестве третьего вектора приведённого репера берётся тот из самых коротких, который образует с вектором неострый угол. Аналогичный способом выбираются и остальные векторы приведённого репера. Аналитическое описание этого алгориша можно найти в [8]. Неудобство алго - (н-/) ритма заключается в том, что для отыскания векторов , t,

-(JL) > ь-/ приходится выбирать некоторые конечные множества целых точек (ос^.^ ос*^ ), с f заведомо содержащие минимальные Бекторы, а затем посредством перебора точек в каждом из таких множеств находить представления минимума соответствующей формы.

При аналитическом выполнении алгоритма приведения по Коркину-Золотарёву наиболее удобно рассматривать квадратичные формы

Хн.) - ZT/^v ХС OCj 9 (0.1) записанными в виде разложений по Лагранжу ffx*,., Х^)^ - i^v Xjf. (0.2)

J - «V/

Представление положительной квадратичной формы в виде (0.2 j принято и в настоящей диссертации, и поэтому области приведения выбираются в пространстве коэффициентов сС,*,,.,, таких разложений, а не в пространстве коэффициентов форм как делается при других способах приведения.

Установлено, что при любом данном натуральном п ^существует конечная зависящая от *ь> система М-^ неравенств, наложенных на коэффициенты ^^ - ^ ^ разложения (0.2,/, которая представляет собой совокупность необходимых и достаточных условий того, что положительная квадратичная форма (ОЛ), записанная в виде разложения по Лагранжу(0.2), приведена по Коркину-Золотарёву. Эти неравенства двух видов -линейные неравенства г ; - £ - ^ -z >г* Со.з) наложенные на "внутренние" коэффициенты разложения ф.ф, и неравенства вида ( система М ^ ) ф.:. = Г// )

Ь г с е { i-fjj /с elJ , где строка (gc, .v J пробегает при данном А- некоторое конечное зависящее лишь от множество наборов целых значений. Следовательно, граница области образована конечнш числом <)- мерных плоскостей и поверхностей 3-его порядка.

Основные результаты диссертации:

1. Для всех размерностей а* - 8 системы неравенств М ^ получены в явном виде. Для каждого из п- £ 5 доказано, что полученная система М ^ минимальна - среди её неравенств нет ни одного, которое было бы следствием остальных неравнств этой системы и линейных неравенств.

2. Построены алгоритмы приведения в области Ж^ , основанные на использовании систем Мн, и не требующие перебора точек решётки.

Отметим, что те методы, посредством которых получены перечисленные результаты могут быть использованы и в более высоких размерностях.

Кратко изложим содержание диссертации по главам: Глава I "Конечность числа неравенств, задающих области приведения" является вводной. Первые два параграфа этой главы содержат достаточно широко известные сведения о задаче приведения в геометрии положительных квадратичных форм и, в частности, о приведении по Коркину-Золотарёву. Далее в §3, в те ореме I.I устанавливается, что при любом данном натуральном п- существует конечная, зависящая от ^ система неравенств, образующих совокупность необходимых и достаточных условий того, что положительная квадратичная форма J-fXi, .j Хи,)^ записанная в виде её разложения по лагранжу, приведена по Коркину-Золотарёву.

Отметим, что при предложенном ниже в диссертации конкретном построении системы М hs среди её неравенств мо1ут оказаться и необязательные, являющиеся следствиями неравенств списка (0.3J и других неравенств этой системы, то есть получается хотя и конечная, но не минимальная система.

Глава П "Области и алгоритмы приведения для форм от 2-х и 3-х переменных" содержит вывод областей приведения JC^ , «^j и алгоритмов приведения для форм от 2-х и 3-х переменных, проведённый независимо от построения общей теории и выполненный с большими подробностями. Такое выделение случаев = 2,3, по нашему мнению, позволяет сделать чтение работы более удобным, так как теория построения областей и алгоритмов приведения по Коркину-Золотарёву при фиксированных ^ уже сама по себе просматривается в этих случаях, в особенности в случае 3. Кроме того, всего вероятнее, что именно случаи = 2 и 3 прежде других могут потребоваться в приложениях.

Для случая форм от 2-х переменных показано, что минимальная система М ь состоит только из одного неравенства

Таким образом, вся система , задающая область , состоит всего из трёх неравенств: названного вше и неравенств Оё ^ ^ вида (О.ЗЗ . Отметим, что в пространстве /& У коэффициентов форм области Хд,с & 3 соответствует область, эквивалентная области приведения по Лагранжу 0 - ^^^ Естественно, что и алгоритм ^ju приведения форм от двух переменных по Коркину-Золотарёву по существу оказался совпадающим с алгоритмом приведения по Лагранжу.

Если случай = 2 ещё мало показателен для специфики приведения по Коркину-Золотарёву, то при = 3 уже видны характерные черты построения теории в случае произвольного :

1) способ получения системы М и, , основанный на разделении её неравенств на те, что являются следствиями неравенств приведения в меньших размерностях, и на неравенства, впервые появляющиеся при данном ^ ;

2) способ доказательства минимальности системы А1*. ;

3) выделение в алгоритме приведения ^^.преобразований, приводящих к выполнению серии неравенств (о.з) , и преобразований, приводящих к выполнению неравенств системы М ;

4) способ доказательства конечности алгоритма ОЬ*, .

В § I главы Ш "Общие вопросы строения и вывода областей и алгоритмов приведения по Коркину-Золотарёву" дано описание целочисленного унимолулярного преобразования посредством которого данная положительная форма / , заданная в виде разложения по Ланранжу, переводится в эквивалентную ей форму, для которой условие приведения (о.з) выполнены, а коэффициенты ., Лразложения остались теми же, что и у форш / .

В §§ 2-4 получены важные свойства систем неравенств М и, при произвольном и^ , а также специфические свойства этих систем для случаев к- - 8. В следующих главах на базе этих свойств строятся конкретные системы Ми, (а * ^ £ s) и проводятся доказательства минимальности систем Mi, , Ms .

В § 5 главы Ш содержится описание для ^ £ 8 общей схемы алгоритма ОЬи, приведения по Коркину-Золотарё ву и доказательство его конечности. Основным в этом новом алгоритме приведения является то, что каждому из неравенств системы м к- сопоставляется преобразование W , переводящее форму £ , для которой это неравенство не выполняется, в эквивалентную ей форму т , для которой оно выполнено. Алгоритм fft^ не требует переборов точек решётки и составлен из шагов трёх видов: ij запись приводимой формы / в виде разложения по Лагравд; ^

2) выполнение преобразования Us ;

3) проверка выполнения неравенств системы Af/t- и выполнение преобразования W , сопоставленного не выполненному неравенству системы At ^.

Глава ЗУ 'Построение областей и " посвящена выводу, на основе общей теории главы Ш, минимальных систем М iv в случаях форм от 4-х и 5-ти переменных и конкретизации соответствующих алгоритмов . Оказалось, что система Мц состоит из 21 неравенства, из которых 9 неравенств вытекают из систем М^и М3, а 12 - существенно новые, характерные .для размерности п> = 4. Система М5состоит уже из 89 неравенств, из которых существенно новых 52. При доказательстве минимальности построенной системыМ^, ввиду громоздкости вычислений, была использована ЭВМ. Программа этих вычислений и их результаты даны в Приложении к .диссертации.

В главе У, последней, проведен вывод систем М^для размерностей 6,7,8. Систему Мg составили, во-первых, 157 неравенств, вытекающих из системMs и, во-вторых, 408 новых, появляющихся только начиная с размерности Н* = 6, неравенств. Доказательство минимальности построенных систем.: Mt'Mgне проводилось, поэтому число новых неравенств у минимальной системы Меокажется, возможно, и меньшим, чем 408. В еще большей степени это замечание относится к числу неравенств систем Мь Mf .

В "Заключительных замечаниях" рассмотрены некоторые вопросы связанные с перспективами расширения исследований данной диссертации на большие размерности.

Основные результаты диссертации опубликованы в статьях [32] и [33] . Они докладывались на Всесоюзной школе по теории чисел (г.Душанбе, 1977), Всесоюзном симпозиуме по теории симметрии и ее обобщением (г.Кишинев, 1980) £35] , некоторые из результатов .диссертации включены в обзорную статью [8] .

Диссертация выполнена в Ивановском государственном университете .

Автор пользуется случаем выразить глубокую признательность С.С. Рышкову и ЕЛ. Барановскому за предложенную тему, постоянное внимание и ценные советы во время работы над диссертацией.

Список литературы диссертационного исследования кандидат физико-математических наук Новикова, Н.В., 1984 год

1. Е.И.Золотарёв. Об одном неопределенном уравнении третьей степени. - Магистерская диссертация, 1869, .(см.также За).

2. A.Korkine, G.Zolotareff. Sur les formes quadratiques. -Math.Ann.I873, 6, 366-389 (см.также За).

3. A.Korkine, G.Zolotareff. Sur les formes quadratiques positives. Math. Ann., 1877,11, 242-292 (см.также За).За. Е.И.Золотарёв. Полное собрание соч.,вып.I, Изд-во А.Н., 1931 г.

4. L.У.Lagrange. Recherches d'arithmetique. ETeuveaux Memoires de I'Academie royal des Sciences et Belles-Lettres de Berlin.1973, 265-312см.также Oeu-Vvts , щ, 693-758).5. k.F.Gauss. Disquisitiones arithmetical. Werke, Bd.I,art. 171, S.X46.

5. Б.Н.Делоне. Геометрия положительных квадратичных форм. -У.М.Н. 1937, вып. 3,16-62, 1938, вып.4, 102-164.

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

7. H.F.Blichfeld. The minimum values of positive quadratic о forms in six , seven and eight Variables . .Math. Zeitsch., 1934-5,39,1-15.

8. Н.М.Ветчинкин. Единственность классов положительных квадратичных форм от ^переменных, на которых достигаются значения ^ (при п- =6,7,8). Труды МШШ СССР им. В.А.Стеклова, 152,1979.

9. B.L. van der Waerden. Die Reduktionstheorie derquadratischen Formen. Acta mathem., 1956,96,265.309; 1957, 98, 3-4,

10. С.С.Рышков. 0 приведении положительных квадратичных формот переменных по Эрмиту, по Мянковскому и по Венкову.- ДАН СССР, 1972, 207, № 5, 1054-1056.

11. С.С.Рышков. 0 приведении положительных квадртичных форм по Венкову. Учён.зап.Ивановского ун-та, 1974, 89, 5-36.

12. Б.А.Венков. 0 приведении положительных квадратичных форм.- Изв.АН СССР, серия матем., 1940, 4 , Ж, 37-52.

13. Н.Minkowski. Sur la reduction des formesquadratiques positives quaternaires . - Compl. Rend. Acad. Sei. , 1883,95,1205-1210.

14. H.Minkowski. Uber positive quadratische Formen .J. reine und angew. Math. , 1886,99,1-9.

15. С.С.Рышков. К теории приведения положительных квадратичных форм по Эрмиту-Минковскому. -Исследования по теории чисел. 2. (Записки научных семинаров ЛОМИ,33), 1973, 37-64.

16. П.П.Таммела. Область Эршта-Минковского приведения положительных квадратичных форм от шести переменных.- Исследования по теории чисел. 2. (Записки научных семинаров ЛОМИ, 33), 1973, 72-89.

17. П.П.Таммела. Область приведения Минковского для положительных квадратичных форм от семи переменных. Исследования по теории чисел. 4. (Записки научных семинаров ЛОМИ, 67), 1977, 108-143.

18. B.S.Barnes, M.J.Cohn. Ou Minkowski reduction ofpositive quarternary quadratic formes. Mathematika, 1976,23,156-158.

19. С.С.Рышков, М.Дж.Кон. К теории строения области приведения Минковского. Труды матем.ин-та им.В.А.Стеклова, 1980, 152.

20. С.С.Рышков, М.Дж.Кон, З.Д.Ломакина. Вершины симметризо-ваннои области Минковского при п>£5. Труды матем.ин-тв им.В.А.Стеклова, 1980, 152.

21. G.Torovoi. Sur quelques proprietes des formesquadratiques positives parfaites . -J.reine und qngew. Math. ,1908, 133,97-178.-

22. С.С.Рышков. К проблеме отыскания совершенных квадратичныхформ от многих переменных. Трубы матем.ин-та им.В.А.Сте(к-лова АН СССР, 1976, 142, 215-239.

23. K.C.Stacey. The enumeration of perfect septenary forms.J .London Math. Soc,,1975, 10, 97-104.

24. З.Д. Ломакина. Полиэдр Вороного П (л) при fb-Ъж максимальные конечные группы целочисленных 5x5 матриц. -Труды матем. ин-та им.В.А.Стеклова АН СССР, 1980, 152, I38-I6I.

25. З.Д.Ломакина. Исследование граней полиэдра Вороного с приложениями к геометрической кристаллографии и теории приведения. Диссертация, Москва, 1980.

26. Е.П.Барановский. Область приведения по Зеллингу положительных квадратичных форм от пяти переменных. Труды матем.ин-ститута mi.В.А.Стеклова, 1980, 152, 5-33.

27. J.W.S.Cassels. Rational quadratic forms . -L.,N.,Y., San Francisco: Acad., Press. , 1979 (русский перевод: Дж.Касселс. Рациональные квадратичные формы. -Москва "Мир", 1982).

28. Н.В.Захарова (Новикова). Об одной системе условии того,что положительная квадратичная форма приведена по Коркину-Золотарёву. Тез.докл. и сообщ.Всесоюзной школы по теории чисел, Душанбе, 1977, 44.

29. Н.В.Новикова. Новый алгоритм приведения положительных квадратичных форм в область Коркина Золотарева. - Тез. докл.Всесоюзного симпозиума по теории симметрии и ее обобщениям, Кишинев, 1980, 85-86.