4.5. Диофантово представление экспоненты

Воспользуемся теперь полученным в предыдущем разделе диофантовым представлением предиката Q(a, x, y, n) для построения диофантова представления экспоненты, т.е. предиката n

E(u, v, n) <-> u=vⁿ & v>=3.

Будем следовать рассуждениям Дж.Робинсон, относящимся еще к 1952 г. (она установила тогда, что предикат u=vⁿ "диофантово выразим" через предикат Q, но, разумеется, не имела диофантова представления для Q, полученного Ю.В.Матиясевичем 18 лет спустя).

Возьмем наше основополагающее равенство

(a+sqrt(a²-1))ⁿ = x_n(a)+y_n(a)sqrt(a² -1)

и обозначим v=a+sqrt(a²-1). Тогда слева будем иметь просто vⁿ , а справа вместо sqrt(a²-1 можем подставить v-a. Таким образом, уравнение

vⁿ - x_n(a) - y_n(a) (v - a) = 0

имеет корень v₁=a+sqrt(a²-1). Поскольку коэффициенты уравнения рациональны, то число v₂=a-sqrt(a²-1) также должно быть его корнем. С другой стороны, v₁, v₂ - корни квадратного уравнения

v² - 2av + 1 = 0.

Это значит, что трехчлен v²-2av+1 является делителем полинома vⁿ-x_n(a)-y_n(a)(v-a) в поле рациональных чисел. Более того, частное от этого деления должно быть полиномом с целыми коэффициентами (старший коэффициент делителя равен 1). Отсюда nследует, что если v - целое число, то vⁿ-x_n(a)-y_n(a)(v-a) делится на v²-2av+1. В этом и состоит утверждение следующей леммы Дж.Робинсон:

ЛЕММА 9. При a>=1 и n>=0

vⁿ = x_n(a)+y_n(a)(v - a) mod(v²-2av+1).

Упражнение 4.13. а) Проверьте, что лемма 9 действительно выполняется и для n=0, 1 (наше рассуждение проходит только при n>=2).

б) Проверьте, что на самом деле

vⁿ - x_n(a) - y_n(a)(v - a) = (v²-2av+1)(y₁v^n-2 + y₂v^n-3 + ... + y_n-2v + y_n-1).

(Это будет по существу новым доказательством леммы 9, уже без использования алгебры полиномов.)

Значение леммы 9 состоит в том, что она связывает произвольную степень v с хорошо изученными числами x_n(a), y_n(a), причем связь эта достигается посредством полиномов фиксированной степени (v-a, v²-2av+1). Отсюда легко получается диофантово представление для u=vⁿ.

В самом деле, мы должны исходить из произвольных u, v, n, и, накладывая на них диофантовы условия, добиться выполнения nравенства u=vⁿ. Возьмем сначала числа a, x, y и подчиним их условию

F₁: Q(a, x, y, n),

т.е. x=x_n(a) & y=y_n(a). Тогда по лемме 9

vⁿ = x+y(v-a) mod(v²-2av+1).

Чтобы как-то "привязать" число u к числу v , потребуем

F₂: u = x+y(v-a) mod(v²-2av+1).

Тогда

u = vⁿ mod(v²-2av+1).

Чтобы отсюда можно было заключить, что u=vⁿ, надо обеспечить достаточную величину модуля - он должен быть больше как u, так и vⁿ. Этого можно добиться, увеличивая свободный параметр a - тогда модуль будет расти (по абсолютному значению). В частности, условие

F₃: u < 2av-v²-1

обеспечивает половину требуемого. Но как (с помощью диофантовых условий) добиться неравенства vⁿ<2av-v²-1? Проще ли это по сравнению с обеспечением сразу равенства u=vⁿ? Проще, поскольку с помощью диофантовых условий мы умеем "заставить" величину расти со скоростью экспоненты, но не умеем пока "заставить" ее в точности следовать экспоненте. В самом деле, из леммы 2 мы знаем, что x_n(v)>=vⁿ, а обеспечить условие x_n(v)<2av-v²-1 очень легко. Вводим числа X, Y такие, что

F₄: Q(v, X, Y, n),

т.е. X=x_n(v) & Y=y_n(v), и требуем, чтобы число a было настолько велико, чтобы имело место

F₅: X < 2av -v² - 1.

Отсюда следует

vⁿ < x_n(v) = X < 2av-v²-1,

что совместно с F₃ и (1) влечет u=vⁿ.

Таким образом, мы сумели вывести u=vⁿ из условия

