О приведенных регулярных непрерывных дробях Жабицкая, Елена Николаевна

Введение к работе

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

Одним из инструментов исследования в теории диофантовых приближений является аппарат непрерывных дробей. Статистические свойства разложения действительных чисел в непрерывные дроби исследовались еще Гауссом. В первой половине XX века этим вопросом занимались Кузьмин¹, Хинчин², Леви³ и некоторые другие математики. Систематическое изложение теории цепных дробей есть, например, в книге Хинчина⁴.

Статистические свойства конечных цепных дробей исследовали Локс⁵ и Хейльброн⁶.

В последнее время к этим вопросам вновь проявился интерес. Здесь следует отметить ряд работ Быковского⁷, Авдеевой⁸, Быковского и Авдеевой⁹, Устинова¹⁰.

Настоящая диссертация, в основном, посвящена исследованию статистических свойств конечных приведенных регулярных непрерывных дробей. Приведенной регулярной непрерывной дробью (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.

Kettenbruch¹¹) называется выражение следующего вида:

{to;ti,t2,... ,ti,...) = to , (1)

ti-...

где все t_n — целые, t_n ^ 2 при n ^ 1. Всякое действительное число г единственным образом представляется в виде приведенной регулярной непрерывной дроби (to; *i, *2, - - .,;,...), где to = [г] (верхняя целая часть г), t_n ^ 2 при п ^ 1 Такие дроби упоминались в книге Перрона¹².

Свойствам подходящих дробей приведенной регулярной непрерывной дроби посвящена работа Финкелыпнейна¹³.

Для рационального числа г представление в виде (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.

Вопрос о поведении средней длины для обычных непрерывных дробей был впервые исследован Хейльбронном¹⁴. Он выделил главный член асимптотики для средней длины, где усреднение ведется по числителям:

щ *Ш = ^щ- ^1оd+ (^{1о4 lQ}g^d)

Статистикам конечных непрерывных дробей посвящены также работы Лок-са¹⁵, Кнута¹⁶, Попова¹⁷. Позднее Портер¹⁸ для того же среднего получил асимптотическую формулу с двумя значащими членами:

М)=і

где є — любое положительное и число

носит название константы Портера.

При усреднении по числителям и знаменателям вероятностными и эрго-

дическими методами ряд результатов был получен Диксоном¹⁹, Хенсли²⁰,

Балле и Балади²¹. В 2000 году Балле²² была доказана асимптотическая

Н. 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.

формула для средней длины со степенным понижением в остаточном члене. Последний результат в этой области принадлежит Устинову²³, который получил асимптотическую формулу с лучшим, чем можно получить из результата Портера, понижением в остаточном члене;

^B-^Cp~^{1 +} W)VW)-¹)-

Что же касается приведенных регулярных непрерывных дробей, то в 2003 году Балле²⁴, исследуя статистические свойства различных видов алгоритмов Евклида, с использованием вероятностных и эргодических методов получила, в частности, главный член асимптотической формулы для математического ожидания числа шагов алгоритма Евклида с «делением по избытку», а следовательно, и для-средней длины приведенной регулярной непрерывной дроби.

В настоящей диссертационной работе на основе подхода, предложенного Устиновым²⁵, получен более сильный результат, чем у Балле.

Остановимся подробнее на сравнении различных видов алгоритмов Евклида. Обычный алгоритм Евклида, приводит к разложению действительного числа а/Ь в непрерывную дробь классического вида:

а/Ъ = [а₀; oi, a₂,...,a_s,...]-a₀ + , (2)

а_{1 +}

а₂ + ...Н

a_s + ...

где а₀ Є Z, a.j Є N при j~l. Для рационального х Є Q представление в виде (2) является конечным, и, для однозначности разложения рационального числа, будем считать, что последнее неполное частное a_s > 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.

Если обозначить сумму ао + а\ + ... + a_s неполных частных разложения (2) рационального числа а/6 через 5''(а/6) и положить

^:={і(},хЄ[0,і]:5М(ї)а + і},

то окажется, что множества J-_n — это так называемые последовательности Штерна-Броко.

