Youtube の Numberphile チャンネルで最近出た Schur Number の動画を見た、 そこでのシューア数の定義は OEIS の "version 1" の方
Smallest number such that for any n-coloring of the integers 1, ..., a(n) no color is sum-free, that is, some color contains a triple x + y = z.
だったが、"version 2" の
Largest number such that there is an n-coloring of the integers 1, ..., a(n) such that each color is sum-free, that is, no color contains a triple x + y = z.
の方が解り易いからこちらで話を進める。version 2 の方が 1 小さい値になるというだけの違いがある。
動画の内容は \(a(n) = 160\) になる証明が2ペタバイトのデータ量で凄い、みたいなこと。 結局、全ての n-coloring を確認するしかないとか何とか。
ここではそういう難しい部分の話はせずに、1, 4, 13, 44, 160 という増え方が大体 3 倍を超えるぐらいというのを納得する議論をしてみたい。 よりはっきり言うと、1, 4, 13 と増える \(a_{n+1} = 3a_n + 1\) という数列が下限になることを示す。 一つ注意を述べると、n-coloring を考えるというより \(\{1,\ldots,k\}\) の和抜き（sum-free）集合による被覆を考えれば良い。被覆ができれば彩色を作れる（自由度を失うだけ）ので。
そういうわけで \(\{1\}\) の被覆を考え始めるわけだが、そちらも \(\{1\}\) で良い。 次に \(\{1, 2\}\) の被覆を考えるが \(1+1=2\) なので \(\{1,2\}\) は和抜きではない。よって \(\{1, 2\}\) の和抜き集合による被覆は \(\{1\},\{2\}\) の2要素が必要になる。 次に \(\{1, 2, 3\}\) は、たとえば \(\{1, 3\}\) と \(\{2, 3\}\) の2要素で覆える。 3の重複を無くすと2種類の2彩色が与えられる。 \(\{1, 2, 3, 4\}\) は、\(\{1, 4\}\) と \(\{2, 3\}\) の2要素で覆える。 \(1+3=4\) なので前者に 3 を増やすことはできない。\(2+2=4\) なので後者に 4 を増やすこともできない。 ということで、次に 5 を増やせるかを考えるが、\(1+4=2+3=5\) なのでどちらにも 5 を入れることはできない。 つまり \(a(2)=4\) が確定する。
\(a_1=1\), \(a_2 = 4 = 3a_1 + 1\) と進む様子をもう少し見直してみる。 \(A_{1,1}=\{1\}\) とする。\(b_2=a_2 + 1=5\) とおいて、\(A'_{1,1} = (b_2 - A_{1,1}) = \{5 - 1\} = \{4\}\) とする。 これを使って \(A_{2,1}=A_{1,1} \cup A'_{1,1} = \{1\}\cup\{4\}\) と定める。 \(A_{2,2}=\{1,\ldots,4\} \setminus A_{2,1} = \{2,3\}\) とおくと、\(\{1,\ldots,4\}\) が \(A_{2,1}\) と \(A_{2,2}\) で被覆される。
次に \(a_3 = 3a_2 + 1 = 13\) さらに \(b_3 = a_3 + 1 = 14\) とおく。 \(A'_{2,1} = (b_3 - A_{2,1}) = \{14 - 1, 14 - 4\} = \{10, 13\}\) とする。 同様に、\(A'_{2,2} = b_3 - A_{2,2} = \{14 - 2, 14 - 3\} = \{11, 12\}\) とする。 これらを使って \(A_{3,1} = A_{2,1}\cup A'_{2,1} = \{1, 4, 10, 13\}\) および \(A_{3,2} = A_{2,2} \cup A'_{2,2} = \{2, 3, 11, 12\}\) を決める。 最後に \(A_{3,3} = \{1,\ldots,13\} \setminus \bigcup_{i=1}^{2} A_{3,i}\) とすると、 \(\{1,\ldots,13\}\) の被覆 \(A_{3,1}, A_{3,2}, A_{3,3}\) が得られる。
以下同様に \(a_k = 3 a_{k-1} + 1\) のとき、\(b_k = a_k + 1\) とおいて、 \(i=1,\ldots,k-1\) に対し \(A'_{k-1,i} = b_k - A_{k-1,i}\) を使って \(A_{k,i}=A_{k-1,i}\cup A'_{k-1,i}\) を決める。 最後に \(A_{k,k} = \{1,\ldots,a_k\} \setminus \bigcup_{i=1}^{k-1} A_{k,i}\) と決めると、 \(\{1,\ldots,a_k\}\) の被覆 \(A_{k,1},\ldots,A_{k,k}\) が得られる。
\(A_{k,i}\) が和抜き集合であるのは作り方からほぼ自明だと思うが、\(A_{k,k}\) だけ少し見ておく。 結局 \(a_{k-1}\) 以下と \(a_k - a_{k-1} + 1\) 以上を取り除いた部分だから \(A_{k,k} = \{a_{k-1} + 1,\ldots,2a_{k-1} + 1\}\) であり、最小の元 \(a_{k-1}+1\) を2つ足すと最大元 \(2a_{k-1} + 1\) を越えてしまうので和抜き集合である。
ということで、このパターンを続けて行くと \(n\) 個の和抜き集合で \(\{1,\ldots,a_n\}\) が被覆できる。 \(a_n\) は \(a_{n+1} = 3a_n + 1\) という漸化式を満たす。つまり、元の問題に戻すと、\(a_n\) がシューア数の下限であり、3倍ぐらいずつ伸びていくことが見て取れる。 逆に言うと、3倍を越えて伸びる部分が正確な値を求める上で工夫の必要な部分となるわけである。