Приложения оценок сумм Клостермана к некоторым задачам метрической и аналитической теории чисел тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Российская Академиия наук

Математический институт имени В. А. Стеклова

На правах рукописи УДК 511.21, 511.33, 511.37

УСТИНОВ Алексей Владимирович

Приложения оценок сумм Клостермана к некоторым задачам метрической и аналитической теории чисел

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

АВТО РЕФЕРАТ диссертации на соискание ученой степени доктора физико-математически

0034ьхио^

п

Москва — 2008

I

003461054

Работа выполнена в отделе теоретической и прикладной математики Хабаровского отделения Института прикладной математики Дальневосточного отделения Российской Академии наук

Научный консультант: чл.-корр. РАН В. А. Быковский

Официальные оппоненты: доктор физико-математических наук,

профессор В. Г. Журавлев

доктор физико-математических наук, профессор А. М. Зубков

доктор физико-математических наук, профессор Н. Г. Мощевитин

Ведущая организация: Московский педагогический

государственный университет

Защита диссертации состоится 26 февраля 2009 г. в 14 часов на заседании диссертационного совета Д 002.022.03 при Математическом институте им. В. А. Стеклова Российской академии наук по адресу Москва, ул. Губкина, д. 8

С диссертацией можно ознакомиться в библиотеке Математического института им. В. А. Стеклова

Автореферат разослан " " 200 & г.

Ученый секретарь диссертационного совета Д 002.022.03 приМИАН, д. ф.-м.н. профессор ^ 47 ' Н. П. Долбилин

Актуальность темы

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

Фундаментом для современных исследований являются классические работы Хинчина, Кузьмина, П.Леви, в которых была создана метрическая теория цепных дробей. Этими авторами были разработаны теоретико-вероятностные и эргодические методы, позволившие позднее получить ряд ярких результатов о статистических свойствах элементов цепных дробей (Бабенко, Ибрагимов, Филипп). В конце XX века были поставлены новые задачи, связанные с работой алгоритма Евклида и его вариантов (Кнут, Арнольд). Основной прогресс в их решении был достигнут эргодическими методами (Хенсли, Балле, Балади, Флажо-ле). Но в некоторых случаях удавалось применить методы аналитической теории чисел, восходящие к Хейльбронну и Портеру, приводящие к более точным результатам (Кнут, Яо, Авдеева, Быковский).

О классических приложениях сумм Клостермана.

Асимптотические свойства целочисленных решений уравнения

Х1У1 + Х2У2 = п (1)

лежат в основе различных теоретико-числовых результатов. При фиксированном значении одной из переменных, например, у2> переменные Xi, оказываются связаны сравнением

Х1У1 = п (mod у2). (2)

Наличие нетривиальных оценок на суммы Клостермана

Kq(a,b)= 1)-е2^, (3)

1,1/=о

согласно критерию Вейля, означает равномерность распределения решений сравнения (2). Это наблюдение позволяет находить

асимптотические формулы для сумм вида

Х1У1+Х2У2=П

Частным случаем уравнения (1) является соотношение be — ad — 1, которому удовлетворяют числители и знаменатели последовательных дробей а/Ь < с/d ряда Фарея. Для фиксированного знаменателя d и числителя с (0 ^ с ^ d, (с, d) = 1) длина отрезка [a/b,c/d]

с а _ 1 d~b~bd

определяется величиной Ь = с-1 (mod d). Равномерность распределения пар (Ь, с), для которых be =1 (mod d) позволяет описать распределение длин отрезков между соседними дробями в ряде Фарея, что приводит к усовершенствованию кругового метода Харди-Литтлвуда1.

Ещё одним важным вопросом, в котором возникает уравнение (1) является аддитивная проблема делителей, связанная с асимптотическим поведением сумм

^a0(fc)cro(/í+ п).

к^Т

К ним сводится подсчёт четвертого момента ^-функции Римана на критической прямой2.

Хейльбронн3 установил связь уравнения (1) с конечными цепными дробями. Благодаря этому ему удалось доказать асимптотическую формулу для среднего числа шагов в алгоритме Евклида (см. ниже).

О задачах метрической теории цепных дробей. Хорошо известно, что любое вещественное число а каноническим спосо-

1 Kloosterman H. D. On the representation of numbers in the form ax2 + by2 + сг2 + dt2 - Acta Math., 49 (1927), 407-464

2Heath-Brown D. E. The fourth power moment of the Riemann zeta function Proc. — London Math. Soc. (3), 1979, 38, 385-422

3HElLBRONN H. On the average length of a class of finite continued fractions. — Abhandlungen aus Zahlentheorie und Analysis, Berlin, VEB (1968), 89-96

бом раскладывается в цепную (непрерывную) дробь

а = [?о;91,-..,дп,...] = 9о +--—:— (4)

+ | 1

с целой частью <?о = [а] и неполными частными дп = ^„(а) € N при п ^ 1. Она конечна только для рациональных а = [Яо'> <?ь • ■ •, н в этом случае при я ^ 1 последнее неполное частное больше 1. По определению,

Р„ = Р„(а) и <Э„ = д„(а) (п = 0,1,2,...)

— числитель (целое) и знаменатель (натуральное) несократимой

п-ой подходящей к а дроби

рп

При этом Р0 = <7о и <5о = 1В метрической теории чисел ряд задач посвящен статистическим свойствам цепных дробей. Например, для действительных чисел а удается описать типичное поведение неполных частных в представлении (4), рост знаменателей <5„(а) и порядок аппроксимации а подходящими дробями Р„(сс)/<Э„(о;)4-

Пусть £ € [0,1] — фиксированное действительное число и

ап = Тп{а) = [0;д„+1,9„+2,...], где Т — отображение Гаусса, переводящее в себя отрезок [0,1]:

Т(а) = при а Ф 0, Г(0) = 0.

Обозначим через ¥п{х) меру множества всех иррациональных чисел а, для которых а„ ^ х. Гаусс исследовал итерации отображения Т и пришел к следующей гипотезе:

Нт Рп(ж) = 1оё2(1 + ж)

п—юо

4хинчин А. Я. Цепные дроби. — М.: Наука, 1978

Лишь в 1928 году появилась работа Кузьмина5 с доказательством асимптотической формулы

F„(z) = log2(l+z) + 0(e-A^),

где Л некоторая абсолютная положительная константа. В качестве следствия теоремы Кузьмина легко получить асимптотическую формулу для меры множества точек, для которых q„ — к

где

й = 1о&(1+ЩТ2))' (5)

Более сильный результат (экспоненциальную скорость сходимости) в этом направлении получил французский математик П. Леви6. Вирзинг7 указал явно скорость сходимости:

Fn(x) - log2(l H- х) ж А"

с абсолютной константой Ai = — О.ЗОЗбб... (впоследствии названной константой Вирзинга). Последнюю точку поставил Ба-бенко8, доказав существование бесконечной убывающей к нулю последовательности чисел Aj

и соответствующей последовательности аналитических функций для которых

оо

F„(x) = log2(l + х) + ]Г МФПк-fc=1

5Kuz'min R. О. Sur un problème de Gauss — Atti del Congresso Internazionale dei Matematici, Bologna, 6 (1928), 83-89

6LÉVY P. Sur les lois de probabilité dont dependent les quotients complets et incomplets d'une fraction continue. — Bull. Soc. Math. France, 57 (1929), 178-194

7Wirsing E. On the theorem of Gauss-Kusmin-Lévy and a Probenius-type theorem for function spaces. — Acta Arith. 24 (1974), 507-528

8Бабенко К. И. Об одной задаче Гаусса. — ДАН СССР, 238:5 (1978), 1021-1024

Изучение свойств отображения Гаусса Т основано на спектральных свойствах оператора

(например, при s = 1 такой оператор используется в доказательстве теоремы Кузьмина4). Ключевую роль здесь играет его доминирующее собственное значение A(s). Про эту функцию известно, что она определена и аналитична в области Res > 1/2 и положительна для действительных s > 1/2. В частности, теорема Кузьмина означает, что Л(1) = 1 и соответствующей собственной функцией является плотность Гаусса log2(l + ж). Число

известно как константа Леви, а число А"(1), для которого не известно представления через арифметические постоянные, — как константа Хенсли.

Оператор G„ также связал с поведением случайной величины Хп = log Q„(a), где Qj (а) — знаменатель j-ой подходящей дроби к числу а, которое выбирается случайно из отрезка [0,1] (см. работы Ибрагимова9 и Филиппа10). Для Хп доказана центральная предельная теорема11:

Кроме того, для математического ожидания и дисперсии Хп известны двучленные асимптотические формулы

9Ибрагимов И. А. Одна теорема из метрической теории цепных дробей. — Вестник Ленингр. Унив., 16: 1 (1961), 13-24

10Philipp W. Ein zentraler Grenzwertsatz mit Anwendungen auf die Zahlentheorie. — Z. Wahrsch. Venu. Gebiete, 8 (1967), 185-203

uFlajolet Ph., Vallée В. Continued fraction algorithms, functional operators, and structure constants. — Theoret. Comput. Sei., 194: 1-2 (1998),

адм-Ё^гпЬр

m—I 4 '

\m + zj

E{Xn) = El-n + Eo + 0{\T),

1-34

где

и Л1 — константа Вирзинга.

О статистических свойствах алгоритма Евклида. Детальный анализ алгоритма Евклида приводит к различным задачам о статистических свойствах конечных цепных дробей12. Если на вход алгоритма подается пара натуральных чисел с и в, (с < с?), то основной интерес представляет число выполняемых делений с остатком, которое совпадает с 5 = ) — количеством неполных частных в цепной дроби

Ф=[ 0; Л].

Впервые вопрос о поведении величины ¿(с/й) в среднем был исследован Хейльбронном3. Сводя задачу к уравнению (1) с 1 ^ Х\ ^ ж2) 1 ^2/1 < ?/2, элементарными методами он доказал асимптотическую формулу

s(c!d) = ~77о\~ ' logd + 0(log4logd).

(c,d) = l

