Программирование, 2021, № 1, стр. 39-44

1. ВВЕДЕНИЕ

В современных системах компьютерной алгебры (таких, как Mathematica, Maple, PARI/GP, SageMath и др.) реализовано только небольшое число известных алгоритмов для решения диофантовых уравнений в целых числах. Как правило, речь идет о системах линейных уравнений с произвольным числом неизвестных, квадратных уравнениях с двумя неизвестными, а также кубических уравнений Туэ (но при некоторых дополнительных условиях, см. [1]). Между тем, имеется довольно широкий класс диофантовых уравнений с двумя неизвестными

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

Краткое описание упрощенной версии метода Рунге можно найти в хорошо известных монографиях [2–4]. Необходимо отметить, что оригинальная версия метода Рунге является более общей (см. старую статью Рунге [5] или, в современном изложении, статью [6]). Несмотря на то, что метод Рунге известен уже более ста лет, его реализация в системах компьютерной алгебры весьма ограничена. Лишь в очень небольшом числе публикаций (см. [7–9] и, особенно, [10]) обсуждаются алгоритмические аспекты реализации этого метода, которые в целом представляются нетривиальными. Последнее частично объясняется следующим обстоятельством.

Пусть многочлен $f(x,y) \in \mathbb{Z}[x,y]$ неприводим. Положим

Можно доказать, что если $f(x,y)$ удовлетворяет так называемому стандартному условию Рунге (см. ниже), то справедлива оценка

для всех решений $(x,y) \in {{\mathbb{Z}}^{2}}$ уравнения (1) (см. [6]). Здесь h – высота многочлена $f(x,y)$ (максимум модулей его коэффициентов). В частности, этот результат показывает, что тривиальная реализация – полный перебор в предписанных границах – является практически бессмысленной даже в случае довольно малого d₀.

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

Пусть $d = degf(x,y)$ и ${{f}_{d}}(x,y)$ – старшая однородная часть многочлена $f(x,y)$.

Теорема Рунге. Предположим, что ${{f}_{d}}(x,y)$ разложима в произведение двух взаимно простых многочленов из $\mathbb{Z}[x,y]$ положительных степеней. Тогда уравнение (1) имеет конечное множество решений $(x,y) \in {{\mathbb{Z}}^{2}}$.

Далее для краткости условие теоремы Рунге будем называть стандартным условием Рунге. В случае кубических уравнений (d = 3) при выполнении стандартного условия Рунге в работе [9] был предложен практически работающий алгоритм решения уравнения (1). Этот алгоритм основан на так называемой элементарной версии метода Рунге для диофантовых уравнений степени не выше четвертой (см. [11]). Алгоритмическая реализация элементарной версии метода Рунге при d = 4 пока получена только в некоторых частных случаях (см. [12, 13]). Следует также упомянуть хорошо известный элементарный алгоритм решения для наиболее простого типа уравнений 4-й степени, к которым применим метод Рунге (этот алгоритм подробно описан в [7]). Как отмечено в [10], имеет смысл “избегать разложений в ряды Пюизо и алгебраических коэффициентов”, поскольку это обычно приводит к плохим оценкам типа (2). Собственно, данное обстоятельство и составляет основную трудность в алгоритмической реализации метода Рунге.

Элементарная версия метода Рунге для диофантовых уравнений малой степени базируется на специальных параметризациях, которые позволяют перечислить возможные целочисленные решения. Как результат, решение данного диофантова уравнения может быть сведено к решению конечного множества уравнений (как правило, квадратных или кубических) с одним неизвестным в целых числах. Эта идея была воплощена в работах [9, 12, 13]. Особенно хорошо метод работает в случае кубических диофантовых уравнений, где необходимо решать только квадратные уравнения (и, следовательно, все сводится к алгоритмически простой задаче извлечения квадратных корней).

Пример 1. а) Для решения диофантова уравнения

(см. пример 9 из [9]) достаточно решить порядка ${\text{|}}H{{{\text{|}}}^{{1/4}}}$ квадратных уравнений с одним неизвестным. В частности, это позволяет за приемлемое время решить уравнение для каждого H в диапазоне $ - {{10}^{{10}}} \leqslant H$ < 0.

