Giriş
Ekim ayının ortasında, Justin Gilmer bir arkadaşının düğününe katılmak için California'dan New York'a uçtu. Doğu Sahili'ndeyken eski danışmanını ziyaret etti. Michael Saks, Gilmer'in yedi yıl önce doktorasını aldığı Rutgers Üniversitesi'nde bir matematikçi.
Saks ve Gilmer öğle yemeğinde görüştüler ama matematik hakkında konuşmadılar. Aslında Gilmer, 2015'te Rutgers'ta mezun olduğundan beri matematiği ciddi olarak düşünmemişti. O zaman akademide kariyer yapmak istemediğine karar verdi ve bunun yerine kendi kendine programlamayı öğretmeye başladı. Saks'la yemek yerken Gilmer, eski akıl hocasına makine öğrenimi ve yapay zeka üzerinde çalıştığı Google'daki işinden bahsetti.
Gilmer'ın Rutgers'ı ziyaret ettiği gün hava güneşliydi. Etrafta dolaşırken, 2013'te bir yılın büyük bir bölümünü aynı kampüs yollarında yürüyerek sendika kapalı varsayımı denen bir sorunu düşünerek nasıl geçirdiğini hatırladı. Sonuçsuz da olsa bir saplantıydı bu: Gilmer tüm çabasına rağmen sayı kümeleriyle ilgili basit görünen problemin neden çözülmesinin bu kadar zor olduğunu kendi kendine öğrenmeyi başarmıştı.
"Bence pek çok insan, sorunun neden zor olduğunu anladıklarına ikna olana kadar sorun hakkında düşünüyor. Muhtemelen çoğu insandan daha fazla zaman harcadım, ”dedi Gilmer.
Ekim ziyaretinin ardından beklenmedik bir şey oldu: Aklına yeni bir fikir geldi. Gilmer, sendika kapalı varsayımını çözmek için bilgi teorisinden teknikleri uygulamanın yollarını düşünmeye başladı. Her fırsatta başarısız olmasını bekleyerek bir ay boyunca bu fikrin peşine düştü. Ama bunun yerine, ispata giden yol açılmaya devam etti. Nihayet 16 Kasım'da türünün ilk örneği bir sonuç yayınladı bu, matematikçileri tam varsayımı kanıtlamanın büyük bir yolunu bulur.
Gazete, bir takip çalışması telaşı başlattı. Diğer kurumların yanı sıra Oxford Üniversitesi, Massachusetts Institute of Technology ve Institute for Advanced Study'deki matematikçiler, Gilmer'in yeni yöntemlerini hızla geliştirdiler. Ama bunu yapmadan önce kendilerine bir soru sordular: Bu adam kim?
Yarı dolu
Birleşime kapalı varsayım, {1, 2} ve {2, 3, 4} gibi küme adı verilen sayı toplulukları hakkındadır. Kümeler üzerinde, birliklerini almak, yani birleştirmek de dahil olmak üzere işlemler yapabilirsiniz. Örneğin, {1, 2} ve {2, 3, 4}'ün birleşimi {1, 2, 3, 4}'tür.
Ailedeki herhangi iki kümenin birleşimi, ailedeki mevcut herhangi bir kümeye eşitse, kümelerden oluşan bir koleksiyon veya aile, "birleşim kapalı" olarak kabul edilir. Örneğin, bu dört setlik aileyi ele alalım:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Herhangi bir çifti birleştirin ve zaten ailede olan bir set elde edin, bu da aile birliğini kapalı hale getirir.
Matematikçiler, 1960'lara kadar uzanan, birliğin kapalı olduğu varsayımının versiyonları hakkında sohbet ettiler, ancak ilk resmi ifadesini 1979'da, tarafından yazılan bir makalede aldı. Peter Frankl1980'lerde Japonya'ya göç eden ve sokak performansını ilgi alanları arasında sayan Macar bir matematikçi.
Frankl, eğer bir kümeler ailesi kapalıysa, kümelerin en az yarısında görünen en az bir öğeye (veya sayıya) sahip olması gerektiğini varsaydı. İki nedenden dolayı doğal bir eşikti.
İlk olarak, kümelerin tam olarak %50'sinde tüm unsurların göründüğü, birliğe kapalı ailelerin kolayca bulunabilen örnekleri vardır. Örneğin, 1'den 10'a kadar sayılardan yapabileceğiniz tüm farklı setler gibi. Birliğe kapalı bir aile oluşturan bu tür 1,024 küme vardır ve 10 elementin her biri 512 tanesinde bulunur. İkincisi, Frankl varsayımı yaptığında, hiç kimse bu varsayımın geçerli olmadığı, sendikaya kapalı bir aile örneği sunmamıştı.
Yani %50 doğru tahmin gibi görünüyordu.
Bu, kanıtlamanın kolay olduğu anlamına gelmiyordu. Frankl'ın makalesinden bu yana geçen yıllarda çok az sonuç alındı. Gilmer'in çalışmasından önce, bu makaleler yalnızca ailedeki set sayısına göre değişen eşikler belirlemeyi başardı (her boyuttaki set aileleri için aynı %50 eşik olmasının aksine).
"Kolay olması gerekiyormuş gibi hissettiriyor ve kolay olan pek çok soruna benziyor, ancak saldırılara direndi" dedi. Will Sawin Columbia Üniversitesi'nden.
İlerleme eksikliği, hem problemin aldatıcı doğasını hem de birçok matematikçinin bu konu hakkında düşünmemeyi tercih ettiği gerçeğini yansıtıyordu; çözmesi imkansız olan aldatıcı bir sorunun peşinde koşarak kariyerlerinin yıllarını kaybedeceklerinden endişe ediyorlardı. Gilmer, 2013'te Saks'ın ofisine gidip sendika kapalı varsayımını gündeme getirdiği bir günü hatırlıyor. Geçmişte sorunla kendisi de mücadele etmiş olan danışmanı onu neredeyse odadan atıyordu.
Gilmer, "Mike, 'Justin, bu sorunu tekrar düşünmeme neden olacaksın ve bunu yapmak istemiyorum' dedi" dedi.
Bir Belirsizlik Anlayışı
Rutgers'ı ziyaretinin ardından Gilmer, neden bu kadar zor olduğunu anlamaya çalışarak sorunu zihninde evirip çevirdi. Kendi kendine temel bir gerçeği sordu: 100 kişilik bir aileniz varsa, ikisini seçip birleştirmenin 4,950 farklı yolu vardır. Sonra kendi kendine şunu sordu: En azından bir sıklıkta bu birleşimlerde hiçbir öğe görünmüyorsa, 4,950 farklı birleşimin yalnızca 100 kümeye geri dönmesi nasıl mümkün olabilir?
O noktada bile, henüz bilmese de bir kanıta doğru ilerliyordu. Rastgele bir çift nesne çektiğinizde ne bekleyeceğiniz konusunda titiz bir düşünme yolu sağlayan bilgi teorisinden gelen teknikler, onu oraya götürürdü.
Bilgi teorisi, 20. yüzyılın ilk yarısında, en ünlüsü Claude Shannon'ın 1948 tarihli makalesi ile geliştirildi, “Bir Matematiksel İletişim Kuramı” Makale, mesajın tam olarak ne söyleyeceği konusundaki belirsizlik miktarına bağlı olarak, bir mesaj göndermek için gereken bilgi miktarını hesaplamanın kesin bir yolunu sağladı. Bu bağlantı - bilgi ve belirsizlik arasında - Shannon'ın olağanüstü, temel içgörüsü buydu.
Bir oyuncak örneği almak için, beş kez yazı tura attığımı ve ortaya çıkan diziyi size gönderdiğimi hayal edin. Normal bir madeni para ise, iletilmesi için beş bitlik bilgi gerekir. Ancak yüklü bir madeni paraysa - diyelim ki %99 tura gelme olasılığı - çok daha az zaman alır. Örneğin, yüklenen madeni para beş kez de tura gelirse size 1 (tek bir bilgi biti) göndereceğim konusunda önceden anlaşabiliriz ki bu çok olasıdır. Adil bir yazı-tura atmanın sonucunda, önyargılı olana göre daha fazla sürpriz ve dolayısıyla daha fazla bilgi vardır.
Aynı düşünce, sayı kümelerinin içerdiği bilgiler için de geçerlidir. Birleşik kapalı kümelerden oluşan bir ailem varsa - 1,024'den 1'a kadar olan sayılardan oluşan 10 küme diyelim - rastgele iki küme seçebilirim. O zaman size her setin unsurlarını iletebilirim. Bu mesajı göndermek için gereken bilgi miktarı, bu öğelerin ne olduğu konusundaki belirsizliğin miktarını yansıtır: Örneğin, ilk kümedeki ilk öğenin 50 olma olasılığı %1'dir (çünkü 1, kümelerin yarısında görünür). aile), tıpkı adil bir yazı tura atma dizisinin ilk sonucunun tura gelme ihtimalinin %50 olduğu gibi.
Bilgi teorisi, genellikle Gilmer'ın yüksek lisans öğrencisi olarak çalıştığı, nesneleri saymakla ilgili bir matematik alanı olan kombinatorikte ortaya çıkar. Ancak California'ya geri dönerken, enformasyon teorisini kapalı birlik varsayımına bağlama düşüncesinin bir amatörün naif içgörüsü olduğundan endişeliydi: Çalışan matematikçiler bu parlak cisme daha önce rastlamış ve onu aptal altını olarak görmüşlerdi. .
Gilmer, "Dürüst olmak gerekirse, bunu daha önce kimsenin düşünmemesine biraz şaşırdım," dedi. "Ama belki de şaşırmamalıyım, çünkü ben de bunu bir yıldır düşünüyordum ve bilgi teorisini biliyordum."
Olma ihtimali olmama ihtimalinden daha yüksek
Gilmer, Google'daki işini bitirdikten sonra geceleri ve Ekim ayının ikinci yarısı ile Kasım ayı başlarında hafta sonları sorun üzerinde çalıştı. Bir grup matematikçinin yıllar önce keşfettiği fikirler onu cesaretlendirdi. açık işbirliği Tim Gowers adlı tanınmış bir matematikçinin blogunda. Ayrıca unuttuğu formüllere bakabilmek için yanında bir ders kitabıyla çalıştı.
"Harika bir sonuç bulan birinin 2. Bölüm'e başvurması gerekmediğini düşünürsünüz. Bilgi Teorisinin Unsurları, ama yaptım, ”dedi Gilmer.
Gilmer'ın stratejisi, tüm setlerin %1'inde bile hiçbir unsurun bulunmadığı sendikaya kapalı bir aile hayal etmekti - bu, gerçekten var olsaydı, Frankl'ın varsayımını yanlışlayacak bir karşı örnek.
Diyelim ki bu aileden rastgele A ve B olmak üzere iki küme seçtiniz ve bu kümelerde olabilecek öğeleri teker teker değerlendirdiniz. Şimdi sorun: A kümesinin 1 sayısını içerme olasılığı nedir? Ve B'yi ayarla? Her öğenin herhangi bir kümede görünme şansı %1'den biraz daha az olduğundan, ne A ne de B'nin 1 içermesini beklemezsiniz. yapmak.
Sonra, A ve B'nin birleşiminin 1 içermesi olasılığını düşünün. Yine de olası değildir, ancak bireysel kümelerden herhangi birinde görünme olasılığı daha yüksektir. A'da görünme olasılığı ile B'de görünme olasılığı eksi her ikisinde de olma olasılığının toplamıdır. Yani, belki %2'nin biraz altında.
Bu hala düşük, ancak 50-50 önermesine daha yakın. Bu, sonucu paylaşmak için daha fazla bilgi gerektiği anlamına gelir. Başka bir deyişle, tüm kümelerin en az %1'inde hiçbir öğenin bulunmadığı birleşime kapalı bir aile varsa, iki kümenin birleşiminde, kümelerin kendilerinden daha fazla bilgi vardır.
“Her şeyi öğe öğe ortaya çıkarma ve öğrendiğiniz bilgi miktarına bakma fikri son derece zekice. Kanıtın ana fikri bu” dedi. ryan alweiss Princeton Üniversitesi'nden.
Bu noktada Gilmer, Frankl'ın varsayımına yaklaşmaya başlıyordu. Bunun nedeni, birleşime kapalı bir ailede, iki kümenin birleşiminin kümelerin kendilerinden zorunlu olarak daha az bilgi içerdiğini - daha fazlasını değil - göstermenin kolay olmasıdır.
Nedenini görmek için, 1,024'den 1'a kadar sayılardan oluşturabileceğiniz 10 farklı kümeyi içeren birliğe kapalı aileyi düşünün. Bu kümelerden rastgele ikisini seçerseniz, ortalama olarak beş öğe içeren kümeler elde edersiniz. (Bu 1,024 kümeden 252'si beş öğe içerir, bu da onu en yaygın küme boyutu yapar.) Ayrıca, muhtemelen yaklaşık yedi öğe içeren bir birleşim elde edeceksiniz. Ancak yedi öğe içeren setler yapmanın yalnızca 120 farklı yolu vardır.
Mesele şu ki, rastgele seçilen iki kümenin içeriği hakkında, bunların birleşimi hakkında olduğundan daha fazla belirsizlik var. Birlik, daha az olasılığın olduğu, daha fazla öğe içeren daha büyük kümelere doğru eğilir. Sendikaya kapalı bir ailede iki kümenin birleşimini aldığınızda, ne elde edeceğinizi bir bakıma bilirsiniz - taraflı bir yazı tura attığınızda olduğu gibi - bu, birleşimin oluşturduğu kümelerden daha az bilgi içerdiği anlamına gelir.
Bununla Gilmer'ın bir kanıtı vardı. Setlerin %1'inde bile hiçbir öğenin görünmediğini biliyordu, birlik daha fazla bilgi içermek zorunda kalıyordu. Ancak sendika daha az bilgi içermelidir. Bu nedenle, kümelerin en az %1'inde görünen en az bir öğe olmalıdır.
50'ye Zorla
Gilmer, 16 Kasım'da kanıtını yayınladığında, yöntemini tam varsayımın kanıtına daha da yaklaşmak için kullanmanın mümkün olduğunu düşündüğünü ve potansiyel olarak eşiği %38'e yükseltebileceğini düşündüğü bir not ekledi.
Beş gün sonra, üç farklı gruplar Matematikçilerin oranı, Gilmer'ın tam da bunu yapmak için yaptığı çalışmaları temel alan makaleleri saatler içinde yayınladı. Ek kâğıtlar takip, ancak ilk patlama Gilmer'ın yöntemlerini gidebilecekleri kadar ileri götürmüş görünüyor; %50'ye ulaşmak büyük olasılıkla ek yeni fikirler gerektirecektir.
Yine de, takip makalelerinin yazarlarından bazıları için %38'e ulaşmak nispeten kolaydı ve Gilmer'ın bunu neden kendisinin yapmadığını merak ettiler. En basit açıklamanın doğru olduğu ortaya çıktı: Matematikten yarım on yıldan fazla bir süre sonra, Gilmer bunu başarmak için gereken teknik analitik çalışmanın bir kısmını nasıl yapacağını bilmiyordu.
Gilmer, "Biraz paslandım ve dürüst olmak gerekirse sıkışıp kaldım" dedi. "Ama topluluğun onu nereye götüreceğini görmek için sabırsızlanıyordum."
Yine de Gilmer, onu uygulamanın dışında bırakan aynı koşulların, muhtemelen ilk etapta kanıtını mümkün kıldığını düşünüyor.
"Lisansüstü okulda bu problem hakkında bir yıl boyunca neden düşündüğümü ve ilerleme kaydedemediğimi, altı yıl boyunca matematiği bıraktığımı ve sonra probleme geri dönüp bu çığır açışı yaptığımı ancak bu şekilde açıklayabilirim" dedi. "Makine öğreniminde olmak dışında nasıl açıklayacağımı bilmiyorum, düşüncelerimi önyargılı hale getirdi."
Düzeltme: Ocak 3, 2023
Orijinal başlık, Gilmer'dan "Google mühendisi" olarak söz ediyordu. Aslında o bir araştırmacıdır.
