Экспоненциальный многочлен Джулии Робинсон

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

a₁x₁ + a₂x₂ + ... + a_k x_k + b,

где a₁, a₂, ..., a_k , b — целые неотрицательные числа.

Простейшими примерами экспоненциальных многочленов от переменной n являются правые части формул (8) и (9).

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

В 1952 году американский математик Джулия Робинсон опубликовала следующий замечательный результат:

Существует экспоненциальный многочлен R(x₀, ..., x_k ), такой, что

• любое его положительное значение при целых положительных значениях переменных является простым числом;

• любое простое число можно представить в таком виде.

В результате получается такая «формула для простых чисел»:

p = R(x0, ..., xk ).

(10)

Эта формула замечательна вот чем. Во-первых, в неё входят только целые числа, и потому, в отличие от формул Миллса, Райта и им подобных, формула Джулии Робинсон может быть выписана явно. Во-вторых, она задаёт все простые числа, а не только какие-то избранные из них, в отличие от всех рассмотренных выше формул. В-третьих, хотя формула (10) задаёт и не только простые числа, у нас есть очень простой способ отсеивания «лишних» чисел: каждое не простое значение R при целых положительных значениях неизвестных не превосходит нуля. Этим формула Джулии Робинсон выгодно отличается от формул (8) и (9), а также и от только что рассмотренных полиномиальных формул .

Доказательство Джулии Робинсон совершенно элементарно. Ниже излагаются его основные идеи.

Что мы должны сделать?

Чтобы доказать теорему Джулии Робинсон, мы, очевидно, должны указать экспоненциальный многочлен R такой, что уравнение (10) разрешимо в натуральных числах относительно переменных x₀, ..., x_k тогда и только тогда, когда выполнено следующее условие:

p — простое число.

(11)

Это — пример условия на переменную p.

Приведём ещё несколько примеров условий на набор переменных

λ1, ..., λn, x0, ..., xk .

(11')

Если мы потребуем, чтобы набор чисел (11) удовлетворял системе уравнений вида

Fi(λ1, ..., λn, x0, ..., xk ) = 0     (i = 1, ..., s),

(11″)

или допустим словесное описание типа: «все λ_i — простые числа», или «λ₁ — простое число, x₀, ..., x_k — чётные числа» и т.д., то тем самым мы из множества всех наборов (11') выделим некоторые, подчиняющиеся наложенному на них  условию.

Мы не станем точно определять, условия какого вида являются для нас допустимыми. Приведённое описание примеров условий достаточно для оправдания того способа действий, которым в дальнейшем будем пользоваться.

В последующем изложении различаются переменные, называя некоторые из них параметрами, так что деление переменных на параметры и неизвестные является чисто условным.

Если все левые части системы уравнений (11″) являются экспоненциальными многочленами от λ₁, ..., λ_n, x₀, ..., x_k , и решения этой системы ищутся в целых положительных числах, то такая система называется экспоненциально диофантовой; если F_i — обыкновенные многочлены, то система уравнений (11″) называется просто диофантовой.

Уравнение (10) является примером экспоненциально диофантова уравнения относительно переменных p, x₀, ..., x_k .

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

Примером эквивалентных условий относительно параметра λ, могут служить неравенство

2ⁿ < λ < 2ⁿ⁺¹

и равенство

λ = (2x₀ + 1)·x₁.

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

В этой терминологии наша цель формулируется так: найти экспоненциальный многочлен R(x₀, ..., x_k ), такой, что условие (10) эквивалентно условию (11) относительно параметра p.

Однако требование, чтобы параметр p стоял только в левой части равенства (10), является, как мы сейчас увидим, излишне жёстким.

Пусть удалось найти экспоненциальный многочлен Q(p, x₁, ..., x_k ), такой, что экспоненциально диофантово уравнение (условие на p, x₁, ..., x_k )

Q(p, x1, ..., xk ) = 0

(12)

эквивалентно условию (11).

Положим

R(x0, ..., xk ) = x0·(1 – Q^2(x0, ..., xk )).

(13)

Лемма 1. Если экспоненциальные многочлены R и Q связаны соотношением (13), то уравнения (10) и (12) эквивалентны относительно параметра  p.

Нам достаточно даже найти не уравнение, а хотя бы систему экспоненциально диофантовых уравнений

ì í î  Q1( p, x1, ... , xk ) = 0,  ·  ·  ·  ·  ·  ·  ·  ·  ·  ·   Ql( p, x1, ... , xk ) = 0,

(14)

эквивалентную условию (11) относительно p.

Лемма 2. Если

	l
Q( p, x1, ... , xk ) =	∑	Qi^2( p, x1, ... , xk ),
	i=1

то система (14) эквивалентна уравнению (12).

Именно поиском системы экспоненциально диофантовых уравнений, эквивалентной условию (11), мы и будем заниматься.