加法的整数論:加法的基

提供: Mathpedia


$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\K}{\mathbb{K}}$

$\newcommand{\AA}{\mathscr{A}}$ $\newcommand{\BB}{\mathscr{B}}$ $\newcommand{\CC}{\mathscr{C}}$ $\newcommand{\PP}{\mathscr{P}}$ $\newcommand{\SS}{\mathscr{S}}$

$\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$


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

基本用語

$0$ 以上の整数全体の集合 $\NN_{\geq 0}$ の部分集合 $\AA$ は $0$ 以上の整数の狭義単調増加列（以下、単純に整数列という） $$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$ の加法的基あるいは単に基という。

例 1

先と同様、素数全体の集合を $\PP$, $0$ を含む平方数全体の集合を $\SS$ であらわすと、 Waring-Lagrangeの四平方数定理は $$\SS + \SS + \SS + \SS = \NN_{\geq 0}$$ あるいは、$\SS$ が $\NN_{\geq 0}$ の位数 $4$ の基であるとあらわされ、Goldbach予想は $$\{2n\mid n\geq 2, n\in\NN\}\subset \PP + \PP$$ とあらわされる。

Schnirelmann密度

整数列 $\AA$ のSchnirelmann密度 (Schnirelmann density) $\sigma\AA$ を $$\sigma\AA=\inf_{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\NN_{\geq 0}$ に対して、$A(n)\geq n\sigma\AA$($n=0$ のときも、両辺が $0$ なので成り立つ)。
  • $\AA\subset\BB$ ならば $\sigma\AA\leq \sigma\BB$.


例 2

奇数全体の集合のSchnirelmann密度は $1/2$. 偶数全体の集合のSchnirelmann密度は $0$ だが、$1$ と偶数全体からなる集合のSchnirelmann密度は $1/2$.

1933年にSchnirelmannは、つぎの$2$つの定理を証明した。

定理 1

$\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).$$

Proof.

$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}$$

□
定理 2

$\AA, \BB$ がともに $0$ を含む整数列で、 $$\sigma\AA + \sigma\BB\geq 1$$ となるとき $$\AA + \BB = \NN_{\geq 0}.$$

Proof.

$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=\NN_{\geq 0}$$ となることから、 $\AA$ は $\NN_{\geq 0}$ の基であることがわかる。つまり、つぎの定理が成り立つ。

定理 3

$\AA$ が $0$ を含む整数列で、$\sigma\AA>0$ ならば $\AA$ は $\NN_{\geq 0}$ の基である。

素数と加法的基

素数全体の集合 $\PP$ は $0, 1$ を含まないので加法的基ではないが、$0, 1$ を加えると加法的基となる。 具体的には、Brunの篩の応用として、次の事実が示される。

定理 4

$\PP^\prime$ を $0, 1$ および素数からなる集合とすると、$\sigma(\PP^\prime + \PP^\prime)>0.$

このことから、$\PP^\prime$ は $\NN_{\geq 0}$ の基であることがわかる。 まず、Brunの篩を用いて次の補題を示す。

補題 1

$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記号である。

Proof.

$\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の篩の定理13より、$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}$$ が示された。

□

これを用いて、定理はすぐに証明できる。

定理の証明.

$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)$$ となる。よって、先の補題から、$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$ となる。

□

Schnirelmannは、この事実と、Schnirelmann密度に関する前節の定理から、Goldbach予想の部分的解決として、つぎの事実を示した。

定理 5

ある絶対定数 $C$ について、$2$ 以上のすべての整数は $C$ 個以下の素数の和であらわされる。

Proof.

$\sigma(\PP^\prime + \PP^\prime)>0$ だから定理3より $\PP^\prime + \PP^\prime$ は $\NN_{\geq 0}$ の加法的基であるから、その位数を $k$ とおくと $\PP^\prime$ は位数 $2k$ の $\NN_{\geq 0}$ の基であるから、$n\geq 4$ のとき $$n-2=s+\sum_{i=1}^t p_i$$ かつ $$s+t\leq 2k$$ となる整数 $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$ 個の素数の和であらわされる。 よって、$4$ 以上の整数は $t+(s+1)/2\leq s+t+1\leq 2k+1$ 個以下の素数の和であらわされる。 $2, 3$ は素数だから、結局 $2$ 以上のすべての整数は $2k+1$ 個以下の素数の和であらわされる。

□

$2$ 以上のすべての整数が $C$ 個以下の素数の和としてあらわされるとき、$C$ をSchnirelmann定数という。Goldbach予想が正しければ $C=3$ となる。


Mannの定理

和集合のSchnirelmann密度については、Schnirelmannの定理より強い定理が成り立つ。

定理 6 (Mannの定理)

