Комбинаторика параллелоэдров и ее связь с гипотезой Вороного тема диссертации и автореферата по ВАК РФ 01.01.04, кандидат наук Магазинов, Александр Николаевич

• Магазинов, Александр Николаевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Магазинов, Александр Николаевич

ГЛАВА 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. Основные результаты главы ..........................................80

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Комбинаторика параллелоэдров и ее связь с гипотезой Вороного»

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

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

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

Параллелоэдром (см. [15]) называется выпуклый многогранник Р, допускающий разбиение грань-в-грань пространства M.d своими транслятами (параллельными копиями). Т.е. для d-мерного параллелоэдра Р существует такое множество транслятов

Т(Р) = {Р + ti : г = О,1,2,..., t0 = 0}, (1.1)

что

оо

(TI) U(-P + t¿)=Md;

г=0

(Т2) reí int(P +1¿) П reí int(P + t¿) = 0 при i ф j\

(ТЗ) Пересечение (P + t¿) П (P + tj) пусто, или является гранью каждого

из многогранников (P + t¿) и (P + t¿). В дальнейшем через Т{Р) будем обозначать именно разбиение вида (1.1) со свойствами (Т1) - (ТЗ).

Пусть Р — d-мерный параллелоэдр. Тогда (см., например, [35]) множество векторов трансляций, совмещающих Р с какой-либо ячейкой разбиения Т(Р) (т.е. множество {t¿}^0 в формуле (1.1)) является d-мерной решеткой. Будем обозначать эту решетку через Л(Р).

Всякий ¿-мерный параллелоэдр Р обладает следующими свойствами. (МУ1) Р имеет центр симметрии.

(МУ2) Любая (в, — 1)-грань (гипергрань) Р С Р имеет центр симметрии. (МУЗ) Любой (<1 — 2)-грани С С Р параллельны либо ровно 4, либо ровно 6 гиперграней параллелоэдра Р. Свойства (МУ1) и (МУ2) доказаны Минковским [35], а свойство (МУЗ) — Б. Н. Делоне [20]. Б. А. Венков [4] и независимо П. МакМаллен [34] показали, что если выпуклый многогранник Р обладает свойствами (МУ1) -(МУЗ), то Р — параллелоэдр. Свойства (МУ1) - (МУЗ) называются свойствами Минковского-Венкова.

Пусть С — произвольная (в, — 2) грань (¿-мерного параллелоэдра Р. Пояском, заданным гранью (7, называется множество всех гиперграней параллелоэдра Р, параллельных грани С?.

Пусть поясок параллелоэдра Р, заданный гранью С, состоит из га гиперграней (га = 4 или 6). Тогда можно все — 2)-грани параллелоэдра Р, параллельные грани С, можно занумеровать как

С?2> ■ ■ • > 1)

