インテジャーズ

インテジャーズ

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

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

128と言えば2^7ですが、「相異なる平方数の和として表すことができない最大の整数」という特徴を持っています。

すなわち、相異なる平方数の和として表すことができない自然数は有限個しか存在せず、それは次の31個の整数です:

\begin{equation}\begin{split}&2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67,\\ &72, 76, 92, 96, 108, 112, 128\end{split}\end{equation}

Lagrangeの四平方の定理は「全ての自然数は4つ以下の平方数の和として表すことができる」というものでしたが、「相異なる」という条件はなかったことに注意してください。
integers.hatenablog.com

129以上の整数が必ず相異なる平方数の和として表すことができることの証明には次の補題を使います:

補題 (Sierpinski 1955) 自然数列\{a_n\}_{n=1}^{\infty}が次の二条件を満たすと仮定する:

  1. 非負整数rが存在して、n \geq r+1に対してa_{n+1}\leq 2a_nが成り立つ。
  2. 非負整数lが存在して、l\leq N < l+a_{r+1}なる任意の整数NN=\sum_{n=1}^r\epsilon_na_n \ (\epsilon_n \in \{0, 1\})と書ける。

このとき、l以上の任意の整数は数列\{a_n\}_{n=1}^{\infty}の有限個の相異なる項の和として表される(ただし、l=0のときは0個の和=0も含める)。

証明は最後に紹介します。まずは応用しましょう。

応用1 (Sprague 1948) 129以上の任意の整数は相異なる平方数の和として表すことができる。

証明. a_n=n^2とする。n \geq 3(n+1)^2 \leq 2n^2が成り立つ。l=129, r=10として補題を適用する。条件2を満たすことは次のように確かめられる(表示法は一意ではないですが、適当に手計算で見つけているため、使う平方数の個数を最小にするなどはしていないです):

