Комбинаторика параллелоэдров и ее связь с гипотезой Вороного Магазинов Александр Николаевич

Содержание к диссертации

Введение

ГЛАВА 1. Введение 4

1.1. Параллелоэдры, условия Минковского-Венкова и гипотеза Вороного 4

1.2. Основные понятия 8

1.3. Ключевые результаты теории параллелоэдров 9

1.4. Основные результаты диссертации 15

1.5. План диссертации 17

ГЛАВА 2. Локальная структура разбиения на параллелоэдры 20

2.1. Определения и основные результаты главы 20

2.2. Локальная структура граней разбиения, имеющих коразмерность три 25

2.3. Свойства граней параллелоэдров коразмерности три 29

2.4. Верхняя оценка степени грани разбиения данной коразмерности 36

ГЛАВА 3. Удлинения параллелоэдров 42

3.1. Параллелоэдры, свободные вдоль векторов 42

3.2. Необходимое и достаточное условие свободы параллелоэдра вдоль вектора 45

3.3. Параллелоэдры, свободные вдоль векторов, и гипотеза Вороного 52

3.4. Послойная конструкция разбиения 60

3.5. Свободные и совершенные свободные пространства 67

3.6. Двумерные свободные пространства параллелоэдров Вороного 69

ГЛАВА 4. Гипотеза Вороного для удлинений параллелоэдров Вороного 80

4.1. Основные результаты главы з

4.2. Дополнения к основным результатам главы и план доказательства Теорем 4.1 и 4.2 81

4.3. Операция обобщенного удлинения параллелоэдров Вороного 84

4.4. Шаг индукции для Теорем 4.2 и 4.6 89

4.5. Шаг индукции для Теоремы 4.4 96

Список использованных источников

• Ключевые результаты теории параллелоэдров
• Локальная структура граней разбиения, имеющих коразмерность три
• Параллелоэдры, свободные вдоль векторов, и гипотеза Вороного
• Операция обобщенного удлинения параллелоэдров Вороного

Введение к работе

Актуальность темы

Параллелоэдром называется выпуклый многогранник Р, допускающий разбиение грань-в-грань Т(Р) аффинного пространства своими транслята-ми (параллельными копиями). Термин параллелоэдр был введен в 1885 году российским кристаллографом Е. С. Федоровым¹. Параллелоэдры привлекли внимание таких замечательных математиков конца XIX — начала XX века, как Г. Минковский и Г. Ф. Вороной, которые и считаются основоположниками теории параллелоэдров в математике.

Г. Минковский² показал, что для каждого фиксированного натурального d существует лишь конечное число <і-мерных параллелоэдров. Он же установил необходимые свойства, которыми обладает всякий параллелоэдр — существование центра симметрии у самого параллелоэдра и у каждой его гиперграни. В 1954 г. Б. А. Венков³ показал, что условия, найденные Минковским, вместе с еще одним условием (о числе гиперграней в поясках), на самом деле необходимы и достаточны для того, чтобы выпуклый многогранник был параллелоэдром.

Задача о классификации всех параллелоэдров данной размерности d является важной в теории параллелоэдров. Однако в настоящее время она решена только для d < 4. Значимые результаты в этом направлении получены Е. С. Федоровым, Б. Н. Делоне и М. И. Штогриным. Так, было установлено, что число комбинаторных типов параллелоэдров размерности d равно при d = 1,2,3,4 соответственно 1, 2, 5 и 52. Уже при d = 5 наблюдается т.н. «комбинаторный взрыв»: среди пятимерных параллелоэдров только т.н. примитивные образуют 222 комбинаторных типа (при d = 1, 2, 3,4 число комбинаторных типов примитивных паралелоэдров равно соответственно 1,1,1 и 3). Классификация пятимерных примитивных параллелоэдров была получена С. С. Рышковым и Е. П. Барановским⁴, а позднее проверена и уточнена

¹Е. С. Федоров, Начала учения о фигурах. С.-Петербург, 1885. Переиздание: Е. С. Федоров, Начала учения о фигурах. М., АН СССР, 1953.

²H. Minkowski, Allgemeine Lehrsatze uber die konvexe Polyeder // Nach. Ges. Wiss., Gottingen, 1897,

198-219.

³Б. А. Венков, Об одном классе эвклидовых многогранников // Вестник Ленинградского Университета, сер. мат., физ., хим., 2 (1954), 11–31.

⁴С. С. Рышков, Е. П. Барановский, С-типы n-мерных решеток и пятимерные примитивные параллелоэдры (с приложением к теории покрытий) // Тр. МИАН СССР, 137 (1976), 132 с.

П. Энгелом и В. П. Гришухиным⁵. Вычисления П. Энгела⁶ показывают, что существует более 100 000 комбинаторных типов пятимерных параллелоэдров, и поэтому в размерностях d > 5 задача классификации параллелоэдров является труднообозримой.

Таким образом, более перспективным путем исследований становится установление свойств, имеющих место для всех параллелоэдров. Особый интерес представляет комбинаторика разбиения пространства на параллелоэдры. Комбинаторные свойства параллелоэдров и соответствующих им разбиений изучались в работах Б. Н. Делоне, Б. А. Венкова, П. МакМаллена, А. Хорвата, Н. П. Долбилина и др.

В 1908 году Г. Ф. Вороной⁷ сформулировал гипотезу о том, что для всякого параллелоэдра можно указать такую евклидову метрику, в которой он будет ячейкой разбиения Вороного (эквивалентные термины: мозаики Вороного, разбиения Дирихле, разбиения Дирихле-Вороного; в настоящем автореферате и диссертации как основной будет использоваться термин «разбиение Вороного») для некоторой решетки. Несмотря на то, что гипотеза Вороного не доказана в полной общности, имеются как классические (Г. Ф. Вороной, О. К. Житомирский, Б. Н. Делоне), так и современные (Р. Эрдал, А. Ордин) доказательства для важных специальных классов параллелоэдров.

