Rastgele seçilmiş bir sayı kümesinde toplama işlemi çılgına dönebilir.

Böyle bir kümedeki her çifti bir araya topladığınızda, muhtemelen başladığınızdan çok daha fazla sayı içeren yeni bir liste elde edersiniz. 10 rastgele sayıyla başlayın; bu yeni liste (toplam adı verilen) yaklaşık 50 öğeye sahip olacaktır. 100 ile başlayın ve toplamın yaklaşık 5,000 olması muhtemeldir; 1,000 rastgele başlangıç ​​sayısı, 500,000 sayı uzunluğunda bir toplam oluşturacaktır.

Ancak başlangıç ​​kümeniz bir yapıya sahipse, toplam bundan daha az sayıda sayıyla sonuçlanabilir. Başka bir 10 sayılık küme düşünün: 2'den 20'ye kadar tüm çift sayılar. Farklı çiftlerin toplamı aynı sayıya ulaşacağından - 10 + 12, 8 + 14 ve 6 + 16 ile aynıdır - toplam kümede yalnızca 19 sayı vardır, değil 50. Setler büyüdükçe bu fark daha da derinleşiyor. 1,000 sayıdan oluşan yapılandırılmış bir listede yalnızca 2,000 sayı içeren bir toplam bulunabilir.

1960'lı yıllarda bir matematikçi Gregory Freiman toplama ve küme yapısı arasındaki bağlantıyı araştırmak amacıyla küçük toplam kümeleri olan kümeleri araştırmaya başladı; bu, toplamalı kombinatoriklerin matematiksel alanını tanımlayan çok önemli bir bağlantıdır. Freiman etkileyici bir ilerleme kaydetti ve küçük toplam kümeye sahip bir kümenin, elemanları son derece düzenli bir düzende aralıklandırılmış daha büyük bir küme tarafından kapsanması gerektiğini kanıtladı. Ancak daha sonra alan durdu. “Freiman'ın orijinal kanıtını anlamak olağanüstü derecede zordu, öyle ki hiç kimse bunun doğruluğundan kesinlikle emin değildi. Yani gerçekte sahip olabileceği etkiyi yaratmadı” dedi. Timothy GowersCollège de France ve Cambridge Üniversitesi'nde matematikçi ve Fields madalyası sahibi. "Ama sonra İmre Ruzsa olay yerine koştu."

Bir dizi iki kâğıtlar 1990'larda Ruzsa, Freiman'ın teoremini zarif ve yeni bir argümanla yeniden kanıtladı. Birkaç yıl sonra, Katalin Marton2019'da ölen etkili Macar matematikçi, küçük bir toplam kümenin orijinal kümenin yapısı hakkında ne anlama geldiği sorusunu değiştirdi. Matematikçilerin daha da fazla bilgi çıkarmasına olanak sağlayacağını düşünerek, kümede görünen öğe türlerini ve matematikçilerin araması gereken yapı türünü değiştirdi. Marton'un varsayımının kanıt sistemleri, kodlama teorisi ve kriptografiyle bağlantıları vardır ve toplamsal kombinatoriklerde yüce bir yere sahiptir.

Onun varsayımı "gerçekten anlamadığımız en temel şeylerden biri gibi geliyor" dedi Ben YeşilOxford Üniversitesi'nden bir matematikçi. "Önem verdiğim pek çok şeyin temelini oluşturdu."

Green, Gowers'la güçlerini birleştirdi Freddie Davranışları Kaliforniya Üniversitesi, San Diego ve Terence taoİsrailli matematikçi ve blog yazarının oluşturduğu Kaliforniya Üniversitesi, Los Angeles'ta Fields madalyası sahibi Gil Kalai “ denirBir takım” matematikçilerin. Bir makalede varsayımın bir versiyonunu kanıtladılar 9 Kasım'da paylaşıldı.

Ağ KatzRice Üniversitesi'nden çalışmada yer almayan bir matematikçi, kanıtı "son derece basit" ve "hemen hemen tamamen birdenbire" olarak tanımlıyor.

