Trik Matematika Menjinakkan Jarak Tengah | Majalah Quanta

Sejauh tahun ini, Quanta telah mencatat tiga kemajuan besar dalam teori Ramsey, studi tentang bagaimana menghindari pembuatan pola matematika. Itu hasil pertama beri batasan baru pada seberapa besar sekumpulan bilangan bulat tanpa mengandung tiga angka yang berjarak sama, seperti {2, 4, 6} atau {21, 31, 41}. Itu kedua dan ketiga sama halnya menempatkan batas baru pada ukuran jaringan tanpa kelompok titik yang semuanya terhubung, atau semuanya terisolasi satu sama lain.

Bukti-bukti membahas apa yang terjadi ketika jumlah yang terlibat tumbuh sangat besar. Paradoksnya, ini terkadang lebih mudah daripada berurusan dengan kuantitas dunia nyata yang mengganggu.

Misalnya, pertimbangkan dua pertanyaan tentang pecahan dengan penyebut yang sangat besar. Anda mungkin bertanya apa itu perluasan desimal, katakanlah, 1/42503312127361. Atau Anda bisa bertanya apakah angka ini akan semakin mendekati nol saat penyebutnya bertambah. Pertanyaan pertama adalah pertanyaan khusus tentang kuantitas dunia nyata, dan lebih sulit untuk dihitung daripada yang kedua, yang menanyakan bagaimana kuantitas 1/n akan "asimptotik" berubah sebagai n tumbuh. (Semakin dekat dan semakin dekat ke 0.)

“Ini adalah masalah yang mengganggu semua teori Ramsey,” kata William Gasarch, seorang ilmuwan komputer di University of Maryland. "Teori Ramsey dikenal memiliki hasil yang sangat bagus tanpa gejala." Tetapi menganalisis angka yang lebih kecil dari tak terhingga membutuhkan kotak alat matematika yang sama sekali berbeda.

Gasarch telah mempelajari pertanyaan dalam teori Ramsey yang melibatkan bilangan hingga yang terlalu besar untuk diselesaikan dengan kekerasan. Dalam satu proyek, dia mengambil versi terbatas dari terobosan pertama tahun ini — sebuah makalah bulan Februari oleh Zander Kelly, seorang mahasiswa pascasarjana di University of Illinois, Urbana-Champaign, dan Raghu Meka dari Universitas California, Los Angeles. Kelley dan Meka menemukan batas atas baru pada berapa banyak bilangan bulat antara 1 dan N Anda dapat memasukkan ke dalam satu set sambil menghindari progresi tiga suku, atau pola angka dengan jarak yang sama.

Padahal hasil Kelley dan Meka berlaku sekalipun N relatif kecil, itu tidak memberikan ikatan yang sangat berguna dalam kasus itu. Untuk nilai yang sangat kecil dari N, lebih baik Anda tetap menggunakan metode yang sangat sederhana. Jika N adalah, katakanlah, 5, lihat saja semua kumpulan angka yang mungkin antara 1 dan N, dan pilih yang bebas perkembangan terbesar: {1, 2, 4, 5}.

Tetapi jumlah kemungkinan jawaban yang berbeda tumbuh dengan sangat cepat dan membuatnya terlalu sulit untuk menggunakan strategi sederhana seperti itu. Ada lebih dari 1 juta set yang terdiri dari angka antara 1 sampai 20. Ada lebih dari 10⁶⁰ menggunakan angka antara 1 dan 200. Menemukan set bebas perkembangan terbaik untuk kasus ini membutuhkan daya komputasi yang besar, bahkan dengan strategi peningkatan efisiensi. “Anda harus bisa memeras banyak hal dari berbagai hal,” kata James Glen, seorang ilmuwan komputer di Universitas Yale. Pada tahun 2008, Gasarch, Glenn dan Clyde Kruskal dari Universitas Maryland menulis sebuah program untuk menemukan set bebas perkembangan terbesar hingga N dari 187. (Pekerjaan sebelumnya mendapatkan jawaban hingga 150, juga untuk 157.) Meskipun ada daftar trik, program mereka membutuhkan waktu berbulan-bulan untuk diselesaikan, kata Glenn.

Untuk mengurangi beban komputasi mereka, tim menggunakan tes sederhana yang mencegah program mereka mengejar pencarian buntu dan membagi set mereka menjadi bagian-bagian yang lebih kecil yang mereka analisis secara terpisah.

