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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

о'

3 ^ На правах рукописи

С УДК 511.5

Всемирное Максим Александрович

МЕТОДЫ ПОСТРОЕНИЯ ДИОФАНТОВЫХ ПРЕДСТАВЛЕНИЙ

(01.01.06 — математическая логика, алгебра и теория чисел)

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

Санкт-Петербург —1997

Работа выполнена в Санкт-Петербургском отделении Математического института им. В. А. Стеклова Российской академии наук

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

член-корреспондент РАН Ю. В. Матиясевич

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

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

кандидат физико-математических наук Б. Б. Лурье

Ведущая организация: Московский государственный университет

Защита состоится " /4 " ¿ЬЬ&^Я 199е? года в час. на заседании Диссертационного совета К 063.57.45 по защите диссертаций на соискание ученой степени кандидата наук в Санкт-Петербургском государственном университете (адрес совета: 198904, Санкт-Петербург, Старый Петергоф, Библиотечная пл., 2, математико-механический факультет Санкт-Петербургского государственного университета).

Защита будет проводиться по адресу: 191011, Санкт-Петербург, наб. р. Фонтанки, 27, ауд. 311 (помещение ПОМИ РАН).

С диссертацией можно ознакомиться в научной библиотеке им. А. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9

Автореферат разослан " Ь " О^К-О-оПЪЦ997 года.

Ученый секретарь

диссертационного совета

кандидат физико-математических наук

Р. А. Шмидт

Общая характеристика работы. Актуальность темы. Диофантовы множества и диофан-товы представления тесно связаны с исследованиями по 10-й проблеме Гильберта и смежными вопросами алгоритмической теории чисел. В 1970 году Ю. В. Матиясевич 1 доказал совпадение понятия диофантова множества и понятия рекурсивно перечислимого множества. Таким образом, диофантовы представления позволяют получать теоретико-числовую характе-ризацию рекурсивно перечислимых множеств. Например, по заданному рекурсивно перечислимому множеству натуральных чисел можно построить многочлен от нескольких переменных (принимающих натуральные значения), множество неотрицательных значений которого совпадает с данным множеством.

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

Среди множеств, представляющих особый интерес, следует выделить множество простых чисел и его подмножества. Pix диофантовы представления строились в работах Джоунса, Сато, Вада и Вьенса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 Fermât primes // 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.

8Davis M. 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 наименования.

Содержание работы

Во введении дается обзор результатов по исследуемой проблеме и кратко формулируются основные результаты диссертации.

В первой главе рассматривается задача построения дио-фаптовых представлений для простых чисел специального вида. В §1.1 даны основные определения. Приведем некоторые из них.

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

(аи...,ап) е М&Зхl€N...гmeN

[Р(аи... ,ап,хи... ,хт) =0].

Эквивалентность (1) называется диофантовым представлением множества, Л4.

Для п-ок целых чисел также определяется понятие Z-диo-фантова представления, т.е. представления, аналогичного (1),

но в котором переменные X],... ,хт принимают целые значения.

В §1.2 формулируется основной результат данной главы: Теорема 1.1. Существуют экспоненциально-полиномиальные функции Т(р, к, /, х\,..., хд) и Q(k, l,xi,..., ¡rg), удовлетворяющие следующим условиям:

(1) при каждом фиксированном к функции V и Q полиномиально зависят от всех остальных переменных;

(2) для любого нечетного простого р не может не быть значений параметров к и I таких, что к < 3 и множество положительных значений Р(р, к, I, Х\,..., х9) при положительных целых значениях переменных ж1}... , хд есть бесконечное множество простых чисел;

