Дальнейшее обобщение цепной дроби
( Further generalization of the continued fraction
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Брюно А.Д., Парусников В.И.
(A.D.Bruno, V.I.Parusnikov)

ИПМ им. М.В.Келдыша РАН

Москва, 2005
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты №№ 05-01-00050, 03-01-00027) и программы "Современные проблемы теоретической математики" ОМН РАН

Аннотация

Во введении обсуждается история цепной дроби и ее обобщений. Ранее авторами было предложено обобщение цепной дроби, дающее периодичность для кубической иррациональности с положительным дискриминантом. Здесь предлагается обобщение цепной дроби, дающее периодические разложения для кубической иррациональности с отрицательным дискриминантом. Речь идет о совместных рациональных приближениях числа и его квадрата. Сначала описывается строение наилучших целочисленных приближений в однородных координатах, в которых заданы две вещественные формы: линейная и квадратичная. Затем предлагается алгоритм вычисления приближений. Приведены примеры вычислений этим алгоритмом.

Abstract

In Introduction we discuss the history of the continued fraction and of its generalizations. Early authors proposed a new generalization of the continued fraction that gives periodicity for cubic irrationalities with positive discriminant. Here we propose a new generalization giving periodicity for cubic irrationalities with negative discriminant. We consider the simultaneous rational approximations of a number and its square. At first we describe the structure of the best integer approximations in the homogeneous coordinates when two real forms (linear and quadratic) are given. After that we propose an algorithm to compute the approximants. Examples of computations are given as well.

E-mail: bruno@keldysh.ru, parus@keldysh.ru

Введение

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

a₀=a₀a₁+a₂,    a₁=a₁a₂+a₃,    a₂=a₂a₃+a₄,…,

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

a=a₀+

 1

---

a₁+

 1

---

a2+	1 a3+  ^···

,

(1)

и

ж
з
з
и

a_k+1

a_k+2

ц
ч
ч
ш

=

ж
з
з
и

0	1
1	-ak

ц
ч
ч
ш

ж
з
з
и

a_k

a_k+1

ц
ч
ч
ш