Tao daha sonra kanıtı resmileştirmek için bir çaba başlattı. Yalınmatematikçilerin teoremleri doğrulamasına yardımcı olan bir programlama dili. Sadece birkaç hafta içinde bu çaba başarıya ulaştı. 5 Aralık Salı sabahı erken saatlerde, Tao duyurdu Lean'in bu varsayımı herhangi bir "özür dilemeden" kanıtladığını söyledi; bu, bilgisayar belirli bir adımı doğrulayamadığında ortaya çıkan standart ifadedir. Bu, bu türden en yüksek profilli kullanımdır 2021'den beri doğrulama araçlarıve matematikçilerin bilgisayarın anlayabileceği terimlerle ispat yazma biçimlerinde bir dönüm noktasını işaret ediyor. Gowers, bu araçların matematikçilerin kullanımı için yeterince kolay hale gelmesi durumunda, genellikle uzun süren ve zahmetli akran değerlendirmesi sürecinin yerini alabileceklerini söyledi.

Kanıtın içeriği onlarca yıldır kaynıyordu. Gowers ilk adımlarını 2000'li yılların başında attı. Ancak Kalai'nin alanın "kutsal kâsesi" olarak adlandırdığı şeyin kanıtlanması 20 yıl sürdü.

Grup İçi

Marton'un varsayımını anlamak için, bir küme ve bir işlemden oluşan matematiksel bir nesne olan grup kavramını bilmek yardımcı olur. Tam sayıları (sonsuz bir sayı kümesi) ve toplama işlemini düşünün. İki tam sayıyı her topladığınızda başka bir tam sayı elde edersiniz. Toplama işlemi aynı zamanda grup işlemlerinin, işlemlerin sırasını değiştirmenizi sağlayan ilişkisellik gibi diğer birkaç kuralına da uyar: 3 + (5 + 2) = (3 + 5) + 2.

Bir grup içinde bazen tüm grup özelliklerini karşılayan daha küçük kümeler bulabilirsiniz. Örneğin herhangi iki çift sayıyı toplarsanız başka bir çift sayı elde edersiniz. Çift sayılar kendi başlarına bir gruptur ve onları tam sayıların bir alt grubu haline getirir. Tek sayılar ise aksine bir alt grup değildir. İki tek sayıyı toplarsanız, orijinal kümede olmayan bir çift sayı elde edersiniz. Ancak her çift sayıya 1 ekleyerek tüm tek sayıları elde edebilirsiniz. Bunun gibi kaydırılmış bir alt gruba koset denir. Bir alt grubun tüm özelliklerine sahip değildir ancak birçok yönden alt grubunun yapısını korur. Örneğin, tıpkı çift sayılar gibi, tek sayılar da eşit aralıklarla yerleştirilmiştir.

Marton, eğer bir setiniz varsa arayacağımızı düşündü. A toplamı çok da büyük olmayan grup elemanlarından oluşur. A kendisi varsa, o zaman bir alt grup vardır - buna adını verin G - özel bir özelliğe sahip. Vardiya G kosetler yapmak için birkaç kez ve bu kosetler birlikte alındığında orijinal seti içerecektir A. Dahası, kosetlerin sayısının toplamın boyutundan çok daha hızlı artmadığını varsaydı; bunun çok daha hızlı bir üstel büyümenin aksine bir polinom faktörüyle ilişkili olması gerektiğine inanıyordu.

Bu oldukça teknik bir merak gibi gelebilir. Ancak basit bir testle ilgili olduğu için kümeye yalnızca iki öğe eklediğinizde ne olur? — Bir alt grubun kapsayıcı yapısı matematikçiler ve bilgisayar bilimcileri için çok önemlidir. Aynı genel fikir, bilgisayar bilimcileri mesajları şifrelemeye çalıştıklarında da ortaya çıkıyor, böylece mesajın sadece bir kısmını çözebilirsiniz. Aynı zamanda olasılıksal olarak kontrol edilebilir kanıtlarda da görülür; bu, bilgisayar bilimcilerin yalnızca birkaç izole bilgi parçasını kontrol ederek doğrulayabildiği bir kanıt biçimidir. Bu durumların her birinde, bir yapıdaki yalnızca birkaç noktayla çalışırsınız (uzun bir mesajdan yalnızca birkaç bitin kodunu çözmek veya karmaşık bir kanıtın küçük bir bölümünü doğrulamak) ve daha büyük, daha üst düzey bir yapı hakkında bir sonuca varırsınız.

