Средние значения чисел Фробениуса, длин алгоритмов Евклида и характеров Дирихле тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

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

На правах рукописи УДК 511.335+511.336

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

Средние значения чисел Фробениуса, длин алгоритмов Евклида и характеров Дирихле.

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

7 НОЯ 2013

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

Москва - 2013

005537365

005537365

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

Научный руководитель:

доктор физико-математических наук, профессор Шкредов Илья Дмитриевич, ведущий научный сотрудник отдела алгебры и теории чисел ФГВУН Математический институт имени В.А. Стеклова РАН.

Официальные оппоненты:

доктор физико-математических наук Устинов Алексей Владимирович, заведующий отделом теоретической и прикладной математики Хабаровского отделения ФГВУН Института прикладной математики Дальневосточного отделения РАН; 1

кандидат физико-математических наук Кап Игорь Давидович, доцент кафедры 311 - Математическое моделирование факультета «Системы управления, информатика и электроэнергетика» ФГБОУ ВПО «Московский авиационный институт ( национальный исследовательский университет)».

Ведущая организация: Механико-математический факультет ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова».

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

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

Автореферат разослан " октября 2013 г.

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

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

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

A. Гранвиль, К. Саундарараджан и многие другие. Изучение вопроса о поведении чисел Фробениуса в среднем

началось в 1994 году со статьи Д. Дейвисона1, в которой им были сформулированы две гипотезы, утверждающие, что число Фробениуса от ''случайного" набора (а,Ь,с) имеет порядок у/abc. Чуть позже В.И. Арнольд2 предположил, что верны даже более сильные утверждения, а именно, что при всех п ^ 2 распределение чисел Фробениуса от переменных аг,..., а„ определяется плотностью, пропорциональной • ... • ап.

Для случая трех переменных гипотезы Д. Дейвисона и

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

Первые результаты о среднем количестве шагов

1 Davison J. L. On the linear diophantine problem of Frobenius, J.Number Theory.,48:3 (1994),353-363.

2 Арнольд В. И. Задачи Арнольда, Фазис, М., 2000.; Арнольд В. И. Экспериментальное наблюдение математических фактов, МЦНМО, М., 2006.

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

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

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

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

Первые нетривиальные оценки сумм характеров Дирихле были независимо получены и опубликованы Д. Пойя10 и И.М. Виноградовым11 в 1918 год}' (результат получил название "неравенство Пойя-Виноградова"). Существенное усиление этого неравенства было найдено лишь в 2007 году А. Гранвилем и К. Саундарараджаном12. Позднее, данный результат был улучшен Л. Голдмакером13. В этой

6 Heilbronn Н. On the average length of a class of finite continued fractions, Abhandlungen aus Zahlentheorie und Analysis, Berlin, VEB, 1968, 89-96.

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

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

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

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

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

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

13 goldmakher L. Multiplicative mimicry and improvements of the Polya-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).

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

В работе используются методы разработанные A.B. Устиновым, методы теории цепных дробей, идеи из элементарного доказательства А.Сельберга асимптотического

14 Pomerance С. Remarks on the Pölya-Vinogradov inequality, Integers (Proceedings of the Integers Conference. October 2009), IIA (2011), Article 19 11pp.

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

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

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

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

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

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

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

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

» "Научный семинар Хабаровского отделения Института прикладной математики ДВО РАН" под руководством чл.-корр. РАН В. А. Быковского:

в международная конференция "27th Journees Arithmétiques" Вильнюс, Литва, 27.06.2011-01.07.2011;

» международная конференция "Днофантовы приближения. Современное состояние и приложения." Минск, Беларусь, 03.07.2011.-09.07.2011;

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

Публикации

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

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

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

Краткое содержание работы

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

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

Определение 1. Числом Фробениуса д(а\,..., ап) натуральных чисел а1,...,ап, взаимно простых в совокупности, называется наибольшее целое к, не представилюе в виде суммы

Х\ах + • • • + хпап — к, где х^ ^ 0,..., хп ^ 0. (1)

Во многих задачах оказывается удобнее рассматривать функцию

/(аь ..., ап) = д(аг,..., ап) + аг -I-----Н ап (2)

равную наибольшему целому к, не представимому в виде суммы (1), но уже с натуральными коэффициентами Ж1...., хп. Приведем краткий обзор предшествующих результатов.

Пусть N > 0,х'1 > 0,хо > О.х'з > 0 —действительные числа, а -натуральное. Тогда обозначим за А1а(х1,х2), а;2,хз)

следующие области