,    a_k=[a_k/a_k+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

ц
ч
ч
ш

,    

det

ж
з
з
и

pk	pk-1
qk	qk-1

ц
ч
ч
ш

=± 1,

т.е векторы (a_k,a_k+1) и (p_k,q_k) принадлежат сопряженным плоскостям, и пара векторов (p_k,q_k), (p_k-1,q_k-1) может служить базисом в одной из них.

Цепные дроби (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, 33, 34].

Здесь предлагается обобщение цепной дроби, дающее периодическое разложение для кубической иррациональности с отрицательным дискриминантом. В 1850 г. Эрмит [16] предложил свое обобщение цепной дроби, которое использовал Шарв [17] для нахождения единиц простейших числовых полей. В 1896 г. Вороной [18, отдел II] рассмотрел линейную и квадратичную формы и предложил свой алгоритм нахождения их последовательных относительных минимумов (или наилучших приближений). Другие алгоритмы были предложены в [27-30] (см. [31, гл. 5]). Все они заключаются в вычислении последовательности целочисленных базисов с вложенными первыми октантами, содержащими приближаемую прямую. Два последних свойства последовательности базисов - излишнее ограничение на алгоритм, приводящее к его неоправданному усложнению.

Интерес одного из авторов к обобщению цепной дроби возник в связи с его работой [19] 1964 г., которая была повторена Ленгом [20] в 1972 г. (см. также Старк [21]). В [15, §§ 1,2] рассмотрены различные виды цепной дроби и их плоские интерпретации. Наиболее подходящей для обобщения оказывается диагональная цепная дробь, впервые введенная Минковским в 1896 г. [22, раздел I, случай W = 1], но без названия. В 1902 г. он ввел ее вторично, уже с названием [23] (см. также [24, 25, 26]).

§ 1. Постановка задачи

Пусть в пространстве R³ с координатами X=(x₁,x₂,x₃) заданы две формы - линейная

l1(X)=бJ,Xс

def =

j1x1+j2x2+j3x3

(1.1)

и квадратичная

l2(X)=бK,Xсб

K

,Xс,

(1.2)

где J=(j₁,j₂,j₃) - вещественный вектор, K=(k₁,k₂,k₃) - комплексный вектор, [`(K)] - комплексно сопряженный вектор и скобки б K,Xс[(   def) || ( = )]  k₁x₁+k₂x₂+k₃x₃ означают скалярное произведение. Произведение форм l_i(X) обозначим L(X):

L(X)=l1(X)l2(X).

(1.3)

Очевидно, что для X ∈ R³ обе формы l₁(X) и l₂(X) вещественны. Пусть вектор A таков, что l₂(A)=0. Тогда форма l₂(X) обращается в ноль на прямой X=mA, m ∈ R. Положим

mi(X)=|li(X)|,  i=1,2,

(1.4)

M(X)=(m1(X),m2(X)).

(1.5)

Говорят, что целочисленная точка X ∈ Z³ дает наилучшее приближение к прямой mA или к плоскости l₂(X)=0, если нет такой целочисленной точки Y ∈ Z³, Y ≠ 0, что

M(Y) ≤ M(X),  m1(Y)+m2(Y) < m1(X)+m2(X).

(1.6)

Задача: Найти наилучшие целочисленные приближения X к прямой mA со сколь угодно малым m₂(X) (не обязательно все).

§ 2. Основная конструкция

Введенная по (1.4), (1.5) вектор-функция M(X) отображает R³ в первый квадрант плоскости R²₊ с координатами M=(m₁,m₂). При этом в одну точку M ∈ R²₊ отображаются две окружности пространства R³ - одна при l₁ < 0 и другая при l₁ > 0. Поэтому ограничимся полупространством pR³=R³∩{l₁ > 0}. Пусть при этом отображении множество целочисленных точек X ∈ Z³, исключая X=0, переходит в множество Z², т.е. Z²=M(Z²\0). В случае общего положения в одну точку M может отображаться не более одной целочисленной точки X ∈ pZ³[(   def) || ( = )]  pR³∩Z³, т.е. целочисленный прообраз в pZ³ единственен.

Пусть M - выпуклая оболочка множества Z² и ∂M - ее граница. Очевидно, что ∂M - это выпуклая ломаная линия. Она состоит из вершин и ребер. Все вершины являются образами M(X) целочисленных точек X ∈ R³. Но на ∂ M могут быть еще образы целочисленных точек, расположенные внутри ребер. Пусть все образы целочисленных точек занумерованы последовательно целыми индексами в направлении роста m₁. Обозначим эти точки U_k=(u_1k,u_2k), u_1k < u_1,k+1, а их прообразы с l₁ > 0 обозначим F_k, т.е.

Uk=M(Fk),  k ∈ Z.

(2.1)

Лемма 2.1. Миноры матрицы (F_k-1F_k) не имеют общего делителя.

Для каждого k определим

w(k)=|

det

(Fk-1FkFk+1)|.

(2.2)

Очевидно, что w(k) принимает целые неотрицательные значения.

Лемма 2.2. Для кубических иррациональностей функция w(k) может принимать любые неотрицательные значения, включая ноль и сколь угодно большие целые числа.

Аналогичное утверждение для последовательных минимумов доказано в [30].

Алгоритм обычной цепной дроби дает последовательность базисов, и переход к следующему базису дается унимодулярной матрицей. В нашем трехмерном случае можно образовывать последовательность базисов, состоящую только из векторов F_k и связанных унимодулярными преобразованиями, только если w(k) принимает значения 0 и 1. Если же w(k) имеет значения большие единицы, то точек F_k не достаточно для образования такой последовательности базисов.

Каждой паре соседних точек U_k-1,U_k поставим в соответствие точку V ∈ R² следующим образом. Среди всех точек G ∈ Z³ выберем те, для которых

det	(Fk-1FkG)=-1,0,+1.

(2.3)

Согласно лемме 2.1 для каждого из этих трех значений имеется двумерная решетка точек G со свойством (2.3). Из этих точек G оставим только те, для которых m₁(G) > m₁(F_k) и обозначим G_k множество таких точек G. Теперь среди таких точек M(G) с G ∈ G_k выберем ту (обозначим ее M^*), для которой отрезок [U,M(G)] наиболее наклонен в сторону оси m₁, т.е. все точки M(G) с G ∈ G_k лежат не ниже прямой, проведенной через точки U_k и M^*. Технически это можно сделать, отмечая точку пересечения прямой, проходящей через точки U_k и M(G), с осью m₁. Легко заметить, что для M=M(G) это значение

m₁=h₁(U_k,M)=

det

|UM|

---

m₂-u_2k

.

(2.4)

Если для всех G ∈ G_k точки M(G) имеют m₂(G) > u_2k, то h₁(U_k,M(G)) < u_1k. В этом случае в качестве M^* берем то M(G) на котором достигается minh₁(U_k,M) по G ∈ G_k.

Если есть G ∈ G_k с m₂(G) < u_2k, то для них h₁(U_k,M(G)) > u_1k. В этом случае в качестве M^* берем то M(G), на котором достигается minh₁(U_k,M) для G: m₂(G) < u_2k. Этот отбор можно упростить, если положить

z1(Uk,M(G))=

1 h1-u1k

=

m2-u2k u2k(u1k-m1)

.

(2.5)

В качестве M^* берем ту точку M(G) с G ∈ G_k, на которой z₁(U_k,M(G)) достигает максимума. Если таких точек несколько, то берется ближайшая к точке U_k.

Итак, каждой паре соседних точек U_k-1,U_k поставлена в соответствие точка V_k=M^*. Если w = 0 или =1, то точка V_k совпадает с точкой U_k+1. Если w > 1, то точка V_k отлична от точки U_k+1 и лежит внутри выпуклого множества M (рис. 1).

Теорема 2.1. v_1k < u_1,k+1.

Аналогичное неравенство для вторых координат, v_2k > u_2,k+1, вообще говоря, неверно: зачастую v_2k < u_2,k+1.

Пусть прообраз точки V_k в pZ³ есть G_k, т.е. V_k=M(G_k).

Теорема 2.2. Если G_k ≠ F_k+1, то det(F_kG_kF_k+1) ≤ 1, det(G_kF_k+1G_k+1) ≤ 1.

Пусть P(l)=l³+al²+bl+c - многочлен с целыми коэффициентами и отрицательным дискриминантом. Он имеет три корня l₁,l₂,l₃, причем l₁ ∈ R, l₂=[`(l)]₃ ∈ C, где черта сверху означает комплексное сопряжение. Будем предполагать, что число l₁ иррационально. Введем векторы (вектор-строки)

J=(1,l1,l1^2),  K=(1,l2,l2^2)

(2.6)

и соответствующие вещественные формы (1.1),(1.2). Сопряженной к (2.6) парой форм будут формы, аналогичные (1.1),(1.2), но где вместо векторов (2.6) фигурируют вектора J^*,K^* - строки матрицы, обратной транспонированной матрице Вандермонда:

J^*=

1 3l1^2+2al1+b

(l1^2+al1+b,l1+a,1),

K^*=

1 3l2^2+2al2+b

(l2^2+al2+b,l2+a,1).

Обозначим U и V последовательности точек U_k и V_k, бесконечные в обе стороны, и W=U╚V. Аналогично, последовательности F и G ⊂ R³ и H = F╚G.

Теорема 2.3. Для форм (1.1),(1.2) с векторами (2.6) последовательность H (и W) периодична, т.е. существуют такие натуральное t и унимодулярная матрица T, что

Fk+t=TFk,  Gk+t=TGk,  k ∈ Z.

(2.7)

По периоду легко находится фундаментальная единица соответствующего числового поля [32].

§ 3. Алгоритм обобщенной цепной дроби

Сформулируем наши требования к алгоритму, который является обобщением цепной дроби.

a) Если начинать с произвольного базиса в R³, то через конечное число шагов он должен приводить к базису, составленному из векторов последовательности H.

