К обобщениям цепной дроби
( On generalizations of the continued fraction
Preprint, Inst. Appl. Math., the Russian Academy of Science)

E-mail: bruno@keldysh.ru

Введение

Пусть a₀ и a₁ - натуральные числа. Для нахождения их наибольшего общего делителя используется алгоритм Евклида [1] последовательного деления с остатком:

a0=a0a1+a2,    a1=a1a2+a3,    a2=a2a3+a4, … ,

где натуральные числа a₀,a₁,a₂,╝ суть неполные частные. Это алгоритм разложения числа a =a₀/a₁ в правильную цепную дробь, и он применим к любым вещественным числам a. При этом a₀=[a], где [a] - целая часть числа a, a₁=[1/(a-a₀)], ╝, т.е.

a=a0+  1 a1+  1 a2+  1 a3+  ··· ,

(1)

и

ж з з и ak+1 ak+2 ц ч ч ш = ж з з и 0 1 1 -ak ц ч ч ш ж з з и ak ak+1 ц ч ч ш ,    ak=[ak/ak+1].

(2)

Если разложение (1) оборвать на a_k и свернуть эту оборванную цепную дробь в рациональное число p_k/q_k, то получается подходящая дробь, которая дает наилучшее рациональное приближение к числу a. При этом

ж з з и pk pk-1 qk qk-1 ц ч ч ш = ж з з и pk-1 pk-2 qk-1 qk-2 ц ч ч ш ж з з и ak 1 1 0 ц ч ч ш

(3)

и

ж з з и ak 1 1 0 ц ч ч ш -1   = ж з з и 0 1 1 -ak ц ч ч ш ,

т.е векторы (a_k,a_k+1) и (p_k,q_k) принадлежат сопряженным плоскостям.

Цепные дроби (1) и соотношения (2), (3) рассматривал Валлис [3] в 1655 г. В 1737 г. Эйлер [4] дал название "непрерывная дробь" (fractio continua). Лагранж [5] доказал, что для квадратичных иррациональностей a разложение в цепную дробь периодично (и обратно).

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

1) прост;

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

3) периодичен для квадратичных иррациональностей.

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

В 1775 г. Эйлер [6] сделал первую попытку обобщить алгоритм цепной дроби на векторы. Впоследствии его подход развивали Якоби [7,8], Пуанкаре [9], Брун [10], Перрон [11], Бернштейн [12], Пустыльников [13] и др. (см. [14]). Они по аналогии с (2) строили матричные алгоритмы вида

Ak+1=CkAk,    k=0,1,2, … ,

(4)

где A_k - n-мерный вектор и C_k - квадратная n-матрица с целыми элементами, которая образована по вектору A_k, и det C_k=▒1. Эти алгоритмы просты, но, вообще говоря, не дают наилучших рациональных приближений к вектору и не всегда при n=3 обладают аналогом свойства 3):

3 ′ ) периодичность для кубических иррациональностей.

Еще Эрмит [15] критиковал алгоритм Якоби. В работах [16-23] было проведено сравнение качества матричных алгоритмов и было установлено, что ни один их них не обладает свойствами 2) и 3 ′ ) для всех векторов A₀. При этом оказалось, что наихудшим является алгоритм Пуанкаре [9].

В 1842 г. Дирихле [24] при n=3 предложил рассматривать не трехмерный вектор A=A₀, а две линейные однородные формы l₁(X) и l₂(X) такие, что l₁(A)=l₂(A)=0. В 1850 г. Эрмит [25], развивая этот подход, предложил свое обобщение цепной дроби. Наконец, в 1895-96 гг. Клейн [26], Минковский [27] и Вороной [28] независимо пришли к тому, что надо в R³ рассматривать тройку однородных линейных форм l₁(X), l₂(X), l₃(X) и предложили свои концепции обобщения цепной дроби. При этои Клейн ограничился общими геометрическими соображениями, а Минковский и Вороной предложили конкретные алгоритмы. Впоследствии подход Клейна переоткрывали Скубенко [29] и Арнольд [30] и называли многогранники Клейна парусами и многогранниками Арнольда [43,44]. И хотя в [16] был предложен алгоритм вычисления многогранников Клейна, в [17-23] было выяснено, что многогранники Клейна-Скубенко-Арнольда не дают основы для хорошего алгоритма, обобщающего цепную дробь. Только алгоритмы Минковского и Вороного обладают свойствами 2 и 3 ′ , но они весьма громоздки. Их применению и развитию было посвящено много работ (см. [31-33]).

Свой подход к обобщению цепной дроби предложил Гурвиц [34] в 1894 г., но без алгоритма.

Интерес автора к обобщению цепной дроби возник в связи с его работой [35] 1964 г., которая была повторена Ленгом [36] в 1972 г. (см. также Старк [37]). Ниже в § 1 для правильной цепной дроби излагаются конструкции Клейна и Вороного, а также предложенная автором "выпуклая цепная дробь". В § 2 показано, как вычисляется выпуклая цепная дробь. В § 3 излагаются конструкции Клейна, Вороного и автора для n=3. В § 4 дан новый алгоритм, обобщающий выпуклую цепную дробь. В § 5 сравниваются множества целочисленных точек разных типов, встречающихся в цепных дробях (n=2) и их обобщениях (n=3).

§ 1. Правильная цепная дробь

Клейн [26,38,39] предложил следующую геометрическую интерпретацию цепной дроби числа a (см. также [40]). Пусть на плоскости с координатами x₁,x₂ проведены две прямые линии L₁={x₁=ax₂} и L₂={x₂=0}. Они образуют два смежных угла O₁={x₁,x₂: x₁ ≥ ax₂,x₂ ≥ 0} и O₂={x₁,x₂: x₁ ≤ ax₂,x₂ ≥ 0}. Через K_i обозначим выпуклую оболочку целочисленных точек (x₁,x₂), кроме x₁=x₂=0, попавших в O_i,  (i=1,2). Границы ∂ K_i этих множеств K_i суть выпуклые ломаные линии, состоящие из вершин B_j и ребер R_j. Вершинам B_j=(x₁,x₂) этих линий соответствуют подходящие дроби x₁/x₂ цепной дроби числа a. Целочисленным точкам (x₁,x₂), лежащим на ребрах R_j ломаных ∂ K_i, соответствуют промежуточные дроби цепной дроби числа a (см. [2, с. 21]). Число целочисленных точек на ребре, минус один равно неполному частному цепной дроби и т.д. (см. рис. 1).

