十分大きい任意の整数は相異なるn乗数の和で表すことができる。

この記事では次の定理の証明を解説します*1：

定理 (Sprague, 1947) $n$ を自然数とする。このとき、ある整数 $g_n$ が存在して、 $g_n$ より大きい整数は全て相異なる $n$ 乗数の和として表すことができる。

ただし、この記事全体において $n$ 乗数と言えば「自然数の $n$ 乗数」を意味するものとします。

紹介する証明では $g_n$ は一般にとても大きい数となります。 $g_n$ として取り得る最小の整数を $r_n$ とすると、

128より大きい任意の整数は相異なる平方数の和として表すことができる。 - INTEGERS

で紹介したように $r_2=128$ です。 $r_3=12758$ であることをDressler-Parkerが1974年に計算機を用いて発見・証明しており*2、今では

$\begin{align} r_4&=5134240\\ r_5&=67898771\\ r_6&=11146309947\\ r_7&=766834015734\end{align}$

が分かっているようです。ちなみに $r_5=67898771$ は素数です。

一般に $r_n$ を求めることは非常に難しいように思われます。

Spragueの定理の証明

いくつかのステップに分けます：

Step１

主張１ Spragueの定理を証明するためには、次の条件を満たすような偶数 $s_n$ が存在することを示せばよい：
任意の自然数 $m$ に対して、 $ms_n$ は相異なる $n$ 乗数(ただし、奇数の $n$ 乗数に関しては $s_n$ 未満のもの)の和として表すことができる。

証明. 条件を満たす $s_n$ が存在したと仮定する。このとき、

$g_n:=(s_n+1)^n+(2s_n+1)^n+\cdots +((s_n-1)s_n+1)^n$

と取れる。実際、 $N$ を $g_n$ より大きい整数とし、 $N$ を $s_n$ で割った余りを $r$ とすると、

$N-(s_n+1)^n-(2s_n+2)^n-\cdots -(rs_n+1)^n \equiv r - \underbrace{1^n-\cdots -1^n}_{r} \equiv 0 \pmod{s_n}$

であり、 $N > g_n$ なので、自然数 $m$ が存在して

$N-(s_n+1)^n-(2s_n+2)^n-\cdots -(rs_n+1)^n = ms_n$

と書ける。 $s_n$ に対する条件より $ms_n$ は相異なる $n$ 乗数の和で書け、従って $N$ も $n$ 乗数の和で書ける。このとき、条件の「ただし、」の部分から $ms_n$ の分解に現れる奇数の $n$ 乗数は $s_n$ 未満であるため、 $(s_n+1)^n, \cdots, (rs_n+1)^n$ とかぶることはない(全て $s_n$ より大きい奇数)。従って、 $N$ は相異なる $n$ 乗数の和として表される。 Q.E.D.

Step２

主張２ 偶数 $s_n$ が $2^{n}-1$ 通りの「相異なる奇数の $n$ 乗数の和」としての表現をもち、 $2^n-1$ 通りの表現に現れる全ての $n$ 乗数が相異なるならば、この $s_n$ は主張１の条件を満たす。

証明. $s_n$ が主張２の条件を満たすと仮定する。 $m$ を任意の自然数とし、その $2^n$ 進数表示を

$m=a_0+a_1\cdot 2^n + a_2\cdot 2^{2n}+\cdots +a_k\cdot 2^{kn}$

とする( $0 \leq a_i < 2^n$ )。このとき、

$ms_n=a_0s_n+a_1s_n\cdot 2^n + a_2s_n\cdot 2^{2n}+\cdots +a_ks_n\cdot 2^{kn}$ -①

なので、　

主張３ 主張２の条件を満たす $s_n$ について、 $s_n, 2s_n, \dots, (2^n-1)s_n$ はそれぞれが相異なる $s_n$ 未満の奇数の $n$ 乗数の和として表される。

を示せば十分。

実際、主張３が示されれば $a_0s_n, a_1s_n, \dots, a_ks_n$ の部分がそれぞれ奇数の $n$ 乗数の和なので①より $ms_n$ は $n$ 乗数の和になっていることが分かるが、 $a_is_n\cdot 2^{in}$ に現れる $n$ 乗数と $a_js_n\cdot 2^{jn}$ に現れる $n$ 乗数では素因数分解における $2$ の指数が異なるため( $i \neq j$ )、①は相異なる $n$ 乗数の和としての表示を与える。また、その得られた表示において奇数の $n$ 乗数が現れるのは $a_0s_n$ の部分だけなので、主張１の条件を満たすことが分かる。

Step３

主張３の証明. 主張２の $s_n$ に関する条件によって存在する $2^n-1$ 通りの「相異なる奇数の $n$ 乗数の和」としての表現をそれぞれ

$\begin{equation}\begin{split} s_n &= b_{1, 1}^n+\cdots +b_{1, l_1}^n \\ &= b_{2, 1}^n+ \cdots +b_{2, l_2}^n \\ &= \cdots \\ &= b_{2^n-1, 1}^n+\cdots +b_{2^n-1, l_{2^n-1}}^n\end{split}\end{equation}$

とする( $b_{i, j}$ は全て $s_n$ 未満の奇数で相異なる)。このとき、 $1 \leq a \leq 2^n-1$ を満たす任意の整数 $a$ に対して、 $as_n$ は

$as_n = b_{1, 1}^n+ \cdots + b_{1, l_1}^n+b_{2, 1}^n+\cdots +b_{2, l_2}^n+\cdots +b_{a, 1}^n+ \cdots +b_{a, l_a}^n$

