ブリッチフェルトの定理 – 日本語百科事典辞書

Blichfeldt’s_theorem
Blichfeldtの定理は、数の幾何学における数学的定理であり、ユークリッド平面の有界集合に面積があるときはいつでもそれを述べています。 {A}
、少なくとも含まれるように翻訳することができます
⌈ ⌉
{ lceil A rceil}
整数格子の点。同等に、セットには次のものが含まれます
⌈ ⌉
{ lceil A rceil}
座標がすべて整数で異なる点。それは他の格子やより高い次元に一般化することができ、鳩の巣原理の連続バージョンとして解釈することができます。 1914年に出版したデンマーク系アメリカ人の数学者ハンスフレデリックブリクフェルトにちなんで名付けられました。一部の情報源はそれをブリクフェルトの原理またはブリクフェルトの補題と呼んでいます。
Blichfeldtの定理、すべての平面セットの領域{A}（ここでは、領域のある楕円 π { pi}
）少なくとも含まれています
⌈ ⌉
{ lceil A rceil}
ポイント（ここでは、
⌈ 4
{ lceil pi rceil = 4}
ポイント）、その座標はすべて整数で互いに異なります。この定理は、セットアップを整数グリッドの正方形で切り取り（上）、各ピースを整数変換ベクトルで単一の単位正方形に変換し、その単位正方形内で多くのピースで覆われている点を見つけることによって証明されます（中央）。このポイントのプレイメージを目的のポイントとして使用します（下）。

コンテンツ
1 声明と証明
2 アプリケーション
2.1 ミンコフスキーの定理 2.2 その他のアプリケーション
3 一般化
4 計算の複雑さ
5 も参照してください
6 参考文献
7 外部リンク

声明と証明
定理は、ユークリッド平面内の点と平面内の整数格子について最も簡単に述べることができます。このバージョンの定理では、 {S}
$S""$
任意の測定可能なセットであり、 {A}

その面積を示し、この数値を次の整数値に切り上げます。 =
⌈ ⌉
{n = lceil A rceil}

。次に、Blichfeldtの定理は次のように述べています。 {S}

翻訳されたコピーに少なくとも含まれるように翻訳することができます {n}

整数座標のポイント。
証明の基本的な考え方はカットすることです {S}

整数格子の二乗に従って断片に分割し、それらの各断片を整数量で変換して、原点を右下隅とする単位正方形内に配置します。この変換により、単位正方形の一部が複数回カバーされる可能性がありますが、変換された部分の合計面積が多重度でカウントされた場合、それは変更されず、次のようになります。 {A}

。一方、単位正方形全体が多重度で覆われている場合 − 1 {n-1}

その面積は − 1 {n-1}

、未満 {A}

。したがって、いくつかのポイント {p}

単位正方形の少なくとも多重度でカバーする必要があります {n}

。かかる翻訳 {p}

原点にすべてを取ります {n}

のポイント {S}

カバーした {p}

整数点に、それが必要だったものです。
より一般的には、定理はに適用されます {d}

-次元セット {S}

、と {d}

-次元ボリューム {A}

、および任意に {d}

-次元格子 Λ { Lambda}

（のポイントのセット {d}

-すべてが低次元の部分空間にあるわけではなく、最小距離だけ互いに分離されている次元空間。座標を加算または減算することで結合して、同じセット内の他の点を生成できます）。整数格子が平面を正方形に分割するのと同じように、任意の格子はその空間を基本領域（平行同位体と呼ばれる）に分割し、一意の格子点の座標を追加することで、これらの領域のいずれかを他の領域に変換できるという特性を備えています。。もしも L {L}

それは {d}

-平行四辺形の1つの次元体積、Blichfeldtの定理は次のように述べています {S}

少なくとも含むように翻訳することができます
⌈ /L ⌉
{ lceil A / L rceil}

のポイント Λ { Lambda}

。証拠は以前と同じです：カットアップ {S}

parallelotopesによって、翻訳ベクトルによってピースを翻訳します。 λ { lambda}

総量（多重度でカウント）を変更せずに単一の平行四辺形に、点がなければならないことに注意してください {p}

少なくとも多重度の
⌈ /L ⌉
{ lceil A / L rceil}

、およびかかる翻訳を使用する {p}

原点へ。
ある翻訳を求める代わりに {n}

格子点、定理の同等の形式は次のように述べています {S}

それ自体には、のセットが含まれています {n}

ポイント。そのペアごとの違いはすべてラティスに属します。定理の強化版はコンパクト集合に適用され、少なくとも含むように翻訳できると述べています
⌊ +1 ⌋
{ lfloor A + 1 rfloor}

