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

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

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

Фроленков Дмитрий Андреевич

Средние значения чисел Фробениуса, длин

алгоритмов Евклида и характеров Дирихле.

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

Диссертация

на соискание ученой степени

кандидата физико–математических наук

Научный руководитель — доктор физико–математических наук И. Д. Шкредов Москва 2013 Содержание Введение 3 0.1.

Общая характеристика работы

0.2. Обозначения 0.3. Содержание работы Глава 1. Среднее значение чисел Фробениуса с тремя аргументами 1.1. Вспомогательные утверждения и обозначения 1.2. О функции Редсета 1.3. Выделение плотности 1.4. Разделение задачи на отдельные случаи 1.5. Вычисление сумм первого типа 1.6. Вычисление сумм второго типа 1.7. Вычисление сумм третьего типа 1.8. Доказательство теоремы 4 Глава 2. Асимптотическое поведение первого момента для числа шагов в алгоритме Евклида по избытку и недостатку 2.1. О сумме дробных долей 2.2. Вспомогательные утверждения 2.3. Доказательство теоремы 5 2.4. Доказательство теоремы 6 2.5. Доказательство теоремы 7 Глава 3. Новый численный вариант неравенства Пойя -Виноградова 3.1. Метод Быковского 3.2. Доказательство теоремы 8 Список литературы Введение 0.1. Общая характеристика работы Диссертация подготовлена в отделе алгебры и теории чисел Федерального государственного бюджетного учреждения науки Математического института имени В.А. Стеклова Российской Академии наук.

Актуальность темы диссертации.

Настоящая диссертация посвящена изучению средних значений чисел Фробениуса и количества шагов в алгоритмах Евклида, а также исследованию сумм характеров Дирихле. Все три задачи являются классическими задачами аналитической теории чисел, ими занимались соответственно: В.И. Арнольд, Я. Бургейн, Я.Г. Синай; Г. Хейльбронн, Д. Хенсли; И.М. Виноградов, Д. Пойя, Э.Ландау, А. Хилдебранд, А. Гранвиль, К. Саундарараджан и многие другие.

Изучение вопроса о поведении чисел Фробениуса в среднем началось в 1994 г. со статьи Д. Дейвисона [2], в которой им были сформулированы две гипотезы (см. S 0.3.1). Чуть позже В.И. Арнольд [27], [28] предположил, что верны даже более сильные утверждения о средних значениях чисел Фробениуса. Для случая чисел Фробениуса от трех переменных гипотезы Д. Дейвисона и В.И. Арнольда в более сильной форме были доказаны А.В. Устиновым [36] в 2009 г. В той же работе А.В. Устинов предположил, что при усреднении по всем трем переменным может быть получен еще более точный результат. В настоящей диссертации доказывается это предположение А.В. Устинова. Отметим, что поведение чисел Фробениуса от произвольного числа аргументов было исследовано в работах Й. Марклофа [14] и А. Стромбергссона [26].

Первые результаты о среднем количестве шагов в стандартном алгоритме Евклида были получены Г. Хейльбронном [8] в 1968 г.

В последствии целый ряд математиков последовательно уточняли результат Хейльбронна (формулировки могут быть найдены, например, в [37]). Другим направлением исследований стало получение аналогичных результатов для модифицированных алгоритмов Евклида (см. работы А.В. Устинова [39], [40] и Е.Н. Жабицкой [31], [32]). В настоящей диссертации доказываются новые оценки остаточных членов в асимптотических формулах для числа шагов различных алгоритмов Евклида.

Первые нетривиальные оценки сумм характеров Дирихле были независимо получены и опубликованы Д. Пойя и И.М. Виноградовым в 1918 г (результат получил название “неравенство Пойя-Виноградова”).

Существенное усиление этого неравенства было получено лишь в г. А. Гранвилем и К. Саундарараджаном [4]. Позднее, данный результат был улучшен Л. Голдмакером [5]. В этой проблематике важной задачей является также получение наиболее точной константы в неравенстве Пойя-Виноградова, так как известно, что эта константа связана с оценкой величины минимального квадратичного невычета. На сегодняшний момент, наилучшее значение константы принадлежит А.

Гранвилю и К.Саундарараджану [4]. Однако в некоторых задачах важнее оказывается не информация об этой константе, а использование численно точной формы неравенства Пойя-Виноградова. В настоящей диссертации мы доказываем новый вариант численно точного неравенства ПойяВиноградова, улучшая предыдущий результат К. Померанца [20].

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

