はじめに

加法的整数論における基本概念である加法的基について解説する。

加法的基

$0$ 以上の整数全体の集合 $\N_{\geq 0}$ の部分集合 $\AA$ は
$0$ 以上の整数の狭義単調増加列（以下、単純に**整数列** (*integer sequence*) という）
$$0=a_0<a_1<a_2<\cdots$$
あるいは
$$0<a_1<a_2<\cdots$$
とみることができる。

整数列 $\AA$ に対して、
$n$ 以下の正の項の個数を $A(n)$ であらわす。ただし $A(0)=0$ とおく。
$A(n)$ を $\AA$ の**計数関数** (*counting function*) という。
$$k=A(n)\Longleftrightarrow a_k\leq n<a_{k+1}$$
が成り立つ。

$2$つの整数列 $\AA, \BB$ の**和集合** (*sumset*) を、$\AA$ と $\BB$ の要素の和であらわされる数全体の集合
$$\AA+\BB=\{a+b\mid a\in\AA, b\in\BB\}$$
と定める（unionとは全く別概念なので、混同しないように）。

$h\AA\supset \BB$ となるとき、$\AA$ を $\BB$ の位数 $h$ の**加法的基** (*additive basis*) あるいは単に**基** (*basis*) という。
そのような整数 $h\geq 1$ が存在するとき、$\AA$ を $\BB$ の加法的基あるいは単に基という。

&&&ex [ex1]
先と同様、素数全体の集合を $\PP$, $0$ を含む平方数全体の集合を $\SS$ であらわすと、
Waring-Lagrangeの四平方数定理は
$$\SS + \SS + \SS + \SS = \N_{\geq 0}$$
あるいは、$\SS$ が $\N_{\geq 0}$ の位数 $4$ の基であるとあらわされ、Goldbach予想は
$$\{2n\mid n\geq 2, n\in\N\}\subset \PP + \PP$$
とあらわされる。
&&&

基本用語

加法的整数論は、整数や自然数などの加法的な性質について扱う理論である。すなわち
$\Z$, $\N$, より一般にある加法半群 $G$ の要素 $g$ を、$G$ の部分集合 $A_1, A_2, \ldots, A_k$ の要素の和
$$g=a_1+a_2+\ldots +a_k\ (a_i\in A_i)$$
としてあらわす方法について扱う理論である。

具体的な例としては、つぎのような定理、予想、問題がある。

&&&ex Lagrangeの定理 [ex1]
$\SS$ を、$0$ を含む平方数全体の集合とすると、$\N_{\geq 0}=\{0, 1, \ldots\}$ の任意の要素 $n$ は $n=a_1+a_2+a_3+a_4 (a_i\in\SS)$ の形にあらわすことができる。
&&&

&&&ex Goldbachの予想 [ex2]
$\PP$ を素数全体の集合とすると、$4$ 以上のすべての偶数 $n$ は $n=p+q (p, q\in\PP)$ の形にあらわすことができる。
&&&

&&&ex 郵便切手の問題 [ex3]
整数 $k\geq 2$ を定める。$A$ が $\N_{\geq 0}$ の部分集合で、$0\leq m\leq n$ となる任意の整数 $m$ が $a_1+a_2+\ldots+a_k (a_i\in A)$ の形であらわされるとする。そのような $A$ で要素の数が可能な限り少ないものを求めよ。
&&&

&&&ex 硬貨交換問題 [ex4]
整数 $n\geq 2$ と、互いに素な正の整数 $a_1, a_2, \ldots, a_n$ が与えられたとき、$0$ 以上の整数 $k_1, \ldots, k_n$ により $k_1 a_1+k_2 a_2+ \cdots +k_n a_n$ の形であらわされない最小の整数を求めよ。
&&&



整数列 $\AA$ の**Schnirelmann密度** (*Schnirelmann density*) $\sigma\AA$ を
$$\sigma\AA=\liminf_{n\geq 1}\frac{A(n)}{n}$$
により定める。