"Her şeyin bir grubun büyük bir alt kümesi olduğunu iddia edebilirsiniz" dedi Tom SandersGowers'ın eski bir öğrencisi ve şu anda Green'in Oxford'daki bir meslektaşı olan ya da siz, “birçok ek tesadüfün varlığından istediğiniz her şeyi elde edebilirsiniz. Bu bakış açılarının her ikisi de faydalıdır.”

Ruza Marton'un varsayımını 1999'da yayınladı, ona tam kredi veriyor. "Bu varsayıma benden ve Freiman'dan bağımsız olarak ve muhtemelen bizden önce ulaştı" dedi. "Bu yüzden onunla konuştuğumda buna onun varsayımı demeye karar verdim." Yine de matematikçiler artık buna polinom Freiman-Ruzsa varsayımı veya PFR adını veriyor.

Sıfırlar ve Birler

Birçok matematiksel nesne gibi gruplar da birçok farklı biçime sahiptir. Marton, varsayımının tüm gruplar için doğru olduğunu varsaydı. Bu henüz gösterilmedi. Yeni makale, (0, 1, 1, 1, 0) gibi ikili sayıların öğelerini listeleyen belirli bir grup türü için bunu kanıtlıyor. Bilgisayarlar ikili sistemde çalıştığı için bu grup bilgisayar biliminde çok önemlidir. Ama aynı zamanda katkısal kombinatoriklerde de faydalı oldu. Sanders, "Bu, içinde oyun oynayabileceğiniz ve bir şeyler deneyebileceğiniz bir oyuncak ortamına benziyor" dedi. "Cebir, tam sayılarla çalışmaktan çok çok daha güzel" diye ekledi.

Listelerin sabit uzunlukları vardır ve her bit 0 veya 1 olabilir. 1 + 1 = 0 kuralıyla her girişi başka bir listedeki karşılığına ekleyerek bunları bir araya getirirsiniz. Yani (0, 1, 1, 1) , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR, bir kümenin tam olarak bir alt grup olmasa da bazı grup benzeri özelliklere sahip olması durumunda nasıl görünebileceğini anlamaya yönelik bir girişimdir.

PFR'yi kesinleştirmek için, adında bir dizi ikili listeniz olduğunu hayal edin. A. Şimdi her öğe çiftini alın A ve bunları toplayın. Ortaya çıkan toplamlar toplamını oluşturur ADenilen A + A. Eğer unsurları A Rastgele seçilirse, toplamların çoğu birbirinden farklıdır. Eğer varsa k içindeki elemanlar A, bu etrafta olacak anlamına geliyor k²Toplamda /2 öğe. Ne zaman k büyük - örneğin 1,000 - k²/2 bundan çok daha büyük k. Ama eğer A bir alt gruptur, her elemanı A + A olduğu A, anlamında A + A ile aynı boyutta A kendisi.

PFR, rastgele olmayan ancak alt grup da olmayan kümeleri dikkate alır. Bu kümelerdeki eleman sayısı A + A biraz küçük - örneğin 10kVeya 100k. "Yapı anlayışınız tam bir cebirsel yapı olmaktan çok daha zengin olduğunda bu gerçekten faydalıdır" dedi Shachar Lovett, San Diego'daki Kaliforniya Üniversitesi'nde bilgisayar bilimcisi.