b) Он должен давать последовательность унимодулярных матриц или последовательность базисов.

с) Он должен давать все точки последовательности F, начиная с некоторой.

d) Он должен давать точки последовательности G (или близкие к ним точки).

Пусть имеется базис

B1,B2,B3,

(3.1)

который упорядочен так, что m₁₁ < m₁₂ < m₁₃, где

Mi=M(Bi)=(m1i,m2i),  i=1,2,3.

(3.2)

Опишем один шаг алгоритма, приводящего к другому упорядоченному базису B₁′,B₂′,B₃′. Рассматриваем все точки

G=a1B1+a2B2+a3B3,

(3.3)

где

a1=-1,0,+1, a2,a3 ∈ Z,

(3.4)

и выберем из них ту, для которой

1) m₁(G) > m₁₃,

2) z₁(M₃,M′(G)) имеет наибольшее значение по всем точкам G.

Затем, если для выбранной точки (3.3) a₁ ≠ 0, то вместо B₁ включаем в базис вектор G и получаем новый базис B₂,B₃,B₄=G; если в (3.3) a₁=0, то G берем вместо B₂ и новый базис будет B₁,B₃,B₄=G.

Технически это можно сделать так. Пусть в базисе B₁,B₂,B₃ вектор A есть L = (l₁,l₂,l₃), т.е.

