Jump to content

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

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

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

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

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

Позволять быть решеткой. То есть, для какой-то матрицы .

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

Если отождествляется с используя скалярное произведение , мы можем написать Важно векторами в диапазоне ограничиться , в противном случае полученный объект не является решеткой .

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

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

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

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

  • Если — матрица, дающая основу решетки , затем удовлетворяет .
  • Если — матрица, дающая основу решетки , затем дает основу для двойственной решетки. Если полный ранг дает основу для двойственной решетки: .
  • Предыдущий факт показывает, что . Это равенство выполняется при обычном отождествлении векторного пространства с его двойным двойником или в ситуации, когда внутренний продукт идентифицирует со своим двойником.
  • Починить две решетки . Затем тогда и только тогда, когда .
  • Определитель решетки является обратным определителю ее двойственной:
  • Если является ненулевым скаляром, тогда .
  • Если является матрицей вращения, тогда .
  • Решетка называется целым, если для всех . Предположим, что решетка является полным рангом. При отождествлении евклидова пространства с двойственным ему имеем для цельных решеток . Напомним, что если и , затем . Отсюда следует, что для целой решетки .
  • Целочисленная решетка называется унимодулярной, если , что, согласно вышеизложенному, эквивалентно

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

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

  • Двойник является .
  • Двойник является .
  • Позволять — решетка целочисленных векторов, координаты которых имеют четную сумму. Затем , то есть двойственная решетка — это решетка, порожденная целочисленными векторами вместе со всеми вектор 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 .

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

  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 .
  3. ^ Кон, Генри; Кумар, Абхинав; Райхер, Кристиан; Шюрманн, Ахилл (2014). «Формальная двойственность и обобщения формулы суммирования Пуассона». Дискретная геометрия и алгебраическая комбинаторика . Современная математика. Том. 625. стр. 123–140. arXiv : 1306.6796v2 . дои : 10.1090/conm/625/12495 . ISBN  9781470409050 . S2CID   117741906 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 49dde1b865028b50f410e40bb91a09d0__1717641600
URL1:https://arc.ask3.ru/arc/aa/49/d0/49dde1b865028b50f410e40bb91a09d0.html
Заголовок, (Title) документа по адресу, URL1:
Dual lattice - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)