Диссертация (Рефлективные гиперболические решётки), страница 8

Классифицировал все 2-рефлективные гиперболические решетки ранга 4.• 2006 год, Д. Лонг, К. Маклахлан и А. Рид (см. [37]). Конечность числа максимальных арифметических групп отражений на плоскости ℍ2 .• 2006 год, И. Агол (см. [1]). Конечность числа максимальных арифметическихгрупп отражений в пространстве ℍ3 .• 2007 год, В.В.

Никулин (см. [52]). Окончательно установил конечность числамаксимальных арифметических групп отражений в пространствах Лобачевского во всех размерностях.37• 2008 год, (независимо, но позже Никулина) И. Агол, М. Белолипецкий, К. Сторми П. Уайт (см. [2]) доказали конечность числа максимальных арифметическихгрупп отражений во всех размерностях с помощью спектрального метода.• 2011 год, Д. Аллкок (см. [4]). Классифицировал вообще все рефлективные гиперболические решетки ранга 3.• 2015 год, А. Марк (см. [41]).

Классификация рефлективных гиперболическихрешеток над ℤ вида [−] ⊕ [1] ⊕ … ⊕ [1], где — простое число.• 2015 год, А. Марк (см. [42]). Классификация всех рефлективных гиперболических решеток над ℤ[√2] ранга 3, свободных от квадратов.• 2017 год, И. Туркал (см. [59]). Классификация всех рефлективных гиперболических решеток над ℤ ранга 6, свободных от квадратов.• 2016–2018 год, Н.В.

Богачев (см. [10, 62, 11]). Классификация всех устойчиворефлективных анизотропных гиперболических решеток над ℤ ранга 4.• 2018–2019 год, Н.В. Богачев (см. главу 5). Классификация всех максимальныхустойчиво рефлективных гиперболических решеток над ℤ[√2] ранга 4.38Глава 3Алгоритм Винберга и проект VinAl3.1. Общее описание алгоритма ВинбергаКак было сказано ранее, в 1972 году Э.Б. Винберг предложил эффективный алгоритм, позволяющий построить фундаментальный многогранник для любой дискретной группы отражений в пространстве Лобачевского.

В этом разделе мы опишем алгоритм Винберга, следуя [20]. Выберем произвольную точку 0 ∈ ℍ , которую будемназывать базисной. Фундаментальная область 0 её стабилизатора 0 — это многогранный конус в ℍ . Пусть 1 , … , — грани этого конуса, а 1 , … , — внешниенормали к ним. Определим полупространства− = { ∈ ,1 ∶ (, ) ≤ 0}.Тогда 0 = ⋂=1 − .Существует единственный фундаментальный многогранник группы , содержащийся в 0 и содержащий точку 0 . Его грани, содержащие 0 , образованы гранями конуса 1 , … , . Поиск остальных граней +1 , … и соответствующих внешнихнормалей +1 , … осуществляется по индукции. А именно, в качестве берётся такое зеркало, что ортогональный ему вектор удовлетворяет условиям1) (0 , ) < 0;2) ( , ) ≤ 0 для всех < ;3) расстояние (0 , ) минимально при выполнении условий 1) и 2).Если же = () для некоторой решетки , то нормали являются корнямиэтой решётки.Длины корней { } удовлетворяют следующему полезному условию.Предложение 3.1.1.

(Винберг, 1984, см. [23]) Скалярные квадраты корней в квадратичной решётке являются делителями удвоенного последнего инвариантного множителя решётки .Алгоритм Винберга завершает работу, если на каком-то шаге получается многогранник Кокстера конечного объема.393.2. Компьютерные реализации алгоритма ВинбергаПопытки реализовать на компьютере алгоритм Винберга предпринимались с 80х годов прошлого века, но все они ограничивались решётками частного вида, какправило, имеющими ортогональный базис. Упоминания о таких программах можновстретить, к примеру, в работах В.

О. Бугаенко (1992, см. [17]), Р. Шарлау и К. Вальхорн (1992, см. [58]), В. В. Никулина (2000, см. [51]) и Д. Аллкока (2011, см. [4]). Носами программы не были опубликованы, за исключением работы В. В. Никулина,в которой приведён код программы для решёток нескольких частных видов. Единственной известной реализацией, опубликованной вместе с подробной документацией, является программа Р. Гульельметти 2016 года1 , работающая с решётками,имеющими ортогональный базис, инвариантые множители которых свободны от квадратов. Р.

Гульельметти применял её в своей диссертации для классификации рефлективных решёток с ортогональным базисом, элементы которого имеют малые длины(2017, см. [29]). Эта программа работает эффективно во всех размерностях, где существуют рефлективные решётки.В данной работе представлена собственная реализация (проект VinAl) алгоритмаВинберга для произвольных гиперболических решёток без каких-либо ограничений.Программа, написанная в 2017 году совместно с А. Ю.

Перепечко, опубликована вИнтернете (см. [12]), а её подробное описание доступно в статье [63]. Программабыла проверена на значительном количестве известных рефлективных гиперболических решёток.3.3. Основные шаги программы VinAl и вспомогательные результаты3.3.1. Выбор базисной точкиНа вход программа получает квадратную матрицу размера +1, задающую скалярное умножение сигнатуры (, 1) в гиперболической решётке = [] (здесь []обозначает квадратичную решётку со скалярным умножением, заданным в некотором базисе симметричной матрицей ). Программа находит такую замену координат над ℚ, что в новых координатах матрица скалярного произведения — диагональная с отрицательным первым диагональным элементом.