A

ж з з и

B1 B2 B3

ц ч ч ш

=L,

(3.6)

где все векторы - строки. Вычислим целые числа

a_i=[l_i/|l₁|],

i=1,2,3,

a₁=±1,

b_i=[l_i/|l₂|],

i=2,3,

b₂=±1,

c=[|b₃|/10]+1,

(3.5)

и положим

X₀=

a₁B₁

+a₂B₂

+a₃B₃,

X_k=

X₀

+kB₃,

-c ≤ k ≤ c,

Y₀=

X₀

+B₂,

Y_k=

Y₀

+kB₃,

-c ≤ k ≤ c,

Z_l=

b₂B₂

+lB₃,

-|b₃|-1 ≤ l ≤ |b₃|+1.

В качестве точек G берем все точки X_k,Y_k,Z_l. Из них отбираем те, для которых выполнено свойство 1) и среди них находим maxz₁(M₃,M(G)). Если выбрана одна из точек X_k или Y_k, то вместо B₁ берем выбранную точку G и получаем новый базис B₂,B₃,B₄=G=[(a)\tilde]₁B₁+[(a)\tilde]₂B₂+[(a)\tilde]₃B₃, т.е.

ж
з
з
и

B₁ў

B₂

B₃ў

ц
ч
ч
ш

=N

ж
з
з
и

B₁

B₂

B₃

ц
ч
ч
ш

,  N =

ж
з
з
з
и

0

1

0

0

0

1

~ a

1

~ a

2

~ a

3

ц
ч
ч
ч
ш

.

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

Lў=N^*-1L,  N^*-1 =

ж
з
з
з
з
и

-

~ a

1

~ a

2

1

0

-

~ a

1

~ a

3

0

1

~ a

1

0

0

ц
ч
ч
ч
ч
ш

,

где звездочка означает транспонирование и L - вектор-столбец.

Если выбрана одна из точек Z_l, то вместо B₂ берем выбранную точку G=Z_l=[(b)\tilde]₂B₂+[(b)\tilde]₃B₃ и получаем новый базис B₁,B₃,B₄=G, т.е.

ж
з
з
и

B₁ў

B₂ў

B₃ў

ц
ч
ч
ш

=N

ж
з
з
и

B₁

B₂

B₃

ц
ч
ч
ш

,  N =

ж
з
з
з
и

1

0

0

0

0

1

0

~ b

2

~ b

3

ц
ч
ч
ч
ш

.

При этом

Lў=N^*-1L,   N^*-1 =

ж
з
з
з
и

1

0

0

0

-

~ b

2

~ b

3

1

0

~ b

2

0

ц
ч
ч
ч
ш