E axyXY (F₁&F₂&F₃&F₄&F₅). (2)

Одновременно мы обеспечили также неравенство v>=3 (оно содержится в F₄), т.е. из (2) выведена истинность предиката E(u, v, n).

Упражнение 4.14. а) Покажите, как преобразовать (2) в диофантово представление вида (E)P=0. Оцените число кванторов E, степень полинома P и сумму модулей его коэффициентов.

б) Чтобы завершить доказательство, покажите, что (2) вытекает из E(u, v, n), т.е. u=vⁿ & v>=3.

Итак, следуя работам Ю.В.Матиясевича и Дж.Робинсон, мы получили для предиката u=vⁿ & v>=3 диофантово представление вида

(Ez₁...Ez_k) P(u, v, n, z₁, ..., z_k) = 0.

Полагая v=3 и добавив квантор En, мы получаем диофантово представление предиката:

"u является степенью числа 3".

Существует, таким образом, диофантово уравнение

P(u, v₁, ..., v_s)=0

с параметром u, которое имеет решения в натуральных числах, если и только если u имеет вид 3ⁿ. Этот результат оказался неожиданным для многих специалистов по теории чисел.

4.6. Диофантовы представления числа сочетаний и факториала

Еще в 1952 г. Дж.Робинсон показала, что предикаты x=C_y^z, x=z! диофантово выразимы через экспоненту. Теперь, имея диофантово представление экспоненты, можно построить диофантовы представления и этих предикатов.

Метод Дж.Робинсон, относящийся к сочетаниям, был усовершенствован Ю.В.Матиясевичем. Будем исходить из формулы бинома Ньютона

(1 + p)^y = sum {C_y^z p^z | for z =0 to y} (1)

При p=1 мы имели бы

2^y = sum {C_y^z | for z =0 to y},

таким образом, C_y^z <= 2^y для всех z<=y. Поэтому если p - большое натуральное число, например, p=3^y , то C_y^z < p для всех z<=y, и мы можем смотреть на числа C_y^z как на цифры в системе счисления с основанием p. Сумма в (1) представляет тогда p-ичную запись числа (1+p)^y. Если мы хотим теперь наложить на число x условие, приводящее к равенству x= C_y^z, надо потребовать, чтобы x было цифрой при степени p^z в записи числа (1+p)^y , т.е.

x < p & (1+p)^y = u + xp^z + vp^z+1,

где

u = sum {C_yⁱ pⁱ | for i=0 to z-1}, vp^z+1 = sum {C_yⁱ pⁱ | for i=z+1 to y}

Число v однозначно определяется тем, что оно стоит у множителя p^z+1 (как частное от деления (1+p)^y на p^z+1). Для выделения же u (не обращаясь к формуле, содержащей C_yⁱ) мы должны потребовать, чтобы имело место неравенство u<p^z (тогда u определяется однозначно как остаток от деления (1+p)^y на p^z). В самом деле (учитывая, что C_yⁱ < p),

sum {C_yⁱ pⁱ | for i=0 to z-1} <= (p-1) sum {C_yⁱ | for i=0 to z-1} = (p-1)(p^z-1)/(p-1) < p^z.

Таким образом, если x=C_y^z & z<=y, то

Epuv (p=3^y & (1+p)^y = u + xp^z + vp^z+1 & x<p & u<p^z). (2)

Покажем теперь, что из z<=y вместе с (2) вытекает x=C_y^z. Согласно (2) число u является остатком от деления (1+p)^y на p^z. Согласно же (1) этот остаток выражается также суммой

sum {C_yⁱ pⁱ | for i=0 to z-1},

т.е. u равно этой сумме. Рассмотрим тогда число

q = ((1+p)^y - u)/p^z = x + vp.

Так как x<p, то x является остатком от деления q на p. С другой стороны,

q = C_y^z + sum {C_yⁱ p^i-z | for i=z+1 to y},

где C_y^z <= 2^y < p и большая сумма делится на p. Это значит, что C_y^z также является остатком от деления q на p, т.е. x=C_y^z, что и yтребовалось.

Упражнение 4.15. Покажите, как преобразовать z<=y & (2) в диофантово представление вида (E)P=0. Оцените число кванторов E, степень полинома P и сумму модулей его коэффициентов.

Займемся, наконец, предикатом x=z!. Рассуждения Дж.Робинсон исходят из следующей идеи. Как известно,

C_y^z = y(y-1)...(y-z+1)/z!.

