双対格子

同義語:逆格子dual latticereciprocal lattice

概要

双対格子(dual lattice)とは、内積をもつ有限次元実ベクトル空間の格子 $L$ に対し、$L$ のすべての元との内積が整数になるベクトルの全体 $L^\ast$ のことである。$L^\ast$ は双対基底を基底とする格子で、$L$ を細かくすると $L^\ast$ は同じ指数だけ粗くなる。部分空間と格子の共通部分がその部分空間を張るとき、その双対は $L^\ast$ の直交射影で得られ、$A_n$ 型の格子では双対との商が位数 $n+1$ の巡回群になる。原始的な双対ベクトルは格子の点を乗せる平行な超平面の族に対応し、$n$ 次元で逐次最小について $\lambda_1(L)\lambda_n(L^\ast)\ge1$ と $\lambda_1(L)\lambda_1(L^\ast)\le n$ が成り立つ(移行定理)。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 格子(群), 内積, 双対基底

双対格子(dual lattice)とは、内積をもつ有限次元実ベクトル空間 $V$ の格子 $L$ に対して、$L$ のすべての元との内積が整数になるベクトルの全体
$$ L^\ast=\{y\in V\mid\text{すべての }x\in L\text{ について }\langle y,x\rangle\in\mathbb{Z}\} $$
のことである。逆格子(reciprocal lattice)ともいう(結晶学や物理では、内積が $2\pi\mathbb{Z}$ に入るように $2\pi$ 倍した $2\pi L^\ast$ を逆格子とよぶことが多い)。$L^\ast$ はふたたび格子で、$L$ の基底の双対基底を基底にもち、$(L^\ast)^\ast=L$、基本領域の体積は $\operatorname{covol}(L^\ast)=\operatorname{covol}(L)^{-1}$ である(格子(群) の命題「双対格子」)。
双対格子の元 $y$ は、関数 $x\mapsto\langle y,x\rangle$ が $L$ の上で整数値をとるような線形関数を表す。したがって $y\ne0$ を固定すると、$L$ は平行な超平面の族 $\{\langle y,x\rangle=k\}$($k\in\mathbb{Z}$)の上に乗る。この見方から、$L$ の短いベクトルと $L^\ast$ の短いベクトルの間の不等式(移行定理)が出てくる。また $L^\ast$ は円周群への指標の空間でもあり、Fourier 解析では $L$ の上の和を $L^\ast$ の上の和に取り替える Poissonの和公式 に現れる。
双対基底・Gram 行列・判別式による $L^\ast$ の計算は 格子(群) と 格子(数論) の記事にある(後者は不定値のものも含む非退化な対称双線形形式について同じ式で双対格子を定め、定理「双対格子と判別式」で整な格子の判別式群 $L^\ast/L$ を扱う)。体の拡大のトレース形式 $\operatorname{Tr}(xy)$ について同じ形で定める双対は トレース双対格子 で扱う。そこでは係数を Noether 正規整域(差積と分岐 では数体の整数環)にとり、トレース形式の正定値性も仮定しないので、この記事の双対格子とは別の対象である。この記事では、包含と指数、和と共通部分、部分空間の格子の双対と射影、超平面による解釈、移行定理を証明し、$A_n$ 型の格子などの双対を計算する。

定義

以下、$V$ は内積 $\langle\ ,\ \rangle$ をもつ $n$ 次元実ベクトル空間($n\ge1$)、$\|y\|=\sqrt{\langle y,y\rangle}$ とする。$V$ の 格子 とは、$V$ の基底 $v_1,\dots,v_n$ によって $L=\mathbb{Z}v_1+\cdots+\mathbb{Z}v_n$ と書ける部分群のことであり(格子(群) の定義「格子」)、基本平行体の体積を $\operatorname{covol}(L)$ と書く。

双対格子

$V$ の格子 $L$ に対し
$$ L^\ast:=\{y\in V\mid\text{すべての }x\in L\text{ について }\langle y,x\rangle\in\mathbb{Z}\} $$
を $L$ の 双対格子 という。$y\in L^\ast$ が 原始的 であるとは、$y\ne0$ であり、$2$ 以上の整数 $k$ で $y/k\in L^\ast$ となるものがないことをいう。

