«КОМБИНАТОРИКА ПАРАЛЛЕЛОЭДРОВ И ЕЕ СВЯЗЬ С ГИПОТЕЗОЙ ВОРОНОГО ...»

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ

БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ

МАТЕМАТИЧЕСКИЙ ИНСТИТУТ ИМ. В.А. СТЕКЛОВА

РОССИЙСКОЙ АКАДЕМИИ НАУК

На правах рукописи

Магазинов Александр Николаевич

КОМБИНАТОРИКА ПАРАЛЛЕЛОЭДРОВ

И ЕЕ СВЯЗЬ С ГИПОТЕЗОЙ ВОРОНОГО

01.01.04 — Геометрия и топология

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

д.ф.-м.н. Н. П. Долбилин Москва — 2014

ОГЛАВЛЕНИЕ

Стр.

ГЛАВА 1. Введение 1.1. Параллелоэдры, условия Минковского–Венкова и гипотеза Вороного.................................. 1.2. Основные понятия........................... 1.3. Ключевые результаты теории параллелоэдров........... 1.4. Основные результаты диссертации.................. 1.5. План диссертации........................... ГЛАВА 2. Локальная структура разбиения на параллелоэдры 2.1. Определения и основные результаты главы............. 2.2. Локальная структура граней разбиения, имеющих коразмерность три................................ 2.3. Свойства граней параллелоэдров коразмерности три....... 2.4. Верхняя оценка степени грани разбиения данной коразмерности ГЛАВА 3. Удлинения параллелоэдров 3.1. Параллелоэдры, свободные вдоль векторов............. 3.2. Необходимое и достаточное условие свободы параллелоэдра вдоль вектора.............................. 3.3. Параллелоэдры, свободные вдоль векторов и гипотеза Вороного. 3.4. Послойная конструкция разбиения................. 3.5. Свободные и совершенные свободные пространства........ 3.6. Двумерные свободные пространства параллелоэдров Вороного.. ГЛАВА 4. Гипотеза Вороного для удлинений параллелоэдров Вороного 4.1. Основные результаты главы..................... 4.2. План доказательства......................... 4.3. Операция обобщенного удлинения параллелоэдров Вороного.. 4.4. Шаг индукции для Теорем 4.2 и 4.6................. 4.5. Шаг индукции для Теоремы 4.4................... Список использованных источников ГЛАВА

ВВЕДЕНИЕ

1.1. Параллелоэдры, условия Минковского–Венкова и гипотеза Вороного Параллелоэдром (см. [14]) называется выпуклый многогранник P, допускающий разбиение грань-в-грань аффинного пространства своими транслятами (параллельными копиями). Т.е., если dim P = d, то существует такое множество транслятов (1.1) T (P ) = {P + ti : i = 0, 1, 2,..., t0 = 0}, что (T1) (P + ti ) = Rd ;

i= (T2) rel int(P + ti ) rel int(P + tj ) = при i = j;

(T3) Пересечение (P + ti ) (P + tj ) пусто, или является гранью каждого из многогранников (P + ti ) и (P + tj ).

В дальнейшем через T (P ) будем обозначать только разбиения со свойствами (T1) – (T3).

Пусть P — d-мерный параллелоэдр. Тогда (см., например, [34]) множество векторов трансляций, совмещающих P с какой-либо ячейкой разбиения T (P ) (т.е. множество {ti } в формуле (1.1)) является d-мерной i= решеткой. Будем обозначать эту решетку через (P ).

Всякий d-мерный параллелоэдр P обладает следующими свойствами.

(MV1) P имеет центр симметрии.

(MV2) Любая (d 1)-мерная грань (гипергрань) F P имеет центр симметрии.

(MV3) Любой (d 2)-мерной грани G P параллельны либо ровно 4, либо ровно 6 гиперграней параллелоэдра P.

Свойства (MV1) и (MV2) доказаны Минковским [34], а свойство (MV3) — Б. Н. Делоне [19]. Б. А. Венков [3] и независимо П. МакМаллен [33] показали, что если выпуклый многогранник P обладает свойствами (MV1) – (MV3), то P — параллелоэдр. Свойства (MV1) – (MV3) называются свойствами Минковского–Венкова.

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

Если поясок состоит из m гиперграней (m = 4 или 6), то все (d 2)грани параллелоэдра P, параллельные грани G, можно обозначить а все гиперграни пояска, заданнного гранью G, можно, соответственно, обозачить так, что Fi Fi+1 = Gi при i = 1, 2,..., m.

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

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

Пусть Ed — d-мерное евклидово пространство с отмеченным «началом координат» 0. Пусть, далее, — d-мерная решетка в Ed и 0. Тогда определим параллелоэдр Вороного PV () как множество всех точек пространства Ed, для которых 0 — одна из ближайших точек среди узлов решетки. Иначе говоря, Несложно показать, что PV () — действительно параллелоэдр, и что Используя данное выше определение, гипотезу Вороного можно сформулировать в следующем (наиболее известном) виде.

Гипотеза (Гипотеза Вороного, формулировка 1). Всякий параллелоэдр P аффинно эквивалентен некоторому параллелоэдру Вороного PV ().

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

Дадим более общее определение параллелоэдра Вороного.

Пусть — положительно определенная квадратичная форма в пространстве Rd. Скалярное произведение векторов x и y относительно формы будем записывать как xT y.

Пусть — решетка в Ed и пусть 0. Многогранник будем называть параллелоэдром Вороного решетки относительно формы Рассмотрим аффинное пространство Rd с фиксированной (аффинной) системой координат. В выбранной системе координат целочисленные точки образуют выделенную решетку Zd. Легко видеть, что всякий d-мерный параллелоэдр P аффинно эквивалентен некоторому параллелоэдру P, для которого (P ) = Zd.

Предположим, что параллелоэдр P аффинно эквивалентен параллелоэдру PV () (где PV () Ed ). Пусть : Rd Ed — такое аффинное отображение, что (P ) = PV (). Тогда в пространстве Rd можно ввести такую евклидову метрику, что отображение будет изометрией. Поэтому параллелоэдр P можно представить в виде P (Zd, ). Следовательно, гипотеза Вороного допускает следующую переформулировку.

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

Этот подход удобен тем, что позволяет ввести классификацию т.н. Lтипов положительно определенных квадратичных форм в пространстве Rd, если фиксирована решетка Zd Rd.

Наконец, предыдущее рассуждение можно повторить, взяв вместо P сам параллелоэдр P, а вместо решетки Zd — решетку (P ). Это приведет к третьей формулировке гипотезы Вороного.

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

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

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

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

Рис. 1.1. Двумерные вееры граней параллелоэдров Обозначим через proj проекцию вдоль линейного подпространства на трансверсальное аффинное подпространство. В случае, если выбор подпространства существенен, этот выбор будет оговариваться особо.

Обозначение projQ, где Q — многогранник, эквивалентно proja Q, где a Q — аффинная оболочка многогранника Q.

Пусть E — произвольная k-грань d-мерного параллелоэдра P. Пусть P0 = P, P1, P2,..., Pm1 — все ячейки разбиения T (P ), содержащие грань E. Тогда проекции projE (Pi ) попарно не имеют общей относительной внутренности, и целиком заполняют некоторую (d k)-мерную окрестность U точки projE (E). Семейство многогранников {projE (Pi )}i=0 делит U так же, как и некоторый полный (d k)-мерный полиэдральный веер Fan(E), который мы назовем веером грани E.

Заметим, что свойство Минковского–Венкова (MV3) о числе гиперграней в пояске гарантирует, что для любой (d 2)-мерной грани G P веер Fan(G) принадлежит одному из двух комбинаторных типов (рис. 1.1).

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

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

Параллелоэдр P называется приводимым, если он представим в виде прямой суммы параллелоэдров меньшей размерности: P = P1 P2 (т.е.

такой суммы Минковского, что линейные оболочки слагаемых P1 и P2 являются дополнительными подпространствами). Прямая сумма параллелоэдров Вороного есть параллелоэдр Вороного; и наоборот, если параллелоэдр Вороного приводим, то каждое из прямых слагаемых — параллелоэдр Вороного.

1.3. Ключевые результаты теории параллелоэдров Понятие параллелоэдра было введено в 1885 г. кристаллографом Е. С. Федоровым [14]. Он же вывел все 5 комбинаторных типов трехмерных параллелоэдров (см. рис. 1.2).

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

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

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

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

Вороным был введен специальный класс примитивных параллелоэдров.

Параллелоэдр P размерности d называется примитивным, если для любой его вершины v веер Fan(v) состоит ровно из d + 1 конуса размерности d. Это значит, что в каждой вершине разбиения сходится минимально возможное число параллелоэдров, d + 1.

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

Работа Б. Н. Делоне [19] посвящена классификации четырехмерных параллелоэдров. Был получен 51 комбинаторный тип параллелоэдров в R4.

Последний, 52-й был добавлен в классификацию М. И. Штогриным [16].

Для всех четырехмерных параллелоэдров верна гипотеза Вороного.

Кроме того, в [19], по-видимому, впервые получено третье условие Минковского–Венкова (условие о поясках). Наконец, Делоне показал, что для любого натурального d, любого d-параллелоэдра P и любой (d 3)мерной грани E P веер Fan(E) имеет один из пяти комбинаторных типов Рис. 1.3. Трехмерные вееры граней параллелоэдров (см. рис. 1.3). Последняя теорема оказала влияние на последующие работы по теории параллелоэдров. Ключевую роль играет она и в настоящей диссертации.

О. К. Житомирский [40] ввел понятие примитивной грани параллелоэдра. Если P — d-параллелоэдр, то его k-грань E называется примитивной, если Fan(E) состоит ровно из d k + 1 конуса размерности d k.

Если все k-грани параллелоэдра P примитивны, то P — k-примитивный параллелоэдр. Основной результат работы [40] в том, что любой (d 2)примитивный d-параллелоэдр является параллелоэдром Вороного. Иначе говоря, контрпример к гипотезе Вороного обязательно имеет хотя бы один четырехгранный поясок.

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

Гипотеза (О размерности). Пусть P — d-параллелоэдр, E — грань разбиения T (P ), t1, t2,..., tm — центры всех d-мерных ячеек разбиения T (P ), содержащих E. Тогда Б. А. Венков [3] показал, что выпуклый многогранник, удовлетворяющий всем трем условиям Минковского–Венкова, является параллелоэдром.

Кроме того, если выпуклый многогранник P допускает какое-либо разбиение Rd своими транслятами (не обязательно грань-в-грань), то P — параллелоэдр. Эти же результаты были получены независимо П. МакМалленом [33]. Н. П. Долбилиным был предложен другой подход к доказательству [22].

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

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

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