と相異なる $s_n$ 未満の奇数の $n$ 乗数の和として表される。 Q.E.D.

Step４

主張４ ある偶数 $l$ と相異なる $2l$ 個の正の奇数 $k_1, \dots, k_{2l}$ が存在して、 $x$ の多項式に関する恒等式

$(x+k_1)^n+\cdots + (x+k_l)^n = (x+k_{l+1})^n+\cdots +(x+k_{2l})^n$ -②

が成り立てば、主張２の条件を満たす $s_n$ が存在する。

証明. $n$ 個の偶数 $d_1, \dots, d_n$ を $2ln$ 個の整数

$k_j+d_i \ \ \ (j=1, \dots, 2l, \ i = 1, \dots, n)$

が全て相異なるように取る。そうして、 $i=1, \dots, n$ に対して多項式 $f_i^0(x), f_i^1(x)$ を

$\begin{align} f_i^0(x) &:= (x+k_1+d_i)^n+\cdots +(x+k_l+d_i)^n \\ f_i^1(x) &:= (x+k_{l+1}+d_i)^n+\cdots +(x+k_{2l}+d_i)^n \end{align}$

と定義する。 $\epsilon_1, \dots, \epsilon_n \in \{0, 1\}$ に対して

$\displaystyle f_1^{\epsilon_1}(x)\cdots f_n^{\epsilon_n}(x) = \sum_{1 \leq j_1, \dots, j_n \leq l} \left\{ \prod_{i=1}^n(x+k_{j_i+\epsilon_i(2l-2j_i+1)}+d_i) \right\}^n$

を考える。 $x$ に正の偶数を代入すると $l^n$ 個の奇数の $n$ 乗数の和になっていることに注意する。

$\epsilon_1, \dots, \epsilon_n$ の全ての取り方のケースを考えることにより $2^n$ 個の多項式が得られ、

$\displaystyle \prod_{i=1}^n(x+k_{j_i+\epsilon_i(2l-2j_i+1)}+d_i)$

の形の多項式が $(2l)^n$ 個現れることになる。 $d_i$ の取り方からこれらは全て多項式として相異なる。異なる多項式が一致するような $x$ は高々有限個しかないため、十分大きい整数を $x$ に代入したときに得られる $(2l)^n$ 個の数は全て相異なる。そのような整数を正の偶数として取り、 $c$ とする。

このとき、 $s_n$ を $f_1^{\epsilon_1}(c)\cdots f_n^{\epsilon_n}(c)$ と定義すると、恒等式②よりこれは $\epsilon_1, \dots, \epsilon_n$ の取り方に依らない値であり、従って $s_n$ は $2^n$ 通りの「 $l^n$ 個の相異なる奇数の $n$ 乗数の和」としての表現を持ち、そこに現れる $(2l)^n$ 個の $n$ 乗数は全て相異なる。 Q.E.D.

Step５

主張５ ある偶数 $l$ と相異なる $2l$ 個の正の奇数 $k_1, \dots, k_{2l}$ が存在して

$k_1^i+\cdots +k_l^i = k_{l+1}^i+\cdots +k_{2l}^i$

が $i=1, 2, \dots, n$ で成り立てば、恒等式②が成立する。

証明. 主張５の仮定が成り立つと仮定すると、②の両辺の多項式をそれぞれ展開して整理した後の $x^i \ (i=0, \dots, n)$ の係数が全て等しいことから②の恒等式が成立することがわかる。 Q.E.D.

Step６

今までの議論では $n$ を固定して差し支えなかったですが(Step４の $c$ などは $n$ 毎に決まる整数)、次の主張は $n$ に関する帰納法で証明します：

主張６ 自然数 $n$ 毎に相異なる $2^{n+1}$ 個の正の奇数 $k_1^{(n)}, \dots, k_{2^{n+1}}^{(n)}$ が存在して

$(k_1^{(n)})^i+\cdots +(k_{2^n}^{(n)})^i = (k_{2^n+1}^{(n)})^i+\cdots +(k_{2^{n+1}}^{(n)})^i$

が $i=1, 2, \dots, n$ に対して成立する。更に、 $k_j^{(n)} < 2^{n+2} \ (j=1, \dots, 2^{n+1})$ が成り立つようにできる。

証明. $n=1$ のときは $l_1=2$ と取ることができ、等式

$1+7=3+5$

より題意が成立することが分かる。 $n$ のときに成立すると仮定しよう。すなわち、

$(k_1^{(n)})^i+\cdots +(k_{2^n}^{(n)})^i = (k_{2^n+1}^{(n)})^i+\cdots +(k_{2^{n+1}}^{(n)})^i \ \ (i=1, 2, \dots, n)$

が成り立つと仮定する( $k_j^{(n)} < 2^{n+2} \ (j=1, \dots, 2^{n+1})$ )。このとき、

$\begin{equation}\begin{split}(k_1^{(n)})^i+&\cdots +(k_{2^n}^{(n)})^i+(k_{2^n+1}^{(n)}+2^{n+2})^i + \cdots +(k_{2^{n+1}}^{(n)}+2^{n+2})^i \\ & = (k_{2^n+1}^{(n)})^i+\cdots +(k_{2^{n+1}}^{(n)})^i +(k_1^{(n)}+2^{n+2})^i+\cdots +(k_{2^n}^{(n)}+2^{n+2})^i \end{split}\end{equation}$