$v_1,\dots,v_n$ の双対基底 $w_1,\dots,w_n$($\langle w_j,v_i\rangle=\delta_{ij}$)は $L^\ast$ の基底である。$V=\mathbb{R}^n$(標準内積)で基底を列に並べた行列を $B$ とすると、$L^\ast$ の基底を並べた行列は $(B^{\mathsf T})^{-1}$ である。これらは 格子(群) の命題「双対格子」の内容で、Pei16 p. 7、Reg09 pp. 15–16 にも同じ記述がある。
定義の式は $V$ の任意の部分集合 $S$ について意味をもつので、格子でない部分群 $S$ についても同じ式で $S^\ast$ と書く(たとえば $\{0\}^\ast=V$)。$S$ が格子でなければ $S^\ast$ は格子とは限らない(下の「反例」の節)。
$y\in L^\ast$ に、$L$ 上の準同型 $x\mapsto\langle y,x\rangle$ を対応させる写像 $L^\ast\to\operatorname{Hom}(L,\mathbb{Z})$ は同型である(双対基底は $\operatorname{Hom}(L,\mathbb{Z})$ の双対基底に写る)。内積を使わずに $\operatorname{Hom}(L,\mathbb{Z})$ を双対格子とよぶ流儀もあり、内積があるときは両者をこの同型で同一視する。
$V$ の部分空間 $W$ の格子($W$ の基底で生成される部分群)についても、$W$ に内積を制限して $W$ の中で双対格子を考える。このとき双対格子は $W$ の部分集合であり、どの空間の中で考えるかを明示する(thm-dl-projection)。

包含・指数・演算

双対格子の基本性質

$L,M$ を $V$ の格子とする。

  1. $M\subset L$ ならば $L^\ast\subset M^\ast$ であり、$[M^\ast:L^\ast]=[L:M]$ である。
  2. $c\in\mathbb{R}\setminus\{0\}$ について $(cL)^\ast=c^{-1}L^\ast$ である。$V=\mathbb{R}^n$ で $A\in\operatorname{GL}_n(\mathbb{R})$ なら $(AL)^\ast=(A^{\mathsf T})^{-1}L^\ast$ であり、とくに $A$ が直交行列なら $(AL)^\ast=AL^\ast$ である。
  3. $V=V_1\oplus V_2$ が直交直和で、$L_i$ が $V_i$ の格子なら、$(L_1\oplus L_2)^\ast=L_1^\ast\oplus L_2^\ast$ である($L_i^\ast$ は $V_i$ の中の双対格子)。
  4. $L\cap M$ が $V$ の格子($n$ 個の一次独立な元を含む)ならば、$L+M$ も格子であり、
    $$ (L+M)^\ast=L^\ast\cap M^\ast,\qquad(L\cap M)^\ast=L^\ast+M^\ast $$
    が成り立つ。
定義と体積の比較

要点:1 は体積の比で指数を測る。2・3 は定義の書き換え、4 は 1 で $L+M$ を格子 $(ab)^{-1}(L\cap M)$ に押し込み、双対を 2 回とる。

詳しい証明を開く

1:$y\in L^\ast$ は $L$ の元との内積が整数なので、$L$ の部分集合 $M$ の元との内積も整数であり、$y\in M^\ast$ である。$L^\ast\subset M^\ast$ はともに格子なので、格子(群) の定理「部分格子の指数と体積」により $[M^\ast:L^\ast]=\operatorname{covol}(L^\ast)/\operatorname{covol}(M^\ast)=\operatorname{covol}(M)/\operatorname{covol}(L)=[L:M]$ である。

2:$y\in(cL)^\ast$ は、すべての $x\in L$ で $\langle cy,x\rangle\in\mathbb{Z}$、すなわち $cy\in L^\ast$ と同値である。同様に $\langle y,Ax\rangle=\langle A^{\mathsf T}y,x\rangle$ なので、$y\in(AL)^\ast$ は $A^{\mathsf T}y\in L^\ast$ と同値である。直交行列では $(A^{\mathsf T})^{-1}=A$ である。

3:$y=y_1+y_2$($y_i\in V_i$)と書く。$x_1\in L_1$ について $\langle y,x_1\rangle=\langle y_1,x_1\rangle$ なので、$y\in(L_1\oplus L_2)^\ast$ ならば $y_1\in L_1^\ast$、同様に $y_2\in L_2^\ast$ である。逆は $\langle y,x_1+x_2\rangle=\langle y_1,x_1\rangle+\langle y_2,x_2\rangle$ から従う。