Если y значительно больше z, то числитель незначительно отличается от y^z, т.е. z! ~ y^z/C_y^z. Чтобы оценить необходимую величину y, изучим частное y^z/C_y^z подробнее:

y^z/C_y^z = z! (y/y) (y/y-1) ... (y/y-z+1).

Отсюда вытекает, что

z! <= y^z/C_y^z <= z! (y/y-z)^z = z! (1+z/y-z)^z.

Если возьмем y=z+zt, то

z! <= y^z/C_y^z <= z! (1+1/t)^z = z! (1+ sum{ C_zⁱ t^-i | for i=1 to z}.

Учитывая, что C_zⁱ <=2^z, возьмем t=2^zu, тогда

z! <= y^z/C_y^z <= z! (1+z/u).

Наконец, взяв u=2zz^z, получаем (поскольку z!<=z ^z)

z! <= y^z/C_y^z <= z! + 1/2.

Таким образом, если y=z+2z² 2^z z^z, то

z! = [y^z/C_y^z ],

где [ ] - символ целой части (наибольшее целое, не превосходящее число в скобках).

Упражнение 4.16. Покажите, как отсюда получить для предиката x=z! диофантово представление вида (E)P=0. Оцените число кванторов E, степень полинома P и сумму модулей его коэффициентов.

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

x in A <-> (Ez₁...Ez_n) P(x, z₁, ..., z_n) = 0

для некоторого полинома P с целыми коэффициентами, представимо как множество всех положительных значений некоторого (другого) полинома Q (также с целыми коэффициентами).

Упражнение 4.17. Покажите, что можно взять Q = x (1 - P²).

Упражнение 4.18. Исходя из теоремы Вильсона (см. А.А.Бухштаб [1966]):

"x - простое число" <-> x>1 & x² делит x!+x,

постройте диофантово представление для множества всех простых чисел. Оцените, как всегда, число кванторов и степень полинома P под ними. Полином Q = x (1 - P²) представляет множество всех простых чисел как множество всех своих положительных значений. Таким образом, "формула для простых чисел", о невозможности которой все время говорили специалисты по теории чисел, в определенном смысле все-таки существует.

4.7. Устранение ограниченного квантора всеобщности

Теперь мы подошли к своей конечной цели - научиться преобразовывать формулы вида

(Ay<=t)(Ez₁...Ez_n) P(a₁, ..., a_m, y, z₁, ..., z_n) = 0 (1)

(P - полином с целыми коэффициентами, t - полином первой степени с натуральными коэффициентами от a₁, a₂, ..., a_m) в диофантовы представления вида

(Ev₁...Ev_k) Q(a₁, ..., a_m, v₁, ..., v_k) = 0.

Именно этого не хватило нам в разделе 4.2 для преобразования формул, представляющих вычислимые функции, в диофантовы представления. Наши рассуждения будут следовать в основном по пути, намеченному в 1960-1961 гг. М.Дэвисом, Х.Патнэмом и Дж.Робинсон. Некоторые усовершенствования были внесены (уже после 1970 г.) совместно Ю.В.Матиясевичем и Дж.Робинсон.

При фиксированных a₁, ..., a_m формула (1) действительно представляет собой утверждение о существовании (несмотря на присутствие квантора всеобщности) - о существовании (t+1)n чисел (по n на каждое значение y = 0, 1, ..., t). Введем специальные обозначения для этих чисел:

y=0; z₁⁽⁰⁾, ..., z_n⁽⁰⁾,

y=1; z₁⁽¹⁾, ..., z_n⁽¹⁾,

...

y=t; z₁^(t), ..., z _n^(t),

Избавиться от квантора A<= можно, закодировав эту таблицу ограниченным (не зависящим от t) числом натуральных чисел. Можно попытаться, например, закодировать одним числом каждый из n столбцов таблицы. Для кодирования можно использовать китайскую теорему об остатках. Если бы имелись попарно взаимно простые числа u₀, u₁, ..., u_z, то по этой теореме можно было бы подобрать числа w₁, ..., w_n такие, чтобы всякое z_i^(y) оказалось остатком от деления w_i на u_y, т.е.

z_i^(y) <u_y & w_i = z_i^(y) mod u_y (2)

для всех y<=t и i=1, ..., n (для этого делители u_y должны быть, разумеется, достаточно большими).

Но если все это будет сделано, какие условия надо наложить на w₁, ..., w_n, чтобы остатки z_i^(y) удовлетворяли уравнению (1)? Выбор у нас небольшой - попытаемся подставить числа w₁, ..., w_n в уравнение P=0 вместо чисел z_i^(y). Вместо y подставим iнеопределенное пока число x. Что можно сказать о значении P(a₁, ..., a_m, x, w₁, ..., w_n)? Если в дополнение к (2) мы потребуем еще, чтобы для всех y = 0, 1, ..., t имело место

x = y mod u_y, (3)

то можно будет утверждать, что

P(a₁, ..., a_m, x, w₁, ..., w_n) = P(a₁, ...,a_m, y, z₁^(y), ..., z_n^(y)) mod u_y.

Так как значение P справа равно нулю, то получаем

P(a₁, ..., a_m, x, w₁, ..., w_n) = 0 mod u_y

для всех y<=t, т.е. значение слева делится на все числа u_y. Но эти числа попарно взаимно просты, поэтому значение P должно делиться и на их произведение:

P(a₁, ..., a_m, x, w₁, ..., w_n) = 0 mod u₀u₁...u_z. (4)

Посмотрим теперь на (4) с другой стороны - не как на следствие каких-то предположений, а как на условие, налагаемое на числа w₁, ... ,w_n. Тогда если числа z_i^(y) - остатки от деления w_i на u_y, то согласно (1) и (2) должно иметь место

P(a₁, ..., a_m, y, z₁^(y), ..., z_n^(y)) = 0 mod u_y.

Чтобы получить отсюда не только = 0 mod u_y, но и = 0, значение слева должно было меньше модуля u_y. Грубую оценку значения полинома P можно получить следующим образом. Через z обозначим число, которое больше всех чисел z_i^(y), через N - степень полинома P, через M - сумму модулей его коэффициентов. Тогда

|P(a₁, ..., a_m, y, z₁^(y), ..., z_n^(y))| <= M ((a₁+1)...(a_m+1)(t+1)(z+1))^N.

Упражнение 4.19. Убедитесь, что это действительно так.

Выражение справа обозначим через T. Чтобы интересующие нас значения полинома P оказались меньше всех u_y, мы должны yпотребовать:

а) чтобы остаток от деления чисел w_i на u_y всегда был i yменьше z,

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

