Ц е й т И п Г. С. s: "

1 Ассоциативное исчисление с неразрешимой нроблемоп эквивалентности.- Тр. мат. ин-та АН СССР им. В. А. Стеклова, 52. М.: Изд-во АН СССР, 1!>58, с. 172-189.

2. Изложение теории алгоритмов на языке бинарных отношенип.--В кн.: 5-й Всес. коллоквиум но общей алгебре: Резюме сообщений и докладов. Новосибирск: Ин-т математики, 1963, с. 55.

Ч ё р ч (Church А.) , , .

1 An unsolvable problem of elementary number theory.- Amer. J. Math., 193C, 58, p. 345-363 .

2. A note on the Entscheidungsproblem.- J. Symbolic Logic, 1930, 1, p. 40-41. Correction.- J. Symbolic Logic, 1936, 1, p. 101- 102.

3. The Calculi of Lambda-conversion.- Princeton (N. J.), 1941. Шеннон (Shannon C.)

1. A universal Turing machine with two internal states.- In: Auto- mata Studies. Princeton, 1956. [Русский перевод: ni e н н о н К. Универсальная машпна Тьюринга с двумя внутренними состояниями.- В кн.: Автоматы. М.: ИЛ, 1956.]

Шепердсон пСтургис (Shepherdson J. С, Sturgis Н. Е.)

1 Computability of recursive function.- J. Assoc. Сотр. Mach., 1963, 4, p. 217-255.

Ш M e л ё в a (Szmieleлv W.) , ,пск

1 Elementary properties of Abelian groups.- Fundam. math., 1955, 41, № 2, p. 203-271.

ПРИЛОЖЕНИЕ

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

Д. А. ЗАХАРОВ

1. Основная теорема. Известно, что каждое диофантово множество и предикат являются рекурсивно перечислимыми (с. 325). В начале пятидесятых годов, по-видимому впервые М. Девисом, была высказана гипотеза, что верно и обратное, т. е. каждое рекурсивно перечислимое множество и предикат диофантовы. В 1961 г. Девис, Патнем и Ю.Робинсон [1] *) доказали, что каждое рекурсивно перечислимое множество и предикат показательно диофантовы (последняя reopesia § 16).

Пусть а е Af 32 (Р (а, у, z, у") = 0), где Р (а, у, z, и) - многочлен с целыми коэффициентами. Тогда

а е Ж" 44 (Byzu) {Р (а, у, z, и) = О & и = у).

Если бы удалось доказать, что отношение и - у диофантово, скажем,

U = (Эуу у.) 2, i;,, Уд, . . .,- v) =0),

где Q - многочлен с целыми коэффициентами, то мы nerio бы установили, что М диофантово.

Ясно, как обобщить этот пример. В 1952 г. Ю. Р о б и н с о н 2] *) получила зультат; если существует диофантово oinomemie D \ [Уии) (D (и, v)rv u), (Vk)(3uv) (D {и, v) & < v),

следующий pe-u, v) такое, что

то отношение z = диофантово.

Говорят, что отношение D {и, v) имеет экспоненциальный рост, если оно удовлетворяет условпям (1) п (2).

Первый пример диофантова отношения экспоненциального роста был указан Ю. В. Матпясевпчем в 1970 г. в работе [1*]. Таким будет отношение v = ф,и, где сро = О, = 1, ф„, = ф„, + ф„

(ф„ -известная последовательность Фибоначчи). Заметим, что 2"-<Ф2и <3", и>0. Так была установлена

Основная теорема ([1*], [2*]). Всякий рекурсивно пе-речислимый предикат диофантов. Всякое рекурсивно перечислимое множество диофантово.

Такт! образом, класс диофантовых предпкатов совпадает с классом рекурсивно иеречислньплх предпкатов и класс дпофантовых

*) См. список литературы к основному тексту книги.- Примеч. ред.

множеств совпадает с классом рекурсивно перечислпмых множеств.

Наше приложение имеет весьма скролшую цель - к материалу книги добавить минимальное число фактов, необходимых для доказательства основной теоремы, точнее, для доказательства дпофантовости отношения Z = хУ. В п. 2 мы изчаем уравнения Пелля специального типа и свойства решений этих уравнений, в п. 3 с по-мош,ыо одного диофантова отношешш находим диофантово представление для отношения у = х", в п. 4 приводим некоторые следствия и дополнения.

2. Специальные уравнения Пелля. Переходим к изучению уравнений Пелля вида

