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

Математический институт имени

В. А. Стеклова

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

УДК 511.335+511.336

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

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

длин алгоритмов Евклида

и характеров Дирихле.

01.01.06 – математическая логика,

алгебра и теория чисел

АВТО РЕФЕРАТ

Работа выполнена в отделе алгебры и теории чисел Федерального государственного бюджетного учреждения науки Математического института имени В.А. Стеклова Российской Академии наук

Научный руководитель: доктор физико-математических наук, профессор И. Д. Шкредов

Официальные оппоненты: доктор физико-математических наук, А. В. Устинов кандидат физико-математических наук, И. Д. Кан

Ведущая организация: Московский государственный университет имени М.В. Ломоносова на заседании

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

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

Автореферат разослан “

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

И.М. Виноградов, Д. Пойя, Э.Ландау, А. Хилдебранд, А. Гранвиль, К. Саундарараджан и многие другие.

Изучение вопроса о поведении чисел Фробениуса в среднем началось в 1994 году со статьи Д. Дейвисона1, в которой им были сформулированы две гипотезы, утверждающие, что число Фробениуса от “случайного” набора (a, b, c) имеет порядок abc. Чуть позже В.И. Арнольд2 предположил, что верны даже более сильные утверждения, а именно, что при всех n 2 распределение чисел Фробениуса от переменных a1,..., an определяется плотностью, пропорциональной n1 a1 ·... · an.

Для случая трех переменных гипотезы Д. Дейвисона и В.И. Арнольда в более сильной форме были доказаны А.В. Устиновым3 в 2009 году. В той же работе было высказано предположение, что при усреднении по всем трем аргументам может быть получен еще более точный результат. В настоящей диссертации доказывается эта гипотеза А.В. Устинова. Отметим, что поведение чисел Фробениуса от произвольного числа параметров было исследовано в работах Й. Марклофа4 и А. Стромбергссона5.

Первые результаты о среднем количестве шагов Davison J. L. On the linear diophantine problem of Frobenius, J.Number Theory.,48:3 (1994),353-363.

Арнольд В. И. Задачи Арнольда, Фазис, М., 2000.; Арнольд В. И.

Экспериментальное наблюдение математических фактов, МЦНМО, М., 2006.

Устинов А. В. Решение задачи Арнольда о слабой асимптотике для чисел Фробениуса с тремя аргументами, Матем.сб., 200:4 (2009),131-160.

Marklof J. The asymptotic distribution of Frobenius numbers, Invent.Math. 181 (2010), 179-207.

Strombergsson A. On the limit distribution of Frobenius numbers, Acta Arith. 152 No. 1 (2012), 81-107.

в стандартном алгоритме Евклида были получены Г. Хейльбронном в 1968 году. В последствии целый ряд авторов последовательно уточняли результат Хейльбронна (формулировки могут быть найдены, например, в статье7 ).

Другим направлением исследований стало получение аналогичных результатов для модифицированных алгоритмов Евклида (см. работы А.В. Устинова8 и Е.Н. Жабицкой9 ).

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

Первые нетривиальные оценки сумм характеров Дирихле были независимо получены и опубликованы Д. Пойя10 и И.М. Виноградовым11 в 1918 году (результат получил название “неравенство Пойя-Виноградова”). Существенное усиление этого неравенства было найдено лишь в году А. Гранвилем и К. Саундарараджаном12. Позднее, данный результат был улучшен Л. Голдмакером13. В этой Heilbronn H. On the average length of a class of nite continued fractions, Abhandlungen aus Zahlentheorie und Analysis, Berlin, VEB, 1968, 89–96.

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

Устинов А. В. О среднем числе шагов в алгоритме Евклида с выбором минимального по модулю остатка, Матем. заметки, 85:1(2009), 153-156.;

Устинов А. В. О среднем числе шагов в алгоритме Евклида с неполными нечетными частными, Матем. заметки, 88:4(2010), 594-604.

Жабицкая Е. Н. Средняя длина приведенной регулярной непрерывной дроби, Матем.сб., 200:8 (2009),79-110.; Жабицкая Е. Н.

Среднее значение сумм неполных частных непрерывной дроби, Матем.заметки, 89:3 (2011), 472-476.

Polya G. Uber die Verteilung der quadratischen Reste und Nichreste, Nachrichten Knigl. Ges. Wiss. Gttingen (1918), pp. 21-29.

Виноградов И. М. On the distribution of power residues and nonresidues, J. Phys. Math. Soc. Perm. Univ. 1 (1918),pp. 94-98; Selected works, Springer Berlin,1985,pp. 53-56.

Granville A. and Soundararajan K. Large character sums: pretentious characters and the Plya–Vinogradov theorem, Jour. AMS Vol. 20, Number 2 (2007), 357-384.

Goldmakher L. Multiplicative mimicry and improvements of the Plya- o Vinogradov inequality by Goldmakher Leo I., Ph.D., UNIVERSITY OF MICHIGAN, 2009, 109 pages; 3382190, preprint is available in arXiv:0911.5547v2.

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

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

• найдена асимптотическая формула для среднего значения чисел Фробениуса с тремя аргументами при усреднении по трем параметрам (теорема 4);

• получены новые остаточные члены в асимптотических формулах для первых моментов числа шагов в различных алгоритмах Евклида (теоремы 5 и 6);

• получен новый численный вариант неравенства ПойяВиноградова (теорема 8).

Методы исследования В работе используются методы разработанные А.В. Устиновым, методы теории цепных дробей, идеи из элементарного доказательства А.Сельберга асимптотического Pomerance C. Remarks on the Plya–Vinogradov inequality, Integers (Proceedings of the Integers Conference, October 2009), 11A (2011), Article 19, 11pp.

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

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

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

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

