二重格子

Construction analogous to that of a dual vector space

格子理論において、双対格子は双対ベクトル空間のそれに類似した構成である。ある点において、格子の双対格子の幾何学は の幾何学の逆数であり、この観点は多くの用途の根底にある。 ${\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} ).}$

しかし、双対は単なる抽象的なアーベル群の汎関数としてではなく、自然な内積 を伴うことに注意してください。ここで、は の直交基底です。（同様に、 の 直交基底に対して、 によって定義される双対ベクトル、 は直交基底であると宣言することもできます。）格子理論における双対性の重要な用途の1つは、主格子の幾何学とその双対の幾何学の関係であり、そのためにはこの内積が必要です。上記の具体的な記述では、双対の内積は一般に暗黙的です。 ${\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}}$
• 2つの格子を固定します 。その場合、 のときのみ となります。 ${\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)=\pm 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}\cup \left(\mathbb {Z} ^{n}+({\frac {1}{2}},\ldots ,{\frac {1}{2}})\right)}$ ${\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^{*})}}}$

定理 (Banaszczyk) ^[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. Banaszczyk, W. (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). 「ポアソン和公式の形式的双対性と一般化」.離散幾何学と代数的組合せ論. 現代数学. 第625巻. pp.  123– 140. arXiv : 1306.6796v2 . doi :10.1090/conm/625/12495. ISBN 9781470409050. S2CID  117741906。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Dual_lattice&oldid=1322471979"