u_y = 1 + T t! (1+y),

тем более что диофантово представление факториала мы уже имеем. К сожалению, в таком случае придется проводить специальную работу, чтобы получить диофантово представление для произведения u₀u₁...u_z, т.е. для модуля в сравнении (4). В свое время М.Дэвис, Х.Патнэм и Дж.Робинсон приблизительно так и сделали.

Более удобным оказывается, однако, другой генератор чисел u_y, предложенный позднее Ю.В.Матиясевичем и Дж.Робинсон. Представим число C_v^t+1(при условии t+1<=v) следующим образом:

C_v^{t+1 =} v(v-1)...(v-t) / (t+1)! = ((v+1)/1-1) ((v+1)/2-1) ... ((v+1)/(t+1)-1).

Если потребовать, чтобы v+1 делилось на (t+1)!, то все сомножители окажутся целыми числами. Если потребовать еще больше - чтобы v+1 делилось на ((t+1)!)^z , то эти сомножители окажутся взаимно простыми.

Упражнение 4.20. Проверьте, что это действительно так (если d - общий делитель i-го и j-го сомножителей, рассмотрите их разность).

Итак, потребуем, чтобы v+1 делилось на ((t+1)!)^z, и возьмем

u_y = (v+1) / (y+1) - 1.

Тогда с произведением u₀u₁...u_z никаких проблем не будет - оно равно C_v^t+1, а диофантово представление для числа сочетаний мы строить умеем. Теперь мы можем объединить все свои условия (res(a, b) означает "остаток от деления a на b"):

G₁: P(a₁, ..., a_m, x, w₁, ..., w_n) = 0 mod C_v^t+1,

G₂: (Ay<=t) x = y mod ((v+1)/(y+1)-1)

G_3i: (Ay<=t) res (w_i, (v+1)/(y+1)-1) < z,

G₄: (v+1)/(y+1)-1 > M((a₁+1)...(a_m+1)(t+1)(z+1))^N,

G₅: v+1 делится на ((t+1)!)^z.

Упражнение 4.21. Покажите, что (1) равносильно формуле

Ex Ev Ez Ew₁ ... Ew_n G₁ & G₂ & G₃₁ & ... & G_3n & G₄ & G₅.

Не забудьте воспользоваться китайской теоремой об остатках при построении чисел x, w₁, ...,w_n.