.

Этот алгоритм запрограммирован и в § 4 приведено несколько примеров вычислений по нему.

У алгоритма два недостатка:

1. Он не гарантирует нахождение максимума z₁(M₃,M(G)) по всем G из (3.3), а максимум берется только по той части этого множества, которая представлена точками X_k,Y_k,Z_l. Однако этот недостаток исправляется тем, что на следующем шаге берется точка из той же плоскости a₁=-1,0,+1, т.е. этот максимум достигается не за один шаг.

2. Если точка M₃ лежит внутри множества M, а точка M₂ является вершиной ломаной ∂M, то может случиться, что точка M₄=M(G) не является оптимальной относительно точки M₂, а оптимальной относительно точки M₂ является точка M₅ (см. рис. 2). Алгоритм выйдет на точку M₅ после точки M₄ и, возможно, еще нескольких дополнительных шагов.

Теорема 3.1. Предложенный алгоритм обладает свойствами a) -d).

§ 4. Примеры.

Пример 1. Вороной [18, отдел II] вычислил период разложения вектора (1,r,r²), где r³=23. Период содержит 21 шаг его алгоритма. Наш алгоритм имеет период 16 шагов. Отвечающая ему алгебраическая единица кубического поля обратна единице, найденной Вороным, и совпадает с единицей, найденной Марковым.

В приведенных далее примерах величины d=d_k суть значения определителей

dk=

det

(Bk-2Bk-1Bk), k ≥ 3.

Пример 2. Рассматривается уравнение l³ +22l²+ 11l+ 25=0,

J ≈ (1, .393582e⁺ 0, .861731e⁺ 0 ).

k		Bk		d	L	l1(Bk)	l2(Bk)	[(a)\tilde]1	[(a)\tilde]2	[(a)\tilde]3
1	1	0	0		1	.1000e^+1	.1000e^+1
2	0	1	0		25	.2154e^+2	.1160e^+1
3	0	0	1	1	625	.4641e^+3	.1347e^+1	1	0	1
4	1	0	1	1	109	.4651e^+3	.2344e^+0	1	0	2
5	2	1	2	1	113	.9087e^+3	.1244e^+0	-1	2	3
6	8	3	7	-1	157	.3192e^+4	.4918e^-1	-1	0	2
7	15	6	13	1	85	.5919e^+4	.1436e^-1	-1	1	3
8	51	20	44	-1	235	.2004e^+5	.1173e^-1	-1	0	2
9	94	37	81	1	1	.3689e^+5	.2711e^-4	0	1	21
10	2025	797	1745	0	25	.7947e^+6	.3146e^-4	1	-9	22
11	43719	17207	37674	-1	109	.1716e^+8	.6353e^-5	0	-1	2
12	85413	33617	73603	0	113	.3352e^+8	.3371e^-5	1	1	3
13	300052	118095	258564	-1	157	.1178e^+9	.1333e^-5	-1	0	2
14	556385	218983	479454	1	85	.2184e^+9	.3893e^-6	-1	1	3
15	1883794	741427	1623323	-1	235	.7393e^+9	.3178e^-6

Период алгоритма t=7. При этом выпуклую ломаную образуют точки M(B_k) с номерами k=1, 4, 5, 6, 7, 9,11,12,13,14,15. Соответственно точки с номерами 2, 3, 8, 10 лежат за (выше) выпуклой ломаной. Значения модулей определителей det(B_iB_jB_k), где M(B_i),M(B_j),M(B_k) - соседние точки выпуклой ломаной, равны соответственно 1, 1, 1, 2,22, 1, 1, 1, 1.

Пример 3. Уравнение l³ +19l²+ 11l+ 18=0,

J ≈ (1,-.184569e⁺ 2, .340655e⁺ 3 ).

