'Tim-A' Matematika Membuktikan Hubungan Penting Antara Penjumlahan dan Himpunan | Majalah Kuanta

Dalam kumpulan angka yang dipilih secara acak, penjumlahan bisa menjadi liar.

Tambahkan setiap pasangan dari himpunan tersebut, dan Anda akan mendapatkan daftar baru yang mungkin memiliki lebih banyak nomor daripada yang Anda mulai. Mulailah dengan 10 angka acak, dan daftar baru ini (disebut jumlah) akan memiliki sekitar 50 elemen. Mulailah dengan 100 dan jumlahnya mungkin sekitar 5,000; 1,000 angka awal acak akan menghasilkan jumlah total 500,000 angka.

Namun jika himpunan awal Anda memiliki struktur, himpunan tersebut dapat menghasilkan angka yang lebih sedikit dari ini. Pertimbangkan himpunan 10 angka lainnya: semua bilangan genap dari 2 hingga 20. Karena pasangan yang berbeda akan menghasilkan angka yang sama — 10 + 12 sama dengan 8 + 14 dan 6 + 16 — jumlah tersebut hanya memiliki 19 angka, bukan 50. Perbedaan ini menjadi semakin besar seiring dengan semakin besarnya himpunan. Daftar terstruktur yang terdiri dari 1,000 angka mungkin memiliki jumlah yang hanya berisi 2,000 angka.

Pada tahun 1960an, seorang matematikawan bernama Gregory Freiman mulai menyelidiki himpunan dengan jumlah kecil dalam upaya menyelidiki hubungan antara penjumlahan dan struktur himpunan — hubungan penting yang mendefinisikan bidang matematika kombinatorik aditif. Freiman membuat kemajuan yang mengesankan, membuktikan bahwa himpunan dengan jumlah kecil harus ditampung oleh himpunan lebih besar yang elemen-elemennya ditempatkan dalam pola yang sangat teratur. Namun kemudian lapangan mengalami stagnasi. “Bukti asli Freiman sangat sulit untuk dipahami, sampai pada titik di mana tidak seorang pun benar-benar yakin bahwa bukti tersebut benar. Jadi dampaknya tidak terlalu besar,” kata Timothy Gower, seorang ahli matematika di Collège de France dan Universitas Cambridge dan peraih medali Fields. "Tapi kemudian Aku Ruzsa meledak ke tempat kejadian.”

Dalam serangkaian dua dokumen pada tahun 1990-an, Ruzsa membuktikan kembali teorema Freiman dengan argumen baru yang elegan. Beberapa tahun kemudian, Katalin Marton, seorang matematikawan berpengaruh asal Hongaria yang meninggal pada tahun 2019, mengubah pertanyaan tentang apa yang tersirat dalam jumlah kecil terhadap struktur himpunan aslinya. Dia mengganti jenis elemen yang muncul dalam himpunan dan jenis struktur yang harus dicari oleh ahli matematika, dengan berpikir bahwa hal itu akan memungkinkan ahli matematika untuk mengekstrak lebih banyak informasi. Dugaan Marton mempunyai hubungan dengan sistem pembuktian, teori pengkodean dan kriptografi, dan menempati tempat yang tinggi dalam kombinatorik aditif.

Dugaannya “terasa seperti salah satu hal paling mendasar yang tidak kami pahami,” katanya Ben Hijau, seorang ahli matematika di Universitas Oxford. Itu “hanya mendasari banyak hal yang saya pedulikan.”

Green bergabung dengan Gowers, Freddie Tata Krama dari Universitas California, San Diego, dan Terence tao, peraih medali Fields di Universitas California, Los Angeles yang menjadi ahli matematika dan blogger Israel Gil Kalai disebut “Sebuah tim” dari ahli matematika. Mereka membuktikan versi dugaan tersebut dalam sebuah makalah dibagikan pada 9 November.

