ベーレンドの定理

算術的組合せ論において、ベーレンドの定理は、 1 から までの整数の部分集合で、その集合のどの要素も他の要素の倍数ではないものは、が大きくなるにつれて対数密度がゼロに近づく必要があることを述べています。この定理は、1935 年にこれを発表した フェリックス・ベーレンドにちなんで名付けられました。${\displaystyle n}$${\displaystyle n}$

1 から までの整数の集合の対数密度は、各整数の重みを に設定し、集合の総重みを調和級数の 番目の部分和で割ることによって定義できます(または、漸近解析の目的で を で割ることと同等です)。集合にその範囲の整数がすべて含まれている場合は、結果として得られる数は 1 または 1 に近くなりますが、多くの整数が欠けている場合、特に欠けている整数自体が小さい場合は、結果の数は小さくなります。^[1]${\displaystyle n}$${\displaystyle i}$${\displaystyle 1/i}$${\displaystyle n}$${\displaystyle \log n}$

の部分集合は、その部分集合の要素が他の要素の倍数ではないという性質を持つ場合、原始的と呼ばれます。ベーレンドの定理によれば、任意の原始部分集合の対数密度は小さくなければなりません。より正確には、そのような集合の対数密度は でなければなりません。^[1]${\displaystyle \{1,\dots n\}}$${\displaystyle O(1/{\sqrt {\log \log n}})}$

無限原始列の場合、最大可能密度はより小さくなります。^[2]${\displaystyle o(1/{\sqrt {\log \log n}})}$

の大きな原始部分集合が存在します。しかし、これらの集合の対数密度は依然として小さいです。 ${\displaystyle \{1,\dots n\}}$

• サブセット では、すべての数のペアが互いに 2 未満の因数内にあるため、2 つの数が倍数になることはありません。これには、 から までの数の約半分が含まれます。ディルワースの定理(整数を 2 のべき乗に奇数を掛けたチェーンに分割する) により、このサブセットは、2 つの数が倍数にならないすべてのサブセットの中で最大の濃度を持ちます。ただし、その要素はすべて大きいため、このサブセットの対数密度は のみと低くなります。${\displaystyle \{\lceil (n+1)/2\rceil ,\dots n\}}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle O(1/\log n)}$
• もう 1 つの原始サブセットは素数の集合です。前の例の要素数よりも素数の数は少ないにもかかわらず、この集合は、素数の逆数の和の発散に従って、より大きな対数密度 を持ちます。${\displaystyle O(\log \log n/\log n)}$

これらの部分集合は両方とも、ベーレンドの定理によって与えられた境界よりもかなり小さい対数密度を持っています。GHハーディの予想を解決して、ポール・エルデシュとスバヤ・シヴァサンカラナラヤナ・ピライの両者は、 に対して、 （重複度で数えた）ちょうど素因数 を持つ数の集合は対数密度を持つことを示しました。${\displaystyle k\approx \log \log n}$${\displaystyle k}$

${\displaystyle {\frac {1+o(1)}{\sqrt {2\pi \log \log n}}},}$

ベーレンドの定理の形と完全に一致する。^[3]この例は、他の原始部分集合が同じ形とより大きな先頭定数を持つ対数密度を持たないという意味で、最も可能性の高い例である。^[4]

この定理は、フェリックス・ベーレンドが1934年に証明し、^[1] 1935年に発表したため、ベーレンドの定理として知られています。 ^[5] ポール・エルデシュは、ヨーロッパで高まる反ユダヤ主義から逃れるために1934年にハンガリーからケンブリッジへの列車旅行中に同じ結果を証明しましたが、到着時にベーレンドの証明がすでに知られていたことを発見しました。^[1]