Аффинные типы L-многогранников пятимерных решеток тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Кононенко, Павел Геннадьевич

• Кононенко, Павел Геннадьевич
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Кононенко, Павел Геннадьевич

Предисловие.

Основные обозначения.

Глава I. Предварительные сведения из геометрии решеток и теории L-разбиений.

1. Векторный и барицентрический базисы и порожденные ими формы.

2. Точечные решетки.

3. L-разбиения решеток.

Глава II. Предварительные сведения из теории гиперметрических пространств. Гиперметрический конус, Cut-конус, L-многогранники решеток.

Глава III. Исследование конуса НУРпи при п < 5.

Аффинные типы »-мерных (п < 5) L-многогранников, содержащих основной симплекс решетки.

1. Невырожденные гиперметрики.

2. Размерность решеток и аффинные типы ¿-многогранников, соответствующие граням конусов HYP^\ и C^i.

3. Об одном сечении конуса ¿7я+1.

4. Невырожденные грани cut-конуса б^и- Размерность решетки Ьд для d е С^х.

5. Матрица М{Р) невырожденной грани F конуса On+i.

6. Классы эквивалентности граней конуса Сп+\ и их матричное представление.

7. Матричное представление аффинных типов L-многогранников.

8. Алгоритм нахождения аффинных типов Z-многогранников размерности п < 5, содержащих основной симплекс решетки. Результаты.

Глава IV. Обобщенно гиперметрические пространства.

Глава V. Примеры обобщенно гиперметрических пространств.

1. Координатное множество. Общие замечания.

2. Обобщенно гиперметрический конус НУР^г1.

3. Обобщенно гиперметрический конус НУР^.

4. Обобщенно гиперметрические конусы НУР^г.

Глава VI. Полнота списка пятимерных Ь-многогранников.

Итоговые теоремы.

1. Выделение ¿-симплекса из ¿-многогранника.

2. Все пятимерные Ь-многогранники, порождающие решетку, - основные.

3. Итоговые теоремы.

Таблица 1. Аффинные типы Ь-многогранников 5-мерных решеток.

Введение диссертации (часть автореферата) на тему «Аффинные типы L-многогранников пятимерных решеток»

Тема настоящей диссертации относится к одной из глав геометрии решёток — теории задаваемых решётками Ь-разбиений евклидовых пространств. В диссертации дан полный вывод типов Ь-многогранни-хов пятимерных решёток; важным этапом вывода было использование вычислительной техники — персонального компьютера.

Основополагающей работой, которая положила начало теории Ь-разбиений, был мемуар, как принято называть эту статью, известного русского математика Г.Ф.Вороного [9] о примитивных параллелоэд-рах. В этой, ставшей классической, работе Г.Ф.Вороной ввел понятие Ь-симплекса, правда, только применительно к решёткам общего вида, связал задачу о комбинаторных типах параллелоэдров с задачей о типах Ь-разбиений решёток, показал, что при данной размерности п таких типов существует лишь конечное число, построил алгоритм их вывода и вывел эти типы для случаев п < 3.

Последующие фундаментальные достижения в теории Ь-разбиений принадлежат Б.Н.Делоне. (Как дань его выдающейся роли в этой теории, наряду с названием "Ь-многогранник", которое пошло от термина "симплекс Ь" в мемуаре Вороного, используется название "многогранник Делоне".) Статья Б.Н.Делоне [11] до сих пор остаётся учебником, вводящим в теорию Ь-разбиений.

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

Настоящая диссертация относится к наиболее актуальной теме теории Ь-разбиений — Ь-раз биениям точечных решёток. В последние годы здесь полностью решены вопросы описания видов Ь-многогранников и строении Ь-разбиений решёток размерности п < 4, исследованы Ь-разбиения наиболее значимых отдельных решёток и классов решёток в произвольных размерностях, в монографии С.С.Рышкова и Е.П.Барановского найдено строение Ь-разбиений 5-мерных решёток общего вида. Все комбинаторные типы 4-мерных Ь-многогранников были выведены в работе С.С.Рышкова и Р.Эрдала [21], где получил своё развитие положенный В.Н.Делоне в основу описания Ь-разбиений метод "пустого шара". На очереди стала задача вывода всех аффинно различных видов 5-мерных решёточных Ь-многогранников.