4:$N:=L\cap M$ とおく。1 の指数の有限性により $a:=[L:N]$、$b:=[M:N]$ は有限で、$aL\subset N$、$bM\subset N$ である。よって $ab(L+M)\subset N$、すなわち $L\subset L+M\subset(ab)^{-1}N$ である。$(ab)^{-1}N$ は格子で、その部分群は離散であり(格子(群) の補題「有界集合に含まれる点の有限性」)、$L$ を含むので $n$ 個の一次独立な元を含む。格子(群) の定理「格子であるための条件」により $L+M$ は格子である。$(L+M)^\ast=L^\ast\cap M^\ast$ は定義からただちに従う($y$ が $L$ と $M$ の元との内積が整数なら $L+M$ の元とも整数)。とくに $L^\ast\cap M^\ast$ は格子 $L+M$ の双対なので格子である。したがって $L^\ast,M^\ast$ に前半を当てると $L^\ast+M^\ast$ は格子で、$(L^\ast+M^\ast)^\ast=L^{\ast\ast}\cap M^{\ast\ast}=L\cap M$ である。両辺の双対をとると $L^\ast+M^\ast=(L\cap M)^\ast$ を得る。$\square$

1 は「格子を細かくすると双対は粗くなり、その比は同じ」ことを述べている。たとえば $M=2\mathbb{Z}\subset L=\mathbb{Z}$ では $L^\ast=\mathbb{Z}\subset M^\ast=\frac12\mathbb{Z}$ で、指数はどちらも $2$ である。整な格子 $L$($L\subset L^\ast$)では、同じ体積の比較から $[L^\ast:L]=\operatorname{covol}(L)/\operatorname{covol}(L^\ast)=\operatorname{covol}(L)^2$ が出る。これは判別式群の位数が判別式の絶対値に等しいこと(格子(数論) の定理「双対格子と判別式」の 2)の言い換えである。

例

双対格子の計算
  1. $\mathbb{Z}^n$ は自分自身の双対格子である。長方形の格子 $\bigoplus_i a_i\mathbb{Z}e_i$($a_i>0$)の双対格子は $\bigoplus_i a_i^{-1}\mathbb{Z}e_i$ である(prop-dl-basic の 2・3)。
  2. 六方格子:$\mathbb{R}^2$ で $v_1=(1,0)$、$v_2=(\frac12,\frac{\sqrt3}{2})$ が生成する格子 $H$(正三角形の格子)を考える。双対基底は $w_1=(1,-\frac{1}{\sqrt3})$、$w_2=(0,\frac{2}{\sqrt3})$ である。$\|w_1\|=\|w_2\|=\frac{2}{\sqrt3}$ で、$w_1,w_2$ のなす角は $120^\circ$ なので、$H^\ast$ も正三角形の格子である。より正確には $R$ を $-30^\circ$ の回転とすると $Rv_1=\frac{\sqrt3}{2}w_1$、$Rv_2=\frac{\sqrt3}{2}(w_1+w_2)$ となり、$H^\ast=\frac{2}{\sqrt3}RH$ である。六方格子は、回転と拡大を除いて自分の双対と一致する。
  3. 長方形でない平行四辺形:$v_1=(1,0)$、$v_2=(1,1)$ が生成する格子は $\mathbb{Z}^2$ そのものなので双対は $\mathbb{Z}^2$ だが、$v_1=(1,0)$、$v_2=(1,2)$ の格子 $L$ では双対基底が $w_1=(1,-\frac12)$、$w_2=(0,\frac12)$ で、$L^\ast=\mathbb{Z}(1,-\frac12)+\mathbb{Z}(0,\frac12)$ である。$[\mathbb{Z}^2:L]=2$、$[L^\ast:\mathbb{Z}^2]=2$ で、prop-dl-basic の 1 と合う。
2・3 の確かめを開く

2:$\langle w_1,v_1\rangle=1$、$\langle w_1,v_2\rangle=\frac12-\frac12=0$、$\langle w_2,v_1\rangle=0$、$\langle w_2,v_2\rangle=1$ である。$\langle w_1,w_2\rangle=-\frac23$ で $\|w_1\|\|w_2\|=\frac43$ なので、角の余弦は $-\frac12$ である。$R(x,y)=(\frac{\sqrt3}{2}x+\frac12y,\,-\frac12x+\frac{\sqrt3}{2}y)$ より $Rv_1=(\frac{\sqrt3}{2},-\frac12)=\frac{\sqrt3}{2}w_1$、$Rv_2=(\frac{\sqrt3}{2},\frac12)$、$\frac{\sqrt3}{2}(w_1+w_2)=\frac{\sqrt3}{2}(1,\frac{1}{\sqrt3})=(\frac{\sqrt3}{2},\frac12)$ である。3:$\langle w_1,v_2\rangle=1-1=0$、$\langle w_2,v_2\rangle=1$ である。$L\subset\mathbb{Z}^2$ は $\operatorname{covol}(L)=2$ から指数 $2$ であり、$\mathbb{Z}^2\subset L^\ast$ は $e_1=w_1+w_2$、$e_2=2w_2$ から分かる。