Для параллелоэдров Вороного (параллелоэдров, являющихся областью Вороного для некоторой решетки) разработана глубокая теория. Фундамент этой теории заложил сам Вороной, разработавший метод непрерывного параметра — алгоритм, позволяющий классифицировать все параллелоэдры Вороного данной размерности. Он же ввел понятие области L-типа квадратичной формы.

В теории параллелоэдров Вороного широко используется также понятие и конструкция разбиения Делоне — разбиения, двойственного разбиению Вороного. Вводя эти разбиения в рассмотрение, сам Б. Н. Делоне использовал термин «L-разбиение»⁸.

Теория параллелоэдров Вороного и тесно связанная с ней геометрия поло-

⁵Р. Engel, V. Grishukhin: There are exactly 222 L-types of primitive five-dimensional lattices // European Journal of Combinatorics, 23:3 (2002), 275-279.

⁶P. Engel, The contraction types of parallelohedra in E⁵ // Acta Crystallographica Section A, 56 (2000), 491-496.

G. F. Voronoi, Nouvelles applications des parametres continus a la theorie des formes quadratiques, Deuxieme Memoire, Recherches sur les parallelloedres primitifs // J. Reine Angew. Math. 134 (1908) 198-287, 136 (1909) 67-181. Переиздание: Г. Ф. Вороной, Исследования по теории примитивных параллелоэдров. Собр. соч., Т. 2. Киев: Изд. АН УССР, 1952. - 482 с.

⁸В. N. Delaunay, Sur la sphere vide // in Proc. Math. Congr. Toronto, August 11 - 16, 1924, Univ. of Toronto Press, Toronto, 1928, 695-700.

жительно определенных квадратичных форм изучались в работах Г. Ф. Вороного, Б. Н. Делоне, С. С. Рышкова, Е. П. Барановского, Р. Эрдала, К. А. Рыбникова-мл., М. Дютура, А. Шюрманна, Ф. Валлентина и др.

Трудности, возникающие при изучении параллелоэдров без предположения о справедливости гипотезы Вороного, видны из рассмотрения Главы 2 диссертации. Основной предмет изучения в Главе 2 — это локальная комбинаторная теория параллелоэдров, которая изучает комбинаторную структуру разбиения пространства R^d на параллелоэдры в малой окрестности точки, лежащей в относительной внутренности данной грани разбиения. Здесь нас интересует количество параллелоэдров, сходящихся в данной грани, и комбинаторный тип схождения.

Результаты локальной комбинаторной теории параллелоэдров, не использующие предположение о справедливости гипотезы Вороного, были эффективно использованы при доказательстве частных случаев гипотезы Вороного⁹,¹⁰. Отметим, что такие результаты, как правило, имеют более сложные доказательства, чем их аналоги для параллелоэдров Вороного.

Отдельно уделим внимание локальной комбинаторике разбиения в гранях коразмерности 3 (т.е. гранях размерности d — 3, где d — размерность па-раллелоэдра). Все 5 возможных типы схождения параллелоэдров в гранях коразмерности 3 были впервые найдены в 1929 году Б. Н. Делоне (см. 8 цитированной работы), причем сразу без предположения о справедливости гипотезы Вороного. Эти типы схождения приводятся на рис. 1 (стр. 11 автореферата).

Результат Делоне имеет огромное значение для гипотезы Вороного: в цитированной работе Житомирского⁹ гипотеза Вороного доказана для таких разбиений, у которых все схождения в гранях коразмерности 3 исчерпываются типами a) и b) рис. 1, а в диссертации Ордина¹⁰ к этим двум типам добавлен еще тип c). Несмотря на это, доказательство теоремы Делоне является, насколько известно автору данного автореферата, малоизвестным и недостаточно прозрачным. Поэтому, по мнению автора автореферата, нахождение современного подхода к теореме Делоне заслуживает внимания.

Будем называть зонотопальными параллелоэдрами те параллелоэдры, которые являются зонотопами, т.е. представимы в виде суммы Минковского конечного числа отрезков. Зонотопальные параллелоэдры представляют собой

⁹O. K. Zitomirskij, Verscharfung eines Satzes von Woronoi // Журнал Ленинградского физ.-мат. общества, 2 (1929), 131-151.

¹⁰A. Ordine, Proof of the Voronoi conjecture on parallelotopes in a new special case // диссертация, Queen’s University, Ontario, 2005.

интересный специальный класс параллелоэдров. Р. Эрдал доказал¹¹, что все зонотопальные параллелоэдры являются параллелоэдрами Вороного. Ззоно-топальные параллелоэдры и связанные с ними понятия (в первую очередь, дайсинги и унимодулярные системы векторов) изучались в работах Р. Эрда-ла, Дж. Шепарда, П. МакМаллена, С. С. Рышкова, Ф. Валлентина, М. Деза, В. Г. Данилова, В. П. Гришухина и др.

Одно из свойств зонотопов (не только являющихся параллелоэдрами) — положительная толщина в направлении любой собственной грани. Понятие положительной толщины параллелоэдра в данном направлении было введено Б. А. Венковым¹².

В дальнейшем особое внимание было уделено случаю положительной толщины параллелоэдра в одномерном направлении. Всякий параллелоэдр Р положительной толщины вдоль заданной прямой есть сумма Минковского Р' + I другого параллелоэдра Р' и отрезка /, параллельного прямой .