(при этом сама грань (? получит некоторый номер; пусть, не умаляя общности, га), а все гиперграни пояска, заданнного гранью занумеровать, соответственно,

так, что Р1 П 1 = при г = 1,2,..., га (в случае г = т считается, что ^т+1 =

Далее, если не оговорено иное, будем считать, что центр параллелоэдра Р расположен в «начале координат» 0. Для центра симметрии выпуклого многогранника <5 (не обязательно параллелоэдра), если этот центр существует, мы будем использовать обозначение с {О).

Перейдем к формулировке гипотезы Вороного.

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

iV(A) = {у € Ed : ||ут - 0|| = min ||у - х||}.

хеА

Многогранник Д/(Л), а также любой его транслят, будем называть парал-лелоэдром Вороного решетки А в метрике пространства Ed.

Несложно показать, что Pv{h) — действительно параллелоэдр, и что

T(PV(А)) = {Pv{А) + х : х G А}.

Используя данное выше определение, гипотезу Вороного можно сформулировать в следующем (наиболее известном) виде. Гипотеза (Гипотеза Вороного, формулировка 1). Всякий параллелоэдр Р аффинно эквивалентен некоторому параллелоэдру Вороного Py{h).

При этом нам будет удобно считать, что аффинное пространство W1 в котором лежит параллелоэдр Р, и евклидово пространство Е^, в котором лежит параллелоэдр Ру(А), — это разные пространства; более того, в R^ нет наперед заданной метрической структуры.

Дадим более общее определение параллелоэдра Вороного. Пусть Q — положительно определенная квадратичная форма в пространстве Жа. Скалярное произведение векторов х и у относительно формы О, будем записывать как хт О у.

Пусть А — решетка в Rd и пусть О G А. Многогранник

Р(А, Ü) = {у е Ш* : УГ% = min(y - x'ff2(y - х')},

х'еА

а также любой его транслят, будем называть параллелоэдром Вороного решетки А относительно формы П.

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

Гипотеза (Гипотеза Вороного, формулировка 2). Всякий параллелоэдр Р аффинно эквивалентен некоторому параллелоэдру Вороного вида Р{Ъй,0), где О, — некоторая положительно определенная квадратичная форма в МЛ

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

Предположим, что параллелоэдр Р' аффинно эквивалентен параллелоэдру Ру{А) (где РУ(Л) С Е^). Пусть <р : Ж* Еа — такое аффинное отображение, что ф{Р') = Ру(Л). Тогда в пространстве можно ввести такую евклидову метрику, что отображение цз будет изометрией. Поэтому параллелоэдр Р' можно представить в виде Р(2,й,0).

Наконец, только что изложенное рассуждение можно повторить, взяв вместо Р' сам параллелоэдр Р, а вместо решетки Ъй — решетку Л(Р). Это приведет к третьей формулировке гипотезы Вороного. Гипотеза (Гипотеза Вороного, формулировка 3). Всякий параллелоэдр имеет вид Р(Л, Г2), где Л = Л(Р), а £1 — некоторая положительно определенная квадратичная форма в М^. Иначе говоря, всякий параллелоэдр является параллелоэдром Вороного.

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

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

а)

Ь)

Рис. 1.1. Двумерные вееры граней параллелоэдров

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

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

Обозначим через рго]а проекцию вдоль аффинного подпространства а на трансверсальное аффинное подпространство (3. В случае, если выбор подпространства /3 существенен, этот выбор будет оговариваться особо. Обозначение рго]д, где С} — многогранник, эквивалентно рго^д, где аА:<5 — аффинная оболочка многогранника <5.

Пусть Е — произвольная /с-грань «¿-мерного параллелоэдра Р. Пусть Рг,Р2, ■ • ■ ,Рт, где Р\ = Р, — все ячейки разбиения Т(Р), содержащие грань Е. Тогда проекции рго^Д) попарно не имеют общей относительной внутренности, и целиком заполняют некоторую (с1-к)-мерную окрестность 11 точки рто]Е(Е). Семейство многогранников {рго^Рг)}^ разбивате множество и так же, как и некоторый полный — А;)-мерный полиэдральный веер ¥&п(Е), который мы назовем веером грани Е.

Заметим, что свойство Минковского-Венкова (МУЗ) о числе гиперграней в пояске гарантирует, что для любой (с? — 2)-мерной грани С? С Р веер Еап(С) принадлежит одному из двух комбинаторных типов (рис. 1.1).

Мы будем рассматривать конструкции, связанные с понятием суммы Минковского. Напомним, что суммой Минковского (см. также [1]) двух

множеств X, У с называется множество

Х + У = {х + у:хеХ,уеУ}>

где под сложением точек имеется в виду взятие покоординатной суммы, т.е. точки отождествляются со своими радиус-векторами.

Пусть Р — «¿-мерный параллелоэдр, а I — такой отрезок в что сумма Минковского Р + 7 — также параллелоэдр. Будем называть параллелоэдр Р +1 удлинением параллелоэдра Р.

В работе В. П. Гришухина [8] вводится понятие параллелоэдр, свободный вдоль вектора. Мы будем говорить, что параллелоэдр Р свободен вдоль вектора х, если сумма Минковского Р+[—х, х] — параллелоэдр той же размерности, что и Р, т.е. удлинение параллелоэдра Р.

Сумму Минковского нескольких множеств .. С М^ будем

называть прямой и обозначать

Хг © х2 ©... е хк;