Портер13, используя оценки сумм Клостермана, для того же среднего получил асимптотическую формулу с двумя значащими членами

Щ Е в(с/<0 = + + 0£{й-116+% (6)

М=1

где е — любое положительное и

21о82/31о82 С(2) Л 1

р ~ ТРГ ("г- СРТ ~ 7 ~ 2

— константа, получившая название константы Портера.

12кнут Д. Э. Искусство программирования, т. 2. Получисленные алгоритмы. — М., Санкт-Петербург, Киев: Вильяме, 2000

13porter J. W. On a theorem of Heilbronn. — Mathematika, 22: 1 (1975), 20-28

В то же время для дисперсии величины в(с/й) (при фиксированном значении знаменателя й) известна лишь правильная с точностью до константы оценка, принадлежащая Быковскому14:

Она получена методами аналитической теории чисел, также опирающимися на оценки сумм Клостермана.

Отдельно изучается задача о поведении в{с/й), когда параметры с и (1 меняются в пределах 1 < с < <1 < Я, где Я — растущий параметр. Определим среднее значение числа шагов в алгоритме Евклида

и дисперсию

п{к) = тЬй £ £" •

Суммируя равенство (6) нетрудно получить, что

ВД - ^ •:108 Я + С'р + (7)

с некоторой абсолютной константой С'Р. Однако, при усреднении по обоим параметрам с и й естественно надеяться на более точное описание поведения величины з(с/с1).

Ряд результатов в этом направлении был получен вероятностными и эргодическими методами. Диксон15 показал, что для любого положительного £ найдётся такая константа Со > 0, что

< (logd)1""

14Быковский В. А. Оценка дисперсии длин конечных непрерывных дробей. - ФПМ, 11: 6 (2005), 15-26

15Dixon J. D. The Number of Steps in the Euclidean Algorithm. — J. of Number Theory, 2 (1970), 414-422

для всех пар чисел (с, d) лежащих в области 1 < с < d < R, за исключением, не более R? ехр(—Co(log пар. Хенсли16 уточнил результат Диксона и доказал, что разность между величиной s(c/d) и ее средним значением асимптотически имеет нормальное распределение. Кроме того, Хенсли доказал асимптотическую формулу для дисперсии величины s(c/d):

D(R) = Dx • log R + o(Iog R),

где

Dl ~2 A'(l)3 ' (8)

Позднее Балле17 для дисперсии была получена двучленная асимптотическая формула со степенным понижением в остаточном члене

D(H) = А • log Д +Д,+ 0(R"™), (9)

где 7о — некоторая положительная постоянная. Аналогичные равенства были доказаны и для моментов более высокого порядка, откуда следует, что длина работы алгоритма асимптотически является гауссовской величиной18.

Статистики Гаусса-Кузьмина. В.И.Арнольдом19 была поставлена задача о статистических свойствах элементов цепных дробей для чисел c/d, когда точки (с, d) лежат внутри круга с2 + d? ^ R2, где R —► оо, или внутри другой расширяющейся области. Там же было сделано предположение, что ответ не зависит от формы области и во всех случаях пропорционален мера Гаусса.

Для фиксированного х 6 [0,1] и рационального г = [io;tb • ■ • ,ts\ статистики Гаусса-Кузьмина задаются равенством

5(x)(r) = = s(r)) [0; tjf... Л] ^ ху

16Hensley D. The Number of Steps in the Euclidean Algorithm. — J. of Number Theory, 49 (1994), 142-182

17Vallée В. A Unifying Framework for the Analysis of a Class of Euclidean Algorithms. — Proceedings of LATIN'2000, Lecture Notes in Computer Science 1776, Springer, 343-354

18Baladi V., Vallée В. Euclidean algorithms are Gaussian. — J. Number Theory, 110 (2005), 331-386

19 АРНОЛЬД В. И. Задачи Арнольда. — M.: Фазис, 2000

Задача Арнольда заключается в определении асимптотического поведения суммы

NX(R)= £ s{x)(c/d), (Ю)

М)еП(я)

где Q(R) — область, полученная гомотетией с коэффициентом R (R —* оо) из некоторой фиксированной области По:

ад = R ■ Оо = {{х, у): х,у > 0, (яг/Л, y/R) 6 Q0} ■

Аргументы Хейльбронна и Портера позволяют доказать20 асимптотическое равенство

2 s(.)(c/<¡) = НМ1M.ibji+OM,

равномерное по х € [0,lj. Однако этого результата недостаточно для преодоления главной трудности, которая заключается в том, что в равенстве (10) при фиксированном d переменная с пробегает отрезок, длина которого, вообще говоря, не кратна d.

Для сектора с2 + d2 ^ R2 (с, d ^ 0) задача Арнольда была впервые решена Авдеевой и Быковским21. Доказательство опиралось на оценки сумм Клостермана и существенно использовало внешнее усреднение по d. Затем Авдеевой22 была доказана более точная асимптотическая формула

NX{R) = - log(l + х) ■ R2 logR + 0(R2).

7г

В работе [1] была получена асимптотическая формула с двумя значащими членами:

NX(R) = -log(l+®)-R2logR + C0(x)-R2 + O{R17/9log2R). (11)

7г

20Авдеева М. О. Распределение неполных частных в конечных цепных дробях. — Владивосток: Дальнаука, 2000, препринт ДВО РАН, ХО ИПМ №4

21 Авдеева М. О., Быковский В. А. Решение задачи Арнольда о статистиках Гаусса-Кузьмина. — Владивосток, Дальнаука, 2002 (препринт)

22Авдеева М. О. О статистиках неполных частных конечных цепных дробей. — Функц. анализ и его прил. 38: 2 (2004), 1-11

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

Задача Синая Бильярд Синая является простейшей моделью рассеивающей динамической системы: маленький шар движется внутри квадратного поля, в центр которого помещено круглое препятствие с отражающими стенками. Предполагается, что все удары абсолютно упруги. Очевидно, что вместо квадратного бильярда можно рассматривать плоскость, на которой круглые препятствия располагаются вокруг каждой точки целочисленной решетки. Такая модель и будет рассматриваться в дальнейшем.

Пусть 0</г<|иТ>0. Открытый круг радиуса Л с центром в некоторой точке назовем ее /¿-окрестностью. Определим подмножество Ол(Т) в [0,2п), состоящее из углов (р, для которых луч

пересекает /i-окрестность некоторой целочисленной точки (т, п) Ф (0,0) из круга

В 1918 г. Полиа23 доказал, что С/ДТ) = 1 для всех Т > /г-1. Отвечая на вопрос, поставленный в 1981 г. Синаем, Бока, Гологан и Захареску24 доказали, что для любого е > 0 равномерно по

Г€[ 0,/Г1]

23Полиа Г., Сеге Г. Задачи и теоремы, из анализа, т. 2. — М.: Наука,

1978

24Boca 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-73

{(icos<£,isiny?) : t > 0}

{(x,y)GR2:at + y^T2}. Обозначим через Gh(T) нормйрованную меру ft/,(Г):

Gh(T) = ~mesnh(T)€[0,1].

где

если 0 < £ ^ \\ 1) (1 - 1ое - 1)) , если I < < ^ 1.

С физической точки зрения, величину (З/^Т) можно интерпретировать как функцию распределения длин свободного пробега частиц, движущихся прямолинейно из начала координат до их первого попадания в Л-окрестность некоторой ненулевой целочисленной точки. Речь идет об однородной двумерной модели "Периодический газ Лоренца".

Цель работы

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

Научная новизна

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

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

2) В задаче Арнольда о статистиках Гаусса-Кузьмина для конечных цепных дробей доказана асимптотическая формула с

а(«) =

12/1

-

двумя значащими членами и степенным понижением в остатке. Как следствие доказана независимость главного члена от формы рассматриваемой области.

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

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

Теоретическая и практическая ценность

Диссертация носит теоретический характер. Метод, развитый в работе, может быть использован для дальнейшего анализа алгоритма Евклида, его вариантов и многомерных аналогов. Решение задачи Синая может быть использовано в ядерной физике в теории каналирования частиц.

Апробация работы

Результаты работы прошли апробацию на семинарах по теории чисел под руководством А. А. Карацубы, Н. Г. Мощевитина, Ю. В. Нестеренко, на семинаре кафедры дискретной математики под руководством О.Б.Лупанова, на семинаре по динамическим системам под руководством В. В. Козлова и Д. В. Трещева механико-математического факультета МГУ, на семинаре по теории вероятностей под руководством А. М. Зубкова в МИРАН, на семинарах по теории чисел под руководством В. Г. Чирского в МПГУ и В. Г. Журавлева в ВГПУ, а также на международных конференциях по теории чисел, "Аналитические методы в теории чисел, теории вероятностей и математической статистике" (ПО-МИ РАН, 2005), "Аналитические и комбинаторные методы в теории чисел и геометрии" (МГУ, 2006), "Аналитические и вероят-

ностные методы в теории чисел" (Паланга, 2006), "Диофантовы и аналитические проблемы теории чисел" (МГУ, 2007), XXVth Journées Arithmétiques (Эдинбург, 2007) и на Дальневосточных математических школах (2006, 2007).

Публикации

Основные результаты диссертации опубликованы в работах, список которых приведен к конце автореферата. В совместной работе [б] вклад соавторов одинаков.

Структура и объем работы

Диссертация изложена на 154 страницах и состоит из введения, четырех глав и приложения. Библиография содержит 77 наименований. В четырёх главах диссертации доказываются основные результаты (см. теоремы 1-7 ниже). В приложение помещены вспомогательные утверждения. Некоторые из них (оценки сумм Клостермана, применение метода ван дер Корпута, см. раздел "методы исследования") являются новыми и уточняют известные результаты25,26.

Содержание работы

О числе знаменателей цепных дробей, не превосходящих данной границы. В главе 1 диссертации исследуется случайная величина, которая как и Хп отвечает за рост знаменателей подходящих дробей. Для иррационального а € [0,1] через Е(а, R) будем обозначать число

Д(а>Д) = #0>1 :<&(<*)< Д}.

Величину E(a,R) можно считать непрерывным аналогом длины конечной цепной дроби 5(a), которая изучена во второй главе диссертации.

25Estermann Т. On Kloosterman's sum. — Mathematika, 8 (1961), 83-86

26Выковский В. А. Асимптотические свойства целых точек (ai, а2), удовлетворяющих сравнению сцаг = I (mod q).

Рассмотрим среднее значение Е(а, Я)

E(R)= f Е(а, R) da Jo

и дисперсию

D{R)= ! (E{a,R)-E{R)fdoc= f E2{a,R)da-E2(R). Jo Jo

Для них доказываются асимптотические формулы с двумя значащими членами и степенными понижениями в остатках.

Теорема 1. При R ^ 2

£(Я) = El-\ogR + E0 + О (Я-1 log Я),

где

б'=02Г в» = 7РГ11ое2+г Ф)} 2'

Теорема 2. Яри Л ^ 2

Ъ(Я) = А • к^Я + Д> + 0(Я~1/Зк^4 Я), где £>1, Д) — абсолютные константы.

Константа ¿1 в главном члене для математического ожидания очевидным образом связайа с константой Леви — А'(1). Константа Г>1 выражается через сумму абсолютно сходящегося ряда. В последствии выясняется, что она связана с константой Хенсли.

Задача о вычислении Е(Я) и -О (Я) является более простой, чем её дискретный вариант (см. теоремы 3-4). В то же время доказательства теорем 1-2 могут служить иллюстрацией ключевых идей, которые будут применяться при анализе конечных цепных дробей.

О статистических свойствах алгоритма Евклида. В главе 2 математическое ожидание Е(Я) выражается через число решений неравенства

ХхУх + х2у2 <R (1 < < ®а, 1 < 01 < г/2)- (12)

Наличие дополнительного усреднения по параметру d ^ Я позволяет доказать асимптотическую формулу с лучшим, чем в (7), понижением в остаточном члене.

Теорема 3. Пусть R > 2. Тогда

E(R) = Ех ■ logR + Е0 + OÍR'1 log4R), (13)

где

~ 2log2 2log2 / 3 log 2 <'(2) 3\ 3

1 = 1 =~СЩ~' + 2J-2-

Вычисление дисперсии D(ñ) сводится к исследованию неравенства

x\(ayi + by2) + x2(cyi + dy2) < R,

где 1 ^ xi < Жг, 1 ^ 2/1 < У2 и det(® j) = ±1. С его помощью, как и в главе 1, для дисперсии доказывается двучленная асимптотическая формула.

Теорема 4. Пусть R ^ 2. Тогда

Я(Д) = £>! • log Л + £>о + 0(R~1/4 log7/4 Л),

где Di = Di и Do — абсолютные константы.

Отметим, что в соответствующем результате (9) утверждается лишь существование некоторой константы 7о > 0; теорема 4 показывает, что в качестве 70 можно брать любое число, меньшее 1/4.

Сопоставление равенства (8) с формулами для вычисления Di и Di в теоремах 2 и 4 показывает, что

ъ -D 2Л'/(1)-Л/(1)2

Dl ~ Dl ~2 Ш3 '

По мнению разных авторов константа Di (которую также называют константой Хенсли) не выражается в терминах известных арифметических постоянных. Нахождение её численного значения представляет собой отдельную задачу. Известен полиномиальный алгоритм вычисления Di, то есть алгоритм, который вы-

дает первые d цифр за 0(сГ) арифметических операций27. Доказательство теоремы 4 дает новую явную формулу для вычисления Di (в цитированных работах алгоритмы основаны на вычислении спектра оператора G3). Теорема 4 может быть также использована для нахождения константы £)0, для которой в настоящее время не известно численного значения.

Статистики Гаусса-Кузьмина. В главе 3 излагается результат работы [2], где была рассмотрена область fio общего вида. Предполагается, что она задана в полярных координатах

fio = {{р,<р) ■ 0 ^ <Р < тг/4,0 ^ р < г(р)}

и имеет площадь

■i гтг/4 У°=21

Для суммы (10) удается не только доказать двучленную асимптотическую формулу вида (11), но и уточнить оценку остаточного члена.

Теорема 5. Пусть R ^ 2, и r{ip) 6 C^'QO, 7г/4]). Предположим также, что для всех <р £ [0, тг/4] функция г((р) удовлетворяет ограничениям

t

r{<p) ^ е0 > 0, r'(<£>) ^ г{<р) • tg <р.

Тогда, равномерно по х € [0,1], оу

NX(R) = ■ log (ж + 1) • R2 log R + C(x) ■ R2 + 0(fí9/5 log3 R), sW

где C(x) не зависит от R.

В частности, теорема 5 показывает, что главный значащий член в асимптотической формуле пропорционален мере Гаусса и зависит не от формы области а лишь от ее площади Vq.

Как следствие из теоремы 5 получается ответ на вопрос Арнольда: для относительной частоты встречаемости натурального

27Lhote L. Computation of a class of continued fraction constants. — Analytic Algorithmics and Combinatorics (ANALCO), Proc. 2004 New Orleans workshop

к в качестве неполных частных рассматриваемых цепных дробей выполняется асимптотическое равенство

Ni(R) \logRy

где Pk = log2 + J — вероятность появления числа к в качестве неполного частного действительного числа (см. формулу (5)).

В качестве дополнения к теореме 5, в конце главы 3 доказывается уточнение результата Портера (6), распространенное на случай статистик Гаусса-Кузьмина.

Теорема 6. Пусть 6^2 — натуральное и х € (0,1] — действительное. Тогда для суммы

®:(Ь)= Е

1<а<6 (а.Ь) = 1

справедлива асимптотическая формула

ф:(Ь) = ^ (log(* + 1) log b + Ср(х)) + 0£>х (*/■ log'/- Ь), где е > 0 — сколь угодно малое число,

СР(х) = log(l + х) (log , - + 27 - 2^1 - l) +

+hi(x) + h2{x) + ^ fx ■ [х < 1] - Х

2 V l + xJ

а функции h\(x) и hг(х) заданы абсолютно сходящимися рядами

х

п-\-тх

-log(l + x) ,

00 1 / "

Е

п=1 \т=1 П=1 \п^,п<п+п /

При этом оценка остаточного члена становится равномерной по х в предположении, что х € [хо, 1] для некоторого фиксированного Хо > 0.

Алгоритм Евклида, в котором при делении выбирается наименьший по модулю остаток

а = Ьд + г, д =

а 1 Ь + 2

1<г<1 2 2'

приводит к разложению в дробь

о

т = ¿0 +

¿2+ . ¡Н

'"Ч

длины I = 1{а/Ь), где ¿о — целое, ¿1, ..., ^ — натуральные,

ек = ±1, (к = 1,...,1), Ьк+ек+1^2 (к= 1,...1),

и е^ = — 1 при и — 2.

Для среднего числа шагов в таком алгоритме Евклида известен результат18

где <р — (1 + \/5) /2 — золотое сечение, С{ — абсолютная постоянная и (3 > 0. Оказывается, что для любого рационального числа а/Ь выполняется равенство 1(а/Ь) = Поэтому вари-

ант теоремы 5 для треугольной области и теорема 6 приводят к асимптотическим формулам аналогичным (7) и (13)

тр^ту ЕЕ '<•/»> * «>•

щ Е • ь«'+сг+°.(»"1/в 1о«"6+'

где Я, Ь ^ 2 и С[ — абсолютная константа.

Задача Синая. При изучении движущихся в кристалле достаточно быстрых частиц, траектории которых обусловлены

главным образом многократным их рассеянием на ядрах, возникает необходимость рассматривать более общую ситуацию, когда траектория начинается не в некоторой целой точке, а в её /i-окрестности.

Зафиксируем вещественное v из интервала (—1,1). Ориентированная в направлении (eos y?, sin у?), параметрически заданная прямая

{(—hv sin ip + t cos tp, hv cos <p + t sin ip) ей2 :t e (—00,00)} (14)

на плоскости при t — 0 проходит через ближайшую к началу координат О = (0,0) точку О' = (-hv s'm (p,hv cos <р) (проекция О на прямую (14)). Еще одно параметрическое представление

{(ж-t'sinyj, y + í'cos<p) GR2 : t' € (-00,00)}

определяет перпендикулярную к (14) прямую, проходящую при if = 0 через точку (х,у). Они пересекаются в некоторой точке при

t = R(x,y) = xcos(p + ys\n<p, t' -— U(x, y) = xs'míp — ycos<p + hv.

Среди всех целочисленных точек (m, п) на плоскости с условиями

Я(т,п)>0 и \U(m,n)\<h

выберем ту из них — (m(ip), n(tp)), для которой величина R(m, п) принимает минимальное значение. Такая точка (т(<р), п((р)) всегда найдется, поскольку по теореме Минковского о линейных формах существует целочисленная пара (т,п) ф (0,0), для которой

|mcos¡p+nsm¡¿>| ^ (h(l — М))-1, |msin!¿>-ncos<p| < h{l — |v|).

Другими словами, (m(¡p),n(ip)) — первая целочисленная точка (т, п) (0,0), /i-окрестность которой пересекает частица, движущаяся вдоль прямой (14) из точки О' в положительном направлении. Положим

r(ip) ----h-R (m(ip), n(ip)), u{ip) - /Г1 • U (т{ф),п{<р)).

При этом

О < г(<р) < -——¡—г и - 1 < u{ip) < 1. 1 - и

Ориентируясь на терминологию из ядерной физики, назовем г = r(ip) нормированным свободным пробегом, a v и и = и(<р) — нормированными выходным и входным прицельными параметрами. Пусть

О < г0 < , 1, , и - 1 < и- < и+ < 1.

1-М

Главным результатом главы 4 является следующее утверждение.

Теорема 7. Пусть |v| < с < 1. Тогда при любом е > О для функции распределения

Г to

= / Х[о,г0] (r(v))X[u_,u+] И<р)) d(p Jo

при h —► 0 справедлива асимптотическая формула

$v{h) = J J J p{<p,r,v,u)d<pdrdu + 0e>c(h5~e^,

равномерная no v,u-,u+ и ip0 G [0,2n] с плотностью

p(<p, r, v, и) = p(r, v, u) = p{r, u, v) = p(r, -u, -v), которая при и ^ |г>| имеет вид

если 0 ^ г < ¿y; />(»■.«.«)= (;-!-«). если ^ < г <

если j^; ^ r.

С физической точки зрения функцию ^р{<р, г, v, и) можно интерпретировать как плотность частиц, движущихся прямолинейно с единичной скоростью под углом ip после первого рассеяния

с выходным прицельным параметром V — h • v в /i-окрестности некоторого узла целочисленной решетки и проходящих расстояние R = Л-1 • г до повторного рассеяния с входным прицельным параметром h • и.

Следует отметить, что плотность p(ip,r,v,u) не зависит от угла <р. Это означает, что целочисленная решетка в пределе обладает свойством изотропности, которое, как известно, проявляется также в задачах о случайных блужданиях и дискретных гармонических функциях28. Симметрия плотности относительно замены (v, и) на (и, v) объясняется изотропностью и "обратимостью" траекторий частиц.

Синай29 доказал эргодичность прямоугольного бильярда с вырезанным из него кругом радиуса h. Ему же принадлежит постановка задачи об асимптотическом поведении функции распределения длины траектории до первого столкновения с вырезанным кругом (столкновения с бортами не принимаются во внимание) при h —► 0. Речь идет о частном случае рассматриваемой нами задачи для v = 0, = 1, и+ = 1, tp0 = 2п. При v — 0 (однородная задача) теорема 7 была доказана в [6].

Рассматриваемая двумерная модель связана с теорией кана-лирования частиц, движущихся параллельно кристаллографическим плоскостям30.

Методы исследования

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

Многократно приходится решать вопрос об асимптотическом

28Spitzer F. Principles of Random Walks. — New York: Van Nostrand, 1964

29Синай Я. Г. Эргодические свойства газа Лоренца. — Функциональный анализ и его приложения, 13: 3 (1979), 46-59

30Кадменский А. Г., Самарин В. В., Тулинов А. Ф. Регулярное и стохастическое движение в кристалле при каналировании. Эволюция потока частиц в толстом кристалле. — Физика элементарных частиц и атомного ядра, т. 34 (2003), вып. 4, 822-868

поведении сумм

3-1

и,и=0

для различных функций /. При этом используется стандартный подход, основанный на переходе к тригонометрическим суммам. Пусть / записана в виде конечного ряда Фурье

т,п—0

где ^

СМ, п) = ^ £ / (и/в, «/в) • е-2**22»22

— конечные коэффициенты Фурье функции /. Тогда тождество £ 5в(1и, - 1) • / (и/в, «/в) = ^ £ / («/?,«/?) + ВД,

и,у=0 и,и=0

где

3-1

Еч1Л = Е Ся(т>п)' Кя(т>п)

т,п=0 (т.п)^(О.О)

сводит задачу об асимптотическом поведении суммы (15) к оценкам сумм Клостермана (3). В диссертации используются утверждения, основанные на оценке Эстермана25

\Кд(т,п)\ ^ а0(9) • (т,п,д)1/2 • <?1/2. (16)

Доказательства каждой из теорем 1-6 разбиваются на случаи в зависимости от значений параметров. Например, при исследовании неравенства (12) отдельно рассматриваются случаи х2 < [Д1/2] + 1/2 ях2> [В}/2\ + 1/2. Идейно такой подход близок к круговому методу с его разбиением на большие и малые дуги. Отличие заключается в следующем: из условия х2 > [Я1/2] +1/2 вытекает, что у2 < Я1/2+ 1/2 и, таким образом, "малые дуги" для

переменных хь становятся "большими" для У\,У2- Как и в круговом методе возникает необходимость изучения "особых рядов". Их слагаемыми являются остаточные члены различных асимптотических формул, а через их суммы выражаются константы в теоремах 1-6.

Пусть q — натуральное число, I — целое и / — неотрицательная функция. Обозначим через Т[/] число решений сравнения ху = 1 (mod q), лежащих в области Pi < х < Р2, 0 < у < f(x):

тм= Е Е 5ч(хУ~1)-

Pl<x^P2 0

При доказательстве теорем 4 и 6 встает вопрос об асимптотических формулах для Т[/]. Подобные формулы лежат также в основе результатов о свертках арифметических функций2,31, суммах арифметических функций на значениях квадратичного полинома31, 26, статистических свойствах алгоритма Евклида13,20 и др.

В общем случае задача об асимптотике величины T[f] впервые была решена Быковским26. Доказательство основывалось на формуле суммирования Пуассона и использовании оценки Эстер-мана (16).

В приложении излагается результат работы [7], уточняющий теорему Быковского. Через S[f] обозначим сумму

sw = l Е м*)/(*).

q pi<I<P2

где ßq,i{x) — число решений сравнения ху = I (mod q) относительно переменной у, лежащей в пределах 1 ^ у ^ q.

Теорема 8. Пусть Р\, Р-х — действительные числа, Р = Р2 — Pi J5 2. Предположим также, что на всем отрезке [Pi, Р2] вещественная неотрицательная функция f(x) дважды непрерывно дифференцируема и при х € [Fi, Р2]

2 *\f"(x)| ^ Н

31Hooley С. On the number of divisors of a quadratic polynomial. Acta Math., 110 (1963), 97-114

для некоторых А > 0, w ^ 1. Тогда справедлива асимптотическая формула

T[f] = 5[/] — — ■ 6q(l) + R[f\,

где

R[f] «ш ol'\q) ol'3{a) а%(а) PA'1'3 + a0{q) a0(a) a log P+ +o0{q) a0(a) (А1/2а1/2а^(д) a_1/2(a) + q1/2a0(a) a2_1/2(a) log2 P),

ua = (l,q).

При использовании теоремы 8 в остаточном члене Д[/] наиболее существенным оказывается первое слагаемое

Л) оТ{а) а%(а) РА~V» « Л) a2 (a) РА^\

В работе Быковского26 соответствующее слагаемое имеет вид

(f ■ a1/2 • log4/3 Р • РА~1/3.

За счет такого улучшения в теореме 6 и получается уточнение остаточного члена по сравнению с формулой (6).

Доказательство теоремы 8 отличается тем, что вместо элементарного метода Виноградова для подсчета целых точек в областях26, оно использует оценки тригонометрических сумм, полученных методом ван дер Корпута. Кроме того, в доказательстве применяется новая оценка сумм Клостермана

Kq(l,m,ri) = j26q(xy-l)eM^,

х,у= 1

обобщающая неравенство (16):

|Kq(l, т, n)| ^ <70(д) • ао{{1,т, п, q)) • (lm, In, тп, q)1/2 • q1/2.

Работы автора по теме диссертации

[1] УСТИНОВ А. В. О статистических свойствах конечных цепных дробей. — Записки научн. семин. ПОМИ, 322 (2005), 186-211.

[2] Устинов A.B. О статистиках Гаусса-Кузьмина для конечных цепных дробей. — Фунд. и прикл. математика 11 (2005), 195-208.

[3] УСТИНОВ А. В. Короткое доказательство тождества Эйлера для континуантов. — Мат. заметки, 79: 1 (2006), 155-156.

[4] УСТИНОВ A.B. Вычисление дисперсии в одной задаче из теории цепных дробей. — Мат. сборник, 198: 6 (2007), 139— 158.

[5] УСТИНОВ А. В. О среднем числе шагов в алгоритме Евклида. — Материалы IX краевого конкурса молодых ученых, Хабаровск, ТОГУ (2007), 149-157.

[6] Быковский В. А., Устинов А. В Статистика траекторий частиц для однородной двумерной модели "Периодический газ Лоренца". — Функц. анализ и приложения, 42: 3 (2008), 10-22.

[7] УСТИНОВ А. В. О числе решений сравнения ху = I (mod q) под графиком дважды непрерывно дифференцируемой функции. — Алгебра и анализ, 20: 5 (2008), 186-216.

[8] УСТИНОВ A.B. Асимптотическое поведение первого и второго моментов для числа шагов в алгоритме Евклида. — Известия РАН, 72: 5 (2008), 189-224.

<

Обозначения и соглашения

Предисловие

Введение

0.1. О задачах метрической теории цепных дробей 9 0.2. О числе знаменателей цепных дробей, не превосходящих данной границы

0.3. О статистических свойствах алгоритма Евклида

0.4. Статистики Гаусса-Кузьмина для конечных цепных дробей

0.5. Задача Синая

0.6. Методы исследования

Глава 1. Вычисление первого и второго моментов в одной задаче из метрической теории цепных дробей

1.1. О цепных дробях

1.2. Асимптотическая формула для математического ожидания

1.3. Выражение дисперсии через сумму специального вида

1.4. Вычисление трех вспомогательных сумм

1.5. Асимптотическая формула для дисперсии

Глава 2. Асимптотическое поведение первого и второго моментов для числа шагов в алгоритме Евклида

2.1. О математическом ожидании и дисперсии

2.2. Предварительные вычисления

2.3. Асимптотическая формула для математического ожидания

2.4. Вычисление двух вспомогательных сумм

2.5. Асимптотическая формула для дисперсии

Глава 3. Задача Арнольда о статистиках Гаусса-Кузьмина

3.1. Переход к системе уравнений и неравенств

3.2. Анализ первого случая

3.3. Анализ второго случая

3.4. Асимптотическая формула в задаче Арнольда

3.5. Результаты для сектора и треугольной области

3.6. Уточнение теоремы Портера

3.7. О среднем числе шагов в алгоритме Евклида с выбором минимального по модулю остатка

Глава 4. Статистики траекторий в задаче Синая

4.1. Свойства целочисленных пар (т((р), n{ip))

4.2. Вспомогательные преобразования

4.3. Применение оценок сумм Клостермана

4.4. Выделение главного члена

В первой половине XX века в основополагающих работах А. Я. Хинчина, Р. О. Кузьмина, П. Леви и других авторов была создана метрическая теория чисел — одно из самых актуальных направлений теории чисел. При этом были разработаны теоретико-вероятностные и эргодические методы, позволившие получить целый ряд фундаментальных результатов, касающихся статистических свойств элементов цепных дробей. Во второй половине XX века этот подход нашёл широкое применение при изучении алгоритма Евклида и других задач.

В настоящей диссертации развиваются новые методы исследования задач метрической теории цепных дробей, основанные на оценках сумм Кло-стермана. Они позволяют в ряде случаев не только существенно усилить известные результаты, но и решить новые теоретико-числовые задачи, возникающие в статистической физике. К основным можно отнести следующие результаты диссертации:

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

2) в задаче Арнольда о статистиках Гаусса-Кузьмина для конечных цепных дробей доказана асимптотическая формула с двумя значащими членами и степенным понижением в остатке. Как следствие доказана независимость главного члена от формы рассматриваемой области;

3) получены принципиально новые оценки остаточных членов в асимптотических формулах для первого и второго моментов числа шагов в алгоритме Евклида;

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

Введение

Асимптотические свойства целочисленных решений уравнения

12/1 + ^22/2 = га (0.1) лежат в основе различных теоретико-числовых результатов. При фиксированном значении одной из переменных, например, переменные х\, у\ оказываются связаны сравнением

Х1У1 = п (mod у2). (0.2) Наличие нетривиальных оценок на суммы Клостермана я-1

Kq(a, b)=Yl 5^ХУ ~ ' (0.3) х,у=0 согласно критерию Вейля, означает равномерность распределения решений сравнения (0.2). Это наблюдение позволяет находить асимптотические формулы для сумм вида

Х1У1+Х2У2=П

Частным случаем уравнения (0.1) является соотношение be — ad = 1, которому удовлетворяют числители и знаменатели последовательных дробей а/Ъ < c/d ряда Фарея. Для фиксированного знаменателя d и числителя с (0 ^ с ^ d, (с, d) = 1) длина отрезка [а/Ъ, c/d} с а 1 d~b = bd определяется величиной b = с"1 (mod d). Равномерность распределения пар (Ь,с), для которых be = 1 (mod d), позволяет описать распределение длин отрезков между соседними дробями в ряде Фарея, что приводит к более точному варианту кругового метода Харди-Литтлвуда (см. работу Клостермана [54|).

Ещё одним важным вопросом, в котором возникает уравнение (0.1), является аддитивная проблема делителей, связанная с асимптотическим поведением сумм а0(к)а0(к + п). к^Т

К ним сводится подсчёт четвертого момента ("-функции Римана на критической прямой (см. статью Хис-Брауна [47], а также обзор [52]).

Хейльбронн в работе [49] установил связь уравнения (0.1) с конечными цепными дробями. Благодаря этому ему удалось доказать асимптотическую формулу для среднего числа шагов в алгоритме Евклида (см. далее раздел 0.3 введения).

О других арифметических приложениях уравнения (0.1) и сумм Кло-стермана см. обзор [48].

В основе результатов диссертации наряду с уравнением (0.1) лежат асимптотические свойства решений неравенств хт + Х2У2 < Я, хг(аух + Ъу2) + х2(су1 + йу2) ^ Я, где В, — растущий параметр и ёеЦ £ = ±1. Второе из них также анализируется с помощью оценок сумм Клостермана. В рамках такого подхода удается получить новые результаты и существенно уточнить уже известные, доказанные ранее эргодическими методами.

0.1. О задачах метрической теории цепных дробей

Хорошо известно, что любое вещественное число а каноническим способом раскладывается в цепную (непрерывную) дробь а = [до; Чи ■ ■ ■, Чп, • ■ ■] = 9о +------(0.4)

71 + . [ 1

Яп + . с целой частью до = М и неполными частными дп = дп(а) £ N при п ^ 1. Она конечна только для рациональных а — [до; д],., д5], и в этом случае при в ^ 1 последнее неполное частное д8 больше 1. По определению,

Рп = Рп(а) и д„ = дп(а) (71 = 0,1,2,.) числитель (целое) и знаменатель (натуральное) несократимой п-ой подходящей к а дроби рп Ц/п

При этом Ро = до и = 1В метрической теории чисел ряд задач посвящен статистическим свойствам цепных дробей. Например, для действительных чисел а удается описать типичное поведение неполных частных в представлении (0.4), рост знаменателей (¿п(а) и порядок аппроксимации а подходящими дробями Рп{а)/Яп{а) (см. [32]).

Пусть х £ [0,1] — фиксированное действительное число и ап = Тп(а) = [0; д„+ь дп+2,. ], где Т{а) — отображение Гаусса, переводящее в себя отрезок [0,1]:

Т(а) = при аф 0, Г(0) = 0.

Обозначим через Рп(х) меру множества всех иррациональных чисел а, для которых ап ^ х. Гаусс исследовал итерации отображения Т и пришел к следующей гипотезе:

Нт ад = 1оё2(1 + х) = 10У + п—>оо 2 об этом известно из переписки Гаусса с Лапласом, см. [15, глава 3]). Лишь в 1928 году появилась работа Кузьмина [57] с доказательством асимптотической формулы где Л — некоторая абсолютная положительная константа. В качестве следствия теоремы Кузьмина легко получить асимптотическую формулу для меры множества точек, для которых дп = к:

Р*(п) = - =рк + 0(е-Л^), где

Более сильный результат (экспоненциальную скорость сходимости) в этом направлении получил французский математик П. Леви (1929, [58]). Вирзинг (1974, [77]) указал явно скорость сходимости: п(ж)-1оё2(1 + х)хА? с абсолютной константой А1 = —0.30366 . (впоследствии названной константой Вирзинга). Окончательное решение задачи Гаусса принадлежит Бабенко (1978, [8]). Он доказал существование бесконечной убывающей к нулю последовательности чисел \j и соответствующей последовательности аналитических функций ^(гс), для которых оо 1ова(1 + х) + ]Г Ы*)К к= 1 о вычислении чисел Ах, А2, . см. [7, 9]).

Изучение свойств отображения Гаусса Т основано на спектральных свойствах оператора млм = Е (йгЬр ■ / тп= 1 4 ' 41 ' например, при й = 1 такой оператор используется в доказательстве теоремы Кузьмина, см. [32]). Ключевую роль здесь играет его доминирующее собственное значение А(в). Про эту функцию известно, что она определена и аналитична в области Иед > 1/2 и положительна для действительных я > 1/2. В частности, теорема Кузьмина означает, что А(1) = 1 и соответствующей собственной функцией является плотность Гаусса к^2(1 + х). Число

А'(1) = М log2 известно как константа Леви, а число А"(1), для которого представление через арифметические постоянные не известно, — как константа Хенсли. Оператор также связан с поведением случайной величины Хп = где Я](а) — знаменатель ^'-ой подходящей дроби к числу а, которое выбирается случайно из отрезка [0,1] (см. работы Ибрагимова [17], Филиппа [65]—[67], а также обзор [43]). Для Хп доказана центральная предельная теорема:

П-ОО , , „„„.,,00 л/£>1 • п )

Кроме того, для математического ожидания и дисперсии Хп известны двучленные асимптотические формулы

Е(Хп)=Ё1-п + Ё0 + О(Хп1), А-п + Д, + 0(А?), где А'(1) - А"(1) ~ А'(1)2 и А1 — константа Вирзинга.

0.2. О числе знаменателей цепных дробей, не превосходящих данной границы

В главе 1 диссертации исследуется случайная величина, которая, как и Хп, отвечает за рост знаменателей подходящих дробей. Для иррационального о; € [0,1] через Е(а, К) будем обозначать число

Величину Е(а,К) можно считать непрерывным аналогом длины конечной цепной дроби з(а), которая будет изучаться в главе 2 диссертации. Рассмотрим среднее значение Е(а, Щ

Е(Я) = [ Е(а, К) ¿а Jo и дисперсию

Ъ{Щ= [ (Е(а, Я) — Е(11))2 йсс = [ Е2(а, К) йа — Ё2(Щ. У о ./о

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

Теорема 1. При Я ^ 2

E{R) = E1-\ogR + E0 + O , (0-6) 2 log 2 ~ 21og2/ С'(2)Л 3 o = WÍlos2+7"®" 2"

Теорема 2. При R > 2 А • log Л + Д, + 0(Я~1/3 log4 i?), где Di, Do — абсолютные константы.

Константа Е\ в главном члене для математического ожидания очевидным образом связана с константой Леви —А'(1). Консганта D\ выражается через сумму абсолютно сходящегося ряда, и впоследствии выясняется, что она связана с константой Хенсли.

Задача о вычислении E(R) и D(R) является более простой, чем её дискретный вариант (см. теоремы 3-4). В то же время доказательства теорем 1-2 могут служить иллюстрацией ключевых идей, которые будут применяться при анализе конечных цепных дробей.

0.3. О статистических свойствах алгоритма Евклида

Детальный анализ алгоритма Евклида приводит к различным задачам о статистических свойствах конечных цепных дробей (см. [20, разд. 4.5.3]). Если на вход алгоритма подается пара натуральных чисел с и d (с < d), то основной интерес представляет число выполняемых делений с остатком, которое совпадает с s = s(c/d) — количеством неполных частных в цепной дроби с/d — [0; ¿i,., ts].

Впервые вопрос о поведении величины s(c/d) в среднем был исследован Хейльбронном. В 1968 г., сводя задачу к уравнению (0.1) с 1 < жх ^ ж2> 1 ^ Vi ^ У2, элементарными методами он доказал асимптотическую формулу (см. [49]) щ s(c/d) = .logd + 0(log4logd). cfdjll

Уточнения остаточного члена в этой формуле принадлежат Тонкову (см. работы [71, 72]). В 1975 г. Портер, используя оценки сумм Клостермана, для того же среднего получил асимптотическую формулу с двумя значащими членами (см. [68]) s(c/d) = ^ . logd + Ср - 1 + Oe(d~1/6+£), (0.7) где е — любое положительное и

21о82/31о82 С'(2) Л 1 константа, получившая название константы Портера (её окончательный вид был найден Ренчем, см. [56]).

В то же время для дисперсии величины б'(с/с£) (при фиксированном значении знаменателя с1) известна лишь правильная с точностью до константы оценка, принадлежащая Быковскому (2005, [11]):

1 d d ' -- 2 log 2 Л2 , , --^-log dj «Clog d.

Она получена методами аналитической теории чисел, также опирающимися на оценки сумм Клостермана.

Отдельно изучается задача о поведении 5(с/<^), когда параметры с и d меняются в пределах 1 ^ с ^ ^ ^ Я, где R — растущий параметр. Рассмотрим среднее значение числа шагов в алгоритме Евклида

4 ; с^Я с^ и дисперсию т) = штг) Е Е - Е(д))2 •

Суммируя равенство (0.7), нетрудно получить, что

Е{В) = ■ 1о6 Я + СР + (0.8) с некоторой абсолютной константой С'Р (см. [63]). Однако при усреднении по обоим параметрам cжd естественно надеяться на более точное описание поведения величины з(с/в).

Ряд результатов в этом направлении был получен вероятностными и эргодическими методами. В 1970 г. Диксон в работе [38] показал, что для любого положительного е найдётся такая константа со > 0, что !й\ 21°ё21 j s{c/d) - -¡гщ-log d (log d)V2+£ для всех пар чисел (с, d), лежащих в области 1 ^ с ^ d ^ R, за исключением не более R2 ехр(—co(log.R)e/2) пар (см. также [39]). Хенсли в статье 1994 г. [50] уточнил результат Диксона и доказал, что разность между величиной s(c/d) и ее средним значением асимптотически имеет нормальное распределение. Кроме того, Хенсли доказал асимптотическую формулу для дисперсии величины s(c/d):

D(R) = Di • log R + o(log R),

Позднее Балле (2000, [75]) для дисперсии была получена двучленная асимптотическая формула со степенным понижением в остаточном члене

D(R) = Di ■ logR + Do+ 0(R-^), (0.10) где 7o — некоторая положительная постоянная. Аналогичные равенства были доказаны и для моментов более высокого порядка, откуда следует, что длина работы алгоритма асимптотически является гауссовской величиной (см. [34]). В той же работе рассмотрены другие варианты алгоритма Евклида и другие, отличные от s(c/d), характеристики сложности алгоритма.

В главе 2 математическое ожидание E(R) выражается через число решений неравенства xiyi + х2у2 < R (1 ^ xi ^ х2,1 < 2/1 ^ у2)- (0.11)

Наличие дополнительного усреднения по параметру d ^ R позволяет доказать асимптотическую формулу с лучшим, чем в (0.8), понижением в остаточном члене.

Теорема 3. Пусть R ^ 2. Тогда

E(R) = Ех ■ log R + Е0 + OiR"1 log4 R), (0.12) где 21og2 2log2/3log2 „ C'(2) 3N 3

Eí-Eí~WT' 0 wl~+27~т'У~2.

Вычисление дисперсии D(R) сводится к исследованию неравенства х\(аух + Ъу2) + x2{cyi + dy2) ^ R, где 1 < xi ^ х2, 1 ^ у\ ^ У2 и det(" ¿) = ±1. С его помощью, как и в главе 1, для дисперсии доказывается двучленная асимптотическая формула.

Теорема 4. Пусть R ^ 2. Тогда

D(R) = D1 ■ log Я + D0 + 0(R~1/4 log7/4 R), (0.13) где Di = Di и Dq — абсолютные константы.

Отметим, что в соответствующем результате (0.10) работы [34] утверждается лишь существование некоторой константы 7о > 0; теорема 4 показывает, что в качестве 70 можно брать любое число, меньшее 1/4.

Сопоставление равенства (0.9) с формулами для вычисления Di и Di в теоремах 2 и 4 показывает, что

Di -Di -2—ш—"

По мнению разных авторов, константа (которую также называют константой Хенсли) не выражается в терминах известных арифметических постоянных (см. [42, 61]). Нахождение её численного значения представляет собой отдельную задачу (см. [37, 44, 74]). Известен полиномиальный алгоритм вычисления то есть алгоритм, который выдает первые сI цифр за О(оГ) арифметических операций (см. [60, 61]). Доказательство теоремы 4 дает новую явную формулу для вычисления 0\ (в цитированных работах алгоритмы основаны на вычислении спектра оператора С5). Теорема 4 может быть также использована для нахождения константы Д)) для которой в настоящее время численное значение не известно.

0.4. Статистики Гаусса-Кузьмина для конечных цепных дробей

В книге [5, задача 1993-11] (см. также [6]) В. И. Арнольдом была поставлена задача о статистических свойствах элементов цепных дробей для чисел с/(1, когда точки (с, с!) лежат внутри круга с2 + сР ^ Я2, где Я —» оо, или внутри другой расширяющейся области. Там же было сделано предположение, что ответ не зависит от формы области и во всех случаях такой же, как указывает инвариантная мера Гаусса.

Для фиксированного х е [0,1] и рационального т — [¿05^15 ■ • • статистики Гаусса-Кузьмина задаются равенством

8{х\г) = #0' : 1 < ^ < в = з(г), [0;£„. Л] <

В главе 3 рассматривается вопрос об асимптотическом поведении суммы

Л*(Л) = £ (0.14) где 0,{Я) — область, полученная гомотетией с коэффициентом Я (Я —» оо) из некоторой фиксированной области

П(Л) = Я ■ П0 = {(ж, у) : х, у > 0, (ж/Я, у/Я) & ОД •

Как показано в работе [1], аргументы Хейльбронна [49] и Портера [68] позволяют доказать асимптотическое равенство *{хЧФ) = 21о^х) -а^ + ом, (о.15) равномерное по х £ [0,1]. Однако этого результата недостаточно для преодоления главной трудности, которая заключается в том, что в равенстве (0.14) при фиксированном ё, переменная с пробегает отрезок, длина которого, вообще говоря, не кратна в,.

Для сектора с2 + сР ^ Я2 (с, с/ ^ 0) задача Арнольда была впервые решена в 2002 г. Авдеевой и Быковским в работе [3]. Доказательство опиралось на оценки сумм Клостермана и существенно использовало внешнее усреднение по d. Затем в статье [2] Авдеевой была доказана более точная асимптотическая формула

NX{R) = - log(l + х) • R2 log R + 0(R2),

7Г в которой остаточный член на log1''2 R лучше, чем в [3]. В 2005 г. в работе [25] была получена асимптотическая формула с двумя значащими членами:

NX(R) = - log(l + х) • R2 log R + Cq(x) ■ R2 + 0{Rl7'g log2 R).

7г

В главе 3 излагается результат работы [26], где была рассмотрена область fio общего вида. Предполагается, что она задана в полярных координатах

По = {{р,<р) : 0 ^ ip ^ тг/4,0 ^ р < г{<р)} и имеет площадь г-тг/4 i г71"/4

Vo=2 Jo т*{<р)йр.

Теорема 5. Пусть R ^ 2 и r((p) е (7^([0,7г/4]). Предположим также, что для всех (р G [0,7г/4] функция r(ip) удовлетворяет ограничениям г(ф) ^ е0 > 0, r\tp) ^ г(ф) • tg <р.

Тогда, равномерно по х £ [0,1],

NX{R) = • log (а; + 1) • R2 log R + С(х) ■ R2 + 0(Я9/5 log3 R), где C(x) не зависит от R.

В частности, теорема 5 показывает, что главный значащий член в асимптотической формуле пропорционален мере Гаусса и зависит не от формы области í^oi а лишь от ее площади Vq.

Как следствие из теоремы 5 получается ответ на вопрос Арнольда: для относительной частоты встречаемости натурального к в качестве неполных частных рассматриваемых цепных дробей выполняется асимптотическое равенство где pf. = log2 + k(k+2)) — вероятность появления числа к в качестве неполного частного действительного числа (см. формулу (0.5)).

В качестве дополнения к теореме 5, в конце главы 3 излагается результат работы [31], в которой результат Портера (0.7) уточняется и распространяется на случай статистик Гаусса-Кузьмина.

ТЕОРЕМА 6. Пусть b 2 — натуральное и х £ (0,1] — действительное. Тогда для суммы км = Е s(x)(a/&) а,Ь)=1 справедлива асимптотическая формула

К(Ъ) = ^ (log(x + 1) log b + Ср{х)) + Ов1Я log^ Ъ) , где е > 0 — сколь угодно малое число,

СР(Х) = log(l + х) (log х - Üü£±í> + 27 - 2g| - l) +

М*0 + f'Ax) + ® (ж ■ [х < 1] - , (0.16) а функции h\(x) и h2{x) заданы абсолютно сходящимися рядами

ОО 1 / п \ м*)-£- (0.17) n=l \га=1 /

П=1 \ZI^m<2+n /

При этом оценка остаточного члена становится равномерной по х в предположении, что х G [ж0,1] для некоторого фиксированного Xq > 0.

Алгоритм Евклида, в котором при делении выбирается наименьший по модулю остаток а = bq + г, q — приводит к разложению в дробь а 1 Ь + 2 я . в ' ~2 2' а Е\

7 + г2 + . £[ длины I = 1(а/Ь), где £0 — целое, ¿1, ., ^ — натуральные, е* = ±1, (А; = 1,.,0, + = 1,., I - 1), и £1 = — 1 при ^ = 2.

Для среднего числа шагов в таком алгоритме Евклида известен результат щтт) Е £ = ^'108 л+°+0(лА где <р = (1 + \/5)/2 — золотое сечение, Ci — абсолютная постоянная и (3 > 0. (см. [34]). Оказывается, что для любого рационального числа а/6 выполняется равенство 1{а/Ъ) = s^\a/b). Поэтому упрощенный вариант теоремы 5 (см. замечание 3.1) и теорема 6 приводят к асимптотическим формулам, аналогичным (0.8) и (0.12): кщт) Е Е wv ■ i°g д+а+о(д-1 log4 я),

Щ Е iWb)=^-log6 + OÎ + Oe(ô-1/eiog7/e^ô)> где Я, ¿> ^ 2 и С/ — абсолютная константа.

0.5. Задача Синая

Бильярд Синая является простейшей моделью рассеивающей динамической системы: маленький шар движется внутри квадратного поля, в центр которого помещено круглое препятствие с отражающими стенками. Предполагается, что все удары абсолютно упруги. Очевидно, что вместо квадратного бильярда можно рассматривать плоскость, на которой круглые препятствия располагаются вокруг каждой точки целочисленной решетки. Такая модель и будет рассматриваться в дальнейшем.

Пусть 0</г<|иТ>0. Открытый круг радиуса h с центром в некоторой точке назовем ее /i-окрестностыо. Определим подмножество в [0,27г), состоящее из углов 9?, для которых луч i cos</?, tsinip) : t ^ 0} пересекает /i-окрестность некоторой целочисленной точки (m, п) ф (0,0) из круга

Обозначим через Gh(T) нормированную меру fi/^T):

Gh(T) = mes Пн(Т)е[0,1]. z7t

В 1918 г. Полиа (см. [23], теория чисел, задача 239) доказал, что

Gh(T) = 1 для всех T ^ h-1. Отвечая на вопрос, поставленный в 1981 г. Синаем, в совместной работе [36] Бока, Гологан и Захареску доказали, что для любого Е > 0 равномерно по T G [0, h~l]

Gh{T) = Г7 a{t)dt + 0£{hl'*-s), (0.19) где a(t) если 0 < t ^

I (f - 1) (1 - log (i - 1)) , если i < í < 1.

С физической точки зрения величину Gh{T) можно интерпретировать как функцию распределения длин свободного пробега частиц, движущихся прямолинейно из начала координат до их первого попадания в h-окрестность некоторой ненулевой целочисленной точки. Речь идет об однородной двумерной модели "Периодический газ Лоренца".

При изучении движущихся в кристалле достаточно быстрых частиц, траектории которых обусловлены главным образом многократным их рассеянием на ядрах, возникает необходимость рассматривать более общую ситуацию, когда траектория начинается не в некоторой целой точке, а в её /i-окрестности.

Зафиксируем вещественное v из интервала (—1,1). Ориентированная в направлении (cos^, sinyp), параметрически заданная прямая hvsinip + icos(fi, hveos<p +1sinip) G E2 : ¿ G (—oo, oo)} (0.20) на плоскости при t = 0 проходит через ближайшую к началу координат О = (0,0) точку О' = (—hv sin ip, hv cos ф) (проекция О на прямую (0.20)). Еще одно параметрическое представление х - t' sin <р, у +1' cos (p) G M2 : t' G (—oo, oo)} определяет перпендикулярную к (0.20) прямую, проходящую при t' = 0 через точку (х,у). Они пересекаются в некоторой точке при t = R(x} у) = х cos (р + у sin <р, t' = U (х, у) — х sin ^р — у cos <р + hv.

Среди всех целочисленных точек (т, п) на плоскости с условиями

R(m,n)> 0 и \U(m,n)\ < h выберем ту из них — (т((р), п((р)), для которой величина R(m,n) принимает минимальное значение. Такая точка (ш(</?), п(</?)) всегда найдется, поскольку по теореме Минковского о линейных формах существует целочисленная пара (т,п) ф (0,0), для которой mcoscp + ns\xnp\ ^ {h{ 1 — Н))-1, \msm<p — ncos</?| < h( 1 — |v|).

Другими словами, (m(íp), п((р)) — первая целочисленная точка (т,п) ф (0,0), Д-окрестность которой пересекает частица, движущаяся вдоль прямой (0.20) из точки О' в положительном направлении. Положим г(ф) — h • R (m(ip), п((р)), u(ip) = h~l • U (m((p), n(cp)).

При этом

0 < г(ф) < и - 1 < u{tp) < 1.

Ориентируясь на терминологию из ядерной физики, назовем г = г(</?) нормированным свободным пробегом, a v и и = u(ip) — нормированными выходным и входным прицельными параметрами.

Пусть

0 < го < 1 и — 1 < и- < и+ < 1.

1-М

Главным результатом главы 4 является следующее ниже утверждение.

Теорема 7. Пусть |г>| < с < 1. Тогда при любом е > 0 для функции распределения

С физической точки зрения функцию ^р(<р,г,у,и) можно интерпретировать как плотность частиц, движущихся прямолинейно с единичной скоростью под углом после первого рассеяния с выходным прицельным параметром V = к ■ v в /г-окрестности некоторого узла целочисленной решетки и проходящих расстояние Я — /г-1 • г до повторного рассеяния с входным прицельным параметром И • и.

Следует отметить, что плотность /?(</?, г, V, и) не зависит от угла (р. Это означает, что целочисленная решетка в пределе обладает свойством изотропности, которое, как известно, проявляется также в задачах о случайных блужданиях и дискретных гармонических функциях (см., например, [69]). Симметрия плотпости относительно замены (г>, и) на (и,у) объясняется изотропностью и "обратимостью" траекторий частиц.

В работе [24] Синай доказал эргодичность прямоугольного бильярда с вырезанным из него кругом радиуса /г. Ему же принадлежит постановка задачи об асимптотическом поведении функции распределения длины траектории до первого столкновения с вырезанным кругом (столкновения с бортами не принимаются во внимание) при Н —> 0. Речь идет о частном случае рассматриваемой нами задачи для и = 0, = 1, = 1, </?о = 2тг. При V = 0 (однородная задача) теорема 7 была доказана в [12].

Из результатов работы [62], доказанных эргодическими методами, основанными на теореме Ратнер о классификации инвариантных эргодиче-ских мер под действием унипотентных потоков, следует существование при Н —> 0 справедлива асимптотическая формула предела функции при к —» 0 в частном случае с = 2-я. Этого недостаточно для доказательства изотропности и симметричности функции р(г, у,и).

Рассматриваемая двумерная модель связана с теорией каналирования частиц, движущихся параллельно кристаллографическим плоскостям (см., например, [18, 22]).

0.6. Методы исследования

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

Многократно приходится решать вопрос об асимптотическом поведении сумм

0-21) для различных функций /. При этом используется стандартный подход, основанный на переходе к тригонометрическим суммам (см., например, [21]). Пусть / записана в виде конечного ряда Фурье \

Па'а) = X) п) ' е 9 , где

Сд{т,п) = ~ V/ - - -е *

7 Ч) конечные коэффициенты Фурье функции /. Тогда тождество и,у=о ч/ ч и,и=0 чу где

9-1 д»[/] = X] Сд{т,п) • Кя(т,п) т,п=0 (т,п)/(0,0) сводит задачу об асимптотическом поведении суммы (0.21) к оценкам сумм Клостермана (0.3). В диссертации используются утверждения (см. разделы 5.2-5.3 приложения), основанные на оценке Эстермана из работы [40]: т.пЖ^'Кп,?)1'2-^2. (0.22)

Доказательства каждой из теорем 1-6 разбиваются на случаи в зависимости от значений параметров. Например, при исследовании неравенства (0.11) отдельно рассматриваются случаи ^ [Я1/2] + 1/2 и жг > 1/2. Идейно такой подход близок к круговому методу с его разбиением на большие и малые дуги. Отличие заключается в следующем: из условия х2 > [Я1/2]+ 1/2 вытекает, что у2 < R1^2 +1 и, таким образом, "малые дуги" для переменных х\, х2 становятся "большими" для у2. Как и в круговом методе, возникает необходимость изучения "особых рядов" (см., например, леммы 1.3, 1.7, 1.9, 2.5, 2.7, 2.9). Их слагаемыми являются остаточные члены различных асимптотических формул, а через их суммы выражаются константы в теоремах 1-6.

Пусть q — натуральное число, I — целое и / — неотрицательная функция. Обозначим через T[f] число решений сравнения ху = I (mod q), лежащих в области Pi < х ^ Р2, 0 < у ^ /(.г):

Tw= Е Е

При доказательстве теорем 4 и 6 встает вопрос об асимптотических формулах для T[f]. Подобные формулы лежат также в основе результатов о свертках арифметических функций [47, 51], суммах арифметических функций назначениях квадратичного полинома [10, 51], статистических свойствах алгоритма Евклида [1, 68] и др.

В общем случае задача об асимптотике величины T[f] впервые была решена Быковским в работе [10]. Доказательство основывалось на формуле суммирования Пуассона и использовании оценки Эстермана (0.22).

В разделе 5.5 приложения излагается результат статьи [31], уточняющий теорему Быковского. Через S[f] обозначим сумму где fJ>q,i{x) — число решений сравнения ху = I (mod q) относительно переменной у, лежащей в пределах 1 ^ у ^ q. теорема 8. Пусть Pi, Р2 — действительные числа, Р = Р2 — Pi ^ 2. Предположим такэюе, что на всем отрезке [Р\,Р2] вещественная неотрицательная функция J (х) дважды непрерывно дифференцируема и при х ё [Рг,Р2]

2 < и"{х)] * 2 для некоторых А > 0, w ^ 1. Тогда справедлива асимптотическая формула

T[f] = S[f] - | • 5g(l) + R[fl (0.23) где

R[f] vl'\q) о-У\а) a%(a) PA~1'4 (0.24) cr0(g) a0(a) (A1/2a1/2a^(q) <r1/2(a) + q1/2a0(a) a21/2(a) log2 P + a log P) , и a — (l,q).

При использовании теоремы 8 в остаточном члене Я[/] наиболее существенным оказывается первое слагаемое о/3(я) 4ГЧа) *%(а) PA-V3 « а02%) а2(а)

В работе [10] соответствующее слагаемое имеет вид qe • а1/2 ■ log4/3 Р • РА~1/3.

За счет такого улучшения в теореме б и получается уточнение остаточного члена по сравнению с формулой (0.7).

Доказательство теоремы 8 отличается тем, что вместо элементарного метода Виноградова для подсчета целых точек в областях, как было сделано в статье [10], оно использует оценки тригонометрических сумм, полученных методом ван дер Корпута. Кроме того, в доказательстве применяется новая оценка сумм Клостермана ад т, п) = Sq(xy - 1) е2-1^, х,у—\ обобщающая неравенство (0.22) (см. раздел 5.2 приложения):

Kq(l,m,n)\ ^ a0(q) • a0((l,m,n,q)) • (lm,ln,mn1q)1/2 ■ ql/2.

1. Авдеева М. О. Распределение неполных частных в конечных цепных дробях. — Владивосток: Дальнаука, 2000, препринт ДВО РАН, ХО ИПМ № 4.

2. Авдеева М. О. О статистиках неполных частных конечных цепных дробей. — Функц. анализ и его прил. 38: 2 (2004), 1-11.

3. Авдеева М. О., Быковский В. А. Решение задачи Арнольда о статистиках Гаусса-Кузьмина. — Владивосток, Дальнаука, 2002 (препринт).

4. Арнольд И. В. Теория чисел. — Госуд. учебно-педагогическое изд-во Наркомпроса РСФСР, 1939.

5. Арнольд В. и. Задачи Арнольда. — М.: Фазис, 2000.

6. Быковский В. А., Устинов А. В Статистика траекторий частиц для однородной двумерной модели "Периодический газ Лоренца". — Функц. анализ и приложения, 42: 3 (2008), 10-22.

7. Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.

8. Виноградов И. М. Особые варианты метода тригонометрических сумм. — М.: Наука, 1976.

9. Гнеденко Б. В. Курс теории вероятностей. (Дополнение.) — М.: Наука, 1988.

10. Грэхем Р. Л., Кнут Д. Э., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.

11. Ибрагимов И. А. Одна теорема из метрической теории цепных дробей. — Вестник Ленингр. Унив., 16: 1 (1961), 13-24.

12. Кадменскпн А. Г., Самарин В. В., Тулинов А. Ф. Регулярное и стохастическое движение в кристалле при каналировании. Эволюция потока частиц в толстом кристалле. — Физика элементарных частиц и атомного ядра, т. 34 (2003), вып. 4, 822-868.

13. Карацуба A.A. Основы ишпштической теории чисел. — М.: Наука, 1983.

14. Кнут Д. Э. Искусство программирования, т. 2. Получисленные алгоритмы. — М., Санкт-Петербург, Киев: Впльямс, 2000.

15. Коробов Н. М. Тригоноли т/)ические суммы и их приложения. — М.: Наука, 1989.

