ミンコフスキーの定理

数学において、ミンコフスキーの定理とは、における原点に関して対称であり、より大きい体積を持つすべての凸集合には、非ゼロの整数点（つまり、における原点ではない点）が含まれるという主張である。この定理は、1889 年にヘルマンミンコフスキーによって証明され、数の幾何学と呼ばれる数論の一分野の基礎となった。この定理は、整数からおよびより大きい体積を持つ任意の対称凸集合に拡張することができ、は格子の共体積（そのいずれかの基数の行列式の絶対値）を表す。 $\mathbb {R} ^{n}$ $2^{n}$ $\mathbb {Z} ^{n}$ $L$ $2^{n}\,d(L)$ $d(L)$

処方

$L が$ $n$ 次元実ベクトル空間の行列式 $d($ $L$ $)$ の格子であり、 $S が$ 原点に関して対称なの凸部分集合であるとします。つまり、 $x が$ $S$ に含まれる場合、 $-$ $x$ も $S$ に含まれるということです。ミンコフスキーの定理によれば、 $S$ の体積が $2$ $n$ $d($ $L$ $)$ よりも大きい場合、 $S$ には原点以外の格子点が少なくとも 1 つ含まれている必要があります。(集合 $S は$ $対称であるため、少なくとも 3 つの格子点、つまり原点 0 と 2 つの点\pm$ $x$ 、ただし $x$ $\in$ $L$ $\ 0$ が含まれます。) $\mathbb {R} ^{n}$ $\mathbb {R} ^{n}$

例

格子の最も単純な例は、整数係数を持つすべての点の整数格子です。その行列式は 1 です。 $n$ $= 2$ の場合、定理は、原点を中心に対称で面積が 4 より大きいユークリッド平面の凸図形は、原点に加えて少なくとも 1 つの格子点を囲むと主張しています。面積の境界は鋭く、つまり、 $S が$ $頂点(\pm1, \pm1)$ を持つ正方形の内部である場合、 $S は$ 対称かつ凸で、面積は 4 ですが、含まれる唯一の格子点は原点です。定理の境界が鋭いことを示すこの例は、すべての次元 $n$ の超立方体に一般化されます。 $\mathbb {Z} ^{n}$

証拠

以下の議論は、ミンコフスキーの定理を特定のケースで証明するものである。 $L=\mathbb {Z} ^{2}.$

証拠： ${\textstyle \mathbb {Z} ^{2}}$ 地図を考えてみます

f:S\to \mathbb {R} ^{2}/2L,\qquad (x,y)\mapsto (x{\bmod {2}},y{\bmod {2}})

直感的には、この写像は平面を 2 x 2 の正方形に切り分け、それらの正方形を積み重ねます。明らかに、 $f (S) の$ 面積は 4 以下です。これは、この集合が 2 x 2 の正方形の中に収まるからです。矛盾点として、 $f が$ 単射である可能性があると仮定します。単射とは、正方形で切り取られた $Sの断片が重なり合わないように積み重なることを意味します。$ $f は局所的に面積を保存するので、この重なり合わない性質により、$ $S$ 全体に対して面積が保存され、 $f (S)$ の面積は $S$ の面積と同じになり、4 より大きくなります。しかし、そうではないので、仮定は誤りでなければなりません。つまり、 $f は単射ではなく、つまり、$ $f$ によって同じ点に写像される $S$ 内の少なくとも 2 つの異なる点 $p 1 、 p 2が存在するということです。つまり、$ $f$ $($ $p$ $1$ $) =$ $f$ $($ $p$ $2$ $)$ です。

$f の$ 定義方法により、 $f (p 1)が$ $f (p 2)$ に等しくなる唯一の方法は、 $i$ と $j が$ 両方とも 0 ではなく、何らかの整数に対して、 $p 2が$ $p 1 + (2 i, 2 j)$ に等しくなることです。つまり、 2 つの点の座標は 2 つの偶数だけ異なります。 S は原点について対称なので $、$ − $p$ $1$ $も$ $S$ 内の点です。 $S$ $は凸なので、 -$ $p$ $1$ と $p$ $2$ の間の線分は完全に $S$ 内にあり、特にその線分の中点は $S$ 内にあります。言い換えると、

