В геометрии и групповой теории , A решетки вявляется подгруппой аддитивной группыкоторая изоморфна аддитивной группеИ который пролеты реальное векторное пространство . Другими словами, для любой основе из, подгруппа всех линейных комбинаций с целыми коэффициентами базисных векторов образует решетку. Решетку можно рассматривать как правильную мозаику пространства примитивной ячейкой .
Решетки имеют много важных приложений в чистой математике, особенно в связи с алгебрами Ли , теорией чисел и теорией групп. Они также возникают в прикладной математике в связи с теорией кодирования , в криптографии из-за предполагаемой вычислительной сложности нескольких задач решетки и по-разному используются в физических науках. Например, в материаловедении и физике твердого тела решетка является синонимом «каркаса» кристаллической структуры , трехмерного массива регулярно расположенных точек, совпадающих в особых случаях с положениями атома или молекулы в кристалле. . В более общем плане решеточные модели изучаются в физике , часто с помощью методов вычислительной физики .
Соображения и примеры симметрии
Решетка - это группа симметрии дискретной трансляционной симметрии в n направлениях. Узор с этой решеткой трансляционной симметрии не может иметь больше, но может иметь меньшую симметрию, чем сама решетка. Как группа (отказавшись от своей геометрической структуры) решетка является конечно порожденной свободной абелевой группой и, таким образом, изоморфна.
Решетка в смысле трехмерного массива регулярно расположенных точек, совпадающих, например, с положениями атома или молекулы в кристалле , или, в более общем смысле, с орбитой действия группы при трансляционной симметрии, является трансляцией трансляционной решетки: класс смежности , который не обязательно должен содержать начало координат и, следовательно, не обязательно должен быть решеткой в предыдущем смысле.
Простой пример решетки в это подгруппа . Более сложные примеры включают решетку E8 , которая является решеткой в, а решетка пиявки в. Период решетки взанимает центральное место в изучении эллиптических функций , разработанных в математике девятнадцатого века; он обобщается на более высокие измерения в теории абелевых функций . Решетки, называемые корневыми решетками , важны в теории простых алгебр Ли ; например, решетка E8 связана с одноименной алгеброй Ли.
Разделение пространства по решетке
Типичная решетка в таким образом имеет вид
где { v 1 , ..., v n } - основа для. Различные основания могут генерировать такую же решетку, но абсолютное значение из определителя векторов v я однозначно определяется Л, и обозначается й (Л). Если думать о решетке как о делении всегона равные многогранники (копии n- мерного параллелепипеда , известного как фундаментальная область решетки), то d (Λ) равно n -мерному объему этого многогранника. Поэтому d (Λ) иногда называют коволомом решетки. Если это равно 1, решетка называется унимодулярной .
Точки решетки в выпуклых множествах
Теорема Минковского связывает число й (Л) и объем симметричного выпуклого множества S к числу точек решетки , содержащихся в S . Число точек решетки, содержащихся в многограннике, все вершины которого являются элементами решетки, описывается многочленом Эрхарта многогранника . Формулы для некоторых коэффициентов этого многочлена также содержат d (Λ).
Вычислительные решеточные задачи
Вычислительные решеточные задачи имеют множество приложений в информатике. Например, алгоритм редукции решеточного базиса Ленстры – Ленстры – Ловаса (LLL) использовался в криптоанализе многих схем шифрования с открытым ключом [1], и многие криптографические схемы на основе решеток, как известно, безопасны при предположении, что определенные решеточные задачи сложны в вычислительном отношении . [2]
Решетки в двух измерениях: подробное обсуждение
Согласно кристаллографической теореме ограничения существует пять типов двумерной решетки . Ниже группа обоев решетки дана в обозначениях IUC , Orbifold и Coxeter вместе с диаграммой обоев, показывающей области симметрии. Обратите внимание, что образец с этой решеткой трансляционной симметрии не может иметь больше, но может иметь меньшую симметрию, чем сама решетка. Полный список подгрупп имеется. Например, ниже шестиугольная / треугольная решетка дана дважды с полной 6-кратной и половиной 3-кратной отражательной симметрией. Если группа симметрии паттерна содержит n- кратное вращение, то решетка имеет n- кратную симметрию для четных n и 2 n -кратных для нечетных n .
cmm, (2 * 22), [∞, 2 + , ∞] | p4m, (* 442), [4,4] | p6m, (* 632), [6,3] |
---|---|---|
ромбическая решетка также центрированная прямоугольная решетка равнобедренная треугольная | квадратная решетка право равнобедренный треугольник | шестиугольная решетка (равносторонняя треугольная решетка) |
pmm, * 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, мы рассматриваем положение третьей точки решетки. Эквивалентность в смысле порождения одной и той же решетки представлена модулярной группой : представляет собой выбор другой третьей точки в той же сетке, представляет собой выбор другой стороны треугольника в качестве опорной стороны 0-1, что обычно подразумевает изменение масштаба решетки и ее поворот. Каждый «изогнутый треугольник» на изображении содержит для каждой формы двумерной решетки одно комплексное число, серая область - это каноническое представление, соответствующее приведенной выше классификации, с 0 и 1 двумя ближайшими друг к другу точками решетки; дублирования можно избежать, включив только половину границы. Ромбические решетки представлены точками на его границе с гексагональной решеткой в качестве вершины и i для квадратной решетки. Прямоугольные решетки расположены на мнимой оси, а оставшаяся область представляет собой параллелограмметические решетки, причем зеркальное отображение параллелограмма представлено зеркальным отображением на мнимой оси.
Решетки в трех измерениях
14 типов решеток в 3D называются решетками Браве . Они характеризуются своей космической группой . Трехмерные узоры с трансляционной симметрией определенного типа не могут иметь больше, но могут иметь меньшую симметрию, чем сама решетка.
Решетки в сложном пространстве
Решетка в дискретная подгруппа который охватывает как реальное векторное пространство. Как размер как реальное векторное пространство равно решетка в свободная абелева группа ранга .
Например, гауссовские целые числа сформировать решетку в , в виде является основой над .
В группах Ли
В более общем смысле решетка Γ в группе Ли G - это дискретная подгруппа , такая, что фактор-группа G / Γ имеет конечную меру для меры на ней, унаследованной от меры Хаара на G (левоинвариантной или правоинвариантной - определение не зависит от этого выбора). Это, безусловно, будет иметь место, когда G / Γ компактно , но это достаточное условие не является необходимым, как показывает случай модулярной группы в SL 2 ( R ) , которая является решеткой, но где фактор не компактный (имеет бугорки ). Имеются общие результаты о существовании решеток в группах Ли.
Решетка называется равномерной или кокомпактной, если G / Γ компактна; в противном случае решетка называется неоднородной .
Решетки в общих векторных пространствах
Хотя мы обычно рассматриваем решетки в это понятие может быть обобщено на любое конечномерное векторное пространство над любым полем . Это можно сделать следующим образом:
Пусть K будет поле , пусть V быть п - мерный K - векторное пространство , пустьбыть К - основа для V и пусть R будет кольцо содержится в K . Тогда R- решеткав V, порожденный B , задается следующим образом:
В общем, разные основания B будут порождать разные решетки. Однако, если матрица перехода T между основаниями находится в- линейная группа из R (в простых терминах это означает , что все элементы матрицы Т находятся в R и все элементы матрицыв R - что эквивалентно тому, что определитель из Т в- единичная группа элементов в R с мультипликативными обратными), то решетки, порожденные этими базами, будут изоморфными, поскольку T индуцирует изоморфизм между двумя решетками.
Важные случаи таких решеток встречаются в теории чисел, где K - p -адическое поле, а R - целые p -адические числа .
Для векторного пространства, которое также является внутренним пространством продукта , двойственная решетка может быть конкретно описана множеством
или эквивалентно как
Связанные понятия
- Примитивный элемент решетки - это элемент, который не является положительным целым числом, кратным другому элементу решетки. [ необходима цитата ]
Смотрите также
- Решетка (заказ)
- Решетка (модуль)
- Обратная решетка
- Унимодулярная решетка
- Кристаллическая система
- Теорема компактности Малера
- Решетчатый граф
- Криптография на основе решеток
Заметки
- ^ Нгуен, Фонг; Стерн, Жак (2001). Две стороны решеток в криптологии . Криптография и решетки . Конспект лекций по информатике. 2146 . С. 146–180. DOI : 10.1007 / 3-540-44670-2_12 . ISBN 978-3-540-42488-8.
- ^ Регев, Одед (01.01.2005). О решетках, обучении с ошибками, случайных линейных кодах и криптографии . Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений . STOC '05. Нью-Йорк, Нью-Йорк, США: ACM. С. 84–93. CiteSeerX 10.1.1.110.4776 . DOI : 10.1145 / 1060590.1060603 . ISBN 978-1581139600.
Рекомендации
- Конвей, Джон Хортон ; Слоан, Нил Дж. А. (1999), Сферические упаковки, решетки и группы , Grundlehren der Mathematischen Wissenschaften, 290 (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-98585-5, MR 0920369
Внешние ссылки
- Каталог решеток (Небе и Слоан)