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

Математический институт им. В. А. Стеклова Российской Академии Наук

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

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кал щ и дата фи з и ко- м атем ати чес ких 11 ау к

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

7 АВГ 2014

Москва, 2014 г.

005551543

Работа выполнена в отделе геометрии и топологии ФГБУН «Математически, институт им. В. А. Стеклова РАН»

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

Официальные оппоненты:

Ведущая организация:

Долбилин Николай Петрович — д.ф-м.н., ведущий научный сотрудник отдела геометрии и топологии ФГБУН «Математический институт им. В. А. Стеклова РАН»

Панина Гаянэ Юрьевна —-д.ф.-м.н., ведущий научный сотрудник лаборатории речевых и многомодальных интерфейсов

ФГБУН «Санкт-Петербургский институт информатики и автоматизации РАН» (СПИИРАН)

Тарасов Сергей Павлович — к.ф.-м.и., старший научный сотрудник отдела математического моделирования систем проектирования ФГБУН «Вычислительный центр им. А. А. Дородницына РАН»

ФГБУН «Институт математики им. С. Л. Соболева СО РАН»

сю

на заседании дие

Защита диссертации состоится 17 октября 2014 г. в 15 сертационного совета Д 002.022.03 при ФГБУН «Математический инстату-им. В. А. Стеклова РАН» по адресу: 119991, г. Москва, ул. Губкина, д. 8.

С диссертацией можно ознакомиться в библиотеке МИ АН и по адресу http ://www.mi.ras.ru/dis/ref14/magazinov/magazinov_dis.pdf.

Автореферат разослан ^^ _2014 года

Ученый секретарь диссертационного совета Д 002.022.03 при ФГБУН «Мате матический институт им. В. А. Стеклова РАН», д.ф.-м.н., ведущий научный сотрудник ___fs,

дов И. Д.

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7G. 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 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из всех ci-мерных параллелоэдров только параллелепипеды свободны вдоль любого вектора в К'г. Для любого другого параллелоэдра существуют векторы, вдоль которых этот параллелоэдр несвободен. Поэтому нас будет интересовать необходимое и достаточное условие, характеризующее векторы, вдоль которых данный параллелоэдр свободен. Такое условие было сформулировано В. П. Гришухиным. Однако в его работе13 не была преодолена трудность, возникающая при проверке условия о числе граней в пояске.

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

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

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

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

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

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

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

Цели работы

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

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

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

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

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

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

15А. Vegh, Räcsok, kör- es gömbelrendezesek // диссертация, BME, Budapest, 2006.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Диссертация состоит из четырех глав, первая из которых — Введение.

16 A. Magazinov, Voronoi's Conjecture for extensions of Voronoi parallelobcdra // Preprint: arXiv:1308.6225, 2013.

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

Пусть Л — решетка, a Q — положительно определенная квадратичная форма в пространстве К'г. Предположим такде, что 0 € Л. Рассмотрим многогранник

Р(Л, n)={y6R¿: утПу = min(y - x)Tft(y - *)}.

хел

Несложно видеть, что разбиение Вороного пространства с евклидовой метрикой ||х|| = VхтПх для решетки Л состоит из конгруэнтных ячеек, каждая из которых есть транслят многогранника Р(Л, П). Поэтому Р(Л, Г2) — параллелоэдр.

Многогранник Р(Л, Í7), а также любой его параллельный перенос будем называть параллелоэдром Вороного решетки Л относительно формы Q. Такое определение параллелоэдра Вороного дает возможность сформулировать гипотезу Вороного следующим образом.

Гипотеза Вороного. Всякий параллелоэдр является параллелоэдром Вороного.

Все результаты диссертации так или иначе мотивированы связью с гипотезой Вороного. Поэтому гипотеза Вороного (доказательство или опровержение которой для параллелоэдров размерности d > 5 остается нерешенной задачей) занимает центральное место в диссертации.

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

