加法的整数論

同義語:additive number theory加法的数論

概要

加法的整数論(additive number theory)とは、整数の集合の和で何が表せるかを調べる数論の分野である。中心の問いは、平方数・冪・素数のような集合の和で、どの整数が何項で表せるかである。Waring の問題、Goldbach 予想、Schnirelmann の密度の理論などを含み、円周法と篩法が主な道具である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 素数, 合同式, 母関数

加法的整数論(additive number theory)は、整数の集合どうしの和を調べる数論の分野である。中心の問いは「与えられた集合 $A$ の元を決まった個数だけ足して、すべての整数(または十分大きいすべての整数)を作れるか」と「その作り方は何通りあるか」の 2 つである。$A$ が平方数なら Lagrangeの四平方定理、$k$ 乗数なら Waringの問題、素数なら Goldbach予想 が代表である。$A$ を正の整数全体とし、足す個数を固定せず、和の順序も区別しないで表し方を数えたものが 分割数 である。
この記事は分野の地図である。基本の言葉を定義し、問いと結果を記事とともに一覧にする。個々の定理の証明はそれぞれの記事に任せ、ここでは分野の出発点の 1 つである Schnirelmann の基底定理だけを完全に証明する(thm-addnt-schnirelmann)。

基本の言葉

この記事では $\mathbb{Z}_{\ge0}=\{0,1,2,\ldots\}$ とする。

和集合と基底

$A,B\subset\mathbb{Z}_{\ge0}$ の和集合(sumset)を $A+B:=\{a+b\mid a\in A,\ b\in B\}$ と定め、$A$ を $h$ 回足した集合を $hA:=A+\cdots+A$ と書く。$0\in A$ で $hA=\mathbb{Z}_{\ge0}$ となる $h\ge1$ があるとき、$A$ を有限位数の基底といい、最小の $h$ をその位数という。$hA$ が有限個を除くすべての $n\in\mathbb{Z}_{\ge0}$ を含む $h$ があるとき、$A$ を漸近基底という。

$0\in A$ を仮定すると、$hA$ は「$h$ 個以下の $A$ の正の元の和」の全体になる。Lagrangeの四平方定理 は、平方数の集合が位数 $4$ の基底であることを述べる($7$ が $3$ 個の平方数の和でないので $3$ にはできない)。

表現の個数

$A\subset\mathbb{Z}_{\ge0}$ と $h\ge1$ について、$n$ の順序を区別した表し方の個数を
$$ r_{A,h}(n):=\#\{(a_1,\ldots,a_h)\in A^h\mid a_1+\cdots+a_h=n\} $$
と書く。$n\in hA$ であることは $r_{A,h}(n)>0$ と同値である。

$r_{A,h}$ は解析の言葉に翻訳できる。$e(x):=e^{2\pi ix}$ とし、$N\ge n$ について $f(\alpha):=\sum_{a\in A,\,a\le N}e(a\alpha)$ とおく。$f(\alpha)^h$ を展開すると、$e(m\alpha)$ の係数は $a_1+\cdots+a_h=m$ となる $N$ 以下の元の組の個数である。整数 $k$ について $\int_0^1e(k\alpha)\,d\alpha$ は $k=0$ のとき $1$、それ以外で $0$ なので、
$$ r_{A,h}(n)=\int_0^1f(\alpha)^h\,e(-n\alpha)\,d\alpha $$
が成り立つ(和が $n$ の組の元はすべて $n$ 以下である)。たとえば $A=\{1,2\}$、$h=2$ では $f(\alpha)^2=e(2\alpha)+2e(3\alpha)+e(4\alpha)$ で、$3=1+2=2+1$ の 2 通りが係数 $2$ として読める。この等式から $f$ の大きさの評価へ進むのが Hardy–Littlewoodの円周法 である。$\alpha$ を形式的な変数 $x=e(\alpha)$ に置き換えれば、同じ展開は 母関数 の積であり、分割数 の母関数 $\prod_{k\ge1}(1-x^k)^{-1}$ は、項の個数を固定せず順序も区別しないで数える母関数である。

主な問題と結果の一覧

整数全体を作る問題

集合 $A$問い代表的な結果入る記事
平方数いくつ足せば足りるか位数は $4$。$2$ 個の和になる素数は $2$ と $4$ で割って $1$ 余る素数、$3$ 個の和になる数は $4^a(8b+7)$ の形でない数Lagrangeの四平方定理、Fermatの二平方定理、Legendreの三平方定理
$k$ 乗数すべての数に要る個数 $g(k)$、十分大きい数に要る個数 $G(k)$$g(k)$ は有限(Hilbert、1909 年)。$g(2)=4$、$g(3)=9$、$g(4)=19$。2002 年の時点で $G(k)$ が決まっているのは $G(2)=4$、$G(4)=16$ だけで、$4\le G(3)\le7$Waringの問題
素数偶数は $2$ 個の素数の和か、奇数は $3$ 個の素数の和か偶数の場合は未解決。十分大きい奇数は $3$ 個の素数の和(Vinogradov、1937 年)。十分大きい偶数は素数と「素因数が $2$ 個以下の数」の和(陳景潤)。$7$ 以上の奇数すべてについては Helfgott が 2013 年にプレプリントで証明を発表したGoldbach予想
自然数全体和の順序を区別しない表し方の個数は$p(n)$ の母関数は $\prod_{k\ge1}(1-x^k)^{-1}$。円周法はこの個数の研究から始まった分割数
密度が正の集合密度だけから基底と言えるかSchnirelmann 密度が正で $0$ を含む集合は有限位数の基底thm-addnt-schnirelmann