В диссертации А. Ордина [35] усилена теорема Житомирского. А именно, для 3-неприводимых параллелоэдров доказывается гипотеза Вороного.

Параллелоэдр P размерности d называется 3-неприводимым, если веер каждой его (d 3)-грани отвечает одному из типов a), b) или c) рис. 1.3.

При этом заметим, что параллелоэдр (d 2)-примитивен (является параллелоэдром Житомирского) тогда и только тогда, когда веер каждой его (d 3)-грани отвечает одному из типов a) или b).

Наиболее сложная часть доказательства гипотеза Вороного для 3неприводимых параллелоэдров заключается в анализе локальной структуры разбиения T (P ) в (d 4)-гранях.

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

В работе [7] В. П. Гришухин доказал гипотезу Вороного для удлинений (d 2)-примитивных параллелоэдров. Эти параллелоэдры, в силу результата Житомирского [40], образуют подкласс класса параллелоэдров Вороного. Там же [7] поставлена задача доказать гипотезу Вороного для всех параллелоэдров вида P +I, где P — параллелоэдр Вороного, а I — отрезок.

Обратное утверждение (гипотеза Вороного для параллелоэдра P следует из гипотезы Вороного для параллелоэдра P + I) доказано в [37, Теорема 3.17].

Н. П. Долбилин [9] ввел понятие стандартной грани параллелоэдра.

Пусть P и P = P +t — ячейки разбиения T (P ), при этом P P =. Тогда грань E = P P назовем стандартной гранью параллелоэдра P. Грань E имеет центр симметрии в точке t/2 (по-прежнему мы предполагаем, что c(P ) = 0; см. также [28]). Вектор t назовем стандартным вектором грани E.

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

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

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

Соответственно, для различения двух типов (d 2)-граней мы будем применять термины стандартные и примитивные.

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

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

• В любой (d k)-мерной грани разбиения T (P ) сходится не более, чем 2k ячеек разбиения. При любых целых d 1, k 0, d k эта оценка Этот результат развивает локальную теорию параллелоэдров — часть теории параллелоэдров, изучающую локальные свойства разбиения. Для параллелоэдров Вороного вопросы локальной теории сводятся к изучению решетчатых многогранников Делоне. Однако для параллелоэдров общего вида (к которым относится рассматриваемый результат диссертации) задача значительно труднее. Для граней коразмерности 3 классификация локальных структур нетривиальна (ее решение — это теорема Делоне). Для граней коразмерности 4 и более полная классификация вееров на текущий момент неизвестна (частичное продвижение для (d 4)-граней, далекое от окончательного ответа, сделано в [35]).

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

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

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

Это утверждение (Теорема 4.2 настоящей диссертации) непосредственно обобщает следующий факт, известный автору как фольклорный.

Предложение. (См., напрмер, [7, Предложение 4].) Пусть P — параллелоэдр Вороного в Rd. Предположим, что в Rd существуют два таких дополнительных друг к другу подпространства и ( = 0, = Rd ), что всякий фасетный вектор параллелоэдра P принадлежит либо подпространству, либо подпространству. Тогда P приводим.

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

Однако еще более обобщить Теорему 4.2 — на случай произвольного параллелоэдра P (не обязательно параллелоэдра Вороного) — пока не удалось.

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

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

1.5. План диссертации Последующие главы устроены следующим образом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЛОКАЛЬНАЯ СТРУКТУРА РАЗБИЕНИЯ НА ПАРАЛЛЕЛОЭДРЫ

2.1. Определения и основные результаты главы Пусть E — произвольная грань разбиения T (P ). Определим дуальную клетку D(E) как множество всех центров параллелоэдров T (P ), содержащих E. Это определение было использовано, например, А. Ординым [35].

Следуя [15, §17.3], можно определить звездное разбиение кусочно-линейного многообразия M по данному локально конечному полиэдральному разбиению грань-в-грань TM этого многообразия. А именно, рассмотрим сначала разбиение TM, являющееся барицентрическим подразделением TM.

Затем для каждой грани E TM определим (замкнутую) клетку E как объединение всех симплексов разбиения TM, содержащих барицентр грани E, но не содержащих барицентров никаких ее подграней. Обозначим это разбиение TM.

В случае M = Rd и TM = T (P ) обозначим соответствующее звездное разбиение через T (P ). Легко видеть, что для k-мерной грани E разбиения T (P ) клетка E гомеоморфна (d k)-мерному диску. Кроме того, биекция, сопоставляющая каждой дуальной клетке D(E) диск E, сохраняет отношение включения. Таким образом, изучение комбинаторики T (P ) можно свести к изучению комбинаторики T (P ), а комбинаторику T (P ), в свою очередь, к отношению частичного порядка, соответствующего включению дуальных клеток D(E1 ) D(E2 ), где E1, E2 — грани разбиения T (P ).

Веер Fan(E) комбинаторно двойственен дуальной клетке D(E), поскольку существует биекция между гранями веера Fan(E) и подклетками дуальной клетки D(E), обращающая отношение включения.

В 1929 году Б. Н. Делоне [19] доказал теорему, которая может быть сформулирована следующим образом в терминах диссертации.

Теорема 2.1. Пусть P — параллелоэдр размерности d, E P — его (d 3)-мерная грань. Тогда комбинаторика клетки D(E), т.е. множество всех дуальных клеток, являющихся подклетками D(E), с частичным порядком включения изоморфно решетке граней одного из пяти трехмерных многогранников: тетраэдра, октаэдра, четырехугольной пирамиды, треугольной призмы или параллелепипеда. Или, эквивалентно, веер любой (d3)-мерной грани комбинаторно эквивалентен одному из изображенных на рис. 1.3 (стр. 11).

Замечание. Значение теоремы 2.1 объясняется ее использованием во многих известных доказательствах частных случаев гипотезы Вороного. В качестве примеров приведем [19, 35, 40].

Мы приведем комбинаторное доказательство теоремы 2.1 с использованием понятия тесного полиэдрального веера. Дадим его определение.

Пусть C — полный k-мерный полиэдральный веер в Rk. Рассмотрим его произвольную грань C C и положим dim C = k m.

Можно определить веер C так же, как и веер грани в разбиении пространства на параллелоэдры. А именно, пусть L — m-мерная аффинная плоскость в Rk, трансверсально пересекающая C. В некоторой достаточно малой окрестности C L сечение веера C плоскостью L совпадает с некоторым полным m-мерным полиэдральным веером, который мы и назовем веером грани C.

Грань C C (представляющая собой полиэдральный конус) называется стандартной, если ее веер обладает центральной симметрией. В дальнейшем будет продемонстрирована связь между стандартными гранями полиэдральных конусов и стандартными гранями разбиения T (P ), определенными в Главе 1.

Пусть C — стандартный конус полного полиэдрального веера C. Будем говорить, что конусы C1, C2 C, такие что C C1 и C C2 симметричны относительно C, если центральная симметрия в точке C L локально меняет местами L-сечения C1 и C2.

Очевидно, что для любого стандартного конуса C C все конусы C C, для которых C C, распадаются на пары симметричных относительно C.

Назовем k-мерный полный полиэдральный веер C тесным, если для любых двух различных k-мерных конусов C1, C2 C конус C = C1 C является стандартным и, кроме того, C1 и C2 симметричны относительно В этой главе мы покажем, что веер любой грани разбиения T (P ) является тесным, а затем будет дана полная комбинаторная классификация тесных полиэдральных вееров. Будет доказана следующая теорема.

Теорема 2.2. Любой трехмерный тесный полиэдральный веер принадлежит одному из пяти комбинаторных типов, изображенных на рис. 1.3.

Далее, для любой (d 3)-мерной грани E разбиения мы доказываем, что комбинаторика D(E) как дуальной клетки совпадает с комбинаторным строением многогранника conv D(E). В частности, это подразумевает, что аффинная размерность точечного множества D(E) равна трем.

Затем будут исследованы два способа сопоставления грани E некоторой решетки. Первый способ — это взятие минимальной подрешетки (P ), содержащей D(E). В результате получается трехмерная решетка, обозначаемая (E). Второй способ — рассмотреть решетку Очевидно, (E) a (E). На самом деле, мы докажем, что данные решетки совпадают. Другими словами, индекс равен единице.

Автору неизвестно, имеют ли место аналогичные результаты для (d4)мерных граней. Для (d 5)-мерных граней теорема о совпадении решеток неверна, поскольку 5-мерный симплекс индекса 2 может быть даже клеткой Делоне для некоторой решетки (см., напр., [23]).

Наконец, будут рассмотрены грани разбиения T (P ) произвольной коразмерности. Основным результатом является следующая теорема.

Теорема 2.3. Пусть E — грань размерности (d k) разбиения T (P ).

Тогда веер Fan(E) состоит не более чем из 2k конусов размерности k (т.е. конусов максимальной размерности).

Отметим, что в случае параллелоэдров Вороного утверждение Теоремы 2.3 хорошо известно, но все известные доказательства (например, [20, Proposition 13.2.8]) существенно опираются на равенство dim a D(E) = k.

Вообще, Теорема 2.3 является следствием гипотезы о размерности. С другой стороны, из нее немедленно следует неравенство более слабое, чем гипотеза о размерности.

Также выделим одно следствие Теоремы 2.3.

Следствие 2.4. Пусть k N. Тогда существует такой конечный набор полных k-мерных полиэдральных вееров что для любого d, любого d-параллелоэдра P и любой (d k)-мерной грани E разбиения T (P ) веер грани E комбинаторно изоморфен некоторому Cik.

Вывод Следствия 2.4 из Теоремы 2.3. Существует лишь конечное число комбинаторных типов полных k-мерных полиэдральных вееров, разбивающих Rk не более, чем на 2k полиэдральных конусов размерности k. По Теореме 2.3, веер грани E обязан принадлежать одному из этих комбинаторных типов.

2.2. Локальная структура граней разбиения, имеющих коразмерность три Напомним, что тесным мы называем такой полный полиэдральный веер C, что для любых двух различных конусов полной размерности C1, C2 C конус C1 C2 стандартный, и при этом C1 и C2 симметричны относительно C1 C2.

Начнем с установления взаимосвязи между схождением ячеек T (P ) в гранях разбиения и тесными веерами.

Предложение 2.5. Веер любой грани разбиения T (P ) является тесным.

Доказательство. Пусть Fan(E) — веер грани E разбиения T (P ). Через L будем обозначать плоскость – носитель веера Fan(F ).

Пусть C1, C2 Fan(E) — два конуса размерности dim L = d dim E.

Тогда существуют два таких параллелоэдра P1, P2 T (P ), что Pi L Ci (i = 1, 2).