{\tfrac {1}{2}}\left(-p_{1}+p_{2}\right)={\tfrac {1}{2}}\left(-p_{1}+p_{1}+(2i,2j)\right)=(i,j)

$はS$ 内の点です。しかし、この点 $(i, j)は整数点であり、$ $i$ と $j が$ 両方ともゼロではないため原点ではありません。したがって、 $S$ にはゼロ以外の整数点が含まれます。

備考：

上記の議論は、任意の体積集合には格子ベクトルだけ異なる2つの異なる点が含まれるという定理を証明している。これはブリッヒフェルトの定理の特別な場合である。^[1] ${\textstyle >\!\det(L)}$
上記の議論は、項が格子の共体積であることを強調しています。 ${\textstyle 2^{n}\det(L)}$ ${\textstyle 2L}$
一般の格子の証明を得るには、ミンコフスキーの定理をについてのみ証明すれば十分です。これは、すべてのフルランク格子は何らかの線形変換についてと表すことができ、凸で原点について対称であるという特性は線形変換によって保持される一方で、の共体積はであり、物体の体積はを適用した場合に正確にによってスケールされるためです。 ${\textstyle \mathbb {Z} ^{n}}$ ${\textstyle B\mathbb {Z} ^{n}}$ ${\textstyle B}$ ${\textstyle B\mathbb {Z} ^{n}}$ ${\textstyle |\!\det(B)|}$ ${\textstyle {\frac {1}{\det(B)}}}$ ${\textstyle B^{-1}}$

アプリケーション

最短ベクトルの境界

ミンコフスキーの定理は、最短の非ゼロベクトルの長さの上限を与えます。この結果は、格子暗号や数論に応用されています。

定理（最短ベクトルに関するミンコフスキーの境界）：を格子とします。このとき、となるが存在します。特に、とノルムの標準的な比較により、となります。 ${\textstyle L}$ ${\textstyle x\in L\setminus \{0\}}$ ${\textstyle \|x\|_{\infty }\leq \left|\det(L)\right|^{1/n}}$ ${\textstyle l_{2}}$ ${\textstyle l_{\infty }}$ ${\textstyle \|x\|_{2}\leq {\sqrt {n}}\,\left|\det(L)\right|^{1/n}}$

証拠

とし、と設定します。の場合、には非ゼロの格子点が含まれますが、これは矛盾です。したがってです。QED ${\textstyle l=\min\{\|x\|_{\infty }:x\in L\setminus \{0\}\}}$ ${\textstyle C=\{y:\|y\|_{\infty }<l\}}$ ${\textstyle {\text{vol}}(C)=(2l)^{n}}$ ${\textstyle (2l)^{n}>2^{n}|d(L)|}$ ${\textstyle C}$ ${\textstyle l\leq |d(L)|^{1/n}}$

備考：

境界内の定数は、たとえば上記の議論のように半径の開いた球を取ることによって改善することができます。最適な定数はエルミート定数として知られています。 ${\textstyle L^{2}}$ ${\textstyle <l}$ ${\textstyle C}$
定理によって与えられる境界は、によって生成される格子を考えればわかるように、非常に緩いものになり得る。しかし、すべてのに対してを満たす-次元格子が存在するような大域定数が存在するという意味で、この定理をさらに改善することはできない。さらに、そのような格子は自己双対になることもある。^[2] ${\textstyle (1,0),(0,n)}$ $c$ $n$ $L$ $\|x\|_{2}\geq c{\sqrt {n}}\cdot \left|\det(L)\right|^{1/n}$ $x\in L\setminus \{0\}$
ミンコフスキーの定理は、ある大きさの境界内で短い格子ベクトルを保証しているが、このベクトルを見つけることは一般に難しい計算問題である。ミンコフスキーの境界によって保証された因子内でベクトルを見つけることはミンコフスキーのベクトル問題 (MVP) と呼ばれ、近似 SVP は双対格子の転移特性を使用してこれに帰着することが知られている。この計算問題は、エルミート SVP と呼ばれることもある。^[3]
LLL基底簡約アルゴリズムは、最短ベクトルのミンコフスキーの境界の弱いが効率的なアルゴリズムバージョンと見ることができます。これは、の-LLL 簡約基底がという特性を持つためです。詳細については、Micciancio の講義ノートを参照してください。^{[3]で説明されているように、}エルミート定数の境界の証明には、LLL 簡約アルゴリズムの重要なアイデアがいくつか含まれています。 ${\textstyle \delta }$ ${\textstyle b_{1},\ldots ,b_{n}}$ ${\textstyle L}$ ${\textstyle \|b_{1}\|\leq \left({\frac {1}{\delta -.25}}\right)^{\frac {n-1}{4}}\det(L )^{1/n}}$