16. Кумахов М. А., Ширмир Г. Атомные столкновения в кристаллах. — М.: Атом-издат, 1980.

17. Полиа Г., Сеге Г. Задичи и теоре.чы из анализа, т. 2. — М.: Наука, 1978.

18. Синай Я. Г. Эргодические свойства газа Лоренца. — Функциональный анализ и его приложения, 13: 3 (1979), 46-59.

19. Устинов А. В. О статистических свойствах конечных цепных дробей. — Записки научн. семин. ПОМИ, 322 (2005), 186-211.

20. Устинов А. В. О статистиках Гаусса-Кузьмина для конечных цепных дробей. — Фунд. и прикл. мат&матика 11 (2005), 195-208.

21. Устинов А. В. Вычисление дисперсии в одной задаче из теории цепных дробей. — Мат. сборник, 198: 6 (2007), 139-158.

22. Устинов А. В. Асимптотическое поведение первого и второго моментов для числа шагов в алгоритме Евклида. — Известия РАН, 72: 5 (2008), 189-224.

23. Устинов А. В. О числе решений сравнения ху = I (mod q) под графиком дважды непрерывно дифференцируемой функции. — Алгебра и анализ, 20: 5 (2008), 186216.

24. Хинчин А. Я. Цепные дроби. — М.: Наука, 1978.33. apostol Т. М. Mathematical analysis — Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1974.

