close

Вход

Забыли?

вход по аккаунту

?

166541

код для вставкиСкачать
На правах рукописи
Илларионов Андрей Анатольевич
Статистические свойства
полиэдров Клейна
и локальных минимумов решеток
01.01.06 — математическая логика, алгебра и теория чисел
Автореферат
диссертации на соискание ученой степени
доктора физико-математических наук
Хабаровск – 2014
Общая характеристика работы
Актуальность темы. Алгоритм разложения вещественного числа в непрерывную (цепную) дробь является одним из важнейших
инструментов теории чисел, восходящим еще к античному алгоритму Евклида нахождения наибольшего общего делителя. Начало
современной теории непрерывных дробей положил в 1613 г. П. Катальди и продолжил Д. Валлис, предложивший термин «непрерывная дробь». Применялись эти дроби в первую очередь для рационального приближения вещественных чисел; например, Х. Гюйгенс
использовал их для проектирования зубчатых колес своего планетария. Алгоритм цепных дробей занял видное место в теории чисел
после трудов Л. Эйлера и Ж. Лагранжа, которые применили его к
решению уравнения Пелля, что привело к пониманию фундаментальной роли непрерывных дробей в теории квадратичных иррациональностей. Эйлер открыл, а Лагранж доказал одно из важнейших свойств: «непрерывная дробь периодична только у квадратичных иррациональностей». Еще одним основополагающим результатом является теорема Лагранжа о наилучших приближениях
вещественных чисел с помощью подходящих дробей. Исследование
иррациональностей степени три и выше, а также поиск многомерных наилучших приближений привели к необходимости обобщения
цепных дробей на многомерный случай.
Первое формальное обобщение алгоритма непрерывных дробей было дано Эйлером1 , идеи которого развивали и дополняли
К. Якоби, А. Пуанкаре, П. Бахман, О. Перрон и другие авторы.
Следующий этап начал Л. Дирихле, а продолжили Л. Кронекер,
Ш. Эрмит, Шарв, Е. Золотарев, которые пытались построить обобщение непрерывной дроби, имеющее для общей теории алгебраических чисел такое же значение, какое имеют цепные дроби для
квадратичных числовых полей. Черту под этими исследованиями
подвел Г.Ф. Вороной. В 1896 г. он защитил диссертацию «Об одном обобщении алгорифма непрерывных дробей», в которой дал
метод нахождения основных единиц кубического числового поля
как положительного, так и отрицательного дискриминанта. Алго1
“De relatione inter ternas pluresve quantitates instituenda”, Leonhardi Euleri
Commentationes arithmeticae collectae, т. II, С.-Петербург, 1849, с. 99
3
ритм основан на рассмотрении взаимного расположения некоторых
специальных узлов решеток. Эти узлы Вороной называл «относительными минимумами». Одновременно и независимо от Вороного минимумы трехмерных решеток изучал Г. Минковский2 , который использовал термин «локальный минимум» (исследования
Минковского относятся к случаю чисто вещественного расширения
числового поля).
Относительные (локальные) минимумы решеток представляют собой геометрическую интерпретацию многомерных наилучших
приближений. Они являются естественным объектом с точки зрения целочисленного линейного программирования, а также возникают при изучении теоретико-числовых квадратурных формул3 и
в теории равномерного распределения4 .
Еще одно интересное геометрическое обобщение непрерывных
дробей было дано Ф. Клейном5 в 1895 г., и основано на рассмотрении, так называемых, полиэдров (многогранников) Клейна которые определяются как выпуклая оболочка узлов решетки, лежащих в заданном симплициальном конусе. Исходно исследуя Aградуированные алгебры6 , В.И. Арнольд столкнулся с теорией многомерных непрерывных дробей. Начиная с 1989 г. он сформулировал множество задач о геометрических и статистических свойствах многогранников Клейна7 , возобновляя тем самым интерес к
этим вопросам. Различные аспекты теории полиэдров Клейна изучали Х. Цутихаси (1983), Б.Ф. Скубенко (1988, 1990), Ж. Лашо
(1993, 1998, 2002), Е.И. Коркина (1994-1996), А.Д. Брюно, В.И. Парусников (1994–2005), Ж.О. Муссафир (2000), О.Н. Герман (2002–
2008), О.Н. Карпенков (2004–2013), В.А. Быковский (2006) и другие авторы. Однако задачи Арнольда о статистических свойствах
полиэдров Клейна по-прежнему остаются малоизученными. В из2
H. Minkowski, “Generalisation de la theorie des fraction continues”, Ann. Sci.
Ècole Norm. Sup. Ser. 3. 13:2 (1896), 41–60.
3
В. А. Быковский, ДАН, 382:2 (2003), 154–155.
4
В. А. Быковский, Изв. РАН. Сер. матем., 76:3 (2012), 19–38.
5
F. Klein, “Ueber die geometrische Auffassung der gewohlichen
Kettenbruchentwichlung” Nachr. Ges. Wiss. Göttingem, № 3 (1895), 357–359.
6
V. I. Arnold, Commun. Pure Appl. Math., 142 (1989), 993–1000.
7
«V. I. Arnold, Amer. Math. Soc. Transl., 197:2 (1999), ix-xii», «Задачи Арнольда, М.: Фазис, 2000.»
4
вестной работе М.Л. Концевича и Ю.М. Сухова8 аннонсированы
некоторые результаты о существовании статистик для многогранников Клейна и предложена схема их доказательства. В диссертации Ж.О. Муссафир9 некоторые из этих статистик вычислены
приближенно. В статье О.Н. Карпенкова10 сформулированы гипотезы о частоте появления многогранника заданного целочисленнолинейного типа в качестве грани полиэдра Клейна.
В двумерном случае конструкции Клейна и Вороного – Минковского совпадают и их статистические свойства непосредственно вытекают из теории непрерывных дробей. Однако, несмотря на
значительный интерес, практически отсутствуют результаты для
решеток размерности три и выше. Восполнению этого пробела и
посвящена настоящая диссертация.
Целью работы является исследование статистических свойств
локальных минимумов и полиэдров Клейна многомерных решеток.
Научная новизна. В диссертации разработан метод исследования статистических свойств многомерных непрерывных дробей по
Клейну и Вороному – Минковскому. Он позволил ответить на некоторые вопросы В.И. Арнольда о свойствах многогранников Клейна
и получить ряд асимптотических формул для средних характеристик локальных минимумов, которые можно рассматривать, как
многомерное обобщение классических результатов о вероятностных свойствах цепных дробей. К основным можно отнести следующие результаты диссертации.
1. Доказаны правильные, с точностью до констант, зависящих
от размерности, верхние оценки для максимального количества относительных минимумов целочисленных неполных решеток и максимального количества относительных минимумов неполных (нецелочисленных) решеток, лежащих в заданном кубе. Также получены двусторонние оценки для среднего
8
M. L. Kontsevich, Yu. M. Suhov, Amer. Math. Soc. Trasl., 197:2 (1999), 9–27.
J.-O. Moussafir, Voiles et polyèdres de Klein: Géométrie, algorithmes et
statistiques, Doc. Sci. Thése, Univ. Paris IX–Dauphine, 2000.
10
О. Н. Карпенков, Тр. МИАН, 258 (2007), 79–92.
9
5
количества вершин полиэдров Клейна целочисленных многомерных решеток фиксированного определителя.
2. Впервые изучено поведение в среднем количества локальных
минимумов многомерных целочисленных решеток. А именно
получена асимптотическая формула для среднего числа локальных минимумов целочисленных многомерных решеток с
определителем из заданного отрезка. Также доказано многомерное обобщение классической теоремы Хейльбронна о средней длине конечной непрерывной дроби в терминах относительных минимумов.
3. Получены асимптотические формулы для среднего числа граней фиксированного типа и вершин полиэдров Клейна трехмерных целочисленных решеток фиксированного определителя.
4. Выведены асимптотические формулы для среднего числа наилучших приближений линейных форм с рациональными коэффициентами и математического ожидания количества наилучших приближений форм с вещественными коэффициентами.
Методы исследования: элементарная и аналитическая теория
чисел, геометрия чисел, теория приведения квадратичных форм,
теория локальных минимумов Вороного и Минковского.
Теоретическая и практическая значимость. Работа носит
теоретический характер. Разработанные методы и полученные результаты могут быть использованы для дальнейшего анализа статистических и геометрических свойств локальных минимумов, полиэдров Клейна и диофантовых приближений, а также для оценки
сложности некоторых алгоритмов целочисленного линейного программирования.
Апробация работы. Основные результаты диссертации докладывались на следующих семинарах и конференциях.
6
• Научный семинар ХО ИПМ ДВО РАН (рук. В.А. Быковский), 2006–2014 гг.
• Московский семинар по теории чисел (МГУ, рук. Ю.В. Нестеренко, Н.Г. Мощевитин), 2011, 2014.
• Семинар «Современные проблемы теории чисел» (МИАН, рук.
С.В. Конягин, И.Д. Шкредов), 2011, 2014.
• Семинар «Дискретная геометрия и геометрия чисел» (МГУ,
рук. Н.Г. Мощевитин), 2011.
• International Conference on Number Theory (Шяуляй, Литва,
11-15 августа, 2008).
• «XXXII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова» (Владивосток, 29 августа – 4
сентября 2008).
• Международная конференция «Фундаментальные проблемы
математики и информационных наук» (Хабаровск, 25–30 июня
2009)
• Международная конференция «27th Journée Arithmétiques»
(Вильнюс, Литва, 27 июня – 1 июля 2011).
• Международная конференция «Diophantine Approximation. Current State of Art and Applications» (Минск, Беларусь, 3–8 июля
2011).
• Международная конференция «Toric Topology and Automorphic
Functions» (Хабаровск, 5–10 сентября 2011).
• Международная конференция «Diophantine Analysis» (Астрахань, июль 2012).
• Международная конференция «Multidimensional Continued Fractions» (Грац, Австрия, 22–26 июня 2013).
• Международная конференция «28th Journée Arithmétiques»
(Гренобль, Франция, 1–5 июля 2013).
7
• Международная конференция «Torus Actions: Topology, Geometry and Number Theory» (Хабаровск, 2–7 сентября 2013).
Публикации. Основные результаты диссертации опубликованы в работах [1]–[16]. В совместных статьях [2, 3] вклад соавторов
одинаков. Работы [1]–[12] опубликованы в научных журналах, входящих в перечень ВАК.
Структура и объем диссертации. Диссертация изложена на
164 страницах, состоит из введения, шести глав, приложения и
списка используемой литературы, включающего 134 наименования.
8
Содержание работы
В о в в е д е н и и излагается краткая история изучаемых вопросов, формулируются основные определения и результаты диссертации. Дадим необходимые определения.
Пусть Γ — решетка в Rs .
Ненулевой узел γ решетки Γ будем называть относительным
минимумом, если не существует ненулевого узла γ ′ ∈ Γ такого, что
|γi′ | ≤ |γi |,
i = 1, s,
причем хотя бы одно из неравенств является строгим.
Возьмем любую функцию f : Rs−1 → [0, +∞). Ненулевой узел
γ решетки Γ будем называть цилиндрическим f -минимумом, если
не существует узла γ ′ ∈ Γ \ {0} такого, что
′
f (γ1′ , . . . , γs−1
) ≤ f (γ1 , . . . , γs−1 ),
|γs′ | ≤ |γs |,
причем хотя бы одно из неравенств является строгим.
Рассмотрим теперь более общую конструкцию, включающую в
себя и относительные, и цилиндрические минимумы.
Пусть Φ = (Φl , . . . , Φr ) : Rs → [0, +∞)r . Ненулевой узел γ решетки Γ будем называть локальным Φ-минимумом, если не существует ненулевого узла η ∈ Γ такого, что
Φl (η) ≤ Φl (γ),
l = 1, r,
причем хотя бы одно из неравенств строгое.
Далее всюду мы считаем, что функции Φl имеют вид
Φ1 (x) = ϕ1 (x1 , . . . , xs1 ), . . . , Φr (x) = ϕr (xsr−1 +1 , . . . , xs ),
(1)
т.е. Φl (x) = ϕl (xsl−1 +1 , . . . , xsl ), l = 1, r. Здесь s0 , . . . , sr — такие
целые, что
0 = s0 < s1 < . . . < sr = s,
а ϕl : Rtl → R (tl = sl − sl−1 , l = 1, r) — лучевые11 , непрерывные,
кусочно-дифференцируемые функции.
Функция ϕ : Rt → R называется лучевой, если для любых x ∈ Rt \ {0},
λ ∈ R справедливы соотношения 0 < ϕ(x); ϕ(λx) = |λ| · ϕ(x).
11
9
Алгоритм Г.Ф. Вороного основан на следующих соображениях.
Пусть K — чисто вещественное расширение степени s поля рацио(1)
(1)
нальных чисел Q. Возьмем любой базис ω1 , . . . , ωs , состоящий из
(i)
(i)
целых поля K. Пусть ω1 , . . . , ωs — сопряженные базисы (i = 2, s),
∑
(1)
а K ′ — порядок поля K. Для любого α = sj=1 nj ωj ∈ K ′ определим геометрическое изображение γ(α) числа α по формулам
γ(α) = (γ1 (α), . . . , γs (α)),
(i)
γi (α) = n1 ω1 + . . . + ns ωs(i) .
Тогда, если α — единица поля K, то γ(α) является относительным
минимумом решетки Γ = {γ(α) : α ∈ K ′ }.
В общем случае геометрическое изображение единицы числового поля степени s = s1 + 2s2 (s1 — количество вещественных,
а 2s2 — количество комплексных изоморфизмов K в C) является
локальным Φ-минимумом некоторой s-мерной решетки, если положить
r = s1 + s2 ,
Φi (x) = |xi |, i = 1, s1 ,
√
Φl (x) = x2s1 +2l−1 + x2s1 +2l , l = 1, s2 .
Г.Ф. Вороной доказал ряд важных свойств относительных и
цилиндрических минимумов трехмерных решеток и с их помощью
разработал метод нахождения единиц в кубических полях.
Рассмотрим теперь связь между наилучшими приближениями
и локальными минимумами. Дробь P/Q (P ∈ Z, Q ∈ N) называется
наилучшим приближением (второго рода) вещественного α, если
не существует дроби P ′ /Q′ (P ′ ∈ Z, Q′ ∈ N) такой, что
|Q′ α − P ′ | ≤ |Qα − P |,
Q′ ≤ Q,
причем хотя бы одно из неравенств строгое.
По определению, для любого вещественного α множество относительных минимумов решетки
Γα = {(Q, Q · α − P ) : Q, P ∈ Z}
состоит из ±(0, 1) и точек вида ±(Q, Qα−P ), где P/Q — наилучшее
приближение α. Поэтому классическую теорему Лагранжа можно
10
сформулировать следующим образом: если α ∈ [0, 1) \ {1/2}, то
множество относительных минимумов решетки Γα состоит из
следующих узлов:
±(0, 1),
±(Qn , αQn − Pn ),
(2)
где n = 0, 1, 2, . . ., если α ∈ [0, 1/2) и n = 1, 2, . . ., если α ∈ (1/2, 1);
при этом P0 /Q0 = 0/1 и Pn /Qn = [q1 , . . . , qn ] — n-я подходящая
дробь для α (с неполными частными qi = qi (α)).
Рассмотрим теперь многомерные обобщения понятия наилучшего приближения. Пусть f : Rn → [0, +∞). Ненулевой вектор
(u, v) ∈ Zn × Z называется f -наилучшим приближением линейной формы L : Rn → R, если не существует ненулевого вектора
(u′ , v ′ ) ∈ Zn × Z такого, что
|Lu′ − v ′ | ≤ |Lu − v|,
f (u′ ) ≤ f (u),
причем хотя бы одно из неравенств строгое.
Возьмем теперь две функции: f : Rm → [0, +∞) и g : Rn →
[0, +∞). Рассмотрим линейные формы L = (L1 , . . . , Lm ) : Rn →
Rm . Ненулевой вектор (u, v) ∈ Zn × Zm будем называть (f, g)наилучшим совместным приближением линейных форм L, если
не существует ненулевого вектора (u′ , v ′ ) ∈ Zn × Zm такого, что
f (Lu′ − v ′ ) ≤ f (Lu − v),
g(u′ ) ≤ g(u),
причем хотя бы одно из неравенств строгое.
Наилучшие приближения неявно использовались еще Г.Ф. Вороным, В. Ярником и другими авторами. По-видимому, систематическое изучение многомерных наилучших приближений было начато Дж. Лагариасом. Ссылки и более подробный обзор можно найти
в статье Н. Шевалье12 .
По определению, задача о нахождении наилучших приближений эквивалентна задаче о вычислении локальных минимумов решеток специального вида. Действительно, определим (n + m)-мерную решетку Γ, состоящую из узлов γ(u, v) = (u, Lu − v), где
(u, v) ∈ Zn × Zm . Положим
r = 2,
Φ1 (x) = g(x1 , . . . , xn ),
12
Φ2 (x) = f (xn+1 , . . . , xn+m ).
N. Chevallier, Moscow Journal of Combinatorics and Number Theory, 3:1
(2013), 3–56
11
В этом случае γ(u, v) является локальным Φ-минимумом решетки
Γ тогда и только тогда, когда (u, v) есть (f, g)-наилучшее совместное приближение линейных форм L.
Рассмотрим теперь геометрическую интерпретацию непрерывной дроби, предложенную Ф. Клейном. Возьмем любую s-мерную
решетку Γ и симплициальный конус C ⊂ Rs с вершиной в начале
координат 0. Множество K = K(Γ, C), которое является выпуклой оболочкой ненулевых узлов Γ, содержащихся в C, называется
полиэдром Клейна решетки Γ для конуса C. Пусть линейное отображение L : Rs → Rs является невырожденным. Тогда LK является полиэдром Клейна решетки LΓ для конуса LC. Подходящим
образом выбирая L, можно придти к случаю LΓ = Zs (решетка
фиксирована) либо к случаю LC = [0, +∞)s (конус фиксирован).
В оригинальной конструкции Клейна рассматривался произвольный конус и фиксированная решетка Zs . Нам будет удобнее рассматривать случай, когда решетка является произвольной, а конус
фиксированым. Будем придерживаться следующей терминологии.
Пусть θ = (θ1 , . . . , θs ), где θi = ±1. Множество Kθ (Γ), которое
является выпуклой оболочкой ненулевых узлов Γ, лежащих в угле
{x ∈ Rs :
θi xi ≥ 0, i = 1, s},
будем называть полиэдром Клейна решетки Γ.
В двумерном случае конструкция Клейна дает следующую геометрическую интерпретацию непрерывной дроби. Для любого α ∈
(0, 1/2) множество вершин полиэдров Клейна решетки Γα = {(Q, Q·
α − P ) : Q, P ∈ Z} совпадает с множеством относительных минимумов и поэтому состоит из точек (2). Кроме того, если
a = (Qn−1 , αQn−1 − Pn−1 ) и b = (Qn+1 , αQn+1 − Pn+1 )
— вершины некоторой стороны многоугольника Клейна, то #(Γ ∩
(a, b]) = qn+1 , т.е. «целочисленная» длина отрезка [a, b]) равна (n +
1)-му неполному частному.
Г л а в а I посвящена выводу оценок для максимального количества локальных минимумов решеток.
Хорошо известен следующий результат, характеризующий скорость роста знаменателей подходящих дробей, если Qk = Qk (α) —
12
знаменатель k-й подходящей дроби для α ∈ R, то Qk ≥ 2(k−1)/2 .
Поэтому
∀P ≥ e
#{k : Qk (α) ≤ P } = O(ln P ).
(3)
Аналогичные оценки справедливы и для многомерных наилучших
приближений13 . Из (3) вытекает, что для любой двумерной решетки Γ с базисом (0, 1), (1, α)
#{γ ∈ M(Γ) : |γ|∞ ≤ P } ≪ ln P.
Здесь и далее M(Γ) — множество относительных минимумов решетки Γ. Мы распространяем этот результат на случай решеток
произвольной размерности и ранга.
Напомним, что любая s-мерная решетка Γ ранга t имеет вид
{
}
(1)
(t)
Γ = n1 a + . . . + nt a : ni ∈ Z, i = 1, t ,
где a(1) , . . . , a(t) — некоторые линейно-независимые векторы из Rs
(базис Γ). Матрицу со столбцами a(1) , . . . , a(t) будем называть базисной. Если t = s, то решетка называется полный, если t < s, то
неполной.
Для полных целочисленных решеток известны следующие верхняя14 и нижняя15 оценки максимального количества относительных минимумов:
sup
#M(Γ) ≍ lns−1 N + 1,
s
Γ∈Ls (Z;N )
где Ls (Z; N ) — множество целочисленных полных s-мерных решеток определителя N ∈ N. Ряд работ был посвящен уточнению соответствующих констант. Наилучший результат16 имеет вид
2s
1
,
≤ C(s) ≤
(s
−
1)!
(s − 1)! · 100 · logs−1
(128s)
2
13
(4)
J. C. Lagarias, J. Austral. Math. Soc. Ser. A, 34:1 (1983), 114–122.
В. А. Быковский, ДАН, 382:2 (2003), 154–155.
15
М. О. Авдеева, Фундамент. и прикл. матем., 11:6 (2005), 9–14.
16
М. О. Авдеева, В. А. Быковский, Матем. заметки, 87:4 (2010), 483–491.
14
13
где

