Структура минимальных систем узлов трехмерных решеток

Начала" Евклида, написанные в начале III века до н.э., на протяжении более чем двух тысячелетий оставались основным источником геометрических знаний для всех культурных народов. И не только геометрических! В книгах VII — X «Начал» (см. [1]) излагаются теоретико-числовые вопросы. Седьмая книга начинается с определений. Для нас представляет интерес следующие три:

1. Единица есть то, через что каждое из существующих считается единым.

2. Число же — множество, составленное из единиц.

13.Первые между собой числа — суть измеряемые только единицей как общей мерой.

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

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

Далее, во втором предложении, эта же процедура применяется для вычисления d =*НОД (а, 6) с d > 1. Если дословно следовать Евклиду, то для пары (70,55) она имеет следующий вид:

70, 70 — 55 = 15- 55, 55 — 15 = 40, 40 — 15 = 25, 25 — 15 = 10: 15, 15 — 10 = 5- 10, 10−5 = 5 = Н (Щ70,55).

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

70 = 1 • 55 + 15- 55−3-15 + 10- 15 = 1 • 10 + 5- 10 = 2−5- НОД (70, 55) = 5.

Здесь вторые слагаемые в левых частях есть остатки от деления соответствующих чисел. Это самый «древний» алгоритм, до сих пор имеющий большое практическое значение. И не только! Он является мощным инструментом при исследовании многих вопросов теоретической и прикладной математики. В общем виде алгоритм Евклида можно представить как последовательность делений с остатком: s-2 — Qs — 2 ' CLs-l + «s! asi — qs-1 ¦ as.

При этом НОД (ао, а1) = НОД (а1,а2) = • • ¦ = НОД (а517а5) — as. В результате возникает разложение дроби ciq/cii в конечную дробь а0 = до • ai + «2- al=qiа2 + а3- о ai 1 Qo + —-i + iTT 1.

• + a. s которое формально записывается в виде: а о г.

0.1).

Более общо, любое рациональное число г однозначно записывается в виде (0.1) с целым до и натуральными gi,. ., qs- (неполными частными). Оборвав цепную дробь (0.1) на гтом шаге, получим подходящую дробь с взаимно простыми целым Ри натуральным Qi. Подходящие дроби P-n-xIQii-x с нечетными номерами составляют возрастающую последовательность, a Poi/Qoi (с четными номерами) — убывающую. При этом p2i-l /. P2i.

— < V < ——.

Qli-l Ч?2 г И p2i Р2i — l 1 Q2i Qli-l Q2iQ2i-l.

Удобно положить Pq = 1 ж Qo = 0. Тогда для всех i = 2, 3,•• •.

Pi+1 — g, P- + Pii, Qi+i = g: Q- + Qt-1 (0.2).

Для иррациональных чисел, а возникает разложение с бесконечной последовательностью неполных частных q, в том смысле, что ol = lim [q0:q1,q2,., qi]. г—>оо.

Пусть, а 6 (0,½). Пара (a, q) с натуральным q и целым, а называется наилучшим приближением к а, если выполняется неравенство q’a — а' > qa — а| для любого натурального q' < q и любого целого а'. В этом случае НОД (а, д) = 1 и классическая теорема Лагранжа (см. 2] или [3]) утверждает, что последовательность.

Pi, Яг) (i = 1,2,.), с числителями и знаменателями подходящих дробей к, а состоит из всех пар наилучших приближений. В конце XIX века, независимо друг от друга, Г. Ф. Вороной [4] и Г. Минковский [5] положили это наблюдение в основу концепции локальных минимумов решеток с целью обобщения классического алгоритма непрерывных дробей на многомерный случай.'Напомним, что любую полную s— мерную решетку из IRS (для краткости, в дальнейшем просто решетка) можно представить в виде.

Г = {у = m 17(1) + ¦ • • + ms7(s) |mi,., ms? Z} с линейно независимыми базисными узлами 7^ = (7^,.,) из Ш8.

По определению, ненулевой узел у = (yi,.-, ys) называется локальным минимумом, если не существует другого ненулевого узла q = (771,., t]s) с liI < ъ пРи всех i = 1, •., s, w при этом хотя бы одно из неравенств строгое.

Замечание 1. Узлы у и —у только одновременно являются локальными минимумами решетки Г.

Замечание 2. Для любого ненулевого узла т] решетки Г найдется локальный минимум у, для которого |7, | < r) j при всех i = 1,., 5.

Замечание 3. Любой локальный минимум у примитивен в том смысле, что для любого натурального q > 1 вектор ^ ¦ у не есть узел решетки Г.

Замечание 4. Если у и у' с у ф ±7' - локальные минимумы, то они линейно независимы.

Составим из всех локальных минимумов решетки Г множество 9Л (Г). Для s = 1 любая решетка Г в М1 имеет вид m7(11)|m.

ЩГ) = {±7(11}}. В случае s = 2 для a? (0,½) определим решетку.

Га = {l = («i2,mi — m2a) = mi (0,1) + m2(l, -а)чщ, m2 € Z}.