Tao, matematikçilerin bu özelliğe uyduğunu bildiği tüm kümelerin "gerçek alt gruplara oldukça yakın" olduğunu söyledi. "Ortalıkta başka türden sahte grupların olmadığı yönündeki sezgi buydu." Freiman orijinal eserinde bu ifadenin bir versiyonunu kanıtlamıştı. 1999'da Ruzsa, Freiman teoremini tam sayılardan ikili listelerin ayarına kadar genişletti. kanıtladı içindeki elementlerin sayısı A + A boyutunun sabit bir katıdır A, A bir alt grup içerisinde bulunur.

Ancak Ruzsa'nın teoremi alt grubun çok büyük olmasını gerektiriyordu. Marton'un görüşü, tek bir dev alt grupta yer almak yerine şunu ileri sürmekti: A orijinal kümeden daha büyük olmayan bir alt grubun polinom sayıda kosetinde yer alabilir A.

'Gerçek Bir Fikir Gördüğümde Gerçek Bir Fikir Anlarım'

Milenyumun başında Gowers, Ruzsa'nın Freiman teoreminin ispatlarına, eşit aralıklı sayı dizileri içeren kümelerle ilgili farklı bir problem üzerinde çalışırken rastladı. Gowers, "Belirli bir küme hakkında çok daha gevşek bilgilerden yapısal bilgi elde etme gibi bir şeye ihtiyacım vardı" dedi. "Çok şanslıydım ki çok geçmeden Ruzsa bu muhteşem kanıtı üretti."

Gowers, varsayımın polinom versiyonunun potansiyel bir kanıtını bulmaya başladı. Onun fikri bir setle başlamaktı A toplamı nispeten küçük olan, daha sonra yavaş yavaş manipüle edilen A bir alt gruba ayrılır. Ortaya çıkan alt grubun orijinal kümeye benzer olduğunu kanıtlayabilseydi Akolaylıkla varsayımın doğru olduğu sonucuna varabilirdi. Gowers fikirlerini meslektaşlarıyla paylaştı ama hiç kimse bunları tam bir kanıt haline getiremedi. Gowers'ın stratejisi bazı durumlarda başarılı olsa da bazı durumlarda manipülasyonlar uzun sürdü. A polinom Freiman-Ruzsa varsayımının arzu edilen sonucundan daha da uzaktadır.

Sonunda saha ilerledi. 2012 yılında Sanders'ın PFR'yi neredeyse kanıtladı. Ancak ihtiyaç duyduğu kaydırılmış alt grupların sayısı, çok az da olsa, polinom seviyesinin üzerindeydi. Gowers, "Bunu yaptığında, bu daha az acil bir şey haline geldiği anlamına geliyordu, ancak yine de büyük bir sevgi duyduğum gerçekten güzel bir sorundu" dedi.

Ancak Gowers'ın fikirleri meslektaşlarının anılarında ve sabit disklerinde yaşamaya devam etti. Kendisi de Gowers'ın öğrencisi olan Green, "Orada gerçek bir fikir var" dedi. “Gerçek bir fikir gördüğümde gerçek bir fikir olduğunu anlarım.” Bu yaz Green, Manners ve Tao nihayet Gowers'ın fikirlerini araftan kurtardılar.

Green, Tao ve Manners, Gowers'ın 37 yıllık fikirlerine dönmeyi düşünmeden önce 20 sayfalık bir işbirliği içindeydiler. 23 Haziran'da kâğıtKüçük toplamlı kümelerin yapısını araştırmak için olasılık teorisinden rastgele değişkenler adı verilen bir kavramı başarıyla kullanmışlardı. Grup, bu değişikliği yaparak setlerini daha ustalıkla değiştirebildi. Manners, "Rastgele değişkenlerle uğraşmak, kümelerle uğraşmaktan bir şekilde çok daha az katıdır" dedi. Rastgele bir değişkenle, "Olasılıklardan birini küçük bir miktar değiştirebilirim ve bu bana daha iyi bir rastgele değişken verebilir."