数論への応用

2つの平方数の和である素数

2 つの平方数の和に関するフェルマーの定理の難しい含意は、最短ベクトルに関するミンコフスキーの境界を使用して証明できます。

定理:を持つすべての素数は、2 つの平方数の和として表すことができます。 ${\textstyle p\equiv 1\mod 4}$

証拠

およびが素数を法とする平方剰余である場合、かつその場合に限り(オイラーの条件)にの平方根が存在する。 1 つを選び、それに対するにおける1 つの代表を呼ぶ。ベクトルによって定義される格子を考え、関連する行列を表すものとする。この格子の行列式はであり、ここからミンコフスキーの境界からとなる非ゼロのが存在することがわかる。となり、整数を定義する。ミンコフスキーの境界からとなり、簡単なモジュラー演算からとなり、したがってとなる。QED ${\textstyle 4\,|\,p-1}$ $1つの$ ${\textstyle p}$ $a^{\frac {p-1}{2}}=1~({\text{mod}}~p)$ ${\textstyle -1}$ ${\textstyle \mathbb {Z} /p\mathbb {Z} }$ ${\textstyle \mathbb {Z} }$ ${\textstyle j}$ ${\textstyle L}$ ${\textstyle (1,j),(0,p)}$ ${\textstyle B}$ ${\textstyle p}$ ${\textstyle x=(x_{1},x_{2})\in \mathbb {Z} ^{2}}$ ${\textstyle 0<\|Bx\|_{2}^{2}<2p}$ ${\textstyle \|Bx\|^{2}=\|(x_{1},jx_{1}+px_{2})\|^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}}$ ${\textstyle a=x_{1},b=(jx_{1}+px_{2})}$ ${\textstyle 0<a^{2}+b^{2} <2p}$ ${\textstyle a^{2}+b^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}=0\mod p}$ ${\textstyle a^{2}+b^{2}=p}$

さらに、格子観点では、フェルマーの平方和の定理に対して計算効率の高いアプローチが得られます。

ラグランジュの四平方定理

ミンコフスキーの定理は、あらゆる自然数は4 つの自然数の平方の和として表すことができるとするラグランジュの四平方定理を証明するのにも役立ちます。

同時有理近似に関するディリクレの定理

ミンコフスキーの定理は、同時有理近似に関するディリクレの定理を証明するために使用できます。

代数的整数論

ミンコフスキーの定理の別の応用は、数体 $K$ のイデアル類群のすべての類には、 $K$ に依存する特定の境界を超えないノルムの整イデアルが含まれるという結果であり、この境界はミンコフスキーの境界と呼ばれます。これにより、代数的数体の類数の有限性が直ちに明らかになります。

複雑性理論

ミンコフスキーの定理、あるいはそれに密接に関連するブリッヒフェルトの定理によって保証される点を見つける複雑さは、TFNP探索問題の観点から研究されてきた。特に、ミンコフスキーの定理の証明の系であるブリッヒフェルトの定理の計算類似体はPPP完全であることが知られている。 ^[4]ミンコフスキーの定理の計算類似体はPPPクラスにあることも知られており、 PPP完全であると予想された。^[5]

参照

参考文献