Параллелоэдр Р размерности d, являющийся суммой Минковского другого (і-мерного паралелоэдра Р' и отрезка, называется удлинением параллелоэдра Р'. Удлинения параллелоэдров изучались в работах В. П. Гришухина, А. Хорвата, А. Вега.

Операция удлинения параллелоэдров подробно изучается в Главах 3 и 4 диссертации.

Пусть Р — (i-мерный параллелоэдр, а / — такой отрезок в R^d, что сумма Минковского Р + I — также параллелоэдр. Если / = [—х,х], где х — некоторый вектор, то скажем, что параллелоэдр Р свободен вдоль вектора х. Можно показать, что параллелоэдр, свободный вдоль вектора х, свободен и вдоль любого вектора Ах, А Є R.

Из всех <і-мерных параллелоэдров только параллелепипеды свободны вдоль любого вектора в R^d. Для любого другого параллелоэдра существуют векторы, вдоль которых этот параллелоэдр несвободен. Поэтому нас будет интересовать необходимое и достаточное условие, характеризующее векторы, вдоль которых данный параллелоэдр свободен. Такое условие было сформулировано В. П. Гришухиным. Однако в его работе¹³ не была преодолена трудность, возникающая при проверке условия о числе граней в пояске.

С операцией удлинения параллелоэдров связан и следующий вопрос¹⁴: можно ли получить контрпример к гипотезе Вороного при помощи операции

¹¹R. Erdahl, Zonotopes, dicings, and Voronoi’s conjecture on parallelohedra // European Journal of Combinatorics, 20:6 (1999), 527-549.

¹²Б. А. Венков, О проектировании параллелоэдров // Матем. сб., 49(91):2 (1959), 207-224.

¹³ В. П. Гришухин, Параллелоэдры ненулевой толщины // Матем. сб., 195:5 (2004), 59-78.

¹⁴ В. П. Гришухин, Сумма параллелоэдра и отрезка по Минковскому // Матем. сб., 197:10 (2006), 15-32.

удлинения параллелоэдра Вороного? Или наоборот: можно ли доказать гипотезу Вороного для всякого удлинения параллелоэдра? Этот частный случай гипотезы Вороного был сведен¹⁴'¹⁵ к следующей задаче: верно ли, что всякий параллелоэдр Вороного, который свободен вдоль бесконечного числа попарно неколлинеарных векторов, является приводимым, т.е. прямой суммой параллелоэдров меньшей размерности? До последнего времени обе задачи оставались нерешенными.

Таким образом, с задачами об удлинении параллелоэдров Вороного тесно связана задача о приводимости параллелоэдров. Понятие приводимости параллелоэдра и установление условий, при которых параллелоэдр приводим, представляет и самостоятельный интерес, как видно, например, из Главы 8 цитированной ранее диссертации А. Ордина.

Цели работы

1. Изучить локальные комбинаторные свойства разбиения пространства R^d
на параллелоэдры в окрестности грани коразмерности к.

Показать, что число комбинаторных типов ^-мерных вееров, реализуемых как веер некоторой грани какого-либо разбиения (т.е. число возможных комбинаторных типов схождения параллелоэдров в грани коразмерности /с), конечно для каждого фиксированного к. Для этого получить верхнюю оценку числа параллелоэдров, сходящихся в грани коразмерности к. Доказательства не должны опираться на предположение о справедливости гипотезы Вороного.

Подробно исследовать случай грани коразмерности к = 3. Комбинаторными методами доказать классификационную теорему Делоне. Дополнительно проверить «гипотезу о размерности» для граней коразмерности 3 и проверить, что индекс трехмерной подрешетки, соответствующей такой грани, равен 1.

2. Исследовать вопросы об удлинениях параллелоэдров.

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

Дать полное доказательство необходимого и достаточного условия, при котором удлинение данного параллелоэдра Вороного есть снова параллелоэдр Вороного.

¹⁵A. Vegh, Racsok, kor- es gombelrendezesek // диссертация, BME, Budapest, 2006.

Доказать гипотезу Вороного для удлинений параллелоэдров Вороного.

3. Исследовать задачу о приводимости параллелоэдров, а именно ослабить достаточное условие в известном критерии приводимости параллелоэдров Вороного.

Методы исследования

В диссертации используются методы линейной алгебры, теории выпуклых многогранников и комбинаторной геометрии. Кроме того, в Главе 2 используются простейшие соображения комбинаторной топологии, а в Главе 4 — методы теории положительно определеных квадратичных форм.

Научная новизна

Сформулируем основные результаты диссертации.

1. Получена точная верхняя оценка числа параллелоэдров, сходящихся в данной грани разбиения, в зависимости от коразмерности грани. А именно, в (d — &)-мерной грани разбиения <і-мерного пространства на парал-лелоэдры сходится не более 2^к параллелоэдров разбиения.

2. Для суммы Минковского параллелоэдра Вороного и отрезка справедлива гипотеза Вороного.

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

Данные результаты являются новыми.

Помимо перечисленных результатов, в диссертации приведено новое, комбинаторное, доказательство теоремы Делоне, перечисляющей все комбинаторные типы вееров (d — 3)-мерных граней, где d — размерность параллелоэдра. Наконец, впервые дано полное доказательство критериального условия, при котором параллелоэдр свободен вдоль вектора.

Теоретическая и практическая ценность

Работа носит теоретический характер. Результаты могут быть использованы в дальнейших исследованиях по теории параллелоэдров и геометрии положительно определенных квадратичных форм.

Апробация работы

Результаты диссертации докладывались автором на следующих конференциях и семинарах:

4. The Fifth Discrete Geometry and Algebraic Combinatorics Conference, Brownsville, Texas, USA, April 17-20, 2013.

5. The Fifth International Conference on Analytic Number Theory and Spatial Tessellations, 16-20 сентября 2013 г., Киев, Украина.

6. Семинар «Дискретная геометрия и геометрия чисел» (рук. Н. П. Дол-билин, М. Д. Ковалев, Н. Г. Мощевитин), МГУ.

7. Семинар «Выпуклые многогранники» (рук. Н. П. Долбилин), МГУ.

8. Семинар «Теория сложности вычислений» (рук. С. П. Тарасов), ВЦ РАН.

9. Семинар «Теория Морса» (рук. Г. Ю. Панина), СПбГУ

Публикации

По теме диссертации опубликовано 4 статьи в ведущих российских и зарубежных рецензируемых изданиях. Их список приводится в конце автореферата.

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

Работа [4] основана на препринте¹⁶ автора диссертации.

Ключевые результаты теории параллелоэдров

В данной диссертации изучаются такие разбиения аффинного пространства Wd на выпуклые многогранники, что существует группа трансляций (параллельных переносов), действующая транзитивно на ячейках разбиения. Иначе говоря, рассматриваются разбиения, правильные относительно некоторой группы трансляций.

Для точечного множества X и вектора t в пространстве M,d обозначим через X + t параллельный перенос (транслят) множества X на вектор t.

Параллелоэдром (см. [15]) называется выпуклый многогранник Р, допускающий разбиение гранъ-в-гранъ пространства Rd своими транслятами (параллельными копиями). Т.е. для і-мерного параллелоэдра Р существует такое множество транслятов (Т2) rel int(P + ti) П rel int(P + tj) = 0 при і jt j (ТЗ) Пересечение (Р + tj) П (Р + tj) пусто, или является гранью каждого из многогранников (P + t;) И (P + tj). В дальнейшем через Т(Р) будем обозначать именно разбиение вида (1.1) со свойствами (ТІ) - (ТЗ). Пусть Р — d-мерный параллелоэдр. Тогда (см., например, [35]) множество векторов трансляций, совмещающих Р с какой-либо ячейкой разбиения Т(Р) (т.е. множество {tj} 0 в формуле (1.1)) является (І-МЄрНОЙ решеткой. Будем обозначать эту решетку через Л(Р). Всякий (i-мерный параллелоэдр Р обладает следующими свойствами. (MV1) Р имеет центр симметрии. (MV2) Любая (d — 1)-грань (гипергрань) F с Р имеет центр симметрии. (MV3) Любой (d — 2)-грани G С Р параллельны либо ровно 4, либо ровно 6 гиперграней параллелоэдра Р. Свойства (MV1) и (MV2) доказаны Минковским [35], а свойство (MV3) — Б. Н. Делоне [20]. Б. А. Венков [4] и независимо П. МакМаллен [34] показали, что если выпуклый многогранник Р обладает свойствами (MV1) -(MV3), то Р — параллелоэдр. Свойства (MV1) - (MV3) называются свойствами Минковского-Венкова.

Пусть G — произвольная (d — 2) грань d-мерного параллелоэдра Р. Пояском, заданным гранью G, называется множество всех гиперграней параллелоэдра Р, параллельных грани G. Пусть поясок параллелоэдра Р, заданный гранью G, состоит из m гиперграней (ш = 4 или 6). Тогда можно все (d — 2)-грани параллелоэдра Р, параллельные грани G, можно занумеровать как Gi, &2, , GTO_i, GTO (при этом сама грань G получит некоторый номер; пусть, не умаляя общности, ш), а все гиперграни пояска, заданнного гранью G, занумеровать, соответственно,

Далее, если не оговорено иное, будем считать, что центр параллелоэдра Р расположен в «начале координат» 0. Для центра симметрии выпуклого многогранника Q (не обязательно параллелоэдра), если этот центр существует, мы будем использовать обозначение c(Q). Перейдем к формулировке гипотезы Вороного.

Пусть Ed — (і-мерное евклидово пространство с отмеченной точкой — «началом координат» 0. Пусть, далее, Л — і-мерная решетка в Ed и 0 є Л. Рассмотрим многогранник Ру(Л), определяемый как множество всех точек пространства Ed, для которых 0 — одна из ближайших точек среди узлов решетки Л. Иначе говоря,

Многогранник Ру(Л), а также любой его транслят, будем называть параллелоэдром Вороного решетки Л в метрике пространства Ed. Несложно показать, что Д/(Л) — действительно параллелоэдр, и что T(iV(A)) = {iV(A)+x:xGA}. Используя данное выше определение, гипотезу Вороного можно сформулировать в следующем (наиболее известном) виде. Гипотеза (Гипотеза Вороного, формулировка 1). Всякий параллелоэдр Р аффинно эквивалентен некоторому параллелоэдру Вороного Pv(A).

При этом нам будет удобно считать, что аффинное пространство Wd в котором лежит параллелоэдр Р, и евклидово пространство Ed, в котором лежит параллелоэдр Ру(Л), — это разные пространства; более того, в Rd нет наперед заданной метрической структуры.

Дадим более общее определение параллелоэдра Вороного. Пусть Q — положительно определенная квадратичная форма в пространстве Wd. Скалярное произведение векторов х и у относительно формы Q будем записывать как хтГ2у. Пусть Л — решетка вМ и пусть 0 є Л. Многогранник Р(Л, f]) = {yGRd: уТ% = min(y - х/)Т (у - х )}, x GA а также любой его транслят, будем называть параллелоэдром Вороного решетки Л относительно формы Q. Пусть в аффинном пространстве Rd фиксирована (аффинная) система координат. В этой системе координат целочисленные точки образуют некоторую фиксированную решетку Zd. Используя введенные обозначения, можно переформулировать гипотезу Вороного.

Гипотеза (Гипотеза Вороного, формулировка 2). Всякий параллелоэдр Р аффинно эквивалентен некоторому параллелоэдру Вороного вида P(Zd, Q), где Q — некоторая положительно определенная квадратичная форма в Rd.

В самом деле, всякий d-мерный параллелоэдр Р аффинно эквивалентен некоторому параллелоэдру Р , для которого Л(Р ) = Zd.

Предположим, что параллелоэдр Р аффинно эквивалентен параллелоэдру iV(A) (где iV(A) С Ш1). Пусть (р : Rd - Ш1 — такое аффинное отображение, что ф(Р ) = Ру(Л). Тогда в пространстве Wd можно ввести такую евклидову метрику, что отображение if будет изометрией. Поэтому параллелоэдр Р можно представить в виде P(Zd,Q).

Наконец, только что изложенное рассуждение можно повторить, взяв вместо Р сам параллелоэдр Р, а вместо решетки Zd — решетку Л(Р). Это приведет к третьей формулировке гипотезы Вороного. Гипотеза (Гипотеза Вороного, формулировка 3). Всякий параллелоэдр имеет вид Р(Л, Q), где Л = А(Р), a Q — некоторая положительно определенная квадратичная форма в Rd. Иначе говоря, всякий параллелоэдр является параллелоэдром Вороного.

В работе [39], где Г. Ф. Вороной впервые сформулировал гипотезу, используется формулировка 2. В данной диссертации в качестве основной будет использована формулировка 3. Полное доказательство или опровержение гипотезы Вороного остается открытой проблемой. Некоторые специальные подклассы класса параллело-эдров, для которых гипотеза Вороного доказана, перечисляются далее при обзоре ключевых результатов теории параллелоэдров.

Локальная структура граней разбиения, имеющих коразмерность три

Следовательно, в случаях а), Ь), с), d), е) многогранник convV(E) = conv{xi,x2,... ,хто} есть образ (при некотором линейном отображении if) тетраэдра, четырехугольной пирамиды с квадратным основанием, октаэдра, треугольной призмы и трехмерного куба соответственно. Из неравенства (2.4) следует, что отображение ip невырожденное, следовательно, комбинаторика многогранника-образа convP(E ) такая же, как и комбинаторика многогранника-прообраза if 1(convV(E)). Поэтому легко видеть, что условия двойственности для дуальной клетки Т (Е) выполняются.