25. Baladi V., Vallée В. Euclidean algorithms are Gaussian. — J. Number Theory, 110 (2005), 331-386.35. berndt b.c. Ramanujan's notebooks. Part I — Springer-Verlag, 1985.

26. Boca 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-73.

27. Daudé H., Flajolet P., Vallée В. An average-case analysis of the Gaussian algorithm for lattice reduction. — Combin. Probab. Comput., 6 (1997), 397-433.

28. Dixon J. D. The Number of Steps in the Euclidean Algorithm. — J. of Number Theory, 2 (1970), 414-422.

29. DlXON J. D. A simple estimate for the number of steps in the Euclidean algorithm. — Amer. Math. Monthly, 78 (1971), 374-376.

30. Estermann T. On Kloosterman's sum. — Mathematika, 8 (1961), 83-86.41. finch S. R. Mathematical constants, (Encyclopedia of Mathematics and its Applications, 94.) — Cambridge University Press, Cambridge, 2003.

31. Finch S.R. Continued fraction transformation. — unpublished note (2007), http://algo.inria.fr/csolve/kz.pdf .

32. Flajolet Ph., Vallée В. Continued fraction algorithms, functional operators, and structure constants. — Theoret. Comput. Sci., 194: 1-2 (1998), 1-34.

33. Flajolet Ph., Vallée 13. Continued fractions, comparison algorithms, and fine structure constants. — Constructive., Experimental et Non-Linear Analysis, Proceedings of Canadian Mathematical Society, 27 (2000), 53-82.