sup
#M(Γ)
 Γ∈Ls (Z,N )
C(s) = lim sup 
lns−1 N
N →+∞


.
Рассмотрим теперь произвольную решетку Γ. Тогда множество
M(Γ) может оказаться бесконечным. Для любого P > 0 определим
множество
M(Γ, P ) = {γ ∈ M(Γ) : |γ|∞ ≤ P },
где |γ|∞ = max1≤i≤s |γi | — sup-норма γ.
В §§ 1, 2 главы I доказываются следующие результаты.
Теорема 1 ([5]). Пусть Γ — s-мерная решетка Γ ранга t. Определим λ = min{|γ|∞ : γ ∈ Γ \ {0}}. Тогда для любого P ≥ λ
#M(Γ, P ) ≪ lnt−1 (P/λ) + 1.
s,t
(5)
Отметим, что если Γ — t-мерная алгебраическая решетка, то
для любого P ≥ 1
#M(Γ, P ) ≫ lnt−1 P + 1.
Γ
Это означает, что неравенство (5) является правильным с точностью до константы, зависящей только от t и s.
Следствие 1 ([1]). Для любой целочисленной s-мерной решетки
Γ ранга t справедлива оценка
#M(Γ) ≪ lnt−1 D + 1,
s,t
где D = D(Γ) — максимум из модулей миноров t-го порядка базисной матрицы решетки Γ.
В последнем параграфе главы I доказывается оценка для максимального количества локальных Φ-минимумов.
Теорема 2. Пусть выполняются условия (1). Тогда для любой
полной целочисленной s-мерной решетки Γ справедлива оценка
#MΦ (Γ) ≪ lnr−1 det Γ + 1,
Φ
где MΦ (Γ) — множество локальных Φ-минимумов решетки Γ.
14
В г л а в е II рассматривается вопрос о количестве целочисленных точек на детерминантной поверхности.
Пусть Ms (Z; N ) — множество целочисленных матриц размера
s×s определителя N . Исследование статистических свойств конечных непрерывных дробей приводит к задачам об асимптотическом
распределении целочисленных матриц размера 2 × 2, лежащих в
заданной области. Например, вычисление средней длины непрерывной дроби для рациональных чисел фиксированного знаменателя N сводится к нахождению количества матриц M ∈ M2 (Z; N )
следующего вида
)
(
a1 b1
M=
,
0 < b 1 < a 1 , 0 < a 2 < b2 .
−a2 b2
Аналогичным образом при исследовании статистических свойств
многомерных аналогов непрерывных дробей возникает задача: найти величину #(Ω ∩ Ms (Z, N )), где Ω — заданное подмножество
GLs (R).
Известен следующий результат. Если
Ω = {t · X :
X ∈ Ω′ , t ∈ (0, +∞)},
(6)
где Ω′ — измеримое по Жордану множество из SL+
s (R) = {X ∈
GLs (R) : det X = 1}, то
#(Ω ∩ Ms (Z, N )) ∼
#Ls (Z; N )
· µH (Ω′ ) при N → +∞,
ζ(2) · . . . · ζ(s)
(7)
где µH — мера Хаара на группе SL+
s (R). Отметим, что справедлива
следующая оценка для количества полных s-мерных целочисленных решеток определителя N :
∑
s−1
#Ls (Z; N ) ≍ N
· σ−1 (N )
(σ−1 (N ) =
d−1 ).
d|N
Формула (7) доказана Ю.В. Линником и Б.Ф. Скубенко17 при s =
2, 3 и Б.Ф. Скубенко18 для произвольного s ≥ 2.
17
18
Ю. В. Линник, Б. Ф. Скубенко, Вестник ЛГУ, № 13 (1964), 25–36.
Б. Ф. Скубенко, Тр. МИАН СССР, 80 (1965), 129–144.
15
Условие (6) означает, что множество Ω инвариантно относительно левого действия группы, составленной из диагональных матриц X, у которых xii = xjj > 0, i, j = 1, s. Множества матриц,
которые возникают в настоящей работе, являются инвариантными
относительного левого действия группы Ds (R+ ), состоящей из всех
диагональных матриц с положительными элементами на главной
диагонали. Такие множества являются более «широкими», нежели
множества, удовлетворяющие (6).
В главе II рассматривается случай, когда множество Ω ⊂ GLs (R)
обладает следующими свойствами:
{
}
(А) Ω = ((xij )) : (xi1 , . . . , xis ) ∈ Vi , i = 1, s , где Vi — конусы в
Rs с липшицевыми границами;
(Б) существует такая постоянная C > 0, что для любой X ∈ Ω
s
∏
i=1
max |xij | ≤ C · det X.
1≤j≤s
Подчеркнем, что такое Ω нельзя представить в виде конечного
объединения множеств, удовлетворяющих (7). Поэтому результаты
Линника – Скубенко становятся неприменимыми в этом случае.
Согласно (А), множество Ω инвариантно относительно левого
действия группы Ds (R+ ). Рассмотрим s(s−1)-мерное многообразие
Ps (R) = Ds (R+ )\GLs (R)
— проективизацию группы GLs (R) относительно левого действия
группы Ds (R+ ). Пусть P(Ω) — образ множества Ω ⊂ GLs (R) при
проективизации GLs (R) → Ps (R). Для любых наборов
k = (k1 , . . . , ks ), ki ∈ {1, . . . , s} и θ = (θ1 , . . . , θs ), θi = ±1,
определим
{
GLs (R, k, θ) = ((xij )) ∈ GLs (R) :
}
xiki = θi , i = 1, s ,
Ps (R, k, θ) = P(GLs (R, k, θ)).
Тогда Ps (R) содержится в объединении всех Ps (R, k, θ), причем
каждый элемент из Ps (R, k, θ) имеет единственный прообраз при
проективизации
GLs (R, k, θ) → Ps (R, k, θ).
(8)
16
Поэтому множество всех Ps (R, k, θ) образуют атлас многообразия
Ps (R), а матрицы из GLs (R, k, θ) являются координатами соответствующих элементов Ps (R, k, θ).
Определим меру µ̃ = µ̃k,θ на поверхности GLs (R, k, θ) следующим образом:
∫
dX
при W ⊂ GLs (R, k, θ),
µ̃(W ) =
s
|det
X|
W
где dX — дифференциал s(s − 1)-мерной
меры Лебега поверхности
∏
GLs (R, k, θ) в точке X (т.е. dX = 1≤i,j≤s, dxij ). Мера µ̃ порождает
j̸=ki
меру µ на карте Ps (R, k, θ):
µ(w) = µ̃(W )
где W — прообраз w ⊂ Ps (R, k, θ) при проективизации (8). Отметим, что µ не зависит от выбора карты и поэтому корректно определена на всем многообразии Ps (R). Если Ω измеримо по Лебегу и
удовлетворяет (Б), то множество P(Ω) является µ-измеримым,
Для любого натурального N положим
χ(N ) = 1 +
∑ ln p
p|N
p
(сумма по простым делителям N ).
Отметим, что χ(N ) ≪ 1 + ln ω(N ) ≪ ln ln N при N ≥ 3, где ω(N )
— количество простых делителей N .
Основной результат главы II заключается в следующем.
Теорема 3 ([16]). Пусть выполняются условия (А), (Б). Тогда
для любого натурального N > 1 количество целочисленных матриц M ∈ Ω, удовлетворяющих условию det M = N , равно
(
(
))
#Ls (Z; N ) · C(Ω) · lns−1 N + OΩ χ(N ) · lns−2 N ,
где
C(Ω) =
1
µ(P(Ω))
·
.
ζ(2) · ζ(3) · . . . ζ(s) (s − 1)!
17
В г л а в е III рассматривается вопрос о среднем количестве
относительных минимумов.
Пусть E(N, s) — среднее число относительных минимумов полных целочисленных s-мерных решеток определителя N , т.е.
∑
1
E(N, s) =
#M(Γ).
#Ls (Z; N )
Γ∈Ls (Z;N )
Основной результат главы III заключается в следующем.
Теорема 4 ([11]). Для любой размерности s ≥ 2 и целого N > 1
(
)
s−1
s−2
E(N, s) = C(s) · ln
N + Os χ(N ) · ln
N ,
(9)
где C(s) — положительная постоянная, зависящая только от s.
При s = 2 формула (9) вытекает из теоремы Хейльбронна19 о
средней длине конечной непрерывной дроби, причем
C(2) =
4 · ln 2
ζ(2)
(используя результат Портера20 , можно получить асимптотическую
формулу с двумя значащими членами и степенным понижением в
остатке). Соотношение (9) является многомерным обобщением теоремы Хейльбронна в терминах относительных минимумов.
Постоянная C(s) выражается через некоторый s(s − 1)-мерный
интеграл. Явную формулу не приводим ввиду ее громоздкости. К
сожалению, константу C(s) при s > 2 даже приближенно вычислить удается только в трехмерном случае. В последнем параграфе
главы III получены двусторонние оценки:
1
2s
≤ C(s) ≤
.
(s − 1)!
(s − 1)!
Из них, в частности, вытекает следующее уточнение первого неравенства из (4):
1
≤ C(s).
(s − 1)! · logs−1
e
2
19
H. Heilbronn, “On the average length of a class of finite continued fractions”,
Abhandlungen aus Zahlentheorie und Analysis, Berlin, VEB (1968), 89–96.
20
J. W. Porter, “On a theorem of Heilbronn”, Mathematika, 22: 1 (1975), 20–28.
18
Доказательство теоремы 4 основано на построении алгоритма,
который позволяет единственным образом дополнить относительный минимум до базиса (решетки) специального вида. С его помощью задача вычисления суммы
∑
#M(Γ)
Γ∈Ls (Z;N )
сводится к нахождению количества всех базисов этого специального вида, то есть к вычислению количества матриц из Ms (Z; N ),
лежащих в некоторой области. Для этого применяется теорема 3.
Г л а в а IV посвящена исследованию полиэдров Клейна.
Пусть F1 и F2 — многогранники с вершинами в Zs . Напомним,
что F1 и F2 целочисленно-линейно эквивалентны, если существует
такое линейное отображение L, что LZs = Zs и LF1 = F2 .
Возьмем любую компактную гипергрань F многогранника Клейна трехмерной полной решетки Γ. Пусть L : R3 → R3 такое линейное преобразование, что
LΓ = Z3 .
(10)
Целочисленно-линейный тип многоугольника LF не зависит от выбора L. Это позволяет следующим образом классифицировать грани полиэдров Клейна.
Пусть T — целочисленно-линейный тип многоугольников из R3 .
Будем говорить, что грань F принадлежит типу T , если LF принадлежит целочисленно-линейному типу T для любого линейного
преобразования L : R3 → R3 , удовлетворяющего (10).
Пусть F(Γ; T ) — множество граней типа T , а V(Γ) — множество
вершин полиэдров Клейна решетки Γ. Определим
1
ET (N, 3) =
#L3 (Z; N )
∑
#F(Γ, T )
Γ∈L3 (Z;N )
— среднее количество граней типа T и
1
EV (N, 3) =
#L3 (Z; N )
19
∑
Γ∈L3 (Z;N )
#V(Γ)
— среднее количество вершин многогранников Клейна целочисленных полных трехмерных решеток определителя N ∈ N ∩ [2, +∞).
При s = 2 гиперграни являются отрезками, и их тип однозначно определяется количеством точек решетки, которые лежат на
грани. Поэтому из приведенных выше результатов о связи между
двумерными многогранниками Клейна и непрерывными дробями,
а также известных результатов о распределении неполных частных21 следует, что
)
(
4
1
· ln N при N → ∞,
ETk (N, 2) ∼
· ln 1 +
ζ(2)
k(k + 2)
где (k + 1) — количество точек решетки лежащих на грани типа Tk .
В двумерном случае M(Γ) = V(Γ), за исключением решеток Γ
с базисом вида (u, v), (u, −v), для которых
V(Γ) = {±(2u, 0), ±(0, 2v)},
M(Γ) = {±(2u, 0), ±(0, 2v), ±(u, v), ±(u, −v)}.
Поэтому согласно (9)
EV (N, 2) ∼ C(2) · ln N.
Пусть T F3 — множество типов граней, которые реализуются на
трехмерных полиэдрах Клейна, т.е. для любого T ∈ T F3 найдется
такая трехмерная полная решетка Γ, что F(Γ, T ) ̸= ∅.
Основные результаты главы IV заключаются в следующем.
Теорема 5 ([10]). Для любого T ∈ T F3 справедлива асимптотическая формула для среднего числа граней типа T трехмерных
полиэдров Клейна:
ET (N, 3) = CT · ln2 N + OT (χ(N ) · ln N ).
(11)
Теорема 6 ([10]). Справедлива асимптотическая формула для
среднего числа вершин трехмерных полиэдров Клейна:
EV (N, 3) = CV · ln2 N + O(χ(N ) · ln N ).
21
(12)
см., напр., «H. Heilbronn, Abhandlungen aus Zahlentheorie und Analysis,
Berlin, VEB (1968), 89–96.»
20
Здесь CT — положительная постоянная, зависящая только от
T , а CV — абсолютная положительная постоянная. Аналитические
выражения не приводятся ввиду громоздкости.
Доказательство соотношения (11) основано на построении алгоритма, который грани типа T ставит в соответствие некоторый
базис специального вида. В результате, вычисление суммы
∑
#F(Γ; T )
Γ∈L3 (Z;N )
сводится к задаче о нахождении количества всех базисов этого
специального вида, то есть к вычислению количества матриц из
M3 (Z; N ), лежащих в некоторой области. Для этого применяется
теорема 3.
Доказательство (12) основано на следующих соображениях.
1. Любая вершина многогранника Клейна является относительным минимумом22 . Поэтому достаточно подсчитать количество минимумов, которые не являются вершинами, и использовать (9).
2. О.Н. Герман23 описал ситуации, в которых относительные минимумы трехмерных решеток не являются вершинами. Согласно этим результатам, вычисление суммы
∑
#(M(Γ) \ V(Γ))
Γ∈L3 (Z;N )
сводится к подсчету суммарного количества треугольных граней некоторого специального вида. Для этого используются
идеи доказательства (11) и результаты О.Н. Карпенкова24 о
классификации граней полиэдров Клейна.
При s ≥ 4 получены двусторонние оценки для среднего числа
вершин:
EV (N, s) ≍ lns−1 N, N > 1.
s
22
В. А. Быковский, Функц. анализ и его прил., 40:1 (2006), 69–71.
О. Н. Герман, Матем. заметки., 79:4 (2006), 546–552.
24
O. N. Karpenkov, Monatsh. Math., 152:3 (2007), 217–249.
23
21
В г л а в е V рассматриваются цилиндрические минимумы и
наилучшие приближения линейных форм.
Возьмем любую лучевую, непрерывную, кусочно-дифференцируемую функцию f : Rs−1 → R. Пусть Ls (Z; [1, R]) — множество,
состоящее из всех полных целочисленных s-мерных решеток Γ, удовлетворяющих условию det Γ ∈ [1, R] Множество цилиндрических
f -минимумов решетки Γ ∈ Ls (Z; [1, R]) обозначим через Mc,f (Γ).
Пусть Ec,f [1, R] — среднее число цилиндрических f -минимумов
решеток из Ls (Z; [1, R]), т.е.
1
Ec,f [1, R] =
#Ls (Z; [1, R])
∑
#Mc,f (Γ).
Γ∈Ls (Z;[1,R])
Первые два параграфа главы V посвящены доказательству следующего результата.
Теорема 7 ([8]). Для любого R > 1
Ec,f [1, R] = Cc,f · ln R + Of (1),
(13)
где Cc,f — положительная постоянная, зависящая только от f .
Формулу для Cc,f не приводим ввиду громоздкости.
Доказательство основано на специальной процедуре дополнения цилиндрического минимума до базиса решетки, основанной на
идеях Г.Ф. Вороного (в изложении Б.Н. Делоне и Д.К. Фаддеева25 ).
В результате, вычисление суммы
∑
#Mc,f (Γ)
Γ∈Ls (Z;[1,R])
сводится к нахождению количества целочисленных матриц M таких, что
M ∈ Ωc,f , | det M | ∈ [1, R],
(14)
где Ωc,f — некоторое подмножество GLs (R). Технические результаты, связанные с задачей о количестве целочисленных матриц в
Ωc,f , вынесены в приложение.
25
§ 60 главы 5 из «Б. Н. Делоне, Д. К. Фаддеев, Теория иррациональностей
третьей степени, Тр. Матем. ин-та им. В. А. Стеклова. 11 (1940), Изд-во АН
СССР, М.-Л., 3–340.»
22
В последнем параграфе главы V исследуется вопрос о среднем
количестве наилучших приближений линейных форм. Положим
n = s − 1. Пусть Bf (α) — множество f -наилучших приближений
(u, v) ∈ Rn × R линейной формы x ∈ Rn → α1 x1 + . . . + αn xn .
Множество Bf (α) конечно только в случае, когда числа α1 , . . . , αn
линейно зависимы над полем Q. Для любого P ≥ 1 и α ∈ [0, 1)n
определим множество
Bf (α, P ) = {(u, v) ∈ Bf (α) : f (u) ≤ P }.
Оно конечно, причем справедлива оценка
#Bf (α, P ) ≪ ln P + 1.
f
Если функция f выпуклая, то это неравенство вытекает из известных результатов о скорости роста наилучших приближений26 . В
общем случае оно является тривиальным следствием из результатов главы I настоящей диссертации.
Для любого вещественного R > 1 определим множество ∆n (R) ⊂
[0, 1)n , состоящее из рациональных векторов α ∈ [0, 1)n с координатами αi = Pi /Q, где Pi , Q — целые, причем
0 ≤ Pi < Q ≤ R,
i = 1, n.
Определим среднее количество
1
EB,f ([1, R], P ) =
#∆n (R)
∑
#Bf (α, P ),
α∈∆n (R)
f -наилучших приближений, удовлетворяющих условию f (u) ≤ P ,
линейных форм с рациональными коэффициентами из ∆n (R), а
также математическое ожидание
∫
EB,f (P ) =
#Bf (α, P ) dα
[0,1)n
количества f -наилучших приближений, удовлетворяющих условию
f (u) ≤ P , линейных форм с вещественными коэффициентами. Отметим, что функция α ∈ [0, 1)n → #Bf (α, P ) измеримая по Лебегу
26
J. C. Lagarias, J. Austral. Math. Soc. Ser. A, 34:1 (1983), 114–122.
23
и ограниченная. Поэтому интеграл Лебега EB,f (P ) существует и
конечен.
В одномерном случае (т.е. при n = 1, f (x) = |x|) асимптотические формулы для определенных средних вытекают из известных
статистических свойств непрерывных дробей. В частности,
1
#∆n (R)
∑
EB,f (P ) = C(2) · ln P + O(1),
#Bf (α) = C(2) · ln R + O(1),
α∈∆n (R)
где постоянная C(2) такая же, как и в (9). В последнем параграфе
главы V мы доказываем обобщение этих результатов на многомерный случай в следующем виде.
Теорема 8. Для любого n ≥ 1 и любой непрерывной, кусочно-дифференцируемой, лучевой функции f : Rn → R справедливы асимптотические формулы:
[
]
1/n
EB,f ([1, R], P ) = Cc,f · n · ln P + Of (1),
P ∈ 1, R
, (15)
EB,f (P ) = Cc,f · n · ln P + Of (1),
P ∈ [1, +∞) . (16)
Постоянная Cc,f такая же, как и в формуле (13)
Доказательство (15) основано на следующих соображениях. Как
уже отмечалось, существует взаимно однозначное соответствие между наилучшими приближениями линейной формы и цилиндрическими минимумами некоторой решетки. Поэтому EB,f ([1, R], P ) равно среднему количеству цилиндрических f -минимумов γ, у которых f (γ1 , . . . , γn ) ≤ P , некоторых (n + 1)-мерных решеток специального вида. В результате, вычисление EB,f ([1, R], P ) сводится к
нахождению количества целочисленных матриц M , удовлетворяющих (14) и условиям:
f (m11 , . . . , m(s−1)1 ) ≤ P,
ds−1 (M ) = 1,
где s = n + 1, а ds−1 (M ) — наибольший общий делитель алгебраических дополнений к элементам последней строки M .
Соотношение (16) получается предельным переходом в (15) при
R → ∞.
24
Г л а в а VI посвящена изучению локальных Φ-минимумов.
Через EΦ [1, R] обозначим среднее число локальных Φ-минимумов
полных целочисленных s-мерных решеток Γ, удовлетворяющих условию: det Γ ∈ [1, R], т.е.
1
EΦ [1, R] =
#Ls (Z; [1, R])
∑
#MΦ (Γ),
Γ∈Ls (Z;[1,R])
где MΦ (Γ) — множество локальных Φ-минимумов решетки Γ.
Основной результат главы VI заключается в следующем.
Теорема 9. Пусть Φ = (Φ1 , . . . , Φr ) и функции Φl удовлетворяют условиям (1). Тогда для любого R ≥ 2
EΦ [1, R] = CΦ · lnr−1 R + OΦ (lnr−2 R),
где CΦ — положительная постоянная, зависящая только от Φ.
Как и в предыдущих случаях, доказательство основано на построении специальной процедуры дополнения локального минимума до базиса решетки. В результате вычисление суммы
∑
#MΦ (Γ)
Γ∈Ls (Z;[1,R])
сводится к нахождению количества целочисленных матриц с определителем из отрезка [1, R], лежащих в некотором множестве ΩΦ ⊂
GLs (R). Используемый метод дополнения минимума до базиса похож на тот, который применяется для случая относительных минимумов, и отличен от использованного для цилиндрических минимумов.
П р и л о ж е н и е содержит технические результаты, связанные
с задачами о количестве целочисленных точек в некоторых многомерных множествах. Леммы приложения используются только в
главах V, VI.
25
Публикации автора по теме диссертации
[1] А. А. Илларионов, “Оценка количества относительных минимумов неполных целочисленных решеток произвольного ранга”, ДАН, 418:2 (2008), 155–158.
[2] А. А. Илларионов, Д. А. Слинкин, “О количестве вершин
многогранников Клейна целочисленных решеток в среднем”,
Дальневост. матем. журн., 11:1 (2011), 48–55.
[3] А. А. Илларионов, Ю. А. Сойка, “О количестве относительных минимумов целочисленных решеток”, Дальневост. матем. журн., 11:2 (2011), 149–154.
[4] А. А. Илларионов, “О цилиндрических минимумах трехмерных решеток”, Дальневост. матем. журн., 11:1 (2011), 37–
47.
[5] А. А. Илларионов, “Оценки количества относительных минимумов решеток”, Матем. заметки, 89:2 (2011), 249–259.
[6] А. А. Илларионов, “Среднее количество относительных минимумов трехмерных целочисленных решеток”, Алгебра и анализ, 23:3 (2011), 189–215.
[7] А. А. Илларионов, “О статистических свойствах локальных
минимумов целочисленных решеток”, Дальневост. матем.
журн., 12:2 (2012), 201–230.
[8] А. А. Илларионов, “О цилиндрических минимумах целочисленных решеток”, Алгебра и анализ, 24:2 (2012), 154–170.
[9] А. А. Илларионов, “Среднее количество относительных минимумов трехмерных целочисленных решеток фиксированного
определителя”, Изв. РАН. Сер. матем., 76:3 (2012), 111–138.
[10] А. А. Илларионов, “О статистических свойствах многогранников Клейна трехмерных целочисленных решеток”, Матем.
сб., 204:6 (2013), 23–46.
26
[11] А. А. Илларионов, “Многомерное обобщение теоремы Хейльбронна о средней длине конечной непрерывной дроби”, Матем. сб., 205:3 (2014), 119–132.
[12] А. А. Илларионов, “О среднем количестве наилучших приближений линейных форм”, Изв. РАН. Сер. матем., 78:2 (2014),
61–86
[13] А. А. Илларионов, “Оценка количества относительных минимумов неполных целочисленных решеток”, Чебышевский сб.,
7:4 (2006), 92–98.
[14] А. А. Илларионов, “Оценки количества относительных минимумов решеток”. В сб. «Наука - Хабаровскому краю. Материалы X краевого конкурса молодых ученых», Хабаровск,
Изд-во Тихо-океан. гос. ун-та, 2008, 65–75.
[15] А. А. Илларионов, “Статистические свойства многомерных
аналогов непрерывных дробей”. В сб. «Наука - Хабаровскому
краю. Материалы XII краевого конкурса молодых ученых»,
Хабаровск, Изд-во Тихоокеан. гос. ун-та, 2010, 5–15.
[16] A. A. Illarionov, “On the Asymptotic Distribution of Integer
Matrices”, Moscow Journal of Combinatorics and Number
Theory, 1:4 (2011), 301–345.
27
Подписано в печать 05.06.2014
Тираж 100 экз.
Отпечатано в Математическом институте им. В.А. Стеклова РАН
Москва, 119991, ул. Губкина, 8
Документ
Категория
Без категории
Просмотров
1
Размер файла
917 Кб
Теги
166541
1/--страниц
Пожаловаться на содержимое документа