Из только что доказанной Теоремы 2.7 немедленно следует гипотеза о размерности для (d — 3)-мерных граней. Следствие 2.8. Для любой (d — 3)-мерной грани Е разбиения Т(Р) верно равенство dimaffV(E) = 3. В Параграфе 2.1 были введены два способа построения решетки по грани Е разбиения Т(Р). Соответствующие решетки были обозначены через Л(Р) и Aaff(E ). Мы покажем, что в случае dimE = d — 3 оба способа дают на самом деле одну и ту же решетку. Теорема 2.9. Для любой (d — 3)-мерной грани Е разбиения Т(Р) выполняется Aaff(P) = Л(Р). Доказательство. Не умаляя общности, будем считать, что Е с Р. Выберем точку х є relintP. Для единообразия обозначений положим Р\ = Р. Пусть Р2 — некоторый параллелоэдр разбиения Т(Р), отличный от Р\ и такой, что Е с Р - Поскольку точка х принадлежит параллелоэдру Р , имеем х + c(Pi) - с(Р2) є Р2 + с(Рі) - с(Р2) = Рь Таким образом, если Р\)Р і) ,Pn — это все параллелоэдры разбиения Т(Р), содержащие грань Е, то conv{-c(P,) +х + с(Рі) : і = 1,2,...,п} С Pi. Следовательно, для любого Р є Т(Р) верно включение (-convP(P))+x + c(P/) С Р . Оставим в рассмотрении лишь параллелоэдры Р , удовлетворяющие условию с(Р ) є Aaff(E ). Эти параллелоэдры попарно не пересекаются по внутренним точкам, а значит, семейство трехмерных многогранников {(- convP(P)) + х + t : t Є Aaff(Р)} образует упаковку в трехмерном пространстве affV(E) + x. Следовательно, (см., например, [18]) семейство транслятов симметризации Минковского {!(-conv ()) + convV(E) + t : t Є Aaff(E )} также образует упаковку. Таким образом, трехмерный объем многогранника \{— convV(E)) + convV(E) не превосходит фундаментального объема решетки А (Е), т.е. верно неравенство V(l(-convV(E)) + lconvV(E)) V(AaS(E))} (2.8) где в левой части стоит объем трехмерного множества, а в правой — фундаментальный Объем решеТКИ Aaff(E ). Разделив обе части неравенства (2.8) на V(A(E)) и рассмотрев обратные величины, получаем (Aaff() : А(Е)) — гё Tj -y (2.9) Если веер Fan(E ) имеет тип Ь), с), d) или е) на рис. 1.3, то в правой части неравенства 2.9 стоит число 3/2, 12/7, 3/2 или 1 соответственно. Поскольку индекс (Aaff(E ) : А{Е)) — натуральное число, то имеется единственная возможность — (Aaff(E ) : А(Е)) = 1. Пусть теперь веер Fan(E ) имеет тип а) на рис. 1.3, т.е. многогранник convV(E) — тетраэдр. Тогда в правой части неравенства 2.9 стоит число 5/2. Это означает, что индекс (Аад(Е) : А(Е)) равен 1 или 2.

