Рекуррентные последовательности и их приложения тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РГБ ОД

1 московский ГОСУДАРСТВЕННЫЙ

1 К МНР да УНИВЕРСИТЕТ

I о Ь1НГ и.,Л ИменИ м.в. ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи УДК 511.216 511.218

Кан Игорь Давидович

РЕКУРРЕНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ И ИХ ПРИЛОЖЕНИЯ

Специальность 01.01.06 Математическая логика, алгебра и теория чисел

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

Москва, 1997

Ша^/

Работа выполнена на кафедре теории чисел

механико-математического факультета Московского государственного университета им. М.В. Ломоносова

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

доктор физико-математических наук, профессор Коробов Н.М.

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

- доктор физико-математических наук, профессор Нечаев В.И.

- доктор физико-математических наук, доц. Маренич Е.Е.

Ведущая организация:

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

Защита диссертации состоится » 199&г. в 16

час. 15 мин. на заседании диссертационного'совета Д.053.05.05. при МГУ по адресу: 118899, ГСП, Москва, Воробьевы горы, МГУ, механическо-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан » 199^

г.

Ученый секретарь диссертационного совету Д.053.05.05 при МГУ /^/1 ;

д.ф.-м.н., профессор ^¿А В.Н. Чубариков

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

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

История вопроса начинается с проблемы, сформулированной Сильвестром 1 в 1884 году: «Чему равно наибольшее целое число g, не представимое в виде суммы некоторого количества экземпляров двух взаимно простых чисел а и 6?- Чему равно количество п натуральных числе, не представимых в виде суммы нескольких экземпляров а и b?» Ответ, данный Сильвестром, таков:

g-ab-a-b, п = (а —1)(6-1)/2.

Вопросы, поставленные Сильвестром, в последствии были обобщены: «Чему равно наибольшее целое число g = g(a0,ai,...,am_i), не представимое в виде неотрицательной целочисленной линейной комбинации заданных m натуральных чисел а0,а1,а2,..-,сг„,_1, взаимно

простых в совокупности? Чему равно количество п = n(a,ai,...,am_^) натуральных чисел, не представимых в виде любого числа слагаемых (совпадение слагаемых допускается), равных одному из чисел а0,а1,...,ат_1?» Первый из этих вопросов был сформулирован Фробениусом в его лекциях в начале XX века и получил название проблемы Фробениуса, а функция g{aQ,a\,...,am^- функции Фробениуса.

Являясь простой по формулировке, содержательно проблема Фробениуса оказывается сложной. Так, при т — 3 ее решение получается уже не в виде формулы, а алгоритмически. Говоря об алгоритмах, удобно дать следующее определение. Назовем алгоритм поиска ¿7),...,£/,„_])

приемлемым, если на его выполнение уйдет не более 0(1пао) арифметических операций. Первый приемлемый алгоритм для §(а0,а1,а2) в 1960 г. дал Джонсон2, который доказал также, что для

любого натурального d, делящего каждое из чисел «о,^,...,«,,,^, справедлива «формула Джонсона»:

(:1 ) g(a0 ,a},...,am^,ani) = dg(^-, ^,..., H/jtL, +{d-1 )а,„.

Несмотря на усилия многих математиков, при m >4 не получено ни одного приемлемого в смысле данного выше определения алгоритма для g(aQ,al,a2,...,am_l).

1 Sylveslcr J.J. Malhcmatical questions, wilh tlicir solutions. //

Educalional limes. - 1X84. -№41. -P.21

2 Jolmsoa S.M. A Iincar Dioplinuluicproblcm.// Cauad. J. Math. - 1960. - №12. - P.390-39SS

Со времени работы Джонсона его идеи развивались многими исследователями (Бейер3, Селмер4, Редеет6), и в 1979 г. Редеет 6 дал наиболее общий до настоящего времени результат, получив приемлемый алгоритм для %(а0,аиа2,...1) и' я(а0,а1,...а/,1_1) (/н>3), когда аргументы а(),а1,...,а11!_1 образуют арифметическую прогрессию.

Результат Редсета о функции g доказал новым способом КайМан Цан7. Способ его доказательства основан на рассмотрении и решении максимизационной проблемы /Зх

тах(-<& + у

) {а,/3,у,д

а

где х- целая переменная, а,Р,у,5,% - параметры. Проблема Фробениуса, таким образом, оказывается связанной с задачами дискретной оптимизации.

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

Назовем последовательность натуральных чисел ч

{т> 3) .цепной, если для всех / = 1,2Д...,ш — 2 число а^ является делителем суммы а}-\ Назовем последовательность

а0,а,,...,<з„,_1,<з„г.почти цепной, если а0,а1,...)а„,_1 - цепная

