1980'lerin ortasında matematikçi Jean Bourgain yüksek boyutlu şekillerle ilgili basit bir soru düşündü. Ve sonra hayatının geri kalanında buna takılıp kaldı.

2018 yılında hayatını kaybeden Bourgain, modern çağın önde gelen matematikçilerinden biriydi. Bir kazanan Alanlar MadalyasıMatematiğin en büyük onuru olan, olağanüstü bir problem çözücü olarak biliniyordu; aylardır üzerinde çalıştığınız bir problem hakkında konuşup, hemen çözmesini sağlayabileceğiniz türden bir insandı. Ancak Bourgain yüksek boyutlu şekillerle ilgili kendi sorusuna cevap veremiyordu.

"Bir keresinde Jean bana bu soruna daha fazla zaman harcadığını ve üzerinde çalıştığı diğer sorunlardan daha fazla çaba harcadığını söylemişti" diye yazdı. Vitali Milman Bu yılın başlarında Tel Aviv Üniversitesi'nden.

Bourgain'in problemini formüle etmesinden bu yana geçen yıllarda bu, Milman ve Bo'az Klartag İsrail'deki Weizmann Bilim Enstitüsü'nün denilen Yüksek boyutlu dışbükey şekiller (her zaman herhangi iki noktasını birleştiren doğru parçasının tamamını içeren şekiller) hakkındaki çok çeşitli soruları anlamak için "açılış kapısı". Yüksek boyutlu dışbükey şekiller, yalnızca matematikçiler için değil aynı zamanda istatistikçiler, makine öğrenimi araştırmacıları ve yüksek boyutlu veri kümeleriyle çalışan diğer bilgisayar bilimcileri için de merkezi bir çalışma nesnesidir.

Bourgain'in sorunu şu basit soruya dayanıyor: Diyelim ki dışbükey bir şeklin en sevdiğiniz birim seçiminde hacmi 1. Bir boyut daha düşük düz bir düzlem kullanarak şekli dilimlemenin tüm yollarını düşünürseniz, bu dilimlerin hepsi son derece düşük alana sahip olabilir mi, yoksa en azından birinin oldukça büyük olması mı gerekir?

Bourgain, bu düşük boyutlu dilimlerden bazılarının önemli bir alana sahip olması gerektiğini tahmin etti. Özellikle, boyuttan bağımsız bazı evrensel sabitlerin var olduğunu, öyle ki her şeklin alanı bu sabitten daha büyük olan en az bir dilim içerdiğini varsaydı.

İlk bakışta Bourgain'in varsayımı açıkça doğru görünebilir. Sonuçta, eğer şekil her yönden son derece inceyse, nasıl bir birim hacim oluşturmaya yetecek kadar maddeye sahip olabilir?

"Hadi ama, ne kadar zor olabilir ki?" Ronen EldanWeizmann Enstitüsü'ndeki yüksek boyutlu bir geometri uzmanı, problemi ilk duyduğunda düşündüğünü hatırlıyor. "Ve sonra, bunun hakkında ne kadar çok düşünürseniz, gerçekte ne kadar hassas olduğunu o kadar çok anlarsınız."

Buradaki zorluk, yüksek boyutlu şekillerin çoğu zaman insani, düşük boyutlu sezgilerimize meydan okuyan şekillerde davranmasıdır. Örneğin, 10 ve üzeri boyutlarda, küpün hacmi toptan daha büyük olacak şekilde bir küp ve bir top oluşturmak mümkündür, ancak küpün merkezinden geçen her dilim, küpün merkezinden geçen karşılık gelen dilimden daha küçük bir alana sahiptir. top.

"Yüksek boyutlu geometrinin güzelliği tam olarak ikinci boyuta benzememesidir" dedi Sebastien Bubeck Redmond, Washington'daki Microsoft Research'ten.

Bourgain'in dilimleme varsayımı, yüksek boyutlu uysallığa verilen bir oydur; yüksek boyutlu şekillerin en azından bazı açılardan sezgilerimize uyduğu yönündeki bir tahmin.

