Bu yıla kadar, Kuantum matematiksel kalıplar oluşturmaktan nasıl kaçınılacağına dair çalışma olan Ramsey teorisindeki üç büyük ilerlemeyi kaydetti. bu ilk sonuç {2, 4, 6} veya {21, 31, 41} gibi eşit aralıklı üç sayı içermeyen bir tam sayı kümesinin ne kadar büyük olabileceğine yeni bir sınır koyun. bu ikinci ve üçüncü benzer şekilde, tümü birbirine bağlı veya tümü birbirinden izole edilmiş nokta kümeleri olmadan ağların boyutuna yeni sınırlar koyun.

Kanıtlar, ilgili sayılar sonsuz derecede büyüdükçe ne olduğunu ele alıyor. Paradoksal olarak, bu bazen sinir bozucu gerçek dünya miktarlarıyla uğraşmaktan daha kolay olabilir.

Örneğin, paydası gerçekten büyük olan bir kesirle ilgili iki soruyu ele alalım. Diyelim ki 1/42503312127361'in ondalık açılımının ne olduğunu sorabilirsiniz. Veya payda büyüdükçe bu sayının sıfıra yaklaşıp yaklaşmayacağını sorabilirsiniz. İlk soru, gerçek dünyadaki bir miktar hakkında özel bir sorudur ve hesaplaması, 1/ miktarının nasıl olduğunu soran ikinci sorudan daha zordur.n olarak “asimptotik olarak” değişecektir n büyür. (0'a gittikçe yaklaşır.)

"Bu, tüm Ramsey teorisini rahatsız eden bir sorun," dedi William Gasarch, Maryland Üniversitesi'nde bir bilgisayar bilimcisi. "Ramsey teorisi, asimptotik olarak çok güzel sonuçlara sahip olmasıyla bilinir." Ancak sonsuzdan küçük sayıları analiz etmek, tamamen farklı bir matematiksel araç kutusu gerektirir.

Gasarch, sorunun kaba kuvvetle çözülmesi için çok büyük olan sonlu sayıları içeren Ramsey teorisindeki soruları inceledi. Bir projede, bu yılki atılımların ilkinin sonlu versiyonunu ele aldı - Şubat ayında yayınlanan bir makale Zander Kelley, Illinois Üniversitesi, Urbana-Champaign'de yüksek lisans öğrencisi ve Raghu Meka Kaliforniya Üniversitesi, Los Angeles. Kelley ve Meka, 1 ile XNUMX arasındaki tam sayıların sayısına ilişkin yeni bir üst sınır buldu. N üç terimli ilerlemelerden veya eşit aralıklı sayı kalıplarından kaçınarak bir kümeye koyabilirsiniz.

Kelley ve Meka'nın sonucu, N nispeten küçüktür, bu durumda özellikle yararlı bir sınır vermez. çok küçük değerler için N, çok basit yöntemlere bağlı kalmanız daha iyi. Eğer N 5 diyelim, sadece 1 ile XNUMX arasındaki olası tüm sayı kümelerine bakın. N, ve en büyük ilerlemesiz olanı seçin: {1, 2, 4, 5}.

Ancak farklı olası cevapların sayısı çok hızlı artıyor ve bu kadar basit bir stratejinin uygulanmasını çok zorlaştırıyor. 1 ile 1 arasındaki sayılardan oluşan 20 milyondan fazla set var. 10'dan fazla var⁶⁰ 1 ile 200 arasındaki sayıları kullanarak. Bu durumlar için en iyi ilerlemesiz seti bulmak, verimliliği artıran stratejilerle bile yüksek dozda bilgi işlem gücü gerektirir. "Bir şeylerden çok fazla performans çıkarabilmeniz gerekiyor," dedi James Glenn, Yale Üniversitesi'nde bir bilgisayar bilimcisi. 2008 yılında Gasarch, Glenn ve Clyde Kruskal Maryland Üniversitesi'nin bir program yazdı kadar en büyük ilerlemesiz setleri bulmak için N (Önceki çalışma 187'ye kadar ve 150'ye kadar cevap almıştı.) Glenn, bir dizi numaraya rağmen programlarının tamamlanmasının aylar sürdüğünü söyledi.

Hesaplama yüklerini azaltmak için ekip, programlarının çıkmaz aramalar yapmasını engelleyen basit testler kullandı ve kümelerini ayrı ayrı analiz ettikleri daha küçük parçalara ayırdı.

Gasarch, Glenn ve Kruskal başka stratejiler de denediler. Gelecek vaat eden bir fikir rastgeleliğe dayanıyordu. İlerlemesiz bir küme bulmanın basit bir yolu, kümenize 1 koymak ve ardından her zaman bir aritmetik ilerleme oluşturmayan bir sonraki sayıyı eklemektir. 10 rakamına ulaşana kadar bu prosedürü izleyin ve {1, 2, 4, 5, 10} setini elde edin. Ancak bunun genel olarak en iyi strateji olmadığı ortaya çıktı. "Ya 1'den başlamazsak?" dedi. “Rastgele bir yerden başlarsanız, aslında daha iyisini yaparsınız.” Araştırmacıların rastgeleliğin neden bu kadar yararlı olduğu hakkında hiçbir fikirleri olmadığını da sözlerine ekledi.