Согласно основной теореме о стандартных гранях [9, 28], для любых двух различных d-мерных ячеек P1 и P2 разбиения T (P ), имеющих непустое пересечение, G = P1 P2 — грань разбиения T (P ) с центром симметрии в точке 1 (c(P1 ) + c(P2 )).

В нашем случае P1 P2 =, поскольку E P1 P2. Следовательно, симметрия с центром 1 (c(P1 ) + c(P2 )) меняет параллелоэдры P1 и P2 местами, переводит разбиение T (P ) в себя и оставляет на месте грань G = P1 P2.

Поэтому грань C1 C2, соответствующая в конусе Fan(F ) грани G разбиения T (P ), является стандартной в Fan(F ). По той же причине конусы C и C2 симметричны относительно C1 C2.

Для доказательства Теоремы 2.1 мы классифицируем все тесные трехмерные вееры. Иначе говоря, сначала докажем Теорему 2.2. Предваряя классификацию, отметим некоторые важные свойства тесных трехмерных вееров.

Предложение 2.6 (Свойства тесных трехмерных вееров). Пусть C — тесный трехмерный веер. Тогда 1. Любой луч R C содержится в трех или четырех двумерных гранях C (имеет степень 3 или 4).

2. Для любых двух трехмерных конусов C1, C2 C выполнено ровно одно из следующих утверждений:

(i) C1 C2 — двумерный конус;

(iii) C симметричен относительно вершины, центральная симметрия C меняет местами C1 и C2, а пересечение C1 C2 есть в Доказательство. Легко видеть, что веер любой грани тесного веера тесен.

Рассмотрим луч R C. Веер, соответствующий R, двумерен. Но легко видеть, что тесный двумерный веер может иметь только 3 или 4 двумерных конуса. Таким образом, пункт 1 доказан.

Для доказательства пункта 2 рассмотрим пересечение C = C1 C2. Если dim C = 2, то выполняется (i). Если dim C = 0, то выполяется (iii) в силу определения тесного веера. Наконец, если dim C = 1, то C — стандартный луч C. Поэтому C имеет четную степень, таким образом, единственно возможная степень C — 4. Соответственно, выполнено (ii).

Замечание. Заметим, что пункт 1 Предложения 2.6 дает условие Минковского–Венкова о поясках.

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

Предположим, что трехмерный тесный веер C несимметричен, т.е. его вершина не является стандартной гранью. В этом случае утверждение 2.(iii) предложения 2.6 не выполняется ни для какой пары различных трехмерных конусов C1, C2 C.

Пусть a3 число лучей C, имеющих степень 3, a4 — число лучей степени 4, b — число двумерных и c — число трехмерных граней C.

Поскольку любая двумерная грань C имеет 2 подграни-луча, Далее, рассмотрим единичную сферу S 2 с центром в вершине C. Для любой грани C C ненулевой размерности пересечение C S 2 является диском размерности dim C 1. Совокупность относительных внутренностей всех таких дисков является представлением S 2 в виде CW-комплекса.

Эйлерова характеристика (см., напр., [15, § 13.5, упражнение 8]) такого комплекса равна двум. Поэтому Наконец, пересечение любых двух трехмерных конусов удовлетворяет одному из описаний в пункте 2 Предложения 2.6, следовательно Исключением a4 и b из системы уравнений (2.1), (2.2) и (2.3), получаем Из неравенств вытекает, что c = 4, 5 или 6. Используя (2.1) – (2.3), находим Перечисляя комбинаторные типы полных трехмерных полиэдральных вееров не более чем с шестью лучами, находим всевозможные комбинаторые типы несимметричных тесных вееров. А именно, получаем типы a), c) и d) на рис. 1.3.

Для симметричного трехмерного веера (т.е. такого, что его вершина является стандартной гранью) пусть a3, a4, b, c также обозначают число лучей степени 3, лучей степени 4, граней и трехмерных конусов соответственно. Тогда равенства (2.1) и (2.2) выполняются в силу тех же причин, что и ранее. Вместо равенства (2.3) имеет место где новое слагаемое соответствует парам трехмерных конусов C, пересекающимся по вершине (описанным в пункте 2.(iii) предложения 2.6).

Как и ранее, мы исключаем a4 and b из системы уравнений (2.1), (2.2) и (2.3 ). В результате получаем Число c трехмерных граней симметричного трехмерного полиэдрального веера четно и не меньше 6. Следовательно, неравенство влечет c = 6 или c = 8. Таким образом, Перечисляя все возможные комбинаторные типы трехмерных симметричных полных полиэдральных вееров с шестью и восемью лучами, получаем, что лишь два комбинаторных типа отвечают тесным веерам. Эти типы показаны на рис. 1.3, b) и e).

Выведем теперь Теорему 2.1.

Доказательство Теоремы 2.1. Из Теоремы 2.2 и Предложения 2.5 следует, что ни один веер, отличный от вееров рис. 1.3, a) – e), не может быть веером (d 3)-мерной грани. С другой стороны, все вееры a) – e) реализуются уже для трехмерных параллелоэдров.

2.3. Свойства граней параллелоэдров коразмерности три Пусть E — грань T (P ). Предположим, что выполняются следующие условия.

1. Для любой дуальной клетки D(G), являющейся подклеткой дуальной клетки D(E), многогранник conv D(G) — грань conv D(F ).

2. Обратно, множество вершин любой грани многогранника conv D(E) является подклеткой дуальной клетки D(F ).

В этом случае будем говорить, что D(E) удовлетворяет условиям двойственности.

В этом разделе мы получим следующий результат.

Теорема 2.7. Дуальная клетка любой (d 3)-мерной грани E разбиения T (P ) удовлетворяет условиям двойственности.

Доказательство. Покажем сначала, что Предположим, наоборот, что dim a D(E) 2. Тогда, очевидно, где G — произвольная (d 2)-мерная грань разбиения T (P ), содержащая Пусть, как оговорено ранее, projG обозначает проекцию вдоль грани G на дополнительную двумерную плоскость. Известно [19, 34], что множество есть разбиение плоскости на шестиугольники в случае если грань G примитивна, или на параллелограммы, если грань G стандартна.

В случаях a) – d) на рис. 1.3 веер Fan(E) содержит примитивную (d 2)-мерную грань G. Тогда из рассмотрения проекции projG следует, что множество не содержит ни одного подмножества из 4 параллелоэдров, имеющих общую точку. С другой стороны, хотя бы 4 параллелоэдра содержат грань E, противоречие.

В случае e) на рис. 1.3 пусть G — произвольная (d 2)-мерная грань разбиения T (P ), содержащая грань E. Из рассмотрения проекции projG следует, что множество не содержит ни одного подмножества из 5 параллелоэдров, имеющих общую точку. Но ровно 8 параллелоэдров содержат грань E, противоречие.

Итак, неравенство (2.4) доказано.

Пусть теперь E E — стандартная грань T (P ) и Pmi T (P ) при i = 1, 2, 3, 4. Предположим, что Тогда поскольку обе части равенства равны 2c(E ).

Пусть D(F ) = {x0, x1,..., xn }, где xm = c(Pm ). Тогда любое равенство вида (2.5) влечет векторное соотношение Рассматривая отдельно каждый из случаев a) – e) на рис. 1.3, запишем всевозможные соотношения вида (2.6). Решая данную систему, в каждом случае получаем, что существуют 3 таких вектора e1, e2, e3, что каждый из векторов (xm x0 ) (m = 0, 1,..., n) есть линейная комбинация e1, e и e3 с действительными коэффициентами. Поэтому conv D(E) есть образ конкретного трехмерного многогранника D при некотором линейном отображении (хотя для каждого из случаев a) – e) этот многогранник свой).

Неравенство (2.4) показывает, что это отображение невырождено, поэтому многогранник conv D(E) аффинно (следовательно, и комбинаторно) эквивалентен D. Но соотношения (2.6) дают следующие комбинаторные типы D в случаях a) – e): тетраэдр, октаэдр, четырехугольная пирамида, треугольная призма и параллелепипед соответственно. Также легко видеть, что и условия двойственности для D выполняются.

В Параграфе 2.1 были введены два способа построения решетки по грани E разбиения T (P ). Соответствующие решетки были обозначены через (E) и a (E). Мы покажем, что в случае dim E = d 3 оба способа дают на самом деле одну и ту же решетку.

Теорема 2.8. Для любой (d 3)-мерной грани E разбиения T (P ) выполняется Доказательство. Выберем точку x rel int E и зафиксируем параллелоэдр P0 T (P ), содержащий грань E. Рассмотрим произвольный параллелоэдр P1 разбиения T (P ), содержащий грань E (возможно, совпадающий с P0 ). Точка x принадлежит P1, поэтому Таким образом, если P0, P1,..., Pn — это все параллелоэдры T (P ), содержащие грань E, тогда Следовательно, для любого P T (P ) Рассматривая лишь параллелоэдры P со свойством c(P ) a (E), заключаем, что семейство образует упаковку.

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

Из сказанного следует неравенство где в левой части стоит объем трехмерного множества, а в правой — фундаментальный объем решетки.

Разделив обе части неравенства (2.7) на V ((F )) и рассмотрев обратные величины, получаем В случаях b) – e) на рис. 1.3 правая часть последнего неравенства меньше 2, следовательно (a (E) : (E)) = 1. В случае a) то же рассуждение дает (a (E) : (E)) 2.

Пусть теперь conv D(E) — тетраэдр и (a (E) : (E)) = 2. Последнее равенство означает, что где t — вектор решетки (E). Если (t1 t2 )/2 — вектор решетки (E), то решетки совпадают. Таким образом, при фиксированном D(E) решетка (E) также фиксирована, и для a (F ) существует 7 возможностей.

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

Из полученного противоречия следует, что и в случае a) на рис. 1. выполняется (a (E) : (E)) = 1.

2.4. Верхняя оценка степени грани разбиения данной коразмерности В данном параграфе приводится доказательство Теоремы 2.3. Мы разобьем доказательство на отдельные леммы. Сначала мы изучим множество всех граней параллелоэдра P, эквивалентных данной грани E с точностью до параллельного переноса, сохраняющего решетку (P ). Далее, по такому множеству граней при помощи проекции мы построим множество точек в Rk, обладающее свойством антиподальности, аналогичным введенному Данцером и Грюнбаумом в [17]. И, наконец, мы модифицируем доказательство Данцера и Грюнбаума для получения оценки мощности антиподального множества.

Для единообразия обозначений положим E1 = E. Выберем параллелоэдр P0 T (P ), для которого E1 P0. Пусть {E1, E2,..., Em } — множество всех граней P0, эквивалентных грани E1 с точностью до параллельного переноса, сохраняющего решетку (P ).

