автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Аффинные типы L-многогранников пятимерных решеток

ч

Министерство общего и профессионального образования

Российской Федерации

Ивановский государственный университет

КОНОНЕНКО П.Г.

АФФИННЫЕ ТИПЫ Ь-МНОГОГРАННИКОВ ПЯТИМЕРНЫХ РЕШЁТОК

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

(05.13.16 - "Применение вычислительной техники, математического моделирования и математических методов

в научных исследованиях")

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

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

профессор Е. П. Барановский

Иваново 1999

СОДЕРЖАНИЕ

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

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

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

теории L-разбиений...............................................9

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

решеток...........................................................77

Литература.............................................................83

Приложение 1. Матрицы координат Ь-многогранников

5-мерных решеток..............................................85

Приложение 2. Пакет программ на языке Паскаль..............98

1. Инструкция по применению пакета программ.

Список программных файлов.................................98

2. Схема взаимодействия модулей пакета программ.....100

3. Представление основных данных..........................100

4. Краткое описание основных модулей и процедур.......102

5. Тексты программ...........................................105

ПРЕДИСЛОВИЕ

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

Основополагающей работой, которая положила начало теории Ь-разбиений, был мемуар, как принято называть эту статью, известного русского математика Г.Ф.Вороного [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,..., »} — множество точек гиперметрического пространства.

> • — соответственно начало и конец доказательства.

ГЛАВА I. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ ГЕОМЕТРИИИ РЕШЕТОК И ТЕОРИИ Ь-РАЗБИЕНИЙ

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

Базисом (репером) в «-мерном евклидовом пространстве Е" называется система линейно независимых векторов

ё1,ё2,...,ё„ (1.1)

Для любогого вектора V пространства Ея существуют однозначно определенные числа V2 € К (называемые его координатами) для которых вектор V разлагается в сумму

V- г/ёх + «/^-Ь ...+ ьпёп. (1.2)

Точки Д),пространства Ея называются линейно (аф-финно) независимыми, если векторы А^А\, А0А2,..., АоАь линейно независимы. Барицентрическим (аффинным) базисом пространства Е" называется система линейно независимых точек Д >, А\,..., А„ (с радиус векторами а = ОА^ г = 0,..., п относительно некоторой начальной точки О).

Для любой точки X пространства Ея (с радиус вектором х = ОХ) существуют однозначно определенные числа £,..., яР € К с суммой У^о = 1 называемые барицентрическими (аффинными) координатами точки Х} для которых выполнено равенство

л п

ОХ = х= ^х'а, ЕЕ (1.3)

¿=0 *=0

не зависящее от выбора начальной точки О. Набор из п барицентрических координат з^ точки X является (обычными) координатами вектора АцХ относительно (обычного векторного) базиса АкАъ,..., АьАк-1, ДьДн-1»• • - > ЛкАп.

Для любого вектора Ю пространства Ея существуют однозначно определенные числа Vе,..., У € К с ]Г)1о - 0, называемые барицентрическими (аффинными) координатами вектора г>, для которых

справедливо равенство

п п

V =£у (1.4)

¿=0 ¿=0

не зависящее от выбора начальной точки О. Набор из п барицентрических координат ..., г/*1-1, г/**1,..., г/1 являются (обычными) координатами вектора г> относительно (обычного векторного) базиса . •., АъАц-1, Д*Дн-1,.. •, АкАп. Пусть далее (векторный) базис ,..., еп и барицентрический базис Ао,... ,Ап связаны соотношениями

ё, = А0Аг- (г= 1,...,«). (1.5)

Попарные скалярные произведения а,у = ёхёу (1 < < я) определяют симметричную матрицу = (л,у) размера йхл, называемую матрицей Грома и определяющую метрическую квадратичную форму

п

/(х) = х € а" (1.6)

или

/(х) = х€ К",

имеющую геометрический смысл квадрата длины вектора х со строкой (обычных) координат (¿г1,..., зР). Квадратичная форма Дх) с матрицей А = (й,у) является положительно определенной. И любая положительно определенная квадратичная форма /(х) с матрицей = (а,у) определяет с точностью до положения в пространстве (ортогонального преобразования) базис ёП) удовлетворяющий соотношениям (1.5).

Пусть О — »-мерная сфера с радиусом Я и центром Степенью точки X относительно сферы О называется величина |<?ЛГ|2 - Л2.

Квадраты расстояний между точками барицентрического базиса задают (я£1) = п(п+ 1)Д величин

= \A~Atf (0 <!</<»), (1.8)

которые определяют форму

<£(х) = - ^ х€ К*4"1. (1.9)

о<*<?'<»

Форма 0(х) может иметь геометрический смысл:

а) Квадрата длины вектора х с барицентрическими координатами ..., х" (в случае, когда £2=0 & = 0).

б) Степени точки X с барицентрическими координатами аР,..., а?* (в сдучае, когда = 1) относительно сферы (однозначно) определенной принадлежащими ей точками Д),..., Ап.

Величины и {(¿?)о<г<1<п взаимно определяют друг друга

и связаны соотношениями

«я = (¿01 (1 < г < я), % = (¿о« + - ^1>)/2 (1 < < У < я),

= ^й (1 < < »), ^ = +• ¿гу- - 2<2у (1 < г' < у < я).

(1.7)

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

Множество У евклидова пространства Ея называется равномерно дискретным,, если существуют числа г и Л, такие, что

а) шары с радиусами г и центрами в точках множества Т попарно не пересекаются;

б) шары с радиусами Я и центрами в точках множества /'покрывают все пространство Б".

Точечной »-мерной решеткой (далее решеткой) евклидова пространства Еп называется равномерно дискретное множество Г С Ея, сохраняющееся при любом преобразовании параллельного переноса пространства Ея на вектор, соединяющий любые две точки множества Г,

Для любой »-мерной решетки Г С Б" найдется базис ёь..., ёп пространства Ея, называемый основным базисом решетки Гу такой, что решетка Г представляется как множество точек с целочисленными координатами:

Г={х=з}ё1+... + | з*,..., зГ € X}.

(1.10)

Барицентрический базис Л = {А0,..., Ап) называется основным для решетки Г% если Г представляется (относительно Л) как множество точек X с целочисленными барицентрическими координатами

п

Г - х0ао+ ¿щ + + з