$G(3)$ の上界 $7$ は Linnik による(VW02 p. 4)。$G(k)\ge k+1$ は Waringの問題 の定理「$G(k)$ の下からの評価」にある。

有限集合の和と構造

無限集合の基底の問題と並んで、有限集合 $A$ の和 $A+A$ がどれほど小さくなれるかも調べる。この方向は 加法的組合せ論 とも呼ばれ、次の結果がある。

問い代表的な結果入る記事
$\mathbb{F}_p$ の中で $\lvert A+B\rvert$ はどこまで小さいか$\lvert A+B\rvert\ge\min\{p,\lvert A\rvert+\lvert B\rvert-1\}$Cauchy–Davenportの定理
一般のアーベル群では$\lvert A+B\rvert\le\lvert A\rvert+\lvert B\rvert-2$ なら、$A+B$ は自明でない有限部分群の剰余類の和集合であるKneserの定理(加法的組合せ論)
$n$ で割り切れる和を選べるか$2n-1$ 個の整数から和が $n$ で割り切れる $n$ 個を選べるErdős–Ginzburg–Zivの定理
和が小さい集合の反復和は$\lvert A+B\rvert\le K\lvert A\rvert$ なら $\lvert mB-nB\rvert\le K^{m+n}\lvert A\rvert$Plünnecke–Ruzsaの不等式
$\lvert A+A\rvert\le K\lvert A\rvert$ の $A$ の形は整数の有限集合なら、次元が $K$ だけで抑えられ、体積が $\lvert A\rvert$ の $K$ だけで決まる定数倍以下の一般化等差数列に含まれるFreimanの定理
上密度が正の整数の集合は等差数列を含むか任意の長さの等差数列を含むSzemerédiの定理
素数は等差数列を含むか任意の長さの等差数列を含むGreen–Taoの定理

道具の一覧

道具何をするか代表的な使い道入る記事
円周法$r_{A,h}(n)$ の積分を、有理数の近くの主弧と残りの副弧に分けて評価するWaring の問題、3 個の素数の和Hardy–Littlewoodの円周法
篩法小さい素数の倍数を除いた残りの個数を上下から評価する素因数の少ない数の和、下の Schnirelmann の方法篩法、Selbergの篩
密度の議論和を取るごとに密度が増えることを使う下の thm-addnt-schnirelmannこの記事
多項式の方法集合の上で消える多項式の次数を比べるCauchy–Davenport の定理の別証明Combinatorial Nullstellensatz、Chevalley–Warningの定理
平均の定理素数の分布の誤差を法について平均する素数と概素数の和Bombieri–Vinogradovの定理

具体例:Schnirelmann の基底定理

Schnirelmann は、集合の細かい性質を使わず「密度」だけから基底であることを導く方法を作った。この節は Pol09 第 6 章 §6.1(pp. 196–198)に沿う。$A\subset\mathbb{Z}_{\ge0}$ について $A(n):=\#\{a\in A\mid1\le a\le n\}$ とする。

Schnirelmann 密度

$A\subset\mathbb{Z}_{\ge0}$ の Schnirelmann 密度を $\delta(A):=\inf_{n\ge1}A(n)/n$ と定める。

$n=1$ の項があるので、$1\notin A$ なら $\delta(A)=0$ である。また $\delta(A)=1$ は $A$ が正の整数をすべて含むことと同値である。

密度の和が 1 以上なら和集合は全体

$0\in A\cap B$、$\delta(A)+\delta(B)\ge1$ なら $A+B=\mathbb{Z}_{\ge0}$ である。

鳩の巣原理

$n\in\mathbb{Z}_{\ge0}$ とする。$n=0$ は $0+0$ である。$n\ge1$ のとき、$A\cap[0,n]$ の元の個数は $A(n)+1$、集合 $\{n-b\mid b\in B\cap[0,n]\}$ の元の個数は $B(n)+1$ で、どちらも $\{0,1,\ldots,n\}$ の部分集合である。
$$ (A(n)+1)+(B(n)+1)\ge(\delta(A)+\delta(B))n+2\ge n+2 $$
なので、2 つの部分集合は交わる。よって $a=n-b$ となる $a\in A$、$b\in B$ がある。

和を取ると密度が増える

