Введение к работе
Актуальность темы
Одним из инструментов исследования в теории диофантовых приближений является аппарат непрерывных дробей. Статистические свойства разложения действительных чисел в непрерывные дроби исследовались еще Гауссом. В первой половине XX века этим вопросом занимались Кузьмин1, Хинчин2, Леви3 и некоторые другие математики. Систематическое изложение теории цепных дробей есть, например, в книге Хинчина4.
Статистические свойства конечных цепных дробей исследовали Локс5 и Хейльброн6.
В последнее время к этим вопросам вновь проявился интерес. Здесь следует отметить ряд работ Быковского7, Авдеевой8, Быковского и Авдеевой9, Устинова10.
Настоящая диссертация, в основном, посвящена исследованию статистических свойств конечных приведенных регулярных непрерывных дробей. Приведенной регулярной непрерывной дробью (ein reduziert-regalmaessiger
Р. О. Кузьмин. Об одной задаче Гаусса. ДАН ССР, 1928, с. 375-380. А. Я. Хинчин. Metrische Kettenbruechproblem. Compos. Math. 1935, Bd. 1, pp. 361-382 P.Levy. Sur les his de probabilite dont dependent Its quotients complets et incomplets d'unt fraction continue. Bull. Soc. Math. France, v. 57, 1929, pp. 178-194.
A. Я. Хинчин. Цепные дроби. M., Наука, 1978.
G. Lochs. Statistic der Teiinenner der zu den echten Bruechen gehoerigen regelmaessigen Kettenbrueche. Monatshefte fuer Mathematic, 1960, Bd. 65, pp. 27-53. H.Heilbrorm. On the average length of a class of finite continued fractions. In Abhandlungen aus Zahlentheorie und Analysis, Berlin, VEB, 1968, pp. 89-96.
B. А. Быковский. Оценка дисперсии длин конечных непрерывных дробей. ФПМ, 1.11, №6,
2005, с. 15-26.
М. О. Авдеева. Распределение неполных частных в конечных цепных дробях. Владивосток : ИПМ ДВО РАН, 2000, с. 19
М.О.Авдеева, В.,А.Быковский. Решение задачи Арнольда о статистиках Гаусса-Кузьмина. Препринт ДВО РАН №08, Дальнаука, Владивосток, 2002. А. В.Устинов. Асимптотическое поведение первого и второго моментов для числа шагов в алгоритме Евклида. Известия РАН, т. 72, № 5, 2008, с. 86-216.
Kettenbruch11) называется выражение следующего вида:
{to;ti,t2,... ,ti,...) = to , (1)
ti-...
где все tn — целые, tn ^ 2 при n ^ 1. Всякое действительное число г единственным образом представляется в виде приведенной регулярной непрерывной дроби (to; *i, *2, - - .,;,...), где to = [г] (верхняя целая часть г), tn ^ 2 при п ^ 1 Такие дроби упоминались в книге Перрона12.
Свойствам подходящих дробей приведенной регулярной непрерывной дроби посвящена работа Финкелыпнейна13.
Для рационального числа г представление в виде (1) конечно и однозначно определено. Пусть г = (to;ti,*2> ---,^), длину I приведенной регулярной непрерывной дроби, представляющей рациональное число г, обозначим через 1(г).
Длина обычной непрерывной дроби s(a/b) числа а/Ь есть число шагов в классическом алгоритме Евклида, примененном к числам а и Ь. Этот алгоритм использует деление с остатком:
a = bq + г, g Є Z, 0 < г < 6.
Аналогично можно рассматривать длину приведенной регулярной непрерывной дроби l(a/b) числа а/Ь как число шагов в алгоритме Евклида с «делением по избытку», т. е.
a = bq + r, g Є Z, -b < г ^ 0.
Таким образом, средняя длина приведенной регулярной непрерывной дроби
E(R) — . —7\У^/_/^а/^ является математическим ожиданием
числа шагов алгоритма Евклида с «делением по избытку», примененного к числам а и Ь, меняющимся в пределах І^а^Ь^Я, Я—» со.
О. Perron. Die Lehre von den Kettenbruchen. Bd.I.Teuber, 1954.
0. Perron. Die Lehre von den Kettenbruchen. Bd.I.Teuber, 1954.
Ю. Ю. Финкелыптейн. Полигоны Клейна и приведенные регулярные непрерывные дроби.
Успехи мат. наук, 1993, т. 48, Вып.З, с. 205-206.
Вопрос о поведении средней длины для обычных непрерывных дробей был впервые исследован Хейльбронном14. Он выделил главный член асимптотики для средней длины, где усреднение ведется по числителям:
щ *Ш = ^щ- 1оd+ (1о4 lQgd)
Статистикам конечных непрерывных дробей посвящены также работы Лок-са15, Кнута16, Попова17. Позднее Портер18 для того же среднего получил асимптотическую формулу с двумя значащими членами:
М)=і
где є — любое положительное и число
носит название константы Портера.
При усреднении по числителям и знаменателям вероятностными и эрго-
дическими методами ряд результатов был получен Диксоном19, Хенсли20,
Балле и Балади21. В 2000 году Балле22 была доказана асимптотическая
Н. Heilbronn. On the average length of a class of finite continued fractions. In Abhandlungen
aus Zahlentheorie und Analysis, Berlin, VEB, 1968, pp. 89-96.
G. Lochs. Statistic der Teilnenner der zu den echten Bruechen gehoerigen regelmaessigen
Kettenbrueche. Monatshefte fuer Mathematic, 1960, Bd. 65, pp. 27-53.
D. E. Knuth. Analysis of the substractive algorithm for greatest common divisors. Proc. Nat.
Acad. USA, v. 72, №12, 1975, pp. 4720-4722.
B. H. Попов. Асимптотика суммы сумм элементов непрерывных дробей чисел вида о/р.
Аналитическая теория чисел и теория функций. 2, Зап. научн. сем. ЛОМИ, 91, Изд-во
«Наука», Ленинград, отд., Л., 1979, с. 81-93
J.Porter. On a theorem of Heilbronn. Matematika, 1975, v. 22, №1, pp. 20-28.
J. D. Dixon. The number of steps in the Euclidean algorithm. J. Number Theory, v. 2, 1970,
pp. 414-422.
D.Hensley. The Number of Steps in the Euclidean Algorithm. J. of Number Theory, v. 49,
1994, pp. 142-182.
B.Vallee, V. Baladi. Euclidean algorithms are gaussian. J. Number Theory, v. 110, 2005,
pp. 331-386.
B.Vallee. A unifying framework for the analysis of a class of Euclidean algorithms.
Proceedings of LATIN'2000, Lecture Notes in Computer Science 1776, Springer, pp.343-
354.
формула для средней длины со степенным понижением в остаточном члене. Последний результат в этой области принадлежит Устинову23, который получил асимптотическую формулу с лучшим, чем можно получить из результата Портера, понижением в остаточном члене;
B-Cp~1 + W)VW)-1)-
Что же касается приведенных регулярных непрерывных дробей, то в 2003 году Балле24, исследуя статистические свойства различных видов алгоритмов Евклида, с использованием вероятностных и эргодических методов получила, в частности, главный член асимптотической формулы для математического ожидания числа шагов алгоритма Евклида с «делением по избытку», а следовательно, и для-средней длины приведенной регулярной непрерывной дроби.
В настоящей диссертационной работе на основе подхода, предложенного Устиновым25, получен более сильный результат, чем у Балле.
Остановимся подробнее на сравнении различных видов алгоритмов Евклида. Обычный алгоритм Евклида, приводит к разложению действительного числа а/Ь в непрерывную дробь классического вида:
а/Ъ = [а0; oi, a2,...,as,...]-a0 + , (2)
а1 +
а2 + ...Н
as + ...
где а0 Є Z, a.j Є N при j~l. Для рационального х Є Q представление в виде (2) является конечным, и, для однозначности разложения рационального числа, будем считать, что последнее неполное частное as > 2.
A. В.Устинов. Асимптотическое поведение первого и второго моментов для числа ша
гов в алгоритме Евклида. Известия РАН, т. 72, №5, 2008, с. 86-216.
B. Vallee. Dynamical analysis of a class of Euclidean algorithms. Theoretical computer
science, v.297, 2003, pp. 447-486.
А. В. Устинов. О статистических свойствах конечных цепных дробей. Труды по теории чисел, Зап. научн. сем. ПОМИ, 322, ПОМИ, СПб., 2005, с. 186-211.
Если обозначить сумму ао + а\ + ... + as неполных частных разложения (2) рационального числа а/6 через 5''(а/6) и положить
^:={і(},хЄ[0,і]:5М(ї)а + і},
то окажется, что множества J-n — это так называемые последовательности Штерна-Броко.
Назовем F(x) предельной функцией распределения последовательности Мп конечных подмножеств отрезка [0,1], если
lim Fn{x) = F(x),
П-+0О
Предельная функция распределения последовательности J-n, совпадает с известной функцией Минковского ?(х), введенной Г. Минковским26. Свойства функции ?(а:) подробно исследуются в работах Денжуа27, Виадера, Парадиза и Бибилони28, а также Кинне 29.
Алгоритм Евклида с делением «по избытку» приводит к разложению действительного числа х в приведенную регулярную непрерывную дробь (1). Как и в случае обычных непрерывных дробей, приведенная регулярная непрерывная дробь рационального числа будет конечной.
Аналогично последовательности Тп для обычных непрерывных дробей, введем последовательность множеств Еп рациональных чисел с суммой неполных частных приведенной регуляной непрерывной дроби, ограниченной числом п. Предельную функцию распределения последовательности множеств Sn обозначим через F^(x).
Наконец, алгоритм Евклида, в котором при делении выбирается минимальный по модулю остаток:
Ь ^ ь
a = bq + r, --<r<-,
Н. Minkowski. Gesammelte Abhandungen, vol.2.
A. Denjoy. Sur unefonction reek de Minkowski. J. Math. Pures Appl. v. 17,1938, pp. 105-151.
P.Viader, J.Paradis, L.Bibiloni. A new light of Minkowski's ?(i) function. J. Number
Theory., v. 73, 1998, pp. 212 -227.
J.R. Kinney. Note on a singular function of Minkowski. J. Number Theory., v. 73, 1998,
pp. 212-227.
приводит к разложению в непрерывную дробь с минимальными остатками
і ' 1 , Єі ІА\
ад —-,. -, —, -. = ао Н , (4)
а1 0.1 J е2
oi +
а2+ ... + —
щ + ...
где ао Є Z, ; = ±1 и a,j ^ 2, а, + єу+і > 2 при j > 1. В этой дроби
присутствуют как знаки «+», так и «-». Для х Є Q представление в виде
(4) является конечным, и, для однозначности этого представления, в случае
когда последнее неполное частное сц = 2 полагаем є; = 1.
Устинов30 доказал следующие асимптотические формулы для средней
длины дроби с минимальными остатками:
Е 1>1Ь) = Е ^Г tog R + ^3 + О (/Г1 log4 Л),
*] + D^ ч" С(2)
где l'(a/b) — число неполных частных в разложении (4) числа a/b, ip = ^у^, а Сз, С4 — некоторые указанные постоянные.
Для таких дробей также можно рассмотреть последовательность множеств с ограниченной суммой неполных; частных. Обозначим ее через 2п. Предельную функцию распределения последовательности множеств Zn обозначим через F^(x).
В 1938 году Денжуа31 ввел в рассмотрение функции к(х,а), а Є (0,1), х Є [0, со), обобщающие функцию Минковского ?(ж). А 1995 году, в работе Тихий и Уитц32 рассмотрели однопараметрическое семейство сингулярных функций д\, А Є (0,1), аналогичных функциям к(х,а). Функция ?(х) является членом семейства д\(х) с А = 1/2. Для х Є [0,1] функции к(х, а) и дх связаны соотношением
к(х,а) = 1 - (1 - а)д^а(х).
А.В.Устинов. О среднем числе шагов в алгоритме Евклида с выбором минимального по модулю остатка. Матем. заметки, т. 85, №1, 2009, с. 153-156.
A.Denjoy. Sur ипе function reek de Minkowski. J. Math. Pures Appl. v. 17, 1938, pp. 105-151. R. F.Tichy, J.Uitz. An extension of Minkowski's singular function. Appl. Math. Lett., v. 8, 1995, pp. 39-46.
В данной диссертационной работе показано, что предельная функция FW(i) распределения последовательности множеств Еп является членом семейства дх(х), а именно,
F^(x) = gAx),
Что же касается функции F^ (х), то она не является членом семейства д\(х), но обладает похожими свойствами. В частности, Fi2' (х) существует и равна 0 почти всюду в смысле меры Лебега, т.е. функция F^'(x), как и функции из семейства дх, является сингулярной.
Цель работы
Цель диссертации — исследование свойств непрерывных дробей особого вида (приведенных регулярных непрерывных дробей и непрерывных дробей с минимальными остатками), получаемых с помощью алгоритма Евклида, в котором вместо обычного деления используется деление «по избытку» и «центральное» деление соответственно.
Научная новизна
Основные результаты диссертации являются новыми и состоят в следующем:
-
Получена трехчленная асимптотическая формула для средней длины приведенной регулярной непрерывной дроби.
-
Доказано, что предельная функция распределения последовательности множеств рациональных чисел с ограниченной суммой неполных частных приведенной регулярной непрерывной дроби является членом семейства сингулярных функций дх, введенных Тихим и Уитцем в 1995 году.
-
Доказаны некоторые свойства предельной функции распределения последовательности множеств рациональных чисел с ограниченной суммой неполных частных непрерывной дроби с минимальными остатками. В частности, доказана формула, выражающая значение этой функции в точке х через неполные частные представления х в виде непрерывной дроби с минимальными остатками.
Методы исследования
Доказательства асимптотических формул базируются на явных арифметических конструкциях, которые позволяют свести исходную задачу к нахождению числа целочисленных решений системы неравенств. Исследование функций распределения связано с детальным анализом расположения дробей Фарея.
Теоретическая и практическая ценность
Диссертация носит теоретический характер. Результаты, полученные в ней, представляют интерес для теории цепных дробей.
Апробация результатов
Результаты диссертации докладывались и обсуждались на следующих научно-исследовательских семинарах и международных конференциях.
XV Международная конференция студентов, аспирантов и молодых ученых "Ломоносов" (Москва, 2008 г.)
Семинар "Арифметика и Геометрия", руководители — профессор Н. Г. Мо-щевитин, д.ф.м.н. А. М. Райгородский, доцент О. Н. Герман (2008,2009 г.)
"Научно-исследовательский семинар по теории чисел", руководители -чл.-корр. РАН Ю. В. Нестеренко и профессор Н. Г. Мощевитин (2009 г.)
Семинар "Модели и методы дискретной математики", руководители -профессор О. М. Касим-Заде (2009 г.)
Публикации
Основные результаты диссертации опубликованы в 5-ти работах автора. Список этих работ приведен в конце автореферата [1-5].
Структура и объем работы