Для каждой пары i, j {1, 2,..., m} определим параллельный перенос tij и параллелоэдр Pij при помощи формул Легко видеть, что Pij T (P ).

Лемма 2.9. Грань E1 содержится ровно в m параллелоэдрах разбиения T (P ).

Доказательство. Поскольку Ei P0, имеем Следовательно, в грани E1 сходятся как минимум m параллелоэдров разбиения T (P ), поскольку все параллелоэдры попарно различны.

Пусть существует параллелоэдр P T (P ), отличный от перечисленных и такой, что E1 P. Рассмотрим такой параллельный перенос t, что P = P0 + t. Легко видеть, что t = ti1, таким образом, t = t1i при любом Следовательно, E — грань параллелоэдра P0, эквивалентная грани E1 с точностью до параллельного переноса, сохраняющего решетку (P ). Значит E = Ei для некоторого i {2, 3,..., m}.

По определению t1i, имеем Следовательно t = t1i, противоречие. Таким образом, в грани E1 сходятся в точности m параллелоэдров разбиения T (P ), а именно Конечное множество W Rk назовем антиподальным, если для любой пары различных точек x, y W найдется такая пара несовпадающих параллельных гиперплоскостей, (т.е. плоскостей размерности k1), что x, y и все точки множества W заключены (нестрого) между и Через projE1 будем обозначать проекцию вдоль аффинной оболочки a E1 на дополнительное пространство (a F1 )compl = Rk.

Лемма 2.10. Пусть wi = projE1 (Ei ). Тогда множество антиподально в Rk.

Доказательство. По определению антиподального множества, нам надо показать, что для любой пары i, j, 1 i < j m в Rk найдется такая пара параллельных гиперплоскостей ij и ji, что и множество W заключено между этими гиперплоскостями.

В Rd возьмем гиперплоскость (плоскость размерности d 1) ij так, чтобы параллелоэдры P0 и Pji находились в разных полупространствах относительно ij. Поскольку Ej P0, имеем и, следовательно, Ei P0 Pji ij. Действительно, гиперплоскость ij разделяет 2 параллелоэдра с непустым пересечением, поэтому она должна содержать общую грань P0 Pji. Далее, ij P0 = и ij Pji =, а поэтому гиперплоскость ij является опорной гиперплоскостью и для P0, и для Pji.

Положим по определению ji = ij tji. Гиперплоскость ij является опорной для Pji, значит, гиперплоскость ij будет опорной для Pji tji = P0.

Кроме того, поскольку Ei ij, имеем Таким образом, гиперплоскости ij и ji параллельны и удовлетворяют условиям Теперь положим Поскольку параллелоэдр P0 заключен между ij и ji, множество W заключено между ij и ji. Гиперплоскости ij и ji различны в силу того, что точка projE1 (c(P0 )) лежит строго между ними. Следовательно, для любой пары точек wi, wj W мы построили требуемую пару гиперплоскостей.

При доказательстве следующей леммы мы, по существу, воспроизводим рассуждение Данцера и Грюнбаума [17]. Однако в [17] рассматриваются лишь конечные подмножества Rk полной размерности, т.е. удовлетворяющие условию dim a W = k. Мы применяем технику Данцера и Грюнбаума к множествам, удовлетворяющим модифицированному определению антиподальности.

Лемма 2.11. Пусть W = {w1, w2,..., wm } Rk — антиподальное множество. Тогда m 2k.

Доказательство. Возьмем произвольное число a (0, 1 ). Через Hx будем обозначать гомотетию с центром в точке x и коэффициентом a.

Пусть ij — гиперплоскость в Rk, параллельная гиперплоскостям ij and ji и равноудаленная от этих гиперплоскостей. Множества Hwi (conv W ) и Hwj (conv W ) лежат в разных открытых полупространствах относительно ij, поэтому Если через k обозначить аффинную размерность W, то k k. Далее, пусть Vk обозначает k -мерный объем. Тогда В самом деле, (2.9) следует из (2.8) и того факта, что Hwi (conv W ) conv W.

Далее, поскольку Vk (conv W ) > 0, из неравенства (2.9) следует Но неравенство (2.10) выполняется для любого 0 < a < 2, поэтому в предельном случае a = оно также верно, т.е.

Доказательство Теоремы 2.3. По Лемме 2.9, число параллелоэдров разбиения T (P ), содержащих грань E1, совпадает с мощностью множества граней параллелоэдра P0 T (P ) таких, что параллельный перенос, совмещающий Ei и Ej, сохраняет решетку (P ).

Согласно Лемме 2.10, множество является антиподальным.

Наконец, по Лемме 2.11, m 2k, где k = d dim E1.

УДЛИНЕНИЯ ПАРАЛЛЕЛОЭДРОВ

3.1. Параллелоэдры, свободные вдоль векторов В работе [4] Б. А. Венков определил параллелоэдры положительной толщины в направлении выбранного линейного подпространства. Параллелоэдр P имеет положительную толщину вдоль линейного подпространства размерности k, если для любой k-мерной аффинной плоскости пересечение P либо пусто, либо является k-мерным выпуклым многогранником.

Приведем основной результат Венкова [4] о параллелоэдрах положительной толщины.

Теорема 3.1. Пусть P — d-мерный параллелоэдр, имеющий положительную толщину вдоль d -мерной плоскости. Пусть F1, F2,..., Fk — все гиперграни параллелоэдра P, параллельные. Пусть, наконец, si = s(Fi ) обозначает фасетный вектор гиперграни Fi. Через proj обозначим проекцию вдоль на дополнительное подпространство. Тогда 1. proj является биекцией линейной оболочки s1, s2,..., sk и подпространства. В частности, 2. Семейство многогранников есть разбиение грань-в-грань плоскости на параллелоэдры.

Каждая ячейка этого разбиения есть транслят многогранника В данной главе будет изучен случай k = 1, т.е. параллелоэдров положительной толщины вдоль прямой. Как показал В. П. Гришухин [6], для всякого параллелоэдр P, имеющего положительную толщину вдоль прямой, верно одно из следующих двух утверждений.

1. P = P I, где I — отрезок, I. Иными словами, P — призма с образующей, параллельной прямой.

2. P = P + I, где I — отрезок, I, а параллелоэдр P не является параллелоэдром положительной толщины вдоль.

Если же для некоторого отрезка I Rd d-многогранники P и P + I — параллелоэдры, то параллелоэдр P + I имеет положительную толщину вдоль прямой, где I.

Для описания комбинаторики многогранника P + I воспользуемся следующим предложением.

Предложение 3.2. Пусть E — грань многогранника P + I, где P — произвольный выпуклый многогранник (не обязательно параллелоэдр).

Пусть I = [x, x] — отрезок. Тогда имеет место один из следующих взаимоисключающих пунктов.

1a. (E + x) (P + I) =. Тогда существует такая единственная грань E P, что E = E + x. При этом для любого > 0 выполняется 1b. (E x) (P + I) =. Тогда существует такая единственная грань E P, что E = E x. При этом для любого > 0 выполняется 2. E I, и для произвольной гиперплоскости, опорной для P + I и такой, что (P + I) = E, и гиперплоскости, опорной для P и оставляющей P с той же стороны, выполняется dim(P ) = dim E. Тогда существует такая единственная грань E P, что 3. E I, и для произвольной гиперплоскости, опорной для P + I и такой, что (P + I) = E, и гиперплоскости, опорной для P и оставляющей P с той же стороны, выполняется dim(P ) = dim E 1. Тогда существует такая единственная грань E P, Замечание. В обозначениях Предложения 3.2 назовем грань E предшествующей грани E. Заметим, что если для грани E P выполняются свойства, указанные в пункте 1a, 1b, 2 или 3, то E обязательно порождает грань E (P + I) согласно формуле из соответствующего пункта.

Напомним, что параллелоэдр P свободен вдоль вектора x, если многогранник P + [x, x] — параллелоэдр.

Из Предложения 3.2 и последующего замечания следует, что при = условия Минковского–Венкова для многогранника P + [x, x] выполняются тогда и только тогда, когда условия Минковского–Венкова выполняются для многогранник P +[x, x]. Значит, параллелоэдр P свободен вдоль вектора x тогда и только тогда, когда он свободен вдоль вектора x. Поэтому множество векторов, вдоль которых параллелоэдр P свободен, образует центральносимметричный конус.

Пусть P — параллелоэдр, а I — произвольный отрезок. Покажем, что многогранник P + I есть параллелоэдр тогда и только тогда, когда параллелоэдр P свободен вдоль какого-либо ненулевого вектора, параллельного отрезку I. В самом деле, возьмем такой отрезок I = [x, x], что I I. В силу Предложения 3.2 и последующего замечания, условия Минковского– Венкова для многогранника P + I равносильны условиям Минковского– Венкова для многогранника P + I. Следовательно, P + I — параллелоэдр тогда и только тогда, когда P + I — параллелоэдр, т.е. тогда и только тогда, когда параллелоэдр P свободен вдоль вектора x.

3.2. Необходимое и достаточное условие свободы параллелоэдра вдоль вектора В работе [6] В. П. Гришухин сформулировал необходимое и достаточное условие для того, чтобы параллелоэдр был свободен вдоль вектора.

Теорема 3.3. Для данного параллелоэдра P и отрезка I следующие условия эквивалентны.

1. Сумма Минковского P + I есть параллелоэдр.

2. Любой поясок длины 6 параллелоэдра P содержит хотя бы одну пару антиподальных гиперграней, параллельных отрезку I.

М. Дютур заметил, что доказательство, данное в [6], является неполным. Ниже дается полное доказательство Теоремы 3.3.

Доказательство Теоремы 3.3.

1 2. Предположим, что пункт 2 не выполняется. Тогда найдется такая примитивная (d 2)-грань G параллелоэдра P, что поясок длины 6 Belt(G) не содержит гиперграней, параллельных I. Тогда у P + I есть грань G, параллельная G, но при этом projG (P + I) — восьмиугольник. Следовательно G не может задавать пояска длины 4 или 6. Таким образом, для P + I неверно условие Минковского–Венкова о поясках, и пункт 1 неверен.

Импликация 1 2 доказана.

2 1. Пусть выполнен пункт 2. Проверим условия Минковского– Венкова для многогранника P + I. Поскольку P и I имеют центр симметрии, P + I также имеет центр симметрии. Далее, если F — гипергрань многогранника P + I, то в силу Предложения 3.2, имеет место один из трех случаев.

1. F = F1 ± x в предположении, что F1 — гипергрань параллелоэдра P и I = [x, x]. P — параллелоэдр, следовательно его гипергрань F имеет центр симметрии. Поэтому F также имеет центр симметрии.

