Программирование, 2019, № 2, стр. 17-31

I. ВВЕДЕНИЕ

Пусть в вещественном $n$-мерном пространстве ${{\mathbb{R}}^{n}} = \{ X\} $ задано m однородных вещественных форм ${{f}_{i}}(X)$, $i = 1,\; \ldots ,\;m$, $2 \leqslant m \leqslant n$. Выпуклая оболочка множества значений G(X) = (|  f₁(X)|, ..., ${\text{|}}{{f}_{m}}(X){\text{|}}) \in \mathbb{R}_{ + }^{m}$ для целочисленных $X \in {{\mathbb{Z}}^{n}}$ во многих случаях является выпуклым многогранным множеством, граница которого для $\left\| X \right\| < {\text{const}}$ вычисляется с помощью стандартной программы компьютерной алгебры. Точки $X \in {{\mathbb{Z}}^{n}}$, для которых значения $G(X)$ лежат на этой границе, названы граничными. Они являются наилучшими диофантовыми приближениями для корневых множеств указанных форм. Их вычисление дает глобальное обобщение цепной дроби (раздел III). Для n = 3 обобщить цепную дробь безуспешно пытались Эйлер, Якоби, Дирихле, Эрмит, Пуанкаре, Гурвиц, Клейн, Минковский, Брун, Арнольд и многие другие.

Пусть $p(\xi )$ – целый неприводимый в $\mathbb{Q}$ многочлен степени n и λ – его корень. Набор основных единиц кольца $\mathbb{Z}[\lambda ]$ можно вычислить по граничным точкам некоторой совокупности линейных и квадратичных форм, построенных по корням многочлена $p(\xi )$ (раздел IV). До сих пор эти единицы вычислялись только для n = 2 (с помощью обычных цепных дробей [1, гл. II, § 7]), n = 3 (с помощью алгоритмов Вороного [2]) и n = 4, когда комплексны все четыре корня многочлена $p(\xi )$, Парусниковым [3], но большинство найденных им единиц не являются основными. Каждая единица определяет как автоморфизм граничных точек $X \in {{\mathbb{R}}^{n}}$, так и автоморфизм соответствующих точек $G(X) \in \mathbb{R}_{ + }^{m}$. В логарифмической проекции положительного ортанта $\mathbb{R}_{ + }^{m}$ на ${{\mathbb{R}}^{{m - 1}}}$ можно найти фундаментальную область для группы автоморфизмов, соответствующих единицам (раздел V).

С помощью этих конструкций можно находить целочисленные решения диофантовых уравнений специального вида (раздел VI). Аналогично вычисляются все указанные объекты для других колец поля $\mathbb{Q}(\lambda )$ (раздел VII). В разделе VIII перечислены предшествующие вычисления основных единиц. Приведены примеры для $n = 2,3$ и 4 (разделы IX–XII).

Наш подход обобщает цепную дробь, позволяет вычислить наилучшие совместные приближения, основные единицы алгебраических колец поля $Q(\lambda )$ и все решения некоторого класса диофантовых уравнений для любого n.

II. ЦЕПНАЯ ДРОБЬ

Пусть ${{\alpha }_{0}}$ и ${{\alpha }_{1}}$ – натуральные числа. Для нахождения их наибольшего общего делителя используется алгоритм Евклида последовательного деления с остатком:

где натуральные числа ${{a}_{0}},\;{{a}_{1}},\;{{a}_{2}},\; \ldots $ суть неполные частные. Это алгоритм разложения числа α = ${{\alpha }_{0}}{\text{/}}{{\alpha }_{1}}$ в правильную цепную дробь [4], и он применим к любым вещественным числам $\alpha $. При этом ${{a}_{0}} = [\alpha ]$, где $[\alpha ]$ – целая часть числа $\alpha $, a₁ = $[1{\text{/}}(\alpha \, - \,{{a}_{0}})]$, …, т.е. и

Если разложение (1) оборвать на ${{a}_{k}}$ и свернуть эту оборванную цепную дробь в рациональное число ${{p}_{k}}{\text{/}}{{q}_{k}}$, то получается подходящая дробь, которая дает наилучшее рациональное приближение к числу $\alpha $. При этом

т.е. векторы $({{\alpha }_{k}},{{\alpha }_{{k + 1}}})$ и $({{p}_{k}},{{q}_{k}})$ принадлежат сопряженным плоскостям, и пара векторов $({{p}_{k}},{{q}_{k}})$, $({{p}_{{k - 1}}},{{q}_{{k - 1}}})$ может служить базисом в одной из них. Лагранж [4, § 10] доказал, что для квадратичных иррациональностей $\alpha $ разложение в цепную дробь периодично (и обратно), т.е. последовательность неполных частных ${{a}_{0}},\;{{a}_{1}},\;{{a}_{2}},\;{{a}_{3}},\; \ldots $ начиная с какого-то номера состоит из повторяющегося отрезка a_k, ${{a}_{{k + 1}}}, \ldots ,{{a}_{{k + t}}}$.

Итак, разложение числа в цепную дробь:

• просто;

•дает наилучшие рациональные приближения к числу;

• конечно для рационального числа;

•периодично для квадратичных иррациональностей [4, § 10];

• устроено как для почти всех чисел [4, гл. III] для кубических иррациональностей [5].

Кроме того, оно обладает еще рядом замечательных свойств.

III. ГЛОБАЛЬНОЕ ОБОБЩЕНИЕ ЦЕПНОЙ ДРОБИ И НАИЛУЧШИЕ ДИОФАНТОВЫ ПРИБЛИЖЕНИЯ

Обобщить цепную дробь для векторов безуспешно пытались Эйлер, Якоби, Дирихле, Эрмит, Пуанкаре, Гурвиц, Клейн, Минковский, Брун, Арнольд и многие другие [6, 7, п. 1.2]. Только пошаговые алгоритмы Вороного [2] безотказны, но сложны.

В [7–9] предложено следующее обобщение цепной дроби.

