Авторефераты по всем темам >>
Авторефераты по разное
Российская Академиия наукМатематический институт имени В. А. Стеклова
На правах рукописи
УДК 511.21, 511.33,
511.37 УСТИНОВ Алексей Владимирович Приложения оценок сумм Клостермана к некоторым задачам метрической и аналитической теории чисел
01.01.06 - математическая логика, алгебра и теория чисел А В Т О Р Е Ф Е Р А Т диссертации на соискание ученой степени доктора физико-математических наук Москва 2008
Работа выполнена в отделе теоретической и прикладной математики Хабаровского отделения Института прикладной математики Дальневосточного отделения Российской Академии наук
Научный консультант: чл.-корр. РАН В. А. Быковский
Официальные оппоненты: доктор физико-математических наук, профессор В. Г. Журавлев доктор физико-математических наук, профессор А. М. Зубков доктор физико-математических наук, профессор Н. Г. Мощевитин
Ведущая организация: Московский педагогический государственный университет
Защита диссертации состоится 26 февраля 2009 г. в 14 часов на заседании диссертационного совета Д 002.022.03 при Математического института им. В. А. Стеклова Российской академии наук по адресу Москва, ул. Губкина, д.
С диссертацией можно ознакомиться в библиотеке Математического института им. В. А. Стеклова
Автореферат разослан У Ф 200 г.
Ученый секретарь диссертационного совета Д 002.022.03 при МИАН, д. ф.-м. н. профессор Н. П. Долбилин
Актуальность темы В последнее десятилетие возросло число работ, посвященных анализу алгоритма Евклида и родственных алгоритмов, связанных с геометрическими решетками. Внимание к этой области обусловлено тем, что она лежит на пересечении интересов специалистов по вычислительным методам, теории чисел и теории динамических систем.
Фундаментом для современных исследований являются классические работы Хинчина, Кузьмина, П. Леви, в которых была создана метрическая теория цепных дробей. Этими авторами были разработаны теоретико-вероятностные и эргодические методы, позволившие позднее получить ряд ярких результатов о статистических свойствах элементов цепных дробей (Бабенко, Ибрагимов, Филипп). В конце XX века были поставлены новые задачи, связанные с работой алгоритма Евклида и его вариантов (Кнут, Арнольд). Основной прогресс в их решении был достигнут эргодическими методами (Хенсли, Валле, Балади, Флажоле). Но в некоторых случаях удавалось применить методы аналитической теории чисел, восходящие к Хейльбронну и Портеру, приводящие к более точным результатам (Кнут, Яо, Авдеева, Быковский).
О классических приложениях сумм Клостермана.
Асимптотические свойства целочисленных решений уравнения x1y1 + x2y2 = n (1) лежат в основе различных теоретико-числовых результатов. При фиксированном значении одной из переменных, например, y2, переменные x1, y1 оказываются связаны сравнением x1y1 n (mod y2). (2) Наличие нетривиальных оценок на суммы Клостермана q-ax+by q Kq(a, b) = q(xy - 1) e2i, (3) x,y=согласно критерию Вейля, означает равномерность распределения решений сравнения (2). Это наблюдение позволяет находить асимптотические формулы для сумм вида f(x1, y1, x2, y2).
x1y1+x2y2=n Частным случаем уравнения (1) является соотношение bc ad = 1, которому удовлетворяют числители и знаменатели последовательных дробей a/b < c/d ряда Фарея. Для фиксированного знаменателя d и числителя c (0 c d, (c, d) = 1) длина отрезка [a/b, c/d] c a - = d b bd определяется величиной b c-1 (mod d). Равномерность распределения пар (b, c), для которых bc 1 (mod d) позволяет описать распределение длин отрезков между соседними дробями в ряде Фарея, что приводит к усовершенствованию кругового метода ХардиЦЛиттлвуда1.
Ещё одним важным вопросом, в котором возникает уравнение (1) является аддитивная проблема делителей, связанная с асимптотическим поведением сумм 0(k)0(k + n).
k T К ним сводится подсчёт четвертого момента -функции Римана на критической прямой2.
Хейльбронн3 установил связь уравнения (1) с конечными цепными дробями. Благодаря этому ему удалось доказать асимптотическую формулу для среднего числа шагов в алгоритме Евклида (см. ниже).
О задачах метрической теории цепных дробей. Хорошо известно, что любое вещественное число каноническим спосоKloosterman H. D. On the representation of numbers in the form ax2 + by2 + cz2 + dt2 Acta Math., 49 (1927), 407Ц4Heath-Brown D. R. The fourth power moment of the Riemann zeta function Proc. London Math. Soc. (3), 1979, 38, 385Ц4Heilbronn H. On the average length of a>
.
.
+ qn +.
.
.
с целой частью q0 = [] и неполными частными qn = qn() N при n 1. Она конечна только для рациональных = [q0; q1,..., qs] и в этом случае при s 1 последнее неполное частное qs больше 1. По определению, Pn = Pn() и Qn = Qn() (n = 0, 1, 2,...) числитель (целое) и знаменатель (натуральное) несократимой n-ой подходящей к дроби Pn = [q0; q1,..., qn].
Qn При этом P0 = q0 и Q0 = 1.
В метрической теории чисел ряд задач посвящен статистическим свойствам цепных дробей. Например, для действительных чисел удается описать типичное поведение неполных частных в представлении (4), рост знаменателей Qn() и порядок аппроксимации подходящими дробями Pn()/Qn()4.
Пусть x [0, 1] фиксированное действительное число и n n = T () = [0; qn+1, qn+2,... ], где T отображение Гаусса, переводящее в себя отрезок [0, 1]:
T () = при = 0, T (0) = 0.
Обозначим через Fn(x) меру множества всех иррациональных чисел , для которых n x. Гаусс исследовал итерации отображения T и пришел к следующей гипотезе:
lim Fn(x) = log2(1 + x) n Хинчин А. Я. Цепные дроби. М.: Наука, 19Лишь в 1928 году появилась работа Кузьмина5 с доказательством асимптотической формулы Fn(x) = log2(1 + x) + O(e- n), где некоторая абсолютная положительная константа. В качестве следствия теоремы Кузьмина легко получить асимптотическую формулу для меры множества точек, для которых qn = k 1 pk(n) = Fn - Fn = pk + O(e- n), k k + где pk = log2 1 +. (5) k(k + 2) Более сильный результат (экспоненциальную скорость сходимости) в этом направлении получил французский математик П. Леви6. Вирзинг7 указал явно скорость сходимости:
Fn(x) - log2(1 + x) n с абсолютной константой 1 = -0.30366... (впоследствии названной константой Вирзинга). Последнюю точку поставил Бабенко8, доказав существование бесконечной убывающей к нулю последовательности чисел j 1 > |1| > |2|... |k| |k+1|...
и соответствующей последовательности аналитических функций k(x), для которых Fn(x) = log2(1 + x) + k(x)n.
k k=KuzТmin R. O. Sur un problme de Gauss Atti del Congresso Internazionale dei Matematici, Bologna, 6 (1928), 83ЦLvy P. Sur les lois de probabilit dont dependent les quotients complets et incomplets dТune fraction continue. Bull. Soc. Math. France, 57 (1929), 178Ц1Wirsing E. On the theorem of Gauss-Kusmin-Lvy and a Frobenius-type theorem for function spaces. Acta Arith. 24 (1974), 507Ц5Бабенко К. И. Об одной задаче Гаусса. ДАН СССР, 238:5 (1978), 1021Ц10Изучение свойств отображения Гаусса T основано на спектральных свойствах оператора 1 Gs[f](z) = f (m + z)2s m + z m=(например, при s = 1 такой оператор используется в доказательстве теоремы Кузьмина4). Ключевую роль здесь играет его доминирующее собственное значение (s). Про эту функцию известно, что она определена и аналитична в области Re s > 1/и положительна для действительных s > 1/2. В частности, теорема Кузьмина означает, что (1) = 1 и соответствующей собственной функцией является плотность Гаусса log2(1 + x). Число (2) - (1) = log известно как константа Леви, а число (1), для которого не известно представления через арифметические постоянные, как константа Хенсли.
Оператор Gs также связан с поведением случайной величины Xn = log Qn(), где Qj() знаменатель j-ой подходящей дроби к числу , которое выбирается случайно из отрезка [0, 1] (см. работы Ибрагимова9 и Филиппа10). Для Xn доказана центральная предельная теорема11:
t Xn - E(Xn) 1 ulim P t = e- du.
n D1 n 2 - Кроме того, для математического ожидания и дисперсии Xn известны двучленные асимптотические формулы E(Xn) = E1 n + E0 + O(n), D(Xn) = D1 n + D0 + O(n), Ибрагимов И. А. Одна теорема из метрической теории цепных дробей. Вестник Ленингр. Унив., 16: 1 (1961), 13ЦPhilipp W. Ein zentraler Grenzwertsatz mit Anwendungen auf die Zahlentheorie. Z. Wahrsch. Verw. Gebiete, 8 (1967), 185Ц2Flajolet Ph., Valle B. Continued fraction algorithms, functional operators, and structure constants. Theoret. Comput. Sci., 194: 1-2 (1998), 1Цгде (1) (1) - (1)E1 = -, D1 = 2 и 1 константа Вирзинга.
О статистических свойствах алгоритма Евклида. Детальный анализ алгоритма Евклида приводит к различным задачам о статистических свойствах конечных цепных дробей12.
Если на вход алгоритма подается пара натуральных чисел c и d (c < d), то основной интерес представляет число выполняемых делений с остатком, которое совпадает с s = s(c/d) количеством неполных частных в цепной дроби c/d = [0; t1,..., ts].
Впервые вопрос о поведении величины s(c/d) в среднем был исследован Хейльбронном3. Сводя задачу к уравнению (1) с 1 x1 x2, 1 y1 y2, элементарными методами он доказал асимптотическую формулу 1 2 log s(c/d) = log d + O(log4 log d).
(d) (2) 1 c d (c,d)=Портер13, используя оценки сумм Клостермана, для того же среднего получил асимптотическую формулу с двумя значащими членами 1 2 log s(c/d) = log d + CP - 1 + O(d-1/6+), (6) (d) (2) 1 c d (c,d)=где любое положительное и 2 log 2 3 log 2 (2) CP = + 2 - 2 - 1 (2) 2 (2) константа, получившая название константы Портера.
Кнут Д. Э. Искусство программирования, т. 2. Получисленные алгоритмы. М., Санкт-Петербург, Киев: Вильямс, 20Porter J. W. On a theorem of Heilbronn. Mathematika, 22: 1 (1975), 20ЦВ то же время для дисперсии величины s(c/d) (при фиксированном значении знаменателя d) известна лишь правильная с точностью до константы оценка, принадлежащая Быковскому14:
d 1 c 2 log s - log d log d.
d d (2) c=Она получена методами аналитической теории чисел, также опирающимися на оценки сумм Клостермана.
Отдельно изучается задача о поведении s(c/d), когда параметры c и d меняются в пределах 1 c d R, где R растущий параметр. Определим среднее значение числа шагов в алгоритме Евклида E(R) = s(c/d) R(R + 1) d R c d и дисперсию D(R) = (s(c/d) - E(R))2.
R(R + 1) d R c d Суммируя равенство (6) нетрудно получить, что 2 log E(R) = log R + CP + O(R-1/6+) (7) (2) с некоторой абсолютной константой CP. Однако, при усреднении по обоим параметрам c и d естественно надеяться на более точное описание поведения величины s(c/d).
Ряд результатов в этом направлении был получен вероятностными и эргодическими методами. Диксон15 показал, что для любого положительного найдётся такая константа c0 > 0, что 2 log s(c/d) - log d < (log d)1/2+ (2) Быковский В. А. Оценка дисперсии длин конечных непрерывных дробей. ФПМ, 11: 6 (2005), 15ЦDixon J. D. The Number of Steps in the Euclidean Algorithm. J. of Number Theory, 2 (1970), 414Ц4для всех пар чисел (c, d) лежащих в области 1 c d R, за исключением, не более R2 exp(-c0(log R)/2) пар. Хенсли16 уточнил результат Диксона и доказал, что разность между величиной s(c/d) и ее средним значением асимптотически имеет нормальное распределение. Кроме того, Хенсли доказал асимптотическую формулу для дисперсии величины s(c/d):
D(R) = D1 log R + o(log R), где (1) - (1)D1 = 2. (8) (1)Позднее Валле17 для дисперсии была получена двучленная асимптотическая формула со степенным понижением в остаточном члене D(R) = D1 log R + D0 + O(R- ), (9) где 0 некоторая положительная постоянная. Аналогичные равенства были доказаны и для моментов более высокого порядка, откуда следует, что длина работы алгоритма асимптотически является гауссовской величиной18.
Статистики Гаусса-Кузьмина. В. И. Арнольдом19 была поставлена задача о статистических свойствах элементов цепных дробей для чисел c/d, когда точки (c, d) лежат внутри круга c2 + d2 R2, где R , или внутри другой расширяющейся области. Там же было сделано предположение, что ответ не зависит от формы области и во всех случаях пропорционален мера Гаусса.
Для фиксированного x [0, 1] и рационального r = [t0; t1,..., ts] статистики Гаусса-Кузьмина задаются равенством s(x)(r) = #{j : 1 j s = s(r), [0; tj,..., ts] x}.
Hensley D. The Number of Steps in the Euclidean Algorithm. J. of Number Theory, 49 (1994), 142Ц1Valle B. A Unifying Framework for the Analysis of a>
(R) = R 0 = {(x, y) : x, y > 0, (x/R, y/R) 0}.
Аргументы Хейльбронна и Портера позволяют доказатьасимптотическое равенство 2 log(1 + x) s(x)(c/d) = d log d + O(d), (2) 1 c d равномерное по x [0, 1]. Однако этого результата недостаточно для преодоления главной трудности, которая заключается в том, что в равенстве (10) при фиксированном d переменная c пробегает отрезок, длина которого, вообще говоря, не кратна d.
Для сектора c2 + d2 R2 (c, d 0) задача Арнольда была впервые решена Авдеевой и Быковским21. Доказательство опиралось на оценки сумм Клостермана и существенно использовало внешнее усреднение по d. Затем Авдеевой22 была доказана более точная асимптотическая формула Nx(R) = log(1 + x) R2 log R + O(R2).
В работе [1] была получена асимптотическая формула с двумя значащими членами:
Nx(R) = log(1 + x) R2 log R + C0(x) R2 + O(R17/9 log2 R). (11) Авдеева М. О. Распределение неполных частных в конечных цепных дробях. Владивосток: Дальнаука, 2000, препринт ДВО РАН, ХО ИПМ № Авдеева М. О., Быковский В. A. Решение задачи Арнольда о статистиках Гаусса-Кузьмина. Владивосток, Дальнаука, 2002 (препринт) Авдеева М. О. О статистиках неполных частных конечных цепных дробей. Функц. анализ и его прил. 38: 2 (2004), 1ЦКроме того оказалось, что аналогичная формула справедлива и для произвольной области (R), удовлетворяющей некоторым техническим ограничениям (см. теорему 5 ниже).
Задача Синая Бильярд Синая является простейшей моделью рассеивающей динамической системы: маленький шар движется внутри квадратного поля, в центр которого помещено круглое препятствие с отражающими стенками. Предполагается, что все удары абсолютно упруги. Очевидно, что вместо квадратного бильярда можно рассматривать плоскость, на которой круглые препятствия располагаются вокруг каждой точки целочисленной решетки. Такая модель и будет рассматриваться в дальнейшем.
Пусть 0 < h < и T > 0. Открытый круг радиуса h с центром в некоторой точке назовем ее h-окрестностью. Определим подмножество h(T ) в [0, 2), состоящее из углов , для которых луч {(t cos , t sin ) : t 0} пересекает h-окрестность некоторой целочисленной точки (m, n) = (0, 0) из круга (x, y) R2 : x2 + y2 T.
Обозначим через Gh(T ) нормированную меру h(T ):
Gh(T ) = mes h(T ) [0, 1].
2 В 1918 г. Полиа23 доказал, что Gh(T ) = 1 для всех T h-1.
Отвечая на вопрос, поставленный в 1981 г. Синаем, Бока, Гологан и Захареску24 доказали, что для любого > 0 равномерно по T [0, h-1] hT Gh(T ) = (t) dt + O(h1/8-), Полиа Г., Сеге Г. Задачи и теоремы из анализа, т. 2. М.: Наука, 19Boca F. P., Gologan R. N., Zaharescu A. The statistics of the trajectory of a certain billiard in a flat two-torus, Comm. Math. Phys., 240:
1Ц2 (2003), 53Цгде 12, если 0 t ;
2 (t) = 12 1 1 - 1 1 - log - 1, если < t 1.
2 t t С физической точки зрения, величину Gh(T ) можно интерпретировать как функцию распределения длин свободного пробега частиц, движущихся прямолинейно из начала координат до их первого попадания в h-окрестность некоторой ненулевой целочисленной точки. Речь идет об однородной двумерной модели УПериодический газ ЛоренцаФ.
Цель работы Расширить область приложений аналитической теории чисел к метрической теории чисел, анализу алгоритмов и статистической физике. Получить новые результаты, связанные со статистическим свойствами цепных дробей, и уточнить уже известные, доказанные ранее эргодическими методами. Исследовать статистические свойства траекторий частиц в двумерной кристаллической решетке.
Научная новизна В диссертации разработаны новые методы исследования задач метрической теории цепных дробей, основанные на оценках сумм Клостермана. Они позволили в ряде случаев не только существенно усилить известные результаты, но и решить новые теоретико-числовые задачи, возникающие в статистической физике. К основным можно отнести следующие результаты диссертации.
1) Для действительных чисел изучено поведение в среднем количества знаменателей подходящих дробей, не превосходящих данной границы. Для первого и второго момента доказаны двучленные асимптотические формулы со степенными понижениями в остаточных членах.
2) В задаче Арнольда о статистиках Гаусса-Кузьмина для конечных цепных дробей доказана асимптотическая формула с двумя значащими членами и степенным понижением в остатке.
Как следствие доказана независимость главного члена от формы рассматриваемой области.
3) Получены принципиально новые оценки остаточных членов в асимптотических формулах для первого и второго моментов числа шагов в алгоритме Евклида.
4) В задаче Синая о статистических свойствах траекторий частиц, движущихся в двумерной кристаллической решетке, исследован неоднородный случай, когда траектории начинаются в окрестности целочисленной точки. Найдена плотность совместного распределения длины свободного пробега и прицельного параметра (расстояния от траектории до центра первой пересеченной окрестности). В остаточном члене асимптотической формулы для плотности получено корневое понижение.
Теоретическая и практическая ценность Диссертация носит теоретический характер. Метод, развитый в работе, может быть использован для дальнейшего анализа алгоритма Евклида, его вариантов и многомерных аналогов. Решение задачи Синая может быть использовано в ядерной физике в теории каналирования частиц.
Апробация работы Результаты работы прошли апробацию на семинарах по теории чисел под руководством А. А. Карацубы, Н. Г. Мощевитина, Ю. В. Нестеренко, на семинаре кафедры дискретной математики под руководством О. Б. Лупанова, на семинаре по динамическим системам под руководством В. В. Козлова и Д. В. Трещева механикоЦматематического факультета МГУ, на семинаре по теории вероятностей под руководством А. М. Зубкова в МИРАН, на семинарах по теории чисел под руководством В. Г. Чирского в МПГУ и В. Г. Журавлева в ВГПУ, а также на международных конференциях по теории чисел, УАналитические методы в теории чисел, теории вероятностей и математической статистикеФ (ПОМИ РАН, 2005), УАналитические и комбинаторные методы в теории чисел и геометрииФ (МГУ, 2006), УАналитические и вероятностные методы в теории чисеФ (Паланга, 2006), УДиофантовы и аналитические проблемы теории чисеФ (МГУ, 2007), XXVth Journes Arithmtiques (Эдинбург, 2007) и на Дальневосточных математических школах (2006, 2007).
Публикации Основные результаты диссертации опубликованы в работах, список которых приведен к конце автореферата. В совместной работе [6] вклад соавторов одинаков.
Структура и объем работы Диссертация изложена на 154 страницах и состоит из введения, четырех глав и приложения. Библиография содержит наименований. В четырёх главах диссертации доказываются основные результаты (см. теоремы 1Ц7 ниже). В приложение помещены вспомогательные утверждения. Некоторые из них (оценки сумм Клостермана, применение метода ван дер Корпута, см.
раздел Уметоды исследованияФ) являются новыми и уточняют известные результаты25,26.
Содержание работы О числе знаменателей цепных дробей, не превосходящих данной границы. В главе 1 диссертации исследуется случайная величина, которая как и Xn отвечает за рост знаменателей подходящих дробей. Для иррационального [0, 1] через E(, R) будем обозначать число E(, R) = # {j 1 : Qj() R}.
Величину E(, R) можно считать непрерывным аналогом длины конечной цепной дроби s(), которая изучена во второй главе диссертации.
Estermann T. On KloostermanТs sum. Mathematika, 8 (1961), 83ЦБыковский В. A. Асимптотические свойства целых точек (a1, a2), удовлетворяющих сравнению a1a2 l (mod q).
Рассмотрим среднее значение E(, R) E(R) = E(, R) d и дисперсию 1 D(R) = (E(, R) - E(R))2 d = E2(, R) d - E2(R).
0 Для них доказываются асимптотические формулы с двумя значащими членами и степенными понижениями в остатках.
Теорема 1. При R E(R) = E1 log R + E0 + O(R-1 log R), где 2 log 2 2 log 2 (2) E1 =, E0 = log 2 + - -.
(2) (2) (2) Теорема 2. При R D(R) = D1 log R + D0 + O(R-1/3 log4 R), где D1, D0 абсолютные константы.
Константа E1 в главном члене для математического ожидания очевидным образом связана с константой Леви - (1). Константа D1 выражается через сумму абсолютно сходящегося ряда.
В последствии выясняется, что она связана с константой Хенсли.
Задача о вычислении E(R) и D(R) является более простой, чем её дискретный вариант (см. теоремы 3Ц4). В то же время доказательства теорем 1Ц2 могут служить иллюстрацией ключевых идей, которые будут применяться при анализе конечных цепных дробей.
О статистических свойствах алгоритма Евклида. В главе 2 математическое ожидание E(R) выражается через число решений неравенства x1y1 + x2y2 R (1 x1 x2, 1 y1 y2). (12) Наличие дополнительного усреднения по параметру d R позволяет доказать асимптотическую формулу с лучшим, чем в (7), понижением в остаточном члене.
Теорема 3. Пусть R 2. Тогда E(R) = E1 log R + E0 + O(R-1 log4 R), (13) где 2 log 2 2 log 2 3 log 2 (2) 3 E1 = E1 =, E0 = + 2 - - -.
(2) (2) 2 (2) 2 Вычисление дисперсии D(R) сводится к исследованию неравенства x1(ay1 + by2) + x2(cy1 + dy2) R, a b где 1 x1 x2, 1 y1 y2 и det = 1. С его помощью, c d как и в главе 1, для дисперсии доказывается двучленная асимптотическая формула.
Теорема 4. Пусть R 2. Тогда D(R) = D1 log R + D0 + O(R-1/4 log7/4 R), где D1 = D1 и D0 абсолютные константы.
Отметим, что в соответствующем результате (9) утверждается лишь существование некоторой константы 0 > 0; теорема показывает, что в качестве 0 можно брать любое число, меньшее 1/4.
Сопоставление равенства (8) с формулами для вычисления D1 и D1 в теоремах 2 и 4 показывает, что (1) - (1)D1 = D1 = 2.
(1)По мнению разных авторов константа D1 (которую также называют константой Хенсли) не выражается в терминах известных арифметических постоянных. Нахождение её численного значения представляет собой отдельную задачу. Известен полиномиальный алгоритм вычисления D1, то есть алгоритм, который выдает первые d цифр за O(dr) арифметических операций27. Доказательство теоремы 4 дает новую явную формулу для вычисления D1 (в цитированных работах алгоритмы основаны на вычислении спектра оператора Gs). Теорема 4 может быть также использована для нахождения константы D0, для которой в настоящее время не известно численного значения.
Статистики Гаусса-Кузьмина. В главе 3 излагается результат работы [2], где была рассмотрена область 0 общего вида. Предполагается, что она задана в полярных координатах 0 = {(, ) : 0 /4, 0 r()} и имеет площадь /V0 = r2() d.
Для суммы (10) удается не только доказать двучленную асимптотическую формулу вида (11), но и уточнить оценку остаточного члена.
Теорема 5. Пусть R 2, и r() C(1)([0, /4]). Предположим также, что для всех [0, /4] функция r() удовлетворяет ограничениям r() 0 > 0, r () r() tg .
Тогда, равномерно по x [0, 1], 2VNx(R) = log(x + 1) R2 log R + C(x) R2 + O(R9/5 log3 R), (2) где C(x) не зависит от R.
В частности, теорема 5 показывает, что главный значащий член в асимптотической формуле пропорционален мере Гаусса и зависит не от формы области 0, а лишь от ее площади V0.
Как следствие из теоремы 5 получается ответ на вопрос Арнольда: для относительной частоты встречаемости натурального Lhote L. Computation of a>
Analytic Algorithmics and Combinatorics (ANALCO), Proc. 2004 New Orleans workshop k в качестве неполных частных рассматриваемых цепных дробей выполняется асимптотическое равенство N1/k(R) - N1/(k+1)(R) pk(R) = = pk + O, N1(R) log R где pk = log2 1 + вероятность появления числа k в k(k+2) качестве неполного частного действительного числа (см. формулу (5)).
В качестве дополнения к теореме 5, в конце главы 3 доказывается уточнение результата Портера (6), распространенное на случай статистик Гаусса-Кузьмина.
Теорема 6. Пусть b 2 натуральное и x (0, 1] действительное. Тогда для суммы (b) = s(x)(a/b) x 1 a b (a,b)=справедлива асимптотическая формула 2(b) (b) = (log(x + 1) log b + CP (x)) + O,x b5/6 log7/6+ b, x (2) где > 0 сколь угодно малое число, log(x + 1) (2) CP (x) = log(1 + x) log x - + 2 - 2 - 1 + 2 (2) (2) x +h1(x) + h2(x) + x [x < 1] -, 2 1 + x а функции h1(x) и h2(x) заданы абсолютно сходящимися рядами n 1 x h1(x) = - log(1 + x), n n + mx n=1 m= 1 h2(x) = - log(1 + x).
n m n n n= m< +n x x При этом оценка остаточного члена становится равномерной по x в предположении, что x [x0, 1] для некоторого фиксированного x0 > 0.
Алгоритм Евклида, в котором при делении выбирается наименьший по модулю остаток a 1 q q a = bq + r, q = +, - r <, b 2 2 приводит к разложению в дробь a = t0 + 2, b t1 + t2 + l.
.
.
+ tl длины l = l(a/b), где t0 целое, t1,..., tl натуральные, k = 1, tk 2 (k = 1,..., l), tk+k+1 2 (k = 1,..., l-1), и l = -1 при tl = 2.
Для среднего числа шагов в таком алгоритме Евклида известен результат2 2 log l(a/b) = log R + Cl + O(R-), R(R + 1) (2) b R a b где = (1 + 5)/2 золотое сечение, Cl абсолютная постоянная и > 0. Оказывается, что для любого рационального числа a/b выполняется равенство l(a/b) = s(-1)(a/b). Поэтому вариант теоремы 5 для треугольной области и теорема 6 приводят к асимптотическим формулам аналогичным (7) и (13) 2 2 log l(a/b) = log R + Cl + O(R-1 log4 R), R(R + 1) (2) b R a b 1 2 log l(a/b) = log b + Cl + O(b-1/6 log7/6+ b), (b) (2) 1 a b (a,b)=где R, b 2 и Cl абсолютная константа.
Задача Синая. При изучении движущихся в кристалле достаточно быстрых частиц, траектории которых обусловлены главным образом многократным их рассеянием на ядрах, возникает необходимость рассматривать более общую ситуацию, когда траектория начинается не в некоторой целой точке, а в её h-окрестности.
Зафиксируем вещественное v из интервала (-1, 1). Ориентированная в направлении (cos , sin ), параметрически заданная прямая (-hv sin + t cos , hv cos + t sin ) R2 : t (-, ) (14) на плоскости при t = 0 проходит через ближайшую к началу координат O = (0, 0) точку O = (-hv sin , hv cos ) (проекция O на прямую (14)). Еще одно параметрическое представление (x - t sin , y + t cos ) R2 : t (-, ) определяет перпендикулярную к (14) прямую, проходящую при t = 0 через точку (x, y). Они пересекаются в некоторой точке при t = R(x, y) = x cos + y sin , t = U(x, y) = x sin - y cos + hv.
Среди всех целочисленных точек (m, n) на плоскости с условиями R(m, n) > 0 и |U(m, n)| < h выберем ту из них (m(), n()), для которой величина R(m, n) принимает минимальное значение. Такая точка (m(), n()) всегда найдется, поскольку по теореме Минковского о линейных формах существует целочисленная пара (m, n) = (0, 0), для ко торой |m cos +n sin | (h(1 - |v|))-1, |m sin -n cos | < h(1-|v|).
Другими словами, (m(), n()) первая целочисленная точка (m, n) = (0, 0), h-окрестность которой пересекает частица, дви жущаяся вдоль прямой (14) из точки O в положительном направлении. Положим r() = h R (m(), n()), u() = h-1 U (m(), n()).
При этом 0 < r() < и - 1 < u() < 1.
1 - |v| Ориентируясь на терминологию из ядерной физики, назовем r = r() нормированным свободным пробегом, а v и u = u() нормированными выходным и входным прицельными параметрами.
Пусть 0 < r0 < и - 1 < u- < u+ < 1.
1 - |v| Главным результатом главы 4 является следующее утверждение.
Теорема 7. Пусть |v| < c < 1. Тогда при любом > 0 для функции распределения v(h) = v(h; 0, r0, u-, u+) = = [0,r ] (r()) [u,u+] (u()) d 0 при h 0 справедлива асимптотическая формула 0 r0 u+ - v(h) = (, r, v, u) d dr du + O,c h, 0 0 uравномерная по v, u-, u+ и 0 [0, 2] с плотностью (, r, v, u) = (r, v, u) = (r, u, v) = (r, -u, -v), которая при u |v| имеет вид 6 , если 0 r ;
u+6 1 1 1 (r, u, v) = - 1 - v, если r ;
u+1 1+v u-v r 0, если r.
1+v С физической точки зрения функцию (, r, v, u) можно ин2 терпретировать как плотность частиц, движущихся прямолинейно с единичной скоростью под углом после первого рассеяния с выходным прицельным параметром V = h v в h-окрестности некоторого узла целочисленной решетки и проходящих расстояние R = h-1 r до повторного рассеяния с входным прицельным параметром h u.
Следует отметить, что плотность (, r, v, u) не зависит от угла . Это означает, что целочисленная решетка в пределе обладает свойством изотропности, которое, как известно, проявляется также в задачах о случайных блужданиях и дискретных гармонических функциях28. Симметрия плотности относительно замены (v, u) на (u, v) объясняется изотропностью и УобратимостьюФ траекторий частиц.
Синай29 доказал эргодичность прямоугольного бильярда с вырезанным из него кругом радиуса h. Ему же принадлежит постановка задачи об асимптотическом поведении функции распределения длины траектории до первого столкновения с вырезанным кругом (столкновения с бортами не принимаются во внимание) при h 0. Речь идет о частном случае рассматриваемой нами задачи для v = 0, u- = 1, u+ = 1, 0 = 2. При v = (однородная задача) теорема 7 была доказана в [6].
Рассматриваемая двумерная модель связана с теорией каналирования частиц, движущихся параллельно кристаллографическим плоскостям30.
Методы исследования Доказательства всех теорем базируются на явных арифметических конструкциях, построенных с помощью цепных дробей.
Эти конструкции сводят исходные задачи к исследованию таких арифметических объектов как суммы специального вида и системы неравенств.
Многократно приходится решать вопрос об асимптотическом Spitzer F. Principles of Random Walks. New York: Van Nostrand, 19Синай Я. Г. Эргодические свойства газа Лоренца. Функциональный анализ и его приложения, 13: 3 (1979), 46ЦКадменский А. Г., Самарин В. В., Тулинов А. Ф. Регулярное и стохастическое движение в кристалле при каналировании. Эволюция потока частиц в толстом кристалле. Физика элементарных частиц и атомного ядра, т. 34 (2003), вып. 4, 822Ц8поведении сумм q-q(uv - 1) f (u/q, v/q) (15) u,v=для различных функций f. При этом используется стандартный подход, основанный на переходе к тригонометрическим суммам.
Пусть f записана в виде конечного ряда Фурье q-mu+nv q f (u/q, v/q) = Cq(m, n) e2i, m,n=где q-mu+nv q Cq(m, n) = f (u/q, v/q) e-2i q u,v= конечные коэффициенты Фурье функции f. Тогда тождество q-1 q-(q) q(uv - 1) f (u/q, v/q) = f (u/q, v/q) + Rq[f], qu,v=0 u,v=где q-Rq[f] = Cq(m, n) Kq(m, n) m,n=(m,n) =(0,0) сводит задачу об асимптотическом поведении суммы (15) к оценкам сумм Клостермана (3). В диссертации используются утверждения, основанные на оценке Эстермана|Kq(m, n)| 0(q) (m, n, q)1/2 q1/2. (16) Доказательства каждой из теорем 1Ц6 разбиваются на случаи в зависимости от значений параметров. Например, при исследовании неравенства (12) отдельно рассматриваются случаи x2 [R1/2] + 1/2 и x2 > [R1/2] + 1/2. Идейно такой подход близок к круговому методу с его разбиением на большие и малые дуги.
Отличие заключается в следующем: из условия x2 > [R1/2] + 1/вытекает, что y2 < R1/2 +1/2 и, таким образом, Умалые дугиФ для переменных x1, x2 становятся УбольшимиФ для y1, y2. Как и в круговом методе возникает необходимость изучения Уособых рядовФ.
Их слагаемыми являются остаточные члены различных асимптотических формул, а через их суммы выражаются константы в теоремах 1Ц6.
Пусть q натуральное число, l целое и f неотрицательная функция. Обозначим через T [f] число решений сравнения xy l (mod q), лежащих в области P1 < x P2, 0 < y f(x):
T [f] = q(xy - l).
P1 В общем случае задача об асимптотике величины T [f] впервые была решена Быковским26. Доказательство основывалось на формуле суммирования Пуассона и использовании оценки Эстермана (16). В приложении излагается результат работы [7], уточняющий теорему Быковского. Через S[f] обозначим сумму S[f] = q,l(x)f(x), q P1 Теорема 8. Пусть P1, P2 действительные числа, P = P2 P1 2. Предположим также, что на всем отрезке [P1, P2] вещественная неотрицательная функция f(x) дважды непрерывно дифференцируема и при x [P1, P2] 1 w |f (x)| A A Hooley C. On the number of divisors of a quadratic polynomial. Acta Math., 110 (1963), 97Ц1для некоторых A > 0, w 1. Тогда справедлива асимптотическая формула P T [f] = S[f] - q(l) + R[f], где 2/3 5/3 4/R[f] 0 (q) 0 (a) -1/2(a) P A-1/3 + 0(q) 0(a) a log P + w +0(q) 0(a) A1/2a1/2-1(q) -1/2(a) + q1/20(a) -1/2(a) log2 P, и a = (l, q). При использовании теоремы 8 в остаточном члене R[f] наиболее существенным оказывается первое слагаемое 2/3 5/3 4/3 2/0 (q) 0 (a) -1/2(a) P A-1/3 0 (q) 0(a) P A-1/3. В работе Быковского26 соответствующее слагаемое имеет вид q a1/2 log4/3 P P A-1/3. За счет такого улучшения в теореме 6 и получается уточнение остаточного члена по сравнению с формулой (6). Доказательство теоремы 8 отличается тем, что вместо элементарного метода Виноградова для подсчета целых точек в областях26, оно использует оценки тригонометрических сумм, полученных методом ван дер Корпута. Кроме того, в доказательстве применяется новая оценка сумм Клостермана q mx+ny q Kq(l, m, n) = q(xy - l) e2i, x,y=обобщающая неравенство (16): |Kq(l, m, n)| 0(q) 0((l, m, n, q)) (lm, ln, mn, q)1/2 q1/2. Работы автора по теме диссертации [1] Устинов А. В. О статистических свойствах конечных цепных дробей. Записки научн. семин. ПОМИ, 322 (2005), 186Ц211. [2] Устинов А. В. О статистиках ГауссаЦКузьмина для конечных цепных дробей. Фунд. и прикл. математика (2005), 195Ц208. [3] Устинов А. В. Короткое доказательство тождества Эйлера для континуантов. Мат. заметки, 79: 1 (2006), 155Ц156. [4] Устинов А. В. Вычисление дисперсии в одной задаче из теории цепных дробей. Мат. сборник, 198: 6 (2007), 139 - 158. [5] Устинов А. В. О среднем числе шагов в алгоритме Евклида. Материалы IX краевого конкурса молодых ученых, Хабаровск, ТОГУ (2007), 149Ц157. [6] Быковский В. А., Устинов А. В Статистика траекторий частиц для однородной двумерной модели УПериодический газ ЛоренцаФ. Функц. анализ и приложения, 42: 3 (2008), 10Ц22. [7] Устинов А. В. О числе решений сравнения xy l (mod q) под графиком дважды непрерывно дифференцируемой функции. Алгебра и анализ, 20: 5 (2008), 186Ц216. [8] Устинов А. В. Асимптотическое поведение первого и второго моментов для числа шагов в алгоритме Евклида. Известия РАН, 72: 5 (2008), 189Ц224.