Введение к работе
Актуальность темы. Основные результаты настоящей диссертации относятся к приложению теории рекуррентных последовательностей к проблеме Фробениуса, лежащей в области аддитивной теории чисел.
История вопроса начинается с проблемы, сформулированной Сильвестром ' в 1884 году: «Чему равно наибольшее целое число g, не представимое в виде суммы некоторого количества экземпляров двух взаимно простых чисел а и bl- Чему равно количество п натуральных числе, не представимых в виде суммы нескольких экземпляров а и Ь?» Ответ, данный Сильвестром, таков:
g = ab-a-b, n = (a-l)(b-l)/2.
Вопросы, поставленные Сильвестром, в последствии были обобщены: «Чему равно наибольшее целое число g = g(oo>ai>--->a/»-i)-не представимое в виде неотрицательной целочисленной линейной комбинации заданных т натуральных чисел а0,ах,а2,---,сіт_\, взаимно
простых в совокупности? Чему равно количество п~ п{а,а\,...,ат_і)
натуральных чисел, не представимых в виде любого числа слагаемых (совпадение слагаемых допускается), равных одному из чисел а$,а\, ...,am_!?» Первый из этих вопросов был сформулирован Фробениусом в его лекциях в начале XX века и получил название проблемы Фробениуса, а функция g{aQ,a\,...,am^- функции Фробениуса.
Являясь простой по формулировке, содержательно проблема Фробениуса оказывается сложной. Так, при т — 3 ее решение получается уже не в виде формулы, а алгоритмически. Говоря об алгоритмах, удобно дать следующее определение. Назовем алгоритм поиска g{a,а\,...,сг,„^)
приемлемым, если на его выполнение уйдет не более О(\па0) арифметических операций. Первый приемлемый алгоритм для g(a0,ai,a2) в 1960 г. дал Джонсон2, который доказал также, что для
любого натурального d, делящего каждое из чисел а0,а{,...,0,,,^, справедлива «формула Джонсона»:
(,1) g(a0,a],...,am^,am) = dg\^,^,...,C^,an,J+(d-l)am.
Несмотря на усилия многих математиков, при /;/ > 4 не получено ни одного приемлемого в смысле данного выше определения алгоритма для g(aQ,al,a2,...,am_l).
1 Sylvester J.J. Mathematical questions, with their solutions. II
Educational times. - Ш4. -№41. -P.21
2 Johnson S.M. A linear Dioplinutuic problem.// Cauad. J. Math. - 1960. - №12. - Р.390-ЗУ8
Со времени работы Джонсона его идеи развивались многими исследователями (Бейер3, Селмер4, Редеет6), и в 1979 г. Редеет 6 дал наиболее общий до настоящего времени результат, получив приемлемый алгоритм для g{a0,aua2,...)am_l) и' и(а0,а,,...<„,_,) (/н>3), когда аргументы а,а.\,...,ат_х образуют арифметическую прогрессию.
Результат Редсета о функции g доказал новым способом Кай-Ман Цан7. Способ его доказательства основан на рассмотрении и решении максимизационной проблемы
max(-<& + у
а
) (а,Дг,*єКиє2).
где х- целая переменная, а,Р,у,д,^ - параметры. Проблема Фробениуса, таким образом, оказывается связанной с задачами дискретной оптимизации.
Результат Редсета о функуии g обобщен в настоящей диссертации на последовательности.более общего вида по сравнению с арифметическими прогрессиями, а именно - получено выражение для g от цепных и почти цепных последовательностей аргументов (определение -ниже).
Назовем последовательность натуральных чисел aQ,a\,...,am^ {in > З) .цепной, если дЛЯ всех j = ід Д..., т— 2 число а, является
делителем суммы aj-i+aj+i- Назовем последовательность а0,щ,...,ат_иат_почти .цепной, если a0,af,...,aw_i - цепная
последовательность a0,al5 следующие условия:
Всюду далее через la Л обозначаем цепную (ш>3), для которой выполнены
>am-V
3 Beyer О. The problem of Frobeiiius in three variables. I Thesis,
Univ. of Bergenia Norvcgian), Dcpt. of Math., 1976.
4 Sclmcr E.S., Beyer 0. On the linear Diophanlinc problem of
Frobcnius in three variables. II J.Rcinc Angew Math. - 1978. -
B.301. -161-170.
5R6dset 0.J. On a linear Diophanlinc problem of Frobcnius. II
J.Rcinc Angcw.Malh. - 1978. - B.301. - 171-178. 6 Rodset 0.J. On a linear Diophanlinc problem of . II
J.Rcinc Angc\v.Malh. -1979. - B.307/308. - 431440. 'kai-Man Tsang. On the linear Diophanlinc problem of Frobcnius.// Sludia Scicutarum Math. Hnngarica. -1988. №23.-443-452.
(2)я0>2,
(3)H.o.d.(a0,fli) = l.
(4) aj_x + aJ+l > aj(j = 1,2,...,m-2).
Как показано в диссертации, из формулы Джонсона (1) и данных выше определений следует, что условия (2) - (4) не ограничивают общности рассматриваемых вопросов.
Цель работы.
Настоящая диссертация имеет следующие цели.
-
Получение точного решения (формулы) для проблемы Фробениуса возрастающей цепной последовательности аргументов.
-
Получение приемлемого алгоритма для функции Фробениуса от почти цепной последовательности аргументов.
-
Развитие теоретических средств, направленных на решение проблемы Фробениуса (создание аппарата цепных последовательностей, рассмотрение специальных частичных порядков, улучшение метода максимизации Кай-Ман Цана).
-
Получение асимптотических формул для giciQ,^,..^ и
и(а0,аІ5...) при а0 < а| для бесконечных почти цепных последовательностей аргументов.
Методы исследования. При доказательстве основных результатов использовались методы теории чисел, теории частичных порядков и теории цепных дробей. Последняя послужила основой для создания аппарата рекуррентных цепных последовательностей (I глава диссертации), пригодного для исследования проблемы Фробениуса.
Научная новизна. Все основные результаты диссертации являются новыми.
Практическая и теоретическая ценность диссертации.
Диссертация имеет теоретический характер. Полученные в диссертации результаты и методы могут найти свое приложение в аддитивной теории чисел и теории дискретной оптимизации.
Апробация работы. Результаты диссертации докладывались и обсуждались на научно-исследовательских семинарах механико-математического факультета МГУ им. М.В.Ломоносова, математического института им. Стеклова и на международной конференции «Современные проблемы теории чисел» (Тула, 1993).
Публикации. Основные результаты диссертации опубликованы в 4 работах, список которых приведен в конце автореферата.
Структура и объем диссертации. Диссертация состоит из введения, подразделенного на 3 параграфа, и четырех глав, включающих в себя 14 параграфов. Список литературы подразделяется на 4 части и содержит всего 79 наименований, в том числе 53 - проблеме Фробениуса. Объем диссертации 175 машинописных листов.