Гипотеза о размерности17. Множество центров всех параллелоэдров разбиения Т(Р), сходящихся в данной {d — к)-мерной грани разбиения, есть множество вершин выпуклого k-мерного многогранника.

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

В § 2.1 приводятся основные результаты главы, затем, в §§ 2.2 - 2.4, даются доказательства. Перечислим ключевые результаты Главы 2 с необходимыми определениями.

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

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

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

Пусть Е — произвольная (d — /с)-мерная грань разбиения Т(Р), ячейки которого — трансляты d-мсрного параллелоэдра Р. Пусть Р\, Р2, ■.., Рт — все ячейки разбиения Т(Р), содержащие грань Е. Через а обозначим /с-мерную аффинную плоскость — образ проекции proj£. Все m проекций вида projÊ(P,) попарно не имеют общей относительной внутренности, и целиком заполняют некоторую окрестность точки v = proj£(i?) в плоскости а. Семейство многогранников вида projE(Pi) делит эту окрестность таким же образом, как и некоторый полный /с-мерный полиэдральный веер Fan(.E) с вершиной в точке v. Веер Fan(S) назовем веером грани Е.

Для к <2 классификация вееров граней сложности не представляет. Рассмотрим случай к = 3. В этом случае все комбинаторные типы трехмерных вееров граней были найдены Б. Н. Делоне18.

Теорема Делоне. Веер любой (d — 3)-мерной грани разбиения Т{Р), где Р — d-мерный параллелоэдр, комбинаторно эквивалентен одному из изображенных на рис. 1.

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

1. Определим веер грани С полного полиэдрального веера С по аналогии с определением веера грани Е разбиения Т(Р).

2. Пусть С — грань (конус) полного полиэдрального веера С. Построим веер грани С. Это построение зависит лишь от выбора плоскости а, трансвер-

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

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

3. Конусы максимальной размерности С\ и С? полного полиэдрального веера С можно назвать симметричными относительно некоторого конуса С того же веера, если С = С1ПС2, и проекции projafTC(Ci) и projaffC(C2) симметричны относительно точки projaffc(C) в некоторой окрестности этой точки.

Назовем ¿-мерный полный полиэдральный веер С тесным,, если для любых двух различных fc-мерных конусов С\, Сг € С конусы С\ и С2 симметричны относительно их пересечения С if] С2 (это пересечение — конус веера С и имеет размерность < к).

Теорема Делоне следует из двух утверждений, приводимых ниже. Доказательства этих утверждений приведены в § 2.2 диссертации. Теорема 2.2. Любой трехмерный тесный полиэдральный веер принадлежит одному из пяти комбинаторных типов, изображенных на рис. 1. Предложение 2.5. Веер любой грани разбиения Т{Р) является тесным.

В § 2.3 приводятся следствия теоремы Делоне. Для этого вводятся следующие обозначения.

Пусть Т>(Е) — множество центров параллелоэдров, сходящихся в грани Е разбиения Т(Р). Пусть А(Р) — решетка центров всех параллелоэдров разбиения Т(Р). Рассмотрим минимальную по включению подрешетку решетки Л(Р), содержащую все точки множества Т>(Е). Обозначим эту подрешетку через А(Е). Обозначим также

Лад (Я) =Л(Р) naff V(E).