部分空間の格子の双対と射影

格子 $\Lambda\subset V$ と部分空間 $W$ について、$\Lambda\cap W$ が $W$ を張るとき、$\Lambda\cap W$ は $W$ の格子である(離散部分群で $W$ を張るので、格子(群) の定理「格子であるための条件」)。その双対格子($W$ の中で考える)は、$\Lambda^\ast$ を $W$ へ直交射影すれば得られる。

部分空間の格子の双対は射影で得られる

$\Lambda$ を $V$ の格子、$W\subset V$ を部分空間、$p\colon V\to W$ を直交射影(直交射影)とし、$\Lambda_W:=\Lambda\cap W$ が $W$ を張ると仮定する。このとき、$W$ の中での $\Lambda_W$ の双対格子について
$$ (\Lambda_W)^\ast=p(\Lambda^\ast) $$
が成り立つ。

基底を延ばして双対基底を射影する

$k:=\dim W$ とする。$y\in\Lambda^\ast$、$x\in\Lambda_W$ について、$y-p(y)$ は $W$ に直交するので $\langle p(y),x\rangle=\langle y,x\rangle\in\mathbb{Z}$ である。よって $p(\Lambda^\ast)\subset(\Lambda_W)^\ast$ である。
逆向きを示す。まず $\Lambda/\Lambda_W$ は捩れをもたない。実際、$x\in\Lambda$ と整数 $m\ne0$ で $mx\in\Lambda_W$ なら、$mx\in W$ から $x\in W$、したがって $x\in\Lambda_W$ である。$\Lambda/\Lambda_W$ は有限生成で捩れをもたないので自由アーベル群である(有限生成アーベル群の構造定理)。自由加群への全射は分裂するので、$\Lambda_W$ の基底 $v_1,\dots,v_k$ に、$\Lambda/\Lambda_W$ の基底の持ち上げ $v_{k+1},\dots,v_n$ を加えたものは $\Lambda$ の基底である。その双対基底を $w_1,\dots,w_n$ とすると、$w_j\in\Lambda^\ast$ である。
$i,j\le k$ について $v_i\in W$ なので $\langle p(w_j),v_i\rangle=\langle w_j,v_i\rangle=\delta_{ij}$ である。$p(w_j)\in W$ で $v_1,\dots,v_k$ は $W$ の基底なので、$p(w_1),\dots,p(w_k)$ は $W$ の中での $v_1,\dots,v_k$ の双対基底であり、$(\Lambda_W)^\ast=\sum_{j\le k}\mathbb{Z}p(w_j)\subset p(\Lambda^\ast)$ である。$\square$

証明から、$j>k$ では $p(w_j)$ は $v_1,\dots,v_k$ のすべてと直交する $W$ の元なので $0$ である。したがって $p(\Lambda^\ast)$ は $p(w_1),\dots,p(w_k)$ で生成され、$p|_{\Lambda^\ast}\colon\Lambda^\ast\to(\Lambda_W)^\ast$ は全射で核の階数は $n-k$ である。

$A_n$ 型の格子の双対

