KONJEKTUR BUNGA MATAHARI AKHIRNYA TERBUKTI
Ambil bilangan 1 sampai n dan perhatikan semua cara memilih sebagian di antaranya: ada 2ⁿ subhimpunan semacam itu. Sekarang pilih beberapa subhimpunan yang berbagi bagian bersama yang persis sama, dan tidak ada yang lain. Matematikawan menyebutnya bunga matahari (sunflower): bagian bersama itu adalah inti, dan sisa dari setiap himpunan adalah kelopak yang tidak menyentuh kelopak lain.
Bunga matahari adalah alat dasar dalam kombinatorika. Makalah ini menyebut kaitannya dengan batas kemampuan rangkaian logika tertentu, dengan masalah “cap set”, dengan perkalian matriks cepat, dan dengan teori informasi.
Pertanyaan dari tahun 1970
Pertanyaan paling alami tentangnya, menurut para penulis, berasal dari makalah Paul Erdős tahun 1970. Seberapa besar suatu koleksi subhimpunan dari {1, …, n} bisa dibuat jika tidak ada k himpunan di dalamnya yang membentuk bunga matahari?
Pada 1970-an, Erdős dan Endre Szemerédi menduga bahwa koleksi semacam itu pasti jauh lebih kecil secara eksponensial daripada 2ⁿ subhimpunan yang mungkin: paling banyak cⁿ, untuk suatu bilangan c yang benar-benar di bawah 2.
Selama puluhan tahun, batas terbaik hanya memangkas sedikit, tidak pernah cukup untuk menurunkan basisnya di bawah 2. Hanya kasus tiga kelopak (k = 3) yang terjawab, pada 2016, berkat terobosan pada masalah cap set dan sebuah reduksi dari Alon, Shpilka, dan Umans.
Batasnya
Matija Bucić dan Fankang He (Universitas Wina) serta Hyunwoo Lee (KAIST dan Institute for Basic Science, Korea Selatan) membuktikan konjektur ini untuk setiap k ≥ 3. Teorema utama mereka: koleksi tanpa bunga matahari ber-k kelopak memiliki paling banyak
3 · (2 − 1/(16k³))ⁿ
anggota. Basisnya sedikit di bawah 2, tetapi merupakan bilangan tetap di bawah 2, dan itulah tepatnya yang diminta Erdős dan Szemerédi. Sebuah konstruksi dari 1997 menunjukkan bahwa, untuk k besar, nilai sebenarnya tidak mungkin jauh lebih rendah.
Dari himpunan ke vektor
Buktinya melewati versi masalah ini dengan vektor. Bagi bilangan-bilangan itu menjadi n blok berisi D elemen dan pilih satu elemen per blok: setiap pilihan adalah sebuah vektor. Beberapa vektor membentuk bunga matahari jika, di setiap posisi, entri-entrinya semuanya sama atau semuanya berbeda.
Para penulis lalu membangun “penguji bunga matahari”: sebuah fungsi yang, pada koleksi bebas bunga matahari, bernilai tidak nol hanya jika semua masukannya adalah vektor yang sama. Bahan barunya adalah menuliskan fungsi ini, langkah demi langkah, dengan polinomial interpolasi berderajat rendah. Menghitung polinomial-polinomial itu membatasi ukuran koleksi (Teorema 2 mereka). Sebuah argumen probabilistik, dengan blok acak yang dirata-ratakan atas semua ukuran himpunan, membawa batas itu kembali ke himpunan biasa.
Ditemukan oleh satu mesin, diperiksa oleh mesin lain
Pernyataan makalah ini tentang AI luar biasa lugas. Bukti Teorema 2 ditemukan oleh ChatGPT 6 Astra Pro, setelah diskusi singkat yang dimulai dengan memintanya menggeneralisasi argumen tiga kelopak yang sudah dikenal. Para penulis membutuhkan langkah itu untuk tujuan lain: versi terinduksi dari sebuah masalah graf yang diajukan Szemerédi, yang mereka umumkan untuk catatan berikutnya.
Model itu menulis buktinya dalam bahasa “slice rank”. Para penulis menulis ulang dalam bahasa metode polinomial, yang menurut mereka lebih mudah bagi pembaca. Mereka menyatakan telah memverifikasi setiap hasil dan bertanggung jawab penuh, serta bahwa buktinya telah diverifikasi di Lean 4.35, sebuah perangkat lunak pemeriksa bukti, dengan hasil verifikasi yang akan diunggah ke repositori Palomar.
Yang belum terjawab
Para penulis tidak berusaha mengoptimalkan basisnya. Untuk tiga kelopak, basis itu tidak mengalahkan batas Naslund dan Sawin tahun 2017, sekitar 1,89. Dan masalah saudaranya yang lebih kuat, konjektur bunga matahari Erdős–Rado, masih terbuka: batas mereka masih sangat bergantung pada ukuran blok D, padahal justru itulah yang dilarang oleh masalah tersebut.