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

Конструкция, аналогичная конструкции дуального векторного пространства

В теории решеток дуальная решетка — это конструкция, аналогичная конструкции дуального векторного пространства . В некоторых отношениях геометрия дуальной решетки решетки является обратной геометрией , перспектива, которая лежит в основе многих ее применений. ${\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,v\cdot x\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} }$
• Пусть — решетка целочисленных векторов, координаты которых имеют четную сумму. Тогда , то есть, двойственной является решетка, порожденная целочисленными векторами вместе со всеми векторами s. ${\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}$

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

Каждое разбиение в соответствии с уровнями, соответствующими каждому из целочисленных значений. Меньший выбор создает уровни с большим расстоянием между ними; в частности, расстояние между слоями равно . Рассуждая таким образом, можно показать, что нахождение малых векторов в дает нижнюю границу наибольшего размера неперекрывающихся сфер, которые могут быть размещены вокруг точек . В общем случае теоремы, связывающие свойства решетки со свойствами ее двойственной решетки, известны как теоремы переноса. В этом разделе мы объясним некоторые из них, а также некоторые следствия для теории сложности. ${\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}$

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

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

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

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

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

Теорема  —  Теорема (суммирование Пуассона) ^[3] Пусть — хорошо себя ведущая функция, например, функция Шварца, и пусть обозначает ее преобразование Фурье . Пусть — решетка полного ранга. Тогда: ${\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. Банащик, В. (1993). «Новые границы в некоторых теоремах переноса в геометрии чисел». Mathematische Annalen . 296 (1). Springer Science and Business Media LLC: 625–635. doi :10.1007/bf01445125. ISSN  0025-5831. S2CID  13921988.
2. Cai, Jin-Yi; Nerurkar, Ajay (2000). «Заметка о не-NP-трудности приближенных решеточных задач при общих сокращениях Кука». Information Processing Letters . 76 (1–2): 61–66. doi :10.1016/S0020-0190(00)00123-X. MR  1797563.
3. Кон, Генри; Кумар, Абхинав; Рейхер, Кристиан; Шюрманн, Ахилл (2014). «Формальная двойственность и обобщения формулы суммирования Пуассона». Дискретная геометрия и алгебраическая комбинаторика . Contemporary Mathematics. Т. 625. С. 123–140. arXiv : 1306.6796v2 . doi : 10.1090/conm/625/12495. ISBN 9781470409050. S2CID  117741906.