Основные положения диссертации, выносимые на защиту найдена асимптотическая формула для среднего значения чисел Фробениуса с тремя аргументами при усреднении по трем параметрам (теорема 4);

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

Практическая значимость полученных результатов.

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

Личный вклад соискателя. Все результаты диссертации получены автором самостоятельно.

Апробация работы. Результаты настоящей диссертации докладывались автором на следующих семинарах и международных конференциях.

кафедральный семинар кафедры теории чисел под руководством чл.–корр. РАН Ю. В. Нестеренко и д.ф.–м.н. Н. Г. Мощевитина;

семинар “Арифметика и геометрия” под руководством д.ф.–м.н.

Н. Г. Мощевитина, к.ф.–м.н. О. Н. Германа и к.ф.–м.н. И. П. Рочева;

семинар “Тригонометрические суммы и их приложения” под руководством д.ф.–м.н. Н. Г. Мощевитина и к.ф.–м.н. И. П. Рочева;

“Научный семинар Хабаровского отделения Института прикладной математики ДВО РАН” под руководством чл.–корр. РАН В. А. Быковского;

международная конференция “27th Journees Arithmetiques” Вильнюс, Литва, 27.06.2011-01.07. международная конференция “Диофантовы приближения. Современное состояние и приложения.” Минск, Беларусь, 03.07.2011.-09.07.2011.

международная конференция “Конференция памяти Пола Турана” Будапешт, Венгрия, 22.08.2011-26.08.2011.

Опубликованность результатов диссертации Результаты диссертации опубликованы в работах [42], [43], [44] списка использованных источников. Всего по теме диссертации опубликовано работы.

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

Благодарности Соискатель считает своим приятным долгом в первую очередь поблагодарить доктора физико–математических наук, профессора И. Д. Шкредова, доктора физико–математических наук, профессора Н. Г. Мощевитина за постоянный интерес и внимание к работе.

Кроме того, соискатель благодарит кандидата физико–математических наук И. С. Резвякову за высказанные идеи по упрощению доказательства теоремы 7.

[] –целая часть числа,т.е. наибольшее целое число, не превосходящее ; {} = [] –дробная часть числа ;

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

Запись = [0 ; 1..., ] означает разложение рационального числа в стандартную цепную дробь длины = (), в которой 0,..., — натуральные и 2 при Через 1 () будем обозначать сумму неполных частных числа () –функция Мебиуса:

() = (1), если = 1 · · ·, где различные простые;

() –функция Эйлера:

() –функция Мангольдта:

() –характеристическая функция делимости на натуральное число Если — некоторое утверждение, то [] означает 1, если истинно, и 0 в противном случае.

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

0.3.1. Среднее значение чисел Фробениуса с тремя аргументами.

Определение 1. Числом Фробениуса (1,..., ) натуральных чисел 1,...,, взаимно простых в совокупности, называется наибольшее целое, не представимое в виде суммы Во многих задачах оказывается удобнее рассматривать функцию равную наибольшему целому, не представимому в виде суммы (0.2), но уже с натуральными коэффициентами 1,...,. Наиболее обширный обзор результатов и задач, связанных с числом Фробениуса, приведен в книге Д. Рамиреса Алфонзина [22].

Пусть > 0, 1 > 0, 2 > 0, 3 > 0 —действительные числа, натуральное. Тогда обозначим за (1, 2 ), (1, 2, 3 ) следующие области Заметим, что | (1, 2, 3 )| 1 2 3 3. Д. Дейвисон [2] сформулировал следующую гипотезу Гипотеза 1. Существует конечный предел Эта гипотеза, даже в более сильной форме, была доказана А.В. Устиновым в работе [36]. В статье [36] было получено, что функция (,, ) в среднем ведет себя как.

Теорема 1. (А.В. Устинов) Для любого > 0 справедливо где Теорема 2. (А.В. Устинов) Для любого > 0 справедлива асимптотическая формула Отметим, что теорема 2 является прямым следствием применения теоремы 1. Также используя теорему 1, А. Стромбергссон1 уточнил результаты Устинова.

Теорема 3. (А. Стромбергссон) Для любого > 0 справедливы асимптотические формулы Основным результатом первой главы является следующая теорема.

Теорема 4. Для любого > 0 выполнено где Это утверждение было сформулировано А.В. Устиновым в работе [36] в виде гипотезы.

Замечание 1. Отметим, что непосредственное применение теоремы 1 позволяет получить лишь следующий результат Используя теорему 4, можно получить следующий результат, улучшающий теорему 3.