К сожалению, последнюю формулу нельзя сразу преобразовать в диофантово представление. Мешают этому кванторы Ay<=t в условиях G₂, G_3i. Однако в отличие от Ay<=t в исходной формуле (1), здесь этот квантор стоит не над произвольным диофантовым представлением, а над конкретными и достаточно простыми преди- катами. Можно надеяться, что эта простота позволит избавиться от кванторов Ay<=t полностью.

Сначала заметим, что если взять v=x, то условие G₂ будет выполнено автоматически,т.е. в нашем списке требований его можно опустить. В самом деле,

(x+1)/(y+1)-1 = (x-y)/(y+1)

является целым числом, которое делит x-y (частное равно y+1), т.е.

x = y mod ((x+1)/(y+1)-1).

Займемся теперь условиями G_3i. Если остаток от деления w_i на (x+1)/(y+1)-1 меньше z, то одно из чисел w_i, w_i-1, ..., w_i-z+1 делится на (x+1)/(y+1)-1, т.е. на это число делится и произведение

w_i(w_i-1)...(w_i-z+1) = w_i! / (w_i-z)!.

Поскольку числа (x+1)/(y+1)-1 для различных y попарно взаимно просты, то условие

Ay<=t ( (x+1)/(y+1)-1 делит w_i! / (w_i-z)! )

равносильно условию

G_3i': C_x^t+1 делит w_i! / (w_i-z)!

(т.е. исчезает квантор Ay<=t). Это тем более приятно, что мы умеем строить диофантово представление факториала и для нас не составит труда записать G_3i' диофантовыми средствами. Но, к сожалению, G_3i' не равносильно G_3i !. Из G_3i вытекает G_3i' (как мы только что убедились), однако из G_3i' не вытекает G_3i - если произведение делится на некоторое число, нет гарантии, что на это число будет делиться один из сомножителей. Что же тогда можно гарантировать?

Если число R делит прозведение P₁P₂.. P_k, то R можно разложить в прозведение R₁R₂...R_k , где каждое R_i делит свое P_i. Если R_i - наибольший из сомножителей R, то R_i^k >= R и R_i >= k-root(R). Таким образом, если произведение P₁P₂...P_k делится на R, можно утверждать только, что R и один из сомножителей P_i имеют общий делитель >= k-root(R). Большего гарантировать нельзя.

Поэтому если вместо условий G_3i возьмем (с одной стороны, более удобные) условия G_3i', то можно гарантировать только, что некоторое w_i - j (где 0<=j<=z) имеет общий делитель с числом

u_y = (x+1) / (y+1) - 1,

который по величине >= z-root(u_y). К счастью, этого оказывается yдостаточно. В самом деле, "пройдем" следующим образом от w₁ до w_n (при фиксированном y<=t). При некотором z₁^(y) < z разность w₁ - z₁^(y) делится на некоторый делитель S₁ >= z-root(u_y) числа u_y. Далее, при некотором z₂^(y) < z разность w₂ - z₂^(y) делится на некоторый делитель S₂ >= z-root(S₁) числа S₁, т.е. w₂ - z₂^(y) делится на делитель S₂ >= z²-root(u_y) числа u_y. И так далее, до разности w_n - z_n^(y), которая делится на делитель S_n >= zⁿ-root(u_y) числа u_y (здесь также z_n^(y) < z).

Подводя итог, заключаем, что для всех i=1, ..., n

w_i = z_i^(y) mod S_n,

где S_n делит u_y (а следовательно, и C_i^t+1) и S_n >= zⁿ-root(u_y). По условию G₁ имеем

P(a₁, ..., a_m, x, w₁, ..., w_n) = 0 mod S_n,

Отсюда вытекает, что

P(a₁, ..., a_m, y, z₁^(y), ..., z_n^(y)) = 0 mod S_n.

причем все z_i^(y) < z. Значение слева должно будет равняться нулю, если оно будет (по абсолютному значению) меньше модуля S_n, т.е. если zⁿ-root(u_y) будет больше

T = M((a₁+1)...(a_m+1)(t+1)(z+1))^N.

Это значит, что условие G₄ можно заменить условием

G₄': (x+1) / (t+1) - 1 > T**z**n,

где ** означает возведение в степень.

Упражнение 4.22. Проверьте еще раз, что (1) действительно равносильно формуле

Ex Ev Ez Ew₁ ... Ew_n G₁' & G₃₁'& ... & G_3n' & G₄' & G₅'.

где G₁', G₅' отличаются от G₁, G₅ тем, что вместо v подставлено x. Покажите, как преобразовать эту последнюю формулу в диофантово представление.

Тем самым задача устранения A<= решена до конца.