つぎのことがすぐにわかる。
* $1\not\in\AA$ ならば $\sigma\AA=0$.
* $\lim_{n\rightarrow\infty} A(n)/n=0$ ならば $\sigma\AA=0$.
* $\sigma\AA=1$ ならば $\AA=\mathbb{N}_{\geq 0}$ または $\AA=\mathbb{N}_{>0}=\{1, 2, \ldots\}$.
* $n\in\N_{\geq 0}$ に対して、$A(n)\geq n\sigma\AA$($n=0$ のときも、両辺が $0$ なので成り立つ)。
* $\AA\subset\BB$ ならば $\sigma\AA\leq \sigma\BB$.

&&&ex [ex1]
奇数全体の集合のSchnirelmann密度は $1/2$.
偶数全体の集合のSchnirelmann密度は $0$ だが、$1$ と偶数全体からなる集合のSchnirelmann密度は $1/2$.
&&&

1933年にSchnirelmannは、つぎの$2$つの定理を証明した。
&&&thm [th1]
$\AA$ が $1$ を含む整数列で、$\BB$ が $0$ を含む整数列ならば
$$\sigma(\AA + \BB)\geq \sigma\AA + \sigma\BB - \sigma\AA \sigma\BB$$
あるいは
$$1-\sigma(\AA + \BB)\leq (1- \sigma\AA)(1 - \sigma\BB).$$
&&&

&&&prf
$A(n)=r$ とおく。
$0\in\BB$ より、$a_i=a_i+0\in \AA + \BB$ となる。
$g_i=a_{i+1}-a_i-1$ とおくとき、$i\leq r-1$ かつ $0<b_j\leq g_i$ ならば $a_i+b_j\in \AA + \BB$ かつ
$$a_i<a_i+b_j<a_{i+1}\leq n$$
となる。さらに $0<b_j\leq n-a_r$ ならば $a_r+b_j\in \AA + \BB$ かつ
$$a_r<a_r+b_j<\leq n$$
となる。よって
$$\begin{split}
(A+B)(n)\geq & A(n)+\sum_{i=1}^r B(g_i)+B(n-a_r) \\
\geq & n\sigma\AA + \sigma\BB ((n-a_r)+\sum_{i=1}^{r-1} g_i) \\
\geq & n\sigma\AA + \sigma\BB (n-a_r+\sum_{i=1}^{r-1} (a_{i+1}-a_i-1)) \\
= & n\sigma\AA + \sigma\BB (n-a_1-(r-1)) \\
= & n\sigma\AA + \sigma\BB (n-r)\geq n(\sigma\AA + \sigma\BB - \sigma\AA\sigma\BB).
\end{split}$$
&&&

&&&thm [th2]
$\AA, \BB$ がともに $0$ を含む整数列で、
$$\sigma\AA + \sigma\BB\geq 1$$
となるとき
$$\AA + \BB = \N_{\geq 0}.$$
&&&

&&&prf
$2$ 以上の任意の整数 $n$ をとり、 $n\in \AA + \BB$ となることを示す。
仮定より $0\in\BB$ だから、$n\in\AA$ ならば
$$n=n+0\in \AA + \BB$$
となる。$n$ が $\AA$ に含まれないとし、$A(n-1)=r, B(n-1)=s$ とおくと、
$A(n)=A(n-1)=r$ であるから
$$r+s=A(n)+B(n-1)\geq n\sigma\AA + (n-1)\sigma\BB>(n-1)(\sigma\AA + \sigma\BB) \geq n-1$$
より $r+s>n-1$ である。
$$1\leq b_1<\cdots <b_s\leq n-1$$
より
$$n-1\geq n-b_1>\cdots b_s\geq 1$$
であるから、
$r+s$ 個の数 $a_1, a_2, \ldots, a_r, n-b_1, n-b_2, \ldots, n-b_s$ はすべて
$$1\leq a_1, a_2, \ldots, a_r, n-b_1, n-b_2, \ldots, n-b_s\leq n-1$$
となる。よって
$$a_i=n-b_j$$
となる $i, j$ が存在するので
$$n=a_i+b_j\in \AA + \BB$$
となる。
&&&

この2つの定理から、$\AA$ が $0$ を含む整数列で、$\sigma\AA>0$ ならば
$$1-\sigma(h\AA)\leq (1-\sigma\AA)^h$$
となり、$\sigma(h_0\AA)\geq 1/2$ となる $h_0$ が存在し、
$$2h_0\AA=h_0\AA + h_0\AA=\N_{\geq 0}$$
となることから、 $\AA$ は $\N_{\geq 0}$ の基であることがわかる。