Исследования различных подходов к последней задаче показывали, что для её решения нужно будет преодолеть большие вычислительные трудности, в первую очередь вызванные существенно большим по сравнению с размерностями п < 4 количеством типов многогранников. (Их оказалось 139, тогда как при п— 2,3,4 число их равно соответственно 2,5,19.) Преодолеть эти вычислительные трудности было естественно посредством применения вычислительной техники. Именно на этом пути, путём создания алгоритма для переложения вычислительной работы на персональный компьютер, и удалось получить решение задачи.

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

Теория гиперметрических пространств (теория гиперметрик) возникла около трёх десятков лет назад (М.Деза [10], Дж.Келли [22]). Развитие теории гиперметрик стимулировалось её связью с радом задач теории графов, геометрии Хемминга единичных кубов, теории кодов. В 1984 году П.Асуад [16] установил связь этой теории с геометрией решёток — открыл взаимно-однозначное соответствие между гиперметрическими пространствами и Ь-многогранниками.

Установление связи между теорией гиперметрик и теорией Ь-разбиений, ранее развивавшихся обособленно друг от друга, выявило, что в этих ветвях геометрии существует рад одинаковых по сути задач, сформулированных каждая на языке своей теории. Например, задача, исследованная в статье [16] конуса гиперметрик, рассматривалась как задача об Ь-условиях для симплекса решётки в статье [1].

Здесь, в диссертации, роль теории гиперметрик состоит в том, что после выделения невырожденных гиперметрик и невырожденных граней разрезного конуса (с^-конуса) и установления их соответствия с решётками и многогранниками Ь-разбиений можно было при построении нужных вычислительных алгоритмов существенно использовать полученные в теории гиперметрик результаты о строении гиперметрических конусов и си1;-конусов.

Основными результатами диссертации являются следующие: построен алгоритм для применения вычислительной техники при решении задачи о выводе аффинных типов Ь-многогранников решёток, а также некоторых других задач теории Ь-разбиений решёток; на базе названного выше алгоритма создана программа вычислений на персональном компьютере; эта программа использована при выводе аффинных типов Ь-многогранников 5-мерных решёток; полностью решена задача вывода и описания строения Ь-много-гранников пятимерных решёток; исследован вопрос о многослойных Ь-многогранниках в размерностях п < 5; введены понятия невырожденных гиперметрик и невырожденных граней разрезного конуса (сгй-конуса) и задача вывода типов Ь-многогранников сведена к задаче исследования невырожденных граней с^-конуса.

Результаты диссертации опубликованы в статьях [12], [6], [13], [5].

Диссертация состоит из предисловия, шести глав, списка литературы и двух приложений — списка хоординатных матриц вершин пятимерных Ь-многогранников и программы на языке ПАСКАЛЬ для персонального компьютера.

Первые две главы носят вводный характер и содержат предварительные сведения из геометрии решеток, Ь-разбиений и соответственно теории гиперметрических пространств.

Третья глава содержит основные конструкции и общий алгоритм, позволивший найти список аффинных типов Ь-многогранников 5-мерных решеток, представленный в таблице 1. Было введено понятие невырожденных гиперметрик и установлено взаимно-однозначное соответствие между невырожденными гиперметриками (X, г/) (|ЛГ| = п + 1) и парами ф), где Р — это Ь-многогранник некоторой »-мерной решетки ЬуЪф- инъективное отображение из X — {0,., п} во множество вершин многогранника Р, причем ф(Х) образует основной симплекс решетки Ь. Это соответствие открыло путь для решения вопроса о типах Ь-многогранников через исследование множества граней сг^-конуса Сп± 1. Пользуясь понятием ^--эквивалентности граней конуса и матричным представлением таких граней, задача вывода аффинных типов Ь-многогранников свелась к задаче исследования на специальном классе матриц. Было получено матричное представление аффинных типов Ь-многогранников. Завершается третья глава построением общего алгоритма нахождения этих типов, переложенного затем на язык компьютера (язык Паскаль).

