«Статистические свойства полиэдров Клейна и локальных минимумов решеток ...»

Хабаровское отделение Федерального государственного бюджетного

учреждения наук

и Института прикладной математики

Дальневосточного отделения Российской Академии наук

На правах рукописи

Илларионов Андрей Анатольевич

Статистические свойства

полиэдров Клейна и

локальных минимумов решеток

01.01.06 — математическая логика, алгебра и теория чисел

Диссертация на соискание ученой степени доктора физико-математических наук

Научный консультант:

д.ф.-м.н., чл.-корр. РАН Быковский В.А.

Хабаровск – 2014 Оглавление Предисловие Обозначения и соглашения Введение § 1. Актуальность темы.............................. § 2. Основные определения............................ § 3. Основные результаты............................. I. Оценки максимального количества локальных минимумов Глава § 1. Вспомогательные оценки........................... § 2. Оценки количества относительных минимумов.............. § 3. Оценки количества локальных минимумов................. II. Асимптотическое распределение целочисленных матриц Глава § 1. Формулировка основного результата..................... § 2. Вспомогательные результаты......................... § 3. Вычисление некоторых сумм......................... § 4. Доказательство теоремы 1.1......................... III. Среднее количество относительных минимумов Глава § 1. Двумерный случай............................... § 2. Трехмерный случай.............................. § 3. Случай произвольной размерности..................... Оценки постоянной ().............

§ 4................ IV. Статистические свойства многогранников Клейна Глава § 1. Оценки количества элементов многогранников Клейна.......... § 2. Среднее количество граней фиксированного типа............. § 3. Среднее количество вершин......................... Г л а в а V. Среднее количество цилиндрических минимумов и наилучших приближений линейных форм § 1. Базис Вороного и его свойства........................ § 2. Среднее количество цилиндрических минимумов.............. § 3. Среднее количество наилучших приближений линейных форм..... VI. Среднее количество локальных -минимумов Глава § 1. Дополнение локального минимума до базиса: частные случаи...... § 2. Дополнение локального минимума до базиса................ § 3. Среднее количество локальных минимумов................ Приложения § 1. Приложение к главе V............................. § 2. Приложение к главе VI............................ Литература Предисловие В конце 19 века были предложены два обобщения алгоритма непрерывных дробей на многомерный случай. Одно Ф. Клейном, а другое Г.Ф. Вороным и независимо от него Г. Минковским. Они основаны на рассмотрении полиэдров Клейна и, соответственно, локальных минимумов решеток. Ряд задач теории чисел (построение основных единиц числовых полей, нахождение наилучших приближений, оценки погрешности теоретико-числовых квадратурных формул и отклонений сеток от равномерного распределения) приводят к исследованию этих конструкций. Статистические свойства локальных минимумов и полиэдров Клейна двумерных решеток непосредственно вытекают из теории непрерывных дробей. Однако, несмотря на значительный интерес, практически отсутствуют результаты для решеток размерности три и выше. Восполнению этого пробела и посвящена настоящая работа.

В диссертации разработан метод исследования статистических свойств многомерных непрерывных дробей по Клейну и Вороному – Минковскому. Он позволил ответить на некоторые вопросы В.И. Арнольда о свойствах полиэдров Клейна и получить ряд асимптотических формул для средних характеристик локальных минимумов, которые можно рассматривать, как многомерные обобщения классических результатов о вероятностных свойствах цепных дробей. К основным можно отнести следующие результаты диссертации.

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

2. Впервые изучено поведение в среднем количества локальных минимумов многомерных целочисленных решеток. А именно, получена асимптотическая формула для среднего числа локальных минимумов целочисленных многомерных решеток с определителем из заданного отрезка. Также доказано многомерное обобщение классической теоремы Хейльбронна о средней длине конечной непрерывной дроби в терминах относительных минимумов.

3. Получены асимптотические формулы для среднего числа граней фиксированного типа и вершин полиэдров Клейна трехмерных целочисленных решеток фиксированного определителя.

4. Выведены асимптотические формулы для среднего числа наилучших приближений линейных форм с рациональными коэффициентами и математического ожидания количества наилучших приближений форм с вещественными коэффициентами.

Обозначения и соглашения Главы диссертации разделены на параграфы, нумерация которых начинается заново в каждой главе. Формулы -го параграфа любой главы нумеруются (n.1), (n.2), (n.3) и т. д. (номер главы не указывается). Аналогичная нумерация используется для теорем, лемм, следствий и замечаний. При ссылке на формулу (теорему, лемму и т.д.) других глав указывается номер этой главы. Считаем, что введение это глава с номером 0, а приложение глава с номером A. Например, теорема V.1.1 это теорема 1.1 из главы V, формула (0.1.1) это формула (1.1) из введения, лемма A.2.1 это лемма 2.1 из приложения.

На протяжении всей диссертации используются следующие обозначения:

# количество элементов конечного множества ;

множество неотрицательных целых чисел;

множество положительных вещественных чисел;

() дзета-функция Римана;

GL (R) множество невырожденных матриц из M (R);

GL (Z) множество унимодулярных матриц из M (Z);

если не указано противное, то элементы матрицы обозначаем через ( номер строки, номер столбца);

Через, (R) обозначаем множество всех -мерных вещественных решеток ранга ( ). Любая решетка, (R) имеет вид где (1),..., () некоторые линейно-независимые векторы из R (базис ). Матрицу со столбцами (1),..., () будем называть базисной. Если =, то решетка называется полный, если <, то неполной. Модуль определителя базисной матрицы полной решетки называется определителем решетки и обозначается det.

Используем следующие обозначения, связанные с решетками:

, (Z) множество целочисленных решеток из, (R);

Запись означает, что существует такая абсолютная постоянная > 0, что для любого имеет место оценка | ()| · (). Если зависит от параметра, то пишем Гиперповерхность R называем кусочно-дифференцируемой, если она состоит из фиксированного числа гиперповерхностей класса 1.

Множество R называем конусом, если для всех R+,.

Функция : R R называется лучевой, если для всех R {0}, R Введение § 1. Актуальность темы Любое вещественное единственным образом раскладывается в непрерывную (цепную) дробь:

где 0 = [] (целая часть) и = () N (неполные частные). Она конечна только для рационального / = [0 ; 1,..., ] и в этом случае накладываем дополнительное условие: 2. Несократимая дробь называется -й подходящей для.

Алгоритм разложения вещественного числа в непрерывную дробь является одним из важнейших инструментов теории чисел, восходящим еще к античному алгоритму Евклида нахождения наибольшего общего делителя. Начало современной теории непрерывных дробей положил в 1613 г. П. Катальди и продолжил Д. Валлис, предложивший термин непрерывная дробь. Применялись эти дроби в первую очередь для рационального приближения вещественных чисел; например, Х. Гюйгенс использовал их для проектирования зубчатых колес своего планетария. Алгоритм цепных дробей занял видное место в теории чисел после трудов Л. Эйлера и Ж. Лагранжа, которые применили его к решению уравнения Пелля, что привело к пониманию фундаментальной роли непрерывных дробей в теории квадратичных иррациональностей.

Эйлер открыл, а Лагранж доказал одно из важнейших свойств: непрерывная дробь периодична только у квадратичных иррациональностей. Лагранж также доказал следующее основополагающее свойство рациональных приближениях вещественных чисел.

Напомним, что дробь / ( Z, N) называется наилучшим приближением (второго рода) вещественного, если не существует дроби / ( Z, N) такой, что причем хотя бы одно из неравенств является строгим.

Теорема (Лагранж). Для любого [0, 1) а) любая подходящая дробь для есть наилучшее приближение, за исключением б) любое наилучшее приближение есть подходящая дробь, за исключением случая = 1/2, / = 1/1.

Исследование иррациональностей степени три и выше, а также поиск многомерных наилучших приближений привели к необходимости обобщения цепных дробей на многомерный случай.

Первое формальное обобщение алгоритма непрерывных дробей было дано еще Эйлером [94], идеи которого развивали и дополняли К. Якоби, А. Пуанкаре, П. Бахман, О. Перрон и другие авторы. Следующий этап начал Л. Дирихле, а продолжили Л. Кронекер, Ш. Эрмит, Шарв, Е. Золотарев, которые пытались построить обобщение непрерывной дроби, имеющее для общей теории алгебраических чисел такое же значение, какое имеют цепные дроби для квадратичных числовых полей. Черту под этими исследованиями подвел Г.Ф. Вороной. В 1896 г. он защитил диссертацию Об одном обобщении алгорифма непрерывных дробей, в которой дал метод нахождения основных единиц кубического числового поля как положительного, так и отрицательного дискриминанта. Алгоритм основан на рассмотрении взаимного расположения некоторых специальных узлов решеток. Эти узлы Вороной называл относительными минимумами. Одновременно и независимо от Вороного минимумы трехмерных решеток изучал Г. Минковский [125, 126], который использовал термин локальный минимум (исследования Минковского относятся к случаю чисто вещественного расширения числового поля). Относительные (локальные) минимумы решеток представляют собой геометрическую интерпретацию многомерных наилучших приближений. Они являются естественным объектом с точки зрения целочисленного линейного программирования, а также возникают при изучении теоретико-числовых квадратурных формул [10, 11] и в теории равномерного распределения [15, 73].

Еще одно интересное геометрическое обобщение непрерывных дробей было дано Ф. Клейном [111] и основано на рассмотрении, так называемых, полиэдров (многогранников) Клейна, которые определяются как выпуклая оболочка узлов решетки, лежащих в заданном симплициальном конусе. Исходно исследуя -градуированные алгебры [78], В.И. Арнольд столкнулся с полиэдрами Клейна. Начиная с 1989 г. он сформулировал множество задач о геометрических и статистических свойствах многомерных непрерывных дробей (см. [3, 4, 79, 80]), возобновляя тем самым интерес к этим вопросам.

В двумерном случае конструкции Клейна и Вороного – Минковского совпадают, и их статистические свойства непосредственно вытекают из теории непрерывных дробей. Однако, несмотря на значительный интерес, практически отсутствуют результаты для решеток размерности три и выше. Целью настоящей работы является исследование статистических свойств полиэдров Клейна и локальных минимумов многомерных решеток.

§ 2. Основные определения Локальные минимумы Определение 2.1. Ненулевой узел -мерной решетки будем называть относительным минимумом, если не существует ненулевого узла такого, что причем хотя бы одно из неравенств является строгим.

Возьмем любую неотрицательную функцию : R1 [0, +).

Определение 2.2. Ненулевой узел -мерной решетки будем называть цилиндрическим -минимумом, если не существует ненулевого узла такого, что причем хотя бы одно из неравенств является строгим.

С геометрической точки зрения, это означает, что цилиндр не содержит ненулевых узлов, за исключением точек, лежащих на границах оснований цилиндра. В дальнейшем, мы ограничимся случаем, когда функция является лучевой и кусочно-дифференцируемой.

Рассмотрим теперь более общую конструкцию, включающую в себя и относительные, и цилиндрические минимумы. Пусть = (1,..., ) : R [0, +).

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

Далее всюду считаем, что функции имеют следующий вид:

а : R R ( = 1, = 1, ) лучевые, непрерывные, кусочно-дифференцируемые функции.

Локальные -минимумы совпадают с относительными, если и с цилиндрическими, если Локальные минимумы и единицы числовых полей. Пусть чисто вещественное расширение степени поля рациональных чисел Q. Обозначим через 1,..., базис, состоящий из целых поля. Пусть 1,..., сопряженные базисы ( = 2, ), а порядок поля с базисом 1,...,. Для каждого определим геометрическое изображение () = (1 (),..., ()) числа по формуле Пусть решетка состоит из узлов (), где. Для любого число 1 ·...· является целым. Следовательно, Поэтому, если узел = () удовлетворяет условию |1 ·... · | = 1 (т.е.

единица поля ), то он является относительным минимумом решетки.

