BERAPA WARNA UNTUK MEWARNAI RUANG? UNTUK PENGGARIS TIPIKAL, TIDAK LEBIH DARI 2d

Ambil setiap titik pada sebuah bidang datar dan beri masing-masing satu warna. Satu aturan: dua titik yang berjarak tepat satu satuan tidak boleh memiliki warna yang sama. Berapa jumlah warna paling sedikit yang memenuhi?

Inilah masalah Hadwiger–Nelson, yang berasal dari tahun 1950 dan, menurut para penulis, merupakan salah satu masalah terbuka paling terkenal dalam geometri diskret. Lama sekali jawabannya hanya diketahui berada di antara 4 dan 7. Sebuah terobosan baru-baru ini menaikkan batas bawahnya menjadi 5. Jawaban pastinya masih belum diketahui.

Mengganti penggaris

Jarak tidak harus diukur dengan penggaris biasa. Matematikawan mendefinisikan banyak norma lain — cara mengukur panjang — yang masing-masing dijelaskan oleh “bola satuan”-nya, yaitu himpunan titik yang berjarak paling jauh 1 dari pusat. Untuk jarak biasa, bentuknya bola bundar; untuk norma lain, bentuknya bisa berupa bangun cembung apa pun yang simetris terhadap pusatnya.

Untuk setiap norma pada bidang datar, jawaban teka-teki pewarnaan ini berada di antara 4 dan 7. Dalam d dimensi, jawabannya paling banyak eksponensial terhadap d untuk norma apa pun, dan untuk banyak norma alami — termasuk norma Euklides yang biasa — juga paling sedikit eksponensial: jumlah warna meledak seiring bertambahnya dimensi.

Apakah ledakan itu aturannya? Noga Alon (Universitas Princeton dan Universitas Tel Aviv), Matija Bucić (Universitas Wina), dan James Davies (Universitas Leipzig) meneliti norma yang tipikal. Tidak ada cara alami untuk memilih norma “secara acak”, sehingga mereka menggunakan pengertian topologis: suatu sifat berlaku untuk norma tipikal jika pengecualiannya membentuk himpunan yang dapat diabaikan (“meagre”). Karya sebelumnya oleh Alon, Bucić, dan Lisa Sauermann telah menunjukkan bahwa norma tipikal membutuhkan paling banyak 2ᵈ warna, dan mempertanyakan seberapa dekat angka itu dengan kenyataan.

Linear, bukan eksponensial

Jawabannya: masih jauh. Makalah baru ini membuktikan bahwa

• untuk norma tipikal pada ruang berdimensi d, 2d warna selalu cukup;
• ini adalah yang terbaik: sebuah himpunan terbuka dari norma-norma membutuhkan paling sedikit 2d warna. Jadi beberapa norma membutuhkan tepat 2d.

Dalam sepuluh dimensi, norma tipikal membutuhkan paling banyak dua puluh warna, sementara jarak biasa membutuhkan jumlah yang tumbuh secara eksponensial. Menurut para penulis, ini juga pertama kalinya bilangan pewarnaan ditentukan secara pasti untuk norma yang “konveks sempurna” (strictly convex) di dimensi d berapa pun.

Batas bawahnya memakai jebakan yang cerdik. Temukan 2d titik yang semuanya saling berjarak tepat satu satuan, kecuali dua titik, a dan b, yang berjarak setengah satuan. Tambahkan bayangan cermin seluruh konfigurasi itu terhadap a. Dengan kurang dari 2d warna, baik b maupun bayangan cerminnya akan dipaksa mengambil warna a — padahal keduanya berjarak tepat satu satuan. Kontradiksi. Sebuah lema stabilitas menunjukkan bahwa konfigurasi ini tetap bertahan terhadap perubahan kecil apa pun pada norma.

Pelari kesepian di dimensi tinggi

Batas atasnya mewarnai setiap titik menurut letak jatuhnya proyeksi titik itu yang dipilih dengan cermat, dalam irisan selebar 1/(2d). Agar berhasil, dibutuhkan bahan kunci yang oleh para penulis digambarkan sebagai versi matriks berdimensi tinggi dari konjektur pelari kesepian (lonely runner conjecture) yang terkenal:

sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

dengan ‖t‖ adalah jarak dari t ke bilangan bulat terdekat, untuk sembarang n vektor aᵢ dalam k dimensi yang setiap k di antaranya saling bebas. Pernyataan ini juga menuntaskan konjektur I. J. Schoenberg dari 1978 tentang “penghalangan pandangan” (view obstruction) — pertanyaan tentang seberapa tebal lempengan periodik harus dibuat agar menghalangi setiap pandangan ke tak hingga — yang oleh para penulis disebut salah satu masalah terbuka paling klasik di bidang ini, serta sebuah konjektur terkait dari Henze dan Malikiosis.

Mesin di bagian ucapan terima kasih

Para penulis berterus terang: “ChatGPT 6 Pro memberi kami bukti untuk bahan terakhir yang kami perlukan dalam pembuktian Teorema 1, yaitu bukti Lema 7, setelah diskusi panjang”, di mana mereka telah membagikan pengamatan mereka sendiri — termasuk gagasan induksi dan strategi umumnya. “Argumen batas bawah juga ditemukan dengan bantuan ChatGPT 6 Pro.”

Masih ada pertanyaan tersisa. Nilai pasti 2d dibuktikan pada sebuah himpunan terbuka dari norma-norma, bukan untuk semua norma tipikal. Dan untuk jarak Euklides biasa, para penulis memperkirakan dibutuhkan lebih dari 2d warna di setiap dimensi — sesuatu yang sudah diketahui pada dimensi 2, 4, 7, 8, dan 9 ke atas, tetapi masih terbuka pada dimensi 3, 5, dan 6.