Artık Bourgain'in tahmini doğrulandı: A çevrimiçi yayınlanan kağıt Kasım ayında, Bourgain'in tam varsayımı olmadığı, ancak tüm pratik amaçlar için yüksek boyutlu tuhaflığa katı bir sınır koyacak kadar yakın bir versiyon olduğu kanıtlandı.

Klartag, Bourgain'in bu kadar güçlü bir sonuca ulaşmayı "hayal ettiğini" söyledi.

Yeni makale, Yuansi Chen - Zürih İsviçre Federal Teknoloji Enstitüsü'nde doktora sonrası araştırmacı olan ve Duke Üniversitesi'nin istatistiksel bilimler fakültesine katılmak üzere olan - Bourgain dilimleme problemine, KLS varsayımı adı verilen dışbükey geometri hakkında daha da geniş kapsamlı bir soru aracılığıyla ulaşıyor. Bir şekli iki eşit parçaya ayırmanın en iyi yolunu soran 25 yıllık bu varsayım, Bourgain'in varsayımını ima ediyor. Dahası, KLS varsayımı istatistik ve bilgisayar bilimlerindeki, ısının dışbükey bir şekilde yayılmasının ne kadar süreceği veya rastgele bir yürüyüşçünün bir başlangıç ​​noktasından oraya varmadan önce kaç adım atması gerektiği gibi birçok sorunun merkezinde yer alır. gerçekten rastgele bir konum.

Rastgele yürüyüşler Eldan, rastgele noktaları örneklemek için mevcut olan tek etkili yöntemlerin hemen hemen bunlar olduğunu söyledi. Ve çok çeşitli farklı bilgisayar bilimi problemleri için, "algoritmadaki en önemli alt rutin, rastgele bir noktayı örneklemek istemenizdir" dedi.

Chen'in yeni sonucu, aşağıdaki gibi görevler için algoritmaların bilinen çalışma sürelerinde anında iyileştirmeler sağlıyor: hacmi hesaplama dışbükey bir şekil veya çeşitli makine öğrenimi modellerinden örnekleme. Chen'in çalışması KLS varsayımının tamamını tam olarak kanıtlamıyor. Ancak bilgisayar bilimi uygulamaları söz konusu olduğunda Bubeck şöyle dedi: "Tam etkiyi elde etmek için tüm varsayımlara ihtiyacınız yok."

Chen, eğitim almış bir dışbükey geometri uzmanı değil; bunun yerine, rastgele örnekleme konusunu ele almak istediği için KLS varsayımıyla ilgilenen bir istatistikçidir. Eldan, "Toplumumuzda Yuansi Chen'i tanıyan kimse yok" dedi. "Bu adamın bir anda ortaya çıkıp en önemli sorunlarımızdan birini çözmesi çok güzel."

Gizli Dambıllar

Bourgain dilimleme problemi gibi, KLS varsayımı da (yaratıcılarının adını almıştır) Ravi Kannan, László Lovász ve Miklós Simonovits) basit bir soru sorar: Diyelim ki dışbükey bir şekli (belki de çukurları olmayan bir elmayı) iki eşit büyüklükte parçaya kesmek istiyorsunuz ve birini daha sonra kullanmak üzere bir kenara ayırmayı planlıyorsunuz. Açıkta kalan yüzey kahverengiye dönecek ve iştah açıcı olmayacak, bu yüzden onu mümkün olduğu kadar küçük yapmak istiyorsunuz. Tüm olası kesimler arasında açıkta kalan yüzeyi en aza indirecek olan hangisidir?

Düz kesimlerle sınırlıysanız, en azından yaklaşık olarak bu soruyu yanıtlamak çok zor değil. Ancak kavisli kesimler yapmanıza izin verilirse tüm bahisler geçersiz olur. İkinci boyutta matematikçiler en iyi kesimin her zaman düz bir çizgi veya bir daire yayı olacağını biliyorlar. Ancak üçüncü boyutta, en iyi kesim yalnızca birkaç basit şekil için anlaşılır ve daha yüksek boyutlu şekiller için matematikçilerin genellikle en uygun kesimi bulma umudu bile yoktur.