В общем случае геометрическое изображение (определение см. в [29, с. 29]) единицы числового поля степени = 1 + 22 (1 количество вещественных, а количество комплексных изоморфизмов в C) является локальным -минимумом некоторой -мерной решетки, если положить Г.Ф. Вороной [19, 20] построил алгоритм вычисления относительных и цилиндрических минимумов трехмерных решеток и с его помощью разработал метод нахождения единиц в кубических полях положительного и отрицательного дискриминанта соответственно. Одновременно и независимо от Вороного относительные минимумы трехмерных решеток изучал Г. Минковский [124, 125] в связи с этими же вопросами. По поводу дальнейшего развития алгоритмов Вороного, Минковского и их обобщений на случай более высоких размерностей см., например, работы [82, 83, 84, 85, 86, 87, 90, 89, 131, 134] и ссылки там. Алгоритмы Вороного и Минковского нахождения единиц чисто вещественного расширения числового поля основаны на изучении взаимного расположения, так называемых, минимальных базисов решеток (составленных из относительных минимумов), при этом ряд важных свойств был сформулирован ими без доказательства. Доказательство, обсуждение, переизложение и дополнение оригинальных результатов Вороного и Минковского можно найти в [32, 95, 97, 130, 18].

Локальные минимумы и наилучшие приближения. Для любого вещественного определим решетку Пусть M( ) множество относительных минимумов этой решетки. По определению, M( ) состоит из ±(0, 1) и точек вида ±(, ), где / наилучшее приближение. Поэтому согласно теореме Лагранжа, где 1 = 1, 1 = 0 и / -я подходящая дробь для при = 0, 1, 2,....

Рассмотрим теперь многомерные обобщения понятия наилучшего приближения.

Возьмем любую неотрицательную функцию : R [0, +).

Определение 2.4. Ненулевой вектор (, ) Z Z будем называть -наилучшим приближением линейной формы : R R, если не существует ненулевого вектора причем хотя бы одно из неравенств строгое.

Определение 2.5. Вектор (, ) N Z будем называть -наилучшим совместным приближением вещественных 1,...,, если и не существует другого натурального такого, что причем хотя бы одно из неравенств строгое. Здесь = (1,..., ), расстояние от вещественного до ближайшего целого.

Возьмем теперь две неотрицательные функции: : R [0, +) и : R [0, +), а также набор линейных форм L = (1,..., ) : R R.

Определение 2.6. Ненулевой вектор (, ) Z Z будем называть (, )-наилучшим совместным приближением линейных форм L, если не существует ненулевого вектора (, ) Z Z такого, что причем хотя бы одно из неравенств строгое.

Отметим, что вместо термина наилучшее совместное приближение линейных форм L часто используют наилучшее приближение матрицы, где -я строка составлена из коэффициентов линейной формы (см., например, [61]).

Наилучшие приближения неявно использовались еще Г.Ф. Вороным [19, 20], В. Ярником [77, 100, 101, 102] и другими авторами. По-видимому, систематическое изучение многомерных наилучших приближений было начато Дж. Лагариасом [117, 118, 119, 120, 121]. Более подробный обзор можно найти в статьях Н. Шевалье [93] и Н.Г. Мощевитина [127, 61].

Согласно определениям задача о нахождении наилучших приближений эквивалентна задаче о вычислении локальных минимумов решеток специального вида.

Возьмем, например, линейную форму : R1 R и определим решетку, составленную из узлов вида (, ) = (, ), где (, ) Z1 Z. Тогда (, ) является цилиндрическим -минимумом, если и только если (, ) есть -наилучшее приближение линейной формы.

В общем случае, возьмем две функции: : R [0, +) и : R [0, +), а также набор линейных форм L = (1,..., ) : R R. Определим (+)-мерную решетку, состоящую из узлов (, ) = (, L ), где (, ) Z Z. Положим В этом случае (, ) является локальным -минимумом решетки тогда и только тогда, когда (, ) есть (, )-наилучшее совместное приближение линейных форм L.

Еще несколько ссылок. Конструкция локальных минимумов возникает и в других областях дискретной математики и анализа. Например, В.А. Быковский доказал, что погрешность теоретико-числовых квадратурных формул (см. [10, 11], [57, § 6.4]), а также отклонение сеток от равномерного распределения [15] определяется множеством относительных минимумах решеток специального вида. Он также разработал [12] алгоритм вычисления всех относительных минимумов решеток (алгоритм Вороного, в общем случае, находит только часть минимумов, которые нужны для построения основных единиц). Модификации этого алгоритма, реализации и приложению к вычислению параметра Бахвалова параллелепипедальных сеток Коробова посвящены работы С.В. Гассана [16, 17].

В ряде статей (см. [14, 21, 72] и ссылки там) рассматривался вопрос о двумерном обобщении теоремы Валена (о соседних подходящих дробях) в терминах относительных минимумов.

Полиэдры Клейна.

Возьмем любую -мерную решетку и симплициальный конус C R с вершиной в начале координат 0.

Определение 2.7. Множество = (, C), которое является выпуклой оболочкой ненулевых узлов, содержащихся в C, называется полиэдром Клейна решетки для конуса C.

Пусть линейное отображение : R R является невырожденным. Тогда является полиэдром Клейна решетки для конуса C. Подходящим образом выбирая, можно прийти к случаю = Z (решетка фиксирована) либо к случаю C = [0, +) (конус фиксирован). В оригинальной конструкции Клейна рассматривался произвольный конус и фиксированная решетка Z. Нам будет удобнее рассматривать случай, когда решетка является произвольной, а конус фиксированным.

Будем придерживаться следующей терминологии.

Определение 2.8. Пусть = (1,..., ), где = ±1. Множество (), которое является выпуклой оболочкой ненулевых узлов, лежащих в угле будем называть полиэдром Клейна решетки.

Замечание 2.1. Каждая -мерная решетка имеет 2 полиэдров Клейна. В общем случае полиэдр Клейна не является обобщенным многогранником. Более того, он может быть не замкнутым множеством (см. [128]). Если, например, решетка является целочисленной либо не имеет ненулевых узлов на координатных плоскостях (решетка общего положения), то полиэдры Клейна являются обобщенными многогранниками1.

В этом случае будем ссылаться на полиэдры Клейна, как на многогранники Клейна.

В двумерном случае конструкция Клейна дает следующую геометрическую интерпретацию непрерывной дроби. Если [0, 1) {1/2}, то множество вершин полиэдров Клейна решетки, определяемой формулой (2.2), совпадает с множеством относительных минимумов, которое равно (2.3). Кроме того, если две соседние вершины полиэдра Клейна, то то есть количество точек решетки на полуинтервале (, ] ( целочисленная длина [, ]) равно соответствующему неполному частному.

Отметим, что множество относительных минимумов любой двумерной решетки совпадает с множеством вершин полиэдров Клейна (), за исключением решеток с базисом вида (, ), (, ), для которых вершинами являются узлы ±(2, 0), ±(0, 2), а минимумами Начиная с размерности 3 конструкции Клейна и Вороного – Минковского становятся различными. В частности, существуют четырехмерные решетки, имеющие относительные минимумы, лежащие внутри полиэдров Клейна, причем множество таких решеток имеет положительную меру (см. [24]). Однако, как доказано В.А. Быковским [13], любая вершина полиэдра Клейна является относительным минимумом.

Не претендуя на полноту изложения, приведем краткий обзор некоторых известных результатов, связанных с полиэдра Клейна. Более полный обзор можно найти в монографии [106].

В 1983 г. Х. Цутихаси [133] установил соответствие между периодическими полиэдрами Клейна и многомерными касповыми особенностями, которое обобщает известное ранее соответствие между периодическими непрерывными дробями и двумерными касповыми особенностями.

Б.Ф. Скубенко [65, 66] обнаружил связь между минимумами произведений линейных форм и многогранниками Клейна.

т.е. их пересечения с любым многогранником также являются многогранниками.

Исходно исследуя -градуированные алгебры [78], В.И. Арнольд столкнулся с полиэдрами Клейна. Начиная с 1989 г. он сформулировал множество задач о геометрических и статистических свойствах многомерных непрерывных дробей (см. [3, 4, 79, 80]), возобновляя тем самым интерес к этим вопросам.

Примеры некоторых простейших полиэдров Клейна для алгебраических трехмерных решеток, а также их свойства рассматривались в работах Е.И. Коркиной [109, 56, 110], Ж. Лашо [114], О.Н. Карпенкова [48, 49, 103, 105], Ж. Муссафир [129], А.Д. Брюно и В.И. Парусникова [7, 62, 63].

Связь между полиэдрами Клейна и базисами Гильберта изучали Ж.О. Муссафир [58] и О.Н. Герман [22], который также вывел эквивалентные формулировки известных гипотез Литтлвуда и Оппенгейма в терминах полиэдров Клейна [23, 96] (см. также [25]).

В ряде работ изучались многомерные аналоги теоремы Лагранжа о периодичности непрерывных дробей у квадратичных иррациональностей в терминах полиэдров Клейна. Комбинаторно-топологический аналог предложен (без доказательства) Е.И.

Коркиной [109], а алгебраический Лашо [114, 115, 116]. Уточнение и полное доказательство результата Коркиной опубликовано в [25]. Еще один вариант многомерного обобщения теоремы Лагранжа см. в [8, 9].

О.Н. Карпенков [104] получил полное описание целочисленно-линейных типов двумерных граней полиэдров Клейна, которые лежат на расстоянии, большем единицы от начала координат.

Ряд публикаций (см. [129, 48, 105] и ссылки там) посвящены разработке алгоритмов построения многогранников Клейна алгебраических решеток, которые тесно связаны с фундаментальными областями чисто вещественных расширений числового поля.

Несмотря на значительный интерес, почти не исследованными являются поставленные Арнольдом задачи о статистических свойствах многомерных аналогов непрерывных дробей. В известной работе М.Л. Концевича и Ю.М. Сухова [108] аннонсированы некоторые результаты о существовании статистик для полиэдров Клейна и предложена схема их доказательства. В диссертации Ж. Муссафир [129] некоторые из этих статистик вычислены приближенно. В статье О.Н. Карпенкова [51] сформулированы гипотезы о частоте появления многогранника заданного целочисленнолинейного типа в качестве грани полиэдра Клейна.

§ 3. Основные результаты Оценки максимального количества локальных минимумов. Хорошо известен следующий результат о скорости роста знаменателей подходящих дробей: если = () знаменатель -й подходящей дроби для R, то [76, теорема 12] Следовательно, для любого Аналогичные оценки справедливы и для многомерных наилучших приближений [91, 93, 118, 120]. Неравенство (3.1) можно переписать в следующем виде: для любой двумерной решетки вида (2.2) Здесь и далее M() мы распространяем этот результат на случай решеток произвольной размерности и ранга.

Назовем решетки 1 и 2 из, (R) подобными, если существует такой набор ненулевых вещественных чисел (1,..., ), что Множество относительных минимумов M() конечно тогда и только тогда, когда решетка подобна целочисленной (см. [27]).

Для полных целочисленных решеток известны следующие оценки максимального количества относительных минимумов:

Верхняя доказана в [10, 11], а нижняя в [1]. Ряд публикаций был посвящен уточнению соответствующих констант (см. [57, 28, 2] и ссылки там). Наилучший результат получен в [2] и имеет вид Возьмем теперь произвольную решетку, (R). Для любого R+ положим В главе I диссертации мы докажем оценку где Отметим, что для алгебраической решетки (R) Отсюда вытекает, что оценка (3.4) является правильной с точностью до константы, зависящей от и.