Ма(х 1, х2) = {(Ь,с) : 1 ^ 6 ^ XIа, 1 < с ^ ж2о, (о, Ъ, с) ~ 1} ,

SN(xi,x2,xs) = {(аД с) : (аД с) = 1, 1 < а < xiN, 1 < b < х2Лг, 1 < с < x3iV, }.

Заметам, что \Sk(xi,X2,X3)\ х Xlx2xzNz. Д. Дейвисон d сформулировал две гипотезы.

Гипотеза 1. Имеем

1 у- Да А с) <сс

Гипотеза 2. Существует конечный предел

1 f(a,b,c)

Ä> ]5дг(1,1,1)1 (aAc)^(lil>i) ^ '

Эти гипотезы, даже в более сильной форме, были доказаны A.B. Устиновым в работе16. Точнее, в статье16 было доказано, что функция /(а, Ь, с) в среднем ведет себя как §\fabc.

Теорема 1. (A.B. Устинов) Для любого е > 0 справедливо

1

(f{a,b,c) - ^Väbcj = Oe(Re(a-,xi,®2)),

Л/f _ (П-Ч "Trv^ ^

a3/2|Ma(xbx2)l t , fr*. ,

где

/ 3/2 , 3/2 \

RM xu xa) = ( a'1^ + x2) + + ) ^

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

1 V lM = 8 + .

|М»(М)! (6iC)^(U) V^-c п \ J

15 Davison J. L. On the linear diophantine problem of Frobenius, J.Number •

Theory.,48:3 (1994),353-363.

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

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

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

1 у^ /(аЛ с) _

¡^(жх.жг.жз)! . , . f-f , x/äbc

(a,b,c)&SN{xi,x2,x-3) 8 / i i \

Основным результатом первой главы является следующая теорема.

Теорема 4. Для любого е > 0 выполнено

, ь ^ , (/(°'С) - =

(a,b,c)eS/\-(xi,X2,Z3)

= Oc{N~1'2+eTe{xi,x2,x3)),

где

TE{X„X2, х3) = х\+Щ + + х

х2 Х1

Это утверждение было сформулировано A.B. Устиновым в работе10 в виде гипотезы.

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

«n/aiо /-si Е (f(a,b,c) --Väbc) =

N3/2\SN(XUX2,X3)\ \ 7Г J

= I ).

17частное сообщение А.Строыбергссона, переданное A.B. Устинову.

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

Следствие 1. Для любого е > 0 справедлива оценка

_1_ у^ /(а, Ь, с) =

\SN(xi,X2,x-i)\ f-f Väbc

= + {N-^+ETE{xux2,xz){xxx2xz)-^j .

Доказательство теоремы 4 использует идеи из работ A.B. Устинова18'16 и работы E.H. Жабицкой19. Также применяются классические оценки тригонометрических сумм.

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

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

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

£ = Г0;а1...,<*,] =-----(3)

Ь ' ах+ 1

длины 5 = в(а/Ь), в которой аь ... ,а, — натуральные и а3 > 2 при б ^ 1. Алгоритму Евклида с делением по избытку соответствует

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

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

разложение числа в приведенную регулярную непрерывную дробь

1

т,

(4)

длины I = 1{а/Ь), в которой Ьу, ... ,6; -- натуральные и Ь{ ^ 2 при Алгоритму Евклида с выбором минимального по модулю остатка

1"

а — bq + ег, е — ±1, q ~ ^ соответствует разложение в дробь

, b ^ Ь + 1' _2 < Г 2

= ¿0 +

£2

(5)

длины т = т(а/Ь), где í0 целое, £ i, ..., tm — натуральные,

Sk = ±1, th ^ 2 (fc = 1,... ,т), ífc + ^fc+i > 2 {к ~l,...,m- 1), = — 1 ПРИ m И ¿m = 2.

Алгоритму Евклида с нечетными неполными частными

а

а = bq + ег, е = ±1, q = 2 соответствует разложение в дробь

/Г00

L26.

+ 1, -Ь <г

+

(6)

а2 + .

' • Н--

ah

длины h = h(a/b), где а0 -- нечетное целое, a ..., аи —нечетные натуральные,

efc = ±1, afe+£fe+i>l (/г ~ 1,... ,h - .1), £h — 1 при h ^ 1 и ан — 1.

Так же нам понадобятся статистики Гаусса-Кузьмина, которые для фиксированного х б [0,1] и рационального г = [0; ах,..., а.,| задаются равенством

.,(*>(г) = :1< «(г), [0; щ, ...,«,]< х}.

В работе18 А.В.Устинов исследовал среднее значение

величины s(c/d). Для E+(R) была получена асимптотиче формула

, log2 / o^í^l

:кая

< л> = тсГ д + ?§) I3108 2+47 -2 сМ - 3Г

-| + «+(Л), (8)

и;+(Д) = 0(Л-11о§5Д). (9)

В книге20 А.В.Устинова эта оценка уточняется до о;+(Я) = 0(Я~1 к^4 Я). В работе21 Е.Н.Ждбицкой исследовалось среднее значение

величины 1(а/Ь). Для Е~{Я) была доказана асимптотическая формула

1 , 1 (п 3 С'(2)'

<*> - адlog2 д + с(2) V27" а - сШ1о§

+02)V7 ~ 7 /_2j+ 2С2(2)

(R), где W" (Я) - 0(RTl log5 R).

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

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

21 Жавицкая Е. Н. Средняя длина приведенной регулярной

непрерывной дроби, Матем. сб., 200:8(2009),79-110.

Теорема 5. Для остаточного ■члена в асимптотической формуле (8) выполнено

lü+{R) = OCR"1 log3 Д). (И)

Теорема б. Для остаточного члена в асимптотической формуле () выполнено

(R) = 0(Я-1 log3 R). (12)

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

Лемма 1. Пусть а = 2 = [а0; ai,..., ая] рациональное число, а ф 0, {р, q) = 1; 0, Ry, R-¿ действительные числа Rx < R-¿, тогда

Ri<x<R3 1 J

где si Г2 J = ai -сумма неполных частных числа | и р(х) =

Для доказательства, теоремы 5 достаточно заменить в статье13 лемму 3 на новую лемму 1 и повторить вывод формулы (8). Использование леммы 1 позволяет выделить главные члены в асимптотических формулах некоторых сумм, входящих в остаток. Для доказательства теоремы б достаточно аналогичным образом подставить в рассуждения из работы21 лемму 1, после чего необходимо нетривиально оценить сумму специального вида. Этому и посвящена теорема 7, которая, возможно, имеет самостоятельный интерес.

Теорема 7. Для суммы

т) - (§). л т - ^ Е £ (I) f

выполнено

T(R) - О (/i log2 Я).

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

Замечание 2, В статье19 доказано, что

Таким образом из теоремы 6 следует новая оценка остаточного члена в асимптотической формуле для среднего значения суммы неполных частных классических цепных дробей

uJSl{R) = 0{R-l\ogzR).

Замечание 3. Аналогично (8) доказывается асимптотическая формула для статистик Гаусса-Кузьмина (см. работу20)

= (log(l + X) log R + Сх(х)) + UM(R), Cv2)

ujW(R) = 0{R~l log1 R).

Определение константы Ci(x) см. в работе20. Проделывая рассуждения, аналогичные доказательству теоремы 5, получаем новую оценку остаточного члена

u{x){R) - СИЯ'1 log3Я).

Замечание 4. В статье23 для среднего числа шагов в алгоритме Евклида с выбором минимального по модулю остатка

22 Постников А. Г., Pomahobob Н. П. Упрощение элементарного доказательства А.Сельберга асимптотического закона распределения простых чисел, Успехи мат. наук, т.Ю вып. 4(66), 75-87, 1955.

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

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

tOmin(R) = OÍR'1 fog4 R).

Используя Замечание 3 несложно получить новую оценку остаточного члена

^min(R) — OÍR'1 log3 R).

Замечание 5. В cmambe2i для среднего числа шагов в алгоритме Евклида с нечетными неполными частными была доказана асимптотическая формула с остаточным членом равным

oJodd(R) = OÍR-1 log* R).

Используя Замечание 3 несложно получить новг/ю оценку остаточного члена

ujodd(R) = 0(R~1log3R).

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

В третьей главе доказывается новый численный вариант неравенства Пойя-Виноградова (теорема 8).

Пусть х (mod q) -примитивный характер Дирихле. Положим

S-. = max

N

х(п)

п=М

Tv = max

* N

N

а=О

Характер называется четным или нечетным, если 1) — 1 или = — соответственно. В случае четного характера

выполнено

5Х = 2 Тх. (13)

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

В 1918 году Д. Пойя25 и И.М. Виноградов26 независимо доказали, что для любого неглавного характера Дирихле имеет место неравенство

< Cy/qlogq, (14)

где с некая абсолютная константа. В 2007 году А. Гранвиль и К. Саундарараджан27 доказали, что для любого примитивного характера Дирихле х (mod я) нечетной степени д имеет место оценка

Тх < ^q{\ogq)l-^+o{l\ где Sg = l-^ sin ^, q оо.

Позднее этот результат был улучшен JI. Голдмакером28, а именно, он доказал, что

Тх « V5(log qy-S°+o{1\

а также

Тх « ^(loglogg)1-5»^1',

в предположении справедливости обобщенной гипотезы Римана. Ранее, в предположении справедливости обобщенной гипотезы Римана, Г. Монтгомери и Р. Вон29 доказали, что

Sx ^ \/5 log log д.

25 pölya G. Über die Verteilung der quadratischen Reste und Nichreste. Nachrichten Königl. Ges. Wiss. Göttingen (1918),pp. 21-29.

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

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

28 Goldmakher L. Multiplicative mimicry and improvements of the Pölya-Vinogradov inequality by Goldmakher Leo I., Ph.D., Universityh of Michigan, 2009, 109 pages; 3382190, preprint is available in arXiv:0911.5547v2.

29 Montgomery H. L. and Vaughan R. C. Exponential sums with multiplicative coefficients, Invent. Math. 43 (1977), 69-82.

В общем случае эта оценка неулучшаема, так как Р. Палей30 установил существование бесконечной последовательности квадратичных характеров Хп (mod Чп) для которых

SXn » л/^ log log f]n.

Этот результат был обобщен JT. Годмакером и И. Ламзори , которые доказали, что для любого четного g существуют достаточно большие q и примитивные характеры Дирихле х (mod q) степени g такие, что

Sx » y/q log log q.

Также JI. Годмакер и Й. Ламзори32 показали, что для любого нечетного g существуют достаточно большие q и примитивные характеры Дирихле х (mod q) степени g такие, что

»e ^(loglog?)1-^.

В этой проблематике важной задачей является также и получение наиболее точной формы неравенства (14). Все результаты в данном вопросе можно разделить на два типа. К первому типу (асимптотические результаты) относятся утверждения, в которых не вычислена константа в остаточном члене. Ко второму типу (численные результаты) относятся результаты, в которых для всех констант выписаны явные оценки. Естественно, утверждения первого вида имеют лучшую константу в главном члене, чем результаты второго вида. Асимптотические результаты Э. Ландау33 доказал, что

30 Paley R. Е- А. С. A theorem on characters, J.London Math. Soc. 7 (1932), 28-32.

. 31 Goldmakher L. and Lamzouri Y. Large even order character sums, to appear in Proc. Amer. Math. Soc.

32 Goi,nn,\K:;::a L. and Lamzouri Y. Lower bounds on odd order character sums, published in IMRN 2012 (21), 5006-5013.

33 Landau E. Abschätzungen von Charaktersummen, Einheiten und klassen-zalilen. Nachrichten Königl. Ges. Wiss. Göttingen (1918),pp. 79-97.

j Vq^ogq, если x(~l) = 1

И

< ( — + о(1)) \Z9log?, если Х(-1) = -1. А. Хилдебранд34 получил неравенство

Тх < (3^2 + °(1)) если х(-1) = 1

и

Тх < Г— + о(1) у^ёЗ. если Х(-1) = -1-

Позднее А. Хилдебранд35 усилил свой результат для случая четного характера и показал, что выполняется оценка

Тх < (-^д + о( 1)^ у/д^д, если х(-1) = 1.

где

7, если q свободно от кубов; с = <i т

иначе,

:=(}' 6СЛ I I- ИНЗ

А. Гранвиль и К. Саундарараджан27 доказали два новых неравенства

(^ълД + ^logq' если = 1

тх < + °(1)) л/51о89. если х(-1) =

с той же, что и у Хилдебранда, константой с. На сегодняшний день это наилучший из известных результатов. Численные результаты

Приведем ряд результатов второго типа. Кью36 доказал, что

< Ау/Ч-1о§ Я + °-38\/9 + 0.608-^1 + 0.116^.

7Г х/д

34 Hildebrand A. On the constant in the P6lya-Vinogradov inequality, Canad. Math. Bull. 31 (1988), 347-352.

35 Hildebrand A. Large values of character sums, J. Number Theory 29 (1988), 271-296.

36 Qiu Z. M. An inequality of Vinogradov for character (Chinese), J. Shan-

dong Univ., Nat. Sci. Ed. 26 (1991), 125-128.

А. Сималаридес37 получил следующие оценки

если х(-1) = 1

И 1 1

Тх ^ -y/q\ogq+ yfq+ - если 1) = —17Т £

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

Г. Бахман и JI. Рачаконда39 улучшили этот результат, доказав, что

для любого неглавного характера Дирихле х (mod q). К. Поме-ранц40 установил справедливость неравенств

2 4

Sx ^ ^y/qlogq + ^loglogq + {q) если х(-1) = 1 (15)

и

sx < + --Jq\oglogq + ф^ч) если х(-1) =

¿п ж

(16)

37 Simalarides A. D. An elementary proof of Pôlya-Vinogradov's inequality. Period. Math.Hungar. 38 (1999) 99-101.; Simalarides A. D. An elementary proof of Polya-Vinogradov's inequality, 2. Period. Math.Hungar. 40 (2000) 7175.

38 Dobrowolski E. and Williams K. S. An upper bound for the suin J2nta+\ /(") for a certain class of functions J, Proc. Amer. Math. Soc. 114(1992),° 29-35.

33 Bachman G. and Rachakonda L. On a, problem of Dobrowolski and Williams and the Pôlya-Vinogradov inequality, Ramanujan J. 5 (2001), 65-71.

40 pomerance C. Remarks on the Pôlya-Vinogradov inequality. Integers (Proceedings of the Integers Conference, October 2009), 11A (2011), Article 19, 11pp.

где

4 / з log(4/7r) 7Г2 Л 1

X 3

Ыя) = -\/5(1о§(4/^) + 7 + log 2 + 1 + -+

log(4/ir) 7Г

log д ^ 12i2log5) + ^

и n = [2^/glog ij], m = [(4/тг) ^/д log д] и q достаточно велико (см. работу40). Отметим, что неравенства (15) и (16) также остаются верными, если положить 4>i{q) = §л/?> =

y/q. На сегодняшний день это наилучший численный вариант неравенства Пойя-Виноградова. Основным результатом третьей главы является следующая теорема, усиливающая результат К. Померанца.

Теорема 8. Пусть х (mod q) -примитивный характер.

1. Если х(—1) = 1, то

Sx < +AxW + 'T + bgqo + ^te),

IT' 7Г-

2. Если х(—1) = —1. то

1 1 / 2 С \

Sx < TT^ogq + -y/q ( 1+ 7 + log — + Мя),

27Г 7Г \ 7Г /

где 7 -константа Эйлера, Co — 4vr5/2 + 5 u

24 8 v/5

Со ттехр^)-!'

Таким образом, нам удалось улучшить второе слагаемое в обеих оценках (15) и (16). Несложные вычисления показывают, что при q > ехр(С0/4) и 1.38 • 108 обе оценки в теореме 8 лучше, чем (15) и (16), соответственно.

Благодарности.

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

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

[1] фроленков д. А. Асимптотическое поведение первого момента для числа шагов в алгоритме Евклида по избытку и недостатку. Матем. сб., 203:2 (2012), 143 -160.

[2] Фроленков Д. А. Среднее значение чисел Фробениуса с тремя аргументами. Изв. РАН. Сер. матем., 76:4 (2012), 125 -184,

[3] фроленков Д. A. A numerically explicit version of the Polya -Vinogradov inequality. Moscow Journal of Combinatorics and Number Theory 2011, vol.1, iss.3, p. 26 -42.

Подписано в печать 19.09.2013 г. Печать трафаретная Усл. печ. л. -1,25 Заказ № 2605 Тираж: 100 экз. Типография «БапрпШ®» 119334, Москва, Ленинский пр-т. Д.37А (495) 626-42-43 www.sanprint.ru/www.sanpromo.ru

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

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

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

л / «плЯ ~Ч / ! / Л 1

ич^иисю!«

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

Средние значения чисел Фробениуса, длин алгоритмов Евклида и характеров Дирихле.

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

Диссертация

на соискание ученой степени кандидата физико-математических наук

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

Москва 2013

Содержание

Введение 3

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

0.2. Обозначения 5

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

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

1.1. Вспомогательные утверждения и обозначения 16

1.2. О функции Редсета 21

1.3. Выделение плотности 22

1.4. Разделение задачи на отдельные случаи 26

1.5. Вычисление сумм первого типа 32

1.6. Вычисление сумм второго типа 57

1.7. Вычисление сумм третьего типа 65

1.8. Доказательство теоремы 4 70

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

шагов в алгоритме Евклида по избытку и недостатку 77

2.1. О сумме дробных долей 77

2.2. Вспомогательные утверждения 78

2.3. Доказательство теоремы 5 81

2.4. Доказательство теоремы 6 84

2.5. Доказательство теоремы 7 91

Глава 3. Новый численный вариант неравенства Пойя -Виноградова 94

3.1. Метод Быковского 94

3.2. Доказательство теоремы 8 98

Список литературы 102

ь

Введение

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

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

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

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

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

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

Первые нетривиальные оценки сумм характеров Дирихле были независимо получены и опубликованы Д. Пойя и И.М. Виноградовым в 1918 г (результат получил название "неравенство Пойя-Виноградова"). Существенное усиление этого неравенства было получено лишь в 2007 г. А. Гранвилем и К. Саундарараджаном [4]. Позднее, данный результат был улучшен JI. Голдмакером [5]. В этой проблематике важной задачей является также получение наиболее точной константы в неравенстве Пойя-Виноградова, так как известно, что эта константа связана с оценкой величины минимального квадратичного невычета. На сегодняшний момент, наилучшее значение константы принадлежит А. Гранвилю и К.Саундарараджану [4]. Однако в некоторых задачах важнее оказывается не информация об этой константе, а использование численно точной формы неравенства Пойя-Виноградова. В настоящей диссертации мы доказываем новый вариант численно точного неравенства Пойя-Виноградова, улучшая предыдущий результат К. Померанца [20].

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

Основные положения диссертации, выносимые на защиту

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

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

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

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

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

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

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

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

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

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

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

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

ч л .-корр. РАН В. А. Быковского;

• международная конференция "27th Journees Arithmétiques" Вильнюс, Литва, 27.06.2011-01.07.2011

• международная конференция "Диофантовы приближения. Современное состояние и приложения." Минск, Беларусь, 03.07.2011.-09.07.2011.

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

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

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

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

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

-расстояние до ближайшего целого, также нам понадобится функция Р{х) = | - {ж}.

• для обозначения наибольшего общего делителя будем использовать круглые скобки (ai,..., ап) = НОД(а1,..., ап)

• Знак звездочки в суммах вида

0.2. Обозначения

а

х=1

a

х

означает, что суммирование ведется по числам, удовлетворяющим условию (а, ж) = 1.

• В суммах суммирование ведется по делителям числа п. В суммах

d\n

£. £

n^R n^R

d\n d\n

суммирование ведется по п, удовлетворяющим условию п — О (mod d),n ф 0 (mod d) соответственно.

• Запись г = [ао; ai.. •, as] означает разложение рационального числа в стандартную цепную дробь

[а0; ai..., ав] = а0 Л--—

ах+ 1

as

длины s = s(r), в которой ао, ■ ■ ■ ,as — натуральные и as ^ 2 при s ^ 1.

• Через Si (г) будем обозначать сумму неполных частных числа г

si(r) = J2 üi'

• /i(n) -функция Мебиуса:

{1, если п = 1;

(—l)fc, если п = pi • • -pk, где Pi различные простые; 0, иначе.

• <р(п) -функция Эйлера:

a=l d\n

• crfc(n) = -сумма fc-ых степеней делителей числа п, в частности,

d\n

т{п) = сг0(п)

• А(п) -функция Мангольдта:

A(n) = í если п ~ Pk'i к ' ^ 0, иначе.

• 6q(á) -характеристическая функция делимости на натуральное число

q

Sq(a) = -Техр( 2кг™) = { 6СЛИ a = ° (m°d (0.1)

94 ' \ q J 10> иначе. v '

• Если А — некоторое утверждение, то [Л] означает 1, если А истинно, и 0 в противном случае.

• е{х) = ехр(27ггж)

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

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

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

Определение 1. Числом Фробениуса g(ai,..., ап) натуральных чисел aii • • • 5 fln; взаимно простых в совокупности, называется наибольшее целое к, не представимое в виде суммы

xiai -----Ь хпап = к, где Xi ^ 0,..., хп ^ 0. (0.2)

Во многих задачах оказывается удобнее рассматривать функцию

/(аь ..., ап) = д{аъ ..., ап) + а1 Ч-----\-ап (0.3)

равную наибольшему целому к, не представимому в виде суммы (0.2), но уже с натуральными коэффициентами Наиболее обширный

обзор результатов и задач, связанных с числом Фробениуса, приведен в книге Д. Рамиреса Алфонзина [22].

Пусть N > 0, xi > 0, X2 > 0, хз > 0 —действительные числа, а -натуральное. Тогда обозначим за Ма(хi, х2), Sn(xi, х2, хз) следующие области

Ма{х 1, х2) = {(Ь, с) : 1 < Ь ^ xia, 1 < с ^ х2а, (а, Ь, с) = 1} ,

Sn(x 1, х2, ж3) = {(а, 6, с) : 1 < а ^ X\N, 1 < Ъ ^ x2N, 1 ^ с ^ x$N, (а, 6, с) = 1}.

Заметим, что |£лг(;с1,Ж2>жз)| ^ X1X2X3N3. Д. Дейвисон [2] сформулировал следующую гипотезу

Гипотеза 1. Существует конечный предел

у 1 у- /(«> Ъ, с)

Ä|SN(l,l,l)|(a^(ui) VSTc ■

Эта гипотеза, даже в более сильной форме, была доказана A.B. Устиновым в работе [36]. В статье [36] было получено, что функция /(а, Ь, с) в среднем ведет себя как -\fabc.

Теорема 1. (A.B. Устинов) Для любого £ > 0 справедливо

где

ЯДа; хих2) = (а"1'6^ + х2) + аГ1/\х\/2 + ж^Хад)-1/4 + оГх/2) а£

Теорема 2. (A.B. Устинов) Для любого е > 0 справедлива асимптотическая формула

1 v- Д«Лс) 8

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

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

I-ТГГ-=- + 0£(11£{а]х1,х2){х1х2)-1А,

\Ма{хъх2) . ^ , у/аЬс тг V /

1 ^ /(а, Ь, с) 8

Т"? 7Г \ /

Г— Уаос

Основным результатом первой главы является следующая теорема. Теорема 4. Для любого е > 0 выполнено 1

^ ^/(а, 6, с) - ^Vätej =

(а,Ь,с) eSjv (xi ,Х2 ,х3)

где

ГеСхь Х2, *3) = + +

Это утверждение было сформулировано A.B. Устиновым в работе [36] в виде гипотезы.

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

{a,b,c)£SN (х1,х2,хз)

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

Следствие 1. Для любого е > 0 справедлива оценка 1 ^ ДаДс) 8

J2 =

Vabc

(a,6,c)eSjv(x1,X2,X3)

Доказательство теоремы 4 использует идеи из работ A.B. Устинова [36], [37] и работы E.H. Жабицкой [31]. Также применяются классические оценки тригонометрических сумм.

Цастное сообщение А.Стромбергссона, переданное A.B. Устинову

0.3.2. Асимптотическое поведение среднего значения числа шагов в различных модификациях алгоритма Евклида.

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

а г , 1

- = 0; а!..., аа] =---

о <ц +

1

(0.4)

а.

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

Ь Ъх - .

1

(0.5)

длины I = 1(а/Ь), в которой &1, ... ,6г — натуральные и ^ > 2 при г > 1. Алгоритму Евклида с выбором минимального по модулю остатка

а = + ег, б = ±1, # = соответствует разложение в дробь

Ъ Ъ

+ 1' '2<Г^2

а

ъ = и +

£1

¿1 +

£2

¿2 + . £т ' +

Ью.

а = Ьд + ег, е = ±1, д = 2 соответствует разложение в дробь

а

ъ=а° +

12 Ъ\

+ 1, -Ъ<г <6

ах 4-

^2

а2 + . ен ан

(0.6)

длины т = т(а/Ъ), где ¿о ~ целое, ¿1, ..., — натуральные,

= ±1, % ^ 2 (к = 1,..., га), ^ + (А; = 1,... ,т - 1),

= —1 при т ^ 1 и ¿т = 2.

Алгоритму Евклида с нечетными неполными частными

а

(0.7)

длины h = h(a/b), где ао — нечетное целое, ai,..., а^ —нечетные натуральные,

ек = ±1, ак + £к+i^l (fc = 1,... ,h - 1), = 1 при Д ^ 1 и a^ = 1.

Так же нам понадобятся статистики Гаусса-Кузьмина, которые для фиксированного а: £ [0,1] и рационального г = [0; ах,... ,as] задаются равенством

я<*>(г) = ; j < s(r), [0; a,-,..., aj < ж}. В работе [37] А.В.Устинов исследовал среднее значение

величины s(c/d). Для E+(R) была получена асимптотическая формула

£+(iJ) = WlosK+§T(31og2+47"2c8"3)"^+w+(ñ)'

(0.9)

(R) = OÍR-1 log5 R). (0.10)