En uygun kavisli kesimi belirlemek çok zor olduğundan Kannan, Lovász ve Simonovits, yalnızca düz kesimlere izin verseniz işlerin ne kadar kötü olacağını merak ettiler. 1995'te, tahmin ettiler Bu kısıtlamanın işleri hiçbir zaman çok daha kötü hale getirmeyeceğini düşünüyorum: En iyi düz kesimin yüzey alanının en fazla sabit çarpı en iyi genel kesimin yüzey alanı olduğu evrensel bir sabit vardır.

"Bu harika bir fikirdi" dedi Santosh Vempala Kannan, Lovász ve Simonovits varsayımlarını kanıtlayamasa da Georgia Teknoloji Enstitüsü'nden. Evrensel bir sabit oluşturmak yerine yapabilecekleri en iyi şey, şeklin içinde yaşadığı boyutun kabaca karekökünü hesaplayan bir faktör oluşturmaktı. Yani örneğin 100 boyutlu bir dışbükey şekil için en iyi düz şeklin olduğunu biliyorlardı. kesim, en iyi kesimin yaklaşık 10 katı kadar yüzey alanını açığa çıkaracaktır.

10 kat daha fazla yüzey alanını açığa çıkarmak kulağa pek hoş gelmeyebilir. Ancak yüksek boyutlu şekillerin pek çok özelliği, boyut büyüdükçe katlanarak arttığından, bir karekökün büyüme değeri, kıyaslandığında mütevazı kalır. Bubeck, "Bu zaten yüksek boyutlarda hoş bir fenomenin var olduğunun bir göstergesi" dedi. "İşler sanıldığı kadar çılgınca değil."

Ancak araştırmacılar bu sonucu iyileştirmeye istekliydi ve bu sadece akademik ilgiden kaynaklanmıyordu: KLS faktörünün, dışbükey bir şekil içinde rastgele süreçlerin nasıl davrandığına ilişkin bir bilgi dünyasını kapsadığını biliyorlardı. Bunun nedeni, en iyi kesim ne kadar küçükse, rastgele bir sürecin şeklin etrafına hızla yayılması da o kadar zor olur.

Dar bir köprüyle birbirine bağlanan iki büyük topun bulunduğu bir dambıl düşünün. Sadece küçük bir kesimle onu iki eşit parçaya bölebilmeniz, köprünün bir darboğaz olduğu fikrini tam olarak yansıtıyor. İki toptan birindeki bir ısı kaynağının veya rastgele bir yürütecin, darboğazdan yolunu bulması gerektiğinden diğer topa ulaşması genellikle uzun zaman alacaktır.

Tabii ki dambıl dışbükey değildir. Dışbükey bir şekil, dambıldaki gibi orantısız derecede küçük düz bir kesime sahip olamaz, ancak orantısız olarak küçük kavisli bir kesime sahip olabilir. KLS varsayımı temel olarak, yüksek boyutlu bir dışbükey şeklin, rastgele karışımı yavaşlatan gizli, kıvrımlı bir tür dambıl içerip içermediğini soruyor.

Kannan, Lovász ve Simonovits'in karekök sınırı, bu gizli dambılların ne kadar aşırı olabileceğine sınır koyuyor. Ve 2012'de Eldan, sınırı boyutun küp köküne indirdi. bir teknik tanıtmak kabaca söylemek gerekirse, dışbükey şeklin eğilmesini ve noktalarının belirli bir bölgede yığılıncaya kadar bir yöne doğru kaydırılmasını öngören stokastik lokalizasyon olarak adlandırılır. Bir dambıldan olabildiğince farklı olan, yüksek derecede yoğunlaşmış bir kütle için KLS varsayımını kanıtlamak kolaydır. Eldan, eğme işleminin işleri çok fazla değiştirmediğini göstererek, orijinal şekil için sınırlanan KLS'yi hesaplamayı başardı. Bubeck, "Bu çok çok güzel bir süreç" dedi.