Рис. 3.1. Невозможность локального разбиения при наличии восьмигранного пояска 2. F = F1 + I в предположении, что F1 — гипергрань параллелоэдра P и F1. Тогда из центральной симметрии гиперграни F1 также следует центральная симметрия F.

3. F = G1 I, где G1 — грань параллелоэдра P размерности d 2. Т.к.

пункт 2 условия Теоремы 3.3 верен по предположению, а также из Предложения 3.2 следует, что G1 не может быть примитивной гранью P. Значит, грань G1 стандартна и поэтому имеет центр симметрии. В силу этого F также имеет центр симметрии.

Остается проверить, что и условие Минковского–Венкова о поясках также выполнено для многогранника P +I. Для этого мы покажем, что вокруг любой (d 2)-грани многогранника P + I существует локальное разбиение грань-в-грань пространства Rd транслятами многогранника P + I. Из этого немедленно будет следовать условие о поясках — действительно, если бы некоторый поясок многогранника P + I состоял бы из 8, 10 или большего четного числа гиперграней, то при последовательном приклеивании транслятов P + I друг к другу вокруг (d 2)-грани G, задающей такой поясок, невозможно было бы приклеить уже третий многогранник без пересечений транслятов друг с другом (см. рис. 3.1).

Итак, пусть G — грань размерности (d 2) многогранника P + I. По Предложению 3.2, вновь имеют место три случая.

1. G = G1 ± x в предположении, что G1 — (d 2)-грань параллелоэдра 2. G = G1 + I в предположении, что G1 — (d 2)-грань параллелоэдра 3. G = E1 I, где G1 — грань параллелоэдра P размерности d 3.

Существование требуемого локального разбиения вокруг G в случаях 1 и 2 немедленно следует из пункта 2 условия Теоремы 3.3. Остается рассмотреть случай 3.

Напомним определение веера грани E1. Рассмотрим сечение разбиения T (P ) трехмерной плоскостью, трансверсальной a E1 и проходящей через некоторую точку y rel int E1. В достаточно малой окрестности точки y это сечение совпадает с трехмерным полным полиэдральным веером, который и называется веером грани E1. До этого выбор плоскости был произвольным, сейчас же, поскольку I трансверсален a E1, мы будем считать, что I. Будем обозначать этот веер Fan(E1 ).

Для фиксированного веера Fan(E1 ), лежащего в трехмерной плоскости, будем называть отрезок I допустимым, если среди любых трех граней веера Fan(E1 ), сходящихся в луче степени 3, отрезок I параллелен хотя бы одной из них. Пункт 2 условия Теоремы 3.3 гарантирует допустимость отрезка I для веера Fan(E1 ), если G = E1 I — (d 2)-грань многогранника P + I.

Из Теоремы 2.1 о классификации схождений в (d 3)-мерных гранях следует, что существует 13 комбинаторно различных типов допустимых отрезков (рис. 3.2).

В восьми случаях a.1), a.2), b.2), c.2), c.3), d.2), d.3), e.3) грань вида E1 I не образуется. В трех случаях c.1), d.1) и e.1) локальное разбиение вокруг грани E1 I состоит из трех транслятов многогранника P + I, поэтому поясок, задаваемый гранью E1 I, состоит из шести гиперграней.

Наконец, в оставшихся двух случаях b.1) и e.2) локальное разбиение вокруг грани E1 I состоит из четырех транслятов многогранника P + I, и поясок, задавыемый гранью E1 I, состоит из четырех гиперграней.

Следовательно, и условие Минковского–Венкова о поясках для P + I также верно. Значит, P + I — параллелоэдр, и импликация 2 1 доказана.

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

AI (P ) = {s(G) : dim G = d 2 и G I является гипергранью P + I}, Теорема 3.4. Пусть I — отрезок, а P и P +I — d-мерные параллелоэдры.

Тогда Кроме того, если projI обозначает проекцию вдоль I на дополнительную гиперплоскость, то многогранник Q = projI (P ) является параллелоэдром и имеет место равенство 3.3. Параллелоэдры, свободные вдоль векторов и гипотеза Вороного Применим методы предыдущего параграфа к изучению вопроса, когда для параллелоэдра вида P +I, где P — параллелоэдр Вороного, а I — отрезок, верна гипотеза Вороного. Если P I — прямая сумма, положительный ответ очевиден, поскольку оба прямых слагаемых — параллелоэдры Вороного. Поэтому далее мы всегда предполагаем, что dim(P + I) = dim P. В этом случае назовем параллелоэдр P + I удлинением параллелоэдра P.

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

Пусть — положительно определенная квадратичная форма в Rd, — произвольная аффинная гиперплоскость. Вектор n назовем нормалью относительно формы к гиперплоскости, если для любых двух точек x, y выполяется Пусть в Rd фиксирована квадратичная форма и d-мерный параллелоэдр P. Предположим, что каждой гиперграни F P сопоставлен вектор s(F ), являющийся нормалью относительно к гиперплоскости a F. Также предположим, что выполнены следующие условия.

1. Для каждой гиперграни F вектор s(F ) — внешняя нормаль грани F 2. s(F ) = s(F ), где F и F — параллельные друг другу грани параллелоэдра P (антиподальные грани).

3. Для любого шестигранного пояска, гиперграни которого занумерованы F1, F2,..., F6 в порядке обхода, верно Тогда отображение s гиперграней в нормали назовем канонической нормировкой параллелоэдра P.

Сформулируем основную теорему о канонической нормировке. Работы Вороного, Житомирского и Ордина, устанавливающие гипотезу Вороного для специальных классов параллелоэдров, используют эту теорему или эквивалентные ей утверждения. Для случая единичной матрицы формулировку и доказательство Теоремы 3.5 можно найти в [21, Theorem 2, 1 3]. Случай произвольной положительно определенной формы сводится к случаю единичной матрицы аффинным преобразованием.

Теорема 3.5. Пусть P — параллелоэдр, а — положительно определенная квадратичная форма в Rd. Тогда следующие условия эквивалентны.

1. P — параллелоэдр Вороного относительно некоторой квадратичной формы, вообще говоря, отличной от.

2. P допускает каноническую нормировку относительно формы.

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

Графом Венкова параллелоэдра P назовем граф GP, если 1. Вершины GP находятся во взаимно-однозначном соответствии с (неупорядоченными) парами антиподальных гиперграней P.

2. Вершина v1, соответствующая паре гиперграней (F1, F1 ), соединена красным ребром с вершиной v2, соответствующей паре гиперграней (F2, F2 ) тогда и только тогда, когда грани F1, F1, F2, F2 входят в один и тот же 6-поясок.

3. Вершина v1, соответствующая паре гиперграней (F1, F1 ), соединена синим ребром с вершиной v2, соответствующей паре гиперграней (F2, F2 ) тогда и только тогда, когда грани F1, F1, F2, F2 образуют 4-поясок.

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

Сформулируем теорему Ордина [35, Theorem 13] о приводимости параллелоэдра.

Теорема 3.6. Параллелоэдр P приводим, т.е. представляется в виде прямой суммы параллелоэдров меньшей размерности P = P1 P2 тогда и только тогда, когда Gr несвязен.

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

Теорема 3.7 ( [7, 35] ). Пусть — положительно определенная квадратичная форма в Rd, P — параллелоэдр Вороного относительно некоторой квадратичной формы, вообще говоря, отличной от. Каноническая нормировка параллелоэдра P относительно формы единственна с точностью до умножения всех нормалей на один и тот же положительный коэффициент тогда и только тогда, когда Gr связен, т.е.

тогда и только тогда, когда P приводим.

Через P (, ) будем обозначать такой параллелоэдр P, что T (P ) есть разбиение Вороного для решетки в евклидовой метрике, заданной положительной квадратичной формой. Напомним также, что обозначение s(E) мы используем для стандартного вектора стандартной грани E параллелоэдра P. Соответственно, если F — гипергрань, то s(F ) — ее фасетный вектор.

Как показал А. Вег [37, Теорема 3.17], для того, чтобы сумма Минковского P + I была параллелоэдром Вороного, необходимо, чтобы и P был параллелоэдром Вороного.

В. П. Гришухиным [7] была сформулирована следующая теорема.

Теорема 3.8. Пусть P = P (, ), и параллелоэдр P свободен вдоль вектора x. Предположим, что xT · · s(G) = 0 для всякой (d 2)-грани G такой, что Тогда P + [x, x] — параллелоэдр Вороного. Если же P неприводим, то условие (3.2) необходимо для того, чтобы параллелоэдр P + [x, x] был параллелоэдром Вороного.

В доказательстве из [7] также имеются нерассмотренные случаи, указанные М. Дютуром. Поэтому мы приведем и доказательство Теоремы 3.8.

Доказательство Теоремы 3.8.

Пусть выполнено условие (3.2). Построим каноническую нормировку на (P + I), где I = [x, x]. Нормали к гиперграням параллелоэдра P + I будем при этом определять относительно метрики, заданной формой.

В доказательстве Теоремы 3.3 были перечислены 3 типа гиперграней параллелоэдра P + I.

1. F = F1 ± x, где F1 — гипергрань параллелоэдра P.

2. F = F1 + I, где F1 — гипергрань параллелоэдра P и I F1.

3. F = G1 I, где G1 — грань параллелоэдра P размерности d 2. При этом грань G1 стандартна.

s(F ) = s(G1 ) соответственно.

Легко проверить, что значения функция s на антиподальных гранях параллелоэдра P + I совпадают. Поэтому остается проверить только условие (3.1) для примитивных (d 2)-граней параллелоэдра P + I.

Любая примитивная (d 2)-грань G параллелоэдра P + I образована одним из следующих способов.

1. G = G1 ± x, где G1 — примитивная (d 2)-грань параллелоэдра P.

2. G = G1 ± x, где G1 — стандартная (d 2)-грань параллелоэдра P.

3. G = G1 + I, где G1 — примитивная (d 2)-грань параллелоэдра P и 4. G = E1 I, где G1 — грань параллелоэдра P размерности d 3, и имеет место одна из ситуаций c.1), d.1) и e.1) рисунка 3.2.

Несложно показать, что в каждом из случаев 1 – 4 условие (3.1) действительно выполняется. При этом в случае 4 используется аффинная структура дуальной клетки D(E1 ), установленная Теоремой 2.7.

Теперь предположим, что параллелоэдр P неприводим, а P + I — параллелоэдр Вороного. Тогда существует канонические нормировки sP и sP +I параллелоэдров P и P + I соответственно.

По Теореме 3.7, каноническая нормировка параллелоэдра P восстанавливается однозначно с точностью до умножения на положительный коэффициент. Но в том же порядке можно восстановить и нормировку тех гиперграней параллелоэдра P + I, которые получены способами 1 и 2. При этом sP +I (F ) = sP (F1 ) где либо F = F1 + I, либо F = F1 ± x.