В качестве базисной точки0 берётся примитивный вектор решётки, пропорциональный первому вектору нового базиса.1см. проект AlVin https://rgugliel.github.io/AlVin403.3.2. Построение фундаментального конусаПусть 0 принадлежит -мерной грани фундаментального конуса группы ()0 ,1 ⩽ ⩽ . Поскольку внешние нормали 1 , … , к граням фундаментального конуса перпендикулярны к 0 в пространстве ,1 , то они лежат в евклидовом пространстве 1 = ⟨0 ⟩⟂ . Но по предложению 3.1.1 их длины ограничены, их число конечно,и мы можем их найти с помощью сопрограммы, которая описана в пункте 3.3.5 данной статьи. В частности, порождённая этими нормалями группа отражений ()0конечна, то есть является эллиптической группой Кокстера ранга .Построение фундаментального конуса происходит следующим образом.

В начале берём конус , равный всему пространству , а затем выполняем последовательно для каждого корня в 1 следующую процедуру: если зеркало данного корня пересекает внутренность , то заменяем конус на его пересечение с полупространством − = { ∣ (, ) ⩽ 0}. Это конечная процедура, выдающая в качестве фундаментальную область группы ()0 .3.3.3. Разложение корней решёткиПредложение 3.3.1.

Решётка ′ = ( ∩ 1 ) ⊕ ℤ0 является подрешёткой конечногоиндекса в решётке , причём /′ является циклической группой, порядок которой =|/′ | является делителем числа (0 , 0 ).Доказательство. Образ всякого элемента решетки при факторизации по ′ однозначно определяется скалярным произведением с вектором 0 по модулю (0 , 0 ).■Следствие 3.3.1.

Cуществуют такие векторы 1 , … , ∈ , что = ⨆=1 ( +′ ).В частности, все векторы ∈ единственным образом записываются в виде =0 0 + 1 + , где 0 ∈ ℤ, 1 ∈ ∩ 1 , 1 ⩽ ⩽ .Выпишем условие 3) минимальности расстояния алгоритма Винберга в полученном разложении. Обозначая = (0 , 0 ) ∈ ℤ<0 , = (, ), получаем:sh ( , 0 ) =|(, 0 )|√(, )(0 , 0 )=|0 + ( , 0 )|√.Значит, расстояние от зеркала до базисной точки определяется целым числом 0 ,компонентой и длиной самого корня .

Но длина корня (см. предложение 1) и номер компоненты допускают конечное число вариантов. Таким образом, все корниразбиваются на подмножества, задаваемые тройками (0 , , ), на которых мы задаём линейный порядок по расстоянию от зеркала до точки 0 .413.3.4. Вывод корнейПосле того как фундаментальный многогранный конус найден, программа перебирает корни согласно введённому выше линейному порядку на тройках (0 , , ).Для каждой тройки вектор определяется компонентой 1 ∈ 1 из условия (, ) = и находится с помощью сопрограммы из пункта 3.3.5.

Поэтому для каждой тройкипоиск корня, подходящего под условия 1) и 2), происходит за конечное время. Найденный корень будет удовлетворять условию 3) в силу порядка на тройках.Каждый раз, когда найден очередной корень , программа добавляет его к системе предыдущих корней и проверяет, является ли система корней (1 , … , ) системой внешних нормалей многогранника Кокстера конечного объёма. Для проверкиконечности объёма известно несколько программ, в частности, программа В. О. Бугаенко, а также используемая нами программа2 Р. Гульельметти (см.

статью [28]).Таким образом, программа последовательно выводит корни, являющиеся внешними нормалями искомого многогранника . Если на каком-то шаге они задают многогранник конечного объёма, то программа заканчивает работу.3.3.5. Подпрограмма решения квадратичных диофантовых уравненийПрактически вся вычислительная сложность алгоритма Винберга заключается впоиске решений квадратичного диофантова уравнения вида + + = 0, где — положительно определённая целочисленная симметричная матрица порядка , — целочисленная строка длины , = (1 , … , ) — строка неизвестных, ∈ ℤ.В нашем проекте данная задача решена с помощью Python-сопрограммы, действующей индукцией по .

А именно, поскольку решения лежат на некотором эллипсоиде, может принимать лишь конечное число целых значений. Подпрограмма находитих при помощи метода сопряжённых градиентов и для каждого значения сводитк ( − 1)-мерной задаче в гиперплоскости { = const}. При = 1 подпрограмманаходит целочисленные корни квадратного трёхчлена.3.4. Программа для решеток над ℤ[√2]Для классификации устойчиво рефлективных решеток над ℤ[√2] возникла необходимость написаит программу, которую надо немного переделывать для каждойновой решетки.

В дальнейшем планируется совместно с А.Ю. Перепечко сделать этупрограмму такой же универсальной, как и проект VinAl для решёток над ℤ. Более того, планируется осуществить слияние этих программ в единый проект, реализующийалгоритм Винберга для решеток над квадратичными полями ℤ[√].2См. проект CoxIter: https://github.com/rgugliel/CoxIter42Текущая версия программы работает довольно просто.