Birkaç yıl sonra Vempala ve Yin-Tat Lee Washington Üniversitesi'nden Eldan'ın stokastik yerelleştirmesi şu şekilde geliştirildi: KLS faktörünü düşürün daha da ileriye, boyutun dördüncü köküne kadar. Ve kısa, görkemli bir an için çok daha güçlü bir şey yaptıklarını düşündüler. Boyut çağrılırsa d, o zaman karekök d^1/2, küp kökü d^1/3ve dördüncü kök d^1/4. Önyükleme adı verilen yeni bir teknik sunarak Lee ve Vempala, KLS sınırını tamamen aşağıya indirebileceklerini düşündüler. d 0 artı küçük bir şekerleme faktörüne yükseltildi. O zamandan beri d⁰ her zaman 1'e eşit olduğundan Lee ve Vempala'nın sınırı aşağı yukarı bir sabitti.

Bubeck, Lee ona sonuçtan bahsettiğinde "Bu harika" dediğini hatırlıyor. "Bana göre bu büyük bir olaydı, en büyük övgüyü hak ediyordu" dedi.

Lee ve Vempala makalelerini internette yayınladılar. Ancak birkaç gün içinde Klartag, kanıtlarını baltalayan bir boşluk buldu. d⁰ ciltli. Lee ve Vempala hızla gözden geçirilmiş bir taslak yayınladılar. d^1/4 ciltli. Ve birkaç yıl boyunca araştırmacılar bunun KLS hikayesinin sonu olabileceğini düşündüler.

Bunun nedeni Eldan ve Klartag'ın daha önce gösterilen herhangi bir KLS sınırı anında bir Bourgain dilimleme sınırına dönüşür - örneğin Lee ve Vempala'nınki d^1/4 sınırlı, Bourgain dilimleme probleminde her zaman yüzey alanı en az yaklaşık 1/XNUMX olan bir dilimin olduğu anlamına gelir.d^1/4. Ancak matematikçiler 1/'yi kanıtlamanın birkaç yolunu zaten biliyorlardı.d^1/4 Bourgain dilimleme için bağlı. Belki de Lee ve Vempala'nın KLS sorusunun doğal son noktasına ulaşmış olduklarını düşündüler.

Eldan, "'Evet, belki de gerçek budur' diye hissetmeye başlamıştım" dedi.

Klartag, "Güçlü insanların bu yöntem üzerinde çalıştığı ve sömürülebilecek her şeyin sömürüldüğü hissi vardı" dedi. Ama bu Yuansi Chen gelmeden önceydi.

Sınırlayıcı Dilimler

Lee ve Vempala gözden geçirilmiş makalelerini yayınladıklarında, kabaca bir ispatın nasıl yapılacağına dair fikirlerini içinde korudular. d⁰ bağlı işe yarayabilir. Kanıtlarının yalnızca bir parçasının başarısız olduğunu açıkladılar.

Makaleleri, o zamanlar Berkeley'deki Kaliforniya Üniversitesi'nde istatistik yüksek lisans öğrencisi olan ve rastgele örnekleme yöntemlerinin karışım oranları üzerinde çalışan Chen'in dikkatini çekti. Rastgele örnekleme, yeni kanıtlara dayalı olarak inançları güncellemeye yönelik bir çerçeve olan Bayes istatistikleri gibi birçok istatistiksel çıkarım türünün önemli bir bileşenidir. Chen, "Bayes istatistikleri yapmak istiyorsanız her gün bu [rastgele] örneklemeyle uğraşırsınız" dedi.

Lee ve Vempala'nın makalesi Chen'e stokastik yerelleştirme fikrini tanıttı. Chen, "Bunun bir süredir gördüğüm en güzel ispat tekniklerinden biri olduğunu düşündüm" dedi.

