二重格子

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

格子が短い非ゼロベクトル、つまりベクトル自体を持つという主張には、常に効率的に検証可能な証明があります。バナシュチクの転移定理の重要な系は であり、これは、格子に短いベクトルがないことを証明するために、短いベクトルからなる双対格子の基底を示すことができることを意味します。これらのアイデアを使用すると、格子の最短ベクトルを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^{*})}}}$

デュアル格子は、一般的なポアソン和公式の記述に使用されます。

• エーベリング、ヴォルフガング (2013)。 「格子とコード」。数学の上級講義。ヴィースバーデン: Springer Fachmedien Wiesbaden。土井：10.1007/978-3-658-00360-9。ISBN 978-3-658-00359-3. ISSN  0932-7134.