インテジャーズ

INTEGERS

数、特に整数に関する記事。

十分大きい任意の整数は相異なる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の定理の証明

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

Step1

主張1 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

と取れる。実際、Ng_nより大きい整数とし、Ns_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乗数の和で書け、従ってNn乗数の和で書ける。このとき、条件の「ただし、」の部分からms_nの分解に現れる奇数のn乗数はs_n未満であるため、(s_n+1)^n, \cdots, (rs_n+1)^nとかぶることはない(全てs_nより大きい奇数)。従って、Nは相異なるn乗数の和として表される。 Q.E.D.

Step2

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

証明. s_nが主張2の条件を満たすと仮定する。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} -①

なので、 

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

を示せば十分。

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

Step3

主張3の証明. 主張2の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.

Step4

主張4 ある偶数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 -②

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

証明. n個の偶数d_1, \dots, d_n2ln個の整数

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

Step5

主張5 ある偶数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で成り立てば、恒等式②が成立する。

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

Step6

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

主張6 自然数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}

i=1, \dots, n+1で成立し、n+1のときに期待される性質が全て満たされていることがわかる。 Q.E.D.

証明完了

Step6によってStep5の仮定が成り立つことが確認されるので、Spragueの定理の証明は完結します。

*1:Grahamの定理の証明に用います。

*2:論文のタイトルは"12,758"。