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

• Фроленков, Дмитрий Андреевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Фроленков, Дмитрий Андреевич

Содержание

Введение

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], в которой им были сформулированы две гипотезы (см. § 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). Все результаты в данной задаче можно разделить на два типа. К первому типу (асимптотические результаты) относятся результаты, в которых не вычислена константа в остаточном члене. Ко второму типу (численные результаты) относятся результаты, в которых для всех констант выписаны оценки. Естественно, результаты первого вида имеют лучшую константу в главном члене, чем результаты второго вида.

Асимптотические результаты Э. Ландау [13] доказал, что

Sx ^ + °(1)) если х(-1) = 1

Sx < ^ + о(1)^ y/q\ogq ,если х(-1) = -1. А. Хилдебранд [9] получил

Тх ^ + 0(1)) y/qlogq, если х("1) = 1

и

Тх ** (з1+ о(1)) если =

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

Тх ^ (^д + о(1)) ^/qlogq, если *(-1) = 1,

и

где

если q свободно от кубов; иначе,

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

/69 с \

ТХ < i——^ + o(l)J ,/q\ogq, если = 1

и

< + «(I)) V^bgg, если х(-1) = -1

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

Приведем ряд результатов второго типа. Кью [21] доказал, что sx ^ ^v^logi? + 0.38л/д + 0.608-^г + 0.116л/д. А. Сималаридес [24], [25] получил следующие оценки

Ii<^V?loge+(2 если Х(-1) = 1

и

Tx<-y/qlogq + y/q + - если х(—1) =

7Г Z

Э. Добровольский и К. Вилльямс [3] доказали, что для любого неглавного

характера Дирихле х (mod q) справедливо неравенство

Sx ^ +

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

Sx ^ + 6.5Jq

для любого неглавного характера Дирихле х (mod q). В [20] К. Померанц доказал неравенства

2 4

Sx < "о >/5 log 9 + — ^/qloglogq + iliiiq) если х(~1) = 1 i0-1^

7Г 7Г

и

Sx ^ + + если = -1, (0-19)

Z7T 7Г

где

7Г2

, , ч 4 / ^ 3 log(4/Tr)

(?) = — y/q bg 4 + 7 + 1 + - + f 1 } + 7г2 \ n log q

+ 1

12q2 log <7,

= ±V5 (log(4M + 7 + log2 +1 +1 + + + 1,

и n — [2y/q\ogq], m = [(4/7т)^/g log g] и q достаточно велико (см. [20]). Отметим, что неравенства (0.18) и (0.19) также остаются верными, если положить ipi(q) = \\fq, V^Oz) = \fq- На сегодняшний день это наилучший численный вариант неравенства Пойя-Виноградова. Основным результатом третьей главы является следующая теорема, усиливающая результат К. Померанца.

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

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

2 4

< — уД^ёЯ + —у/я (1 + 7 + ^С0) + чргк),

7Г 7Г

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

1 \ ( 2 С \

где 7 -константа Эйлера, Со = 47т5/2 + 5 и

, / ч 24 8 л/д

^(д) = 1 ++ У

-20> ^2ехр(^)

Со 7гехр(^1)-1-

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

ГЛАВА 1

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

аргументами

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

Разложим рациональное число г 6 [0,1] в стандартную цепную дробь

г = [0;аь...,ав] =-—^---(1.1)

ах+ 1

а3

длины 5 = ¿(г), в которой ах, ... ,а3 — натуральные и а8 ^ 2 при в ^ 1. Через б'! (г) будем обозначать сумму неполных частных

Si(r) = X)

a¿

Лемма 1. (см. [12]) Для любого натурального Ъ > 1 выполнено

£>(<*/&) <61og2b.

Лемма 2. (см. [45, гл 6, §3, теорема Ь]) Пусть т(п) = число

d\n

делителей натурального числа п, тогда

т(п) = о(п£)

для любого е > 0.

Следующая лемма общеизвестна (преобразование Абеля)

Лемма 3. (см. [33, гл. 2, §5],) Пусть f(x)—непрерывно-дифференцируема на [1 + [а];Ь], сп— произвольные числа,

С{х) - Сп-

а<п^х

Тогда

ь

cnf(n) = C(b)f(b) - í C(x)f'(x)dx.

а<П^Ь [a]+l

16