б) Аналогично, диофантово уравнение

сводится к решению порядка ${\text{|}}H{{{\text{|}}}^{{1/3}}}$ квадратных уравнений. Это не только теоретически проще, но и гораздо быстрее, чем нахождение целых точек на подходящей кривой Морделла (как предлагалось в [14], см. раздел 6.1).

в) Диофантово уравнение

(см. [15]) заменой приводится к виду (1), где (см. в других обозначениях пример 1.1 из [13]). Оптимизированный алгоритм из [9] сводит решение уравнения (1) с такой левой частью к решению порядка ${\text{|}}H{{{\text{|}}}^{2}}$ квадратных уравнений. Но и этот результат можно улучшить, понизив порядок числа решаемых квадратных уравнений до ${\text{|}}H{{{\text{|}}}^{{3/2}}}$. Для сравнения отметим, что стандартный алгоритм решения (см. [7]) потребовал бы решения порядка ${\text{|}}H{{{\text{|}}}^{3}}$ квадратных уравнений.

В настоящей статье рассматривается новое семейство диофантовых уравнений (1) 4-й степени с левой частью вида

где, в свою очередь,

Коэффициент d предполагается ненулевым, что и гарантирует применимость метода Рунге. Как показано в [11], произвольное уравнение со старшей однородной частью

сводится к уравнению с левой частью (3).

Статья организована следующим образом.

В разделе 2 предлагается алгоритм решения уравнения (1) с левой частью (3). Корректность его работы гарантируется теоремой 1. Технически данный алгоритм несколько отличается от подобных алгоритмов (см. [9, 12]), так как требует решения некоторого количества уравнений 4-й степени с одним неизвестным в целых числах. Это необходимо принимать во внимание, если мы хотим корректно оценить сложность алгоритма. Как и в работе [13], с этой целью вводится дополнительный параметр – весовой коэффициент, который зависит от той системы компьютерной алгебры, в которой мы планируем реализовывать алгоритм (PARI/GP, см. [1]). Далее можно оптимизировать алгоритм уже известным способом (см. [9, 13]). К сожалению, многочисленные технические детали на этом пути пока не преодолены, поэтому мы приводим только один пример такой оптимизации.

В разделе 3 делаются некоторые замечания относительно полученных результатов. Кроме того, обсуждаются дальнейшие перспективы применения элементарной версии метода Рунге для решения оставшихся типов диофантовых уравнений 4-й степени.

2. АЛГОРИТМ

Будем считать $A \ne 0$ (в случае A = 0 предлагаемый метод можно упростить, см. раздел 3). Напомним, что $d \ne 0$.

Предполагая $x \ne 0$, рассмотрим число

Очевидно, что l должно быть целым для каждого решения $(x,y) \in {{\mathbb{Z}}^{2}}$ с $x \ne 0$. Поделив на x обе части уравнения, получим

Это равенство влечет сравнение

в кольце $\mathbb{Z}$. Далее имеем для некоторых целых чисел B₁ и C₁ (это сравнение в кольце $\mathbb{Z}[y]$). А именно:

Ввиду того, что $h(y) \equiv 0$ $\left( {modx} \right)$, получим еще одно сравнение ${{A}^{2}}l + {{B}_{1}}y + {{C}_{1}} \equiv 0$ $\left( {modx} \right)$ (оба сравнения в кольце $\mathbb{Z}$). Наконец, положим

Ясно, что k также должно быть целым числом. Таким образом, приходим к следующему результату.

Теорема 1. Пусть $(x,y) \in {{\mathbb{Z}}^{2}}$ – произвольное решение уравнения с $x \ne 0$. Тогда число

является целым. Здесь ${{B}_{1}}$ и ${{C}_{1}}$ определяются равенствами (4).

Отметим, что формальное доказательство теоремы 1 легко получить, опираясь на символьные вычисления в какой-нибудь системе компьютерной алгебры. Выразим из уравнения коэффициент C:

