何十年もの間、素朴な疑問がつきまとっていた マテ・マトルシ、ブダペスト工科経済大学教授。 XNUMX つの色付き点が正確に XNUMX 単位の距離離れていないことを確認しながら、無限の平面をどの程度色付けできるでしょうか?

この疑問は、1960 年代初頭にカナダの数学者レオ モーザーによって初めて提起されました。 1967 年、ケンブリッジ大学のハラード クロフトは、かなりうまく機能すると思われる構造を考案しました。 現在「クロフトの亀」と呼ばれている彼の形は、円と六角形のクッキー型が合わさったように見えます。 各カメ内のすべての点は、同じカメ内の他の点から XNUMX 単位未満離れており、隣接するカメの最も近い点からは XNUMX 単位以上離れています。

それ以来半世紀が経ち、亀が覆う平面の 22.936% を改善する形状を誰も見つけることができませんでした。 しかし、理論上でも存在する可能性はあるでしょうか? 1984 年、ハンガリーの数学者ラースロー セーケリーは、平面の 27.91% 以上を覆う形状を見つけることは不可能であることを証明しました。 翌年、多作の予想家であるパウル・エルデシュ氏（同じハンガリー人）は、上限は25％未満だと考えていると述べた。 多くの場合と同様に エルデシュの予想、長年にわたって多くの野心的な数学者の注目を集めました。

マトルシ氏は 2000 年代初頭の博士論文でこの問題に焦点を当てました。 彼はフーリエ解析 (三角法から取得した正弦関数を加算してより複雑な関数を表す) に取り組んでおり、これらの手法をエルデシュの予想の証明に使用できると考えました。

「私にはそれができませんでした」と彼は言いました。 「25%に非常に近づきましたが、それを下回ることはありませんでした。 私は少しがっかりしました。 私たちはそれに多くの努力を注ぎました。 私はハンガリー科学アカデミーで博士号の弁護人を務めていましたが、委員会でこう言いました。「ほら、これが真実かどうかさえもうわかりません。 私たちはこれに多大な努力を払ってきましたが、このひどい数字は 25 を下回ることはありません。」

彼が自分が間違っていたと証明するにはほぼ四半世紀かかるだろう。

他の数学者もこの数字を少しずつ計算し続けました。 2010 年までに、現在ケルン大学に在籍しているフランク・ヴァレンティンと現在デルフト工科大学に在籍しているフェルナンド・オリベイラは、その上限を 27% 未満に押し上げました。 マトルシもそれを続け、2014 年に同僚とともに、 彼は26%合格した。 2018年までに、彼はGergely Ambrusとともに、 限界を 25.442% まで下げました — エルデシュ氏の 25% の推測に興味をそそられるほど近い。

それから彼は諦めた。

2018年の論文の後、マトルシ氏はこう回想した。「私は『この問題には二度と触れない』と言いました。 それはうまくいかないからです。 できることはやりました。」

彼はそうしなかったことが判明した。 マトルシ氏は、誕生日パーティーで数人の研究者が彼にアプローチした後、最後にもう一度問題を解決してみることに同意した。 ハンガリー科学アカデミーのダニエル・ヴァルガ氏、アドリアン・シザーリク氏、パル・ザンボキ氏は、AlphaGo や AlphaFold のような機械学習モデルが、問題の解決に必要な複雑な一連の点を特定するのに役立つのではないかと考えました。

1984 年の結果以来、有益であることが証明されている手法の XNUMX つは、自己相関関数と呼ばれるものを使用して、候補の点セットがそれ自体のシフトされたコピーと持つ重複の量を調べることでした。 特定のシフト (たとえば、上に XNUMX 単位、右に XNUMX 単位) に対して、関数はオーバーラップのサイズの尺度となる数値を与えます。 セットが「単位距離回避」である場合、そのセットがどの方向にでも XNUMX 単位だけシフトされると、その自己相関関数はゼロになります。

Matolcsi、Ambrus、および彼らの新しい共同研究者らは、関数をフーリエ変換して、正弦波の巨大な合計に変換することに注目しました。 すべての単位長シフトに対して関数がゼロであるという要件により、フーリエ和の要素の取り得る値が制限されます。 彼らは、その要件を線形最適化問題として表現する方法を考え出しました。Varga、Csiszárik、Zsámboki には、それを処理する能力が十分に備わっていました。

「非常に繊細で、非常にまれなプロパティのセットを持つ点のセットを見つけなければなりませんが、その方法がわかりません。 そこで私たちはコンピューターにこれらのオブジェクトを検索するよう依頼します」とヴァルガ氏は語った。

このプロセスは彼らが予想していたよりも簡単でした。 ヴァルガ氏とシザーリク氏は、ポイントを特定するためにより複雑な人工知能モデルを実験し、予想以上に苦労しましたが、ザンボキ氏は 1980 年代に開発された古い検索戦略を使用しました。

「高度な機能がそれほどうまく機能しないのは非常に奇妙でした。 私は古い方法を使用することにしました」とザンボキ氏は言いました。「それがたまたまうまくいっただけです。」 (Zsámboki 氏は、Varga 氏がツリー検索と呼ばれる特定の手法を使用することを提案したと付け加えました。)

使用するアルゴリズムを決定すると、25,552 個の変数と 6,099 個の制約という大きな問題を解決する必要がありました。 彼らは 128 個の CPU で XNUMX 週間にわたって検索を実行しました。 週末に結果が出た。

2022 年 XNUMX 月に、チームは 論文を投稿しました これは、単位距離のペアを使用しないと平面の 24.7% しか色を付けることができないことを示し、最終的にエルデシュの限界を破りました。

「本当に、とても満足のいく瞬間だったと言わざるを得ません」とマトルシは語った。 「とてもきちんとした素晴らしい結果だ。」

「現在のコンピューター能力では 25% を下回るのは不可能だとすでに思っていたので、彼らがこれを実現してくれてとてもうれしいです」と Vallentin 氏は言いました。

それでも、飛行機の 1967% 弱を占めるクロフトの 23 年のカメよりも完全なカラーリングを思いついた人は誰もいません。 しかし、著者の何人かは、カメに向けて上限を下げ続けるのではなく、現在、関連する問題に焦点を当てています。それは、すべての色が単位距離であることを確認しながら、平面を完全にカバーするために必要な色数を計算することです。避けること。

この数を平面の彩色数と呼びます。 2018年、アマチュア数学者（そして長寿の伝道者）オーブリー・デ・グレイが 証明 新しい論文は、de Grey とは異なる方法を使用して、少なくとも 5 色が必要であることを示唆しています。 「少なくとも 7 であることを証明できますか?」 アンブルスは尋ねた。 「それは可能性があるかもしれないことだ。 私たちは現在それに取り組んでおり、私たちの方法で可能性があるかもしれません。」