Лемма 4. Пусть и(х1,х2,хз) € С1 (М3 ) , с{п\,п2,пз)—произвольные числа,

С(уиу2,уз)= с(аЛс).

Тогда

52 52 52 с(а'сМа> &>с) == х3)и(х 1}х2, х3)~

XI х2 х3

-///

111

XI х3

ду1ду2ду3

1 1

+

//

1 1

д2и(у1,х2,у3)

духдуз

XI /

ди{уъх2,х 3) дуг

XI ж2

+ J У

Х2 ХЗ

Х2

■

д2и(уъу2,хз)

ду\ду2

С(уиу2,хъ)(1у1<1у2+

д2и(х1,у2,уз)

1 1

ду2дуз

С(х1,у2,уз)<1у2(1уз-

ди(хиу2,хй) ду2

С{хъу2,хз)(1у2-

я3 /

ди(х1,х2,Уз) дуз

С(хих2,Уэ,)<Луг.

ДОКАЗАТЕЛЬСТВО. Достаточно последовательно применять Лемму 3.

□

Лемма 5. (см. [34, гл. 1, §1]^ Пусть а—произвольное действительное число, целое и Р— натуральное. Тогда

Я+р

52 е(аг1)

п=<Э+1

^ пип Р,

21Н1У'

где || а || —расстояние от а до ближайшего целого.

Следствие 2. Пусть а—произвольное действительное число. Если /(х) непрерывно дифференцируема на отрезке [<5 + 1, ф+Р] и монотонна, то

я+р

52 е(ап)/(п)

п=д+1

<(|/(Р + д)| + |/(д)|)тт Р,

а

ДОКАЗАТЕЛЬСТВО. После применения леммы 3 и леммы 5, получаем

Я+р

Я+р

52 е(ап)/(п)

п=<Э+1

«1/(^ + ^)1+ I и'Ш

V <5+1

I тт ( Р,

а

Используя монотонность функции /(ж), получаем нужную оценку. □

Лемма 6. Пусть г, р —произвольные натуральные числа, а и Ъ — действительные. Тогда

(а)

а<п^Ь т т{п

(Ь)

(с)

(с!)

а<п^Ь " т ' т\п

1. п2 - а а2

а<п^6 " г1 г|п

Р

а<п^Ь 1 т т|п

ДОКАЗАТЕЛЬСТВО. Доказательство (а) можно найти в книге Н.М. Коробова [34, гл. 1, §1]. Для доказательства остальных пунктов достаточно воспользоваться леммой 3.

□

Следующая лемма так же общеизвестна (формула суммирования Эйлера-Маклорена)

Лемма 7. (см. [33],) Пусть а,Ь -действительные, /(ж) непрерывно дифференцируема на отрезке [а,Ь], тогда

ь ъ

£ /Н = [ /(х)<*с + р(Ь)/(Ь) - р(а)/(а) - [ р{х)Г{х)дх.

а<п<Ь а а

Отметим, что если /(ж) непрерывно дифференцируема лишь на отрезке [1 4- [а], [&]], то необходимо использовать следующий вариант леммы 7

М М

Е/(«)= / / Р{х)г{х)йх.

а<п^ь 1+[а] 1+[а]

Нам понадобятся следствия леммы 7.

Следствие 3. Пусть f(x) непрерывно дифференцируема на отрезке [1 + [а], [6]], и количество экстремумов функции /(ж) на этом отрезке не превосходит некой константы А, тогда

[Ъ]

£/(*) = [ 1Шх + Оа( шах/(*)).

а<п<Ъ 1+[а]

ДОКАЗАТЕЛЬСТВО. Действительно, если функция имеет конечное число экстремумов, то

М ь

[ р{х)}'{х)йх < [ Ц'(х)\с1х = 0А{тах ¡{х)).

] J а<х^Ь

1+[а] а.

Теперь утверждение непосредственно следует из леммы 7. □

Следствие 4. Справедливы следующие асимптотические формулы

(а) Для любого натурального р выполнено

_ 1

(Ь) Для любого натурального р выполнено

о

£ пР - = Т^ТГ^ + 0 (ЕР 1о§ V '

(с)

(с!)

(е)

п^Я

'25

ЕК — П 7Г 1, ^ . /1 .

п^Я

п2 + Я2 4 2

(О

^п21о§М + (б)

Е

п

Д-п

Я2 + п2

(Ь)

4 7

0)

= ( * - 1 - ^ Я5 + О (Л* 108 Д)

пЛ + п) V10 20 5 У

(к)

(1)

(т)

(п)

(0)

(Р)

(г)

(8)

„ Я2 + п2 \4 12 2

Е»ь«(1+й) = Т+0(Л)'

п^Я

п<й

4 ' 4 '

^=(3-41оЕ2)Д + 0(1),

пЦЕ 4 ;

Ушоё 5 +п\ = о (н2),

V к + п =о( 1).

п^Н

ДОКАЗАТЕЛЬСТВО. Все пункты доказываются непосредственным применением следствия 3.

□

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

В работе [23] Редеет построил следующий метод для подсчета функции /(а,&, с). Пусть а,Ь,с —натуральные числа и (а, Ь) = 1, (а, с) = 1, тогда существует натуральное число I

. с = Ы (тос! а), 1 < / ^ а, (I, а) = 1.

Разложим число у в приведенную регулярную цепную дробь (см. например [18, гл. 1].)

7 — (йъ а,2 ..., ат) = ах--—- (1.2)

( а2 — . 1

&ТП

и определим последовательности {е.,} и при — 1 ^ ^ ^ т следующим образом

= 0, 1 = 1, = 0, д0 = 1

= aj+lsj ~ Sj+l, = ~ Чз-ъ 0 ^ ] < га - 1.

Легко доказать (см [23] или [36]) что, для последовательностей {д^} выполнено

О^тп ^ ¿>га—1 во

= — <-< • • • < — <--- оо.

Ятп Ятп-1 Яо

Определим функцию Рёдсета Р1,а{ос) следующим образом

Р1,а(а) = вп-1 + аЯтг ~ тга{5п, — ^ ос < ,

Яп Чп-\

тогда функция /(а, 6, с), определенная в (0.3), находится по формуле

/(аДс) = &аа(£). (1.3)

Так же нам понадобится следующее утверждение о последовательностях {«,}, Ы (см [36]).

Утверждение 1. Четверки (дп, 5п_х, дп_1, вп) при 0 ^ п ^ т находятся во взаимно однозначном соответствии с решениями (и^щ, г>1, у2) уравнения

щи2 — уху2 = а,

для которых

0 ^ их < щ < а, (их, их) = 1, 0 < г»2 < «2 ^ а, (^2, = 1. В дальнейшем нам понадобится функция

а

РКа) = £ аа(<*). (1-4)

1=1

Используя утверждение 1, можно получить следующую формулу (см. [36, §6])

р;(а) = А*(а,а) + аА*(а,-У (1.5)

а

где

а п а а—1

* ж—> *—

»•м=ЕЕ ЕЕ

п=1 к=1 <2'=1 <5=0

' , ^ С} <2

пЦ + К.Ц — а, — ^ а <--

п п — к

(ф + О + ак).

(1.6)

Освобождаясь от условий взаимной простоты, получаем

А*(а, а) = ]Г ММд^ЪХ , (1.7)

Л. 1л * '

где

п5г 1 А:=1

пС}' + = а, — ^ а < —

п п — к

(д' + д + а^).

(1.8)

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

Этот параграф является переработкой соответствующего параграфа из работы Устинова (см. [36, §5]) с учетом того, что теперь усреднение ведется по трем переменным. Обозначим за Г и С следующие суммы

Е Е Е ЯаАс), с= £ Е £ (1.9)

(а,Ь,с)=1 (а,ь,с)=1

Лемма 8. Пусть х\ > 0, х2 > 0, е > 0 —действительные числа. Тогда справедливо следующее равенство

XIN Х2N йх <¿2

а

о о

5|а

где

6 — НОК

¿1__¿2

,(¿1^2)' (¿2,^1),

Доказательство. Обозначим

Так как (а, Ь, с) = 1, то (с/ь ¿¿2) = 1- Получаем

Е 53 53 /№^201,^161,^1) =

а^х зЛГ (¿1<г2|а Ь^э^ЛГ

(сг1,сг2)=1 (Ь,а)—(с,а)=<г2

53 53 53 53 ^2/(01,61,01). (<г11(г2)=1 1 «¡13^

(Ь1,а1с12)=1 (с1,а1(11)=1

В последнем равенстве мы воспользовались тождеством Джонсона (см [И])

/(¿а, с) = с?/(а, Ь, с). Выражая функцию /(а, 6, с) через функцию Рёдсета, получим

р= Е ^ Е Е Е Е^-1(Ьх'-с1)б1Р||в1(^) =

(Ь1,а1с!2) = 1 (с1,а1<г1)=1

= Е ^ Е Е Е

<1га2^х3ЛГ 0 ¿1|й201 «ЬИкп

(й1,(12)=1 «¡г^г

•ЕЕ Е ^ ~ () •

Используя лемму 2 из [36, §5], получаем

Е Е ~ С1)Ь1А,а1 ( ^ ) =

г11ь1 5г1с1

Следовательно,

Е Е

((¿1,<г2)=1 ^«^¿г

Е Е Е ЕХ^(£Н-

(1.10)

Для оценки остаточного члена воспользуемся леммой 1 и леммой 2, получаем (

О £ £ £ £ Б'*

°1 / 7

ч* / I

ч «1

<11Л2^х3М ¿^(¿га! ¿21^101 1=1 4

\ (<*1><*2)=1 '^«'г

/

= 0,

(¿1^2^x3 N

\ (<гъ<г2)=1

Подставляя полученную оценку в (1.10) и используя формулы (1.4), (1.5), получаем

= Е ад Е Е Е

¡¿га! <Ы<*1<Ч

(й1,<г2>=1 ^¿г]^

I I (аь I) + ^ (аь ) + °£ (Ж1:С2Хз+еЛГ4+£) •

(1.11)

Меняем порядок суммирования

„= е ад е ^ Е ^ Е

£¡1 йо^жчЛГ г , гсоЛГ ^ г ^хчИ 2 ^ хъИ

(^;<г2)11

/ / -ь-^-V-+ ое (Х1х2х1+£ИА+£) . (1.12)

7о Л а1

Заметим, что ($1, ¿2)|(^1аь <12а\), но (¿101, с^аг) = ^1(^1,^2) = «1- Следовательно, (¿1,<У2)|а1, тогда

(аь ¿1,62) = (аь (¿1,62)) = (¿ъ ¿2). Условия ¡<¿2«!, равносильны условию £|ах, где

Тем самым лемма 8 доказана. □

Замечание 6. Аналогично лемме 8 доказывается следующее равенство

£ ад Е Е

(й1;112) = 1 Й! <г2

XIЛГ хоАГ

Г2 у:

Л Л ^Г т л/а

<5|а

Из леммы 8 следует, что для доказательства теоремы 4 необходимо исследовать сумму вида

ЕЛ* (а, а) а

6|а

Используя формулу (1.7) получаем

Е~ = Е £ =Е Е =

гг|5 1<а<Я

п|<5 1<а<

(^<¿2.«)=™ ^ 1 2

Используя лемму 3, получаем

А(о, а) 1 /,л

^ = ъ Е *(«.<*) + / л Е ^^ (1Л4)

Е

<5|а <5|а 5|а

Следовательно, задача свелась к нахождению асимптотической формулы для суммы

Е л(а'°0-

5|а

Нахождению этой формулы и посвящены последующие разделы.

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

Используя формулу (0.1), из формулы (1.8) легко получить следующее равенство

2=1 £=1 <5^0

(5|а

[пЯ' + кЯ<П,а(п~к)<Я^ осп] е (Я'+ Я + ак) =

6 п

= X) М' + ^ я'а(п - к) < ® ^ Н

2=1 д'>1<5^о

'пО' \ (кЯ

-г е

^ (Я' + Я + ак). (1.15)

V 5 ) \ 6

Разобьем область суммирования по переменным (п, к, ф', ф)

тг<7 + кЯ < Я, а(п — к) < Я ^ ст, 1 ^ к ^ п,

0 ^ Я, 1 < Я'-

(1.16)

на пять подобластей. Тогда

553Л(а'а) = Е1 + Е2 + Ез + 24 + Е55 (1.17)

а^Я «5|а

где Ег — сумма для ьго случая. Для этого введем параметры

и1 = \-, и2 = у/Ёа. (1.18) V си

Очевидно, что выполнено

и1и2 = Я и и2 = аих. (1.19)

В Случае 1 мы рассматриваем ситуацию, когда п ^ £Д. Следовательно, остальные случаи посвящены рассмотрению ситуации п > но тогда Я' ^ и2. В Случаях 2 и 3 рассматривается ситуация, когда к ^ Цх, а в Случаях 4 и 5 рассматривается ситуация, когда к > II1. В каждом из этих пяти случаев мы представляем сумму по переменным (п, к, Я, Я') в виде двух двойных сумм. Таким образом, две из четырех переменных образуют "внешнее" суммирование, а две другие-'внутреннее."

1.4.1. Случай 1. Пусть п ^ II1 и внешнее суммирование ведется по области

= {п ^ к ^ п}. Тогда, ввиду (1.16), переменные Я,Я' должны удовлетворять условиям

а(п — к) < ф ^ тт ^ап, ^^ , <5' <

, Я-кЯ

Список литературы диссертационного исследования кандидат наук Фроленков, Дмитрий Андреевич, 2013 год

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

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

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

[3] Dobrowolski E. and Williams K. S. An upper bound for the sum Y^a+i f(n) for a certain class of functions f, Proc. Amer. Math. Soc. 114(1992), 29-35

[4] Granville A. and Soundararajan K. Large character sums: pretentious characters and the Pölya-Vinogradov theorem, Jour. AMS Vol. 20, Number 2(2007), 357-384.

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

[6] Goldmakher L. and Lamzouri Y. Lower bounds on odd order character sums, published in IMRN 2012 (21), 5006-5013.

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

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

[9] Hildebrand A. On the constant in the Pölya-Vinogradov inequality, Canad. Math. Bull. 31 (1988), 347-352.

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

[11] Johnson S. M. A linear diophantine problem. Canad.J.Math.,12(1960),390-398

[12] Knuth D. E, Yao A. C Analysis of thesubstractive algorithm for gretest common divisors. -Proc.Nat.Acad.USA,v.72,№12,1975,4720-4722

[13] Landau E. Abschätzungen von Charaktersummen, Einheiten und klassenzahlen. Nachrichten Königl.Ges.Wiss.Göttingen (1918),pp. 79-97.

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

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

[16] Ostrowski A. Bemerkungen zur Theorie der Diophantischen Approximationen, Abh. Math. Sem Hamburg, 1922, 1, s. 77-98

[17] Paley R. E. A. C. A theorem on characters, J.London Math. Soc. 7 (1932), 28-32.

[18] perron o. Die Lehre von den Kettenbruchen. Bd.l. Elementare Kettenbruche. Teu-ber,1954

[19] pölya G. Uber die Verteilung der quadratischen Reste und Nichreste. Nachrichten Königl.Ges.Wiss.Göttingen (1918),pp. 21-29.

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

[21] QlU Z. M. An inequality of Vinogradov for character (Chinese), J. Shandong Univ., Nat. Sei. Ed. 26 (1991), 125-128.

[22] Ramirez Alfonsin J. L. The Diophantine Frobenius problem, Oxford Lecture Ser. Math. Appl., 30, Oxford Univ, Press, Oxford,2005

[23] Rodseth 0. J. On a linear Diophantine problem of Frobenius, J. Reine Angew. Math., 301 (1978), 161-170

[24] Simalarides A. D. An elementary proof of Polya-Vinogradov's inequality. Period. Math.Hungar. 38 (1999) 99-101.

[25] Simalarides A. D. An elementary proof of Polya-Vinogradov's inequality, 2. Period. Math.Hungar. 40 (2000) 71-75.

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

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

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

[29] Быковский В. А. Отклонение сеток Коробова, Изв. РАН. Сер. матем., 76:3 (2012), 19-38

[30] Виноградов И. М. 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.

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

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

[33] Карацуба А. А. Основы аналитической теории чисел.-М.,Наука,1983.

[34] коробов Н. М. Тригонометрические суммы и их приложения.-М.,Наука,1989.

[35] ПОСТНИКОВ А. Г., Pomahobob Н.П. Упрощение элементарного доказательства А.Сельберга асимптотического закона распределения простых чисел, Успехи мат. наук, т. 10 вып. 4(66), 75-87, 1955.

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

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

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

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

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

[41] устинов А. В. Вычисление дисперсии в одной задаче из теории цепных дробей. Матем.сб., 198:6(2007), 139-158

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

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

[44] Фроленков Д. 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.

[45] Чандрасекхаран К. Введение в аналитическую теорию чисел.-М.,Мир,1974.

[46] Чандрасекхаран К. Арифметические функции.-М.,Наука, 1975.