Jaring Katz, seorang ahli matematika di Rice University yang tidak terlibat dalam penelitian ini, menggambarkan bukti tersebut sebagai “sangat jelas” – dan “kurang lebih benar-benar tiba-tiba.”

Tao kemudian memulai upaya untuk meresmikan bukti tersebut Bersandar, bahasa pemrograman yang membantu ahli matematika memverifikasi teorema. Hanya dalam beberapa minggu, upaya itu berhasil. Selasa dini hari tanggal 5 Desember, Tao mengumumkan bahwa Lean telah membuktikan dugaan tersebut tanpa kata "maaf" - pernyataan standar yang muncul ketika komputer tidak dapat memverifikasi langkah tertentu. Ini adalah penggunaan yang paling terkenal alat verifikasi sejak 2021, dan menandai titik perubahan dalam cara para ahli matematika menulis bukti dalam istilah yang dapat dipahami oleh komputer. Jika alat-alat ini menjadi cukup mudah untuk digunakan oleh para ahli matematika, mereka mungkin dapat menggantikan proses tinjauan sejawat yang seringkali memakan waktu lama dan berat, kata Gowers.

Bahan-bahan pembuktiannya telah mendidih selama beberapa dekade. Gowers merencanakan langkah pertamanya pada awal tahun 2000an. Namun butuh waktu 20 tahun untuk membuktikan apa yang disebut Kalai sebagai “cawan suci” di bidang ini.

Grup Dalam

Untuk memahami dugaan Marton, ada baiknya kita mengenal konsep grup, suatu objek matematika yang terdiri dari himpunan dan operasi. Bayangkan bilangan bulat - himpunan bilangan tak terbatas - dan operasi penjumlahan. Setiap kali Anda menjumlahkan dua bilangan bulat, Anda mendapatkan bilangan bulat lainnya. Penjumlahan juga mematuhi beberapa aturan operasi grup lainnya, seperti asosiatif, yang memungkinkan Anda mengubah urutan operasi: 3 + (5 + 2) = (3 + 5) + 2.

Dalam suatu grup, terkadang Anda dapat menemukan himpunan lebih kecil yang memenuhi semua properti grup. Misalnya, jika Anda menjumlahkan dua bilangan genap, Anda akan mendapatkan bilangan genap lainnya. Bilangan genap adalah satu grup tersendiri, menjadikannya subgrup dari bilangan bulat. Sebaliknya, bilangan ganjil bukanlah subgrup. Jika Anda menjumlahkan dua bilangan ganjil, Anda mendapatkan bilangan genap — bukan bilangan aslinya. Namun Anda bisa mendapatkan semua bilangan ganjil hanya dengan menambahkan 1 pada setiap bilangan genap. Subgrup yang bergeser seperti ini disebut koset. Ia tidak memiliki semua properti subgrup, tetapi ia mempertahankan struktur subgrupnya dalam banyak hal. Misalnya, sama seperti bilangan genap, bilangan ganjil semuanya mempunyai jarak yang sama.

Marton mengira jika Anda memiliki set yang akan kami hubungi A terdiri dari elemen-elemen grup yang jumlahnya tidak jauh lebih besar A itu sendiri, maka terdapat beberapa subgrup — sebut saja G — dengan properti khusus. Menggeser G beberapa kali untuk membuat koset, dan koset tersebut, jika digabungkan, akan berisi himpunan aslinya A. Selain itu, ia berasumsi bahwa jumlah koset tidak bertambah lebih cepat dibandingkan jumlah kohimpunan — ia percaya bahwa jumlah koset harus dikaitkan dengan faktor polinomial, bukan pertumbuhan eksponensial yang jauh lebih cepat.