Пусть в n-мерном вещественном пространстве ${{\mathbb{R}}^{n}}$ с координатами $X = ({{x}_{1}},\; \ldots ,\;{{x}_{n}})$ заданы $m$ однородных вещественных форм (т.е. многочленов от переменных) ${{f}_{1}}(X)$, …, ${{f}_{m}}(X)$, $2 \leqslant m \leqslant n$.

Модули ${{g}_{i}}(X) = \left| {{{f}_{i}}(X)} \right|$ форм ${{f}_{i}}(X)$, $i = 1,\; \ldots ,\;m$, задают отображение $G(X) = ({{g}_{1}}(X), \ldots ,{{g}_{m}}(X))$ пространства ${{\mathbb{R}}^{n}}$ в положительный ортант ${\mathbf{S}}\;\mathop = \limits^{{\text{def}}} \;\mathbb{R}_{ + }^{m}$ в m-мерном пространстве ${{\mathbb{R}}^{m}}$ с координатами S = = $({{s}_{1}}, \ldots ,{{s}_{m}})$: ${{s}_{i}} = {{g}_{i}}(X) = \left| {{{f}_{i}}(X)} \right|$, $i = 1, \ldots ,m$. При этом целочисленная решетка ${{\mathbb{Z}}^{n}} \subset {{\mathbb{R}}^{n}}$ отображается в некоторое множество ${\mathbf{Z}} \subset {\mathbf{S}}$. Замыкание выпуклой оболочки ${\mathbf{H}}$ множества ${\mathbf{Z}}{\backslash }0$ является выпуклым множеством. Все целочисленные точки $X \in {{\mathbb{Z}}^{n}}{\backslash }0$, отображающиеся на границу $\partial {\mathbf{H}}$ множества ${\mathbf{H}}$, назовем граничными.

Задача 1. Найти все граничные точки X.

Решение задачи 1. В дальнейшем ограничимся случаями, когда выпуклое множество ${\mathbf{H}}$ является многогранным, т.е. его граница $\partial {\mathbf{H}}$ состоит из вершин, ребер, граней различных размерностей и не содержит непрерывных “кривых” частей. В этих случаях граница $\partial {\mathbf{H}}$ вычисляется с помощью стандартных программ компьютерной алгебры, предназначенных для вычисления выпуклых многогранных оболочек [10, 11]. Это и дает алгоритмическое обобщение цепной дроби на любую размерность. Примеры см. в [7].

В частности, это дает возможность вычислить наилучшие совместные рациональные приближения ${{q}_{1}}{\text{/}}{{q}_{0}}$, …, ${{q}_{l}}{\text{/}}{{q}_{0}}$ к вещественным числам ${{\beta }_{1}}, \ldots ,{{\beta }_{l}}$, где ${{q}_{0}},{{q}_{1}}, \ldots ,{{q}_{l}} \in \mathbb{Z}$ и ${{f}_{0}}({{q}_{0}}) = {{q}_{0}}$, ${{f}_{i}}({{q}_{0}},{{q}_{i}})$ = = q₀β_i – q_i, $i = 1,\; \ldots ,\;l$. Здесь $n = m = l + 1$. Если l = 1, то получаем одно число ${{\beta }_{1}}$, тогда выпуклый многогранник ${\mathbf{H}}$ – это выпуклый многоугольник на плоскости с координатами ${\text{|}}{{q}_{0}}{\text{|}},\;{\text{|}}{{q}_{0}}{{\beta }_{1}} - {{q}_{1}}{\text{|}}$. Его граница $\partial {\mathbf{H}}$ – это ломаная линия, вершины которой соответствуют подходящим дробям ${{q}_{1}}{\text{/}}{{q}_{0}}$ цепной дроби числа ${{\beta }_{1}}$.

Гипотеза 1. Если все ${{f}_{1}},\; \ldots ,\;{{f}_{m}}$ суть линейные и квадратичные формы, то граница $\partial {\mathbf{H}}$ не имеет непрерывных кривых участков, т.е. является многогранной.

Более того, до сих пор неизвестно ни одного набора форм ${{f}_{1}},\; \ldots ,\;{{f}_{m}}$, для которого граница $\partial {\mathbf{H}}$ не была бы многогранной.

IV. ОСНОВНЫЕ ЕДИНИЦЫ КОЛЬЦА $\mathbb{Z}[\lambda ]$

Пусть дан целый неприводимый в $\mathbb{Q}$ вещественный многочлен

с целыми коэффициентами ${{b}_{i}}$, т.е. он не разлагается в произведение двух нетривиальных многочленов с коэффициентами из $\mathbb{Q}$. Ему соответствует кольцо $\mathbb{Z}[\lambda ]$ чисел вида с целыми коэффициентами ${{x}_{i}}$, где $\lambda $ – корень многочлена (4) и $X = ({{x}_{1}},\; \ldots ,\;{{x}_{n}}) \in {{\mathbb{Z}}^{n}}$. Каждому числу (5) соответствует квадратная матрица D(ξ) = $({{d}_{{ij}}})$:

Определитель $detD(\xi )$ называется нормой числа (5) и обозначается $N(\xi )$. Норма произведения чисел равна произведению их норм: $N({{\xi }_{1}} \cdot {{\xi }_{2}})$ = = $N({{\xi }_{1}}) \cdot N({{\xi }_{2}})$. Те числа (5), у которых норма $N(\xi ) = \pm 1$, называются единицами [1, гл. II]. В дальнейшем предполагаем, что среди корней многочлена $p(\xi )$ нет единиц, т.е. ${\text{|}}{{b}_{n}}{\text{|}} \ne 1$. Этим исключается кручение в абелевой группе единиц. Существует такой набор единиц $\Sigma = ({{\varepsilon }_{1}},\; \ldots ,\;{{\varepsilon }_{r}})$, что всякая единица $\varepsilon \in \mathbb{Z}[\lambda ]$ однозначно представляется в виде

где ${{a}_{i}}$ – целые числа. Эти единицы ${{\varepsilon }_{1}},\; \ldots ,\;{{\varepsilon }_{r}}$ называются основными.

Задача 2. Для фиксированного многочлена (4) найти набор основных единиц кольца $\mathbb{Z}[\lambda ]$.

