シュニレルマン密度

加法的整数論（英語版）(additive number theory)では、シュニレルマン密度 (Schnirelmann density) は、整数列の密度の概念の一種である。これは、後にリンニク（英語版）(Yuri Linnik)やヴィノグラドフ（英語版）(Ivan Matveyevich Vinogradov)の仕事に重要なアイデアをもたらした。この概念を定義・研究した数学者L.G.シュニレルマン(L.G.Schnirelmann)に因む。 A を自然数からなる集合とし、 A ( n ) {\displaystyle A(n)} を A の元のうち 1 以上 n 以下のものの個数とする。このとき、実数 σ A := inf n A ( n ) n {\displaystyle \sigma A:=\inf _{n}{\frac {A(n)}{n}}} が必ず定義され、これを A のシュニレルマン密度という。inf は「全ての部分列の中の最も小さな下界を採用する」ことを意味する。 自然数全体の集合のシュニレルマン密度は 1 である。 奇数全体の集合のシュニレルマン密度は 1/2 である。 偶数全体の集合 E のシュニレルマン密度は 0 である (A(1)=0 であるため)。 1 と偶数全体からなる集合のシュニレルマン密度は 1/2 である。 1 と素数からなる集合のシュニレルマン密度は 0 である。 1 と2つの素数の和で表される整数からなる集合のシュニレルマン密度は 正 である（後述）。 次の性質は定義から明らかである。 0 ≤ σ A ≤ 1. {\displaystyle 0\leq \sigma A\leq 1.} すべての n に対して A ( n ) ≥ n σ A . {\displaystyle A(n)\geq n\sigma A.} σ A = 1 {\displaystyle \sigma {A}=1\quad } ならば A = N . {\displaystyle A=\mathbb {N} .\quad } k ∉ A {\displaystyle k\notin A} ならば σ A ≤ 1 − 1 / k {\displaystyle \sigma A\leq 1-1/k} . 特に、 A が 1 を含まなければ、 σ A = 0 {\displaystyle \sigma A=0} である。また、 A が 2 を含まなければ、 σ A ≤ 1 / 2 {\displaystyle \sigma A\leq 1/2} である。 σ A = 0 {\displaystyle \sigma A=0} ならば、任意の正の ε に対して、 A ( n ) < ϵ n {\displaystyle A(n)<\epsilon n} となる n が存在する。 A が 1 を含んでおり、正の下極限密度を持つとき、 σ A > 0 {\displaystyle \sigma A>0} である。 ※追記 ： 定義より全ての n に対して、0 ≤ A(n) ≤ n であり nσA ≤ A(n) であるから、0 ≤ σA ≤ 1 かつ σA = 1 であることは A = N であることと同値である。さらに、 σ A = 0 ⇒ ∀ ϵ > 0   ∃ n   A ( n ) < ϵ n . {\displaystyle \sigma A=0\Rightarrow \forall \epsilon >0\ \exists n\ A(n)<\epsilon n.} シュニレルマン密度は集合の最初の値に対して敏感である． ∀ k   k ∉ A ⇒ σ A ≤ 1 − 1 / k {\displaystyle \forall k\ k\notin A\Rightarrow \sigma A\leq 1-1/k} . 特に、 1 ∉ A ⇒ σ A = 0 {\displaystyle 1\notin A\Rightarrow \sigma A=0} かつ 2 ∉ A ⇒ σ A ≤ 1 2 {\displaystyle 2\notin A\Rightarrow \sigma A\leq {\frac {1}{2}}} 　である。 結局、偶数と奇数のシュニレルマン密度はそれぞれ、0 と 1/2 である。シュニレルマンとリンニクは、以下に見るように、この敏感さを利用した。（シュニレルマン密度は A の小さな部分に強く依存する。しかし、比較的容易に加法的整数論に関する定理を得ることができるため、シュニレルマンによって早くから研究がなされた。） 以下、 a + b ( a ∈ A , b ∈ B ) {\displaystyle a+b(a\in A,b\in B)} と表されるもの全体の集合を A + B {\displaystyle A+B} と記す。また、 a 1 + a 2 + … + a n ( a i ∈ A ) {\displaystyle a_{1}+a_{2}+\ldots +a_{n}(a_{i}\in A)} と表されるもの全体の集合を nA と記す。 nA が自然数全体の集合と一致する最小の n に対して A を位数 n の加法的な基(additive basis)もしくは単に基であるという。たとえば四平方定理より 0 と平方数からなる集合は位数 4 の基である。 どのような整数列が基であるか、また基であるときにその位数がいくつかを知ることが加法的整数論の中心的な課題である。 定理　A と B を自然数の集合で、共に 0 を含むものとする。 C = A + B {\displaystyle C=A+B} とすると、 σ C ≥ σ A + σ B − σ A ⋅ σ B {\displaystyle \sigma C\geq \sigma A+\sigma B-\sigma A\cdot \sigma B} が成り立つ。 このことは次のようにして分かる。 0 < a 1 < a 2 < … {\displaystyle 0<a_{1}<a_{2}<\ldots } を A の元全体とする。 σ A = 0 {\displaystyle \sigma A=0} ならば 上の不等式の右辺は σ B {\displaystyle \sigma B} に等しいから σ A > 0 {\displaystyle \sigma A>0} （よって a 1 = 1 {\displaystyle a_{1}=1} である）の場合を考える。 b ∈ B {\displaystyle b\in B} かつ 1 ≤ b ≤ a i + 1 − a i − 1 {\displaystyle 1\leq b\leq a_{i+1}-a_{i}-1} ならば、 a i + b {\displaystyle a_{i}+b} は C の元であるが A の元ではない。 B が 0 を含んでいることより C は A の元を含んでいるから、 r = A ( x ) {\displaystyle r=A(x)} とおくと、 C ( x ) ≥ r + ∑ i = 1 r − 1 B ( a i + 1 − a i − 1 ) + B ( x − a r ) , {\displaystyle C(x)\geq r+\sum _{i=1}^{r-1}B(a_{i+1}-a_{i}-1)+B(x-a_{r}),} ここで σ B ≤ B ( x ) / x {\displaystyle \sigma B\leq B(x)/x} が常に成り立つことから C ( x ) ≥ r + σ B ( x − a r + ∑ i = 1 r − 1 ( a i + 1 − a i − 1 ) ) ≥ x σ B + r ( 1 − σ B ) {\displaystyle C(x)\geq r+\sigma B(x-a_{r}+\sum _{i=1}^{r-1}(a_{i+1}-a_{i}-1))\geq x\sigma B+r(1-\sigma B)} となる。 r = A ( x ) ≥ x σ A {\displaystyle r=A(x)\geq x\sigma A} が常に成り立つから、 C ( x ) ≥ x σ B + x σ A ( 1 − σ B ) = x ( σ A + σ B − σ A ⋅ σ B ) {\displaystyle C(x)\geq x\sigma B+x\sigma A(1-\sigma B)=x(\sigma A+\sigma B-\sigma A\cdot \sigma B)} である。これより定理が示された。 この定理を変形すると ( 1 − σ ( A + B ) ) ≤ ( 1 − σ A ) ( 1 − σ B ) {\displaystyle (1-\sigma (A+B))\leq (1-\sigma A)(1-\sigma B)} となる。これを帰納的に適用して、 1 − σ ( A 1 + A 2 + … A n ) ≤ ∏ i ( 1 − σ A i ) {\displaystyle 1-\sigma (A_{1}+A_{2}+\ldots A_{n})\leq \prod _{i}(1-\sigma A_{i})} を得る。 シュニレルマンの定理は、和集合がどのように蓄積されるかについて、最初の見方を与えている。この結論は、一見、 σ {\displaystyle \sigma } が優加法性(superadditive)を持っていることが、不幸に見えるが、シュニレルマンは次のような結果を示し、彼の目指した目的へほぼ到達した。 定理. A {\displaystyle A} と B {\displaystyle B} を自然数 N {\displaystyle \mathbb {N} } の部分集合とする。 σ A + σ B ≥ 1 {\displaystyle \sigma A+\sigma B\geq 1} であれば、 A ⊕ B = N . {\displaystyle A\oplus B=\mathbb {N} .} となる。言い換えると、 σ A + σ B > 1 {\displaystyle \sigma A+\sigma B>1} かつ A が 0 を含んでいるならば A + B はすべての整数を含んでいる。 実際、 n ∉ A + B {\displaystyle n\notin A+B} ならば、 n および n − a i {\displaystyle n-a_{i}} の形の数は B に含まれないから、 B ( n ) ≤ n − 1 − A ( n − 1 ) ≤ n − A ( n ) {\displaystyle B(n)\leq n-1-A(n-1)\leq n-A(n)} となり、よって σ A + σ B ≤ ( A ( n ) + B ( n ) ) / n ≤ 1 {\displaystyle \sigma A+\sigma B\leq (A(n)+B(n))/n\leq 1} となる。 上記の二つの定理から、A が 0 を含んでおり、正のシュニレルマン密度を持つならば、ある自然数 n に対して σ ( n − 1 ) A > 1 / 2 {\displaystyle \sigma (n-1)A>1/2} となり、よって 2 ( n − 1 ) A {\displaystyle 2(n-1)A} はすべての整数を含んでいることがわかる。つまり 定理. (シュニレルマン) A ⊆ N {\displaystyle A\subseteq \mathbb {N} } とする。 σ A > 0 {\displaystyle \sigma A>0} であれば、 ⨁ i = 1 k A = N . {\displaystyle \bigoplus _{i=1}^{k}A=\mathbb {N} .} となるような k {\displaystyle k} が存在する。 有限和 A ⊕ A ⊕ ⋯ ⊕ A = N {\displaystyle A\oplus A\oplus \cdots \oplus A=\mathbb {N} } という性質を持つ部分集合 A ⊆ N {\displaystyle A\subseteq \mathbb {N} } を加法的な基(additive basis)といい、そのようにとることが可能な最小の和の数を基の次数(degree)という。このようにすると上記の定理は、任意の正のシュニレルマン密度を持つ集合は、加法的な基であるということになる。この用語を使うと、平方数の集合 G 2 = { k 2 } k = 1 ∞ {\displaystyle {\mathfrak {G}}^{2}=\{k^{2}\}_{k=1}^{\infty }} の加法的な基の次数は 4 であることになる。全ての平方数の集合を G 2 = { k 2 } k = 1 ∞ {\displaystyle {\mathfrak {G}}^{2}=\{k^{2}\}_{k=1}^{\infty }} とすると、ラグランジュの四平方定理は σ ( G 2 ⊕ G 2 ⊕ G 2 ⊕ G 2 ) = 1 {\displaystyle \sigma ({\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2})=1} と書きなおすことができる。（ここに、記号 A ⊕ B {\displaystyle A\oplus B} は、 A ∪ { 0 } {\displaystyle A\cup \{0\}} と B ∪ { 0 } {\displaystyle B\cup \{0\}} との sumset とする。） σ G 2 = 0 {\displaystyle \sigma {\mathfrak {G}}^{2}=0} であることは明らかである。事実、依然として、 σ ( G 2 ⊕ G 2 ) = 0 {\displaystyle \sigma ({\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2})=0} であり、どの点がシュニレルマン密度を 1 とし、どのように密度を増加させるのかを問うかもしれない。実際は、3つの和の場合は、 σ ( G 2 ⊕ G 2 ⊕ G 2 ) = 5 / 6 {\displaystyle \sigma ({\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2})=5/6} であり、 G 2 {\displaystyle {\mathfrak {G}}^{2}} の sumset を取ることをすると、より大きな集合、すなわち、全ての自然数の集合 N {\displaystyle \mathbb {N} } となる。シュニレルマンは、さらにこれらの考え方を進め、上記の定理とし、加法的整数論の研究を進め、（たとえ巨大な威力を発揮しなかったとしても）多くの貴重な結果を証明し、ウェアリングの問題やゴルドバッハの予想のような重要な問題を解明しようとした。 歴史的には、シュニレルマンの定理より強い予想は、それ以前の一時期よりエドムンド・ランダウ(Edmund Landau)によって「アルファ+ベータ予想」として使われていた。1942年、ヘンリー・マン（英語版）によりこの予想は証明され、マンの定理として定式化された。 定理. (Mann 1942) A {\displaystyle A} と B {\displaystyle B} を N {\displaystyle \mathbb {N} } の部分集合とする。 A ⊕ B ≠ N {\displaystyle A\oplus B\neq \mathbb {N} } の場合、 σ ( A ⊕ B ) ≥ σ A + σ B {\displaystyle \sigma (A\oplus B)\geq \sigma A+\sigma B} が成り立つ。 つまり、A が 0 を含んでおり、また σA ≥ 1/n ならば、A は次数が高々 n の基となっていることが分かる。 マンの証明の直後、エミル・アルティン(Emil Artin)と P. Scherk はマンの定理の証明を簡素化した。この定理の低い漸近密度での類似は、クネーザー(Kneser)により得られた。 k {\displaystyle k} と N {\displaystyle N} を自然数とする。 G k = { i k } i = 1 ∞ {\displaystyle {\mathfrak {G}}^{k}=\{i^{k}\}_{i=1}^{\infty }} とする。 r N k ( n ) {\displaystyle r_{N}^{k}(n)} を x i {\displaystyle x_{i}} の方程式 x 1 k + x 2 k + ⋯ + x N k = n {\displaystyle x_{1}^{k}+x_{2}^{k}+\cdots +x_{N}^{k}=n\,} の非負の整数解の数とし、 R N k ( n ) {\displaystyle R_{N}^{k}(n)} を x i {\displaystyle x_{i}} の不等式 0 ≤ x 1 k + x 2 k + ⋯ + x N k ≤ n , {\displaystyle 0\leq x_{1}^{k}+x_{2}^{k}+\cdots +x_{N}^{k}\leq n,} の非負の整数解の数とする。すると、 R N k ( n ) = ∑ i = 0 n r N k ( i ) {\displaystyle R_{N}^{k}(n)=\sum _{i=0}^{n}r_{N}^{k}(i)} となり、次の 2つを得る。 r N k ( n ) > 0 ↔ n ∈ N G k , {\displaystyle r_{N}^{k}(n)>0\leftrightarrow n\in N{\mathfrak {G}}^{k},} R N k ( n ) ≥ ( n N ) N k . {\displaystyle R_{N}^{k}(n)\geq \left({\frac {n}{N}}\right)^{\frac {N}{k}}.} 0 ≤ x 1 k + x 2 k + ⋯ + x N k ≤ n {\displaystyle 0\leq x_{1}^{k}+x_{2}^{k}+\cdots +x_{N}^{k}\leq n} により定義される N {\displaystyle N} -次元の領域の体積は、大きさが n 1 / k {\displaystyle n^{1/k}} の超立方体の体積を最大として有界である。従って、 R N k ( n ) = ∑ i = 0 n r N k ( i ) = n N / k {\displaystyle R_{N}^{k}(n)=\sum _{i=0}^{n}r_{N}^{k}(i)=n^{N/k}} である。ここで難しい部分は、この限界値が平均でもうまく機能することです。つまり、 補題. (リンニクの定理) 全ての k ∈ N {\displaystyle k\in \mathbb {N} } に対して、 k {\displaystyle k} にのみ依存する N ∈ N {\displaystyle N\in \mathbb {N} } と定数 c = c ( k ) {\displaystyle c=c(k)} が存在して、全ての n ∈ N {\displaystyle n\in \mathbb {N} } と全ての 0 ≤ m ≤ n . {\displaystyle 0\leq m\leq n.} について r N k ( m ) < c n N k − 1 {\displaystyle r_{N}^{k}(m)<cn^{{\frac {N}{k}}-1}} が成り立つ。 このことを元にして、次の定理をエレガントに証明できる。 定理. 全ての k {\displaystyle k} に対し、 σ ( N G k ) > 0 {\displaystyle \sigma (N{\mathfrak {G}}^{k})>0} となる N {\displaystyle N} が存在する。 このようにして、ウェアリングの問題の一般的な解法が確立した。 系. (Hilbert 1909) 全ての k {\displaystyle k} に対し、 k {\displaystyle k} にのみ依存する N {\displaystyle N} が存在し、全ての正の整数 n {\displaystyle n} は、高々、 N {\displaystyle N} の k {\displaystyle k} -乗のべきの和として表すことができる。 シュニレルマンがこの概念を研究したのはゴールドバッハの予想の研究のためでもあった。P を 0, 1 と素数からなる集合とすると、これはシュニレルマン密度 0 を持つが、シュニレルマンはブルンの篩を用いて P + P が正のシュニレルマン密度を持つことを示した（1930年、シュニレルマンの定理 、この定理は、上に述べたように、任意の 1 より大きな自然数は、計算可能な定数を C として C 個より少ない数の素数の和により表されるという定理）。よって P は基である。すなわち、ある定数 C が存在し、全ての整数は 高々 C 個の素数の和で表される。シュニレルマンは C < 800000 {\displaystyle C<800000} を示している。このことに因んで、「1 より大きい全ての整数が高々 C 個の素数の和で表される」が正しくなる最小の C をシュニレルマン定数と呼ぶ。ゴールドバッハの予想は、シュニレルマンの定数 C = 3 {\displaystyle C=3} を証明することとなる。 オリバー・ラマレー（英語版）(Olivier Ramaré)は、(Ramaré 1995) で、シュニレルマンの定数は、高々 7 であることを示し、先に上の境界が 19 であることを示したハンス・リーゼル(Hans Riesel)とロバート・チャールズ・ヴォーン（英語版）(Robert Charles Vaughan)によって得られている結果を改善した。 アレクサンドル・ヒンチン(Aleksandr Khinchin)は、平方数の数列は、たとえシュニレルマン密度 0 であったとしても、シュニレルマン密度が 0 と 1 の間の数列を加えると、密度が増大することを証明した。全ての 0 < σ ( A ) < 1 {\displaystyle 0<\sigma (A)<1} である数列 A {\displaystyle A} に対し σ ( A + G 2 ) > σ ( A ) {\displaystyle \sigma (A+{\mathfrak {G}}^{2})>\sigma (A)} となる。このことは、すぐにポール・エルデシュ(Paul Erdős)により単純化され、かつ拡張され、A がシュニレルマン密度 α であり、B が次数(order) k の加法的な基であれば、 σ ( A + B ) ≥ α + α ( 1 − α ) 2 k {\displaystyle \sigma (A+B)\geq \alpha +{\frac {\alpha (1-\alpha )}{2k}}} が成り立つことを示した。プリューネッケ(Plünnecke)は、さらに改善し、 σ ( A + B ) ≥ α 1 1 − k {\displaystyle \sigma (A+B)\geq \alpha ^{\frac {1}{1-k}}} を示した。 この加法により密度が増える性質を持つ数列は、ヒンチンにより必須な構成要素(essential components)と名付けられた。ユーリ・リンニク（英語版）(Yuri Linnik)は、 x より小さな xo(1) 個の元を持つ必須な構成要素を構成することで、必須な構成要素が必ずしも加法的な基である必要はないことを示した。さらに詳しくは、数列がある C < 1 に対し x よりも小さな元を e ( log ⁡ x ) C {\displaystyle e^{(\log x)^{C}}\,} 個持っていることを、彼は示した。この結果は、E. ワーシング(E. Wirsing)により、 e log ⁡ x log ⁡ log ⁡ x {\displaystyle e^{{\sqrt {\log x}}\log \log x}} まで改善された。 暫くの間、どのくらい多くの要素を必須な構成要素が持たねばならないかについては未解決問題であった。最終的には、イムレ・ルッツァ（英語版）(Imre Z. Ruzsa)は、必須な構成要素はある x に対しては少なくとも ( log ⁡ x ) C {\displaystyle (\log {x})^{C}} 個の元を持ち、全ての C > 1 に対して x に対して必須な構成要素は高々 (log x)C 個の元しか持たないことを結論付けた。