Ini mungkin terdengar seperti keingintahuan yang sangat teknis. Namun karena ini berkaitan dengan pengujian sederhana - apa yang terjadi jika Anda menambahkan hanya dua elemen dalam kumpulan? — untuk keseluruhan struktur subgrup, hal ini sangat penting bagi ahli matematika dan ilmuwan komputer. Gagasan umum yang sama muncul ketika ilmuwan komputer mencoba mengenkripsi pesan sehingga Anda dapat memecahkan kode sedikit saja dari pesan tersebut pada suatu waktu. Hal ini juga muncul dalam bukti yang dapat diperiksa secara probabilistik, suatu bentuk bukti yang dapat diverifikasi oleh ilmuwan komputer dengan hanya memeriksa beberapa bagian informasi yang terisolasi. Dalam masing-masing kasus ini, Anda bekerja hanya dengan beberapa poin dalam sebuah struktur - mendekodekan hanya beberapa bit dari pesan yang panjang, atau memverifikasi sebagian kecil dari bukti yang rumit - dan menyimpulkan sesuatu tentang struktur yang lebih besar dan tingkat yang lebih tinggi.

“Anda bisa berpura-pura semuanya adalah bagian besar dari suatu kelompok,” katanya Tom Sanders, mantan mahasiswa Gowers yang sekarang menjadi kolega Green's di Oxford, atau Anda bisa, “mendapatkan semua yang Anda inginkan dari adanya banyak kebetulan tambahan. Kedua perspektif ini berguna.”

Ruzsa menerbitkan dugaan Marton pada tahun 1999, memberinya penghargaan penuh. “Dia sampai pada dugaan itu secara independen dari saya dan Freiman, dan mungkin sebelum kami,” katanya. “Itulah mengapa, saat aku berbicara dengannya, aku memutuskan untuk menyebutnya sebagai dugaannya.” Namun, para ahli matematika sekarang menyebutnya sebagai dugaan polinomial Freiman-Ruzsa, atau PFR.

Nol dan Satu

Grup, seperti banyak objek matematika, mempunyai banyak bentuk yang berbeda. Marton menduga dugaannya berlaku untuk semua kalangan. Ini masih belum diperlihatkan. Makalah baru membuktikannya untuk jenis kelompok tertentu, yang mengambil daftar bilangan biner seperti (0, 1, 1, 1, 0) sebagai elemennya. Karena komputer bekerja dalam biner, kelompok ini sangat penting dalam ilmu komputer. Tapi itu juga berguna dalam kombinatorik aditif. “Ini seperti setting mainan di mana Anda bisa bermain-main dan mencoba berbagai hal,” kata Sanders. “Aljabar jauh lebih bagus” daripada bekerja dengan bilangan bulat, tambahnya.