Далее подставим это выражение вместо C в правую часть (5). После сокращения на x² мы получим явное (но довольно громоздкое) выражение для k в виде многочлена из $\mathbb{Z}[x,y]$. Теперь очевидно, что значение k должно быть целым, поскольку $(x,y) \in {{\mathbb{Z}}^{2}}$. Отметим, что подобные “механические” рассуждения очень просты логически и актуальны всякий раз, когда мы хотим верифицировать сложное “синтетическое” доказательство или быстро удостовериться в справедливости гипотезы (см., например, [16]).

Пример 2. Для уравнения с левой частью

описанная выше процедура приводит к следующему результату:

Фактически речь идет о равенстве

в кольце классов вычетов $\mathbb{Z}[x,y]{\text{/}}\left\langle {f(x,y)} \right\rangle $.

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

неприводим. Пусть α – любой вещественный корень ϕ(t). Для соответствующей ветви $y = \Psi (x)$ алгебраической функции, определяемой уравнением, имеет место оценка

Как следствие, функция

при $x \to \infty $ имеет пределом число

Таким образом, для любого числа $m > 0$ найдется такое число ${{Q}_{\alpha }}(m) > 0$, что

для всех x с условием ${\text{|}}x{\text{|}} > {{Q}_{\alpha }}(m)$. Теперь можно предложить следующий алгоритм для решения уравнения (1) с левой частью (3).

Алгоритм решения. Для всех вещественных корней α многочлена ϕ(t) сделать:

1. Выбрать $m > 0$ и найти ${{Q}_{\alpha }}(m)$.

2. Для всех целых чисел $x$ с условием

решить уравнение $f(x,y) = 0$ как кубическое относительно y в целых числах. Найденные пары $(x,y) \in {{\mathbb{Z}}^{2}}$ добавить в множество решений.

3. Для всех целых чисел k с условием

найти все пары $(x,y) \in {{\mathbb{Z}}^{2}}$, удовлетворяющие системе уравнений и добавить их в множество решений.

Первая проблема в реализации нашего алгоритма состоит в том, что необходимо задать ${{Q}_{\alpha }}(m)$ как явную функцию управляющего параметра m. Эта проблема технически довольно сложна и пока полностью не решена (мы кратко обсудим это в разделе 3).

Вторую проблему можно сформулировать следующим образом: как выбрать оптимальное значение m? Более формально, для каждого фиксированного α мы хотим минимизировать функцию затрат вида

где весовой коэффициент q предлагается определять экспериментально – в зависимости от той системы компьютерной алгебры, в которой предполагается реализовывать алгоритм (PARI/GP). Более точно, в качестве q следует взять отношение сложности решения систем уравнений вида (6) к сложности решения кубических уравнений (в обоих случаях – в целых числах).

Рассмотрим систему уравнений (6) более подробно. Исключив y, мы получим уравнение 4-й степени относительно x вида

где ${{K}_{j}} = {{K}_{j}}(k)$ – многочлены от $k$ с целыми коэффициентами (мы не приводим их явных и довольно громоздких выражений, отметим лишь, что $deg{{K}_{0}}(k) = 3$ и $deg{{K}_{j}}(k) \leqslant 2$ для остальных j). Таким образом, необходимо определить, насколько более сложной является проблема решения уравнений четвертой степени в целых числах по сравнению с аналогичной проблемой для кубических уравнений. В PARI/GP мы намерены решать обе проблемы с помощью функции nfroots, которая позволяет, в частности, находить все рациональные корни многочлена от одной переменной с целыми коэффициентами. Как итог, весовой коэффициент q может быть выбран с помощью компьютерных экспериментов и предварительного анализа возможной высоты многочлена в левой части равенства (8).