$n\ge1$、$V=\mathbb{R}^{n+1}$、$\mathbf{1}=(1,\dots,1)$、$W=\{x\mid\langle x,\mathbf{1}\rangle=0\}$ とし、$A_n:=\mathbb{Z}^{n+1}\cap W$ とおく。$A_n$ は $e_i-e_{i+1}$($1\le i\le n$)を基底にもち、$W$ を張る。thm-dl-projection により、$W$ の中での双対格子は
$$ A_n^\ast=p(\mathbb{Z}^{n+1})=\sum_{i=1}^{n+1}\mathbb{Z}\,p(e_i),\qquad p(e_i)=e_i-\frac{1}{n+1}\mathbf{1} $$
である。$p(e_i)-p(e_1)=e_i-e_1\in A_n$ なので $A_n^\ast/A_n$ は $p(e_1)$ の類で生成される。$k\,p(e_1)=ke_1-\frac{k}{n+1}\mathbf{1}$ は $1\le k\le n$ では整数でない成分 $-\frac{k}{n+1}$ をもち $A_n$ に入らず、$(n+1)p(e_1)=(n+1)e_1-\mathbf{1}\in A_n$ である。よって
$$ A_n^\ast/A_n\cong\mathbb{Z}/(n+1)\mathbb{Z} $$
である。$\|p(e_1)\|^2=\frac{n}{n+1}$ で、$A_n$ のノルム最小の元 $e_i-e_j$ の長さの 2 乗は $2$ である。$n=2$ の $A_2$ は六方格子に相似で(ex-dl-examples の 2)、$A_2^\ast$ はその $\frac{1}{\sqrt3}$ 倍を回転したものである。

$A_n$ の基底の確かめを開く

$x\in A_n$ なら $x=\sum_{i=1}^{n}(x_1+\cdots+x_i)(e_i-e_{i+1})$ である。実際、右辺の第 $i$ 成分は $(x_1+\cdots+x_i)-(x_1+\cdots+x_{i-1})=x_i$($i\le n$)、第 $n+1$ 成分は $-(x_1+\cdots+x_n)=x_{n+1}$ である。$e_i-e_{i+1}$ は一次独立で $n=\dim W$ 個なので $W$ を張る。$n=2$ では $A_2$ の基底 $e_1-e_2$、$e_2-e_3$ の Gram 行列は $\begin{pmatrix}2&-1\\-1&2\end{pmatrix}$ で、六方格子の基底の Gram 行列 $\begin{pmatrix}1&\frac12\\\frac12&1\end{pmatrix}$ の $2$ 倍(基底の向きを 1 つ変えたもの)である。

$D_n$ の双対格子 $D_n^\ast=\mathbb{Z}^n\cup(h+\mathbb{Z}^n)$($h=(\frac12,\dots,\frac12)$)の計算は 格子(数論) の例「$D_n$ から作るユニモジュラー格子」にある。$E_8$ 格子は $E_8^\ast=E_8$ を満たす(E8格子)。

超平面の族としての双対格子

$y\in L^\ast$ を $0$ でない元とすると、$L$ のすべての点は、平行な超平面
$$ H_k:=\{x\in V\mid\langle y,x\rangle=k\}\qquad(k\in\mathbb{Z}) $$
のどれかに乗る。隣り合う超平面の距離は $1/\|y\|$ である。$y$ が原始的なら、どの $H_k$ も $L$ の点を含み、$L$ は「超平面 $H_0$ の中の格子」を層状に積み重ねたものになる。

原始的な双対ベクトルと格子超平面

$n\ge2$ とし、$L$ を $V$ の格子、$y\in L^\ast$ を原始的な元、$L_0:=\{x\in L\mid\langle y,x\rangle=0\}$ とする。

  1. $\{\langle y,x\rangle\mid x\in L\}=\mathbb{Z}$ である。とくにすべての $k\in\mathbb{Z}$ について $H_k\cap L\ne\emptyset$ である。
  2. $L_0$ は超平面 $y^\perp=H_0$ の格子である。
  3. $y^\perp$ の中での体積について $\operatorname{covol}(L_0)=\|y\|\operatorname{covol}(L)$ が成り立つ。
整数値の線形関数の核と高さ