Daftar tersebut memiliki panjang yang tetap, dan setiap bit dapat berupa 0 atau 1. Anda menjumlahkannya dengan menambahkan setiap entri ke pasangannya di daftar lain, dengan aturan bahwa 1 + 1 = 0. Jadi (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR adalah upaya untuk mencari tahu seperti apa suatu himpunan jika ia bukan merupakan subgrup tetapi memiliki beberapa fitur mirip grup.

Untuk membuat PFR lebih presisi, bayangkan Anda mempunyai sekumpulan daftar biner yang disebut A. Sekarang ambil setiap pasangan elemen dari A dan menambahkannya. Jumlah yang dihasilkan merupakan jumlah dari A, Yang disebut A + A. Jika unsur dari A dipilih secara acak, maka sebagian besar jumlahnya berbeda satu sama lain. jika ada k elemen di A, itu berarti akan ada sekitar k²/2 elemen dalam jumlah. Kapan k besar — ​​katakanlah, 1,000 — k²/2 jauh lebih besar dari k. Tapi jika A adalah subgrup, setiap elemen dari A + A dalam A, yang berarti bahwa A + A ukurannya sama dengan A itu sendiri.

PFR mempertimbangkan himpunan yang tidak acak, namun juga bukan subgrup. Dalam himpunan ini, jumlah elemen di A + A agak kecil — katakanlah, 10k, Atau 100k. “Ini sangat berguna ketika gagasan Anda tentang struktur jauh lebih kaya daripada sekadar struktur aljabar eksak,” kata Shachar Lovett, seorang ilmuwan komputer di Universitas California, San Diego.

Semua himpunan yang diketahui ahli matematika yang mematuhi properti ini “cukup dekat dengan subkelompok sebenarnya,” kata Tao. “Itulah intuisinya, bahwa tidak ada kelompok palsu lainnya yang beredar.” Freiman telah membuktikan versi pernyataan ini dalam karya aslinya. Pada tahun 1999, Ruzsa memperluas teorema Freiman dari bilangan bulat ke pengaturan daftar biner. Dia membuktikan bahwa ketika jumlah elemen dalam A + A adalah kelipatan konstan dari ukuran A, A terkandung dalam subgrup.

Namun teorema Ruzsa mengharuskan subgrupnya berukuran sangat besar. Wawasan Marton adalah mengandaikan bahwa alih-alih tergabung dalam satu subgrup raksasa, A dapat ditampung dalam sejumlah koset polinomial dari suatu subgrup yang tidak lebih besar dari himpunan aslinya A.

'Saya Tahu Ide Nyata Ketika Saya Melihat Ide Nyata'

Sekitar pergantian milenium, Gowers menemukan bukti teorema Freiman Ruzsa saat mempelajari masalah berbeda tentang himpunan yang berisi rangkaian bilangan yang berjarak sama. “Saya memerlukan sesuatu seperti ini, semacam mendapatkan informasi struktural dari informasi yang lebih longgar tentang kumpulan tertentu,” kata Gowers. “Saya sangat beruntung karena belum lama ini, Ruzsa menghasilkan bukti yang sangat indah ini.”

Gowers mulai mencari bukti potensial dari dugaan versi polinomial. Idenya adalah memulai dengan satu set A yang jumlahnya relatif kecil, kemudian dimanipulasi secara bertahap A menjadi subgrup. Jika dia dapat membuktikan bahwa subgrup yang dihasilkan mirip dengan himpunan aslinya A, dia dapat dengan mudah menyimpulkan dugaan itu benar. Gowers berbagi idenya dengan rekan-rekannya, namun tidak ada yang bisa mewujudkannya menjadi bukti penuh. Meskipun strategi Gowers berhasil dalam beberapa kasus, namun pada kasus lain terjadi manipulasi A semakin jauh dari kesimpulan yang diinginkan dari dugaan polinomial Freiman-Ruzsa.

Akhirnya, lapangan terus berjalan. Pada tahun 2012, Sanders hampir terbukti PFR. Namun jumlah subgrup bergeser yang dibutuhkannya berada di atas level polinomial, meski hanya sedikit. “Setelah dia melakukan itu, itu berarti masalah tersebut menjadi tidak terlalu mendesak, namun tetap menjadi masalah yang sangat bagus dan saya sangat menyukainya,” kata Gowers.

Namun gagasan Gowers tetap hidup dalam ingatan dan hard drive rekan-rekannya. “Ada ide nyata di sana,” kata Green, yang juga pernah menjadi mahasiswa Gowers. “Saya mengetahui ide yang sebenarnya ketika saya melihat ide yang nyata.” Musim panas ini, Green, Manners, dan Tao akhirnya membebaskan ide Gowers dari api penyucian mereka.

Green, Tao, dan Manners berkolaborasi sedalam 37 halaman sebelum mereka berpikir untuk kembali ke ide Gowers yang berusia 20 tahun. Pada tanggal 23 Juni kertas, mereka telah berhasil menggunakan konsep dari teori probabilitas yang disebut variabel acak untuk menyelidiki struktur himpunan dengan jumlah kecil. Dengan melakukan peralihan ini, grup dapat memanipulasi set mereka dengan lebih mahir. “Berurusan dengan variabel acak jauh lebih tidak kaku dibandingkan berurusan dengan himpunan,” kata Manners. Dengan variabel acak, “Saya dapat mengubah salah satu probabilitas dengan jumlah kecil, dan itu mungkin memberi saya variabel acak yang lebih baik.”

Dengan menggunakan perspektif probabilistik ini, Green, Manners, dan Tao dapat beralih dari bekerja dengan jumlah elemen dalam suatu himpunan ke pengukuran informasi yang terdapat dalam variabel acak, kuantitas yang disebut entropi. Entropi bukanlah hal baru dalam kombinatorik aditif. Faktanya, Tao telah mencoba untuk mempopulerkan konsep tersebut pada akhir tahun 2000an. Namun belum ada yang mencoba menggunakannya pada dugaan polinomial Freiman-Ruzsa. Green, Manners, dan Tao menemukan bahwa itu sangat kuat. Namun mereka masih belum bisa membuktikan dugaan tersebut.

Saat kelompok tersebut merenungkan hasil baru mereka, mereka menyadari bahwa mereka akhirnya membangun lingkungan di mana ide-ide Gowers yang tidak aktif dapat berkembang. Jika mereka mengukur ukuran suatu himpunan menggunakan entropinya, bukan jumlah elemennya, detail teknisnya mungkin akan lebih baik. “Pada titik tertentu kami menyadari bahwa ide-ide lama dari Tim dari 20 tahun lalu sebenarnya lebih mungkin berhasil dibandingkan ide-ide yang kami coba,” kata Tao. “Jadi kami membawa Tim kembali ke proyek ini. Dan kemudian semua bagiannya sangat cocok satu sama lain.”

Namun, masih banyak detail yang harus diketahui sebelum bukti muncul. “Agak bodoh kalau kami berempat sangat sibuk dengan hal lain,” kata Manners. “Anda ingin mempublikasikan hasil luar biasa ini dan memberi tahu dunia, tetapi Anda sebenarnya masih harus menulis ujian tengah semester Anda.” Akhirnya, kelompok tersebut berhasil lolos, dan pada tanggal 9 November, mereka memposting makalah mereka. Mereka membuktikan bahwa jika A + A tidak lebih besar dari k kali ukuran A, kemudian A dapat dicakup oleh tidak lebih dari tentang k¹² pergeseran subkelompok yang tidak lebih besar dari A. Ini adalah potensi perubahan dalam jumlah yang sangat besar. Tapi ini polinomial, jadi tidak tumbuh secepat eksponensial k menjadi lebih besar, seperti yang terjadi jika k berada di eksponen.

Beberapa hari kemudian, Tao mulai meresmikan buktinya. Dia menjalankan proyek formalisasi secara kolaboratif, menggunakan paket kontrol versi GitHub untuk mengoordinasikan kontribusi 25 sukarelawan di seluruh dunia. Mereka menggunakan alat yang disebut Denah dikembangkan oleh Patrick Masot, seorang ahli matematika di Universitas Paris-Saclay, untuk mengatur upaya menerjemahkan dari apa Tao bernama “Bahasa Inggris Matematika” ke dalam kode komputer. Cetak biru antara lain dapat menciptakan a grafik menggambarkan berbagai langkah logis yang terlibat dalam pembuktian. Setelah semua gelembung tertutup oleh apa yang disebut Tao sebagai “warna hijau yang indah”, tim selesai. Mereka menemukan beberapa kesalahan ketik kecil di koran — di media online pesan, Tao mencatat bahwa “bagian yang paling menarik secara matematis dari proyek ini relatif mudah untuk diformalkan, namun langkah-langkah teknisnya yang 'jelas' lah yang memakan waktu paling lama.”

Marton meninggal hanya beberapa tahun sebelum dugaannya yang terkenal itu terbukti, tetapi buktinya sama pekerjaan hidup tentang entropi dan teori informasi. “Semuanya bekerja lebih baik ketika Anda melakukannya dalam kerangka entropi ini daripada dalam kerangka yang saya coba lakukan,” kata Gowers. “Bagiku, ini masih terasa ajaib.”

Quanta sedang melakukan serangkaian survei untuk melayani audiens kami dengan lebih baik. Ambil milik kami survei pembaca matematika dan anda akan diikut sertakan untuk menang secara gratis Quanta barang dagangan