Сформулируем основные результаты § 2.3. Следствие 2.8. Для любой (d — 3)-мерной грани Е разбиения Т(Р) верно равенство dimafFX>(£') = 3.

Иначе говоря, для граней коразмерности 3 верна гипотеза о размерности. Теорема 2.9. Для любой (d — 3)-мерной грани Е разбиения Т(Р) выполняется

Л aS(E) = A(E).

Отметим, что для (d — 5)-мерных граней утверждение о совпадении решеток А(Е) и Aag(Е), аналогичное Теореме 2.9, неверно. В самом деле, 5-мерный симплекс индекса 2 может быть даже клеткой Делоне для некоторой решетки; на этот факт впервые обратил внимание Вороной в § 67 цитированной работы7, явные конструкции таких пятимерных симплексов Делоне приведены Рышковым19 и, в более общем виде, Барановским20. При этом неизвестно, имеет ли место аналог Теоремы 2.9 для (d — 4)-мерных граней, однако любой контрпример опровергнет и гипотезу Вороного.

Далее, в § 2.4, переходим к случаю произвольной коразмерности к грани разбиения Е. Основной результат этого параграфа — это Теорема 2.3, приводимая ниже. Ее аналог для параллелоэдров Вороного следует из того, что ранг решетки А(Е) в точности равен d — k. Как наиболее доступную, приведем ссылку на монографию М. Деза и М. Лоран21.

Теорема 2.3. Пусть Е — грань размерности (d— к) разбиения Т(Р). Тогда eeepFan(E) состоит не более чем из 2к конусов размерности к (т.е. конусов м.аксим,алъной размерности).

Пусть грань Е принадлежит параллелоэдрам Р\ = Р, А, • • •, Рт разбиения Т(Р), и пусть Pi = Р I t, (в частности, tj = 0). Тогда положим Ег = Е—Ьг при i = 1,2,... ,m. Поскольку Е — грань параллелоэдра Pi, то Ei является гранью параллелоэдра Р.

Ключевой в доказательстве Теоремы 2.3 является следующая лемма. Лемма 2.11. Пусть w, = proj£](Ei). Тогда множество

W = {w: i = 1, 2,..., то}

антиподалъно22 в

Использованное определение антиподального множества несколько отличается от определения антиподального множества по Данцеру и Грюнбау-му23. Однако методы из работы Данцера и Грюнбаума можно применить к

19С. С. Рышков, Основные экстремальные задачи геометрии положительных квадратичных форм // Диссертация, 1970.

20Е. П. Барановский, Объемы L-симплексов пятимерных решеток // Матем. заметки, 13:5 (1973), 771782.

21M. Деза, М. Лоран, Геометрия разрезов и метрик, Москва, МЦНМО, 2001; Предложение 13.2.8.

22 Конечное множество W С Rk назовем антиподальным, если для любой пары различных точек х, у € W найдется такая пара несовпадающих параллельных гиперплоскостей /3,7 (т.е. плоскостей размерности к — 1), что х € ß, у € 7 и все точки множества W заключены (нестрого) между ¡3 и 7.

23L. 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.

множеству W практически в неизменном виде и тем самым получить оценку т < 2к.

В Главе 3 диссертации изучаются свойства удлинений параллелоэдров. Напомним, что параллелелоэдр Р размерности d называется удлинением d-мерного параллелоэдра Р'. если для некоторого отрезка I и суммы Минков-ского Р' + I справедливо равенство Р = Р' + I.

§ 3.1 является для Главы 3 вводным. В § 3.2 доказывается, что некоторое условие необходимо и достаточно для того, чтобы данный параллелоэдр был свободен вдоль данного вектора. В Параграфе 3.3 доказывается критерий того, что сумма Минковского данного неприводимого параллелоэдра Вороного и данного отрезка является параллелоэдром Вороного. В §§ 3.4 - 3.6 даны доказательства технических результатов, используемых в Главе 4.

Приведем основной результат § 3.2. Теорема 3.3. Для данного d-мерного параллелоэдра Р и отрезка I следующие два условия эквивалентны.

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

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

Далее будем использовать обозначение s(E) для стандартного вектора стандартной грани Е параллелоэдра Р24. Если I — отрезок, Р + I — параллелоэдр, и dim Р = dim(P + I) = d, то положим

А](Р) = (s(G) : G — такая грань параллелоэдра Р, что

dim G = d — 2 и G ф / - гипергрань параллелоэдра Р + I}.

Замечание. По Теореме 3.3, (d — 2)-грань G в определении А](Р) может задавать только четырехгранный поясок. Поэтому грань G стандартна, а следовательно, для нее существует стандартный вектор s(G).