\begin{equation}\begin{split}
129 &= 2^2+5^2+10^2\\ 
130 &= 1^2+2^2+5^2+10^2\\
131 &= 3^2+4^2+5^2+9^2\\
132 &= 1^2+3^2+4^2+5^2+9^2\\
133 &= 4^2+6^2+9^2\\
134 &= 1^2+4^2+6^2+9^2\\
135 &= 2^2+3^2+4^2+5^2+9^2\\
136 &= 6^2+10^2\\
137 &= 1^2+6^2+10^2\\
138 &= 2^2+3^2+5^2+10^2\\
139 &= 1^2+2^2+3^2+5^2+10^2\\
140 &= 2^2+6^2+10^2\\
141 &= 1^2+2^2+6^2+10^2\\
142 &= 5^2+6^2+9^2\\
143 &= 1^2+5^2+6^2+9^2\\
144 &= 1^2+2^2+3^2+7^2+9^2\\
145 &= 2^2+4^2+5^2+10^2\\
146 &= 2^2+5^2+6^2+9^2\\
147 &= 1^2+2^2+5^2+6^2+9^2\\
148 &= 1^2+3^2+5^2+7^2+8^2\\
149 &= 7^2+10^2\\
150 &= 1^2+7^2+10^2\\
151 &= 3^2+5^2+6^2+9^2\\
152 &= 1^2+3^2+5^2+6^2+9^2\\
153 &= 2^2+7^2+10^2\\
154 &= 1^2+2^2+7^2+10^2\\
155 &= 5^2+7^2+9^2\\
156 &= 1^2+5^2+7^2+9^2\\
157 &= 1^2+2^2+4^2+6^2+10^2\\
158 &= 3^2+7^2+10^2\\
159 &= 1^2+3^2+7^2+10^2\\
160 &= 1^2+2^2+3^2+4^2+7^2+9^2\\
161 &= 3^2+4^2+6^2+10^2\\
162 &= 2^2+3^2+7^2+10^2\\
163 &= 1^2+2^2+3^2+7^2+10^2\\
164 &= 8^2+10^2\\
165 &= 1^2+8^2+10^2\\
166 &= 1^2+2^2+3^2+4^2+6^2+10^2\\
167 &= 3^2+4^2+5^2+6^2+9^2\\
168 &= 1^2+3^2+4^2+5^2+6^2+9^2\\
169 &= 1^2+2^2+8^2+10^2\\
170 &= 5^2+8^2+9^2\\
171 &= 2^2+3^2+4^2+5^2+6^2+9^2\\
172 &= 1^1+2^2+3^2+4^2+5^2+6^2+9^2\\
173 &= 3^2+8^2+10^2\\
174 &= 2^2+5^2+8^2+9^2\\
175 &= 1^2+2^2+5^2+8^2+9^2\\
176 &= 1^2+3^2+6^2+7^2+9^2\\
177 &= 2^2+3^2+8^2+10^2\\
178 &= 1^2+2^2+3^2+8^2+10^2\\
179 &= 2^2+3^2+6^2+7^2+9^2\\
180 &= 1^2+2^2+3^2+6^2+7^2+9^2\\
181 &= 6^2+8^2+9^2\\
182 &= 1^2+6^2+8^2+9^2\\
183 &= 2^2+3^2+5^2+8^2+9^2\\
184 &= 1^2+2^2+3^2+5^2+8^2+9^2\\
185 &= 2^2+6^2+8^2+9^2\\
186 &= 4^2+5^2+8^2+9^2\\
187 &= 1^2+4^2+5^2+8^2+9^2\\
188 &= 1^2+2^2+3^2+5^2+7^2+10^2\\
189 &= 5^2+8^2+10^2\\
190 &= 2^2+4^2+5^2+8^2+9^2\\
191 &= 1^2+2^2+4^2+5^2+8^2+9^2\\
192 &= 1^2+5^2+6^2+7^2+9^2\\
193 &= 2^2+5^2+8^2+10^2\\
194 &= 7^2+8^2+9^2\\
195 &= 3^2+4^2+5^2+8^2+9^2\\
196 &= 1^2+3^2+4^2+5^2+8^2+9^2\\
197 &= 4^2+6^2+8^2+9^2\\
198 &= 2^2+7^2+8^2+9^2\\
199 &= 2^2+3^2+4^2+5^2+8^2+9^2\\
200 &= 1^2+2^2+3^2+4^2+5^2+8^2+9^2\\
201 &= 2^2+4^2+9^2+10^2\\
202 &= 1^2+2^2+4^2+9^2+10^2\\
203 &= 2^2+3^2+4^2+5^2+6^2+7^2+8^2 \\ 
204 &=1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2\\ 
205 &= 4^2+5^2+8^2+10^2\\
206 &= 1^2+4^2+5^2+8^2+10^2\\
207 &= 4^2+5^2+6^2+7^2+9^2\\
208 &= 1^2+4^2+5^2+6^2+9^2\\
209 &= 2^2+4^2+5^2+8^2+10^2\\
210 &= 2^2+5^2+9^2+10^2\\
211 &= 2^2+4^2+5^2+6^2+7^2+9^2\\
212 &= 1^2+2^2+4^2+5^2+6^2+7^2+9^2\\
213 &= 7^2+8^2+10^2\\
214 &= 2^2+4^2+7^2+8^2+9^2\\
215 &= 1^2+2^2+4^2+7^2+8^2+9^2\\
216 &= 3^2+4^2+5^2+6^2+7^2+9^2\\
217 &= 1^2+3^2+4^2+5^2+6^2+7^2+9^2\\
218 &= 1^2+6^2+9^2+10^2\\
219 &= 2^2+3^2+5^2+9^2+10^2\\
220 &= 2^2+3^2+4^2+5^2+6^2+7^2+9^2\\
221 &= 1^2+2^2+3^2+4^2+5^2+6^2+7^2+9^2\\
222 &= 4^2+5^2+9^2+10^2\\
223 &= 2^2+3^2+4^2+7^2+8^2+9^2\\
224 &= 1^2+2^2+3^2+4^2+7^2+8^2+9^2\\
225 &= 5^2+6^2+8^2+10^2\\
226 &= 4^2+5^2+6^2+7^2+10^2\\
227 &= 1^2+4^2+5^2+6^2+7^2+10^2\\
228 &= 3^2+5^2+7^2+8^2+9^2\\
229 &= 1^2+3^2+5^2+7^2+8^2+9^2\\
230 &= 2^2+4^2+5^2+6^2+7^2+10^2\\
231 &= 3^2+4^2+5^2+9^2+10^2\\
232 &= 2^2+3^2+5^2+7^2+8^2+9^2\\
233 &= 1^2+2^2+3^2+5^2+7^2+8^2+9^2\\
234 &= 3^2+5^2+6^2+8^2+10^2\\
235 &= 2^2+3^2+4^2+5^2+6^2+8^2+9^2\\
236 &= 1^2+2^2+3^2+4^2+5^2+6^2+8^2+9^2\\
237 &= 2^2+4^2+6^2+9^2+10^2\\
238 &= 5^2+7^2+8^2+10^2\\
239 &= 2^2+4^2+5^2+7^2+8^2+9^2\\
240 &= 1^2+2^2+4^2+5^2+7^2+8^2+9^2\\
241 &= 4^2+5^2+6^2+8^2+10^2\\
242 &= 5^2+6^2+9^2+10^2\\
243 &= 1^2+5^2+6^2+9^2+10^2\\
244 &= 3^2+4^2+5^2+7^2+8^2+9^2\\
245 &= 1^2+3^2+4^2+5^2+7^2+8^2+9^2\\
246 &= 2^2+5^2+6^2+9^2+10^2\\
247 &= 1^2+2^2+5^2+6^2+9^2+10^2\\
248 &= 2^2+3^2+4^2+5^2+7^2+8^2+9^2\\
249 &= 1^2+2^2+3^2+4^2+5^2+7^2+8^2+9^2
\end{split}\end{equation}
Q.E.D.