Четвертая и пятая главы содержат конструкции, являющиеся некоторым обобщением построений теории гиперметрических пространств, и включает три примера исследования обобщенных гиперметрических пространств. В контексте задачи отыскания аффинных типов 5-мерных Ь-многограннихов основной результат четвертой и пятой глав (и в частности третьего примера — исследования конусов (//УР^)1 и (//УР*+1)2) лежит в теореме 5.1, которая играет решающую роль в шестой главе при доказательстве полноты списка аффинных типов Ь-многогранников 5-мерных решеток, представленного в таблице 1.

В шестой главе приведена теорема 6.4, сформулированная как итог всей диссертации.

Отметим, что пятимерные Ь-многогранники, имеющие центр симметрии (их всего 13 из общего количества 139), были выведены другими методами Б.В.Власовым [8] и автором диссертации [12].

Результаты работы докладывались на Международных конференциях по проблемам теоретической кибернетики (Москва, 1998 год, Нижний Новгород, 1999 год), на Международной конференции по геометрии "в целом"[5] (г.Черкассы, 8-13 сент. 1997 г.), на отчётных научных конференциях ИвГУ (1997-99 годы).

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

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ а£Л/— наименьшая плоскость в Ея, содержащая множество М.

Ann(¿¿), Апп(У^ — аннулятор гиперметрики, грани конуса HYI%V bp{Q} — »-мерная бипирамида над (п -1)-мерным многогранником Q.

Сп±\ — Cut-конус, конус разрезных функций.

C^xQ — »-мерная призма над (»-1)-мерным многогранником Q,

Сп — »-мерный кроссполиэдр. сотМ — выпуклая оболочка множества М. diтМ— размерность множества М в Еп. ext Р — множество вершин многогранника Р.

Fx = HYPnbi П fíx — грань конуса HYP^i.

F\d] — наименьшая грань конуса HYP^ содержащая гиперметрику d. х) = Y1¡¡у= i ^^ — квадратичная форма на переменных fX -yJ1

Нх — плоскость в пространстве гиперметрик rC**), заданная обращением в равенство гиперметрического неравенства на строке х € R"*1.

HYP^i — гиперметрический конус.

НУР^Х — обобщенно гиперметрический конус, построенный на основе симплекса с7-кратного объема.

K{d), K{F) — дефект гиперметрики úf, грани F.

М{Р) — множество строк барицентрических координат вершин L-многогранника, соответствующего грани F конуса НУР^\.

Г, L, Ln — »-мерная точечная решетка.

Рп — »-мерный параллелепипед. p{Q) - »-мерная пирамида над (»- 1)-мерным многогранником Q.

Uo,., ип — строки вида (1,0,., 0),., (0,., 0,1) из R*4"1.

X — {0,1,., »} — множество точек гиперметрического пространства. • — соответственно начало и конец доказательства.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Кононенко, Павел Геннадьевич

Результаты работы программы по нахождению аффинных типов L-многогранников 5-мерных решеток, содержащих среди своих вершин основной симплекс решетки, представлен в таблице 1. Вместе с теоремой 6.2 они позволяют сформулировать основную теорему работы.

Теорема 6.4. Существует всего 139 видов аффинно неэквивалентных L-многогранников пятимерных решеток, строение 138 из которых дано в таблице 1. Не названным в таблице Lмногогранником является симтглекс двойного объема. > •