если сумма линейных пространств, ассоциированных с аффинными оболочками а!ТХг, является прямой. Параллелоэдр Р называется приводимым, если он представим в виде прямой суммы параллелоэдров меньшей размерности: Р = Р\ © Р2. Прямая сумма параллелоэдров Вороного есть параллелоэдр Вороного; и наоборот, если параллелоэдр Вороного Р приводим, то каждое слагаемое в разложении параллелоэдра Р в прямую сумму Минковского есть параллелоэдр Вороного (подробнее см., например, [6]).

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

Понятие параллелоэдра было введено в 1885 г. кристаллографом Е. С. Федоровым [15]. Он же вывел все 5 комбинаторных типов трехмерных параллелоэдров (см. рис. 1.2).

Рис. 1.2. Трехмерные параллелоэдры

Заметим, что одномерные выпуклые многогранники единственно возможного типа — отрезки — являются параллелоэдрами. Также легко доказать, что все двумерные параллелоэдры — это параллелограммы и цен-тральносимметричные шестиугольники.

Федоров существенно опирался на то, что параллелоэдры обладают центральной симметрей, считая это очевидным фактом. Строгое доказательство существования центра симметрии у любого параллелоэдра впервые дал Г. Минковский [35]. В той же работе он показал, что и все гиперграни параллелоэдра имеют центр симметрии. Тем самым были установлены свойства Минковского-Венкова (МУ1) и (МУ2).

Там же [35] Минковский показал, что число гиперграней ¿-мерного параллелоэдра не превосходит 2(2^—1). Отсюда мгновенно следует, что число комбинаторных типов й-параллелоэдров для каждого фиксированного с1 конечно.

В работе [39] Г. Ф. Вороной разработал метод непрерывного параметра, из которого следует алгоритм классификации всех параллелоэдров

А

--г

"7

7

а)

Ь)

с)

<0

е)

Рис. 1.3. Трехмерные вееры граней параллелоэдров

Вороного.

Вороным был введен специальный класс примитивных, параллелоэдров. Параллелоэдр Р размерности в, называется примитивным, если для любой его вершины V веер Рап(у) состоит ровно из в. + 1 конуса размерности сI. Это значит, что в каждой вершине разбиения сходится минимально возможное число параллелоэдров, <¿ + 1.

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

Работа Б. Н. Делоне [20] посвящена классификации четырехмерных параллелоэдров. Был получен 51 комбинаторный тип параллелоэдров в К4. Последний, 52-й был добавлен в классификацию М. И. Штогриным [17]. Для всех четырехмерных параллелоэдров верна гипотеза Вороного.

Кроме того, в [20], по-видимому, впервые получено условие Минковского-Венкова (МУЗ) о поясках. Наконец, Делоне показал, что для любого натурального с1, любого ¿-параллелоэдра Р и любой (с? — 3)-мерной грани Е С Р веер ¥ап(Е) имеет один из пяти комбинаторных типов (см. рис. 1.3). Последняя теорема оказала влияние на последующие работы по теории параллелоэдров. Ключевую роль играет она и в настоящей диссертации.

О. К. Житомирский [41] ввел понятие примитивной грани параллело-