^ Olds, CD ; Lax, Anneli ; Davidoff, Giuliana P. (2000). 「第 9 章: 数の幾何学における新しい原理」。数の幾何学。Anneli Lax 新数学図書館。第 41 巻。アメリカ数学協会、ワシントン DC。p. 120。ISBN 0-88385-643-3. MR 1817689。
^ ミルナー、ジョン; ヒュースモラー、デール (1973)。対称双線形形式。p. 46。doi : 10.1007/ 978-3-642-88330-9。ISBN 978-3-642-88332-3。
^ ab Nguyen, Phong Q. (2009). 「エルミート定数と格子アルゴリズム」. LLL アルゴリズム. 情報セキュリティと暗号化. ベルリン、ハイデルベルク: Springer Berlin Heidelberg. pp. 19–69. doi :10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN 1619-7100。
^ 「PPP-完全性と暗号化との関連」。Cryptology ePrint Archive: Report 2018/778。2018年8月15日。 2020年9月13日閲覧。
^ Ban, Frank; Jain, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad (2019-05-01). 「PPPの削減」. Information Processing Letters . 145 :48–52. doi :10.1016/j.ipl.2018.12.009. ISSN 0020-0190. S2CID 71715876. 2020-09-13閲覧。

さらに読む

ボンビエリ、エンリコ、ギュブラー、ウォルター（2006）。ディオファントス幾何学の高さ。ケンブリッジ大学出版局。ISBN 9780521712293。
Cassels, JWS (2012) [1959]. 数の幾何学入門. 数学の古典. Springer. ISBN 978-3-642-62035-5。
コンウェイ、ジョン、スローン、ニール JA (2013 年 6 月 29 日) [1998]。球状パッキング、格子および群 (第 3 版)。シュプリンガー。ISBN 978-1-4757-6568-7。
ハンコック、ハリス (2005) [1939].ミンコフスキー数幾何学の発展. ドーバー出版. ISBN 9780486446400。
Hlawka, エドマンド;ショイセンガイアー、ヨハネス。ルドルフ・タシュナー (2012) [1991]。幾何学的および解析的数論。スプリンガー。ISBN 978-3-642-75306-0。
Lekkerkerker、CG (2014) [1969]。数字の幾何学。エルゼビア。ISBN 978-1-4832-5927-7。
シュミット、ヴォルフガング M. (1980)。ディオファントス近似。数学講義ノート。第 785 巻。シュプリンガー。doi : 10.1007/ 978-3-540-38645-2。ISBN 978-3-540-38645-2。（[1996年、若干の修正あり]）
Wolfgang M. Schmidt .ディオファントス近似とディオファントス方程式、数学講義ノート、Springer Verlag 2000年。
シーゲル、カール・ルートヴィヒ(2013) [1989]. 数の幾何学に関する講義. シュプリンガー・フェアラーク. ISBN 9783662082874。
シュナイダー、ロルフ（1993）。凸体：ブルン・ミンコフスキー理論。ケンブリッジ大学出版局。ISBN 978-0-521-35220-8。

外部リンク

スティーブンハーゲン、ピーター。ナンバーリング。
マリシェフ、AV (2001) [1994]、「ミンコフスキーの定理」、数学百科事典、EMS プレス
「数の幾何学」、数学百科事典、EMS Press、2001 [1994]

[1] Olds, CD ; Lax, Anneli ; Davidoff, Giuliana P. (2000). 「第 9 章: 数の幾何学における新しい原理」。数の幾何学。Anneli Lax 新数学図書館。第 41 巻。アメリカ数学協会、ワシントン DC。p. 120。ISBN 0-88385-643-3. MR 1817689。

[2] ミルナー、ジョン; ヒュースモラー、デール (1973)。対称双線形形式。p. 46。doi : 10.1007/ 978-3-642-88330-9。ISBN 978-3-642-88332-3。

[Nguyen_2009_pp._19–69-3] Nguyen, Phong Q. (2009). 「エルミート定数と格子アルゴリズム」. LLL アルゴリズム. 情報セキュリティと暗号化. ベルリン、ハイデルベルク: Springer Berlin Heidelberg. pp. 19–69. doi :10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN 1619-7100。

[Cryptology_ePrint_Archive:_Report_2018/778_2018-4] 「PPP-完全性と暗号化との関連」。Cryptology ePrint Archive: Report 2018/778。2018年8月15日。 2020年9月13日閲覧。

[Information_Processing_Letters_2019_pp._48–52-5] Ban, Frank; Jain, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad (2019-05-01). 「PPPの削減」. Information Processing Letters . 145 :48–52. doi :10.1016/j.ipl.2018.12.009. ISSN 0020-0190. S2CID 71715876. 2020-09-13閲覧。

処方

例

証拠