34. Graham S.W., Kolesnik G. van der Coiput's method of exponential sums. — Cambridge University Press, 1991.

35. Hardy G.H , Write E. M. An Introduction to the Number Theory. — Clarendon Press, Oxford, 1979.

36. Heath-Brown D. R. The fourth power moment of the Riemann zeta function Proc. — London Math. Soc. (3), 197!). 38, 385-422.

37. Heath-Brown D. Arithmetic applications of Kloosterman sums. — Nieuw Arch. Wiskd., 5/1 (2000), 380-384.

38. Heilbronn II. On the average length of a class of finite continued fractions. — Abhandlungen aus Zahlenthcorie und Analysis, Berlin, VEB (1968), 89-96.

39. Hensley D. The Number of Steps in the Euclidean Algorithm. — J. of Number Theory, 49 (1994), 142-182.

40. HOOLEY C. On the number of divisors of a quadratic polynomial. Acta Math., 110 (1963), 97-114.

41. Jutila M. The fourth moment of Riemann's zeta-function and the additive divisor problem. — Analytic number theory, Vol. 2, Birkhäuser Boston, 139 (1996), 517-536.

42. Knuth D. E., Yao, A. C. Analysis of the subtractive algorithm for greatest common divisors. Proc. Nat. Acad. Sei. USA, 72: 12 (1975), 4720-4722.

