Решетка (групповая)

В геометрии и теории групп — решетка в реальном координатном пространстве. $\mathbb {R} ^{n}$ представляет собой бесконечное множество точек в этом пространстве со свойствами, заключающимися в том, что сложение или вычитание двух точек в решетке по координатам создает еще одну точку решетки, что все точки решетки разделены некоторым минимальным расстоянием и что каждая точка в пространстве является на некотором максимальном расстоянии от точки решетки. Замыкание при сложении и вычитании означает, что решетка должна быть подгруппой аддитивной группы точек пространства, а требования минимального и максимального расстояния можно резюмировать, сказав, что решетка является множеством Делоне . Более абстрактно, решетку можно описать как свободную абелеву группу размерности $n$ который охватывает векторное пространство $\mathbb {R} ^{n}$ . На основе любой $\mathbb {R} ^{n}$ , подгруппа всех линейных комбинаций с целыми коэффициентами базисных векторов образует решетку, и таким образом каждая решетка может быть образована из базиса. Решетку можно рассматривать как регулярное замощение пространства примитивной ячейкой .

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

Соображения и примеры симметрии

Решетка — это группа симметрии дискретной трансляционной симметрии в n направлениях. Узор с этой решеткой трансляционной симметрии не может иметь больше, но может иметь меньшую симметрию, чем сама решетка. ^[1] Как группа (отбрасывающая свою геометрическую структуру) решетка представляет собой конечно порожденную свободную абелеву группу и, следовательно, изоморфна $\mathbb {Z} ^{n}$ .

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

Простой пример решетки в $\mathbb {R} ^{n}$ это подгруппа $\mathbb {Z} ^{n}$ . Более сложные примеры включают решетку E8 , которая представляет собой решетку в $\mathbb {R} ^{8}$ и решетка Лича в $\mathbb {R} ^{24}$ . периодов Решетка в $\mathbb {R} ^{2}$ занимает центральное место в изучении эллиптических функций , разработанных в математике девятнадцатого века; оно обобщается на более высокие измерения в теории абелевых функций . Решетки, называемые корневыми решетками, играют важную роль в теории простых алгебр Ли ; например, решетка E8 связана с алгеброй Ли, имеющей то же имя.

Разделение пространства по решетке

Решетка $\Lambda$ в $\mathbb {R} ^{n}$ таким образом, имеет вид

\Lambda ={\biggl \{}\sum _{i=1}^{n}a_{i}v_{i}\mathbin {\bigg \vert } a_{i}\in \mathbb {Z} {\biggr \}},

где { v ₁ , ..., v _n } — основа для $\mathbb {R} ^{n}$ . могут порождать одну и ту же решетку, но значение определителя абсолютное векторов vi _{Разные базисы} однозначно определяется соотношением $\Lambda$ и обозначается d( $\Lambda$ ). Если представить себе решетку, разделяющую все $\mathbb {R} ^{n}$ на равные многогранники (копии n -мерного параллелепипеда , известного как фундаментальная область решетки), то d( $\Lambda$ ) равен n -мерному объему этого многогранника. Вот почему д( $\Lambda$ ) иногда называют кообъемом решетки. Если оно равно 1, решетка называется унимодулярной .

Точки решетки в выпуклых множествах

Теорема Минковского связывает число d( $\Lambda$ ) и объём симметричного выпуклого множества S к числу точек решётки, содержащихся в S . Количество точек решетки, содержащихся в многограннике, все вершины которого являются элементами решетки, описывается многочленом Эрхарта многогранника . Формулы для некоторых коэффициентов этого полинома включают d( $\Lambda$ ) также.

Проблемы вычислительной решетки

Задачи о вычислительной решетке имеют множество приложений в информатике. Например, алгоритм сокращения базиса решетки Ленстры-Ленстры-Ловаса (LLL) использовался при криптоанализе многих схем шифрования с открытым ключом . ^[2] Известно , что многие криптографические схемы на основе решеток безопасны при условии, что некоторые задачи решетки сложны в вычислительном отношении . ^[3]

Решетки в двух измерениях: подробное обсуждение

Существует пять типов двумерных решеток, как указано в кристаллографической ограничительной теореме . Ниже группа обоев решетки представлена в обозначениях IUCr , обозначениях Орбифолда и обозначениях Кокстера , а также диаграмма обоев, показывающая области симметрии. Обратите внимание, что узор с этой решеткой трансляционной симметрии не может иметь больше, но может иметь меньшую симметрию, чем сама решетка. Полный список подгрупп доступен. Например, ниже дважды дана гексагональная/треугольная решетка с полной 6-кратной и половиной 3-кратной отражательной симметрией. Если группа симметрии узора содержит n -кратное вращение, то решетка имеет n -кратную симметрию для четных n и 2 n -кратную для нечетных n .