Chen literatüre daldı ve Lee ile Vempala'nın kanıtındaki boşluğu doldurmak için birkaç hafta harcadı, ancak işe yaramadı. Önümüzdeki birkaç yıl içinde periyodik olarak, stokastik yerelleştirmenin nasıl değiştirileceğine dair bir fikir aklına geldi ve pes etmeden önce birkaç saat boyunca bunun üzerinde düşündü. Sonunda fikirlerinden biri meyvesini verdi: Lee ve Vempala'nın kanıtındaki eksik ifadeyi kanıtlamanın değil, bu kadar güçlü bir ifadeye duyulan ihtiyacı aşmanın bir yolu olduğunu fark etti.

Chen'in "bazı küçük numaralar" dediği, ancak Vempala'nın "zarif ve önemli yeni bir anlayış" dediği şey sayesinde Chen, Lee ve Vempala'nın önyükleme yönteminin nasıl işe yarayacağını buldu. Bu yöntem, sınırı oldukça küçük hale getirebilirseniz onu daha da küçültmenin bir yolu olduğunu göstererek KLS sınırını düşürmek için yinelemeli bir yaklaşım benimser. Tekrar tekrar uygulandığında bu önyükleme yaklaşımı, KLS varsayımı ve ayrıca Bourgain dilimleme problemi için yaklaşık olarak sabit sınıra ulaşır.

Chen çalışmasını internette yayınladığında, Klartag, "Yaptığım her şeyi hemen durdurdum ve bu makaleyi kontrol ettim" dedi. Önceki yanlış kanıtlar ve çoğunun Chen'in adını hiç duymamış olması nedeniyle araştırmacılar temkinli davrandılar. Ancak katkısının doğrulanmasının kolay olduğu ortaya çıktı. Klartag, "Bu makale %100 doğrudur" dedi. "Buna şüphe yok."

Chen'in sonucu, dışbükey bir şeklin en iyi 50-50 kesiminin, en iyi düz kesimden çok da küçük olmadığı anlamına geliyor; diğer bir deyişle, yüksek boyutlu dışbükey şekiller, çok dar köprülere sahip gizli dambıllar içermiyor. Bubeck, saf matematik perspektifinden bakıldığında "bu çok önemli, çünkü anlayışımızda çok büyük bir boşluk vardı" dedi.

Ve pratik açıdan bakıldığında bu, rastgele bir yürüyüşün dışbükey bir şekli araştırmacıların daha önce kanıtlayabildiğinden çok daha hızlı bir şekilde karıştırmasının garanti edildiği anlamına geliyor. Diğer şeylerin yanı sıra bu anlayış, bilgisayar bilimcilerin farklı rastgele örnekleme teknikleri arasında öncelik belirlemelerine, en temel rastgele yürüyüşün ne zaman en iyi olduğunu ve daha karmaşık ancak hesaplama açısından pahalı bir algoritmanın ne zaman daha iyi performans göstereceğini anlamalarına yardımcı olacaktır.

Sonuçta, kaç kişinin kanıtlamayı denediğini ve başarısız olduğunu düşünürsek d⁰ Vempala, kanıtın şaşırtıcı derecede basit olduğunu söyledi. Bourgain'in muhtemelen "Bunu nasıl kaçırdım?" diye düşüneceğini tahmin etti.

Matematikçiler Bourgain'in bu gelişmeden heyecan duyacağı konusunda hemfikir. 2018'deki ölümünden sadece birkaç ay önce Milman'la temasa geçerek herhangi bir ilerleme olup olmadığını sordu. Milman, "Ayrılmadan önce cevabı bilmek istedi" diye yazdı.

Düzeltme: 2 Mart 2021

Bu makale, Yuansi Chen'in Duke Üniversitesi'ndeki asıl görevinin İstatistik Bilimleri Bölümünde olduğunu açıklığa kavuşturmak için revize edildi.