Используя (3.4), мы получим следующее неравенство для количества всех относительных минимумов неполной целочисленной решетки, (Z) где = () максимум из модулей миноров -го порядка базисной матрицы решетки (() не зависит от выбора базисной матрицы). Из (3.2) вытекает, что оценка (3.6) является правильной с точностью до константы, зависящей от и.

В последнем параграфе главы I доказывается следующая оценка для максимального количества локальных -минимумов:

Асимптотическое распределение целочисленных матриц. Исследование статистических свойств конечных непрерывных дробей приводит к задачам об асимптотическом распределении целочисленных матриц размера 2 2, лежащих в заданной области. Пусть, например, = (/ ) длина разложения рационального / = [0; 1,..., ] в непрерывную дробь. Вычисление величины Подчеркнем, что если выполняются условия А), Б), то нельзя представить в виде объединения конечного набора множеств, каждое из которых удовлетворяет (3.8).

Основной результат главы II заключается в доказательстве соотношения где постоянная () 0 зависит только от (явную формулу см. в § II.1), а простые делители натурального. Отметим, что при Здесь где ( ) количество простых делителей.

Среднее количество относительных минимумов. В 1968 г. Г. Хейльбронн [98] получил асимптотическую формулу для средней длины конечной цепной дроби:

Здесь = (/) длина разложения / = [0; 1,..., ] в непрерывную дробь;(множество () состоит из целых [1, ], которые взаимно просты с, а () = 1 (.

Портер [132] уточнил формулу для остатка:

где некоторая положительная константа, впоследствии найденная Ренчем [107].

В главе III мы доказываем многомерное обобщение теоремы Хейльбронна в терминах относительных минимумов. А именно, определим среднее количество относительных минимумов полных -мерных целочисленных решеток определителя :

Учитывая связь между относительными минимумами двумерных решеток и непрерывными дробями (см. (2.3)), соотношение (3.11) можно переписать так Основной результат главы III заключается в доказательстве соотношения для любой размерности 2. Здесь () положительная постоянная, зависящая только от. К сожалению, константу () при 3 даже приближенно вычислить удается только в трехмерном случае. В последнем параграфе главы III доказываются двусторонние оценки:

Из них, в частности, вытекает следующее уточнение первого неравенства из (3.3):

Доказательство (3.12) основано на построении алгоритма, который позволяет единственным образом дополнить относительный минимум до базиса (решетки) специального вида. В результате, вычисление суммы сводится к нахождению количества всех базисов этого специального вида, то есть к вычислению количества матриц из M (Z; ), лежащих в некоторой области. Для этого применяется формула (3.10).

Статистические свойства полиэдров Клейна. В статье Хейльбронна [98] также доказана асимптотическая формула для среднего количества неполных частных, равных заданному натуральному :

где (, ) = (1 ()). А.В. Устинов [70], используя метод Портера [132], уточнил остаток:

где постоянная () зависит только от.

В главе IV доказывается обобщение результатов Хейльбронна (3.11), (3.13) в терминах полиэдров Клейна.

Пусть 1 и 2 многогранники из R с вершинами в Z. Напомним, что 1 и 2 принадлежат одному целочисленно-линейному типу, если существует такое отображение Возьмем любую компактную гипергрань полиэдра Клейна решетки (R).

Пусть : R R такое линейное преобразование, что Очевидно, что целочисленно-линейный тип многогранника не зависит от выбора. Это позволяет следующим образом классифицировать грани полиэдров Клейна.

целочисленно-линейный тип ( 1)-мерных многогранников из R.

Определение 3.1. Будем говорить, что грань принадлежит типу, если принадлежит целочисленно-линейному типу для любого линейного преобразования : R R удовлетворяющего (3.14).

Пусть (; ) множество граней типа, а () множество вершин полиэдров Клейна решетки. Для любого натурального определим среднее количество граней типа :

и среднее количество вершин:

многогранников Клейна целочисленных полных -мерных решеток определителя.

Пусть = 2. Тогда гиперграни являются отрезками, и их тип однозначно определяется количеством точек решетки, которые лежат на грани. Поэтому, согласно (2.4), вопрос о среднем числе граней фиксированного типа сводится к задаче о частоте появления заданного натурального в качестве неполного частного. Соотношение (3.13) в терминах многоугольников Клейна можно записать так количество точек решетки лежащих на грани типа. Кроме того, где ( + 1) при = 2 M() = (), за исключением решеток с базисом вида (, ), (, ), для которых () = {±(2, 0), ±(0, 2)}, M() = {±(2, 0), ±(0, 2), ±(, ), ±(, )}.

Следовательно, (считаем 0 (/2) = 0 для нечетного ). Поэтому из (3.12) (из (3.11)) следует, что Пусть 3 множество типов граней, которые реализуются на решетках из 3 (R), т.е.

Возьмем любой 3. Основными результатами главы IV являются следующие асимптотические формулы для трехмерных полиэдров Клейна:

положительная постоянная, зависящая только от ;

положительная постоянная. Аналитические выражения для них приведены в § IV. и § IV.3 соответственно.

Доказательство (3.15) основано на построении алгоритма, который грани типа ставит в соответствие некоторый базис специального вида. В результате, задача о сводится к нахождению количества всех базисов этого специального вида, то есть к вычислению количества матриц из M (Z; ), лежащих в некоторой области. Для этого применяется формула (3.10).

Доказательство (3.16) основано на следующих соображениях.

1. Согласно [13] любая вершина полиэдра Клейна является относительным минимумом. Поэтому достаточно подсчитать количество минимумов, которые не являются вершинами, и использовать (3.12).

2. В [24] получено описание относительных минимумов трехмерных решеток, которые не являются вершинами. Согласно [24], вычисление суммы сводится к подсчету суммарного количества треугольных граней некоторого специального вида. Для этого используются идеи доказательства (3.15) и результаты О.Н. Карпенкова [104] о классификации граней.

К сожалению, результаты главы IV не удается распространить на случай 4.

При 4 получены только оценки (см. § IV.1) Среднее количество цилиндрических минимумов. Пусть лучевая, непрерывная и кусочно-дифференцируемая функция, определенная на R1.

Определим среднее число, [1, ] цилиндрических -минимумов -мерных целочисленных решеток с определителем из отрезка [1, ] по формуле где M, () множество цилиндрических -минимумов.

В первых двух параграфах главы V доказывается асимптотическая формула где, положительная постоянная, зависящая только от.

Доказательство основано на специальной процедуре дополнения цилиндрического минимума до базиса решетки, основанной на идеях Г.Ф. Вороного (см. [32, глава 5, § 60]). В результате, вычисление суммы сводится к нахождению количества целочисленных матриц таких, что где, некоторое подмножество GL (R). Доказательство технических результатов о количестве целочисленных матриц в, вынесено в приложение.

Среднее количество наилучших приближений линейных форм. По-видимому, первые результаты о статистических свойствах конечных непрерывных дробей получил G. Lochs [122], который, в частности, доказал следующую формулу где 1 абсолютная положительная постоянная, а 1 () = (1/2 ). Ряд работ был посвящен улучшению оценки остатка 1 (). Последний результат получен Д.А. Фроленковым [74] и имеет вид В работе А.В. Устинова [69] получена следующая асимптотическая формула для математического ожидания количества подходящих знаменателей, не превосходящих фиксированного 2:

где 1 абсолютная положительная постоянная.

В последнем параграфе главы V доказывается многомерное обобщение результатов (3.19), (3.20) в терминах наилучших приближений линейных форм.

Пусть B () множество -наилучших приближений линейной формы R 1 1 +... +. Множество B () конечно только в случае, когда числа 1,..., линейно зависимы над полем Q.

Для любого 2 и [0, 1) определим множество Оно конечно, причем Если функция выпуклая, то неравенство (3.21) вытекает из известных результатов об экспоненциальном росте наилучших приближений [120, теорема 1]. В общем случае, оно является тривиальным следствием из теоремы I.3.1 настоящей работы.

Кроме того, согласно результатам Шевалье [92] существует такая положительная постоянная, зависящая только от, что для почти всех (по Лебегу) [0, 1) Для любого вещественного > 1 определим множество (), состоящее из векторов [0, 1) с координатами = /, где, целые, причем Определим среднее количество -наилучших приближений, удовлетворяющих условию (), линейных форм с рациональными коэффициентами из (), а также математическое ожидание количества -наилучших приближений, удовлетворяющих условию (), линейных форм с вещественными коэффициентами.

Отметим, что функция [0, 1) #B (, ) измеримая по Лебегу (см. лемму V.3.5) и ограниченная (согласно (3.21)). Поэтому интеграл Лебега B, ( ) существует и конечен.

В одномерном случае (т.е. при = 1, () = ||) асимптотические формулы для определенных средних величин вытекают из известных статистических свойств непрерывных дробей (см. (3.19), (3.20)). В частности, Рассмотрим теперь случай произвольной размерности. Согласно (3.21), (3.22) В § 3 главы V мы докажем, что для любого 1 и любой непрерывной, кусочнодифференцируемой, лучевой функции : R R Постоянная, такая же, как и в формуле (3.17) Обоснование (3.23) основано на следующих соображениях. Как уже отмечалось, существует взаимно однозначное соответствие между наилучшими приближениями линейной формы и цилиндрическими минимумами некоторой решетки. Поэтому B, ([1, ], ) равно среднему количеству цилиндрических -минимумов, у которых (1,..., 1 ), решеток специального вида. В результате, вычисление B, ([1, ], ) сводится к нахождению количества целочисленных матриц, удовлетворяющих (3.18) и условиям:

где = + 1, а 1 ( ) наибольший общий делитель алгебраических дополнений к элементам последней строки.

Формула (3.24) получается предельным переходом в (3.23) при.

Доказательство технических результатов о количестве целочисленных матриц в, вынесено в приложение.

Среднее количество локальных -минимумов. Пусть [1, ] среднее число локальных -минимумов -мерных целочисленных решеток с определителем из отрезка [1, ], то есть где M () множество локальных -минимумов решетки.

Основной результат главы V заключается в следующем. Пусть функция удовлетворяет условиям (2.1). Тогда для любого где положительная постоянная, зависящая только от.

Как и в предыдущих случаях, доказательство основано на построении специальной процедуры дополнения локального минимума до базиса решетки. В результате, сводится к нахождению количества целочисленных матриц с определителем из отрезка [1, ], лежащих в некотором множестве GL (R).

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

Также как и главе V доказательство технических результатов о количестве целочисленных матриц из вынесено в приложение.

Глава I Оценки максимального количества локальных минимумов В этой главе мы получим верхние и нижние оценки для максимального количества локальных минимумов (неравенства (0.3.4), (0.3.5), (0.3.6) и (0.3.7)).

В § 1 мы выведем некоторые вспомогательные соотношения. В § 2 получим оценки для количества относительных минимумов, а в последнем разделе для локальных -минимумов.

Напомним, что ненулевой узел -мерной решетки называется относительным минимумом, если не существует ненулевого узла такого, что причем хотя бы одно из неравенств является строгим. Через M() мы обозначаем множество относительных минимумов решетки.

§ 1. Вспомогательные оценки Пусть, (R), т.е. -мерная решетка ранга. Возьмем любые векторы P = = 1,. Определим Целью данного раздела является получение оценки Отметим, что непосредственное применение методов работ [2, 28], в которых исследуются полные целочисленные решетки, приводит к завышенной оценке Следующие две леммы доказываются также как и в [2, 28]. В них не учитывается ограничение на ранг решетки.

Лемма 1.1. Пусть {1,..., } = {}, причем множества,, {} попарно непересекаются. Тогда для любого (1,..., ) R количество относительных минимумов, удовлетворяющих неравенствам не больше, чем 2.

Доказательство. Предположим, что утверждение леммы неверно. Тогда найдутся два минимума, M(), удовлетворяющие (1.1), причем 0, = 1, (координаты имеют одинаковые знаки). Рассмотрим узел ( ). Пусть, для определенности, | | | |. Тогда | | < | |. Кроме того, Значит, узел ( ) противоречит условию M().

Лемма 1.2. Пусть {1,..., } = {}, причем множества,, {} попарно непересекаются. Пусть, R+, причем < при {1,..., } {}. Тогда количество относительных минимумов, удовлетворяющих неравенствам Доказательство. Достаточно заметить, что для любого, удовлетворяющего (1.2), существуют натуральные log2 ( / ) ( {1,..., } {}) такие, что и воспользоваться леммой 1.1.

Согласно лемме 1.2 для любого {1,..., } Получим теперь более точную (при больших ) оценку для неполных решеток.

Пусть = () базисная матрица. Будем использовать обозначения:

Отметим, что величины (, ) не зависят от выбора базисной матрицы.

Пусть <,. Через обозначим матрицу, полученную из, к которой в качестве последнего столбца дописали. Тогда rang. Следовательно, det () = 0 для любого I+1 (). Занумеруем элементы из по возрастанию:

1 < 2 <... < +1. Раскладывая det () по последнему столбцу получаем формулу из которой вытекает оценка Пусть (0) множество узлов, все координаты которых не равны нулю.

Лемма 1.3. Пусть <, (0) =, I+1 (), причем rang () =. Тогда для любого узла (0) существуют такие,, и R+, что причем зависит только от,, и.

Доказательство. Возьмем номера,, удовлетворяющие условиям Так как все координаты не равны нулю, то из (1.4), (1.7) вытекает, что Используя неравенство (1.5), получаем Осталось положить = |( )|/|( )|.

Определение 1.1. Пусть =. Будем говорить, что множество удовлетворяет условию (R), если для некоторого набора номеров, {1,..., }, = 1,, удовлетворяющего условиям существуют такие числа R+, = 1,, что для любого Лемма 1.4. Множество (0) можно представить в виде объединения не более, чем (( + 1)) множеств, удовлетворяющих условию (R).

Доказательство. Пусть =. Используем математическую индукцию по = 0, 1, 2,.... При = 0 утверждение леммы тривиально.

Индукционный переход от ( 1) к. Для краткости, положим = ( + 1).

Возьмем любой набор I+1 () такой, что rang () =, где базисная матрица. По лемме 1.3 множество (0) можно представить в виде так, что для каждого существуют номера = (), = () и число = () R+, удовлетворяющие (1.6) для всех. Пусть решетка, составленная из узлов, у которых вычеркнули ()-ю координату. Так как (() ) = 0, то,1 (R).

Значит, по предположению индукции множество можно представить в виде множества удовлетворяют условию (R). Следовательно, узел () получается из вычеркиванием ()-й координаты. Осталось доказать, что каждое множество удовлетворяет условию (R).

Возьмем любое =. Тогда существуют номера,,, и числа, R+ ( = 1, 1) такие, что для любого выполняются неравенства (1.6) и (1.8) (при, = 1, 1), причем =, = для всех. Положим =. Осталось подобрать и. Возможны два случая.

Следовательно, можно положить =, =.

, = 1,. Тогда справедлива оценка Доказательство. Пусть любое множество из M(; P; p), удовлетворяющее условию (R). Так как M(; P; p) (0), то в силу леммы 1.4 достаточно доказать, что По определению условия (R) существуют номера, {1,..., } и R+ ( = 1, ), удовлетворяющие (1.8). Положим = 1 и определим следующие множества индексов Возьмем любой M(; P; p). Тогда существуют такие целые, что Так как {2,..., }, то из (1.8), (1.10) вытекает По лемме 1.2 количество относительных минимумов, удовлетворяющих (1.10), (1.11) при заданном наборе, не больше, чем § 2. Оценки количества относительных минимумов Верхняя оценка количества минимумов нецелочисленных решеток Обоснование оценки (0.3.4) проведем по следующей схеме.

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

2. Используем лемму 1.5 для оценки количества оставшихся минимумов и применяем математическую индукцию.

() максимум из модулей миноров -го порядка матрицы ;

Согласно определениям, Напомним, что если R+, то Лемма 2.1. Пусть, (R), = (), = (), (, +). Тогда где — некоторые подрешетки ранга, меньшего чем, постоянная (, ) определена в лемме 1.5.

Доказательство. Для каждого номера {1,..., } определим и представим множество M(; ) в виде Если {1,..., }, = 0, то из (1.5) вытекает, что = 0 для всех. Поэтому, не умаляя общности, считаем, что = 0 для всех.

Докажем, что любые узлов из M линейно зависимы. Пусть (1),..., () M {0}. Определим матрицу со столбцами (1),..., (). Возьмем набор I () такой, что |()| = и обозначим через () матрицу, составленную из строк с номерами из. Пусть базисная матрица решетки. Тогда существует невырожденная целочисленная квадратная матрица такая, что · =. Так как | det ()| = |()| =, то С другой стороны, из определения множества M вытекает, что Получили противоречие. Значит, любые узлов из M линейно зависимы.

Таким образом, M M( ; ), где некоторая подрешетка ранга меньшего, чем. Осталось доказать, что Если для некоторого >, то M =. Поэтому считаем, что, = 1,.

Пусть * I (), |( * )| =. Из (1.5) вытекает, что для любого Если * оно тривиально (т.к. тогда = ). Если *, то для доказательства достаточно в (1.5) выбрать = * {}.

Используя (2.3), получаем для любого M(; ) Следовательно, Применяя лемму 1.5 для оценки #M(; P; p) и учитывая, что / = ! /, получаем (2.2).

Замечание 2.1. Для полной решетки ( = ) неравенство (2.1) можно уточнить:

Для этого достаточно положить = и учесть, что = для всех.

Определим Нетрудно проверить следующие формулы Пусть, (R), = (), = (). Возьмем набор индексов * I () такой, что |( * )| =. Тогда из (1.5) вытекает оценка Согласно теореме Минковского о линейных формах существует ненулевой узел такой, что | | 1/ для всех *. Тогда | | 1/ при * и поэтому Отметим, что для полной решетки выполняется лучшая оценка:.

Теорема 2.1. Для любого вещественного (1, +) справедлива оценка где Доказательство. Из леммы 2.1, оценок (2.5), (2.6) и очевидного неравенства () () при, вытекает Осталось заметить, что 1, = 2 и применить математическую индукцию (по ).

Из теоремы 2.1 и формулы 2.4 вытекает следующий результат.

Следствие 2.1. Пусть, (R), = (), (, +). Тогда где (, ) — постоянная, определенная в лемме 1.5 и теореме 2.1.

Нижняя оценка максимального количества минимумов нецелочисленных решеток Докажем, что существуют решетки, (R), удовлетворяющие условию Пусть чисто вещественное расширение степени поля рациональных чисел Q. Обозначим через 1,..., базис, состоящий из целых поля. Пусть 1,..., сопряженные базисы ( = 2, ). Для каждого полагаем т.е. () = ( 1 (),..., ()) геометрическое изображение числа.

Пусть -мерная полная решетка с базисной матрицей то есть состоит из узлов (), где, а порядок поля с базисом 1,...,. Докажем, что для такой решетки выполняется нижняя оценка (2.7).

Любой узел {0} имеет ненулевые координаты, причем 1 ·... · целое число. Следовательно, |1 ·... · | 1, и поэтому Согласно теореме Дирихле об единицах (см. [5]) существуют числа 1,..., (основные единицы кольца ) такие, что все элементы вида попарно различны, причем (). Тогда очевидно, что Оценка (2.7) доказана при =. Для построения неполной решетки из, (R) ( > ), удовлетворяющей (2.7), достаточно ко всем узлам дописать координаты +1,...,, равные нулю.

Верхняя оценка количества минимумов целочисленных решеток Мы докажем что любой минимум M() целочисленной решетки, (Z) удовлетворяет неравенству:

и, как следствие теоремы 2.1, получим оценку для максимального числа относительных минимумов целочисленных решеток.

Возьмем любую решетку, (Z) с базисом (1),..., (). Пусть = (( )) соответствующая базисная матрица. Для I1 () и {1,..., } обозначим через () () матрицу размера ( 1) ( 1), полученную из удалением -го столбца и всех строк с номерами, не принадлежащими. Пусть () подмножество в, состоящее из узлов ±(), где I1 (), Согласно свойствам определителя матрицы В частном случае = ( полная решетка) множество () состоит из 2 узлов ±() вида () = (0,..., 0,, 0,..., 0), т.е. -я координата вектора () равна = det, а остальные нули.

Лемма 2.2. Пусть, (Z), = () и R, причем Тогда существует такой набор I (), что () = 0, причем Доказательство. Проведем математическую индукцию по =.

При = 0 утверждение леммы очевидно.

|( )| =. Если | | для всех, то утверждение леммы справедливо (в силу (1.5)). Предположим, что это не так, то есть существует такой *, что | | >. Тогда Пусть решетка в Z1, полученная из удалением -й координаты, а R1 вектор, полученный из таким же способом. Если ранг меньше, то () = 0 для всех наборов I (), не содержащих. Тогда для набора * = * {} согласно (1.4) Поэтому | ( * )| | | при всех, что противоречит условию леммы. Следовательно, ранг решетки равен. Заметим, что множество () состоит из узлов ±() по всем наборам I1 (), не содержащим, где () получен из () отбрасыванием -й координаты. Ввиду (2.10), для любого () () найдется такой номер =, что | | < | |. Таким образом, решетка и вектор удовлетворяют условиям леммы.

Осталось воспользоваться предположением индукции.

Следствие 2.2. Относительные минимумы любой целочисленной решетки, (Z) удовлетворяют оценке (2.8).

Доказательство. Возьмем любой минимум M(). Если для некоторого () выполняется | | = | | для всех, то оценка (2.8) очевидна. Пусть для любого () найдется индекс для которого | | = | |. Тогда, по определению относительного минимума, Значит, вектор = удовлетворяет условиям леммы 2.2. Согласно лемме 2.2 существует набор 0 I (), для которого (0 ) = 0 и для любого Если =, то сразу получаем ||. Пусть >. Используя формулу (1.4), в которой = 0 {} приходим к оценкам:

Следовательно, | | · для всех 0.

Следствие 2.3. Пусть, (Z), = () > 1. Тогда Доказательство. Согласно следствию 2.2, M() = M(; ) при = ·. Применяя следствие 2.1, получаем требуемую оценку.

§ 3. Оценки количества локальных минимумов Положим Пусть функции : R R ( = 1, ) лучевые, непрерывные и кусочно-дифференцируемые. Определим = (1,..., ) : R R следующим образом Напомним, что ненулевой узел решетки (R) мы называем локальным минимумом, если не существует ненулевого узла такого, что причем хотя бы одно из неравенств строгое.

Пусть M () множество локальных -минимумов решетки. Основной целью настоящего параграфа является доказательство оценки (0.3.7).

Так как функции непрерывные, лучевые и кусочно-дифференцируемые, то существует такая постоянная 1, что для всех, R, {1,..., }.

Из (3.2), в частности, следует, что Лемма 3.1. Возьмем любой {1,..., } и положим =, =. Пусть постоянные, и конус R удовлетворяют условиям где (, ) — скалярное произведение векторов,. Тогда Доказательство. Пусть,, | | = | | = 1. Тогда согласно (3.5) Докажем утверждение а). Используя (3.3), получаем Применяя (3.1), (3.6), приходим к оценке подставляя которую в (3.7), заключаем так как 1 > 2 · 2. Утверждение а) доказано.

