Решетка (группа) - Lattice (group)

Не путать с частично заказанным набором, Решетка (заказ). Для других связанных применений см. Решетка (значения).

Решетка в Евклидова плоскость.

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

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

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

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

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

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

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

Типичная решетка ${\displaystyle \Lambda }$ в ${\displaystyle \mathbb {R} ^{n}}$ таким образом имеет вид

${\displaystyle \Lambda =\left\{\left.\sum _{i=1}^{n}a_{i}v_{i}\;\right\vert \;a_{i}\in \mathbb {Z} \right\}}$

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

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

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

Смотрите также: Целые точки в многогранниках

Вычислительные решеточные задачи

Основная статья: Решетка проблема

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

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

Пять решеток на евклидовой плоскости

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

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

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

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

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

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

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

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

Основная статья: Решетка Браве

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

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

Решетка в ${\displaystyle \mathbb {C} ^{n}}$ дискретная подгруппа ${\displaystyle \mathbb {C} ^{n}}$ который охватывает 2п-мерное реальное векторное пространство ${\displaystyle \mathbb {C} ^{n}}$. Например, Гауссовские целые числа сформировать решетку в ${\displaystyle \mathbb {C} ^{1}}$.

Каждая решетка в ${\displaystyle \mathbb {R} ^{n}}$ это свободная абелева группа из классифицировать п; каждая решетка в ${\displaystyle \mathbb {C} ^{n}}$ свободная абелева группа ранга 2п.

В группах Ли

Основная статья: Решетка (дискретная подгруппа)

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

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

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

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

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

${\displaystyle {\mathcal {L}}=\left\{\sum _{i=1}^{n}a_{i}\mathbf {v} _{i}\mid a_{i}\in R\right\}.}$

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

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

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

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

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

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

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

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

Смотрите также

• Решетка (заказ)
• Решетка (модуль)
• Обратная решетка
• Унимодулярная решетка
• Кристаллическая система
• Теорема компактности Малера
• Решетчатый граф
• Криптография на основе решеток

Примечания

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

Рекомендации

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

внешняя ссылка

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