Вороной [28, отдел I] предложил такую интерпретацию цепной дроби. Пусть на плоскости X=(x₁,x₂) заданы две линейные формы l₁(X)=x₁-ax₂ и l₂(X)=bx₁+gx₂. Значения пары форм l₁(X) и l₂(X) в целочисленной точке X ≠ 0 называются относительным минимумом, если нет другой целочисленной точки Y ≠ 0, для которой

|l1(Y)| ≤ |l1(X)|,    |l2(Y)| ≤ |l2(X)|    и    |l1(Y)|+|l2(Y)| < |l1(X)|+|l2(X)|.

Вороной показал, что все точки X, в которых пара форм l₁(X) и l₂(X)=X₂ имеет относительные минимумы, соответствуют всем подходящим дробям цепной дроби числа a, и их последовательность по убыванию |l₁(X)| и возрастанию |l₂(X)| соответствует последовательности подходящих дробей. На рис. 2 в I-м квадранте плоскости |l₁|, |l₂| для каждого относительного минимума (|l₁^(k)|, |l₂^(k)|) заштрихован прямоугольник |l₁| ≤ |l₁^(k)|, |l₂| ≤ |l₂^(k)|, в котором нет точек (|l₁(X)|, |l₂(X)|) для целочисленных X ≠ 0. Если точки X=B_k-1 и X=B_k соответствуют двум соседним относительным минимумам, то один шаг алгоритма цепных дробей состоит в переходе от базиса B_k-2, B_k-1 к базису B_k-1, B_k по формулам (3).

В [41] автор предложил такую конструкцию. Пусть в R² заданы две однородные линейные формы l₁(X)=l₁₁x₁+l₁₂x₂ и l₂(X)=l₂₁x₁+l₂₂x₂, причем l₁₁a+l₁₂=0. Рассматриваются только точки полуплоскости l₂(X) ≥ 0. На плоскости с координатами m₁(X)=|l₁(X)|, m₂(X)=|l₂(X)|, M(X)=(m₁(X),m₂(X)) рассмотрим множество Z² точек M(X) для всех целочисленных точек X ∈ Z² кроме нуля. Пусть M - выпуклая оболочка множества Z². Граница ∂ M множества M является ломаной линией, состоящей из вершин V_k и ребер U_k. Она обладает следующими свойствами.

1. Всякая вершина V_k является точкой относительного минимума пары форм l₁, l₂, т.е. V_k=M(B_l) ∈ Z², но обратное, вообще говоря, не верно.

2. На каждом ребре U_k нет точек множества Z², кроме вершин.

3. Пусть V_k=M(B_l) и V_k+1=M(B_{l ′} ) - две соседние вершины ломаной ∂ M, тогда det(B_lB_{l ′} )= ± 1. Если вектор (1,a) лежит между векторами B_l и B_{l ′} , то V_k и V_k+1 суть соседние относительные минимумы (им соответствуют соседние подходящие дроби b_l1/b_l2 и b_{l ′ ,1}/b_{l ′ ,2} цепной дроби числа a, где (b_l1,b_l2)=B_l). Если вектор (1,a) не лежит между векторами B_l и B_{l ′} , то между относительными минимумами V_k и V_k+1 имеется еще один и только один относительный минимум W_k=M(B_l+1) ∈ Z².

4. Если число a является квадратичной иррациональностью, то последовательности V_k и B_l периодичны, начиная с некоторого номера.

Последовательность вершин V_k ломаной ∂ M, занумерованные в порядке убывания |l₁| и возрастания |l₂|, назовем выпуклой цепной дробью. Ее можно получить как подходящие дроби цепной дроби вида

b0▒  1 b1▒  1 b2▒  ··· ,

где b_i - натуральные числа.

Пример 1.1. Пусть a =(3+ √ {21})/6=1.2637626╝, l₁(X)=x₁-
-ax₂, l₂(X)=x₂. Для a правильная цепная дробь периодична:

a=1+  1 3+  1 1+  1 3+  ··· .

Последовательные подходящие дроби суть

1,      4 3 ,      5 4 ,      19 15 ,      24 19 ,      91 72 ,      115 91 ,      436 345 , … .

Вершинам ломаной ∂ M соответствуют только подходящие дроби с нечетными номерами. Они являются также подходящими дробями цепной дроби

1+  1 4-  1 5-  1 5-  ··· .

(1.1)

Ребра и вершины ломаной ∂ M показаны на рис. 2 жирными отрезками и жирными точками. Выпуклая цепная дробь (1.1) также является диагональной цепной дробью [50;51;40, с. 39]. Но они не всегда совпадают, как показывает следующий пример.

Пример 1.2. Пусть a =(1+ √ 3)/2=1.3660254╝, l₁(X)=x₁-ax₂, l₂(X)=x₂. Для a правильная цепная дробь периодична:

a=1+  1 2+  1 1+  1 2+  ··· ,

и выпуклая цепная дробь совпадает с правильной. Но диагональная цепная дробь такова

1+  1 3-  1 4-  1 4-[ 1/(4-  ···)] .

Замечание 1.1. Вообще говоря, выпуклая цепная дробь отличается от цепной дроби до ближайшего целого [52;40, с. 39], ибо первая всегда дает наилучшие приближения к числу a, а вторая - не всегда [53, с. 27].

§ 2. Вычисление выпуклой цепной дроби

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

a+  1 1+  1 b+b ,

где b < 1, на агрегат a+1-1/(b+1+b), как это сделано в примере 1.1 (к этим местам относятся все случаи с b ≥ 3 и некоторые случаи с b=2). Однако можно вычислять ее последовательно шаг за шагом.