応用2 (Richert 1949) 7以上の任意の整数は相異なる素数の和として表すことができる。

証明. これもBertrandの定理によって補題を適用することができるが、証明は既に詳述したため省略する。
integers.hatenablog.com
Q.E.D.

応用3 (Dressler 1972) 10以上の任意の整数は相異なる奇素数の和として表すことができる。

証明. a_nn番目の奇素数とする。

a_1=3, a_2=5, a_3=7, a_4=11, a_5=13, a_6=17, a_7=19, \dots

l=10, r=6として補題を適用する。仮定1はBertrandの仮説よりわかる。仮定2は

\begin{align}
10 &= 3+7\\
11 &= 11\\
12 &= 5+7\\
13 &= 13\\
14 &= 3+11\\
15 &= 3+5+7\\
16 &= 5+11\\
17 &= 17\\
18 &= 7+11\\
19 &= 3+5+11\\
20 &= 7+13\\
21 &= 3+5+13\\
22 &= 5+17\\
23 &= 3+7+13\\
24 &= 11+13\\
25 &= 3+5+17\\
26 &= 3+5+7+11\\
27 &= 3+7+17\\
28 &= 3+5+7+13\\
\end{align}

よりわかる。 Q.E.D.

応用4 (Dressler 1973) 46以上の任意の整数は相異なる11以上の素数の和として表すことができる。

証明. a_n11から数えてn番目の素数とする:

\begin{align}&a_1=11, a_2=13, a_3=17, a_4=19, a_5=23, a_6=29, a_7=31, a_8=37, a_9=41, \\ &a_{10}=43, a_{11}=47\dots \end{align}

l=46, r=10として補題を適用する。仮定1はBertrandの仮説よりわかる。仮定2は

\begin{align}
46 &= 11+29\\
47 &= 11+17+19\\
48 &= 13+29\\
49 &= 13+17+19\\
50 &= 13+37\\
51 &= 11+17+23\\
52 &= 11+41\\
53 &= 13+17+23\\
54 &= 11+43\\
55 &= 13+19+23\\
56 &= 13+43\\
57 &= 11+17+29\\
58 &= 17+41\\
59 &= 11+17+31\\
60 &= 11+13+17+19\\
61 &= 13+17+31\\
62 &= 19+43\\
63 &= 13+19+31\\
64 &= 11+13+17+23\\
65 &= 11+17+37\\
66 &= 11+13+19+23\\
67 &= 13+17+37\\
68 &= 31+37\\
69 &= 11+17+41\\
70 &= 11+13+17+29\\
71 &= 11+17+43\\
72 &= 11+13+19+29\\
73 &= 13+17+43\\
74 &= 11+13+19+31\\
75 &= 13+19+43\\
76 &= 33+43\\
77 &= 11+23+43\\
78 &= 13+17+19+29\\
79 &= 13+23+43\\
80 &= 37+43\\
81 &= 17+23+41\\
82 &= 11+19+23+29\\
83 &= 11+13+17+19+23\\
84 &= 41+43\\
85 &= 11+31+43\\
86 &= 11+13+19+43\\
87 &= 13+31+43\\
88 &= 11+14+23+41\\
89&= 11+13+17+19+29\\
90 &= 11+13+23+43\\
91 &= 11+37+43\\
92 &= 13+19+29+31\\
\end{align}

よりわかる。 Q.E.D.

応用5 (Brown 1976) 58以上の任意の整数は相異なる13以上の素数の和として表すことができる。

Grothendieck素数として有名な57ですが、「相異なる13以上の素数の和として表すことのできない最大の整数」という特徴を持ちます。
integers.hatenablog.com

証明. a_n13から数えてn番目の素数とする:

\begin{align}&a_1=13, a_2=17, a_3=19, a_4=23, a_5=29, a_6=31, a_7=37, a_8=41, a_{9}=43, \\ &a_{10}=47, a_{11}=53, \dots \end{align}

