Введение к работе
. Актуальность темы. Диофантовы множества и диофан-товы представления тесно связаны с исследованиями по 10-й проблеме Гильберта и смежными вопросами алгоритмической теории чисел. В 1970 году Ю. В. Матиясевич 1 доказал совпадение понятия диофантова множества и понятия рекурсивно перечислимого множества. Таким образом, диофантовы представления позволяют получать теоретико-числовую характе-ризацию рекурсивно перечислимых множеств. Например, по заданному рекурсивно перечислимому множеству натуральных чисел можно построить многочлен от нескольких переменных (принимающих натуральные значения), множество неотрицательных значений которого совпадает с данным множеством.
Однако универсальная техника построения диофантовых представлений приводит к многочленам очень большой сложности, что практически не оставляет надежд для применения таких представлений при изучении свойств конкретных множеств. Поэтому весьма актуальна задача построения диофантовых представлений, использующих специфику рассматриваемых множеств.
Среди множеств, представляющих особый интерес, следует выделить множество простых чисел и его подмножества. Их диофантовы представления строились в работах Джоунса, Сато, Вада и Вьенса2, Ю. В. Матиясевича3. При этом удает-
1 Матиясевич Ю. В. Диофантовость перечислимых множеств // Доклады ЛИ СССР.— 1970 — Т. 191, №2.— С. 278-282.
2Jones J.P., Sato D., Wada H., Wiens D. Diophantine representation of the set of prime numbers // American Mathematical Monthly— 1976 — Vol. 83, №6.— P. 449-464.
3Матиясевич Ю.В. Диофантово представление множества
ся получить многочлен меньшей степени по сравнению с универсальной конструкцией. Однако в настоящее время число переменных остается таким же - 10, как и в случае применения общей техники 4. Для простых чисел Мерсенна и Ферма диофантовы представления с 7 переменными были получены Джоунсом 5. Однако до настоящего времени неизвестно, бесконечны ли данные множества (а для конечных множеств достаточно одной переменной). Поэтому актуальна следующая задача: можно ли уменьшить количество переменных за счет рассмотрения не всего множества простых чисел, а какого-либо его бесконечного подмножества?
Другой задачей, имеющей большое значение, является построение диофантовых представлений рекуррентных последовательностей. Это вызвано тем, что представления таких множеств играют существенную роль в доказательстве алгоритмической неразрешимости 10-й проблемы Гильберта и используются при построении универсальных диофантовых представлений. Так, исходное доказательство неразрешимости 10-й проблемы Гильберта, данное Ю. В. Матиясевичем1, опиралось на диофантово представление чисел Фибоначчи.
простых чисел // Доклады АН СССР.— 1971.— Т. 196, №4.— С. 770-773.
4Матиясевич Ю.В. Простые числа перечисляются полиномом от десяти переменных // Записки научных семинаров ЛОМИ АН СССР.— 1977.— Т. 68.— С. 62-68.
5Jones J.P. Diophantine representation of Mersenne and Fermat primes /I Acta Arithmetica — 1979—Vol. 35, №3 — P. 209-221.
6Чудновский Г.В. Диофантовы предикаты // Успехи математических наук.— 1970.— Т. 25, №4.— С. 185-186.
7Косовский Н. К. О диофантовых представлениях последовательности решений уравнения Пелля // Записки научных
Г. В. Чудновский 6, Н. К. Косовский 7, М. Дейвис 8 независимо друг от друга построили диофантовы представления последовательностей 2-го порядка, связанных с уравнением Пелля.
Представляют интерес диофантовы представления последовательностей более высоких порядков. В частности, это даст новое независимое доказательство алгоритмической неразрешимости 10-й проблемы Гильберта.
Цель работы. Разработать новые методы построения диофантовых представлений для множеств значений линейных рекуррентных последовательностей третьего порядка с постоянными коэффициентами и для бесконечных множеств простых чисел специального вида.
Общая методика работы. В работе использованы разработанная автором техника, позволяющая свести задачу построения диофантовых представлений рекуррентных последовательностей к исследованию свойств группы единиц некоторого кольца алгебраических чисел, теорема Дирихле о единицах, теорема Делоне о количестве представленрій 1 бинарными кубическими формами отрицательного дискриминанта, критерии простоты особого вида, а также общие методы алгебраической теории чисел.
Основные результаты работы Доказано существование бесконечных множеств простых чисел совпадающих с мно-
семинаров ЛОМИ АН СССР.— 1971 — Т. 20.— С. 49-59.
8 Davis М. An explicit diophantine definition of the exponential function.// Commun. Pure Appl. Math.— 1971.-— Vol. 24, №2.— P. 137-145
жествами положительных значений многочленов от 8 и от 9 переменных, принимающих положительные целые значения. Количество переменных оказывается меньше наилучшей известной универсальной границы - 10.
Построены новые диофантовы представления множеств значений линейных рекуррентных последовательностей третьего порядка. С помощью таких представлений построено новое представление экспоненциального отношения, что дает независимое доказательство алгоритмической неразрешимости 10-й проблемы Гильберта.
Научная новизна. Все основные результаты диссертации являются новыми.
Практическая и теоретическая ценность. Работа носит теоретический характер. Ее методы и результаты могут быть полезны специалистам Математического института им. В. А. Стеклова РАН, Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН, Московского государственного университета, Санкт-Петербургского государственного университета.
Апробация работы. Результаты диссертации докладывались на общемосковском семинаре по математической логике (руководители семинара — член-корр. РАН С. И.Адян, проф. В.А.Успенский), на семинаре по математической логике Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН (руководитель семинара — проф. Ю.В. Матиясевич), на Санкт-Петербургском алгебраическом семинаре им Д. К. Фадцеева (руководитель семинара
— проф. А. В. Яковлев), а также на международных конференциях по теории чисел (Тула, 1993; Воронеж, 1995).
Публикации. Результаты диссертации опубликованы в шести работах, перечисленных в конце автореферата.
Структура и объем диссертации. Диссертация состоит из введения и двух глав, разделенных на 12 параграфов. Нумерация параграфов, формул, лемм и теорем ведется отдельно для каждой главы. Текст диссертации изложен на 71 странице. Список литературы содержит 32 наименования.