Из уже упоминавшейся теоремы Лагранжа о наилучших приближениях следует, что.

ЩГа) = {±(Qi, Pi — Qi*)i = 0,1,2,.}.

Таким образом, в рассматриваемом случае, локальные минимумы взаимно однозначно соответствуют подходящим дробям разложения, а в цепную дробь. Именно этот факт лежит в основе мотивировки концепции локальных минимумов. В рассматриваемой нами общей теории локальные минимумы 7(1) и 7^ с у^ ф ±7(2) решетки Г называются смежными, если не существует ненулевого узла т] из Г, для которого: а) при i = 1,2 тах{у^ЪШ < max{7^lbf} (1 < j < s) — б) для каждого г хотя бы одно из этих s неравенств строгое.

Это понятие длятрехмерных решеток введено Вороным [4] и играет важную роль при построении аналога алгоритма цепных дробей. Вороной и Минковский в своих исследованиях ориентировались на задачу вычисления единиц алгебраических числовых полей. Поэтому они и их последователи ограничились решетками «общего положения», где каждый ненулевой узел имеет только отличные от нуля координаты. В связи с задачами целочисленного линейного программирования [6] представляет интерес построение соответствующей теории для произвольных решеток, включая целочисленные. Как будет видно из дальнейшего, при этом возникают дополнительные технические трудности и некоторые специфические нюансы.

Главная цель настоящей работы состоит в том, чтобы изучить структуру взаимного расположения «соседних» локальных минимумов для произвольных трехмерных решеток. Как уже отмечалось, Вороной [4] рассматривал только решетки «общего положения». По этой причине в первой главе мы подробно излагаем теорию локальных минимумов для произвольных двумерных решеток. С принципиальной точки зрения в ней не содержится ничего нового по сравнению с соответствующей главой из диссертации Вороного [4]. Однако, с методической точки зрения, она представляет определенный интерес, поскольку изучаемые конструкции достаточно просты и лежат в основе мотивировок соответствующих построений для трехмерных решеток.

Вторая глава носит вспомогательный характер. В ней приводятся некоторые хорошо известные факты и нужные технические леммы. Особо отметим теорему 4, которая в трехмерном случае сформулирована Вороным [4] для решеток «общего положения». В ней речь идет о том, что любую пару смежных минимумов можно дополнить до базиса решетки. В самом общем случае она доказана в [7] и играет важную роль в теории локальных минимумов.

Главные результаты содержатся в третьей главе. Здесь изучаются «минимальные системы» узлов трехмерных решеток, состоящие из трех линейно независимых локальных минимумов. Для решеток «общего положения» это понятие было введено Минковским [5]. Он же доказал, что в этом случае они составляют базис решетки. Мы распространяем этот результат на общий случай (см. [8]). Оказывается, что в некоторых случаях (они все явно указываются) минимальные системы не составляют базис.

В заключительных параграфах главы для решеток «общего положения» (и некоторых других видов) устанавливаются необходимые и достаточные условия (в виде линейных неравенств на координаты) минимальности базиса трехмерных решеток, опубликованные в [9].

И, наконец, в дополнении, на примерах решеток специального вида, изучаемые в диссертации конструкции представлены в наглядной форме как графы Минковского конкретных решеток.

1. Хинчин А. Я. Цепные дроби, с. 112, Москва, (1961). •3. Касселс Дж.

Введение

в теорию диофантовых приближений, с. 213, Москва. ИЛ.

2. Вороной Г. Ф. Собрание сочинений. Т. 1, Киев, (1952).

3. Minkowski Н. Zur Theorie der Kettenbruche, Gesammelte Abhandlungen, Leipzig, 1911, v. l, pp. 278−292.

4. Срейвер A. Теория линейного и целочисленного программирования. Т. 1, Москва.: Мир, (1991).

5. Быковский В. А. Горкуша О.А. Смелсные минимумы решеток. Да. льневосточный математический сборник. 1999. Выпуск 7.

6. Горкуша О. А. Минимальные базисы трехмерных полных решеток. Математические заметки. 2001. Выпуск 3. Том 69. 353−362.

7. Быковский В. А. Горкуша О.А. Минимальные системы трехмерных полных решеток. Математический сборник. 2001. .№ 2. Т.

8. Касселс Дж._ Введение в геометрию чисел, с. 421, Москва. Мир. 1995.

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

10. Buchmann .J. On the Computation of Units and Class Numbers by a Generalization of Lagrange’s Algorithm. Journal of Number Theory, V. 26, 8−30 (1987).

11. Горкуша О. А. Приведение базисов трехмерных решеток. Препринт/ ИПМ ДВО РАН. Владивосток: Дальнаука, 1998.

12. Быковский В. А. Горкуша О.А. Смежные минимумы решеток. Дальневосточный математический сборник. 1999. Выпуск 7. С 18−22.

13. Bullig Zur Kettenbruchtheorie in Dreidimensionen (Zl)", Abhandlungen aus dem Mathematischen Seminar der Hanseschen Univer-sitat, vol. 13, 1940.