l=58, r=10として補題を適用する。仮定1はBertrandの仮説よりわかる。仮定2は

\begin{align}
58 &= 17+41\\
59 &= 19+41\\
60 &= 17+43\\
61 &= 13+17+31\\
62 &= 19+43\\
63 &= 13+19+31\\
64 &= 23+41\\
65 &= 13+23+29\\
66 &= 19+47\\
67 &= 13+17+37\\
68 &= 31+37\\
69 &= 17+23+29\\
70 &= 29+41\\
71 &= 13+17+41\\
72 &= 31+41\\
73 &= 13+17+43\\
74 &= 31+43\\
75 &= 13+19+43\\
76 &= 29+47\\
77 &= 13+23+41\\
78 &= 37+41\\
79 &= 13+19+47\\
80 &= 37+43\\
81 &= 17+23+41\\
82 &= 13+17+23+29\\
83 &= 17+19+47\\
84 &= 41+43\\
85 &= 19+23+43\\
86 &= 13+19+23+31\\
87 &= 17+23+47\\
88 &= 41+47\\
89 &= 19+23+47\\
90 &= 43+47\\
91 &=13+31+47\\
92 &= 13+19+29+31\\
93 &= 17+29+47\\
94 &= 13+17+23+41\\
95 &=  19+29+47\\
96 &= 13+17+29+37\\
97 &= 19+31+47\\
98 &= 13+19+29+37\\
99 &= 23+29+47\\
100 &= 13+19+31+37\\
101 &= 13+41+47\\
102 &= 13+19+29+41\\
103 &= 13+43+47\\
104 &= 13+19+29+43\\
105 &= 17+41+47\\
106 &= 13+19+31+43\\
107 &=  19+41+47\\
108 &= 13+19+29+47\\
109 &= 19+43+47\\
110 &= 13+19+31+47\\
\end{align}

よりわかる。 Q.E.D.

補題の証明

直接証明することもできますが、Brownによるより適用範囲の広い命題を示します。

命題 (Brown 1976) 自然数列\{a_n\}_{n=1}^{\infty}が次の二条件を満たすと仮定する:

  1. 非負整数rが存在して、n \geq rに対してa_{n+1}\leq a_{r+1}+\sum_{i=r+1}^na_iが成り立つ。
  2. 非負整数lが存在して、l\leq N < l+a_{r+1}なる任意の整数NN=\sum_{n=1}^r\epsilon_na_n \ (\epsilon_n \in \{0, 1\})と書ける。

この時、任意のn \geq rに対して、次が成り立つ:
l \leq N < l+a_{r+1}+\sum_{i=r+1}^na_iなる任意の整数NN=\sum_{i=1}^n\epsilon_ia_i \ (\epsilon_i \in \{0, 1\})と書ける。ここで、記号\sum_{i=1}^kk=0ならば和は0であると約束する。
特に、l以上の任意の整数は数列\{a_n\}_{n=1}^{\infty}の有限個の相異なる項の和として表される(ただし、l=0の時は0個の和=0のも含める)。

証明. n=rのときは仮定2より成立する。nに関する数学的帰納法で証明する。nのときは正しいと仮定しよう。このとき、

\displaystyle l+a_{r+1}+\sum_{i=r+1}^na_i \leq N < l+a_{r+1}+\sum_{i=r+1}^{n+1}a_i

を満たす任意のNN=\sum_{i=1}^{n+1}\epsilon_ia_iと書けることを示せばよい。仮定1より

\displaystyle l \leq l+a_{r+1}+\sum_{i=r+1}^na_i-a_{n+1} \leq N -a_{n+1} < l+a_{r+1}+\sum_{i=r+1}^na_i

なので、帰納法の仮定より

\displaystyle N-a_{n+1} = \sum_{i=1}^n\epsilon_ia_i

と書ける。これで証明は完了する。 Q.E.D.

補題の仮定1より命題の仮定1が満たされることを証明する。 n=rのときは自明に成り立つ。nに関する数学的帰納法で証明する。nのときは正しいと仮定しよう。このとき、

\displaystyle a_{n+2} \leq 2a_{n+1} \leq a_{n+1}+a_{r+1}+\sum_{i=r+1}^na_i = a_{r+1}+\sum_{i=r+1}^{n+1}a_i

n+1のときも仮定1が満たされることが示された。 補題の証明終わり.

命題は数列の半完全性に関する十分条件を与えています。同じBrownさんによる結果
integers.hatenablog.com
と比較してみてください。

次はGrahamの定理の証明に用いるために、一般の冪乗数の場合に一般化します。