(2') не может не быть значений параметров к и I таких, что к < 10896 и множество положительных значений Q(k, l,xi,...,x 8) при положителышх целых значениях переменных Xi,..., х% есть бесконечное множество простых чисел.

В §1.3 определяются множества 7Z(p, k, I) (параметры к и I - натуральные числа, р - простое число) и доказываются их свойства.

Лемма 1.2. Если # 7Z(jp, 1, к) = оо, то либо # 7Z(p, 1, к — 1) = со, либо при достаточно большом I множество 7Z(p, I, к) есть бесконечное множество простых чисел.

Лемма 1.3. Для каждого простого р не может не быть значений параметров к и I таких, что 7Z(p, I, к) есть бесконечное множество простых чисел, и к < 3 для'р ф 2, к < 10896 для р - 2.

В §1.4 построено диофантово представление последовательностей Фа{п): определенных следующим образом

Фа{0) = 0, =

фА{п + 1) = 2Афл{п) - фА{п - 1).

Применяемая техника является модификацией метода, предложенного Дж. Робинсон9, и содержит ряд технических улучшений, позволяющих понизить степень искомых многочленов. Лемма 1.8. Пусть А > 1, В > 1, С > 1, В четно, L - произвольное положительное число. Для того, чтобы С — фА{В), необходимо и достаточно, чтобы существовали i и j такие, что

DFI = □, F\Н + С, в < С,

где

D^(A2-1)C2 + 1, Е ^ 2iC2DL, F (А2 — 1 )Е2 + 1, G ^ -A + F{A + 1),

+ 2jC, I ^ (G2 - 1 )Я2 + 1.

Аналогичное утверждение имеет место и для нечетного В.

Диофантово представление последовательностей фА{п) затем используется при построении диофантовых представлений экспоненциального отношения Y = SB.

9Matijasevic Yu.V., Robinson J. Reduction of an arbitrary diophantine equation to one in 13 unknowns // Acta Arithmetica.— 1975.— Vol. 27.— P. 521-553.

В §1.5 доказывается теорема 1.1. При этом строятся дио-фаитовы представления множеств lZ(p,k,l). Для фиксированных к и I соответствующие многочлены зависят от 8 переменных при р = 2 (и их степень не превосходит 9 • 104) и от 9 переменных при р ф 2 (в этом случае их степень равна 1211).

Во второй главе рассматривается задача построения дио-фантовых представлений линейных рекуррентных последовательностей.

В §2.1 рассматриваются бесконечные в обе стороны цело-значные рекуррентные последовательности ап(Ьо,..., = ап, удовлетворяющие соотношению

ап+к = h-ian+k-i +----h Ь0ап, (2)

(где b¿ - целые числа, Ь0 = ±1) и начальным условиям

а0 — 1, a_i = а_2 = • • • = a_jfc+i = 0. (3)

Кроме того, предполагаем, что многочлен f(t) = th—bk-\tk~l — • • ■ — &о неприводим над полем Q. В лемме 2.1 доказано, что случай произвольных начальных данных сводится к частному случаю (3). В §2.1 также рассматриваются некоторые матричные конструкции, связанные с рекуррентными последовательностями. Положим

А{х0, XI,..., = Zx¡{Bl - ¿ bk4Bl-i),

1=0

где

В =

( о 1

о о

о о

¿=1

Ьх

о о

1 Ьк.

1 /

Показано, что однородный многочлен к-й степени Fb{xq, ..., хк-1) = det А(х0,..., xk„i)

(4)

(5)

обладает следующим свойством:

Ед(ап,ап+\,... ,ап+к-1) — ±1,

Рв{~ап, —1ап+ь • • • > = ±1-

Определение. Будем говорить, что соотношение

Гв(х0,х!,... ,Хк-1) = ±1 (7)

является характеристическим для последовательности (2)-(3), если все удовлетворяющие ему целочисленные наборы (хо, жь ..., Хк~\) исчерпываются следующими двумя сериями:

(жо,жь • • • ,Як-\) = {ап,ап+1, ■ • • ,ап+к-1),

(хо,х\,.. .,Хк_х) = {—ап, —ап+1,..., —а„+А;_1).

В §2.2 задача описания тех последовательностей, для которых (7) является характеристическим, сводится к изучению мультипликативных групп обратимых элементов (групп единиц) в кольцах целых алгебраических чисел. Доказывается Теорема 2.1. Рассмотрим последовательность ап, определенную согласно (2)-(3). Пусть многочлен /(£) = Ьк — -----¿о неприводим над полем С^, и пусть А - корень /. Определим многочлен Т7^ цепочкой равенств (4), (6). Для того чтобы (7) было характеристическим для последовательности а„, необходимо и достаточно, чтобы

(г[А]Г = <±Ап:пег>.

Эта теорема дает ответ на открытый вопрос 2.3 из монографии Ю. В. Матиясевича10. Из теоремы 2.1 вместе с теоремой

10Матиясевич Ю.В. Десятая проблема Гильберта / М.: Физ-матлит, 1993. - 224 с.

Дирихле о единицах следует, что (7) может быть характеристическим лишь для последовательностей второго, третьего и четвертого порядков (причем, в двух последних случаях на коэффициенты 6, накладываются дополнительные арифметические ограничения).

В §2.3 исследуются дальнейшие свойства единиц вещественного квадратичного поля. В теореме 2.2 вычисляется индекс подгруппы (±Ап|гс 6 Z) в группе (г[А])* в случае, когда А -обратимый элемент кольца целых вещественного квадратичного поля . Показано, что этот индекс равен 1 или 2.

В §2.4 рассматривается аналогичная задача в кольцах кубических алгебраических чисел отрицательного дискриминанта. Эта задача представляет и самостоятельный интерес. В теореме 2.5 находятся индексы подгрупп (±А" | п € Z) в мультипликативной группе (г[А])* Показано, что

[(г[А])+ : (±АП | га е г)] € { 1,2,3,4,5, 9}.

Доказательство теоремы 2.5 использует результат Б. Н. Делоне1^ количестве представлений 1 бинарной кубической формой отрицательного дискриминанта. В §2.4 также получены диофантовы представления следующих множеств:

М(Ь0,ЬиЬ2) =

{(Уо, Уи У-2) : эпег [У1 = ап_г(Ь0, Ьь Ь2), г = 0,1,2]} ,

М+(Ь0ММ) =

{{у^УиУч) : Зп е N [у1 = ап^(Ь0,ЬиЬ2), г = 0,1,2]}

Теорема 2.7. Пусть Ь(, = ±1, Ь\, Ьо таковы, что В = ЩЬ'^ + 46? - АЪф\ - 27&о - 18Ь0б1б2 < 0, Б ф -3, -16, -27. Пусть

11 Делоне В. Н., Фаддеев Д. К. Теория иррациональностей третьей степени // Труды математического института им. В. А. Стеклова.— 1940.— Т. 11.— 340 С.

последовательность ап = ап(Ьо, Ь\, 62) определена согласно (2)-(3), а множества М. и Л4+ определены выше.

1) Для того чтобы (уо? 2/15 У2) € Л4(6о, Ь], 62) необходимо и достаточно, чтобы существовали целые Х0,Х\,Х2 такие что выполнено (7) и

{А(уо,у1,У2)=В{(А(хо,х1,х2))ш} (8)

где матрицы В и А(хо, х\, хо) определены согласно (5) и (4), соответственно.

2) Для того чтобы (уо,УьУг) £ М+(Ь0,ЬиЬ2) необходимо и достаточно, чтобы существовали целые ж0, х% такие что выполнены (7) и (8) и

¿е1{(А2(уо,уиу2) - Е)(В2 - Е)} > О.

В §2.5 доказываются две редукционные леммы, переносящие редукционные леммы из 9 на алгебраические числа.

В §2.6 для последовательностей третьего порядка строятся диофантовы представления множеств {(п, ап) : п £ ГЧ}.

В §2.7 приведена новая конструкция диофантова представления экспоненциального отношения У = вв. Это представление опирается па следующую лемму.

Лемма 2.13. Пусть 5 > 1, п > 1 и Ь > (35)". Тогда

5„ = Га^Ы-5,0,1)'

[ а„(М,1)

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

Публикапди автора по теме диссертации

[1] Всемирнов М.А. Диофантовы представления простых чисел специального вида // Международная конференция: Современные проблемы теории чисел. Тезисы докладов. / Тула, 1993.— С. 32.

[2] Всемирнов М.А. Бесконечные множества простых чисел, допускающие диофантовы представления с восемью переменными // Записки научных семинаров ПОМ И.— 1995.— Т. 220.— С. 36-48.

[3] Всемирнов М.А. Диофантовы представления линейных рекуррентных последовательностей. I // Записки научных семинаров ПОМИ.— 1995,— Т. 227,— С. 52-60.

[4] Всемирнов М.А. О диофантовых представлениях линейных рекуррентных последовательностей // // Международная конференция: Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел. Тезисы докладов / Воронеж, 1995.— С. 36.

[5] Всемирнов М.А. Прямые методы построения диофантовых представлений линейных рекуррентных последовательностей // Материалы международной конференции и Чебы-шевских чтений, посвященных 175-летию со дня рождения П.Л.Чебышева / М.: издательство МГУ, 1996.— Т. 1,— С. 101-103.

[6] Vsemimov М.А. Diophantine representations of linear recurrent sequences of small orders // Number Theory conference: Abstracts / Eger (Hungary), 1996.— P. 40-41.