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

По поводу двойников теоретико-порядковых решеток см. Двойственность (теория порядка).

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

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

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

Определение

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

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

${\displaystyle 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,x\cdot v\in \mathbb {Z} \}.}$ Важно ограничиться векторов в охватывать из ${\textstyle L}$, иначе полученный объект не будет решетка.

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

${\displaystyle 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 вектор.

q-арные решетки

Важный класс примеров, особенно в решеточной криптографии, дают q-ичные решетки. Для матрицы ${\textstyle A\in \mathbb {F} _{q}^{m\times n},}$ мы определяем ${\textstyle \Delta _{q}(A)=\{x\in \mathbb {Z} ^{n}:x\mod q\in A^{T}\mathbb {F} _{q}^{m}\},\Delta _{q}^{\perp }(A)=\{x\in \mathbb {Z} ^{n}:Ax=0\mod q\}}$; они называются, соответственно, образной и ядерной q-арными решетками, ассоциированными с ${\textstyle A}$. Тогда, отождествив евклидово пространство с двойственным ему, мы получаем, что образ и ядро ​​q-арной решетки матрицы ${\textstyle A}$ двойственны с точностью до скаляра. Особенно, ${\textstyle \Delta _{q}(A)^{*}={\frac {1}{q}}\Delta _{q}^{\perp }(A)}$ и ${\textstyle \Delta _{q}^{\perp }(A)^{*}={\frac {1}{q}}\Delta _{q}(A)}$.^{[нужна цитата ]} (Доказательство можно провести как упражнение.)

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

Каждый ${\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^{*})}}}$.

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

• ${\displaystyle 1\leq 2\lambda _{1}(L)\mu (L^{*})\leq n}$

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

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

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

• Отношения ${\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^{*})}}}$.

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

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

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

${\displaystyle \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.

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

1. Banaszczyk, W. (1993). «Новые оценки некоторых теорем переноса в геометрии чисел». Mathematische Annalen. ООО "Спрингер Сайенс энд Бизнес Медиа". 296 (1): 625–635. Дои:10.1007 / bf01445125. ISSN  0025-5831. S2CID  13921988.
2. Кон, Генри; Кумар, Абхинав; Райер, Кристиан; Шюрманн, Ахилл (2014). Формальная двойственность и обобщения формулы суммирования Пуассона. Современная математика AMS. Современная математика. 625. С. 123–140. arXiv:1306.6796v2. Дои:10.1090 / conm / 625/12495. ISBN  9781470409050. S2CID  117741906. Получено 2020-09-13.