смм, (2*22), [∞,2 ⁺,∞]	п4м, (*442), [4,4]	п6м, (*632), [6,3]
ромбическая решетка также центрированная прямоугольная решетка равнобедренный треугольный	квадратная решетка правый равнобедренный треугольный	шестиугольная решетка (равносторонняя треугольная решетка)
пмм, *2222, [∞,2,∞]	p2, 2222, [∞,2,∞] ⁺	p3m1, (*333), [3 ^[3]]
прямоугольная решетка также центрированная ромбическая решетка правый треугольный	косая решетка разносторонний треугольный	равносторонняя треугольная решетка (шестиугольная решетка)

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

Пять случаев соответствуют треугольнику равностороннему, прямоугольному, прямоугольному, равнобедренному и разностороннему . В ромбической решетке кратчайшее расстояние может быть либо диагональю, либо стороной ромба, т. е. отрезок, соединяющий первые две точки, может быть, а может и не быть одной из равных сторон равнобедренного треугольника. Это зависит от того, составляет ли меньший угол ромба менее 60° или находится в диапазоне от 60° до 90°.

Общий случай известен как решетка периодов . Если векторы p и q порождают решетку, то вместо p и q мы также можем взять p и p - q и т. д. В общем, в 2D мы можем взять a p + b q и c p + d q для целых чисел a , b , c и d такие, что ad-bc равен 1 или -1. Это гарантирует, что p и q сами по себе являются целочисленными линейными комбинациями двух других векторов. Каждая пара p , q определяет параллелограмм, все с одинаковой площадью, величиной векторного произведения . Один параллелограмм полностью определяет весь объект. Без дополнительной симметрии этот параллелограмм является фундаментальным параллелограммом .

Фундаментальная область периодов решетки .

Векторы p и q могут быть представлены комплексными числами . С точностью до размера и ориентации пара может быть представлена их частным. Выражаясь геометрически: если две точки решетки равны 0 и 1, мы рассматриваем положение третьей точки решетки. Эквивалентность в смысле образования одной и той же решетки представлена модулярной группой : $T:z\mapsto z+1$ представляет собой выбор другой третьей точки в той же сетке, $S:z\mapsto -1/z$ представляет собой выбор другой стороны треугольника в качестве опорной стороны 0–1, что обычно подразумевает изменение масштаба решетки и ее вращение. Каждый «изогнутый треугольник» на изображении содержит для каждой формы двумерной решетки одно комплексное число, серая область представляет собой каноническое представление, соответствующее приведенной выше классификации, с двумя точками решетки 0 и 1, наиболее близкими друг к другу; дублирования можно избежать, включив только половину границы. Ромбические решетки представлены точками на ее границе, с шестиугольной решеткой в качестве вершины и i для квадратной решетки. Прямоугольные решетки находятся на воображаемой оси, а оставшаяся площадь представляет собой параллелограмматические решетки, причем зеркальное изображение параллелограмма представлено зеркальным изображением на воображаемой оси.

Решетки в трех измерениях

14 типов решеток в 3D называются решетками Браве . Они характеризуются своей пространственной группой . Трехмерные узоры с трансляционной симметрией определенного типа не могут иметь большей, но могут иметь меньшую симметрию, чем сама решетка.

Решетки в сложном пространстве

Решетка в $\mathbb {C} ^{n}$ является дискретной подгруппой $\mathbb {C} ^{n}$ который охватывает $\mathbb {C} ^{n}$ как реальное векторное пространство. Поскольку размерность $\mathbb {C} ^{n}$ как действительное векторное пространство равно $2n$ , решетка в $\mathbb {C} ^{n}$ будет свободной абелевой группой ранга $2n$ .

Например, гауссовы целые числа $\mathbb {Z} [i]=\mathbb {Z} +i\mathbb {Z}$ образовать решетку в $\mathbb {C} =\mathbb {C} ^{1}$ , как $(1,i)$ является основой $\mathbb {C}$ над $\mathbb {R}$ .

В группах Лжи

В более общем смысле решетка Γ в группе Ли G представляет собой дискретную подгруппу такую, что фактор G /Γ имеет конечную меру, поскольку мера на ней унаследована от меры Хаара на G (левоинвариантная или правоинвариантная - определение не зависит от этого выбора). Это, безусловно, будет иметь место, когда G /Γ компактна , но это достаточное условие не является необходимым, как показывает случай модулярной группы в SL ₂ ( R ) , которая является решеткой, но фактор не компактен. (у него есть выступы ). Имеются общие результаты, утверждающие существование решеток в группах Ли.

