インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

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

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

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

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

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

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

integers.hatenablog.com

で紹介したように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"。