Напомним, что через Р(А, Г2) мы обозначаем параллелоэдр Вороного решетки Л в евклидовой метрике, заданной квадратичной формой П. Теорема 3.8. Пусть Р = Р(Л, П), и параллелоэдр Р свободен вдоль вектора х; пусть I = [—х, х]. Предположим, что для любой [d — 2)-грани G парал-

24 Грань Е параллелоэдра Р называется стандартной, если Е = Р П /''. где Р' — параллелоэдр разбиения Т[Р). Вектор t такой, что Р' = Р + t, назовем стандартным вектором грани Е. См. также: Н. П. Долбилин, Свойства граней параллелоэдров // Геометрия, топология и математическая физика II, Сборник статей. К 70-летию со дня рождения академика Сергея Петровича Новикова, Тр. МИАН, 266 (2009), 112-126.

лелоэдра Р, удовлетворяющей условию s(G) Е А](Р), выполнено равенство

хг • П - s (G) = 0. (1)

Тогда Р + I — параллелоэдр Вороного (вообще говоря, в другой метрике, нежели Р). Если же Р неприводим, то условие (1) является необходимым для того, чтобы параллелоэдр Р + I был параллелоэдром Вороного.

Формулировки Теорем 3.3 и 3.8 впервые приведены в работах В. П. Гри-шухина13,14. До последнего времени их доказательства не были завершены. Для полного доказательства Теорем 3.3 и 3.8 оставалось изучить грани многогранника Р + I вида Е © /, где Е — (d — 3)-мерная грань многогранника Р. А именно, для Теоремы 3.3 требовалась проверка условия Минковского-Венкова о длине пояска, заданного (d — 2)-гранью Е © а для Теоремы 3.8

9е;

— проверка условия каноническом нормировки" вокруг такой грани.