Докажем б). Пусть, например, || ||. Ввиду (3.1) и (3.5), Поскольку то ( ) < min{(), ()}. Утверждение б) доказано.

Замечание 3.1. Условие (3.5) означает, что угол между векторами и не больше, чем arccos(1 ). Поэтому, для любого (0, 1), пространство R можно разбить на фиксированное (зависящее только от и ) число конусов, каждый из которых удовлетворяет условию (3.5).

Возьмем любые векторы P = (1,..., 1 ), p = (1,..., 1 ) R1 такие, что. Для любой решетки (R) определим Лемма 3.2. Пусть выполняются следующие условия:

положительная постоянная < (24 )1 такая, что Тогда для любого вещественного, удовлетворяющего (3.4), справедлива оценка Доказательство. Возьмем любой минимум M (; P, p). Тогда существует набор (1,..., 1 ) N1 такой, что Докажем, что еще одного локального минимума, удовлетворяющего (3.8) и принадлежащего, не существует. Действительно, пусть найдется M () такой, что Пусть, например, q () q (). Тогда, согласно лемме 3.1 а), Кроме того, (1+)1 ·q () q () (1+)·q (), = 1, 1. Поэтому по лемме 3.1 б) Значит, узел ( ) противоречит условию M ().

Таким образом, существует не более одного локального минимума, удовлетворяющего (3.8), при фиксированном наборе 1,.., 1 ). Осталось заметить, что количество наборов оценивается величиной 1 log1+ ( / ).

