Small set (組み合わせ論)

数学における組合せ論において small set は自然数の集合

$S=\{s_{0},s_{1},s_{2},s_{3},\dots \}$

で、次の級数

${\frac {1}{s_{0}}}+{\frac {1}{s_{1}}}+{\frac {1}{s_{2}}}+{\frac {1}{s_{3}}}+\cdots$

が収束するもののことである。large setとは、それ以外の集合(すなわち、件の級数が発散するもの)のことである。

例

• 自然数全体からなる集合 $\{1,2,3,4,5,\dots \}$ は large set であることが知られている(調和級数を見よ)。同様に、等差数列は全てlarge setである。

• 平方数全体からなる集合は small であることが知られている(バーゼル問題を見よ)。同様に、立方数の集合、4乗数の集合、などは全て small である。一般化して、任意の自然数上の二次以上の多項式関数について、その像集合はsmallである。

• 2の冪乗数の集合 $\{1,2,4,8,\dots \}$ は small であることが知られている。等比数列はすべて small である。

• 素数全体の集合は large であることが知られている。一方、双子素数全体からなる集合は small であることが知られている(ブルンの定理を見よ)。

• 冪次数2以上の素冪の集合 $\{\,p^{n}\,|\,n\geq 2{\mbox{ and }}p{\mbox{ is prime }}\}$ は small set である。この性質はen:analytic number theoryにおいてしばしば用いられる。一般化して、累乗数全体の集合は small である。

• 十進表示に特定の数字を使わない数からなる集合は small である。例えば、数字7を使わない数の集合

$\{\dots ,6,8,\dots ,16,18,\dots ,66,68,69,80,\dots \}$

は small である。(十進表示に限らず、他の底による表示法についても同様である。en:Kempner seriesも見よ。）

性質

• 二つの収束する級数の和が収束するので、small set の有限和は small である。large set から small set を引いたものはなお large set である。集合論の文脈では、small set 全体はイデアルをなすと言える。

未解決問題

large と small のどちらになるかが知られていない数列もたくさん存在する。

ポール・エルデシュは large な集合は必ず、任意の長さの等差数列を内部に持つような集合であるのかという問題を提唱した。en:Erdős conjecture on arithmetic progressionsを参照のこと。

彼はこの問題の懸賞金を3000ドル（これはエルデシュの提唱した問題のうちで最高額である）とし、また「この金額は最低賃金法に抵触している」との冗談を残している。

参考文献

• A. D. Wadhwa (1975). An interesting subseries of the harmonic series. American Mathematical Monthly 82 (9) 931–933. JSTOR 2318503