Что мы должны сделать?
Чтобы доказать теорему Джулии Робинсон, мы, очевидно, должны указать экспоненциальный многочлен R такой, что уравнение (10) разрешимо в натуральных числах относительно переменных x0, ..., xk тогда и только тогда, когда выполнено следующее условие:
| p — простое число. | (11) |
Это — пример условия на переменную p.
Приведём ещё несколько примеров условий на набор переменных
| λ1, ..., λn, x0, ..., xk . | (11') |
Если мы потребуем, чтобы набор чисел (11) удовлетворял системе уравнений вида
| Fi(λ1, ..., λn, x0, ..., xk ) = 0 (i = 1, ..., s), | (11″) |
или допустим словесное описание типа: «все λi — простые числа», или «λ1 — простое число, x0, ..., xk — чётные числа» и т.д., то тем самым мы из множества всех наборов (11') выделим некоторые, подчиняющиеся наложенному на них условию.
Мы не станем точно определять, условия какого вида являются для нас допустимыми. Приведённое описание примеров условий достаточно для оправдания того способа действий, которым в дальнейшем будем пользоваться.
В последующем изложении различаются переменные, называя некоторые из них параметрами, так что деление переменных на параметры и неизвестные является чисто условным.
Если все левые части системы уравнений (11″) являются экспоненциальными многочленами от λ1, ..., λn, x0, ..., xk , и решения этой системы ищутся в целых положительных числах, то такая система называется экспоненциально диофантовой; если Fi — обыкновенные многочлены, то система уравнений (11″) называется просто диофантовой.
Уравнение (10) является примером экспоненциально диофантова уравнения относительно переменных p, x0, ..., xk .
Мы будем говорить, что две системы условий, имеющие одни и те же параметры, эквивалентны друг другу относительно этих параметров, если множество тех значений параметров, при которых имеет решение одна из этих систем, совпадает со множеством тех значений параметров, при котором имеет решение и другая система. (Обратите внимание, что в этом определении ничего не говорится о связи значений неизвестных — для наших целей это неважно, эквивалентные в нашем понимании системы могут вообще не иметь общих неизвестных.)
Примером эквивалентных условий относительно параметра λ, могут служить неравенство
2n < λ < 2n+1
и равенство
λ = (2x0 + 1)·x1.
Ясно, что каждое из этих условий имеет решение тогда и только тогда, когда параметр λ принадлежит множеству чисел, не являющихся целыми степенями числа 2.
В этой терминологии наша цель формулируется так: найти экспоненциальный многочлен R(x0, ..., xk ), такой, что условие (10) эквивалентно условию (11) относительно параметра p.
Однако требование, чтобы параметр p стоял только в левой части равенства (10), является, как мы сейчас увидим, излишне жёстким.
Пусть удалось найти экспоненциальный многочлен Q(p, x1, ..., xk ), такой, что экспоненциально диофантово уравнение (условие на p, x1, ..., xk )
| Q(p, x1, ..., xk ) = 0 | (12) |
эквивалентно условию (11).
Положим
| R(x0, ..., xk ) = x0·(1 – Q 2(x0, ..., xk )). | (13) |
Лемма 1. Если экспоненциальные многочлены R и Q связаны соотношением (13), то уравнения (10) и (12) эквивалентны относительно параметра p.
Нам достаточно даже найти не уравнение, а хотя бы систему экспоненциально диофантовых уравнений
| (14) |
эквивалентную условию (11) относительно p.
Лемма 2. Если
| l | ||
| Q( p, x1, ... , xk ) = | ∑ | Qi2( p, x1, ... , xk ), |
| i=1 |
то система (14) эквивалентна уравнению (12).
Именно поиском системы экспоненциально диофантовых уравнений, эквивалентной условию (11), мы и будем заниматься.