эдра. Если Р — (¿-параллелоэдр, то его /с-грань Е называется примитивной, если Fan(J5) состоит ровно из d — к + 1 конуса размерности d — к. Если все /¿-грани параллелоэдра Р примитивны, то Р — к-примитивный параллелоэдр. Основной результат работы [41] в том, что любой {d — 2)-примитивный d-параллелоэдр является параллелоэдром Вороного. Иначе говоря, контрпример к гипотезе Вороного обязательно имеет хотя бы один четырехгранный поясок.

. В работах [19] и [9] Б. Н. Делоне ввел понятие L-разбиения (в настоящее время используется термин разбиение Делоне). Разбиение Делоне двойственно разбиению Вороного. Действительно, если А — решетка в M.d, V — разбиение Вороного, то каждой грани Е разбиения V можно сопоставить одну и только одну грань D{E) разбиения Делоне V так, что множество вершин многогранника D{E) — в точности множество центров всех ¿-мерных ячеек разбиения V, содержащих грань Е. При этом

dim Е + dim D(E) = d. (1.2) -

Аналогичное (1.2) равенство для всех параллелоэдров (а не только для параллелоэдров Вороного) не доказано и не опровергнуто. А именно, имеет место следующая неразрешенная гипотеза (см., например, [11]). Гипотеза (О размерности). Пусть Р — d-параллелоэдр, Е — грань разбиения Т(Р), ti, t2,... ,tm — центры всех d-мерных ячеек разбиения Т{Р), содержащих Е. Тогда

dim äff {ti, t2,..., tm} = d — dimi?.

Б. А. Венков [4] показал, что выпуклый многогранник, удовлетворяющий всем трем условиям Минковского-Венкова, является параллелоэдром. Кроме того, если выпуклый многогранник Р допускает какое-либо разбиение Rd своими транслятами (не обязательно грань-в-грань), то Р — параллелоэдр. Эти же результаты были получены независимо П. МакМал-

леном [34]. Н. П. Долбилиным был предложен другой подход к доказательству [23].

Е. П. Барановский и С. С. Рышков нашли [3] (с учетом поправок Эн-гела и Гришухина [27]) все 222 типа пятимерных примитивных параллело-эдров. Поскольку при d — 1,2,3 таких типов всего по одному, а при d = 4 — три, этот результат демонстрирует «комбинаторный взрыв», т.е. резкое увеличение числа типов параллелоэдров с ростом размерности. Согласно П. Энгелу [26], различных комбинаторных типов пятимерных параллелоэдров (не только примитивных) не менее 103 769. Это означает, что в размерностях d > 5 задача построения явного списка комбинаторных типов параллелоэдров, скорее всего, не является обозримой.

П. МакМаллен [33] рассмотрел еще один класс параллелоэдров — па-раллелоэдры, являющиеся зонотопами {space-filling zonotopes). Зоното-пом называется многогранник, представимый как параллельная проекция куба размерности п > d в пространство Rd. Или, что эквивалентно, зоно-топ — это сумма Минковского конечного набора отрезков.

В [33] доказывается ослабленная версия гипотезы Вороного для параллелоэдров, являющихся зонотопами, — любой параллелоэдр, являющийся зонотопом, комбинаторно эквивалентен параллелоэдру Вороного. Гипотеза Вороного для параллелоэдров, являющихся зонотопами, была окончательно доказана Р. Эрдалом [28].

В диссертации А. Ордина [36] усилена теорема Житомирского. А именно, для 3-неприводимых параллелоэдров доказывается гипотеза Вороного. Параллелоэдр Р размерности d называется 3-неприводимым, если веер каждой его (d — 3)-грани отвечает одному из типов а), Ь) или с) рис. 1.3. При этом заметим, что параллелоэдр (d — 2)-примитивен (является парал-лелоэдром Житомирского) тогда и только тогда, когда веер каждой его (d — 3)-грани отвечает одному из типов а) или Ь).

Наиболее сложная часть доказательства гипотеза Вороного для 3-

неприводимых параллелоэдров заключается в анализе локальной структуры разбиения Т(Р) в {в, — 4)-гранях.

Также в [36] доказывается критерий приводимости параллелоэдра (и находится число неприводимых компонент) в терминах красно-синего графа Венкова.

В работе [8] В. П. Гришухин доказал гипотезу Вороного для удлинений {в,—2)-примитивных параллелоэдров. Существенным моментом является то, что в силу результата Житомирского [41] {в, — 2)-примитивные параллело-эдры образуют подкласс класса параллелоэдров Вороного. Поэтому там же [8] поставлена задача доказать гипотезу Вороного для всех параллелоэдров вида Р+7, где Р — параллелоэдр Вороного, а 7 — отрезок. Обратное утверждение (гипотеза Вороного для параллелоэдра Р следует из гипотезы Вороного для параллелоэдра Р + 7) доказано в [38, Теорема 3.17].