Решение задачи 2. Пусть неприводимый в $\mathbb{Q}$ многочлен (4) имеет $l$ вещественных корней ${{\lambda }_{1}}$, ..., ${{\lambda }_{l}}$ и $k$ пар комплексно сопряженных корней ${{\lambda }_{{l + 1}}}$, ..., ${{\lambda }_{{l + k}}}$, ${{\bar {a}}_{{l + 1}}}$, ..., ${{\bar {\lambda }}_{{l + k}}}$, $l + 2k = n$. Здесь $l \geqslant 0$, $k \geqslant 0$. Рассмотрим $m = k + l$ форм

где

По теореме Дирихле [1, гл. II, § 4, п. 3] для многочлена (4) число основных единиц $r = k + l - 1$. Далее предполагаем, что $m = k + l \geqslant 2$. Ибо если $k + l \leqslant 1$, то $r \leqslant 0$ и по теореме Дирихле основные единицы отсутствуют.

Теорема 1. ([1, гл. II, § 1, п. 2]). Для чисел (5) с $X = ({{x}_{1}}, \ldots ,{{x}_{n}}) \in {{\mathbb{R}}^{n}}$

Поэтому для всех единиц вида (5)

Пусть – множество точек $X \in {{\mathbb{Z}}^{n}}$ со свойством (15). Рассмотрим для него (т.е. для ) конструкции раздела III: множество значений

где ${{g}_{i}}(X) = \left| {{{f}_{i}}(X)} \right|$, $i = 1,\; \ldots ,\;m$, выпуклую оболочку множества и ее границу . Граница имеет размерность $m - 1 = r$, не имеет кривых участков и состоит из вершин, ребер и граней.

Гипотеза 2. Все грани границы являются симплексами, а значение ${{G}_{0}} = (1,1,\; \ldots ,\;1)$ является ее вершиной.

Пусть Δ – некоторая $(m - 1)$-мерная грань границы , содержащая вершину ${{G}_{0}} = (1,1,\; \ldots ,\;1)$, а ${{R}_{1}},\; \ldots ,\;{{R}_{{m - 1}}}$ – ее ребра, содержащие ${{G}_{0}}$.

Теорема 2. Пусть ${{G}_{i}}$ – вторая вершина ребра ${{R}_{i}}$, отличная от вершины G₀, $i = 1,\; \ldots ,\;m - 1$. Числа (5), у которых $G(X) = {{G}_{i}}$, $i = 1,\; \ldots ,\;m - 1$, образуют набор основных единиц кольца $\mathbb{Z}[\lambda ]$.

Следовательно, для вычисления основных единиц надо на некотором ограниченном множестве $\left\| X \right\| < {\text{const}}$, вычислить кусок границы , содержащий $(m - 1)$-мерную грань $\Delta $.

Каждому числу (5) соответствует матрица

где E – единичная, а B – это матрица, сопровождающая многочлен (4):

Если число (5) является единицей, то матрица $T(\xi )$ унимодулярна и линейное преобразование $X{\text{*}} = T(\xi )X$ в ${{\mathbb{R}}^{n}}$ индуцирует автоморфизм

множества в ${\mathbf{S}} = \mathbb{R}_{ + }^{m}$. Следовательно, каждой единице $\varepsilon $ соответствуют два автоморфизма: граничных точек в ${{\mathbb{R}}^{n}}$ и многогранника ${\mathbf{H}}$ в $\mathbb{R}_{ + }^{m}$, т.е. $T(\varepsilon )$ – это период обобщенной цепной дроби. Количество независимых периодов равно m – 1. Это – обобщение теоремы Лагранжа [4, § 10], доказанной для $n = l = 2$, $k = 0$, т.е. $m = k + l = 2$.

V. ФУНДАМЕНТАЛЬНАЯ ОБЛАСТЬ

В поле $\mathbb{Q}(\lambda )$ всякая целая степень $t \geqslant n$ числа $\xi $ из (5) однозначно записывается в виде многочлена от $\lambda $ степени $n - 1$, ибо

Поэтому отношение двух многочленов от $\lambda $ однозначно записывается в виде многочлена от $\lambda $ степени $n - 1$.

Теорема 3. Пусть $X = ({{x}_{1}},\; \ldots ,\;{{x}_{n}})$, Y = $({{y}_{1}}, \ldots ,{{y}_{n}})$, $Z = ({{z}_{1}},\; \ldots ,\;{{z}_{n}}) \in {{\mathbb{Q}}^{n}}$ и $\xi (X) \cdot \xi (Y) = \xi (Z)$, тогда ${{f}_{i}}(X) \cdot {{f}_{i}}(Y) = {{f}_{i}}(Z)$, $i = 1,\; \ldots ,\;m$.

Следствие 1. В условиях теоремы 3 ${{g}_{i}}(X) \cdot {{g}_{i}}(Y)$ = = g_i(Z), $i = 1,\; \ldots ,\;m$.

Логарифмическая замена

