打ち消し合う和をめぐる1969年の予想、誤りと判明
6時間しかない時計と、動きのリストを考えよう。「針を1時間進める」「4時間進める」といった具合だ。1時間ずつの動きが5つなら、どれをどう組み合わせても、針がちょうど出発点に戻ることはない。動きが6つあれば、それがどんなものであっても、ある組がいつも針を戻す。数学者はこの時計の算術をC₆と書き、ここでの数6が、この時計のDavenport定数である。
次に、こうした時計をr個並べ、1回の動きでそれぞれの針をそれぞれの量だけ回すことにする。この時計の組のDavenport定数はD(C₆^r)と書かれ、合計がすべての針を同時に出発点に戻すような組の存在を保証する、最小の動きの数である。論文の言葉でいえば、零和部分列(zero-sum subsequence)だ。この定数は、グラフ理論、有限幾何学、組合せ論、そして分解理論(factorization theory)の問題と結びついている。
1969年の公式
簡単な下界がある。各時計について、その時計だけに触れる1時間の動きを5つとる。時計がr個なら、どの組も打ち消し合わない5r個の動きができる。したがって、少なくとも5r + 1個の動きが必要だ。一般に、n時間の時計なら、少なくともr(n − 1) + 1個である。
1969年、van Emde BoasとKruyswijkは、この簡単な下界がいつも正確な答えだと予想した。
D(C_n^r) = r(n − 1) + 1.
この式は1960年代に、時間の数が素数のべき乗である時計や、時計が2個以下の場合など、いくつかのケースで証明された。それ以外では、正確な値には手が届かなかった。2018年になっても、6時間時計が4個の場合さえわかっていなかった。それでも、この予想はこの分野の「長年にわたる著名な問題」となり、成り立つと期待されていた。
決して打ち消し合わない116個の動き
Weidong Gao(天津大学)、Alfred Geroldinger(グラーツ大学)、Guoqing Wang(天津工業大学、Tiangong University)、Xiangneng Zeng(中山大学)は、今回、この予想が成り立たないことを示した。
チームは、積み木を組むように動きを組み立てる。
- 6時間時計5個の上の24個の動きのリスト。小さな表からつくられ、そのうち合計が3つの位置からなる小さな集合に入る組は、いつも同じ0でない位置に行き着く。
- その3つの位置を共有するそうしたリスト2つ。これで、打ち消し合う組をもたない48個の動きが得られる。
- 同じく打ち消し合う組をもたない、別の20個の動きのリスト。
これらを並べると、23個の6時間時計の上の2 × 48 + 20 = 116個の動きが得られ、そのどの組もすべての針を出発点に戻さない。予想によれば、そうしたリストは最長でも23 × 5 = 115個のはずだった。したがって、時計が23個の場合のDavenport定数は116ではなく、少なくとも117である。
このブロックのコピーは積み重ねることができる。一般的な結果は D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1 で、⌊r/23⌋ は23個からなる完全なブロックがrの中にいくつ収まるかを数える。したがって、6時間時計では、rが23に達したとたんに予想は誤りとなり、それより大きいすべてのrでも誤りである。著者らは、同じ定理が被覆(coverings)に関するある予想された結果も否定することを指摘している。
残された問題
証明はD(C₆^r)の本当の値を与えるわけではなく、予想が禁じていた下界を与えるだけだ。時計が23個未満の場合については何も新しいことをいわない。そこでは新しい下界が古い公式と一致するからだ。6時間以外の時計についても同様である。ノートは5ページで、査読はまだこれからだ。