последовательность следующие условия:

3 Beyer O. The problem of Frobenius in tlircc variables. / Thesis, Univ. ofBcrgcn(in Norvcgian), Dept. of Math., 1976.

* Sclnicr E.S., Beyer 0. On the linear Dioplianline problem of Frobenius in three variables. // J.Rcinc Angcw Math. - 1978. -B.301. - 161-170.

5Rodset 0.1. On a linear Dioplianline problem of Frobenius. // J.Rcinc Angcw.Math. - 1978. - B.301. - 171-178.

6 Rodset 0.J. On a linear Diophantine problem of Frobeiiius.il. // J.Rcinc Angcw.Math. - 1979. - B.307/308. - 431-440.

'kai-Man Tsang. On llic linear Dioplianline problem of Frobenius.//Sludia Scientarum Math. Hiingarica. - 1988. №23.-443-452.

Всюду далее через обозначаем цепную

а0,йг1,...,й(/„_1 [пг> 3), для которой выполнены

(2) а0> 2,

(3) н.о.д.(а0,а1) = 1,

(4) а]_х >дДу' = 1,2,...,т-2).

Как показано в диссертации, из формулы Джонсона (1) и данных выше определений следует, что условия (2) - (4) не ограничивают общности рассматриваемых вопросов.

Цель работы.

Настоящая диссертация имеет следующие цели.

1. Получение точного решения (формулы) для проблемы Фробениуса возрастающей цепной последовательности аргументов.

2. Получение приемлемого алгоритма для функции Фробениуса от почти цепной последовательности аргументов.

3. Развитие теоретических средств, направленных на решение проблемы Фробениуса (создание аппарата цепных последовательностей, рассмотрение специальных частичных порядков, улучшение метода максимизации Кай-Ман Цана).

4. Получение асимптотических формул для g(a0,a1,...) и

и(а0,а1;...) при а0 < а| для бесконечных почти цепных последовательностей аргументов.

Методы исследования. При доказательстве основных результатов использовались методы теории чисел, теории частичных порядков и теории цепных дробей. Последняя послужила основой для создания аппарата рекуррентных цепных последовательностей (I глава диссертации), пригодного для исследования проблемы Фробениуса.

Научная новизна. Все основные результаты диссертации являются новыми.

Практическая и теоретическая ценность диссертации.

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

Апробация работы. Результаты диссертации докладывались и обсуждались на научно-исследовательских семинарах механико-математического факультета МГУ им. М.В.Ломоносова, математического института им. Стеклова и на международной конференции «Современные проблемы теории чисел» (Тула, 1993).

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

з

Структура и объем диссертации. Диссертация состоит из введения, подразделенного на 3 параграфа, и четырех глав, включающих в себя 14 параграфов. Список литературы подразделяется на 4 части и содержит всего 79 наименований, в том числе 53 - проблеме Фробениуса. Объем диссертации 175 машинописных листов.

Содержание диссертации. Во введении кратко изложена история проблемы Фробениуса, приведены наиболее значительные результаты в этой области. Также приведен обзор основных результатов диссертации, даны общие сведения и понятия, использованные в работе.

В первой главе диссертации (§§4-6) строится аппарат цепных последовательностей и выводится ряд вспомогательных утверждений, необходимых для дальнейшего.

С этой целью по данной цепной последовательности

^cij | строится ряд специальных целочисленных функций, в том числе 6j{z)\Z-> Z(j - 0,1,...,/и—1) по правилам :

где £?0(1) определено условиями:

0о(1)а, = l(mod а0), 0 < 0o(l) Отметим, что абстрактно определенное,-число 6о(1) можно вычислить с

помощью алгоритма Евклида, затратив О(1гш0) арифметически*