2;2 = 1 d = а2 1,

N, а>1.

Наша блгокайшая цель - описать все решения уравнения (*) в N ш установить ряд свойств этих решений.

Так как l/d - число иррациональное, то для всякого > О однозначно определяются натуральные числа Ха («) и фа {«) такие, что

Отсюда, используя биномиальное разложение, получаем

i четно

i нечетно

Очевидно наряду с (1) имеем такн{с

Дополнительно определяем

Ху {)= 1> («) = п.

(3)

При фиксированном а иногда будем писать хп вместо Ха (") " Уп вместо (п).

Предложение 1 (описание решений). Совокупность всех решений уравнения (•) в N описывается последовательностью (Ха (я), («)), ге = О, 1, 2, . . . Доказательство. Перемножая сЬотвётственно .Чевые,. и правые частп равенств (1) и (3), ползчаем " , " . 1

Х(ге)--Й1,2(,г)= (а2й)?-= 1.;;-. :Г;

Таким образом, (Хд (ге), а {п)) ость решенпе ypaBnennW (*). Чтобы доказать, что дротах решений в 2Ууравненпе (*) не имеет, потребуются две лешш.

Лемма 1. Не существует никаких целых чисел х, у, удовлетворяющих уравнению (*) и таких, что \ < х -\- г < а -}- l/ d.

Допустим, что такие х, у cjTnecTBjTOT. Тогда

(X -J- у\И) {х - y]fl) = (fl -Ь /йУ (а - А5)" = 1, .

В исходном неравенстве сначала перейдем к обратным числам, затем умножим все части на -1. Тогда получим - 1 < -х -f- yY <. < -а -j- Yd. Складывая это неравенство почленно с исходным, найдем, что О < 2yfd < 2\fd и О < i/ < 1. Получаем противоречие, так как у - целое число.

Лемма 2. Пусть х, у и х, у - це.гые числа, удовлетворяющие уравнению (*), а ж", у" определяются из равенства х" -\-

+ yYd= {х -}- yYd) {х + yYd). Тогда (х", у") - тоже решение уравнения (*).

Из определения х", у" имеем также х" - y"Yd = {х - yYi) • • {х - yYd). Перемножая соответственно левые и правые части равенств, получим

Х" - dy" = (х2 - dy) (Х - dy) = 1.

njCTb теперь (х, у) - решение уравнения (*) в N. Если {х, у) = (1, 0), то в (1) берем = 0. Полагаем далее х, г/ > 0. Тогда X -f- yYd > 1. Так как а -(- > 1, то найдется к такое, что

(а + Yd) <x + yYd<(a+ Yd)- Если имеем равенство, то (х, у) = (xjt, ут) в силу (1). Если же (а +/й)" <+ г 5"< (fl-f-/1)+1,

то, умножая все части неравенства на {а - Y) = x-j; - yYd, получим

i<{x-\-y]/d) (х„ - yjYd) < fl -Ь Yd,

что противоречит леммам 1 и 2. Итак, (х, у) = (Ха (), фа ())-

Далее (Yq (п), iba (п)) будем называть ге-м решением уравнения (*) в Дг.

Предложеппе 2 (формулы сложения). Для О т п X{n±m)=x{n)j(a{m)±%(n)%{m)d,

0]) (ге ± m) = ± Ха (п) % (т) + Ха (т) % (п).

Пишем Хп вместо у а (ге), уп вместо -фа (п), а фиксировано. В силу (1) имеем

+ Уп V= + /)", х, -f j/iAd = (fl +1/)".

Тогда

Уп!/) i-m + ymVd) = {a + Yd)" = -n.m+lnVd.

Отсюда следтот формулы (5) для ге -Ь т.

Пусть т-\- q = п и a;„-f ynY d = {х -Ь jg/5) (.г, -f--г ymYd)- Уьшожая обе части на х - y,nYd п читывая, что .г- dy= 1, получим

9 -Ь г/дТ/ = К + Уп V) (m - УщУ) Это дает формулы (5) для п - т.

В частности,

ПредложениеЗ (рекуррентные соотношения). Имеем 1а (0) = 1, га (1) = а, Ха {п + 1) = 2аХа (п) - Ха {п - 1), (7) % (0) = О, % (1) = 1, Ia (п + 1) = 2а% (п) -%(п- 1), а также