Предположим, что (Aas(E) : А(Е)) = 2. Тогда AaS(E) = А(Е) U (А(Е) + it) , где t є А(Е). Рассмотрим две шестерки точек {уі + Ь2:УьУ2 є ()} и Все точки этих шестерок принадлежат решетке \к(Е), но, как несложно видеть, никакие две точки из одной шестерки не сравнимы mod. Л(Е ). Решетка \А(Е) состоит из 8 классов точек mod. Л(Е ), поэтому какие-то две точки из разных шестерок сравнимы mod. Л(Е ). Следовательно, найдется такой вектор и є Л(Е ), что 2 тетраэдра (-conv ())+х + с(Р) и (-conv ())+x + t + u + c(P) имеют общую точку, которая является серединой ребра каждого из них. Но все середины ребер первого тетраэдра лежат строго внутри параллелоэдра Р, а все середины ребер второго тетраэдра лежат строго внутри параллелоэдра Р + 7jt + и. Но эти параллелоэдры — различные ячейки разбиения Т(Р).

Полученное противоречие показывает, что (Аад(Е) : А(Е)) ф 2. Значит, и в случае, если многогранник convV(E) — тетраэдр, также имеем (AeS(E):A(E)) = l. Верхняя оценка степени грани разбиения данной коразмерности В данном параграфе приводится доказательство Теоремы 2.3. Пусть Е — произвольная грань разбиения Т(Р). Далее, не умаляя общности, будем считать, что Е — грань параллелоэдра Р. Напомним, что размерность параллелоэдра Р обозначена через d, а к — коразмерность грани Е, т.е. такое целое число, что dimE = d — k.