операций. Важность ■ введенных функций-показывает следующая доказанная^ §6

Теорема 6.1. Пусть для н = 1,2,...,т-1 уравнение аи = а0х0 + аххх+...+аи_ххи_х неразрешимо в целых неотрицательных Тогда для любых целых j,h,k

удовлетворяющих условию 0 < j <k<h<m-1, справедливы соотношения:

Эта теорема используется при. доказательстве результатов главы

II.

Глава II (§§7-9) посвящена;вычислению функции Фробениуса от цепных и почти цепных последовательностей аргументов при условии а0'<ах. Для формулировки этих результатов введем следующие

обозначения. Для j -\,2,...,т-2 -через /у обозначим частное: , _aJ-i+aJ+\

(По условию, /. > 2 - натуральные числа). Через £ обозначим число

е-

к-

I -1

т-1

«О

В §7 доказаны, в частности, следующие теоремы. Теорема 7.3. Для любого фиксированного N е Z уравнение Лг = айх$ + а\х\+-~+ат-\хт-\ разрешимо в целых неотрицательных числах х0,х1,...,хт_х тогда и только тогда, когда Л^^Х^-Шо). Теорема 7.4. Если для ад..<а], то

,аь...,ат_х) = ах(а0 -1) + а0[(1 -а0)е].

Далее на И вводится частичный - порядок <0, определенный правилом

X У <=> У- * = #0*0 + а\х\+-+ат-\хт-1 для некоторых целых неотрицательных х0,х1,...,д"/;г„]. Теорема 7.3, таким образом, дает для частичного порядка <0 аналитическое

выражение, что становится далее существенным инструментом исследования.

В §8 начинается исследование проблемы Фробениуса почти цепной последовательности аргументов' . Установлено,

что функция Фробениуса в этом случае выражается через рекуррентные последовательности и {г/} (_/' = 0,1,...), для которых

г0 = 0, /] =1, с]о = а0, 0 < ^ < а0 -1, / = ^(тос^о),

а для ] — 1,2,....', при Ф 0, положено по определению: ~ 1

<7/>| =

ГМ =

•+1

1

-+1

а если qj=Ol то "_/-й член в обеих последовательностях

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

следует, что в следующем равенстве, определяющем некоторое число V, минимум берется по непустому множеству:

V = minjy eN|r} > qfa - aar0)}.

результатов §8 в §9

выводится следующая

На основании основная в главе II

Теорема 9.1. Если для почти цепной последовательности {а0,ах,...,ат_х,{) выполнено неравенство а0 <ах,то

g(a0,а1,...ат_1^) = гу-1 + а1 -1) +

Отсюда в качестве одного из следствий получается результат Редсетаепри ^ = /2 =...= 1т_2 =2;

