537個の数、6つの色、和はなし

子どもにもわかるパズルがある。1、2、3……と数を並べる。それぞれに色を1つずつ塗る。ルールは一つだけ。同じ色の中に、2つの数とその和が一緒に見つかってはならない。2つの数は同じでもよい。だから2を赤にしたら、4は赤にできない。2 + 2 = 4だからだ。

そのような3つ組を含まない集合は和のない集合（sum-free）と呼ばれる。このルールのせいで止まらざるをえなくなるまで、どこまで進めるだろうか。k色の場合のその限界が**シューア数S(k)**である。この問題は、参考文献リストの最初に挙げられたI. Schurの1916年の論文にさかのぼる。

頑固なことで知られる数列

1色では、すぐに行き詰まる。1 + 1 = 2なので、その色には数1しか入れられない。知られている値は次のとおりだ。

• S(1) = 1
• S(2) = 4
• S(3) = 13
• S(4) = 44
• S(5) = 160。M. J. H. Heuleが決定した（2018年に発表された論文）。

6色については、誰も答えを知らない。2000年以来、H. FredricksenとM. M. Sweetが対称な色分けを探索して見つけた最良の構成が536に達していた。この数は、それ以来ずっと最良の下界として引用されてきた。下界とはいわば「床」である。S(6)は少なくともこの大きさであり、いまだわかっていない本当の値はもっと大きいかもしれない。

もう1つの数

トロント大学のZhiyang ChenとFan Long、そしてNVIDIA ResearchのLigeng Zhuが、いまそれを537に押し上げた。彼らの証明は、そのぶっきらぼうさゆえに数学者に愛されるたぐいのものだ。答えを印刷しているのである。数のリストが6つ――それぞれ76、76、88、70、76、151個の数を含む――あり、合わせると1から537までのすべての整数をちょうど1回ずつ含み、どの色にもx、y、x + yが同時に入っていない。確かめるには、各リストの中のあらゆる和を調べればよい。コンピューターならすぐに終わる作業だ。

この解は印象的な形をしている。対称なのだ。どの数xも、538 − xと同じ色である。最初の4色は1、2、3、4から始まる。5番目の色は38からしか現れず、6番目の色は151からしか現れない。そして6番目の色は、237から301までの真ん中の区間全体を埋め尽くす。最初の色でさえ、わずか14個の小さな数からなる種から、鏡像による折り返し、ずらし、そして数を一つ加えることで組み立て直せる。

さらに上へ広がる波紋

シューア数は互いにつながっている。知られている手順を使えば、k色のよい色分けを、k + 2色やk + 5色の色分けに変えられる。S(k + 2)は少なくとも10 S(k) + 2であり、S(k + 5)は少なくとも380 S(k) + 148である。そのため、新しい537はほかの記録も押し上げる。

• 8色：5,362から5,372へ――チームはその色分けも具体的に構成した。
• 11色：203,828から204,208へ。
• 13色：2,038,282から2,042,082へ。

さらに、ラムゼー数R₆(3)も改善される。これは、点をすべて2つずつ線で結んだとき、その線を6色でどう塗っても必ず同じ色の三角形ができてしまうような、最小の点の数である。538個の点に0から537までの番号をつけ、点iと点jを結ぶ線に、その差|i − j|の色を塗る。すると和のない色分けからは、同じ色の三角形が一つもできない。したがってR₆(3)は少なくとも539であり、これまでの538から上がる。

131通りのやり方

探索で見つかったのは1つの解ではなく、本質的に異なる131の解だった。著者たちはそれらを5つのファミリーに分類し、すべてを公開している。大半は最初の解にとても近い。ファミリーF1からF4に属する解は、537の位置のうち少なくとも462で最初の解と一致する。あるファミリーは鏡映の対称性を破り、別のファミリーは元の解をかき混ぜた3つのコピーを混ぜ合わせて作られている。

論文は、探索そのものをどのように実行したかを説明していない。著者たちは、131の色分けは6色の解の完全な一覧ではなく、538に挑みたい人のための新たな出発点にすぎないと強調している。