k		Bk		d	L	l1(Bk)	l2(Bk)	[(a)\tilde]1	[(a)\tilde]2	[(a)\tilde]3
1	0	1	0		191	.1638e^-2	.2941e^+0
2	1	0	0		324	.2941e^-2	.2778e^+0
3	0	0	1	-1	1	.3016e^-2	.8363e^-3	-1	0	19
4	0	-1	19	1	18	.5566e^-1	.8156e^-3	1	-10	18
5	1	-18	332	1	64	.9746e^+0	.1656e^-3	0	1	2
6	2	-37	683	0	8	.2005e^+1	.1006e^-4	-1	3	17
7	37	-683	12606	1	144	.3701e^+2	.9814e^-5	1	3	2
8	81	-1495	27593	1	1	.8100e^+2	.3113e^-7	0	1	18
9	1495	-27593	509280	0	18	.1495e^+4	.3036e^-7	-1	-9	18
10	26179	-483182	8918020	1	64	.2618e^+5	.6165e^-8	0	1	2
11	53853	-993957	18345320	0	8	.5385e^+5	.3746e^-9	-1	3	17
12	993957	-18345320	338596907	1	144	.9940e^+6	.3654e^-9

Период t=5. Выпуклую ломаную образуют точки M(B_k) с номерами 1, 3,5, 6, 8,10,11,12. Модули определителей det(B_iB_jB_k) для соседних точки выпуклой ломаной равны 1, 1, 2,18, 1, 1. Соответственно точки с номерами 2,4,7,9 лежат за выпуклой ломаной.

Пример 4. Уравнение l³ +16l²+ 8l+ 20=0, сопряженный случай,

J^* ≈ (1,-.155687e⁺ 2, .242383e⁺ 3 ).

k		Bk		d	L	l1(Bk)	l2(Bk)	[(a)\tilde]1	[(a)\tilde]2	[(a)\tilde]3
1	0	1	0		108	.1820e^-2	.2134e^+0
2	0	0	1		1	.4220e^-2	.8522e^-3
3	1	0	0	1	400	.5421e^-2	.2653e^+0	-1	15	0
4	0	-1	15	-1	27	.6148e^-1	.1579e^-2	1	0	1
5	0	-1	16	-1	20	.6570e^-1	.1095e^-2	1	7	9
6	1	-16	249	-1	65	.1027e^+1	.2276e^-3	-1	0	2
7	2	-31	483	1	87	.1993e^+1	.1570e^-3	-1	3	2
8	7	-109	1697	-1	1	.7001e^+1	.5137e^-6	-1	-1	16
9	109	-1697	26420	1	20	.1090e^+3	.6599e^-6	1	-6	16
10	1704	-26529	413021	1	65	.1704e^+4	.1372e^-6	1	-1	2
11	3306	-51470	801319	1	87	.3306e^+4	.9464e^-7	-1	3	2
12	11615	-180830	2815281	-1	1	.1162e^+5	.3096e^-9	-1	-1	16
13	180830	-2815281	43830156	1	20	.1808e^+6	.3978e^-9

Период t=4. Выпуклую ломаную образуют точки M(B_k) с номерами 1, 2,6, 7, 8,10,11,12. Модули определителей det(B_iB_jB_k) для соседних точки выпуклой ломаной равны 1, 1, 1,16, 1, 1. За выпуклой ломаной лежат точки с номерами 3,4,5,9, 13.

Пример 5. Уравнение l³ -4l²+ 25l+ 17=0, сопряженный случай,

J^* ≈ (1,-.165761e⁺ 0, .359480e^- 1 ).