Н. Г. Мощевитина;

• семинар “Арифметика и геометрия” под руководством д.ф.–м.н. Н. Г. Мощевитина, к.ф.–м.н. О. Н. Германа и к.ф.–м.н. И. П. Рочева;

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

И. П. Рочева;

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

• международная конференция “27th Journees Arithmetiques” Вильнюс, Литва, 27.06.2011-01.07.2011;

• международная конференция “Диофантовы приближения.

Современное состояние и приложения.” Минск, Беларусь, 03.07.2011.-09.07.2011;

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

Публикации Результаты диссертации опубликованы в трех работах, список которых приведен к конце автореферата.

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

Краткое содержание работы Содержание главы 1.

В первой главе доказывается асимптотическая формула для среднего значения чисел Фробениуса с тремя аргументами при усреднении по всем трем параметрам (теорема 4).

Определение 1. Числом Фробениуса g(a1,..., an ) натуральных чисел a1,..., an, взаимно простых в совокупности, называется наибольшее целое k, не представимое в виде суммы Во многих задачах оказывается удобнее рассматривать функцию равную наибольшему целому k, не представимому в виде суммы (1), но уже с натуральными коэффициентами x1,..., xn.

Приведем краткий обзор предшествующих результатов.

Пусть N > 0, x1 > 0, x2 > 0, x3 > 0 действительные числа, a -натуральное. Тогда обозначим за Ma (x1, x2 ), SN (x1, x2, x3 ) следующие области Заметим, что |SN (x1, x2, x3 )| сформулировал две гипотезы.

Гипотеза 2. Существует конечный предел Эти гипотезы, даже в более сильной форме, были доказаны А.В. Устиновым в работе16. Точнее, в статье16 было доказано, что функция f (a, b, c) в среднем ведет себя как abc.

Теорема 1. (А.В. Устинов) Для любого > 0 справедливо где Теорема 2. (А.В. Устинов) Для любого > 0 справедлива асимптотическая формула Davison J. L. On the linear diophantine problem of Frobenius, J.Number Theory.,48:3 (1994),353-363.

Устинов А. В. Решение задачи Арнольда о слабой асимптотике для чисел Фробениуса с тремя аргументами, Матем.сб., 200:4(2009), 131-160.

Отметим, что теорема 2 является прямым следствием применения теоремы 1. Также используя теорему 1, А. Стромбергссон17 уточнил результаты Устинова.

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

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

Замечание 1. Отметим, что непосредственное применение теоремы 1 позволяет получить лишь следующий результат частное сообщение А.Стромбергссона, переданное А.В. Устинову.

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

Следствие 1. Для любого > 0 справедлива оценка Доказательство теоремы 4 использует идеи из работ А.В.

Устинова18,16 и работы Е.Н. Жабицкой19. Также применяются классические оценки тригонометрических сумм.

Содержание главы 2.

Во второй главе рассматриваются первые моменты числа шагов в разных алгоритмах Евклида, для них получены асимптотические формулы с новыми остаточными членами (теоремы 5 и 6).

Существует много модификаций алгоритма Евклида, приводящие к представлению рационального числа в виде различных непрерывных дробей. Рассмотрим произвольное рациональное число из отрезка [0, 1]. Классическому алгоритму Евклида соответствует разложение числа в стандартную цепную дробь длины s = s(a/b), в которой a1,...,as натуральные и as 2 при s 1. Алгоритму Евклида с делением по избытку соответствует Устинов А. В. Асимптотическое поведение первого и второго моментов для числа шагов в алгоритме Евклида. Изв. РАН.

Сер.матем.,72:5(2008), 189-224.

Жабицкая Е. Н. Среднее значение сумм неполных частных непрерывной дроби. Матем.заметки, 89:3 (2011), 472-476.

разложение числа в приведенную регулярную непрерывную дробь длины l = l(a/b), в которой b1,...,bl натуральные и bi 2 при i 1. Алгоритму Евклида с выбором минимального по модулю остатка соответствует разложение в дробь длины m = m(a/b), где t0 целое, t1,..., tm натуральные, Алгоритму Евклида с нечетными неполными частными соответствует разложение в дробь длины h = h(a/b), где a0 нечетное целое, a1,..., ah нечетные натуральные, Так же нам понадобятся статистики Гаусса-Кузьмина, которые для фиксированного x [0, 1] и рационального r = [0; a1,..., as ] задаются равенством В работе18 А.В.Устинов исследовал среднее значение величины s(c/d). Для E + (R) была получена асимптотическая формула В книге20 А.В.Устинова эта оценка уточняется до + (R) = O(R1 log4 R). В работе21 Е.Н.Жабицкой исследовалось среднее значение величины l(a/b). Для E (R) была доказана асимптотическая формула Основным результатом второй главы являются следующие две теоремы.

Устинов А. В. Приложения сумм Клостермана в арифметике и геометрии, Lambert Academic Publishing, 2011.

Жабицкая Е. Н. Средняя длина приведенной регулярной непрерывной дроби, Матем. сб., 200:8(2009),79-110.

Теорема 5. Для остаточного члена в асимптотической формуле (8) выполнено Теорема 6. Для остаточного члена в асимптотической формуле () выполнено Таким образом, нами получены асимптотические формулы с лучшими понижениями в остаточных членах. Следующая лемма уточняет лемму 3 из работы18.

Лемма 1. Пусть = p = [a0 ; a1,..., as ] рациональное число, = 0, (p, q) = 1;, R1, R2 действительные числа R1 R2, тогда