Green, Manners ve Tao, bu olasılıksal bakış açısını kullanarak, bir kümedeki öğelerin sayısıyla çalışmaktan, entropi adı verilen bir nicelik olan rastgele bir değişkenin içerdiği bilginin ölçümüne geçebildiler. Entropi, eklemeli kombinatorik açısından yeni bir şey değildi. Aslında Tao'nun teşebbüs etmişti 2000'li yılların sonlarında kavramı popülerleştirmek için. Ancak henüz hiç kimse bunu polinom Freiman-Ruzsa varsayımında kullanmaya çalışmamıştı. Green, Manners ve Tao bunun güçlü olduğunu keşfettiler. Ama yine de bu varsayımı kanıtlayamadılar.

Grup yeni sonuçların üzerinde düşünürken sonunda Gowers'ın hareketsiz fikirlerinin yeşerebileceği bir ortam oluşturduklarını fark etti. Bir kümenin boyutunu eleman sayısı yerine entropisini kullanarak ölçselerdi, teknik ayrıntılar çok daha iyi sonuç verebilirdi. Tao, "Bir noktada Tim'in 20 yıl önceki bu eski fikirlerinin işe yarama ihtimalinin bizim denediklerimizden daha yüksek olduğunu fark ettik" dedi. “Böylece Tim'i projeye geri getirdik. Ve sonra tüm parçalar şaşırtıcı derecede güzel bir şekilde birbirine uyuyor.

Yine de bir kanıt ortaya çıkmadan önce çözülmesi gereken pek çok ayrıntı vardı. Manners, "Dördümüzün de başka şeylerle inanılmaz derecede meşgul olması biraz aptalcaydı" dedi. "Bu harika sonucu yayınlayıp dünyaya duyurmak istiyorsunuz ama aslında yine de ara sınavlarınızı yazmanız gerekiyor." Sonunda grup başarıya ulaştı ve 9 Kasım'da makalelerini yayınladılar. Eğer kanıtladılar ki A + A şundan daha büyük değil k büyüklüğünün katı A, Daha sonra A yaklaşık olarak daha fazlası tarafından kapsanamaz k¹² daha büyük olmayan bir alt grubun kaymaları A. Bu potansiyel olarak muazzam sayıda vardiyadır. Ama bu bir polinom olduğundan üstel olarak daha hızlı büyümez. k daha da büyüyor sanki k üs içindeydi.

Birkaç gün sonra Tao başladı Kanıtı resmileştirin. Resmileştirme projesini işbirliği içinde yürüttü ve GitHub sürüm kontrol paketini kullanarak katkıları koordine etti. Dünya çapında 25 gönüllü. adlı bir araç kullandılar. Blueprint tarafından geliştirildi Patrick MassotParis-Saclay Üniversitesi'nden bir matematikçi olan Tao'nun söylediklerini tercüme etme çabalarını organize etmek için denilen Bilgisayar koduna “Matematiksel İngilizce”. Blueprint, diğer şeylerin yanı sıra, bir grafik ispatta yer alan çeşitli mantıksal adımları tasvir etmektedir. Tüm baloncuklar Tao'nun "yeşilin güzel tonu" dediği şeyle kaplandığında ekibin işi bitmişti. Çevrimiçi ortamda, gazetede çok küçük birkaç yazım hatası keşfettiler. mesajTao, "projenin matematiksel açıdan en ilginç kısımlarının resmileştirilmesi nispeten kolaydı, ancak en uzun süren teknik 'bariz' adımlardı."

Marton, ünlü varsayımının kanıtlanmasından sadece birkaç yıl önce öldü, ancak kanıtlar onu yansıtıyor hayatın işi Entropi ve bilgi teorisi üzerine. Gowers, "Bu entropi çerçevesinde yaptığınızda, benim yapmaya çalıştığım çerçeveye göre her şey çok daha iyi çalışıyor" dedi. “Bana hâlâ biraz büyülü görünüyor.”

Kuantum izleyicilerimize daha iyi hizmet verebilmek için bir dizi anket yürütüyor. Bizimkini al matematik okuyucu anketi ve ücretsiz kazanmak için girileceksiniz Kuantum ek ürün.