Решетка называется однородной или кокомпактной , если G /Γ компактна; в противном случае решетка называется неоднородной .

Решетки в общих векторных пространствах

Хотя мы обычно считаем $\mathbb {Z}$ решетки в $\mathbb {R} ^{n}$ эта концепция может быть обобщена на любое конечномерное векторное пространство над любым полем . Это можно сделать следующим образом:

Пусть K — поле , пусть — V n -мерное K - векторное пространство , пусть $B=\{\mathbf {v} _{1},\ldots ,\mathbf {v} _{n}\}$ — K - базис для V и пусть R — , содержащееся внутри K. кольцо Тогда R- решетка ${\mathcal {L}}$ в V, порожденном B, определяется следующим образом:

{\mathcal {L}}={\biggl \{}\sum _{i=1}^{n}a_{i}\mathbf {v} _{i}\mathbin {\bigg \vert } a_{i}\in R{\biggr \}}.

В общем, разные базы B будут порождать разные решетки. Однако если матрица перехода T между базисами находится в $\mathrm {GL} _{n}(R)$ - общая линейная группа R (просто говоря, это означает , что все элементы T находятся в R и все элементы $T^{-1}$ находятся в R , что эквивалентно утверждению, что определитель T находится в $R^{*}$ - единичная группа элементов в R с мультипликативными обратными), то решетки, порожденные этими базисами, будут изоморфными , поскольку T индуцирует изоморфизм между двумя решетками.

Важные случаи таких решеток встречаются в теории чисел, где K — p -адическое поле , а R — - p адические целые числа .

Для векторного пространства, которое также является пространством внутреннего произведения , двойственная решетка может быть конкретно описана множеством

{\mathcal {L}}^{*}=\{\mathbf {v} \in V\mid \langle \mathbf {v} ,\mathbf {x} \rangle \in R\,{\text{ for all }}\,\mathbf {x} \in {\mathcal {L}}\},

или эквивалентно как

{\mathcal {L}}^{*}=\{\mathbf {v} \in V\mid \langle \mathbf {v} ,\mathbf {v} _{i}\rangle \in R,\ i=1,...,n\}.

Связанные понятия

Примитивный элемент решетки — это элемент, который не является целым положительным числом, кратным другому элементу решетки. ^{[ нужна ссылка ]}

См. также

Примечания

^ «Симметрия в кристаллографических заметках» . xrayweb.chem.ou.edu . Проверено 6 ноября 2022 г.
^ Нгуен, Фонг; Стерн, Жак (2001). «Два лица решеток в криптологии». Криптография и решетки . Конспекты лекций по информатике. Том. 2146. стр. 146–180. дои : 10.1007/3-540-44670-2_12 . ISBN 978-3-540-42488-8 .
^ Регев, Одед (1 января 2005 г.). «О решетках, обучении с ошибками, случайных линейных кодах и криптографии». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений . СТОК '05. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 84–93. CiteSeerX 10.1.1.110.4776 . дои : 10.1145/1060590.1060603 . ISBN 978-1581139600 . S2CID 53223958 .

Ссылки

Конвей, Джон Хортон ; Слоан, Нил Дж. А. (1999), Сферические упаковки, решетки и группы , Основы математических наук, том. 290 (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-98585-5 , МР 0920369

Внешние ссылки

Каталог решеток (Небе и Слоана)

[1] «Симметрия в кристаллографических заметках» . xrayweb.chem.ou.edu . Проверено 6 ноября 2022 г.

[2] Нгуен, Фонг; Стерн, Жак (2001). «Два лица решеток в криптологии». Криптография и решетки . Конспекты лекций по информатике. Том. 2146. стр. 146–180. дои : 10.1007/3-540-44670-2_12 . ISBN 978-3-540-42488-8 .

[3] Регев, Одед (1 января 2005 г.). «О решетках, обучении с ошибками, случайных линейных кодах и криптографии». Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений . СТОК '05. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 84–93. CiteSeerX 10.1.1.110.4776 . дои : 10.1145/1060590.1060603 . ISBN 978-1581139600 . S2CID 53223958 .

[1]

[2]

[3]

v т и Кристаллические системы
Решетка Браве Кристаллографическая точечная группа
Семь 3D-систем	триклинный (анортикальный) моноклинический орторомбический четырехугольный тригональные и шестиугольные кубический (изометрический)
Четыре 2D-системы	косой прямоугольный квадрат шестиугольный