Schnirelmann密度

和集合のSchnirelmann密度については、Schnirelmannの定理より強いMannの定理が成り立つ。

&&&thm Mann, 1942 [th1]
$\AA, \BB$ がともに $0$ を含む自然数列ならば、
$$\sigma(\AA + \BB) \geq \min\{1, \sigma\AA + \sigma\BB\}$$
が成り立つ。
&&&
すなわち、和集合は $\N_{\geq 0}$ に一致するか、Schnirelmann密度が元の$2$ つの集合のSchnirelmann密度の和以上となる。

本節ではHalberstam-Roth [[HR]], Chapter I の方法によりこの定理を証明する。この定理は次の定理から容易に従う。

&&&thm Halberstam-Roth [[HR]], Chapter I, Theorem $3^\prime$ [th2]
$\eta$ を $0<\eta\leq 1$ の範囲にある実数とし、$n$ を正の整数とする。
また、$\AA, \BB$ がともに $0$ を含む自然数列とし、$\CC = \AA + \BB$ とする。
$$A(m)+B(m)\geq \eta m (m=1, 2, \ldots, n)\label{eq1}\tag{1}$$
が成り立つならば
$$C(m)\geq \eta m (m=1, 2, \ldots, n)\label{eq2}\tag{2}$$
が成り立つ。
&&&

この定理は
$$[A(m)+B(m)\geq \eta m (\forall m=1, 2, \ldots n)]\Longrightarrow [C(m)\geq \eta m (\forall m=1, 2, \ldots n)]$$
が成り立つといっているのであって、
$$[A(m)+B(m)\geq \eta m \Longrightarrow C(m)\geq \eta m] (\forall m=1, 2, \ldots n)$$
が成り立つということではない（実際、後者は一般には成立しない）。