格子の点。このポイント数は
⌈ ⌉
{ lceil A rceil}

の時だけ {A}

は整数であり、1だけ大きくなります。

アプリケーション

ミンコフスキーの定理
ヘルマン・ミンコフスキーによるブリッチフェルトの研究よりも早く証明されたミンコフスキーの定理は、原点を中心に中心対称であり、面積が4より大きい平面内の凸集合（または面積が4に等しいコンパクトな対称集合）にはゼロ以外の整数点が含まれると述べています。。より一般的には、 {d}

-次元格子 Λ { Lambda}

その基本的な並列同位体はボリュームを持っています L {L}

、原点を中心に中心対称で、体積がより大きい任意のセット 2L {2 ^ {d} L}

ゼロ以外の格子点が含まれています。
ミンコフスキーの元の証明は異なっていましたが、ブリッチフェルトの定理はミンコフスキーの定理の簡単な証明に使用できます。させて {X}

ボリュームがより大きい中央対称セットである 2L {2 ^ {d} L}

（ミンコフスキーの定理の条件を満たします）、それを2分の1に縮小して、セットを取得します。 1 2 {{ tfrac {1} {2}} X}

より大きいボリュームの L {L}

。Blichfeldtの定理により、 1 2 {{ tfrac {1} {2}} X}

2つのポイントがあります {p}

と {q}

その座標の違いはに属します L {L}

。収縮操作を逆にして、
2 {2p}

と
2 {2q}

に属する {X}

。対称性によって − 2 {-2q}

に属する {X}

、および凸性によって中点
2 {2p}

と − 2 {-2q}

属する {X}

。しかし、この中点は − {pq}

、の非ゼロ点 L {L}

。

その他のアプリケーション

非凸集合の格子点を見つけるためのミンコフスキーの定理に対するブリッチフェルトの定理の力の増加の例。（クローズド）イエローセットY Y}

左側には領域1があるため、赤い格子など、基本領域の体積が1である任意の格子の2点をカバーするように変換できます。したがって、青いセット =Y − Y {X = YY}

左、上
の点のペアの違いのセットでY Y}

、原点を中心とする場合、ゼロ以外の格子点が含まれます。対照的に、青い長方形K K}

右、上の
最大の凸サブセットの{X}

、ミンコフスキーの定理では面積が小さすぎて、ゼロ以外の格子点と黄色の長方形が含まれていることを保証できません。1 2 K {{ tfrac {1} {2}} K}

その中は、ブリッチフェルトの定理がその中の2つの点を見つけるには小さすぎます。
ミンコフスキーの定理への適用のように、ブリッチフェルトの定理の多くの適用は、十分に大きい集合の中のゼロ以外の格子点を見つけることを含みますが、凸ではありません。ミンコフスキーの定理を証明するために、集合間の重要な関係 {X}

と 1 2 {{ tfrac {1} {2}} X}

それが証明を機能させるのは、点のペアのすべての違いが 1 2 {{ tfrac {1} {2}} X}

に属する {X}

。ただし、セットの場合 {X}

それは凸状ではありません、 1 2 {{ tfrac {1} {2}} X}

差が属していない点のペアがある可能性があります {X}

、この手法では使用できなくなります。代わりに、最大の中心対称凸サブセットを見つけることができます K ⊂ {K subset X}

、次にミンコフスキーの定理をに適用します K {K}

、または同等にBlichfeldtの定理をに適用します1 2 K {{ tfrac {1} {2}} K}

。ただし、多くの場合、特定の非凸集合 {X}

サブセットがあります Y ⊂ {Y subset X}

それはより大きい1 2 K {{ tfrac {1} {2}} K}

、そのペアワイズ差はに属します {X}

。この場合、大きいサイズの Y {Y}

に関連して1 2 K {{ tfrac {1} {2}} K}

どのくらいの大きさのより厳しい境界につながります {X}

ラティスポイントが含まれていることを確認する必要が
中心対称の星状領域の場合、変分法を使用して最大のセットを見つけることができます。 ′
{X ‘}

そのペアワイズ差はに属します {X}

。この方法のアプリケーションには、同時ディオファントス近似が含まれます。これは、与えられた無理数のセットを、すべて同じ分母を持つ有理数で近似する問題です。

一般化
Blichfeldtの定理の類似体は、格子以外の点のセットで証明されており、十分に大きい領域にこれらのセットからの多くの点が含まれていることを示しています。これらには、フックス群の定理、格子状のサブセットが含まれます。 2 ×× 2 {2 times 2}