В книге [38] А.В.Устинова эта оценка уточняется до cu+(R) = 0{R~l log4 R). В работе Е.Н.Жабицкой (см. [31]) исследовалось среднее значение

(0Л1)

L JU 1 ' b^R a^b

величины l(a/b). Для E~(R) была доказана асимптотическая формула

=" Ш)1оёК+ (0Л2)

4- 1 (ъ? *v4-7 3\ 2(СЧ2))2-Г(2)С(2)\ (т

с(2) \ -37 + 1~ф) Г"--)+UJ {Rh

ÜJ- (R) = OÍR-1 log5 R). (0.13)

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

Теорема 5. Для остаточного члена в асимптотической формуле (0.9) выполнено

Lü+ (R) = OiR-1 log3 R). (0.14)

Теорема 6. Для остаточного члена в асимптотической формуле (0.12) выполнено

uj- [R) = OÍR-1 log3 R). (0.15)

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

Теорема 7. Для суммы

d^R 4 7 sv ' x^VR 4 7

выполнено

T{R) = 0(R log2 R).

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

Замечание 2. В статье [32] доказано, что

L J ' d^R c^d

Таким образом из теоремы 6 следует новая оценка остаточного члена в асимптотической формуле для среднего значения суммы неполных частных классических цепных дробей

