Двойная решетка

В теории решеток двойственная решетка — конструкция, аналогичная конструкции двойственного векторного пространства . В некоторых отношениях геометрия двойственной решетки решетки ${\textstyle L}$ является обратной величиной геометрии ${\textstyle L}$ , точка зрения, которая лежит в основе многих его применений.

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

Статью с упором на приложения физики и химии см. в разделе Обратная решетка . В данной статье основное внимание уделяется математическому понятию двойственной решетки.

Определение [ править ]

Позволять ${\textstyle L\subseteq \mathbb {R} ^{n}}$ быть решеткой. То есть, ${\textstyle L=B\mathbb {Z} ^{n}}$ для какой-то матрицы ${\textstyle B}$ .

Двойственная решетка — это набор линейных функционалов на ${\textstyle L}$ которые принимают целые значения в каждой точке ${\textstyle L}$ :

L^{*}=\{f\in ({\text{span}}(L))^{*}:\forall x\in L,f(x)\in \mathbb {Z} \}.

Если ${\textstyle (\mathbb {R} ^{n})^{*}}$ отождествляется с ${\textstyle \mathbb {R} ^{n}}$ используя скалярное произведение , мы можем написать ${\textstyle L^{*}=\{v\in {\text{span}}(L):\forall x\in L,v\cdot x\in \mathbb {Z} \}.}$ Важно векторами в диапазоне ограничиться ${\textstyle L}$ , в противном случае полученный объект не является решеткой .

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

L^{*}=\{f:L\to \mathbb {Z} :{\text{f is a linear function}}\}={\text{Hom}}_{\text{Ab}}(L,\mathbb {Z} ).

Однако отметим, что двойственный не рассматривается просто как абстрактная абелева группа функционалов, а имеет естественный внутренний продукт: ${\textstyle f\cdot g=\sum _{i}f(e_{i})g(e_{i})}$ , где ${\textstyle e_{i}}$ является ортонормированным базисом ${\textstyle {\text{span}}(L)}$ . (Точно так же можно объявить, что для ортонормированного базиса ${\textstyle e_{i}}$ из ${\textstyle {\text{span}}(L)}$ , двойственные векторы ${\textstyle e_{i}^{*}}$ , определяемый ${\textstyle e_{i}^{*}(e_{j})=\delta _{ij}}$ являются ортонормированным базисом.) Одним из ключевых применений двойственности в теории решеток является связь геометрии первичной решетки с геометрией ее двойственной решетки, для чего нам нужен этот внутренний продукт. В конкретном описании, данном выше, внутренний продукт двойственного числа обычно подразумевается.

Свойства [ править ]

Перечислим некоторые элементарные свойства двойственной решетки:

Если ${\textstyle B=[b_{1},\ldots ,b_{n}]}$ — матрица, дающая основу решетки ${\textstyle L}$ , затем ${\textstyle z\in {\text{span}}(L)}$ удовлетворяет ${\textstyle z\in L^{*}\iff b_{i}^{T}z\in \mathbb {Z} ,i=1,\ldots ,n\iff B^{T}z\in \mathbb {Z} ^{n}}$ .
Если ${\textstyle B}$ — матрица, дающая основу решетки ${\textstyle L}$ , затем ${\textstyle B(B^{T}B)^{-1}}$ дает основу для двойственной решетки. Если ${\textstyle L}$ полный ранг ${\textstyle B^{-T}}$ дает основу для двойственной решетки: ${\textstyle z\in L^{*}\iff B^{T}z\in \mathbb {Z} ^{n}\iff z\in B^{-T}\mathbb {Z} ^{n}}$ .
Предыдущий факт показывает, что ${\textstyle (L^{*})^{*}=L}$ . Это равенство выполняется при обычном отождествлении векторного пространства с его двойным двойником или в ситуации, когда внутренний продукт идентифицирует ${\textstyle \mathbb {R} ^{n}}$ со своим двойником.
Починить две решетки ${\textstyle L,M}$ . Затем ${\textstyle L\subseteq M}$ тогда и только тогда, когда ${\textstyle L^{*}\supseteq M^{*}}$ .
Определитель решетки является обратным определителю ее двойственной: ${\textstyle {\text{det}}(L^{*})={\frac {1}{{\text{det}}(L)}}}$
Если ${\textstyle q}$ является ненулевым скаляром, тогда ${\textstyle (qL)^{*}={\frac {1}{q}}L^{*}}$ .
Если ${\textstyle R}$ является матрицей вращения, тогда ${\textstyle (RL)^{*}=RL^{*}}$ .
Решетка ${\textstyle L}$ называется целым, если ${\textstyle x\cdot y\in \mathbb {Z} }$ для всех ${\textstyle x,y\in L}$ . Предположим, что решетка ${\textstyle L}$ является полным рангом. При отождествлении евклидова пространства с двойственным ему имеем ${\textstyle L\subseteq L^{*}}$ для цельных решеток ${\textstyle L}$ . Напомним, что если ${\textstyle L'\subseteq L}$ и ${\textstyle |L/L'|<\infty }$ , затем ${\textstyle {\text{det}}(L')={\text{det}}(L)|L/L'|}$ . Отсюда следует, что для целой решетки ${\textstyle {\text{det}}(L)^{2}=|L^{*}/L|}$ .
Целочисленная решетка называется унимодулярной, если ${\textstyle L=L^{*}}$ , что, согласно вышеизложенному, эквивалентно ${\textstyle {\text{det}}(L)=1.}$

Примеры [ править ]

Используя перечисленные выше свойства, двойственную решетку можно эффективно рассчитать вручную или на компьютере.

Двойник ${\textstyle \mathbb {Z} ^{n}}$ является ${\textstyle \mathbb {Z} ^{n}}$ .
Двойник ${\textstyle 2\mathbb {Z} \oplus \mathbb {Z} }$ является ${\textstyle {\frac {1}{2}}\mathbb {Z} \oplus \mathbb {Z} }$ .
Позволять ${\textstyle L=\{x\in \mathbb {Z} ^{n}:\sum x_{i}=0\mod 2\}}$ — решетка целочисленных векторов, координаты которых имеют четную сумму. Затем ${\textstyle L^{*}=\mathbb {Z} ^{n}+({\frac {1}{2}},\ldots ,{\frac {1}{2}})}$ , то есть двойственная решетка — это решетка, порожденная целочисленными векторами вместе со всеми ${\textstyle 1/2}$ вектор s.

Теоремы переноса

Каждый ${\textstyle f\in L^{*}\setminus \{0\}}$ перегородки ${\textstyle L}$ согласно наборам уровней, соответствующим каждому из целочисленных значений. Меньший выбор ${\textstyle f}$ создавать наборы уровней с большим расстоянием между ними; в частности, расстояние между слоями ${\textstyle 1/||f||}$ . Рассуждая таким образом, можно показать, что нахождение малых векторов в ${\textstyle L^{*}}$ обеспечивает нижнюю границу наибольшего размера непересекающихся сфер, которые можно разместить вокруг точек ${\textstyle L}$ . В общем, теоремы, связывающие свойства решетки со свойствами ее двойственной решетки, известны как теоремы переноса. В этом разделе мы объясним некоторые из них, а также некоторые следствия для теории сложности.

Напомним некоторую терминологию. Для решетки ${\textstyle L}$ , позволять ${\textstyle \lambda _{i}(L)}$ обозначают шар наименьшего радиуса, содержащий набор ${\textstyle i}$ линейно независимые векторы ${\textstyle L}$ . Например, ${\textstyle \lambda _{1}(L)}$ длина кратчайшего вектора ${\textstyle L}$ . Позволять ${\textstyle \mu (L)={\text{max}}_{x\in \mathbb {R} ^{n}}d(x,L)}$ обозначаем радиус покрытия ${\textstyle L}$ .

В этих обозначениях нижняя граница, упомянутая во введении к этому разделу, гласит, что ${\textstyle \mu (L)\geq {\frac {1}{2\lambda _{1}(L^{*})}}}$ .

Теорема (Банащика) ^[1] — Для решетки ${\textstyle L}$ :

$1\leq 2\lambda _{1}(L)\mu (L^{*})\leq n$
$1\leq \lambda _{i}(L)\lambda _{n-i+1}(L^{*})\leq n$

Всегда существует эффективно проверяемый сертификат для утверждения о том, что решетка имеет короткий ненулевой вектор, а именно сам вектор. Важным следствием теоремы переноса Банажчика является то, что ${\textstyle \lambda _{1}(L)\geq {\frac {1}{\lambda _{n}(L^{*})}}}$ , из чего следует, что для доказательства отсутствия в решетке коротких векторов можно указать базис двойственной решетки, состоящий из коротких векторов. Используя эти идеи, можно показать, что аппроксимация кратчайшего вектора решетки с точностью до n раз ( ${\textstyle {\text{GAPSVP}}_{n}}$ проблема ) находится в ${\textstyle {\text{NP}}\cap {\text{coNP}}}$ . ^[2]

Другие теоремы переноса:

Отношения ${\textstyle \lambda _{1}(L)\lambda _{1}(L^{*})\leq n}$ следует из оценки Минковского на кратчайшем векторе ; то есть, ${\textstyle \lambda _{1}(L)\leq {\sqrt {n}}({\text{det}}(L)^{1/n})}$ , и ${\textstyle \lambda _{1}(L^{*})\leq {\sqrt {n}}({\text{det}}(L^{*})^{1/n})}$ , откуда следует утверждение, поскольку ${\textstyle {\text{det}}(L)={\frac {1}{{\text{det}}(L^{*})}}}$ .

Формула суммирования Пуассона

Двойственная решетка используется в формулировке общей формулы суммирования Пуассона.

Теорема — Теорема (суммирование Пуассона) ^[3]Позволять ${\textstyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ быть функцией с хорошим поведением , например функцией Шварца, и пусть ${\textstyle {\hat {f}}}$ обозначим его преобразование Фурье . Позволять ${\textstyle L\subseteq \mathbb {R} ^{n}}$ быть решеткой полного ранга. Затем:

\sum _{x\in L}f(x)={\frac {1}{\det(L)}}\sum _{y\in L^{*}}{\hat {f}}(y)

.

Дальнейшее чтение [ править ]

Эбелинг, Вольфганг (2013). Решетки и коды. Продвинутые лекции по математике . Висбаден: Springer Fachmedien Wiesbaden. дои : 10.1007/978-3-658-00360-9 . ISBN 978-3-658-00359-3 . ISSN 0932-7134 .

Ссылки [ править ]

^ Банащик, В. (1993). «Новые оценки в некоторых теоремах переноса в геометрии чисел». Математические Аннален . 296 (1). ООО «Спрингер Сайенс энд Бизнес Медиа»: 625–635. дои : 10.1007/bf01445125 . ISSN 0025-5831 . S2CID 13921988 .
^ Цай, Джин-И; Неруркар, Аджай (2000). «Заметка о не-NP-трудности приближенных решеточных задач при общих сокращениях Кука». Письма об обработке информации . 76 (1–2): 61–66. дои : 10.1016/S0020-0190(00)00123-X . МР 1797563 .
^ Кон, Генри; Кумар, Абхинав; Райхер, Кристиан; Шюрманн, Ахилл (2014). «Формальная двойственность и обобщения формулы суммирования Пуассона». Дискретная геометрия и алгебраическая комбинаторика . Современная математика. Том. 625. стр. 123–140. arXiv : 1306.6796v2 . дои : 10.1090/conm/625/12495 . ISBN 9781470409050 . S2CID 117741906 .

[Banaszczyk_1993_pp._625–635-1] Банащик, В. (1993). «Новые оценки в некоторых теоремах переноса в геометрии чисел». Математические Аннален . 296 (1). ООО «Спрингер Сайенс энд Бизнес Медиа»: 625–635. дои : 10.1007/bf01445125 . ISSN 0025-5831 . S2CID 13921988 .

[2] Цай, Джин-И; Неруркар, Аджай (2000). «Заметка о не-NP-трудности приближенных решеточных задач при общих сокращениях Кука». Письма об обработке информации . 76 (1–2): 61–66. дои : 10.1016/S0020-0190(00)00123-X . МР 1797563 .

[Cohn_Kumar_Reiher_Schürmann_2013-3] Кон, Генри; Кумар, Абхинав; Райхер, Кристиан; Шюрманн, Ахилл (2014). «Формальная двойственность и обобщения формулы суммирования Пуассона». Дискретная геометрия и алгебраическая комбинаторика . Современная математика. Том. 625. стр. 123–140. arXiv : 1306.6796v2 . дои : 10.1090/conm/625/12495 . ISBN 9781470409050 . S2CID 117741906 .

[1]

[2]

[3]