Ха {г + 1) = аха («) + dipa («)> >!« ( + 1) = Ха (") + аа («)• (8)

Для проверки (7) достаточно установить равенство

(я + l/l)"+i= 2а {а + Vdf - {а + Vf.

Формулы (8) немедленно следуют пз формул (5) для д + l• Пpeдлoжeниe4 (о сравнениях). Если я > О, Ь > О и а Ъ mod т, то

Ха {п) = Хь (I) mod т, \\>а (п) = % («) mod m.

5 частности, если Ь = 1 mod ni, то (ге) = mod т.

Утверждения прямо следуют из формул (2) для Ха (п) и \ра ("), из обычных свойств сравнений и из (4).

Дальше нас более будут интересовать числа -фц (ге). Рассмотрим ряд дополнительных свойств этих чисел.

Предложение 5 (неравенства и оценки). Имеют место следующие утверждения:

1) Для а 1 1)а (п) монотонно возрастают и ге г))а (п).

2) Если 1 < а < fa, mo (re) <а)ь (гг).

3) Для а > 1 ц ге О имеем

(2я- 1)«<а,„(и+ 1)<(2я)«. (9)

Первые два утверждения следуют пз (8) н (2). Доказательство третьего утверждения ведем индукцией по п. Для ге = О, 1 пмеемiJJq (1) = l,i)a (2) = 2я п неравенства очевидны. Еслп1)а (ге + !)< (2а)",

то а (п + 2) < 2а\а (гг + 1) < (2я)""" в силу (7). Аналогично, умножая левто часть (9) на 2а - 1, получпм

(2а - !)"«< (2я - 1) \ (ге + 1) = 2а% (ге + 1) -il, (ге + 1) <

<("+2),

так как i)a (д + 1) > Io {)-

Предложение 6 (первая передаточная лемма). Для я > О имеем

(10) (11)

11Ъ (т) \\а(п) т\ ге,

(") I to (") "ta («) I п-

Берем гег, > О, ге > О п временно для краткости записи обозна-4mi tIq (s) через у, а %а (s) через Zj. Тогда в силу (5)

УтН = V/ + /Jm = mJ/; od у.

Так как (жт, Ут) = 1 (эти числа удовлетворяют уравнению Пелля

(*)), то

Ут\Ут.1Уш\=тУ1УтУг

Если ге = mg + Г, О < Г < т, ТО отсюда у г/„ -О г/ у. Однако, при О < г < имеем О <Уг<Ут Ут Ут- Поэтому ут \ynni\n. Тем самым (10) доказано.

Далее, пусть у„. Тогда m ] ге и ге = т.к. В силу (1)

Отсюда

!n = Jm = 4"J/mm°d4. (12)

Теперь из (12) и из взаимной простоты х. и ут получаем

Ут\УпУт\шУтУт\

Т. е. А = у,„д, п= тк = туд и лгГт ?г. Иа (12) при ге =ту выводим I i/jj. Тем самым (И) установлено.

В частности, отсюда получаем

Уm\УnУm\ Ут\У:

(13)

Предложение 7 (вторая передаточная лемма). Пусть а > 1 g > 0. Тогда, если тро (г) = грц (у) mod у а (д), гего г = / или г = -] mod 2д.

Пусть опять Xs = Ха (*)i is = "Фа («)• Из (G) получаем

-2, = 4 + "4 = 4 + (4 -1) = 24 - 1, У,,= 2хи,. Отсюда в силу (5) получаем

г/2,±,„ S ± Хэдг/„, + = + ?™ mod

У<,±гп = ~У2±т=±Ут """q.

Это означает, что последовательность j/o, у, . . ., у, . . . по mod Xq периодична с длиной периода 4д. Для гег < g имеем по mod Xq

Ущт УЯ+т- Ут Угя-т - Ут yig-m- Ут

Покажем, что чпсла - yq, . . ., - у, Уо, уу, . . ., yq попарно не-cpaBHHinj по mod Хд (кроме случая я = 2, g = 1)*).

Для я > 2 имеем iy\ < (я - 1) + 1 = п г/, < Xq/2. Поэтому указанные числа принадлежат полной системе абсолютно наименьших вычетов по mod xq п, следовательно, попарно несравним по mod xq.

Для я = 2, g > 1 из рекфрентных соотношений (8) получаем

*) При я = 2, g = 1 в сплу (7) пмеем xq = 2, y,t = О, и y-is+i = = lmod 2, а тогда yi =у] mod 2 влечет i = ] mod 2.