$\AA, \BB$ がともに $0$ を含む自然数列ならば、 $$\sigma(\AA + \BB) \geq \min\{1, \sigma\AA + \sigma\BB\}$$ が成り立つ。

すなわち、和集合は $\NN_{\geq 0}$ に一致するか、Schnirelmann密度が元の$2$ つの集合のSchnirelmann密度の和以上となる。

この定理は次の定理から容易に従う。

定理 7

$\eta$ を $0<\eta\leq 1$ の範囲にある実数とし、$n$ を正の整数とする。 また、$\AA, \BB$ がともに $0$ を含む自然数列とし、$\CC = \AA + \BB$ とする。 $$A(m)+B(m)\geq \eta m (m=1, 2, \ldots, n) \ \ \ (3.1)$$ が成り立つならば $$C(m)\geq \eta m (m=1, 2, \ldots, n) \ \ \ (3.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)$$ が成り立つということではない（実際、後者は一般には成立しない）。

定理 7から定理 6はすぐに従う。実際、 $\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$$ から $(3.1)$ はすぐに従うので、$(3.2)$ が成立する。$n$ は任意の整数をとれるから、結局 $C(n)\geq \eta n$ が任意の正の整数 $n$ について成り立つので、定理 6が成り立つ。

Proof.

$(3.1)$ が成り立つが $(3.2)$ が成り立たない $n$ が存在すると仮定し、そのような最小の $n$ をとる。 そのうえで、$(3.1)$ が成り立つが $(3.2)$ が成り立たない自然数列 $\AA, \BB$ のうち、 $B(n)$ が最小のものをとる。 また、$\AA, \BB$ は $n$ 以下の整数のみを含んでいるとしてもよい。というのは $\AA, \BB$ から $n$ より大きな要素を取り除いても、 $(3.1)$ および $(3.2)$ が成立するかどうかには関係しないからである。

$B(n)=0$ のときは、$\BB$ は $0$ しか含まないから、$\CC = \AA + \BB = \AA$ となるので、 $m=1, 2, \ldots, n$ に対して $$C(m)=A(m)=A(m)+B(m)$$ となって、$(3.1)$ が成り立つなら $(3.2)$ も成り立ってしまう。よって $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), \ \ \ (\mathrm{a})$$ $$\AA^\prime + \BB^\prime\subset \AA + \BB, \ \ \ (\mathrm{b})$$ $$B^\prime(n)<B(n). \ \ \ (\mathrm{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}$ に含まれる要素が存在する。よって $(\mathrm{c})$ が成り立つ。 $$\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$$ となるから、 $(\mathrm{b})$ が成り立つ。

$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)$$ となるので、$(\mathrm{a})$ が成り立つ。

そこで、$a^*>0$ の場合に $(\mathrm{a})$ を示す。まず $m=1, 2, \ldots, n$ を任意にとる。 $\BB^{\prime\prime}$ の定義から、$a^*+\BB^{\prime\prime}$ の要素は $\AA$ には含まれないので $$A^\prime(m)=A(m)+B^{\prime\prime}(m-a^*) \ \ \ (3.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, \ \ \ (3.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$$ となる。 一方、仮定より $(3.1)$ は $m=1, 2, \ldots, r$ について成り立つが、$r<n$ であるから、$n$ のとり方より $(3.2)$ も $m=1, 2, \ldots, r$ については成り立つ。とくに $C(r)\geq \eta r$ となる。 $(3.4)$ より $$\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)$$ となる。 また、$(3.1)$ は $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^*)$ となる。よって $(3.3)$ より $$A^\prime(m)+B^\prime(m)\geq A(m)+B(m-a^*)=A(m)+B(b_1-1)\geq \eta m$$ となる。

このようにして、$a^*>0$ の場合に $(\mathrm{a})$ が成り立つことが示された。しかし、$\CC^\prime = \AA^\prime + \BB^\prime$ とおくと、 $(\mathrm{a})$ より $m=1, 2, \ldots, n$ に対して $$A^\prime(m)+B^\prime(m)\geq \eta m$$ が成り立つが $(\mathrm{b})$ より $C^\prime(n)\leq C(n)$ となるため $C^\prime(n)\geq \eta m$ は成り立たない。つまり $\AA, \BB, \CC$ をそれぞれ $\AA^\prime, \BB^\prime, \CC^\prime$ に置き換えると $(3.1)$ は成り立つが $(3.2)$ は成り立たない。一方で $B^\prime(n)<B(n)$ となる。しかし、これは $B(n)$ が、 $(3.1)$ が成り立つが $(3.2)$ が成り立たない $\AA, \BB$ の中では最小となるという選び方に反する。

この矛盾から、$(3.1)$ が成り立つならば $(3.2)$ も成り立つことが示された。

□

参考文献

「https://math.jp/w/index.php?title=加法的整数論:加法的基&oldid=11648」から取得