Назовем F(x) предельной функцией распределения последовательности М_п конечных подмножеств отрезка [0,1], если

lim F_n{x) = F(x),

П-+0О

Предельная функция распределения последовательности J-_n, совпадает с известной функцией Минковского ?(х), введенной Г. Минковским²⁶. Свойства функции ?(а:) подробно исследуются в работах Денжуа²⁷, Виадера, Парадиза и Бибилони²⁸, а также Кинне ²⁹.

Алгоритм Евклида с делением «по избытку» приводит к разложению действительного числа х в приведенную регулярную непрерывную дробь (1). Как и в случае обычных непрерывных дробей, приведенная регулярная непрерывная дробь рационального числа будет конечной.

Аналогично последовательности Т_п для обычных непрерывных дробей, введем последовательность множеств Е_п рациональных чисел с суммой неполных частных приведенной регуляной непрерывной дроби, ограниченной числом п. Предельную функцию распределения последовательности множеств S_n обозначим через 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 е₂

oi +

а₂+ ... + —

щ + ...

где ао Є Z, ; = ±1 и a,j ^ 2, а, + єу+і > 2 при j > 1. В этой дроби

присутствуют как знаки «+», так и «-». Для х Є Q представление в виде

(4) является конечным, и, для однозначности этого представления, в случае

когда последнее неполное частное сц = 2 полагаем є; = 1.

Устинов³⁰ доказал следующие асимптотические формулы для средней

длины дроби с минимальными остатками:

Е ¹>1^Ь) = Е ^Г tog ^R + ^3 + О (/Г¹ log⁴ Л),

*] + D^ ^ч" С(2)

где l'(a/b) — число неполных частных в разложении (4) числа a/b, ip = ^у^, а Сз, С4 — некоторые указанные постоянные.

Для таких дробей также можно рассмотреть последовательность множеств с ограниченной суммой неполных; частных. Обозначим ее через 2_п. Предельную функцию распределения последовательности множеств Z_n обозначим через F^(x).

В 1938 году Денжуа³¹ ввел в рассмотрение функции к(х,а), а Є (0,1), х Є [0, со), обобщающие функцию Минковского ?(ж). А 1995 году, в работе Тихий и Уитц³² рассмотрели однопараметрическое семейство сингулярных функций д\, А Є (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^ (х), то она не является членом семейства д\(х), но обладает похожими свойствами. В частности, Fⁱ²' (х) существует и равна 0 почти всюду в смысле меры Лебега, т.е. функция F^'(x), как и функции из семейства дх, является сингулярной.

Цель работы

Цель диссертации — исследование свойств непрерывных дробей особого вида (приведенных регулярных непрерывных дробей и непрерывных дробей с минимальными остатками), получаемых с помощью алгоритма Евклида, в котором вместо обычного деления используется деление «по избытку» и «центральное» деление соответственно.

Научная новизна

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

1. Получена трехчленная асимптотическая формула для средней длины приведенной регулярной непрерывной дроби.

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

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

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

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

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

Диссертация носит теоретический характер. Результаты, полученные в ней, представляют интерес для теории цепных дробей.

Апробация результатов

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

XV Международная конференция студентов, аспирантов и молодых ученых "Ломоносов" (Москва, 2008 г.)

Семинар "Арифметика и Геометрия", руководители — профессор Н. Г. Мо-щевитин, д.ф.м.н. А. М. Райгородский, доцент О. Н. Герман (2008,2009 г.)

"Научно-исследовательский семинар по теории чисел", руководители -чл.-корр. РАН Ю. В. Нестеренко и профессор Н. Г. Мощевитин (2009 г.)

Семинар "Модели и методы дискретной математики", руководители -профессор О. М. Касим-Заде (2009 г.)

Публикации

Основные результаты диссертации опубликованы в 5-ти работах автора. Список этих работ приведен в конце автореферата [1-5].

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

Похожие диссертации на О приведенных регулярных непрерывных дробях

Статистические и экстремальные свойства цепных дробей Авдеева Мария Олеговна