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

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

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

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

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

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

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

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

Таким образом , типичная решетка имеет вид $\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 } — основа для . Разные базисы могут порождать одну и ту же решетку, но модуль определителя векторов vi однозначно определяется через Λ и обозначается d(Λ) _.Если рассматривать решетку как деление всего на равные многогранники (копии n -мерного параллелепипеда , известного как фундаментальная область решетки), то d(Λ) равна n -мерному объему этого многогранника. Поэтому d(Λ) иногда называют кообъемом решетки . Если оно равно 1, решетка называется унимодулярной . $\mathbb {R} ^{n}$ $\mathbb {R} ^{n}$

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

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

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

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

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

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

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

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

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

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

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

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

Важные случаи таких решеток встречаются в теории чисел, где 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.

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

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