Gasarch, Glenn dan Kruskal juga mencoba beberapa strategi lainnya. Satu ide yang menjanjikan bersandar pada keacakan. Cara sederhana untuk menghasilkan rangkaian bebas perkembangan adalah dengan memasukkan 1 ke dalam rangkaian Anda, lalu selalu tambahkan angka berikutnya yang tidak menghasilkan perkembangan aritmatika. Ikuti prosedur ini sampai Anda mencapai angka 10, dan Anda akan mendapatkan himpunan {1, 2, 4, 5, 10}. Namun ternyata ini bukanlah strategi terbaik secara umum. “Bagaimana jika kita tidak mulai dari 1?” kata Gasarch. "Jika Anda memulai dari tempat acak, Anda benar-benar melakukannya dengan lebih baik." Para peneliti tidak tahu mengapa keacakan sangat berguna, tambahnya.

Menghitung versi terbatas dari dua hasil teori Ramsey baru lainnya bahkan lebih menjengkelkan daripada menentukan ukuran himpunan bebas perkembangan. Hasil tersebut menyangkut jaringan matematika (disebut grafik) yang terdiri dari simpul yang dihubungkan oleh garis yang disebut tepi. Nomor Ramsey r(s, t) adalah jumlah simpul terkecil yang harus dimiliki suatu graf sebelum menjadi tidak mungkin untuk menghindari menyertakan salah satu grup s node yang terhubung atau t yang terputus. Nomor Ramsey sangat memusingkan untuk menghitungnya r(5, 5) tidak diketahui — antara 43 dan 48.

Dalam 1981, Brendan McKay, sekarang seorang ilmuwan komputer di Universitas Nasional Australia, menulis sebuah program perangkat lunak yang disebut nauty, yang dimaksudkan untuk mempermudah penghitungan angka Ramsey. Nauty memastikan bahwa peneliti tidak membuang waktu untuk memeriksa dua grafik yang hanya dibalik atau diputar versi satu sama lain. “Jika seseorang berada di area tersebut dan tidak menggunakan nauty, permainan berakhir. Anda harus menggunakannya, ”kata Stanisław Radziszowski, seorang matematikawan di Rochester Institute of Technology. Namun, jumlah perhitungan yang terlibat hampir tidak dapat dipahami. Pada 2013, Radziszowski dan Jan Goedgebeur membuktikan itu r(3, 10) paling banyak 42. “Menurut saya, butuh hampir 50 tahun CPU,” kata Goedgebeur, ilmuwan komputer di KU Leuven University di Belgia.

Jika Anda tidak dapat menghitung angka Ramsey yang tepat, Anda dapat mencoba mempersempit nilainya dengan contoh. Jika Anda menemukan grafik 45 simpul tanpa lima simpul yang semuanya terhubung dan tanpa lima simpul yang semuanya terputus, itu akan membuktikan bahwa r(5, 5) lebih besar dari 45. Matematikawan yang mempelajari bilangan Ramsey biasanya berpikir bahwa menemukan contoh tersebut, yang disebut grafik Ramsey, akan mudah, kata Radziszowski. Tapi ternyata tidak demikian. “Ada harapan bahwa konstruksi matematika yang bagus dan keren akan memberikan konstruksi terbaik, dan kami hanya membutuhkan lebih banyak orang untuk mengerjakannya,” katanya. "Perasaanku semakin kacau."

Keacakan merupakan hambatan untuk memahami dan alat yang berguna. Geoffrey Exo, seorang ilmuwan komputer di Indiana State University, telah menghabiskan waktu bertahun-tahun menyempurnakan metode acak untuk menghasilkan grafik Ramsey. Di dalam sebuah kertas 2015 mengumumkan lusinan grafik Ramsey baru yang memecahkan rekor, Exoo dan Milos Tatarevic membuat grafik acak dan kemudian secara bertahap menyesuaikannya dengan menghapus atau menambahkan tepi yang mengurangi jumlah cluster yang tidak diinginkan hingga mereka menemukan grafik Ramsey. Namun, teknik Exoo adalah seni, kata Radziszowski. Mereka terkadang memintanya untuk menggabungkan beberapa metode, atau menggunakan penilaian tentang jenis grafik yang akan dimulai. “Banyak, banyak orang mencobanya, dan mereka tidak bisa melakukannya,” kata Radziszowski.

Teknik yang dikembangkan untuk menghasilkan grafik Ramsey dapat berguna secara lebih luas suatu hari nanti, kata Goedgebeur, yang memiliki bekerja pada menghasilkan jenis lain dari grafik, seperti grafik yang mewakili senyawa kimia. “Bukan tidak mungkin teknik ini juga dapat ditransfer dan disesuaikan untuk membantu menghasilkan kelas grafik lain dengan lebih efisien (dan sebaliknya),” tulisnya dalam email.

Namun bagi Radziszowski, alasan mempelajari bilangan Ramsey kecil jauh lebih sederhana. “Karena terbuka, karena tidak ada yang tahu jawabannya,” ujarnya. “Kasus sepele yang kami lakukan dengan tangan; sedikit lebih besar, Anda membutuhkan komputer, dan sedikit lebih besar, bahkan komputernya tidak cukup bagus. Maka tantangan itu muncul.”