Теперь рассмотрим гипергрань F параллелоэдра P + I вида G I. Тогда G + x — примитивная (d 2)-грань параллелоэдра P + I. Грань G содержится ровно в двух гипергранях параллелоэдра P, пусть F1 и F1. Тогда, не умаляя общности, F = F1 + x и F = F1 x — грани параллелоэдра P + I. Вследствие правила (3.1) имеем sP +I (F )n(F ) = sP +I (F )n(F ) + sP +I (F )n(F ) = s(F1 ) + s(F1 ) = s(G).

Таким образом, n(F ) s(G). Т.е. для любого вектора y a F выполняется yT · · s(G) = 0. Но I F, следовательно, x a F, откуда и следует xT · · s(G) = 0.

Приведем важное следствие Теоремы 3.8. Отметим, правда, что А. Вег в своей диссертации привел аналогичное утверждение без доказательства (см. [37, Теорема 3.18]).

Следствие 3.9. Пусть I — такой отрезок, что P и P +I — параллелоэдры, кроме того, пусть P — параллелоэдр Вороного. Если имеет место равенство то гипотеза Вороного верна и для параллелоэдра P + I.

Доказательство. Пусть P = P (, ). Всюду в доказательстве термин ортогональность относится к евклидовой метрике, заданной квадратичной формой.

Равенство (3.3) и Теорема 3.4 гарантируют включение Далее, по определению, BI (P ) — множество фасетных векторов всех гиперграней параллелоэдра P, параллельных I. Поскольку P — параллелоэдр Вороного, отрезок I ортогонален каждому вектору множества BI (P ).

Следовательно, отрезок I ортогонален и линейной оболочке BI (P ). Это, в частности, значит, что отрезок I ортогонален и любому вектору множества AI (P ). Отсюда, по Теореме 3.8, P + I — параллелоэдр Вороного.

Приведем результат из [7] о редукции гипотезы Вороного для удлинения приводимого параллелоэдра P = P1 P2 к гипотезе Вороного для удлинений каждого из параллелоэдров P1 и P2.

Теорема 3.10. Пусть I — такой отрезок, что P и P + I — параллелоэдры. Предположим, что P — приводимый параллелоэдр Вороного, т.е.

раскладывается в прямую сумму вида P = P1 P2. По определению положим считая, что projP2 — это проекция вдоль a P2 на плоскость a P1 и аналогично для projP1. Тогда 1. P1 + I1 и P2 + I2 — параллелоэдры.

2. Гипотеза Вороного верна для параллелоэдра P + I тогда и только тогда, когда она выполняется для параллелоэдров P1 + I1 и P2 + I одновременно.

По Теореме 3.1, если параллелоэдр P свободен вдоль вектора x, то проекция proj x P — параллелоэдр. Нас будет интересовать вопрос — верно ли, что указанная проекция является параллелоэдром Вороного. Ответ будет положительным при одном дополнительном условии — гипотеза Вороного верна для параллелоэдра P + [x, x].

Лемма 3.11. Пусть I — отрезок, P и P + I — d-параллелоэдры, при этом P + I — параллелоэдр Вороного. Тогда при любом выборе гиперплоскости = projI (Rd ) многогранник projI (P ) — параллелоэдр Вороного относительно некоторой евклидовой метрики в плоскости.

Доказательство. Достаточно доказать Лемму 3.11 для какого-то конкретного выбора, поскольку смена пространства – образа проекции ведет лишь к аффинному преобразованию этой проекции.

По уже упоминавшемуся результату [37, Теорема 3.17], из условия теоремы следует, что и P — параллелоэдр Вороного.

Пусть = AI (P ) BI (P ). Существует такая квадратичная форма, что P = P (, ) и отрезок I ортогонален плоскости в евклидовой метрике, заданной формой. Действительно, для неприводимого P это мгновенно следует из Теоремы 3.8, а для приводимых — из [7, §9].

Тогда, в силу [7, Предложение 5], 3.4. Послойная конструкция разбиения Главной целью данного параграфа, как и следующего, является нахождение таких свойств параллелоэдров, допускающих удлинение, которые будут использованы для доказательства основных результатов Главы 4. В данном параграфе будет введено и исследовано понятие шапочек. Также будет показано, что для данного параллелоэдра P, свободного вдоль фиксированного вектора x, разбиение T (P ) можно естественным образом разделить на слои.

Отметим, что понятия слоев и шапочек восходят к Б. Н. Делоне и были использованы [19] для нахождения четырехмерных параллелоэдров.

Например, Лемма 3.15 позволяет установить комбинаторику параллелоэдра, зная проекцию одного слоя и взаимное расположение соседних слоев.

Здесь и далее мы будем предполагать, что I — отрезок, а P и P + I — параллелоэдры в пространстве Rd. Не умаляя общности, будем считать, что I = I(x) = [x, x].

Определим шапочку параллелоэдра P, видимую вдоль вектора x как однородный (d 1)-мерный полиэдральный комплекс, максимальные грани которого суть те и только те гиперграни F параллелоэдра P, которые удовлетворяют условию Если I = I(x), то I-шапочкой параллелоэдра P будем называть любую из двух антиподальных шапочек параллелоэдра P — видимую вдоль x и видимую вдоль x. Для каждого отрезка I фиксируем одну из двух I-шапочек и будем обозначать ее через CapI (P ). Для согласованности обозначений будем считать, что если отрезок I рассматривается как I(x), то CapI (P ) — та шапочка, которая видна вдоль вектора x, а не вдоль вектора x.

Для параллелоэдра P, свободного вдоль вектора x и отрезка I = I(x) введем обозначение для семейства фасетных векторов гиперграней шапочки.

CI (P ) = {s(F ) : F — максимальная грань шапочки CapI (P )}.

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

Лемма 3.12. Для всякого параллелоэдра P, свободного вдоль вектора x и отрезка I = I(x) имеет место включение Доказательство. Предположим противное. Пусть тогда F1 и F2 — такие (d 1)–грани шапочки CapI (P ), что Из сказанного в Параграфе 4.1 (или из Теоремы 3.3) следует, что для любого > 0 параллелоэдр P свободен вдоль вектора x. При этом многогранники F1 + x и F2 + x являются гипергранями параллелоэдра P + I и имеют фасетные векторы соответственно Поэтому s(F1 ) s(F2 ) — вектор решетки (P + I), а значит, В силу предположения о векторе s(F1 ) s(F2 ) и Теоремы 3.4, решетка, порожденная векторами множеств AI (P ) и BI (P ) и вектором s(F1 ) s(F2 ), имеет размерность d и не зависит от. Если V — фундаментальный объем такой решетки, то объем параллелоэдра P + I, равный фундаментальному объему решетки (P + I), не превосходит V. Но при объем параллелоэдра P + I становится произвольно большим. Противоречие.

Нам также потребуется утверждение об индексе подрешетки Z(AI (P ) BI (P )) (P ).

Лемма 3.13. Для всякого параллелоэдра P, свободного вдоль вектора x, и отрезка I = I(x) имеет место равенство Доказательство. Положим 0 = (P ) AI (P ) BI (P ).

Пусть равенство (3.4) не выполняется.

Обозначим t = s(F0 ), где F0 — произвольная (d 1)-грань комплекса CapI (P ). В силу Леммы 3.12, для любой гиперграни F параллелоэдра P имеем Через projlin a 0 мы обозначили проекцию вдоль гиперплоскости lin a на прямую R · t.

Множество фасетных векторов параллелоэдра P порождает решетку (P ), поэтому Пусть I = [x, x], eI = 2x. Для произвольного > 0 рассмотрим разбиение T (P + I). Покажем, что Для этого достаточно проверить, что все фасетные векторы параллелоэдра P + I принадлежат множеству В самом деле, каждый такой фасетный вектор принадлежит либо AI (P ), либо BI (P ), либо имеет вид где F — гипергрань параллелоэдра P, а знак выбирается в зависимости от того, какое из двух включений выполнено — F CapI (P ) или F CapI (P ). В первых двух случаях фасетный вектор принадлежит 0, а в третьем — ±(0 + t + eI ) с соответственным выбором знака.