$\varphi\colon L\to\mathbb{Z}$、$\varphi(x)=\langle y,x\rangle$ とおく。
1:$\varphi(L)$ は $\mathbb{Z}$ の部分群なので $d\mathbb{Z}$($d\ge0$)の形である。$L$ は $V$ を張り $y\ne0$ なので $\varphi\ne0$ で、$d\ge1$ である。すべての $x\in L$ で $\langle y/d,x\rangle\in\mathbb{Z}$ なので $y/d\in L^\ast$ であり、$y$ が原始的なので $d=1$ である。
2:$\varphi$ は全射なので、$u_n\in L$ を $\varphi(u_n)=1$ ととると $L=L_0\oplus\mathbb{Z}u_n$ である($x=(x-\varphi(x)u_n)+\varphi(x)u_n$)。$L_0$ は離散部分群 $L$ の部分群なので離散であり、格子(群) の定理「離散部分群の構造」により、$L_0$ が張る部分空間 $W_0$ の格子である。$L=L_0\oplus\mathbb{Z}u_n$ が $V$ を張るので $\dim W_0\ge n-1$ であり、$W_0\subset y^\perp$ なので $W_0=y^\perp$ である。
3:$L_0$ の基底 $u_1,\dots,u_{n-1}$ をとると、2 から $u_1,\dots,u_n$ は $L$ の基底である。$e:=y/\|y\|$ とし、$u_n=he+u'$($u'\in y^\perp$)と分けると $h=\langle e,u_n\rangle=1/\|y\|$ である。正規直交基底で $V=\mathbb{R}^n$ とみて、ベクトルを列に並べた行列式を考えると、$u_1,\dots,u_{n-1},u'$ は $(n-1)$ 次元の $y^\perp$ に入るので行列式は $0$ であり、多重線形性から
$$ \det(u_1,\dots,u_{n-1},u_n)=h\det(u_1,\dots,u_{n-1},e) $$
である。$(u_1,\dots,u_{n-1},e)$ の Gram 行列は $L_0$ の基底の Gram 行列 $G_0$ と $1$ のブロック対角行列なので、$\det(u_1,\dots,u_{n-1},e)^2=\det G_0=\operatorname{covol}(L_0)^2$ である。よって $\operatorname{covol}(L)=h\operatorname{covol}(L_0)=\operatorname{covol}(L_0)/\|y\|$ である。$\square$

$0$ でない $y\in L^\ast$ は、原始的な $y_0$ と正の整数 $d$ で $y=dy_0$ と一意に書ける($\{t\in\mathbb{R}\mid ty\in L^\ast\}$ は $1$ を含む $\mathbb{R}$ の離散部分群なので $t_0\mathbb{Z}$($t_0>0$)の形であり、$1=dt_0$ となる整数 $d\ge1$ について $y_0=t_0y$ とおく)。$\langle y,x\rangle=k$ は $\langle y_0,x\rangle=k/d$ と同じなので、$y_0$ の超平面の族は $y$ の族を $d$ 枚ごとに取り出したものであり、$y$ の族のうち残りの超平面には $L$ の点が乗らない。超平面の間隔は $1/\|y_0\|$ なので、$L$ の点を乗せる平行な超平面の族のうち間隔が最も広いものは、$L^\ast$ の最も短い $0$ でないベクトルに対応する。

平面の格子直線

$L=\mathbb{Z}^2$ と互いに素な整数 $a,b$ について $y=(a,b)$ は $L^\ast=\mathbb{Z}^2$ の原始的な元で、$\mathbb{Z}^2$ は直線 $ax+by=k$($k\in\mathbb{Z}$)の上に乗る。$L_0=\mathbb{Z}(-b,a)$ なので $\operatorname{covol}(L_0)=\sqrt{a^2+b^2}=\|y\|\cdot1$ であり、thm-dl-hyperplanes の 3 と一致する。$ax+by=1$ に整数解があることは 1 の特別な場合で、Bézout の等式にほかならない。

移行定理:$L$ と $L^\ast$ の短いベクトル

格子 $L$ と $1\le i\le n$ について、$L$ の一次独立な $i$ 個の元で、長さがすべて $r$ 以下のものがあるような $r$ の最小値を $\lambda_i(L)$ と書き、$L$ の第 $i$ 逐次最小 という。有界集合に含まれる格子の点は有限個なので(格子(群) の補題「有界集合に含まれる点の有限性」)、この最小値は存在し、$\lambda_1(L)\le\lambda_2(L)\le\cdots\le\lambda_n(L)$ である。$\lambda_1(L)$ は $L$ の $0$ でない元の長さの最小値である。

移行定理

$L$ を $V$ の格子とする。

  1. $1\le i\le n$ について $\lambda_i(L)\,\lambda_{n-i+1}(L^\ast)\ge1$ である。
  2. $\lambda_1(L)\,\lambda_1(L^\ast)\le n$ である。
内積の整数性と Minkowski の定理