Следствие 1. Для любого > 0 справедлива оценка Доказательство теоремы 4 использует идеи из работ А.В. Устинова [36], [37] и работы Е.Н. Жабицкой [31]. Также применяются классические оценки тригонометрических сумм.

1частное сообщение А.Стромбергссона, переданное А.В. Устинову 0.3.2. Асимптотическое поведение среднего значения числа шагов в различных модификациях алгоритма Евклида.

Существует много вараиантов алгоритма Евклида, приводящие к представлению рационального числа в виде различных непрерывных дробей. Рассмотрим произвольное рациональное число из отрезка [0, 1].

Классическому алгоритму Евклида соответствует разложение числа в стандартную цепную дробь длины = (/), в которой 1,..., — натуральные и 2 при 1.

Алгоритму Евклида с делением по избытку соответствует разложение числа в приведенную регулярную непрерывную дробь Алгоритму Евклида с выбором минимального по модулю остатка соответствует разложение в дробь длины = (/), где 0 — целое, 1,..., — натуральные, Алгоритму Евклида с нечетными неполными частными соответствует разложение в дробь длины = (/), где 0 — нечетное целое, 1,..., —нечетные натуральные, Так же нам понадобятся статистики Гаусса-Кузьмина, которые для фиксированного [0, 1] и рационального = [0; 1,..., ] задаются равенством В работе [37] А.В.Устинов исследовал среднее значение величины (/). Для + () была получена асимптотическая формула В книге [38] А.В.Устинова эта оценка уточняется до + () = (1 log4 ).

В работе Е.Н.Жабицкой (см. [31]) исследовалось среднее значение величины (/). Для () была доказана асимптотическая формула Основным результатом второй главы являются следующие две теоремы.

Теорема 5. Для остаточного члена в асимптотической формуле (0.9) выполнено Теорема 6. Для остаточного члена в асимптотической формуле (0.12) выполнено Таким образом, нами получены асимптотические формулы с лучшими понижениями в остаточных членах. Важную роль в доказательстве теоремы 6 играет теорема 7, которая, возможно, имеет самостоятельный интерес.

Теорема 7. Для суммы выполнено Рассуждения, применяемые при доказательстве теоремы 7, схожи с методами, которые были использованы Н.П. Романовым и А.Г. Постниковым в [35] для получения элементарного доказательства асимптотического закона распределения простых чисел.

Замечание 2. В статье [32] доказано, что Таким образом из теоремы 6 следует новая оценка остаточного члена в асимптотической формуле для среднего значения суммы неполных частных классических цепных дробей Замечание 3. Аналогично (0.9) доказывается асимптотическая формула для статистик Гаусса-Кузьмина (см. [38]) Определение константы 1 () см. в [38]. Проделывая рассуждения, аналогичные доказательству теоремы 5, получаем новую оценку остаточного члена Замечание 4. В [39] для среднего числа шагов в алгоритме Евклида с выбором минимального по модулю остатка была доказана асимптотическая формула с остаточным членом равным Используя Замечание 3 несложно получить новую оценку остаточного члена Замечание 5. В [40] для среднего числа шагов в алгоритме Евклида с нечетными неполными частными была доказана асимптотическая формула с остаточным членом равным Используя Замечание 3 несложно получить новую оценку остаточного члена 0.3.3. Новый численный вариант неравенства Пойя-Виноградова.

Пусть (mod ) –примитивный характер Дирихле. Положим 1.38 · 108 обе оценки в теореме 8 лучше, чем (0.18) и (0.19), соответственно.

Среднее значение чисел Фробениуса с тремя 1.1. Вспомогательные утверждения и обозначения Разложим рациональное число [0, 1] в стандартную цепную дробь Через 1 () будем обозначать сумму неполных частных Лемма 1. (см. [12]) Для любого натурального > 1 выполнено делителей натурального числа n, тогда для любого > 0.

Следующая лемма общеизвестна (преобразование Абеля) Лемма 3. (см. [33, гл. 2, S5]) Пусть ()—непрерывно-дифференцируема на [1 + []; ], —произвольные числа, 2. Будем вести внешнее суммирование по,. Рассмотрим случай, когда C не принадлежит отрезку AB, следовательно Получаем и условие + 2 необходимо учитывать. Тогда внешнее суммирование ведется по области а внутреннее по, который мы разбиваем следующим образом Следовательно, Проделывая преобразования аналогичные тем, что были сделаны для получаем В этом параграфе мы вычислим 11, 21, 31, 41, 51.

1.5.1. Случай 1.

Лемма 9. Справедлива следующая асимптотическая формула где 11 определена в (1.20).

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