行列およびアルキメデスタイルの頂点のセット。
他の一般化により、セットが可能になります {S}

可測関数であるために、平行移動された格子点のいくつかのセットの合計が少なくともその積分と同じ大きさであることを証明するか、単一のセットを置き換えます {S}

セットの家族と。

計算の複雑さ
Blichfeldtの定理に関連する計算上の問題は、PPPの複雑さのクラスに対して完全であることが示されているため、多項式時間で解ける可能性は低いです。この問題は、入力として、の基礎を形成する整数ベクトルのセットを取ります。 {d}

-次元格子 Λ { Lambda}

、およびセット {S}

与えられたベクトルがに属するかどうかをテストするためのブール回路によって暗黙的に表される整数ベクトルの {S}

。のカーディナリティが必要です {S}

、の基本平行同位体の体積で割った値 Λ { Lambda}

は、少なくとも1つであり、Blichfeldtの定理の離散バージョンは次のことを意味します。 {S}

違いがに属するポイントのペアが含まれています Λ { Lambda}

。タスクは、そのようなペア、またはのポイントを見つけることです {S}

それ自体が属する Λ { Lambda}

。このタスクの計算の難しさは、衝突耐性のある暗号化ハッシュ関数の候補の構築を動機付けます。

も参照してください
ドットプラニメータ、形状に含まれる格子点を数えることにより形状の面積を推定するための装置
ピックの定理、格子点の頂点を持つポリゴンで覆われた面積と格子点の間のより正確な関係

参考文献
^ オールズ、CD ; ラックス、アンネリ; Davidoff、Giuliana P.（2000）、「第9章：数字の幾何学における新しい原理」、数字の幾何学、Anneli Lax New Mathematical Library、41、米国数学協会、ワシントンDC、119〜127ページ、ISBN 0-88385-643-3、MR 1817689 ^ Cassels、JWS（1978）、””Theorem 2.1（Blichfeldt）””、Rational quadratic forms、London Mathematical Society Monographs、13、Academic Press、p。68、ISBN 0-12-163260-1、MR 0522835 ^ Blichfeldt、HF（1914）、「いくつかのアプリケーションを使用した、数の幾何学の新しい原理」、米国数学会のトランザクション、15（3）：227–235、doi：10.1090 / S0002-9947-1914-1500976 -6、JSTOR 1988585、MR 1500976 ^ Marvin、Stephen、「B」、Dictionary of Scientific Principles、John Wiley＆Sons、pp。19–36、doi：10.1002 / 9781118582121.ch2
^ Honsberger、Ross（1973）、「果樹園の問題」、Mathematical Gems I、Dolciani Mathematical Expositions、1、Mathematical Association of America、pp。43–53 ; 特にブリクフェルトの補題、pを参照して44 ^ Spohn、WG（1968）、「Blichfeldtの定理と同時ディオファントス近似」、American Journal of Mathematics、90：885–894、doi：10.2307 / 2373489、JSTOR 2373489、MR 0231794 ^ 辻、正嗣（1956）、「フックス群に対するブリッチフェルトの定理の類似」、Commentarii Mathematici Universitatis Sancti Pauli、5：17–24、MR 0081323 ^ Cao、Penghao; 元、Liping（2011）、「ブリクフェルト型の定理{H}

-ポイント」、American Mathematical Monthly、118（8）：743–746、doi：10.4169 / amer.math.monthly.118.08.743、MR 2843996 ^ Schymura、Matthias; 元、Liping（2019）、「アルキメデスタイルへの適用を伴う離散格子周期集合に関する注記」、BeiträgezurAlgebraund Geometrie、60（4）：749–759、arXiv：1710.02552、doi：10.1007 / s13366-019 -00446-x、MR 4025474 ^ Lekkerkerker、CG（1969）、「セクション2.6：Blichfeldtの定理の一般化」、数の幾何学、Bibliotheca Mathematica、8、北ホラント、pp。40–43、MR 0271032 ^ ソティラキ、カテリーナ; ザンペタキス、マノリス; Zirdelis、Giorgos（2018）、「PPP-完全性と暗号化への接続」、Thorup、Mikkel（ed。）、第59回IEEE Annual Symposium on Foundations of Computer Science、FOCS 2018、パリ、フランス、2018年10月7〜9日、 IEEE Computer Society、pp。148–158、arXiv：1808.06407、doi：10.1109 / FOCS.2018.00023、MR 3899585

外部リンク
ワイスタイン、エリックW.、「ブリッヒフェルトの定理」、MathWorld”