k		Bk		d	L	l1(Bk)	l2(Bk)	[(a)\tilde]1	[(a)\tilde]2	[(a)\tilde]3
1	0	0	1		289	.3735e^+0	.7738e^+3
2	0	1	0		17	.6111e^+0	.2782e^+2
3	1	0	0	-1	1	.1000e^+1	.1000e^+1	1	-5	28
4	28	-5	1	-1	123	.3143e^+2	.3914e^+1	0	-1	-1
5	-29	5	-1	0	113	.3243e^+2	.3485e^+1	1	3	1
6	55	-9	2	-1	69	.6125e^+2	.1127e^+1	0	-1	1
7	84	-14	3	0	61	.9368e^+2	.6512e^+0	0	1	1
8	139	-23	5	0	11	.1549e^+3	.7100e^-1	1	1	10
9	1502	-249	54	1	47	.1674e^+4	.2807e^-1	1	3	1
10	2003	-332	72	1	27	.2233e^+4	.1209e^-1	0	1	1
11	3505	-581	126	0	13	.3907e^+4	.3327e^-2	0	1	2
12	9013	-1494	324	0	1	.1005e^+5	.9953e^-4	-1	-4	33
13	283270	-46955	10183	-1	123	.3158e^+6	.3895e^-3	0	-1	-1
14	-292283	48449	-10507	0	113	.3258e^+6	.3468e^-3	1	4	2
15	552019	-91503	19844	-1	69	.6153e^+6	.1121e^-3	0	-1	1
16	844302	-139952	30351	0	61	.9412e^+6	.6481e^-4	0	1	1
17	1396321	-231455	50195	0	11	.1557e^+7	.7067e^-5

Период t=9. Выше выпуклой ломаной лежат точки с номерами 4,5,6,7,9,13, 14, 15, 16. Значения модулей определителей det(B_iB_jB_k) для соседних точек выпуклой ломаной равны 1, 5, 4, 1, 0, 5.

Пример 6. Уравнение l³ -8l²+ 21l+ 13=0,

J ≈ (1,-.335627e⁺ 0, .394273e^- 1 ).

k		Bk		d	L	l1(Bk)	l2(Bk)	[(a)\tilde]1	[(a)\tilde]2	[(a)\tilde]3
1	0	0	1		169	.2627e^+0	.6433e^+3
2	0	1	0		13	.5126e^+0	.2536e^+2
3	1	0	0	-1	1	.1000e^+1	.1000e^+1	1	-8	24
4	24	-8	1	-1	73	.2836e^+2	.2574e^+1	-1	3	1
5	27	-9	1	1	61	.3188e^+2	.1914e^+1	0	1	1
6	51	-17	2	0	9	.6024e^+2	.1494e^+0	-1	0	2
7	101	-34	4	1	9	.1195e^+3	.7533e^-1	0	1	1
8	152	-51	6	0	11	.1797e^+3	.6121e^-1	1	1	5
9	888	-298	35	-1	29	.1050e^+4	.2762e^-1	1	1	2
10	2029	-681	80	-1	3	.2399e^+4	.1250e^-2	1	2	6
11	14102	-4733	556	-1	47	.1667e^+5	.2819e^-2	0	-1	-1
12	-16131	5414	-636	0	47	.1907e^+5	.2464e^-2	-1	4	1
13	39389	-13220	1553	1	17	.4657e^+5	.3650e^-3	-1	-1	1
14	41418	-13901	1633	-1	13	.4897e^+5	.2655e^-3	0	1	1
15	80807	-27121	3186	0	1	.9554e^+5	.1047e^-4	1	5	26
16	2291941	-769237	90365	1	73	.2710e^+7	.2694e^-4	1	3	1
17	2575780	-864501	101556	1	61	.3046e^+7	.2003e^-4	0	1	1
18	4867721	-1633738	191921	0	9	.5756e^+7	.1564e^-5	-1	0	2
19	9654635	-3240355	380656	1	9	.1142e^+8	.7884e^-6

Период t=12. Выше выпуклой ломаной лежат точки с номерами 4,5, 11, 12,13, 16, 17. Значения модулей определителей det(B_iB_jB_k) для соседних точек выпуклой ломаной равны 1, 2, 0, 0, 1, 1, 3, 0, 2, 0.

Пример 7. Уравнение l³ -5l²+ 11l+ 9=0,

J ≈ (1,-.387899e⁺ 0, .690079e^- 1 ).