К сожалению, ожидаемое аналитическое выражение для ${{Q}_{\alpha }}(m)$ (см. раздел 3) не позволяет минимизировать функцию затрат (7) символьными методами. Обозначим через m* значение m, доставляющее глобальный минимум ${\text{cost}}$ (m). Имеет смысл сосредоточиться на “разумных” оценках для m* и ${\text{cost}}$ (m*) – тогда мы сможем оценить теоретическую сложность так называемого оптимизированного алгоритма (алгоритма, в котором m = m*). Практически мы можем найти m* с помощью любого приближенного метода (при этом желательно решить проблему локализации для m* аналитически).

Приведем один пример с целью продемонстрировать все трудности, которые необходимо преодолеть в общем случае.

Пример 3. Сконструируем “вручную” оптимизированный алгоритм для семейства уравнений

где H > 0. Единственный вещественный корень $\phi (t) = {{t}^{3}} - 2$ есть $\alpha = {{2}^{{1/3}}}$. Тогда

Кроме того, мы имеем

Коэффициенты уравнения (8) таковы:

Для $y = \Psi (x)$ можно доказать следующее: если ${\text{|}}x{\text{|}} > {{H}^{{1/2}}}$, то справедлива оценка

С помощью (10) нетрудно получить требуемую оценку для ${\text{|}}k - l(H){\text{|}}$. А именно,

для тех x, для которых ${\text{|}}x{\text{|}} > {{H}^{{1/2}}}$. Поэтому, положив $m = {{H}^{{1/2}}}$, получим

Поскольку при $x = {{H}^{{1/2}}}$ имеем

оценка для ${\text{cost}}(m{\kern 1pt} *)$ имеет такой же порядок по H. Тем самым оптимизированный алгоритм для семейства уравнений (9) построен.

3. ЗАМЕЧАНИЯ

При A = 0 предложенный алгоритм будет работать быстрее, чем в общем случае. Действительно, тогда второе уравнение в (6) сводится к линейному, так что уравнение (8) становится кубическим по x (но по-прежнему остается кубическим по k).

Конечно, узкое место нашего алгоритма – это получение явного символьного выражения для ${{Q}_{\alpha }}(m)$. Очевидный подход (успешно примененный в [9]) состоит в том, чтобы решить уравнение (8) как кубическое относительно k по формуле Кардано. Однако из-за громоздких выражений для коэффициентов такой подход представляется непродуктивным. Более реалистичный путь – решить исходное уравнение (1) как кубическое по $y$ и далее явно оценить разность $y{\text{/}}x - \alpha $ при $x \to \infty $. Иными словами, мы можем конкретизировать теоретическую оценку

подобно тому, как это было сделано в примере 3 (т. е. получить оценку типа (10) для всех достаточно больших x, причем с указанием явной границы для этих $x$). С этой целью можно рассмотреть несколько первых членов степенного разложения для функции $\Psi (x){\text{/}}x$ при $x \to \infty $. В общем случае, помимо (очень осторожного) обращения к рядам Пюизо, можно воспользоваться алгоритмами степенной геометрии, хорошо себя зарекомендовавшими при разрешении алгебраических особенностей (см. [17, 18]).

Чтобы проиллюстрировать возможные трудности, вновь обратимся к примеру 3. Имеем

Здесь может показаться, что существует такая абсолютная константа M, что для всякого $x \ne 0$ верна оценка

Однако это не так – из-за того, что коэффициенты разложения зависят от параметра H, который может быть сколь угодно большим. В самом деле, если x = 1, то, как можно убедиться, $y \sim - {{H}^{{1/3}}}$ при $H \to \infty $. Таким образом, в общем случае нам следует указать явную нижнюю границу для ${\text{|}}x{\text{|}}$, которая гарантировала бы оценку типа (11) для $y{\text{/}}x - \alpha $. В конкретной ситуации (пример 3) такую границу указать легко.

В заключение скажем несколько слов о дальнейших перспективах элементарной версии метода Рунге, предложенной в [11].

По-видимому, самым нетривиальным в плане алгоритмической реализации является последний неисследованный случай, когда старшая однородная часть уравнения (1) допускает разложение вида

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

Работа поддержана Красноярским математическим центром, финансируемым Минобрнауки РФ в рамках мероприятий по созданию и развитию региональных НОМЦ (Соглашение 075-02-2020-1534/1).