[定理2](#th2)から[定理1](#th1)はすぐに従う。実際、$\eta=\min\{1, \sigma\AA + \sigma\BB\}$ とおくと、$m=1, 2, \ldots, n$ に対して
$$A(m)+B(m)\geq (\sigma\AA) m+(\sigma\BB) m\geq \eta m$$
から\eqref{eq1}はすぐに従うので、定理2のもとでは\eqref{eq2}が成立する。$n$ は任意の整数をとれるから、結局 $C(n)\geq \eta n$ が任意の正の整数 $n$ について成り立つので、[定理1](#th1)が成り立つ。

&&&prf
\eqref{eq1}が成り立つが\eqref{eq2}が成り立たない $n$ が存在すると仮定し、そのような最小の $n$ をとる。
そのうえで、\eqref{eq1}が成り立つが\eqref{eq2}が成り立たない自然数列 $\AA, \BB$ のうち、 $B(n)$ が最小のものをとる。
また、$\AA, \BB$ は $n$ 以下の整数のみを含んでいるとしてもよい。というのは $\AA, \BB$ から $n$ より大きな要素を取り除いても、\eqref{eq1}および\eqref{eq2}が成立するかどうかには関係しないからである。

$B(n)=0$ のときは、$\BB$ は $0$ しか含まないから、$\CC = \AA + \BB = \AA$ となるので、$m=1, 2, \ldots, n$ に対して
$$C(m)=A(m)=A(m)+B(m)$$
となって、\eqref{eq1}が成り立つなら\eqref{eq2}も成り立ってしまう。よって $B(n)>0$ となって、$\BB$ は正の要素を含むことがわかる。

$a+\BB\subset \AA$ が成り立たないような $a\in \AA$ が存在することは容易に確かめられる。実際、$\BB$ は正の要素を含むので、$a_r, b_s$ を $\AA, \BB$ の最大の要素とおくと、$a_r+b_s$ は $a_r$ より大きいから、これは $\AA$ に含まれない。

さて、
$$A^\prime(m)+B^\prime(m)\geq \eta m ~ (\forall m=1, 2, \ldots n), \label{eqa}\tag{a}$$
$$\AA^\prime + \BB^\prime\subset \AA + \BB, \label{eqb}\tag{b}$$
$$B^\prime(n)<B(n)\label{eqc}\tag{c}$$
が成り立つように自然数列 $\AA^\prime, \BB^\prime$ を構成する。

まず、$a + \BB\subset \AA$ が成り立たないような、最小の $a\in \AA$ を $a^*$ とおいて
$$\BB^\prime = \{b\in \BB, a^*+b\in \AA\}, \BB^{\prime\prime} = \BB \setminus \BB^\prime = \{b\in \BB, a^*+b\not\in \AA\}$$
とおくと、$a^*\in \AA$ より $\BB^\prime$ は $0$ を含む。また、$a + \BB\subset \AA$ が成り立たないのだから、$\BB^{\prime\prime}$ に含まれる要素が存在する。よって\eqref{eqc}が成り立つ。
$$\AA^\prime=\AA \cup \left((a^* + \BB^{\prime\prime})\cap [0, n]\right)$$
とおくと、$b^\prime\in \BB^\prime, b^{\prime\prime}\in \BB^{\prime\prime}$ に対して
$$(a^*+b^{\prime\prime})+b^\prime=(a^*+b^\prime)+b^{\prime\prime}\in \AA + \BB$$
となるから、\eqref{eqb}が成り立つ。

$a^*=0$ の場合、
$$\BB^\prime = \AA \cap \BB, \AA^\prime=\AA\cup \BB^{\prime\prime}=\AA \cup (\BB\setminus \AA)$$
なので、
$$A^\prime(n)+B^\prime(n)=A(n)+(B(n)-B^\prime(n))+B^\prime(n)=A(n)+B(n)$$
となるので、\eqref{eqa}が成り立つ。

そこで、$a^*>0$ の場合に\eqref{eqa}を示す。まず $m=1, 2, \ldots, n$ を任意にとる。$\BB^{\prime\prime}$ の定義から、$a^*+\BB^{\prime\prime}$ の要素は $\AA$ には含まれないので
$$A^\prime(m)=A(m)+B^{\prime\prime}(m-a^*)\label{eq3}\tag{3}$$
となる。
$\BB$ が $m-a^*<b\leq m$ となる要素を含まないとき、$B^{\prime\prime}(m-a^*)=B^{\prime\prime}(m)$ なので、
$$A^\prime(m)+B^\prime(m)=A(m)+B^{\prime\prime}(m)+B^\prime(m)=A(m)+B(m)$$
となる。
そこで、$\BB$ が $m-a^*<b\leq m$ となる要素を含むとし、そのような最小の要素を $b_1$ とおく。
$m=b_1+r$ とおくと、 $0\leq r<a^*$ となるから、$r$ 以下の $\AA$ の要素 $a$ について
$$a+\BB\subset \AA$$
が成り立つ。よって
$$(\AA \cup [0, r])+\BB\subset \AA\label{eq4}\tag{4}$$
とくに
$$(\AA \cup [0, r])+b_1\subset \AA$$
となる。つまり $0\leq a\leq r$ で $a$ が $\AA$ の要素ならば、$b_1+a$ も $\AA$ の要素である。
よって
$$A(b_1+r)-A(b_1-1)\geq A(r)+1$$
となる。

一方、仮定より\eqref{eq1}は $m=1, 2, \ldots, r$ について成り立つが、$r<n$ であるから、$n$ のとり方より\eqref{eq2}も $m=1, 2, \ldots, r$ については成り立つ。とくに $C(r)\geq \eta r$ となる。\eqref{eq4}より
$$\CC\cup [0, r]\subset \AA$$
となるから、$A(r)\geq C(r)$ となり、
$$A(b_1+r)-A(b_1-1)\geq C(r)+1\geq \eta(r+1)$$
となる。
また、\eqref{eq1}は $m=1, 2, \ldots, n$ について成り立つので
$$A(b_1-1)+B(b_1-1)\geq \eta(b_1-1)$$
が成り立つ。よって
$$A(b_1+r)+B(b_1-1)\geq \eta (b_1+r)=\eta m$$
となる。$b_1$ は $m-a^*<b\leq m$ となる $\BB$ の最小の要素だから、$B(b_1-1)=B(m-a^*)$ となる。よって\eqref{eq3}より
$$A^\prime(m)+B^\prime(m)\geq A(m)+B(m-a^*)=A(m)+B(b_1-1)\geq \eta m$$
となる。

このようにして、$a^*>0$ の場合に\eqref{eqa}が成り立つことが示された。しかし、$\CC^\prime = \AA^\prime + \BB^\prime$ とおくと、\eqref{eqa}より $m=1, 2, \ldots, n$ に対して
$$A^\prime(m)+B^\prime(m)\geq \eta m$$
が成り立つが\eqref{eqb}より $C^\prime(n)\leq C(n)$ となるため $C^\prime(n)\geq \eta m$ は成り立たない。つまり $\AA, \BB, \CC$ をそれぞれ $\AA^\prime, \BB^\prime, \CC^\prime$ に置き換えると\eqref{eq1}は成り立つが\eqref{eq2}は成り立たない。一方で\eqref{eqc}より $B^\prime(n)<B(n)$ となる。しかし、これは $B(n)$ が、\eqref{eq1}が成り立つが\eqref{eq2}が成り立たない $\AA, \BB$ の中では最小となるという選び方に反する。

この矛盾から、\eqref{eq1}が成り立つならば\eqref{eq2}も成り立つことが示された。
&&&


Mannの定理

素数全体の集合 $\PP$ は $0, 1$ を含まないので加法的基ではないが、$0, 1$ を加えると加法的基となる。
具体的には、[Brunの篩](/textbooks/be48bcSfeIPwMZ4U0pfg/TtzkDOOg4QeKcLDJF9Ek)の応用として、次の事実が示される。

&&&thm [th1]
$\PP^\prime$ を $0, 1$ および素数からなる集合とすると、$\sigma(\PP^\prime + \PP^\prime)>0.$
&&&

このことから、$\PP^\prime$ は $\N_{\geq 0}$ の基であることがわかる。
まず、Brunの篩を用いて次の補題を示す。

&&&lem [lm2]
$r(n)$ を、整数 $n$ を$2$つの素数の和 $p+q$ の形にあらわす方法の個数とすると、$x\geq 4$ のとき
$$\sum_{n\leq x}r(n) \gg \frac{x^2}{\log^2 x}$$
かつ
$$\sum_{n\leq x}r^2 (n) \ll \frac{x^3}{\log^4 x}.$$
ただし $n=p+q$ とあらわすうえで、$p=q$ でもよく、また $p, q$ を入れ替えたものは別の表現として数える。また、$\gg, \ll$ は[Vinogradov記号](/glossaries/Rbm0v1DpSK7G3GzcEc9Q)である。
&&&

&&&prf
$\sum_{n\leq x}r(n)$ は $p+q\leq x$ となる素数の組 $(p, q)$ の総数と一致するが、$p, q$ が $x/2$ 以下の素数ならば $p+q\leq x$ となるので、$x\geq 4$ のとき
$$\sum_{n\leq x}r(n) \geq (\pi(x/2))^2\gg\frac{(x/2)^2}{\log^2(x/2)}\gg\frac{x^2}{\log^2 x}$$
となるのでひとつ目の不等式が示される。

一方、[「篩法」Brunの篩（応用）の定理3](/textbooks/be48bcSfeIPwMZ4U0pfg/TtzkDOOg4QeKcLDJF9Ek#th3)より、$n$ が偶数のとき
$$r(n)\ll \frac{f(n)n}{\log^2 n}\leq \frac{n}{\log^2 n}\sum_{d\mid n}\frac{1}{d}$$
となる。ただし、
$$f(n)=\prod_{p\mid n}\left(1+\frac{1}{p}\right)$$
である。また、$n$ が奇数の場合、 $n=p+q$ ならば $p, q$ の一方が $2$ でなければならないから $n$ が奇数ならば $r(n)\leq 2$ となるので、結局上記の不等式はすべての正の整数について成り立つ。
よって
$$\begin{split}
\sum_{n\leq x} r^2(n) & \ll \sum_{n\leq x}\frac{n}{\log^2 n}\left(\sum_{d\mid n}\frac{1}{d}\right)^2 \\
& \leq \frac{x^2}{\log^4 x}\sum_{n\leq x} \sum_{d_1, d_2\mid n}\frac{1}{d_1 d_2} \\
& =\frac{x^2}{\log^4 x}\sum_{d_1, d_2\leq x} \frac{1}{d_1 d_2} \#\{n\leq x: (d_1\mid n)\land(d_2\mid n)\} \\
& \leq \frac{x^2}{\log^4 x}\sum_{d_1, d_2\leq x} \frac{x}{d_1 d_2\mathrm{LCM}[d_1, d_2]}
\end{split}$$
となるが、
$$\mathrm{LCM}[d_1, d_2]\geq \max\{d_1, d_2\}\geq (d_1 d_2)^{1/2}$$
より
$$\begin{split}
\sum_{n\leq x} r^2(n) & \leq \frac{x^3}{\log^4 x}\sum_{d_1, d_2\leq x} \frac{1}{(d_1 d_2)^{3/2}} \\
& =\frac{x^3}{\log^4 x}\left(\sum_{d\leq x}\frac{1}{d^{3/2}}\right)^2 \\
& <\frac{\zeta^2(3/2)x^3}{\log^4 x}
\end{split}$$
となるので
$$\sum_{n\leq x}r^2 (n) \ll \frac{x^3}{\log^4 x}$$
が示された。
&&&

これを用いて、[定理1](#th1)はすぐに証明できる。
実際、$A=\PP^\prime + \PP^\prime$ とおくと、Cauchy-Schwarzの不等式から
$$\left(\sum_{n\leq x}r(n)\right)^2\leq A(x)\sum_{n\leq x}r^2(n)$$
となる。よって、[先の補題](#lm2)から、$x\geq 4$ のとき
$$\frac{x^4}{\log^4 x}\ll A(x)\frac{x^3}{\log^4 x}$$
つまり
$$A(x)\gg x$$
となる。$A$ は $0, 1$ を含むので、$\sigma A>0$ となる。

このことから、Goldbach予想の部分的解決として、つぎのSchnirelmannの定理が示される。

&&&thm [th3]
十分大きなすべての整数は $C$ 個以下の素数の和であらわされる。
&&&

&&&prf
[Schnirelmanの定理](./Fv9n85fvRrTFZil1IkYy)あるいは[Mannの定理](./xF1TbXZ7mTHjl5Vcn37x)より $\PP$ は $\N_{\geq 0}$ の基であるから、その位数を $k$ とおくと
$$n-2=s+\sum_{i=1}^t p_i$$
かつ
$s+t\leq k$
となる整数 $s, t$ および素数 $p_1, p_2, \ldots, p_t$ が存在する。
よって
$$n=s+2+\sum_{i=1}^t p_i$$
となる。$s=2m$ が偶数の場合
$$n=2(m+1)+\sum_{i=1}^t p_i$$
となるので、$n$ は $m+t+1\leq t+(s+1)/2$ 個の素数の和であらわされる。
$s=2m+1$ が奇数の場合
$$n=2m+3+\sum_{i=1}^t p_i$$
となるので、やはり $n$ は $m+t+1\leq t+(s+1)/2$ 個の素数の和であらわされる。
&&&

素数と加法的基

Sequences (reprinted version)

加法的整数論は、整数や自然数などの加法的な性質について扱う理論である。すなわち
$\mathbb{Z}$, $\mathbb{N}$, より一般にある加法半群 $G$ の要素 $g$ を、$G$ の部分集合 $A_1, A_2, \ldots, A_k$ の要素の和
$$g=a_1+a_2+\ldots +a_k\ (a_i\in A_i)$$
としてあらわす方法について扱う理論である。

すべての自然数が$4$つの平方数の和であらわされるというLagrangeの定理、
$4$ 以上のすべての偶数が$2$つの素数の和であらわされるというGoldbachの予想、
与えられた数 $n$ 以下のすべての整数が、ある部分集合 $A$ について、一定の個数以下の $A$ の要素の和であらわされるとき、
そのような部分集合 $A$ で要素の数が可能な限り少ないものをもとめる郵便切手の問題などが加法的整数論で取り扱われる。

基本用語

参考文献