ブリッヒフェルトの定理

ブリヒフェルトの定理は、数の幾何学における数学的な定理であり、ユークリッド平面内の面積を持つ有界集合は、少なくとも整数格子の点を含むように変換できるというものである。^[1]同様に、面積のすべての有界集合には、座標がすべて整数だけ異なる点の集合が含まれる。 ^[2]${\displaystyle A}$${\displaystyle \lceil A\rceil }$${\displaystyle A}$${\displaystyle \lceil A\rceil }$

この定理は他の格子や高次元にも一般化でき、鳩の巣原理の連続版として解釈できる。^[2]この定理は、1914年に発表したデンマーク系アメリカ人の数学者ハンス・フレデリック・ブリッヒフェルトにちなんで名付けられた。 ^{[3]一部の文献では、}ブリッヒフェルトの原理^[4]またはブリッヒフェルトの補題^[5]と呼ばれている。

この定理は、ユークリッド平面上の点と平面上の整数格子に対して最も簡単に述べることができる。この定理のバージョンでは、 を任意の測定可能な集合とし、 をその面積とし、この数を次の整数値 に切り上げる。すると、ブリッヒフェルトの定理は、を変換して、その変換コピーに少なくとも整数座標の点が含まれるようにできることを述べている。 ^[1]${\displaystyle S}$${\displaystyle A}$${\displaystyle n=\lceil A\rceil }$${\displaystyle S}$${\displaystyle n}$

証明の基本的な考え方は、整数格子の正方形に従って断片に切り分け、それらの断片のそれぞれを整数量だけ平行移動させて、原点を右下隅とする単位正方形内に収まるようにすることです。この平行移動により、単位正方形の一部の断片が複数回覆われる場合がありますが、平行移動した断片の合計面積を重複度で数えると、変化せず、 に等しくなります。一方、単位正方形全体が重複度で覆われると、その面積は になり、 未満になります。したがって、単位正方形のどこかの点は、少なくとも 重複度で覆われている必要があります。原点までの平行移動は、覆われたすべての点を整数点に取ることになりますが、これが要求されたことです。^[1]${\displaystyle S}$${\displaystyle A}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle A}$${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle S}$${\displaystyle p}$

より一般的には、定理は、次元の体積を持つ次元集合と、任意の次元格子(次元空間内の点の集合で、そのすべてがより低い次元の部分空間に存在せず、互いに最小距離で分離されており、座標を加算または減算することで結合して同じ集合内の他の点を生成できるもの) に適用されます。整数格子が平面を正方形に分割するのと同じように、任意の格子はその空間を基本領域 (平行四辺形と呼ばれる) に分割し、これらの領域のいずれも、一意の格子点の座標を追加することで他の領域に移動できるという特性があります。 が平行四辺形の 1 つの 次元体積である場合、ブリッヒフェルトの定理によれば、 は少なくともの点を含むように移動できます。証明は前と同じです。平行体で切り分け、全体の体積を変えずに（重複度で数えて）平行体への平行移動ベクトルで断片を移動し、少なくとも重複点が1つあることを確認し、原点までの平行移動を使用します。^[1]${\displaystyle d}$${\displaystyle S}$${\displaystyle d}$${\displaystyle A}$${\displaystyle d}$ ${\displaystyle \Lambda}$${\displaystyle d}$${\displaystyle L}$${\displaystyle d}$${\displaystyle S}$${\displaystyle \lceil A/L\rceil }$${\displaystyle \Lambda}$${\displaystyle S}$${\displaystyle \lambda}$${\displaystyle p}$${\displaystyle \lceil A/L\rceil }$${\displaystyle p}$

格子点が存在する変換を求める代わりに、定理の同等の形式は、それ自体が点の集合を含み、そのすべての対差が格子に属することを述べています。^[2]定理の強化版はコンパクト集合に適用され、それらは格子の少なくとも点を含むように変換できることを述べています。この点の数は、が整数の場合にのみ異なり、その場合、1だけ大きくなります。^[1]${\displaystyle n}$${\displaystyle S}$${\displaystyle n}$${\displaystyle \lfloor A+1\rfloor }$${\displaystyle \lceil A\rceil }$${\displaystyle A}$

ミンコフスキーの定理は、ブリヒフェルトの研究よりも前にヘルマン・ミンコフスキーによって証明されたもので、平面上の凸集合で原点を中心に対称で面積が より大きいもの（または面積が のコンパクトな対称集合）は、非ゼロの整数点を含むというものである。より一般的には、基本平行四辺形の体積が である次元格子について、原点を中心に対称で体積が より大きい集合は非ゼロの格子点を含む。^[1]${\displaystyle d}$${\displaystyle \Lambda}$${\displaystyle L}$${\displaystyle 2^{d}L}$