$0\in A\cap B$ なら $\delta(A+B)\ge\delta(A)+\delta(B)-\delta(A)\delta(B)$ である。

隙間を数える

$\beta:=\delta(B)$ とし、$n\ge1$ を固定する。$A\cap[1,n]$ の元を $a_1<\cdots< a_m$($m=A(n)$)とし、$a_0:=0$、$a_{m+1}:=n+1$ とおく。$0\le i\le m$ について $g_i:=a_{i+1}-a_i-1$ は隙間 $(a_i,a_{i+1})$ の中の整数の個数で、$\sum_{i=0}^mg_i=n-m$ である。
$b\in B$、$1\le b\le g_i$ なら $a_i+b$ は $A+B$ の元で隙間 $(a_i,a_{i+1})$ に入るので、$A+B$ はその隙間に $B(g_i)\ge\beta g_i$ 個以上の元をもつ。$0\in B$ より $A\subset A+B$ でもあるので、
$$ (A+B)(n)\ge m+\sum_{i=0}^m\beta g_i=m+\beta(n-m)=m(1-\beta)+\beta n\ge\bigl(\delta(A)+\beta-\delta(A)\beta\bigr)n $$
である。最後に $m=A(n)\ge\delta(A)n$ と $1-\beta\ge0$ を使った。$n$ で割って下限を取ればよい。

Schnirelmann の基底定理

$0\in A\subset\mathbb{Z}_{\ge0}$ で $\delta(A)>0$ なら、$A$ は有限位数の基底である。

密度を 1/2 以上に上げる

lem-addnt-growth を $B=A$ に用いると $1-\delta(2A)\le(1-\delta(A))^2$ である。$2A$ も $0$ を含むので、帰納法で $1-\delta(2^kA)\le(1-\delta(A))^{2^k}$ が成り立つ。$\delta(A)>0$ より、ある $k$ で右辺は $1/2$ 以下になり、$\delta(2^kA)\ge1/2$ である。lem-addnt-half を $A=B=2^kA$ に用いて $2^{k+1}A=\mathbb{Z}_{\ge0}$ を得る。

平方数には直接使えない。 平方数の集合 $Q$ は $Q(n)/n\to0$ なので $\delta(Q)=0$ である。一方 $Q$ は位数 $4$ の基底なので(Lagrangeの四平方定理)、$Q$ は thm-addnt-schnirelmann の逆の反例であり、$\delta(A)>0$ は基底であるための必要条件ではない。素数全体も密度が $0$ で、そのうえ $1$ を含まない。thm-addnt-schnirelmann を使うには、先に和を取って密度が正の集合を作る必要がある。実際 Schnirelmann は、$2$ 個の素数の和で表す方法の個数の上界(篩法 から得る)を使って、$2$ 個の素数の和で書ける数の集合に $0,1$ を加えた集合の密度が正であることを示し、$2$ 以上のすべての整数が決まった個数 $S$ 以下の素数の和であることを導いた(Pol09 Theorem 6.22、pp. 196–201)。定数 $S$ の大きさはこの議論の主題ではない。十分大きい整数に限れば、円周法による Vinogradov の結果から $4$ 個以下の素数の和になる(Pol09 p. 201)。
密度の定理の精密化。 Mann は lem-addnt-growth を $\delta(A+B)\ge\min\{1,\delta(A)+\delta(B)\}$ に強めた(Pol09 p. 198 の注意)。これを認めると、thm-addnt-schnirelmann の位数は $\lceil1/\delta(A)\rceil$ 以下である。この記事では Mann の定理を証明しない。

読み進め方

段階読むもの分かること
1. 初等的な表現Fermatの二平方定理 → Lagrangeの四平方定理 → Legendreの三平方定理平方和の定理と、合同式による障害
2. 問題の全体像Waringの問題、Goldbach予想、分割数基底の問いと個数の問い
3. 解析の道具解析的整数論 → Hardy–Littlewoodの円周法、篩法個数を評価する方法
4. 有限集合の和Cauchy–Davenportの定理 → Plünnecke–Ruzsaの不等式 → Freimanの定理和が小さい集合の構造
5. 等差数列van der Waerdenの定理 → Szemerédiの定理 → Green–Taoの定理密度と構造

1 の次に 4 へ進んでもよい。3 と 5 は独立に読める。

未解決問題

  • Goldbach 予想:$4$ 以上の偶数は $2$ 個の素数の和か。2026 年の時点で未解決である(Goldbach予想)。
  • $G(k)$ の決定:$G(3)=4$ と予想されている(VW02 p. 5)。2002 年の時点で、$k=2,4$ のほかに $G(k)$ の値が決まった場合はない(VW02 p. 2)。
  • 和と積の問題:実数の有限集合 $A$ について $\max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}\ge\lvert A\rvert^{2-o(1)}$ か。Erdős と Szemerédi の予想である(Zha23 Conjecture 8.0.2)。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する