üjSi (R) — О (Л-1 log3 R).

Замечание 3. Аналогично (0.9) доказывается асимптотическая формула для статистик Гаусса-Кузьмина (см. [38] J

[д]([д] + 1) £ £ = щ (log(l + X) logR + ОД) + ы(*>(Д),

co^(R) = 0(R~1 log4 R).

Определение константы C±(x) см. в [38]. Проделывая рассуждения, аналогичные доказательству теоремы 5, получаем новую оценку остаточного члена

сoix\R) = 0{R~1 log3 R).

Замечание 4. В [39] для среднего числа шагов в алгоритме Евклида с выбором минимального по модулю остатка была доказана асимптотическая формула с остаточным членом равным

Umin{R) = 0{R~1 log4 R). Используя Замечание 3 несложно получить новую оценку остаточного члена

Umin(R)= OÍR-1 log3 R).

Замечание 5. В [40] для среднего числа шагов в алгоритме Евклида с нечетными неполными частными была доказана асимптотическая формула с остаточным членом равным

Uodd(R) = OÍR-1 log4 R).

Используя Замечание 3 несложно получить новую оценку остаточного члена

Uodd(R) = OÍR'1 log3 R).

0.3.3. Новый численный вариант неравенства Пойя-Виноградова.

Пусть х (mod q) -примитивный характер Дирихле. Положим