ミンコフスキーの最初の証明は異なっていたが、ブリッヒフェルトの定理はミンコフスキーの定理の簡単な証明に使用できる。を より大きい体積を持つ任意の中心対称集合とし（ミンコフスキーの定理の条件を満たす）、それを 2 倍に縮小してより大きい体積の集合を得る。ブリッヒフェルトの定理により、 には2 つの点と があり、その座標差は に属する。縮小操作を逆にすると、とは に属する。対称性によりも に属し 、凸性によりとの中点は に属する。しかし、この中点は の非ゼロ点である である。^[2]${\displaystyle X}$${\displaystyle 2^{d}L}$${\displaystyle {\tfrac {1}{2}}X}$${\displaystyle L}$${\displaystyle {\tfrac {1}{2}}X}$${\displaystyle p}$${\displaystyle q}$${\displaystyle L}$${\displaystyle 2p}$${\displaystyle 2q}$${\displaystyle X}$${\displaystyle -2q}$${\displaystyle X}$${\displaystyle 2p}$${\displaystyle -2q}$${\displaystyle X}$${\displaystyle pq}$${\displaystyle L}$

ブリッヒフェルトの定理の多くの応用は、ミンコフスキーの定理への応用のように、十分に大きいが凸ではない集合内で非ゼロの格子点を見つけることを伴います。ミンコフスキーの定理の証明では、証明を機能させる集合との間の重要な関係は、 内の点のペアの差がすべて に属するということです。しかし、凸でない集合の場合、 には、差が に属さない点のペアが含まれる可能性があり、この技法では使用できなくなります。代わりに、最大の中心対称凸部分集合 を見つけてから、ミンコフスキーの定理を に適用するか、同等にブリッヒフェルトの定理を に適用することができます。しかし、多くの場合、与えられた非凸集合にはよりも大きい部分集合があり、そのペアごとの差は に属します。この場合、に対するのサイズが大きいため、 に格子点が含まれることを保証するために必要な大きさの境界が狭くなります。 ^[6]${\displaystyle X}$${\displaystyle {\tfrac {1}{2}}X}$${\displaystyle {\tfrac {1}{2}}X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle {\tfrac {1}{2}}X}$${\displaystyle X}$${\displaystyle K\subset X}$${\displaystyle K}$${\displaystyle {\tfrac {1}{2}}K}$${\displaystyle X}$${\displaystyle Y\subset X}$${\displaystyle {\tfrac {1}{2}}K}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle {\tfrac {1}{2}}K}$${\displaystyle X}$

中心対称の星型領域では、変分法を使用して、ペアワイズ差が に属する最大の集合を見つけることが可能です。この方法の応用には、同時ディオファントス近似、つまり、与えられた無理数の集合を、すべて同じ分母を持つ有理数で近似する問題が含まれます。 ^[6]${\displaystyle X'}$${\displaystyle X}$

ブリッヒフェルトの定理の類似物は格子以外の点の集合に対しても証明されており、十分に大きな領域にはこれらの集合からの点が多数含まれることを示しています。これには、フックス群、格子状の行列のサブセット、^[7]およびアルキメデスのタイリングの頂点の集合に対する定理が含まれます。^{[8] [9]}${\displaystyle 2\times 2}$

他の一般化では、集合が測定可能な関数であることを可能にし、平行移動した格子点の集合全体にわたるその和が少なくともその積分と同じ大きさであることを証明したり、単一の集合を集合の族に置き換えたりします。^[10]${\displaystyle S}$${\displaystyle S}$

ブリッヒフェルトの定理に関連する計算問題は、 PPP 計算量クラスに対して完全であることが示されており、したがって多項式時間で解ける可能性は低い。この問題は、次元格子の基底を形成する整数ベクトルの集合と、与えられたベクトルが に属するかどうかをテストするためのブール回路によって暗黙的に表される整数ベクトルの集合を入力として取る。 の濃度を の基本平行四辺形の体積で割った値が少なくとも 1 であることが要求され、そこからブリッヒフェルトの定理の離散バージョンは、に差が に属する点のペアが含まれることを意味する。タスクは、そのようなペア、またはに属するの点を見つけることである。このタスクの計算困難さは、衝突耐性のある暗号ハッシュ関数の候補を構築する動機となっている。^[11]${\displaystyle d}$${\displaystyle \Lambda }$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \Lambda }$${\displaystyle S}$${\displaystyle \Lambda }$${\displaystyle S}$${\displaystyle \Lambda }$

• ドットプラニメーターは、図形に含まれる格子点の数を数えることで図形の面積を推定する装置である。
• ピックの定理、格子点頂点を持つ多角形が覆う格子点と面積との間のより正確な関係

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