Двойная решетка
Алгебраическая структура → Теория групп Теория групп |
---|
![]() |
В теории решеток двойственная решетка — конструкция, аналогичная конструкции двойственного векторного пространства . В некоторых отношениях геометрия двойственной решетки решетки является обратной величиной геометрии , точка зрения, которая лежит в основе многих его применений.
Двойные решетки имеют множество приложений в теории решеток, теоретической информатике, криптографии и математике в более широком смысле. Например, он используется в формулировке формулы суммирования Пуассона , теоремы переноса обеспечивают связь между геометрией решетки и геометрией ее двойственной решетки, а многие алгоритмы решетки используют двойственную решетку.
Статью с упором на приложения физики и химии см. в разделе Обратная решетка . В данной статье основное внимание уделяется математическому понятию двойственной решетки.
Определение [ править ]
Позволять быть решеткой. То есть, для какой-то матрицы .
Двойственная решетка — это набор линейных функционалов на которые принимают целые значения в каждой точке :
Если отождествляется с используя скалярное произведение , мы можем написать Важно векторами в диапазоне ограничиться , в противном случае полученный объект не является решеткой .
Несмотря на такое отождествление объемлющих евклидовых пространств, следует подчеркнуть, что решетка и двойственная ей решетка представляют собой фундаментально разные виды объектов; один состоит из векторов в евклидовом пространстве , а другой — из набора линейных функционалов в этом пространстве. В этом духе можно дать и более абстрактное определение:
Однако отметим, что двойственный не рассматривается просто как абстрактная абелева группа функционалов, а имеет естественный внутренний продукт: , где является ортонормированным базисом . (Точно так же можно объявить, что для ортонормированного базиса из , двойственные векторы , определяемый являются ортонормированным базисом.) Одним из ключевых применений двойственности в теории решеток является связь геометрии первичной решетки с геометрией ее двойственной решетки, для чего нам нужен этот внутренний продукт. В конкретном описании, данном выше, внутренний продукт двойственного числа обычно подразумевается.
Свойства [ править ]
Перечислим некоторые элементарные свойства двойственной решетки:
- Если — матрица, дающая основу решетки , затем удовлетворяет .
- Если — матрица, дающая основу решетки , затем дает основу для двойственной решетки. Если полный ранг дает основу для двойственной решетки: .
- Предыдущий факт показывает, что . Это равенство выполняется при обычном отождествлении векторного пространства с его двойным двойником или в ситуации, когда внутренний продукт идентифицирует со своим двойником.
- Починить две решетки . Затем тогда и только тогда, когда .
- Определитель решетки является обратным определителю ее двойственной:
- Если является ненулевым скаляром, тогда .
- Если является матрицей вращения, тогда .
- Решетка называется целым, если для всех . Предположим, что решетка является полным рангом. При отождествлении евклидова пространства с двойственным ему имеем для цельных решеток . Напомним, что если и , затем . Отсюда следует, что для целой решетки .
- Целочисленная решетка называется унимодулярной, если , что, согласно вышеизложенному, эквивалентно
Примеры [ править ]
Используя перечисленные выше свойства, двойственную решетку можно эффективно рассчитать вручную или на компьютере.
- Двойник является .
- Двойник является .
- Позволять — решетка целочисленных векторов, координаты которых имеют четную сумму. Затем , то есть двойственная решетка — это решетка, порожденная целочисленными векторами вместе со всеми вектор s.
Теоремы переноса
Каждый перегородки согласно наборам уровней, соответствующим каждому из целочисленных значений. Меньший выбор создавать наборы уровней с большим расстоянием между ними; в частности, расстояние между слоями . Рассуждая таким образом, можно показать, что нахождение малых векторов в обеспечивает нижнюю границу наибольшего размера непересекающихся сфер, которые можно разместить вокруг точек . В общем, теоремы, связывающие свойства решетки со свойствами ее двойственной решетки, известны как теоремы переноса. В этом разделе мы объясним некоторые из них, а также некоторые следствия для теории сложности.
Напомним некоторую терминологию. Для решетки , позволять обозначают шар наименьшего радиуса, содержащий набор линейно независимые векторы . Например, длина кратчайшего вектора . Позволять обозначаем радиус покрытия .
В этих обозначениях нижняя граница, упомянутая во введении к этому разделу, гласит, что .
Теорема (Банащика) [1] — Для решетки :
Всегда существует эффективно проверяемый сертификат для утверждения о том, что решетка имеет короткий ненулевой вектор, а именно сам вектор. Важным следствием теоремы переноса Банажчика является то, что , из чего следует, что для доказательства отсутствия в решетке коротких векторов можно указать базис двойственной решетки, состоящий из коротких векторов. Используя эти идеи, можно показать, что аппроксимация кратчайшего вектора решетки с точностью до n раз ( проблема ) находится в . [2]
Другие теоремы переноса:
- Отношения следует из оценки Минковского на кратчайшем векторе ; то есть, , и , откуда следует утверждение, поскольку .
Формула суммирования Пуассона
Двойственная решетка используется в формулировке общей формулы суммирования Пуассона.
Теорема — Теорема (суммирование Пуассона) [3] Позволять быть функцией с хорошим поведением , например функцией Шварца, и пусть обозначим его преобразование Фурье . Позволять быть решеткой полного ранга. Затем:
- .
Дальнейшее чтение [ править ]
- Эбелинг, Вольфганг (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 .