1:$x_1,\dots,x_i\in L$ を一次独立で $\|x_a\|\le\lambda_i(L)$ となるもの、$y_1,\dots,y_{n-i+1}\in L^\ast$ を一次独立で $\|y_b\|\le\lambda_{n-i+1}(L^\ast)$ となるものとする。すべての $a,b$ で $\langle y_b,x_a\rangle=0$ だとすると、$y_1,\dots,y_{n-i+1}$ は $x_1,\dots,x_i$ が張る $i$ 次元部分空間の直交補空間($n-i$ 次元)に入り、一次独立であることに反する。よってある $a,b$ で $\langle y_b,x_a\rangle\ne0$ であり、これは整数なので、Cauchy–Schwarz の不等式から
$$ 1\le\lvert\langle y_b,x_a\rangle\rvert\le\|y_b\|\,\|x_a\|\le\lambda_{n-i+1}(L^\ast)\,\lambda_i(L) $$
である。
2:正規直交基底で $V=\mathbb{R}^n$ とみる。$c:=\operatorname{covol}(L)^{1/n}$ と $\varepsilon>0$ について、立方体 $K_\varepsilon=[-(1+\varepsilon)c,(1+\varepsilon)c]^n$ は原点について対称な凸集合で、体積は $2^n(1+\varepsilon)^n\operatorname{covol}(L)>2^n\operatorname{covol}(L)$ である。Minkowskiの凸体定理 の系「一般の格子に対する凸体定理」により、$K_\varepsilon$ は $L$ の $0$ でない点を含む。$K_1$ に含まれる $L$ の点は有限個なので、$0< \varepsilon\le1$ を $0$ に近づけるとき、そのうちの $1$ つの $0$ でない点 $x$ がいくらでも小さい $\varepsilon$ について $K_\varepsilon$ に入る。よって $x\in K_0$ で、各成分の絶対値が $c$ 以下なので $\|x\|\le\sqrt n\,c$ である。すなわち
$$ \lambda_1(L)\le\sqrt n\operatorname{covol}(L)^{1/n} $$
である。これを $L^\ast$ に当てると $\lambda_1(L^\ast)\le\sqrt n\operatorname{covol}(L)^{-1/n}$ であり(格子(群) の命題「双対格子」)、掛け合わせて 2 を得る。$\square$

1 で $i=1$ とすると $\lambda_1(L)\lambda_n(L^\ast)\ge1$ である。逆向きについては、Banaszczyk(1993)により $\lambda_1(L)\lambda_n(L^\ast)\le n$ が成り立つ(Reg09 Lemma 2.3、p. 16。この記事では証明しない)。$\lambda_1(L^\ast)\le\lambda_n(L^\ast)$ なので、これは 2 より強い。Banaszczyk の不等式は「$L$ に短いベクトルがないなら、$L^\ast$ に短いベクトルが一次独立に $n$ 本ある」という形であり(2 は同じ仮定から $L^\ast$ に短いベクトルが 1 本あることを述べる)、$L$ についての問題を $L^\ast$ についての問題に移す道具になる。格子暗号 の安全性の議論では、こうした移行が繰り返し使われる。

等号と大きさ
  1. $L=\mathbb{Z}^n$ では $L^\ast=\mathbb{Z}^n$、すべての $\lambda_i=1$ で、thm-dl-transference の 1 は等号である。
  2. $L=a\mathbb{Z}\oplus a^{-1}\mathbb{Z}\subset\mathbb{R}^2$($a>1$)では $L^\ast=a^{-1}\mathbb{Z}\oplus a\mathbb{Z}$ で、$\lambda_1(L)=\lambda_1(L^\ast)=a^{-1}$、$\lambda_2(L)=\lambda_2(L^\ast)=a$ である。$\lambda_1(L)\lambda_2(L^\ast)=1$ は 1 の等号で、$\lambda_1(L)\lambda_1(L^\ast)=a^{-2}$ はいくらでも小さくなる。$\lambda_1(L)\lambda_1(L^\ast)$ には正の下限がない。
  3. 六方格子 $H$(ex-dl-examples の 2)では $\lambda_1(H)=1$、$\lambda_1(H^\ast)=\frac{2}{\sqrt3}$ で、$\lambda_1(H)\lambda_1(H^\ast)=\frac{2}{\sqrt3}\approx1.155\le2$ である。

補足

  • 指標と Fourier 解析:$y\in L^\ast$ について $x\mapsto e^{2\pi i\langle y,x\rangle}$ は $L$ の上で $1$ なので、トーラス $V/L$ の指標を与える。$V/L$ の連続な指標はこの形のものに限り、$L^\ast$ は $V/L$ の Pontryagin双対 と同一視される。この対応により、$L$ の上の和を $L^\ast$ の上の和で表す Poissonの和公式 の定理「格子の Poisson の和公式」と、格子のテータ級数の変換則(テータ級数)が得られる。
  • 整な格子:$L\subset L^\ast$ となる格子(内積が $L$ の上で整数値)を整な格子といい、$L^\ast/L$ を判別式群という。$L=L^\ast$ のとき $L$ はユニモジュラーである(格子(数論)、判別式形式)。$\mathbb{Z}^n$、$E_8$ 格子、Leech格子 はユニモジュラーである。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