Опишем один шаг такого вычисления. Пусть в качестве базиса взяты точки [(B)\tilde]_k и [(B)\tilde]_k+1, соответствующие соседним вершинам V_k и V_k+1 ломаной ∂ M. Найдем точку [(B)\tilde]_k+2. Положим E₁=[(B)\tilde]_k+1, E₂=[(B)\tilde]_k - единичные векторы. Пусть в этом базисе вектор A имеет вид A=(a₁,a₂), где a₁ > |a₂| > 0. Для простоты будем считать, что |a₂|=1. Пусть линейные формы l₁(X) и l₂(X) в этом базисе имеют вид

l1(X)=a2x1-a1x2,    l2(X)=l21x1+l22x2,    l21 > 0,    sgn l22=sgn a2.

Точку [(B)\tilde]_k+2 ищем на прямой

x2=sgn a2=a2.

(2.1)

Пусть a=[a₁/|a₂|], тогда ближайшими к точке персечения прямой (2.1) с лучом lA, l > 0 являются две целочисленные точки, лежащие на прямой (2.1): с x₁=a и с x₁=a+1 (см. рис. 3). Следовательно, из двух точек B ′ =(a,a₂) и B"=(a+1,a₂) надо выбрать такую, которой соответствует точка V_k+2, являющейся вершиной ломаной ∂ M. Предшествующие две вершины этой ломаной суть

Vk=M( ~ B   k  )=(a1,|l22|),    Vk+1=M( ~ B   k+1  )=(1,l21).

Далее

M ′ =M(B ′ )=(a1-a,l21a+|l22|),

M"=M(B")=(a+1-a1,l21(a+1)+|l22|).

Пусть C=(c₁,c₂) и D=(d₁,d₂) две точки плоскости Y=(y₁,y₂). Проведенная через них прямая пересекает ось y₂ в точке

y2(C,D)=   ú ú ú ú c1 d1 c2 d2 ú ú ú ú c1-d1 .

(2.2)

Вычислим значения (2.2) для двух пар точек