Сначала мы изучим множество всех граней параллелоэдра Р, эквивалентных грани Е с точностью до параллельного переноса, сохраняющего решетку Л(Р). Далее, спроектировав эти грани вдоль любой из них, мы получим некоторое множество точек в Шк. Мы покажем, что это множество обладает свойством антипо дальности, аналогичным введенному Данцером и Грюнбаумом в работе [18]. Наконец, мы модифицируем доказательство Данцера и Грюнбаума для того, чтобы оценить сверху мощность антиподального множества.

Для единообразия обозначений положим Е\ = Е. Пусть {Ei,E2,... ,Ет} — это множество всех граней параллелоэдра Р, эквивалентных грани Е\ с точностью до параллельного переноса, сохраняющего решетку Л(Р). Для каждой пары (i,j) є {1, 2,...,m}2 определим параллельный перенос tij и параллелоэдр Р так, чтобы выполнялись равенства

Параллелоэдр Р заключен между гиперплоскостями Г и Г , поэтому множество W заключено между гиперплоскостями jij и jji. Гиперплоскости 7у и lji различны в силу того, что точка proj (с(Р)) лежит строго между ними. Следовательно, для любой пары точек w;,Wj є W мы построили требуемую пару гиперплоскостей.

Параллелоэдры, свободные вдоль векторов, и гипотеза Вороного

По предположению, выполняется условие 2 Теоремы 3.3. Отсюда следует, что в рассматриваемом случае (G3) образования (d — 2)-грани многогранника Р +1 отрезок / допустим для веера Fan(").

По Теореме 2.1 о классификации схождений в (d — 3)-мерных гранях, веер Fan(E") принадлежит одному из пяти типов (см. рис. 1.3 на стр. 11). Для каждого из этих типов веера несложно классифицировать все допустимые отрезки. А именно, пара (Fan("),7), где Fan(E") — веер одного из типов, указанных на рис. 1.3, а / — отрезок допустимый для веера Fan("), отвечает одному из 13 комбинаторно различных типов (см. рис. 3.2).

В восьми случаях а.1), а.2), Ь.2), с.2), с.З), d.2), d.3), е.З) никакой транслят вида Е" = " + t, где t є Л(Р) и Е" — грань параллелоэдра Р, не может порождать грань вида Е" 0 / многогранника Р + I. При t = 0 это противоречит предположению (G3) о том, что у многогранника Р +1 есть грань вида Е 0 I.

Далее, в трех случаях c.l), d.l) и е.1) ровно 3 транслята вида Е" = Е +1, где t є Л(Р) и Е" — грань параллелоэдра Р, порождают грань вида Е" 0 / многогранника Р + I. Легко проверить, что локальное разбиение вокруг каждой такой грани Е"ф1 существует и состоит из трех транслятов многогранника Р +1.

С другой стороны, мы предполагаем, что верно условие (G3) о том, что у многогранника Р + I есть грань вида Е 0 I. Это значит, что среди транслятов вида Е" = " + t, порождащих грань многогранника P + I вида Е" 0/, есть и грань Е . Таким образом, в случаях c.l), d.l) и е.1) грань Е 0 / задает шестигранный поясок многогранника Р + I.

Наконец, в оставшихся двух случаях b.l) и е.2) ровно 4 транслята вида Е" = Е + t, где t є Л(Р) и Е" — грань параллелоэдра Р, порождают грань вида Е" 0 / многогранника Р + I. Легко проверить, что локальное разбиение вокруг каждой такой грани Е" 0 / существует и состоит из

С другой стороны, мы предполагаем, что верно условие (G3) о том, что у многогранника Р + I есть грань вида Е 0 I. Это значит, что среди транслятов вида Е" = " + t, порождащих грань многогранника P + I вида Е" 0 /, есть и грань Е . Таким образом, в случаях Ь.1) и е.2) грань Е ф I задает четырехгранный поясок многогранника Р + I.

Следовательно, для многогранника Р + I верно и условие (MV3) о поясках. Значит, Р +1 — параллелоэдр, и импликация 2 == 1 доказана.

Приведем здесь же результат А. Хорвата [30], совмещающий Теорему 3.3 с Теоремой 3.1 Венкова. Как и раньше, мы будем использовать обозначение s(E) для стандартного вектора стандартной же грани Е па-раллелоэдра Р. Если / — такой отрезок, что многогранники Р и Р + I — d-мерные параллелоэдры, то введем следующие обозначения.