Теорема 3.1. Пусть P, p R1, причем > > 0, = 1, 1. Тогда для любой решетки (R) справедлива оценка Доказательство. В соответствии с замечанием 3.1 пространство R можно разбить на фиксированное (зависящее только от и ) число множеств, каждое из которых удовлетворяет условию а) леммы 3.2. Применяя лемму 3.2 для оценки количества минимумов, попадающих в каждую часть, получаем требуемое неравенство.

Пусть M (), причем q () = 0, = 1,. Тогда, согласно (3.1) и определению локального минимума, множество не содержит ненулевых узлов решетки. Поэтому, по теореме Минковского о выпуклом теле, mes () 2 · det. Так как Следствие 3.1. Пусть (Z; ), > 1. Тогда #M () ln1.

Доказательство. Разобьем множество M () на две непересекающиеся части:

Согласно (3.9) для всех M () выполняется оценка q (), = 1,. Поэтому, используя теорему 3.1, в которой = ( ), = 1, = 1, 1, получаем Осталось оценить #M (). Не умаляя общности, рассматриваем минимумы, которые для некоторого < удовлетворяют условиям:

Узел = (1,..., ) является локальным (1,..., )-минимумом решетки Поэтому, согласно (3.10), количество минимумов M (), удовлетворяющих (3.11), не больше, чем (ln1 + 1), где = det. Число делит. Это вытекает из классического результата о существовании у целочисленной решетки базиса треугольного вида (см., например, [54, глава I, следствие 2]). Значит, и, следовательно, Асимптотическое распределение целочисленных матриц § 1. Формулировка основного результата Пусть множество GL (R) удовлетворяет следующим условиям R с липшицевыми границами;

(Б) существует такая постоянная > 0, что для любой матрицы = (( )) Целью настоящей главы является получения асимптотической формулы для количества целочисленных матриц заданного определителя, лежащих в.

Из условия (А) следует, что множество инвариантно относительно левого действия группы D (R+ ), состоящей из диагональных матриц размера с положительными вещественными на главной диагонали. Рассмотрим ( 1)-мерное многообразие P (R) = D (R+ )GL (R) проективизацию группы GL (R) относительно левого действия группы D (R+ ).

Пусть () образ множества GL (R) при проективизации GL (R) P (R).

Тогда P (R) содержится в объединении всех P (R,, ), причем каждый элемент из P (R,, ) имеет единственный прообраз при проективизации Значит, множество всех P (R,, ) образуют атлас многообразия P (R), а матрицы из GL (R,, ) являются координатами соответствующих элементов P (R,, ).

Определим меру =, на плоскости GL (R,, ) следующим образом:

дифференциал ( 1)-мерной меры Лебега ( 1)-мерной поверхности GL (R,, ) в точке (т.е. = 1,, ). Она порождает меру =, на карте P (R,, ):

прообраз P (R,, ) при проективизации GL (R,, ) P (R).

Нетрудно проверить, что мера не зависит от выбора карты, т.е.

Действительно, пусть, например, Пусть и прообразы при проективизациях соответственно. Рассмотрим отображение GL (R,, ) GL (R,, ), действующее по формуле:

(1-ю строку делим на 12, а остальные не меняем). Тогда Значит,, () =, ().

Таким образом, мера не зависит от выбора карты и поэтому корректно определена на всем многообразии P (R).

Отображение · инвариантно относительно правого действия группы GL (R), а именно, если GL (R), причем () является -измеримым, то для любого GL (R) Эта формула легко проверяется, если матрица удовлетворяет одному из условий:

1) диагональная матрица;

2) для любого GL (R) матрица · получается из матрицы изменением нумерации столбцов;

3) для любого GL (R) матрица · получается из матрицы заменой одного из столбцов матрицы на его сумму с некоторым другим столбцом.

В общем случае достаточно заметить, что любую невырожденную матрицу можно представить в виде произведения матриц вида 1), 2), 3).

Множество () является -измеримым, если измеримо по Лебегу и удовлетворяет условию (Б).

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

Теорема 1.1. Пусть множество GL (R) удовлетворяет условиям (А), (Б).

Тогда для любого целого > 1 количество целочисленных матриц, удовлетворяющих условию det =, равно где Замечание 1.1. При = 2, используя метод Портера [132], можно получить более точную формулу со степенным понижением в остаточном члене.

Замечание 1.2. Пусть множество GL (R) удовлетворяет (А) и следующему условию:

(Б’) (В отличие от (Б) в правой части неравенства стоит | det | вместо det ). Тогда количество целочисленных матриц, у которых | det | =, также равно (1.1). Действительно, пусть Множества (+ ) и ( ) не пересекаются. Поэтому, применяя теорему 1.1, получаем требуемый результат.

Следствие 1.1. Пусть множество GL (R) удовлетворяет условиям (А), (Б’).

Пусть N, (2, 3,..., ) Z1. Тогда для любого целого > 1 количество целочисленных матриц = (( )), удовлетворяющих условиям равно Доказательство. Определим матрицу по формуле Тогда количество искомых матриц равно количеству целочисленных матриц определителя, лежащих в · = { · : }. Множество · удовлетворяет условиям (А), (Б’). Осталось применить теорему 1.1, замечание 1.2 и учесть, что (()) = (( · )).

Доказательство теоремы 1.1 мы проведем следующим образом. Очевидно, что наибольший общий делитель миноров ( 1)-го порядка матрицы, а где ( ) Чтобы вычислить (, ) мы должны найти количество узлов некоторой решетки, лежащих в заданном множестве. Эта задача является достаточно простой. Основная проблема заключается в вычислении суммы Будем использовать следующие обозначения: если M, (R),, то () максимум из модулей миноров -го порядка матрицы, Тогда условие (Б) можно записать так матриц таких, что det =.

§ 2. Вспомогательные результаты О разложениях целочисленных матриц Пусть TM (Z) множество целочисленных нижнетреугольных матриц = (( )) M (Z) таких, что для любого Теорема 2.1. Любая целочисленная решетка (Z) имеет единственную базисную матрицу TM (Z).

Доказательство существования см, например, в [54, гл. 1]. Единственность легко проверяется от противного (достаточно рассмотреть разложение векторов одного базиса по другому базису).

Из теоремы 2.1 вытекает следующий результат.

Следствие 2.1. Любая невырожденная матрица M (Z) единственным образом представима в виде: = ·, где TM (Z), GL (Z).

Определим функции : N R+, = 0, 1, 2,... следующим образом Используя индукцию, получаем где суммирование ведется по всем натуральным 1,..., таким, что 1 ·...· |.

Возьмем любое натуральное. По теореме 2.1, Из (2.2), (2.3) вытекают оценки Через ( ) будем обозначать наибольший общий делитель миноров -го порядка матрицы M, (Z), <.

Лемма 2.1. Пусть M, (Z), <. Тогда ( ) = ( · ) для любого GL (Z).

Для доказательства достаточно заметить, что правое действие любой матрицы из GL (Z) можно представить в виде произведения следующих отображений:

1) изменение нумерации столбцов;

2) изменение знака некоторого столбца;

3) замена одного столбца на его сумму с другим.

Оценки мощности некоторых матричных множеств Лемма 2.2. Пусть R+, GL (R), (1,..., ) R. Тогда количество матриц · GL (Z), удовлетворяющих условиям Доказательство. Рассмотрим сначала случай, когда удовлетворяет следующим дополнительным условиям:

Пусть || максимум из модулей элементов матрицы. Разделим каждую -ю строку на и обозначим полученную матрицу через. Тогда Пусть (, ) Учитывая (2.7), получаем || ! ·. Количество таких не больше, чем (1 + 2 · · !) 1. Лемма доказана при выполнении условий (2.6).

Пусть (2.6) не выполняется. Возьмем любую 0 · GL (Z), удовлетворяющую (2.6), где заменяем на 0 (если таких матриц нет, то утверждение леммы тривиально). Тогда · GL (Z) = 0 · GL (Z), det = det 0. Заменяя на 0, приходим к случаю (2.6).

Напомним, что множество M (Z, ) состоит из целочисленных матриц размера определителя. Аналогичным образом, положим множество матриц из TM (Z) определителя.

Тогда количество матриц M (Z, ), удовлетворяющих неравенствам не больше, чем 1 · ( ), где 1 — постоянная из леммы 2.2.

Доказательство. Используя следствие 2.1 и лемму 2.2, получаем, что искомое число равно Следствие 2.3. Пусть N [2, +), [1, +). Тогда количество матриц M (Z, ), удовлетворяющих условиям:

не больше, чем, ( ( ) · ln2 ).

Доказательство. Для любой матрицы, удовлетворяющей указанным условиям, существует набор = (1,..., ) N такой, что где Так как 21 ·... 2 2 ·, то используя следствие 2.2, мы видим, что количество матриц M (Z, ), удовлетворяющих (2.8) (при фиксированном наборе ), не больше, чем, ( ( )). Осталось заметить, что количество наборов для которых выполняются (2.9), (2.10) оценивается величиной, (ln2 ).

Пусть ( ) наибольший общий делитель миноров -го порядка, составленных из первых строк матрицы M (Z).

Следствие 2.4. Пусть, N, [1, +), (1,..., 1 ) [1, +)1. Тогда количество матриц M (Z; ), удовлетворяющих условиям не больше, чем, ( 1 · 1 () · 1 ).

Доказательство. Положим Тогда для любой, удовлетворяющей требуемым условиям, Последовательно применяя следствие 2.1, леммы 2.1, 2.2, получаем, что искомое число не больше, чем Нетрудно заметить, что Осталось воспользоваться (2.3) для оценки #TM1 (Z; ).

Тогда количество матриц M (Z), удовлетворяющих условиям:

не больше, чем,, Доказательство. Если матрица M (Z) удовлетворяет (2.12), то Поэтому, используя леммы 2.1, 2.2 и следствие 2.1, мы видим, что количество матриц M (Z), удовлетворяющих (2.11), (2.12), не больше, чем где (, ) Пусть множество N () состоит из N таких, что 1 ·... ·. Тогда Напомним, что если M, (Z) ( < ), то через ( ) и ( ) мы обозначаем соответственно наибольший общий делитель и максимум модулей миноров -го порядка матрицы.

Тогда количество матриц M, (Z), удовлетворяющих условиям:

не больше, чем,, Доказательство. Не умаляя общности рассматриваем только такие матрицы, что Допишем к следующие строки (снизу) Обозначим полученную матрицу через. Тогда | det | = ( ) и удовлетворяет условиям (2.11), (2.12), в которых = 1 при + 1. Осталось применить следствие 2.3.

§ 3. Вычисление некоторых сумм Пусть | | модуль градиента скалярной функции.

Лемма 3.1. Пусть а) — конус в R с липшицевой границей;

в) 1 ( ), причем существует такая постоянная > 0, что для всех Доказательство. Возьмем такой базис {() } решетки, что Этому условию удовлетворяет, например, базис из теоремы 2.1.

Пусть = {1 (1) +... + () : [0, 1)} основной параллелепипед, построенный на векторах (1),..., (). Для любого узла определим Тогда Пусть Сразу отметим, что мера -окрестности поверхности оценивается величиной ( · 1 ). Используя (3.1), получаем следующие утверждения.

1. Множество содержится в (), где () окрестность поверхности и, используя условие в), имеем Используя условие в), получаем Возьмем любую точку. Используя формулу конечных приращений Лагранжа и теорему о среднем для интегралов, получаем Применяя в) и (3.1), приходим к оценке Подставляя последнее соотношение в правую часть (3.3), заключаем Осталось использовать (3.2) и учесть, что Лемма 3.2. Пусть {1,..., 1}, M1, (Z), = ( ). Возьмем любое натуральное, кратное. Пусть решетка = (, ) состоит из решений Z Тогда det = (/)+1.

Доказательство. Используя следствие 2.1 и лемму 2.1, мы всегда можем свести нашу задачу к случаю = 0 при >. Тогда и требуемая формула становится очевидной.

Лемма 3.3. Пусть {1,..., 1} и выполняются следующие условия а) матричное множество определяется формулой где — конусы из R {0} с липшицевыми границами, причем существует б) P = (1,..., ) [1, +), множество (P) определяется формулой Тогда для любого натурального имеет место асимптотическая формула:

где Доказательство. Пусть (P,, ) определим Из условия а) вытекает, что для любого а используя в) и определение 2 получаем, что для всех (P),, {1,..., } Доказательство проведем, используя математическую индукцию по = 1, 2,....

База индукции. Пусть = 1. Используя свойства функции Мебиуса, получаем Согласно (3.5) () 2 /1 при 1 (P). Поэтому Используя последнее соотношение, оценим сумму по > = 1 /:

Здесь и далее в этому доказательстве постоянные в оценках, (...) могут зависеть только от, и.

Применяя лемму 3.1, получаем асимптотическую формулу для () используя которую, вычислим сумму по :

Следовательно, имеет место соотношение подставляя которое и (3.7) в (3.6), получаем утверждение леммы при = 1.

Индукционный переход от ( 1) к. Для любых 1, определим матрица, полученная из к которой в качестве -й строки дописали. Определим также Используя свойства функции Мебиуса, получаем где Используя первое неравенство из (3.5) и лемму 2.3, оценим :

Вычислим. Согласно лемме 3.2, определитель решетки, составленной из решений Z сравнения (, ) 0 (mod ), равен (/)+1. Функция ( ) (, ) удовлетворяет условиям леммы 3.1 (в которой = 2 /(1 ·... · 1 ) ). Поэтому, применяя лемму 3.1, получаем где функция 0 : 1 R+ определяется формулой:

Отметим, что согласно первой оценки из (3.5) Поэтому Следовательно, где Подставляя полученное соотношение в формулу для, имеем где Оценим #{ 1 (P) : ( ) = } с помощью леммы 2.3. Учитывая, что получаем Таким образом, Учитывая (3.9), (3.8), заключаем Согласно предположению индукции, Подставляя последнее соотношение в (3.10), учитывая, что приходим к требуемой формуле.

§ 4. Доказательство теоремы 1. Для любой (R) определим где минимум берется по всем базисам {() } решетки. Из хорошо известных результатов о последовательных минимумах (см., например, [54, глава 8]) вытекает, что для любой линейно-независимой системы {() } где положительная постоянная 0 зависит только от.

Если R+, а гиперповерхность из R, то полагаем замыкание -окрестности относительно нормы | · |.

Лемма 4.1. Пусть (Z, ), 0 R, = (). Возьмем любое ограниченное измеримое по Лебегу множество из R. Тогда Доказательство. Не умаляя общности считаем, что 0 = 0.

Пусть {() } такой базис, что Пусть = {1 (1) +... + () : [0, 1)} основной параллелепипед, построенный на векторах (). Для любого yзла определим Отметим, что () = {}. Кроме того, Тогда Так как Осталось заметить, что (* * ) (, ).

Лемма 4.2. Пусть множество GL (R) удовлетворяет условиям (А), (Б).

Пусть — делитель натурального, а P = (1,..., 1 ) [1, +)1. Положим где 0 — постоянная из оценки (4.1). Предположим, что Тогда количество целочисленных матриц, удовлетворяющих условиям:

равно где () — постоянная из теоремы 1.1.

Доказательство. Пусть Для любой целочисленной матрицы определим Напомним, что (, ) это матрица размера, полученная из, к которой дописали в качестве -й строки, т.е.

Вычисление этой суммы проведем по следующей схеме.

1. Получим асимптотическую формулу для (, ).

2. Вычислим Сразу отметим, что т.к. в противном случае нарушается условие (Б).

Для любого вещественного 1 определим функцию : R+ по формуле:

где mes решений (1,..., ) уравнения а () = (1)+ (), () определитель матрицы, полученной из вычеркиванием -го столбца. Справедливы следующие свойства функции :

где, Diag D1 (R+ ). Для доказательства (4.6) достаточно заметить, что конус и сделать в интеграле замену = ·. Для доказательства (4.7) достаточно учесть, что (Diag · ) = det Diag · (), поэтому 1 (Diag · ) = ()/(det Diag ), где = 1/(det Diag ), и воспользоваться (4.6). Сооотношение (4.8) очевидно.

Возьмем любую целочисленную (P), у которой ( ) =. Докажем, что Здесь и далее в этом доказательстве постоянные в оценках и (...) могут зависеть только от. Для краткости, определим для любой M, (R) Рассмотрим сначала случай, когда выполняются два дополнительные условия Здесь и далее = ( ). Так как множество связное и не содержит 0, то функция знакопостоянная. Не умаляя общности, будем считать, что > 0 для Величина (, ) равна количеству целочисленных точек в ( ). Так как делит, то существует целочисленная точка ( ). Тогда где = (, ) проекция множества ( ) на плоскость { R : = 0}, сравнения Как хорошо известно, det = | |/. Поэтому, используя лемму 4.1, получаем где = ( ). Сразу отметим, что Осталось оценить остаточный член соотношения (4.11). Для этого сделаем замену Преобразование (1,..., 1 ) (1,..., 1 ) отображает на, где такое множество из R1, что т.е. это проекция сечения конуса плоскостью { R : = 1} на плоскость { R : = 0}. Согласно (4.10) множество является ограниченным.

Выясним, что является образом (, ) при отображении.

Строки матрицы образуют линейно-независимую систему из. Поэтому, согласно (4.1) и условию (P), Возьмем любую точку (1,..., 1 ) (, ). Тогда найдется такая точка (1,..., 1 ) Так как (P), то Тогда (1,..., ) ( ) и, используя (4.10), (4.14), (4.15), (4.4), получаем Согласно последней оценке, преобразование переменных (4.13) переводит множество Матрица (, ) принадлежит (в силу условий (А)). Поэтому, согласно (Б), Значит, Подставляя последнюю оценку и равенство (4.12) в (4.11), получаем (4.9).

Формула (4.9) доказана при выполнении условий (4.10). Рассмотрим теперь общий случай. Согласно (Б), где = (). Поэтому Значит, мы можем разбить множество на не более, чем конусов (зависящих только от ), каждый из которых, после изменения нумерации координат, удовлетворяет условиям (4.10). Соотношение (4.9) полностью доказано.

Используя (4.9), получаем Согласно следствию 2.5, Значит, Согласно (А), (Б), (4.6), (4.7), (4.8), (4.5), множество = и функция = удовлетворяет условиям леммы 3.3. Применяя ее, получаем следующую асимптотическую формулу для Осталось доказать, что Рассмотрим случай, когда существуют номера 1,..., {1,..., } такие, что Пусть, например, Так как множество связное, то функции знакопостоянные. Пусть > 0, = 1,. Тогда каждое можно представить в виде:

некоторое ограниченное множество из R1. Согласно (4.12), Cделаем в этом интеграле замену переменных (4.13). Учитывая (4.16), получаем сделаем замену Тогда Формула (4.19) доказана при выполнении условий (4.20) с =. Для других вариантов выбора доказательство проводится точно таким же образом. В общем случае множество достаточно разбить на фиксированное число попарно непересекающихся частей, каждая из которых удовлетворяет (А), (Б), (4.20). Соотношение (4.19) полностью доказано.

Подставляя (4.19) в (4.18), а (4.18) в (4.17), получаем утверждение леммы.

Лемма 4.3. Для любого натурального имеет место оценка Доказательство. Пусть () функция Мангольдта, т.е.

Используя формулу ln = | (), получаем Для завершения доказательства осталось заметить, что Замечание 4.1. Для любого натурального 1 имеют место соотношения Доказательство теоремы 1.1. Для любого {1,..., } определим Согласно следствию 2.3, количество матриц (Z; ) c ( ) = ( ) ( = ), не больше, чем ( ( ) · ln2 ). Здесь и далее в этом доказательстве постоянные в оценках и (...) могут зависеть только от. Поэтому Осталось доказать, что для любого Не умаляя общности рассмотрим случай =. Пусть 1 = max{*, !}, где * постоянная из леммы 4.2. Определим множества Сразу отметим следующие свойства.

1. Если ( ), то параметры = 2 1 удовлетворяют условиям леммы 4.2.

Поэтому мы можем использовать лемму 4.2 для вычисления количества целочисленных матриц ( ), удовлетворяющих условию 1 ( ) =.

Для доказательства достаточно определить натуральные 1,..., 1 из условий 3. Согласно (Б) и определению детерминанта матрицы, Перейдем к вычислению # (Z; ). Докажем сначала, что Возьмем любую ( ). Тогда ( ) с некоторым ( ). Согласно (4.25), Значит, max11 ( ) ( ), т.е. (Z; ). Соотношение (4.26) доказано.

Оценим теперь мощность множества (Z; )( ). Возьмем любую (Z; ) такую, что ( ). Так как (Z; ), то и, используя (4.24), (4.25), получаем Значит, max11 ( ) ( ). Согласно следствию 2.3, количество таких матриц оценивается величиной ( ( ) · ln2 ). Учитывая (4.26), приходим к оценке Осталось вычислить #( ).

Возьмем натуральное. Разобьем ( ) на две непересекающиеся части:

Здесь и далее Положим Сразу отметим, что Согласно следствию 2.4, #, ( ) 1 ·1 ()·1. Учитывая (4.28), получаем Вычислим (, ). Согласно лемме 4.2 (в которой = 2 1 ), Следовательно, Используя (4.29), заключаем Подставим последнее соотношение и (4.31) в (4.30). Используя (2.3) для суммирования главного члена и (2.4), (4.21) для оценки остатка, получаем формулу Подставляя ее в (4.27), приходим к (4.23) (при = ). Из (4.23) и (4.27) вытекает утверждение теоремы 1.1.

Г л а в а III Среднее количество относительных минимумов Напомним, что M() среднее число относительных минимумов полных целочисленных -мерных решеток определителя. Здесь и далее N, > 1.

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