Н. П. Долбилин [10] ввел понятие стандартной грани параллелоэдра. Пусть РяР' = Р + Ь — ячейки разбиения Т(Р), при этом Р П Р' ф 0. Тогда грань Е — Р П Р' назовем стандартной гранью параллелоэдра Р. Если, по-прежнему, предполагается, что с(Р) = 0, то грань Е имеет центр симметрии в точке 1;/2 [10,29]. Вектор t назовем стандартным вектором грани Е.

В [10] доказывается теорема об индексе. Индексом грани Е параллелоэдра называется число 1/и(Е), где и{Е) — число конусов максимальной размерности в веере ¥ап(Е). Тогда

Е

где суммирование ведется по всем стандартным граням Е фиксированного параллелоэдра Р.

Заметим, что все гиперграни параллелоэдра Р стандартны и имеют индекс 1/2. Это дает другое доказательство оценки Минковского на число гиперграней параллелоэдра.

Среди (<& — 2)-граней «¿-параллелоэдра стандартны те и только те, которые задают четырехгранные пояски. Напротив, примитивны (по Житомирскому) те и только те (с£ — 2)-грани, которые задают шестигранные пояски. Соответственно, для различения двух типов (в, — 2)-граней мы будем применять термины стандартные и примитивные.

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

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

В формулировках мы всюду предполагаем, что Р — «¿-мерный паралле-лоэдр. Грани размерности <1 — к мы будем также называть гранями коразмерности к.