43. Knuth D. E. Evaluation of Porter's Constant. — Сотр. and Maths, with Appls., 2 (1976), 137-139.

44. Kuz'min R. O. Sur un problème de Gauss — Atti del Congresso Internazionale dei Matematici, Bologna, 6 (1928), 83-89.

45. Lévy P. Sur les lois de probabilité dont dependent les quotients complets et incomplets d'une fraction continue. — Bull. Soc. Math. France, 57 (1929), 178-194.

46. Lewin L. Polylogarithms and associated functions. — New York: Elsevier North Holland, 1981.

47. Lhote L. Modélisation et approximation de sources complexes. — Masters thesis, University of Caen (2002).

48. Liiote L. Computation of a class of continued fraction constants. — Analytic Algorithmics and Combinatorics (ANALCO), Proc. 2004 New Orleans workshop.

49. MARKLOF J., StrömberGSSON A. The distribution of free path lengths in the periodic Lorentz gas and related lattice point problems. — arXiv:math/0706.4395vl.

50. Norton G. H. On the asymptotic analysis of the Euclidean algorithm. — J. Symbolic Comput. 10:1 (1990), 53-58.

51. Perron O. Die Lehre von den Kettenbrüchen (Band 1). — Stuttgart: B.G. Teubner Verlagsgesellschaft, 1954.65. philipp W. Ein zentraler Grenzwertsatz mit Anwendungen auf die Zahlentheorie. — Z. Wahrsch. Vcrw. Gebiete, 8 (1967), 185-203.