Если Е — {d — 3)-мерная грань многогранника Р, то по теореме Делоне ее веер принадлежит одному из пяти типов (см. рис. 1). Рассматривается взаимное расположение веера Fan(.E') и отрезка proj£•(/). При этом отрезок proj£(/) должен удовлетворять следующму условию: для каждого луча веера Fan (is), в котором сходится ровно три двумерные грани, отрезок proj£(/) параллелен хотя бы одной из этих граней.

Всего оказывается допустимыми 13 комбинаторно различных типов взаимного расположения веера Fan(£) и отрезка proj£(/). Для 5 из этих 13 типов у параллелоэдра Р есть грани вида E+t, где t е А(Р), такие, что (E + t)®I

— (d — 2)-грань многогранника Р +1. Для остальных 8 типов взаимного расположения веера Fan(£) и отрезка proj£(/) многогранник Р + I не имеет (d — 2)-граней вида (Е + t) ф I.

Все грани вида (Е + t) ф I попарно параллельны, следовательно, задают один и тот же поясок многогранника Р + I. Оказывается, что число гиперграней в таком пояске однозначно определяется типом расположения веера Fan(£) и отрезка proj£(/), и может быть равно только 4 или б. Это приводит к доказательству Теоремы 3.3.

Для доказательства Теоремы 3.8 явно строится каноническая нормировка s параллелоэдра Р + I. Положим s(F') = s(F), если у гиперграни F' параллелоэдра Р + I есть параллельная гипергрань F параллелоэдра Р с тем же направлением внешней нормали, то положим s(F') = s(F). Если же гипергрань F' параллелоэдра Р +1 не параллельна ни одной гиперграни параллелоэдра Р, то имеет место равенство F' = G © где G — стандартная (d — 2)-грань параллелоэдра Р. В этом случае положим s(F') = s(G).

25О канонической нормировке и ее связи с гипотезой Вороного см.: М. Deza, V. Grishukhin, Properties of parallelotopes equivalent to Voronoi's conjecture // European Journal of Combinatorics, 25 (2004), 517-533.

Мы проверим условия канонической нормировки для поясков параллело-эдра Р + I, порожденных (d — 2)-гранями вида Е@ I, где Е — (d — 3)-грань параллелоэдра Р. Все гиперграни такого пояска параллельны отрезку I. Но заметим, что для любой гиперграни F' параллелоэдра Р + I, параллельной отрезку I, вектор s(F') совпадает с фасетным вектором гиперграни F'. Поэтому условие канонической нормировки превращается в верное соотношение на фасетные векторы пояска параллелоэдра.

Остальные условия канонической нормировки были проверены ранее14. Таким образом, завершено доказательство Теоремы 3.8.

Основными результатами Главы 4 являются Теоремы 4.1 и 4.2. Они сформулированы в § 4.1.

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

Теорема 4.2. Пусть Р — параллелоэдр Вороного, а ß\,ß2 — гиперплоскости в Ed. Предположим, что для каждой гиперграни F С Р имеет место хотя бы одно включение

s(F) е ßi или s(F) G ß2. (2)

Тогда Р приводим, т.е. Р = Р\ © Р2, где Р\ и Р2 — параллелоэдры меньшей размерности.

В § 4.2 намечается план доказательства Теорем 4.1 и 4.2. Сначала Теорема 4.1 сводится к следующей, эквивалентной.

Теорема 4.4. Пусть Р — параллелоэдр Вороного, имеющий двул^ерное свободное пространство. Тогда Р приводим.

Затем формулируется теорема, уточняющая Теорему 4.2. Теорема 4.6. Пусть Р — приводимый параллелоэдр Вороного, и Р = Р\ © Р2© - - • © Рк — его разложение в прямую сумму неприводимых слагаемых. Предположим, что ß\,ß2 — такие гиперплоскости в Ed, что для каждой гиперграни F С Р имеет место хотя бы одно включение (2). Тогда для каждого г = 1,2,... ,к имеет место хотя бы одно из двух утверждений — äff Pi || ßi или äff Pi || ß2.

Далее предлагается схема индуктивного доказательства Теорем 4.2, 4.4 и 4.6. Для каждого натурального d через А(d) (соответственно, В(с!) и С(с()) обозначим утверждение о справедливости Теоремы 4.4 (соответственно, 4.2 и 4.6) для всех параллелоэдров размерности < d. Предположим, что доказаны следующие импликации:

1. B(d — 3) =»■ C(d — 2);

2. (A(d - 2), С(d - 2)) B(d - 2);

3. (B(d - 2), C(d - 2)) =>- A(d).

Тогда имеем переход индукции, который вместе с базой (А(4), В(2), С(2)) доказывает одновременно Теоремы 4.2, 4.4 и 4.6.

В § 4.4 доказываются импликации B(cf — 3) => C(d— 2) и (A(d— 2), C(d — 2)) => B(ci — 2). Вторая является наиболее сложной из всех трех, участвующих в переходе индукции. Для ее доказательства используются результаты § 4.3, т.е. приводимая ниже конструкция и Лемма 4.7 об основном свойстве этой конструкции.

Пусть Г2 — положительно определенная квадратичная форма, an — произвольный вектор в Md. Введем обозначение П„ для новой квадратичной формы, заданной формулой

Пп = П+ (fin) • (fin)r.

Пусть Jr(А, П) — множество всех фасетных векторов параллелоэдра Р(A, Q). Введем обозначение

,Fn(A, П) = {s : s € Т(А, П) и nri)s^0}.

Имеет место следующая лемма. Лемма 4.7. {Тп(А, Пп)) С (JTn(A,fi)).

Наконец, в § 4.5 доказывается импликация (B(d — 2), C(d — 2)) A(d) и тем самым завершается доказательство основных результатов Главы 4.

Список работ автора по теме диссертации

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

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

3. М. 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 . ejс. 2014.05.005.

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

Подписано в печат ь 05.06.2014 Тираж 100 экз.

Отпечатано » Математическом институте им. В.А. Сгеклова РАН Москва, 119991, ул. Губкина, К