Из Теоремы 3.4 следует, что при любом достаточно большом значении гиперплоскость a 0, за исключением подмножества размерности d 2, будет покрыта внутренностями параллелоэдров Пусть v 0 \ Z(AI (P ) BI (P ). Тогда предыдущее утверждение верно и для внутренностей параллелоэдров Но это невозможно, поскольку T (P + I) — разбиение. Таким образом, вектора v не существует, и поэтому равенство (3.4) выполнено.

Лемма 3.14. Пусть P — параллелоэдр, свободный вдоль вектора x, и I = I(x). Пусть F — такая гипергрань параллелоэдра P, что Тогда I F.

Доказательство. Предположим противное: I F. Тогда, не умаляя общности, имеем s(F ) CI (P ). Отсюда следует, что т.е. пересечение слева непусто. Отсюда, применяя Лемму 3.12, получаем Значит, Но множества векторов BI (P ) и CI (P ) в совокупности порождают dмерную решетку (P ). Противоречие.

Лемма 3.15. Пусть P — параллелоэдр, свободный вдоль вектора x, и I = I(x). Через t обозначим любой вектор, для которого выполняется равенство Наконец, допустим, что v Z(AI (P ) BI (P )). Тогда Доказательство. Из Леммы 3.13 немедленно вытекает, что Не умаляя общности предположим, что в последнем равенстве выбирается знак “+”.

Рассмотрим однородный (d1)-мерный полиэдральный комплекс K, все грани которого являются гранями разбиения T (P ), и носитель которого определяется следующим образом:

где вектор v пробегает все точки решетки Z(AI (P ) BI (P )).

Говоря неформально, K разделяет два слоя параллелоэдров Комплекс K обладает следующими тремя свойствами.

1. Проекция projI в направлении отрезка I на произвольную трансверсальную I гиперплоскость есть гомеоморфизм |K| и.

3. projI (P |K|) = projI (P ) для любого параллелоэдра P такого, что Свойство 1 следует из теоремы А. Д. Александрова о разбиении [1].

Применим эту теорему к полиэдральному комплексу размерности d 1, множество максимальных граней которого есть В качестве отображения комплекса возьмем projI. Чтобы показать, что образ комплекса есть разбиение гиперплоскости, в силу теоремы Александрова достаточно проверить, что для любой (d3)-грани E этого комплекса проекции (d 1)-граней, сходящихся в E, образуют локальное разбиение вокруг projI (E). Но это так, поэтому проекция projI есть гомеоморфизм |K| и.

Отсюда следует, что каждую прямую, параллельную I, комплекс |K| делит на два луча с общим началом, скажем, верхний и нижний относительно некоторого фиксированного выбора направления I. Будем называть объединение нижних (замкнутых) лучей нижней частью, а (также замкнутых) верхних — верхней частью Rd по отношению к комплексу |K|.

Чтобы доказать второе свойство комплекса |K|, заметим, что все параллелоэдры слоя L0 лежат в одной и той же (скажем, нижней) части Rd.

Тогда, соответственно, все параллелоэдры слоя L1 лежат в верхней части.

Поэтому пересечение слоев содержится в пересечении нижней и верхней частей, т.е. в |K|. Но, как следует из определения K, любая точка |K| при этом принадлежит пересечению некоторого параллелоэдра из L0 и некоторого параллелоэдра из L1.

Свойство 3 немедленно следует из определения шапочки и построения комплекса K.

В обозначениях, принятых в условии Леммы 3.15, положим P = P + v + t. Тогда имеем Из свойства 2 комплекса |K| получаем, что По свойству 1 проекция projI является гомеоморфизмом пространства |K|, следовательно, имеют место равенства projI (P P ) = projI (P |K|) (P |K|) = Последнее равенство есть следствие свойства 3.

3.5. Свободные и совершенные свободные пространства Пусть P — параллелоэдр в Rd. Линейное подпространство Rd называется свободным пространством параллелоэдра P, если P свободен вдоль любого вектора x.

Имеется естественный способ построения свободных пространств данного параллелоэдра P. Рассмотрим любой такой набор гиперграней F1, F2,..., Fs параллелоэдра P, что любой поясок P длины 6 содержит хотя бы одну гипергрань Fi из выбранного набора. Тогда подпространство, заданное формулой является свободным для P. Действительно, для любого вектора x выполняется условие Теоремы 3.3.

Свободное подпространство вида (3.6) будем называть совершенным для P.

Лемма 3.16. Пусть P — параллелоэдр. Тогда 1. Любое свободное пространство для P является подпространством некоторого совершенного свободного подпространства для 2. Пусть — совершенное свободное подпространство для P и dim = k. Тогда для любого целого k такого, что 0 k k, существует совершенное свободное подпространство с 3. Пусть — свободное подпространство для P и dim = k. Тогда существует совершенное свободное подпространство с dim = Доказательство. Докажем пункт 1. Пусть 0 — свободное пространство для P. Рассмотрим набор гиперграней F1, F2,..., Fs параллелоэдра P такой, что гипергрань F входит в этот набор тогда и только тогда, когда 0 F.

Существует такой вектор x 0, что F1, F2,..., Fs есть в точности набор всех гиперграней параллелоэдра P, параллельных вектору x. Но поскольку параллелоэдр P свободен вдоль вектора x, то по Теореме 3.3 любой поясок P длины 6 содержит хотя бы одну гипергрань Fi. Это означает, что пространство, удовлетворяющее формуле (3.6), является совершенным свободным, и при этом 0.

Докажем пункт 2. Пусть получено согласно формуле (3.6). Тогда нормали к граням F1, F2,..., Fs порождают подпространство размерности d k. Но нормали ко всем гиперграням параллелоэдра P порождают все Rd. Следовательно, можно взять набор такой, что нормали к гиперграням этого набора порождают подпространство размерности d k. Теперь достаточно положить Пункт 3 немедленно следует из пунктов 1 и 2.

Для предшествующей части данного параграфа не имело значения, является P параллелоэдром Вороного, или нет. Если же P = P (, ), то 1. Параллелоэдр P свободен вдоль вектор x тогда и только тогда, когда из любой тройки фасетных векторов, соответствующих какому-либо пояску длины 6, можно выбрать вектор s(F ) такой, что s(F )T x = 0.

2. Пусть s(F1 ), s(F2 ),..., s(Fs ) — некоторый поднабор множества фасетных векторов параллелоэдра P. Допустим также, что любая тройка фасетных векторов, соответствующих какому-либо пояску длины 6, содержит либо некоторый s(Fi ), либо некоторый s(Fi ). Тогда ортогональное дополнение является совершенным свободным пространством для P. При этом 3.6. Двумерные свободные пространства параллелоэдров Вороного В этом параграфе будет доказан ряд результатов о параллелоэдрах Вороного, имеющих двумерное свободное пространство. В силу пункта Леммы 3.16, каждый такой параллелоэдр имеет и двумерное совершенное пространство. Поэтому мы ограничимся рассмотрением пар (P, ), где — двумерное совершенное свободное подпространство для параллелоэдра P = P (, ).

Все леммы данного параграфа технические, и используются при доказательстве основных результатов Главы 4. Более того, если бы результаты Главы 4 принимались как уже доказанные, то по Теореме 4.4 было бы известно, что все параллелоэдры Вороного, имеющие двумерное свободное пространство, приводимы. (Напомним, что приводимым мы называем параллелоэдр вида P = P1 P2, где P1 и P2 — параллелоэдры меньшей размерности, чем P.) В этом случае все доказательства в этом параграфе допускали бы значительное упрощение.

Всюду в данном параграфе символ обозначает ортогональность относительно квадратичной формы. Введем новые обозначения. Пусть A (P ) = {s(G) : G P — стандартная (d 2)-грань и s(G) }.

По определению совершенного свободного пространства и замечанию в конце Параграфа 4.5 о случае параллелоэдра Вороного, имеем Поэтому подпространство B (P ) есть ортогональное дополнение к. Следовательно, вне зависимости от выбора отрезка I.

Лемма 3.17. Пусть P = P (, ) — параллелоэдр Вороного, а — его двумерная совершенная свободная плоскость. Пусть (т.е. S1 () — единичная окружность в плоскости ).

Рассмотрим отображение, сопоставляющее каждому вектору x S1 () гиперплоскость Тогда точки, в которых данное отображение разрывно — это в точности все единичные относительно формы векторы, параллельные совершенным прямым плоскости.

Доказательство. Заметим, что для любого отрезка I имеет место включение B (P ) BI (P ).

Пусть вектор x S1 () не параллелен никакой совершенной прямой в плоскости. Тогда dim BI(x) (P ) < d 1, а следовательно, Равенство BI(x ) (P ) = B (P ) выполняется и для всех x S1 (), достаточно близких к x. Также, для всех x S1 (), достаточно близких к x, выполнено и равенство Таким образом, при всех x S1 (), достаточно близких к x гиперплоскость AI(x ) (P ) BI(x ) (P ) постоянна и совпадает с гиперплоскостью Пусть теперь вектор x S1 () параллелен некоторой совершенной прямой. Тогда dim BI(x) (P ) = d 1.

Поскольку множество стандартных векторов параллелоэдра P конечно, гиперплоскость AI (P ) BI (P ) при условии, что P + I — параллелоэдр, принадлежит некоторому конечному множеству. Поэтому достаточно доказать, что для любого вектора x S1 (), достаточно близкого к вектору x, но не совпадающего с ним.

Далее, у параллелоэдра P найдется такая гипергрань F, что случае выполнялось бы F, что противоречит (3.8). По Лемме 3.14, Остается заметить, что условие (3.7) немедленно следует из сравнения (3.8) и (3.9).

Лемма 3.18. Пусть P = P (, ) — параллелоэдр Вороного, а — его двумерная совершенная свободная плоскость. Тогда 1. Плоскость содержит ровно две совершенные прямые.

обеим этим прямым (в последнем случае гипергрань параллельна Доказательство. Докажем пункт 1. Пусть вектор x S1 () таков, что dim BI(x) (P ) выбирать любой вектор из S 1 () за исключением лишь конечного числа возможностей.

Пусть G — такая стандартная (d 2)-грань параллелоэдра P, что Грань G содержится ровно в двух гипергранях, которые мы обозначим Кроме того, не умаляя общности, можно считать, что F CapI(x) (P ) и F CapI(x) (P ).

Пусть G — (d 2)-грань параллелоэдра P, определяемая условиями Теперь рассмотрим произвольный вектор x S1 (). Несложно видеть, что где v {s(F ), s(F ), s(G), s(G )}. При этом случаи {s(F ), s(F )} имеют место если и только если x Fиx F соответственно. Следовательно, два случая x F иx F (и, соответственно, две пары противоположных значений вектора x ) — это все точки где изменение плоскости в зависимости от x не является непрерывным. Поэтому, в силу Леммы 3.17, совершенных прямых в плоскости ровно две, а именно:

Выберем такой вектор x S1 (), что x F. Это можно сделать, поскольку dim F + dim = d + 1 > d. Имеем Поэтому вектор x является направляющим для совершенной прямой.

По предположению, x F, т.е. гипергрань F параллельна совершенной прямой.

Изучим возможные случаи взаимного расположения (d 3)-грани параллелоэдра P и трансверсальной ей совершенной свободной плоскости.

Лемма 3.19. Пусть E — (d 3)-грань параллелоэдра Вороного P = P (, ), а — его двумерная совершенная свободная плоскость, и при этом и E трансверсальны. Пусть веер Fan(E) получен сечением разбиения T (P ) трехмерной плоскостью и projE обозначает проекцию вдоль lin a E на. Тогда все возможные случаи взаимного расположения Fan(E), projE () и projE ( i ), где — совершенные прямые в плоскости, показаны на рис. 3.3.

Доказательство. Возможные расположения projE () — это те двумерные Рис. 3.3. Возможные расположения Fan(E), projE () и projE ( i ) мым для Fan(E), т.е. соответствует одному из случаев рис. 3.2. Чтобы выбрать в найденных плоскостях направления для projE ( i ), достаточно воспользоваться Леммой 3.18.

Лемма 3.20. Пусть P = P (, ) — параллелоэдр Вороного, а — его двумерная совершенная свободная плоскость. Пусть, как и в Лемсовершенные прямые, лежащие в плоскости. Пусть 1. Если G — стандартная (d 2)-грань паралелоэдра P и s(G) 2. P + Y1 — параллелоэдр Вороного (не обязательно в метрике ).

4. Многогранник P + Y1 + Y2 + I — параллелоэдр.

Доказательство. Пункт 1 докажем от противного. Пусть s(G) A (P ).

Из доказательства Леммы 3.18 следует, что вектор x S1 () такой, что x есть точка, в окрестности которой гиперплоскость постоянна. С другой стороны, поскольку отрезок Y1 параллелен совершенной прямой, по Лемме 3.17, указанная гиперплоскость в окрестности точки x изменяется скачком. Получено противоречие, поэтому пункт 1 доказан.

Пункт 2 немедленно следует из определения совершенной прямой и Следствия 3.9.

Докажем пункт 3. Чтобы проверить, что — совершенная свободная плоскость параллелоэдра P, покажем, что в любом пояске длины 6 параллелоэдра P + Y1 найдется пара гиперграней, параллельных плоскости.

Рассмотрим три возможных случая.

1. Поясок Belt6 (G ) длины 6 параллелоэдра P + Y1 образовался из пояска Belt6 (G) длины 6 параллелоэдра P. Тогда все гиперграни пояска Belt6 (G ) параллельны соответствующим гиперграням пояска Belt6 (G). Но поскольку — совершенная свободная плоскость, то Belt6 (G) содержит пару гиперграней, параллельных. Значит, и Belt6 (G ) тоже содержит такую пару гиперграней.

2. Поясок Belt6 (G ) длины 6 параллелоэдра P + Y1 образовался из пояска Belt4 (G) длины 4 параллелоэдра P. В частности, поясок Belt6 (G ) содержит гипергрань G Y1. При этом ни одна из гиперграней пояска Belt4 (G) не параллельна отрезку Y1. По пункту 2 Леммы 3.18, все гиперграни пояска Belt4 (G) параллельны прямой 2. Следовательно G 2. Как итог, 3. Поясок Belt6 (G ) длины 6 параллелоэдра P + Y1 таков, что G = E Y1, где E — (d 3)-грань параллелоэдра P. Тогда взаимное расположение E и Y1 отвечает одному из случаев c.1), d.1), e.1) на рис. 3.2. Имеем два подслучая.