$L$ が $V$ を張る(格子の定義)$V=\mathbb{R}^2$、$L=\mathbb{Z}e_1$$L^\ast$ が格子であること
$L$ が離散(格子の定義)$V=\mathbb{R}$、$L=\mathbb{Z}+\sqrt2\,\mathbb{Z}$$(L^\ast)^\ast=L$
$L\cap M$ が格子(prop-dl-basic の 4)$V=\mathbb{R}$、$L=\mathbb{Z}$、$M=\sqrt2\,\mathbb{Z}$$(L\cap M)^\ast=L^\ast+M^\ast$
$\Lambda\cap W$ が $W$ を張る(thm-dl-projection)$\Lambda=\mathbb{Z}^2$、$W=\mathbb{R}(1,\sqrt2)$$(\Lambda\cap W)^\ast=p(\Lambda^\ast)$
$y$ が原始的(thm-dl-hyperplanes)$L=\mathbb{Z}^2$、$y=(2,0)$1 の $\langle y,L\rangle=\mathbb{Z}$ と 3 の体積の等式
反例の確かめ

各行で、外した条件以外は満たされている。

各行の確かめを開く

1 行目:$L=\mathbb{Z}e_1$ は離散部分群だが $\mathbb{R}^2$ を張らない。$y=(s,t)$ について $\langle y,me_1\rangle=ms$ なので $L^\ast=\mathbb{Z}\times\mathbb{R}$ で、これは離散でないので格子でない。2 行目:$L$ は $\mathbb{R}$ を張る部分群だが、$\sqrt2$ が無理数なので離散でない($\lvert a+b\sqrt2\rvert$ はいくらでも小さい正の値をとる)。$y\in L^\ast$ なら $y\in\mathbb{Z}$ かつ $\sqrt2y\in\mathbb{Z}$ で、$y\ne0$ なら $\sqrt2=(\sqrt2y)/y$ が有理数になるので $y=0$、すなわち $L^\ast=\{0\}$、$(L^\ast)^\ast=\mathbb{R}\ne L$ である。3 行目:$L,M$ は格子で、$L\cap M=\{0\}$($\sqrt2$ は無理数)は格子でない。$\{0\}$ の双対は $\mathbb{R}$ だが、$L^\ast+M^\ast=\mathbb{Z}+\frac{1}{\sqrt2}\mathbb{Z}$ は可算集合なので $\mathbb{R}$ でない。4 行目:$\Lambda$ は格子、$W$ は部分空間で、$(a,b)\in\mathbb{Z}^2$ が $W$ に入るのは $b=\sqrt2a$、すなわち $a=b=0$ のときだけなので $\Lambda\cap W=\{0\}$ は $W$ を張らない。$W$ の中での $\{0\}$ の双対は $W$ 全体だが、$p(\mathbb{Z}^2)$ は可算集合なので $W$ でない。5 行目:$y=(2,0)\in\mathbb{Z}^2=L^\ast$ は $0$ でないが、$y/2\in L^\ast$ なので原始的でない。$\langle y,L\rangle=2\mathbb{Z}$ で、$H_1=\{x_1=\frac12\}$ は $L$ の点を含まない。$L_0=\mathbb{Z}e_2$ で $\operatorname{covol}(L_0)=1$ だが、$\|y\|\operatorname{covol}(L)=2$ である。

関連項目

参考文献

[1]
Chris Peikert, A Decade of Lattice Cryptography, Foundations and Trends in Theoretical Computer Science, 2016, §2.2.1 The dual lattice(p. 7、双対格子の定義、$(\mathbb{Z}^n)^\ast=\mathbb{Z}^n$、$(cL)^\ast=c^{-1}L^\ast$、基底 $B^{-\mathsf{T}}$)。頁は著者公開版(2016 年 2 月 17 日版)による
[2]
Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM, 2009, §2(pp. 15–16、双対格子・双対基底・$\det(L^\ast)=1/\det(L)$)、Lemma 2.3(p. 16、Banaszczyk の移行定理 $1\le\lambda_1(L)\lambda_n(L^\ast)\le n$)。頁は著者公開版(2009 年 5 月 2 日版)による

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する