Список литературы диссертационного исследования кандидат физико-математических наук Кононенко, Павел Геннадьевич, 1999 год

1.. Барановский Е.П. Симплексы Z-раз биений евклидовых пространств. Матем.заметки. 1971. 10, N 6. С. 659-670.

2. Е.П. Барановский. Объемы L-симплексов пятимерных решеток. Матем. заметки. 1973. В.13 N 5, С.771-782.

3. Барановский Е.П. Об L-симплексах шестимерных решеток. Вторая международная конференция "Алгебраические, Вероятностные, Геометрические, Комбинаторные и Функциональные Методы в Теории Чисел", 25-30 сентября 1995 г., Воронеж, Россия. С. 13.

4. Барановский Е.П., Власов Е.В., Новикова Н.В. Строение L-разбиений четырёхмерных решёток// Деп. ВИНИТИ. 1991. N 78-В91. С. 1-38.

5. Барановский Е.П., Кононенко П.Г. Двухслойные L-многогран-ники 5-мерных решеток. Международная конференция по геометрии "в целом", 8-13 сентября 1997г., г. Черкассы, Украина. С.8-9.

6. Барановский Е.П., Кононенко П.Г. Двухслойные /-многогранники 5-мерных решёток// Деп. ВИНИТИ. 1998. N 387-В98. С. 1 -28.

7. Барановский Е.П., Кононенко П.Г. Об одном способе вывода Z-многогранников ^-мерных решёток. Матем. заметки. 1999. (в печати).

8. Власов Е.В. Полиэдр четности, дуальные системы и первичные элементы L-разбиений решеток // Дисс. на соискание уч. ст. канд. физ-мат. наук, Иваново, 1996.

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

10. Деза М.(Тылкин М.Е.) О геометрии Хэмминга единичных кубов. ДАН СССР. 1960. Т.134, N5. С. 1037-1040.

11. Делоне Б.Н. Геометрия положительных квадратичных форм// Успехи матем. наук. 1937. Вып.З. С.16 62; 1938. Вып.4. С.102 - 164.

12. Кононенко П.Г. Получение пятимерных первичных L-мно-гогранников методом наслоения // Научные труды Ивановского Государственного Университета. 1997, Вып. 1. С.47-55.

13. Кононенко П.Г. Вывод аффинных типов L-многогранников 5-мерных решеток// Деп. в ВИНИТИ 25.11.98 N 3449-В98. С.1-35.

14. Рышков С.С., Барановский Е.П. С-типы га-мерных решёток и пятимерные примитивные параллелоэдры (с приложением к теории покрытий). Труды МИАН СССР. Т.137. М., "Наука". С.З -31.

15. Рышков С.С., Эрдал P.M. Поэтажное построение L-тел решеток. Успехи матем. наук. 1989. т. 44, вып. 2. С.241 242.

16. Assuad P. Sur les inegalites valides dans Ll. European Journal of Combinatorics. 1984. V.5. P.99-112.

17. Avis D., Mutt. All facets of the six point Hamming cone. European J. Combin. 1989. V.10. P.309-312.

18. Deza M., Grishukhin V.P., Laurent M. Extreme hypermetric and ¿-polytopes. Colloq. Math. Soc. Janos Bolyai. Budapest, 1991. V.60. P.157 209.

19. Deza M., Grishukhin V.P., Laurent M. The hypermetric cone is polyhedral. Combinatorica. 1993. 13(4). P.397-411.

20. Deza M., Grishukhin V.P., Laurent M. Hypermetrics in Geometry of Numbers. DIM ACS Series in disc. math, and theor. comp. science. 1995. V.20. P.l 109.

21. Erdahl R.M., Ryshkov S.S. The empty sphere// Can.J.Math. 1987. V.39, N 4. P.794 824.

22. Kelly J.B. Hypermetric Spaces // Lecture Notes in Math. 490, Springer-Verlag. 1975. P.17-31.