Sx = max

0

N

52 X(n)

п=М

Ту = max

Л N

N

Х>(»)

а=0

Характер называется четным или нечетным, если х(—1) — 1 или х(~~1) — —1, соответственно. В случае четного характера выполнено

= 2 Тх. (0.16)

В 1918 Д. Пойя [19] и И.М. Виноградов [30] независимо доказали, что для любого неглавного характера Дирихле имеет место неравенство

Sx^c^q\ogq, (0.17)

где с некая абсолютная константа. В 2007 А. Гранвиль и К. Саундарараджан [4] доказали, что для любого примитивного характера Дирихле х (mod q) нечетной степени g имеет место оценка

Тх < y/q(\og д)1-^1), где Sg = 1 - ^ sin -, q оо.

7г g

Позднее этот результат был улучшен J1. Голдмакером [5], а именно, он доказал, что

Тх « y/qQogq)1-*'*«»,

а также

Тх « ^(loglogg)1^^1), в предположении справедливости обобщенной гипотезы Римана. Ранее,в предположении справедливости обобщенной гипотезы Римана, Г. Монтгомери и Р. Вон [15, теорема 3] доказали, что

sx < i/qloglogq.

В общем случае эта оценка неулучшаема, так как Р. Палей [17] доказал существование бесконечной последовательности квадратичных характеров Хп (mod qn) для которых

SXn » V^logloggn.

Этот результат был обобщен JI. Годмакером и Й. Ламзори [7], которые доказали, что для любого четного д существуют достаточно большие q и примитивные характеры Дирихле х (mod q) степени д такие, что

Sx » yfq log log q.

Также JI. Годмакер и Й. Ламзори [6] доказали, что для любого нечетного д существуют достаточно большие q и примитивные характеры Дирихле X (mod q) степени д такие, что

»е v^loglogs)1-^.

В этой проблематике важной задачей является также и получение наиболее точной формы неравенства (0.17). Все результаты в данной задаче можно разделить на два типа. К первому типу (асимптотические результаты) относятся результаты, в которых не вычислена константа в остаточном члене. Ко второму типу (численные результаты) относятся результаты, в которых для всех констант выписаны оценки. Естественно, результаты пер