Пусть множество состоит из пар (, ), где (R) и относительный минимум с положительными координатами. Определим также Из оценки (I.3.12) вытекает, что у любой решетки (Z, ) количество относительных минимумов, имеющих хотя бы одну нулевую координату, оценивается величиной (ln2 ). Поэтому (в силу симметрии) Вычисление # ( ) будет проводиться следующим образом. Мы построим отображение, которое каждой паре (, ) ставит в соответствие базисную матрицу решетки. Причем, если M, состоит из базисных матриц, полученных таким спообраз ), а M, переводит некоторое подмножество на M,. Поэтому Здесь и далее, если GL (R), то (Z; ) множество целочисленных матриц из определителя. Следовательно, где M, граница M,. Для вычисления #M, (Z, ) и оценки #M, (Z, ) будем использовать теорему 1.1.

Чтобы проиллюстрировать идею доказательства мы сначала рассмотрим случай произвольного. К сожалению, постоянная () не выражается через известные при 3. В § 4 доказываются оценки позволяющие судить о поведении () при +.

Отметим, что используемый в § 2 метод дополнения минимума до базиса не обобщается на случай 4. Однако он позволяет получить более наглядное описание константы (3), чем то, которое вытекает из результатов § 3.

§ 1. Двумерный случай Этот раздел содержит известные результаты и приводится для полноты изложения.

Определение 1.1. Пусть (R). Множество {(1),..., () } M() будем называть минимальной системой, если не существует ненулевого такого, что Минимальную систему, образующую базис, называем минимальным базисом.

Минимальные системы впервые были изучены в работах Г.Ф. Вороного [20] и Г. Минковского [124] (см., также [126] ) в связи с методами построения единиц в числовых полях. Ими были исследованы различные свойства минимальных систем двух и трехмерных решеток общего положения (в трехмерном случае без доказательства). Доказательство, обсуждение и переизложение оригинальных результатов см.

в [18, 95, 97, 130] Некоторые свойства минимальных систем произвольных решеток изучены в [26, 72].

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

Возьмем любую пару (, ) 2. Выберем узел = (±1, 2 ) из следующих условий Справедливы следующие очевидные свойства.

2. = (1, 2 ), 1 > 0 (иначе ( ) противоречит выбору ).

Таким образом каждой паре (, ) 2 поставлена в соответствие (возможно не единственная) базисная матрица = Очевидно, что разным парам из 2 соответствуют разные матрицы из. Кроме того, если (, ) 2 ( ), то M2 (Z, ). Значит, справедлива оценка гда 0 < 1 < 1, 0 < 2 < 2. Пусть = (, ) решетка, порожденная,. Нетрудно проверить, что M(), а является единственным узлом, удовлетворяющим (1.1).

То есть существует взаимно однозначное соответствие между и некоторым подмножеством 2. Значит, # (Z, ) #2 ( ) и учитывая (1.2), получаем где граница.

Множество удовлетворяет условиям теоремы 1.1, согласно которой Нетрудно вычислить, что Поэтому из (0.1), (1.3), (1.4) следует асимптотическая формула § 2. Трехмерный случай Содержание этого раздела излагается по следующему плану:

1) доказываем, что любой относительный минимум трехмерной решетки можно дополнить до базиса специального вида (лемма 2.2);

2) доказываем, что почти всегда это дополнение является единственным (следствие 2.1);

3) доказываем асимптотическую формулу (0.1) при = 3 (теорема 2.1).

Замечание 2.1. Пусть (R). По теореме Минковского о линейных формах для Возьмем любую пару (, ) 3. Дополним узел до базиса решетки узлами, следующим образом.

Согласно замечанию 2.1, найдется такой ненулевой узел, что | | <, = 1, 3. Выберем узел = (±1, 2, ±3 ) из условий Тогда 2 2 (иначе M()). Следовательно,, линейно независимые. Кроме того, хотя бы одна из координат отрицательная (иначе ( ) противоречит выбору ). Значит, возможны следующие три варианта комбинации знаков у координат :

В силу симметрии будем рассматривать только первый и второй случай.

Лемма 2.1. Пусть удовлетворяет (2.1), причем имеет вид (2.2) или (2.3).

Тогда существует узел = (1, 2, 3 ) такой, что {,, } — базис и |1 | 1, Доказательство. Из выбора и условия M() вытекает, что треугольник с вершинами в точках 0,, не содержит ненулевых узлов, кроме и. Значит,, можно дополнить до базиса некоторым узлом. Далее, всегда можно выбрать так, что |1 | 1. Пусть вторая координата вектора неотрицательная и наименьшая среди всех возможных, т.е. 0 2 |2 | для любого, удовлетворяющего условиям:

{,, } базис, |1 | 1. Предположим, что 2 2. Тогда, рассматривая узлы получаем противоречие с выбором. Значит, 2 < 2.

Пусть удовлетворяет (2.2) либо (2.3). Согласно лемме 2.1, существует (возможно не единственный) узел = (±1, ±2, 3 ) такой, что Исследуем свойства базиса {,, }. Определим следующие множества:

где 1, 2, 3 положительные, а остальные,, неотрицательные вещественные, причем Лемма 2.2. Возьмем любой узел, удовлетворяющий (2.1). Пусть выполняются (2.2) или (2.3). Тогда существует, удовлетворяющий (2.5), причем где = (,, ) — матрица со столбцами,,.

Доказательство. Пусть любой узел, удовлетворяющий (2.5). Как уже отмечалось ранее 2 2. Кроме того, 3 < 3 (иначе противоречит выбору ) и хотя бы одна координата отрицательная (иначе ( ) противоречит выбору ). Таким образом, достаточно рассмотреть следующие случаи:

Здесь и ниже, неотрицательные вещественные, причем 2, 3 > 0.

Если 1 + 1 1, то узел = ( + ) удовлетворяет условиям:

Это противоречит выбору. Значит 1 + 1 > 1 и 1.

противоречит выбору, т.е. этот случай невозможен.

Рассмотрим узел = (1, 2, 3 ) =. Имеем Значит, 3 = 3, т.е. 3 = 3. Тогда узел также удовлетворяет (2.5) и (,, ) Если 2 > 2 + 2, то узел ( ) противоречит выбору. Поэтому Тогда (иначе противоречит условию M()). Рассмотрим узел = (1, 2, 3 ) = + +. Тогда Тогда |3 | = 3 (иначе противоречит выбору ), т.е. 3 = 3. Следовательно, узел также удовлетворяет (2.5) и (,, ) 3.

Если 3 > 0, то узел () противоречит выбору. Значит, 3 = 0. Тогда узел = также удовлетворяет (2.5), причем Рассмотрим теперь вопрос: в каких случаях узел единственным образом дополняется до базиса указанным выше способом (т.е. когда узлы, однозначно определяются условиями (2.1), (2.5))?

Пусть внутренность множества, то есть для матриц из все неравенства, входящие в определение, являются строгими. Очевидно, что = при =.

Лемма 2.3. Пусть = (,, ) 4, решетка порождена векторами,,. Тогда не существует такого узла {0, ±, ±, ±}, что Доказательство. Пусть Нужно доказать, что |1 | > 1 либо |2 | > 2, либо |3 | > 3. Целые,, будем называть коэффициентами. Не умаляя общности считаем, что первая ненулевая координата вектора (,, ) является положительной. Случай, когда два коэффициента равны нулю является тривиальным. Всюду ниже,, натуральные.

Пусть ровно один из коэффициентов равен нулю. Тогда Пусть теперь все коэффициенты ненулевые. Возможны четыре случая.

Если 4, то Если 3, то Если 2, то Из леммы очевидным образом вытекает следующий результат.

Следствие 2.1. Пусть (,, ) 4, решетка порождена векторами,,. Тогда а) и являются единственными узлами, удовлетворяющими условиям (2.1) и (2.5) соответственно;

б) система {,, } является минимальной.

Мера и оператор проективизации : GL (R) P (R) определены в § II.1.

Теорема 2.1. Для любого целого > 1 среднее количество относительных минимумов трехмерных решеток равно где Доказательство. Будем использовать соотношение (0.1). Множество 3 ( ) разобьем на три (пересекающиеся) части:

(1) = {(, ) 3 ( ) : существует, удовлетворяющий (2.1) и (2.2)}, (2) = {(, ) 3 ( ) : существует, удовлетворяющий (2.1) и (2.3)}, (3) = {(, ) 3 ( ) : существует, удовлетворяющий (2.1) и (2.4)}.

В силу симметрии, Кроме того, где Докажем (2.7). Пусть (, ) (1). Согласно лемме 2.2 узел можно дополнить до базиса (,, ) так, что = (,, ) 1 2. Матрицы из 1 2 имеют положительный определитель. Следовательно, M3 (Z; ). Таким образом, каждой паре (, ) (1) мы можем поставить в соответствие (хотя бы одну) целочисленную матрицу из 1 2 определителя. Очевидно, что разным парам из (1) соответствуют разные матрицы. Значит, Возьмем любую целочисленную матрицу = (,, ) 1 2 с det =.

Рассмотрим решетку с базисом,,. Согласно следствию 2.1, и являются единственными узлами, удовлетворяющими условиям (2.1) и (2.5). Кроме того, (, ) (1). Значит, существует взаимно однозначное соответствие между 1 (Z; ) 2 (Z; ) и некоторым подмножеством (1). Поэтому Из (2.10), (2.11) вытекает (2.7). Соотношение (2.8) доказывается аналогично.

Для обоснования (2.9) достаточно заметить следующее. Если (, ) () (), то существует, как минимум, два узла, удовлетворяющих (2.1). Значит, матрица (,, ) не может лежать в 4 (иначе противоречие со следствием 2.1), т.е.

(,, ) принадлежит объединению границ множеств. Повторяя рассуждения, использованные при доказательстве (2.10), получаем (2.9).

Из (2.6), (2.7), (2.8), (2.9) вытекает асимптотическая формула Если (,, ) принадлежит некоторому, то система {,, } является минимальной по следствию 2.1. Поэтому, согласно теореме Минковского о линейных формах, Значит, множество = удовлетворяет условию (Б) главы II. Выполнение (А) очевидно. Поэтому мы можем применить теорему 1.1. Ввиду (( )) = 0, получаем Осталось подставить последние соотношения в (2.12), (0.1).

Замечание 2.2. По-видимому, постоянная (3) не выражается через известные.

Приближенные вычисления дали следующий результат:

Отметим, что § 3. Случай произвольной размерности Введем следующее отношение упорядоченности на R (лексикографическое). Пусть, R. Пишем, если существует такой номер {1,..., }, что =, -наименьшим вектором, если для любого другого. Любое конечное множество имеет единственный -наименьший вектор.

Возьмем любую пару (, ). Выберем ненулевые узлы (1),..., () решетки следующим образом.

1 шаг. Полагаем (1) =.

2 шаг. Определим множество 2 = 2 (; (1) ), состоящее из ненулевых, удовлетворяющих условиям:

Оно непусто согласно замечанию 2.1. Выберем узел (2) из условий:

Если таких узлов несколько, то в качестве (2) выбираем -наименьший. Отметим, что Действительно, в противном случае Это противоречит условию M().

k-й шаг. Пусть (1),..., (1) выбраны. Через = (; (1),..., (1) ) обозначаем множество, состоящее из таких ненулевых, что Оно непусто согласно замечанию 2.1. Узел () выбираем из условий:

Если таких узлов несколько, то в качестве () выбираем -наименьший. Отметим, что так как в противном случае () 1, однако 1 < 1, что противоречит выбору (1).

Набор {() } будем называть M-подходящей системой для пары (, ). Подчеркнем, что для любой пары (, ) существует единственная M-подходящая система.

Лемма 3.1. Пусть {() } — M-подходящая система для пары (, ). Тогда а) для любого {1,..., } справедливы оценки:

б) система (1),..., () линейно-независимая, причем в) справедлива оценка:

Доказательство. Докажем а). Так как (), то Учитывая (3.1), (3.2), получаем (3.3).

Докажем б). В силу (3.3) для любой нетождественной перестановки (1,..., ) из {1,..., } выполняется оценка Поэтому Докажем в). Если (3.5) не выполняется, то по теореме Минковского о линейных формах [54, глава III, § 2, теорема III] существует такой ненулевой узел, что Но тогда (; (1),..., (1) ), причем | | <. Это противоречит выбору ().

Пусть (1),..., () M-подходящая система для пары (, ). Хорошо известно (см., например, [54, глава I, следствие 2]), что существует единственный базис (1),..., () решетки такой, что то есть причем неотрицательные целые удовлетворяют условиям:

Так как (1) = M(), то 11 = 1, то есть (1) = (1) =.

Систему (1), (2),..., () будем называть M-подходящим базисом, а соответствующую матрицу = (( )) (со столбцами (1),..., () ) M-подходящей базисной матрицей для пары (, ).

Для любой пары (, ) существует единственный M-подходящий базис.

равен при и равен нулю при >. Пусть = (( )). Тогда (3.6) можно записать в виде Лемма 3.2. Пусть {() } — M-подходящий базис, а {() } — M-подходящая система для пары (, ). Тогда Доказательство. Используя (3.4), (3.7), получаем det > 0, det > 0. Поэтому (3.9) вытекает из (3.8). Кроме того, Ввиду (3.5) и равенства det = det, приходим к (3.10).

Для доказательства (3.11) достаточно учесть, что для любого и применить математическую индукцию. Оценка (3.12) следует из (3.5), (3.11).

Нам понадобится следующий вспомогательный результат.

Лемма 3.3. Пусть, — некоторые положительные постоянные, (R).

Пусть (1),..., () — такой базис решетки, что Тогда любой узел, удовлетворяющий неравенствам Доказательство. Используя формулы Крамера, получаем где = det, = (( )), а определитель матрицы, полученной из, заменой -го столбца на. Осталось заметить, что Пусть M, множество, состоящее из всех M-подходящих базисных матриц для пар (, ). Рассмотрим cвойства M,.

Многогранным углом в пространстве R с вершиной в точке 0 будем называть множество решений R некоторой конечной системы линейных однородных неравенств, т.е. множество, состоящее из R, удовлетворяющих соотношениям вида:

где 1, 2 неотрицательные целые, а, R.

Определим отображение, которое каждой невырожденной матрице = (( )) ставит в соответствие пару (, ), где = (1), а решетка с базисом {() } (т.е.

столбцы образуют базис ). Тогда множество M, состоит из матриц таких, что () = (, ), причем матрица является M-подходящей для пары (, ).

Теорема 3.1. Справедливы следующие свойства:

а) взаимно однозначно отображает M, на ;

б) для любой матрицы = (( )) M, имеет место оценка:

в) M, является объединением фиксированного числа множеств вида где — многогранные углы из R с вершинами в точке 0.

Доказательство. Утверждение а) вытекает из определений, а б) эквивалентно (3.12).

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

Определим множество GL (R), состоящее из матриц GL (R), у которых элементы первого столбца положительные.

Возьмем любую = (( )) GL (R). Пусть (, ) = (). Тогда M,, если и только если M() и существует M-подходящая система (для пары (, )), которая определяется формулами (3.6), где целые числа, удовлетворяющие (3.7).

Согласно леммам 3.1, 3.2, M-подходящая система должна удовлетворять оценкам ров целочисленных коэффициентов = (11, 12,..., ) для которых выполняются (3.7), (3.10), причем 11 = 1. Тогда M, можно представить в виде:

где состоит из матриц = (( )) GL (R), удовлетворяющих следующим условиям (в которых () определяются (3.6), а (, ) = ()):

1) выполняются оценки (3.3) для () ;

2) M(); система {() } является M-подходящей для пары (, ).

Подчеркнем, что коэффициенты в (3.6) однозначно определяются по.

Так как множество конечное, то осталось доказать, что каждое удовлетворяет в).

полняется условие 1). Очевидно, что удовлетворяет в). Рассмотрим некоторые свойства множества.

Возьмем любую матрицу = (( )). Пусть = (( )). Тогда и поэтому где 3 = (!)+1 · 2(1). Кроме того, используя (3.6), (3.7), (3.10), имеем Положим (, ) = () и определим множества Матрица не принадлежит, если и только если не выполняется условие 2), то есть существует узел {0}, удовлетворяющий одному из следующих двух условий:

i) | |, = 1,, причем хотя бы одно из неравенств строгое;

ii) существует такой номер {2,..., }, что () и либо | | <, либо Условие i) означает, что M(), а ii) {() } не является M-подходящей системой. Используя (3.14), получаем, что в обоих случаях Применяя лемму 3.3 (с учетом (3.13)), мы видим, что любой, удовлетворяющий i) или ii), представим в виде где 4 некоторая постоянная, зависящая только от. Значит, где, ( = (1,..., )) состоит из матриц таких, что выполняется i) или ii), в которых = 1 (1) +...+ (). Каждое из множеств, удовлетворяет в). Значит, это условие выполняется и для. Следовательно, также удовлетворяет в).

det =. Тогда Поэтому, используя теорему 3.1 а), получаем Замечание 3.1. Пусть -мерная решетка. Из утверждения а) теоремы 3.1 вытекает, что множество относительных минимумов с положительными координатами совпадает с множеством первых столбцов матриц M, (), где () множество всех базисных матриц.

Оператор проективизации и мера определены в § II.1.

Теорема 3.2. Для любых целых, 2 справедлива следующая асимптотическая формула для среднего количества относительных минимумов:

где Доказательство. Используя (0.1) и (3.15), получаем Осталось заметить, что множество M, удовлетворяет условиям (А), (Б) главы II (см. теорему 3.1) и применять теорему II.1.1 для вычисления #M, (Z; ).

§ 4. Оценки постоянной () Теорема 4.1. Для любого простого и целого 2 справедливы оценки Доказательство. Пусть M+ () множество относительных минимумов решетки где Так как простое, то согласно формулам (II.2.3), Кроме того, # ( ) = 1. У любой решетки из (Z; ) количество относительных минимумов оценивается величиной (ln1 ). Поэтому, используя (0.1), заключаем где (, ) количество решеток ( ) таких, что M(). Поэтому достаточно доказать следующие оценки:

Другими словами, (, ) совпадает с количеством решений Z1 ( ) сравнения а (,, ) равно количеству решений Z1 ( ) системы сравнений Для любого натурального и вещественного 2 определим множество Нетрудно проверить, что Следовательно, Докажем второе неравенство из (4.1). Если (Z, ), M+ (), то ( ) по теореме Минковского о линейных формах. Поэтому, используя (4.2), (4.3), получаем Второе неравенство из (4.1) доказано.

Осталось доказать первую оценку из (4.1). Пусть (Z, ),. Положим Если M(), то множество () содержит хотя бы один узел решетки. Поэтому Ввиду (4.2), имеем Возьмем любую постоянную (0, 1). Согласно (4.3), (4.4), Следовательно, Выбирая = 1/21, получаем первое неравенство из (4.1).

Следствие 4.1. Для любого целого 2 справедлива оценка Доказательство. Пусть { } последовательность простых чисел, занумерованных по возрастанию. По определению, Осталось применить теорему 4.1.

Статистические свойства многогранников Клейна () множество вершин полиэдров Клейна решетки ;

() множество компактных гиперграней полиэдров Клейна решетки ;

(, ) множество граней из () типа (грань () принадлежит типу, если для любой базисной матрицы решетки многогранник 1 · имеет целочисленно-линейный тип );

3 множество допустимых типов компактных гиперграней многогранников Клейна трехмерных решеток, т.е. 3 3 (R) : (, ) =.

Кроме того, среднее число граней типа и вершин многогранников Клейна целочисленных -мерных решеток определителя.

В настоящей главы мы докажем следующие асимптотические формулы где 3, положительная постоянная, зависящая только от, а абсолютная положительная постоянная. Также мы получим двусторонние оценки для ( ; ) в случае произвольной размерности.

§ 1. Оценки количества элементов многогранников Клейна Оценки количества вершин многомерных полиэдров Клейна Пусть N, > 1. В этом разделе мы докажем следующую нижнюю оценку для среднего числа вершин многогранников Клейна:

Так как любая вершина многогранника Клейна является относительным минимумом (см. [13, 24]), то для любой целочисленной решетки Поэтому из неравенства (1.1) и известных оценок (0.3.2) для максимального количества относительных минимумов следуют следующие двусторонние оценки для среднего и максимального числа вершин многогранников Клейна решеток из (Z; ):

Доказательство соотношения (1.1) основано на идеях [1].

Лемма 1.1. Для любого = (1,..., ) Z {0} существует целочисленная унимодулярная матрица GL (Z) такая, что Доказательство вытекает, например, из следствия II.2.1.

количество решеток из (Z; ), содержащих узел. Согласно лемме 1.1, (, ) равно количеству решеток (Z; ), которые содержат узел (, 0,..., 0). Применяя теорему II.2.1, получаем формулу где суммирование ведется по всем (1,..., ) N таким, что 1 | и 1 ·... · =.

(Если использовать обозначения теоремы 2.1, то = ).

Следствие 1.1. Пусть = (1,..., ) [1, +). Тогда где суммирование ведется по всем таким (1,..., ) Z, что | |.

Доказательство. Пусть = 1 ·... ·. Для любого Z определим Используя (1.3), получаем Для любого натурального определим множество Кроме того, если, (1, ), Z, то+ Лемма 1.2. Пусть – конечное множество из R. Тогда для любых N,, (1, ) справедлива оценка где 1 = ( 1)!/(!( 1 )!) — биномиальный коэффициент.

Лемма является тривиальным следствием из [1, лемма 2].

Теорема 1.1. Пусть каждой решетке (Z; ) поставлено в соответствие конечное множество () {0}, причем существует такая положительная постоянная > 0, что из условий вытекает Тогда справедлива оценка Доказательство. Пусть = 3 · () ·. Возьмем любую постоянную такую, что Подчеркнем, что зависит только от и. Положим Не умаляя общности, считаем, что 1 (т.е. ). Тогда для любого Z Используя лемму 1.2, получаем где Из (1.5) и условий теоремы вытекает, что для любых Z, (Z; ) найдется такой узел (), что Поэтому Используя следствие 1.1 и соотношения (1.5), получаем Из последнего соотношения и асимптотической формулы вытекает, что Следовательно, Учитывая условие (1.4) и определение, получаем утверждение теоремы.

Согласно теореме Минковского о линейных формах, множество относительных минимумов () = M() удовлетворяет условиям теоремы 1.1, где = 1. Докажем, что множество вершин () = () также удовлетворяет условиям теоремы 1.1.

Лемма 1.3. Пусть (R). Тогда для любого ненулевого узла решетки найдется такая вершина (), что Доказательство. Не умаляя общности считаем, что [0, +). Пусть – точка пересечения отрезка [0, ] и границы полиэдра Клейна решетки. Согласно теореме Каратеодори (см., например, [30]) точку можно представить в виде где Пусть = max{1,..., }. Тогда 1/, и поэтому Вершина = () удовлетворяет требуемым условиям.

Следствие 1.2. Пусть (Z; ). Тогда для любой точки R, удовлетворяющей условию существует такая вершина (), что Доказательство. Согласно теореме Минковского о линейных формах найдется ненулевой узел такой, что Осталось воспользоваться леммой 1.3.

Согласно следствию 1.2 множество вершин () = () удовлетворяет условиям теоремы 1.1, в которых =. Поэтому имеет место следующий результат.