52. Philipp W., Stackelberc; O.P. Zwei Grenzwertsätze für Kettenbrüche. — Math. Annalen, 181 (19(59), 152-156.

53. Philipp W. Some metrical theorems in number theory. II. — Duke Math. J. 37 (1970), 447-458; errata 37 (J 970), 788.

54. Porter J. W. Oil a theorem of Heilbronn. — Mathematika, 22: 1 (1975), 20-28.

55. Spitzer F. Principles of Random Walks. — New York: Van Nostrand, 1964.

56. Tenenbaum G. Introduction to analytic and probabilistic number theoryh. — Cambridge University Press, 1995.

57. TONKOV T. The moan length of finite continued fractions. — Math. Balkanica, 4 (1974), 617-629.

58. TONKOV T. On I lie average length of finite continued fractions. — Acta Arith., 26 (1974/75), 47-57.

59. VALLÉE В. Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'EucluIe ut de Gauss. — Acta Arith. 81 (1997), 101-144.

60. VALLÉE B. Dynamique des fractions continues contraintes priodiques. — Journal of Number Theory, 72- 2 (1998), 183-235.

61. Vallée В. A Unifying Framework for the Analysis of a Class of Euclidean Algorithms. — Proceedings of LATIN'2000, Lecture Notes in Computer Science 1776, Springer, 343-354.

62. Weisstein E.W. CRC concise encyclopedia of mathematics. — Chapman & Hall/CRC, Boca Raton, FL, 2003.77. wlrslng e. On the theorem of Gauss-Kusmin-Lévy and a Frobenius-type theorem for function spaces. — Acta Arith. 24 (1974), 507-528.