Содержание к диссертации
Введение
ГЛАВА 1. Локальные минимумы двумерных полных решеток 11
1. Определения и простейшие свойства 11
2. Локальные минимумы и цепные дроби 15
3. Минимальные базисы и матрицы 21
ГЛАВА 2. Локальные минимумы многомерных полных решеток 24
1. Основные определения и простейшие свойства 24
2. Дополнение смежных локальных минимумов до базиса .30
ГЛАВА 3. Минимальные базисы трехмерных решеток 33
1. Вспомогательные леммы 33
2. Минимальные системы узлов 36
3. Достаточные условия минимальности базиса для трехмерных решеток "общего положения" 52
4. Необходимые условия минимальности базиса для трехмерных решеток "общего положения" 56
Дополнение 62
Список литературы 69
- Локальные минимумы и цепные дроби
- Дополнение смежных локальных минимумов до базиса
- Достаточные условия минимальности базиса для трехмерных решеток "общего положения"
- Необходимые условия минимальности базиса для трехмерных решеток "общего положения"
Введение к работе
"Начала" Евклида, написанные в начале III века до н.э., на протяжении более чем двух тысячелетий оставались основным источником геометрических знаний для всех культурных народов. И не только геометрических! В книгах VII - X "Начал" (см. [1]) излагаются теоретико-числовые вопросы. Седьмая книга начинается с определений. Для нас представляет интерес следующие три:
Единица есть то, через что каждое из существующих считается единым.
Число же - множество, составленное из единиц.
13.Первые между собой числа - суть измеряемые только единицей как общей мерой.
Во времена Евклида единица не считалась числом. Поэтому рассуждения проводились отдельно для единицы и остальных натуральных чисел. Это следует иметь в виду при ознакомлении с алгоритмом нахождения наибольшего общего делителя двух натуральных чисел, излагаемого в первых двух предложениях книги VII. Сначала рассматриваются взаимно простые числа:
"Если отложены два неравных числа и все время при последовательном отнятии меньшего от большего остаток не измеряет предшествующего ему (отнимаемого), пока не останется единица, то первоначальные числа будут первыми между собой."
Далее, во втором предложении, эта же процедура применяется для вычисления d =*НОД(а,Ь) с 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.
Здесь вторые слагаемые в левых частях есть остатки от деления соответствующих чисел. Это самый "древний" алгоритм, до сих пор имеющий большое практическое значение. И не только! Он является мощным инструментом при исследовании многих вопросов теоретической и прикладной математики. В общем виде алгоритм Евклида можно представить как последовательность делений с остатком:
а0 = до а\ + а2]
&S-2 — Qs-2 &s-l + ^s!
При этом НОД(ао,аі) = НОД(аі,о2) = = ROR(as-1,as) = as. В результате возникает разложение дроби ао/оі в конечную дробь
ао . 1
— = Qo + —; г
42 +
'. + Л.
которое формально записывается в виде:
г = — = Ьо59ь?2,--.,95-1] (0-1)
«і
Более общо, любое рациональное число / однозначно записывается в виде (0.1) с целым до и натуральными gi,. .., qs-\ (неполными частными). Оборвав цепную дробь (0.1) на г -том шаге, получим подходящую дробь
jj- = fe>; 91, 92, ---,9г-і]
с взаимно простыми целым Р; и натуральным Q{. Подходящие дроби P-ii-xIQii-x с нечетными номерами составляют возрастающую последовательность, a P^i/Qoi (с четными номерами) - убывающую. При этом
Р2І-1 . , Р2І
— < г < ——
Qii-\ Ч2і
2 г
Р2І-1 1
92i Qzi-i Q2xQii-\
Удобно положить Ро = 1 и Qo = 0. Тогда для всех г = 2, 3,
Рг+1 = qtPi + Pi-bQi+i = qiQi + Qi_! (0.2)
Для иррациональных чисел а возникает разложение
«= [905 91,92,---]
с бесконечной последовательностью неполных частных 9/ в том смысле, что
а= lim[q0:qi,q2,...,qi].
г—>оо
Пусть а Є (0,1/2). Пара (a, q) с натуральным q и целым а называется наилучшим приближением к а, если выполняется неравенство
\q'a — а'\ > \qa — а\
для любого натурального q' < q и любого целого а'. В этом случае НОД(а,д) = 1 и классическая теорема Лагранжа (см.[2] или [3]) утверждает, что последовательность
(Pi,Q,-) (/ = 1,2,...),
с числителями и знаменателями подходящих дробей к а состоит из всех пар наилучших приближений. В конце XIX века, независимо друг от друга, Г.Ф.Вороной [4] и Г.Минковский [5] положили это наблюдение в основу концепции локальных минимумов решеток с целью обобщения классического алгоритма непрерывных дробей на многомерный случай.'Напомним, что любую полную s— мерную решетку из IRS (для краткости, в дальнейшем просто решетка) можно представить в виде
Г = {у = mi7(1) + + ms7(s) |mi,..., ms Є Z}
с линейно независимыми базисными узлами 7^ = (7 і ? ws ) из Es.
По определению, ненулевой узел 7 = (7ь--->7в) называется локальным минимумом, если не существует другого ненулевого уз-ла г] = (rji,..., t]s) с \rji\ < \ji\ при всех і = 1,..., s, и при этом хотя бы одно из неравенств строгое.
Замечание 1. Узлы у и —у только одновременно являются локальными минимумами решетки Г.
Замечание 2. Для любого ненулевого узла т] решетки Г найдется локальный минимум у, для которого \у.;\ < \r/j\ при всех
І = 1,.. .,5.
Замечание 3. Любой локальный минимум у примитивен в том смысле, что для любого натурального q > 1 вектор ^ у не есть узел решетки Г.
Замечание 4. Если у и у' с у ф ±у' - локальные минимумы, то они линейно независимы.
Составим из всех локальных минимумов решетки Г множество УЯ(Г). Для S = 1 любая решетка Г в Ш1 имеет вид
{my{p\m Є Z} с некоторым вещественным 7 і Ф 0. Поэтому, для нее
9Я(Г) = {±7(11)}. В случае s = 2 для а Є (0,1/2) определим решетку
Га = {l = (n*2,mi - m2Qf) = ГПі(0, 1) + m2(l, -a)|mi,77i2 Є Щ-
Из уже упоминавшейся теоремы Лагранжа о наилучших приближениях следует, что
Ш(Га) = {±{Qi,Pi - Qi*)\i = 0,1,2,...}
Таким образом, в рассматриваемом случае, локальные минимумы взаимно однозначно соответствуют подходящим дробям разложения а в цепную дробь. Именно этот факт лежит в основе мотивировки концепции локальных минимумов. В рассматриваемой нами общей теории локальные минимумы 7(1) и у^ с 7^ ф ±7(2) решетки Г называются смежными, если не существует ненулевого узла т] из Г1, для которого:
а) при г" = 1,2
тахіні \v3\} < max{\7fl \7f\} (1 < j < s);
б) для каждого і хотя бы одно из этих s неравенств строгое.
Это понятие для -трехмерных решеток введено Вороным [4] и играет важную роль при построении аналога алгоритма цепных дробей. Вороной и Минковский в своих исследованиях ориентировались на задачу вычисления единиц алгебраических числовых полей. Поэтому они и их последователи ограничились решетками "общего положения", где каждый ненулевой узел имеет только отличные от нуля координаты. В связи с задачами целочисленного линейного программирования [6] представляет интерес построение соответствующей теории для произвольных решеток, включая целочисленные. Как будет видно из дальнейшего, при этом возникают дополнительные технические трудности и некоторые специфические нюансы.
Главная цель настоящей работы состоит в том, чтобы изучить структуру взаимного расположения "соседних" локальных минимумов для произвольных трехмерных решеток. Как уже отмечалось, Вороной [4] рассматривал только решетки "общего положения". По этой причине в первой главе мы подробно излагаем теорию локальных минимумов для произвольных двумерных решеток. С принципиальной точки зрения в ней не содержится ничего нового по сравнению с соответствующей главой из диссертации Вороного [4]. Однако, с методической точки зрения, она представляет определенный интерес, поскольку изучаемые конструкции достаточно просты и лежат в основе мотивировок соответствующих построений для трехмерных решеток.
Вторая глава носит вспомогательный характер. В ней приводятся некоторые хорошо известные факты и нужные технические леммы. Особо отметим теорему 4, которая в трехмерном случае сформулирована Вороным [4] для решеток "общего положения". В ней речь идет о том, что любую пару смежных минимумов можно дополнить до базиса решетки. В самом общем случае она доказана в [7] и играет важную роль в теории локальных минимумов.
Главные результаты содержатся в третьей главе. Здесь изучаются "минимальные системы" узлов трехмерных решеток, состоящие из трех линейно независимых локальных минимумов. Для решеток ''общего положения" это понятие было введено Минковским [5]. Он же доказал, что в этом случае они составляют базис решетки. Мы распространяем этот результат на общий случай (см. [8]). Оказывается, что в некоторых случаях (они все явно указываются) минимальные системы не составляют базис.
В заключительных параграфах главы для решеток " общего положения" (и некоторых других видов) устанавливаются необходимые и достаточные условия (в виде линейных неравенств на координаты) минимальности базиса трехмерных решеток, опубликованные в [9].
И, наконец, в дополнении, на примерах решеток специального вида, изучаемые в диссертации конструкции представлены в наглядной форме как графы Минковского конкретных решеток.
Локальные минимумы и цепные дроби
Таким образом, в рассматриваемом случае, локальные минимумы взаимно однозначно соответствуют подходящим дробям разложения а в цепную дробь. Именно этот факт лежит в основе мотивировки концепции локальных минимумов. В рассматриваемой нами общей теории локальные минимумы 7(1) и у с 7 ф ±7(2) решетки Г называются смежными, если не существует ненулевого узла т] из Г1, для которого: б) для каждого і хотя бы одно из этих s неравенств строгое.
Это понятие для -трехмерных решеток введено Вороным [4] и играет важную роль при построении аналога алгоритма цепных дробей. Вороной и Минковский в своих исследованиях ориентировались на задачу вычисления единиц алгебраических числовых полей. Поэтому они и их последователи ограничились решетками "общего положения", где каждый ненулевой узел имеет только отличные от нуля координаты. В связи с задачами целочисленного линейного программирования [6] представляет интерес построение соответствующей теории для произвольных решеток, включая целочисленные. Как будет видно из дальнейшего, при этом возникают дополнительные технические трудности и некоторые специфические нюансы.
Главная цель настоящей работы состоит в том, чтобы изучить структуру взаимного расположения "соседних" локальных минимумов для произвольных трехмерных решеток. Как уже отмечалось, Вороной [4] рассматривал только решетки "общего положения". По этой причине в первой главе мы подробно излагаем теорию локальных минимумов для произвольных двумерных решеток. С принципиальной точки зрения в ней не содержится ничего нового по сравнению с соответствующей главой из диссертации Вороного [4]. Однако, с методической точки зрения, она представляет определенный интерес, поскольку изучаемые конструкции достаточно просты и лежат в основе мотивировок соответствующих построений для трехмерных решеток.
Вторая глава носит вспомогательный характер. В ней приводятся некоторые хорошо известные факты и нужные технические леммы. Особо отметим теорему 4, которая в трехмерном случае сформулирована Вороным [4] для решеток "общего положения". В ней речь идет о том, что любую пару смежных минимумов можно дополнить до базиса решетки. В самом общем случае она доказана в [7] и играет важную роль в теории локальных минимумов.
Главные результаты содержатся в третьей главе. Здесь изучаются "минимальные системы" узлов трехмерных решеток, состоящие из трех линейно независимых локальных минимумов. Для решеток общего положения" это понятие было введено Минковским [5]. Он же доказал, что в этом случае они составляют базис решетки. Мы распространяем этот результат на общий случай (см. [8]). Оказывается, что в некоторых случаях (они все явно указываются) минимальные системы не составляют базис.
В заключительных параграфах главы для решеток " общего положения" (и некоторых других видов) устанавливаются необходимые и достаточные условия (в виде линейных неравенств на координаты) минимальности базиса трехмерных решеток, опубликованные в [9].
И, наконец, в дополнении, на примерах решеток специального вида, изучаемые в диссертации конструкции представлены в наглядной форме как графы Минковского конкретных решеток.
Дополнение смежных локальных минимумов до базиса
Легко заметить, что Фі(М) при 5=1 и Ф2(А/) -при = — 1 опять имеют вид (4.1). Пусть = 1. Если Сі а і и 62 С2, то з «з5 поскольку узел не лежит в Г (Ьі,сі2,сз). Тогда для матрицы ФДМ) условие 63 аз эквивалентно условию с 2 Ъ 2, где 62, с2 соответствующие элементы матрицы ФЦМ). Таким образом, М или ФХ(М) принадлежит к первому типу из (3.6). Пусть є = — 1. Если а2 Ь2 + ?2, то узел лежит в Г"(6і,а2,сз), что противоречит минимальности матрицы М. Следовательно а2 52 + с2 для всех М вида (4.1) с s = — 1. Если Ь3 «з, то «і сі, поскольку узел 7(1) +7(2) + Т(3) = («і +Ьі - ci,a2 - &2 - с2,а3 - 63 + с3) не лежит в Г/(Ь1,а2,с3). Но тогда для матрицы Ф2(А/) условие ci\ с\ эквивалентно неравенству 63 аз для соответствующих элементов матрицы Ф2(М). Таким образом, хотя бы одна из матриц Af, Ф2(М) принадлежит ко второму типу из (3.6). Лемма 10 доказана. Пусть 7,7 —минимумы Г и г Є {1,2,3}. Следуя [11] назовем 7 смежным с 7 по координате г, если выполнены условия: 2) Г {х) - { ±7, ±7 } с ХІ=УІ и Xj=jj для всех j ф і. Очевидно, что для любой пары смежных минимумов один из них смежен с другим по некоторой координате. Для і Є {1,2,3} обозначим через ж І проекцию R3 в Ш2 вдоль координаты г. При этом 7Г1(хі,Х2,Х3) = (Х2,Х3), 7Г2(хі,Х2,Х3) = {Хі,Х3), 3( 1, 2, 3) = ( 1, 2) Легко показать (см. [4]), что для любой пары смежных минимумов 7 и У найдется координата j, для которой г/- = TTJ{J) И (J) — Tijij ) составляют минимальный базис порожденной ими двумерной решетки. Такую координату назовем регулярной для пары смежных минимумов 7-1 Из определения непосредственно следует Замечание 3. Пусть у смежен с у по координате і. Тогда координата і не является регулярной, а среди остальных координат регулярна по крайней мере одна. Пусть минимальное множество Г. Переставляя в случае необходимости узлы, мы можем считать, что для г = 1,2,3 Справедливо следующее утверждение Лемма 11. Если узлы из У линейно независимы, то найдется координата с индексом і, которая регулярна относительно пары узлов из У, отличных от 7 доказательство. Предположим, что утверждение леммы 11 неверно. Обозначим через М матрицу , соответствующую узлам 7 ,7 ,7 - Для некоторого преобразования Ф Є 5" положим М = Ф(М) a (1) 2) 3) —соответствующий М базис решетки Г{М) = Г. Из нерегулярности всех координат относительно соответствующей пары узлов из {7( \ 7(2) 7(3)} следует, что знаки в каждой паре произведений 7 7 и 7 7 Для (»,j) Є {(2,3),(1,3),(1,2)} одинаковые. Поэтому молено выбрать Ф Є $ (речь идет только о перемене знаков) таким, что с 1, 2 3 Є{ —1,1} и пололштельными а-і,Ьі,Сі. Заметим, что Поскольку 7 и 7-2 — смелшые минимумы, то е-2 = — \Єз- Соответствующая мнолееству {7(1 1 2\ 7 } минимальная матрица имеет вид Умножим вторую и третью строки матрицы соответственно на Єї, Єо, а затем умножим второй и третий столбец на Є\, е2. Тогда (4.3) преобразуется в минимальную матрицу Заметим, что у узла первые две координаты по абсолютной величине не превосходят «і, Ь2 соответственно. Тогда из минимальности матрицы следует, что аз + &з сз- Далее, у узла = («і —hi — сл, a2 — b2 + со, a3 + b3 — c3) абсолютные величины всех трех координат не превосходят а і, 62, с3 соответственно. Поэтому, по причине минимальности (4.4), третий столбец равен разности первого и второго. А это противоречит линейной независимости узлов 7(1\ 1(2\ 7 3)- Лемма 11 доказана. Замечание 4. При доказательстве леммы 11 мы попутно установили, что если узлы -jA1), 2),- 3 линейно зависимы (над Ш) и составляют минимальное подмножество решетки, то один из них равен сумме двух остальных. Теорема 8. Пусть J7( 7 7 } —минимальное множество в Г с линейно независимыми узлами. Тогда: а) у у2) 3 составляют базис Г; б) для соответствующей матрицы М найдется преобразование Ф Є т?, для которого матрица Ф(М) имеет один из двух видов в (3.6).
Достаточные условия минимальности базиса для трехмерных решеток "общего положения"
Напомним, что По определению, произвольная полная решетка Г в Ш имеет вид Г = {ml7(1) + + msy(s) I mi,... ,m8 Є Z} с линейно независимыми узлами 7(1 , У К составляющими базис Г. В дальнейшем, для краткости, прилагательное "полная" будем опускать. Напомним также, "что запись М С М означает строгое включение множества М в М . То есть, М есть подмножество М и М ф М . Запись М С М подразумевает возможность равенства М = М . По определению, ненулевой узел 7 решетки Г называется локальным минимумом, если не существует другого ненулевого узла і] из Г, для которого P(rj) С - (l) Назовем два локальных минимума у и у решетки Г с у ф ±.у смежными, если не существует ненулевого узла г\ из Г, для которого Речь идет о перефразировке соответствующих определений из введения. Из замечания 2 во введении непосредственно следует Замечание 1. В определении смежности в качестве rj можно выбрать локальный минимум решетки Г. Также очевидны Замечание 2. Если у и у локальные минимумы с у ф ±у и Р(у) = tP(y ), то у и 7 смежны. Замечание 3. Если у и у локальные минимумы решетки Г с то найдутся г и j из {1, 2,..., s }, для которых Предложение 1. Пусть у и у произвольные локальные минимумы с &(у) ф ?(у ). Тогда найдется смежный с у локальный минимум п, для которого &(у,ц) С (7,У) ДОКАЗАТЕЛЬСТВО. ПОЛОЖИМ Т/) = у и, в соответствии с замечанием 1 настоящего параграфа, построим последовательность локальных минимумов для которых и +1) ф ±7- Так как в ограниченной области из Rs число узлов решетки конечно, то наша последовательность {rj } оборвется пррі некотором г = к. В таком случае /у = т/ есть смежный с у локальный минимум, для которого Предложение 1 доказано. Назовем две решетки Г\ и J 2 из s подобными, если для некоторых ненулевых «і,...-, cvs Из определений непосредственно следует Замечание 4. Если Г"х и Г подобные решетки с коэффициен тами Ф подобиям,... ,o;s, ТО отображение (х\,..., s) —(ai i,..., #scvs) сохраняет свойства локальной минимальности, и смежности Нам понадобится следующая вспомогательная Лемма. Пусть 0 == (0Х,... 0S) произвольная точка из М5. Тогда множество {а + /-0 \aeZs;leZ} является решеткой в Шв тогда и только тогда, когда 0i,... 9S рациональные числа. ДОКАЗАТЕЛЬСТВО. Если 0i,... 0S есть рациональные числа, то для некоторого натурального Тогда все элементы рассматриваемого множества, умноженные на iV, есть целочисленные вектора и они составляют подрешетку в Xs. Утверждение леммы в одну сторону доказано. Предположим теперь, что среди чисел Oi,...,9S хотя бы одно иррационально. Из теории диофантовых приближений хорошо известно (см. [3]), что Ve 0 найдутся ненулевые целые ах,..., as. /, для которых Это означает, что рассматриваемое множество не дискретно. Поэтому оно не есть решетка. Лемма 1 полностью доказана
Как известно, разложение вещественного а в цепную дробь конечно только для рациональных а. Этот факт обобщается в следующем виде.
Необходимые условия минимальности базиса для трехмерных решеток "общего положения"
Предположим, что утверждение леммы неверно и 7 — узел решетки Г вида (2.8). Тогда остальные комбинации также являются узлами решетки. Без ограничения общности можно считать, что координаты узла 7 — неотрицательные числа.
Пусть і Є {2,3} и j Є {1,2,3}. Положим e(j} = 1, если 7 , 0 и є = —1, если 7j 0. Тогда найдутся т2,тА Є { — 1,1} с Поэтому, для выполняются неравенства \li\ max{1{ll\\1fl\1{f)\} = \y\i (2-9) при всех і = 1,2,3. Если в (2.9) выполняются строгие неравенства, то из минимальности- следует, что 7 = (0,0,0). Это невозможно, так как 7 ,7(2\т — линейно независимые узлы. Предположим, что в (2.9) хотя бы по одной координате і выпол няется равенство, іогда одно из чисел 7 , т\ Ь \1 І \ — НУЛЬ, а два остальных равны. Переставляя (в случае необходимости) местами координаты с номерами г и 1, а также принимая во внимание возможность замены знаков по отдельным координатам иу7(3), мы можем считать, что узлы системы У имеют вид: 7(1) = (аьа2,а3), 7(2) = ( i,1 2, 2 3), 7(3) = (0,е3с2,с3) с положительным d\ и неотрицательными Пусть Єї - є2 = е3 = -1. Согласно лемме 3, система У является "исключительной". Таким образом, в данном случае исходное предположение неверно. Пусть Єї = -1 и (б2, е3) ф (-1, -1). Рассмотрим узел Для его координат справедливы ограничения: Так как по условию леммы У — минимальная система, то у \ 1 2\ 7 3) — линейно независимые вектора. Поэтому выполняется хотя бы одно из равенств: - Ы = И2,Ы = Из. Пусть І72І = ИІ2- В этом случае система У имеет вид: У = {(а1, а2, а3), (аь -а2, ег з), (0,0, с3))}. Для б2 = —1 система совпадает с (2.4). Согласно лемме З У — "исключительная" система. В случае е2 = 1, поменяв у узлов системы местами первые и вторые координаты, а также умножив 7(2) на —1, опять приходим к (2.4). Таким образом, І72І Ф \У\г и Ы - Из При этом У можно отнести к одному из трех видов: Переставляя местами (в случае необходимости) вторые и третьи координаты, изменяя порядок следования узлов, и меняя знак у некоторых координат, с помощью леммы 3 получаем, что во всех случаях У — "исключительная" система, а это противоречит условию леммы. ПуСТЬ \ — 1 И 62 = — 1. Поменяв местами вторые и третьи координаты у узлов минимальной системы, приходим к случаю, рассмотренному выше. ПуСТЬ бі = 1 И о = 1. Для узла имеют место ограничения Как отмечалось выше, для того, чтобы не нарушались условия леммы, необходимо выполнение хотя бы одного из равенств: А это возможно только для систем вида: Система а) — частный случай У с б і = — 1. Такую ситуацию мы обсуждали выше. Система б) перестановкой вторых и третьих координат сводится к виду а). Система в) преобразуется к виду б), если поменять местами у{1К 1 2\ и изменить знак у 7(3)- Следовательно, У — "исключительная" система, чего не может быть. Лемма 5 доказана. Лемма 6. Пусть У = {7(1),7 2 7(3)} — минимальная система узлов решетки Г. Тогда для любой комбинации знаков ДОКАЗАТЕЛЬСТВО. Предположим что 7 = (±7(1) ±7(2))/ЗєГ. Для координат узла справедливо ограничение 7,- 2И.-/3, что противоречит минимальности У. Таким образом, Лемма 6 доказана. Лемма 7. Пусть У = {7 7 7 } — минимальная система узлов решетки Р. Тогда для любой яз 8 комбинаций знаков Для і = 1,2,3 выполняется неравенство І7; \У\і- Так как У — минимальная система, то для одной из координат І7?: = \У\І ф 0. Без ограничения общности можно считать.