y2(Vk+1,M ′ )    и    y2(Vk+1,M"),

(2.3)

и в качестве точки [(B)\tilde]_k+2 возьмем ту из точек B ′ и B", для которой значения y₂ в (2.3) меньше (см. рис. 4).

Выбрав точку [(B)\tilde]_k+2, переходим к базису [(B)\tilde]_k+1, [(B)\tilde]_k+2 и т.д.

§ 3. Трехмерные обобщения геометрических конструкций

Клейн [26,38] предложил трехмерный аналог своей двумерной интерпретации цепной дроби. Пусть в R³ заданы три плоскости

Li={X: бLi,Xс = 0},    i=1,2,3,

пересекающиеся в нуле X=0. Здесь X О R³, L_i О R³_*, б · , · с означает скалярное произведение, и пространство R³_* двойственно пространству R³. Каждому набору S = (s₁,s₂,s₃), где s_i= ± 1, соответствует свой октант

OS={X: si бLi,Xс ≥ 0,    i=1,2,3},

ограниченный плоскостями L₁, L₂, L₃. В каждом октанте O_S рассматривается выпуклая оболочка K_S всех целочисленных точек X ∈ O_S, X ≠ 0. Ее граница ∂ K_S является выпуклой двумерной многогранной поверхностью, состоящей из вершин, ребер и граней. Ее вершины должны давать наилучшие целочисленные приближения в октанте O_S к плоскостям L_i и к прямым, являющимся их пересечением.

В работах [16-23,42-46] многогранники Клейна были вычислены для ряда однородных кубических форм с целыми коэффициентами вида

h(X)=бL1,XсбL2,XсбL3,Xс,

(3.1)

каждая из которых соответствует корням свего кубического уравнения. Оказалось, что они устроены довольно сложно и разнообразно. На сайте [46] приведено много примеров плоских логарифмических проекций многогранников Клейна. На рис. 5 и 6 показаны ортогонализованные логарифмические проекции поверхностей многогранников Клейна ∂ K₊₊₊ для двух кубических форм

h7(X) = x13+2x12x2+x12x3-x1x22-x1x2x3-2x1x32-x23+ +2x22x3+x2x32-x33

и

~ h   7  (X) = -8x13+24x12x2-8x12x3-10x1x22+16x1x2x3+2x1x32+x23- -x22x3-9x2x32+x33

вида (3.1), взятых из [23] и соответствующих уравнению l³-2l²-l+1=0, в координатах

~ n   2  =  lnm1+2lnm2-lnm3 Ц6 ,     ~ n   3  =  lnm1-lnm3 Ц2 ,

где m_i(X)= | б L_i,X ñ|, i=1,2,3. Показаны проекции вершин, ребер и целочисленных точек, лежащих на ребрах и гранях поверхности ∂ K₊₊₊, а также - целочисленных точек X=B ′ , являющихся относительными минимумами для одного октанта O₊₊₊. Точка B ′ ∈ O_S, B ′ ≠ 0 называется точкой относительного минимума октанта O_S, если нет другой целочисленной точки B" ∈ O_S, B" ≠ 0, и такой, что

mi(B") ≤ mi(B ′),    i=1,2,3,    и

m1(B")+m2(B")+m3(B") < m1(B ′)+m2(B ′)+m3(B ′).

На рис. 5 и 6 рядом с каждой точкой указано значение модуля формы (3.1) в ней. Видна двупериодичность рис. 5 и 6. На них жирными линиями выделены границы фундаментальных областей.

На рис. 5 фундаментальная область состоит из одного шестиугольника и двух треугольников. У многогранника ∂K₊₊₊ грани, соответствующие шестиугольнику и малому треугольнику, удалены от начала координат на расстояние 1, а большие треугольные грани - на расстояние 3. На малых треугольных гранях нет внутренних целочисленных точек, на больших треугольных гранях имеется по одной целочисленной точке с |h|=|h₇|=8 и за гранью имеются шесть точек относительных минимумов с |h|=13 и 29. На шестиугольных гранях имеются по 9 целочисленных точек с |h|=7,8,13.

На рис. 6 фундаментальная область состоит из граней трех типов: (I) один равносторонний треугольник, (II) три скошенных треугольника и (III) три четырехугольника. Грань типа I отстоит от начала координат на расстояние 2, не содержит внутренних целочисленных точек и за ней имеется одна точка относительного минимума с |h|=|[(h)\tilde]₇|=49. Грань второго типа отстоит на расстояние 3, не содержит внутренних целочисленных точек и за ней имеются две точки относительного минимума с |h|=29 и 56. Грань типа III отстоит на расстояние 1 и имеет одну внутреннюю целочисленную точку с |h|=13. Кроме того, на некоторых ребрах имеются целочисленные точки с |h|=8.

В [16] предложен алгоритм вычисления многогранника Клейна одновременно с его сопряженным многогранником, но этот алгоритм нельзя рассматривать как обобщение алгоритма цепной дроби.

Пусть теперь в R³ заданы три линейные однородные формы

li(X)= б Li,X ñ,    Li ∈ R3*,    i=1,2,3.

(3.2)

Положим m_i(X)=|l_i(X)| и M(X)=(m₁(X),m₂(X),m₃(X)). Значение M(X) в целочисленной точке X ∈ Z³ называется относительным минимумом, если нет такой целочисленной точки Y ∈ Z³, что

M(Y) ≤ M(X)    и    ||M(Y)|| < ||M(X)||,

где ||M||=m₁+m₂+m₃. Вороной [28, отдел III] рассматривал в R³ точки X ∈ Z³, соответствующие относительным минимумам форм (3.2). Он предложил способ их частичного упорядочивания и построил алгоритм движения по этим упорядоченным точкам. Этот алгоритм он назвал обобщением алгоритма цепной дроби (см. также [47, гл. IV; 48]). По одному примеру вычислений алгоритмом Вороного имеется в работах [28, § 53; 47, § 59].

В [41] предложена следующая конструкция. Вектор-функция M(X) отображает пространство R³ с координатами X в пространство R³ с координатами M=(m₁,m₂,m₃), точнее - в его неотрицательный октант. При этом множество Z³\0 всех целочисленных точек X кроме X=0 отображается в некоторое множество Z³ в R³. Пусть M - выпуклая оболочка точек множества Z³ и ∂ M - ее граница. Очевидно, что M - это выпуклый многогранник и ∂ M - это выпуклая многогранная поверхность, состоящая из вершин V_i, ребер R_i и граней G_i.

Теорема 2.1. Каждая грань G_i поверхности ╢ ∂ M является треугольником с вершинами

Vj=M(Bj),    Bj ∈ Z3,    j=1,2,3,

(3.3)

она не содержит других точек из множества Z³.

Теорема 2.2. Если грань G_i поверхности ∂ M имеет вершины (3.3) и det(B₁B₂B₃)=0, то один из векторов B₁,B₂,B₃ является суммой двух остальных.

Для грани G_i поверхности ∂ M с вершинами (3.3) положим w(G_i)=|det (B₁B₂B₃)|. На рис. 7 и 8, взятых из [49], в координатах

n1=lnm1,    n2=lnm2

(3.4)

показаны логарифмические проекции поверхности ∂ M для форм h₇ и [(h)\tilde]₇, многогранники Клейна для которых показаны на рис. 5 и 6 соответственно. На рис. 7 и 8 показаны вершины и ребра, а также точки относительных минимумов. Для каждой точки Y=M(X) указаны значение модуля формы h(X) и значение вектора X. Жирными линиями показаны границы фундаментальных областей. В них для каждой грани G_i указано значение w(G_i). Для обеих форм в вершинах многогранника ∂ M имеем |h|=1.

На рис. 7 фундаментальная область состоит из 6 треугольников, два имеют w =1 и четыре - w =0. В ней есть одна точка относительного минимума, соответствующая точке, лежащей в центре большой треугольной грани рис. 5. Следовательно, не все относительные минимумы соответствуют вершинам многогранников Клейна, как это было в двумерном случае. Очевидно, что всем вершинам многогранника ∂ M соответствуют вершины многогранников Клейна, но обратное не верно.

На рис. 8 фундаментальная область состоит из двух треугольников (для обоих w =1) и содержит четыре точки относительных минимумов, в одной |h|=|[(h)\tilde]₇|=7 и в трех |h|=8 (точка с |h|=8 у левой границы фундаментальной области лежит в ней, а точка с |h|=7 лежит в правом треугольнике). Все эти точки с |h|=7 и 8 соответствуют вершинам многогранников Клейна. Здесь все вершины многогранников Клейна являются относительными минимумами.

Наконец, на рис. 9 и 10 в координатах (3.4) показаны логарифмические проекции многогранников ∂ M форм h₇ и [(h)\tilde]₇ соответственно вместе со всеми точками, как лежащими на поверхностях многогранников Клейна ∂ K_S, так и являющимися их относительными минимумами в октантах.

Из рис. 7-10 видно, что количество относительных минимумов Вороного существенно меньше, чем точек Клейна, а количество вершин многогранников ∂ M еще меньше.

Предлагаемое ниже обобщение цепной дроби является направленным движением по поверхности ∂ M, один шаг которого дает переход от грани с w =1 к ближайшей грани с этим же свойством.

§ 4. Алгоритм движения по поверхности ∂ M

Лемма 4.1. Пусть в R³ заданы три точки U=(u₁,u₂,u₃), V=(v₁,v₂,v₃) и W=(w₁,w₂,w₃). Проходящая через них плоскость пересекает третью координатную ось в точке

y3(U,V,W)= det  (UVW)   ú ú ú ú u1 v1 u2 v2 ú ú ú ú + ú ú ú ú v1 w1 v2 w2 ú ú ú ú + ú ú ú ú w1 u1 w2 u2 ú ú ú ú   .

(4.1)

Пусть в R³ заданы три линейные формы (3.2) и такой вектор A=(a₁,a₂,a₃), что l₁(A)=l₂(A)=0. Обозначим через pR³ полупространство l₃(X) ≥ 0. Пусть A ∈ pR³ (этого всегда можно достичь изменением знака вектора A). Наша цель - построить целочисленные приближения к лучу mA, m > 0.

Предположим сначала, что на поверхности ∂ M у всех граней

w ≤ 1.

(4.2)

Пусть векторы B₁,B₂,B₃ ∈ pZ³ образуют базис. Тогда мы имеем l_ij[(   def) || ( = )]  l_i(B_j), i,j=1,2,3 и такой вектор L = (l₁,l₂,l₃), что l₁B₁+l₂B₂+l₃B₃=A. При этом ∑ _j=1³l_ijl_j=0, i=1,2. Эти начальные данные удобно записать в виде таблицы

B1 l11 l21 l31 l1 B2 l12 l22 l32 l2 B3 l13 l23 l33 l3.

(4.3)

При этом M_i=M(B_i), т.е. m_ij=|l_ij|, i,j=1,2,3. Для точки M или множества точек, например G_i, в пространстве R³ чертой сверху [`(M)] или [`(G)]_i будем обозначать их ортогональные проекции на плоскость (m₁,m₂).

Переход к другому базису B₁ ^′ ,B₂ ^′ ,B₃ ^′ состоит из последовательного выполнения следующих 5 шагов.

Шаг 1. Первым делом на плоскости (m₁,m₂) надо выяснить взаимное расположение трех точек [`(M)]<sub>j</sub>=(|l<sub>1j</sub>|,|l<sub>2j</sub>|)[(   def) || ( = )]  (m<sub>1j</sub>,m<sub>2j</sub>), j=1,2,3. А именно, эти точки являются вершинами треугольника. Каждая его сторона имеет внешнюю нормаль. Возьмем такую строну треугольника, для которой обе компоненты вектора внешней нормали отрицательны. Пара точек из [`(M)]₁, [`(M)]<sub>2</sub>, [`(M)]₃, лежащих на этой стороне, является выделенной. Технически выделение такой пары точек можно сделать либо на рисунке, либо вычислениями, которые описаны в [41,§ 4] и повторяются здесь в § 6. Если таких точек нет, то алгоритм не работает. Если таких сторон две, т.е. имеется две пары выделенных точек, то алгоритм разветвляется, и надо его продолжить для каждой из этих пар отдельно. Пусть для определенности выделены [`(M)]<sub>1</sub> и [`(M)]₂. Прямую, проходящую через них, обозначим L. Для простоты предположим, что ее нормальный вектор D=(d₁,d₂) положителен.

Шаг 2. Вычисляем a_i=[l_i/|l₃|], i=1,2,3.

Шаг 3. Для каждой из шести точек

M(B1+B2)    def =     U1,    M(B1-B2)    def =     U2; M(a1B1+a2B2+a3B3)    def =     V1, M((a1+1)B1+a2B2+a3B3)    def =     V2, M(a1B1+(a2+1)B2+a3B3)    def =     V3, M((a1+1)B1+(a2+1)B2+a3B3)    def =     V4

(4.4)

выясняем расположение ее проекции [`(U)]<sub>i</sub>, [`(V)]_j относительно прямой L. Точки U_i, V_j, у которых проекции [`(U)]<sub>i</sub>, [`(V)]_j лежат правее прямой L, отбрасываем. Оставляем только точки, проекции которых лежат левее прямой L.

Лемма 4.2. Из двух точек [`(U)]<sub>1</sub>, [`(U)]₂ не более одной точки лежит левее прямой L.

Лемма 4.3. Из четырех точек [`(V)]<sub>1</sub>-[`(V)]₄ хотя бы одна лежит левее прямой L.

Шаг 4. Для каждой из оставшихся точек (4.4) по лемме 4.1 вычисляем точку пересечения плоскости, проведенной через точки M₁,M₂ и эту точку, с третьей координатной осью. Из этих значений выбираем наименьшее и соответствующую ему точку U_i или V_j.

Шаг 5. Если выбранное на шаге 4 значение соответствует одной из точек U_i, то делаем шаг 5а). Если оно соответствует одной из точек V_i, то делаем шаг 5б).

Шаг 5а. Пусть выбрана точка U₁. Рассматриваем треугольник с вершинами [`(M)]<sub>1</sub>, [`(M)]₂, [`(U)]<sub>1</sub>. Из двух его ребер, инцидентных с вершиной [`(U)]₁, выбираем то ребро, у которого внешняя нормаль отрицательна (т.е. лежит в III-м квадранте). Если таких ребер нет, то алгоритм прекращается. Если их два, то алгоритм разветвляется. Пусть точка [`(M)]₂ принадлежит выбранному ребру. Тогда из двух векторов B₁ и B₂ оставляем B₂. От базиса B₁,B₂,B₃ переходим к базису B₄=B₁+B₂, B₂,B₃. Выписываем матрицу N, для которой

ж з з з и B1ў B2ў B3ў ц ч ч ч ш    def =      ж з з з и B4 B2 B3 ц ч ч ч ш = N ж з з з и B1 B2 B3 ц ч ч ч ш ,    N= ж з з з и 1 1 0 0 1 0 0 0 1 ц ч ч ч ш .

Матрица N^*-1 дает преобразование

Lў=N*-1L,    N*-1= ж з з з и 1 0 0 -1 1 0 0 0 1 ц ч ч ч ш ,

где звездочка означает транспонирование. Если была выбрана точка U₂, то B₄=B₁-B₂ или B₂-B₁, чтобы B₄ ∈ pR³, и соответственно меняются матрицы N и N^*-1.

Шаг 5б. Пусть выбрана точка V_j=M(B₃ ^′ ), где B₃ ^′ =[(a)\tilde]₁B₁+[(a)\tilde]₂B₂+a₃B₃ согласно (4.4). Тогда от базиса B₁,B₂,B₃ переходим к базису B₁ ^′ =B₁, B₂ ^′ =B₂ ^′ , B₃ ^′ =B₃ ^′ =[(a)\tilde]₁B₁+[(a)\tilde]₂B₂+a₃B₃ по формулам

ж з з з и B1ў B2ў B3ў ц ч ч ч ш =N ж з з з и B1 B2 B3 ц ч ч ч ш ,    N= ж з з з з и 1 0 0 0 1 0 ~ a   1  ~ a   2  a3 ц ч ч ч ч ш .

При этом

Lў=N*-1L,    N*-1= ж з з з з з и 1 0 -a3 ~ a   1  0 1 -a3 ~ a   2  0 0 a3 ц ч ч ч ч ч ш .

Векторы B₁ ^′ ,B₂ ^′ ,B₃ ^′ дают новый базис; вектор L ′ - значение вектора A в этом базисе. Таким образом, переход от старого базиса B₁,B₂,B₃ к новому базису B₁ ^′ ,B₂ ^′ ,B₃ ^′ окончен.

Теорема 4.1. В предположении (4.2) если базису B₁,B₂,B₃ соответствовала грань поверхности ∂ M, то указанный переход к другому базису дает другую грань поверхности ∂ M с вершинами M₁,M₂ и U_i или V_j.

Теорема 4.2. В предположении (4.2) если базису B₁,B₂,B₃ соответствовала грань поверхности ∂ M, после нескольких указанных переходов к новому базису получен базис [(B)\tilde]₁,[(B)\tilde]₂,[(B)\tilde]₃ и в последнем переходе была выбрана точка типа V_j вида (4.4), то новому базису [(B)\tilde]₁,[(B)\tilde]₂,[(B)\tilde]₃ также соответствует грань поверхности ∂ M с вершинами M([(B)\tilde]_i),i=1,2,3.

Замечание 4.1. Выше дана самая простая и общая формулировка перехода к другому базису. Можно выделить различные случаи и подслучаи, когда этот переход упрощается. Например, если l₁₁l₁₂ и l₂₁l₂₂ < 0, то можно не рассматривать точку U₂; если l₁₁l₁₂ и l₂₁l₂₂ > 0, то - точку U₁. Однако, эта общая форма перехода наиболее удобна для программирования.

Замечание 4.2. Если исходному базису не соответствует грань поверхности ∂ M, то предложенный алгоритм после нескольких переходов к другому базису выводит на грань поверхности ∂ M.

Замечание 4.3. Если для исходного базиса B₁,B₂,B₃ треугольник [`(G)] с вершинами [`(M)](B₁), [`(M)](B<sub>2</sub>), [`(M)](B₃) таков, что все внешние нормали к его сторонам не лежат в третьем квадранте, т.е. не имеют отрицательными обе компоненты, то надо либо произвольно перейти к другому базису, подобрав его так, чтобы это свойство было выполнено, либо сделать этот преход по алгоритму, соответствующему приближению луча m[(A)\tilde]: l₂([(A)\tilde])=l₃([(A)\tilde])=0 или луча m[([(A)\tilde])\tilde]: l₃([([(A)\tilde])\tilde])=l₁([([(A)\tilde])\tilde])=0, где m > 0.

Замечание 4.4. Если у треугольника [`(G)] из предыдущего замечания внешние нормали к двум сторонам лежат в третьем квадранте, то алгоритм ветвится: надо сделать переходы к новым базисам, соответствующие обеим этим сторонам, и продолжать для них алгоритм.

Если предположение (4.2) не выполнено, то для треугольника G_i поверхности ∂M с w(G_i) > 1 алгоритм дает последовательность таких треугольников D_ik с w(D_ik)=0 или 1, которые расположены за треугольником G_i и проекции которых [`(D)]<sub>ik</sub> расположены внутри проекции [`(G)]_i. Причем первый из этих треугольников D_ik имеет с треугольником G_i общее ребро. Через несколько шагов алгоритм выходит на другое ребро треугольника G_i и продолжает двигаться по треугольникам поверхности ∂ M. Получается выпукло-вогнутая поверхность, которую обозначим ∂ N₃.

Например, если w(G_i)=2, то имеется точка относительного минимума W_i, проекция которой [`(W)]<sub>i</sub> лежит внутри проекции [`(G)]_i треугольника G_i. Эта точка получается при применении алгоритма к тому ребру R₁ треугольника G_i, проекция которого [`(R)]<sub>1</sub> имеет положительный вектор внешней нормали по отношению к треугольнику [`(G)]_i. На точку W_i и ребра R_k треугольника G_i натянуты три треугольные грани D_ik с w(D_ik)=1, k=1,2,3. Алгоритм сначала выходит на грань D_i1, затем на одну из граней D_i2 или D_i3, а потом - на грань поверхности ∂ M с w =1, примыкающую к грани G_i по соответствующему ребру R₂ или R₃. У поверхности ∂ M каждую грань G_i с w(G_i)=2 заменяем тройкой граней D_ik, а грани G_i с w(G_i) ≤ 1 оставим неизменными. В результате получим многогранную поверхности ∂ N₃, если для поверхности ∂ M все грани G_i имеют w(G_i) ≤ 2.

Гипотеза 4.1. Для поверхности ∂ M всегда все грани G_i имеют w(G_i) ≤ 2.

В [41, § 3] предложен алгоритм движения по поверхности ∂ N₃, который требует меньшего объема вычислений, чем предложенный здесь. Однако, алгоритм из [41] не всегда дает треугольники поверхности ∂ N₃.

§ 5. Сравнение точек различных типов

В двумерном случае (n=2), рассмотренном в §§ 1 и 2, было выделено три типа целочисленных точек X ∈ Z²:

1. Точки Клейна, которые лежат на ломаных Клейна; им соответствуют подходящие и промежуточные дроби. Их множество обозначим K.

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

3. Вершины выпуклой ломаной ∂ M; им соответствуют подходящие дроби выпуклой цепной дроби. Их множество обозначим M.

Очевидны включения

K ⊃ L ⊃ M.

В трехмерном случае (n=3), рассмотренном в §§ 3-6, было выделено 5 типов целочисленных точек X ∈ Z³:

1. Относительные минимумы октантов O_S, включая точки на поверхностях ∂ K_S многогранников Клейна K_S. Их множество обозначим через J.

2. Точки, лежащие на поверхностях ∂ K_S многогранников Клейна K_S. Их множество обозначим K.

3. Точки, соответствующие относительным минимумам Вороного. Их множество обозначим L.

4. Точки, соответствующие вершинам многогранных поверхностей ∂ N₁, ∂ N₂, ∂ N₃. Их множество обозначим N.

5. Точки, соответствующие вершинам поверхности ∂ M. Их множество обозначим M.

Очевидны включения

J ⊃ K,    J ⊃ L ⊃ N ⊃ M.

Возможно справедливо и включение K ⊃ L. По крайней мере, автору не известно ни одного контрпримера.

§ 6. Упорядочивание трех точек

Упорядочивать три точки [`(M)]_j=(|l_1j|,|l_2j|), i=1,2,3 можно следующим образом. Сначала среди чисел |l_1j| выберем наименьшее, и аналогично среди чисел |l_2j|, i=1,2,3. В соответствующих строках таблицы (4.3) поставим звездочки. Будем предполагать, что это разные строки. Пусть для определенности это первые две строки и в них

mi*= min {|li1|,|li2|},    mi**= max {|li1|,|li2|},     i=1,2.

Если в третьей строке таблицы (4.3) хотя бы для одного i=1,2 число |l_i3| > m_i^**, то точка (|l₁₃|,|l₂₃|) лежит правее прямой, проходящей через точки [`(M)]<sub>1</sub> и [`(M)]₂. Эту прямую обозначим через L. Нормальный вектор к прямой L есть

D=(||l12|-|l22||,||l21|-|l11||).

Положение точки [`(M)]₃ относительно прямой L определяется знаком разности

бD, - M   1  с-бD, - M   3  с.

(6.1)

Если она положительна, то точка [`(M)]<sub>3</sub> лежит левее прямой L. В этом случае обе прямые, проведенные через пары точек [`(M)]₁,[`(M)]<sub>3</sub> и [`(M)]₂,[`(M)]₃ являются левыми, т.е. возникают два подслучая, и оба надо рассмотреть. Если разность (6.1) отрицательна, то прямая L является левой и можно переходить к шагу 2.

Автор благодарит В.И. Парусникова за примеры поверхности ∂ M с w(G_i)=2 и за помощь в подготовке рисунков 5-10.

 

Список литературы

1.     Венков Б.А. Элементарная теория чисел. М.-Л.: ОНТИ, 1937.

2.     Хинчин А.Я. Цепные дроби. 3-е изд. М.: Физматгиз, 1961.

3.     Wallis J.A. Arithmetica infinitorum, 1655.

4.     Euler L. De fractinibus continuis // Comm. Acad. Sci. Imper. Petropol., 1737, v. 9.

5.     Lagrange J.L. Complement chez Elements dâalgebre etc. par M.L. Euler, t. III, 1774.

6.     Euler L. De relatione inter ternas pluresve quantitates instituenda // Petersburger Akademie Notiz. Exhib. August 14, 1775 // Commentationes arithmeticae collectae. V. II. St. Petersburg, 1849. P. 99-104.

7.     Jacobi C.G.J. Allgemeine Theorie der Kettenbruchänlichen Algorith-
men, in welchen jede Zahl aus drei vorhergehenden gebildet wird // J. Reine Angew. Math., 1868. V. 69. P. 29-64. // Gesammelte Werke, Bd. IV. Berlin: Reimer, 1891. S. 385-426.

8.     Jacobi C.G.J. Ueber die Auflösung der Gleichung a₁x₁+a₂x₂+╝+a_nx_n=f_n // J. Reine Angew. Math. 1868. V. 69. P. 21-28.

9.     Poincare H. Sur une generalization des fractionés continues // C.R. Acad. Sci. Paris. Ser. 1. 1884. V. 99. P. 1014-1016.

10. Brun V. En generalisation av Kjedebroken // Skrifter utgit av Videnskapsselskapeti Kristiania. I. Matematisk-Naturvidenskabelig Klasse 1919. N 6; 1920. N 6.

11. Perron O. Grundlagen für eine Theorie des Jacobischen Ketten-bruchalgorithmus // Math. Ann. 1907. V. 64. P. 1-76.

12. Bernstein L. The Jacobi-Perron algorithm - its theory and application. LNM 207. Berlin/Heidelberg/New York: Springer Verlag, 1971.

13. Пустыльников Л.Д. Обобщенные цепные дроби и эргодическая теория // УМН, 2003, т. 58, N 1, с. 113-164.

14. Schweiger F. Multidimensional Continued Fractions. Oxford Univ. Press: New York, 2000.

15. Hermite Ch. Correspondance dâHermite et de Stieltjes. T. II, lettres 232, 238, 408. Gauthier-Villars, Paris, 1905.

16. Брюно А.Д., Парусников В.И. Многогранники Клейна для двух кубических форм Давенпорта // Матем. заметки. 1994. Т. 56. N 4. С. 9-27.

17. Брюно А.Д., Парусников В.И. Сравнение разных обобщений цепных дробей // Матем. заметки, 1997, т. 61, N 3, с. 339-348.

18. Parusnikov V.I. Klein polyhedra for complete decomposable forms // Number theory. Dyophantine, Computational and Algebraic Aspects. Editors: K. Györy, A. Pethö and V.T. Sós. De Gruyter. Berlin, New York. 1998, p. 453-463.

19. Парусников В.И. Многогранники Клейна для четвертой экстремальной кубической формы // Матем. заметки, 2000, т. 67, N 1, с. 110-128.

20. Парусников В.И. Многогранники Клейна с большими гранями // Препринт N 93. М.: ИПМ им. М.В.Келдыша, 1997.

21. Парусников В.И. Многогранники Клейна для пятой экстремальной кубической формы // Препринт N 69. М.: ИПМ им. М.В.Келдыша, 1998.

22. Парусников В.И. Многогранники Клейна для шестой экстремальной кубической формы // Препринт N 69. М.: ИПМ им. М.В.Келдыша, 1999. 31 с.

23. Парусников В.И. Многогранники Клейна для седьмой экстремальной кубической формы // Препринт N 79. М.: ИПМ им. М.В.Келдыша, 1999. 32 с.

24. Lejune Dirichlet G.P. Verallgemeinerung eines Satzes aus der Lehre von den Kettenbrüchen nebst einigen Anwendungen auf die Theorie der Zahlen // S.-B. press. Akad. Wiss. 1842. S. 93-95 // Werke. Bd. I. Berlin: Reimer, 1889, S. 635-638.

25. Hermite Ch. Lettres de M. Ch. Hermite á M. Jacobi sur differents objets de la theorie des nombres // J. Reine Angew. Math. 1850, Bd. 40, S. 261-315 // Oeuvres, T. I, Paris: Gauther-Villares, 1905, p. 100-163 // Opuscule Mathematica de Jacobi, v. II.

26. Klein F. Über eine geometrische Auffassung der gewöhnlichen Kettenbruchentwicklung // Nachr. Ges. Wiss. Göttingen Math.-Phys. Kl. 1895. N 3. S. 357-359.

27. Minkowski H. Generalisation de le theorie des fractions continues // Ann. Sci. Ec. Norm. Super. ser III, 1896, t. 13, p. 41-60. Also in: Gesamm. Abh. I, p. 278-292.

28. Вороной Г.Ф. Об одном обобщении алгорифма непрерывных дробей. Варшава: Из-во Варш. Ун-та, 1896. Также: Собр. соч. в 3-х томах. Киев: Из-во АН УССР, 1952. Т. 1. С. 197-391.

29. Скубенко Б.Ф. Минимумы разложимых кубических форм от трех переменных // Записки научных семинаров Ленинградского отделения математич. ин-та им. Стеклова (ЛОМИ). 1988, т. 168, с. 125-139.

30. Арнольд В.И. Цепные дроби. М.: МЦНМО, 2001.

31. Brentjes A.J. Multi-dimensional Continued Fraction Algorithms. Ma-
thematical Centre Tracts 145, Amsterdam: Mathematisch Centrum, 1981.

32. Buchmann J. On the period length of the generalized Lagrange algorithm // J. Number Theory, 1987, v. 26, p. 8-37.

33. Быковский В.А. Теорема Валена для двумерных подходящих дробей // Матем. заметки, 1999, т. 66, N 1, с. 30-37.

34. Hurwitz A. Ueber die angenäherte Darstellung der Zahlen durch rationale Brüche // Math. Ann. 1894. Bd. 44, S. 417-436.

35. Брюно А.Д. Разложения алгебраических чисел в цепные дроби // Журнал вычислительной матем. и матем. физики, 1964, т. 4, N 2, с. 211-221.

36. Lang S., Trotter H. Continued fractions of some algebraic numbers // J. Reine Angew. Math. 1972, Bd. 252, S. 112-134.

37. Старк Х.М. Объяснение некоторых экзотических непрерывных дробей, найденных Бриллхартом // Вычисления в алгебре и теории чисел (ред. Б.Б. Венков и Д.К. Фаддеев). М.: Мир, 1976, с. 155-171.

38. Klein F. Sur une representation geometrique du developpement en fraction continue ordinare // Nouv. Ann. Math. (3), 1896, Bd. 15, S. 327-331.

39. Klein F. Ausgewählte Kapitel der Zahlentheorie. Bd. I, Einleitung. Göttingen, 1896, S. 16-50.

40. Koksma J.F. Diophantische Approximationen. Berlin: Julius Springer, 1936.

41. Брюно А.Д. Правильное обобщение цепной дроби // Препринт N 86. М.: ИПМ им. М.В.Келдыша, 2003. 17 с.

42. Коркина Е. Двумерные цепные дроби. Самые простые примеры. // Труды Мат. ин-та им. Стеклова. 1995, т. 203, с. 143-166.

43. Lachaud G. Polyédre dâArnolâd et voile dâun cône simplicial: analogues du théoreme de Lagrange // C.R. Acad. Sci. Ser. 1. 1993. V. 317. P. 711-716.

44. Lachaud G. Polyedre dâArnolâd et voile dâun cône simplicial, analogues du théoreme de Lagrange pour les irrationnels de degré quelconque. Prétirage N 93-17. Marseille: Laboratoire de Mathématiques Discretes du C.N.R.S., 1993.

45. Kontsevich M.L., Suhov Yu. M. Statistics of Klein polyhedra and multidimensional continued fractions // Amer. Math. Soc. Transl. (2) 1999, v. 197, p. 9-27.

46. Briggs K. Klein polyhedra // http: // www.btexact.com/people/bri-
ggsk2/klein-polyhedra.html

47. Делоне Б.Н., Фаддеев Д.К. Теория иррациональностей третьей степени. Труды МИ АН, т. 11, М.-Л.: АН СССР, 1947.

48. Делоне Б.Н. Петербургская школа теории чисел. М.-Л.: АН СССР, 1947.

49. Брюно А.Д., Парусников В.И. Многогранники модулей троек линейных форм // Препринт N 93. М.: ИПМ им. М.В.Келдыша, 2003. 20 с.

50. Pipping N. Zur Theorie der Diagonalkettenbrüche // Acta Acad. Aboens., 1924, B. 3. 22 S.

51. Нечаев В.И. Диагональная цепная дробь // Математ. Энциклоп. М.: Советская Энциклоп., 1979, т. 2, с. 123.

52. Hurwitz A. Ueber eine besondere Art der Kettenbruch-Entwiklung reller Grössen // Acta math., 1889, B. 12, S. 367-405.

53. Касселс Дж.В.С. Введение в теорию диофантовых приближений. М.: Изд-во иностр. лит., пер. с англ., 1961.

 

File translated from T_EX by T_TH, version 3.40.
On 21 Dec 2004, 19:59.