k		Bk		d	L	l1(Bk)	l2(Bk)	[(a)\tilde]1	[(a)\tilde]2	[(a)\tilde]3
1	0	0	1		81	.3857e^+0	.2100e^+3
2	0	1	0		9	.6211e^+0	.1449e^+2
3	1	0	0	-1	1	.1000e^+1	.1000e^+1	1	-6	15
4	15	-6	1	-1	24	.1911e^+2	.1256e^+1	0	-1	-1
5	-16	6	-1	0	23	.2011e^+2	.1144e^+1	1	4	2
6	28	-11	2	-1	17	.3560e^+2	.4775e^+0	0	-1	1
7	44	-17	3	0	8	.5572e^+2	.1436e^+0	0	1	2
8	116	-45	8	0	1	.1470e^+3	.6801e^-2	-1	-2	21
9	2333	-905	161	-1	23	.2957e^+4	.7778e^-2	1	-5	2
10	4130	-1602	285	-1	17	.5235e^+4	.3247e^-2	0	1	1
11	6463	-2507	446	0	8	.8192e^+4	.9766e^-3	0	1	2
12	17056	-6616	1177	0	1	.2162e^+5	.4626e^-4	1	-5	21
13	325977	-126446	22495	-1	24	.4132e^+6	.5809e^-4	0	-1	-1
14	-343033	133062	-23672	0	23	.4348e^+6	.5290e^-4	1	5	3
15	607249	-235551	41905	-1	17	.7697e^+6	.2209e^-4	0	-1	1
16	950282	-368613	65577	0	8	.1205e^+7	.6642e^-5	0	1	2
17	2507813	-972777	173059	0	1	.3179e^+7	.3146e^-6

Период t=9. Выше выпуклой ломаной лежат точки с номерами 4,5,6,9, 10,13, 14, 15. При этом выпуклую ломаную образуют точки M(B_k) с номерами 1, 2, 3, 7, 8,11,12,16,17. Значения модулей определителей det(B_iB_jB_k) для соседних точек выпуклой ломаной равны 1, 3, 1, 3, 1, 3, 1.

Примеры 2 - 4 демонстрируют, что функция w(k) может примнимать относительно большие значения. В примерах 5 - 7 сразу несколько из найденых по алгоритму точек (от 2 до 4 точек подряд) имеют образы M(B_k) над выпуклой ломаной.

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

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. Брюно А.Д. Алгоритм обобщенной цепной дроби // Препринт N 45. М.: ИПМ им. М.В.Келдыша, 2004.

16. 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.

17. Charve L. De la reduction des formes quadratiques ternaires positives et de leur application aux irrationelles du troisieme degre // Annales Scient. de l'Ecole Normale Superieure, 1880, t. 9, Suppl., p. 3-156.

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

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

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

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

22. 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.

23. Minkowski H. Uber die Anneherung an eine reele Grosse durch rationale Zahlen // Math. Annalen, 1901, B. 54, S. 91-124. Also in: Gesamm. Abh. I, p. 320-352.

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

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

26. Perron O. Die Lehre von den Kettenbrüchen. Leipzig, Teubner, 1913.

27. Berwick W.E.H. The classification of ideal numbers that depend on a cubic irrationality // Proc. London Math. Soc. (2), 1912, V. 12, p. 393-429.

28. Szekers G. Multidimensional continued fractions // Ann. Univ. Sci. Budapest. Rolando Eotvos sect. math. 1970, V. 13, p. 113-140.

29. Dobois E. Meilleures approximations diophantinnes. Application a la recherche de l'unite fondamentale des corps cubiques non totalement reels // C. R. Acad. Sci. Paris Ser. A, 1979, t. 290, p. 39-41.

30. Lagarias J.C. Best simultaneous Diophantine approximation. II. Behavior of consecutive approximations // Pcific J. Math. 1982, V. 102, no. 1, p. 61-88.

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

32. Боревич З.И., Шафаревич И.Р. Теория чисел. М.: Наука, 1972, второе изд.

33. Брюно А.Д. Структура наилучших диофантовых приближений // ДАН, 2005, т. 402, N 4.

34. Брюно А.Д. Алгоритм обобщенной цепной дроби // ДАН, 2005, т. 402, N 6.

Рис. 1

Рис. 2

---

File translated from T_EX by T_TH, version 3.40.
On 14 Jun 2005, 18:21.