Пусть Р — параллелоэдр Вороного, а I — такой отрезок, что сумма Минковского Р + I является параллелоэдром. В данном параграфе мы рассмотрим вопрос: при каком необходимом и достаточном условии для параллелоэдра Р + I верна гипотеза Вороного?

Предположим, что Р ф I — прямая сумма. Тогда Р ф I — параллелоэдр Вороного, поскольку оба прямых слагаемых — параллелоэдры Вороного.

Следовательно, далее мы всегда предполагаем, что dim(P + /) = dim Р. Напомним, что d-мерный параллелоэдр Р + І, полученный как сумма Минковского (і-мерного параллелоэдра Р и отрезка /, называется удлинением параллелоэдра Р.

Для дальнейшего нам потребуется понятие канонической нормировки. Пусть Q — положительно определенная квадратичная форма в Wd, а — произвольная аффинная гиперплоскость. Вектор п назовем нормалью относительно формы Q к гиперплоскости а, если для любых двух точек х, у є а выполяется пт П (х - у) = 0.

Пусть в Wd фиксирована квадратичная форма Q и d-мерный параллелоэдр Р. Предположим, что каждой гиперграни F параллелоэдра Р сопоставлен вектор s(F), являющийся нормалью относительно Q к гиперплоскости aff F. Предположим также, что выполнены следующие условия. (CS1) Для каждой гиперграни F вектор s(F) — внешняя нормаль грани F (т.е. Р П (F + es{F)) = 0 при любом є 0). (CS2) Для любой пары F и — F гиперграней параллелоэдра Р, переходящих друг в друга при центральной симметрии многогранника Р (антипо-далъных гиперграней), имеет место равенство s(—F) = —5(F). (CS3) Для любого шестигранного пояска параллелоэдра Р, гиперграни которого занумерованы F\) F2)..., FQ в порядке обхода, верно соотношение s(Fi)+5(F3)+s(F5) = 0. (3.1) Тогда отображение s, сопоставляющее каждой гиперграни параллелоэдра Р некоторую ее номаль, назовем канонической нормировкой параллелоэдра Р.

Сформулируем основную теорему о канонической нормировке. Для случая единичной матрицы Q формулировку и доказательство Теоремы 3.5 можно найти в [22, Theorem 2, 1 Ф 3]. Случай произвольной положительно определенной формы Q сводится к случаю единичной матрицы аффинным преобразованием.

Теорема 3.5. Пусть Р — параллелоэдр, a Q — положительно определенная квадратичная форма в Rd. Тогда следующие условия эквивалентны. 1. Р — параллелоэдр Вороного относительно некоторой квадратич ной формы Q , вообще говоря, отличной от Q. 2. Р допускает каноническую нормировку относительно формы Q. Замечание. Отметим, что работы Вороного, Житомирского и Ордина, уста навливающие гипотезу Вороного для специальных классов параллелоэдров, используют Теорему 3.5 или эквивалентные ей утверждения. Введем понятие графа Венкова, которым мы воспользуемся при формулировке результатов о единственности канонической нормировки. Графом

Операция обобщенного удлинения параллелоэдров Вороного

Переход от формы Qni к форме ( П1)п2 не уменьшает никакое расстояние между точками, следовательно, расстояние между последовательными гиперплоскостями пучка Х\ в метрике, заданной формой (Г2П1)П2, остается р.