3.1. Плоскость не трансверсальна пространству lin a E. Тогда пересечение = p lin a E есть прямая. При этом Y1, поскольку отрезок Y1 трансверсален грани E. Пусть F — произвольная гипергрань пояска Y1. Вследствие этого F 3.2. Плоскость трансверсальна пространству a E. Тогда все возможные расположения прямой указаны в Лемме 3.19. Среди всех случаев рис. 3.3 многогранник E Y1 является гранью параллелоэдра P + Y1 только в случае 2) и при условии, что расположение отрезка Y1 соответствует случаю e.2) на рис 3.2. Но тогда E Y1 задает поясок параллелоэдра P + Y длины 4, а не 6. Поэтому данный подслучай невозможен.

Заметим, что для каждой из прямых и существует параллельная ей гипергрань параллелоэдра P +Y1 такая, что любая другая прямая плоскости для параллелоэдра P + Y1.

Применяя те же рассуждения к параллелоэдру P + Y1, получаем, что P + Y1 + Y2 — параллелоэдр Вороного в некоторой евклидовой метрике, и — его двумерная совершенная свободная плоскость. Но тогда P +Y1 +Y2 +I — параллелоэдр, и пункт 4 доказан.

Лемма 3.21. Пусть P = P (, ) — параллелоэдр Вороного, а — его двумерная совершенная свободная плоскость. Тогда proj (P ) — параллелоэдр Вороного размерности d 2.

Доказательство. Мы покажем, что P, P + Y1 и P + Y1 + Y2 — параллелоэдры Вороного размерности d, projY1 (P ) и projY1 (P + Y2 ) — параллелоэдры Вороного размерности d 1 и, наконец, proj (P ) — параллелоэдр Вороного размерности d 2.

В самом деле, P — параллелоэдр Вороного по условию. Далее, P + Y1 — параллелоэдр Вороного по Лемме 3.20, пункту 2. P + Y1 + Y2 — параллелоэдр Вороного также в силу Леммы 3.20, пункта 2, примененного к P + Y1 и Y2. Возможность такого применения следует из пункта 3 той же Леммы.

Применение Леммы 3.11 к парам (P, Y1 ) и (P +Y1, Y2 ) дает, что projY1 (P ) и projY1 (P + Y2 ) — параллелоэдры Вороного. Наконец, применим Лемму 3.11 еще раз — к параллелоэдру projY1 (P ) и отрезку projY1 (Y2 ). Поскольку проекция параллелоэдра projY1 (P ) вдоль projY1 (Y2 ) и есть proj (P ), Лемма доказана.

Другими словами, Последнее равенство немедленно влечет следуюшую лемму.

Доказательство. В самом деле, В правой части стоит пересечение двух различных гиперплоскостей, параллельных B (P ). Это пересечение может только совпадать с B (P ).

Лемма 3.23. Пусть P = P (, ) — параллелоэдр Вороного, а — его двумерная совершенная свободная плоскость. Пусть отрезок I таков, множества фасетных векторов, и пусть для j = 1, Если Pj = P + tj, то Доказательство. Рассмотрим (d 1)-мерный полиэдральный комплекс K, определенный в Параграфе 4.4. Напомним, что его носитель |K| разделяет два соседних слоя параллелоэдров L0, L1 T (P ), заданные формулами (3.5). Т.к. P L0 и P1, P2 L1, имеем Положим Q = projI (P ). Q — параллелоэдр Вороного, свободный вдоль направления отрезка projI (Y1 ) (или projI (Y2 ) — отрезки projI (Y1 ) и projI (Y2 ) параллельны). Множества образуют 2 слоя (d 1)-мерного разбиения T (Q) в смысле конструкции Параграфа 4.4, в частности, Леммы 3.15. Назовем эти слои M1 - и M2 слоем соответственно.

Слои M1 и M2 являются соседними. В самом деле, выберем стандартную (d 2)-грань G параллелоэдра P, для которой Затем возьмем (d2)-грань G такую, что Belt4 (G) = Belt4 (G ) и rel int G rel int CapI (P ). Нетрудно видеть, что projI (G ) принадлежит общей границе M1 - и M2 -слоев. Следовательно, projprojI (Y1 ) (Q + projI (t1 )) projprojI (Y1 ) (Q + projI (t2 )) = Остается доказать, что Для этого достаточно показать что общая граница M1 - и M2 -слоев разделяет шапочки параллелоэдра Q, видимые вдоль projI (Y1 ). Это, в свою очередь, мы докажем, показав, что каждая шапочка покрыта своим слоем — одна слоем M1, а другая — M2.

Поскольку dim Q = d 1, обе шапочки Q являются однородными (d 2)-мерными комплексами. Каждая из шапочек гомеоморфна (d 2)-диску, т.е. для завершения доказательства достаточно показать, что любые две максимальные грани одной шапочки, имеющие общую (d 3)-грань, лежат в одном слое. При этом общая (d 3)-грань обязана иметь вид projI (E), где E — (d 3)-грань параллелоэдра P и разделять грани шапочки вида projI (G) и projI (G ), где G и G — стандартные (d2)-грани параллелоэдра Плоскость трансверсальна граням G и G, а значит, и их подграни E. Таким образом, выполняется условие Леммы 3.19, и все возможные взаимные расположения E и I указаны на рис. 3.3. В каждом из этих случаев, если projI (E) действительно разделяет две грани одной шапочки параллелоэдра Q, эти грани действительно покрыты одним и тем же слоем — либо M1, либо M

ГИПОТЕЗА ВОРОНОГО ДЛЯ УДЛИНЕНИЙ ПАРАЛЛЕЛОЭДРОВ

ВОРОНОГО

4.1. Основные результаты главы В данной главе будет доказана следующая теорема.

Теорема 4.1. Пусть I — отрезок. Предположим, что P и P + I — параллелоэдры размерности d, кроме того, P — параллелоэдр Вороного.

Тогда P + I — также параллелоэдр Вороного (возможно, в другой евклидовой метрике).

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

Теорема 4.2. Пусть P — параллелоэдр Вороного, а 1, 2 — гиперплоскости в Ed. Предположим, что для каждой гиперграни F P имеет место хотя бы одно включение Тогда P приводим, т.е. P = P1 P2, где P1 и P2 — параллелоэдры меньшей размерности.

Для сравнения приведем лемму из диссертации [35].

Лемма 4.3. Пусть P — произвольный d-мерный параллелоэдр, а 1, — такие линейные подпространства Ed, что 1 2 = Ed. Предположим, что для каждой гиперграни F P имеет место хотя бы одно включение Тогда P приводим, т.е. P = P1 P2, причем a Pi i (i = 1, 2).

По сравнению с Леммой 4.3, Теорема 4.2 накладывает дополнительное требование (P — параллелоэдр Вороного), но за счет этого ослабляет условие, гарантирующее приводимость — фасетные векторы параллелоэдра P достаточно покрыть двумя гиперплоскостями вместо двух взаимно дополнительных подпространств.

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

Теорема 4.4. Пусть P — параллелоэдр Вороного, имеющий двумерное свободное пространство. Тогда P приводим, т.е. P = P1 P2, где P1 и P2 — параллелоэдры меньших размерностей.

Доказательству Теоремы 4.4 посвящены все последующие разделы данной главы, сейчас же покажем эквивалентность Теореме 4.1.

Лемма 4.5. Теорема 4.1 и Теорема 4.4 эквивалентны.

Доказательство. Предположим, что Теорема 4.1 верна. Если Теорема 4. неверна, то существует неприводимый параллелоэдр Вороного P = P (, ) со свободным двумерным пространством. Но при фиксированном параллелоэдре P для линейной оболочки AI (P ) BI (P ) существует лишь конечное число возможностей. Поэтому существует лишь конечное число векторов x таких, что xT x = 1 и при I = [x, x] Но из Теорем 4.1 и 3.8 следует, что последнее условие должно выполняться для любого x. Противоречие, а значит Теорема 4.4 следует из Теоремы 4.1.

Пусть теперь верна Теорема 4.4. Если Теорема 4.1 неверна, рассмотрим контрпример вида P + I с параллелоэдром P наименьшей возможной размерности. Если P приводим, то по Теореме 3.10 либо P1 + I1, либо P2 + I является, меньшим контрпримером, что противоречит выбору P + I. Если P неприводим, то по Теореме 4.4, у P нет свободных пространств размерности, большей единицы. Это значит, что выполнено равенство (3.3), поскольку в противном случае пространство является свободным для P и имеет размерность не меньше двух. Отсюда по Следствию 3.9 параллелоэдр P + I есть параллелоэдр Вороного, т.е. не является контрпримером к Теореме 4.1. Значит, Теорема 4.1 следует из Теоремы 4.4.

Также сформулируем уточнение Теоремы 4.2.

Теорема 4.6. Пусть P — приводимый параллелоэдр Вороного, и P = P P2...Pk — его разложение в прямую сумму неприводимых слагаемых.

Предположим, что 1, 2 — такие гиперплоскости в Ed, что для каждой гиперграни F P имеет место хотя бы одно включение (4.1). Тогда для каждого i = 1, 2,..., k имеет место хотя бы одно из двух утверждений Для d-мерного параллелоэдра Вороного P будем говорить, что гиперплоскости 1, 2 в Ed образуют крест, покрывающий фасетные векторы (или просто крест) для P, если для каждой гиперграни F P имеет место хотя бы одно включение (4.1).