• В любой ((¿—£)-мерной грани разбиения Т(Р) сходится не более, чем 2к ячеек разбиения. При любых целых <¿>1, к>0, (1>к эта оценка точна.

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

• Пусть I — отрезок, Р и ? + / - параллелоэдры, причем Р — па-раллелоэдр Вороного. Тогда Р + / — также параллелоэдр Вороного (возможно, для другой квадратичной формы, нежели Р). Иначе говоря, для любого удлинения параллелоэдра Вороного верна гипотеза Вороного.

Данный результат является решением задачи В. П. Гришухина (ему эквивалентна, например гипотеза из [8, §7]). Из этого результата также следует теорема Эрдала о том, что гипотеза Вороного верна для паралле-лоэдров, являющихся зонотопами.

• Пусть Р — параллелоэдр Вороного, и каждый его фасетный вектор принадлежит одной из двух фиксированных гиперплоскостей. Тогда Р приводим.

Это утверждение (Теорема 4.2 настоящей диссертации) непосредственно обобщает следующий факт, известный автору как фольклорный. Предложение. (См., напрмер, [8, Предложение 4].) Пусть Р — параллелоэдр Вороного в Предположим, что в М^ существуют два таких дополнительных друг к другу подпространства а и /3 (а Г) (3 = О, а ф /3 = Жа), что всякий фасетный вектор параллелоэдра Р принадлежит либо подпространству а, либо подпространству ¡3. Тогда Р приводим..

В только что приведенном Предложении условие о том, что параллелоэдр Р принадлежит классу параллелоэдров Вороного, избыточно. Это было показано А. Ординым [36] (см. Лемму 4.3 настоящей диссертации). Однако еще более обобщить Теорему 4.2 — на случай произвольного параллелоэдра Р (не обязательно параллелоэдра Вороного) — пока не удалось.

В данной диссертации, кроме того, впервые дано полное доказательство необходимого и достаточного условия для того, чтобы параллелоэдр был свободен вдоль данного вектора (само условие впервые сформулированно в работе [7]). Также приводится новое, комбинаторное, доказательство теоремы Делоне о веерах граней коразмерности 3.

Результаты диссертации опубликованы в работах автора [12,13,31], препринте [32], а также в совместной работе [25] с М. Дютуром и В. П. Гри-шухиным.

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

Дальнейшие главы диссертации (Главы 2-4) устроены следующим образом.

Глава 2 посвящена локальной теории параллелоэдров. Основной ее результат — точная верхняя оценка числа параллелоэдров, сходящихся в грани коразмерности к разбиения — сформулирован в Параграфе 2.1 и доказан в Параграфе 2.4. Доказательство основано на понятии антиподального множества и использует технику Данцера и Грюнбаума из работы [18].

В Параграфе 2.2 изложено новое доказательство теоремы Делоне о схо-жениях параллелоэдров в гранях разбиения коразмерности 3. Для доказательства используется формула Эйлера. Теорема Делоне будет важнейшим инструментом, используемым в остальных главах диссертации. В Разделе 2.3 доказаны следствия из теоремы Делоне, уточняющие свойства трехмерных дуальных клеток. В частности, для граней коразмерности 3 проверена гипотеза о размерности.

Глава 3 посвящена свойствам удлинений параллелоэдров. Главная цель — подготовить необходимые понятия и доказть вспомогательные результаты, используемые в Главе 4.

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

Параграф 3.2 посвящен доказательству критериального условия, при котором параллелоэдр Р свободен вдоль данного вектора. Критерий был впервые сформулирован в [7], но в доказательстве из [7] есть пробел, который восполняется в данной диссертации.

В Параграфе 3.3 приведено полное доказательство критерия того, что

сумма неприводимого параллелоэдра Р и отрезка I удовлетворяет гипотезе Вороного. Критерий был впервые сформулирован в [8]. Приводимое в [8] доказательство также содержит пробел, который восполняется в данной диссертации методом, аналогичным изложенному в Параграфе 3.2. Кроме того, как и в работе [8], в доказательстве используется понятие канонической нормировки. Все необходимые определения и результаты, связанные с канонической нормировкой, также приводятся в Параграфе 3.3.

В последние трех параграфа Главы 3 доказываются технические леммы, используемые в Главе 4.

В Параграфе 3.4 показывается, что для параллелоэдра Р, свободного в направлении вектора х можно определить слои, из которых состоит разбиение Т(Р). Аналогичная послойная конструкция была использована в работе [20] для комбинаторной классификации четырехмерных параллело-эдров.

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

В Параграфе 3.6 изучаются свойства параллелоэдров Вороного, имеющих двумерное свободное пространство. Строятся слои размерности (1 — 2, аналогичные слоям, введенным в [5].

Основной результат Главы 4 — доказательство гипотезы Вороного для удлинений параллелоэдров Вороного. Тем самым дается решение задачи В. П. Гришухина. Попутно для параллелоэдров Вороного усиливается лемма Ордина о приводимости.

Параграф 4.1 является вводным и содержит формулировки основных результатов Главы 4.

В Параграфе 4.2 гипотеза Вороного для удлинений параллелоэдров Во-

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

1. Всякий параллелоэдр Вороного с двумерным свободным пространством приводим.

2. Если каждый фасетный вектор параллелоэдра Вороного Р принадлежит хотя бы одной из двух фиксированных гиперплоскостей, то параллелоэдр Р приводим.

3. Если каждый фасетный вектор параллелоэдра Вороного Р принадлежит хотя бы одной из двух фиксированных гиперплоскостей, то каждая неприводимая компонента в разложении параллелоэдра Р в прямую сумму Минковского параллельна одной из данных гиперплоскостей.

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

Наконец, в Параграфах 4.4 и 4.5 выполнен шаг индукции, откуда немедленно следуют основные результаты Главы 4.

Список литературы диссертационного исследования кандидат наук Магазинов, Александр Николаевич, 2014 год

1. А. Д. Александров, Выпуклые многогранники, М., ГИТТЛ, 1950; Новосибирск, «Наука», 2007.

2. А. Д. Александров, О заполнении пространства многогранниками // Вестник Ленинградского Университета, сер. мат., физ., хим., 2 (1954), 33 - 43.

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

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

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

6. А. А. Гаврилюк, Класс аффинно эквивалентных параллелоэдров Вороного // Матем. заметки, 95:5 (2014), 697 - 707.

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

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

9. Б. Н. Делоне, Геометрия положительных квадратичных форм (Часть I) //УМН, 3 (1937), 16 - 62.

10. Н. П. Долбилин, Свойства граней параллелоэдров // Геометрия, топология и математическая физика II, Сборник статей. К 70-летию со дня рождения академика Сергея Петровича Новикова, Тр. МИАН, 266 (2009), 112 - 126.

11. Н. П. Долбилин, Параллелоэдры: ретроспектива и новые результаты // Тр. ММО, 73:2 (2012), 259 - 276.

12. А. H. Магазинов, К теореме Делоне о классификации схождений па-раллелоэдров в гранях коразмерности 3 // Модел. и анализ информ. систем., 20:4 (2013), 71 - 80.

13. А. Н. Магазинов, Гипотеза Вороного для удлинений параллелоэдров Вороного // УМН, 69:4 (2014), 179 - 180.

14. С. С. Рышков, Е. А. Большакова, К теории коренных параллелоэдров // Изв. РАН. Сер. матем., 69:6 (2005), 187 - 210.

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

16. А. Т. Фоменко, Д. Б. Фукс, Курс гомотопической топологии, Москва, Наука, 1989.

17. М. И. Штогрин, Правильные разбиения Дирихле-Вороного для второй триклинной группы, Тр. МИАН СССР, 123 (1973), ред. С. М. Никольский, 128 с.

18. L. Danzer, В. Grünbaum, Über zwei Probleme bezüglich konvexer Körper von P. Erdös und von V. L. Klee // Math. Zeitschrift, 79 (1962), 95 - 99.

19. B. N. Delaunay, Sur la sphère vide // in Proc. Math. Congr. Toronto, August 11 - 16, 1924, Univ. of Toronto Press, Toronto, 1928, 695 -700.

20. B. N. Delaunay, Sur la partition régulière de l'espace à 4 dimensions // Известия АН СССР. Серия VII, отделение физико-математических наук, 1 - 2 (1929), 79 - 110, 147 - 164.

21. M. M. Deza, M. Laurent, Geometry of Cuts and Metrics. Springer, Berlin - Heidelberg - New York, 1997.

22. M. Deza, V. Grishukhin, Properties of parallelotopes equivalent to Voronoi's conjecture // European Journal of Combinatorics, 25 (2004), 517 - 533.

23. N. P. Dolbilin, The extension theorem, Discrete Math., 221:1-3, Selected papers in honor of Ludwig Danzer (2000), 43 - 59.

24. M. Dutour, The six-dimensional Delaunay polytopes // European Journal of Combinatorics, 25 (2004), 535 - 548.

25. M. Dutour Sikiric, V. Grishukhin, A. Magazinov, On the sum of the Voronoi polytope of a lattice with a zonotope, European Journal of Combinatorics 42 (2014), 49 - 73, online: http://dx.doi.Org/10.1016/j.ejc.2014.05.005.

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

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

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

29. Ä. G. Horväth, On the boundary of an extremal body // Beiträge zur Algebra und Geometrie 40:2 (1999), 331 - 342.

30. Ä. G. Horväth, On the connection between the projection and the extension of a parallelotope // Monatshefte für Mathematik, 150:3 (2007), 211 - 216.

31. A. Magazinov, An upper bound for a valence of a face in a parallelohedral tiling // European Journal of Combinatorics, 34:7 (2013), 1108 - 1113.

32. A. Magazinov, Voronoi's Conjecture for extensions of Voronoi parallelohedra // Preprint: arXiv: 1308. 6225, 2013.

33. P. McMullen, Space tiling zonotopes // Mathematika, 22:2 (1975), 202 - 211.

34. P. McMullen, Convex bodies which tile space by translation // Mathematika, 27:1 (1980), 113 - 121.

35. H. Minkowski, Allgemeine Lehrsätze über die konvexe Polyeder // Nach. Ges. Wiss., Göttingen, 1897, 198 - 219.

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

37. G. C. Shephard, Convex bodies which tile space by translation // Mathematika, 21:2 (1974), 261 - 269.

38. A. Vegh, Räcsok, kör- és gômbelrendezések // диссертация, ВМЕ, Budapest, 2006.

39. G. F. Voronoi, Nouvelles applications des paramètres continus à là théorie des formes quadratiques, Deuxième Mémoire, Recherches sur les parallélloedres primitifs // J. Reine Angew. Math. 134 (1908) 198-287, 136 (1909) 67-181.

Переиздание: Г. Ф. Вороной, Исследования по теории примитивных параллелоэдров. Собр. соч., Т. 2. Киев: Изд. АН УССР, 1952. - 482 с.

40. G. M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, Springer-Verlag, New York, 1995.

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