§{а,а + + = -t + d(c[v_l -1) +

■2"

+ maxi

-Л

-f max

~rv-\+a

tfv-Г

■dqv 4-a

m-1

m-1

Из этих формулировок видно, что полученное в диссертации обобщение результата Редсета не является формальным. В §9 выведен также ряд других следствий из теоремы 9.1".

В главе III (§§10-11) рассматриваются вопросы о приложимости построенного в I главе аппарата рекуррентных последовательностей к задачам дискретной оптимизации, связанным с проблемой Фробениуса, и к теоретическим вопросам, связанным с приближенным вычислением интегралов.

Основной вопрос, решенный в §§10-11, состоит в снятии условия а0 < ах в сформулированных выше теоремах. Это сделано при помощи усовершенствования метода максимизации Кай-Ман Цана7, упомянутого выше. Именно, рассмотрена близкая максимизационная проблема, состоящая в вычислении , где

М(<0 = max [ [ах - а0)х ~ ^

Q<x<,sy

)х + а0

а

£ eZ, х - целая переменная, а и а - числитель и знаменатель дроби

1 Kai-Man Tsang. On the linear Diophantine problem of Frobcnius.//Sludia Scicntarum Malh. Hungarica. - 1988.-№23.-443-452

' Вычисление М(^) осуществляется при помощи рекуррентных последовательностей {0/}> {^"у }'• для которых й =ЙГо-°ь <2о =«о» = А ¿о =а» = а Для ПР"

^7+1 -

■+1

Qj+1 ~

^7-1-1

■ + 1

Qj-Qj-

sj~ i

В этих обозначениях сформулирована доказанная в §10 Теорема 10.1. Имеет место формула

где

W = minj Je N U{0}|ß;+1 < 0 или Zj < о}.

Эта теорема в ряде случаев позволяет вычислять функцию Фробениуса. Так, в §11 доказаны следующие теоремы.

Теорема 11.1. Для цепной последовательности |üj | g(a0,al,...,am_l)= M(a0-l).

Теорема 11.3. Для цепной последовательности ja^-J и

натурального I

( л f M(qv_i —qv -l),

+M{qv_l-\).

Теорема 11.3 является основной в главе III. Из этих теорем выведены также некоторые новые следствия (§11), в частности -следующее.

Следствие. Пусть a.k.I eN. а> 3, к> 2, /> 2,

тогда

g(a,a —\,a - 2,ka - 2k-\, l(ka-2k-\)-a + l)-

-a

{kl - l)(a -1) -1 2{kl -1) + /

2kl + l-2

2Ы + 1-2

•1.

kl-1

В §12 по формулам теорем §§8-11 строятся приемлемые алгоритмы вычисления функции Фробениуса от почти цепных последовательности аргументов.

В §13, завершающем главу ill, исследуется приложимость построенного аппарата рекуррентных последовательностей к теоретическим вопросам связанным приближенным с вычислением двумерных интегралов. А именно, строится алгоритм, который для данных взаимно простых чисел п и t, \<t <п, за 0(1п п) арифметических":

операций вычисляет функцию Нп 2(t), где

Hn>s{t) = -i[l-2 п k=v

tk

п

1-2

V

(Минимизация функции Н„ 4.(/) используется в

теоретикочисловых формулах приближенного интегрирования8 ).

Глава IV (§§14-17). посвящена изучению асимптотики в проблеме Фробениуса. Здесь для получения асимптотических результатов потребовалось привлечение техники обращения Мебиуса в частично упорядоченных множествах9, изложение которое занимает §14.

В §15 рассматривается ситуация бесконечного роста элементов бесконечной почти цепной последовательности t,a0,al,...,aj,... при

фиксированных /1,/2,..., и на эту последовательность накладывается некоторые условия, при выполнении которых пределы

lim

ad->co

g(t,a0,ab..) iim fi(/,fl0,flb...)

«о2

a0

существуют. Далее доказываются теоремы, позволющие эти пределы вычислять (§§16-17).

Автор выражает глубокую благодарность КАРыбникову, весьма способствовавшему автору в совершенствовании научного образования. Автор выражает глубокую благодарность Б.С.Стечкину за руководство исследованиями по теории функций Мебиуса, постановку проблемы Фробениуса и обсуждение, Автор выражает глубокую благодарность Н.М.Доброволькому за обсуждение и многие полезные советы, кардинально повлиявшие на структуру и характер работы. Автор выражает

Коробов Н.М. Тсорстикочисловыс методы d приближенном анализе. - М.:Физматги j. 1963

9 Hall P. A contribulion to Uicory of groups of prime power order // Proc. Loudon Math. // Ser. - 1932. ■ V.36. -p.29-95.

Г

глубокую благодарность своему научному руководителю Н.М.Коробову за постоянное внимание к работе.

Список работ автора по теме диссертации:

1. Кан И.Д. К проблеме Фробениуса. II Прикладная и фундаментальная математика. - 1997. - №3, с. 821-835.

2. Кан И.Д. Тезисы доклада по проблеме Фробениуса. Сб-к Межд. Конференции «Современные проблемы теории чисел»/ Тульский пед. ин-т., -Тула, 1993. - с.71

3. Кан И.Д. Мебиус-функции объединения частичных порядков II Дискретная математика. -1991. - Т.З, №2, с. 121-127.

4. Кан И.Д. Об одной теореме вложения для Мебиус-функций // Вестник Моск. ун-т . - Сер. I, Математика. Механика. - 1993, №3-с. 82-84.

Диссертация выполнена при частичной поддержке гранта РФФИ "Алгебраическая комбинаторика" Л 96-01-00-432.