взаимно однозначно переводит ${\mathbf{S}} = \mathbb{R}_{ + }^{m}$ в ${{\mathbb{R}}^{m}}$. При этом $(m - 1)$-мерная граница $\partial {\mathbf{H}}$ многогранного множества ${\mathbf{H}}$ переходит в $(m - 1)$-мерную поверхность, которая взаимно однозначно проектируется на ${{\mathbb{R}}^{{m - 1}}} = \{ H'\} $, где $H'\;\mathop = \limits^{{\text{def}}} \;({{h}_{1}},\; \ldots ,\;{{h}_{{m - 1}}})$.

На ${{\mathbb{R}}^{{m - 1}}}$ автоморфизм (19) принимает вид

т.е. является параллельным переносом. Единицы кольца $\mathbb{Z}[\lambda ]$ образуют абелеву группу по умножению. По теореме 3 их логарифмы $H$ образуют абелеву группу по сложению. В ${{\mathbb{R}}^{{m - 1}}}$ имеется фундаментальная область $\mathcal{F}$ относительно сдвигов (22) этой группы. Пусть $m$-мерные векторы ${{G}_{i}}$, i = = $1, \ldots ,m - 1$, соответствующие основным единицам теоремы 2, имеют вид ${{G}_{i}} = ({{g}_{{1i}}},\; \ldots ,\;{{g}_{{mi}}})$. Положим

Теорема 4. В ${{\mathbb{R}}^{{m - 1}}}$ фундаментальная область относительно сдвигов (22), (23) – это $(m - 1)$-мерный “куб”

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

Шаг 1. Сначала в кольце $\mathbb{Z}[\lambda ]$ находим все единицы с $X \in {{\mathbb{Z}}^{n}}$ из области ||X|| < const, вычисляя значения $g(X)$ в этих X.

Шаг 2. Затем на множестве единиц {} надо вычислить границу их выпуклой оболочки .

Шаг 3. По теореме 2 из выделяем набор основных единиц, представленных в ${\mathbf{S}}$ вершинами ${{G}_{0}},{{G}_{1}},\; \ldots ,\;{{G}_{{m - 1}}}$.

Шаг 4. По теореме 4 находим фундаментальную область (24).

Шаг 5. Теперь выпуклая оболочка значений $G(X)$ с $\xi (X) \in \mathbb{Z}[\lambda ]$ вычисляется только по тем X, у которых $H{\kern 1pt} {\text{'}}(X)$ попадают в фундаментальную область (24) и ее близкую окрестность.

Шаг 6. По этой части границы $\partial {\mathbf{H}}$ восстанавливается вся граница $\partial {\mathbf{H}}$ с помощью периодов ${{G}_{i}}$, $i = 1, \ldots ,m - 1$, соответствующих основным единицам, или с помощью сдвигов (22).

VI. ДИОФАНТОВЫ УРАВНЕНИЯ

Многочлену $p(\xi )$ степени $n$ из (4) соответствует форма $f(X)$ из (14) степени n от n переменных $X = ({{x}_{1}},\; \ldots ,\;{{x}_{n}})$. Ее коэффициенты являются многочленами от коэффициентов ${{b}_{i}}$ многочлена (4). Так, при n = 2

при n = 3 при n = 4

Для любого n при ${{x}_{3}} = \ldots = {{x}_{n}} = 0$ имеем

Задача 3. Для заданного многочлена (4) найти все решения (5) с $\xi \in \mathbb{Z}[\lambda ]$ уравнения

где число $\beta $ рационально, $\beta \ne \pm 1$.

Решение задачи 3.

Теорема 5. ([1, гл. II, § 5, теорема 1]). Все решения (5) с $\xi \in \mathbb{Z}[\lambda ]$ уравнения (48) имеют вид

где $\xi _{1}^{0},\; \ldots ,\;\xi _{J}^{0}$ – конечное множество выделенных решений и ${{a}_{1}},\; \ldots ,\;{{a}_{r}}$ – любые целые числа. Если выделенных решений $\xi _{j}^{0}$ нет, то уравнение (28) не имеет решений.

Далее дается набросок конструктивного доказательства этой теоремы, позволяющий вычислять соответствующие постоянные и выделенные решения $\xi _{1}^{0}$, …, $\xi _{J}^{0}$.

Согласно предыдущим разделам находим набор основных единиц $\Sigma = ({{\varepsilon }_{1}},\; \ldots ,\;{{\varepsilon }_{{m - 1}}})$ кольца $\mathbb{Z}[\lambda ]$ и по ним строим фундаментальную область $\mathcal{F}$ в координатах $H'\;\mathop = \limits^{{\text{def}}} \;({{h}_{1}},\; \ldots ,\;{{h}_{{m - 1}}})$.

Лемма 1. Для всех точек $X \in {{\mathbb{R}}^{n}}$, у которых логарифмические проекции $H' = ({{h}_{1}},\; \ldots ,\;{{h}_{{m - 1}}})$ лежат в фундаментальной области $\mathcal{F}$, справедливы оценки

где $0 < {{\mu }_{i}} < {{\nu }_{i}}$ – вещественные числа.

Лемма 2. Для всех точек $X$, у которых $H' \in \mathcal{F}$ и выполнено равенство $g(X) = \left| \beta \right|$, справедливы оценки

где $0 < {{\mu }_{m}} < {{\nu }_{m}}$ – вещественные числа.

Нижние оценки в (30) нужны для получения верхней оценки в (31).

Поскольку $\left\langle {K,X} \right\rangle = \left\langle {{\text{Re}}K,X} \right\rangle + i\left\langle {{\text{Im}}K,X} \right\rangle $, то

Лемма 3. Если

то области в ${{\mathbb{R}}^{n}}$, где выполнены неравенства (30) и (31), ограничены.

Поскольку

и последний определитель отличается от определителя Вандермонда

ненулевым множителем, то условие (33) эквивалентно условию, что у многочлена (4) нет кратных корней. Но это так по условию, что многочлен (4) неприводим в $\mathbb{Q}$.

Неравенства (30), (31) выделяют в ${{\mathbb{R}}^{n}}$ всего ${{2}^{m}}$ ограниченных областей вида

В каждой из них количество целочисленных точек $X \in {{\mathbb{Z}}^{n}}$ конечно. В каждой из этих точек можно вычислить $f(X)$ и отобрать те ${{X}_{i}}$, в которых выполнено уравнение (28). Наконец, среди этих точек ${{X}_{i}}$ оставляем только те $X_{1}^{0},\; \ldots ,\;X_{J}^{0}$, для которых отношения $\xi (X_{i}^{0}){\text{/}}\xi (X_{j}^{0})$ по $j \ne i$ не лежат в $\mathbb{Z}{\kern 1pt} [\lambda ]$. Тогда $\xi _{j}^{0} = \xi (X_{j}^{0})$, $j = 1,\; \ldots ,\;J$, являются выделенными решениями уравнения (48) и все решения этого уравнения имеют вид (49).

Это первый способ. Он заключается в том, что в каждом ортанте пространства ${{\mathbb{R}}^{n}} = \{ X\} $ кусок множества значений $X:f(X) = \beta $ заключается в некоторый параллелепипед. В каждом из них перебираются все точки X решетки ${{\mathbb{Z}}^{n}}$ и находятся те, которые удовлетворяют уравнению (28). Затем среди всех этих точек всех ортантов оставляются все выделенные решения.

Второй способ. Все искомые точки решетки лежат в множестве $ - {{\nu }_{i}} \leqslant {{f}_{i}}(X) \leqslant {{\nu }_{i}}$, $i = 1,\; \ldots ,\;m$. Найдем все точки пересечения поверхностей

и для каждого ${{x}_{j}}$ выберем значение ${{z}_{j}} = max\left| {{{x}_{j}}} \right|$ среди этих точек пересечения. Затем среди точек X решетки, для которых найдем все те, которые удовлетворяют уравнению (48). Затем, вычисляя их попарные отношения, находим множество выделенных решений. Этот способ удобнее для вычислений на компьютере, но дает много лишних решений, которые не являются выделенными.

VII. ОБОБЩЕНИЯ

VIII. ПРЕДШЕСТВЕННИКИ И ДИСКРИМИНАНТЫ

Для $n = 2$, $k = 0$, $l = 2$, когда $m = 2$ и $r = 1$, т.е. для вещественных квадратичных полей способ вычисления основной единицы максимального порядка $\widetilde \Omega $, основанный на разложении в цепную дробь, описан в книге [1, гл. II, § 7]. В конце этой книги в табл. 1 приведены значения основных единиц $\varepsilon > 1$ максимальных порядков полей $\mathbb{Q}(\sqrt d )$ для $2 \leqslant d \leqslant 101$, $d \in \mathbb{Z}$.

Для $n = 3$, $m = 2$ ($r = 1$) и $n = 3$, $m = 3$ ($r = 2$) основные единицы максимальных порядков вычислял Вороной [2] с помощью своих пошаговых обобщений цепной дроби. В [6, 7, 12] вычислены многоугольники и многогранники $\partial {\mathbf{H}}$ с помощью других обобщений.

Для $n = 4$, $k = 2$, l = 0, т.е. $m = 2$ ($r = 1$), Парусников [3] вычислил единицы максимальных порядков полей $\mathbb{Q}(\lambda )$ для 41 многочлена (4) с помощью пошагового алгоритма. Но большинство найденных им единиц не являются основными, а являются лишь их целыми степенями.

Напомним, как определить число l вещественных и число k пар комплексно сопряженных корней многочлена (4) в случае, когда нет кратных корней, т.е. дискриминант многочлена $D$ отличен от нуля.

Случай $n = 2$. Тогда $D = b_{1}^{2} - 4{{b}_{2}}$. Имеем l = 2, $k = 0$, если $D > 0$; $k = 1$, если $D < 0$.

Случай $n = 3$. Тогда D = $ - 4b_{1}^{2}{{b}_{3}}\, + \,b_{1}^{2}b_{2}^{2}\, + \,18{{b}_{1}}{{b}_{2}}{{b}_{3}}$ – – $4b_{2}^{2}$ – $27b_{3}^{2}$. Имеем $l = 3,k = 0$, если $D > 0$; l = 1, $k = 1$, если $D < 0$.

Случай $n = 4$. Тогда

Здесь ${{D}_{1}}$ и ${{D}_{2}}$ – субдискриминанты многочлена (4).

$l = 2,$ $k = 1,$ если $D < 0$;

$l = 0,$ $k = 2,$ если $D > 0$ и либо ${{D}_{1}} = {{D}_{2}} = 0$, либо хотя бы один из ${{D}_{1}}$ и ${{D}_{2}}$ отрицателен;

$l = 4,$ $k = 0,$ если все $D,{{D}_{1}},{{D}_{2}}$ положительны [14, 15].

IX. ПРИМЕР СЛУЧАЯ $n = 2,$ $l = 2,$ $k = 0$

Пусть $p(\xi ) = {{\xi }^{2}} - 5$. Тогда $n = 2$, а корни многочлена $p(\xi )$ суть $\lambda = \pm \sqrt 5 \approx \pm 2.23605$. Поэтому $k = 0$, $l = 2$, $m = k + l = 2$ и $r = m - 1 = 1$. Разложение $\sqrt 5 $ в цепную дробь имеет вид

Подходящие дроби суть

На рис. 1 показаны: прямая ${{x}_{2}} = {{x}_{1}}{\text{/}}\sqrt 5 $, кривые $x_{1}^{2} - 5x_{2}^{2}$ = ±1 и лежащие на них точки $({{x}_{1}},{{x}_{2}}):(1,0)$, (2, 1), (9, 4), соответствующие подходящим дробям. На рис. 1 масштабы по осям разные. Здесь ${{f}_{1}}(X)\, = \,{{x}_{1}}\, + \,{{x}_{2}}\sqrt 5 $, ${{f}_{2}}(X) = {{x}_{1}} - {{x}_{2}}\sqrt 5 $ и  f(X) = $x_{1}^{2}\, - \,5x_{2}^{2}$. В координатах ${{g}_{i}}(X) = \left| {{{f}_{i}}(X)} \right|$, $i = 1,2$, для целочисленных X получаем ломаную линию, показанную на рис. 2. Ее вершины соответствуют подходящим дробям. Вообще, если ${{\lambda }_{1}} > 0$ – корень квадратного уравнения, то подходящим дробям цепной дроби числа ${{\lambda }_{1}}$ соответствуют вершины ломаной $\partial {\mathbf{H}}$.

Основная единица максимального порядка $\widetilde \Omega $ есть $\varepsilon \, = \,(1\, + \,\lambda ){\text{/}}2\, \approx \,1.61803$, т.е. в записи (5) ${{x}_{1}}\, = \,{{x}_{2}}$ = = 1/2. Поскольку $N(X) = x_{1}^{2} - 5x_{2}^{2}$, то $N(\varepsilon ) = - 1$ и квазиосновная единица порядка $\widetilde \Omega $ есть $\hat {\varepsilon } = {{\varepsilon }^{2}} = (3 + \lambda ){\text{/}}2$ ≈ 2.61803. Основная единица кольца $\mathbb{Z}[\lambda ]$ есть ${{\varepsilon }^{3}}\, = \,2\, + \,\lambda \, \approx \,4.23605$ с нормой $N({{\varepsilon }^{3}})$ = = –1. Наконец, квазиосновная единица этого кольца есть $\hat {\varepsilon } = {{\varepsilon }^{6}} = 9 + 4\lambda \approx 17.94421$.

Уравнение (48) здесь имеет вид $x_{1}^{2} - 5x_{2}^{2} = \beta $. Положим $\beta = 4$ и найдем все целочисленные решения $({{x}_{1}},{{x}_{2}})$ уравнения

т.е. $\xi ({{x}_{1}},{{x}_{2}}) = {{x}_{1}} + {{x}_{2}}\sqrt 5 \in \mathbb{Z}(\sqrt 5 )$. Ограничимся решениями ${{x}_{1}},{{x}_{2}} \geqslant 0$, остальные решения получаются изменением знаков. Поэтому наша основная единица – это $\hat {\varepsilon } = {{\varepsilon }^{6}} = 9 + 4\sqrt 5 $ ≈ 17.94421 < 18. Фундаментальная область в координатах ${{x}_{1}},\;{{x}_{2}}$ – это

На кривой (66) над выполнены неравенства $4{\text{/}}\hat {\varepsilon } \leqslant {{f}_{2}}\;\mathop = \limits^{{\text{def}}} \;{{x}_{1}} - {{x}_{2}}\sqrt 5 \leqslant 4$, т.е.

На плоскости $({{x}_{1}},{{x}_{2}}) \in {{\mathbb{R}}^{2}}$ неравенства (39), (40) выделяют четырехугольник, ограниченный прямыми ${{f}_{1}} = 1$, ${{f}_{1}} = 18$, ${{f}_{2}} = 2{\text{/}}9$, ${{f}_{2}} = 4$ и показанный на рис. 3. На нем показана ветвь кривой $f(X) = 4$ и три выделенных точки на ней.

Вершины этого четырехугольника суть

Теперь для каждого целого ${{x}_{2}}:0 \leqslant {{x}_{2}} \leqslant 3$ переберем все целые ${{x}_{1}}:1 \leqslant {{x}_{1}} < 11$ и выберем среди таких точек $({{x}_{1}},{{x}_{2}})$ решения уравнения (66). Получаем точки $(2,0)$, $(3,1)$, $(7,3)$. Поскольку отношения $(3 + \sqrt 5 ){\text{/}}2$, $(7 + 3\sqrt 5 ){\text{/}}2$, $\tfrac{{7 + 3\sqrt 5 }}{{3 + \sqrt 5 }} = \tfrac{{3 + \sqrt 5 }}{2}$ не лежат в $\mathbb{Z}[\sqrt 5 ]$, то получим три выделенных решения $\xi _{1}^{0} = 2$, $\xi _{2}^{0} = 3 + \sqrt 5 $, $\xi _{3}^{0} = 7 + 3\sqrt 5 $. По теореме 5 все решения с ${{x}_{1}},{{x}_{2}} \geqslant 0$ имеют вид

10. ПРИМЕР СЛУЧАЯ $n = 3,l = 3,k = 0$

Пусть $p(\xi ) = {{\xi }^{3}} - 7\xi - 2$, все его корни вещественны:

Здесь $n = m = l = 3$, $k = 0$, $r = m - 1 = 2$. Фундаментальный базис максимального порядка $\widetilde \Omega $ есть $1,\lambda ,(\lambda + {{\lambda }^{2}}){\text{/}}2$. Здесь ${{b}_{1}} = 0,$ ${{b}_{2}} = - 7,$ ${{b}_{3}} = - 2$ и согласно разделу VI

Вычисления проведем в 6 шагов раздела V.

Шаг 1. Вычисляя значения $g(Y)$ на точках ξ = = ${{y}_{1}} + {{y}_{2}}\lambda + {{y}_{3}}(\lambda + {{\lambda }^{2}}){\text{/}}2$ с целыми ${{y}_{i}}$, находим единицы ${{\varepsilon }_{i}} = ({{y}_{1}},{{y}_{2}},{{y}_{3}})$: ${{\varepsilon }_{1}} = (0,0,1)$, ${{\varepsilon }_{2}} = (1,2,2)$, ${{\varepsilon }_{3}} = ( - 2,0,1)$, ${{\varepsilon }_{4}} = ( - 10, - 2,3)$, ${{\varepsilon }_{5}} = (5,2, - 2)$, ε₆ = = $(0,2, - 1)$.

Шаг 2. Вычисляем выпуклую оболочку соответствующих точек ${{G}_{0}},{{G}_{i}} = G({{Y}_{i}})$, $i = 1,\; \ldots ,\;6$, и получаем у нее 6 двумерных граней. Их логарифмические проекции на плоскость ${{h}_{1}},\;{{h}_{2}}$ показаны на рис. 4. На нем логарифмические проекции ребер показаны прямыми отрезками, хотя они являются криволинейными. Заметим, что ${{\varepsilon }_{{i + 3}}} = \varepsilon _{i}^{{ - 1}}$, i = 1, 2, 3.

Шаг 3. Здесь любая пара ${{\varepsilon }_{i}}$ и ${{\varepsilon }_{j}} \ne \varepsilon _{i}^{{ \pm 1}}$ (i, j = = $1, \ldots ,6$) образует набор фундаментальных единиц.

Шаг 4. Для пары ${{\varepsilon }_{1}}$, ${{\varepsilon }_{3}}$ фундаментальная область $\mathcal{F}$ – четырехугольник с вершинами 0, ε₁, ${{\varepsilon }_{2}},{{\varepsilon }_{3}}$.

Шаг 5. Логарифмическая проекция границы выпуклой оболочки значений $G(Y)$ по $Y \in {{\mathbb{Z}}^{3}}$ с $H'(Y) \in \mathcal{F}$ показана на рис. 5. Тут имеются две новые вершины: ${{\delta }_{1}} = (0,1,1)$ и ${{\delta }_{2}} = (1,1,1)$. На них $g(Y)$ = 2. Имеется четырехугольная грань с вершинами $0,\;{{\delta }_{1}},\;{{\varepsilon }_{2}},\;{{\delta }_{2}}$.

Шаг 6. Сдвигая фундаментальную область рис. 5 на целочисленные линейные комбинации логарифмов известных единиц, получаем схематическую проекцию всего многогранника $\partial {\mathbf{H}}$ на плоскость ${{h}_{1}},\;{{h}_{2}}$, показанную на рис. 6. На рис. 7 показана точная логарифмическая проекция многогранника $\partial {\mathbf{H}}$ на плоскость ${{h}_{1}},\;{{h}_{2}}$; проекции ребер криволинейны. Отрезки в ромбах – это ошибки: их не должно быть. Этот рисунок взят из [7], куда он попал из [13].

Этот пример взят у Вороного [2, § 59, пример]. Там найдены две пары основных единиц ${{\varepsilon }_{2}},\;{{\varepsilon }_{3}}$ и ${{\varepsilon }_{2}},\;{{\varepsilon }_{4}}$, но нет аналогов наших рисунков. На самом деле, в этом примере граница $\partial {\mathbf{H}}$ вычисляется сразу как выпуклая оболочка значений $G(Y)$ по $Y \in {{\mathbb{Z}}^{3}}$, ибо размерность задачи n = 3 невелика. Но здесь показано разбиение на шаги, которое может быть полезным при больших размерностях $n$ и m.

Найдем все решения $X$ с $\xi (X) \in \widetilde \Omega $ уравнения (48) с $\beta = 4$. В единице ${{\varepsilon }_{1}}$ формы

В единице ${{\varepsilon }_{3}}$ формы

Используем второй способ нахождения выделенных решений. Согласно рис. 4 фундаментальная область $\mathcal{F}$ лежит внутри квадрата

Над этим квадратом лемма 1 принимает вид

Для решения уравнения $g(X) = 4$ имеем

Поэтому для этих решений над квадратом $G$

Теперь согласно (75) все выделенные решения находятся в области

8 точек пересечения $({{x}_{{1i}}},{{x}_{{2i}}},{{x}_{{3i}}})$, $i = 1,\; \ldots ,\;8$, шести плоскостей суть ${{x}_{1}} = \pm 14.17606,$ ${{x}_{2}} = \pm 46.396,$ ${{x}_{3}} = \pm 16.9941$.

Максимальные значения модулей координат этих точек суть

В параллелепипеде

имеется 23 решения нашего уравнения (28), приведенные в табл. 1.

Из них отберем те, отношения которых не лежат в решетке: ${{x}_{1}} \in \mathbb{Z}$, $2{{x}_{3}} \in \mathbb{Z}$, ${{x}_{2}} \in \mathbb{Z}$, если ${{x}_{3}} \in \mathbb{Z}$, и $2{{x}_{2}} \in \mathbb{Z}$, если ${{x}_{3}}\not { \in }\mathbb{Z}$. В $\mathbb{Q}(\lambda )$ отношение двух чисел $X{\text{/}}Y = Z$, если

где ${{\lambda }^{3}} = 7\lambda + 2$ и ${{\lambda }^{4}} = 7{{\lambda }^{2}} + 2\lambda $. Для ${{z}_{i}}$ получаем линейную систему 3 уравнений

Результат показан в табл. 2.

Согласно теореме 4 все решения $\xi \in \widetilde \Omega $ уравнения (48) суть

XI. ПРИМЕРЫ СЛУЧАЯ $n = 3,l = 1,k = 1$

Пусть $p(\xi ) = {{\lambda }^{3}} + 22{{\lambda }^{2}} + 11\lambda + 25$. Этот пример взят из [12, табл. 2]. Здесь

Здесь ${{b}_{1}} = 22$, ${{b}_{2}} = 11$, ${{b}_{3}} = 25$ и согласно разделу VI

Результаты вычисления выпуклой ломаной $\partial {\mathbf{H}}$ для $\xi \in \mathbb{Z}(\lambda )$ на плоскости ${{g}_{1}}(X) = \left| {{{f}_{1}}(X)} \right|$, g₂(X) = = $\left| {{{f}_{2}}(X)} \right|$ приведены в табл. 3. Каждая ее строка соответствует вершине ломаной $\partial {\mathbf{H}}$ и содержит x₁, ${{x}_{2}},{{x}_{3}},$ $g(X) = \left| {f(X)} \right|,$ ${{g}_{1}}(X)$, ${{g}_{2}}(X)$, $ln{{g}_{1}}$, $ln{{g}_{2}}$.

В верхней и нижней строках таблицы стоят основные единицы $\varepsilon = 29 - 171\lambda - 8{{\lambda }^{2}}$ и $\varepsilon \, = \,94\, + \,37\lambda $ + + 81λ². Видна периодичность значений $g(X)$ на этих вершинах.

Аналогичные вычисления вершин ломаной $\partial {\mathbf{H}}$ были проделаны и для других случаев n = 3, $D < 0$ из статьи [12, таблицы 3–7]. Их результаты приводятся ниже в виде таблиц 4–8.

$p(\xi ) = {{\xi }^{3}} + 19{{\xi }^{2}} + 11\xi + 18$; ${{\lambda }_{1}} \approx - 18.4568$, λ_2,3 ≈ ≈ $ - 0.27517 \pm 0.94947i$. Табл. 4.

$p(\xi ) = {{\xi }^{3}} + 16{{\xi }^{2}} + 8\xi + 20$; ${{\lambda }_{1}} \approx - 15.56866$, λ₂ ≈ ≈ $ - 0.215669 \pm 1.1127078i$. Табл. 5.

$p(\xi )\, = \,{{\xi }^{3}} - 4{{\xi }^{2}}\, + \,25\xi \, + \,17$; ${{\lambda }_{1}} \approx - 0.6111166$, λ_2,3 ≈ ≈ $2.305558 \pm 4.74366i$. Табл. 6.

$p(\xi )\, = \,{{\xi }^{3}} - 8{{\xi }^{2}} + 21\xi + 13$; ${{\lambda }_{1}} \approx - 0.5125546$, λ_2,3 ≈ ≈ $4.256277 \pm 2.692072i$. Табл. 7.

$p(\xi ) = {{\xi }^{3}} - 5{{\xi }^{2}} + 11\xi + 9$; ${{\lambda }_{1}} \approx - 0.6210714$, λ_2,3 ≈ ≈ $2.8105357 \pm 2.567484i$. Табл. 8.

XII. ПРИМЕРЫ СЛУЧАЯ $n = 4,\;l = 0,\;k = 2$

В препринте [3] В.И. Парусников вычислил по паре единиц для 41 многочлена (5) с $n = 4$ и двумя парами комплексных корней ${{\lambda }_{1}},\;{{\lambda }_{2}},\;{{\bar {\lambda }}_{1}},\;{{\bar {\lambda }}_{2}}$. По теореме Дирихле в этих случаях имеется ровно одна фундаментальная единица. Здесь получаем две формы

где ${{K}_{i}} = (1,{{\lambda }_{i}},\lambda _{i}^{2},\lambda _{i}^{3})$, $X = ({{x}_{1}},{{x}_{2}},{{x}_{3}},{{x}_{4}})$. Для первых 15 многочленов Парусникова мы вычислили вершины ломаной $\partial {\mathbf{H}}$ по $X \in {{Z}^{4}}$ для двух форм g_i(X) = ${\text{|}}{{f}_{i}}(X){\text{|}}$, $i = 1,2$, и получили для них фундаментальные единицы $\varepsilon $. Результаты приведены в табл. 9. Там каждая строка соответствует одному многочлену. В первом столбце дан его номер $n$, во втором – сам многочлен $p(\xi )$; в третьем, четвертом и пятом – значения субдискриминантов ${{D}_{2}},{{D}_{1}}$ и дискриминанта D, в шестом – значение фундаментальной единицы $\varepsilon $, в седьмом – число вершин $V$ ломаной $\partial {\mathbf{H}}$ внутри фундаментальной области, в восьмом и девятом – единицы ${{\mu }_{2}}$ и ${{\mu }_{3}}$ Парусникова из его табл. 2 и 3 соответственно.

Для уравнения с n = 10 найденная Парусниковым единица ${{\mu }_{3}}$ является столь большой (или малой) степенью основной единицы $\varepsilon $, что оказалась вне просчитанной части ломаной $\partial {\mathbf{H}}$. В этом месте поставлен знак вопроса. Пустые места для ${{\mu }_{2}}$ при n = 5, для ${{\mu }_{3}}$ при $n = 7$ и для ${{\mu }_{2}},{{\mu }_{3}}$ при $n = 9$ означают, что Парусников не привел этих значений.

Замечание. Если единица $\varepsilon (\lambda ) = {{x}_{1}} + {{x}_{2}}\lambda + {{x}_{3}}{{\lambda }^{2}}$ + + x₄λ³, то обычно число –ε(λ) = $ - {{x}_{1}} - {{x}_{2}}\lambda - {{x}_{3}}{{\lambda }^{2}}$ – – x₄λ³ является также единицей. Но для биквадратного многочлена $p(\xi )$ число ε(–λ) = x₁ – ${{x}_{2}}\lambda \, + \,{{x}_{3}}{{\lambda }^{2}}$ – – x₄λ³ также является единицей с той же нормой, ибо вместе с корнем $\lambda $ многочлен $p(\xi )$ имеет корень $ - \lambda $. В табл. 9 такими являются многочлены для $n = 1,2,4,7,10$.

Предыдущие публикации автора в этом направлении: [16, 17].

XIII. ПЕРСПЕКТИВЫ

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

Пример. Марков [18] вычислил фундаментальную единицу

кольца $\mathbb{Z}[\lambda ]$ с ${{\lambda }^{3}} = 23$. Для ее вычисления по алгоритму раздела VI требуется перебор значений нормы для $\left| {{{x}_{i}}} \right| \leqslant {{10}^{{11}}}$, $i = 1,2,3$. Правда, Вороной [2, отдел II] вычислил к ней обратную фундаментальную единицу за 21 шаг своего алгоритма. Для ее вычисления алгоритмом раздела VI требуется перебор значений нормы (81) для $\left| {{{x}_{i}}} \right| \leqslant {{10}^{6}}$, $i = 1,2,3$.

Поэтому для разных n и m желательно найти более простые алгоритмы последовательного вычисления вершин многогранника H. Здесь возможны два следующих подхода.

Подход 1. Пусть известны все вершины ${{V}_{1}}, \ldots ,{{V}_{s}}$ некоторой гиперграни $H_{j}^{{(m - 1)}}$ многогранника H. Надо найти все вершины примыкающих к ней гиперграней многогранника H. При этом можно различать несколько случаев и делать некоторый перебор. Такие алгоритмы для n = 3, $m = 1$ и n = 3, $m = 2$ были предложены автором и В.И. Парусниковым в [6, 12, 19–21].

Подход 2. Вместе с многогранником ${\mathbf{H}}$ в ${{\mathbb{R}}^{n}}$ рассматривать сопряженный многогранник ${{{\mathbf{H}}}_{*}}$ в двойственном пространстве $\mathbb{R}_{*}^{n}$ и двигаться по ним одновременно в зависимости о взаимных свойств граней. Для $n = 3$, $m = 2$ несколько случаев таких пар многогранников описаны в [7, 13 ]. Отметим, что для обычной цепной дроби многогранники H и ${{{\mathbf{H}}}_{*}}$ совпадают, т.е. являются самосопряженными.

Для детальной разработки алгоритмов указанных двух подходов потребуется вычислить много разных примеров с помощью описанного алгоритма обобщенной цепной дроби. Кроме того, надо проверить гипотезу 2 и найти способ ее доказательства.

БЛАГОДАРНОСТИ

Автор благодарит А.Б. Батхина и А.А. Соколова за большую помощь в подготовке этой статьи.

Работа поддержана РФФИ, грант 18-01-00422а.