Diğer iki yeni Ramsey teorisi sonucunun sonlu versiyonlarını hesaplamak, ilerlemesiz kümelerin boyutunu belirlemekten bile daha can sıkıcıdır. Bu sonuçlar, kenar adı verilen çizgilerle birbirine bağlanan düğümlerden oluşan matematiksel ağlarla (grafikler olarak adlandırılır) ilgilidir. Ramsey numarası r(s, t), bir grafik grubunu dahil etmekten kaçınılması imkansız hale gelmeden önce bir grafiğin sahip olması gereken en küçük düğüm sayısıdır. s bağlı düğümler veya t kopuk olanlar Ramsey sayısını hesaplamak o kadar zor ki, r(5, 5) bilinmiyor — 43 ile 48 arasında bir yerde.

1981 olarak, Brendan McKayArtık Avustralya Ulusal Üniversitesi'nde bir bilgisayar bilimcisi olan nauty, Ramsey sayılarının hesaplanmasını kolaylaştırmayı amaçlayan bir yazılım programı yazdı. Nauty, araştırmacıların birbirlerinin sadece ters çevrilmiş veya döndürülmüş versiyonları olan iki grafiği kontrol ederek zaman kaybetmemelerini sağlar. "Bölgede biri varsa ve donanma kullanmıyorsa oyun biter. kullanmalısın" dedi Stanisław Radziszowski, Rochester Teknoloji Enstitüsü'nde bir matematikçi. Yine de, ilgili hesaplama miktarı neredeyse anlaşılmaz. 2013 yılında Radziszowski ve Jan Goedgebeur Kanıtlandı r(3, 10) en fazla 42. Belçika'daki KU Leuven Üniversitesi'nde bilgisayar bilimcisi olan Goedgebeur, "Sanırım yaklaşık 50 CPU yılı aldı" dedi.

Kesin bir Ramsey sayısı hesaplayamıyorsanız, değerini örneklerle daraltmayı deneyebilirsiniz. Tümü birbirine bağlı beş düğümü ve bağlantısı kesilmiş beş düğümü olmayan 45 düğümlü bir grafik bulursanız, bu şunu kanıtlardı: rRadziszowski, (5, 5) 45'ten büyüktür. Ramsey sayılarını inceleyen matematikçiler, Ramsey grafikleri denen bu örnekleri bulmanın basit olacağını düşünürlerdi. Ama öyle değildi. "Güzel, harika matematiksel yapıların mümkün olan en iyi yapıları vereceğine dair bir beklenti vardı ve bunun üzerinde çalışacak daha fazla insana ihtiyacımız var" dedi. "Hislerim giderek daha fazla kaotik oluyor."

Rastgelelik hem anlamanın önünde bir engel hem de yararlı bir araçtır. Geoffrey ExooIndiana Eyalet Üniversitesi'nde bir bilgisayar bilimcisi olan , Ramsey grafikleri oluşturmak için rastgele yöntemleri geliştirmek için yıllarını harcadı. İçinde 2015 kağıdı Düzinelerce yeni, rekor kıran Ramsey grafiğini duyuran Exoo ve Milos Tatareviç, rastgele grafikler oluşturdu ve ardından bir Ramsey grafiği bulana kadar istenmeyen kümelerin sayısını azaltan kenarlar ekleyerek veya silerek bunları kademeli olarak değiştirdi. Radziszowski, Exoo'nun tekniklerinin her şey kadar bir sanat olduğunu söyledi. Bazen ondan birden çok yöntemi birleştirmesini veya ne tür grafiklerle başlayacağı konusunda yargıda bulunmasını isterler. Radziszowski, "Pek çok insan bunu deniyor ve yapamıyorlar," dedi.

Goedgebeur, Ramsey grafikleri oluşturmak için geliştirilen tekniklerin bir gün daha geniş çapta yararlı olabileceğini söyledi. üzerinde çalıştı kimyasal bileşikleri temsil eden grafikler gibi başka türden grafikler üretmek. Bir e-postada, "Bu tekniklerin, diğer grafik sınıflarını daha verimli bir şekilde (ve tersi) oluşturmaya yardımcı olmak için aktarılabilmesi ve ayarlanabilmesi pek olası değildir" diye yazdı.

Ancak Radziszowski'ye göre küçük Ramsey sayılarını incelemenin nedeni çok daha basit. "Çünkü açık, çünkü kimse cevabın ne olduğunu bilmiyor" dedi. “El ile yaptığımız önemsiz durumlar; biraz daha büyük, bir bilgisayara ihtiyacınız var ve biraz daha büyük, bilgisayar bile yeterince iyi değil. Ve böylece meydan okuma ortaya çıkıyor.