Рассмотрим разбиение Делоне V для решетки Л относительно формы ( ni)n2- Покажем, что у каждого треугольника А є V есть хотя бы одно ребро, параллельное (3\ П /.

По Следствию 4.8, любое ребро разбиения V параллельно либо гиперплоскости /Зі, либо гиперплоскости (З2, либо им обеим. По принципу Дирихле, у треугольника А есть 2 ребра, параллельные одной и той же гиперплоскости (3{. Значит, aff А /.

Предположим, что никакое ребро треугольника А не параллельно пересечению (3\ П (З2. Это означает, что ни одно ребро треугольника А не параллельно П , где {i,j} = {1,2}. В таком случае вершины треугольника А принадлежат попарно различным гиперплоскостям пучка Xj. Обозначим вершины треугольника А через хь Х2, хз так, чтобы гиперплоскость пучка Xj, проходящая через Х2 лежала между гиперплоскостями того же пучка,

Рассмотрим подмножество Xj с Xj, состоящее из тех гиперплоскостей пучка Х\, которые содержат хотя бы одну точку двумерной решетки aff А П Л. Легко видеть, что все расстояния между последовательными гиперплоскостями пучка Xj одинаковы, и что пересечение каждой гиперплоскости пучка Xj с гиперплоскостью / содержит {& — 2)-мерную подрешетку решетки Л. Наконец, те гиперплоскости пучка Xj, которые проходят через точки xi, Х2 и хз, принадлежат и пучку Xі-.

Пусть интервал (хі,хз) пересекается в точности с т гиперплоскостями пучка Xі-. При этом, очевидно, т 1. Положим Очевидно, х4 Є [хі,хз]. Неформально говоря, формула (4.6) означает, что Х4 — точка пересечения отрезка [хі,хз] и третьей по направлению от xi к хз плоскости пучка Х-, если считать плоскость, проходящую через хь первой.

Т.к. [хі,хз] — ребро разбиения Делоне V, сфера дВ п )п (хьх3) является пустой. Сделаем гомотетию этой сферы с центром в точке xi и коэффициентом . При этом шар B(fini)n2(xi,x3) перейдет в шар Б(ппі)п2(хі,х4). Поскольку - ц 1, имеем а значит сфера дВ п )n (хі,х4) также пуста. По выбору точки х4, точка (хі+х4)/2 принадлежит некоторой плоскости пучка Х-. Поэтому (п — 2)-мерная аффинная плоскость содержит (п — 2)-мерную решетку, и все ее пустые сферы относительно формы (Г2щ)п2 имеют радиус, не превосходящий р. С другой стороны, сфера поскольку точки xi и х4 принадлежат двум плоскостям пучка Xj, между которыми есть еще отна плоскость того же пучка. Из полученного противоречия следует, что у любого треугольника А є V есть хотя бы одно ребро, параллельное плоскости / П/З2. По Теореме 3.3, ортогональное дополнение относительно формы (Г2П1)П2 к плоскости /Зі П / является свободным пространством параллелоэдра Вороного Р(Л, (Г2щ)п2)- Но несложно проверить, что векторы пі и П2 независимы и ортогональны плоскости / П / относительно формы (Г2П1)П2.

Лемма 4.11. Пусть Теоремы 4.4 и 4.6 выполняются для всех параллелоэдров размерности не более п. Тогда любой n-мерный параллелоэдр Вороного, имеющий крест, приводим, т.е. Теорема 4.2 выполняется для параллелоэдров Вороного размерности п.

Доказательство. Пусть n-мерный параллелоэдр Вороного Р = P(A,Q) имеет крест. Тогда множество фасетных векторов Т(А, Q) можно разделить на 2 подмножества Т\ Т так, что dim (J7;) п. При необходимости добавим к каждому из множеств Т\ и Т по несколько векторов решетки Л так, чтобы получились базисы двух гиперплоскостей, которые обозначим через /Зі и /З2 соответственно. По построению, пара (/31,/) является крестом для параллелоэдра Р, и при этом удовлетворяет условиям Леммы 4.10.

Согласно Лемме 4.10, существует параллелоэдр Р(Л, (Г2П1)П2), для которого плоскость (пі,П2) является свободной. Также, в силу Следствия 4.8, пара (/Зі, /?2) является крестом и для параллелоэдра Р(Л, (Г2П1)П2).

Воспользуемся Теоремой 4.4, которая, по предположению, верна для n-мерных параллелоэдров. Из нее следует, что параллелоэдр Р(Л, (Г2П1)П2) приводим. Пусть его разложение в прямую сумму неприводимых слагаемых имеет вид причем аЛRi / (і = 1,2). Из результата [6, Леммы 5, 6] следует, что аффинные оболочки aff R\ и affi взаимно ортогональны относительно формы (fini)n2 Отсюда следует, что ( П1)П2 = Г2і + Q2, где Г2і и Г22 неотрицательно определенные квадратичные формы с ядрами linaff/ and linaff R\ соответственно.

Ядром квадратичной формы (Г2П1)П2 — Qni является гиперплоскость [32, содержащая в себе линейное подпространство linaff .. Поэтому ядро формы также содержит linaffR2. С другой стороны форма Q[ должна быть положительно определенной на линейном подпространстве linaff Ль поскольку в противном случае форма Qni = Q2 + &[ не является положительно определенной.

Формы Q[ и Q2 имеют ядра linaffR2 и linaffR\ соответственно, т.е. kerf 0ker 2 = Ш.п. Следовательно, имеет место равенство Р(Л,Г2П1) = R[ Ф R i, где affi (3\. Отметим также, что пара гиперплоскостей (/ 1,/) является крестом для параллелоэдра Р(Л, Г2П1).

Таким образом, из приводимости параллелоэдра Р(Л, (Г2П1)П2) была выведена приводимость параллелоэдра Р(Л,Г2П1). Точно так же из приводимости параллелоэдра Р(Л, Г2П1) выведем приводимость параллелоэдра Р.

Закончим доказательство основных результатов данной главы выполнением шага индукции для Теоремы 4.4. Для этого будем использовать Теоремы 4.2 and 4.6 для (d — 2)-мерных параллелоэдров. Это возможно благодаря доказанному в Параграфе 4.4.

Также мы будем интенсивно использовать результаты Параграфа 3.6. Действительно, параллелоэдр Р из условия Теоремы 4.4 имеет свободную двумерную плоскость, а значит, по Лемме 3.16, он должен иметь и совершенную свободную двумерную плоскость.

Разобьем доказательство на шаги, представленные в виде отдельных лемм. Лемма 4.12. Пусть R = P(A,Q) — параллелоэдр Вороного, a v — вектор из линейного пространства linaff R. Будем также считать, что одной из ячеек разбиения T(R) является сам параллелоэдр R, а ценром параллелоэдра R является начало координат.

Зафиксируем транслят R + v параллелоэдра R. Для каждой гиперграни F с R изучим локальную структуру разбиения T(R) в точке v + s(F), центре гиперграни F + v рассматриваемого транслята Л + v. Будем говорить, что гипергрань F хорошая (относительно вектора v), если среди граней разбиения T(R), сходящихся в точке v + s(F), нет гиперграни вида F + t, где t є A(R). В противном случае назовем гипергрань F плохой.

Таким образом, все гиперграни параллелоэдра Р кроме двух параллельны прямой І2- Следовательно Р — призма. Аналогично, параллелоэдр Р является призмой, если V2 Є A(R).

Пусть Р не является призмой. По Лемме 3.21, R — параллелоэдр Вороного для некоторой евклидовой метрики пространства Ed 2, в котором он лежит. Покажем, что если каждая гипергрань параллелоэдра R является хорошей (в смысле Леммы 4.12) относительно хотя бы одного из векторов vi or V2, то R имеет крест. Для j = 1,2 выберем вектор

В силу Леммы 4.12, любая гипергрань параллелоэдра R параллельна хотя бы одному из векторов — vi или v2. Это равносильно тому, что каждый фасетный вектор параллелоэдра R ортогонален хотя бы одному из векторов vi или v2 относительно той метрики, в которой R — параллелоэдр Вороного. Таким образом, ортогональные дополнения к прямым (vi) и (v2) образуют крест для R.